LO & CJLOSS

Knapsack Problem

Knapsack Problem는 NP-complete로 subset sum problem 으로 많이 알려져 있다. 이번에는 modular subset sum problem과 일반화된 문제에 대해 살펴볼 것이다.

Low-density Subset Sum Problems

Definition (Subset Sum Problem). positive integers $a_1, \cdots, a_n$ (the weights)와 target integer $s$가 있다고 할 때 합이 $s$가 되도록 하는 $a_i$의 부분집합을 찾는 문제이다. 즉, 다음을 만족하는 $e_1, \cdots, e_n$ with $e_i \in \lbrace 0, 1 \rbrace$을 찾는 문제.

\[\sum_{i=1}^n e_i a_i = s\]

subset sum problem을 기반으로 하는 많은 cryptosystems이 “low-density” subset sum problem을 해결하는 알고리즘으로 인해 안전하지 않음이 밝혀졌다. weights $a_1, \cdots, a_n$ 집합의 density는 다음과 같이 정의된다.

\[d = \frac{n}{\log_2 \max(a_i)}\]

LO algorithm은 $d<0.6463$인 subset sum problem을 SVP oracle로 해결할 수 있다. CJLOSS algorithm은 LO를 조금 변형한 알고리즘으로 bound를 $d<0.9408$까지 개선하였다. 두 알고리즘 모두 lattice reduction을 기반으로 해결한다.

lattice를 구성하는 방식은 $e_i$ ($\in \lbrace 0, 1 \rbrace$)가 short vector가 되도록 encoding 하는 것이다. LO algorithm에서의 격자 구성은 다음과 같다.

\[B = \begin{bmatrix} 1 & & & & a_1 \\ & 1 & & & a_2 \\ & & \ddots & & \vdots \\ & & & 1 & a_n \\ & & & & s \end{bmatrix}\]

$t = (e_1, \cdots, e_n, -1)$라 할 때 linear combination $tB$는 short vector $x_1 = (e_1, \cdots, e_n, 0)$을 만들어낸다. 따라서 위 격자에 lattice reduction을 함으로써 $e_i$를 찾아낼 수 있다.

CJLOSS algorithm은 lattice를 조금 변형하여 아래와 같이 구성한다.

