LWE Problem

LWE Problem ?

---

Learning With Error Problem

동형암호로서 이용될 수 있는 하나의 문제.

가장 큰 틀은 '약간의 오차가 들어간 연립선형방정식의 해를 구하라'이다.

문제의 어려움

---

암호로서 이용할 수 있기 위해서는 사용자의 정보를 안전하게 보호할 수 있는가가 가장 중요한 요소이다.

일반적인 연립선형방정식과 오차가 들어간 연립선형방정식의 해를 구하는 과정을 비교해보도록 하자.

• 일반적인 연립선형방정식

위와 같은 연립선형방정식이 있다고 가정하자. 위의 연립방정식을 해결하기 위해서는 어느정도의 시간이 필요할까?

이러한 연립선형방정식을 해결하는 알고리즘은 가우스 소거법, 가우스-조던 소거법 등이 있다.

위의 두 알고리즘은 크게 $O(n^3)$ 의 시간복잡도를 갖는다.

즉, $\vec{S}$를 구하기에 어렵지 않을 것이다.

• 약간의 오차가 들어간 연립선형방정식

연립선형방정식에 약간의 오차가 들어간 경우를 확인해보자.

위와 같은 연립선형방정식의 해를 구하기 위해서는 어느정도의 시간이 필요할까?

이 상황에서는 추가적인 변수 $e$가 들어왔기 때문에 $e$를 유추해내기 위한 별도의 연산이 필요로해진다.

이 때 $e$의 스펙트럼이 중요한 요소로 반영 될 것이다.

예를 들어 10가지의 $e$가 있으며, n개의 방정식이 있다고 하자.

이때, 각 방정식의 $e$를 유추해내어 가우스소거법을 진행해야하기 때문에 $O(n^310^{n}) = O(10^{n})$ 이 될 것이다.

단순히 오류를 첨가하는 것 만으로도 해를 구하기 위해 상당히 많은 연산이 필요로 하다는 것을 확인할 수 있었다.

위의 예시에서는 브루트포스적인 접근방식으로 해결하고자 했으나 수학적으로 타당한 다양한 방법들이 존재할 수 있다.

LWE Problem은 위와 같이 연립선형방정식의 약간의 오차를 더하여 $\vec{S}$를 모를 경우, 해를 구하기에 상당히 어려운 문제라는 것을 알 수 있다.

암호로서 활용 방안

---

LWE Problem을 어떤식으로 암호로서 활용할 수 있는가?

우리가 보내고자 하는 메세지인 $M$이 있다고 하자. 이 때, LWE을 이용하여 $M$을 암호화한다고 하면 다음과 같이 표현할 수 있다.

여기서 $\vec{s}$를 모르는 공격자의 경우에는 앞서 서술했듯이 상당한 연산을 거쳐야만 $M$을 구할 수 있을 것이다.

그러나 $\vec{s}$를 아는 사용자의 경우에는 비교적 쉽게 값을 구해낼 수 있다.

그러나 여기서 알 수 있듯이 사용자도 $M+e_i$값을 알 수 있으며, 이는 확인하고자 하는 $M$이 아니다. 여기서 이 임의의 오류 $e_i$를 찾아내기 위해 약간의 기술이 필요하다.

• 벡터공간 $Z_q^n$모든 원소를 추출한다.
• 비트를 기준으로 $M$이 1일 때 어떠한 큰 수 $q/2$를 더해준다.

여기서 1에 $q/2$를 더해주는 것이 암호의 어떠한 경향성을 보이도록 하지 않을까 하는 의문이 있다.
결과적으로 말하자면 위의 LWE Problem은 $Z_q$공간에서 이루어지기 때문에 어떠한 값을 더해준다 한들 경향성을 보이는 경우는 없다.

위의 조건을 토대로 복호화를 진행하면 다음과 같은 결과를 얻을 수 있을 것이다.

즉, 우리는 $M$과 $e_i$에 비해 비교적 큰값 $q/2$를 기준으로 어느정도 오차가 있더라도 값을 $M$의 값을 유추해 낼 수 있을 것이다.

예제

c++ 을 이용하여 LWE Problem을 활용한 암호화, 복호화 예제를 작성해보았다.

/* q = 112, n = 10 */
#include <iostream>
#include <cstdlib>
#include <ctime>
#define _q 112
#define _n 10
using namespace std;

