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

Cecilia Boschini, Jan Camenisch, 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.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. MAJOR revision.PQCrypto 2020
DOI
10.1007/978-3-030-44223-1_14
Keywords
zero-knowledge proofsgroup signatureslattice-based cryptographypost-quantum cryptography
Contact author(s)
cecilia boschini @ gmail com
History
Short URL
https://ia.cr/2020/1190

CC BY

BibTeX

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

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.