Paper 2021/942

Compact Ring Signatures from Learning With Errors

Rohit Chatterjee, Sanjam Garg, Mohammad Hajiabadi, Dakshita Khurana, Xiao Liang, Giulio Malavolta, Omkant Pandey, and Sina Shiehian

Abstract

Ring signatures allow a user to sign a message on behalf of a ``ring'' of signers, while hiding the true identity of the signer. As the degree of anonymity guaranteed by a ring signature is directly proportional to the size of the ring, an important goal in cryptography is to study constructions that minimize the size of the signature as a function of the number of ring members. In this work, we present the first compact ring signature scheme (i.e., where the size of the signature grows logarithmically with the size of the ring) from the (plain) learning with errors (LWE) problem. The construction is in the standard model and it does not rely on a common random string or on the random oracle heuristic. In contrast with the prior work of Backes et al. [EUROCRYPT'2019], our scheme does not rely on bilinear pairings, which allows us to show that the scheme is post-quantum secure assuming the quantum hardness of LWE. At the heart of our scheme is a new construction of compact and statistically witness indistinguishable ZAP arguments for NP $\cap$ coNP, that we show to be sound based on the plain LWE assumption. Prior to our work, statistical ZAPs (for all of NP) were known to exist only assuming sub-exponential LWE. We believe that this scheme might find further applications in the future.

Note: Fixed a citation

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in CRYPTO 2021
Keywords
Ring SignaturesLearning With ErrorsProof SystemsArgument SystemsCorrelation IntractabilityZAPs
Contact author(s)
shiayan @ umich edu
History
2022-05-05: revised
2021-07-13: received
See all versions
Short URL
https://ia.cr/2021/942
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/942,
      author = {Rohit Chatterjee and Sanjam Garg and Mohammad Hajiabadi and Dakshita Khurana and Xiao Liang and Giulio Malavolta and Omkant Pandey and Sina Shiehian},
      title = {Compact Ring Signatures from Learning With Errors},
      howpublished = {Cryptology ePrint Archive, Paper 2021/942},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/942}},
      url = {https://eprint.iacr.org/2021/942}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.