{ "id": "epkfgpxcy8", "slug": "commitment-scheme", "title": "Commitment scheme", "updated": "2026-10-15", "topic_path": [ { "id": "technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/topics/technology" }, { "id": "technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing" }, { "id": "technology.computing.networks", "label": "Networks and security", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.networks" }, { "id": "technology.computing.networks.alpha-2-to-ma", "label": "Titles 2 to Ma", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.networks.alpha-2-to-ma" } ], "geo": [ { "id": "geo.nongeo.t1946.technology.computing.networks.alpha-2-to-ma", "label": "Non-geographic · 1946 to 2000: Titles 2 to Ma", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.networks.alpha-2-to-ma", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t1946", "label": "Non-geographic · 1946 to 2000", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946" }, { "id": "geo.nongeo.t1946.technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology" }, { "id": "geo.nongeo.t1946.technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing" }, { "id": "geo.nongeo.t1946.technology.computing.networks", "label": "Networks and security", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.networks" }, { "id": "geo.nongeo.t1946.technology.computing.networks.alpha-2-to-ma", "label": "Titles 2 to Ma", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.networks.alpha-2-to-ma" } ] } ], "excerpt": "A commitment scheme is a two-phase cryptographic protocol that lets one party lock in a hidden value and later reveal it verifiably, guaranteeing hiding and binding.", "snippet": "A commitment scheme is a two-phase cryptographic protocol that lets one party lock in a hidden value and later reveal it verifiably, guaranteeing hiding and binding.", "node": "technology.computing.networks.alpha-2-to-ma", "markdown": "# Commitment scheme\n\nA commitment scheme is a two-phase cryptographic protocol that lets one party lock in a chosen value while keeping it hidden, and later reveal it in a way the other party can verify. It is the digital analog of a sealed envelope: once the message is placed inside it cannot be changed (binding), and no one can read it until the envelope is opened (hiding).[1](http://web.cs.ucla.edu/~rafail/Lecture3.pdf) Commitment schemes are used on their own and as building blocks in [verifiable secret sharing](https://www.edgepedia.org/verifiable-secret-sharing), zero-knowledge proofs, and e-voting.[2](https://arxiv.org/html/1705.05897v1)\n\n| Key fact | Detail |\n|---|---|\n| Guarantees | Hiding (the receiver learns nothing about the value before opening) and binding (the committer cannot change the value after committing)[1](http://web.cs.ucla.edu/~rafail/Lecture3.pdf) |\n| Phases | A commit phase, in which the committer generates and shares the commitment, and an open phase, in which the value is revealed and verified[3](https://www.zkdocs.com/docs/zkdocs/commitments/) |\n| Standard hash construction | Commit as \\( c \\leftarrow H(m, r) \\) for a random bit string \\( r \\); collision resistance gives binding, and the randomness gives hiding[4](https://crypto.stanford.edu/cs355/23sp/lec3.pdf) |\n| Pedersen commitment | \\( \\mathrm{com} = g^{m} \\cdot h^{r} \\) over a prime-order group: perfectly hiding, computationally binding if the discrete logarithm problem is hard, and additively homomorphic[5](https://berry.win.tue.nl/CryptographicProtocols/LectureNotes.pdf) |\n| KZG polynomial commitment | Constant-size (single group element) commitments to polynomials of any degree, verified with a constant number of pairings[6](https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf) • [7](https://book.encryptorium.com/part-6-post-quantum-zero-knowledge/ch32-commitment-schemes/) |\n| Concrete KZG figures | 96-byte proofs (commitment plus witness) on BLS12-381 at a 128-bit classical security level; verification costs 2 pairings[7](https://book.encryptorium.com/part-6-post-quantum-zero-knowledge/ch32-commitment-schemes/) |\n| Post-quantum status | KZG binding relies on a Strong Diffie-Hellman assumption broken by Shor's algorithm; lattice-based and hash-based alternatives are under active development[7](https://book.encryptorium.com/part-6-post-quantum-zero-knowledge/ch32-commitment-schemes/) • [8](https://www.mdpi.com/2410-387X/10/2/27) |\n\n## How it works\n\nThe protocol runs in two phases. In the commit phase, the receiver may first generate public parameters and send them to the committer; the committer then selects the message, computes a commitment \\( c \\leftarrow \\mathrm{Commit}(b, M) \\), and sends only \\( c \\). In the open (decommit) phase, the committer sends the revelation value and the message, and the receiver runs a verification algorithm to check that the opening matches the earlier commitment.[9](https://cgi.di.uoa.gr/~aggelos/crypto/page9/assets/4.5_commitments_handout.pdf) Equivalently, the sender picks a random key, encodes the message with it, and sends the encoding first; the key itself is sent only in the second phase.[10](http://theory.stanford.edu/~trevisan/cs276/lecture27.pdf)\n\nHiding and binding have precise forms. Hiding means the receiver cannot guess the committed bit with probability significantly better than \\( 1/2 \\) (plus a negligible \\( \\varepsilon \\)); formally, commitments to any two messages \\( m_{0} \\) and \\( m_{1} \\) are indistinguishable.[1](http://web.cs.ucla.edu/~rafail/Lecture3.pdf) • [11](https://perso.ens-lyon.fr/benoit.libert/cours-ZK.pdf) Binding means it is infeasible for any efficient adversary to output a single commitment c with two different valid openings \\( (m_{0}, r_{0}) \\) and \\( (m_{1}, r_{1}) \\) with \\( m_{0} \\neq m_{1} \\); the probability of success is negligible in the security parameter \\( \\lambda \\).[4](https://crypto.stanford.edu/cs355/23sp/lec3.pdf) • [12](https://65610.csail.mit.edu/2024/rec/rec8.pdf)\n\nBoth properties come in perfect (information-theoretic) and computational strengths. In a perfectly binding scheme, each commitment is information-theoretically bound to one decommitment value, and secrecy holds only against a computationally bounded receiver; in a perfectly hiding scheme, secrecy is information-theoretic and binding holds only against computationally bounded senders. A computationally hiding scheme exists under the minimal assumption of [pseudorandom generators](https://www.edgepedia.org/pseudorandom-generator), and a perfectly hiding one under one-way permutations.[13](https://web.cs.ucla.edu/~rafail/PUBLIC/52.pdf) A scheme that is both perfectly binding and perfectly hiding is impossible; this impossibility is folklore.[5](https://berry.win.tue.nl/CryptographicProtocols/LectureNotes.pdf)\n\n## How it is done\n\nThe simplest construction uses a hash function: to commit to \\( m \\), sample a random bit string \\( r \\) and compute \\( c \\leftarrow H(m, r) \\). The hope is that H is complicated enough that c reveals nothing about m (hiding) and that collisions in H are infeasible to find (binding); without modeling H as a random oracle this cannot be proven unconditionally.[4](https://crypto.stanford.edu/cs355/23sp/lec3.pdf) In lecture-note notation, commit0(u, x) = H(u ∥ x) with random u is computationally binding via collision resistance and computationally hiding via partial preimage resistance.[5](https://berry.win.tue.nl/CryptographicProtocols/LectureNotes.pdf)\n\nThe Pedersen commitment works in a group \\( (G, q, g) \\) of prime order \\( q \\). The receiver's setup outputs the group parameters and \\( h = g^{t} \\) for random \\( t \\); the committer samples a random opening value r (written d in some formulations) from \\( \\mathbb{Z}_{q} \\) and sends \\( c = g^{r} \\cdot h^{m} \\), and verification checks that \\( g^{r} \\cdot h^{m} \\) equals the commitment.[2](https://arxiv.org/html/1705.05897v1) • [9](https://cgi.di.uoa.gr/~aggelos/crypto/page9/assets/4.5_commitments_handout.pdf) The scheme is information-theoretically hiding because \\( g^{r} \\cdot h^{m} \\) is statistically independent of \\( m \\) (equivalently, \\( \\mathrm{com} \\) is uniformly distributed in \\( G \\)), and computationally binding as long as the discrete logarithm problem is hard.[5](https://berry.win.tue.nl/CryptographicProtocols/LectureNotes.pdf) • [13](https://web.cs.ucla.edu/~rafail/PUBLIC/52.pdf) In elliptic-curve form \\( C_{r}(x) = x \\cdot g + r \\cdot h \\), the hiding is unconditional: for any value \\( y \\) there exists a unique \\( s \\) with \\( C_{r}(x) = C_{s}(y) \\), whereas the plain commitment \\( C(x) = x \\cdot g \\) leaks committed values from small domains.[14](https://www.zkdocs.com/docs/zkdocs/commitments/kzg_polynomial_commitment/)\n\nPedersen commitments are also additively homomorphic: commit1(u, x) · commit1(u′, x′) = commit1(u + u′, x + x′), with multiplication in the group and additions in Z_n. This is what makes them useful for secure elections and multiparty computation.[5](https://berry.win.tue.nl/CryptographicProtocols/LectureNotes.pdf)\n\n## Origin\n\n[Moni Naor](https://www.edgepedia.org/moni-naor) introduced bit commitment in the bounded-receiver (unbounded-sender) model in the Journal of Cryptology paper \"Bit commitment using pseudorandomness\" in 1991.[15](https://doi.org/10.1007/bf00196774)\n\n## Variants\n\nPolynomial commitments. A polynomial commitment scheme lets a committer commit to a polynomial with a short string that a verifier can use to confirm claimed evaluations. The KZG polynomial commitment scheme gives two constructions in which commitments are single group elements; earlier homomorphic schemes had commitment sizes linear in the polynomial degree.[6](https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf) KZG is pairing-based: the commitment is \\( C = g^{p(\\tau)} \\), and opening at \\( z \\) produces a witness \\( W = g^{q(\\tau)} \\) verified by the pairing equation \\( e(C / g^{y}, g_{2}) = e(W, g_{2}^{\\tau} / g_{2}^{z}) \\).[7](https://book.encryptorium.com/part-6-post-quantum-zero-knowledge/ch32-commitment-schemes/) On BLS12-381, KZG produces 96-byte proofs at a 128-bit classical security level, with verification costing 2 pairings and proving costing \\( O(d \\log d) \\) FFT plus \\( O(d) \\) multi-scalar multiplication.[7](https://book.encryptorium.com/part-6-post-quantum-zero-knowledge/ch32-commitment-schemes/)\n\nVector commitments. Dario Catalano and Dario Fiore studied vector commitments in their 2011 paper \"Vector Commitments and their Applications\": a vector commitment lets one commit to an ordered sequence of q values (m1, …, mq) and later open the commitment at specific positions, with security captured by position binding; the commitment and openings should be concise, that is, independent of the vector length. Realizations exist from RSA and from Computational Diffie-Hellman in bilinear groups.[16](https://eprint.iacr.org/2011/495.pdf) KZG commitments can serve as vector commitments by interpolating a degree-\\( (n-1) \\) polynomial over \\( n \\) field elements, a building block for Verkle Trees with extremely small proof sizes.[14](https://www.zkdocs.com/docs/zkdocs/commitments/kzg_polynomial_commitment/) A Merkle tree over a collision-resistant hash function is the classical way to commit to a vector and open locally to any position.[17](https://www.di.ens.fr/~nitulesc/files/vc-sok.pdf)\n\nEquivocable and non-malleable commitments. Non-malleability, motivated by fair contract bidding where bids must not be correlated with others' commitments, and equivocability, in which a simulator can produce commitments that open to chosen values for use in simulation-based proofs, are both studied strengthenings of the basic notion.[18](https://eprint.iacr.org/2003/080.pdf) Inner-product-argument (IPA) commitments of the Pedersen style, used in Bulletproofs and [Halo 2](https://www.edgepedia.org/halo-2), are transparent and can be statistically hiding via uniform blinding in the exponent.[7](https://book.encryptorium.com/part-6-post-quantum-zero-knowledge/ch32-commitment-schemes/)\n\n## Applications\n\n[Coin flipping](https://www.edgepedia.org/coin-flipping) is the original use: Alice locks her flip r0 in a (metaphorical) safe-deposit box, Bob flips r2 in the open, Alice reveals her combination, and the coin is r0 ⊕ r2.[1](http://web.cs.ucla.edu/~rafail/Lecture3.pdf) Commitment schemes also underpin verifiable secret sharing, zero-knowledge proofs, and e-voting,[2](https://arxiv.org/html/1705.05897v1) and KZG commitments specifically support verifiable secret sharing, zero-knowledge sets, credentials, and content extraction signatures.[6](https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf) In Ethereum, EIP-4844 adds a precompile that verifies a KZG proof claiming that a blob, represented by a commitment, evaluates to a given value at a given point.[19](https://eips.ethereum.org/EIPS/eip-4844) Danksharding uses KZG to reduce a blob of data to a small commitment: the commitment evaluates a polynomial fit to the data at points defined by random numbers generated in the KZG ceremony, which constructs the secret so that no single person knows it.[20](https://ethereum.org/roadmap/danksharding/) • [21](https://github.com/ethereum/kzg-ceremony/blob/main/FAQ.md)\n\n## Limitations and alternatives\n\nQuantum attacks on binding. KZG's binding relies on the d-Strong Diffie-Hellman assumption (one survey writes n-SDH), a discrete-log variant that quantum adversaries break: a Shor-capable adversary computes the discrete logarithm of \\( g^{\\tau} \\), recovers the trapdoor \\( \\tau \\), and forges openings at will.[7](https://book.encryptorium.com/part-6-post-quantum-zero-knowledge/ch32-commitment-schemes/) • [8](https://www.mdpi.com/2410-387X/10/2/27) IPA commitments are likewise Shor-broken.[7](https://book.encryptorium.com/part-6-post-quantum-zero-knowledge/ch32-commitment-schemes/)\n\nTrusted setup. KZG's setup samples a trapdoor τ, builds the structured reference string (g, g^τ, …, g^(τ^d)), and erases τ; a compromised ceremony leaks τ and destroys binding for every user of the string, quantum computer or not.[7](https://book.encryptorium.com/part-6-post-quantum-zero-knowledge/ch32-commitment-schemes/) In the Ethereum deployment, anyone who knew the random evaluation locations could add or remove blob data and still provide a valid proof, so provers receive the locations wrapped in elliptic-curve \"black box\" form.[20](https://ethereum.org/roadmap/danksharding/)\n\nHiding caveats. Published descriptions of KZG's hiding differ: ZKDocs states that hiding holds against up to \\( t \\) openings for a degree-\\( t \\) polynomial but is only computational, resting on discrete-log hardness,[14](https://www.zkdocs.com/docs/zkdocs/commitments/kzg_polynomial_commitment/) while the Book of PQC classifies KZG, Merkle, and FRI as binding but not hiding without an extra randomness coordinate.[7](https://book.encryptorium.com/part-6-post-quantum-zero-knowledge/ch32-commitment-schemes/) KZG also lacks indistinguishability for small-domain values, where an adversary can guess and check given \\( t \\) openings; mitigations include committing to \\( t+1 \\) points with one uniformly random extra point, or a Pedersen variant publishing f(α)·g1 + f̂(α)·h1.[14](https://www.zkdocs.com/docs/zkdocs/commitments/kzg_polynomial_commitment/)\n\nAlternatives. Merkle trees offer transparent, hash-only commitments at the cost of logarithmic proofs.[7](https://book.encryptorium.com/part-6-post-quantum-zero-knowledge/ch32-commitment-schemes/) • [17](https://www.di.ens.fr/~nitulesc/files/vc-sok.pdf) Post-quantum polynomial commitments now divide into lattice-based systems (Brakedown, lattice SNARKs, based on LWE and SIS; SLAP at EUROCRYPT 2024 bases security on the standard Module-SIS assumption)[8](https://www.mdpi.com/2410-387X/10/2/27) • [22](https://dl.acm.org/doi/10.1007/978-3-031-58754-2_4) and hash-based systems such as FRI, used in zk-STARKs, with transparent setups.[8](https://www.mdpi.com/2410-387X/10/2/27) KZG-style commitments can also be built without a structured trusted setup by committing with a plain Pedersen construction over \\( N \\) random elliptic-curve points with no known relationship, via \\( \\sum_{i} c_{i} \\cdot S_{i} \\).[23](https://vitalik.eth.limo/general/2022/03/14/trustedsetup.html)\n\n## References\n\n1. [Lecture notes: hard-core predicate bits and coin flipping using bit commitment](http://web.cs.ucla.edu/~rafail/Lecture3.pdf)\n2. [Automated Cryptographic Analysis of the Pedersen Commitment Scheme](https://arxiv.org/html/1705.05897v1)\n3. [Commitment Schemes | ZKDocs](https://www.zkdocs.com/docs/zkdocs/commitments/)\n4. [Stanford CS355 Lecture 3: Commitment Schemes](https://crypto.stanford.edu/cs355/23sp/lec3.pdf)\n5. [Cryptographic Protocols: Lecture Notes](https://berry.win.tue.nl/CryptographicProtocols/LectureNotes.pdf)\n6. [Constant-Size Commitments to Polynomials and Their Applications (Kate, Zaverucha, Goldberg, ASIACRYPT 2010)](https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf)\n7. [Chapter 32: PQ-secure commitment schemes | Book of PQC](https://book.encryptorium.com/part-6-post-quantum-zero-knowledge/ch32-commitment-schemes/)\n8. [Polynomial Commitment Schemes from Classical Constructions to Post-Quantum Directions](https://www.mdpi.com/2410-387X/10/2/27)\n9. [Commitments handout (University of Athens)](https://cgi.di.uoa.gr/~aggelos/crypto/page9/assets/4.5_commitments_handout.pdf)\n10. [Stanford CS276 Lecture 27 (Trevisan)](http://theory.stanford.edu/~trevisan/cs276/lecture27.pdf)\n11. [Commitment Schemes and Zero-knowledge proofs (Benoît Libert, ENS Lyon)](https://perso.ens-lyon.fr/benoit.libert/cours-ZK.pdf)\n12. [MIT 6.5610 Recitation 8: Commitment Schemes and Secret Sharing](https://65610.csail.mit.edu/2024/rec/rec8.pdf)\n13. [Equivocable and perfectly-hiding commitment schemes (UCLA, Ostrovsky et al.)](https://web.cs.ucla.edu/~rafail/PUBLIC/52.pdf)\n14. [KZG Polynomial Commitments | ZKDocs](https://www.zkdocs.com/docs/zkdocs/commitments/kzg_polynomial_commitment/)\n15. [Moni Naor (1991). Bit commitment using pseudorandomness. Journal of Cryptology.](https://doi.org/10.1007/bf00196774)\n16. [Vector Commitments and their Applications (Catalano-Fiore)](https://eprint.iacr.org/2011/495.pdf)\n17. [SoK: Vector Commitments](https://www.di.ens.fr/~nitulesc/files/vc-sok.pdf)\n18. [Non-malleable/equivocable commitments (NMcommit)](https://eprint.iacr.org/2003/080.pdf)\n19. [EIP-4844: Shard Blob Transactions](https://eips.ethereum.org/EIPS/eip-4844)\n20. [Danksharding | ethereum.org](https://ethereum.org/roadmap/danksharding/)\n21. [KZG ceremony FAQ](https://github.com/ethereum/kzg-ceremony/blob/main/FAQ.md)\n22. [SLAP: Succinct Lattice-Based Polynomial Commitments from Standard Assumptions (EUROCRYPT 2024)](https://dl.acm.org/doi/10.1007/978-3-031-58754-2_4)\n23. [How do trusted setups work?](https://vitalik.eth.limo/general/2022/03/14/trustedsetup.html)\n\n---\n*Topic: Encyclopedia › Technology and the built world › Computing and digital systems › Networks and security › Titles 2 to Ma*\n\n*Initially written Sep 29, 2026 · Edited: Oct 15, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n", "same_as": [ "http://web.cs.ucla.edu/~rafail/Lecture3.pdf", "http://theory.stanford.edu/~trevisan/cs276/lecture27.pdf", "https://web.cs.ucla.edu/~rafail/PUBLIC/52.pdf" ], "url": "https://www.edgepedia.org/commitment-scheme", "markdown_url": "https://www.edgepedia.org/commitment-scheme.md", "license": { "name": "Edgepedia Community License 1.0", "url": "https://www.edgepedia.org/edgepedia/license", "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.", "spdx": "LicenseRef-Edgepedia-Community-1.0" }, "credit": "\"Commitment scheme\", Edgepedia (EdgeChat), https://www.edgepedia.org/commitment-scheme. Edgepedia Community License 1.0.", "credit_md": "\"[Commitment scheme](https://www.edgepedia.org/commitment-scheme)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/commitment-scheme](https://www.edgepedia.org/commitment-scheme). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).", "credit_html": "\"Commitment scheme\", Edgepedia (EdgeChat), https://www.edgepedia.org/commitment-scheme. Edgepedia Community License 1.0.", "speakable": "A commitment scheme is a two-phase cryptographic protocol that lets one party lock in a hidden value and later reveal it verifiably, guaranteeing hiding and binding." }