Cryptology ePrint Archive: Report 2020/007

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

Nabil Alkeilani Alkadri and 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.

Category / Keywords: public-key cryptography / Lattice-based cryptography, Aborts, Hash trees

Original Publication (with minor differences): 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.

Date: received 2 Jan 2020, last revised 14 May 2020

Contact author: nabil alkadri at tu-darmstadt de, rachid elbansarkhani@quanticor-security de

Available format(s): PDF | BibTeX Citation

Version: 20200514:151232 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]