암호론 논문 리딩 #1: Blum-Blum-Shub PRNG (2)

#7: The $x^2 \pmod N$ generator is unpredictable.

우선 $P, Q$가 서로 다른 $3 \pmod {4}$ 소수라 하고, $N=PQ$라 하자. 여기서 우리는 $N$과 서로소인 quadratic residue만을 다루겠다. 

$QR_N$을 $N$과 서로소인 $N$의 이차잉여들의 집합이라 하자. $QR_N$의 집합의 크기가 $\phi(N)/4$임은 자명하다. 

간단한 정수론으로, 다음 사실들을 쉽게 증명할 수 있다. 증명은 기초적이므로 생략한다.

Fact 1: 각 quadratic residue는 총 4개의 서로 다른 discrete square root를 가진다.

Fact 2: 4개의 서로 다른 discrete square root 중, 정확히 하나가 quadratic residue가 된다.

Fact 3: 여기서 우리는 $x \rightarrow x^2 \pmod{N}$이 $QR_N$에서 $QR_N$으로 가는 전단사함수임을 알 수 있다.

이제 $x_0 \in QR_N$, $x_{i+1} = x^2_i \pmod{N}$, $b_i = x_i \pmod{2}$라 할 때, 우리가 무엇을 할 수 있는지 생각해보자.

Fact 1: $N$을 알고, $x_0$를 알면, 빠르게 $x_1, x_2, \cdots $와 $b_1, b_2, \cdots$를 계산할 수 있다. 자명하다.

Fact 2: $N$의 소인수분해를 알고 $x_k$를 알면, 빠르게 $x_{k-1}, x_{k-2}, \cdots$와 $b_k , b_{k-1}, \cdots$를 알 수 있다.

이는 discrete square root를 계산하는 것이 어렵지 않기 때문이다. Tonelli-Shanks를 생각해도 되고, 애초에 $3 \pmod{4}$ 소수를 다루니 그냥 단순하게 계산할 수도 있다. 이제 CRT를 덮어주면 계산을 다항식 시간에 충분히 할 수 있을 것이다. 어렵지 않은 이야기.

Fact 3: $x_k$를 알 때 $x_{k-1}, x_{k-2} , \cdots$를 계산하는 것은 $N$의 소인수분해를 찾는 것 이상으로 어렵다. 

강력한 사실이다. 이걸 보이기 위해서는, $x_k$를 알 때 $x_{k-1}$을 쉽게 계산할 수 있다면 $N$의 소인수분해 역시 쉽게 계산할 수 있음을 보이면 충분하다. $N$에 대한 Jacobi Symbol의 값이 $-1$인 $x$를 하나 잡고, $y \equiv x^2 \pmod {N}$을 생각하자. 이제 $y$를 기준으로 역추적을 하면, $x'^2 \equiv y \pmod{N}$인 이차잉여 $x'$을 얻을 수 있을 것이다. 이제 $x'+x$와 $N$ 사이의 최대공약수를 찾아서 $N$을 소인수분해할 수 있다.

그런데 사실 우리의 진짜 목표는 $x_i$들이 아니라 그들의 parity인 $b_i$들이다. 

$x_i$라는 정보들이 우리에게 $b_i$를 역추적/예측을 하는데 있어서 얼마나 도움을 줄까? 이를 엄밀하게 정의할 필요가 있다.

다항식 $f$를 고정하고, $0 < \epsilon \le 1/2$인 실수 $\epsilon$를 고정하자. 다항시간에 작동하는 확률적 알고리즘이 $N$에 대하여 $x_0 \in QR_N$가 주어졌을 때 $x_{-1}$의 parity를 guessing 하는데 $\epsilon$-advantage가 있다는 것은, $\frac{\sum_{x_0 \in QR_N} P(\text{correct})}{\phi(N)/4} \ge \frac{1}{2} + \epsilon$이라는 것이다. 여기서 $P(\text{correct})$란, $x_0$가 input으로 주어졌을 때 $x_{-1}$의 parity를 성공적으로 출력할 확률이다. 비슷한 방식으로, $x_0$가 주어졌을 때 $x_0$가 quadratic residue인지 guessing 하는데 $\epsilon$-advantage가 있다는 것이 무엇인지를 정의할 수 있다. 여기서 주의할 점이 있는데, Jacobi Symbol을 활용하여 이차잉여가 아닌 값들 일부를 다항시간에 분류할 수 있다. quadratic residue에 대한 $\epsilon$-advantage를 정의할 때는, Jacobi Symbol의 값이 $1$인 원소가 주어졌을 때 이 값이 quadratic residue인지 판별하는 문제를 생각한다. 당연하지만, Jacobi Symbol이 $1$인 원소 중 정확히 절반이 quadratic residue다. 그러니 위 정의와 비슷한 정의를 그대로 가져다가 쓸 수 있겠다. 분모만 $\phi(N)/2$로 바꾸면 된다.

