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
-
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},
url = {https://eprint.iacr.org/2016/399}
}
