Cryptology ePrint Archive: Report 2016/399

Slow Motion Zero Knowledge Identifying With Colliding Commitments

Houda Ferradi and Rémi Géraud and David Naccache

Abstract: Discrete-logarithm authentication protocols are known to present two interesting features: The first is that the prover's commitment, $x=g^r$, claims most of the prover's computational effort. The second is that $x$ does not depend on the challenge and can hence be computed in advance. Provers exploit this feature by pre-loading (or pre-computing) ready to use commitment pairs $r_i,x_i$. The $r_i$ can be derived from a common seed but storing each $x_i$ still requires 160 to 256 bits when implementing DSA or Schnorr.

This paper proposes a new concept called slow motion zero-knowledge. SM-ZK allows the prover to slash commitment size (by a factor of 4 to 6) by combining classical zero-knowledge and a timing side-channel. We pay the conceptual price of requiring the ability to measure time but, in exchange, obtain communication-efficient protocols.

Category / Keywords: Authentication protocols, Zero-Knowledge Proof Systems

Original Publication (in the same form): Inscrypt 2015

Date: received 21 Apr 2016, last revised 22 Apr 2016

Contact author: remi geraud at ens fr

Available format(s): PDF | BibTeX Citation

Note: Posted the wrong revised file.

Version: 20160422:110846 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]