이제 다음을 순서대로 증명한다. 아이디어가 확실히 느낌 있다.

Step 1: $\epsilon$-advantage for guessing parity can be converted to $\epsilon$-advantage for guessing quadratic residuosity

Step 2: $\epsilon$-advantage for guessing QR can be amplified to a $1/2-\epsilon$-advantage for guessing QR

이 시점에서 우리는 $\epsilon$-advantage가 있다면 QRP의 난이도에 대한 우리의 가정에 모순이 발생함을 얻는다.

즉, $N$의 소인수분해를 모르는 시점에서 우리는 $\epsilon$-advantage 조차 얻을 수 없다. 그냥 동전 던지라는 거다.

Step 1: $x$가 Jacobi Symbol $1$을 갖는 원소라고 하자. 우리의 목표는 $x$가 quadratic residue인지 판별하는 것이다.

$x_0 = x^2 \pmod{N}$이라 하면, $x_0$의 discrete square root 중 Jacobi Symbol $1$을 갖는 것은 $x$와 $N-x$다. 

$N$이 홀수이므로, 두 값은 다른 parity를 갖는다. 그러니 parity를 잘 찍는 것과 quadratic residue를 잘 찍는 것은 동치다.

 

Step 2: 통계학에 가깝다. 그냥 테스트를 반복해서 적용하면 된다. 실제로 서술하는 것은 꽤 까다로울 듯.

내 이해가 맞다면 Step 2가 없어도 어쨌든 QRP의 난이도에 대한 가정에 모순이 발생할 것이다. 

이제 $x_0$ 하나를 가지고 $x_{-1}$의 parity를 보는 것에 대한 논의가 끝났다. 이제 진짜 우리가 다루고자 하는 것을 보자.

$b_1, b_2, b_3, \cdots b_k$를 알고 있을 때, $b_0$를 높은 확률로 결정할 수 있을까? 다시 엄밀하게 정의를 하자.

Predictor $P$는 $N$과 $b_1b_2 \cdots b_k$를 (단, $k$는 $|N|$에 대한 다항식에 bound 된다) 입력 받아서, $0$ 또는 $1$을 출력하는 확률적 알고리즘이다. $P$가 $\epsilon$-advantage가 있다는 것은, 적당한 $k \le \operatorname{poly}(|N|)$이 있어 $x \in QR_N$에 대하여 $b_i(x)$를 $x^{2^i} \pmod {N}$의 parity라 할 때, $b_1(x), b_2(x), \cdots b_k(x)$와 $N$을 input으로 받아서 predictor가 $b_0(x)$를 출력할 평균적인 확률이 (모든 $x$를 고려했을 때) $\frac{1}{2} + \epsilon$ 이상이라는 것이다. 

말이 많지만, 어쨌든 위에서 다룬 $\epsilon$-advantage와 큰 그림의 차이는 없다. 목표는 역시 $\epsilon$-advantage가 없다는 것이다.

증명은 어렵지 않다. $x_0 \in QR_N$을 잡은 다음 $x_0x_1 \cdots x_k$를 predictor에게 주자.

그러면 이 predictor는 $x_{-1}$의 parity를 줘야 하는데, 이건 앞에서 불가능하다고 설명했다.

직관적으로도 크게 받아들이기 힘든 내용은 아니라고 생각한다. $x$와 $x^2 \pmod{N}$ 사이의 one-way 느낌을 잘 써먹는 것 같다.

next-bit test를 통과하면 모든 polynomial statistical test를 통과함이 잘 알려져 있다. 

