Paper 2016/399

Slow Motion Zero Knowledge Identifying With Colliding Commitments

Houda Ferradi, 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.

Note: Posted the wrong revised file.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Inscrypt 2015
Keywords
Authentication protocolsZero-Knowledge Proof Systems
Contact author(s)
remi geraud @ ens fr
History
2016-04-22: last of 3 revisions
2016-04-21: received
See all versions
Short URL
https://ia.cr/2016/399
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/399,
      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{https://eprint.iacr.org/2016/399}},
      url = {https://eprint.iacr.org/2016/399}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.