The Non‑Commutative Rung of Correlated‑Secret LWE: A Division-Algebra Classifier and a Cyclic-Algebra-LWE Reduction, with a Conditional Worst-Case Foundation

Jeff Pickhardt

Loading document…

The Non‑Commutative Rung of Correlated‑Secret LWE: A Division-Algebra Classifier and a Cyclic-Algebra-LWE Reduction, with a Conditional Worst-Case Foundation

Abstract

A decade of lattice constructions — GGH15 encodings, matrix PRFs, and most recently the Diamond-iO all-product assumption — rest on a pattern nobody has managed to reduce to standard LWE: many samples 𝑐𝑤 = 𝑠𝑃𝑤𝐴 + 𝑒𝑤 from one shared secret 𝑠 and a public family 𝒫 = {𝑃𝑤}. Each 𝑠𝑃𝑤 is marginally uniform, so the whole difficulty is the correlation the shared secret creates — and every bounded-norm hint framework (Hint-MLWE, Extended-LWE, Leaky-LWE) explicitly excludes this case, since the leakage 𝑃𝑤𝐴 is full-magnitude mod 𝑞. When 𝒫 is the orbit {𝑀𝑗} of one matrix the question is known ring theory in disguise. But the families arising in obfuscation are path-products 𝑃𝑥 = ∏𝑖≤𝐿̄ 𝑆𝑖,𝑥𝑖 of non-commuting {0, ±1} matrices, which no ring-LWE theory reaches. That is the case we treat. Our starting point is why the known attack works: the linear distinguisher needs a short integer combination ∑𝑤 𝛼𝑤𝑃𝑤 that drops rank. We therefore make that impossible by algebra, taking the generators to be left-regular images of ℤ-independent elements of an order in a division algebra, where a rank drop would force a nonzero reduced norm to vanish (Lemma R). The work lies in doing this without surrendering either the exact {0, ±1} shape the obfuscation constructions need or compatibility with a hardness theory that already exists. We exhibit a cyclic division algebra of ℚ-dimension 18 achieving both — it satisfies every hypothesis of the Grover–Mendelsohn–Ling–Vehkalahti (GMLV) cyclic-algebra-LWE theorems — and certify it exhaustively. Two lemmas then carry a reduction across: a coset-convolution noise conversion needing no condition on the source covariance (Lemma N), and a spherical-ization bridge (Lemma B), the cyclic-algebra analogue of PRS17. Unconditionally these give a black-box reduction from fixed-spherical decision cyclic- algebra-LWE to the 𝐿 = 2 path-product family; composing with GMLV’s worst-case theorems over a growing family of such algebras bases it on the worst-case hardness of division-algebra ideal lattices — conditional on two interfaces we name but do not prove: GMLV’s full search-to-decision step (H-S2D), contested in the literature, and genericity across the family (H-Gen), verified only at 𝑝 = 3, 5, 7. What this buys is a change in what the assumption is: rather than a bespoke, per-paper conjecture, the 𝐿 = 2 family becomes tied — conditionally — to 𝒜𝑝-SIVP on division-algebra ideal lattices, named objects with their own cryptanalysis. To our knowledge this is the first worst-case-founded reduction of any kind for a non-commutative path-product family. It is not a proof of the Diamond assumption: ℤ-independence provably caps the method at 2𝐿 ≤ 𝑁 , and searched generators essentially attain that cap (certified 𝐿 = 4 at 𝑁 = 18, 𝐿 = 6 at 𝑁 = 100, 𝐿 = 8 at 𝑁 = 294), while Diamond is efficient precisely when 2𝐿 ≫ 𝑁 . The provable and the useful regimes are disjoint — a concrete statement of why all-product LWE remains an assumption rather than a theorem.

File Details

v1 paper.pdf