여기서는 증명까지 제시하는 것 같은데, 통계학이 꽤 필요한 것 같아서 잠시 남긴다. 직관적으로 이해 불가능하지는 않은듯.

생각을 해보면, 우리는 $x^2 \pmod{N}$에서 (가장 작은) 비트 하나씩을 PRNG에 써먹고 있다.

비트를 여러 개 PRNG에 넣는 것은 어떨까? 그러면 효율은 꽤 좋아질 것이다. 이 질문은 2005년에 답이 나온 것 같다.

일단 결론만 말하자면, $\mathcal{O}(\log \log N)$개의 비트까지는 뽑아도 된다고 한다. 얘는 나중에 읽는 걸로.

가뜩이나 비효율적인 알고리즘으로 평가받는 Blum-Blum-Shub의 성능을 조금이나마 높일 수 있는 좋은 질문거리다.

#8: Lengths of periods of sequences produced by the $x^2 \pmod N$ generator

이제 이 generator를 제대로 써먹으려면 실제로 어떤 성질을 가지는 수열이 생성되는지 탐구할 필요가 있다.

일단 처음으로 볼 내용은 역시 주기성이다. 주기의 길이가 길었으면 좋겠는게 우리의 마음이니, 이를 위해서 $P, Q, x_0$를 어떻게 잡으면 좋을지 생각해보자.

(주기가 있는 점은 자명한 것이, $x \rightarrow x^2$이 $QR_N$에서 $QR_N$으로 가는 전단사함수다)

$x_0 \in QR_N$에 대하여, $\pi (x_0)$을 수열 $x_i = x^{2^i}_0 \pmod N$의 주기라고 정의하자.

$\lambda$를 Carmichael의 $\lambda$ 함수라 하자. 처음으로 보일 사실은 $\pi (x_0) | \lambda ( \lambda (N))$이다.

증명 (Sketch): 먼저 $\operatorname{ord}_N x$를 $x$의 $\pmod{N}$에서의 order라고 정의하자.

$x \in QR_N$이면 $\operatorname{ord}_N x$는 홀수임을 보인다. 그러니 $2^{\lambda (\operatorname{ord}_N x_0)} \equiv 1 \pmod{ \operatorname{ord}_N x_0}$다.

한편, $\pi (x_0)$는 $2^{\pi (x_0)} \equiv 1 \pmod{ \operatorname{ord}_N x_0}$를 만족하는 최소의 자연수다. 그러니 $\pi (x_0) | \lambda (\operatorname{ord}_N x_0)$를 만족해야 하고, $\operatorname{ord}_N x_0 | \lambda(N)$이다.

$a|b$면 $\lambda (a) | \lambda (b)$가 성립한다. 그러므로 $\pi (x_0) | \lambda (\lambda (N))$을 얻고 증명 종료.

전부 Carmichael 함수와 order에 대한 기초적 지식이 있으면 쉽게 증명할 수 있는 사실들이다.

자연스럽게 우리의 목표는 주기를 $\lambda ( \lambda (N))$로 만들고, 이 값을 크게 하는 것이다. 가능하다.

$N$을 잡되, $\operatorname{ord}_{\lambda(N)/2} (2) = \lambda ( \lambda(N))$이 성립하도록 한다.

$x_0 \in QR_N$을 잡되, $\operatorname{ord}_N (x_0) = \lambda(N)/2$가 성립하도록 한다. 이때 $\lambda (\lambda( N)) = \pi (x_0)$가 성립한다.

증명 (Sketch): 위의 증명을 따라가면 큰 차이없이 증명을 할 수 있다.

$\pi (x_0)$는 $2^{\pi (x_0)} \equiv 1 \pmod {\operatorname{ord}_N (x_0)}$를 만족하는 최소의 자연수다.

그런데 $\operatorname{ord}_N (x_0) = \lambda(N)/2$가 성립한다. 

그러니 $\pi (x_0) = \operatorname{ord}_{\lambda(N)/2} (2) = \lambda (\lambda (N))$이 성립해 증명이 끝난다.

문제는 저런 $N$과 $x_0$를 잘 잡을 수 있겠냐는 것이다. 이것 역시 가능하다. 먼저 $N$에 대한 논의를 하자.

