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

• URL: http://arxiv.org/abs/2608.13846v1
• Date: Fri, 14 Aug 2026 00:40:29 GMT
• Title: Verified Pythagorean Composition for Adaptive Cryptographic Games: Noise Flooding in Homomorphic Encryption
• Abstract summary: Noise flooding is a standard defense against decryption attacks on approximate homomorphic encryption.<n>Our proof constructs a new relational program logic over SSProve semantics.
• Score: 45.00791460144501
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 β_{\mathsf{CPA}}(\mathcal B_{\mathcal A,q}) + \frac{\sqrt{qn}}{2γ}. \] where $n$ is the plaintext dimension and $γ$ 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.

Related papers

• A Complexity-Theoretic Approach to Proofs of Space [5.160781170457704]
  We provide an elementary cryptographic framework for constructing PoS from a combination of derandomization assumptions and cryptographic assumptions.<n>PoS with nearly optimal parameters and interaction pattern follows from assumption (a) above and (c) SNARGs for $mathsfP$.
  arXiv  Detail & Related papers  (2026-08-10T01:28:01Z)
• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  In [AS21], Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in convex optimization cannot be improved by a sparse-time algorithm.<n>We establish their conjectured lower bound for least-squares objectives, conditional on the randomized exact-volume Small-Set Expansion Hypothesis.
  arXiv  Detail & Related papers  (2026-08-03T17:57:01Z)
• Optimizing Explicit Unit-Distance Lower-Bound Certificates [0.0]
  The 2026 disproof of Erds's unit-distance conjecture and Sawin's quantitative refinement show that the maximum number $u(n)$ of unit distances among $n$ planar points can exceed $n1+varepsilon$ for a fixed positive $varepsilon$.<n>This report treats Sawin's parameter selection as a nonlinear integer optimization problem and develops an open-source Python pipeline for certificates involving prime sets $T$ and $S_Q$.
  arXiv  Detail & Related papers  (2026-06-02T10:05:23Z)
• Scaling Federated Linear Contextual Bandits via Sketching [49.12000877146222]
  This paper proposes Federated Sketch Contextual Linear Bandits (FSCLB)<n>Experiments on both synthetic and real-world datasets show that FSCLB significantly reduces computational and communication costs by over 90 %.
  arXiv  Detail & Related papers  (2026-05-01T08:22:06Z)
• Cryptanalysis of the Legendre Pseudorandom Function over Extension Fields [0.0]
  The Legendre Pseudorandom Function (PRF) is a highly efficient cryptographic primitive built upon the Legendre symbol.<n>Recent interest has shifted toward instantiations over extension fields $mathbbF_pr$.<n>This paper presents the first comprehensive cryptanalysis of the single-degree Legendre PRF operating over $mathbbF_pr$.
  arXiv  Detail & Related papers  (2026-04-06T16:35:32Z)
• Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization [85.91302339486673]
  We study robust Markov decision processes (RMDPs) with general policy parameterization under s-rectangular and non-rectangular uncertainty sets.<n>We prove novel Lipschitz and Lipschitz-smoothness properties for general policy parameterizations that extends to infinite state spaces.<n>We design a projected gradient descent algorithm for s-rectangular uncertainty and a Frank-Wolfe algorithm for non-rectangular uncertainty.
  arXiv  Detail & Related papers  (2026-02-11T21:44:20Z)
• Cryptographic transformations over polyadic rings [3.0860863056832826]
  cryptosystems rely on binary operations within groups, rings, or fields.<n>We propose a shift to polyadic rings, which generalize classical rings by allowing operations of higher arity.<n>We present two concrete encryption procedures that leverage this structure.
  arXiv  Detail & Related papers  (2025-12-14T07:15:55Z)
• Compile-Time Fully Homomorphic Encryption of Vectors: Eliminating Online Encryption via Algebraic Basis Synthesis [1.3824176915623292]
  ciphertexts are constructed from precomputed encrypted basis vectors combined with a runtime-scaled encryption of zero.<n>We formalize the method as a randomized $mathbbZ_t$- module morphism and prove that it satisfies IND-CPA security under standard assumptions.<n>Unlike prior designs that require a pool of random encryptions of zero, our construction achieves equivalent security using a single zero ciphertext multiplied by a fresh scalar at runtime.
  arXiv  Detail & Related papers  (2025-05-19T00:05:18Z)
• Post-quantum encryption algorithms of high-degree 3-variable polynomial congruences: BS cryptosystems and BS key generation [0.0]
  We will construct post-quantum encryption algorithms based on three-variable Beal-Schur congruence. We will apply this result to generate simple and secure post-quantum encryption algorithms.
  arXiv  Detail & Related papers  (2024-08-14T14:19:46Z)
• Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
  We study the linear contextual bandit problem in the presence of adversarial corruption. We present a variance-aware algorithm that is adaptive to the level of adversarial contamination $C$.
  arXiv  Detail & Related papers  (2021-10-25T02:53:24Z)
• Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
  We introduce a quantum copy-protection scheme for a class of evasive functions known as " compute-and-compare programs" We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM) As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing"
  arXiv  Detail & Related papers  (2020-09-29T08:41:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.