System Security II

01 / System Security IIA construction and its proof are one object

The central question of this course is not only how to compute a signature or a session key. It is how an algorithm that breaks the construction could be used to solve a problem assumed to be hard. We study the reduction as an executable algorithm: it receives a challenge, creates the adversary's environment, answers queries and transforms a successful output into a solution.

The original lectures develop Schnorr and Okamoto identification, pairing-based modifications, signatures, encryption and authenticated key exchange. The chapters below retain that progression and make the proof obligations explicit. Complete elementary derivations are given where possible. A labelled proof outline identifies what still has to be established; it is not presented as a full theorem for a larger adversarial model.

You should be comfortable with System Security I, prime-order groups, conditional probability and algorithmic reductions. The goal is to be able to read an original cryptography paper, reproduce its scheme with correct types, and audit the interface between its construction and its proof.

The route through the course

First learn to simulate one transcript and extract from two. Then account for an adversary that succeeds only sometimes, chooses its queries adaptively and requests signatures before forging. Next compare three extraction styles: recovering a scalar by rewinding, reading a hard group element directly from a forgery, and recognising an informative random-oracle query. Finally apply the same discipline to anonymity and session-key experiments.

An elementary lemma below is proved in full. A construction-specific argument is accompanied by its model and any remaining conditions. This matters especially for the historical leakage-oriented protocols: a cancellation identity is useful, but it does not answer every oracle query in a full key-exchange experiment.

After this course you should be able to: write a reduction without secretly using its challenge solution; explain every change of distribution; identify the exact pair of transcripts needed by an extractor; and distinguish an anonymity proof from an unforgeability proof. The worked examples are classical. They do not claim security against quantum algorithms or quantum access to a random oracle.

02 / System Security IINotation, assumptions and proof contracts

Use $G=\langle g\rangle$ of prime order $q$, secret $a$, public key $A=g^a$, nonce $x$, commitment $X=g^x$, challenge $c$ and response $s$. Scalar arithmetic is in $\mathbb Z_q$. Unless stated otherwise, nonces and challenges are sampled uniformly from the whole field. This convention matters for exact simulation. Secret keys are nonzero. The adversary is $\mathcal A$ and the reduction is $\mathcal B$.

Hash notation and output types

The group subscript names the actual output group. When a derivation uses a generic group $G$, write $\H_G$; use $\H_{G_2}$ if the output is in $G_2$. This does not identify distinct source groups or change a proof's assumptions. All hash inputs are unambiguously encoded byte strings; writing a tuple or group point as an input abbreviates its specified encoding. Independent roles use separate domains, even when they share the symbol $\H$.

A public deterministic hash-to-group function must not provide a publicly computable discrete logarithm of its output relative to the generator. Merely returning a point of the right type is insufficient. In the BLS WebAssembly demo, $\H_{G_1}$ denotes the group-hashing role implemented with MCL's hashAndMapToG1; scalar hashing has a different interface, hashToFr. The notation alone does not assert compatibility with an RFC 9380 suite or a standard BLS byte format. See RFC 9380 and MCL WebAssembly.

The assumption must match the group family and available oracles. In a symmetric pairing group, a pairing can make DDH easy while CDH may remain hard. One cannot transport an ordinary DDH-based argument into that group without checking the assumption.

A proof contract specifies the adversary's running time, query bounds, public-key distribution, corruption rules and winning event. “Secure under DL” omits the attack model and reduction loss. Also distinguish a standard-model theorem from one that treats $\H$ as a programmable random oracle. An implementation using a fixed hash is an instantiation, not a programmable oracle service.

Write the reduction's state first

List the values the reduction knows and those it must not know. In a DL reduction with input $(g,A)$, computing $a$ to answer a training query is circular. A valid simulation must answer from available values or explicitly stop on a bounded bad event.

The direction of a reduction

Suppose an adversary breaks a signature scheme. To reduce forgery to DL, construct $\mathcal B$ that receives a DL instance, runs that adversary as a subroutine and outputs the unknown logarithm. The implication is: an efficient successful forger would give an efficient successful DL solver. We do not assume a DL solver and use it to forge; that reverse implication is usually easy and proves no useful security guarantee.

Write a concrete inequality. If $T$ is the adversary's time and $\epsilon$ its success probability, the reduction might run in time about $2T$ and succeed with probability $\epsilon^2/Q$, or take expected time about $Q\cdot T/\epsilon$ until success. These are different ways to state a loss. Never quote the runtime from one theorem and the success probability from another as if they described the same algorithm.

A reduction's four interfaces: challenge input, public setup, adversary queries and final output. At every stage list known scalars, known group elements and unavailable values. From $A=g^a$ one may compute $A^r$ for known $r$; one may not compute $a\cdot r$ as a scalar. This distinction often makes an otherwise impossible simulation possible.

Why assumptions do not transfer automatically

A DL solver gives a CDH solver by recovering one exponent and exponentiating the other public point. A CDH solver gives a DDH distinguisher by computing the proposed product and comparing it to the fourth input. The converses do not follow. In a symmetric pairing group, $e(g^a,g^b)=e(g,T)$ tests whether $T=g^{a\cdot b}$, so DDH is easy even if computing that source-group point is still hard.

In Type-3 settings the pairing takes one point from each of two distinct source groups. A DDH test requiring an unavailable second-group representative cannot simply be carried out. State the supplied tuples and maps rather than using the word “pairing” as a substitute for an assumption.

Exact distribution or a small statistical difference?

Sampling a scalar from $\mathbb Z_q$ and sampling from $\mathbb Z_q^*$ differ by probability $1/q$. That may be negligible, but it is not zero. Across $t$ samples, a union bound gives at most $t/q$ for encountering a zero in the full-field experiment. The historical slides sometimes use nonzero sampling where their simulator argument assumes the full field. Here nonce and challenge sampling is explicitly full-field unless rejection is part of a stated algorithm. Nonzero keys and inversion denominators remain separate requirements.

03 / System Security IIThree-move protocols: simulation and extraction

For a relation $R$, a statement $y$ and witness $w$ satisfy $(y,w)\in R$. In Schnorr's case $y=A$ and $w=a$, with $A=g^a$. A three-move public-coin protocol exchanges a commitment, a challenge and a response. Here “Sigma protocol” refers to this proof structure; it is unrelated to the name SIGMA for authenticated key exchange.

Three properties play different roles:

1. Completeness: an honest prover with a valid witness is accepted.
2. Special soundness: two accepting transcripts with the same first message and different challenges allow witness extraction.
3. Special honest-verifier zero knowledge: for a specified challenge, a simulator produces the corresponding accepting-transcript distribution without the witness.

For Schnorr, the verifier checks $g^s=X\cdot A^c$. To simulate an honest transcript, sample $c,s\leftarrow_{\$}\mathbb Z_q$ and set $X=g^s\cdot A^{-c}$. In an honest execution, $s=x+a\cdot c$. For fixed $a,c$, adding $a\cdot c$ is a bijection on the field, so uniform $x$ gives uniform $s$. The simulated and honest transcript distributions are identical under this sampling convention.

For extraction, divide two verification equations:

The inverse exists because $q$ is prime and $c\ne c'$. Verify the extracted witness by checking $g^a=A$. This last check is useful both in a reduction and in an implementation test.

Scope. Honest-verifier zero knowledge does not by itself prove zero knowledge against arbitrary malicious verifiers, concurrent security, or a general deniability claim. A verifier may select its challenge as a function of the commitment. A simulator that chooses the challenge first has not yet simulated that interaction.

A full distribution calculation

