Hidden Number Problem

Hidden Number Problem

hidden number problem (HNP)는 Diffie-Hellman key-exchange protocol의 보안성을 증명하기 위해 처음 소개되었다. HNP는 hidden number가 있다고 할 때, 그 수와 관련된 부분적인 선형 관계(linear relations)를 통해 hidden number를 복구하는 것이 목적이다.

Hidden Number Problem을 정의하면 다음과 같다.

Definition (Hidden Number Problem). Let $p$ be a prime and let $\alpha \in [1, p-1]$ be a secret integer. Recover $\alpha$ given $m$ pairs of integers $\lbrace (t_i, a_i) \rbrace_{i=1}^m$ such that

\[\beta_i - t_i \alpha + a_i = 0 \pmod{p}\]

$p$는 공개된 소수이고, $t_i, a_i$는 공격자가 알 수 있는 값들이다. $\beta_i$는 작은 오차항을 의미하며, $B < p$인 $B$에 대해 $\vert \beta_i \vert < B$를 만족한다. 이러한 정보들이 주어졌을 때 hidden number $\alpha$를 복구하는 것이 목적이다.

위 관계식들을 통해 HNP를 CVP로 해결할 수 있으며 lattice는 다음과 같이 구성된다.

\[\mathbf{B} = \begin{bmatrix} p & & & & \\ & p & & & \\ & & \ddots & & \\ & & & p & \\ t_1 & t_2 & \cdots & t_m & 1/p \\ \end{bmatrix}\]

앞서 HNP의 관계식을 integer $k_i$에 대해 $\beta_i + a_i = t_i \alpha + k_i p$로 다시 표현하면, $x = (k_1, \cdots, k_m, \alpha)$ 와의 linear combination $xB$가 lattice vector $xB = (\beta_1 + a_1, \cdots, \beta_m + a_m, \alpha/p)$를 만들어냄을 알 수 있다. 여기서 $t = (a_1, \cdots, a_m, 0)$, $u = (\beta_1, \cdots, \beta_m, \alpha/p)$로 두면 $xB - t = u$가 성립하며 이때 $u$의 length는 $\sqrt{m+1}B$가 되고 lattice의 determinant는 $p^{m-1}$가 된다. 따라서 $xB$와 $t$는 매우 가까우므로 CVP의 근사를 통해 $u$를 찾아낼 수 있고, $u$의 last entry에 $p$를 곱해줌으로써 hidden number $\alpha$를 찾아낼 수 있다.

이러한 접근법은 Babai’s algorithm과 LLL을 이용하면 이론상 $m = 2 \lceil \sqrt{\log p} \rceil$ 와 오차항의 bound $B \leq p/2^k \text{ where } k = \lceil \sqrt{\log p} \rceil + \lceil \log \log p \rceil$에서 해결할 수 있다. 실제로는 더 느슨한 조건에서도 잘 동작하고 recentering과 같은 최적화도 가능하다.

최근 연구에서는 CVP로 푸는 대신 Kannan’s embedding을 활용한 SVP로 환원해서 푸는 것이 더 낫다고 알려져 있다. 위 lattice에서 Kannan’s embedding을 적용하여 CVP target인 $t = (a_1, \cdots, a_m, 0)$를 row로 embed해서 만든 basis $B^{\prime}$은 다음과 같다.

\[\mathbf{B}^{\prime} = \begin{bmatrix} p & & & & \\ & p & & & \\ & & \ddots & & \\ & & & p & \\ t_1 & t_2 & \cdots & t_m & B/p \\ a_1 & a_2 & \cdots & a_m & & B \\ \end{bmatrix}\]

위 lattice는 $(k_1, \cdots, k_m, \alpha, -1)$ 와의 linear combination으로 short vector $u^{\prime} = (\beta_1, \cdots, \beta_m, \alpha B/p, -B)$를 포함한다. $\lVert u^{\prime} \rVert < \sqrt{m + 2}B$ 이므로 proposition $\lVert b_1 \rVert \leq \left( \frac{2}{\sqrt{4 \delta -1}} \right)^{n-1} \sqrt{n} \cdot \vert \det(\mathcal{L}) \vert^{1/n}$에 의해 LLL-reduced basis로 부터 short vector를 찾을 수 있음을 알 수 있다. 위 $\mathbf{B}^{\prime}$ lattice를 다시 보면 $(-t_1, \cdots, -t_m, p, 0)$와의 linear combination이 우리가 찾는 $u^{\prime}$ 보다 더 짧은 $(0, \cdots, 0, B, 0)$을 만들어 냄을 알 수 있다. 따라서 $u^{\prime}$은 LLL-reduced basis의 2번째 vector로 나올 가능성이 높다.

Example $p=401$ $(t_1, t_2, t_3) = (143, 293, 304)$라고 하자. 이 예시에서는 hidden number $\alpha = 309$를 찾기 위해 HNP를 SVP 접근으로 해결할 것이다. $\beta_i - t_i \alpha + a_i = 0 \pmod{p} \text{ for } i \in \lbrace 1, 2, 3 \rbrace \text{ where } (a_1, a_2, a_3) = (62, 300, 86)$가 주어졌고, $\beta_i < B = 20$이라고 할 때, lattice는 다음과 같다.

\[\mathbf{B} = \begin{bmatrix} p & 0 & 0 & 0 & 0 \\ 0 & p & 0 & 0 & 0 \\ 0 & 0 & p & 0 & 0 \\ t_1 & t_2 & t_3 & \frac{B}{p} & 0 \\ a_1 & a_2 & a_3 & 0 & B \\ \end{bmatrix} = \begin{bmatrix} 401 & 0 & 0 & 0 & 0 \\ 0 & 401 & 0 & 0 & 0 \\ 0 & 0 & 401 & 0 & 0 \\ 143 & 293 & 304 & \frac{20}{401} & 0 \\ 62 & 300 & 86 & 0 & 20 \\ \end{bmatrix}\]

LLL-reduced basis $\mathbf{B}^{\prime}$의 결과는 다음과 같다.

\[\mathbf{B}^{\prime} = \begin{bmatrix} 0 & 0 & 0 & 20 & 0 \\ -15 & -12 & -16 & \frac{1840}{401} & 20 \\ 24 & -5 & -6 & -\frac{1800}{401} & 20 \\ 6 & -42 & -5 & -\frac{1440}{401} & -40 \\ -11 & -1 & 57 & -\frac{3880}{401} & 20 \\ \end{bmatrix}\]

예상했듯이 first vector는 $(0, 0, 0, B, 0)$이다. target lattice vector는 $u = (\beta_1, \beta_2, \beta_3, \alpha B/p, -B)$인데, $-u$ 역시 $u$와 같은 길이를 가지므로 last entry로 $B=-20$ 즉, last entry가 $20$인 vector들도 해가 될 수 있다. second basis vector인 $-u$를 보면 $\beta_i < B \text{ for } i \in \lbrace 1, 2, 3 \rbrace$ 를 만족함을 알 수 있다. 따라서 해당 vector의 second last entry인 $\alpha B/p$에서 $\alpha$를 구하면 $\alpha = - \left( \frac{1840}{401} \right) \cdot \frac{401}{20} \pmod{P} = 309$ 가 된다.