Number Theory and Mathematical Foundations of Cryptography Questions

Brief answer / overview

BKZ is a blockwise lattice reduction algorithm that repeatedly applies an SVP oracle on projected β-dimensional blocks to improve the whole basis. The block size β controls the local-strength of reduction: larger β gives a basis closer to optimal but at exponentially higher cost. The root Hermite factor δ(β) quantifies the average shrinkage per dimension: after BKZ(β) one typically has short vectors of length ≈ δ(β)^n · (det L)^{1/n}.

Heuristic derivation (sketch using Gaussian heuristic + geometric GSO model)

• Gaussian heuristic: for a random full-rank lattice of rank n,

λ1 ≈ (det L)^{1/n} · ( (2 π e) / n )^{1/2}

Intuitively shortest vector scales with the determinant and n.

• Geometric GSO model: after BKZ(β) assume Gram–Schmidt lengths follow a geometric progression

||b*_i|| ≈ ||b*_1|| · δ^{i-1}

so (det L)^{1/n} ≈ ||b*_1|| · δ^{(n-1)/2}.

• Local β-block optimality: within a block of size β the first basis vector should be close to the Gaussian-heuristic shortest vector in that β-dimensional projected lattice. Matching the GH for a β-dimblock to the geometric model yields a relation between δ and β. Solving gives the common asymptotic/heuristic relation δ(β) decreasing as β increases — often expressed implicitly by equating the projected GH length to δ^{(β-1)/2}·(det_proj)^{1/β}.

Practically, this implicit relation is summarized by empirical/asymptotic fits used in cryptanalysis, so practitioners use precomputed δ(β) tables or fitted curves.

How δ(β) yields cost estimates for approximate-SVP in cryptanalysis

• Given target root-Hermite factor δ_target required to break a scheme (from parameter analysis), find minimal β such that δ(β) ≤ δ_target using the heuristic curve.
• Cost of BKZ(β) ≈ number_of_blocks · cost_of_SVP(β). Dominant cost is the β-SVP oracle:
  • Sieving-based SVP: time ≈ 2^{α β + o(β)} with α ≈ 0.292 (classical) or lower with improvements/quantum.
  • Enumeration-based SVP: cost grows super-exponentially in β (practical for small β).
• Therefore cryptanalytic cost ≈ 2^{α β} · poly(n). By mapping δ_target → β via the δ(β) relation, you convert a security target (root-Hermite factor) into an estimated runtime.

Takeaways for cryptographers

• BKZ(β) is the bridge between lattice quality (δ) and computational cost (β-dependent SVP complexity).
• Use validated δ(β) tables/empirical fits and current SVP cost models (sieving/enumeration, classical vs quantum) to produce reliable security estimates.

Clear statement of the reduction

Goal: show "an algorithm A that, given (n,e) and any ciphertext c, returns the unique plaintext m = c^{d} mod n" implies an algorithm F that factors n in probabilistic polynomial time.

Sketch reduction (high-level steps):

• Pick random integer x in Z_n^*. Compute c = x^e mod n and feed c to A to recover x.
• Repeat to obtain several pairs (x_i, c_i = x_i^e).
• Use these decrypted roots to learn the structure of the multiplicative group modulo n: with enough sampled x_i one can compute orders of elements and thereby recover λ(n) (Carmichael function) or φ(n) with high probability.
• Once φ(n) (or λ(n)) is known, compute the private exponent d as the inverse of e mod φ(n), then solve for the prime factors of n by solving the quadratic x^2 − S x + n = 0 where S = n + 1 − φ(n).
• Finally factor n by computing the roots of that quadratic (standard algebraic relation between φ(n) and p,q).

Key assumptions and limits

• A must invert every ciphertext (worst-case inversion); a solver that only succeeds on random ciphertexts (average-case) does not necessarily yield factoring.
• We assume e is coprime to φ(n) (standard RSA key-generation), and that A returns exact, unique roots in Z_n^*.
• The reduction is randomized and polynomial-time (probabilistic polynomial reduction), and may require multiple independent queries to A.
• The reduction is non-black-box in some variants (uses algebraic structure and multiple outputs) but overall is a standard black-box reduction from full RSA inversion to factoring.

Is the reduction tight?

• Not tight in a quantitative sense: the reduction incurs polynomial overhead (multiple oracle calls, group-order computations) and does not give a one-to-one cost equivalence. It shows factoring is at most as hard as worst-case RSA inversion, but not that factoring and RSA inversion are exactly equivalent in complexity.
• Importantly, known proofs require worst-case/full inversion. There are separations: existence of algorithms that invert RSA on a large fraction of inputs (or with non-negligible advantage) need not yield factoring. Thus the reduction establishes a strong relationship but not a tight, lossless equivalence.

Takeaway

• Full (worst-case) RSA inversion implies factoring via group-order / φ(n)-recovery techniques; the result relies on exact inversion on all ciphertexts, is probabilistic, and is not a tight, cost-preserving reduction.

Clarify goal & model

We want the RSA modulus size N such that the best classical attack (GNFS) cost ≈ 2^128 classical “work units.” GNFS running time is expressed in L-notation; use the optimized asymptotic form with the standard constant.

Asymptotic cost (GNFS)

L_N[1/3, c] = exp( (c + o(1)) * (ln N)^(1/3) * (ln ln N)^(2/3) )

