1 Core concepts

Commitment schemes are cryptographic protocols that let one party, called the committer, choose a value and lock it in while keeping it concealed from others. Later, the committer can disclose the value together with evidence that it matches the original commitment. This separation between fixing a value and revealing it makes commitment schemes useful in many protocols where timing, honesty, or strategic behavior matters.

A commitment is often compared to placing a note in a sealed envelope. The envelope hides the note’s contents, but it also restricts the sender from changing the note after sealing it. In cryptographic settings, this balance is achieved through mathematical constructions and carefully chosen randomness.

1.1 Definition

A commitment scheme is usually described as a two-stage protocol. In the first stage, the sender commits to a chosen message and produces a commitment string. In the second stage, the sender reveals the message and any opening information, and the receiver checks that the opening is valid.

The scheme is designed so that the receiver learns nothing significant about the committed value before the opening phase, while the sender is unable to substitute a different value later. These two goals define the central tension in commitment design.

1.2 Commit and reveal phases

The commit phase begins when the committer selects a value and often combines it with fresh randomness. The output is the commitment, which can be published or transmitted to another party. At this point, the value is still hidden, but the commitment has fixed it in place.

The reveal phase, sometimes called the open phase, occurs when the committer discloses the value and the auxiliary data needed to verify it. The recipient checks that the opening corresponds to the original commitment. If the check succeeds, the value is accepted as authentic.

1.3 Security properties

The security of a commitment scheme is usually judged by two major properties: hiding and binding. These properties are often difficult to achieve simultaneously in their strongest forms, so different schemes aim for different trade-offs depending on the application.

1.3.1 Hiding

Hiding means that the commitment does not reveal useful information about the message before it is opened. In a strong hiding scheme, even an all-powerful observer cannot infer the value from the commitment alone. In weaker variants, the hidden value remains secure only against efficient attackers.

1.3.2 Binding

Binding means that once a commitment has been made, the sender cannot later open it as two different values. A perfectly binding scheme makes such equivocation impossible. In computationally binding schemes, changing the opening is possible only if the sender can solve a problem assumed to be infeasible.

1.3.3 Statistical, computational, and perfect guarantees

Perfect security means a property holds without exception. Statistical security allows a negligible deviation from ideal behavior, even against unlimited computation. Computational security protects against attackers limited to feasible algorithms. Commitment schemes often provide one property perfectly and the other only computationally or statistically, because achieving both perfectly for general messages is usually impossible.

1.4 Common notation

A commitment is commonly written as c = Com(m; r), where m is the message and r is random padding or witness data. The opening is written as (m, r), which can be verified by a function such as Ver(c, m, r). For bit commitments, the message is usually restricted to 0 or 1, while more general schemes commit to strings, vectors, or structured objects.

2 Types of commitment schemes

Commitment schemes can be categorized by the strength of their hiding and binding properties, as well as by whether they require interaction between the parties. The choice of type depends on the intended use, available assumptions, and desired efficiency.

2.1 Perfectly binding schemes

A perfectly binding scheme makes it impossible for a valid commitment to be opened in two different ways. This is useful when the main concern is preventing equivocation by the sender. Such schemes may still leak some information about the committed value unless additional design features are included.

2.2 Perfectly hiding schemes

A perfectly hiding scheme reveals nothing about the committed value, regardless of the attacker’s computational power. These schemes are especially attractive when confidentiality is paramount. Their drawback is that the binding property is then usually only computational or statistical.

2.3 Computationally binding schemes

Computationally binding schemes rely on the assumed difficulty of certain mathematical problems. An attacker may be able to produce alternate openings in theory, but not within practical limits. This is a common model in modern cryptography because it aligns with standard hardness assumptions.

2.4 Computationally hiding schemes

In a computationally hiding scheme, the commitment conceals the message from efficient adversaries, though a theoretically unlimited observer might recover it. This type is widely used because it can be built from standard cryptographic assumptions and often offers good efficiency.

2.5 Statistically secure schemes

Statistically secure schemes provide one property with a very high probability that is independent of computational power. A commitment may be statistically hiding or statistically binding, depending on the construction. These schemes are valued in settings where one wants assurance even against unusually strong adversaries.

2.6 Non-interactive commitment schemes

Non-interactive commitment schemes require only a single message from the committer to the receiver, or a public broadcast of the commitment. They are convenient in distributed protocols and often easier to use in larger systems. Many modern constructions are non-interactive, especially those based on hashes, algebraic assumptions, or public-key primitives.

3 Construction methods

Commitment schemes can be built from a variety of cryptographic assumptions and mathematical tools. Different methods offer different balances among simplicity, efficiency, and security guarantees.

3.1 Hash-based commitments

