LLL and Markle-Hellman Knapsack cryptosystem

Markle-Hellman Knapsack暗号

一般に部分和問題が難しく、超増加列上では簡単であることを用いた公開鍵暗号

部分和問題: 値の組 $(a_1 ... a_n)$ と値 $t$ があって、 $t = a_1x_1 + a_2x_2 + \cdots + a_nx_n$ を満たす $(x_1...x_n)$ を求めよ

超増加列: $\sum_{i=0}^n < w_{n+1}$ を満たす数列

Knapsack暗号での暗号化

超増加列 $(w_1,...,w_n)$ を秘密鍵、 $(m_1,...,m_n)$ をnbitの平文とする。適当な $q, r$ を持ってきて

公開鍵： $\beta = (w_0*r \mod q, ..., w_n*r \mod q)$

暗号文： $C = \sum m_i\beta_i$

LLLでKnapsack暗号を解く

$n$ 次元ベクトル $\vec{b}$ とスカラ値 $c$ が与えられた時、次を満たし、各要素が $0$ または $1$ である $\vec{u}$ を考える

$\vec{b}\vec{u}^T = c$

このような $\vec{u}$ が存在した時、次式が成り立つ（ $-c$ に注意）

$VM = \begin{pmatrix}u_0 & u_1 & ... & u_{n-1} & 1 \end{pmatrix}\begin{pmatrix}1 & \cdots & 0 & b_0 \ \vdots & \ddots & \vdots & \vdots \0 & \cdots & 1 & b_{n-1} \0 & \cdots & 0 & -c\end{pmatrix}=\begin{pmatrix}u_0 & u_1 & ... & u_{n-1} & 0 \end{pmatrix}=W$

このとき、行列 $M$ の各行 $r_0 ... r_{n}$ はそれぞれ $(1, 0, ..., b_0 ), (0, 1, ..., b_1) ,..., (0, ..., 1, b_{n-1}),(0,...0,-c)$ という形をしており、1次独立である。

1次独立な $n+1$ 個のベクトル $\vec{r_0},..., \vec{r_n}$ はある格子 $L$ の基底ベクトルとなる（ $M$ は基底行列）（このとき $M$ や $r$ が格子 $L$ を張る/構成すると言ったりしそう）。そして、ベクトル $W$ は $u_0\vec{r_0} + \cdots + u_{n-1}\vec{r_n-1} + \vec{r_n}$ という、基底の線型結合で表されるので、 $W \in L$ である。

ここで $||W|| \le \sqrt{n}$ （なぜなら $W$ の各要素は $0$ または $1$ だから）であることを思い出すと、 $W$ は $L$ の短いベクトルだということがわかる。 $L$ の短いベクトルであるなら、 $L$ の短い基底を求めるアルゴリズムであるLLLで求められるのではないか。