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を返してどないすんねん。で、x_iが0,1だったら上手いことP_iを潰していけばいいんだけどさ。
うわ、CDHが拡張CKDHより弱いことの証明が無い。あと3.2節を見ろと言っておきながら3.2節が無い。この帰着が一番知りたいところなのに(;´Д`)
結論: 間が無さ過ぎて分からない。もしもこの論文の方向性が正しいならば、やばいことになる可能性があるので、注意しておく。
*1:通常のKnapsackは{0,1}上で考えているが、それを{Z_p}^{×}に拡張したもの?