Work of Camenisch and Lysyanskaya on Anonymous Credentials

Abstract[From the paper “Signature Schemes with Efficient Protocols” by Camenisch and Lysyanskaya] Digital signature schemes are a fundamental cryptographic primitive, of use both in its own right, and as a building block in cryptographic protocol design. In this paper, we propose a practical and provably secure signature scheme and show protocols (1) for issuing a signature on a committed value (so the signer has no information about the signed value), and (2) for proving knowledge of a signature on a committed value. This signature scheme and corresponding protocols are a building block for the design of anonymity-enhancing cryptographic systems, such as electronic cash, group signatures, and anonymous credential systems. The security of our signature scheme and protocols relies on the Strong RSA assumption. These results are a generalization of the anonymous credential system of Camenisch and Lysyanskaya.
Year2000-2005
Link to the paperhttps://link.springer.com/chapter/10.1007/978-3-540-28628-8_4
Relevance scoreRelevant
Quality score5
LabelsAnonymous CredentialsClassic referenceGood reference sourceSignature schemeVerifiable Credentials

In this note we provide a brief overview of some classical work on Anonymous Credentials (AC). The motivation for doing so is due to:

Introduction

Camenisch and Lysyanskaya are central authors in the Anonymous Credential (AC) literature published around 2000-2005.

Their methods for constructing ACs have appeared as a primitive in some other papers and projects we have reviewed (see below). Additionally, they are heavily cited.

Their schemes are sometimes referred to as “classical Anonymous Credential systems” (see, e.g. the paper from Zero-knowledge credentials with deferred revocation checks)

Next, we list some papers by these two authors. We also mention other projects where such references have been used.

Abstract primitives

The authors define an AC to be an Issuer’s signature on the Holder’s private key sksk and perhaps some further attributes.

To create and use such ACs, they build the following primitives:

With these, the Holder can obtain a signature on its secret key sksk, with the Issuer never learning sksk. This allows the Holder to remain anonymous.

Additionally, the Holder can now prove to a Verifier that it knows a signature from the Issuer on sksk. Again, no private data is leaked.

Remark 1 — Strong privacy goals

This emphasis on the Holder remaining anonymous to the Issuer is stronger than in other projects we have reviewed, such as W3C’s specification (where it is not discouraged nor recommended, and it is barely discussed).

Remark 2 — Why sign the secret key

Why sign sksk and not the Holder’s public key pkpk? Because if the AC was a signature on, say, pkpk, anyone could impersonate the Holder.

Remark 3 — Efficiency constraints

In principle, Protocol A could be realized by a 2-party computation protocol; and Protocol B could be realized by a ZK proof of knowledge.

However, around 2000-2005 these primitives were not efficient enough. As a result, part of the two author’s work is motivated by the need of circumventing these two technical limitations.

Anonymous Credential system from the paper “A signature scheme with efficient protocols”

In this section, we describe a variation of the AC scheme presented in the paper “A signature scheme with efficient protocols” by Camenisch and Lysyanskaya.

The variation appears in the paper “Efficient Attributes for Anonymous Credentials” by Camenisch and Gross. It is the scheme used in the paper Towards Smart Contract-based Verification of Anonymous Credentials and it is natively supported in Hyperledger Indy.

The variation defines an AC as an Issuer’s signature on the Holder’s secret key sksk, together with some attributes A1,,AkA_1, \ldots, A_k. The scheme allows for efficient selective disclosure of attributes during verification time.

The original scheme of Camenisch and Lysyanskaya did not support the usage of attributes.

Strong RSA assumption

The security of the scheme relies on the following assumption:

Strong RSA assumption Given an RSA modulus n=pqn=pq (with p,qp,q being “safe primes”) and a random element gZng\in\mathbb{Z}_n^*, it is hard to compute hZnh\in \mathbb{Z}_n^* and an integer e>1e> 1 such that hegmodnh^e \equiv g \mod n,

