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
[ Cryptology ePrint archive ]