Commitment Schemes

Scenario: Coin Tossing Over the Phone

Imagine two people, Àdébísí and Bọ́lá, want to flip a coin to decide who should pay for drinks, but they are communicating over the phone and, thus, cannot physically toss a coin in the view of both of them. More concretely:

  1. Àdébísí and Bọ́lá want to flip a coin.
  2. Àdébísí secretly decides her guess for “heads” or “tails”.
  3. Bọ́lá flips the coin and announces the result.
  4. Àdébísí reveals her guess, proving she didn’t cheat by changing her guess after hearing the result.
  5. Àdébísí wins the game if her guess matches the announced result.

In this scenario, Àdébísí and Bọ́lá can use a commitment scheme that allows one party to “commit” to a chosen value while keeping it hidden to the other party until an appropriate time. [1]

This ensures neither party can cheat:

  • Àdébísí cannot change her guess after Bọ́lá announces the result (binding).
  • Bọ́lá cannot deduce Àdébísí’s guess before she reveals it (hiding).

A commitment scheme is a cryptographic primitive that allows one party (the sender) to commit to a chosen value while keeping it hidden from another party (the receiver), with the ability to reveal the committed value later. Commitment schemes are essential building blocks in various cryptographic protocols, such as zero-knowledge proofs and secure multi-party computations.

Properties of Commitment Schemes

A commitment scheme must satisfy two fundamental properties:

  1. Binding Property
    • Once the sender has committed to a value, they cannot change it.
    • This ensures that the commitment is “binding,” preventing the sender from lying about the value during the reveal phase.
  2. Hiding Property
    • The commitment does not reveal any information about the value to the receiver until the sender decides to reveal it.
    • This ensures that the value is “hidden” until the sender discloses it.

Phases of a Commitment Scheme

A commitment scheme typically involves two phases:

  1. Commit Phase
    • The sender chooses a value m and generates a commitment C using a commitment function, often involving random coins r.
    • C = \text{Commit}(m, r)
    • The commitment C is sent to the receiver.
  2. Reveal Phase
    • The sender reveals m and r to the receiver.
    • The receiver verifies the commitment C by checking if C = \text{Commit}(m, r).

Hiding

The hiding property of a commitment scheme ensures that the commitment does not reveal any information about the committed value m to the receiver until the sender decides to reveal it. In other words, the commitment conceals the value m while still binding the sender to that value.

Types of Hiding

  1. Perfect/Statistical Hiding: The commitment C provides no information about m at all, even with infinite computational power. This is achieved if the distribution of C is independent of m.
  2. Computational Hiding: It is computationally infeasible for the receiver to deduce m from C (in polynomial time in relevant parameters).

Binding

The binding property in a commitment scheme ensures that once a sender commits to a value, they cannot change it later. This property prevents the sender from “cheating” by revealing a different value during the reveal phase.

Types of Binding

  1. Perfect/Statistical Binding: It is mathematically impossible to find two different values m_1 and m_2 that produce the same commitment C.
  2. Computational Binding: Finding such a pair (m_1, r_1) and (m_2, r_2), that produces the same commitment C, is computationally infeasible for any adversary with limited computational resources.

Exercise

Prove that a commitment scheme cannot be both perfectly hiding and perfectly binding at the same time.

References

[1] Gilles Brassard, David Chaum, and Claude Crépeau, Minimum Disclosure Proofs of Knowledge, Journal of Computer and System Sciences, vol. 37, pp. 156–189, 1988.

[2] Manuel Blum, Coin Flipping by Telephone, Proceedings of CRYPTO 1981.

[3] Oded Goldreich, Silvio Micali, and Avi Wigderson, Proofs that yield nothing but their validity, or all languages in NP have zero-knowledge proof systems, Journal of the ACM, 38: 3, pp. 690–728, 1991

🎉 Happy New Year! 🎉

Here’s to a year filled with joy, success, and unforgettable memories. 🥂🎆

With love,
Daniel Alabi

Leave a comment