commitment scheme

A commitment scheme allows for one party to publicly commit to some value without revealing that value. For example, Alice wants to bet on the outcome of a coin that Bob will flip. If Alice simply announces her call, Bob can cheat to win the bet by simply announcing the opposite outcome. A commitment scheme allows Alice to commit to her call but not reveal what it is until after Bob has flipped the coin and announced the result.

A commitment scheme should satisfy two properties:

1. Hiding: for all messages $m_0$ and $m_1$, the distributions of the respective commitments COM($m_0$) and $COM(m_1)$ are indistinguishable (e.g., to a polynomial-time algorithm). This guarantees that the message cannot be recovered before being revealed. Note that this property requires commitment schemes to be randomized.
2. Binding: for a given commitment COM, there is exactly one $m$ such that the receiver will accept a reveal of $m$.

Commitment using one-way functions

A general outline for a commitment scheme using a one-way function $f$ is that Alice chooses a random value $x$, then sends $\text{COM} = f(x, m)$ and $\text{DECOM} = (x, m)$. This basically works, but some subtleties need to be considered.

First, we need to ensure binding: that Alice can't fake a different $(x', m')$ suchsimply check that $(f(x), h(x) \otimes= f(x, m)$. This can be done trivially by requiring the one-way function to be injective (one-to-one).

Second, we need ensure hiding: that $m$ cannot be recovered from $f(x, m)$. In general a one-way function guarantees only that we can't recover its full input; it can still leak some bits. We need to rely on a stronger property, namely the existence of a hard-core predicate that is guaranteed to be unrecoverable from $f$.

This motivates the Blum commitment scheme, which exploits the fact that any 1-1 one-way function can be augmented to explicitly define a hard-core bit $h(x)$. To commit to a bit $m\in \{0, 1\}$, Alice samples $x$ randomly from the domain of $f$, and sends

To reveal, she then later sends

Bob can then simply check that $(f(x), h(x)\otimes m)$ matches what was sent earlier. This succeeds at hiding $m$, because to recover it Bob would have to recover the hard-core bit $h(x)$, which is intractable by assumption. And it succeeds at binding Alice to $m$ by the assumption that $f$ is one-to-one, so collisions are impossible.

We can relax the 1-1 requirement and allow $f$ to be a hash function where collisions are simply hard to find, rather than impossible. This adds the subtlety that we no longer want to let Alice have exclusive control of $x$, since she could choose an input $x$ for which a collision is known, so the scheme must be augmented with an extra round of communication (see here: https://en.wikipedia.org/wiki/Commitment_scheme#Bit-commitment_from_a_pseudo-random_generator).

Commitment allowing for a partial reveal

In zero knowledge proof schemes, the prover may want to reveal only part of the message they committed to. This is trivially possible by simply generating separate commitments for each part of the message, and only sending the reveal message for the relevant part(s). However, in this scheme the size of the commitment grows with the number of message parts, which can be undesirable.

A more efficient scheme is for Alice to construct a Merkle tree with the individual commitments as the leaves, so that internal nodes represent hashes of all commitments below them. Alice commits to the full tree by simply transmitting the root hash, of size $O(1)$. She can then reveal any leaf by sending her concrete commitments to that leaf and its sibling (from which the parent hash can be computed) along with the hashes of all sibling nodes along the path to the root --- a proof of size $O(\log_2 n)$ --- so that Bob can check that these commitments are consistent with the root hash she originally sent.

References

• https://www.cs.cmu.edu/~goyal/s18/15503/scribe_notes/lecture22.pdf
• https://en.wikipedia.org/wiki/Commitment_scheme