It differs from the usual RSA assumption in that the adversary is able to choose the exponent ee.

It holds “generically” in the plain model.

Camenisch-Lysyanskaya (CL)-signatures

Parameters: m,e,n,λ,L\ell_m, \ell_e, \ell_n, \lambda, L. The parameter λ\lambda is the security parameter.

Key generation: Choose an n\ell_n-bit RSA modulus n=pqn=pq. Choose uniformly random R0,,RL1,S,ZQRnR_0, \ldots, R_{L-1}, S, Z \in QR_n, where QRnQR_n denotes the set of quadratic residues of Zn\mathbb{Z}_n^*, i.e. the set of squares of Zn\mathbb{Z}_n^*.

The public key is pk=(n,R0,,RL1,S,Z)pk= (n, R_0, \ldots, R_{L-1}, S, Z).

The secret key is sk=psk=p.

Message space: {(m0,,mL1)mi±{0,1}m}\{ (m_0, \ldots, m_{L-1}) \mid m_i \in \pm \{0,1\}^{\ell_m} \}

Here ±{0,1}m\pm \{0,1\}^{\ell_m} denotes the set of all positive integers of up to m\ell_m bits, together with all their additive inverses.

In the AC scheme, m0m_0 is the Holder’s secret key, and m1,,mL1m_1, \ldots, m_{L-1} are the Holder’s attributes.

Signing algorithm:

On input (m0,,mL1)(m_0, \ldots, m_{L-1}), choose a random prime ee and a random integer vv of sufficient bit length ( e>m+2\ell_e > \ell_m+2 and v=n+m+λ,respectively)\ell_v=\ell_n + \ell_m + \lambda, respectively).

Compute

A:=(ZR0m0RL1mL1Sv)1/emodn.\begin{equation}A:= \left(\frac{Z}{R_0^{m_0} \cdots R_{L-1}^{m_{L-1}}S^v }\right)^{1/e} \mod n.\end{equation}

(this is done by finding dd such that ed1mod(p1)(q1)ed \equiv 1 \mod (p-1)(q-1) and taking A=(ZR0m0RL1mL1)dA= \left(\frac{Z}{R_0^{m_0} \cdots R_{L-1}^{m_{L-1}} }\right)^d)

The signature is (e,A,v)(e, A, v).

Verification algorithm

To verify that (e,A,v)(e,A,v) is a signature on (m0,,mL1)(m_0,\ldots, m_{L-1}), one checks that Equation (1) holds by asserting:

ZAeR0m0RL1mL1SvmodnZ\equiv A^e R_0^{m_0} \cdots R_{L-1}^{m_{L-1}}S^v \mod n\\

Additionally one also checks that mi±{0,1}mm_i\in \pm \{0,1\}^{\ell_m} for all ii (i.e. the message has the correct shape) and that 2e>e>2e1 2^{\ell_e} > e > 2^{\ell_e -1} (i.e. ee is in the correct range).

Theorem [Camenisch and Lysyanskaya] Under the strong RSA assumption, this signature scheme is secure against an attacker with adaptive chosen messages

(i.e., that’s an attacker A\mathcal{A} that has an oracle for generating signatures on messages of A\mathcal{A}’s choice, and its goal is to create valid signatures without the use of the oracle (I don’t know if it is secure for existential forgeries or selective forgeries)).

Protocol B: Proving ownership of a CL signature

The goal is to allow a signature holder to prove it has a valid signature from the signature issuer without revealing the message signed, nor the signature (this is for unlinkability purposes).

We will use zero-knowledge proofs of knowledge of discrete logarithms. I.e. a protocol that allows to, given z,g1,,gmz, g_1,\ldots, g_m, prove in ZK that one knows γ1,,γm\gamma_1, \ldots, \gamma_m such that

z=g1γ1gmγmz= g_1^{\gamma_1}\ldots g_m^{\gamma_m}.

