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