pedersen-unbounded-adversary.ipynb

Kernel: SageMath 10.0

Break: Opening Pedersen Commitments Two Ways

Module 09 | Breaking Weak Parameters

A computationally unbounded adversary can open a Pedersen commitment to any value, because perfect hiding and perfect binding cannot coexist.

Why This Matters

In 09b, we learned that Pedersen commitments are perfectly hiding: even an all-powerful adversary learns nothing about the committed value from seeing the commitment. We also learned the price: binding is only computational, it relies on the hardness of the discrete logarithm problem.

But what does "only computational binding" actually mean in practice? It means:

• A polynomial-time adversary cannot find two valid openings for the same commitment (assuming DLP is hard).

• A computationally unbounded adversary, one who can solve the DLP, can open any commitment to any value.

In this notebook, we play the role of the unbounded adversary. We will:

1. Commit to a value $m = 42$

2. Open the same commitment to $m' = 99$ (and any other value we choose)

3. Understand why this is a feature, not a bug: the hiding-binding tradeoff is fundamental.

Setup: Pedersen Parameters

We work in a prime-order subgroup of $\mathbb{Z}_p^*$ with:

• Safe prime $p = 2q + 1$

• Generators $g$ and $h$ of the order-$q$ subgroup

• The commitment to message $m$ with randomness $r$ is: $C = g^m \cdot h^r \bmod p$

The critical assumption for binding: nobody knows $a = \log_g(h)$.

For this attack, we will deliberately set up the parameters so that we do know $a$. This simulates a computationally unbounded adversary who can solve the DLP.

# === Pedersen Setup (we cheat and keep track of log_g(h)) ===

def find_safe_prime(bits=20):
    """Find a safe prime p = 2q + 1 where q is also prime."""
    while True:
        q = random_prime(2^bits, lbound=2^(bits-1))
        p = 2 * q + 1
        if is_prime(p):
            return p, q

p, q = find_safe_prime(20)

# Find generator g of the order-q subgroup
while True:
    g = power_mod(randint(2, p - 2), 2, p)
    if g != 1:
        break

# Deliberately choose h = g^a so we know a = log_g(h)
a = randint(2, q - 1)  # THE SECRET: log_g(h)
h = power_mod(g, a, p)

print(f"Safe prime: p = {p}")
print(f"Subgroup order: q = {q}")
print(f"Generator g = {g}")
print(f"Generator h = {h}")
print(f"Verify: g^q mod p = {power_mod(g, q, p)}  (should be 1)")
print(f"Verify: h^q mod p = {power_mod(h, q, p)}  (should be 1)")
print(f"\nThe secret: a = log_g(h) = {a}")
print(f"Verify: g^a mod p = {power_mod(g, a, p)} = h? {power_mod(g, a, p) == h}")
print(f"\nIn practice, nobody knows a. We know it because we set up")
print(f"the parameters ourselves, simulating an unbounded adversary.")

Step 1: Commit to $m = 42$

The honest committer creates $C = g^m \cdot h^r \bmod p$ with a random blinding factor $r$.

# === Step 1: Create an honest commitment ===

def pedersen_commit(m, r, g, h, p):
    """Compute Pedersen commitment C = g^m * h^r mod p."""
    return (power_mod(g, m, p) * power_mod(h, r, p)) % p

def pedersen_verify(C, m, r, g, h, p):
    """Verify that C opens to (m, r)."""
    return C == pedersen_commit(m, r, g, h, p)

# Honest commitment to m = 42
m = 42
r = randint(1, q - 1)
C = pedersen_commit(m, r, g, h, p)

print(f"Message:    m = {m}")
print(f"Randomness: r = {r}")
print(f"Commitment: C = g^{m} * h^{r} mod p = {C}")
print(f"\nVerify opening: {pedersen_verify(C, m, r, g, h, p)}")

Step 2: The Algebra of the Attack

We want to open $C$ to a different message $m'$. We need to find $r'$ such that:

$$C = g^{m'} \cdot h^{r'} \bmod p$$

Since $C = g^m \cdot h^r$, we need:

$$g^m \cdot h^r = g^{m'} \cdot h^{r'}$$

Rearranging:

$$g^{m - m'} = h^{r' - r}$$

Since $h = g^a$, this becomes:

$$g^{m - m'} = g^{a(r' - r)}$$

Working in exponents mod $q$:

$$m - m' \equiv a(r' - r) \pmod{q}$$$$r' \equiv r + \frac{m - m'}{a} \pmod{q}$$

