Repository navigation
feat(crypto): prove GSW parameters with logarithmic-depth noise margin #538
Description
A bounded arithmetic/security milestone under #486, alongside the actual decryption-circuit construction in #528. The existing #501 parameter family provides fresh and one-NAND margins. This task supplies a wider-modulus family with a proved growing evaluation-depth budget; it does not assert that augmented decryption fits the budget before #528 establishes its actual depth.
Candidate to verify rather than assume: t = 1 + clog₂(λ+2), n = η = λ+1, w = 16384*t^2, N = (n+1)*w, m = N+2λ, and budget L = 512*t. Prove for every λ that 4*m*η*(N+1)^L < 2^w, the entropy surplus, positivity, and polynomial bounds/native unary routines for n, η, w, N, m, L. The modulus need only have a binary routine; do not incorrectly claim its value is polynomially bounded or unary polynomial-time. Adjust constants with an explicit explanation if required.
Instantiate the existing actual-algorithm IND-CPA reduction under decision LWE for exactly this new parameter family and its centered-binomial law. The old #501 hardness premise does not automatically cover it; no worst-case lattice reduction or circular-security claim is part of this milestone. Preserve the earlier family/API unchanged.
Use representative nonvacuous arithmetic/runtime clients, zero-security-parameter checks, standard axiom guards, all six gates, independent API/correctness review, and an accurate roadmap/catalogue assessment. The remaining #528 obligation is to prove the actual augmented, layered decryption depth is within this budget; if it is not, revise the family rather than weakening the circuit contract. State: available pending claim. AI-assisted decomposition and candidate estimates by worker-codex-gsw-shallow-decryption-20261023.
Activity
SamuelSchlesinger commentedon Oct 23, 2026
Active —
worker-codex-gsw-bootstrapping-parameters-20261023claims this complete arithmetic/native/security milestone. I will usefeat/gsw-bootstrapping-parameters-20261023in a new isolated/private/tmp/complexitylib-gsw-bootstrapping-parameters-20261023clone with private build outputs, based on the reviewed #524 security tree. The existingGSW.ParametersAPI will remain unchanged.Scope: prove the candidate family’s universal growing-depth noise margin, positive dimensions/noise, entropy surplus, efficient unary numerical parameters and binary modulus computation, and the actual-algorithm IND-CPA corollary under decision LWE for exactly the new family. Tests will exercise parameter zero, nonvacuous arithmetic, varying native inputs and headline axiom guards. The obligation that actual augmented decryption fits this depth remains with #528; no such depth, lattice-hardness, or circular-security assumption will be silently supplied. Next: check the numerical inequalities and reuse the existing logarithm/native/security APIs, then implement in a separate parameter module.
SamuelSchlesinger commentedon Oct 23, 2026
Active —
worker-codex-gsw-bootstrapping-parameters-20261023. The proposed constants now satisfy the full strict noise inequality for every security parameter, with native unary parameters, binary modulus and an IND-CPA corollary under exactly the new family's LWE premise. The focused strict regression target passed; the frozen six-file change is in independent review while all six repository gates run. The augmented-decryption depth fit remains #528's separate obligation. Work continues onfeat/gsw-bootstrapping-parameters-20261023in the claimed private checkout.SamuelSchlesinger commentedon Oct 23, 2026
Awaiting review/integration —
worker-codex-gsw-bootstrapping-parameters-20261023. PR #552 is ready, with all six gates passed and independent exact-head approval. It is stacked on #524; integration must retain the later native decryption/NAND roadmap completion from #537. The proved numerical budget does not close #528's actual augmented-decryption depth obligation. Task-owned language servers are stopped and the private checkout/logs are preserved. This milestone remains open until coordinator integration.feat(crypto): prove GSW logarithmic-depth parameter margins
feat(crypto): prove GSW logarithmic-depth parameter margins