Commitment Schemes

Basic concepts and ideas

Motivation: a day at Christie’s

Let us consider the following situation: Alice is in Christie’s to get Banksy’s last masterpiece (previously, she made sure that the artwork would not self-destruct once sold).

Christie’s opts for the Vickrey sealed bid auction-style. It is a pretty common practice, but let’s remember how it works: each participant submits a secret sealed bid for a piece. Once all the bids are in, the party who submitted the highest bid gets a piece, and the price paid is the second-highest bid.

Commitment schemes solve exactly this problem: they allow to securely commit to a secret value, and reveal it afterwards, so third parties can check that the commitment agrees with the value revealed.

This article will be a walk from the basics of commitment schemes, such as hash-based commitments, to more advanced concepts like vector-commitment schemes. During this promenade, we’ll introduce schemes that are being explored in blockchain technology, such as the Pedersen and Elgamal commitments, that will lead to switch commitments. We end up giving an idea of vector commitments.

Definitions and properties

A commitment scheme consists of two phases, Commit and Reveal, involving a deterministic polynomial-time algorithm

1. Commit phase: in this stage, the sender commits to a binary value m by computing c = Comm(u, m) for a uniformly random binary u in and sending c to the receiver, who stores the result for later checking.
2. Reveal phase: in this stage, the sender opens c by sharing u and m with the receiver, who computes by himself c’ = Comm(u, m) and checks c’ = c.

In the particular situation where the committed message is a bit, we will talk about bit commitment schemes.

We require the following properties:

1. It must be hiding, meaning that the distributions induced by Comm(u, 0), Comm(u, 1) are indistinguishable. In other words: Comm reveals nothing about m.
2. It must be binding, meaning that, for any adversary, the probability of getting Comm(u, 0) = Comm(u’, 1) for two random binary u and u’ is negligible. This means that it should be infeasible for the sender to output a commitment that it can be later open to two different messages.

Two distinctions stand: if the adversary is restricted to probabilistic polynomial-time algorithms, the commitment scheme is called either computationally hiding or binding. Otherwise, the scheme will be called perfectly hiding or binding.

It would be amazing to have a commitment scheme being both perfectly binding and hiding. Yes, it would be so, but as in our childhood: you can’t have it all. Why? Imagine a commitment scheme being information-theoretically binding, meaning that it would be impossible to find random binary u and u’ such that:

otherwise, the sender would be able to compute both u and u’ and open the commitment at its will. Nevertheless, if the sender commits to 0 by computing c = Comm(u, 0) the receiver would notice, using brute force, that there is no u’ such that c = Comm(u’, 1) therefore the receiver would know that the committed bit is 0, and the scheme would not be hiding.

A couple of recipes

We can create commitment schemes pretty easily if following the two recipes below. The merit lies in creating schemes that are efficient and have good hiding and binding properties.

One of the recipes to create commitment schemes is using a collision-resistant hash function H and defining a computationally binding, and hiding, commitment scheme such that:

• Commits to any message m by setting c = Comm(u, m) = H(u||m).
• Opens a commitment by revealing the pair (u, m) and checking that the equality c = H(u||m) holds.

Another way to create a commitment scheme is by using a cryptosystem, either symmetric or asymmetric, indeed: in this kind of scheme we generate the pair (sk, pk) of public and secret keys, and then deletes the secret key sk (for the sake of security, otherwise we could simply decrypt the committed value).

• To commit to a value m, a user samples some randomness parameter r and outputs

• To open a commitment c we reveal (m, r) and check if

We observe that if the cryptosystem is IND-CPA secure, the resulting commitment scheme will be computationally hiding and perfectly binding.

Two proposals that we all should know

This is an active topic in cryptography, especially since it proved particularly useful in blockchain technology and confidential transactions. We can find several proposals including the Damgard-Groth commitment, the Gennaro commitment, the MacKenzie-Yang scheme, the Galindo-Garcia-Van Rossum commitment or the Naor commitment. Nevertheless, towards our interests, we are focusing on two proposals that became particularly popular: the Pedersen commitment and the Elgamal commitment (also spelt ElGamal in the literature).

Pedersen commitment

In this commitment scheme we have the following setup: let q be a prime and G a cyclic group of order q and two generators g and y.

To commit to m ∈ Zq the sender chooses uniformly random element r ∈ Zq and outputs

• To open a commitment c the sender reveals the pair (m, r). The receiver accepts the opening to m if

Observe that if group G is secure under the discrete logarithm assumption, then this commitment is perfectly hiding and computationally binding.

Elgamal commitment

In this case let us assume, as for the Pedersen commitment, that G is a cyclic group of prime order q, and that one is given two generators g and y.

• To commit to an element m ∈ G, one takes uniformly at random r ∈ Zq and sets

• To open a commitment c the sender reveals the pair (m, r). The receiver accepts the opening to m if

We observe that Elgamal commits to elements of G, whilst Pedersen commits to elements of Zq. Concerning its properties, the Elgamal commitment is perfectly binding but computationally hiding.

Switch commitments

So we have a commitment scheme that is perfectly hiding and computationally binding, and another scheme being the opposite: computationally hiding and perfectly binding. Furthermore, these are two very efficient schemes. Combining them cannot lead to a perfectly hiding and binding scheme (remember: you can’t have it all).

