Authentication on the Internet usually has the drawback of leaking the identity of the users, or at least allowing to trace them from a server to another. Anonymous credentials overcome this issue, by allowing users to reveal the attributes necessary for the authentication, without revealing any other information (in particular not their identity). In this article, we provide a generic framework to construct anonymous credential schemes and use it to give a concrete construction of post-quantum (lattice-based) anonymous credential protocol. Our protocol thus allows for long-term security even when one considers the emergence of quantum computers able to break widely used traditional computational assumptions, such as RSA, the discrete logarithm or Diffie-Hellman. We also give a concrete implementation of our protocol, which is only one order of magnitude slower and bandwidth consuming than previous anonymous credentials that are not post-quantum.
Authentication on the Internet usually has the drawback of leaking the identity of the users, or at least allowing to trace them from a server to another. Anonymous credentials overcome this issue, by allowing users to reveal the attributes necessary for the authentication, without revealing any other information (in particular not their identity). In this article, we provide a generic framework to construct anonymous credential schemes and use it to give a concrete construction of post-quantum (lattice-based) anonymous credential protocol. Our protocol thus allows for long-term security even when one considers the emergence of quantum computers able to break widely used traditional computational assumptions, such as RSA, the discrete logarithm or Diffie-Hellman. We also give a concrete implementation of our protocol, which is only one order of magnitude slower and bandwidth consuming than previous anonymous credentials that are not post-quantum.
Anonymous authentication schemes such as group signatures and anonymous credentials are important privacy-protecting tools in electronic communications. The only currently known scheme based on assumptions that resist quantum attacks is the group signature scheme by Gordon et al. (ASIACRYPT 2010). We present a generalization of group signatures called anonymous attribute tokens where users are issued attribute-containing credentials that they can use to anonymously sign messages and generate tokens revealing only a subset of their attributes. We present two lattice-based constructions of this new primitive, one with and one without opening capabilities for the group manager. The latter construction directly yields as a special case the first lattice-based group signature scheme offering full anonymity (in the random-oracle model), as opposed to the practically less relevant notion of chosen-plaintext anonymity offered by the scheme of Gordon et al. We also extend our scheme to protect users from framing attacks by the group manager, where the latter creates tokens or signatures in the name of honest users. Our constructions involve new lattice-based tools for aggregating signatures and verifiable CCA2-secure encryption.
Anonymous credential (AC) systems are privacy-preserving authentication mech-anisms that allow users to prove that they have valid credentials anonymously. These systems provide a powerful tool for several practical applications, such as anonymous pay-ment systems in e-commerce, preserving robust privacy protection for users. Most existing AC systems are constructed using traditional number-theoretic approaches, making them insecure under quantum attacks. With four decades of research in anonymous credential systems, there is a need for a comprehensive review that identifies the design structures of AC systems, organizes the research trends, and highlights unaddressed gaps for the future development of AC, especially bringing AC to post-quantum cryptography. This work is a complete study describing AC systems, as well as their architecture, components, security, and performance. Additionally, real-world implementations of various applications are identified, analyzed, and compared according to the design structure. Lastly, the challenges hindering the shift toward the quantumly secure lattice-based AC designs are discussed.
With the development of quantum computers and quantum algorithms, many of our classical public-key cryptographic systems will be compromised. To circumvent this, one approach is to take our classical cryptographic systems and design them on mathematically hard problems for which no known quantum algorithms can provide a speedup. Our work revolves around one such cryptographic system, the anonymous credential protocol. In this thesis, we implement a post-quantum anonymous credential scheme, and extend it to include additional features like the disclosure of properties of attributes. We implement the protocol in Python, run a series of correctness tests, and then compare our work with implementations from the literature. We also outline a more complete picture of what adversarial models are needed for post-quantum security. The motivation behind our work is to build more usable, feature-intensive anonymous credential systems that are resistant to adversaries with quantum computing capabilities. We present our work as a step towards providing more easily accessiblesoftware for a larger audience to extend.
The Anonymous credential is a fundamental cryptographic primitive for privacy-preserving authentication. Anonymos credentials based on signatures with efficient protocols (SEP) have attracted considerable attention due to their efficiency and compatibility with practical systems. However, most existing SEP-based anonymous credentials rely on classical hardness assumptions and are therefore not expected to withstand quantum adversaries, while post-quantum SEP instantiations remain limited in both number and efficiency. To address these limitations, a novel SEP-based anonymous credential (LSEP-AC) is proposed based on lattice-based cryptographic primitives such as the Plover signature, the LNP framework, and the Ajtai commitment in this paper. In the random oracle model, we formally prove that our LSEP-AC satisfies security properties, including correctness, anonymity, and unforgeability. The theoretical analysis and experimental evaluation both show that the anonymous credential size of the LSEP-AC is about 89.75 KB for 128 bit-security. The total verification key size of the user and issuer is around 2.52 KB, and the total secret key size of the user and issuer is around 7.74 KB, which exhibits significant advantages over related schemes.
Anonymous credential schemes are a key application in modern cryptography. Recent research has advanced these schemes by incorporating issuer-hiding capabilities, which prevent the disclosure of the credential issuer’s identity. While several issuer-hiding anonymous credential schemes exist, none offer resilience against quantum computing adversaries. To address this gap, we propose a post-quantum issuer-hiding anonymous credential scheme, building on the recent work known as ring referral (S&P ’25), which allows anonymous signatures from third-party signers. Ring referral is an integration of ring signature and anonymous credential schemes, enabling issuer-hiding anonymous credentials. In this paper, we present an efficient lattice-based ring referral scheme, which supports quantum-resistant security. Our scheme extends a recent lattice-based credential scheme (CCS ’24) via LNP proof system (CRYPTO ’22).
Anonymous communication networks (ACNs) enable Internet browsing in a way that prevents accessed content from being traced back to the user. This provides a high level of privacy, protecting individuals from being tracked by advertisers, governments, and other entities. The Tor network, a prominent example of such a network, uses a layered encryption scheme to encapsulate data packets, employing Tor nodes to obscure the routing process before the packets enter the public Internet. While Tor is capable of providing substantial privacy, its encryption relies on schemes such as RSA and Diffie-Hellman for distributing symmetric keys, which are vulnerable to quantum computing attacks and are currently in the process of being phased out. To overcome this threat, we propose a quantum resistant alternative to RSA and Diffie-Hellman for distributing symmetric keys, namely, quantum key distribution (QKD). Standard QKD networks depend on trusted nodes to relay keys across long distances. However, reliance on trusted nodes in the quantum network does not meet the criteria necessary for establishing a Tor circuit in the ACN. We address this issue by developing a protocol and network architecture that integrates QKD without the need for trusted nodes, thus meeting the requirements of the Tor network and creating a quantum secure anonymous communication network.