Commitment scheme

From Wikipedia, the free encyclopedia

In cryptography, a commitment scheme or a bit commitment scheme is a method of sending hidden information such that it is verifiable in spite of possible later bias from either the sender or the receiver. Commitment is related to digital timestamping and zero knowledge proof and finds application in electronic cash, electronic voting and online games.

An example of when this is necessary: Suppose two people, Alice and Bob, have opposed interests; and they decide to resolve their dilemma via coin flipping. If Alice flips the coin, then both Alice and Bob can see the coin and are committed to live by its judgment -- no problem has yet occurred. Modifying the example, suppose that Bob cannot witness the outcome -- perhaps he is blind; or perhaps he is on the other side of a telephone. Alice is not necessarily trustworthy; so perhaps Alice will lie about what side actually came up.

A commitment scheme allows Alice to commit to one option without telling Bob about it. Then Bob can call the coin-toss without knowing what Alice committed to; and finally, both Bob and Alice can know both the outcome of the coin toss and the outcome of Bob's knowledge without dispute.

A very simple commitment scheme can be provided by simply involving a trusted third party to hold the hidden knowledge in a sort of escrow. As an example, a secure computer might be entrusted with Alice's message under a username and password, with some sort of timestamp or no-edit policy. Then Alice could provide the username to Bob, Bob could provide his guess to Alice, and after all that, Alice could provide the password to Bob as well.

A useful way to visualize a commitment scheme is to think of Alice as putting the message in a box, securing the box with a lock to which only she has the key, and giving the box to Bob. The challenge, of course, is to find mathematical constructions that capture the behavior of the box, lock and key.

A simple commitment scheme is the following: if b is the commitment, Alice generates a large random number r and gives to Bob a hash of b concatenated with r. To open her commitment, Alice reveals b and r thus letting Bob recalculate the hash and compare it with the hash given him earlier to make sure Alice didn't cheat.

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.

1 Constructing commitment schemes
2 Quantum bit commitment
3 References
4 External links

[edit] Constructing commitment schemes

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

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

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

to Bob, where $\oplus$ 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 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 [1] showed how to create a bit-commitment scheme from a cryptographically secure pseudo-random 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 $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. 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 ^[1] 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 ^[2].