Cryptographic Commitment Principles and Applications - Overview

By @warm3snow/warm3snow
WeChat: Cryptographic Application Techniques in Practice
Blogland Home:/informatics/
Tagged with: technology sharing templates

synopsis

Commitment Scheme (CS)is an important cryptographic primitive (cryptographic primitive), A commitment scheme is a cryptographic protocol that allows a sender to commit to a chosen value (or statement) while keeping it hidden from the receiver, who is able to verify the committed value later. Commitment schemes can usually be divided into two phases.

• Commitment Phase: The sender sends a commitment value to the receiver, which is chosen by the sender, and the receiver has no way of knowing the contents of this value.
• Opening Phase: The sender opens this promise and the receiver can verify the contents of this value.

Cryptographic commitment schemes have a wide range of applications in several domains, and the following are some of the major application scenarios:

• E-voting: In an e-voting system, a commitment program ensures that voters are able to keep their choices secret at the time of voting while at the same time being able to verify the validity of their votes after the polls have closed.
• Auctions: In an auction, a commitment program allows bidders to submit their bids at the beginning of the auction without revealing the exact bid amount. At the end of the auction, all bids can be revealed and verified to ensure that bidders are being honest in their bids.
• Secure multiparty computation: in multiparty computation, participants can use commitment schemes to commit their inputs without revealing them during the computation. This helps to protect the privacy of the participants.
• Digital Signature: Commitment schemes can be used to construct digital signature schemes that ensure the integrity and non-repudiation of messages.
• Blockchain and cryptocurrencies: In blockchain technology, commitment schemes can be used to ensure the privacy and security of transactions. For example, certain privacy coins (e.g., Zcash) use promise schemes to hide transaction amounts and sender information.
• Authentication: Commitment schemes can be used in authentication protocols to allow users to prove their identity without revealing their identifying information.
• GAME THEORY: In game theory, commitment schemes can be used to design mechanisms that enable participants to cooperate or compete without revealing their strategies.

Commitment Program Rationale

Symbol Definition

• \(C\):: Commitment value
• \(m\):: Minwen
• \(r\): Random numbers, which need to be guaranteed to be different each time they are promised
• \(H\):: Hash functions
• \(||\):: String concatenation
• \([m]\):: Minwen\(m\)Commitment value of
• \([m;r]\):: Minwen\(m\)and random numbers\(r\)Commitment value of
• \(G_p\): Modulo\(p\)The order of the\(q\)cyclic group (math.)
• \(g\): \(G_p\)generating element (math.)
• \(h\): \(G_p\)of the generating element, with\(g\)are independent generators, i.e., the subgroups generated by g and h are independent of each other
• \(G\): a point on the elliptic curve, i.e.\((G_x, G_y)\), usually\(G\)is the generating element of an elliptic curve
• \(H\): a point on the elliptic curve, i.e.\((H_x, H_y)\), usually\(H\)random selection
• state in writing (laws, rules etc)\(m\)the value of Pedersen's commitment:\([m;r] = g^m \cdot h^r\)

Program definition

A commitment program is a ternary, containing\((Commit, Open, Verify)\), among others:

• \(Commit\): the sender's commitment algorithm, usually the sender chooses a plaintext\(m\)and a random number\(r\)Calculation of the value of commitments\(C\)。
• \(Open\): the sender's opening algorithm, usually the sender reveals the plaintext\(m\)and random numbers\(r\)。
• \(Verify\): Receiver's verification algorithm, usually the receiver verifies the correctness of the promise.

The commitment value has two attributes:

• Hiding: The receiver cannot know the plaintext corresponding to the sender's commitment value.
• Binding: The sender cannot change the plaintext after the commitment value has been opened.

Note: The above two descriptions are not rigorous

Commitment schemes generally involve two parties, the sender and the receiver. The sender chooses a plaintext\(m\)and a random number\(r\)Calculation of the value of commitments\(C\)and send\(C\)to the receiver. At some point, the sender opens the commitment to reveal the\(m\)cap (a poem)\(r\). The receiver uses\(C\)and the revealed\(m\)respond in singing\(r\)Verify the correctness of the commitment.

Common Commitment Programs and Principles

Common commitment programs areHash Commitment、ElGamal Commitment、Pedersen Commitmentrespond in singingSigma Commitmentetc. Although commitment schemes are realized in different ways, their fundamentals are similar.

The key processes are as follows:

[01] Sending commitments: Sender picks random numbers\(r\), and calculate\(m\)Commitment value of\(C\)that is sent to the Receiver.(Here the random number\(r\)is to ensure that the value is different for each commitment)
[02] Open commitment: Sender opens commitment, reveals\(m\)cap (a poem)\(r\)。
[03] Validating commitments: Receiver recalculates commitment values\(C^{'}\)and validate\(C^{'}\)respond in singing\(C\)Whether or not they are equal. If they are equal, the commitment validation is considered to have passed, otherwise the commitment validation fails.

