Commitment scheme
Encyclopedia
In cryptography
, a commitment scheme allows one to commit to a value while keeping it hidden, with the ability to reveal the committed value later. Commitments are used to bind a party to a value so that they cannot adapt to other message
s in order to gain some kind of inappropriate advantage. They are important to a variety of cryptographic protocol
s including secure coin flipping, zero-knowledge proof
s, and secure computation.
Interactions in a commitment scheme take place in two phases:
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
.
want to resolve some dilemma
via coin flipping
. If they are physically in the same place
, a typical procedure might be:
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:
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.
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.
s.
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. 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.
, 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.
or whether they are non-interactive, 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.
, i.e., it can represented as a k bit string, and let 
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
and 
of increasing length k, the probability that 
and 
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
secure, if for all algorithms that run in time t and output 
the probability that 
and 
is at most 
.
be the uniform distribution over the 
opening values for security parameter k.
A commitment scheme is perfect, statistical, computational hiding, if for all
the probability ensembles 
and 
are equal
, statistically close, or computationally indistinguishable.
that is injective. 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
(while retaining the injective property). Let f be an injective 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. 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 hard-core predicate, recovering h(x) from f(x) with probability greater than one-half is as hard as inverting f. Perfect binding follows from the fact that f is injective and thus f(x) has exactly one preimage.
In 1991 Moni Naor 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
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. For Alice to cheat, she would need to find a Y, such that
. 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 while R and the commitment are both picked out of 23n values in the set of possible 3n-bit values. She does not pick R, so there is a strong 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 pseudo-random generator G from true-random, which contradicts the cryptographic security of G.
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 = gx 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 gx' = 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. 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, public-key encryption scheme, and the decommitment is the string of random bits used to encrypt x. An example of an information-theoretically hiding commitment scheme is the Pedersen commitment scheme, which is binding under the discrete logarithm assumption. Additionally to the scheme above, it use another generator h of the prime group and a random number r. The commitment is set
.
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 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 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.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, a commitment scheme allows one to commit to a value while keeping it hidden, with the ability to reveal the committed value later. Commitments are used to bind a party to a value so that they cannot adapt to other message
Message
A message in its most general meaning is an object of communication. It is a vessel which provides information. Yet, it can also be this information. Therefore, its meaning is dependent upon the context in which it is used; the term may apply to both the information and its form...
s in order to gain some kind of inappropriate advantage. They are important to a variety of cryptographic protocol
Cryptographic protocol
A security protocol is an abstract or concrete protocol that performs a security-related function and applies cryptographic methods.A protocol describes how the algorithms should be used...
s including secure coin flipping, zero-knowledge proof
Zero-knowledge proof
In cryptography, a zero-knowledge proof or zero-knowledge protocol is an interactive method for one party to prove to another that a statement is true, without revealing anything other than the veracity of the statement....
s, and secure computation.
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
Gilles Brassard
Gilles Brassard was born in Montreal, Canada, in 1955. He received a Masters degree from the Université de Montréal in 1975, and obtained his Ph.D. in Computer Science from Cornell University in 1979, working in the field of cryptography with John Hopcroft as his advisor...
, David Chaum
David Chaum
David Chaum is the inventor of many cryptographic protocols, including blind signature schemes, commitment schemes, and digital cash. In 1982, Chaum founded the International Association for Cryptologic Research , which currently organizes academic conferences in cryptography research...
, and Claude Crepeau
Claude Crépeau
Dr. Claude Crépeau is a professor in the School of Computer Science at McGill University. Ηe was born in Montreal, Quebec, Canada, in 1962. He received a Masters degree from the Université de Montréal in 1986, and obtained his Ph.D. in Computer Science from MIT in 1990, working in the field of...
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
Manuel Blum
Manuel Blum is a computer scientist who received the Turing Award in 1995 "In recognition of his contributions to the foundations of computational complexity theory and its application to cryptography and program checking".-Biography:Blum attended MIT, where he received his bachelor's degree and...
, Shimon Even
Shimon Even
Shimon Even was an Israeli computer science researcher. His main topics of interest included algorithms, graph theory and cryptography. He was a member of the Computer Science Department at the Technion since 1974...
, 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
Bit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
.
Coin flipping
Suppose Alice and BobAlice and Bob
The names Alice and Bob are commonly used placeholder names for archetypal characters in fields such as cryptography and physics. The names are used for convenience; for example, "Alice sends a message to Bob encrypted with his public key" is easier to follow than "Party A sends a message to Party...
want to resolve some dilemma
Dilemma
A dilemma |proposition]]") is a problem offering two possibilities, neither of which is practically acceptable. One in this position has been traditionally described as "being on the horns of a dilemma", neither horn being comfortable...
via coin flipping
Coin flipping
Coin flipping or coin tossing or heads or tails is the practice of throwing a coin in the air to choose between two alternatives, sometimes to resolve a dispute between two parties...
. If they are physically in the same place
Principle of locality
In physics, the principle of locality states that an object is influenced directly only by its immediate surroundings. Experiments have shown that quantum mechanically entangled particles must violate either the principle of locality or the form of philosophical realism known as counterfactual...
, 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 they are not in the same place
Nonlocality
In Classical physics, nonlocality is the direct influence of one object on another, distant object. In Quantum mechanics, nonlocality refers to the absence of a local, realist model in agreement with quantum mechanical predictions.Nonlocality may refer to:...
, this procedure is faulty. Alice would have to trust
Web of trust
In cryptography, a web of trust is a concept used in PGP, GnuPG, and other OpenPGP-compatible systems to establish the authenticity of the binding between a public key and its owner. Its decentralized trust model is an alternative to the centralized trust model of a public key infrastructure ,...
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:
- Alice "calls" the coin flip and tells Bob only a commitment to her call,
- Bob flips the coin and reports the result,
- Alice reveals what she committed to
- 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.
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
One particular motivating example is the use of commitment schemes in zero-knowledge proofZero-knowledge proof
In cryptography, a zero-knowledge proof or zero-knowledge protocol is an interactive method for one party to prove to another that a statement is true, without revealing anything other than the veracity of the statement....
s.
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. 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.
Verifiable secret sharing
Another important application of commitments is in verifiable secret sharingVerifiable secret sharing
In cryptography, a secret sharing scheme is verifiable if auxiliary information is included that allows players to verify their shares as consistent. More formally, verifiable secret sharing ensures that even if the dealer is malicious there is a well-defined secret that the players can later...
, a critical building block of secure multiparty computation
Secure multiparty computation
Secure multi-party computation is a sub field of cryptography. The goal of methods for secure multi-party computation is to enable parties to jointly compute a function over their inputs, while at the same time keeping these inputs private...
. In a secret sharing
Secret sharing
Secret sharing refers to method for distributing a secret amongst a group of participants, each of whom is allocated a share of the secret. The secret can be reconstructed only when a sufficient number of shares are combined together; individual shares are of no use on their own.More formally, in a...
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
Cabal
A cabal is a group of people united in some close design together, usually to promote their private views and/or interests in a church, state, or other community, often by intrigue...
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 protocolCryptographic protocol
A security protocol is an abstract or concrete protocol that performs a security-related function and applies cryptographic methods.A protocol describes how the algorithms should be used...
or whether they are non-interactive, 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
Probability theory
Probability theory is the branch of mathematics concerned with analysis of random phenomena. The central objects of probability theory are random variables, stochastic processes, and events: mathematical abstractions of non-deterministic events or measured quantities that may either be single...
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.
Computational binding
Let open be chosen from a set of size, i.e., it can represented as a k bit string, and let 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
and of increasing length k, the probability that and is a negligible function in k.This is a form of Asymptotic analysis
Asymptotic analysis
In mathematical analysis, asymptotic analysis is a method of describing limiting behavior. The methodology has applications across science. Examples are...
. It is also possible to state the same requirement using Concrete security
Concrete security
In cryptography, concrete security or exact security is a practice-oriented approach that aims to give more precise estimates of the computational complexities of adversarial tasks than polynomial equivalence would allow....
: A commitment scheme Commit is
secure, if for all algorithms that run in time t and output the probability that and is at most .Perfect, statistical and computational hiding
Let be the uniform distribution over the opening values for security parameter k.A commitment scheme is perfect, statistical, computational hiding, if for all
the probability ensembles and are equalEqual
Equal commonly refers to a state of equality.Equal or equals may also refer to:* Equal , a brand of artificial sweetener* EQUAL Community Initiative, an initiative within the European Social Fund of the European Union...
, 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.Bit-commitment from any one-way permutation (or injective one way function)
One can create a bit-commitment scheme from any one-way functionOne-way function
In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems...
that is injective. 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
Hard-core predicate
In cryptography, a hard-core predicate of a one-way function f is a predicate b which is easy to compute given x but is hard to compute given f...
(while retaining the injective property). Let f be an injective 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. 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 hard-core predicate, recovering h(x) from f(x) with probability greater than one-half is as hard as inverting f. Perfect binding follows from the fact that f is injective and thus f(x) has exactly one preimage.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 showed how to create a bit-commitment scheme from a cryptographically secure pseudorandom number generator
Cryptographically secure pseudorandom number generator
A cryptographically secure pseudo-random number generator is a pseudo-random number generator with properties that make it suitable for use in cryptography.Many aspects of cryptography require random numbers, for example:...
. 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-orExclusive disjunctionThe logical operation exclusive disjunction, also called exclusive or , is a type of logical disjunction on two operands that results in a value of true if exactly one of the operands has a value of true...
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. For Alice to cheat, she would need to find a Y, such that
. 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 while R and the commitment are both picked out of 23n values in the set of possible 3n-bit values. She does not pick R, so there is a strong 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 pseudo-random generator G from true-random, which contradicts the cryptographic security of G.
A perfectly binding scheme based on the discrete log problem
Alice chooses a groupGroup (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
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 = gx 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 gx' = 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. 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, public-key encryption scheme, and the decommitment is the string of random bits used to encrypt x. An example of an information-theoretically hiding commitment scheme is the Pedersen commitment scheme, which is binding under the discrete logarithm assumption. Additionally to the scheme above, it use another generator h of the prime group and a random number r. The commitment is set
.Quantum bit commitment
It is an interesting question in quantum cryptographyQuantum cryptography
Quantum key distribution uses quantum mechanics to guarantee secure communication. It enables two parties to produce a shared random secret key known only to them, which can then be used to encrypt and decrypt messages...
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 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
Schmidt decomposition
In linear algebra, the Schmidt decomposition refers to a particular way of expressing a vector in the tensor product of two inner product spaces. It has applications in quantum information theory and plasticity....
, 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.