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.
The reveal phase is the sender giving the key to the receiver, who uses it to open the box and verify its contents.
In simple protocols, the commit phase consists of a single message from the sender to the receiver.
It is essential that the specific value chosen cannot be extracted from the message by the receiver at that time (this is called the hiding property).
A real-life application of this problem exists, when people (often in media) commit to a decision or give an answer in a "sealed envelope", which is then opened later.
"Let's find out if that's what the candidate answered", for example on a game show, can serve as a model of this system.
In this way, the prior public commitment to the secret values becomes a critical part of the functioning of the system.
Another important application of commitments is in verifiable secret sharing, a critical building block of secure multiparty computation.
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.
The first such flavour is whether the commitment scheme provides perfect or computational security with respect to the hiding or binding properties.
Using this notation and some knowledge about mathematical functions and probability theory we formalise different versions of the binding and hiding properties of commitments.
opening values for security parameter k. A commitment scheme is respectively perfect, statistical, or computational hiding, if for all
In the UC framework, that essentially means that C is now controlled by the environment, which attempts to distinguish protocol execution from the ideal process.
The protocol is only secure if this scenario is indistinguishable from the ideal case, where the functionality interacts with a simulator S. Here, S has control of C. In particular, whenever R outputs "receipt", F has to do likewise.
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).
Then to commit to a bit b Alice picks a random input x and sends the triple to Bob, where
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.
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. Alice chooses a ring of prime order p, with multiplicative 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.
This scheme isn't perfectly concealing as someone could find the commitment if he manages to solve the discrete logarithm problem.
[19] Additionally to the scheme above, it uses another generator h of the prime group and a random number r. The commitment is set
However, it was shown that basing statistically binding commitment schemes on general unstructured assumption is possible, via the notion of interactive hashing for commitments from general complexity assumptions (specifically and originally, based on any one way permutation) as in.
The security of the above commitment relies on the hardness of the RSA problem and has perfect hiding and computational binding.
Similarly, the RSA-based commitment mentioned above has a homomorphic property with respect to the multiplication operation.
A KZG commitment requires a predetermined set of parameters to create a pairing, and a trusted trapdoor element.
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.
[28] More generally, Mayers' proof applies only to protocols that exploit quantum physics but not special relativity.
Kent has shown that there exist unconditionally secure protocols for bit commitment that exploit the principle of special relativity stating that information cannot travel faster than light.
Electronic, optical and other types of PUFs[30] have been discussed extensively in the literature, in connection with their potential cryptographic applications including commitment schemes.