Commitment scheme

From Wikipedia, the free encyclopedia
Jump to: navigation, search


Commitment schemes and their possible applications can be demonstrated 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:





Coin flipping[edit]

Suppose Alice and Bob want to resolve some dilemma via coin flipping. If they are physically in the same place, a typical procedure might be:

  1. Alice "calls" the coin flip
  2. Bob flips the coin

If they are not in the same place, this procedure is faulty. Alice would have to trust Bob's report of how the coin flip turned out, whereas Bob knows what result is more desirable for him. Using commitments, a similar procedure is:

  1. Alice "calls" the coin flip and tells Bob only a commitment to her call,
  2. Bob flips the coin and reports the result,
  3. Alice reveals what she committed to
  4. If Alice's revelation matches the coin result Bob reported, Alice wins


A way to visualize a commitment scheme is to think of the sender as putting the value in a locked box, and giving the box to the receiver. The value in the box is hidden from the receiver, who cannot open the lock themselves. Since the receiver has the box, the value inside cannot be changed—merely revealed if the sender chooses to give them the key at some later time.

Zero-knowledge proofs[edit]


Signature schemes[edit]



Verifiable secret sharing[edit]


Defining the security of commitment schemes[edit]




Computational binding[edit]

Let open be chosen from a set of size 2^k, i.e., it can represented as a k bit string, and let Commit_k be the corresponding commitment scheme. As the size of k determines the security of the commitment scheme it is called the security parameter.

Then for all non-uniform probabilistic polynomial time algorithms that output x,x' and open,open' of increasing length k, the probability that x \neq x' and Commit_k(x,open)=Commit_k(x',open') is a negligible function in k.

This is a form of asymptotic analysis. It is also possible to state the same requirement using concrete security: A commitment scheme Commit is (t,\epsilon) secure, if for all algorithms that run in time t and output x,x',open,open' the probability that x \neq x' and Commit(x,open)=Commit(x',open') is at most \epsilon.

Perfect, statistical and computational hiding[edit]

Let U_k be the uniform distribution over the 2^k opening values for security parameter k. A commitment scheme is perfect, statistical, computational hiding, if for all x\neq x' the probability ensembles \{Commit_k(x,U_k)\}_{k\in\N} and \{Commit_k(x',U_k)\}_{k\in\N} are equal, statistically close, or computationally indistinguishable.

Constructing commitment schemes[edit]


Bit-commitment from any one-way permutation[edit]


(h,f(x),b \oplus h(x))


Bit-commitment from a pseudo-random generator[edit]




To decommit Alice sends Y to Bob, who can then check whether he initially received G(Y) or G(Y) \oplus R.

This scheme is statistically binding, meaning that even if Alice is computationally unbounded she cannot cheat with probability greater than 2-n. For Alice to cheat, she would need to find a Y', such that G(Y') = G(Y) \oplus R. If she could find such a value, she could decommit by sending the truth and Y, or send the opposite answer and Y'. However, G(Y) and G(Y') are only able to produce 2n possible values each (that's 22n) while R is picked out of 23n values. She does not pick R, so there is a 22n/23n = 2-n probability that a Y' satisfying the equation required to cheat will not exist.







Quantum bit commitment[edit]




See also[edit]


  13. ^ A. Kent: Secure classical Bit Commitment using Fixed Capacity Communication Channels

External links[edit]