Pedersen Commitment Scheme #
This file defines the Pedersen commitment scheme over a pairing group and proves:
Perfect hiding: The hiding advantage is exactly 0 for any adversary. The proof uses a bijection argument: for any two messages
m₀, m₁, the mapr ↦ r + β⁻¹ · (m₁ - m₀)is a bijection onZMod p(whenβ ≠ 0), making the commitment distributions identical.Computational binding from DLog: Any adversary that breaks binding can be used to solve the discrete logarithm problem. Specifically,
Binding_Advantage ≤ DL_Advantagevia an explicit reduction.UC wrapping: Perfect hiding lifts to UC emulation at ε = 0.
Construction #
Given a pairing group with generators g₁ and a second generator h = g₁^β
(where β is the secret trapdoor, unknown to the committer):
commit(m, r) = g₁^m · h^r = g₁^(m + β·r)verify(C, m, r) = (C == g₁^m · h^r)
References #
- [Pedersen, Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing, CRYPTO 1991]
- [CatCrypt KZGPed hiding — bijection argument pattern]
Pedersen Parameters #
Parameters for the Pedersen commitment scheme.
The scheme operates in the source group G₁ of a pairing group P.
The second generator h = g₁^β is determined by the secret exponent β.
Both messages and randomness live in ZMod P.p.
The key security property is that β is unknown to the committer:
- Hiding holds unconditionally (information-theoretically) when
β ≠ 0 - Binding holds computationally, assuming DLog is hard
The underlying pairing group
The secret exponent determining h = g₁^β
β is nonzero (otherwise h = 1 and hiding fails)
Instances For
The second generator h = g₁^β
Equations
Instances For
Commitment Operations #
Pedersen commitment: C = g₁^m · h^r = g₁^(m + β·r).
The commitment is computed as a product of two group elements: one determined by the message, one by the randomness.
Equations
Instances For
The commitment equals g₁^(m + β·r) when expressed as a single exponentiation.
Verification: check that C = g₁^m · h^r.
Instances For
Hiding Game #
Pedersen hiding adversary: chooses two messages, then distinguishes from commitment.
- choose : Core.SPComp (ZMod Crypto.PairingGroup.p × ZMod Crypto.PairingGroup.p)
Choose two messages
- distinguish : Crypto.PairingGroup.G₁ → Core.SPComp Bool
Distinguish given commitment
Instances For
Pedersen hiding game with bit b: commit to m_b with fresh randomness.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Pedersen hiding advantage.
Equations
- pp.PedHiding_Advantage A = CatCrypt.Crypto.Advantage (pp.PedHiding_Game A false) (pp.PedHiding_Game A true)
Instances For
Perfect Hiding Proof #
Key algebraic identity: shifting the randomness by δ = β⁻¹ · (m₁ - m₀)
transforms a commitment to m₀ into a commitment to m₁.
Specifically: commit(m₁, r) = commit(m₀, r + β⁻¹·(m₁ - m₀)).
For any two messages, the commitment games are equal.
This is the core of perfect hiding: sampling r uniformly and computing
commit(m₀, r) gives the same distribution as commit(m₁, r), because
the bijection r ↦ r + β⁻¹·(m₁ - m₀) preserves uniformity.
Perfect hiding: The Pedersen hiding advantage is exactly 0.
For any adversary A, the hiding games for bit 0 and bit 1 produce identical
distributions, regardless of which messages the adversary chooses.
Binding Game and DLog Reduction #
The DLog game specialized for Pedersen: sample β, give h = g₁^β to adversary.
We need a game where β is sampled (rather than fixed as in PedersenParams),
so the reduction works for any β. The adversary outputs (m₁, m₂, r₁, r₂).
Equations
- One or more equations did not get rendered due to their size.
Instances For
The DLog reduction adversary: given h = g₁^β and a binding break
(m₁, m₂, r₁, r₂) with m₁ ≠ m₂ and g₁^(m₁ + β·r₁) = g₁^(m₂ + β·r₂),
extract β = (m₁ - m₂) · (r₂ - r₁)⁻¹.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Algebraic Core Lemmas #
Injectivity of g₁^· : if g₁ ^ᵍ a = g₁ ^ᵍ b then a = b in ZMod p.
When m₁ ≠ m₂ and m₁ + β·r₁ = m₂ + β·r₂ in ZMod p,
we can extract β = (m₁ - m₂) · (r₂ - r₁)⁻¹.
This is the algebraic heart of the binding-to-DLog reduction.
Binding Security Bound #
Computational binding from DLog: Breaking Pedersen binding implies solving DLog.
Given an adversary A that breaks binding with advantage ε, we construct
a DLog adversary binding_to_dlog A with advantage at least ε.
The proof proceeds by:
- Unfolding both games to expose the common
sample β >>= (A (g₁^β) >>= ...) - Applying
prTrue_bind_monoat each bind layer - Using the algebraic lemma to show a binding break implies a DLog solution
UC Wrapping #
UC security for Pedersen hiding (perfect, ε = 0).
Since the commitment distributions are independent of the committed message
(by the bijection argument), UC emulation holds at ε = 0
via UCEmulates_of_game_eq.
Combined Security Statement #
Full Pedersen security: perfect hiding and computational binding.
- Hiding: The hiding advantage is 0 for any adversary (information-theoretic).
- Binding: The binding advantage is bounded by the DLog advantage (computational).
Together, these give the standard Pedersen security guarantee: the scheme is perfectly hiding and computationally binding under DLog.