Paper 2022/803

How to Avoid Repetitions in Lattice-based Deniable Zero-Knowledge Proofs

Xavier Arnal, Universitat Politècnica de Catalunya
Abraham Cano, Universitat Politècnica de Catalunya
Tamara Finogina, Scytl (Spain)
Javier Herranz, Universitat Politècnica de Catalunya

Interactive zero-knowledge systems are a very important cryptographic primitive, used in many applications, especially when deniability (also known as non-transferability) is desired. In the lattice-based setting, the currently most efficient interactive zero-knowledge systems employ the technique of rejection sampling, which implies that the interaction does not always finish correctly in the first execution; the whole interaction must be re-run until abort does not happen. While repetitions due to aborts are acceptable in theory, in some practical applications it is desirable to avoid re-runs for usability reasons. In this work we present a generic technique that departs from an interactive zero-knowledge system (that might require multiple re-runs to complete the protocol) and obtains a 3-moves zero-knowledge system (without re-runs). The transformation combines the well-known Fiat-Shamir technique with a couple of initially exchanged messages. The resulting 3-moves system enjoys honest-verifier zero-knowledge and can be easily turned into a fully deniable proof using standard techniques. We show some practical scenarios where our transformation can be beneficial and we also discuss the results of an implementation of our transformation.

Note: New title, a new co-author, new material (an implementation section) and rewriting of abstract and introduction, to better describe the motivation of the work. The theoretical contribution is essentially the same as in the original submission. Removed incorrect sentence at the end of Section 3

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. to appear in the proceedings of NordSec 2022
zero-knowledge lattices rejection sampling deniability
Contact author(s)
xavier arnal @ upc edu
abraham cano @ upc edu
tamara finogina @ scytl com
javier herranz @ upc edu
2022-12-21: last of 2 revisions
2022-06-21: received
See all versions
Short URL
No rights reserved


      author = {Xavier Arnal and Abraham Cano and Tamara Finogina and Javier Herranz},
      title = {How to Avoid Repetitions in Lattice-based Deniable Zero-Knowledge Proofs},
      howpublished = {Cryptology ePrint Archive, Paper 2022/803},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.