Cryptology ePrint Archive: Report 2020/1190

Efficient Post-Quantum SNARKs for RSIS and RLWE and their Applications to Privacy

Cecilia Boschini and Jan Camenisch and Max Ovsiankin and Nicholas Spooner

Abstract: In this paper we give efficient statistical zero-knowledge proofs (SNARKs) for Module/Ring LWE and Module/Ring SIS relations, providing the remaining ingredient for building efficient cryptographic protocols from lattice-based hardness assumptions. We achieve our results by exploiting the linear-algebraic nature of the statements supported by the Aurora proof system (Ben-Sasson et al.), which allows us to easily and efficiently encode the linear-algebraic statements that arise in lattice schemes and to side-step the issue of "relaxed extractors", meaning extractors that only recover a witness for a larger relation than the one for which completeness is guaranteed. We apply our approach to the example use case of partially dynamic group signatures and obtain a lattice-based group signature that protects users against corrupted issuers, and that produces signatures smaller than the state of the art, with signature sizes of less than 300 KB for the comparably secure version of the scheme. To obtain our argument size estimates for proof of knowledge of RLWE secret, we implemented the NIZK using libiop.

Category / Keywords: public-key cryptography / zero-knowledge proofs, group signatures, lattice-based cryptography, post-quantum cryptography

Original Publication (with major differences): PQCrypto 2020
DOI: 10.1007/978-3-030-44223-1_14

Date: received 29 Sep 2020

Contact author: cecilia boschini at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20200930:075039 (All versions of this report)

Short URL: ia.cr/2020/1190