Glossary
Short, plain-language definitions for terms used elsewhere on this site. Each links back to the page where it’s explained in more depth.
Binding
The property that once you’ve committed to a value, you can’t later “open” the commitment to a different value. See what a commitment scheme is for the two strengths this comes in, and Pedersen commitments for why Pedersen’s binding is computational, reducing to the discrete logarithm problem.
Commitment scheme
A pair of algorithms, Commit and Open, that let you lock in a value now and
reveal it later without being able to change it — the cryptographic version of a
sealed envelope. See what a commitment scheme
is.
Completeness
The property of a proof system that says: if the statement is actually true and both parties follow the protocol honestly, the verifier accepts. (The counterpart to soundness — completeness is about honest provers succeeding, soundness is about dishonest provers failing.)
Discrete logarithm problem
Given a group element and another element , the discrete logarithm problem is finding . In groups where this is believed to be computationally hard (certain subgroups mod a large prime, or elliptic curve groups), it underlies the security of Diffie–Hellman key exchange, Schnorr signatures, and — as used on this site — the binding property of Pedersen commitments.
Hiding
The property that a commitment C reveals nothing about the committed value m
before it’s opened. See what a commitment scheme
is for the computational-vs-information-
theoretic distinction, and why Pedersen’s hiding is
information-theoretic.
Homomorphic commitment
A commitment scheme where combining two commitments (e.g. multiplying them) produces a valid commitment to the combination of the underlying values (e.g. their sum) — without opening either one. Pedersen commitments have this property; see the homomorphic property and its use in confidential transactions.
Nothing-up-my-sleeve
A value (like the generator in a Pedersen commitment) produced by a public, deterministic, auditable procedure — typically hashing a fixed string — instead of being chosen freely by anyone. This rules out the value having been picked to secretly satisfy some relation (like a known discrete log) that would break the scheme’s security. The demos on this site derive their generators this way; see Pedersen commitments.
Prover / verifier
The two roles in an interactive proof: the prover wants to convince the verifier that some statement is true (often, that they know a witness) — ideally without revealing anything beyond that fact.
Soundness
The property of a proof system that says: if the statement is actually false, no cheating prover can convince the verifier it’s true (except with some small probability). The counterpart to completeness.
Witness
The secret information a prover holds that makes a statement true — for example,
the opening (m, r) of a commitment C, or the private key corresponding to a
public key. A zero-knowledge proof lets the prover convince a verifier they
possess a witness without revealing the witness itself.
Zero-knowledge proof
An interactive (or, via the Fiat–Shamir transform, non-interactive) protocol in which a prover convinces a verifier that a statement is true while revealing nothing else — not even the witness itself. Introduced by Goldwasser, Micali, and Rackoff in 1985; see History for the full timeline from there to Pedersen commitments and beyond.
Sources: these are standard definitions used consistently across the cryptography literature; see History for citations to the original papers that introduced several of these concepts.