Hash Commitment

Hash Commitmentis a simple commitment scheme that implements commitments through hash functions. Assuming that\(H\)is a hash function that\(m\)It is the plain text.

The hash commitment is constructed as follows:

• Commitment phase: the sender chooses a plaintext\(m\)Calculation of the value of commitments\(C = H(m)\)and send\(C\)To the recipient.
• introductory phase: Sender Reveals Plaintext\(m\)。
• validation phase: Recipient recalculation of commitment value\(C^{'} = H(m)\)and validate\(C^{'}\)cap (a poem)\(C\)Are they equal.

The hidden and bound nature of hash promises is based on the nature of the hash function, which is a one-way function, and the receiver can't get the value of the promise from the\(C\)Derive the plaintext\(m\). Also, the hash function is collision-resistant; the sender cannot find two different\(m\)makes\(C = H(m)\)。

Hash promises are poorly hidden and may collide when the plaintext space is limited; hash promises for identical plaintexts\(m\)Commitment value\(C\)is fixed, although the introduction of random numbers\(r\)could solve this problem, but would break the binding, since the sender could guarantee that the\(m||r\)Change as much as you want without changing\(m\)cap (a poem)\(r\)The value of the

ElGamal Commitment

ElGamal Commitmentis a commitment scheme constructed based on the difficulty assumption for the discrete logarithm problem. The assumption\(G_p\)be of order (math.)\(q\)of the cyclic group.\(g, h\)is a generator, the\(m\)expressly stated

The ElGamal commitment is constructed as follows:

• Commitment phase: the sender chooses a plaintext\(m\)and a random number\(r\)Calculation of the value of commitments\(C = (g^r, m \cdot h^r)\)and send\(C\)To the recipient.
• introductory phase: Sender Reveals Plaintext\(m\)and random numbers\(r\)。
• validation phase: Recipient recalculation of commitment value\(C^{'} = (g^r, m \cdot h^r)\)and validate\(C^{'}\)cap (a poem)\(C\)Are they equal.

The hidden and bound nature of the ElGamal commitment is based on the difficult assumption of the discrete logarithm problem, where the receiver is unable to extract the commitment value from the\(C\)Derive the plaintext\(m\), the sender is unable to find two different\((r_1, m_1)\)cap (a poem)\((r_2, m_2)\)makes\(C = (g^{r_1}, m_1 \cdot h^{r_1}) = (g^{r_2}, m_2 \cdot h^{r_2})\)。

Suppose the sender finds two different\((r_1, m_1)\)cap (a poem)\((r_2, m_2)\)makes\(C = (g^{r_1}, m_1 \cdot h^{r_1}) = (g^{r_2}, m_2 \cdot h^{r_2})\)Then there is:

contradicts the hypothesis, and thus ElGamal promises to be binding.

Pedersen Commitment

Pedersen Commitmentis a commitment scheme constructed based on the difficulty assumption for the discrete logarithm problem. The assumption\(G_p\)be of order (math.)\(q\)of the multiplicative group of\(g, h\)is an independently generated meta.\(m\)It is the plain text.
The Pedersen commitment is constructed as follows:

• Commitment phase: the sender chooses a plaintext\(m\)and a random number\(r\), calculate the commitment value ¥C = g^m \cdot h^r\( and sent\)C$ to the receiver.
• introductory phase: Sender Reveals Plaintext\(m\)and random numbers\(r\)。
• validation phase: Recipient recalculation of commitment value\(C^{'} = g^m \cdot h^r\)and validate\(C^{'}\)cap (a poem)\(C\)Are they equal.

The hiddenness and boundedness of Pedersen's commitment is based on the difficult assumption of the discrete logarithm problem, where the receiver can't get the commitment values from the\(C\)Derive the plaintext\(m\), the sender is unable to find two different\((r_1, m_1)\)cap (a poem)\((r_2, m_2)\)makes\(C = g^{m_1} \cdot h^{r_1} = g^{m_2} \cdot h^{r_2}\)。

Suppose the sender finds two different\((r_1, m_1)\)cap (a poem)\((r_2, m_2)\)makes\(C = g^{m_1} \cdot h^{r_1} = g^{m_2} \cdot h^{r_2}\)Then there is:

due to\(g\)respond in singing\(h\)are independently generated elements, i.e., they generate subgroups that do not overlap, which implies that\(g^{m_1 - m_2} = h^{r_2 - r_1}\)Only in\(_1 - m_2 = 0\)respond in singing\(r_2 - r_1 = 0\)It was established at the time, i.e:

contradicts the hypothesis, so Pedersen promises boundedness.

The Pedersen commitment can also be constructed based on the ECC, assuming that\(G\)respond in singing\(H\)is a point on an elliptic curve.\(m\)It's explicit.\(r\)It's a random number.

