Motivation
Knowing a secret and revealing a secret are different acts. A user who holds a discrete logarithm can demonstrate knowledge without sending that logarithm: first commit to a random group element, then answer a fresh challenge. The random commitment hides the witness in the response, while two different challenges answered for the same commitment expose it. Understanding both sides explains why the temporary nonce is as sensitive as the long-term key.
The resulting three-message protocol is a mathematical starting point for signatures. Replacing the verifier's challenge by a hash of the message and commitment yields a noninteractive signing rule, but correctness alone does not establish unforgeability. We will prove the exact interaction properties and exhibit concrete failures; a complete random-oracle reduction is not assumed or silently claimed.
Definitions
A witness is a value satisfying a publicly stated relation; here that relation is . A verifier sees the public key and the messages in a conversation, while an honest prover also knows a witness. A transcript is the ordered record of one conversation, including its challenge. An accepting transcript is one for which the verifier’s stated test succeeds. These words describe mathematical roles, not guaranteed properties of a software implementation.
When a protocol chooses a uniform scalar, its probability space assigns probability to each field element. The challenge distribution and the prover’s nonce are independent in an honest execution. A malicious participant can choose values according to another rule; our theorems specify exactly where they need the honest distribution and where they instead apply to arbitrary accepting records. Keeping those quantifiers visible prevents a distributional simulation from being confused with a general attack-prevention guarantee.
Groups, witnesses and interaction
Let be a prime and let be a cyclic group of exactly elements, written multiplicatively. Exponents are elements of the field ; the identity is . The public key is for a secret . The group, its canonical element encoding and are public. Membership and equality in must be efficiently checkable for an implementation; they are mathematical operations in the protocol below.
The prover draws uniformly from and sends . The verifier draws a challenge uniformly and independently from . The prover returns
The verifier accepts exactly when the received values are valid group/scalar elements and . The values form a transcript. Reusing because the same nonce is used twice is not an innocuous compression of two interactions: its consequences will be calculated explicitly.
Common mistake
(Reducing the response modulo the wrong number)
The response is an exponent of , so only its residue modulo the group order matters; it is not an element of the ambient modulus. Take the group generated by modulo , which has order , with , , , and . Then . Reducing modulo gives , and , so the transcript verifies. Reducing modulo instead gives , and : the honest prover is rejected. Leaving unreduced is harmless because ; reducing modulo a number that is not a multiple of is not.
Theorem 4.4.1
(Completeness and special soundness)
An honest prover always passes. From any two accepting transcripts and with the same commitment and distinct challenges, one can efficiently recover a witness satisfying :
The conclusion concerns two accepting transcripts for the same public key and commitment; one accepting transcript alone is not enough for this extraction formula.
Proof
(Divide the two verification equations)
For an honest response, . For extraction, divide the two accepted equations to obtain . Because is nonzero in the field, it has an inverse. Raising both sides to that inverse gives . This algebra does not require us to know the discrete logarithm in advance. Primality of matters: in a composite exponent ring a nonzero challenge difference need not be invertible.
Proof X-ray
The repeated commitment is the common equation
The two responses contain different multiples of the same witness and exactly the same unknown nonce. Subtraction removes that nonce. If commitments differ, subtracting the responses leaves two unknown nonces, and this extraction argument no longer applies. If challenges agree, the needed inverse does not exist. These are hypotheses, not bookkeeping decorations.
Simulating an honest verifier
A transcript can look authentic without being produced using the witness. This observation is a precise distribution statement about an honestly sampled challenge; it is not yet a statement about every interactive verifier.
Theorem 4.4.2
(Exact honest-verifier transcript simulation)
For a valid public key , choose independently and uniformly in and set . The resulting transcript has exactly the same distribution as an honest execution with an independent uniform challenge, and it always verifies.
Proof
(A bijection between nonces and responses)
Write . In an honest execution the pair is uniform on . The map is a bijection, since . Thus is also uniform. The commitment is then , which is precisely the simulator's output. Verification follows immediately from the definition of . The simulator does not compute ; the proof uses its mathematical existence only to compare distributions.
The order in which values are generated is essential. In a real interaction the prover sends before seeing the verifier's challenge. A simulator that chooses after selecting reproduces the final honest transcript distribution, but it does not by itself simulate an arbitrary verifier whose challenge can depend on and its own state. Stronger zero-knowledge definitions and their proofs require additional work.
Concept lensStructural
Existence, knowledge and distribution
Every element of has some exponent because generates . That existential fact does not provide an efficient algorithm to find the exponent. Special soundness supplies one from two specially related accepting transcripts. Honest-verifier simulation supplies an indistinguishable transcript distribution without such a witness. None of these statements alone is a computational hardness theorem.
Worked example 4.4.3
(A complete small transcript)
In the multiplicative group modulo , the element has order : , and its order is neither nor any other divisor of prime . Set , so . For , . With challenge , the response is . Both sides of verification equal modulo : and . The arithmetic is deliberately tiny so that it can be checked by hand; such a group supplies no practical security.
Worked example 4.4.4
(Simulating the same public transcript)
Keep , and . Choose and directly. The simulator computes . The transcript is identical to the previous example, although the simulator did not need to discover . A single matching example illustrates the formula; the bijection above, not the example, proves equality of the entire distributions.
A signature rule and its boundaries
Let be a specified public function that maps a canonical encoding of to . To sign a message , draw a fresh uniform nonce , form , compute and output with . Verification recomputes from the supplied commitment and message, checks all encodings and membership, and accepts exactly when . Correctness follows from the earlier equation.
The hash input must have an unambiguous encoding. In a real protocol, distinct group elements and messages must not accidentally serialize to the same input, and domains and algorithm identifiers need an agreed format. Reject malformed elements or out-of-range scalars instead of treating their bit representations as if they were automatically valid members. These checks are part of defining what is signed; merely displaying a group equation does not supply them.
Common mistake
(Hashing the message without the commitment)
If the challenge is computed as , a forger knows it before choosing the commitment. For any message it picks and sets ; then , so verification accepts without any knowledge of . This is the honest-verifier simulator run with the challenge . In the small group modulo with , a message with and the choice give , the transcript of the simulation example above. Including in the hash input forces the commitment to be fixed before the challenge is known.
Theorem 4.4.5
(Two signatures with one nonce reveal the key)
Suppose two valid signatures under the same public key use the same nonce , have challenges , and reveal responses . Then the public transcripts determine the secret residue
If itself becomes known from one valid response and , then . These statements hold regardless of whether has any cryptographic security property.
Proof
(Special soundness, and a known nonce)
The first conclusion is special soundness: the repeated nonce gives the same . For the second, rearrange and invert the nonzero challenge. If the challenges coincide, the displayed inverses do not exist; one cannot infer the secret from these formulas. A reused nonce can still be dangerous in other ways, but that is a separate claim requiring its own argument.
Worked example 4.4.6
(Recovering a reused secret)
Continue the small group example. A second challenge answered with the same gives . The challenge difference is , whose inverse is . Hence , recovering the secret. Nothing here assumes that a realistic hash can be forced to output the chosen pair of challenges; the calculation is conditional on two actual distinct challenges.
Worked example 4.4.7
(Why a random-looking key is not enough)
Suppose the signer picks a uniformly random secret once, but a software fault repeats the same nonce on two messages whose challenges differ. The extraction formula returns that originally random exactly. A good initial key distribution does not compensate for nonce reuse. Conversely, generating different nonce values by a procedure with hidden bias or leakage requires analysis beyond merely checking that the two observed commitments differ.
Counterexample mode
Correct verification does not imply unforgeability
Take the public function for every input. An adversary who has never asked for a signature chooses any , sets and outputs on any message. Verification accepts because . The honest signing equation remains correct, yet signatures are forgeable. The example rules out a security conclusion based on the equation alone; it does not say that every nonconstant hash is secure.
What the proof does and does not establish
The interaction has perfect completeness, the stated two-transcript extraction property, and an exact honest-verifier transcript simulator. None says that a polynomial-time adversary cannot forge a signature. Such a theorem needs a precise attack experiment, a computational assumption on the group and an appropriate model or concrete properties for the challenge function, along with a reduction accounting for queries and probability loss. The simulator above cannot simply program an ordinary fixed hash. We do not prove the stronger theorem here.
Uniformity means independent sampling from all of in each execution. In particular, this mathematical version allows zero; a concrete standard may specify a different nonce domain and sampling procedure. Avoiding modulo bias, protecting transient state, preventing repeated nonces after crashes, and binding the right protocol context are implementation questions not certified by the abstract proof. Replaying an old valid signature is also different from forging a signature on a fresh message: an application may need its own replay policy.
Exercises
Quick check
(Verify an honest transcript when . Does this single execution reveal ?)
Compare the response with the nonce.
Solution
The response is and , so verification succeeds. Since , this transcript's response equals the nonce but contains no algebraic multiple of . The formula for known-nonce extraction requires ; it cannot be applied here. This does not analyze leakage across other interactions.
Quick check
(For the group modulo above, simulate a transcript with and . Check verification without using .)
Use .
Solution
The simulator takes modulo . The transcript verifies because . It was constructed from public information, and the simulator's full distribution was proved by a bijection rather than by this one sample.
Quick check
(Two accepting transcripts share and have responses , and challenges , in . Recover the exponent and identify the public group element.)
Apply the special-soundness formula, then compute modulo .
Solution
The difference of responses is and the difference of challenges is , whose inverse modulo is . Thus the recovered exponent is , and . The hypothesis that the two transcripts actually verify with the same and public key is necessary; arbitrary numeric pairs need not be transcripts at all. Here they are consistent: both give the nonce .
Quick check
(Explain the precise failure of the two-response extraction formula when the challenges are equal. Is an inverse of their difference available?)
Look at what the verification equations force for and .
Solution
If , then , and zero has no multiplicative inverse in . For two valid responses to the same commitment and challenge, the verification equations force modulo the group order, so subtraction yields only . This gives no value for .
Quick check
(In the constant-zero-hash counterexample, choose in the toy group. Give the forged signature and verify its equation for any message.)
With the verification equation reduces to .
Solution
Choose and output . The verifier obtains and checks modulo . The signature verifies for every message despite requiring no signing query and no knowledge of the secret exponent.