Paper 2022/926

Zero-Knowledge in EasyCrypt

Denis Firsov, Tallinn University of Technology, Guardtime
Dominique Unruh, University of Tartu
Abstract

We formalize security properties of zero-knowledge protocols and their proofs in EasyCrypt. Specifically, we focus on sigma-protocols (three-round protocols). Most importantly, we also cover properties whose security proofs require the use of rewinding; prior work has focused on properties that do not need this more advanced technique. On our way we give generic definitions of the main properties associated with sigma protocols, both in the computational and information-theoretical setting. We give generic derivations of soundness, (malicious-verifier) zero-knowledge, and proof of knowledge from simpler assumptions with proofs which rely on rewinding. Also, we address sequential composition of sigma protocols. Finally, we illustrate the applicability of our results on three zero-knowledge protocols: Fiat-Shamir (for quadratic residues), Schnorr (for discrete logarithms), and Blum (for Hamiltonian cycles, NP-complete).

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
cryptography formal methods EasyCrypt zero-knowledge sigma protocols rewinding
Contact author(s)
denis firsov @ gmail com
unruh @ ut ee
History
2022-07-15: approved
2022-07-15: received
See all versions
Short URL
https://ia.cr/2022/926
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/926,
      author = {Denis Firsov and Dominique Unruh},
      title = {Zero-Knowledge in EasyCrypt},
      howpublished = {Cryptology ePrint Archive, Paper 2022/926},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/926}},
      url = {https://eprint.iacr.org/2022/926}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.