This requires computing $a^{-1} \bmod q$, which is easy since $q$ is prime. But it requires knowing $a = \log_g(h)$, which only an unbounded adversary can compute.

# === Step 2: Open the commitment to m' = 99 ===

m_prime = 99

# Compute r' = r + (m - m') * a^(-1) mod q
a_inv = inverse_mod(a, q)
r_prime = (r + (m - m_prime) * a_inv) % q

print(f"Target message: m' = {m_prime}")
print(f"Compute: r' = r + (m - m') * a^(-1) mod q")
print(f"         r' = {r} + ({m} - {m_prime}) * {a_inv} mod {q}")
print(f"         r' = {r_prime}")
print()

# Verify the alternative opening
C_check = pedersen_commit(m_prime, r_prime, g, h, p)
print(f"Original commitment:  C = {C}")
print(f"Alternative opening: C' = g^{m_prime} * h^{r_prime} mod p = {C_check}")
print(f"Same commitment? {C == C_check}")
print()
print(f"Verification with (m={m}, r={r}):      {pedersen_verify(C, m, r, g, h, p)}")
print(f"Verification with (m'={m_prime}, r'={r_prime}): {pedersen_verify(C, m_prime, r_prime, g, h, p)}")
print()
print(f"Both openings are valid! Binding is BROKEN.")

Step 3: Open to Any Value

The attack is not limited to $m' = 99$. Once we know $a = \log_g(h)$, we can open the commitment to any message whatsoever. Let's demonstrate with several target values.

# === Step 3: Open to ANY value ===

print(f"Original commitment: C = {C}  (honestly committed to m = {m})")
print(f"\nOpening C to various messages:")
print("m_target  r_target  Verifies?")
for m_target in [0, 1, 7, 42, 99, 1000, q - 1]:
    r_target = (r + (m - m_target) * a_inv) % q
    valid = pedersen_verify(C, m_target, r_target, g, h, p)
    marker = " <-- original" if m_target == m else ""
    print(f"{m_target}  {r_target}  {str(valid)}{marker}")

print(f"\nEvery single opening is valid.")
print(f"The commitment C is consistent with EVERY possible message.")
print(f"This is why Pedersen commitments are PERFECTLY hiding --")
print(f"and it is also exactly why binding cannot be perfect.")

Step 4: Why This Requires Solving the DLP

The formula $r' = r + (m - m') \cdot a^{-1} \bmod q$ requires knowing $a = \log_g(h)$. In a proper Pedersen setup, $g$ and $h$ are generated so that nobody knows $\log_g(h)$. Common approaches:

1. "Nothing-up-my-sleeve" generation: Derive $h$ from a hash: $h = \text{HashToGroup}(\text{"Pedersen generator 2"})$. Nobody can compute $\log_g(h)$ from such a derivation.

2. Trusted setup ceremony: Multiple parties contribute randomness; as long as one is honest, $\log_g(h)$ remains unknown.

An efficient adversary who cannot solve the DLP is stuck: the formula exists but is unusable.

# === Demonstrate: without knowing a, the attack fails ===

# Set up a "proper" Pedersen instance where we DON'T know log_g(h)
# We generate h by hashing, so no one knows a
import hashlib

def hash_to_generator(seed, g, p, q):
    """Derive a generator from a seed via hashing (nobody knows log_g(h))."""
    h_int = int(hashlib.sha256(seed.encode()).hexdigest(), 16) % p
    # Map into the order-q subgroup by squaring
    h_candidate = power_mod(h_int, 2, p)
    while h_candidate <= 1:
        h_int = (h_int + 1) % p
        h_candidate = power_mod(h_int, 2, p)
    return h_candidate

h_safe = hash_to_generator("Pedersen generator 2, nothing up my sleeve", g, p, q)
print(f"Safe generator h = {h_safe}")
print(f"h^q mod p = {power_mod(h_safe, q, p)}  (should be 1)")
print()

# Commit with the safe h
C_safe = (power_mod(g, m, p) * power_mod(h_safe, r, p)) % p
print(f"Commitment with safe h: C = {C_safe}")
print(f"\nTo open to m' = 99, we would need log_g(h) = ???")
print(f"Without solving the DLP, we cannot compute r'.")
print(f"Binding holds for any computationally bounded adversary.")

# For small parameters, we CAN brute-force it, illustrating the
# difference between computational and information-theoretic security
print(f"\n--- Brute force for small parameters (would be infeasible for 256-bit q) ---")
a_brute = discrete_log(Mod(h_safe, p), Mod(g, p))
print(f"Brute-forced log_g(h) = {a_brute}")
print(f"Verify: g^{a_brute} mod p = {power_mod(g, int(a_brute), p)} = h? {power_mod(g, int(a_brute), p) == h_safe}")
print(f"\nWith 256-bit q, this brute force would take longer than the age of the universe.")

