Presentation | 2006-05-19 New public-key identification schemes based on NP-complete problems Shunichi HAYASHI, Mitsuru TADA, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | In this paper, we present two public-key identification schemes based on NP-complete problems. The one is constructed based on a problem related to lattices, named NELVP, and the other is constructed based on the Subset Sum problem. It is not shown that these schemes have the zero-knowledge property, but we show that these ones have the witness hiding property. It is considered that the witness hiding property is sufficient to assure the security of identification schemes, and therefore, our schemes are also proved to be secure. Moreover, from the result of the comparison of efficiency between our schemes and others, our schemes outperform the other ones in terms of the number of repetitions for a required security level or the running time of one execution of identification protocols. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | public-key identification scheme / NP-complete problem / lattice / Subset Sum problem |
Paper # | ISEC2006-6 |
Date of Issue |
Conference Information | |
Committee | ISEC |
---|---|
Conference Date | 2006/5/12(1days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | |
Vice Chair | |
Secretary | |
Assistant |
Paper Information | |
Registration To | Information Security (ISEC) |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | New public-key identification schemes based on NP-complete problems |
Sub Title (in English) | |
Keyword(1) | public-key identification scheme |
Keyword(2) | NP-complete problem |
Keyword(3) | lattice |
Keyword(4) | Subset Sum problem |
1st Author's Name | Shunichi HAYASHI |
1st Author's Affiliation | Graduate School of Science and Technology, Chiba University() |
2nd Author's Name | Mitsuru TADA |
2nd Author's Affiliation | Institute of Media and Information Technology, Chiba University |
Date | 2006-05-19 |
Paper # | ISEC2006-6 |
Volume (vol) | vol.106 |
Number (no) | 51 |
Page | pp.pp.- |
#Pages | 7 |
Date of Issue |