\[\mathbf{B}' = \begin{bmatrix} 1 & & & & N a_1 \\ & 1 & & & N a_2 \\ & & \ddots & & \vdots \\ & & & 1 & N a_n \\ \frac{1}{2} & \frac{1}{2} & \cdots & \frac{1}{2} & N s \end{bmatrix}\]

여기서 $N$은 $N > \sqrt{n}$인 정수이다. 여기서도 마찬가지로 $t = (e_1, \cdots, e_n, -1)$와 linear combination을 하면 vector $x_2 = (e_1 - \frac{1}{2}, \cdots, e_n - \frac{1}{2}, 0)$을 만들어내는데, 이때 $x_2$의 norm은 항상 $\lVert x_2 \rVert = \frac{1}{2}\sqrt{n}$이 된다.

Coster et al. (CJLOSS)의 분석에 따르면 $x_2$가 격자 내 유일한 최단 벡터가 아닐 확률 $P$의 상한에 대해 다음과 같이 설명한다.

\[P \leq n(4n \sqrt{n} + 1) \cdot \frac{2^{c_0n}}{\max(a_i)}\]

이때 $c_0 \approx 1.0628$이다. 따라서 이 확률($x_2$가 격자 내 유일한 최단 벡터가 아닐 확률) $P$가 작아지면 우리가 찾고자 하는 해가 유일한 최단 vector로 lattice에 등장할 확률이 올라간다. 이 확률이 작아지려면 $\frac{2^{c_0n}}{\max(a_i)}$가 작아져야 하므로 $\max(a_i) > 2^{c_0n}$가 되야 한다. 이걸 로그로 바꾸면 다음과 같이 된다.

\[\log_2 \max(a_i) > c_0n \to d = \frac{n}{\log_2 \max(a_i)} < \frac{1}{c_0} \to d < \frac{1}{1.0628} \approx 0.9408\]

여기서 $c_0$의 설정 값 $c_0 \approx 1.0628$는 Improved Low‑Density Subset Sum Algorithms 논문에서 특정한 확률 분석과 실험적 근거로 유도된 상수로 격자의 구조, vector 간 거리 분포, 격자 차원 등에 따라 최적으로 설정된 값이라 마음대로 더 작게 만들 수 없다. 따라서 위 식에서 $d$의 bound를 크게 하려고 $c_0$를 더 작게 만들어버리면 오히려 실패율이 증가할 수도 있다.

결론적으로 Density $d< 0.9408$이면, 우리가 찾고자 한 vector $x_2$가 유일한 최단 벡터가 될 확률이 높고, SVP oracle이 있다면 이 벡터를 통해 subset sum문제의 해를 구할 수 있다. 하지만 이 결과는 이론적이고, SVP oracle이 존재한다고 가정할 때만 성립하는데 현실에서는 SVP oracle이 존재하지 않는다. 대신 LLL이나 BKZ와 같은 알고리즘이 충분히 짧은 벡터를 찾아주므로 문제 해결이 가능하다. 또한 density $d$에 의한 upper bound도 이론적인 값이며, 실제로는 higher density subset sum problems도 풀리는 경우가 있다.

Example $(a_1, a_2, a_3, a_4, a_5, a_6) = (83, 59, 47, 81, 76, 51)$이고, target $s=291$인 $n=6$ weight subset sum problem이 있다고 하자. density는 $d=n/ \log_2 \max(a_i) = 6/6.375 = 0.9412$로 이론적인 upper bound보다는 조금 높지만 CJLOSS algorithm을 통해 해결할 수 있다. $N=3$이고, 아래와 lattice를 구성할 수 있다.

\[\mathbf{B} = \begin{bmatrix} 1 & & & & N a_1 \\ & 1 & & & N a_2 \\ & & \ddots & & \vdots \\ & & & 1 & N a_n \\ \frac{1}{2} & \frac{1}{2} & \cdots & \frac{1}{2} & N s \end{bmatrix}= \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 3 \cdot 83 \\ 0 & 1 & 0 & 0 & 0 & 3 \cdot 59 \\ 0 & 0 & 1 & 0 & 0 & 3 \cdot 47 \\ 0 & 0 & 0 & 1 & 0 & 3 \cdot 81 \\ 0 & 0 & 0 & 0 & 1 & 3 \cdot 76 \\ 0 & 0 & 0 & 0 & 0 & 3 \cdot 51 \\ \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & 3 \cdot 291 \end{bmatrix}\]

LLL을 돌리면 다음의 reduced basis $\mathbf{B}’$을 얻는다.

\[\mathbf{B}' = \frac{1}{2} \begin{bmatrix} -1 & 1 & 1 & 1 & -1 & -1 & -1 & 0 \\ 1 & 1 & 1 & -1 & -1 & 1 & 3 & 0 \\ 2 & -2 & 2 & 2 & -4 & 0 & 0 & 0 \\ 1 & 3 & -3 & 3 & -3 & 1 & 0 & 0 \\ 2 & -2 & -2 & -4 & 0 & 0 & 0 & 0 \\ -3 & -1 & -3 & -1 & -1 & 1 & 0 & 0 \\ 0 & -2 & 0 & 0 & -2 & -2 & 0 & -6 \end{bmatrix}\]

first row $\mathbf{b}_ 1 = (b_1, \cdots, b_7) = (-\frac{1}{2}, \frac{1}{2}, \frac{1}{2}, -\frac{1}{2}, -\frac{1}{2}, -\frac{1}{2}, 0)$는 short vector $x=(e_1-\frac{1}{2}, \cdots, e_6-\frac{1}{2}, 0)$ (or $-x$)의 결과가 된다. 따라서 $(b_1 + \frac{1}{2}, \cdots, b_6 + \frac{1}{2})$ (or $(\frac{1}{2} - b_1, \cdots, \frac{1}{2} - b_6)$ )를 계산하여 $e_i$를 얻을 수 있다.

\[(e_1, e_2, e_3, e_4, e_5, e_6) = (1, 0, 0, 1, 1, 1)\]

Low-density Subset Sum Problems: Extensions and Generalisations

위에서 살펴본 문제는 multiple subset sum problem, modular subset sum problem, multiple modular subset sum problem으로 확장될 수 있으며, 각 문제의 정의는 다음과 같다.

Definition (Multiple Subset Sum Problem). positive integers $a_{1,1}, \cdots, a_{k,n}$ (the weights)와 target integer $s_1, \cdots, s_k$가 있을 때, 다음을 만족하는 $e_1, \cdots, e_n$ with $e_i \in \lbrace 0, 1 \rbrace$을 찾는 문제.

\[\sum_{i=1}^n e_i a_{j,i} = s_j \ (1 \leq j \leq k)\]

Definition (Modular Subset Sum Problem). positive integers $a_1, \cdots, a_n$ (the weights)와 target integer $s$ 그리고 modulus $M$이 있다고 할 때, 다음을 만족하는 $e_1, \cdots, e_n$ with $e_i \in \lbrace 0, 1 \rbrace$을 찾는 문제.

\[\sum_{i=1}^n e_i a_i = s \pmod{M}\]

Definition (Multiple Modular Subset Sum Problem). positive integers $a_{1,1}, \cdots, a_{k,n}$ (the weights)와 target integer $s_1, \cdots, s_k$ 그리고 modulus $M$이 있다고 할 때, 다음을 만족하는 $e_1, \cdots, e_n$ with $e_i \in \lbrace 0, 1 \rbrace$을 찾는 문제.

\[\sum_{i=1}^n e_i a_{j,i} = s_j \pmod{M} \ (1 \leq j \leq k)\]

multiple subset sum problem의 density는 $d = \frac{n}{k \cdot \log_2 \max(a_{j, i})}$ 이고, multiple modular subset sum problem의 density는 $d = \frac{n}{k \cdot \log_2 M}$이다. modular subset sum problem의 density는 multiple modular subset sum problem에서 $k=1$을 적용한 값이다.

multiple subset sum problem은 동일한 density bound $d < 0.9408$에서 다음의 lattice로 해결할 수 있다.

\[\mathbf{B} = \begin{bmatrix} 1 & & & & 0 & N a_{1,1} & N a_{2,1} & \cdots & N a_{k,1} \\ & 1 & & & 0 & N a_{1,2} & N a_{2,2} & \cdots & N a_{k,2} \\ & & \ddots & & \vdots & \vdots & \vdots & \ddots & \vdots \\ & & & 1 & 0 & N a_{1,n} & N a_{2,n} & \cdots & N a_{k,n} \\ \frac{1}{2} & \frac{1}{2} & \cdots & \frac{1}{2} & \frac{1}{2} & N s_{1} & N s_{2} & \cdots & N s_{k} \end{bmatrix}\]

$N > \sqrt{\frac{n+1}{4}}$ 이고, 이전과 유사하게 linear combination $(e_1, \cdots, e_n, -1)$은 short vector $x = (e_1 - \frac{1}{2}, \cdots, e_n - \frac{1}{2}, -\frac{1}{2}, 0, \cdots, 0)$을 만들기 때문에 lattice reduction을 통해 target vector를 찾을 수 있다.

modular multiple subset sum problem은 $d < 0.9408$와 $k = o \left( \frac{n}{\log_2 ((n+1) \sqrt{n}+1)} \right)$ 에서 아래의 lattice로 해결할 수 있다.

\[\mathbf{B}^{\prime} = \begin{bmatrix} 1 & & & & 0 & N a_{1,1} & N a_{2,1} & \cdots & N a_{k,1} \\ & 1 & & & 0 & N a_{1,2} & N a_{2,2} & \cdots & N a_{k,2} \\ & & \ddots & & \vdots & \vdots & \vdots & \ddots & \vdots \\ & & & 1 & 0 & N a_{1,n} & N a_{2,n} & \cdots & N a_{k,n} \\ & & & & & NM & & & \\ & & & & & & NM & & \\ & & & & & & & \ddots & \\ & & & & & & & & NM \\ \frac{1}{2} & \frac{1}{2} & \cdots & \frac{1}{2} & \frac{1}{2} & N s_{1} & N s_{2} & \cdots & N s_{k} \\ \end{bmatrix}\]

target vector가 이 lattice에 있는지 확인하기 위해 modular equations $\sum_{i=1}^n e_i a_{j,i} = s_j \pmod{M}$ 를 $\sum_{i=1}^n e_i a_{j,i} = s_j + ℓ_jM$ 으로 표현하면 $(e_1, \cdots, e_n, -ℓ_1, \cdots, -ℓ_k, -1)$ 와의 linear combination이 target vector $x = (e_1 - \frac{1}{2}, \cdots, e_n - \frac{1}{2}, -\frac{1}{2}, 0, \cdots, 0)$를 만들어내는 것을 알 수 있다.

Reference

https://eprint.iacr.org/2023/032.pdf