A simple approach is to commit to a message by hashing it together with random salt. The salt prevents precomputation and helps preserve hiding when the message comes from a limited set. This method is compact and practical, although its security depends on the properties of the hash function and the unpredictability of the message.

3.2 Bit commitment from one-way functions

One-way functions can be used to build bit commitments by encoding a bit in a structure that is easy to create but hard to invert. These constructions are conceptually important because they connect commitment schemes to basic assumptions in cryptography. They also serve as building blocks for more elaborate protocols.

3.3 Commitment from trapdoor permutations

Trapdoor permutations allow a sender to create commitments that are hard to open in multiple ways without a secret trapdoor. The trapdoor helps explain how the scheme can be secure while still being efficiently verifiable. Such constructions are often used in theoretical foundations and in protocols requiring strong proof techniques.

3.4 Commitment from discrete logarithms

Discrete logarithm based schemes use the difficulty of solving logarithms in a cyclic group. They frequently rely on exponentiation with random values, which can create commitments that are compact and mathematically elegant. Their security typically depends on assumptions about the hardness of discrete logarithms in the chosen group.

3.5 Commitment using randomness and salts

Randomness plays a central role in hiding the committed value. A salt or nonce adds uniqueness to the commitment, preventing two identical messages from producing the same output. This makes it harder for an observer to guess the value, especially when the set of possible messages is small.

3.6 Pedersen commitments

Pedersen commitments are a classic algebraic construction known for strong hiding properties and efficient operation. They are widely studied because they are simple, flexible, and compatible with many advanced protocols.

3.6.1 Algebraic structure

A Pedersen commitment is formed in a group where exponentiation is easy and the discrete logarithm problem is difficult. The committer combines the message and a random exponent using two group generators. The result is compact and can often be manipulated algebraically in useful ways.

3.6.2 Hiding and binding assumptions

Pedersen commitments are perfectly hiding under standard assumptions about the group structure and the randomness used. Their binding property depends on the assumption that no efficient party can find the hidden relationship between the generators. This means the scheme is secure when the mathematical setting is chosen carefully.

4 Variants and extensions

Many commitment-like tools extend the basic idea to richer data formats or specialized security features. These variants are designed to fit particular protocol needs rather than replace the fundamental commitment concept.

4.1 Bit commitment

Bit commitment is the simplest form, in which the committed value is either 0 or 1. It is a core primitive because more complex schemes can often be built from it. Despite its simplicity, it captures the essential hiding and binding trade-off.

4.2 String commitment

String commitment allows the sender to commit to an arbitrary bitstring or message. This is more practical than bit commitment alone because real protocols often need to handle larger data. String commitments may be built by committing to each bit separately or by using a single scheme for whole messages.

4.3 Vector commitment

Vector commitments let a sender commit to many values at once while later revealing selected positions. They are useful when a protocol needs compact storage and efficient partial opening. Their design often emphasizes succinct verification and data integrity.

4.4 Trapdoor commitment

Trapdoor commitments include a secret capability that allows special parties to open commitments in ways that ordinary users cannot. This feature is useful in certain proof systems and simulation arguments. The trapdoor is usually held by a trusted party or embedded in a setup phase.

4.5 Extractable commitment

Extractable commitments are designed so that a verifier or simulator can recover the committed value under certain conditions. They are important in formal proofs, especially when demonstrating that a protocol behaves correctly in adversarial environments. Their use is largely theoretical but highly influential.

4.6 Homomorphic commitment

Homomorphic commitments support algebraic operations on commitments that correspond to operations on the underlying messages. For example, combining two commitments may produce a commitment to the sum of the committed values. This property is especially valuable in protocols for distributed computation and proof systems.

5 Applications

Commitment schemes appear in many cryptographic systems because they provide a controlled way to postpone disclosure. They help ensure fairness, enable verification, and support privacy-preserving interaction.

5.1 Zero-knowledge proofs

In zero-knowledge proofs, commitments are often used to hide witness data while still allowing the prover to demonstrate knowledge of it. They help structure interactive challenges and prevent the prover from adapting answers after seeing the verifier’s questions. This makes them a standard component in many proof constructions.

5.2 Secure multiparty computation

In secure multiparty computation, participants may commit to inputs before running a joint computation. This reduces the risk of changing inputs after learning partial results. Commitments also help enforce consistency across multiple rounds or related subprotocols.

5.3 Mental poker and fair protocols

Commitment schemes are useful in games and protocols that require hidden choices followed by later verification. In mental poker, for example, players can commit to shuffled cards, actions, or random seeds. The commitments help preserve fairness by discouraging premature disclosure or cheating.

5.4 Auctions and sealed-bid systems

