ノート:Merkle-Hellmanナップサック暗号

ナップサック暗号と署名

この暗号方式は、暗号（Cipher）には利用できるか、デジタル署名には利用できない。

元々の暗号が解読されてしまっているので, 暗号に利用できるとか署名に利用できるとか言ってもどうしようもないんですが. それはさておき. 一般にナップサック暗号(というか組み合わせ系暗号)を署名に利用するのは難しい話です. 具体的に言えば,

• 秘密鍵を知っていることの非対話ゼロ知識証明を作るのが難しい
  • 元々安全性の基と出来る問題が無いと言っても良いので, 安全性の証明が出来ない
  • 実際どう作って良いのか分からない

となります. しかし, 今のところ無いだけであって, 今の書き方だと原理的にできないように読めてしまいます. これは問題だと思うのですが, 如何なものでしょう? (追記:日本だと早稲田篤志・双紙正和・宮地充子「Knapsack問題に基づいた署名方式の提案」というのもあったりします) --roget 2006年1月4日 (水) 13:46 Roget

「ナップサック問題を利用した暗号方式」と、Merkle-Hellmanが提案した「特別なナップサック問題を利用した暗号方式」とは異なります。Rogetさんがおっしゃっているのは前者についてでしょうね。 --Kazov 2006年1月5日 (木) 01:29 (UTC)

"一般に"以降はそうなってます. 失礼しました. とりあえず"利用できるか"だけ直しておきます. --roget 2006年1月5日 (木) 11:41 (UTC)

「MHナップサック暗号はデジタル署名に利用できない」と言い切ってしまうのは、確かにRogetさんのご指摘のように「それは本当か？（証明はあるのか）」という疑問が生まれるという点で推敲の余地がある表現でした。DSAのように署名専用の方式でも秘匿通信への利用可能性が議論されていますから。修正を試みてみますが、より望ましい表現案をお持ちでしたらどうぞ修正して頂ければと思います。署名への応用については、ナップサック暗号を作成して、こちらで色々な暗号用途の方式と共に署名への応用の可否を記述するのがよいと思います。最近（ここ1～2年の間）でも新しいナップサック暗号の提案とその解読があったりして、執筆する時間さえあれば、トピックスは沢山ですよね。Sina 2006年1月5日 (木) 14:58 (UTC)