Commitment scheme

From Wikipedia, the free encyclopedia

In cryptography, a commitment scheme or a bit commitment scheme is a method that allows a user to commit to a value while keeping it hidden, and while preserving the user's ability to reveal the committed value later. A useful 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 (without the help of the sender), but since the receiver has the box, the value inside cannot be changed. Commitment schemes are important to a variety of cryptographic protocols, especially zero-knowledge proofs and secure computation.

A simple example of an application of commitments is secure coin-flipping. The problem is this: 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) Bob "calls" the coin flip, and (2) Alice flips the coin, and if Bob's call is correct, he wins, otherwise Alice does. If they are not in the same place, however, this procedure is faulty because Bob would have to trust Alice's report of how the coin flip turned out, whereas Alice knows what result is more desirable for her.

Using commitments, a similar procedure is: (1) Bob "calls" the coin flip and tells Alice only a commitment to his call, (2) Alice flips the coin and reports the result, (3) Bob reveals what he committed to; if that matches the coin result Alice reported, Bob wins. If Alice can skew the results in her favor, she must be able to understand the call hidden in Bob's commitment, so if the commitment scheme is a good one, Alice cannot skew the results. Similarly, Bob cannot affect the result if he cannot change the value he commits to.^[1][2]

Contents 1 Terminology 2 Applications 3 Constructing commitment schemes 3.1 Bit-commitment from any one-way function 3.2 Bit-commitment from a pseudo-random generator 3.3 A perfectly binding scheme based on the discrete log problem 4 Quantum bit commitment 5 References 6 External links

[edit] Terminology

The interactions in a commitment scheme take place in two phases: the commit phase during which a value is chosen and specified, and the reveal phase during which the value is revealed and checked. In the simplest commitment schemes, the commit phase consists of a simple message from the sender to the receiver, while the reveal phase consists of a single message from the sender to the receiver, followed by a check performed by the receiver.

The two cryptographic properties of a commitment scheme are the hiding property (that the value chosen during the commit phase cannot be discovered) and the binding property (that the value chosen during the commit phase is the only one that can be revealed during the reveal phase).

A "bit commitment" scheme is simply a commitment scheme where the value chosen is a bit. The terms "bit commitment" and "commitment" are sometimes used interchangeably.

[edit] Applications

The concept of bit commitment schemes was first formalized by Gilles Brassard, David Chaum, and Claude Crepeau in 1988,^[3] but the concept was used without being treated formally prior to that^[2][4]. The notion of commitments appeared earliest in works by Manuel Blum ^[1], Shimon Even ^[5], and Shamir et al. ^[6]; the terminology seems to have been originated by Blum ^[4].

Commitments are used in a wide variety of cryptographic protocols, in order to bind a party to a value so that they cannot adapt to other messages in order to gain some kind of inappropriate advantage.

One particular motivating example is the use of commitment schemes in zero-knowledge proofs. Commitments are used in zero-knowledge proofs for two main purposes: first, to allow the prover to participate in "cut and choose" proofs where the verifier will be presented with a choice of what to learn, and the prover will reveal only what corresponds to the verifier's choice. Commitment schemes allow the prover to specify all the information in advance in a commitment, and only reveal what should be revealed later in the proof.^[7] Commitments are also used in zero-knowledge proofs by the verifier, who will often specify their choices ahead of time in a commitment. This allows zero-knowledge proofs to be composed in parallel without revealing additional information.^[8]

Another important application of commitments is in verifiable secret sharing, a critical building block of secure multiparty computation. In a secret sharing scheme, each of several parties receive "shares" of a value that is meant to be hidden from everyone. If enough parties get together, their shares can be used to reconstruct the secret, but even a malicious cabal of insufficient size should learn nothing. Secret sharing is at the root of many protocols for secure computation: in order to securely compute a function of some shared input, the secret shares are manipulated instead. However, if shares are to be generated by malicious parties, it may be important that those shares can be checked for correctness. In a verifiable secret sharing scheme, the distribution of a secret is accompanied by commitments to the individual shares. The commitments reveal nothing that can help a dishonest cabal, but the shares allow each individual party to check to see if their shares are correct.

