Post-Quantum Verifiable Credentials

Verifiable Credentials

Verifiable Credentials (VCs) are digital credentials designed to represent information that would otherwise be stored in physical credentials, such as passports, driving licences, university degrees, subscriptions to a service, etc. Thanks to the use of cryptography, VCs have several advantages over their physical counterparts. In particular, they are tamper-resistant, privacy-respecting, and machine-verifiable in a decentralized way. VCs are defined in the Verifiable Credentials Data Model of the World Wide Web Consortium open standards [1].

VCs are the top layer (Layer 3) of the Self-Sovereign Identity (SSI) reference model; see Figure 1. Layer 1 is used to store information about public identities and is implemented by a Verifiable Data Registry (VDR), while Layer 2 is used to initiate peer authentication and employs Decentralized Identifiers (DIDs) – in this blog post, we will not focus on these two layers.

Layer 3 works according to the so-called Triangle of Trust (ToT), which consists of three entities:

• The Issuer of the VC (e.g., the government or a private company) is the entity that creates and signs the verifiable credential, ensuring the credential’s credibility and authenticity.
• The Holder of the VC is the entity (an individual or an organization) that can generate Verifiable Presentations (VPs) to prove its Claims (e.g., age of majority, driving license, subscription to a service).
• The Verifier is the entity that receives and checks the VPs of the Holder.

A credential system based on plaintext VCs does not protect the privacy of the Holder because the VC, the claims in the VP, and the digital signature of the Issuer are exchanged in plain text. In particular, plaintext VCs result in the linkability and traceability of peers.

Anonymous VCs (also known as Zero-Knowledge VCs) represent a privacy-preserving alternative that enables the Holder to manage its VCs by choosing the level of information disclosure. For anonymous VCs, the roles in the ToT are modified as follows.

• The Issuer asserts the capability of a Holder to prove its identity, possibly based on the knowledge of some secret attributes. After proper verification, the Issuer issues the anonymous VC to the Holder.
• The Holder owns the anonymous VC and can take advantage of zero-knowledge cryptographic primitives and protocols to interact with the Issuer and Verifier in a privacy-preserving way. This means that the Holder can obtain a VC and prove that its identity satisfies certain properties while still maintaining the desired level of privacy. These operations can happen in a completely anonymous way (i.e., without revealing any identity details) or by selectively disclosing only a subset of the claims contained in the VC (i.e., without revealing specific secret attributes). The Holder can prove, via a VP, to the Verifier that its VC is legitimate, which means it contains a valid signature generated by an Issuer, known as the Proof of Knowledge of a Signature (PoKS).
• The Verifier receives a PoKS from the Holder and verifies that the Holder actually holds a valid VC, containing the undisclosed secrets and a valid signature from an Issuer.

Post-Quantum Verifiable Credentials

QUBIP is implementing post-quantum plaintext VCs (with both a pure post-quantum and a post-quantum/traditional hybrid approach) and post-quantum anonymous VCs with selective disclosure capabilities. This transition exercise employs the IOTA Identity library [2], which is a widely used SSI library written in Rust and is the result of a large open-source, community-led SSI project maintained by the IOTA Foundation. This library provides all the functionality to handle W3C-compliant DIDs, DID documents, VCs, and VPs. In essence, it is a general-purpose SSI library, and therefore the perfect target for a transition exercise.

Plaintext VCs

The main cryptographic technologies in SSI with plaintext VCs are traditional public-key digital signature schemes. These are based on cryptographic assumptions, such as the hardness of the factorization problem and the discrete logarithm problem, which no longer hold in the presence of (sufficiently powerful) quantum computers capable of running Shor’s algorithm. Therefore, the transition to post-quantum plaintext VCs, while technically challenging, is conceptually easy: it mostly involves replacing traditional public-key digital signature schemes with their post-quantum counterparts. Specifically, QUBIP is transitioning plaintext VCs to post-quantum by employing the digital signature schemes of the Module-Lattice-Based Digital Signature Standard (ML-DSA), which is close to final standardization, thus ensuring both current security requirements and timely implementation of the project [3].

Anonymous VCs