With such a proof of knowledge, the signature holder could reveal AA, and then prove in ZK that it knows (e,v,m0,,mL1)(e, v, m_0, \ldots, m_{L-1}) such that

ZAeR0m0RL1mL1Svmodn.Z\equiv A^e R_0^{m_0} \cdots R_{L-1}^{m_{L-1}}S^v \mod n.\\

Recall that in our AC scheme the signature (e,A,v)(e,A,v) is treated as an Anonymous Credential. The protocol just described would be used to verify a credential without revealing its contents (= the signed message).

However, as is, each time the same credential is verified, the same value AA is revealed. This makes the verification of credentials linkable.

Below we see how to avoid revealing AA.

(Note: For simplicity, we omit some technicalities, such as the fact that the elements mim_i and ee need to be “range-checked”)

Other than that, it can be seen that proving knowledge of such tuple (e,v,m0,,mL1)(e, v, m_0, \ldots, m_{L-1}) essentially implies that someone who knows the secret key pp has provided the holder with (A,e,v).(A, e, v).

How to avoid revealing AA?

Notice that if (e,A,v)(e, A, v) is a valid signature on (m0,,mL1)(m_0, \ldots, m_{L-1}), then for any integer rr,

(e,A:=ASrmodn,v:=v+er)(e, A':= AS^{-r} \mod n, v':= v+er)

is also a valid signature. Indeed:

AeR0m0RL1mL1SvAeR0m0RL1mL1SreSv+erZmodnA'{}^{e} R_0^{m_0} \cdots R_{L-1}^{m_{L-1}}S^{v'} \equiv A^eR_0^{m_0} \cdots R_{L-1}^{m_{L-1}} S^{-re} S^{v+er} \equiv Z \mod n\\

Hence, instead of revealing AA, the signature holder can choose a random rr, reveal A:=ASrmodnA' := AS^{-r} \mod n, and follow the strategy outlined previously to prove that it knows (e,v,m0,,mL1)(e, v’, m_0, \ldots, m_{L-1}) such that AeR0m0RL1mL1SvZmodnA'{}^{e} R_0^{m_0} \cdots R_{L-1}^{m_{L-1}}S^{v'} \equiv Z \mod n.

In this case, the information revealed will be different each time this subprotocol is executed, making credential verification unlinkable.

Note: to switch on linkability, simply stop sampling reveal AA during verification.

This can be interesting to prevent double usage of the same credential.

Protocol A: Signing a committed message with the signer not learning the message

Let m:=(m0,,mL1)\vec{m}:=(m_0, \ldots, m_{L-1}) be a message held by the Holder.

Commitment

To commit m\vec{m} we use a Pedersen-type commitment. Namely, we take parameters g0,,gm,hZng_0,\ldots, g_m, h\in \mathbb{Z}_n^* be random elements. Then, to commit m\vec{m}, the Holder chooses a random integer rr and sets

Com(m;r):=hri=0L1gimimodnCom(\vec{m}; r):= h^r \prod_{i=0}^{L-1} g_i^{m_i} \mod n

(Note: This commitment scheme is normally used in groups where the Discrete Log is hard, and not in RSA groups, but Damgard and Fujisaki showed that it can be used on an RSA group to commit integers of arbitrary size).

Signing on the committed message

Suppose the Holder has published a commitment CC to its message m\vec{m}.

Then the Holder chooses a random integer uu and publishes

C=R0m0RL1mL1SuC'= R_0^{m_0} \cdots R_{L-1}^{m_{L-1}} S^u

Next, the Holder proves in zero-knowledge that CC and CC' are Pedersen commitments to the same message using a dedicated subprotocol.

Now the Signer proceeds as in the original signing algorithm, computing

A:=(ZCSv)1/emodn.A:= \left(\frac{Z}{C' S^{v} }\right)^{1/e} \mod n.

for some random vv', e>1e>1, and publishing (e,A,v)(e,A,v) as the signature.