Fix a public key $A=g^a$ and a challenge $c$. An honest nonce $x$ has probability $1/q$ and determines exactly one pair $(X,s)=(g^x,x+a\cdot c)$. A simulator samples $s$ with probability $1/q$ and computes $X=g^s\cdot A^{-c}$. These describe the same set of pairs with the same probabilities. With a uniformly sampled challenge, each accepting transcript has probability $1/q^2$.

The simulator does not calculate $x=s-a\cdot c$. That equation is used only in the mathematical argument comparing distributions. Its executable computation uses $s,c,A$. In proofs, distinguish expressions that define a distribution from values that the simulator actually knows.

The two accepting equations are enough

The extractor does not need an honest explanation of the adversary's response. It starts with the public checks $g^s=X\cdot A^c$ and $g^{s'}=X\cdot A^{c'}$. Division cancels $X$. Because $g$ has prime order and $c-c'\ne0$, the extracted scalar is the unique witness for $A$. We need not assume the adversary internally computed $s=x+a\cdot c$ or knew any nonce. This is why extraction applies to arbitrary accepting algorithms, not only to an honest prover reused as a test fixture.

Worked example. In the order-$23$ subgroup modulo $47$, use $(X,c,s)=(42,3,7)$ and $(X,c',s')=(42,11,17)$. Then $s-s'=13$, $c-c'=15$ and $15^{-1}=20\pmod{23}$. Extraction gives $13\cdot20=7\pmod{23}$, whose public image is $2^7=34\pmod{47}$.

04 / System Security IIPassive identification and rewinding

Suppose an impersonator receives honest training transcripts for $A$ and then talks to an honest verifier. A DL reduction sets the target public key to its input $A$, simulates the training transcripts as above, and runs the impersonation phase. After the adversary sends $X$, the reduction saves its state, including its random tape and the transcript prefix.

It sends a challenge $c$, obtains an accepting response, and restores the saved state. It now sends a fresh challenge $c'$. If the second run also accepts and $c'\ne c$, special soundness extracts the DL. Rewinding means restoring the same computation, not launching an independent adversary with new coins.

Why success needs a probability argument

Fix a saved state $v$ and its random tape. Let $p_v$ be the fraction of challenges that lead to acceptance. Two independent challenges both succeed with probability $p_v^2$. The event that they coincide and succeed has probability $p_v/q$. Averaging over states and writing $\epsilon=\mathbb E[p_v]$ gives

This follows from $\mathbb E[p_v^2]\ge\mathbb E[p_v]^2$. A negative lower bound is replaced by zero. The argument assumes a bounded execution with replayable state and exact simulation. A prover that guesses one challenge in advance can have acceptance probability $1/q$ without giving an extractable pair. That is the knowledge-error scale, not a contradiction.

Proof exercise. Write the passive-identification reduction as pseudocode. Explain why training transcripts can be simulated and why the same simulator does not automatically answer an active verifier whose challenge depends on $X$.

An executable reduction outline

Input: group parameters and a target public key A; do not compute log_g(A).
Training: answer each passive transcript request with the exact simulator.
Impersonation: run the adversary until its first message X is fixed.
Save: random tape, complete machine state, and transcript prefix.
Branch 1: sample c; run to the answer; record s and the acceptance result.
Restore the saved state.
Branch 2: sample an independent c'; record s' and the acceptance result.
If either branch rejects or c = c', return failure.
Otherwise extract the scalar, check its public image, and return it.

This is a black-box proof experiment. It does not assert that an attacker can rewind a remote physical user. In a practical protocol, however, a device reset that reuses a nonce can accidentally give an attacker the same pair of transcripts. The mathematics is the same; the authority to obtain the pair is different.

Why the square cannot be skipped

For a fixed state $v$, let $S_v$ be its accepting challenge set, of size $t_v$. Exactly $t_v\cdot(t_v-1)$ ordered pairs of distinct challenges accept, out of $q^2$ ordered pairs. Thus the conditional probability is $(t_v/q)^2-t_v/q^2=p_v^2-p_v/q$. Averaging first, then using nonnegative variance, gives the bound in the preceding section. Assuming every successful first branch has a successful second branch would replace a conditional probability by one without justification.

For instance, a prover may answer only one challenge per commitment. Its success is $1/q$, but there are zero distinct accepting pairs. At the other extreme, a prover that answers all challenges gives a useful pair with probability $1-1/q$. Both boundary cases agree with the formula.

An active training verifier can choose $c$ after inspecting $X$. The passive simulator cannot simply choose that $c$ in advance. The next construction addresses this by embedding the hard problem somewhere else, so the reduction can know an actual prover witness.

05 / System Security IIOkamoto identification and active training

Okamoto's representation-based protocol uses generators $g_1,g_2$ of the same prime-order group. Sample the secret pair $(a_1,a_2)$ uniformly from $\mathbb Z_q^2$ and set $A=g_1^{a_1}\cdot g_2^{a_2}$, resampling if $A$ is the identity. Individual coordinates may be zero. Choose fresh uniform $x_1,x_2\in\mathbb Z_q$, send $X=g_1^{x_1}\cdot g_2^{x_2}$, and return

Verification checks $g_1^{s_1}\cdot g_2^{s_2}=X\cdot A^c$. Substitution proves completeness. The witness is now a representation of $A$, and a public key has $q$ such representations. Knowing one does not give the discrete logarithm between $g_1$ and $g_2$.

Where the DL challenge is embedded

Given $g_1$ and $g_2=g_1^\alpha$ with unknown $\alpha$, the reduction samples its own $(a_1,a_2)$ and publishes $A$. It knows a valid witness, so it can run honest prover instances even when the training verifier chooses challenges actively. The unknown challenge is in the relation between the two generators, not in the user's secret representation.

After two accepting impersonation transcripts with the same $X$ and distinct challenges, define $\Delta c=c-c'$, $\Delta s_1=s_1-s'_1$ and $\Delta s_2=s_2-s'_2$. The extracted representation is $\bar a_i=\Delta s_i\cdot(\Delta c)^{-1}$ for $i\in\{1,2\}$. Combining it with the reduction's original representation yields

If the two representations differ, the denominator cannot be zero: equal second coordinates would force equal first coordinates as well. But the extractor may return the original representation, in which case this computation fails.

Why a different representation is plausible

Conditioned on $A$, the reduction's representation is uniform among its $q$ possible representations. With full-field fresh nonces, prover transcripts do not reveal which representation was chosen: conditioned on the commitment and challenge, response pairs are uniform among the pairs satisfying the verification equation. Thus an extracted representation determined from that view hits the particular hidden representation with probability $1/q$. This is the witness-hiding step that must accompany the algebra, along with the probability of obtaining a fork.

This explanation addresses the sequential active-training setting followed by impersonation, not an unrestricted concurrent relay model. See Okamoto, Provably Secure and Practical Identification Schemes and Corresponding Signature Schemes. The local modified-Okamoto demo is a different, pairing-based construction: its responses are group elements, whereas the classical protocol above returns scalars. Its leakage analysis needs its own model.

Witness independence against an active training verifier

Write $g_2=g_1^\alpha$. For a fixed public key $A$, the valid representations satisfy $a_1+\alpha\cdot a_2=\log_{g_1}A$. There are exactly $q$ pairs: choose $a_2$ freely and the first coordinate is determined. The prover does not need to know $\alpha$ to use its own pair.

Fix the verifier's random tape and the transcript so far. For the next commitment $X$, the nonce pairs satisfying $g_1^{x_1}\cdot g_2^{x_2}=X$ form a set of size $q$ and are uniform on that set. The verifier's challenge is now fixed as a function of its view and $X$. Translation by $(a_1\cdot c,a_2\cdot c)$ maps those nonce pairs bijectively onto the $q$ response pairs satisfying $g_1^{s_1}\cdot g_2^{s_2}=X\cdot A^c$.

That latter set does not depend on which secret representation the prover used. Inductively, any number of sequential training sessions with fresh full-field coins has a view independent of that representation, conditioned on the public key. The extractor's output, as a function of this view and its own coins, cannot guess the reduction's particular representation with probability greater than $1/q$. This is stronger and more precise than saying that the secret is “probably different”.

Finish the reduction, including failure

The impersonation fork extracts $(\bar a_1,\bar a_2)$. Subtracting the two representation equations gives

If $a_2=\bar a_2$, the equality forces $a_1=\bar a_1$. Otherwise inversion gives $\alpha$. In this sequential, exact-simulation experiment the fork event and extracted witness depend on the public view, not on the hidden choice among representations. A lower bound on useful extraction is therefore $(1-1/q)\cdot\max\{0,\epsilon^2-\epsilon/q\}$. State this sampling/model convention before using the bound.

Exercise. Deliberately replace the full-field nonce pair by a biased distribution. Identify which sentence of the view-independence proof now fails. Completeness still holds, but the distribution proof needs to be redone. Then show why revealing both nonces from one accepting response defeats the ordinary scalar-response version when the challenge is nonzero.

06 / System Security IIFiat–Shamir and the random-oracle table

Use the teaching Schnorr signature $\sigma=(X,s)$ with $c=\H(\mathtt{sig}\|A\|X\|m)$ and $s=x+a\cdot c$. EUF-CMA allows chosen-message signatures and requires a forgery on a fresh message. The reduction is given $A=g^a$ without $a$.

A random oracle is sampled lazily. Its table maps each exact encoded input to one output. A repeated query returns the stored output. It is not resampled. To simulate signing $m$, the reduction chooses $c,s$ uniformly, computes $X=g^s\cdot A^{-c}$, and installs the value $c$ at the corresponding hash input. If that input already has an incompatible answer, the simulator must abort or use a justified retry rule. It may not overwrite the old answer.

If the adversary never queried the challenge of its eventual fresh-message forgery, then, for a nonidentity public key, the accepting challenge for fixed $(X,s)$ is unique. A uniformly sampled unseen answer matches it with probability $1/q$. Otherwise the reduction can identify a critical oracle query associated with the forgery. The next chapter describes how that index is used.

Let $Q_H$ and $Q_S$ bound hash and signing queries. A simple programming-collision estimate scales like $Q_S\cdot(Q_H+Q_S)/q$: each signing simulation chooses a uniform commitment, and only previously occupied inputs for that context can collide. State the counting convention before quoting a concrete bound; internal signing queries also populate the table.

The oracle table is shared state

Hash(input):
    if input is in Table: return Table[input]
    sample a uniform scalar c
    store Table[input] = c
    return c

SimulatedSign(m):
    sample independent uniform c and s
    compute X = g^s / A^c
    encode input = (signature domain, A, X, m)
    if input is already in Table: abort this simulation
    store Table[input] = c
    return (X, s)

The simulator above uses the conservative rule of aborting at any occupied input, even one with a coincidentally compatible value. For signing query number $j$, at most $Q_H+j-1$ entries have already been installed, and $X$ is uniform. A union bound gives

This overcounts entries for other messages and contexts, which is safe for an upper bound. The bound assumes uniform full-field simulator coins and a fixed upper bound on the query counts. Rejecting an identity commitment or using a different signing distribution changes the exact accounting. Repeating the same hash query must never create a fresh entry.

If the real forgery probability is $\epsilon_{\rm real}$, the simulated success after programming aborts is at least $\epsilon_{\rm real}-\delta_{\rm prog}$. Requiring the forger to have asked its final challenge costs at most another $1/q$. Define

This is a lower bound on a specific algorithm's success, not a renamed real-world advantage. To apply a forking theorem, include internal oracle use in its execution model, restore all relevant state, and count the random answers that the chosen theorem actually indexes.

07 / System Security IIForking lemma: what is replayed, what is changed

The Pointcheval–Stern technique turns a successful Fiat–Shamir forgery into two compatible transcripts. A useful abstraction is the general forking experiment of Bellare and Neven. Let an algorithm consume at most $Q$ random answers from a space of size $h$. On success it outputs a relevant query index $I\in\{1,\ldots,Q\}$ and auxiliary output; index zero denotes failure. Let its success probability be $\epsilon$.

Run it once. Restore the same input and random tape, replay answers before index $I$, and resample answer $I$ and the suffix. The fork succeeds only if the second run selects the same index and the answers at that index differ.

The lower bound is

For Schnorr the two runs then have the same encoded commitment and message but different challenges, so the extraction equation applies. Here $\epsilon$ is the success probability of the actual simulated algorithm after its aborts, not automatically the raw EUF-CMA advantage. See Bellare and Neven, Lemma 1 and Pointcheval and Stern's security arguments.

Audit a proposed application

• The reset preserves the adversary's coins and all earlier oracle answers.
• The forked query really determines the forgery's challenge.
• The two signatures refer to the same statement, public key and commitment.
• Repeated queries remain consistent within each run.
• Signing simulation still works on both branches.
• Query guessing, malformed outputs and programming failures are included in the loss.

Forking is not a promise that a second run will forge. A different critical index, rejection or identical challenge is a failed attempt. Nor does this classical reset argument automatically apply to quantum random-oracle access. It relies on the particular query interface and rewinding model.

Exercise. Set $Q=1000$, $h=2^{128}$ and $\epsilon=0.1$. Evaluate the lemma's lower bound and compare it with the false claim that the fork succeeds with probability $0.1$. Explain why a valid but loose reduction may still require larger parameters than a tight one.

A probability proof of the general bound

For each possible selected index $i$, fix the random tape and the oracle answers before $i$. Call that prefix $v$. Let $p_i(v)$ be the probability, over the remaining independent answers, that the algorithm succeeds and selects $i$. Two independently completed branches from this prefix both select $i$ with probability $p_i(v)^2$.

Summing over indices and averaging over prefixes, the probability of two successful runs with the same selected index is

The first inequality is nonnegative variance. The second is Cauchy–Schwarz: the sum of the $Q$ means is $\epsilon$. We must remove the event that the second answer at the selected query repeats the first. After a successful first run that event has probability $1/h$, giving an upper bound $\epsilon/h$ on the discarded probability. Subtraction gives $\epsilon^2/Q-\epsilon/h$.

This derivation explains the three visible terms: two successful branches cause the square, selecting the same one of $Q$ possible indices causes the query loss, and distinct challenges cause the subtraction. It does not add a second independent factor $1/Q$ for “guessing” the index; that would count a loss already present in this experiment.

From a fork to Schnorr's secret

For the Schnorr teaching profile, the selected query encodes $A,X,m$ before its answer is supplied. If both executions select that query index, the shared prefix fixes its input. The two accepting signatures therefore have the same public key, commitment and message. Their differing hash answers are precisely the differing challenges required by special soundness.

The reduction must restore the simulated environment as well as the forger. A hash entry created after the fork cannot remain copied from the first branch if the second branch is meant to resample it. Signing-oracle replies and their table updates must follow the same documented rules on both branches. This is where a mathematically correct extractor can be attached to an incorrect implementation of the proof experiment.

08 / System Security IIPointcheval–Stern: where the constants come from

The historical forking analysis of David Pointcheval and Jacques Stern has more visible constants than the compact general lemma. It constructs a replay strategy with a success threshold and then an expected-time strategy that does not need the adversary's success probability as an input. These are different algorithms. A large constant in the latter is not the cost of one modular inversion.

Let $Q$ be the hash-query bound, let the challenge space have size $h=2^k$, and write $\epsilon$ for the no-message forger's success. Under the generic-signature conditions and $\epsilon\ge7Q/h$, their Lemma 2 gives a constant-success fork using at most $16Q/\epsilon$ executions, with success at least $1/9$. Their Theorem 1 gives expected time at most $84480\cdot Q\cdot T/\epsilon$. See the original paper, Section 3.1.

Reconstruct the accounting

Let $S$ be successful executions that queried their eventual challenge, and $\nu=\Pr[S]$. Losing an unqueried challenge costs at most $1/h$, so the threshold implies $\nu\ge6\epsilon/7$. Split $S$ into buckets by the index of that query. There are at most $Q$ buckets.

Call a bucket heavy if its conditional mass within $S$ is at least $1/(2Q)$. All light buckets together have mass at most $1/2$. Within a heavy bucket, a splitting argument retains at least half its successful executions with a sufficiently good replay prefix. Thus a successful execution has a suitable bucket and prefix with probability at least $1/4$. The fractions are deliberately conservative lower bounds, not special properties of Schnorr arithmetic.

The total trial budget is bounded by $(2+14Q)/\epsilon\le16Q/\epsilon$. Round repetition counts to integers in an implementation; the paper's bounds use the usual harmless rounding convention. The assumption $\epsilon\ge7Q/h$ makes the subtraction of the repeated-challenge probability small enough. Without that threshold, this particular constant-success estimate does not follow.

The expected-time multiplier

In the expected-time schedule, the replay budget grows geometrically. Using the paper's schedule parameters $\alpha=8/7$ and tail bound $\gamma=6/7$, one has $\alpha\cdot\gamma=48/49<1$, so the expected sum converges. The final bound reduces to the numerical expression

Here $7=1/(\alpha-1)$ and $49=1/(1-\alpha\cdot\gamma)$ are geometric-sum factors. The factor $64/7$ bounds the schedule's overshoot relative to $Q$. The factor $165$ is a rounded upper bound after replacing $1/\nu$ by $7/(6\epsilon)$ in the per-stage cost $141/\nu$. The $141$ counts the initial run and a replay budget multiplied by $140$. This explains the origin of the number without suggesting it is an optimal universal loss.

For chosen-message simulation, the paper's collision estimate retains at least $7\epsilon/10$ under its stated threshold $\epsilon\ge10(R+1)(R+Q)/h$, where $R$ bounds signing queries. Substitution explains

Use the runtime convention of that theorem, including the simulated signing work. Do not combine its threshold with a different simulator's collision estimate. In the next ring-signature analysis, the same bookkeeping idea uses a much larger number of query-index patterns.

Checkpoint. A large upper bound is not an attack. A negative lower bound on extraction means that the estimate is uninformative, not that the scheme is insecure. The right security parameters depend on the best applicable analysis, not on treating every historical proof constant as a measured implementation cost.

09 / System Security IIPairings and leakage-oriented responses

A Type-3 pairing has type $e:G_1\times G_2\to G_T$, where all three groups have order $q$. With additive source groups and generators $P\in G_1$, $Q\in G_2$,

The map is efficiently computable and nondegenerate. Do not interchange its arguments or pass two $G_1$ points to it. A historical symmetric pairing uses one source group in both positions; its algebra is not a literal API specification for a Type-3 library.

A modified Schnorr response from the original lectures

In the symmetric multiplicative setting of the lecture derivation, replace the scalar response by a group element. Let $h=\H_G(X,c)\in G$ and return $S=h^{x+a\cdot c}$. Verification is

The scalar $s=x+a\cdot c$ is not sent. Therefore the ordinary division attack on a leaked nonce no longer immediately applies to the wire response. This observation alone is not a proof of security in every leakage or randomness-injection model.

If a simulator programs $\H_G(X,c)=g^r$, it can answer with $S=(X\cdot A^c)^r$ without knowing $a$. For the extraction branch, suppose a CDH challenge contains $B=g^b$ and the simulator has obtained two compatible accepting responses using programmed points $h=B^d$ and $h'=B^{d'}$, with nonzero known $d,d'$ and distinct $c,c'$. Then

