Paper 2020/1190

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

Cecilia Boschini, Jan Camenisch, Max Ovsiankin, and Nicholas Spooner


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.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Major revision. PQCrypto 2020
zero-knowledge proofsgroup signatureslattice-based cryptographypost-quantum cryptography
Contact author(s)
cecilia boschini @ gmail com
2020-09-30: received
Short URL
Creative Commons Attribution


      author = {Cecilia Boschini and Jan Camenisch and Max Ovsiankin and Nicholas Spooner},
      title = {Efficient Post-Quantum SNARKs for RSIS and RLWE and their Applications to Privacy},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1190},
      year = {2020},
      doi = {10.1007/978-3-030-44223-1_14},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.