Corollary 10.1 — a decisional LAR distinguisher for the fixed family yields quantum worst-case and solvers,
ProvedInfoLossLAR.WorstCase.corollary_10_1Consider the fixed public family of §9.9: , , the least prime , , the rounding matrix and quotient encoding of Definition 6.3, so that the decisional LAR experiment draws , and labels .
There are constants , fixed before the adversary, such that with
for every uniform QPT distinguisher on classical inputs, every positive polynomially bounded sample count , every and every infinite set of security parameters with for all , there are a uniform QPT algorithm that solves worst-case and a uniform QPT algorithm that solves worst-case in dimension , for every .
This is the paper's main reduction (Theorem 1.1): quantum worst-case hardness of or on infinitely many dimensions implies decisional LAR hardness for every polynomial sample count.
Differences from the source:
- reading: "uniform QPT distinguisher", "uniform quantum polynomial-time algorithms" →
IsQPT/IsMQPT: uniform Clifford+T circuit families (no advice, fixed gate set) on binary-coded classical inputs, Born-rule measurement of the output wires; reason: the paper names no model - reading: "approximation factor " → fixed before , ; reason: is a constant times a polylogarithmic factor; a larger only makes both problems easier
- reading: "nonnegligible advantage" and "guaranteed only on infinitely many security parameters … succeed on those parameters" → for every and every infinite with advantage on , solvers succeeding at every ; reason: not negligible means infinitely often; the algorithms do not depend on
- reading: worst-case GapSVP/SIVP → nonsingular integer bases in binary, Euclidean norm, rational gap parameter , success probability on every instance, SIVP output = code of integer lattice vectors at the start of the output string; reason: standard conventions of the cited [Reg05], not restated by the paper
- encoding: security parameters → for ; reason: §3.1 indexes families by
- encoding: the third sentence (worst-case hardness implies dLAR hardness) → not a separate clause; reason: it is the contrapositive of the stated implication
- encoding: pp of the fixed family → the code of ; reason: and are determined by
import Mathlib import Definitions.Def_InfoLossLAR_WorstCase_QPT import Definitions.Def_InfoLossLAR_WorstCase_Laws import Definitions.Def_InfoLossLAR_WorstCase_Family import Definitions.Def_InfoLossLAR_WorstCase_LatticeProblems set_option autoImplicit false open QAlgorithms.Complexity
namespace InfoLossLAR.WorstCase
/-- Corollary 10.1 (Worst-case foundation for decisional LAR), p. 60, for the fixed family of
§9.9 (`N = λ`, `σ = λ + 2`, `q` the least prime `≥ 2^{16}(λ + 2)^{64}`,
`d = q(λ + 2)^{96} + 2(λ + 2)^{128}`, `T` and `P = 1ᵀ` of Definition 6.3). There are constants
`C, k ∈ ℕ`, fixed before the adversary, such that with `γ(λ) = C · q(λ) · (log₂(λ + 2))^k`
(`γ = Õ(Nq/σ) = Õ(q)`): for every uniform QPT distinguisher `D`, every positive polynomially
bounded sample count `t`, every `c` and every infinite set `S` of security parameters on which
`Adv^{dLAR}_D(λ, t(λ)) ≥ λ^{−c}`, there are a uniform QPT algorithm that solves worst-case
GapSVP_γ and a uniform QPT algorithm that solves worst-case SIVP_γ in dimension `N = λ`, for
every `λ ∈ S`. -/
theorem corollary_10_1 :
∃ C k : ℕ, ∀ D : Family, IsQPT D →
∀ t : ℕ → ℕ, (∀ lam, 1 ≤ t lam) → PolyBoundedFn t →
∀ c : ℕ, ∀ S : Set ℕ, S.Infinite → (∀ lam ∈ S, 1 ≤ lam) →
(∀ lam ∈ S, (lam : ℝ) ^ (-(c : ℝ)) ≤ famAdvLAR D lam (t lam)) →
(∃ A : Family, IsQPT A ∧ ∀ lam ∈ S,
SolvesGapSVP A (famN lam)
((C : ℝ) * (famq lam : ℝ) * Real.logb 2 ((lam : ℝ) + 2) ^ k)) ∧
(∃ A : MFamily, IsMQPT A ∧ ∀ lam ∈ S,
SolvesSIVP A (famN lam)
((C : ℝ) * (famq lam : ℝ) * Real.logb 2 ((lam : ℝ) + 2) ^ k)) := by sorry
end InfoLossLAR.WorstCase
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.