講演抄録/キーワード |
講演名 |
2014-06-05 16:15
中間平文に基づくナップザック暗号の解読 ○草薙祥広・長尾 篤・森井昌克(神戸大) IA2014-3 ICSS2014-3 |
抄録 |
(和) |
ナップザック暗号とはナップザック問題(特に部分和問題)を安全性の根拠とする公開鍵暗号方式の総称である.
ナップザック暗号の安全性の指標として密度が用いられており,密度が0.94を下回るナップザック暗号は低密度攻撃により解読が可能である.
そのため,密度が1を超える高密度なナップザック暗号が数多く提案されているが,高密度を実現するために構造が複雑になり,低密度ナップザック暗号とは異なる脆弱性を抱えている.
本稿では,まず高密度ナップザック暗号を中間平文を用いてモデル化する.
また,高密度ナップザック暗号に対する新たな攻撃を提案し,高密度ナップザック暗号を構成する際に満たすべき条件を提示する. |
(英) |
Knapsack cryptography is the public key cryptosystem based on knapsack problem (especially subset sum problem).
Density is used as the indicator in subset sum problem.
Low-density knapsack cryptography, whose density is lower than 0.94, is broken by Low-Density Attack.
Hence, a lot of high-density cryptography, whose density is higher than 1, are proposed.
However, high-density knapsack cryptography's structure is more complicated and it has some different weaknesses from low-density cryptography.
In this paper, we model the high-density knapsack cryptography by using intermediary plaintext.
In addition, we propose new attacks on high-density knapsack cryptography and show the condition that the cryptography should satisfy. |
キーワード |
(和) |
公開鍵暗号 / ナップザック暗号 / 高密度ナップザック暗号 / 部分和問題 / 中間平文 / / / |
(英) |
public key cryptosystem / knapsack cryptography / high-density knapsack cryptography / subset sum problem / intermediary plaintext / / / |
文献情報 |
信学技報, vol. 114, no. 71, ICSS2014-3, pp. 9-14, 2014年6月. |
資料番号 |
ICSS2014-3 |
発行日 |
2014-05-29 (IA, ICSS) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
IA2014-3 ICSS2014-3 |
|