Merkle-Hellmanナップサック暗号

Merkle-Hellmanナップサック暗号とは、1978年にラルフ・マークルとマーティン・ヘルマンが発表したナップサック問題（正確には部分和問題）を利用した公開鍵暗号の一つである。この暗号方式は、秘匿用途の方式であり、認証（デジタル署名など）を目的としたものではない。

公開鍵暗号の提案は1976年であり、比較的初期に提案された方式である。 1982年に解読方法が発見されたため、現在は使用されていない。近年になり、鍵の生成に量子コンピュータを用いることにより、量子コンピュータでも解けない暗号として機能することが示され、ふたたび注目を浴びている^[要出典]。

概要

Merkle-Hellmanナップサック暗号は部分和問題（ナップサック問題の特別なインスタンス）に基づいている。

部分和問題は、整数の列（a₁,...,a_n）と目標となる整数（t）を入力とし、 $\sum _{i\in S}a_{i}=t$ となる部分集合 $S\subseteq \{1,2,...,n\}$ を求める問題（a_i でt を合成する問題）である。

一般の部分和問題は、NP完全であることが知られている。しかし、超増加列と呼ばれる数列を用いた場合には、簡単に解けることが分かっている。Merkle-Hellmanナップサック暗号は、合成が簡単にできる超増加列を、見かけ上は合成がむずかしい整数列に変換し、また逆に戻せることに基づいている。超増加列とは、各項がそれまでの全ての項の和よりも大きい数列のことである。

超増加列の例: (1,2,4,8,16)

この暗号方式は発表時から安全性に疑問をもたれていたが、1982年にアディ・シャミア (Adi Shamir) によって一般的解読方法が発見された。これは部分和問題自体を解いたのではなく、超増加列を変換した数列を用いた場合には、どのように変換しても元の超増加という性質が残り、容易に解けることを示したものである。

シャミアの解読以降、多くのナップサック暗号の変形版が提案されているが、そのほとんどが解読可能であることが判明している。

用語については、暗号の用語および暗号理論の用語を参照のこと。

暗号方式

鍵生成

n ビットの平文を暗号化するために、まずn 個の数からなる超増加列

w = (w₁, w₂, ..., w_n)

を生成する（n はセキュリティパラメータであり、100ビット以上の数にすることが推奨されている）。

次に、整数q を q > $\sum _{i=1}^{n}w_{i}$ を満たすようにランダムに選ぶ。更に、整数 r を gcd(r,q) = 1 となるようにランダムに選ぶ。整数q は、q の剰余を取ったときに暗号文が一意に定まるように選ばなければならない。そうしないと二つの平文から同じ暗号文が生成されることになり、復号できなくなる。またr はq と互いに素な整数でなければならない。これは復号時にr の逆元を使うためである。

β_i = r w_i mod q

とし、数列

β = (β₁, β₂, ..., β_n )

を得る。

公開鍵はβ、秘密鍵は(w, q, r )である。

暗号化

n ビットの平文

α = (α₁, α₂, ..., α_n )

を暗号化する。ここで、各 α_i は第i ビットを表す (α_i ∈{0,1})。

$c=\sum _{i=1}^{n}\alpha _{i}\beta _{i}$

を計算し、c を暗号文とする。

復号

暗号文c を受け取った後、 c' = c r ^-1 mod q を計算する。ここで、r ^-1 は、(mod q) の整数の合同における r の逆元である。

すると、c' はw の部分和になっている。w は超増加列なので、{1,2,...,n} の部分集合S を次のようにして簡単に求めることができる。

まず、c' とw_n の大小を比較し、もしc' がw_n 以上の場合には、平文の第n ビットは 1 であり、小さい場合には、0 である。c' が大きい場合にはw_n を減算して、次にw_n-1 との大小を比較し、同様に第n-1 ビットを決める。これを第1ビットまで繰り返せばよい。

具体的なアルゴリズムは、次のとおりになる。

入力： w (超増加列), c'
出力： {1,2,...,n} の部分集合S

sをc' とし, S を空集合とする。
i = n, n-1, ..., 2, 1 について次文を繰り返す。
- s≥w_i ならば、s=s-w_i とし、S=S∪{i} とする。
s が 0 ならばS を, 0 でないならば⊥を出力する。

安全性

Merkle-Hellmanナップサック暗号は、シャミアにより多項式時間で解読できることが示されている。

シャミアの攻撃法

シャミアの攻撃法では、公開鍵β = (β₁, β₂, ..., β_n)から、超増加列w' = (w' ₁, w' ₂, ..., w' _n) を求める。正しい超増加列w とシャミアの攻撃法で求めたw' は異なることが多いが、正しく解読できる。詳しくは参考文献のAdi Shamir, "A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem"を参照のこと。

低密度攻撃(LDA)

密度が低い場合、高確率で格子の最短ベクトルを求める問題 (最短ベクトル問題, Shortest Vector Problem, SVP) へ帰着できる。最短ベクトル問題は、ユークリッド距離ではRandomized帰着の元でNP困難な問題であることが知られている。また、格子の次元が低い場合、LLLアルゴリズム(Lenstra, Lenstra, Lovasz, 1982)を用いて解けることが多い。

LO法(Lagarias, Odlyzkoにより提案) は，密度の低いナップザック問題への解法。
CLOS法(Coster, LaMacchia, Odlyzko,Schnorrにより提案) は，より密度の高いナップザック問題に対しても有効である改良手法。

(参考：格子_(数学)) (stub)

参考文献

Ralph Merkle, Martin Hellman, "Hiding Information and Signatures in Trapdoor Knapsacks", IEEE Trans. Information Theory, 24(5), September 1978, pp.525–530.
Adi Shamir, "A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem", CRYPTO'82, pp.279–288, 1982. (PDF)
J. C. Lagarias and A. M. Odlyzko： “Solving Low Density Subset Sum Problems,” J. Assoc. Comp.Math., vol.32, pp.229–246, Preliminary version in Proc. 24th IEEE, 1985
M. J. Coster, B. A. LaMacchia, A. M. Odlyzko and C. P. Schnorr： “An Improved Low-Density Subset Sum Algorithm,” In Advances in Cryptology Proc. EUROCRYPTO'91,LNCS, pp.54–67.Springer-Verlag, Berlin, 1991.

概要

暗号方式

鍵生成

暗号化

復号

安全性

シャミアの攻撃法

低密度攻撃(LDA)

参考文献

関連項目