Commitment scheme
A commitment scheme is a cryptographic protocol through which one party fixes a value while withholding that value from another party until a later disclosure. It is conventionally compared to placing a written message inside a locked container: the contents remain concealed during the commitment period, while the container prevents their subsequent replacement. Cryptographic commitments implement these properties through mathematical relations rather than physical custody.
The party fixing the value is called the committer, and the party receiving the commitment is called the verifier or receiver. A commitment protocol has a commitment phase followed by an opening phase. During the commitment phase, the committer derives a commitment string from a message and private randomness. During the opening phase, the committer releases information that enables the verifier to recover or validate the committed message.
Commitment schemes are fundamental components of zero-knowledge proofs, secure multi-party computation, coin-flipping protocols, and several forms of electronic voting. Their security is described primarily through the hiding and binding properties, whose exact meanings depend on the computational model and the capabilities assigned to dishonest participants.
Formal structure
A non-interactive commitment scheme is represented by a pair of algorithms, usually denoted by (\mathsf{Com}) and (\mathsf{Ver}). For a message (m) and a random value (r), the commitment algorithm computes
[ c \leftarrow \mathsf{Com}(m;r). ]
The string (c) is transmitted during the commitment phase. An opening consists of (m) together with decommitment information (d), which commonly contains (r) or data derived from it. The verification algorithm evaluates
[ \mathsf{Ver}(c,m,d)\in{0,1}. ]
Correctness requires an honestly generated opening to be accepted except with negligible probability. Interactive commitment schemes distribute the same logical functions across several exchanged messages, and their commitment transcript replaces the single string (c).
The binding property limits a committer’s ability to produce one commitment that admits incompatible openings. Computational binding means that no probabilistic polynomial-time committer can efficiently find accepted openings for distinct messages. Statistical binding places the same restriction on computationally unbounded committers, apart from a negligible probability determined by the security parameter.
The hiding property limits the receiver’s ability to determine the committed message before the opening phase. Computational hiding requires commitments to different messages to be indistinguishable by efficient algorithms. Statistical hiding requires their distributions to have negligible statistical distance, even when the receiver has unlimited computational resources. Perfect hiding is the special case in which the relevant distributions are identical.
A nontrivial classical commitment scheme cannot simultaneously provide perfect hiding and perfect binding without an additional assumption or resource. If commitments to two messages have identical distributions, some commitment strings necessarily possess openings associated with both messages. Binding is then obtained by making such alternative openings computationally inaccessible, while information-theoretic binding instead requires the hiding property to depend on computational hardness.
Historical development
Commitment protocols acquired their modern cryptographic role through research on remotely conducted coin flipping. Manuel Blum’s 1981 protocol used commitments to prevent either participant from selecting a bit after learning the other participant’s choice. This application established the characteristic temporal separation between fixing information and revealing it.
During the following decade, commitments became a standard primitive in protocols for proving statements without disclosing their witnesses. A 1991 construction by Moni Naor and You Watanabe established computationally hiding bit commitments from any pseudorandom generator. Together with the equivalence between pseudorandom generators and one-way functions, the result connected commitment schemes to a minimal general assumption in complexity-based cryptography.
Subsequent work distinguished ordinary commitments from commitments secure under concurrent execution, adaptive corruption, or composition with unrelated protocols. These distinctions changed the formal treatment of commitment from a pair of isolated hiding and binding conditions into a family of security definitions indexed by the surrounding execution model.
Construction from pseudorandom generators
The pseudorandom-generator construction concerns the commitment of a single bit. Let (G) expand an (n)-bit seed into a string of length (3n). The receiver first transmits a uniformly random string (R\in{0,1}^{3n}). For a random seed (s), the committer sends
[ c = \begin{cases} G(s), & b=0,\ G(s)\oplus R, & b=1. \end{cases} ]
An opening reveals (b) and (s), after which the receiver checks the corresponding equation. The commitment is computationally hiding because (G(s)) is computationally indistinguishable from a uniform string. Translation by the fixed string (R) preserves uniformity, so efficient receivers cannot reliably distinguish commitments to the two possible bits.
Binding follows from the size of the generator’s image. A commitment can be opened both ways only when there are seeds (s_0) and (s_1) satisfying
[ G(s_0)=G(s_1)\oplus R. ]
The image of (G) contains at most (2^n) strings among (2^{3n}) possible outputs. For a uniformly selected (R), the probability that the image intersects its translation by (R) is negligible. The construction therefore provides statistical binding against the committer and computational hiding against the receiver.
The receiver’s initial message makes this scheme interactive. The protocol also illustrates that commitment security depends on how messages are generated: replacing the uniformly random receiver string with an adversarially structured value changes the binding analysis and requires a security definition that explicitly models a dishonest receiver.
Algebraic commitments
Torben Pedersen introduced a widely used commitment scheme based on the hardness of the discrete logarithm problem. Let (G) be a cyclic group of prime order (q), with generators (g) and (h). For a message (m\in\mathbb Z_q) and uniform randomness (r\in\mathbb Z_q), a Pedersen commitment has the form
[ C=g^m h^r. ]
The scheme is perfectly hiding. For every fixed message (m), multiplication by (g^m) permutes the group, while (h^r) is uniformly distributed over (G). Consequently, the distribution of (C) is independent of the committed message.
Its binding property is computational. Two valid openings ((m,r)) and ((m',r')), with (m\neq m'), satisfy
[ g^m h^r=g^{m'}h^{r'}. ]
Rearranging this equality reveals the discrete logarithmic relation between (g) and (h). An efficient method for obtaining conflicting openings therefore yields an efficient method for solving the corresponding discrete logarithm instance.
Pedersen commitments are additively homomorphic. Given commitments (C_1=g^{m_1}h^{r_1}) and (C_2=g^{m_2}h^{r_2}), their product is
[ C_1C_2=g^{m_1+m_2}h^{r_1+r_2}, ]
which commits to the sum of the messages. This algebraic structure supports proofs about committed values without exposing them. It also implies that the generators must be established without disclosing their logarithmic relation, since knowledge of that relation permits the construction of alternative openings.
Commitments in proof systems
In a zero-knowledge proof, commitments separate the prover’s initial choices from a verifier’s later challenge. The binding condition prevents the prover from modifying those choices after receiving the challenge, while the hiding condition prevents the verifier from learning them prematurely. This structure appears in identification protocols, proofs of knowledge, and transformations from interactive arguments to more elaborate proof systems.
Commitments also provide inputs to secure multi-party computation. Participants can commit to private values before later protocol messages are known, reducing the ability to choose inputs as a function of another participant’s behavior. When commitments are combined with proofs that their contents satisfy specified relations, the protocol can enforce consistency without publishing the underlying values.
Ordinary hiding and binding do not by themselves guarantee security in every larger protocol. A malleable commitment may allow an adversary to transform a commitment to (m) into a related commitment without learning (m). Non-malleable commitments strengthen the primitive by preventing such dependencies, while extractable and equivocal commitments provide simulation properties used in composable security definitions.
Quantum considerations
Quantum information changes the boundary between computational and information-theoretic commitments. Dominic Mayers, Hoi-Kwong Lo, and H. F. Chau established that unconditionally secure two-party quantum bit commitment is impossible in the standard model. A perfectly hiding quantum commitment leaves the receiver’s reduced state independent of the committed bit, which permits a dishonest committer to transform one purification into another and alter the opening.
This impossibility does not exclude commitments based on computational assumptions or additional physical restrictions. Quantum-resistant commitment schemes instead formulate hiding and binding against quantum algorithm adversaries, with their security derived from assumptions not known to admit efficient quantum solutions.