Cryptographic commitments
The commitment is a useful tool in cryptography that is often utilized with the zero-knowledge proof. In principle, the commitment is designed to ensure some values are selected in the correct manner. The description is subtle so let’s consider a concrete case: a ‘Rock Paper Scissor’ game.
Let Alice and Bob be the players of the ‘Rock Paper Scissor’ game. Imagine the scenario that they’re playing this game through internet, how could they play this game fairly without a trusted third party? The term fair denotes no one decides his / her choice after acquiring the other’s choice. Ideally, if they can express their choices together, it may be a fair game. As we all know, the synchronization in the network is a tough issue which is quite impractical.
Then, how to design the protocol? For data hiding, the symmetric / asymmetric encryption schemes may be an intuitive cryptographic tool; for the non-repudiation, the digital signature may be required. And these two tools may in advance need the certifications from a trusted third party like key distribution center (KDC).
In this post, we’re introducing another powerful cryptographic tool to solve this problem, the cryptographic commitment. There are two phases in the commitment protocol, the commit phase and the open phase. In the commit phase, a prover makes a commit com to hide his / her secret along with a random number r; after some confirmations, the prover opens both the secret and the random number to a verifier; finally, the verifier can verify the validity of the set {commit, secret, r}.
Shown as above there are three algorithms in the commitment framework where the open algorithm just reveals secret and r without any computation. The commitment does not rely on the symmetric / asymmetric keys so there is also no corresponding key management issues like key distribution or KDC. With the commitment, two properties will be guaranteed with cryptography:
Hiding
In the commit phase, the verifier acquires no information about secret and r from the commit com.
Binding
The prover is not able to open {secret’, r’} !={secret, r} which makes verify(com, secret’, r’) = True.
Take the aforementioned ‘Rock Paper Scissor’ game for example, we’ll realize the commitment much better. Assume secretA, secretB belong to {‘Rock’, ‘Paper’, ‘Scissor’} and they denote the choices for Alice and Bob respectively,
First, Alice and Bob exchange their commits in the commit phase as depicted in above picture. By the hiding property of the commitment, no value will be leaked in the commit phase so that both of them cannot cheat.
Then, after they confirm they’ve received the commitment from the other one, it comes to the open phase. Two players reveal their secret and r to the other so that the commit could be verified. By the binding property of the commitment, the prover is not able to change his / her mind after giving a commit; that is, it is cryptographically guaranteed the ‘opened secret’ is the same as the ‘committed secret’. The commitment thus guarantees a fair game between two parties.
Concrete constructions
So far, maybe the commitment sounds magic but it is actually not very difficult to be implemented. There are several famous implementations such as hash-based commitment, ElGamal commitment and Pederson commitment. Following, we take advantage of the properties of hash functions to construct a straightforward commitment.
com = Commit(secret, r)
r = random(512) // a 512 bits random number to guarantee the entropy
com = hash(secret, r)
return comThe one-wayness of the hash function directly guarantees the hiding property of the commitment.
T / F = Verify(com, secret, r)
return (com == hash(secret, r))The collision-resistant property of the hash function inherently leads to the binding property of the commitment.
So far, a basic knowledge of cryptographic commitment has been introduced. In the following story of zero-knowledge proof, there will be some advanced commitment schemes introduced.
