Revision History for: Bit Commitment
- 2025-06-24 at 21:22 by JuliaM
Functionality Description
Bit commitment is a fundamental cryptographic primitive between two parties that allows one party (the committer) to choose a bit (or more generally, a value), commit to it while keeping it hidden, and later reveal it to another party (the receiver) in a way that guarantees consistency. It acts like a sealed envelope: the committer locks in a value during the commit phase, and later opens the envelope in the reveal phase. This functionality is crucial for ensuring fairness and trust in many cryptographic protocols, particularly where parties do not trust each other, and it is often considered one of the most important building blocks of modern cryptography.
Interactions in a commitment scheme take place in two phases:
- The commit phase, during which a value is chosen and committed to
- The reveal phase, during which the value is revealed by the sender, then the receiver verifies its authenticity
The concept of commitment schemes was first formally articulated by Gilles Brassard, David Chaum, and Claude Crépeau in 1988 [1], in the context of constructing zero-knowledge proofs. However, the idea itself predates this formalisation and appeared informally in earlier cryptographic protocols. Early uses of commitment-like primitives can be traced back to foundational works by Manuel Blum in his coin flipping protocol [2]. These early appearances treated commitment more as a tool than as a standalone abstraction, which only later evolved into the rigorous cryptographic primitive we use today. A later formal description in the composable framework can be found in [3]
Classical Analogues
Bit commitment is a naturally classical functionality that is impossible to achieve in the information-theoretic regime, both classically and quantumly. Some famous instantiations of this functionality in the classical world, using different assumptions, include:
Blum’s Coin Flipping Protocol (1981) [2]: Though introduced for coin flipping, this protocol implicitly contains a commitment scheme using one-way functions.
Naor’s Bit Commitment (1991) [4]: Provides a computationally secure commitment scheme based on pseudorandomness and one-way permutations.
Pedersen Commitment (1993) [5]: A statistically hiding, computationally binding commitment scheme based on the discrete logarithm assumption.
Common Constructions involve the following techniques:
- Hash-based Commitments (e.g., $commit(m, r) = H(m || r)$)
- Number-theoretic (Pedersen, RSA-based)
- Lattice-based (for post-quantum security)
Real-world Use Cases
Bit commitment underlies many essential cryptographic tasks, including:
- Zero-Knowledge Proofs: Used as a building block to hide intermediate witness values.
- Secure Multi-party Computation (MPC): Enables secure sharing of values across distrustful parties.
- Coin Flipping & Lotteries: Ensures fairness by preventing cheating during the initial phase.
- Blockchain/Smart Contracts: Used to lock in commitments to data or actions in decentralized settings.
- Electronic Voting: Voters can commit to their vote privately and reveal it later to ensure verifiability.
Properties
A secure bit commitment protocol satisfies the following two main properties:
- Hiding: Ensures the committed value remains secret until the committer chooses to reveal it.
Can be perfect, statistical, or computational, depending on whether the hiding holds against unbounded or bounded adversaries. - Binding: Ensures the committer cannot change the value after committing to it. Like hiding, binding can be perfect, statistical, or computational.
Famous no-go results state that no scheme can be both perfectly hiding and perfectly binding.
Bit-commitment schemes, can also have the following additional properties:
- Non-interactive vs Interactive: Some commitment schemes are non-interactive (single message), others require interaction.
- Efficiency: Commitment size and computational cost are important in practical applications.
- Trapdoor Commitments: Some schemes allow commitment to be equivocal if a trapdoor is known (used in simulation-based proofs).
- Composability: In the Universal composability framework [3], commitment functionality (typically denoted as $\\\mathbb{B}_{commit}$) can be defined in a way that can be composed with other cryptographic primitives, without compromising the security properties. Not all the commitment schemes in the literature have the property of composability.
Further Information
Impossibility or Statistical vs Computational Trade-offs: In the information-theoretic setting, commitment is impossible without assumptions like a trusted setup or shared randomness.
Impossibility in the quantum world: In quantum cryptography as well, no perfectly secure quantum bit commitment is possible without assumptions, due to the Mayers–Lo–Chau no-go results [6,7]
References
[1] Brassard, Gilles, David Chaum, and Claude Crépeau. “Minimum disclosure proofs of knowledge.” Journal of computer and system sciences 37, no. 2 (1988): 156-189.
[2] Blum, Manuel. “Coin flipping by telephone a protocol for solving impossible problems.” ACM SIGACT News 15, no. 1 (1983): 23-27.
[3] Canetti, Ran. “Universally composable security: A new paradigm for cryptographic protocols.” In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pp. 136-145. IEEE, 2001.
[4] Naor, Moni. “Bit commitment using pseudorandomness.” Journal of cryptology 4 (1991): 151-158.
[5] Damgård, Ivan B., Torben P. Pedersen, and Birgit Pfitzmann. “On the existence of statistically hiding bit commitment schemes and fail-stop signatures.” In Annual International Cryptology Conference, pp. 250-265. Berlin, Heidelberg: Springer Berlin Heidelberg, 1993.
[6] Lo, Hoi-Kwong, and Hoi Fung Chau. “Is quantum bit commitment really possible?.” Physical Review Letters 78, no. 17 (1997): 3410.
[7] Mayers, Dominic. “Unconditionally secure quantum bit commitment is impossible.” Physical review letters 78, no. 17 (1997): 3414. - 2025-05-15 at 12:54 by JuliaM
Functionality Description
Bit commitment is a fundamental cryptographic primitive between two parties that allows one party (the committer) to choose a bit (or more generally, a value), commit to it while keeping it hidden, and later reveal it to another party (the receiver) in a way that guarantees consistency. It acts like a sealed envelope: the committer locks in a value during the commit phase, and later opens the envelope in the reveal phase. This functionality is crucial for ensuring fairness and trust in many cryptographic protocols, particularly where parties do not trust each other, and it is often considered one of the most important building blocks of modern cryptography.
Interactions in a commitment scheme take place in two phases:
- The commit phase, during which a value is chosen and committed to
- The reveal phase, during which the value is revealed by the sender, then the receiver verifies its authenticity
The concept of commitment schemes was first formally articulated by Gilles Brassard, David Chaum, and Claude Crépeau in 1988 [1], in the context of constructing zero-knowledge proofs. However, the idea itself predates this formalisation and appeared informally in earlier cryptographic protocols. Early uses of commitment-like primitives can be traced back to foundational works by Manuel Blum in his coin flipping protocol [2]. These early appearances treated commitment more as a tool than as a standalone abstraction, which only later evolved into the rigorous cryptographic primitive we use today. A later formal description in the composable framework can be found in [3]
Protocols
No protocols implement this functionality yet.
Classical Analogues
Bit commitment is a naturally classical functionality that is impossible to achieve in the information-theoretic regime, both classically and quantumly. Some famous instantiations of this functionality in the classical world, using different assumptions, include:
Blum’s Coin Flipping Protocol (1981) [2]: Though introduced for coin flipping, this protocol implicitly contains a commitment scheme using one-way functions.
Naor’s Bit Commitment (1991) [4]: Provides a computationally secure commitment scheme based on pseudorandomness and one-way permutations.
Pedersen Commitment (1993) [5]: A statistically hiding, computationally binding commitment scheme based on the discrete logarithm assumption.
Common Constructions involve the following techniques:
- Hash-based Commitments (e.g., $commit(m, r) = H(m || r)$)
- Number-theoretic (Pedersen, RSA-based)
- Lattice-based (for post-quantum security)
Real-world Use Cases
Bit commitment underlies many essential cryptographic tasks, including:
- Zero-Knowledge Proofs: Used as a building block to hide intermediate witness values.
- Secure Multi-party Computation (MPC): Enables secure sharing of values across distrustful parties.
- Coin Flipping & Lotteries: Ensures fairness by preventing cheating during the initial phase.
- Blockchain/Smart Contracts: Used to lock in commitments to data or actions in decentralized settings.
- Electronic Voting: Voters can commit to their vote privately and reveal it later to ensure verifiability.
Properties
A secure bit commitment protocol satisfies the following two main properties:
- Hiding: Ensures the committed value remains secret until the committer chooses to reveal it.
Can be perfect, statistical, or computational, depending on whether the hiding holds against unbounded or bounded adversaries. - Binding: Ensures the committer cannot change the value after committing to it. Like hiding, binding can be perfect, statistical, or computational.
Famous no-go results state that no scheme can be both perfectly hiding and perfectly binding.
Bit-commitment schemes, can also have the following additional properties:
- Non-interactive vs Interactive: Some commitment schemes are non-interactive (single message), others require interaction.
- Efficiency: Commitment size and computational cost are important in practical applications.
- Trapdoor Commitments: Some schemes allow commitment to be equivocal if a trapdoor is known (used in simulation-based proofs).
- Composability: In the Universal composability framework [3], commitment functionality (typically denoted as $\\\mathbb{B}_{commit}$) can be defined in a way that can be composed with other cryptographic primitives, without compromising the security properties. Not all the commitment schemes in the literature have the property of composability.
Further Information
Impossibility or Statistical vs Computational Trade-offs: In the information-theoretic setting, commitment is impossible without assumptions like a trusted setup or shared randomness.
Impossibility in the quantum world: In quantum cryptography as well, no perfectly secure quantum bit commitment is possible without assumptions, due to the Mayers–Lo–Chau no-go results [6,7]
References
[1] Brassard, Gilles, David Chaum, and Claude Crépeau. “Minimum disclosure proofs of knowledge.” Journal of computer and system sciences 37, no. 2 (1988): 156-189.
[2] Blum, Manuel. “Coin flipping by telephone a protocol for solving impossible problems.” ACM SIGACT News 15, no. 1 (1983): 23-27.
[3] Canetti, Ran. “Universally composable security: A new paradigm for cryptographic protocols.” In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pp. 136-145. IEEE, 2001.
[4] Naor, Moni. “Bit commitment using pseudorandomness.” Journal of cryptology 4 (1991): 151-158.
[5] Damgård, Ivan B., Torben P. Pedersen, and Birgit Pfitzmann. “On the existence of statistically hiding bit commitment schemes and fail-stop signatures.” In Annual International Cryptology Conference, pp. 250-265. Berlin, Heidelberg: Springer Berlin Heidelberg, 1993.
[6] Lo, Hoi-Kwong, and Hoi Fung Chau. “Is quantum bit commitment really possible?.” Physical Review Letters 78, no. 17 (1997): 3410.
[7] Mayers, Dominic. “Unconditionally secure quantum bit commitment is impossible.” Physical review letters 78, no. 17 (1997): 3414. - 2025-05-15 at 12:42 by Mina Doosti