ある意味攻撃

概要

Koichiro Noro and Kunikatsu Kobayashi. “Knapsack Cryptosystem on Elliptic Curves.” (ePrint 2009/091)を軽く読んだ.
書き直してみたら拡張ElGamal暗号の改悪になってしまった. したがってこの論文の価値が消滅した.
面倒くさいので正しい構成は元論文を当たってください.

研究会 講演論文 - 楕円曲線上のナップザック暗号を見るに2008/07にISEC研究会で発表済らしい.

元の暗号方式

パラメータ設定

G_1×G_2→G_T型の双線形写像を用いた群を考える.
それぞれ位数を素数qとしておく.
G_1の生成元をP, G_2の生成元をQとする.
G_Tの生成元はe(P,Q)である.

鍵生成

1. G_1から元をランダムに選びそれをTとする.
2. xをZ/qからランダムに選ぶ.
3. yをy 2^{kl+1} < (q-1)を満たす整数からランダムに選ぶ.
4. a_i = y 2^{i-1} (i=1,...,kl)とし, A_i = a_i Pを計算する.
5. b_{ij} = e(P,Q)^{y j 2^{(i-1)k}}を i=1,...,lとj=1,...,2^{k-1}について計算し, とする.
6. 公開鍵は(P,yP,T,xT,A_1,...,A_{kl},)
7. 秘密鍵は(x,y,a_1,...,a_{kl},f_1,...,f_l)

暗号化

1. m_1,...,m_lをそれぞれkビットの数とする. で, M=\sum_{i=1}^{l} m_i 2^{i-1}としておく.
2. , とする
3. C = M y Pとする.
4. 暗号文は (C, C_{11}, C_{12}, ..., C_{l1}, C_{l2}).

復号

(省略)
f_i(α)を使って頑張っている.

書き直した暗号方式

C_{i2}の計算方法が無駄に重い. A_{i}をすべて公開する必要もなさそうだと考えると以下になる.

パラメータ設定

(省略)

鍵生成

1. G_1から元をランダムに選びそれをTとする. (ElGamal暗号用.)
2. xをZ/qからランダムに選ぶ. (ElGamal暗号用.)
3. yをy 2^{kl+1} < (q-1)を満たす整数からランダムに選ぶ. (拡張部分用.)
4. (省略.)
5. 公開鍵は(P,yP,T,xT)
6. 秘密鍵は(x,y)

暗号化

1. m_1,...,m_lをそれぞれkビットの数とする.
2. t_iをZ/qからランダムに選び, C_{i1} = t_i T, C_{i2}= m_i 2^{i-1} y P + t_i x T とする
3. 暗号文は (C_{11}, C_{12}, ..., C_{l1}, C_{l2}).

これで(C_{i1}, C_{i2}) の部分が拡張ElGamal暗号になることが分かる.

復号

1. C_{i1}とC_{i2}とxよりm_i 2^{i-1} y Pを計算する.
2. m_i Pを計算する.
3. kが小さいので2^{k}通り試せば, m_iが復元できる. これをl回繰り返す.

問題点

• 復号について考えると, 論文中にあるような2^{k}以上回以上演算を行うメリットは無い. なんでこんなややこしくしているのかは俺は知らない.
• 全部群G_1上で計算できるので, そもそもペアリング使う必要が無くなってしまう.
• 暗号文に含まれるCの情報は全く必要ない.
• 素数位数にしておけば, yの謎の条件も必要ない.
• というわけでナップサックかと思ったら拡張ElGamalの改悪でしたとさ.