As for plaintext VCs, anonymous VCs based on traditional cryptography, such as CL [4] or BBS${}^{+}$ [5], are primarily based on the assumption of the hardness of the discrete logarithm problem, making them unsuitable for the post-quantum world. However, in contrast to plaintext VCs, transitioning anonymous VCs to the post-quantum world is significantly more complex.

Indeed, as we mentioned before, anonymous VCs require a mechanism for a PoKS. A PoKS, in turn, usually consists of two parts: a “signature scheme with efficient protocols” (informally, a digital signature scheme with specific features such as the ability to sign committed hidden messages and to prove knowledge of a signature on such messages) and an associated zero-knowledge proof system. While there are many practical proposals for post-quantum zero-knowledge proof systems, the state of post-quantum “signature schemes with efficient protocols” is still at the frontier of research.

First, post-quantum anonymous VCs have been proposed only recently (not before 2022) [6, 7, 8, 9], with the exception of the proposal of Libert et al. [10], which is however impractical due to having a signature size of at least 670 MB [6, p. 4]. Second, the literature on post-quantum anonymous VCs is quite scarce, essentially only the aforementioned papers. Third, none of the papers introducing these schemes is accompanied by a software implementation, nor does any of them take into account implementation issues such as performance and protection against side-channel attacks.

The four proposed schemes [10, 6, 7, 8] are all based on lattice assumptions. The first three represent sequential improvements on each other, with proof sizes steadily decreasing—from 670 MB in [10], to 640 kB in [6], and finally to 500 kB in [7].

The fourth scheme [8], authored by Bootle, Lyubashevsky, Nguyen, and Sorniotti, takes a different approach from the previous proposals. This scheme, which we refer to as the “BLNS framework”, provides the shortest credentials yet, with a size of around 125 kB. In addition to its compactness, the BLNS framework has strong security properties. Specifically, even if the Issuer and Verifier are malicious and collaborate, the process of issuing and verifying a set of attributes reveals no information about the Holder’s non-disclosed attributes. Additionally, the scheme guarantees that malicious Holders cannot generate valid VPs for attributes that were not originally issued by the Issuer, even in scenarios of collusion.

For transitioning anonymous VCs into the post-quantum era, QUBIP has chosen the BLNS framework. This selection is due to its small proof size, maturity in terms of implementability (the paper provides several pages of pseudocode), and security properties tailored for web applications.

BLNS is based on the hardness of a family of lattice problems called ${\mathsf{\text{ISIS}}}_f$, which is parameterized by a function $f:[N]\to {\mathbb{Z}}_p$, where ISIS stands for Inhomogeneous Shortest Integer Solution. The problem ${\mathsf{\text{ISIS}}}_f$ is too technical to be stated here in its entirety. However, roughly speaking, given a random matrix $A\in {\mathbb{Z}}_p^{m\times n}$ and access to an oracle that chooses a random $x\in [N]$ and returns $(x,\overrightarrow{s})$, where $\overrightarrow{s}$ is a short vector such that $A\overrightarrow{s}=f(x)$, the task is to produce a pair $(x^{\prime },\overrightarrow{s}{}^{\prime })$, where $x^{\prime }\in [N]$, $\overrightarrow{s}{}^{\prime }$ is a short vector with $A\overrightarrow{s}{}^{\prime }=f(x^{\prime })$, and $(x^{\prime },\overrightarrow{s}{}^{\prime })$ has not been previously outputed by the oracle.

The problem ${\mathsf{\text{ISIS}}}_f$ has not been considered in previous schemes, but it is a very natural generalization of the underlying problem upon which the classic GPV signature scheme is based [11], and it is also similar to other recently and independently proposed lattice assumptions [12]. Furthermore, when the function $f$ is modeled as a random oracle and $A$ is chosen from a distribution with enough entropy, the ${\mathsf{\text{ISIS}}}_f$ problem becomes equivalent to the well-known $\mathsf{\text{SIS}}$ and $\mathsf{\text{ISIS}}$ lattice problems.

In the concrete instantiation of ${\mathsf{\text{ISIS}}}_f$ in the BLNS framework, $f$ is chosen as a linear function of the binary representation of the input $x\in [N]$. At first glance, this might seem like a bad choice, since linearity appears to be exploitable. However, upon further consideration, the condition that $\overrightarrow{s}$ must be a short vector prevents such exploitation (essentially because the sum of random binary vectors is not a binary vector, except with negligible probability).

References