Commmitment Schemes in Zecrey

As we mentioned earlier, one of the main contributions of Zecrey Protocol is the support to many-to-many private transactions for blockchain users. The driven technology behind this charming creation are mainly twisted ElGamal encryption, zero knowledge proof, and a novel integrated commitment scheme. In the last article, we have already presented an outline of the twisted ElGamal encryption schemes, including its definition, origin, and procedures. The main contribution of this article aims to lead readers into the world of commitment schemes and capture the concepts, principles, and applications to this unique cryptographic primitive.

The notion of commitment is at the heart of almost any construction of modern cryptographic protocols [1]. In this context, making a commitment simply means that a player in a protocol is able to choose a value from some finite set and commit to his choice such that he can no longer change his mind. He does not however, have to reveal his choice — although he may choose to do so at some later time. Intuitively, a non-interactive commitment scheme is a two-party protocol between a sender and a receiver with two stages. At the committing stage, the sender commits to some value m by sending a commitment to the receiver. At the opening stage, the sender can open the commitment by providing m and some auxiliary information, by which the receiver can verify that the value it received is indeed the value committed by the sender during the committing stage. As an informal example, consider the following game between two players P and V :

1. P wants to commit to a bit b. To do so, he writes down b on a piece of paper, puts it in a box, and locks it using a padlock.
2. P gives the box to V
3. P can later open the commitment by giving V the key to the padlock

There are two basic properties of this game, which are essential to any commitment scheme:

1. Having given away the box, P cannot anymore change what is inside. Hence, when the box is opened, we know that what is revealed really was the choice that P committed to originally. This is usually called the binding property.
2. When V receives the box, he cannot tell what is inside before P decides to give him the key. This is usually called the hiding property.

There are many ways of realizing this basic functionality, some are based on physical processes, e.g. noisy channels or quantum mechanics, while others are based on distributing information between many players connected by a network. Then, why should we be interested in building such commitment schemes? Primarily because this simple functionality enables the construction of secure protocols that accomplish surprisingly complicated, even seemingly impossible tasks. In the next section, for a better grasp of this kind of cryptographic primitive, we are going to put forward four typical applications of Commitment Schemes.

First, we will make a coin fliping example. 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:

1. Alice “calls” the coin flip
2. Bob flips the coin
3. 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:

1. Alice “calls” the coin flip but only tells Bob a commitment to her call,
2. Bob flips the coin and reports the result,
3. Alice reveals what she committed to,
4. Bob verifies that Alice’s call matches her commitment,
5. 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 [2]. 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.

In fact, one particular motivating example is the use of commitment schemes in zero-knowledge proofs [3]. 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, and only reveal what should be revealed later in the proof. Second, 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 to the prover [4]. Therefore, commitment schemes greatly enhance the credibility and security of zero-knowledge proofs.

The third meaningful application of commitments is signature schemes. The Lamport signature scheme [5] 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, a system to combine many Lamport Key-sets 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 lamport-key-commitments sets into a single hash value that can be associated with the prospective author of later verified data.

Another important application of commitments is in verifiable secret sharing [6], a critical building block of secure multiparty computation [7]. 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, thus providing more secret trust.

In the future, we will elaborate the novel commitment scheme — — Pedersen Commitment [8], which has been adopted and redesigned widely in the existing privacy protection protocols of various blockchain systems. In addition, the connection between commitment schemes and the well-known zero-knowledge proofs will be introduced as well, which will result in a easier grasp for common readers and privacy enthusiasts of the cryptographic essences in the Zecrey Protocol.

Zecrey official website: Zecrey

Welcome to join our communities and follow us on twitter:

Medium：https://medium.com/@zecrey

Twitter: https://twitter.com/zecreyprotocol

Telegram: https://t.me/zecrey

Discord: https://discord.com/invite/U98ghQsJE5

References

[1] Juels A, Wattenberg M. A fuzzy commitment scheme[C]//Proceedings of the 6th ACM conference on Computer and communications security. 1999: 28–36.

[2] Moni Naor, Bit Commitment Using Pseudorandomness, Journal of Cryptology 4: 2 pp. 151–158, 1991.

[3] Yang X, Li W. A zero-knowledge-proof-based digital identity management scheme in blockchain[J]. Computers & Security, 2020, 99: 102050.

[4] https://en.wikipedia.org/wiki/Commitment_scheme

[5] Abdullah G M, Mehmood Q, Khan C B A. Adoption of Lamport signature scheme to implement digital signatures in IoT[C]//2018 International Conference on Computing, Mathematics and Engineering Technologies (iCoMET). IEEE, 2018: 1–4.

[6] Stadler M. Publicly verifiable secret sharing[C]//International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 1996: 190–199.

[7] Cramer R, Damgård I B. Secure multiparty computation[M]. Cambridge University Press, 2015.

[8] https://crypto.stackexchange.com/questions/64437/what-is-a-pedersen-commitment