Paper 2016/399

Slow Motion Zero Knowledge Identifying With Colliding Commitments

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


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.

Note: Posted the wrong revised file.

Available format(s)
Publication info
Published elsewhere. Inscrypt 2015
Authentication protocolsZero-Knowledge Proof Systems
Contact author(s)
remi geraud @ ens fr
2016-04-22: last of 3 revisions
2016-04-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Houda Ferradi and Rémi Géraud and David Naccache},
      title = {Slow Motion Zero Knowledge Identifying With Colliding Commitments},
      howpublished = {Cryptology ePrint Archive, Paper 2016/399},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.