소수 $P$가 좋다는 것은, $P = 2P_1+1$, $P_1 = 2P_2 + 1$이라 썼을 때 $P_1, P_2$ 역시 홀수 소수라는 것이다.

$N = PQ$가 좋다는 것은, $P, Q$가 서로 다른 홀수 소수고 $P, Q$가 모두 좋은 소수라는 것이다.

$N = PQ$가 좋은 수고, $2$가 $P_1$, $Q_1$ 중 최대 하나의 이차잉여일 때, $\operatorname{ord}_{\lambda(N)/2} (2) = \lambda ( \lambda (N))$이 된다.

증명 (Sktech): 역시 어렵지 않다. 우선 $\lambda (N) = 2 P_1 Q_1$이므로, $\lambda(N)/2 = P_1 Q_1$이다.

이제 $\operatorname{ord}_{P_1 Q_1} (2)$를 봐야하는데, 이는 $\operatorname{ord}_{P_1} (2)$와 $\operatorname{ord}_{Q_1} (2)$의 최소공배수다. 

$\operatorname{ord}_{P_1} (2)$는 $P_2$거나 $2P_2$임이 자명하다. 정확하게는, $2$가 $P_1$의 이차잉여라면 $P_2$고 아니면 $2P_2$다.

마찬가지로, $\operatorname{ord}_{Q_1}(2)$는 $Q_2$거나 $2Q_2$임이 자명하다. 정확하게는, $2$가 $Q_1$의 이차잉여라면 $Q_2$이고 아니면 $2Q_2$이다.

그러니 $2$가 $P_1$, $Q_1$ 중 최대 하나의 이차잉여라면, 두 $\operatorname{ord}$ 값의 최소공배수는 $2P_2Q_2$가 된다.

그런데 $\lambda ( \lambda (N)) = \lambda (2P_1Q_1) = 2P_2Q_2$가 되므로 증명이 끝난다. 

이런 $N$이 무한함을 증명하는 것은 어려운 일이지만, 우리는 어쨌든 저 조건을 만족하는 $N$을 찾기만 하면 된다.

또한, 이러한 $N$을 확률적 알고리즘으로 다항시간에 찾는 것은 충분히 가능하다고 생각하는 것이 reasonable하다. 

대충 $P, P_1, P_2$가 소수인 사건이 독립적이라는 가정을 하고 생각을 하면 될 것이다.

이제 $x_0$에 대한 논의를 하자. 얘는 어렵지 않다. 위수 $\lambda (N)$을 갖는 원소를 찾은 뒤 이를 제곱하면 된다.

위수가 $\lambda (N)$인 원소를 찾으려면, $P, Q$ 각각에 대한 원시근을 잡은 뒤 CRT를 사용하면 된다.

$P, Q$의 원시근의 개수는 각각 $\phi (P-1)$, $\phi(Q-1)$이고 이들은 상당히 큰 수들이다. 

예를 들어, $\phi (x) > \frac{x}{6 \log \log x}$임이 알려져 있다. 그러니 이를 통해서 $x_0$를 잡는 것이 어렵지 않음을 알 수 있다.

애초에 위 방식대로 $N$을 구축한다면, 원시근 여부를 판정하는 것도 빠르게 할 수 있다. 이미 $P-1$, $Q-1$의 소인수분해를 알기 때문이다.

그러니 $x_0$도 적당히 잡을 수 있고, 우리는 매우 큰 주기를 갖도록 수열을 생성할 수 있다. 

이제 문제는 우리가 실제로 써먹는 값은 parity이므로, 실제 주기를 알려면 $b_0, b_1, \cdots $의 주기와 $x_0 , x_1 , \cdots$의 주기 사이의 관계를 알아야 한다는 것이다. 

하지만 이 부분은 이 논문에서는 open problem으로 나와있다. 아직 관련 문헌은 찾지 못했다.

#9: Algorithms for determining length of period and random accessing

주기에 대한 이야기를 계속한다. 여기서 우리의 목적은 $x_0$가 주어졌을 때 $\pi (x_0)$를 계산하고, $x_i$를 효율적으로 계산하는 것이다.

여기서는 $N = P \cdot Q$이고, $P, Q$는 서로 다른 $3 \pmod {4}$ 소수라고 가정한다.