The Insight: Hiding vs. Binding is Fundamental

A deep theorem in cryptography states:

No commitment scheme can be both perfectly hiding AND perfectly binding.

Intuition:

• Perfect hiding means every commitment $C$ is consistent with every message $m$ (for some $r$). This means alternative openings exist.

• Perfect binding means exactly one valid opening $(m, r)$ exists for each $C$. But then $C$ carries information about $m$ (ruling out perfect hiding).

Scheme	Hiding	Binding	Tradeoff
Hash commitment $H(m | r)$	Computational	Perfect	Unbounded adversary could learn $m$
Pedersen $g^m h^r$	Perfect	Computational	Unbounded adversary could open to any $m'$

Pedersen commitments choose perfect hiding because in protocols like zero-knowledge proofs and confidential transactions, privacy (hiding) is the primary goal. The binding guarantee is "good enough" as long as the DLP is hard, and for 256-bit prime-order groups, it is.

Exercises

Exercise 1: Multiple Alternative Openings

Using the parameters from the main demonstration (where we know $a = \log_g(h)$), commit to $m = 7$ with a random $r$, then find valid openings for $m' \in \{0, 50, 100, 200, 500\}$. Verify each one.

# === Exercise 1: Find alternative openings ===

m_ex = 7
r_ex = randint(1, q - 1)
C_ex = pedersen_commit(m_ex, r_ex, g, h, p)

print(f"Commitment: C = Commit({m_ex}, {r_ex}) = {C_ex}")
print()

for m_target in [0, 50, 100, 200, 500]:
    r_target = (r_ex + (m_ex - m_target) * inverse_mod(a, q)) % q
    valid = pedersen_verify(C_ex, m_target, r_target, g, h, p)
    print(f"  Open to m'={m_target}: r'={r_target}, valid={valid}")

print()
print("Each opening is valid, the commitment reveals nothing about m.")

Exercise 2 (Independent)

Show that finding two valid openings $(m_1, r_1)$ and $(m_2, r_2)$ for the same commitment $C$ directly reveals $\log_g(h)$.

Given: $g^{m_1} h^{r_1} = g^{m_2} h^{r_2}$, derive $a = \log_g(h) = (m_1 - m_2) \cdot (r_2 - r_1)^{-1} \bmod q$.

Use the openings from Exercise 1 to recover $a$ and verify it matches.

# === Exercise 2: Recovering log_g(h) from two openings ===

# Two valid openings for C_ex:
m1_ex, r1_ex = m_ex, r_ex                                         # original
m2_ex = 100
r2_ex = (r_ex + (m_ex - m2_ex) * inverse_mod(a, q)) % q           # alternative

# Recover a = log_g(h) = (m1 - m2) / (r2 - r1) mod q
a_recovered = ((m1_ex - m2_ex) * inverse_mod((r2_ex - r1_ex) % q, q)) % q

print(f"Opening 1: m1={m1_ex}, r1={r1_ex}")
print(f"Opening 2: m2={m2_ex}, r2={r2_ex}")
print(f"\nRecovered a = (m1-m2)/(r2-r1) mod q = {a_recovered}")
print(f"Actual a    = {a}")
print(f"Match? {a_recovered == a}")
print(f"\nBreaking binding <=> Solving the DLP.")
print(f"This is a REDUCTION: anyone who breaks binding")
print(f"can be turned into a DLP solver.")

Summary

Aspect	Detail
Property broken	Computational binding of Pedersen commitments
Adversary model	Computationally unbounded (can solve DLP)
Attack	Know $a = \log_g(h)$, compute $r' = r + (m-m') \cdot a^{-1} \bmod q$
Consequence	Can open any commitment to any value
Is this a bug?	No. It is the necessary price for perfect hiding
The tradeoff	Perfect hiding + computational binding (Pedersen) vs. computational hiding + perfect binding (hash commitments)
In practice	With 256-bit $q$, the DLP is intractable; binding holds against all realistic adversaries

The hiding-binding tradeoff is one of the deepest results in commitment scheme theory. You cannot have both properties hold unconditionally. Pedersen commitments choose perfect hiding because in zero-knowledge proofs, confidential transactions, and other privacy-preserving applications, the ability to hide committed values from even unbounded adversaries is worth the tradeoff of computational (rather than perfect) binding.

---

Back to Module 09: Commitment Schemes and Sigma Protocols