The nonce term cancels. The remaining proof must explain how these two hash points are distributed, how the target queries are selected, which oracle queries are answered, and how often the required accepting pair is obtained. That is the difference between the extraction identity and a complete CDH or gap-CDH reduction. The identification demo and research prototype have their own explicit implementation profiles; check their group types instead of silently translating this symmetric sketch.

Read the extraction in three typed steps

Set $A=g^a$ and $B=g^b$ from the challenge. With $h=B^d$, a valid response has the uniquely determined group value $S=B^{d\cdot(x+a\cdot c)}$. Nondegeneracy in the prime-order symmetric setting makes the pairing verification injective in the response point. Raise $S$ to $d^{-1}$ to remove the known randomiser. Do the same for the other branch. Divide the resulting group elements to cancel $x$, and raise the quotient to $(c-c')^{-1}$ to obtain $B^a$.

At no point does the reduction recover $a$, $b$ or $x$ as a scalar. All inversions are of known nonzero field elements. This explains why the result is a CDH solution rather than a DL solution. A DDH oracle, if required to recognise target tuples in the full simulation, changes the claimed assumption to gap CDH.

The lecture's noninteractive variant

The signature variant uses two distinct hash functions on a context containing the message and commitment: a scalar $c=\H(X,m)$ and a group point $h=\H_G(X,m)$. It returns $(X,S)$ with $S=h^{x+a\cdot c}$. The same pairing equation verifies it. This paragraph retains the lecture's symmetric algebra; a concrete protocol must specify its domain-separated encodings and any public-key binding.

For an ordinary group-hash entry, the simulator chooses secret-to-the-adversary $r$ and returns $h=g^r$. It answers even a chosen-nonce signing request by $S=(X\cdot A^c)^r$. At a target group-hash entry it instead uses $h=B^d$. To extract, it keeps this point fixed and forks the scalar hash, giving

Unlike the preceding interactive extraction, both branches now use the same $d$. A complete proof must arrange a suitable order of the two hash queries, handle a signing request at the target entry, and bound target selection and forking failure. If the adversary asks the scalar hash before the group hash, the simulator cannot silently assume the reverse order. The slides' group-hash embedding and this extraction identity are instructional components, not a replacement for those missing scheduling arguments.

Critical implementation distinction. The reduction knows $r$ because it sampled the random oracle internally. The adversary does not. Replacing the real group hash by $\mathcal{H}_{\mathrm{bad}}(X,m)=g^{\operatorname{enc}(X,m)}$ for a publicly computable scalar would let anyone compute $S=(X\cdot A^c)^{\operatorname{enc}(X,m)}$. This would forge responses directly. A proof's trapdoor representation must not become a public representation in the implementation.

10 / System Security IICompromised randomness: the same cancellation, different interfaces

The preceding derivation explains why leakage, setting and injection belong to one research line. They concern loss of control over ephemeral randomness. A reset can also supply a repeated ephemeral. It need not disclose that ephemeral or set it to a known value. The attack chapter in System Security I gives the scalar examples.

What the reduction must simulate

Suppose a training oracle accepts an adversarial nonce $x$ before computing the protocol response. It can model honest nonce generation followed by disclosure by sampling $x$ with the prescribed distribution and then returning it with the transcript. This comparison requires identical phases, permitted values and disclosure timing. It does not identify every leakage oracle with every setting oracle. Choosing public messages is a separate permission.

For ordinary Schnorr, a leaked or chosen nonce and one nonzero challenge expose $a=(s-x)\cdot c^{-1}$. Repetition permits two responses with the same $x$; subtracting eliminates $x$ even if it is unknown. An abstract form, with known coefficients $u_i,v_i$, is

Eliminate $x$ by multiplying and subtracting. Define $D=u_1\cdot v_2-u_2\cdot v_1$. If $D\ne0$ in the prime field, then

This is a rank condition, not a consequence of merely having two transcripts. For Schnorr, $u_1=u_2=1$ and $v_i=c_i$, so distinct challenges give the needed rank. More unknown witnesses, as in a representation proof, require an appropriate extraction argument rather than silently reusing the one-key formula.

Cancellation after lifting into the exponent

Continue in the symmetric group setting of the preceding chapter. After removing the known nonzero hash masks $d,d'$, let the two accepting responses become

Then $T_1\cdot T_2^{-1}=B^{a\cdot(c-c')}$ and raising to $(c-c')^{-1}$ gives $B^a$, not $a$. If the nonce is known, one response similarly gives $(T_1\cdot B^{-x})^{c^{-1}}=B^a$ for $c\ne0$. With $B=g^b$, the result is a CDH-type target. Pairings validate group responses; they do not turn group elements back into readable exponents.

In an ordinary simulated hash entry $h=g^r$, the reduction answers a chosen-nonce query as $S=(X\cdot A^c)^r$. It knows $r$, but not $a$. At a target entry containing the hard instance, this method may no longer answer every query. The proof must handle that case, preserve oracle consistency and bound aborts. The published Salin dissertation, Sections 3.4.3–3.4.4 develops this simulation and cancellation pattern. Its symmetric and asymmetric challenge tuples must not be conflated.

Three checks before claiming security

1. Interface: who chooses or learns which value, and at what phase? What does reset restore? An ephemeral seed, a derived scalar and a public commitment are not interchangeable.
2. Algebra: are the responses scalars or group elements? What cancels, which denominator must be nonzero, and what type does extraction return?
3. Probability: why can the simulator obtain the required accepting pair without forbidden access? Include target selection, oracle programming and failed forks. Physical reset and proof rewinding can share an identity without sharing an execution model.

This is the sense in which the publication catalogue uses one label, randomness leakage and setup. The label groups a methodology and threat family. A security guarantee remains the theorem for the individual construction and its stated model.

11 / System Security IIBLS and a straight-line extraction idea

BLS illustrates a different signature shape. In additive source notation take $P\in G_1$, $Q\in G_2$, secret $a$, verification key $A_2=a\cdot Q$, and a proper $\H_{G_1}:\{0,1\}^*\to G_1$. A signature is one point $\sigma=a\cdot\H_{G_1}(m)$. Verify

The signature point is in $G_1$, not $G_T$. Validation must include the specified encoding, subgroup and nonidentity conditions. Hashing to a known scalar times $P$ is not a substitute for the required hash-to-curve construction: that shortcut changes the problem exposed by signatures.

For a proof sketch with matched public multiples, explicitly assume the following co-CDH-style problem is hard: given $(P,Q,a\cdot P,a\cdot Q,D)$ with random $D\in G_1$, compute $a\cdot D$. The reduction can answer ordinary hash queries with $r\cdot P$ and sign them with $r\cdot(a\cdot P)$. At a guessed fresh-message target query it programs $D$. An accepting forgery there is already $a\cdot D$, so no Schnorr-style witness extraction is needed. Guessing and signing-query aborts still create a reduction loss.

This deliberately states the challenge tuple rather than calling every pairing assumption “CDH”. Other BLS group settings and theorem formulations must be matched to their own assumptions. The scheme originates in Boneh, Lynn and Shacham; the PBC example illustrates the pairing equation. Basic verification alone does not make naive aggregation safe against rogue public keys.

Additive and multiplicative notation describe the same source-group operation

On an elliptic curve, write $\sigma=a\cdot\H_{G_1}(m)$ and $A_2=a\cdot Q$. The lecture-board shorthand writes $\sigma=\H_{G_1}(m)^a$ and $A_2=g_2^a$. The latter does not mean exponentiating the coordinates of a point. It means repeated application of the source-group law, which the library calls scalar multiplication. The target group of the pairing remains naturally multiplicative in both notations.

Matched public keys in both source groups

For the extended profile used in the exercises, publish $A_1=a\cdot P$ as well as $A_2=a\cdot Q$, using one secret scalar. Their consistency is checked by

Indeed, if $A_1=a_1\cdot P$ and $A_2=a_2\cdot Q$, equality implies $e(P,Q)^{a_1-a_2}=1$. Nondegeneracy and prime order imply $a_1=a_2\pmod q$. Validate membership and exclude the all-zero key as required. The check proves equality of the represented exponents, not that the submitter knows that exponent.

Ordinary BLS verification in this orientation needs $A_2$ only. Publishing both keys is an explicit profile choice and is useful for the concrete reduction tuple above. It is not a universal requirement that every BLS user possess two independent secret keys. The BLS exercises and WebAssembly demonstration show this distinction operationally.

Why public scalar encoding is a deliberately broken exercise

Replace the proper $\H_{G_1}$ by the deliberately defective function $\mathcal{H}_{\mathrm{bad}}(m)=\mu(m)\cdot P$ with publicly known $\mu(m)$. In the extended profile anyone computes $\sigma=\mu(m)\cdot A_1$, without a signing query. Even with only $A_2$ public, one signature at a nonzero $\mu(m_0)$ gives $a\cdot P=\mu(m_0)^{-1}\cdot\sigma_0$, enabling all further signatures. Correct BLS requires a specified hash-to-curve map whose output does not reveal such a scalar relation to the generator.

This does not mean the hashed point is an independent generator selected from nowhere: in a prime-order group any nonidentity point generates the group, but its discrete logarithm relative to $P$ is not publicly provided. Use an appropriate hash-to-curve suite and domain separation, not a programmer's ad hoc encoding. RFC 9380 defines that interface.

Complete the simple target-query argument

Fix an upper bound $Q$ on distinct hash-table entries, including entries created by signing and final verification. Choose $J$ uniformly from $\{1,\ldots,Q\}$ before running the adversary. At position $J$, answer with the random challenge point $D$; at all other positions answer with $r\cdot P$ and retain $r$. Each answer has the same uniform distribution in the idealised group-hash model, so the target position is hidden by the answers.

Condition on $J$ being the final fresh-message forgery's position. That message was not signed, so the target signing abort never occurred. If the forgery verifies, injectivity of the pairing in $G_1$ gives $\sigma=a\cdot D$. This elementary reduction has success $\epsilon/Q$ under these idealised distributions and query conventions. Extra rejection rules or a concrete hash-to-curve instantiation must be accounted for separately. This is a transparent baseline argument, not a claim to reproduce every tighter BLS theorem.

12 / System Security IIRSA-FDH and Goh–Jarecki: compare extraction paths

RSA full-domain hash

Let $N=p\cdot r$ be an RSA modulus for distinct primes $p,r$, let $e$ be invertible modulo $\varphi(N)$, and let $d=e^{-1}\bmod\varphi(N)$. Here $e$ is an RSA exponent, not the pairing map of the preceding chapters. The distinct name $F_{\rm FDH}$ denotes the full-domain hash into the RSA group, not a scalar hash into $\mathbb Z_q$. With $F_{\rm FDH}:\{0,1\}^*\to\mathbb Z_N^*$, sign as $\sigma=F_{\rm FDH}(m)^d\bmod N$ and check $\sigma^e=F_{\rm FDH}(m)\bmod N$.

Given an RSA inversion challenge $Y$, a reduction chooses one fresh hash-table position as its target. At ordinary positions it samples $r_m\leftarrow_{\$}\mathbb Z_N^*$ and returns $r_m^e$, retaining $r_m$ as a simulated signature. This is uniform because exponentiation by $e$ is a permutation. At the target it returns $Y$ and cannot answer a signing request there. If a fresh-message forgery lands at that position, the forged signature is an RSA root of $Y$.

Count distinct table entries, including those created internally by signing and final verification. Choosing among a known upper bound of positions gives an inverse-polynomial target probability. Conditioned on targeting the final fresh message, it was not previously signed, so the target signing abort does not occur. This is a query-guessing reduction, not a use of the Schnorr forking equation. Full-domain hashing means the RSA group domain, not a short digest interpreted without the specified encoding.

Goh–Jarecki's equality-of-discrete-logs approach

In this chapter return to $G=\langle g\rangle$, $A=g^a$. A message salt $r$ determines $h=\H_G(m,r)$, and the signature contains $Z=h^a$ together with a Fiat–Shamir proof that $(g,A)$ and $(h,Z)$ use the same exponent. Choose $x$, compute $U=g^x$, $V=h^x$, then

The verifier reconstructs $U=g^s\cdot A^{-c}$ and $V=h^s\cdot Z^{-c}$ and recomputes $c$. The original EDL signature encodes $(Z,r,s,c)$. The salt is separate from the proof nonce. Use parameters from a selected security analysis, not a historical bit length copied without review.

The structural point is that a forgery already contains $h^a$. If a target hash is embedded as $h=B\cdot g^t$, the corresponding valid $Z$ gives $Z\cdot A^{-t}=B^a$. A complete reduction must justify simulation of signatures and proofs, validity of the relation, hash programming and its success bound. The original Goh–Jarecki paper supplies that analysis; the displayed division is its teaching-level extraction idea, not the whole tightness proof.

RSA's target row must be chosen before its future is known

A slide may say “choose one of the hash-table rows”. At the start, the future number and contents of those rows are unknown. Use a known upper bound $Q$, choose a target index beforehand and create rows lazily. If fewer than $Q$ rows are used, the unused choices simply count as failed target guesses. Choosing the row after seeing the forgery would not describe the same online simulation.

Sample ordinary roots from $\mathbb Z_N^*$, not from an undeclared set of integers. The map $r_m\mapsto r_m^e\bmod N$ is a permutation of this group, giving the exact uniform distribution used by the proof. Store the root and hash value together, so a hash query before a signing request and a signing request before a hash query remain consistent. A signing request at the challenge row aborts; filling it with a dummy root that fails verification would reveal the simulation.

The equality-of-discrete-logs proof behind EDL

An interactive version sends $(U,V)=(g^x,h^x)$, receives a random challenge $c$ and returns $s=x+a\cdot c$. It proves that one exponent relates both $A$ to $g$ and $Z$ to $h$. Verification checks two equations:

To simulate a transcript for a prescribed challenge, sample $s$ and set $U=g^s\cdot A^{-c}$ and $V=h^s\cdot Z^{-c}$. If the equality statement is true, this has the honest distribution by the same translation argument as Schnorr. From two accepting transcripts with the same $(U,V)$ and distinct challenges, extraction gives a scalar $a$ satisfying both public relations. The second check is essential: a proof only of $A=g^a$ would not certify that the supplied $Z$ equals $h^a$.

The noninteractive proof hashes the complete equality statement and commitments. Its simulator programs that challenge only at an unoccupied input. The tight EDL signature analysis additionally uses the random message salt to arrange appropriate hash embeddings while answering signing queries. It is not the naive assertion that every hash query can be set to a CDH challenge and still be signed. Keep the proof of equality, the signing simulation and the final group-element extraction as three separate steps.

Comparison exercise. For Schnorr, RSA-FDH, BLS and EDL, write a two-column table: what the forgery contains, and what the hard-problem solver needs. Identify precisely where rewinding is needed and where an accepting output can already contain the hard value. Do not infer tightness from the absence of a final rewind alone.

13 / System Security IIGame hopping: ElGamal and hashed ElGamal

Let $E_i$ be the event that an adversary outputs 1 in game $i$. The triangle inequality gives

Each hop needs a reason: exact equality of distributions, a statistical bound, or a computational reduction. If two coupled games are identical until a bad event, their output probabilities differ by at most the probability of that event under the coupling. This is a proof tool, not permission to change unrelated distributions. Shoup's sequences-of-games tutorial develops this method.

ElGamal under DDH

In the real game the challenge ciphertext is $(g^r,m_b\cdot A^r)$ for a hidden bit $b$. Replace $A^r$ by an independent uniform $T\in G$. A DDH distinguisher embeds $(g,A,g^r,T)$, samples the challenge bit $b$ itself, and outputs one exactly when the adversary's guess $b'$ equals $b$. It must test this success event, not simply return the guessed bit. In the final game, multiplication by $m_b$ permutes $G$, so $m_b\cdot T$ is uniform regardless of $b$. This establishes the CPA argument with the appropriate advantage convention.

Hashed ElGamal and the decisive oracle query

For bit strings of length $\ell$, set $C=(g^r,m\oplus\mathcal D_\ell(A^r))$ with $\mathcal D_\ell:G\to\{0,1\}^{\ell}$. Until the adversary queries the exact DH point, its mask is an independent random string. Thus distinguishing the message requires either querying that point or falling within the accounted simulation error.

A CDH reduction need not be able to recognise the correct query. It can record group queries and output one selected at random. If a decisive query occurs among at most $Q_H$ queries, selection incurs a factor $1/Q_H$. A DDH oracle would allow recognition and changes the assumption to a gap setting. Do not silently grant it to a plain CDH reduction.

Neither argument proves CCA2 security. The related-ciphertext attack on ordinary ElGamal and the malleability of an unauthenticated XOR payload remain relevant. The first course states the corresponding attack interfaces.

State the events, not only the game names

For ElGamal, give a DDH distinguisher the tuple $(g,A,U,T)$. It runs the encryption adversary with public key $A$, obtains two group messages $m_0,m_1$, samples $b$ and returns $(U,m_b\cdot T)$. It outputs one if the adversary guesses $b$. When $T=A^r$ and $U=g^r$, this is the real game. When $T$ is independent uniform, the success probability is exactly $1/2$ because multiplication by either message permutes the group.

Therefore the absolute difference of the distinguisher's output probabilities equals the encryption adversary's guessing bias. If a paper defines encryption advantage as twice that bias, a factor two appears when the same bound is expressed in that convention. It is a convention change, not an extra cryptographic attack.

No decryption oracle was answered by this distinguisher. Adding such an oracle would require decrypting under the unknown exponent of $A$, which the DDH input does not supply. This is why the preceding proof is an IND-CPA proof. It does not justify the CCA1 claim that appears next to the historical warm-up example.

The hash-smoothing route in the original lecture

The hashed-ElGamal slides use a different route from the random-oracle query argument. First replace the DH mask point by a uniform $T\in G$ using DDH. Next replace $\mathcal D_\ell(T)$ by a uniform $\ell$-bit string. This second hop requires a separate smoothing or extraction condition on the hash family: its output on a uniform group element must be sufficiently close to uniform, with the public hash description included in the comparison.

If that distance is at most $\delta_H$, then the two hops bound the guessing bias by the DDH distinguishing advantage plus $\delta_H$. Collision resistance by itself does not establish smoothing. For example, prefixing a digest by a fixed zero can preserve collision resistance while making its output trivially distinguishable from a fully uniform string of the longer length.

One precise information-theoretic formulation uses an independent public seed selecting a universal hash family, with an output short enough relative to the input's entropy. Another formulation treats the hash as a random oracle and accounts for queries to the hidden point. These are different assumptions and proof paths. The original slide's “hash smoothing” must not be silently replaced by a generic claim that any hash output is random.

A full decisive-query experiment

In the random-oracle route, replace the challenge pad by a uniform string. All hash answers are sampled consistently and independently. Until the adversary queries the exact DH point, this game can be coupled with the real challenge distribution. Let $\mathsf{AskDH}$ denote that query event. The difference of success probabilities is at most $\Pr[\mathsf{AskDH}]$ by the identical-until-bad argument.

A CDH solver given $(g,A,U)$ can generate the uniform-pad challenge without knowing the DH point. It records each group input to the hash oracle and returns a random one from a padded list of length $Q_H$. Whenever the decisive query occurred, selection succeeds with probability at least $1/Q_H$. The solver need not recognise which query was correct. The argument relates the event in the coupled uniform-pad experiment to the first decisive query; it does not require computing the missing real pad in the simulator.

Exercise. Explain why replacing the random selection by “return the correct hash query” assumes an extra recognition capability. Then repeat the reasoning for a simulator with an explicit DDH oracle and identify the changed hardness assumption.

14 / System Security IIAnonymous proofs and ring signatures

For a ring $L=(A_1,\ldots,A_n)$, an OR proof establishes knowledge of at least one secret $a_j$ with $A_j=g^{a_j}$ without revealing which one. Fix a canonical ordered ring and bind it to the challenge. Simulate branches $i\ne j$ by choosing $c_i,s_i$ and setting $X_i=g^{s_i}\cdot A_i^{-c_i}$. For the real branch choose $x_j$ and set $X_j=g^{x_j}$.

Define $c=\H(\mathtt{ring}\|L\|m\|X_1\|\cdots\|X_n)$, set $c_j=c-\sum_{i\ne j}c_i$, and return $s_j=x_j+a_j\cdot c_j$. Verification reconstructs every $X_i$ and checks

This is a pedagogical Fiat–Shamir OR composition of Schnorr protocols, not a claim that every ring paper uses this exact encoding. With two accepting forks on the same commitments and ring, a changed total challenge implies a changed branch challenge. For such a branch, $a_i=(s_i-s'_i)\cdot(c_i-c'_i)^{-1}$. A ring-unforgeability theorem must still ensure that this branch supplies a useful uncorrupted target, with the required key-registration and signing-query rules.

Anonymity is a separate claim about the distribution of signatures for different eligible signers. It does not follow from unforgeability. Nor does an algebraic fork identify the signer of an ordinary publicly observed signature; the extractor has access to a special replay experiment. Compare Herranz and Sáez's ring-forking analysis, the cloud-course treatment, and the hierarchical-signature research demo.

Why the constructions must not be mixed

The OR construction uses a sum of branch challenges tied to one hash of all commitments. The Herranz–Sáez construction below uses one separate hash per commitment and one aggregate response. Their verification equations, signature sizes and fork conditions are different. An extraction argument for one cannot be pasted into a proof of the other by renaming the signature.

Ring signatures also differ from multisignatures: one ring member signs, whereas a multisignature normally attests to participation of all specified co-signers. A group-signature system may have an opening authority. The ordinary ring signature below has no such authority. None of these terms means that a public transcript identifies which member actually ran the signing algorithm.

15 / System Security IIHerranz–Sáez: the actual ring construction

This chapter follows Javier Herranz and Germán Sáez, Forking Lemmas in the Ring Signatures' Scenario, especially Sections 4.2–4.4 of the published research report. We rename the paper's secret $x_i$ to $a_i$, its public key $y_i$ to $A_i$, and its scalar response to $z$, keeping the course's meanings consistent. The aggregate ring signature is denoted $\sigma$.

Fix a ring $L=(A_1,\ldots,A_n)$ of public keys $A_i=g^{a_i}$ in the same prime-order group. Keys are nonidentity, and the ring entries are distinct. The commitment restrictions require $1\le n\le q-1$, with realistic ring sizes much smaller than $q$. Fix a message $m$ and a hash $\H(m,R)\in\mathbb Z_q$. For this historical fixed-ring scheme the hash input is the pair $(m,R)$; it is not the OR construction's hash of an entire commitment vector.

Signing with member j's secret

1. For each $i\ne j$, sample distinct nonzero scalars $u_i$ uniformly without replacement, and compute $R_i=g^{u_i}$ and $c_i=\H(m,R_i)$.
2. Sample $u\leftarrow_{\$}\mathbb Z_q$ and compute the remaining commitment

3. If $R_j=1$ or it duplicates an existing $R_i$, repeat step 2. Keep the previously chosen commitments fixed.
4. Set $c_j=\H(m,R_j)$ and compute the scalar response

5. Output $\sigma=(R_1,\ldots,R_n,z)$. The challenge values are recoverable from the message and commitments; the paper also writes them explicitly in its generic signature tuple.

The special commitment is the adjustment that closes the verification equation. It uses other members' public keys, not their private keys. Only the final scalar computation uses the actual signer's secret. The position $j$ is not included as an output field.

Verification and correctness

Validate the parameters, ordered ring, message encoding, scalar response and group elements. Reject identity or duplicate commitments. Recompute every $c_i=\H(m,R_i)$ and accept if

Substitute the definition of $R_j$. For each $i\ne j$, the inverse public-key factor in $R_j$ cancels the matching factor in the verifier's product. What remains is

This proves correctness for every accepted signing attempt. It does not yet prove anonymity or prevent an outsider from creating a new valid tuple.

A two-member example with declared toy hash values

Use $p=47,q=23,g=2$, with $a_1=7,A_1=34$ and $a_2=5,A_2=32$. Let member 2 sign. Choose $u_1=3$, so $R_1=8$, and suppose the fixed toy hash table returns $\H(m,8)=4$. Choose $u=9$. Then $R_2=2^9\cdot34^{-4}=16\pmod{47}$, which is neither the identity nor $R_1$. Suppose $\H(m,16)=6$. The response is $z=9+3+5\cdot6=19\pmod{23}$.

The two sides of verification are $2^{19}=3$ and $8\cdot16\cdot34^4\cdot32^6=3\pmod{47}$. These fixed toy hash values support a readable arithmetic trace only. They are not a secure hash implementation or parameters for deployment.

Fixed-ring proof versus a variable-ring application

An application with variable rings must specify a canonical ring encoding, ring selection and key-registration rules. Binding a domain and the ordered ring to each hash input is a natural teaching extension, but it is a different byte-level scheme and needs a corresponding proof statement. We do not claim that the historical fixed-ring theorem automatically covers maliciously registered keys, arbitrary ring changes or adaptive corruption.

16 / System Security IIAnonymity: an exact distribution proof

Fix the public ring, message and hash function. Consider any valid signature with pairwise distinct nonidentity commitments. Let

There are $(q-1)\cdot(q-2)\cdots(q-n)$ ordered tuples in $\Omega$. We will show that each possible signer gives each one exactly the same probability. This is a pointwise statement about distributions, not an argument that “all signatures look similar”.

First, sample the other n − 1 commitments

For signer $j$, the other commitments are uniform ordered choices without replacement from $q-1$ nonidentity points. The probability of their particular values in the fixed target signature is

For $n=1$, this empty product is one. The public hash values for those commitments are now fixed, regardless of whether the hash is computationally ideal. The anonymity calculation does not need a random-oracle assumption.

Then, account for rejection sampling correctly

For those fixed other commitments, the map $u\mapsto g^u\cdot\prod_{i\ne j}A_i^{-c_i}$ is a bijection from $\mathbb Z_q$ to $G$. Each trial for $R_j$ is uniform on $G$. The signing algorithm excludes exactly $n$ points: the identity and the $n-1$ existing commitments. Therefore the accepted $R_j$ is uniform on the remaining $q-n$ points.

Do not assign probability $1/q$ to the accepted value. Summing over any number of rejected trials gives, for one allowed point,

The expected number of trials is $q/(q-n)$. For a tiny ring in a cryptographically large group this is close to one. The restriction $n<q$ is essential for termination and for the probability calculation.

Finally, the scalar response cannot reveal the signer

For a fixed commitment tuple the hash values are fixed. The verification equation determines a unique $z\in\mathbb Z_q$ because exponentiation by $g$ is bijective. Thus no extra signer-dependent choice is left in the response. For every signer $j$,

The right side is independent of $j$. Hence any two signers induce identical distributions on the public signature. In the usual two-candidate challenge game, even an unbounded observer guesses the hidden signer bit with probability exactly $1/2$. For a uniform prior over all $n$ members the posterior remains uniform. With a nonuniform prior, the signature does not magically erase external information; it leaves that prior unchanged.

Check the same signature under another signer

In the preceding toy example, the signature was $(R_1,R_2,z)=(8,16,19)$. Member 1 can also produce it: its ordinary other-branch nonce is $u_2=4$, and its closing scalar is $u=10$. Then $R_1=2^{10}\cdot32^{-6}=8$, and $z=10+4+7\cdot4=19\pmod{23}$. Each signer produces that same signature with probability $1/(22\cdot21)=1/462$ under the specified sampler.

This explanatory reconstruction may use discrete logarithms because the toy example supplies them. The actual signing algorithm does not compute logarithms of other users' keys. A proof that a transcript could have arisen from any member is different from an algorithm that recovers another member's secret.

What this theorem does not hide

The claim is about the public transcript under the stated sampler. Timing, network addresses, browser logs, faulty randomness, an exposed signing state or a disclosed random tape can give additional evidence absent from that view. Even knowing all long-term keys does not change the pointwise transcript calculation, but knowing the actual ephemeral choices can. Correct verification by itself is never a test of anonymity.

Exercise. Enumerate the toy experiment exactly for both signers, including the conditional distribution after rejecting collisions. Compare counts for every accepted signature. Then bias the other-branch nonce distribution and determine whether the pointwise equality still holds. An experiment can catch a sampling error; the symbolic counting argument establishes the general property.

17 / System Security IIRing forking and the cost of multiple queries

For Herranz–Sáez, a useful fork must keep the message, ring and every $R_i$ fixed. Exactly one challenge, say $c_j$, must change. Divide the two verification equations:

If two branch challenges change, the quotient generally contains two public-key powers and this one-variable extraction does not follow. If a commitment changes, it also fails to cancel. These are not cosmetic differences between forks.

Why the index pattern is larger than Q

The forger queries $n$ distinct inputs $(m,R_i)$. Associate a successful forgery with the ordered vector of their query indices $(\ell_1,\ldots,\ell_n)$. There are at most

such vectors. The ring-forking argument groups successes by this entire pattern. It rewinds at the latest of those $n$ queries. Earlier signature challenges remain fixed; the latest one changes. Successful replay must return to the same index pattern. The common prefix fixes all the associated query inputs, so the commitment tuple really is the same.

This is why applying the ordinary $Q$-indexed forking bound as if it already guaranteed the required ring fork would be unjustified. For example, $Q=10,n=3$ gives $V_{Q,n}=720$, not $10$ and not the unordered-subset count $120$. Each commitment position is associated with its own public key, so order matters.

The historical estimates and their assumptions

Under the generic conditions in Herranz–Sáez, the no-message threshold is $\epsilon\ge7V_{Q,n}/h$, with challenge alphabet parameter $h=2^k$. The expected-time bound is $84480\cdot V_{Q,n}\cdot T/\epsilon$. This carries over the earlier schedule argument with query-index patterns in place of single indices.

For $W$ chosen-message signing queries and signing-simulation time $T_s$, the report states the threshold and bound

The collision accounting retains at least $7\epsilon/12$. The multiplier is the rounded-up value of $84480\cdot12/7$. The quadratic term controls oracle/simulation collisions; it is not part of the final modular inversion. The generic statement assumes high-entropy commitments, a suitable signing simulator and the stated distinctness conditions. For a hash uniform in $\mathbb Z_q$, one can use $h=2^k\le q$ as a conservative bound on inverse challenge probabilities while checking those other conditions separately.

Scalability boundary. $V_{Q,n}$ can be enormous, and need not be polynomial when the ring size grows with the security parameter. The displayed historical reduction must not be called a tight, practical bound for arbitrary large rings. A useful parameter claim needs the actual ring-size regime, query bounds and a theorem applicable there. A threshold greater than one makes this sufficient-condition statement vacuous, not automatically false or an attack on the construction.

Signing simulation and where collisions enter

One instructive simulator first chooses the other commitments and their hash values, then chooses $c_j,z$ and solves the verification equation for $R_j$:

It rejects identity/duplicate commitments and programs the as-yet-unanswered value $\H(m,R_j)=c_j$. If that input is already assigned, it must not overwrite the table. This gives the local algebra behind simulation; a global proof couples the distributions and counts all programming conflicts. The report's simulator additionally samples distinct challenge values and bounds the statistical difference from independent hash outputs. Distinct challenges are not a rule imposed by the real signing algorithm.

This distinction prevents a common mistake: adding a rejection rule to the actual signer merely because it was convenient in a simulator. The anonymity count above uses the real signer's commitment restrictions, not the simulator's auxiliary conditioning.

Embed a useful unknown in every possible extracted branch

In the report's fixed, honestly generated ring reduction, start with a DL challenge $A=g^a$ and choose distinct nonzero multipliers $\alpha_i$. Publish $A_i=A^{\alpha_i}$. When $A$ is a nonidentity generator, this produces uniformly distributed distinct nonidentity ring keys under the corresponding sampling convention. The reduction knows the multipliers, not their secret logarithms.

Whichever branch $j$ changes, the quotient of the two verification equations gives

This avoids an additional guess of which honest member supplies the extracted logarithm in that fixed-ring setup. It does not simulate an adversary that asks to corrupt arbitrary ring members: their secrets remain unknown. A stronger corruption or adversarial-key model requires another reduction, rather than a silent extension of this one.

18 / System Security IIAKE reductions and the meaning of state exposure

AKE proofs must follow multiple session instances, not just a single signature forgery. A session records its role, intended peer, sent and received messages, state, acceptance and derived key. A partnering relation says which instances belong to the same exchange. A freshness predicate excludes revealing the test key and specifies permitted combinations of static and ephemeral compromise.

The session-oracle interface

Write $\pi_U^j$ for session $j$ at party $U$. A CK-style teaching experiment separates the following operations. Their precise admissibility rules belong to the selected definition; eCK and device-leakage refinements do not merely rename this interface.