Repository navigation
feat(crypto): certify native serialized GSW decryption and NAND #527
Description
Part of #486, continuing the actual algorithms from merged #500 / #519. Key generation and encryption now have native certificates; this milestone supplies the deterministic decryption and homomorphic NAND operations needed for evaluation.
Acceptance:
- Define total serialized decryption and NAND programs using the existing secret/ciphertext codecs and the deterministic
GSW.decrypt/GSW.nandsemantics. Reuse the checked modular word and matrix routines; do not infer efficiency from fixed-dimensional finite types. - Prove agreement with the existing typed operations for all input words, including the chosen padding/truncation behavior on malformed words. Preserve exact output widths and handle zero/small widths explicitly.
- Prove uniform native polynomial-time certificates charging unary dimensions, all supplied bitstrings, intermediate values and complete output. Parameter-dependent code or merely polynomially bounded noncomputable parameter functions are insufficient.
- Transport the existing fresh and NAND noise/correctness results to these actual serialized algorithms without strengthening their hypotheses silently.
- Add meaningful clients for well-sized and malformed inputs, native-certificate composition and boundary widths; add headline axiom guards. Run all six checks and obtain independent API/correctness review.
The implementation should use the semantic composition/transfer APIs wherever possible. Record concrete API friction and improve a reusable helper when the client benefit is demonstrated.
This bounded milestone does not claim a full evaluator, shallow decryption circuits, bootstrappability or security of public evaluation keys. The generated-key IND-CPA reduction is separately in #501 / #524; ordinary LWE does not supply circular security. Keep the broader #486 objective open.
Mathematical source: Gentry–Sahai–Waters (2013), with current construction conventions recorded in GSW.Basic, GSW.Noise and GSW.Serialized. AI-assisted task decomposition. State: available; no implementation claim.
Activity
SamuelSchlesinger commentedon Oct 23, 2026
Active —
worker-codex-gsw-decrypt-native-20261023claims the full bounded scope: total serialized decryption/NAND, exact typed bridges, uniform native certificates, correctness transport and regressions. I will work onfeat/gsw-decrypt-native-20261023in the isolated/private/tmp/complexitylib-gsw-native-20261023clone with its private build outputs, based on the reviewed #519 tree. #528's shallow-circuit work remains separate; shared API changes will be coordinated. Next: settle the raw-word contracts and implement them using the existing binary arithmetic and traversal certificates.SamuelSchlesinger commentedon Oct 23, 2026
Shared prerequisite coordinated with #528: worker-codex-gsw-shallow-decryption-20261023 (
/root) authored the exact scalar decoder/typed selected-row identities and raw-input tests. These will be included in this PR with credit, rather than making native decryption wait for the entire shallow circuit. The #527 owner retains implementation/integration ownership;/root/refactor_plan_reviewsupplies independent review. Root is a contributor and will not approve this PR.SamuelSchlesinger commentedon Oct 23, 2026
Active —
worker-codex-gsw-decrypt-native-20261023: the total raw-word decryption/NAND algorithms, exact all-input typed bridges, unchanged-noise correctness transport, and uniform native certificates are implemented in the privatefeat/gsw-decrypt-native-20261023checkout. The root-authored decoder/selected-row prerequisite is included with credit toworker-codex-gsw-shallow-decryption-20261023.MCP diagnostics are clean; the strict focused build of both regression modules passed (6544 jobs). Regressions include signed wraparound, widths zero/one, half-open decoder ties, malformed words, noncommuting NAND products with integer counts, supported positive noise, and an actual growing-input keygen/encrypt/NAND/decrypt PPT client. The 11-file source is frozen for independent review by
/root/refactor_plan_review(manifest SHA2561455ea098c564200546b7e2ec4b4bd663c405bc33d25a8a985ff7491cab53a0b). All six repository gates are now running. Next: address review/check findings, publish the reviewed branch, and hand off for coordinator integration. Complete circuit evaluation, shallow circuits and bootstrappability remain outside this issue.SamuelSchlesinger commentedon Oct 23, 2026
Awaiting review —
worker-codex-gsw-decrypt-native-20261023: PR #537 publishes the complete bounded scope at8504d7fc1a0f942d8e19a0f00c65f2b681bf34a4, treea9b7ed32a53fd7f308e1dfc75c1acc6d0ca59329. This is exactly the tested local tree (ad573b3f10c0c7ae14814a7018d9a38ee4425e5b). All six repository gates passed, with source/tests and roadmap in separate commits./root/refactor_plan_reviewapproved the frozen 11-file source/API/correctness/docs scope with no findings; remote identity confirmation is being recorded on the PR. The root-authored shared decoder files are unchanged from their reviewed hashes. The PR is currently draft pending that final binding; live GitHub reports it mergeable. No full evaluator, shallow circuit, or bootstrappability claim is made. Local artifacts and private build outputs remain in/private/tmp/complexitylib-gsw-native-20261023; review manifest and six-gate log are preserved. Coordinator integration is requested; I will not approve or merge my authored PR.SamuelSchlesinger commentedon Oct 23, 2026
Awaiting coordinator integration —
worker-codex-gsw-decrypt-native-20261023: PR #537 is now ready at unchanged head8504d7fc1a0f942d8e19a0f00c65f2b681bf34a4. Independent API/correctness/docs approval is bound to the published revision and all 11 remote file hashes; all six local gates passed. The title check passed and CI is still running separately. The private checkout is clean and its verified idle Lean/Lake processes are stopped; source, cache and validation artifacts are preserved. No merge or self-approval performed.feat(crypto): certify serialized GSW decryption and NAND
doc(roadmap): record native GSW decryption and NAND
feat(crypto): certify serialized GSW decryption and NAND
doc(roadmap): record native GSW decryption and NAND