An Introduction to Commitment Schemes
Getting the hang of an essential ingredient of most cryptographic protocols.
At the heart of most cryptographic protocols, lies the notion of a commitment. Loosely speaking, a commitment scheme is a cryptographic primitive that allows a party to "commit" to a chosen value (or statement), without revealing it to others. The party can subsequently choose to reveal the committed value. The protocol is designed to ensure that a party cannot change the value or statement after they have committed to it.
Commitment schemes are the digital analogs of opaque sealed envelopes. By placing a note with a value written on it in one such envelope, one can "commit" to a value without revealing the contents of the note.
Although commitment schemes are a key component of many cryptographic protocols, we'll mostly be focused on their application in zero-knowledge proofs. The use of different types of commitment schemes leads to different proofs, like
This article aims to provide an introduction to commitment schemes in general, instead of focusing on any one type. The subsequent articles in this series will each focus on the inner workings of various types of commitment schemes.
A commitment scheme is essentially an efficient protocol between two parties (the prover and the verifier), wherein the prover can bind itself to a value. The protocol is structured so that the following two conflicting requirements are met over the span of its 2 phases, the commit phase, and the reveal phase:
Unambiguity (or binding): Once the prover makes a commitment to some message m, it should be unable to "open" the commitment to any other value than m. This requirement must be met even if the Prover tries to cheat.
Secrecy (or hiding): The commitment itself should not reveal any information about m to the receiver. This requirement must be satisfied even if the Verifier attempts to cheat.
The Different Flavors
The two properties of commitment schemes mentioned above have both statistical/perfect and computational variations — much like the majority of other cryptographic properties. Binding can hold statistically, which means that even provers with unbounded computational power are unable to open a commitment to two different messages, except with a negligibly small probability. Alternatively, it may only be true computationally: provers with limited computational resources are unable to open a commitment to two different messages.
In a similar vein, hiding can be statistical: even computationally unbounded verifiers cannot deduce anything about m from the commitment to m. Or it could be computational: computationally constrained verifiers cannot extract information about m from the commitment.
One thing to keep in mind regarding the definitions of the computational flavors of hiding and binding is that they are based on the adversary's asymptotic behavior when we raise the value of its security parameter. While this is convenient when we’re concerned with mathematical proofs, it leads to implicit classifications.
By “computationally bounded” adversaries we’re simply referring to adversaries confined to problems solvable in probabilistic polynomial time. The distinction of probabilistic polynomial time problems as “easy” and everything else as “hard”, doesn’t always hold in real life. Even an asymptotically hard problem (like breaking a commitment scheme) might be simple in practice for the desired input sizes in a given application.
Relying on Computational Variants
An unconditional guarantee is undeniably superior to a computational one. The why aren't we talking about commitment schemes that are both perfectly hiding and binding? Well, the hiding and binding requirements are, to an extent, contradictory.
If a scheme is hiding, then the commitment shouldn't contain any "information" about the committed value. But in such a circumstance, revealing any value during the reveal phase would be impossible. It is impossible to meet both requirements in the face of parties with unbounded computational power. To solve this paradox, computational assumptions are introduced.
In a two-party protocol, perfect binding and hiding aren't achievable because each play sees everything the other player sends. But is this always the case? No. In a protocol with two or more parties, communication is noisy. The Verifier V is no longer able to see exactly what Prover P sends, and vice versa. In such scenarios, we can attain perfect hiding and binding simultaneously.
Why Cook Up A Commitment Scheme
If a commitment scheme is just publishing a commitment c to a piece of data d, in a way that the following is true:
From c, one cannot recompute d.
Everybody knowing c and d must be able to ascertain that they match.
It must not be possible, to find a d' distinct from d but which still matches c.
Doesn't this seemingly resemble cryptographic hash functions, albeit with a few slight differences?
Let's consider a case where we calculate the commitment c as h(d), given a hash function h. The commitment requirements are met, but there's a catch. The commitment is vulnerable to an exhaustive search on data d. One might hash all possible data items d to find the one that corresponds to commitment c. This issue is also faced when storing password hashes. The answer? Randomization. Use an arbitrary padding r, and calculate c as h(r || d). During the reveal phase, when the commitment is opened, you publish both r and d. Exhaustive search if prevented by the randomness of r.
What changes if a digital signature system is used instead of a hash function? Not a lot . Instead of hashing, one could sign, but since anyone can verify the signature, the problem of exhaustive searches persists. Since hashing is the first step in digital signature algorithms, what you're actually employing is a hash function. Surrounding it with a DSA is obfuscation.
Some commitment switches go beyond merely enabling one to commit to any value. They also make it possible to demonstrate without opening the commitment, that the value committed to satisfies certain algebraic criteria. This type of commitment necessitates more than simply a hash: it may reuse some elements that are also used in some asymmetric encryption and signature techniques, but not those algorithms alone.
What next?
This post was aimed as an introduction to commitment schemes in general, and no single commitment scheme in particular. The upcoming posts will be focused on a commitment scheme each. Subscribe to stay tuned!
As always, thanks for reading. It means the world. :)
You can find me on twitter here, my DMs are always open.