$N, \lambda (N) , \lambda (\lambda (N))$과 $\lambda ( \lambda (N))$의 소인수분해를 안다면, $\pi (x_0)$를 효율적으로 계산할 수 있다.

위수를 빠르게 계산하는 일반적인 방법을 그대로 적용할 수 있기 때문이다. 

정확하게 말하자면, $(x_0)^{2^{\lambda (\lambda(N))/d} \pmod {\lambda(N)}} \pmod {N} \equiv x_0 \pmod{N}$인 최대의 $d| \lambda (\lambda(N))$을 찾으면 된다.

$\lambda (\lambda(N))$의 소인수분해를 알고 있으니, 소인수를 하나씩 지워보는 방식으로 빠르게 $d$를 찾을 수 있다.

또한, $N, \lambda (N)$을 알면 $x_i$ 역시 binary exponentiation을 활용하여 빠르게 계산할 수 있다. 이는 자명하다.

또한, $N, \lambda (N)$을 알면 $x_{-i}$ 역시 빠르게 계산할 수 있다. $N$을 소인수분해할 수 있다면, 답을 $P, Q$에 대해서 각각 계산한 뒤 이를 CRT로 합치면 된다. 

각 소인수에 대해서 답을 계산하는 것은 $\pm x^{(P+1)/4}$가 $x$의 discrete square root임을 이용하면 계산할 수 있다. 

이제 $N$을 소인수분해하는 것이 문제가 된다. 이는 Miller-Rabin이 탄생한 논문에서 그 방식이 설명되어 있다. 

먼저 $a$의 Jacobi Symbol 값이 $-1$인 $1 < a < N$을 하나 잡자. 

그러면 $a$가 $P ,Q$ 중 하나에 대해서는 이차잉여고, 하나에 대해서는 비이차잉여가 된다.

이제 $a^{\lambda(N)/2}$를 계산해보자. 이는 $a$가 $P$의 이차잉여면 $1 \pmod {P}$고, 비이차잉여면 $-1 \pmod {P}$다.

마찬가지로, $a$가 $Q$의 이차잉여면 $1 \pmod {Q}$고, 비이차잉여면 $-1 \pmod {Q}$다. 이제 끝났다.

단순히 $a^{\lambda(N)/2} - 1 \pmod {N}$과 $N$ 사이의 최대공약수를 취하면 된다. 이는 $\lambda (N)$을 알고 있으니 할 수 있다.

반대로, $x_0$에 대해서 $\pi (x_0)$를 알려주고, 각 $i$에 대해 $x_i$를 효율적으로 계산해주는 oracle이 있다면, $N$을 소인수분해 할 수 있다. 

Jacobi Symbol 값이 $-1$인 $y$를 하나 랜덤하게 찾자. 이제 $x_0 = y^2 \pmod{N}$을 잡자.

oracle을 불러서, $\pi (x_0)$의 값을 계산하자. 그 후, 다시 oracle을 불러서 $z = x_{\pi(x_0) - 1}$를 계산하자.

이는 $z^2 \equiv x_0 \pmod {N}$을 만족함이 자명하다. 또한, $z \in QR_N$임 역시 자명하다.

그러니 $y+z$와 $N$의 최대공약수를 취하면 $P$ 또는 $Q$가 계산된다. 증명 끝. 아이디어 참 좋다.

#10: Applications

우선 $1/P$ generator의 쓸모를 보자. de Bruijn sequence를 생성했다는 점도 꽤 흥미로운 점임은 분명하다.

논문에서는 길이 $2|P|_b+1$의 부분수열로는 $P$를 복원할 수 있으나, 길이 $|P|_b-1$의 부분수열로는 $P$에 대한 아무런 정보를 얻지 못한다는 점에 집중했다.

길이 $2|P|_b+1$의 부분수열을 반으로 쪼개서 두 사람에게 주면, 각 사람은 $P$를 복원할 수 없으나 협력하면 $P$를 복원할 수 있다.

이 점은 꽤 암호학적으로 쓸모가 있는 것 같다. shift-register sequence과도 큰 관계가 있다고 한다.

LCG와는 분명히 관계가 있을 것 같은데 LFSR이 등장하는 배경은 잘 모르겠다. 이건 물어봐야 할 듯.

