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.^{[1]} 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, zeroknowledge proofs, and secure computation.
A way to visualize a commitment scheme is to think of a sender as putting a message in a locked box, and giving the box to a receiver. The message in the box is hidden from the receiver, who cannot open the lock themselves. Since the receiver has the box, the message inside cannot be changed—merely revealed if the sender chooses to give them the key at some later time.
Interactions in a commitment scheme take place in two phases:

the commit phase during which a value is chosen and specified

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,^{[2]} but the concept was used without being treated formally prior to that.^{[3]}^{[4]} The notion of commitments appeared earliest in works by Manuel Blum,^{[5]} Shimon Even,^{[6]} and Shamir et al.^{[7]} The terminology seems to have been originated by Blum,^{[4]} although commitment schemes can be interchangeably called bit commitment schemes—sometimes reserved for the special case where the committed value is a binary bit.
Contents

Applications 1

Coin flipping 1.1

Zeroknowledge proofs 1.2

Signature schemes 1.3

Verifiable secret sharing 1.4

Defining the security of commitment schemes 2

Computational binding 2.1

Perfect, statistical, and computational hiding 2.2

Constructing commitment schemes 3

Bitcommitment in the random oracle model 3.1

Bitcommitment from any oneway permutation 3.2

Bitcommitment from a pseudorandom generator 3.3

A perfectly binding scheme based on the discrete log problem 3.4

Quantum bit commitment 4

See also 5

References 6

External links 7
Applications
Coin flipping
Suppose Alice and Bob want to resolve some dispute via coin flipping. If they are physically in the same place, a typical procedure might be:

Alice "calls" the coin flip

Bob flips the coin

If Alice's call is correct, she wins, otherwise Bob wins
If Alice and Bob are not in the same place a problem arises. Once Alice has "called" the coin flip, Bob can stipulate the flip "results" to be whatever is most desirable for him. Similarly, if Alice doesn't announce her "call" to Bob, after Bob flips the coin and announces the result, Alice can report that she called whatever result is most desirable for her. Alice and Bob can use commitments in a procedure that will allow both to trust the outcome:

Alice "calls" the coin flip but only tells Bob a commitment to her call,

Bob flips the coin and reports the result,

Alice reveals what she committed to,

Bob verifies that Alice's call matches her commitment,

If Alice's revelation matches the coin result Bob reported, Alice wins
For Bob to be able to skew the results to his favor, he must be able to understand the call hidden in Alice's commitment. If the commitment scheme is a good one, Bob cannot skew the results. Similarly, Alice cannot affect the result if she cannot change the value she commits to.^{[3]}^{[5]}
Zeroknowledge proofs
One particular motivating example is the use of commitment schemes in zeroknowledge proofs. Commitments are used in zeroknowledge 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.^{[8]} Commitments are also used in zeroknowledge proofs by the verifier, who will often specify their choices ahead of time in a commitment. This allows zeroknowledge proofs to be composed in parallel without revealing additional information.^{[9]}
Signature schemes
The Lamport signature scheme is a digital signature system that relies on maintaining two sets of secret data packets, publishing verifiable hashes of the data packets, and then selectively revealing partial secret data packets in a manner that conforms specifically to the data to be signed. In this way, the prior public commitment to the secret values becomes a critical part of the functioning of the system.
Because the Lamport signature system cannot be used more than once (see the relevant article for details), a system to combine many Lamport Keysets under a single public value that can be tied to a person and verified by others was developed. This system uses trees of hashes to compress many published lamportkeycommitments sets into a single hash value that can be associated with the prospective author of later verified data.
Verifiable secret sharing
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.
Defining the security of commitment schemes
Formal definitions of commitment schemes vary strongly in notation and in flavour. The first such flavour is whether the commitment scheme provides perfect or computational security with respect to the hiding or binding properties. Another such flavour is whether the commitment is interactive, i.e. whether both the commit phase and the reveal phase can be seen as being executed by a cryptographic protocol or whether they are noninteractive, consisting of two algorithms Commit and CheckReveal. In the latter case CheckReveal can often be seen as a derandomised version of Commit, with the randomness used by Commit constituting the opening information.
If the commitment C to a value x is computed as C:=Commit(x,open) with open the randomness used for computing the commitment, then CheckReveal(C,x,open) simply consists in verifying the equation C=Commit(x,open).
Using this notation and some knowledge about mathematical functions and probability theory we formalise different versions of the binding and hiding properties of commitments. The two most important combinations of these properties are perfectly binding and computationally hiding commitment schemes and computationally binding and perfectly hiding commitment schemes. Note that no commitment scheme can be at the same time perfectly binding and perfectly hiding  a computationally unbounded adversary can simply generate Commit(x,open) for every value of x and open until finding a pair that outputs C, and in a perfectly binding scheme this uniquely identifies x.
Computational binding
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 nonuniform 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
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
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.
Bitcommitment in the random oracle model
Bitcommitment schemes are trivial to construct in the random oracle model. Given a hash function H with a 3k bit output, to commit to kbit message m, Alice generates a random k bit string R and sends Bob H(Rm). The probability that any R ', m ' exist where m ' ≠ m such that H(R 'm ') = H(Rm) is ≈ 2^{k}, but to test any guess at the message m Bob will need to make 2^{k} (for an incorrect guess) or 2^{k1} (on average, for a correct guess) queries to the random oracle.^{[10]}
Bitcommitment from any oneway permutation
One can create a bitcommitment scheme from any oneway function that is injective. The scheme relies on the fact that every oneway function can be modified (via the GoldreichLevin theorem) to possess a computationally hardcore predicate (while retaining the injective property). Let f be an injective oneway function, with h a hardcore 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. Bob verifies by computing f(x) and comparing to the committed value. This scheme is concealing because for Bob to recover b he must recover h(x). Since h is a computationally hardcore predicate, recovering h(x) from f(x) with probability greater than onehalf is as hard as inverting f. Perfect binding follows from the fact that f is injective and thus f(x) has exactly one preimage.
Bitcommitment from a pseudorandom generator
Note that since we do not know how to construct a oneway permutation from any oneway function, this section reduces the strength of the cryptographic assumption necessary to construct a bitcommitment protocol.
In 1991 Moni Naor^{[11]} showed how to create a bitcommitment scheme from a cryptographically secure pseudorandom number generator. The construction is as follows. If G is pseudorandom generator such that G takes n bits to 3n bits, then if Alice wants to commit to a bit b:

