- 528 名前：１３２人目の素数さん mailto:sage [2007/10/08(月) 21:43:54 ]
- >>525
> 言葉足らずだった. NP困難に基づいてかつ実用的な暗号ね.
> NP困難に基づくものってだいたい使いづらい気がする.
> OTUとかはナップザック問題に基づいているけど帰着ないし.
そもそも「基づく」って言葉の意味が曖昧だな。NP困難な問題に基づく暗号ってのは
ナップザック問題などのNP困難問題を変形して暗号に利用している。だからその暗号を
解読する問題がNP困難であるとは通常証明されていないし、そもそもそういう暗号系は
現在のところ存在しない。そのためにナップザック暗号はことごとく攻撃されてきたという
歴史があるわけだ。ナップザック系で生き残ってるのってChor-RivestとOTUぐらいか？
実際、解読がそんなに難しい暗号はできないと多くの研究者が無理だと考えている。
例えば一方向性関数でさえ（non-adaptive blackbox reduction で）NP困難ベースなものが
できれば coAM が NP に入ったりするという結果があったりする。
