5. Cryptographic Commitments with Pederson

Cryptographic Commitments

Cryptographic commitments are fundamental cryptographic primitives used to commit to a value while keeping it hidden, with the ability to reveal the committed value later. This concept is akin to putting a value in a locked box, giving the box to someone, and later providing the key to reveal the value inside. Commitments are widely used in protocols such as secure multiparty computation, zero-knowledge proofs, and blockchain technologies.

Commitment Scheme link with hand math eq

General Overview link

Properties of Cryptographic Commitments

Cryptographic commitments have two primary properties:

1. Hiding: The commitment should not reveal any information about the committed value until it is opened.
2. Binding: Once a value is committed, it cannot be changed. The committer cannot open the commitment to a different value than the one they initially committed to.

Types of Cryptographic Commitments

There are different ways to achieve cryptographic commitments, including:

• Hash-based commitments: Use cryptographic hash functions.
• Number-theoretic commitments: Use properties of number theory, such as those based on the discrete logarithm problem.
• Lattice-based commitments: Use lattice problems, relevant in post-quantum cryptography.

Example: Hash-based Commitments

Commit Phase:

1. Choose a secret value $(m)$.
2. Choose a random nonce $(r)$ (also known as a blinding factor).
3. Compute the commitment $(C = H(m \parallel r))$, where $(H)$ is a cryptographic hash function and $(\parallel)$ denotes concatenation.

Reveal Phase:

1. Reveal both $(m)$ and $(r)$.
2. Verify the commitment by checking if $(H(m \parallel r))$ equals $(C)$.

Example: Pedersen Commitment (Number-theoretic)

Pedersen commitments leverage the hardness of the discrete logarithm problem.

Setup:

1. Choose a large prime $(p)$ and a generator $(g)$ of a cyclic group $(G)$ of order $(q)$.
2. Choose another generator $(h)$ such that the discrete logarithm of $(h)$ with respect to $(g)$ is unknown.

Commit Phase:

1. Choose a secret value $(m)$ and a random nonce $(r)$.
2. Compute the commitment $(C = g^m \cdot h^r \mod p)$.

Reveal Phase:

1. Reveal $(m)$ and $(r)$.
2. Verify the commitment by checking if $(g^m \cdot h^r \mod p)$ equals the provided $(C)$.

Applications of Cryptographic Commitments

1. Zero-Knowledge Proofs: Commitments are used to enable a prover to convince a verifier that they know a value without revealing the value itself.
2. Secure Multiparty Computation (SMPC): Commitments allow parties to commit to their inputs while keeping them hidden until all parties are ready to proceed.
3. Blockchain and Cryptocurrencies: Commitments are used in protocols like confidential transactions, ensuring transaction amounts are hidden while preserving the integrity and correctness of the blockchain.
4. Voting Systems: Commitments ensure that votes are cast in a concealed manner and can be revealed and verified later.

Security Considerations

• Hiding property: Ensures that the commitment does not leak any information about the committed value. It relies on the properties of the hash function (for hash-based commitments) or the difficulty of the discrete logarithm problem (for Pedersen commitments).
• Binding property: Ensures that once committed, the value cannot be changed. It relies on the collision resistance of the hash function or the binding nature of the number-theoretic construction.

Conclusion

Cryptographic commitments are essential tools in modern cryptography, providing a foundation for numerous secure protocols and applications. By ensuring both the hiding and binding properties, commitments enable secure, verifiable, and private interactions in various cryptographic systems.

Details

Once $(C)$ is published, the committer cannot change $(m)$ without changing $(r)$. Given $(C)$, it is infeasible to find a pair $((m^{'},r^{'} \neq (m,r))$ such that:

$C = g^{m^{'}} \cdot h^{r^{'}}\ mod\ p$

This binding property relies on the discrete logarithm problem's hardness.

Homomorphic Property

Pedersen commitments are homomorphic, meaning commitments can be combined in a meaningful way. Specifically, given commitments to two values $(m_{1})$ and $(m_{2}):$

1. Commit to $(m_{1})$ with nonce $(r_{1}):$

$C_{1} = g^{m_{1}} \cdot h^{r_{1}}\ mod\ p$

2. Commit to $(m_{2})$ with nonce $(r_{2}):$

$C_{2} = g^{m_{2}} \cdot h^{r_{2}}\ mod\ p$

The product of these commitments is a commitment to the sum $(m_{1} + m_{2})$ with nonce $(r_{1} + r_{2}):$

$C_{1} \cdot C_{2} = \left( g^{m_{1}} \cdot h^{r_{1}} \right) \cdot \left( g^{m_{2}} \cdot h^{r_{2}} \right) = g^{m_{1} + m_{2}} \cdot h^{r_{1} + r_{2}}\ mod\ p$

This property is particularly useful in cryptographic protocols where combining commitments needs to be efficient and secure.

Security Proofs

Hiding Proof: To prove the hiding property, consider an adversary who sees the commitment $(C)$. Since $(r)$ is chosen uniformly at random from $(Z_{q})$, the distribution of $(C)$ is uniformly random over $(G)$ for different $(r)$ values. Therefore, the adversary cannot distinguish between different values of $(m)$.

Binding Proof: To prove the binding property, assume that an adversary can find two pairs $((m,r)and(m^{'},r^{'}))$ such that:

$g^{m} \cdot h^{r} \equiv g^{m^{'}} \cdot h^{r^{'}}\ mod\ p$

Then:

$g^{m - m^{'}} \equiv h^{r^{'} - r}\ mod\ p$

Since $(g)$ and $(h)$ are generators and their discrete logarithm relationship is unknown, finding such a pair implies solving the discrete logarithm problem, which is assumed to be computationally infeasible.