The 1-Bit Barrier is Universal: k-Stage Pipeline Composition and Unified Leakage Bounds for Standard Modular Reductions in PQC Hardware

• URL: http://arxiv.org/abs/2605.02856v2
• Date: Tue, 05 May 2026 21:03:30 GMT
• Title: The 1-Bit Barrier is Universal: k-Stage Pipeline Composition and Unified Leakage Bounds for Standard Modular Reductions in PQC Hardware
• Abstract summary: This paper closes a series of formally-verified analyses of masked NTT hardware for post-quantum cryptography.<n> Arbitrary-depth $k$-stage masked NTT pipelines with fresh inter-stage masking and per-stage PF-PINI($leq 2$) gadgets satisfy a per-observation cardinality bound of $2 cdot q2k-2$.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This is Paper 7 of a series of formally-verified analyses of masked NTT hardware for post-quantum cryptography; Paper 1 [1] established structural dependency analysis of the QANARY platform, and Paper 2 [2] quantified security margins under partial NTT masking. Arbitrary-depth $k$-stage masked NTT pipelines with fresh inter-stage masking and per-stage PF-PINI($\leq 2$) gadgets satisfy a per-observation cardinality bound of $2 \cdot q^{2k-2}$ on the preimage of any output value, machine-checked in Lean 4 with zero \texttt{sorry}. Under the standard (informal) semantic translation that divides this cardinality by the total mask-tuple space size $q^{2k-1}$, the per-observation conditional probability bound is $2/q$, independent of pipeline depth $k$. The QANARY program has previously established machine-checked cardinality bounds on the per-observation leakage of masked NTT hardware: PF-PINI(2) for Barrett reduction (Paper 5 [3]), 2-stage composition with fresh inter-stage masking (Paper 6 [4]), an underlying universality theorem (Paper 3 [5]), and PF-PINI(1) for butterfly wires (Paper 4 [6]). This paper closes the program with four contributions. First, a $k$-stage composition theorem generalizing Paper 6's two-stage result to arbitrary $k \geq 1$ gives the last-stage-determined bound $G_{k-1}.\texttt{maxMult} \cdot q^{2k-2}$: only the last stage's PF-PINI parameter survives, with intermediate parameters erased by fresh inter-stage masking. Second, Montgomery reduction satisfies PF-PINI(2) with tight max-multiplicity 2. Third, we assemble these into the end-to-end bound $2 \cdot q^{2k-2}$ for any depth-$k$ PF-PINI($\leq 2$) pipeline under fresh inter-stage masking. Fourth, a Lean-verified hypothesis-violation conditional anchors the prior empirical and structural Adams Bridge analyses ([1, 2, 7, 8]).

Related papers

• SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant [79.24089819400126]
  Subsampled TurboQuant (SSTQ) is a framework that combines overcomplete equal-width tight frames, coordinate subsampling, and privacy-aware quantization.<n>SSTQ achieves mean squared error scaling while using only $lceil log N il + b$ bits per client, where $N = (d)$ is the frame size.<n>We also derive a surrogate privacy-aware codebook objective that reduces the codebook-dependent MSE scaling from $O(4b)$ to $O(2b)$.
  arXiv  Detail & Related papers  (2026-08-05T17:51:25Z)
• DeepLoop: Depth Scaling for Looped Transformers [91.7922038545625]
  Looped Transformers scale sequential computation by applying a compact stack of physical blocks for multiple rounds.<n>We formalize this tied-depth effect through a first-order perturbation bound controlled by a visit-alignment coefficient.<n>The resulting method, textbfDeepLoop, keeps the Post-LN DeepNorm architecture and sets $= (2N)1/2$ and $=(8N)-1/2$ for unrolled depth.
  arXiv  Detail & Related papers  (2026-07-15T06:37:05Z)
• A Function-Space Dichotomy for Compositional Learning: Exponential Sub-Optimality of the Neural Tangent Kernel [0.0]
  A persistent empirical observation is that trained neural networks outperform their neural kernel (NTK) limit on tasks with compositional structure.<n>We show a dichotomy between two complexity measures of the target: its $textbfFourier complexity$, which controls NTK kernel regression, and its $textbf complexity$, which controls learning over depth-$L$, width-$w$ ReLU networks with the variation norm of the weights bounded by $R$.
  arXiv  Detail & Related papers  (2026-07-07T15:21:20Z)