• Commitment phase: the sender chooses a plaintext\(m\)and a random number\(r\)Calculation of the value of commitments\(C = mG + rH\)and send\(C\)To the recipient.
• introductory phase: Sender Reveals Plaintext\(m\)and random numbers\(r\)。
• validation phase: Recipient recalculation of commitment value\(C^{'} = mG + rH\)and validate\(C^{'}\)cap (a poem)\(C\)Are they equal.
  Concealment and binding slightly, similar to the above.

Pedersen commitments have an important property: homomorphism. That is, the sum of two Pedersen commitments is equal to the explicit sum of the Pedersen commitments. Suppose that\(C_1 = g^{m_1} \cdot h^{r_1}\)cap (a poem)\(C_2 = g^{m_2} \cdot h^{r_2}\)are two Pedersen commitments.\(m_1, m_2\)It's explicit.\(r_1, r_2\)are random numbers. Then there are:

Pedersen commitments constructed using ECC have the same properties. below:

The homomorphism of Pedersen commitments can be used to guarantee the additivity of ciphertexts, i.e., ciphertexts where the sum of two ciphertexts is equal to the sum of the plaintexts. As in Monroe Coin, a miner node can check whether the input sum of a transaction UTXO is equal to the output sum (whether Monroe Coin is generated out of thin air) by verifying the Pedersen commitment.

Zero Knowledge Proof Commitment

In the commitment scheme described in the previous chapter, the communication between the sender and the receiver is in plaintext, i.e., the receiver has access to the sender's plaintext information. In some cases, the sender wishes to prove to the receiver that it possesses a certain plaintext without revealing the exact contents of the plaintext. This can be accomplished by using theZero Knowledge Proof CommitmentPrograms.

Zero Knowledge Proof Commitmentis a special type of commitment scheme that allows a sender to prove to a receiver that it possesses a certain plaintext without revealing the specific content of the plaintext. Zero-knowledge proof commitment schemes can be categorized according to whether they interact in the proof phase or not:

• Interactive Zero-Knowledge Proof Commitment: interaction is required between the sender and the receiver, where the sender sends the proof to the receiver and the receiver verifies the proof.
• Non-interactive zero-knowledge proof promises: the sender can generate the proof without interacting with the receiver, and the receiver can verify the proof.

Sigma Commitment

Sigma Commitmentis a zero-knowledge commitment scheme constructed based on the difficulty assumption of the discrete logarithm problem.The interactive proof procedure for Sigma commitment is as follows:

• [01] Sending a promise: Sender picks a random number\(r\)and generate commitments\(C = \)Send\(C\)To Receiver.
• [02] Send challenge: Receiver sends a random challenge\(e\)To Sender.
• [03] Send Challenge: Sender Computational Proofs\(z = m + er\)and send it to Receiver.(Note the proof here is z for hiding r and m)
• [04] Commitment Verification: Receiver Verification Proof, i.e., Verification\( == C + \)。

Proof of correctness of Sigma commitments

The left side of the equation is equal to the right side of the equation, so following the Sigma Commitment Protocol flow, the verifier Receiver can correctly verify that the

Proof of Sigma commitment to concealment

Non-strict proofs, since Receiver only knows that the\(C\), under the difficulty assumption of the discrete logarithm problem, Receiver is unable to compute the\(r\)value that guarantees the hidden nature of the promise.

Sigma Commitment Binding Proof

Suppose Receiver can find two different\((r_1)\)cap (a poem)\((r_2)\)makes\(C = r_1.G = r_2.G\)Then there is:

contradicts the assumptions and therefore Sigma commitments are binding.

Sigma Commitment to Zero Intellectual Proof

Non-strict proofs, since Receiver only knows that the\((Q, C, e, z)\), and based on that known information, it is not possible to calculate the\(m\)values that guarantee the zero-knowledge nature of the commitment

Sigma Non-Interactive Zero Knowledge Proof Commitment

Sigma commitments can also be constructed as non-interactive zero-knowledge proof commitments using the Fiat-Shamir heuristic. The specific process is as follows:

• [01] Calculating commitments: Sender picks random numbers\(r\)and generate commitments\(C = \);
• [02] Computational challenges: Sender computational challenges\(e = H(Q, C)\)and calculate the proof\(z = r + \);
• [03] Send (e, z): Sender sends challenge\(e\)and certification\(z\)To Receiver.
• [04] Validation: Receiver calculation\(A = - \)and validate\(e == H(Q, A)\)。

The correctness, hiding, binding and zero-knowledge proofs of the non-interactive zero-knowledge proof commitment of the Sigma commitment are similar to those of the interactive zero-knowledge proof commitment. Note that:

