Chapter 32: PQ-secure commitment schemes
L2 is the load-bearing quantum-safety axis in the decomposition Ch 31 introduced. For each L2 family, what does the quantum adversary do, and at what parameter cost is the system restored? Four families are in scope: KZG, named for Kate, Zaverucha and Goldberg (pairing-based, Shor-broken), Merkle (hash-based, quantitatively degraded), FRI (hash-based plus an information-theoretic proximity argument), and lattice polynomial commitments (Module-SIS-based). A short coda covers inner-product arguments as the DL-transparent Shor-broken alternative to KZG. KZG, Merkle and FRI are derived to a common depth: commitment definition, opening protocol, binding reduction, quantum adversary analysis. The lattice family gets the definition, the binding reduction and the quantum analysis, with the evaluation protocols the cited constructions rely on left out of scope and a coefficient-commitment toy in their place. The tradeoff table at the end extends Table 31.2 from Ch 31 with concrete parameters.
A 16-element vector, four commitment families
Section titled “A 16-element vector, four commitment families”A prover holds a polynomial p(x) = a_0 + a_1 x + ... + a_{15} x^{15} with coefficients in a finite field F. The verifier later sends a challenge point z in F and asks for y = p(z). The prover opens the commitment at z by returning y together with a witness W. The verifier runs Verify(C, z, y, W) and accepts or rejects.
The functional interface is identical across the four families. What differs is what C and W are in bytes, which algebraic equation Verify checks, and what a Shor- or Grover-capable adversary can do with the commitment transcript. The rest of the chapter walks that difference, family by family.
Polynomial commitments as a primitive
Section titled “Polynomial commitments as a primitive”A polynomial commitment scheme, abbreviated PCS in the literature and in the tables below, is treated here through a simplified four-algorithm evaluation interface. Kate, Zaverucha and Goldberg define six algorithms, separating whole-polynomial opening and verification from evaluation witnesses and their verification (Kate et al., 2010, sec. 3.1). The four below keep setup and commitment and take the evaluation pair as opening and verification:
Setup(1^lambda, d)returns public parameterspp(and, for schemes with a trusted setup, a trapdoor to be destroyed). The parameterdupper-bounds the degree of polynomials that can be committed.Commit(pp, p)returns a short commitmentCbinding the prover top.Open(pp, p, z)returns(y, W)withy = p(z).Verify(pp, C, z, y, W)returns accept or reject.
Correctness says that honestly-produced openings verify. Binding says that no efficient adversary can produce (C, z, y_1, W_1) and (C, z, y_2, W_2) with y_1 != y_2 that both verify. Hiding, when required, says that C reveals no information about p to a computationally bounded adversary. All four families satisfy correctness and binding. IPA (Pedersen-style) commitments can be statistically hiding via uniform blinding in the exponent; lattice PCS is computationally hiding under Module-LWE; KZG, Merkle, and FRI are binding but not hiding without an extra randomness coordinate.
The field F is a prime-order finite field when polynomial arithmetic is the goal. The construction sections use F_q with q prime throughout. Ring extensions appear only in the lattice PCS subsection, where coefficients live in a polynomial ring R_q = Z_q[X] / (X^n + 1) at the parameters established in Ch 9 and Ch 10.
Four constructions
Section titled “Four constructions”The construction section walks the four families in turn, with a pedagogical Python slice for each. Every inline block is a stdlib-only extract of the standalone package at solutions/ch32-commitment-schemes/. Production KZG and production FRI are out of scope: real KZG requires pairing-friendly curves with two source groups, and production FRI belongs to the STARK pipeline covered in Ch 34.
KZG: trapdoor in the structured reference string
Section titled “KZG: trapdoor in the structured reference string”KZG places the commitment in a prime-order subgroup G of an elliptic-curve group that admits a bilinear pairing e: G x G_2 -> G_T. The setup samples a trapdoor tau in F_q (where q is the group order), builds the structured reference string SRS = (g, g^tau, g^(tau^2), ..., g^(tau^d)) in G, publishes SRS together with its G_2 counterpart, and erases tau.
Commitment is one group element: C = g^(p(tau)). The prover computes C from the SRS without knowing tau by taking the product prod_i SRS[i]^(a_i), which equals g^(sum_i a_i tau^i) = g^(p(tau)). Opening at z produces the quotient polynomial q(x) = (p(x) - y) / (x - z), which is a polynomial because x - z divides p(x) - p(z), together with its commitment W = g^(q(tau)). Verification uses the pairing equation e(C / g^y, g_2) = e(W, g_2^tau / g_2^z) (Kate et al., 2010).
Binding reduces to the d-Strong Diffie-Hellman (d-SDH) assumption, as established in the original Kate-Zaverucha-Goldberg paper (Kate et al., 2010). A discrete-logarithm (DLOG) oracle on the curve suffices to break d-SDH, because recovering tau from g^tau lets an attacker compute arbitrary (c, g^{1 / (tau + c)}) pairs from the SRS. Consequently a DLOG solver breaks KZG binding: Shor’s polynomial-time quantum DLOG is the relevant instantiation (Shor, 1994).
Block 1 shows the SRS construction and commit routine. The toy uses the safe prime p = 2027 = 2 * 1013 + 1, working in the order-1013 multiplicative subgroup of F_p^*. This is the chosen toy safe prime, small enough to brute-force and large enough that the subgroup arithmetic is not trivial. Real KZG commonly uses BN254 (~254-bit subgroup order) or BLS12-381 (~255-bit subgroup order sitting inside a 381-bit base field whose coordinate encoding produces 48-byte compressed G1 elements). The generator g = 4 = 2^2, where 2 is a primitive root of F_2027, so 4 sits in the unique index-2 subgroup of order 1013.
# Block 1: pedagogical slice of commitment_schemes.toy_kzg.setup and commit (stdlib only).
PRIME = 2027 # 2 * 1013 + 1 (safe prime)ORDER = 1013 # prime order of the subgroupGEN = 4 # generator of the order-1013 subgroup
def srs_setup(degree, tau): powers = [] tau_power = 1 for _ in range(degree + 1): powers.append(pow(GEN, tau_power, PRIME)) tau_power = (tau_power * tau) % ORDER return powers
def commit(coeffs, srs): result = 1 for c, power in zip(coeffs, srs): result = (result * pow(power, c, PRIME)) % PRIME return result
tau = 500srs = srs_setup(degree=4, tau=tau)p = [7, 11, 13, 17, 19] # p(x) = 7 + 11x + 13x^2 + 17x^3 + 19x^4C = commit(p, srs)print(f"|SRS| = {len(srs)}, C = {C}")# ==> |SRS| = 5, C = 1499Every Python block this chapter prints is also a standalone file in the companion repository, under chapter-code/ch32/, one file per block. Appendix C covers the clone and the environment they run on.
The commitment is one group element (C = 1499) regardless of the polynomial degree. Opening adds a second element: the witness W = g^(q(tau)) where q(x) = (p(x) - y) / (x - z). In deployed KZG at 128-bit classical security, each compressed G1 point on BLS12-381 is 48 bytes (Hopwood et al., 2026). A KZG commitment plus its opening witness therefore total 96 bytes, independent of d.
The Shor attack on KZG recovers tau from the SRS. The element g^tau is the second SRS entry, published alongside g. A Shor-capable adversary computes the discrete logarithm of g^tau base g and obtains tau in time polynomial in log q (Shor, 1994). Once tau is known, the adversary forges openings at will. For any commitment C, any chosen point z with z != tau, and any chosen evaluation y_fake, the adversary sets W = (C * g^(-y_fake))^(1 / (tau - z)) in the group. The forged (y_fake, W) passes the pairing equation because the equation is an algebraic identity once tau is available. The single edge case z = tau is not a defence. The formula divides by tau - z, so at that point the verification equation forces y = p(tau) and only the honest evaluation is accepted. Every other point still admits an arbitrary forgery.
Read the middle row of the figure below first: the SRS element g^tau is the attack surface. SRS rotation does not close the window: a fresh tau' is recovered on the same polynomial-time schedule.
tau in polynomial time and forges openings for any chosen evaluation y at any z != tau. The operator decision is the L2 family to migrate to (FRI, Merkle, or lattice PCS) and the proof-size budget.Block 2 demonstrates the attack on the toy SRS. Classical brute force substitutes for the quantum circuit: the DLOG search ranges over [1, ORDER), which is 1012 values for the toy and polynomial-time-tractable for Shor on a production curve.
# Block 2: pedagogical slice of toy_kzg.shor_recover_tau and forge_opening (stdlib only).
PRIME = 2027ORDER = 1013GEN = 4
def shor_recover_tau(srs): # Recover tau from (g, g^tau). Classical brute force here; Shor is poly(log q). g_tau = srs[1] for candidate in range(1, ORDER): if pow(GEN, candidate, PRIME) == g_tau: return candidate raise ValueError("tau not recoverable")
def forge_opening(C, z, y_fake, tau): # Given tau, W = (C * g^{-y_fake})^(1 / (tau - z)) in the order-ORDER subgroup. # Edge case: at z == tau the formula divides by zero, forcing y == p(tau); # the forger picks any z != tau. if (tau - z) % ORDER == 0: raise ValueError("z == tau: verification forces y = p(tau), no forgery possible at this point") numerator = (C * pow(GEN, (-y_fake) % ORDER, PRIME)) % PRIME inv_tz = pow((tau - z) % ORDER, -1, ORDER) return pow(numerator, inv_tz, PRIME)
# Prover's honest state from Block 1 (reproduced here; blocks run in isolation).def srs_setup(degree, tau): powers, tau_power = [], 1 for _ in range(degree + 1): powers.append(pow(GEN, tau_power, PRIME)) tau_power = (tau_power * tau) % ORDER return powers
def commit(coeffs, srs): r = 1 for c, power in zip(coeffs, srs): r = (r * pow(power, c, PRIME)) % PRIME return r
tau_true = 777srs = srs_setup(degree=4, tau=tau_true)C = commit([2, 3, 5, 7, 11], srs)
recovered = shor_recover_tau(srs)y_fake = 42W_fake = forge_opening(C, z=100, y_fake=y_fake, tau=recovered)print(f"recovered tau = {recovered}, forged W = {W_fake}")# ==> recovered tau = 777, forged W = 1376Shor recovers the trapdoor and the adversary produces a forged witness for an arbitrary y_fake. Binding collapses at every z != tau. The exception z = tau is forced to the honest evaluation y = p(tau) because the forgery formula divides by zero there. With tau hidden in normal operation, the adversary picks any other point, and binding is destroyed for every commitment. Nothing internal to KZG’s construction stops this. Parameter bumps on the curve order only push the timeline. The attack remains polynomial in log q.
The operator-side implication is that KZG cannot be restored by parameter adjustment. Migration requires a structural replacement of L2. Figure 31.1 in Ch 31 marks Groth16’s L2 cell red for exactly this reason (Groth, 2016). PLONK over KZG has the same cell red, but the PLONK construction factors the polynomial commitment scheme out of the verifier as a separately-instantiable ideal primitive. The PLONK verifier is defined against any polynomial commitment scheme that satisfies the interface. Section 4 of (Gabizon et al., 2019) treats KZG as one concrete choice. This is what makes a commitment swap to FRI or lattice PCS possible without rewriting the protocol logic above L2.
Merkle: hash-based binding
Section titled “Merkle: hash-based binding”A Merkle commitment hashes the data into n-bit digests, folds the digests q at a time up a balanced q-ary tree, and publishes the root digest as the commitment (Merkle, 1989). Opening at leaf index i returns the leaf value together with the path of q - 1 sibling digests at each of the log_q N levels from the leaf to the root. Verification reconstructs each parent digest from the leaf and the recorded siblings and checks equality with the committed root.
Binding reduces to the collision resistance of the hash function. If two distinct leaf sets produce the same root, at least one collision must have occurred at some internal node along the fold. For a commitment to a polynomial, the leaves are the N = 2^k evaluations of p on a fixed evaluation domain. Opening at a queried point returns the matching leaf and its path. A polynomial commitment built this way needs a second ingredient: the verifier must detect a prover who commits to a vector that is not close to any polynomial of degree less than d. The proximity argument for that detection is not part of the Merkle layer itself. FRI adds it in the next subsection.
Block 3 builds a binary and a quaternary Merkle tree, then prints two post-quantum collision margins for each of three hash output widths. Both are named for their authors: BHT for Brassard, Hoyer and Tapp (Brassard et al., 1998), and CNPS for Chailloux, Naya-Plasencia and Schrottenloher (Chailloux et al., 2017).
# Block 3: pedagogical slice of commitment_schemes.merkle.commit_leaves and# quantum_collision_bits_{bht,cnps} (stdlib only).
import hashlib
def hash_bytes(data, width_bits): # SHAKE128's collision-resistance security strength is capped at # 128 bits regardless of output length (FIPS 202 Appendix A.1), so # routing 384/512-bit outputs through SHAKE128 would not actually # deliver the BHT/CNPS margins computed below. SHAKE256 is the # right XOF for output widths past 256 bits. if width_bits == 256: return hashlib.sha256(data).digest() if width_bits >= 384: return hashlib.shake_256(data).digest(width_bits // 8) return hashlib.shake_128(data).digest(width_bits // 8)
def merkle_root(leaves, arity, width_bits): zero = bytes(width_bits // 8) level = [hash_bytes(leaf, width_bits) for leaf in leaves] padded = arity while padded < len(level): padded *= arity level += [zero] * (padded - len(level)) while len(level) > 1: level = [ hash_bytes(b"".join(level[i:i + arity]), width_bits) for i in range(0, len(level), arity) ] return level[0]
leaves = [f"eval-{i}".encode() for i in range(8)]root_bin = merkle_root(leaves, arity=2, width_bits=256)root_quad = merkle_root(leaves, arity=4, width_bits=256)print(f"binary root first 4 bytes = {root_bin[:4].hex()}")print(f"quaternary root first 4 bytes = {root_quad[:4].hex()}")
for n in (256, 384, 512): bht = n // 3 cnps = (2 * n) // 5 print(f"n={n}: BHT={bht}, CNPS={cnps}")# ==> binary root first 4 bytes = e3a3d759# ==> quaternary root first 4 bytes = b1add67a# ==> n=256: BHT=85, CNPS=102# ==> n=384: BHT=128, CNPS=153# ==> n=512: BHT=170, CNPS=204The BHT bound at n = 256 is 85 bits, below the conservative 128-bit post-quantum collision margin used as this book’s long-lived target. NSA / CNSA 2.0 profiles for high-assurance settings motivate wider hashes such as SHA-384 / SHA-512 (US National Security Agency, 2022). NCSC guidance is more parameter-set specific, recommending ML-KEM-768 and ML-DSA-65 for most use cases (UK National Cyber Security Centre, 2024), and does not directly mandate a Merkle / STARK hash width. At n = 384 the BHT bound clears 128 bits. The CNPS bound, which drops the Quantum-Random-Access-Classical-Memory (QRACM) assumption underpinning BHT, gives a less aggressive estimate: 102 bits at n = 256 and 153 bits at n = 384. Deployments that reject QRACM as physically unrealistic can argue for n = 256 at a 102-bit PQ target; deployments that bake in the BHT bound as the worst case need n = 384 to reach 128 bits.
n = 256 gives 85-bit BHT and 102-bit CNPS collision security, both below the 128-bit PQ target. n = 384 gives 128-bit BHT (meets target) and 153-bit CNPS (exceeds).Every width above assumes a hash whose collision-resistance security strength is at least n / 2 bits, which is a constraint on the primitive and not just on the output length. So n = 384 means SHA-384, SHA3-384, or SHAKE256 with 384-bit output. SHAKE128 caps at 128 bits of collision strength however many output bytes it is asked for (FIPS 202 Appendix A.1). A 384-bit SHAKE128 digest would therefore report a 128-bit BHT margin it does not deliver. Ch 31 stated both BHT and CNPS bounds; this chapter sizes the parameters that each implies.
The toy in Block 3 hashes leaves and internal nodes with the same primitive for readability. Production Merkle commitments domain-separate leaf hashes from internal-node hashes (typically a one-byte tag prefix) and bind the tree arity, the vector length, and any evaluation-domain metadata into the commitment to prevent confused-deputy attacks across trees of different shape. The BHT and CNPS bounds analysed above sit on top of that domain-separated layer.
The Shor attack does not apply to Merkle directly. The quantum adversary is limited to collision-finding, and collision-finding on a symmetric primitive is bounded by BHT or CNPS, not by Shor. The operator-side fix, when the target margin is thin, is a hash-width bump. This is why Ch 31 marked the Merkle cell amber rather than red: amber means parameter adjustment restores the margin, red means a structural replacement is required.
FRI: proximity as commitment
Section titled “FRI: proximity as commitment”FRI (Fast Reed-Solomon IOP of Proximity, or IOPP) commits to a polynomial by fixing a multiplicative subgroup L of F_q^* of size N = 2^k, evaluating p on every point of L, and committing to the resulting evaluation vector via a Merkle root. The FRI paper states its main theorem for binary additive codes and extends it to this smooth multiplicative setting in a remark (Ben-Sasson et al., 2018, sec. 1.1.3). What promotes FRI from a vector commitment to a polynomial commitment is the proximity argument. In log_2 d folding rounds the prover reduces a degree claim to a constancy claim. The initial claim is that the committed vector is the evaluation of a polynomial of degree less than d; the reduced claim is that the folded vector, now on N / d points, is constant. The round count is set by the degree bound, not by the domain: one fold more would also flatten every polynomial of degree below 2d, so the verifier would be testing the wrong code.
Each round halves the domain. Given f: L -> F and a verifier challenge beta, the prover sends f': L^2 -> F defined by
f'(x^2) = (f(x) + f(-x)) / 2 + beta * (f(x) - f(-x)) / (2 x).
The identity f(x) = f_e(x^2) + x * f_o(x^2) decomposes f into even and odd components. The folding collapses these two univariate polynomials on L^2 into one, with beta a verifier-chosen linear combination coefficient. After log_2 d rounds the domain has N / d points and the prover sends the final vector, which the verifier checks for constancy and against the consistency of the whole folding chain.
The binding argument is twofold. The Merkle root of each round commits the prover to a specific function at that round. The soundness analysis of FRI handles the rest. The first such analysis is due to Ben-Sasson, Bentov, Horesh, and Riabzev. The proximity-gap theorem the accounting below uses is the later result of Ben-Sasson, Carmon, Ishai, Kopparty, and Saraf (BCIKS). For a codeword at relative Hamming distance delta from every polynomial of degree less than d, with delta below the Johnson bound 1 - sqrt(rho), the proximity-gap theorem bounds each round’s bad-challenge probability as a function of delta, the code rate rho = d / N, and the field size |F| (Ben-Sasson et al., 2018, 2020). A bad challenge is a fold coefficient that brings a far word close to the code, and it is the term the field size enters. Ch 34 Section 5.1 states the theorem’s regimes and error terms. The query phase is accounted separately. A FRI query is not confined to one round: it picks one position of the initial domain and follows it through every folding round, checking at each round that the next function agrees with the fold of the previous one at that position. A single query misses a delta-far codeword with probability roughly 1 - delta, so with mu independent queries the miss probability drops as approximately (1 - delta)^mu.
Across the folding chain, total soundness is not a clean product of per-round terms. The standard accounting bounds the total soundness error by a sum (union bound) over the log_2 d folding rounds plus the query-phase error, with each round’s contribution governed by the proximity-gap theorem at that round’s parameters (Ben-Sasson, Carmon, et al., 2020; Ben-Sasson et al., 2018; Ben-Sasson, Goldberg, et al., 2020). Ch 34 Section 5.2 derives the composition across the FRI folding chain.
Two constraints bound where the construction applies. The folding identity requires char(F) != 2 so that 1/2 and 1/(2x) exist. The field F_97 satisfies this, and so do the standard prime-field FRI/STARK deployments (Goldilocks, BabyBear, Mersenne31). Binary-field systems such as Binius operate over towers of GF(2^k) and use different folding and encoding machinery (Diamond & Posen, 2025). Two neighbours are worth naming for contrast. DEEP-FRI modifies the FRI protocol itself. In every folding round the verifier also samples a point outside the evaluation domain, the prover states the folded polynomial’s value there, and the next round’s function is the fold quotiented by that point. Its soundness is a new theorem about the modified protocol, proved from that paper’s own reduction for Reed-Solomon codes rather than from the Ben-Sasson-Bentov-Horesh-Riabzev argument, and it reaches the code’s list-decoding radius. The construction that samples one out-of-domain point, turns an evaluation claim into a low-degree claim by quotienting, and hands the result to an unchanged proximity test is the same paper’s DEEP-ALI (Ben-Sasson, Goldberg, et al., 2020). Hash-based polynomial commitments like Brakedown use a tensor-code proximity test as an alternative to FRI’s Reed-Solomon folding, at the cost of larger proofs (Golovnev et al., 2023).
Block 4 implements one FRI folding round in F_97. The choice p = 97 admits a multiplicative subgroup of order 32 (since 96 = 2^5 * 3), which is large enough to fold four times. The generator g = 8 has order 16 in F_97^*, spanning a 16-element domain. The domain is closed under negation: for x = g^i, the element -x = g^(i + 8) sits in position i + 8 of the domain list, which the fold pairs against position i.
# Block 4: pedagogical slice of commitment_schemes.fri.fold_once (stdlib only).
PRIME = 97
def gen_domain(size, generator): # Multiplicative subgroup domain {1, g, g^2, ..., g^(size-1)}. out, current = [], 1 for _ in range(size): out.append(current) current = (current * generator) % PRIME return out
def eval_poly(coeffs, x): result = 0 for c in reversed(coeffs): result = (result * x + c) % PRIME return result
def fold_once(evals, domain, beta): half = len(domain) // 2 two_inv = pow(2, -1, PRIME) new_evals, new_domain = [], [] for i in range(half): x = domain[i] fx, f_neg_x = evals[i], evals[i + half] even = ((fx + f_neg_x) * two_inv) % PRIME odd = ((fx - f_neg_x) * two_inv * pow(x, -1, PRIME)) % PRIME new_evals.append((even + beta * odd) % PRIME) new_domain.append((x * x) % PRIME) return new_evals, new_domain
domain = gen_domain(16, generator=8) # order-16 subgroup of F_97^*p = [7, 3] # p(x) = 7 + 3x (degree 1)evals = [eval_poly(p, x) for x in domain]folded_once, domain_once = fold_once(evals, domain, beta=5)folded_twice, domain_twice = fold_once(folded_once, domain_once, beta=11)folded_thrice, _ = fold_once(folded_twice, domain_twice, beta=17)print(f"after 3 folds: len = {len(folded_thrice)}, values = {folded_thrice}")# ==> after 3 folds: len = 2, values = [22, 22]A degree-1 polynomial folded three times collapses to a length-2 constant vector. Both entries equal 22, which for p(x) = 7 + 3 x and beta_1 = 5 is the scalar a_0 + beta_1 * a_1 = 7 + 15 = 22. Subsequent folds with beta_2 = 11 and beta_3 = 17 leave the constant unchanged because the input is already degree zero. For p(x) of degree 1 the degree bound is d = 2, so one fold already ends the protocol on 8 points; Block 4 keeps folding to show that a constant stays constant, and the same three folds would take any polynomial of degree below 8 to a constant on the final two points, which is why the fold count is a protocol parameter and not a choice. A function that is not low-degree need not collapse to a constant. The verifier’s consistency queries detect the failure with probability bounded by the proximity-gap argument (Ben-Sasson, Carmon, et al., 2020; Ben-Sasson et al., 2018), and the bound tightens with each additional query repetition.
The operator decision is the number of queries per round required to reach the target soundness at the chosen field size. Adding queries is cheap compared to rebuilding L2.
log_2 d folding rounds. Each round contributes an error term, and additional queries shrink only its query-miss part; the proximity-gap and bad-challenge parts are fixed by the field, the rate and the fold, as Ch 34 partitions them. The chain is accounted for by a union bound, not a clean product (Ben-Sasson et al., 2018; Block et al., 2023).The quantum posture of FRI has two sides. The proximity-gap result is information-theoretic. It does not assume computational hardness of any primitive, so a quantum adversary gains nothing by running Grover or Shor against the proximity argument itself. The Merkle commitments at each round, however, inherit the BHT or CNPS collision margin of their hash function, and the Fiat-Shamir compilation to non-interactivity inherits the QROM analysis that Ch 33 covers. The Block et al. 2023 result gives the closest published end-to-end QROM analysis for FRI-based SNARKs, establishing the parameters at which the folding rounds compose under a quantum-oracle adversary (Block et al., 2023).
The ethSTARK parameter choices, priced in the random-oracle model with grinding counted, are documented in (Ben-Sasson, 2021, sec. 5.10) and are the worked example in Exercise E1.
FRI’s L2 posture is amber, as Figure 31.2 in Ch 31 shows: a hash-width bump plus additional query rounds compensate for any QROM soundness drop, restoring the target margin without a structural replacement.
Lattice PCS: SIS binding, recent literature
Section titled “Lattice PCS: SIS binding, recent literature”A lattice polynomial commitment encodes the polynomial coefficients as a short vector m and commits via C = A_0 m + A_1 r + e mod q, where (r, e) is short randomness the prover samples independently of m, from a discrete Gaussian in the cited construction, which writes the same commitment as A_0 m + A_1 mu with the error folded into the randomness vector (Hwang et al., 2024). The matrices live in Z_q^(k x n) and Z_q^(k x l) and are sampled by a public seed. Production constructions use the algebraic structure of the polynomial ring R_q = Z_q[X] / (X^n + 1) from Ch 9 and Ch 10 to reduce an evaluation claim p(z) = y to a set of small-norm checks on m and e. Block 5 below works in Z_q rather than R_q to keep the toy inspectable. The evaluation protocols the chapter cites rely on the ring structure and are out of scope here.
Four constructions mark the line from 2024 to 2026, and they do not compete on the same axis. Greyhound combines the ring reduction with the LaBRADOR succinct argument to compress the proof, and is the univariate baseline the later papers measure against (Beullens & Seiler, 2023; Nguyen & Seiler, 2024). Jindo targets client-side proving, where prover speed and evaluation hiding matter more than the last kilobyte of proof. It reports about an order of magnitude over CELPC across proof generation, verification, and proof size together (Hwang et al., 2026). Hachi extends the construction to multilinear polynomials over extension fields (Nguyen et al., 2026).
The fourth entry is a caution about citing this literature at all. HyperWolf, a hypercube-tensor construction, reported proof sizes of similar magnitude to Greyhound at N = 2^25 with lower verifier time (Zhang et al., 2025). That eprint was withdrawn in October 2025. Its authors replaced it with Serval, which its own eprint note describes as an optimization of the same work, adding implementations and -norm proofs. Serval’s abstract headlines L = 2^20, but its own table places Greyhound beside it at L = 2^25 and L = 2^30, both at 128-bit security, and its text says outright that its proofs are larger than Greyhound’s while its verifier is faster at large L (Zhang, Chow, et al., 2025). Two caveats travel with that table: Serval’s sizes are computed from proof-size formulas rather than taken from its microbenchmarks, and its verifier comparison counts ring operations rather than wall-clock time, because it does not compare timings across codebases.
Binding reduces to the hardness of Module-SIS, the Module-Short-Integer-Solution problem. In the toy’s form C = A m + e, where the real scheme’s r would join e as further short coordinates of the same equation, it reads: given A, find a short (m', e') != (0, 0) with A m' + e' = 0 mod q. Two openings of the same commitment with different revealed (m, e) pairs yield A (m_a - m_b) + (e_a - e_b) = 0 mod q, which is a Module-SIS solution. If both openings satisfy ||m||_inf <= beta_m and ||e||_inf <= beta_e, the difference vectors satisfy ||delta_m||_inf <= 2 beta_m and ||delta_e||_inf <= 2 beta_e, so the parameter choice must make Module-SIS at norm bound max(2 beta_m, 2 beta_e) hard.
The toy below works over scalar Z_q rather than the module or ring R_q, so what it displays is plain SIS at small parameters; production lattice PCS works over R_q and reduces to Module-SIS or a construction-specific module or ring SIS variant. Ajtai’s worst-case-to-average-case reduction established SIS over general lattices (Ajtai, 1996). The module variant was formalized by Langlois and Stehle (Langlois & Stehlé, 2015). Greyhound cites them where it states Module-SIS, and Hachi does the same (Nguyen et al., 2026; Nguyen & Seiler, 2024). Hwang, Seo and Song do not: their Module-SIS definition carries no citation and their hardness estimate follows Gama and Nguyen’s root Hermite factor instead (Hwang et al., 2024).
Binding and hiding rest on two different assumptions. Binding is Module-SIS, as above. Hiding is computational and comes from the randomness, not from the message: A_1 r + e is a Module-LWE sample whose secret r and error e are both short and fresh, drawn from the scheme’s discrete Gaussian, so under Module-LWE at that short-secret distribution it is indistinguishable from uniform, and adding A_0 m to a uniform vector hides m. Hwang, Seo, and Song state hiding in exactly those terms, as Module-LWE at the Gaussian width their opening randomness is sampled with, and binding as Module-SIS (Hwang et al., 2024). The secret is short by design and not uniform over the ring: a uniform r would break the short-opening condition the Module-SIS binding argument needs. Randomising e alone does not: a receiver holding two candidate messages subtracts A m_0 and A m_1 from C and keeps the one whose residual is short, which on Block 5’s parameters identifies the message every time. Block 5 shows the binding equation only; it fixes e, carries no r, and is not hiding. Module-LWE is the assumption Ch 9 defines and ML-KEM uses at FIPS 203 parameters (National Institute of Standards and Technology, 2024).
Block 5 builds the commit equation over a small scalar SIS-style instance, not a Module-SIS instance in the ring sense the literature uses. The parameters (q, n, k) here are pedagogical only: q = 257, n = 8 (message dimension, not the ring degree of X^n + 1, since the toy has no ring), k = 4 (commitment dimension), with beta_m = 5 (the message bound from m = [3, -2, 1, 0, -4, 2, -1, 5]) and beta_e = 2 (the error bound from e = [1, -1, 0, 2]). Production parameters are two orders of magnitude larger in each dimension.
# Block 5: pedagogical slice of commitment_schemes.lattice_pcs.commit (stdlib only).
import hashlib
MODULUS = 257DIMENSION = 8COMMIT_SIZE = 4
def sample_matrix(seed): rows, counter, buf = [], 0, b"" for _ in range(COMMIT_SIZE): row = [] for _ in range(DIMENSION): while len(buf) < 4: buf += hashlib.sha256(seed + counter.to_bytes(8, "big")).digest() counter += 1 word = int.from_bytes(buf[:4], "big") buf = buf[4:] row.append(word % MODULUS) rows.append(row) return rows
def commit_sis(A, m, e): C = [] for row, err in zip(A, e): acc = sum(a * mi for a, mi in zip(row, m)) + err C.append(acc % MODULUS) return C
A = sample_matrix(b"ch32-demo-seed")m = [3, -2, 1, 0, -4, 2, -1, 5]e = [1, -1, 0, 2]C = commit_sis(A, m, e)print(f"C = {C}")# ==> C = [67, 146, 188, 205]The commitment is a length-4 vector in Z_q. Production lattice PCS has larger commitments. Greyhound reports 53 KB evaluation proofs for polynomials of degree at most 2^30, with its concrete sizes set to reach a security level of about 128 bits (Nguyen & Seiler, 2024). Hachi’s comparison table reproduces that figure for a 30-variable polynomial and puts its own at 55 KB, so the two sit within four percent of each other on size (Nguyen et al., 2026).
Size is not where the line has been moving. Hachi’s claimed gain over Greyhound is an asymptotic factor of lambda off the verifier, which it puts at 2.8 seconds down to 227 milliseconds (Nguyen et al., 2026). Read that pair carefully. The 227 milliseconds is not one measurement: Hachi’s table times the first round only, at 96.5 milliseconds on a Mac Mini M4 with no AVX support, and its text adds a 130 millisecond tail for the Greyhound stage taken from a private communication. Greyhound’s 2.8 seconds is a whole-verifier time on an AVX-512 Xeon core. The asymptotic claim stands on its own. The two wall-clock figures were not measured on the same machine or over the same work. Proof size has sat near 50 KB since 2024, and the papers since compete on verifier time, prover time, multilinear support, and hiding. A reader quoting one of these numbers should date-stamp it and name the parameter set, because the comparison points differ from paper to paper.
The quantum posture of Module-SIS is plausible post-quantum hardness, with one caveat about the exponent. No Shor-like polynomial-time quantum attack is known for Module-SIS or Module-LWE, and known quantum algorithms remain exponential. Quantum lattice sieving does improve the constant sitting in that exponent. In the core-SVP cost model Ch 13 derives, one call to the sieve at block size beta costs 2^(0.292 beta + o(beta)) classically, and the Laarhoven quantum speedup applied to its nearest-neighbour search brings that to 2^(0.265 beta + o(beta)) (Becker et al., 2016; Laarhoven et al., 2015). The quantum gain is a smaller constant on an exponent that stays linear in the block size, not a polynomial speedup, and that is the qualitative difference from Shor.
The load-bearing uncertainty is the same one Part II identified: lattice cryptanalysis has made incremental progress over the last decade (Albrecht et al., 2016; Guo & Johansson, 2021; MATZOV, 2022), and future improvements would adjust concrete parameters rather than break the construction. Note how thinly the lattice-PCS papers report that adjustment. Greyhound sets its concrete sizes to reach a security level of about 128 bits and states its method only by reference, pointing at LaBRADOR’s parameters and at Micciancio and Regev’s survey for how the ranks are chosen; Hachi fixes its parameters against a 128-bit target using the Lattice Estimator on Module-SIS in the infinity norm (Nguyen et al., 2026; Nguyen & Seiler, 2024). Neither publishes the per-attack, per-cost-model breakdown that Ch 13 walks for ML-KEM, so a lattice PCS margin and a standardized KEM’s are not quoted on the same evidence even when both read 128.
Inner-product arguments as the transparent DL alternative
Section titled “Inner-product arguments as the transparent DL alternative”Bulletproofs (Bünz et al., 2018), Halo (Bowe et al., 2019) and Halo 2 after it (Zcash, 2026) commit to a polynomial via an inner-product argument (IPA) over a prime-order elliptic-curve group. The commitment is a single group element; the opening is O(log N) group elements for a vector of length N. Binding reduces to the discrete logarithm problem on the underlying curve. The setup is transparent: no trapdoor, unlike KZG. A Shor-capable adversary recovers the discrete logarithm relationship between the commitment key elements in polynomial time. The adversary then forges openings by the same mechanism as the KZG attack: the opening equation becomes an algebraic identity once the discrete-log structure is known (Shor, 1994). IPA’s setup transparency does not help against Shor; the transparency argument is about trust, not quantum safety.
The IPA regime is Shor-broken at the same granularity as KZG. Halo 2 and Bulletproofs sit with Groth16 and PLONK on the Shor-broken side of Ch 31’s Figure 31.1. Migration paths lead to FRI, Merkle, or lattice PCS at L2, with the choice determined by the proof-size, prover-cost, and setup-transparency targets of the deployment.
Cryptanalysis per family
Section titled “Cryptanalysis per family”Each family has one dominant quantum attack and, in most cases, one parameter bump that buys margin until the next published result. Table 32.1 summarizes.
Table 32.1. Dominant quantum attack per commitment family.
| Family | Attack | Operator response |
|---|---|---|
| KZG | Shor recovers tau from the SRS, forges openings at any chosen evaluation z != tau. | Structural replacement of L2. No parameter fix. |
| Merkle | Quantum collision-finding on the hash: BHT 2^{n/3} under QRACM, CNPS 2^{2n/5} without. | Hash-width bump. n = 256 at 85 (BHT) / 102 (CNPS) bits PQ; n = 384 at 128 (BHT) / 153 (CNPS) bits PQ. |
| FRI | Merkle/hash collision margin (BHT or CNPS) plus the Fiat-Shamir/QROM compilation and concrete FRI parameter analysis. | Hash-width bump, plus query-round adjustment for the QROM-compiled soundness budget. |
| Lattice PCS | Module-SIS lattice cryptanalysis. No known polynomial-time quantum attack; quantum sieving improves the core-SVP exponent constant from 2^{0.292 beta} to 2^{0.265 beta} at block size beta. | Parameter tuning inside the assumption family under both classical and quantum sieving cost models. |
| IPA (Bulletproofs, Halo 2) | Shor recovers the DL relationship between commitment-key elements, forges openings. | Structural replacement of L2. No parameter fix. |
Table 32.1 distinguishes three families by the binding-reduction shape. KZG and IPA inherit Shor-vulnerable discrete-log binding, with no parameter fix. Merkle and FRI inherit collision-resistance binding, restored by a hash-width bump (and, for FRI, additional query rounds). Module-SIS-bound lattice PCS rests on a post-quantum assumption: no known polynomial-time quantum attack exists, and the best published quantum attack (sieving) gives a constant-factor reduction in the exponent rather than a polynomial speedup. The contrast with Shor’s polynomial-time break of discrete log is qualitative, not just quantitative.
Tradeoffs across the four families
Section titled “Tradeoffs across the four families”Table 32.2 extends Table 31.2 from Ch 31 with concrete parameters. Proof sizes include the commitment plus the opening witness where both are produced. Merkle openings are (q-1) * log_q(N) * n bits for arity q, ignoring leaf-value and domain metadata that production deployments bind in. The table cites the binary case q = 2. In the FRI row, mu is the number of query repetitions chosen to hit the target soundness, the same mu the binding argument above uses. It is not the security parameter, which is the lambda of Setup(1^lambda, d). Prover and verifier cost are asymptotic in the polynomial degree d.
Table 32.2. Two-axis tradeoff at 128-bit classical and 128-bit PQ targets.
| Family | Setup | Binding | Proof size (128-bit classical) | Proof size (128-bit PQ) | Prover cost | Verifier cost |
|---|---|---|---|---|---|---|
| KZG | Trusted (tau destroyed) | d-SDH (DL) | 96 bytes (BLS12-381, C + W) | N/A (Shor-broken) | O(d log d) FFT + O(d) multi-scalar mult | O(1) + 2 pairings |
| Merkle | Transparent | Collision resistance | (q-1) * log_q(N) * n bits | Same form, n >= 384 for BHT-128 | O(N) hashes | O(log_q N) hashes |
| FRI | Transparent | Collision resistance + proximity gap | O(mu * log^2 N) * n bits | Same form, n >= 384, queries bumped; concrete-parameter QROM accounting system-specific and pending (Ch 33) | O(N log N) | O(mu * log^2 N) |
| Lattice PCS (Greyhound) | Transparent (public seed) | Module-SIS | ~53 KB at degree up to 2^30 (Nguyen & Seiler, 2024) | Same at the same parameters | O(N) | O(sqrt N) up to log factors |
| IPA (Bulletproofs / Halo 2) | Transparent | DL | O(log N) group elements | N/A (Shor-broken) | O(N) group ops | O(N) or O(log^2 N) with recursion |
The Shor-broken families (KZG and IPA) have the smallest proofs at 128-bit classical but no restoration path at 128-bit PQ. Deployments that prioritize proof size face a structural migration.
The hash-based families (Merkle and FRI) have a clear path to 128-bit PQ via hash-width bumps and, for FRI, additional query rounds to compensate for QROM soundness losses. The proof size at the PQ target is within a small constant factor of the classical size.
The lattice family carries the same proof size at 128-bit classical and 128-bit PQ because its binding already rests on a post-quantum assumption. The tradeoff is absolute size: approximately 53 KB at degree up to 2^30 for Greyhound (Nguyen & Seiler, 2024), versus 96 bytes for KZG and hundreds of bytes for Merkle at comparable parameters. It shares with the plain IPA row a verifier that is not polylogarithmic: an unmodified Bulletproofs verification is linear in the vector length (Bünz et al., 2018), and the recursive accumulation that amortizes it is a separate qualification rather than the cost of one verification. Greyhound’s proof is polylogarithmic in the degree bound but its verifier runs in the square root of it (Nguyen & Seiler, 2024), which is why the papers after it compete on verification rather than on size.
All transparent setups (Merkle, FRI, lattice PCS, IPA) avoid the trusted-setup risk that KZG carries. In KZG, a compromised trusted-setup ceremony leaks tau and destroys binding for every user of the SRS, independently of whether a quantum computer exists. The Shor break on KZG is the post-quantum version of this same risk: the adversary recovers tau from the SRS directly, without needing a corrupted ceremony participant.
Where Chapter 32 ends and Chapter 33 picks up
Section titled “Where Chapter 32 ends and Chapter 33 picks up”This chapter derived the L2 column of Table 31.2. Four families were priced, three of them to the common depth and the lattice family short of an evaluation-opening protocol, and the answer split three ways rather than two. KZG and IPA are Shor-broken with no parameter fix. Merkle is restored by a hash-width bump, and FRI by that bump plus the additional query rounds the tradeoffs above name. Lattice PCS already rests on a post-quantum assumption and pays for it in absolute size. Nothing above this layer was analyzed.
Chapter 33 takes L4, the Fiat-Shamir transform that compiles the interactive protocols built on these commitments into non-interactive proofs. It classifies deployed systems into three tiers, three-move sigma protocols, multi-round interactive arguments, and FRI-based SNARKs, each with its own published QROM bound, and derives the measure-and-reprogram technique that produces them. The continuity is concrete as well as structural: Ch 33’s Schnorr example reuses this chapter’s toy group, p = 2027 with the order-1013 subgroup generated by g = 4, renaming the subgroup order to n so that q is free for the adversary’s quantum query budget.
What Chapter 33 does not close is the note above. It derives the Fiat-Shamir security proofs and states each tier’s parameter cost. The deployment-parameter accounting at ethSTARK, Plonky2, or Starknet is still open when that chapter ends, and Chapter 35 is where the deployed pipelines are read against it. L3 gets no chapter of its own, for the reason Ch 31 gave: it carries no separate computational hardness assumption, so its posture is inherited from the L2 chosen here. Chapter 34 still prices its information-theoretic contribution inside the composed soundness budget.
Exercises
Section titled “Exercises”E1. The ethSTARK suggested 80-bit configuration targets 80 bits of conjectured security in the random-oracle model with its 20 grinding bits counted, and uses BLAKE2s at a 160-bit digest at its FRI Merkle layer (Ben-Sasson, 2021, sec. 3.5 and §5.10.1). Compute the BHT and CNPS post-quantum collision bounds for 160-bit hashes. Argue whether 160 bits is adequate in three regimes. (a) 80-bit collision-resistance margin against a BHT quantum adversary. (b) The same target against a CNPS no-QRACM adversary. (c) The stricter 128-bit PQ margin that recent NCSC and NSA long-lived-signature guidance steers toward (UK National Cyber Security Centre, 2024; US National Security Agency, 2022). State the minimum hash output width required in each case. Contrast with hypothetical 256-, 320- and 384-bit outputs, and say which of them meets the 128-bit target in each model.
E2. Construct a toy SRS over the safe prime p = 2027 with trapdoor tau = 500 and degree 4. Simulate Shor’s discrete-log subroutine by brute-force search over the order-1013 subgroup. Verify that the recovered value equals tau. Use forge_opening to produce a witness W_fake for an evaluation claim y_fake = 42 at z = 100 against the commitment of the polynomial [7, 11, 13, 17, 19]. Verify the forgery directly in the group by checking that W_fake^(tau - z) mod p equals (C * g^{-y_fake}) mod p, which is the algebraic identity the pairing equation encodes.
E3. The 2024–2026 literature reports a connected line of lattice PCS constructions: Hwang-Seo-Song 2024, Greyhound (Nguyen-Seiler 2024), Jindo (Hwang-Lee-Seo-Song 2026), Hachi (Nguyen-O’Rourke-Zhang 2026), and Serval (eprint 2025/1903, the optimized successor to the withdrawn HyperWolf (Zhang, Chow, et al., 2025; Zhang, Gao, et al., 2025)). Read the abstracts and identify which paper is the current frontier in three regimes. (a) Univariate polynomial commitment with the lowest proof size at 128-bit PQ. (b) Multilinear polynomial commitment with the lowest proof size at the same target. (c) Lowest verifier time at 128-bit PQ. State the concrete proof size and parameter set the chosen paper reports in each case.
E4. Classify Binius’s commitment scheme (Diamond & Posen, 2025) against the four families of Ch 32. Binius operates over towers of binary fields and commits via a Merkle tree over the codeword of a multilinear polynomial. Does it belong to the Merkle family, the FRI family, a new lattice family, or something else? Justify in one paragraph and state the quantum posture of your classification. Pointer forward: Ch 34 builds the FRI pipeline this classification sits beside, over the prime field F_97 rather than over a binary-field tower, and it does not treat Binius.
Worked solutions and editorial notes for these exercises are in Appendix D, Chapter 32. A separate track, for rebuilding rather than reading: the package exercises/ch32-commitment-schemes has every function the chapter teaches replaced by a stub. Run PQC_IMPL=exercises pytest tests/ch32 to grade your version against the suite that proves the reference one.
References
Section titled “References”Last updated: