All rights are reserved and copyright of this manuscript belongs to the authors. This manuscript have been printed and distributed without reviewing and editing as received from the authors: posting the manuscript to SCIS 2005 does not prevent future submission to any journals or conferences with proceedings. SCIS 2005 The 2005 Symposium on Cryptography and Information Security Maiko Kobe, Japan, Jan.25-28, 2005 The Institute of Electronics, Information and Communication Engineers プリコーディングを用いた高密度 MH 型ナップザック暗号の提案 A High-Density MH-Type Knapsack Cryptosystem with Pre-coding 名迫健∗ Takeshi NASAKO 横山晃子 ∗ Akiko YOKOYAMA 村上恭通 ∗ Yasuyuki MURAKAMI あらまし MH 暗号をはじめとするナップザック暗号は従来より安全ではないと考えられている．本稿では超増加性をトラップドアに用いた MH ナップザック暗号に再注目し， SHP 暗号で使用されているプリコーディング手法を適用して高密度化することによって，高い安全性を持つ公開鍵暗号プリミティブ（DOM 暗号）を提案する．また，従来ナップザック暗号に有効とされている各種の攻撃法に対して提案方式は非常に高い耐性を有することを示す．キーワード公開鍵暗号，ナップザック暗号，MH 暗号，SHP 暗号，プリコーディング 1 まえがき Merkle と Hellman は，暗号化処理が加算のみにより実行し得る公開鍵暗号として超増加数列をトラップドアに用いたナップザック暗号 (MH 暗号) を提案した [1]．公開鍵暗号のプリミティブ（DOM 暗号）を提案する． 2 0-1 ナップザック問題とその密度攻撃 [3, 4, 5] によって容易に解読できることが知られて 0-1 ナップザック問題とは，正整数の集合 A = {a1 , a2 , . . . , an } （ナップザックと呼ばれる）と，その部分集合の和 C が与えられたときに，その部分集合を見出す問いる．このことや，それ以降に提案されたナップザック題である．換言すると，一次不定方程式しかしながら，MH 暗号は Shamir の攻撃 [2] や低密度暗号のほとんどが解読されていることから， MH 暗号 a1 x1 + a2 x2 + · · · + an xn = C をはじめとしてナップザック暗号の安全性は疑問視されていた．しかしながら，これだけを根拠にすべてのナップザック暗号が安全ではないと結論付けることはできな (1) の解 (x1 , x2 , . . . , xn ) ∈ {0, 1}n を見出す問題である．ナップザック A の密度 d は，次式で定義される1 ．い．また，量子コンピュータが実現すると，素因数問題， d= 離散対数問題，楕円離散対数問題が解かれてしまうこと n log2 (max ai ) が示され，多くの公開鍵暗号は解読されることが知られ一般に 0-1 ナップザック問題は NP 完全問題であるが，ている．従って，安全なナップザック暗号を探求することは非常に重要な意味を持つ．実際，低密度攻撃（LDA）に対して高い耐性を有する超増加数列をナップザックとする場合は，簡単なナップザック問題と呼ばれ，容易に解くことができる．ナップザック暗号はナップザックを公開鍵とし，0-1 ナップザック暗号方式として服部，村上，笠原によるプリコーディングを用いて高密度化した暗号方式があり， SHP-III, IV, VII 暗号などが提案されている [6, 7]．また，最近，筆者らも法縮小という高密度化手法を提案し，異なる観点から低密度攻撃に高い耐性を有する方式として CHK 暗号を提案している [8]．本稿では，SHP-III 暗号に用いられているプリコーディナップザック問題の難しさに安全性の根拠を置く．本稿では，最大の暗号文を Cmax として，ナップザック暗号の密度を ρ= n log2 Cmax と定義する．一般に，ρ < d であり，本定義はより厳しい評価となっている．ングという手法に着目し，MH 暗号同様に超増加性をトラップドアに用いた方式に応用した新たなナップザック ∗ 大阪電気通信大学通信工学科〒 572-8530 大阪府寝屋川市初町 18-8, Dept. of Telecommunications and Computer Networks, Osaka Electoro-Communication Univ., 18-8, Hatsu-cho, Neyagawashi, Osaka 572-8530, Japan. E-mail: {f01084, f01139, yasuyuki} @isc.osakac.ac.jp 1 密度を d = n log2 (max ai )−log2 (min ai ) として定義している場合もあるが，本定義の方がより密度を小さく評価している（d めこちらの定義を採用した． d）た ✓ 復号アルゴリズム MH 暗号 3 for i = n downto 1 { if (M vi ) { mσ−1 (i) = 1 本節では，提案方式の基礎をなす MH 暗号 [1] の構成法について述べる．ナップザック暗号において，公開鍵の位置を置換して M ← M − vi } else { 公開できるものがあり，MH 暗号はそのひとつである．以下では，その特徴を表すために， n 次対称群の元 σ mσ−1 (i) = 0 を秘密鍵とし，σ による置換操作を明示的に表現した． 3.1 ✏ 鍵生成 } ✒ } MH 暗号の鍵を以下に示す． ✓ ✏ 公開鍵：a ✒ Bob は以下に述べる手順に従って鍵を生成する．本章では，ナップザック暗号に対して有効な従来の攻 ✑ 撃法を紹介する．秘密鍵：P, v, w, σ 4 まず，超増加ベクトル (v1 , v2 , . . . , vn ) を生成する．すなわち，v1 を正整数乱数とし，vi を vi > si−1 (i = 2, 3, . . . , n) ナップザック暗号に対する従来の攻撃法 4.1 ✑ Shamir の攻撃法 Shamir は MH 暗号に対する攻撃法を提案した．この攻撃法は超増加数列をトラップドアに用いたナップザック暗号に対して有効である．を満たす正整数乱数とする．ただし， i si = vk k=1 Shamir の攻撃法は，公開鍵ベクトル a = (a1 , a2 , . . . , an ) が与えられたとき，集合 A = {ai w mod P } が超増加数列をなし，かつ，その総和が P 未満となるような正整数 (w , P ) の組を見出すアルゴリズムである．見出した正整数の組 (w , P ) と A を用いることにより，正当とする．な受信者と同様に超増加ナップザック問題に変換するこ次に，素数 P を P > sn を満たすように生成する．さらに，秘密鍵 w ∈ Z∗P をランダムに生成し，次式に従って vi をモジュラ変換することにより公開鍵ベクトル a = (a1 , a2 , . . . , an ) の各成分 ai を得る． ai = wvσ(i) mod P (i = 1, 2, . . . , n) ただし，σ は n 次対称群の元である．とができ，容易に平文を得ることができる．このとき， (w , P ) および A は，必ずしも受信者の持つ秘密鍵と一致しなくても，秘密鍵と同等な働きをすることに注意されたい． 4.2 低密度攻撃（LDA） Lagarias, Odlyzko は，密度の低いナップザック問題の解法を提案した [4]．さらに，Coster, LaMacchia, Odlyzko, Schnorr は，より密度の高いナップザック問題に対しても有効である改良手法を提案している [5]．以後，前者 3.2 暗号化を LO 法，後者を CLOS 法と呼ぶ． Alice は，平文 m = (m1 , m2 , . . . , mn ) ∈ {0, 1}n と公開鍵ベクトル a を用いて次式により暗号化を行い，暗利用することができるため，低密度攻撃と呼ばれている．号文 C を得る．なお，低密度攻撃は，トラップドアの如何にかかわらず C = ma 3.3 これらの解法は，低密度なナップザック暗号の解読に低密度なナップザック暗号の解読に有効な攻撃法である． 4.2.1 復号 Bob は，まず，中間平文 M を M = w−1 C mod P として求め，以下のアルゴリズムにより復号を行う． LO 法 LO 法は，正整数の集合 A = {a1 , a2 , . . . , an } と，それらの部分集合の和 C  1   0   . B =  ..    0 を用いて，行列 0 1 .. . ... ... .. . 0 0 .. . −a1 −a2 .. . 0 0 0 ... ... 1 0 −an C          逐次的プリコーディングを用意し，この各行ベクトルが張る格子 L(B) に対し格子 5.1 基底縮小を行うことにより，式 (1) の解 (x1 , x2 , . . . , xn ) この格子 L(B) には x = (x1 , x2 , . . . , xn , 0) が含まれ SHP-III 暗号や提案暗号方式に用いるプリコーディングにおいては，逐次的に復号を保証していく必要があるため，符号化平文ベクトルの第 i 成分を平文ベクトルのており，0-1 ナップザック問題においては xi ∈ {0, 1} で第 1 成分から第 i 成分により決定する必要がある．すて，格子基底縮小アルゴリズムを適用することによって，なわち，適当な {0, 1}i → {0, 1} の写像 Fi により，を発見する解法である．あるので，x のユークリッドノルムはごく小さい．従っ L(B) に含まれる最短ベクトルを求めることができると，それが x である可能性が高く，密度 ρ < 0.6463 . . . のとき x が最短ベクトルである確率が 1 であることが示されている [4]． 4.2.2 CLOS 法 m∗i = Fi (m1 , m2 , . . . , mi ) (i = 1, 2, . . . , n) と表される必要がある．このような性質を持つプリコーディングを逐次的プリコーディングと呼び，n 次元の逐次的プリコーディング全体の集合を SPC n とする． √ CLOS 法は，λ > n なる正整数 λ を定め，正整数の集合 A = {a1 , a2 , . . . , an } と，それらの部分集合の和 C と λ を用いて，行列   1 0 ... 0 −λa1    0 1 ... 0 −λa2     .  .. .. .. .. B =  ..  . . . .     0 ... 1 −λan   0 −1/2 −1/2 . . . −1/2 λC を用意し，この各行ベクトルが張る格子 L(B ) に対し格子基底縮小を行うことにより，式 (1) の解 xi を発見する解法である．この格子 L(B ) には x = (x1 −1/2, x2 −1/2, . . . , xn − 逐次的プリコーディングは Fi (m1 , m2 , . . . , mi ) の集合であるが，以後，単に F と書き，m∗ = F(m) と表す．なお，各 Fi (m1 , m2 , . . . , mi ) はそれぞれ任意の関数でよく，逆関数が存在する必要はない． 5.2 逐次的プリコーディング H ∈ SPC n のうち，全ての i = 1, 2, . . . , n について  m∗ = H (m , m , . . . , m , m ) i 1 2 i−1 i i m = H (m , m , . . . , m , m∗ ) i ことができると，それが x である可能性が高く，密度 ρ < 0.9408 . . . のとき x が最短ベクトルである確率が 1 であることが示されている [5]． 5 プリコーディング i 1 2 i−1 i が成立するものを可逆プリコーディングと定義する．全ての i = 1, 2, . . . , n について Fi−1 ∈ PC i−1 として Hi (m1 , m2 , . . . , mi−1 , mi ) 1/2, 0) が含まれており，このユークリッドノルムはごく小さい．従って，格子基底縮小アルゴリズムを適用することによって，L(B ) に含まれる最短ベクトルを求める可逆プリコーディング = Fi−1 (m1 , m2 , . . . , mi−1 ) ⊕ mi により表現できるものは可逆プリコーティングである．可逆プリコーディング全体の集合を IPC n とする．喜安-Gray 逆変換に基づく二通りのプリコーディング G0 および G1 をそれぞれ以下のように定義する [6]．これらは可逆プリコーディングである． i 暗号化に先立って，平文ベクトルを符号化平文ベクト G0i (m1 , m2 , . . . , mi ) = ルに変換する操作をプリコーディングと呼ぶものとする． i 本稿で扱うプリコーディングは，平文ベクトルおよび G1i (m1 , m2 , . . . , mi ) = 符号化平文ベクトルのいずれも n 次元 2 進ベクトルとし，それぞれ，m = (m1 , m2 , . . . , mn ) ∈ {0, 1}n および m∗ = (m∗1 , m∗2 , . . . , m∗n ) ∈ {0, 1}n と表記する．これら n 次元のプリコーディング全体の集合を PC n とする． [定義 1] プリコーディング F ∈ PC n について，m = F(m) とし，m のハミング重みと m のハミング重みの和の最大値を Smax (F) とする．すなわち， Smax (F) = max {WH (m) + WH (F(m))} m∈{0,1}n と定義する．ただし，WH (m) は m のハミング重みを表す． mk k=1 1⊕ mk k=1 可逆プリコーディングを合成して生成される任意のプリコーディングは可逆プリコーディングである． 6 SHP-III 暗号本節では，ナップザック暗号に初めてプリコーディングを導入した暗号方式である SHP-III 暗号 [6, 7] の構成法について述べる．鍵生成 6.1 6.3 SHP-III 暗号の鍵を以下に示す． ✓ ✏ 秘密鍵 : P, v (0) , v (1) , w 復号 Bob は，まず，中間平文 M を M = w−1 C mod P 公開鍵 : a(0) , a(1) , F ✒ ✑として求め，以下のアルゴリズムにより復号を行う． ✓ ✏ 復号アルゴリズム Bob は，適当な逐次的プリコーディング F ∈ SPC n を定め，それを公開し，以下に述べる手順に従って鍵を for i = 1 to n { mi = M mod 2 生成する．まず，i = 1, 2, . . . , n として，正整数乱数ベクトル (0) (0) (0) (1) (0) を満たすように生成する．ただし，基数積 bi (1) bi m∗i = Fi (m1 , m2 , . . . , mi ) (0) (1) M ← M − m∗i vi + mi vi (1) v (0) = (v1 , v2 , . . . , vn ) および v (1) = (v1 , v2 , . . . , (1) vn ) の各成分を  v (0) ≡ 0 (mod 2) i v (1) ≡ 1 (mod 2) i およびを } if (M = 0) { output m } ✒ 7  b(0) = 2i−1 v (0) i i b(1) = 2i−1 v (1) i /2 ✑ 提案方式（DOM 暗号）本節では，MH 暗号を基礎とし，SHP-III で用いられているプリコーディングを適用した暗号方式（DOM 暗 i 号）を提案する．とし，すべての基数積がほぼ同程度のビット長となるよ (0) うに vi (1) および vi (0) すべての基数積 bi 7.1 を生成する． (1) および bi を降順に並べ替えた数列を bk (k = 1, 2, . . . , 2n) とし，素数 P をを満たすように生成する2 ．それを公開し，以下に述べる手順に従って鍵を生成する．さらに，秘密鍵 w ∈ Z∗P をランダムに生成し，基数積ベクトル b (1) および b を次式に従って，それぞれ， (0) モジュラ変換することにより公開鍵 a および a (1) を得る． 6.2  a(0) = wb(0) mod P a(1) = wb(1) mod P Alice は，平文 m = (m1 , m2 , . . . , mn ) ∈ {0, 1}n とプリコーディング F により，平文 m から符号化平文ベクトル m∗ = F(m) を求め，公開鍵ベクトル a(0) およびa (0) を用いて次式により暗号化を行い，暗号文 C を得る． C = m∗ a(0) + ma(1) (0) まず，r-bit の正整数乱数ベクトル v (0) = (v1 , v2 , . . . , (0) vn ) を生成する． (1) (1) (1) 次に，超増加ベクトル v (1) = (v1 , v2 , . . . , vn ) を (1) 生成する．ただし，vi (1) vi (0) > vi を + si−1 (i = 1, 2, . . . , n) を満たす正整数乱数とする．ただし，暗号化 (1) ✏ 公開鍵：a, b, H ✒ ✑ Bob は，可逆プリコーディング H ∈ IPC n を定め， bk k=1 (0) DOM 暗号の鍵を以下に示す． ✓ 秘密鍵：P, v (0) , v (1) , w, t Smax (F ) P > 鍵生成 i (0) si = (1) (vk + vk ) k=1 とする．さらに，素数 P を P > sn を満たすように生成する．また，秘密鍵 w ∈ Z∗P をランダムに生成する．さら 2 一般には，Smax (F ) を求めることは容易ではないが，G0 や G1 のように，比較的単純なプリコーディングについては，容易に求められる場合もある．に，ランダムに t = (t1 , t2 , . . . , tn ) ∈ {0, 1}n を生成 ✓ MH DOM m Plaintext ✏ m Plaintext Pre-coding Summation m Encodedtext m* Summation C Ciphertext C Ciphertext n 2n <1 Density log2 Cmax ✒ log2 Cmax a = (a1 , a2 , . . . , an ) および b = (b1 , b2 , . . . , bn ) を得る．  a = wv (ti ) mod P i i b = wv (1−ti ) mod P i ✓ 復号アルゴリズム (1) if (M vi ) { (t ) mi i = 1 } else { i (ti ) mi } されたい． (0) なお，vi および (1) vi ✏ for i = n downto 1 { 公開鍵は t の値により，シャフルされていることに注意が全数探索により露呈しないためには，これらのビット長を少なくとも 64-bit 以上 } に設定することが望ましい． =0 (1−t ) (1) (1) (1) (ti ) mi i = Hn−i+1 (mn , mn−1 , . . . , mi+1 , mi (1−t ) (0) (t ) (1) M ← M − mi i vi − mi i vi ) if (M = 0) { output m 暗号化 Alice は，平文 m ∈ {0, 1}n とプリコーディング H により，m から符号化平文ベクトル m∗ = H(m) を求め，公開鍵ベクトル a および b を用いて，次式により暗号化を行い，暗号文 C を得る． } ✒ 8 提案方式の安全性 (2) 復号る提案方式の安全性について考察する． 8.1 Bob は，まず，中間平文 M を Shamir の攻撃に対する安全性提案方式では，公開鍵全体の集合 A = {ai } ∪ {bi } は M = w−1 C mod P 完全な超増加数列ではないので，Shamir の攻撃を適用として求め，以下に示す復号アルゴリズムによって復ク A から秘密鍵 v (1) に対応する公開鍵を探し出すこと (1) (1) しても秘密鍵が露呈することはない．もし，ナップザッ (1) 号を行う．ただし，m = (m1 , m2 , . . . , mn ), m∗ = ができれば，これらは超増加数列なので，Shamir の攻 (0) (0) (0) (m1 , m2 , . . . , mn ) 撃により秘密鍵 (w, P ) と等価な働きをする (w , P ) のとする． ✑ 本章では，従来のナップザック暗号への攻撃法に対す C = ma + m∗ b 7.3 ✑ 図 1: MH 暗号と提案方式（DOM 暗号）との密度比較し，次式に従ってモジュラ変換することにより公開鍵 7.2 >1 Density 組を発見されてしまう．しかしながら，秘密鍵 t を特定することは O(2n ) の計算量を必要とするため，t を知らない攻撃者が v (1) に対応する部分を A の中から特定することは計算量的に困難である．従って，攻撃者は Shamir の攻撃を適用することができない．方式 8.2 表 1: 各暗号方式の特徴符号化超増加数列 [1] R. C. Merkle, M. E. Hellman: “Hiding information and signatures in trapdoor knapsacks,” IEEE 密度 MH なし使用 1 未満 CHK 誤り検出一部使用 1 以上 SHP-III 逐次的 PC 未使用 1 以上 Trans. Inf. Theory, IT-24(5), pp.525–530, Sept. 1978. DOM 可逆 PC 半分使用 1 以上 [2] A. Shamir： “A polynomial time algorithm for PC : プリコーディング breaking the basic Merkle-Hellman cryptosystems,” Proc. Crypto’82, LNCS, pp.279–288, SpringerVerlag, Berlin, 1982. 低密度攻撃 (LDA) に対する安全性 (0) 提案方式において，各 vi (1) 参考文献のビット長を r-bit とし， v1 のビット長を l-bit と設定すると，r (1) vi l のとき，のビット長を (l + i − 1)-bit 程度に設定することが可能である．従って， P は (n + l)-bit に設定することができる．ゆえに，提案方式の密度 ρ は ρ= 2n n + log2 n + l + 2 (3) となる．従って，l < n − log2 n − 2 であれば密度は 1 以上となることがわかる．一方，MH 暗号ではいかなるパラメータ設定を行おうとも密度を 1 以上に設定することはできないことに注意されたい（図 1)． [3] E. F. Brickell： “Solving low density knapsacks,” Proc. Crypto’83, LNCS, pp.25–37, Springer-Verlag, Berlin, 1984. [4] 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. [5] 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. 例えば，n = 128 ， r = l = 64 と設定すると，式 (3) より，密度 ρ = 1.273 . . . となる．従って，密度を 1 以上に設定することが可能になるため，低密度攻撃による解読は困難となる． [6] 服部保, 村上恭通, 笠原正雄： “プリコーディングを用いる二，三の加算暗号の提案”, 2001 年情報理論とその応用学会シンポジウム予稿集, pp.351–354, Dec. 2001. 9 むすび [7] 服部保，村上恭通，笠原正雄： “SHP 暗号の安全性本稿では，新たなナップザック暗号として DOM 暗号に関する二，三の考察”, 2002 年暗号と情報セキュを提案した．また，ナップザック暗号への従来の攻撃法リティシンポジウム予稿集, pp.131–136, Jan. 2002. に対する提案方式の安全性について詳細に考察を行った．その結果，DOM 暗号は従来の攻撃法に対して非常に高い耐性を有することが明らかになった．また，DOM 暗号は非常に高速に暗号化および復号処理が行えるという特長を有する．提案方式を含む，各ナップザック暗号の特徴を表 1 に示す．秘密鍵 t によって公開鍵をシャフルするという DOM 暗号特有のアイデアを各種の SHP 暗号に適用することにより，SHP 暗号の安全性をさらに向上させることが可能であるが，紙幅の都合もあり，この点についてはいずれ稿を改めて報告したい．従来，超増加性や，線型性が主な原因で安全でないとされていたナップザック暗号ではあるが，まだまだ改良の余地が残されていることを示した．今後もナップザック暗号の研究がさらに発展することを期待したい． [8] 名迫健, 横山晃子，村上恭通： “ナップザック暗号の法縮小による高密度化手法および探索復号法の提案”, 2004 年情報理論とその応用学会シンポジウム予稿集, pp.123–126, Dec. 2004. [9] A. K. Lenstra, H. W. Lenstra and L. Lov`asz： “Factoring polynomials with integer coefficients,” Mathematische Annalen 261, pp.515–534, 1982. [10] C. P. Schnorr, M. Euchner: “Lattice basis reduction: Improved practical algorithms and solving subset sum problems,” Mathematical Programming, Vol.66, pp.181–191,1994.