ナップザック問題を用いた公開鍵暗号の信頼性に関する検討

伊東　利哉  黒沢　馨  辻井　重男 

誌名
電子情報通信学会論文誌 A  Vol.J67-A  No.12  pp.1176-1180
発行日: 1984/12/20
Online ISSN: 
Print ISSN: 0373-6091
論文種別: 論文
専門分野: 
キーワード: 


本文: PDF(261.4KB)

あらまし: 
近年，コンピュータや通信の情報セキュリティの手段として，暗号の利用が広く注目されている．ナップザック問題を利用する公開鍵暗号方式として，現在のところsuper-increasing性を秘密鍵とするいくつかの暗号，及び乗算形暗号が提案されている．最近，super-increasing性を秘密鍵とする暗号を多項式時間で解読する方法が見出された．これによって，すべてのナップザック暗号の信頼性が失われたかのように考えられている向きもあるが，super-increasing性を利用しないナップザック暗号として乗算形暗号があり，その他，将来新たなナップザック暗号が考案される可能性も残されている．したがって，ナップザック暗号の信頼性を，秘密鍵に依存しない立場から考案することは，重要な問題と考えられる．本文は，秘密鍵に関係なくナップザック暗号を解読する1つの方法を考案するとともに，ナップザック問題が線形時間で解けるため，従来より弱い十分条件を示すものである．これは，乗算形暗号等がこれらの条件を避けなければならないことを意味し，本文は，強固なナップザック暗号を作るための示唆を含んでいることになっている．