| Presentation | 2018-05-17 Public key attack on knapsak PKC based on subset sum decision problem Ryuichi Sakai, Yasuyuki Murakami, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In 2012, Murakami, Hamasho and Kasahara have proposed a knapsack PKC based on the subset sum decision problem. An attack against these type of knapsack PKCs by computing alternative solutions of the knapsack problem is then proposed by Nagao and Morii. In 2016, one of the authors, Murakami, have also proposed the knapsack type PKC (M16 PKC) based on the subset sum decision problem for preventing Nagao and Morii attack. In this paper, we propose the new effective attacks against M16 knapsack PKC. The proposed attacks are able to compute equivalent secret key from the public key, and decode the cipher text of M16 PKC with the equivalent secret key, in a same way of the decryption with the legitimate ecret(decryption) keys. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | knapsack PKC / subset sum decision problem / public key attack / equivalent secret key attack |
| Paper # | IT2018-6,EMM2018-6 |
| Date of Issue | 2018-05-10 (IT, EMM) |
| Conference Information | |
| Committee | IT / EMM |
|---|---|
| Conference Date | 2018/5/17(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Ookayama Campus, Tokyo Institute of Technology |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | Information Security, Information Theory, Information Hiding, etc. |
| Chair | Masayoshi Ohashi(Fukuoka Univ.) / Keiichi Iwamura(TUS) |
| Vice Chair | Jun Muramatsu(NTT) / Hirohisa Hioki(Kyoto Univ.) / Minoru Kuribayashi(Okayama Univ.) |
| Secretary | Jun Muramatsu(Yokohama College of Commerce) / Hirohisa Hioki(UEC) / Minoru Kuribayashi(Shizuoka Univ.) |
| Assistant | Sigeaki Kuzuoka(wakayama univ.) / Hyunho Kang(NIT, Tokyo College) / Harumi Murata(Chukyo Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Information Theory / Technical Committee on Enriched MultiMedia |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Public key attack on knapsak PKC based on subset sum decision problem |
| Sub Title (in English) | |
| Keyword(1) | knapsack PKC |
| Keyword(2) | subset sum decision problem |
| Keyword(3) | public key attack |
| Keyword(4) | equivalent secret key attack |
| 1st Author's Name | Ryuichi Sakai |
| 1st Author's Affiliation | Osaka Electro-Communication University(Osaka Electro-Communication Univ.) |
| 2nd Author's Name | Yasuyuki Murakami |
| 2nd Author's Affiliation | Osaka Electro-Communication University(Osaka Electro-Communication Univ.) |
| Date | 2018-05-17 |
| Paper # | IT2018-6,EMM2018-6 |
| Volume (vol) | vol.118 |
| Number (no) | IT-31,EMM-32 |
| Page | pp.pp.31-34(IT), pp.31-34(EMM), |
| #Pages | 4 |
| Date of Issue | 2018-05-10 (IT, EMM) |