• Offline Channel-Independent QAOA Angles for RIS Power Aggregation: Unit-Circle Phase Dictionaries and Infinite-Size Spin-Glass Limits [0.0]
  We introduce a $2M$-phase $$ dictionary for optimizing power on reconfigurable surfaces.<n>We observe performance reaching a near-optimal multi-start single-flip local-search reference for $N!le!16$ under order-2 modeling.<n>The approach suggests a route to near-optimal large-$N$ performance on future fault-tolerant (FTQ) quantum computers.
  arXiv  Detail & Related papers  (2026-06-23T13:07:10Z)
• Prime-Field PINI: Machine-Checked Composition Theorems for Post-Quantum NTT Masking [0.0]
  We prove, to our knowledge, the first machine-checked composition theorems for arithmetic masking over prime fields.<n>For two PF-PINI gadgets with parameters $k_$ and $k$, the composed two-stage pipeline with fresh masking satisfies PF-PINI($k$), Stage 1's multiplicity is completely erased from the composed output.<n>We formally bridge the algebra and hardware-faithful arithmetic models of Barrett reduction, and instantiate the theorems to diagnose Microsoft's Adams Bridge PQC accelerator.
  arXiv  Detail & Related papers  (2026-04-28T17:21:20Z)
• Machine-Checked Cardinality Bounds for Masked Barrett Reduction: A 1-Bit Side-Channel Leakage Barrier in Post-Quantum Cryptographic Hardware [0.0]
  Barrett reduction is the nonlinear core of every practical NTT-based post-quantum cryptography implementation.<n>Existing composition frameworks address masking over GF(2); none provides a machine-checked characterization of Barrett's leakage.<n> PF-PINI satisfies PF-PINI(2); the Cooley-Tukey butterfly satisfies PF-PINI(1).
  arXiv  Detail & Related papers  (2026-04-27T16:27:33Z)
• Fresh Masking Makes NTT Pipelines Composable: Machine-Checked Proofs for Arithmetic Masking in PQC Hardware [0.0]
  Post-quantum cryptographic (PQC) accelerators rely on pipelined Number Theoretic Transform stages over $mathbbZ_q$.<n>Our prior work established structural dependency analysis at scale and quantified the security margin of partial NTT masking.<n>We present three machine-checked results in Lean 4 with Mathlib, all zero sorry.
  arXiv  Detail & Related papers  (2026-04-22T17:19:22Z)
• 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)
• Scaling Up Liquid-Resistance Liquid-Capacitance Networks for Efficient Sequence Modeling [50.994194925685434]
  LrcSSM is a $textitnon-linear$ recurrent model that processes long sequences as fast as today's linear state-space layers.<n>By forcing its Jacobian matrix to be diagonal, the full sequence can be solved in parallel.<n>LrcSSM offers a formal gradient-stability guarantee that other input-varying systems such as Liquid-S4 do not provide.
  arXiv  Detail & Related papers  (2025-05-27T20:02:59Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• On sampling determinantal and Pfaffian point processes on a quantum computer [49.1574468325115]
  DPPs were introduced by Macchi as a model in quantum optics the 1970s. Most applications require sampling from a DPP, and given their quantum origin, it is natural to wonder whether sampling a DPP on a classical computer is easier than on a classical one. Vanilla sampling consists in two steps, of respective costs $mathcalO(N3)$ and $mathcalO(Nr2)$ operations on a classical computer, where $r$ is the rank of the kernel matrix.
  arXiv  Detail & Related papers  (2023-05-25T08:43:11Z)
• Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policies [88.75843804630772]
  We design an algorithm that achieves an $Oleft(mathrmpoly(S,A,log K)sqrtKright)$ regret in contrast to existing bounds. Our result relies on a sequence of new structural lemmas establishing the approximation power, stability, and concentration property of stationary policies.
  arXiv  Detail & Related papers  (2022-03-24T08:14:12Z)

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.