Compact Lattice Anonymous Credentials from Tighter Approximate Range Proofs

Co-authored with Olivier Sanders.

Not yet published.

Abstract

Accommodating cryptographic authenticity with strong user privacy assurances has been the primary motivation for anonymous credentials systems. Their features have recently come into the spotlight with the European Digital Identity (EUDI) wallet initiative, insisting on the need for efficient and private solutions based on well-understood security foundations for high assurances. This coincides with the post-quantum transition, but current quantum-safe solutions based on standard assumptions are still lagging behind the ones on ad-hoc interactive assumptions performance-wise. In this paper, we present several techniques to improve the efficiency of anonymous credentials from standard lattice assumptions, narrowing the gap with more efficient but also more exotic ones. Alongside other optimizations, our main improvement stems from tighter approximate range proofs in the zero-knowledge protocol of Lyubashevsky, Nguyen, Plançon (Crypto’22), currently the efficiency bottleneck of lattice privacy-oriented constructions.