Song Han, Elizabeth Chang and Tharam Dillon "Knapsack Diffie-Hellman: A New Family of Diffie-Hellman"

Cryptology ePrint Archive 2005/347から。

最近流行のPairing使ってKnapsack作ってみようぜという話の様子。
CKDH⇔Subset-Sumはbiliner mapを使うとほぼ自明。CKDHが解けるならSubset-Sumが解けるは自明でいいんだが逆を証明してないよ、これ。拡張CKDH*1解ければCDHが解けるという話も大丈夫ぽい。インスタンスを超増加列に限った場合は通常のSubset-Sum側で線形時間で解けるので、アウト。CDHが拡張CKDHより弱いってのは、へぇーという印象。

ePrintにあるってことは、こういうところでネタにして良いってことよね?

DPKDH⇔CKDHの証明の書き間違い発見。DPKDHオラクルを使ってYes or Noを返してどないすんねん。\sum_{i=1}^n x_i P_iで、x_iが0,1だったら上手いことP_iを潰していけばいいんだけどさ。

うわ、CDHが拡張CKDHより弱いことの証明が無い。あと3.2節を見ろと言っておきながら3.2節が無い。この帰着が一番知りたいところなのに(;´Д`)

結論: 間が無さ過ぎて分からない。もしもこの論文の方向性が正しいならば、やばいことになる可能性があるので、注意しておく。

*1:通常のKnapsackは{0,1}上で考えているが、それを{Z_p}^{×}に拡張したもの?