Bob selects a random 3nbit vector R and sends R to Alice.

Alice selects a random nbit vector Y and computes the 3nbit vector G(Y).

If b=1 Alice sends G(Y) to Bob, otherwise she sends the bitwise exclusiveor 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}. 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 2^{n} possible values each (that's 2^{2n}) while R is picked out of 2^{3n} values. She does not pick R, so there is a 2^{2n}/2^{3n} = 2^{−n} probability that a Y' satisfying the equation required to cheat will not exist.
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 pseudorandom generator G from truerandom, which contradicts the cryptographic security of G.
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 INDCPA game. One consequence of this is that if the space of possible values of x is small, then an attacker could simply try them all and the commitment would not be hiding.
A better example of a perfectly binding commitment scheme is one where the commitment is the encryption of x under a semantically secure, publickey encryption scheme with perfect completeness, and the decommitment is the string of random bits used to encrypt x. An example of an informationtheoretically hiding commitment scheme is the Pedersen commitment scheme, which is binding under the discrete logarithm assumption. Additionally to the scheme above, it uses another generator h of the prime group and a random number r. The commitment is set c=g^x h^r.^{[12]}
Quantum bit commitment
It is an interesting question in quantum cryptography if unconditionally secure bit commitment protocols exist 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, this is impossible, as Dominic Mayers showed in 1996 (see ^{[13]} for the original proof). 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 binding 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.^{[14]}
See also
References

^ Oded Goldreich (2001). Foundations of Cryptography: Volume 1, Basic Tools, (draft available from author's site). Cambridge University Press. ISBN 0521791723. (see also http://www.wisdom.weizmann.ac.il/~oded/focbook.html ^{:224}

^ Gilles Brassard, David Chaum, and Claude Crepeau, Minimum Disclosure Proofs of Knowledge, Journal of Computer and System Sciences, vol. 37, pp. 156–189, 1988.

^ ^{a} ^{b} Moni Naor, Bit Commitment Using Pseudorandomness, Journal of Cryptology 4: 2 pp. 151–158, 1991.

^ ^{a} ^{b} Claude Crépeau, Commitment, MCgill.ca, accessed April 11, 2008

^ ^{a} ^{b} Manuel Blum, Coin Flipping by Telephone, Proceedings of CRYPTO 1981, pp. 11–15, 1981, reprinted in SIGACT News vol. 15, pp. 23–27, 1983.

^ Shimon Even. Protocol for signing contracts. In Allen Gersho, ed., Advances in Cryptography (proceedings of CRYPTO '82), pp. 148–153, Santa Barbara, CA, USA, 1982.

^ A. Shamir, R. L. Rivest, and L. Adleman, Mental Poker. In D. Klarner, ed., The Mathematical Gardner, pp. 37–43. Wadsworth, Belmont, California, 1981.

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

^ Oded Goldreich and Hugo Krawczyk, On the Composition of ZeroKnowledge Proof Systems, SIAM Journal on Computing, 25: 1, pp. 169–192, 1996

^ Wagner, David (2006), Midterm Solution, p. 2, retrieved 26 October 2015

^ "Citations: Bit Commitment using Pseudorandom Generators  Naor (ResearchIndex)". Citeseer.ist.psu.edu. Retrieved 20140607.

^ Pedersen: Noninteractive and informationtheoretic secure verifiable secret sharing. Advances in Cryptology CRYPTO '91 Springer

^ Brassard, Crépeau, Mayers, Salvail: A brief review on the impossibility of quantum bit commitment

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

Quantum bit commitment on arxiv.org
This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.