| 講演名 | 2015-06-12 乱数系列を秘密鍵とする論理積を用いるナップザック暗号 村上 恭通(阪電通大), 濱正 真佑(阪電通大), 笠原 正雄(早大/中大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 量子コンピュータにより，素因数分解問題・離散対数問題・楕円離散対数問題を多項式時間で解けることが証明された．ナップザック暗号は，NP困難な部分和問題を安全性の根拠とするため，量子コンピュータに対抗し得る公開鍵暗号の一つとして期待されている．筆者らは，符号化率を低くすることにより，秘密鍵に乱数を利用することができるナップザック暗号を提案していた．長尾，森井らによりいくつかの方式が部分和問題の本来の解ではない別解から解読可能であることが示されたが，その後，筆者らは，別解攻撃に安全な方式として，四系列の乱数を使用する方式(MHK4)及び三系列方式(MHK3)を提案した．前者は論理積(AND)，後者は排他的論理和(XOR)を用いており，両者の関係は必ずしも明らかではなかった．本論文ではANDを利用した多系列のナップザック暗号を提案し，MHK3を多系列のXOR利用方式に一般化して再定義することにより，AND利用方式とXOR利用方式の関係，及び，AND利用方式とMHK4の関係を明らかにする．その結果，XOR方式がすべての基本方式であることを示す． |
| 抄録(英) | In 2012, the present authors proposed a knapsack public-key cryptosystem using a random secret sequence, which will be referred to as MHK scheme. However, in CSS2013, Nagao and Morii discovered that the plaintext of MHK scheme can be disclosed by computing an alternative solution. This attack will be referred to as alternative solution attack. We then proposed MHK4 and MHK3 schemes which are secure against the alternative solution attack. In this paper, we clarify the relationship between MHK4 and MHK3 schemes by redefining the generalized version of these schemes and comparing them. |
| キーワード(和) | ナップザック暗号 / 部分和問題 / 乱数列 / MHK4 / MHK3 / 論理積 / 排他的論理和 |
| キーワード(英) | knapsack cryptosystem / subset-sum problem / random sequence / MHK4 / MHK3 / AND / XOR |
| 資料番号 | IA2015-11,ICSS2015-11 |
| 発行日 | 2015-06-04 (IA, ICSS) |
| 研究会情報 | |
| 研究会 | IA / ICSS |
|---|---|
| 開催期間 | 2015/6/11(から2日開催) |
| 開催地（和） | 九工大 百周年中村記念館 |
| 開催地（英） | Kyushu Institute of Technology Univ. |
| テーマ（和） | インターネットセキュリティ、一般 |
| テーマ（英） | Internet Security, etc. |
| 委員長氏名（和） | 吉田 健一(筑波大) / 三宅 優(KDDI研) |
| 委員長氏名（英） | Ken-ichi Yoshida(Univ. of Tsukuba) / Yutaka Miyake(KDDI R&D Labs.) |
| 副委員長氏名（和） | 大崎 博之(関西学院大) / 地引 昌弘(NICT) / 中村 豊(九工大) / 西出 隆志(筑波大) / 白石 善明(神戸大) |
| 副委員長氏名（英） | Hiroyuki Osaki(Kwansei Gakuin Univ.) / Masahiro Jibiki(NICT) / Yutaka Nakamura(Kyushu Inst. of Tech.) / Takashi Nishide(Univ. of Tsukuba) / Yoshiaki Shiraishi(Kobe Univ.) |
| 幹事氏名（和） | 松浦 知史(東工大) / 義久 智樹(阪大) / 植田 武(三菱電機) / 高倉 弘喜(NII) |
| 幹事氏名（英） | Satoshi Matsuura(Tokyo Inst. of Tech.) / Tomoki Yoshihisa(Osaka Univ.) / Takeshi Ueda(Mitsubishi Electric) / Hiroki Takakura(NII) |
| 幹事補佐氏名（和） | 屏 雄一郎(KDDI研) / 山本 寛(立命館大) / 渡辺 俊貴(NEC) / 吉岡 克成(横浜国大) / 神谷 和憲(NTT) |
| 幹事補佐氏名（英） | Yuichiro Hei(KDDI R&D Labs.) / Hiroshi Yamamoto(Ritsumeikan Univ.) / Toshiki Watanabe(NEC) / Katsunari Yoshioka(Yokohama National Univ.) / Kazunori Kamiya(NTT) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Internet Architecture / Technical Committee on Information and Communication System Security |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 乱数系列を秘密鍵とする論理積を用いるナップザック暗号 |
| サブタイトル（和） | |
| タイトル（英） | Knapsack Cryptosystems with Random Secret Sequences using Logical And Operation |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ナップザック暗号 / knapsack cryptosystem |
| キーワード(2)（和/英） | 部分和問題 / subset-sum problem |
| キーワード(3)（和/英） | 乱数列 / random sequence |
| キーワード(4)（和/英） | MHK4 / MHK4 |
| キーワード(5)（和/英） | MHK3 / MHK3 |
| キーワード(6)（和/英） | 論理積 / AND |
| キーワード(7)（和/英） | 排他的論理和 / XOR |
| 第 1 著者 氏名（和/英） | 村上 恭通 / Yasuyuki Murakami |
| 第 1 著者 所属（和/英） | 大阪電気通信大学(略称：阪電通大) Osaka Electro-Communication University(略称：OECU) |
| 第 2 著者 氏名（和/英） | 濱正 真佑 / Shinsuke Hamasho |
| 第 2 著者 所属（和/英） | 大阪電気通信大学(略称：阪電通大) Osaka Electro-Communication University(略称：OECU) |
| 第 3 著者 氏名（和/英） | 笠原 正雄 / Masao Kasahara |
| 第 3 著者 所属（和/英） | 早稲田大学/中央大学(略称：早大/中大) Waseda University/Chuo University(略称：WU/CU) |
| 発表年月日 | 2015-06-12 |
| 資料番号 | IA2015-11,ICSS2015-11 |
| 巻番号（vol） | vol.115 |
| 号番号（no） | IA-80,ICSS-81 |
| ページ範囲 | pp.57-62(IA), pp.57-62(ICSS), |
| ページ数 | 6 |
| 発行日 | 2015-06-04 (IA, ICSS) |