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$를 찾아낼 수 있다.