Cryptology ePrint Archive: Report 2000/021
An Efficient Identification Scheme Based on Permuted Patterns
Abstract: This paper proposes a new identification scheme based on a hard
partition problem rather than factoring or discrete logarithm
problems. The new scheme minimizes at the same time the communication
complexity and the computational cost required by the parties.
Since only simple operations are needed for an identification,
our scheme is well suited for smart cards with very limited
processing power. With a "good" implementation, the scheme is much
faster than the Fiat-Shamir or Shamir's PKP schemes.
Category / Keywords: Identification, NP-completeness, Smart cards.
Date: received 24 May 2000, revised 16 Jan 2001
Contact author: saeednia at ulb ac be
Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation
Version: 20010116:103950 (All versions of this report)
Short URL: ia.cr/2000/021
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]