Cryptographic primitives

We start by describing a number of cryptographic building blocks that are essential for the operations of privacy-preserving payment systems.

Commitment schemes: Commitment schemes allow a party (committer) to commit to a chosen message (chosen statement) while keeping it hidden to others, with the ability to reveal the committed value later. Commitment schemes consist of three operations:

• • params ^ Setup(k), a randomized setup algorithm given input by a security parameter k, and outputting public parameters to be used for the computation of the commitment
• • C_r ^ Commit_{params r}(m), where a commitment on message m is computed using randomness r
• • (r, v) ^ DeCommit_params(C_r), where the committer opens the commitment to a verifier who can then validate it.

Commitment schemes are designed so that they satisfy the following two properties:

• • Binding: Given a commitment C_r to a message m, the committer cannot change the value or statement m they have committed to. That is, they cannot construct another message m' = m such that m' ^ DeCommit_params(C_r).
• • Hiding: Given a commitment value C_r to a message m, the attacker should not be able to retrieve m.

For the schemes described below, Pedersen commitments [22] will be used, where the hiding property is guaranteed against an information theoretic attacker (information theoretically hiding), and the binding property is guaranteed against a computational attacker (computationally binding).

Zero Knowledge Proofs of Knowledge and Signatures of Knowledge: Proof of knowledge protocols allow a party (prover) to prove that a statement is true to another party (verifier) (e.g., that a value v is part of a language L). Zero- knowledge proofs of knowledge enable the prover to achieve the same property without revealing anything else to the verifier apart from the fact that the statement holds.

Most privacy-preserving payment systems built atop Bitcoin use zero-knowledge proofs of knowledge (ZKPoK), and in particular protocols where the prover proves knowledge of a committed value v, without leaking any information on v. In this chapter, we leverage the ZKPoK schemes of Schnorr [23] and its extensions [24-27], and convert them to noninteractive signatures of knowledge [28] using the Fiat-Shamir heuristic [27].

In signature of knowledge schemes, the knowledge of the secret committed value v is used as signing key. The unforgeability property of these schemes implies that no one but the party that has knowledge of v is able to provide a valid signature on any message m (i.e., a signature on m) that the signature verification algorithm accepts.

In the following, we will use the notation of Camenisch and Stadler [25,28,29] when referring to these proofs. Namely,

denotes a noninteractive zero-knowledge proof of knowledge of the elements a and в that satisfy both h = g^a and c = g^e. All values not enclosed in ()s are known to the verifier. Similarly, the extension

indicates a signature of knowledge of a and в on message m.

Accumulators: Cryptographic accumulators basically constitute one-way membership functions; these functions can be used to answer a query whether a given candidate belongs to a set without revealing any meaningful information about the other set members. For the rest of the chapter, we will be referring to the accumulator Acc introduced by Camenisch and Lysyanskaya [30] that supports the following operations:

• • {N, u} ^ ACC.Setup(k). On input a security parameter k, sample primes p and q (with polynomial dependence on the security parameter), Setup computes the RSA modulus N = pq and chooses value u G QR_N, = 1. Finally, Setup outputs (N, u), which will be denoted by params.
• • {Acc} ^ ACC.Accumulate(params, PN). On input params and a set of prime numbers PN = {pi,...,p_n|pj g [A,B]}, where A,B can be chosen with arbitrary polynomial dependence on k, as long as 2 < A and B < A² , ACC. Accumulate computes the accumulator Acc = p₁p₂ • • • p_n ( mod N).
• • ш ^ ACC.GenWitness(params, v, PN). On input params = (N, u), a set of prime numbers PN as described above, and a value v g PN, the witness ш is the accumulation of all the values in Acc besides v (i.e., ш =

ACC.Accumulate(params, Acc|v)).

• {0,1} ^ ACC.Verify(params, Acc, v, ш). On input params (N, u), an element v, and witness ш, ACC.Verify computes Acc' ^ ш^v(modN) and outputs 1 if and only if Acc' = Acc, v is prime, and v G [A, B].

Accumulators in [30] satisfy the strong collision-resistance property if the strong RSA assumption is hard. Informally, this ensures that no computational adversary can produce a pair (v,w) such that v PN and yet ACC.Verify is satisfied. In fact, in [30], Camenisch and Lysyanskaya describe an efficient ZKPoK scheme that proves that a committed value is contained in an accumulator. We refer to the proof in [30] using the following notation: