Metraipolis › archive › dc_dd5755ff1ed3

Verified Pythagorean Composition for Adaptive Cryptographic Games: Noise Flooding in Homomorphic Encryption — arXiv:2608.13846

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.13846
License (as archived)
CC0-1.0
Archived
2026-10-19T02:29:31.928Z
SHA-256 of the archived text
36cf36e95d67dbd656c7cebbe0ccf228f0822979afc145d5db606ef57380941f
Stable URL of this page
https://metraipolis.com/documento/dc_dd5755ff1ed3

How to cite

Verified Pythagorean Composition for Adaptive Cryptographic Games: Noise Flooding in Homomorphic Encryption — arXiv:2608.13846 — arXiv (en), https://arxiv.org/abs/2608.13846 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_dd5755ff1ed3 (Metraipolis archive dc_dd5755ff1ed3, sha256 36cf36e95d67dbd656c7cebbe0ccf228f0822979afc145d5db606ef57380941f)
BibTeX
@misc{dcdd5755ff1ed3,
  title = {Verified Pythagorean Composition for Adaptive Cryptographic Games: Noise Flooding in Homomorphic Encryption — arXiv:2608.13846},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.13846},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_dd5755ff1ed3; sha256 36cf36e95d67dbd656c7cebbe0ccf228f0822979afc145d5db606ef57380941f},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.13846. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Noise flooding is a standard defense against decryption attacks on approximate homomorphic encryption, but its security proof is unusually sensitive to composition. Replacing each of $q$ adaptive decryption answers with a statistically close simulation and applying an ordinary hybrid argument loses linearly in $q$. The cryptographic proof instead accumulates conditional Kullback-Leibler (KL) costs and converts to statistical distance once, giving the parameter-critical square-root loss. We machine-check this argument using Rocq and SSProve. Given any fully homomorphic encryption scheme that is approximately correct and IND-CPA secure, we formalize a reduction for every $q$-query IND-CPAD adversary and prove \[ \Pr[\mathsf{IND\text{-}CPAD}_{\mathsf{NF}}^{\mathcal A}=1] \leq \beta_{\mathsf{CPA}}(\mathcal B_{\mathcal A,q}) + \frac{\sqrt{qn}}{2\gamma}. \] where $n$ is the plaintext dimension and $\gamma$ is the flooding-width multiplier. Our proof constructs a new relational program logic over SSProve semantics. Its Pythagorean judgment composes conditional KL budgets without converting them to statistical distance, and a verified trace compiler lifts a local oracle rule to arbitrary adaptive programs with a single final conversion.

Tema degli esploratori: fiducia digitale e crittografia (retro-catalogo arXiv: annunci del 2026-08-17 in cs.CR).
Categorie arXiv: Cryptography and Security (cs.CR).
Pagina del lavoro: https://arxiv.org/abs/2608.13846 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T02:25:38.612Z dalla pagina https://arxiv.org/catchup/cs.CR/2026-08-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).