$x^2 \pmod N$ generator는 공개키 암호에 사용할 수 있다. Encryption/Decryption Scheme을 다음과 같이 생각해보자.

Alice는 $N_A = P_A \cdot Q_A$를 공개키로 설정한다. 단, $P_A, Q_A$는 서로 다른 $3 \pmod {4}$ 소수이며, $|P_A| = |Q_A|$다.

물론, Alice는 $P_A$와 $Q_A$ 자체는 비밀로 한다. 이제 Bob은 $k$-bit 메세지 $(m_1, m_2, \cdots , m_k)$를 Alice에게 보내고 싶다.

단, $k$는 $|N_A|$에 대한 다항식에 bound 된다. 이제 Encryption을 위해서, Bob은 공개키 $N_A$를 활용한 one-time pad를 구축한다.

$x_1 \in QR_{N_A}$를 하나 뽑고 (원소 하나 잡고 제곱하면 된다) $(N_A, x_1)$을 seed로 하는 $x^2 \pmod N$ generator를 이용하여, $b_1, b_2, \cdots b_k$를 생성한다.

이제 Bob은 $(m_1 \oplus b_1, m_2 \oplus b_2, \cdots m_k \oplus b_k)$와 함께 $x_{k+1}$의 값을 Alice에게 보낸다.

Alice는 $N_A$의 소인수분해를 들고 있으니, $x_{k+1}$을 기반으로 $x_1, x_2, \cdots x_k$를 계산할 수 있다.

이를 이용하여 $b_1, b_2, \cdots b_k$를 계산하고, 다시 원래 메세지인 $(m_1, m_2, \cdots m_k)$를 얻는다.

이 복원과정을 하려면 $N$의 소인수분해를 들고 있어야 함은 앞서 한 QRP의 난이도에 대한 가정에 의해 성립한다.

  

실제로, $N_A$의 소인수분해를 모르는 사람이 $b_1, b_2, \cdots b_k$ 중 하나의 비트를 정확하게 guess 하는데 $\epsilon$-advantage가 있다고 하자.

그러면 이를 활용하여 QRP에 대한 $\epsilon$-advantage를 얻을 수 있다. 아이디어는 위에서 다룬 것과 비슷하다. 

Jacobi Symbol의 값이 $1$인 $x$를 하나 잡자. $1 \le l \le k$를 하나 랜덤하게 잡고, $x_{l+1} = x^2 \pmod {N_A}$이라 하자.

이를 기반으로, $x_{k+1}$까지 계산을 하자. 그 후, $N_A$과 $x_{k+1}$을 주고 비트 하나를 $\epsilon$-advantage를 가지고 guess 하게 하자. 

그러면 $l$번째 bit에 대한 parity를 줄 확률이 $1/k$가 된다. 실제로 $l$번째 bit를 guess 할 때까지 계속 이 과정을 반복하자.

이제 $l$번째 bit를 guess 했다고 하자. 만약 $l$번째 bit가 $x$의 parity와 같다면 $x$가 이차잉여라고 답하면 된다. 

아니면 $x$가 비이차잉여라고 답하면 된다. 이제 이를 통해서 QRP 문제에 대한 $\epsilon$-advantage를 얻을 수 있다. 증명 끝.

그러니 QRP의 난이도에 대한 가정이 참이라면, 이 Encryption은 상당히 안전하다.

$x^2 \pmod N$ generator를 이용하여 randomness를 amplify하는 접근도 소개하고 있다.

또한, 짧은 시드로 매우 긴 random sequence를 제작할 수 있다는 면에서 강점이 있다고 한다.

확실히 아는 게 많을수록 다루기 쉬운 sequence라는 점에서 좋은 점이 많은 것 같다.

애초에 이 논문을 읽은 목적이 blum-blum-shub PRNG를 깨는게 소인수분해만큼 어렵다는 증명을 배우기 위해서였다.

QRP 문제는 매우 어렵다고 여겨지지만, 소인수분해만큼 어려운지는 아직 알려지지 않았다고 한다.

실제로 이 증명을 보려면 후속 논문을 읽어야 할 것 같다. 일단 다음에 읽고 싶은 논문은 RSA에 대한 review paper와, Even-Mansour Scheme에 대한 논문이다.