International Association
for Cryptologic Research

We present a framework for building practical anonymous credential schemes based on the hardness of lattice problems. The running time of the prover and verifier is independent of the number of users and linear in the number of attributes. The scheme is also compact in practice, with the proofs being as small as a few dozen kilobytes for arbitrarily large (say up to $2^{128}$) users with each user having several attributes. The security of our scheme is based on a new family of lattice assumptions which roughly states that given short pre-images of random elements in some set $S$, it is hard to create a pre-image for a fresh element in such a set. We show that if the set admits efficient zero-knowledge proofs of knowledge of a commitment to a set element and its pre-image, then this yields practically-efficient privacy-preserving primitives such as blind signatures, anonymous credentials, and group signatures. We propose a candidate instantiation of a function from this family which allows for such proofs and thus yields practical lattice-based primitives.

We present our recent cryptanalytical results concerning the OpenPGP standard and a number of its most popular implementations. Our corresponding research paper was accepted to CCS'21 and was presented last November. As the OpenPGP encryption standard is widely adopted in practice and has millions of users that critically depend on it, and we found its most used implementations, prominently including \texttt{gnupg}, crucially flawed, we believe our results are of relevance and interest for the RWC'22 audience. In a nutshell, our attacks exploit that different OpenPGP implementations assume different interpretations of ElGamal encryption (group structure, generators, etc).