int temp[3] = {-1, 0, 1};
int sk[_n];
int a[_n][_n];
int err[_n];
int EncMessage[_n];
int Message[_n];
int DecMessage[_n];

void printEncMessage(){
    cout << "Enc Message : " << "\n";
    for(int i=0; i<_n; i++){
        cout << EncMessage[i] << " ";
    }
    cout  << "\n\n";
}

void printSecretKey(){
    cout << "SecretKey : " << "\n";
    for(int i=0; i<_n; i++){
        cout << sk[i] << " ";
    }
    cout  << "\n\n";
}

void printMatrix(){
    cout << "--- Matrix ---" << "\n";
    for(int i=0; i<_n; i++){
        for(int j=0; j<_n; j++){
            if(j != _n-1){
                cout << a[i][j] << "S" << i << " + ";
            }else{
                cout << a[i][j] << "S" << i << "\n";
            }
        }
    }
    cout << "\n\n";
}

void printDecMessage(){
    cout << "DecMessage : " << "\n";
    for(int i=0; i<_n; i++){
        cout << DecMessage[i] << " ";
    }
    cout  << "\n\n";
}

void printInputData(){
    cout << "input data (bit) : ";
    for(int i=0; i<_n; i++){
        cout << Message[i] << " ";
    }
    cout << "\n\n";
}

void initMessage(){
    /*<--- 무작위 이진수 추출 -->*/
    for(int i=0; i<_n; i++){
        Message[i] = rand() % 2;
    }
}

void Encryption(){
    for(int i=0; i<_n; i++){
        for(int j=0; j<_n; j++){
            /* <-- 무작위 a벡터 추출 -->*/
            a[i][j] = rand() % _q;
        }
        /* <-- 무작위 err값 및 무작위 Secret Key 추출 -->*/
        /* err의 경우 -1, 0, 1 중 하나 */
        err[i] = temp[rand()%3];
        sk[i] = rand() % _q;
    }

    for(int i=0; i<_n; i++){
        int tempNum;
        
        /* 
            비트가 1일 경우 m + <a,s> + e + [q/2]
            비트가 0일 경우 m + <a,s> + e
        */

        /* <-- 비트가 1일 경우 --> */
        if(Message[i] == 1){
            tempNum = 1;
            for(int j=0; j<_n; j++){
                /* <-- <a,s> 값 계산 --> */
                tempNum += a[i][j] * sk[j] % _q;
            }
            /*<-- + e + [q/2] -->*/
            tempNum += (err[i] + (_q/2));
            tempNum = tempNum % _q;
            EncMessage[i] = tempNum;
        }else{
            tempNum = 0;
            for(int j=0; j<_n; j++){
                /* <-- <a,s> 값 계산 --> */
                tempNum += a[i][j] * sk[j] % _q;
            }
            /*<-- + e -->*/
            tempNum += err[i];
            tempNum = tempNum % _q;
            EncMessage[i] = tempNum;
        }

    }
}

void Decryption(){
    for(int i=0; i<_n; i++){
        int tempNum = 0;

        for(int j=0; j<_n; j++){
            /* <-- 사용자는 secret Key를 알고있으니 이를 통해 <a,s>를 쉽게 구함 --> */
            tempNum += a[i][j] * sk[j];
        }
        tempNum = tempNum % _q;

        /* LWE(m) - <a,s> = m + e ---> tempNum */
        tempNum = (EncMessage[i] - tempNum) % _q;
        /* 음수가 나올수도 있어 절댓값 */
        if(tempNum < 0){
            tempNum *= -1;
        }

        /* 
            [q/2] 보다 tempNum = m + e 가 0에 가까울 경우 m은 0,
            그 외에 m은 1
        */
        if(_q/4 > tempNum){
            cout << "Value : " << tempNum << " ---> 0\n";
            DecMessage[i] = 0; 
        }else{
            cout << "Value : " << tempNum << " ---> 1\n";
            DecMessage[i] = 1; 
        }
    }
    cout << "\n";
}

int main(){

    srand((unsigned int) time(NULL));

    initMessage();
    Encryption();

    printInputData();
    printEncMessage();

    cout << "<--- decryption Start --->\n\n";

    /* decryption Start */
    Decryption();
    printDecMessage();

    return 0;
}