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

Nabil Alkeilani Alkadri; Rachid El Bansarkhani; Johannes Buchmann

Paper 2020/007

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

Nabil Alkeilani Alkadri, Rachid El Bansarkhani, and Johannes Buchmann

Abstract

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.

Metadata

Available format(s): PDF
Category: 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.
Keywords: Lattice-based cryptography Aborts Hash trees
Contact author(s): nabil alkadri @ tu-darmstadt de
rachid elbansarkhani @ quanticor-security de
History: 2020-05-14: last of 2 revisions; 2020-01-03: received; See all versions
Short URL: https://ia.cr/2020/007
License: CC BY

BibTeX

@misc{cryptoeprint:2020/007,
      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},
      url = {https://eprint.iacr.org/2020/007}
}