Paper 2020/007

On Lattice-Based Interactive Protocols: An Approach with Less or No Aborts

Nabil Alkeilani Alkadri, Rachid El Bansarkhani, and Johannes Buchmann


A canonical identification (CID) scheme is a 3-move protocol consisting of a commitment, challenge, and response. It constitutes the core design of many cryptographic constructions such as zero-knowledge proof systems and various types of signature schemes. Unlike number-theoretic constructions, CID in the lattice setting usually forces provers to abort and repeat the whole authentication process once the distribution of the computed response does not follow a target distribution independent from the secret key. This concept has been realized by means of rejection sampling, which makes sure that the secrets involved in a protocol are concealed after a certain number of repetitions. This however has a negative impact on the efficiency of interactive protocols because it leads to a number of communication rounds that is multiplicative in the number of aborting participants (or rejection sampling procedures). In this work we show how the CID scheme underlying many lattice-based protocols can be designed with smaller number of aborts or even without aborts. Our new technique exploits (unbalanced) binary hash trees and thus significantly reduces the communication complexity. We show how to apply this new method within interactive zero-knowledge proofs. We also present BLAZE+: a further application of our technique to the recently proposed lattice-based blind signature scheme BLAZE (FC'20). We show that BLAZE+ has an improved performance and communication complexity compared to BLAZE while preserving the size of keys and signatures.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Minor revision. An extended abstract of this paper will appear in the proceedings of the 25th Australasian Conference on Information Security and Privacy (ACISP 2020). This is the full version.
Lattice-based cryptographyAbortsHash trees
Contact author(s)
nabil alkadri @ tu-darmstadt de
rachid elbansarkhani @ quanticor-security de
2020-05-14: last of 2 revisions
2020-01-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nabil Alkeilani Alkadri and Rachid El Bansarkhani and Johannes Buchmann},
      title = {On Lattice-Based Interactive Protocols: An Approach with Less or No Aborts},
      howpublished = {Cryptology ePrint Archive, Paper 2020/007},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.