We could try to create a primitive with the property of being at some point perfectly hiding and at some moment perfectly binding. This primitive is the so-called switch commitment: a combination of Pedersen and Elgamal commitments.

Switch commitments, combined with range proofs, play an important role in cryptocurrencies involving confidential transactions and are quantum-resistant against attacks trying to endanger discrete logarithm security. Explaining quantum resistance is never an easy task, but for those interested in this aspect of switch commitments, here you have a good reference.

To be a bit more formal, a switch commitment consists of four algorithms:

1. A setup that outputs a public random string when given a security parameter as input.
2. A commitment algorithm that outputs a commitment together with opening information when given a public random string and a message as inputs.
3. A partial-verification algorithm that outputs 1 if the partial opening information was valid for the commitment associated with.
4. A full-verification algorithm that outputs 1 if the full opening information was valid for the commitment associated with.

A switch commitment must satisfy:

• That the commitment algorithm is computationally hiding.
• That the partial-verification algorithm is computationally binding.
• That the full-verification algorithm is perfectly binding.

Let us get more concise. In our setting we have

1. The algorithm Setup(l, d) initializes a multiplicative group G of prime order q, samples random generators g and y and outputs crs = (G, g, y, d).
2. The commitment algorithm Comm(crs, m) samples a random r ∈ Zq and outputs the pair

3. The partial-verification algorithm VerifyP(crs, c, op, m) returns 1 if

4. The full-verification algorithm VerifyF(crs, c, op, m) returns 1 if

Some people argue that storing the Elgamal component may imply a storage overhead. We can bypass this issue by setting

for some hash function H and a random r’ ∈ Zq, and then defining

This trick allows us to encapsulate the Elgamal commitment into Pedersen’s commitment. In this case, op = r’ and partial verification checks whether

Switch commitments, combined with range proofs, play an important role in cryptocurrencies involving confidential transactions and are quantum-resistant against attacks trying to endanger discrete logarithm security.

On post-quantum proposals

Some authors have been exploring quantum-resistant commitment schemes. In this direction, we highlight the work done by Benhamouda, Krenn, Lyubashevsky and Pietrzak which have designed an efficient commitment scheme, together with a zero-knowledge proof, based on the hardness of the learning with errors over rings problem.

There are other constructions based on the hardness of lattices problems, like Jain et al. proposal whose hiding property is based on the learning parity with noise problem (LPN). LPN is the learning with errors problem with q = 2.

Baum et al. present a practical construction of an additively homomorphic commitment scheme based on structured lattice assumptions, together with a zero-knowledge proof of opening knowledge. Their scheme is a design improvement over the previous work of Benhamouda et al. in that it is not restricted to being perfectly binding. While it is possible to instantiate their scheme to be perfectly binding or perfectly hiding, it is most efficient when both hiding and binding properties are only computational.

Vector commitment schemes

Lattices are not being explored only for the definition of quantum-resistant commitment schemes. The short integer solution problem, which we will describe in a moment, leads to an interesting commitment scheme: vector commitments.

Vector commitments allow committing concisely to an ordered sequence of values so that the values at desired positions can later be proved concisely, i.e.: given a committed d-dimensional vector m, we may prove that m[i] is exactly the ith entry of m. Vector commitments and the associated proofs can be updated to reflect changes to individual entries using knowledge of just those changes.

In this setting, binding is by positional binding, meaning that it should be infeasible to open a commitment at a position i as two different message entries m[i] and m’[i]. For hiding, we require positional hiding, meaning that the commitment and openings reveal nothing about unopened message entries.

Being more formal, a vector commitment scheme with message space M, commitment space C and proof space P is the set of algorithms below:

1. Setup(l, d) output a public commuter parameter cp and verifier parameter vp.
2. Comm(cp, m) takes a d-dimensional message m and outputs a commitment c together with a committer state st.
3. Open(cp, st, i∈[d]) outputs a proof pi ∈ P for the ith entry of the committed message associated to st.
4. Verify(vp, c, m[i], pi) outputs either 1 or 0.

These algorithms must satisfy the following correctness condition: for any d-dimensional m, i ∈ [d], (cp, vp) = Setup(l, d), (c, st) = Comm(cp, m) and proof pi = Open(cp, st, i) the verification algorithm Verify(vp, c, i, m[i], pi) outputs 0 with negligible probability.

A vector commitment scheme is perfectly updatable if the simulations of generating updates for a commitment and a proof to a new entry of the message and generating a completely new commitment and proof on the updated message are indistinguishable.

The security of vector commitment schemes relies on the hardness of the (homogeneous) short integer solution problem which requires, given a uniformly random (n x m)-matrix A with coefficients in Zq, to find a non-zero integer m-vector z such that Az ≡ 0 (mod q) and ║z║< n for some n > 0.

Finale

In this article, we introduced the main concepts and techniques that, hopefully, will help to get an idea and follow the research that is being carried in a topic that claims its place in the blockchain framework.

Those who had the patience to get to the end of the post should have a (clear) idea of how Pedersen and Elgamal commitments work, so they will understand (a part of) the guts of confidential transactions. Concerning vector commitments, we hope to be have been able to transmit the main ideas which should be a good start before diving into the details of the area and its applications in the design of proof of space protocols.