• The security of a non-interactive zero-knowledge proof commitment is related to the choice of a hash function, which needs to be chosen as a secure hash function.
• Compared to interactive zero-knowledge proof commitments, non-interactive zero-knowledge proof commitments perform better because no interaction is required between the sender and the receiver.
• Compared to the interactive zero-knowledge proof commitment, the non-interactive zero-knowledge proof commitment sends a smaller amount of data, with the amount of data only challenging the\(e\)and certification\(z\)No need to send commitment values\(C\)。

Pedersen Zero Knowledge Commitment

Pedersen CommitmentIt can also be constructed as a zero-knowledge commitment scheme. Below we directly present the non-interactive version of Pedersen's zero-knowledge commitment scheme.

• [01] Sending commitments: Sender picks random numbers\(r\)and generate commitments\(C = + \)Send\(C\)To Receiver. (Commitment phase unchanged)
• [02] Generation challenge: Sender generates two random numbers\(x\)cap (a poem)\(y\);
• [03] Proof of generation: Sender calculation\(P = + \)and calculate\(h = H(P)\)Then calculate\(x^{'} = x + \)respond in singing\(y^{'} = y + \);
• [04] Proof of sending: proof of sending by Sender\((P, x^{'}, y^{'})\)To Receiver.
• [05] Validation: Receiver validation proofs, calculations\(h = H(P)\)and validate\(P + == x^{'}G + y^{'}H\)。

The hidden, bounded nature of Pedersen's zero-knowledge commitment is similar to Pedersen's commitment. Note that:

• The security of Pedersen's zero-knowledge commitment is related to the choice of a hash function, which needs to be chosen as a secure hash function.

Correctness Proof of Pedersen's Zero Knowledge Commitment

The left side of the equation is equal to the right side of the equation, so the verifier Receiver can be correctly verified according to the Pedersen Zero Knowledge Commitment Protocol process.

Pedersen's Zero Knowledge Commitment Proof of Zero Knowledgeability

Non-strict proofs, since Receiver only knows that the\((C, P, x^{'}, y^{'})\), and based on that known information, it is not possible to compute the\(m\)respond in singing\(r\)values that guarantee the zero-knowledge nature of the commitment.

Comparison of commitment programs

The following table compares the nature of hash commitments, ElGamal commitments, Pedersen commitments and Sigma commitments:

Commitment Program	invisibility	binding	homomorphism	zero knowledge of sth.	Performance
Hash Commitment	differ from	differ from	clogged	clogged	your (honorific)
ElGamal Commitment	(of an unmarried couple) be close	(of an unmarried couple) be close	be	clogged	high
Pedersen Commitment	(of an unmarried couple) be close	(of an unmarried couple) be close	be	clogged	high
Sigma Commitment - Interactive	(of an unmarried couple) be close	(of an unmarried couple) be close	be	be	general
Sigma Commitment - Non-Interactive	(of an unmarried couple) be close	(of an unmarried couple) be close	be	be	high
Pedersen Zero Knowledge Commitment - Non-Interactive	(of an unmarried couple) be close	(of an unmarried couple) be close	be	be	high

The comparison reveals that Pedersen commitment and Sigma commitment are better commitment schemes with hiding, binding and homomorphism.Sigma commitment is a zero-knowledge commitment scheme that guarantees that the sender proves to the receiver that it owns a certain plaintext without revealing the specific content of the plaintext.Pedersen commitment has homomorphism and can be used to guarantee the additivity of the ciphertext The Pedersen promise is homomorphic and can be used to guarantee the additivity of a ciphertext. Therefore, Pedersen commitment and Sigma commitment have wide applications in practice.

summarize

This paper describes the fundamentals of commitment schemes and common commitment schemes, including hash commitments, ElGamal commitments, Pedersen commitments, and Sigma commitments. Commitment schemes are an important cryptographic primitive that can be used to guarantee that the sender's commitment value corresponds to the plaintext while hiding the specific content of the plaintext. Commitment schemes have a wide range of applications in several domains, including e-voting, auctions, secure multiparty computation, digital signatures, blockchain and cryptocurrencies, authentication, and game theory. A comparison reveals that Pedersen and Sigma commitments are superior commitment schemes with hiding, binding, and homomorphism.Pedersen commitments are homomorphic and can be used to guarantee the additivity of ciphertexts.Sigma commitments are zero-knowledge commitment schemes that guarantee that the sender proves to the receiver that he or she owns a certain plaintext without revealing the specific content of the plaintext . Therefore, Pedersen and Sigma commitments are widely used in practical applications.

It is hoped that through the introduction of this paper, readers will have a more in-depth understanding of the commitment program, which will provide reference for practical applications.

bibliography

• 【1】Pedersen Commitment
• 【2】Zero-Knowledge Proofs: An illustrated primer
• 【3】Sigma Protocol
• 【4】Zero Knowledge Proofs: Example with Pedersen Commitments in Monero