Sealed-bid auctions commonly use commitments so bidders can lock in their offers without revealing them early. This prevents strategic behavior based on competitors’ bids. When the auction closes, bids are opened and compared according to the auction rules.

5.5 Blockchain and distributed systems

In distributed systems, commitments can anchor data, show integrity, or support later verification of choices made earlier. They may be used in protocols that require delayed revelation, dispute resolution, or auditability. Their compactness and verifiability make them especially suitable for decentralized settings.

6 Security analysis

The security of a commitment scheme depends not only on its formal definition but also on the assumptions, environment, and attack model in which it is used. Careful analysis is essential because weaknesses may appear when the scheme is deployed outside idealized conditions.

6.1 Adversarial models

Different adversarial models consider different levels of power. Some attackers are efficient but not omniscient, while others may have unbounded resources in theoretical analyses. The chosen model affects whether the scheme is evaluated as computationally, statistically, or perfectly secure.

6.2 Probability of cheating

A key question is how likely it is for a dishonest committer to produce multiple valid openings or for a receiver to learn the committed value early. Security proofs usually bound these probabilities by negligible functions or by exact impossibility results. These bounds help determine whether a construction is suitable for practical use.

6.3 Randomness requirements

Many schemes rely on fresh randomness to ensure hiding. If the random input is weak, reused, or predictable, the commitment may fail to conceal the message. Good randomness generation is therefore an operational requirement, not just a mathematical detail.

6.4 Assumptions and limitations

Commitment schemes are only as strong as the assumptions behind them. A construction may depend on collision resistance, one-wayness, discrete logarithm hardness, or group setup conditions. If these assumptions are weakened or violated, the scheme’s security can degrade quickly.

6.5 Attack strategies

Attackers may exploit structure, predictability, or side information to undermine a commitment scheme. Security analyses often examine the most plausible ways an adversary could deviate from the protocol.

6.5.1 Collision attacks

Collision attacks aim to find two different messages that produce the same commitment or the same opening relation. Such attacks threaten binding because they enable equivocation. Strong design and suitable cryptographic assumptions are intended to make these attacks infeasible.

If the message space is small, an attacker may simply test possible values until one matches the observed commitment. This is a common concern for weakly randomized or low-entropy messages. Salts and larger message spaces help counter this risk.

6.5.3 Selective opening

Selective opening attacks occur when an adversary requests openings for some commitments and tries to infer information about the others. This is especially relevant in protocols with many related commitments. Robust schemes must remain secure even when only a subset is revealed.

Commitment schemes are closely connected to several other cryptographic primitives. These relationships help explain both their structure and their role in larger systems.

7.1 Hash functions

Hash functions are often used inside commitment constructions, especially when combined with randomness. They compress data and provide a fixed-size output, making them convenient for compact commitments. Their security properties strongly influence the resulting scheme.

7.2 Digital signatures

Digital signatures authenticate authorship and integrity, while commitments conceal content until opening. Although they serve different purposes, both can help prove that a value has not been altered. In some protocols, signatures and commitments are used together.

7.3 Encryption

Encryption hides a message from unauthorized parties, which is similar to the hiding goal of commitments. The difference is that encryption is meant to be decryptable by a recipient, whereas commitment schemes are meant to delay disclosure without granting immediate access. This makes commitments better suited to proof and fairness settings.

7.4 Zero-knowledge arguments

Zero-knowledge arguments often rely on commitments to hold witness values in place while challenge-response steps proceed. These schemes use commitments to prevent adaptive cheating. The two primitives are therefore tightly linked in both theory and practice.

7.5 Oblivious transfer

Oblivious transfer and commitment schemes are foundational primitives that can sometimes be used to construct one another under suitable assumptions. Oblivious transfer focuses on selective message delivery, while commitments focus on delayed disclosure. Their combination supports many advanced secure computation protocols.

8 Historical development

Commitment schemes emerged as part of the early development of modern cryptography, when researchers began formalizing how to hide and later reveal information with strong guarantees. Over time, they became a standard primitive in both theoretical and applied cryptography.

8.1 Early formulations

Early formulations were motivated by problems such as secure betting, fair exchange, and hidden choice. Researchers sought a protocol that would let one party lock in a decision without exposing it too soon. These ideas evolved into formal commitment schemes with precise security definitions.

8.2 Theoretical significance

Commitment schemes became important because they helped bridge the gap between simple cryptographic assumptions and powerful protocol design. They are often among the first nontrivial primitives derived from one-way functions or related hardness assumptions. Their study also clarified the distinction between hiding and binding as separate security goals.

8.3 Influence on modern cryptography

Modern cryptography uses commitment schemes in a broad range of protocols, from proofs and auctions to distributed computation. Their abstract structure makes them adaptable and easy to combine with other tools. As a result, they remain a central component of cryptographic protocol design.