Project · Implement Pedersen commitments

Implement Pedersen commit/open from scratch in Python over a prime-order subgroup of $(\mathbb{Z}/p\mathbb{Z})^*$ (or, for stretch, an elliptic curve). Demonstrate hiding empirically by showing two different messages with fresh randomness produce statistically indistinguishable commitment distributions, and demonstrate the binding reduction by showing that a colluding committer who *does* know $\log_g h$ can break binding — and that without that knowledge, even an adversary who tries millions of randomizations cannot. Your code must be small enough to be auditable in one sitting (under 200 lines) and your write-up must justify each design choice with a citation back to the relevant lemma from this module.

• A Python module `pedersen.py` exposing `setup(bits)`, `commit(m, r)`, `open(c, m, r)`, and `add(c1, c2)` for additive homomorphism, with no external crypto dependencies (use `secrets` for randomness, `pow` for modular exponentiation).
• A test script that verifies (a) `open` succeeds on honest commit, (b) the additive homomorphism $c_1 \cdot c_2 = \text{Commit}(m_1+m_2, r_1+r_2)$ holds for 1,000 random pairs, and (c) commitments to fixed $m$ over uniform $r$ are uniformly distributed across the subgroup (chi-squared test or histogram).
• A 'binding break' demo: a script `break_binding.py` that, when given $a = \log_g h$, produces a second valid opening $(m', r')$ to a previously honest commitment.
• A 1–2 page write-up (Markdown or PDF) tying each line of the implementation to a lemma or definition from Module 1 (DLP hardness, group structure, Pedersen binding/hiding properties).

• The chosen subgroup is of *prime* order $q$, and the code asserts subgroup membership via $x^q \equiv 1 \pmod p$ before using any element. Working in a non-prime-order group silently breaks binding.
• Hiding is verified empirically: 10,000+ samples of $\text{Commit}(m_0, r)$ and $\text{Commit}(m_1, r)$ are produced and a chi-squared test (or visual histogram) confirms both distributions are uniform on the subgroup, with $p$-value > 0.05.
• Binding is broken *only* when $\log_g h$ is known — without it, brute-force search across at least $10^6$ random $r'$ values must fail to produce a second valid opening.
• The write-up cites the binding reduction (a collision yields $\log_g h$) and explicitly identifies which step relies on $q$ being prime (so $(r - r')$ is invertible mod $q$).