For GNFS c = (64/9)^(1/3) ≈ 1.923.

Plain-English: cost grows sub-exponentially in N; to map to 2^128 we solve L_N[...] = 2^128.

Numeric derivation (sketch)

Take logs: set

(c) * (ln N)^(1/3) * (ln ln N)^(2/3) = 128 * ln 2 ≈ 88.72

Solve numerically for ln N → gives ln N ≈ 2120 → N ≈ e^{2120} → bitlength ≈ ln N / ln 2 ≈ 3050–3100 bits. Using more precise constants and practical calibration (using record factorizations and tuned GNFS implementations) yields the commonly cited ≈3072-bit target for 128-bit classical security.

Assumptions & uncertainties

• Asymptotic constant and o(1) terms; finite-size corrections matter for 2–4k-bit N.
• Practical tuning: sieving efficiency, matrix solve improvements, parallel/distributed resources.
• Hardware model: what counts as one “operation” (ASIC, GPU, cloud cost) changes mapping.
• Extrapolation from record factorizations (RSA-768) introduces statistical uncertainty.
• Breakthroughs (algorithmic or engineering) can shift sizes; conservative margins are recommended.

Conclusion

Mapping GNFS to security levels combines the asymptotic formula, numerical root-finding calibrated to practical factorization records and realistic cost models. That derivation — with conservative assumptions about implementation and hardware — yields N ≈ 3072 bits for ≈128-bit classical security, while acknowledging significant uncertainties from constants, parallelization, and future improvements.

Formal definition (search/LWE):

Given modulus q, dimension n, secret s ∈ Z_q^n, and an error distribution χ over Z (or Z_q), the (search) LWE problem is: given polynomially many independent samples (a_i, b_i) with a_i ← U(Z_q^n) and

b_i = ⟨a_i, s⟩ + e_i  (mod q)

where e_i ← χ, recover s. The decision-LWE problem is to distinguish such samples from uniform pairs (a, u) ∈ Z_q^n × Z_q.

Common error distributions:

• Discrete Gaussian D_{Z,σ} (centered, parameter σ): statistically and reduction-theoretically preferred because continuous-Gaussian-to-discrete reductions preserve properties and enable tight proofs.
• Bounded uniform or centered binomial (e.g., Ψ_k): efficient to sample and constant-time friendly; used in implementations (e.g., Kyber uses centered binomial).
• Small fixed-support distributions: simple but sometimes weaker in reductions.

Effect of error rate on hardness vs correctness:

• Hardness: Larger error magnitude (σ) increases reduction to worst-case lattice problems (e.g., GapSVP) — too small errors can make LWE easy (search reduces to linear algebra mod q). Discrete Gaussian with σ ≥ poly(n) / q often appears in reductions.
• Correctness (for encryption/schemes): Larger errors increase decryption failure probability; schemes set q, n, and σ so that errors combine (e.g., during homomorphic ops) but remain below decoding threshold. Trade-off: choose σ large enough for provable hardness yet small enough for negligible decryption failure rate.
• Practical point: design parameters (n, q, σ, error distribution tail bounds) must balance security reductions, implementation efficiency, and provable/falsifiable failure bounds.

Brief answer (role: cryptographer)

Mathematical objects

• Supersingular elliptic curves over F_{p^2}; isogenies (separable homomorphisms) between them; torsion subgroups E[ℓ^k]; endomorphism rings (quaternion algebras for supersingular curves).
• SIDH/SIKE specifically use walks of prescribed ℓ-power degree (typically ℓ=2,3) from a fixed base curve; public keys are target curves plus images of torsion basis points.

Hardness assumption

• The underlying assumption is that given two supersingular curves (and limited auxiliary torsion-image data) it’s hard to find an explicit isogeny between them — formalized as the Computational/Decisional Supersingular Isogeny problems (CSSI/SSCDHP variants) and related path-finding problems in the supersingular isogeny graph. Quantumly, best generic attacks are subexponential in the graph size but not polynomial (prior to recent specialized breaks).

Main attack vectors

• Classical: meet-in-the-middle / baby-step giant-step on isogeny walks (time ~sqrt of search space).
• Quantum: claw-finding / search improvements (Grover/quantum walks) reduce complexities but not to poly-time for generic instances.
• Structure exploits: recovering secret using auxiliary torsion-image points (SIDH provided such points in public keys), leading to algebraic attacks mapping to linear equations.
• Endomorphism-ring computation: if one computes End(E) classically/quantumly, explicit isogenies can be derived via quaternion-algebra techniques.
• Practical: side-channels, fault attacks, implementation pitfalls.

Why promising for compact PQ KEX

• Very small public keys/ ciphertexts relative to lattice/code-based schemes because security is encoded in short isogeny descriptions and a few curve/point coordinates.
• Different hardness foundation than lattices/codes, offering diversification.
• Concrete SIDH design provided efficient Diffie–Hellman-like exchange with relatively small bandwidth.

Caveats / current status

• SIDH/SIKE were optimistic but SIKE was broken (Castryck–Decru 2022) by exploiting torsion-point structure and computing endomorphism rings; this demonstrates structural risks when auxiliary data leaks. Current isogeny research focuses on schemes without those public torsion images (e.g., CSIDH variants, supersingular schemes with different assumptions) and on hardening implementations against algebraic and side-channel attacks.