Commitment Scheme

In cryptography, a commitment scheme allows one to commit to a chosen value (or chosen statement) while keeping it hidden to others, with the ability to reveal the committed value later . Commitment schemes are designed so that a party cannot change the value or statement after they have committed to it: that is, commitment schemes are binding. Commitment schemes have important applications in a number of cryptographic protocols including secure coin flipping, zero-knowledge proofs, and secure computation.

We demonstrate the idea of commitment schemes and their possible applications with a simple example: Say that two people want to play rock-paper-scissors by email. The problem with trying to do so, is that one player may simply wait until they receive the other's email of, say, "rock" and then quickly reply with, say, "paper", winning the game. This problem can be overcome by commitment schemes. At the beginning of the game, each player commits to rock, paper, or scissors. After they have done so, each reveals the choice that they committed to earlier. It is not possible to cheat because as mentioned, commitment schemes are binding.

Interactions in a commitment scheme take place in two phases:

1. the commit phase during which a value is chosen and specified
2. the reveal phase during which the value is revealed and checked

In simple protocols, the commit phase consists of a single message from the sender to the receiver. This message is called the commitment. It is essential that the specific value chosen cannot be known by the receiver at that time (this is called the hiding property). A simple reveal phase would consist of a single message, the opening, from the sender to the receiver, followed by a check performed by the receiver. The value chosen during the commit phase must be the only one that the sender can compute and that validates during the reveal phase (this is called the binding property).

The concept of commitment schemes was first formalized by Gilles Brassard, David Chaum, and Claude Crepeau in 1988, but the concept was used without being treated formally prior to that. The notion of commitments appeared earliest in works by Manuel Blum, Shimon Even, and Shamir et al. The terminology seems to have been originated by Blum, although commitment schemes can be interchangeably called bit commitment schemes—sometimes reserved for the special case where the committed value is a binary bit.