[edit] Constructing commitment schemes

A commitment scheme can either be perfectly binding (it is impossible for Alice to alter her commitment after she has made it, even if she has unbounded computational resources) or perfectly concealing (it is impossible for Bob to find out the commitment without Alice revealing it, even if he has unbounded computational resources) but not both.

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

One can create a bit-commitment scheme from any one-way function. The scheme relies on the fact that every one-way function can be modified (via the Goldreich-Levin theorem) to possess a computationally hard-core predicate. Let f be a one-way function, with h a hard-core predicate. Then to commit to a bit b Alice picks a random input x and sends the triple

to Bob, where denotes XOR, i.e. addition modulo 2. To decommit Alice simply sends x to Bob. This scheme concealing because for Bob to recover b he must recover h(x). Since h is a computationally hard-core predicate, recovering h(x) from f(x) with probability greater than one-half is as hard as inverting f.

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

Note that since we do not know how to construct a one-way permutation from any one-way function, this section reduces the strength of the cryptographic assumption necessary to construct a bit-commitment protocol.

In 1991 Moni Naor ^[9] showed how to create a bit-commitment scheme from a cryptographically secure pseudorandom number generator. The construction is as follows. If G is pseudo-random generator such that G takes n bits to 3n bits, then if Alice wants to commit to a bit b

• Bob selects a random 3n-bit vector R and sends R to Alice.
• Alice selects a random n-bit vector Y and computes the 3n-bit vector G(Y).
• If b=1 Alice sends G(Y) to Bob, otherwise she sends the bitwise exclusive-or of G(Y) and R to Bob.

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

This scheme is statistically binding, meaning that even if Alice is computationally unbounded she cannot cheat with probability greater than 2^-n. The concealing property follows from a standard reduction, if Bob can tell whether Alice committed to a zero or one, he can also distinguish the output of the pseudo-random generator G from true-random, which contradicts the cryptographic security of G.

[edit] A perfectly binding scheme based on the discrete log problem

Alice chooses a group of prime order p, with generator g.

Alice randomly picks a secret value x from 0 to p − 1 to commit to and calculates c = g^x and publishes c. The discrete logarithm problem dictates that from c, it is computationally infeasible to compute x, so under this assumption, Bob cannot compute x. On the other hand, Alice cannot compute a x' <> x, such that g^x' = c, so the scheme is binding.

This scheme isn't perfectly concealing as someone could find the commitment if he manages to solve the discrete logarithm problem. (In fact, this scheme isn't hiding at all with respect to the standard hiding game, where an adversary should be unable to guess which of two messages he chose were committed to - similar to the IND-CPA game. A better example of a perfectly binding commitment scheme is one where the commitment is the encryption of x under a semantically secure, public-key encryption scheme, and the decommitment is the string of random bits used to encrypt x.)

[edit] Quantum bit commitment

It is an interesting question in quantum cryptography if there exist unconditionally secure bit commitment protocols on the quantum level, that is protocols which are (at least asymptotically) binding and concealing even if there are no restrictions on the computational resources. One could hope that there might be a way to exploit the intrinsic properties of quantum mechanics, as in the protocols for unconditionally secure key distribution.

However, Dominic Mayers (see ^[10] for the original proof) showed in 1996, that this is impossible. Any such protocol can be reduced to a protocol where the system is in one of two pure states after the commitment phase, depending on the bit Alice wants to commit. If the protocol is unconditionally concealing, then Alice can unitarily transform these states into each other using the properties of the Schmidt decomposition, effectively defeating the bindingness property.

One subtle assumption of the proof is that the commit phase must be finished at some point in time. This leaves room for protocols that require a continuing information flow until the bit is unveiled or the protocol is cancelled, in which case it is not binding anymore ^[11].

[edit] References

[edit] External links

• Quantum bit commitment on arxiv.org