Cryptographic Primitives

Algebraic MACs must satisfy correctness – that honestly generated MACs must verify correctly – and existential unforgeability – that those without access to the symmetric key cannot generate MACs on new data.

MACs of this nature are combined with ZK proofs to construct anonymous credentials, for example see Chase et al. [CMZ14].

Accumulators were first introduced by Benaloh and De Mare as a time-stamping protocol.

The main constructions for dynamic accumulators according to Benarroch et al and Boneh et al are:

• RSA-Based: Slow to bootstrap, reasonable performance for updates, proof generation and verification ([BP97, CL02, LLX07, Lip12])
• ECC-based: Smaller and faster proofs than RSA. Setup parameters large and the number of elements they support is fixed after creation. Work on curves that support bilinear pairings. ([DT08, CKS09, Ngu05])
• Merkle hash trees: Short setup parameters and accumulator size depends on tree depth ([[Mer88, CHKO08])

Example ECC-based scheme and example RSA-based implementation.

The key security properties of such protocols are that the final output is pseudorandom against malicious clients, and that malicious servers cannot learn anything about client inputs. If verifiability is required, servers must prove to the client that the PRF output is correct.

OPRF constructions typically considered in anonymous credential schemes include [JKK14] and [[NR04]].

Blind RSA signature

Chaum’s Blind RSA signature scheme, analyzed by Bellare et al. is perhaps the most widely known blind signature scheme. Variations of this protocol, using different message encoding schemes such as FDH and PSS, have been proposed and implemented. Blind RSA can also be made partially oblivious to support a fixed amount of public attributes [AF96], albeit at significant performance costs.

Blind Schnorr signatures

Schnorr signatures gave rise to a plethora of variants, some of them with applications to anonymous credentials and e-voting. A Blind Schnorr signature scheme is a two-party protocol for receiving valid Schnorr signatures on hidden inputs.

Derived from Schnorr blind signatures, partially blind signatures (Abe et al.) are signatures which allow the signature to contain a non-blinded part, that is mutually shared between the server and the client.

Security of most Schnorr signature variants reduces to the ROS problem [Sch01]. [BLL+20] demonstrated a polynomial-time attack against this problem, improving on Wagner’s subexponential-time attack. This impacted most known Schnorr variants. [FPS20] introduced a variant of Schnorr’s protocol that is not known to be vulnerable to this attack.

BBS+ signatures (Boneh-Boyen-Shacham signatures)

First introduced by by Boneh et al. as BBS signatures, and then later improved by Au et al. as BBS+ signatures. Also studied by Camenisch et al..

They allow the multi-message signing while producing a single output signature. This fits naturally the use case of attributes in anonymous credentials.

While pairings are used during the scheme, they are not used for signature verification.

PS signatures (Pointcheval-Sanders signatures)

PS signatures are usually used for threshold issuance.

Related signature scheme

Waters+ signatures

Meiklejohn et al. built on a generalized version of Waters signatures, in combination with Groth-Sahai proofs, to construct a round-optimal, partially oblivious blind signature scheme.

BLS signatures (Boneh–Lynn–Shacham signatures)

BLS signatures is a signature scheme based on pairings, with the security property of signature aggregation. This allows multiple signatures to be aggregated into a single signature and verified as such. By using this property we can design anonymous credential schemes with selective attribute disclosure.

Mercurial Signatures

Mercurial signatures are a useful building block for privacy-preserving schemes, such as anonymous credentials, delegatable anonymous credentials, and related applications. They allow a signature σ on a message m under a public key pk to be transformed into a signature σ′ on an equivalent message m′ under an equivalent public key pk′ for an appropriate notion of equivalence. For example, pk and pk′ may be unlinkable pseudonyms of the same user, and m and m′ may be unlinkable pseudonyms of a user to whom some capability is delegated.

Signatures of Knowledge

Signatures of Knowledge allow one to issue signatures on behalf of any NP statement, that can be interpreted as follows: “A person inpossession of a witness to the statement that x∈L has signed message m.”

We demand essentially three main properties from zero knowledge proofs: completeness, which means that honestly-generated proofs should always verify; soundness, which protects the verifier and states that it is computationally unfeasible for an attacker to generate invalid proofs; zero-knowledge, which means that the proof itself leaks no information besides what can be already inferred by the statement itself.

Depending on the anonymous credential application, different notion of soundness might apply.