ナップサック暗号

ナップサック暗号は、ナップサック問題を解く困難さに基づいて安全性が確保された暗号です。これらのアルゴリズムの単純なバージョンは数十年にわたって解読されているため、あまり普及していません。^{[1]しかし、このタイプの暗号システムは}耐量子暗号の良い候補です。^[要出典]

最も有名なナップサック暗号は、RSA暗号と同年に発表された、最初の公開鍵暗号の一つであるマークル・ヘルマン公開鍵暗号です。しかし、この暗号はシャミア^[2]、アドルマン^[3]、そして低密度攻撃など、いくつかの攻撃によって破られてきました。

しかし、現在までに安全であると考えられている現代のナップサック暗号システムも存在しており、その一つがNasako-Murakami 2006である。^[4]

ナップサック暗号は、古典的な暗号解読法に当てはまらない場合、量子コンピュータでさえ解読が困難であると考えられています。しかし、 RSAのように大きな整数の因数分解やECDSAのように離散対数の計算を必要とするシステムでは、ショアのアルゴリズムによって多項式時間で解読できます。^[5]

参考文献

1. シュナイアー、ブルース（2004年）『秘密と嘘』Wiley Publishing, Inc. p.95. ISBN 978-0-471-25311-2。
2. シャミア 1982.
3. アドルマン 1983
4. 奈々子・村上 2006.
5. Shor, Peter (1997). 「量子コンピュータにおける素因数分解と離散対数のための多項式時間アルゴリズム」. SIAM Journal on Computing . 26 (5): 1484–1509 . arXiv : quant-ph/9508027 . doi :10.1137/s0097539795293172. S2CID  2337707.

参考文献

• アドルマン、レナード(1983).「反復マークル・ヘルマン公開鍵暗号の破り方について」.暗号学の進歩. シュプリンガー. pp.  303– 308. doi :10.1007/978-1-4757-0602-4_29. ISBN 978-1-4757-0604-8。
• シャミール、アディ(1982)、「基本的なマークル・ヘルマン暗号を破るための多項式時間アルゴリズム」、第23回コンピュータサイエンスの基礎に関する年次シンポジウム (SFCS 1982)、pp.  145– 152、doi :10.1109/SFCS.1982.5
• 名迫 剛志; 村上 雄三 (2006)「複合トラップドアを用いた高密度ナップサック暗号」日本応用数理学会誌、16 (4): 519– 605, doi :10.11540/jsiamt.16.4_591