Cryptology ePrint Archive: Report 2010/624

No-leak authentication by the Sherlock Holmes method

Dima Grigoriev and Vladimir Shpilrain

Abstract: We propose a class of authentication schemes that are literally zero-knowledge, as compared to what is formally defined as ``zero-knowledge" in cryptographic literature. We call this ``no-leak" authentication to distinguish from an established ``zero-knowledge" concept. The ``no-leak" condition implies ``zero-knowledge" (even ``perfect zero-knowledge"), but it is actually stronger, as we illustrate by examples. The principal idea behind our schemes is: the verifier challenges the prover with questions that he (the verifier) already knows answers to; therefore, even a computationally unbounded verifier who follows the protocol cannot possibly learn anything new during any number of authentication sessions. This is therefore also true for a computationally unbounded passive adversary.

Category / Keywords: cryptographic protocols / authentication, zero knowledge

Date: received 7 Dec 2010, last revised 8 Feb 2012

Contact author: shpil at groups sci ccny cuny edu

Available formats: PDF | BibTeX Citation

Version: 20120208:134353 (All versions of this report)

Discussion forum: Show discussion | Start new discussion