All papers (28595 results)

Last updated:  2026-11-13
Multiparty Computation with Minimal Overhead without Circuit Transformation
Aditya Hegde, Phuoc Van Long Pham, and Mingyuan Wang
A central goal in secure multiparty computation (MPC) is to minimize the gap between the total computation performed by all parties and the cost of insecure circuit evaluation. In the honest majority setting, the ideal overhead of $\widetilde{\mathcal{O}}(1)$ is known to be achievable. However, all prior protocols over prime fields attaining this goal for general circuits relied on the so-called share packing techniques and, as a consequence, required prohibitively expensive circuit transformation steps to impose repetitive structure on the circuit. The only exception is the recent work of Garg, Jain, Mukherjee, and Wang (CRYPTO’24), which introduced a share unpacking technique and obtained the first such protocol without circuit transformation. However, their protocol only applies when the underlying field size is extraordinarily large, in particular, exponential in the *square* of the number of parties. In this work, we present the first MPC protocol with $\widetilde{\mathcal{O}}(1)$ overhead for any prime field $\mathbb{F}_p$ (more generally, any integer ring $\mathbb{Z}_p$) whose size is only required to be $n^{\Omega(n)}$, where $n$ is the number of parties (as opposed to $n^{\Omega(n^2)}$). Technically, we extend the unpacking approach of Garg et al. by developing a new approach to linear randomness extraction over integers, a tool that may be of independent interest.
Last updated:  2026-11-13
Byzantine Agreement with Signature Tokens
Yuval Efron, Mahimna Kelkar, Saachi Mutreja, and Tim Roughgarden
We investigate the power and limitations of quantum cryptography in distributed consensus protocols. Specifically, we study the fundamental problem of Byzantine Agreement in partial synchrony, in a setting in which each party has access to a finite number $k$ of signature tokens. Classically, this problem is solvable only when less than one-third of the parties can be faulty (Dwork, Lynch, Stockmeyer 1988). We prove that protocols with signature tokens can bypass this lower bound by designing a protocol that remains secure against up to a $\frac{2^{k+1}-1}{2^{k+2}-1}$-fraction of faults. In particular, with $k=\Theta(\log n)$, where $n$ denotes the number of parties, our protocol solves Byzantine Agreement in partial synchrony assuming only an honest majority. Conversely, we prove that $\Omega(\log n)$ signature tokens are necessary for such a result. Finally, for $k=1$, we prove that the fault-tolerance threshold of $3/7$ achieved by our protocol is the best possible.
Last updated:  2026-11-13
Quadratic APN Functions of $\mathbb{F}_2^{10}$ with a Self-Equivalence of Prime Order
Emanuele Bellini
Almost perfect nonlinear (APN) functions of $\mathbb{F}_2^n$ have the lowest possible differential uniformity. The only known APN permutation in even dimension, in dimension six, is equivalent to a quadratic APN function with a nontrivial linear self-equivalence; no APN permutation is known for even $n \geq 8$. In a published collection of about 3.8 million quadratic APN classes of dimension eight, at most 0.34% have a nontrivial linear self-equivalence. In dimension ten, the 25 literature classes considered here all have one. We study all quadratic APN functions of $\mathbb{F}_2^{10}$ with such a self-equivalence, which usually confines them to a much smaller linear space. Up to conjugacy and power similarity, self-equivalences of prime order have 299 types. We settle 298 of them. Elementary lemmas exclude 280 types, and exhaustive searches confirm this for 242 of them. The other 18 types are settled by exhaustive searches with exact equivalence certificates. Up to extended affine equivalence, the 298 types contain 29 classes of quadratic APN functions, four of them new. This also classifies the quadratic APN functions with coefficients in a subfield. Exactly 24 classes contain one with coefficients in $\mathbb{F}_4$, and all 3 that contain one with coefficients in $\mathbb{F}_{32}$ are among them. The open type consists of the quadratic canonical triplicate functions. They correspond to maximum additive Hermitian rank-distance codes. Three different searches find only the invariants of 16 classes, all among the 29. We conjecture there are no others. No quadratic APN function in the 298 settled types is Carlet-Charpin-Zinoviev equivalent to a permutation.
Last updated:  2026-11-13
FALCON-PARE: Full-Range Side-Channel Key Recovery of Falcon via Prior-Enhanced Evidence
Shuyi Chen, Yuejun Liu, Jingdian Ming, Wei Cheng, Yuhan Zhao, and Yongbin Zhou
Falcon is a compact post-quantum signature scheme selected by the National Institute of Standards and Technology (NIST), and its number-theoretic transform (NTT) computations constitute a critical side-channel attack surface. Existing NTT attacks rely on truncated coefficient ranges and do not cover the full valid range of Falcon secret coefficients, limiting their applicability to complete key recovery. This paper proposes FALCON-PARE, a prior-enhanced evidence framework for full-range key recovery of Falcon. FALCON-PARE combines Falcon's discrete-Gaussian prior with aggregated leakage from range conversion and Montgomery multiplication to construct input-layer soft evidence, which is propagated through the NTT factor graph. FALCON-PARE further uses posterior entropy to select reliable coefficients and public-key relation to complete the remaining unknowns, yielding full recovery of the secret polynomials f and g. We systematically evaluate FALCON-PARE on STM32F407 under -O0 and -O3 compiler settings, validating its practicality in terms of profiling-trace requirements, coefficient-wise accuracy, and residual candidate-space reduction. FALCON-PARE achieves single-trace full key recovery with 40 and 120 profiling traces, respectively. At the comparison budgets, FALCON-PARE achieves absolute gains of 54.79% and 73.83% in coefficient-wise accuracy over existing soft-analytical side-channel attacks (SASCA) for NTT leakage, and reduces the residual candidate space from approximately \(2^{4352}\) and \(2^{5346}\) to one, respectively.
Last updated:  2026-11-13
Homomorphic Encryption and Bootstrapping for Real Matrices over Conjugate-Invariant Rings
Ilaria Chillotti, Hyojun Kim, Yeongmin Lee, Yongwoo Lee, and Damien Ligier
The conjugate-invariant variant of CKKS (CI-CKKS) by Kim and Song encrypts real vectors over the subring of a power-of-two cyclotomic ring fixed by $X \mapsto X^{-1}$, with as many real slots as the rank of the ring. The Gentry–Lee scheme (GL) packs batches of complex matrices into a three-variable ring and multiplies them natively. GL bootstrapping replaces the rotations of the slot transforms with ciphertext–plaintext matrix products. We combine the two lines of work. First, we give a bootstrapping procedure for CI-CKKS: its transforms factor the real decoding matrix into sparse stages, and its modular reduction runs only once, on real slots, and needs no conjugation key. Second, by folding the three GL variables under their inversions, we obtain three subrings that have real slots and are closed under the matrix product; they define $\mathsf{CI}^{1}\text{-}\mathsf{GL}$, $\mathsf{CI}^{2}\text{-}\mathsf{GL}$, and $\mathsf{CI}^{3}\text{-}\mathsf{GL}$. We describe $\mathsf{CI}^{3}\text{-}\mathsf{GL}$ in detail: it encrypts real matrices, needs no conjugation, and, for the same matrix size and number of matrices, has keys of half the rank of GL keys. Third, we adapt the matrix-product bootstrapping of GL to $\mathsf{CI}^{3}\text{-}\mathsf{GL}$. We prototyped these techniques.
Last updated:  2026-11-13
Round-Key Equivalence and Collisions of the Revised MoFang
Zhang zhihong and Liu fengyaxuan
The revised reference implementation of MoFang moves the S-box of the second message half to row 1, which does not eliminate the original per-round key cancellation. Collisions of this type on the original version have been independently reported2,3; this paper does not repeat those findings, and instead proves for the revised version that when the nonzero words of that half are confined to three designated positions, the full message expansion preserves the per-round cancellation, so that every input has 16 round-key-equivalent inputs. The property holds for any common chaining value and transfers to the complete behavior of the six reference variants under full padding, fixed initialization, and XOF output interfaces. Furthermore, the sufficient condition is promoted to a complete classification of the round key map: the common difference of any two equivalent inputs must belong to the original 16 period-two masks, and the equivalence class sizes can only be 1, 2, 4, or 16, with size 16 corresponding exactly to the original domain D0. For the DM variants, necessary and sufficient conditions for all nontrivial equivalence classes are given, together with an exact integer count of the covered domain (log2 ≈ 814.04647); the domain covered by equivalence classes of size at least four admits a three-state matrix counting formula. These results char acterize the equivalence of complete round-key sequences; the domain sizes do not indicate running time or security strength. The object of study is fixed to the 64-bit word model corresponding to the public submission; mathematical proofs, computer-assisted counting, and experimental verification against the reference C code are stated separately.
Last updated:  2026-11-13
Revisiting homomorphic AES evaluation with Hybrid Byte-Bit Packing
Lu Zhang, Xuan Shen, Ruida Wang, Xianhui Lu, Yin Zhang, Chao Li, and Shaojing Fu
Homomorphic AES evaluation is an important benchmark for practical FHE systems. Existing BGV-based AES transciphering schemes typically employ byte-oriented representations, which are well suited for exploiting the algebraic structure of the multiplicative inversion in the SubBytes operation. However, evaluating the affine transformation and subsequent linear layers in this representation introduces additional automorphisms and key-switching operations. In this work, we propose a hybrid byte-bit packing strategy for efficient BGV-based AES transciphering. After performing the multiplicative inversion in the SubBytes operation, we introduce an unpacking procedure to convert the slot packing scheme from byte-oriented to bit-oriented. The affine transformation in SubBytes and subsequent AES linear transformations are unified and evaluated over GF(2) using homomorphic additions, avoiding the key-switching operations involved in the packed byte-oriented evaluation of these linear components. We further optimize the unpacking procedure using a hoisting technique, achieving a 2.5× speedup in unpacking latency compared with the non-hoisted implementation. We implement our approach in HElib and evaluate it under parameters satisfying at least 128-bit security. Experimental results demonstrate per-block latency speedups of 2.6× and 11.7× without bootstrapping, and 2.1× and 3.3× with bootstrapping, on a local machine and a 64-thread server, respectively, compared with the reproduced BGV-based AES baseline under the same software, hardware, and security settings.
Last updated:  2026-11-13
A Note on Non-interactive Deniable Secret Sharing from Indistinguishability Obfuscation
Shafik Nassar
Deniable secret sharing, introduced by Canetti et al. (TCC 2025), protects shareholders when a subset of them is coerced into revealing their shares. Namely, a set of fakers can produce fake shares that are consistent with a fake secret of their choice, and that are indistinguishable from real shares. Very recently, Amores et al. (TCC 2026) studied deniable secret sharing in a setting where the fakers cannot interact to produce their fake shares. Specifically, each faker locally computes its fake share given only its own share, the set of fakers, and the fake secret. Their constructions of non-interactive deniable secret sharing either have shares of exponential size or rely on virtual black-box obfuscation. We show how to upgrade any secret sharing scheme, for any access structure, into a non-interactive deniable secret sharing scheme using a collusion-resistant constrained PRF with static security, which can be instantiated from polynomially-secure indistinguishability obfuscation and one-way functions. Our transformation incurs an additive share size overhead that is polynomial in the number of shareholders. By using indistinguishability obfuscation directly, together with a somewhere-statistically binding hash, we further reduce the overhead to polylogarithmic in the number of shareholders. In combination with prior work on succinct computational secret sharing, we get succinct deniable secret sharing from indistinguishability obfuscation and standard assumptions.
Last updated:  2026-11-12
Early-Stopping Dishonest Majority Broadcast with Optimal Round Complexity
Renas Bacho and Kecheng Shi
Early-stopping broadcast protocols guarantee termination as a function of the number $f\le t$ of parties actually corrupted in an execution, rather than of the worst-case bound $t<n$. Loss and Nielsen (Eurocrypt 2024) gave such a protocol for every $t<n$, terminating within $O(\min\{f^2+1,t+1\})$ rounds, with polynomial communication and from a plain public-key infrastructure (PKI). In the other direction, Choi, Choi, Liu, and Zikas (ePrint 2026/1878) recently proved a stopping lower bound which implies that $f+3$ rounds are necessary whenever $n+f<2\min\{t,n-2\}$, a condition that covers a broad part of the dishonest-majority regime. It has remained open whether this bound can be attained, even at the cost of exponential communication. In this work, we present a deterministic early-stopping broadcast protocol in which every honest party outputs and terminates within $\min\{f+3,t+1\}$ rounds for every $t<n$. The protocol is built from exponential information gathering (EIG) graphs and incurs exponential communication. It works in the plain PKI model with idealized signatures and is secure against a strongly adaptive adversary. Its stopping round complexity is therefore optimal throughout the stated range of the lower bound.
Last updated:  2026-11-12
Limits of Pseudorandom Codes under Adaptive Corruption
Ganyuan Cao
Pseudorandom codes (PRCs) hide messages in strings that look uniformly random to anyone without the decoder key. If the key may be stolen after some codewords have been sent, security requires that these codewords and the stolen key be indistinguishable from uniform strings, chosen independently of the messages, together with a key that decodes each of them to its message. Since such a string carries no information about its message, the key must store the link. We ask how many key bits this takes. We first isolate an information-theoretic object, \emph{$q$-use codes}, whose key and $q$ codewords are generated together and whose codewords are perfectly uniform. We show that every adaptively secure PRC yields a $q$-use code with the same key length, namely its opened key together with the uniform strings it opens. Lower bounds on the key length of $q$-use codes therefore apply to every adaptively secure PRC, and they hold unconditionally, since their proofs involve no hardness assumption. We then show that every opening costs key bits beyond the length of the opened message. Without errors, the key needs $\omega(\log\lambda)$ extra bits to decode the codeword itself; under random noise of correlation $\rho$, it needs $\frac{1}{\rho^2}\cdot\omega(\log\lambda)$ extra bits to decode most noisy copies; and if every error pattern up to a constant fraction of the length must be corrected, it needs, for every alphabet, a constant fraction of the codeword, which we call the robustness tax. Hence, as for non-committing encryption, adaptively secure PRCs need an a-priori bound on the number of openings, but each opening costs more. For non-committing encryption, the cost is the message length, whereas for PRCs, soundness and robustness add a cost on top. We give simple stateful codes that meet these bounds, showing that they are essentially tight, and turn them into stateful PRCs with perfect bounded adaptive security. We finally show that, unlike for non-committing encryption, a programmable random oracle cannot pay this cost under noise. Errors move the decoder's queries away from any reprogrammed point, so for decoders with non-adaptive random oracle queries, every opening must still be paid for in key bits or in reprogrammed points that the decoder reads on a noticeable fraction of inputs. The random oracle thus only relocates the cost.
Last updated:  2026-11-12
RRHL: A Relational Logic for Rényi Differential Privacy of Private Learning
Gilles Barthe and Davide Davoli
Differential privacy is the standard framework for defining privacy-preserving computation and is adopted in large-scale production systems, including industrial-level private learning. The underlying algorithms are based on complex privacy-enhancing mechanisms such as privacy amplification by subsampling and correlated noising. Proving their privacy requires advanced reasoning techniques such as the moments accountant and shifted composition; no existing approach to formal verification supports all of them. In this work, we introduce RRHL: a relational program logic for proving Rényi differential privacy of imperative programs with continuous sampling instructions. Its judgments express bounds on the privacy budgets of instructions as functions of the program states, and its composition of budgets is sharp. We use RRHL to prove differential privacy of the algorithms widely implemented and deployed. These include several variants of DP-SGD and DP-FTRL, and gradient descent with per-record Rényi filters. In several cases the bounds match the best known Rényi differential privacy analyses. The logic, its soundness proof and the case studies are formalized in Lean. To the best of our knowledge, this is the first formal privacy analysis, via a relational program logic, of private learning algorithms with state-of-the-art Rényi differential privacy bounds.
Last updated:  2026-11-12
Sum-Checking SmallWood: Smaller Hash-Based Zero-Knowledge Arguments
Thibauld Feneuil, Killian Provin, and Matthieu Rivain
Hash-based zero-knowledge (ZK) arguments are particularly attractive for their conservative post-quantum security, relying only on cryptographic hash functions. While VOLE-in-the-Head proofs, based on GGM trees, are the most compact for very small witnesses, Merkle-tree-based approaches take over for larger ones. In this regime, the recent SmallWood scheme achieves the smallest proof sizes for witness sizes ranging from $2^6$ to $2^{16}$. In this work, we present SmallWood+, an enhanced variant of SmallWood that leverages sum-check-based protocols to further reduce proof sizes. Following the paradigm of Longfellow ZK, where a hash-based ZK argument is used to wrap the verification of a sum-check-based protocol, we formalize the notion of Sum-Check Verification Constraint System (SVCS), which captures a broad class of such protocols, including GKR for layered circuits and the sum-check protocol for R1CS. We then design generic compilers transforming SVCS instances into ZK arguments from linear commitment schemes and/or multilinear polynomial commitment schemes, which we efficiently instantiate from SmallWood. Along the way, we develop tools of independent interest: hiding multilinear extensions, which make a multilinear evaluation of the committed witness safe to reveal in the small-field regime, a zero-knowledge version of the ring-switching protocol, and an improved circuit-flattening technique for GKR. Applied to (layered) arithmetic circuits, hash functions, and lattice-based statements, our constructions establish new state-of-the-art proof sizes for hash-based ZK arguments - for instance, 18 KB and 63 KB to prove 1 and 100 Keccak permutations, against 29 KB and 127 KB for the best previous schemes.
Last updated:  2026-11-12
Privacy-Preserving Systemic Portfolio Analysis and Repair
Martin Zbudila, Roozbeh Sarenche, Aysajan Abidin, and Bart Preneel
Financial institutions can be exposed to systemic risk through overlapping portfolios and common liquidity shocks, yet identifying and reducing these dependencies requires precisely the portfolio information that institutions are unwilling to reveal. We present, to the best of our knowledge, the first privacy-preserving framework combining system -level portfolio analysis with coordinated portfolio repair. Our approach uses secure multi-party computation (MPC), allowing mutually distrustful institutions to jointly identify systemic vulnerabilities and determine concrete portfolio adjustments without disclosing their underlying holdings. We provide both an MPC realization and a federated variant that moves fund-local computation outside MPC while retaining secure global coordination, and we analyze the additional leakage introduced by this federated design. We implement and evaluate the complete framework on real, publicly available portfolios. Across representative network profiles, private analysis completes in roughly 1–4 minutes and portfolio repair takes 2.6–8.8 hours in MPC and 13–21 minutes in the federated setting. Our results show that both private systemic-risk analysis and coordinated intervention are practically feasible with current MPC technology.
Last updated:  2026-11-12
Batch, Pack, and Prove: More Efficient Verifiable Computation for CKKS
Ignacio Cascudo, Anamaria Costache, Daniele Cozzo, Dario Fiore, Antonio Guimarães, and Eduardo Soria-Vazquez
An important challenge in homomorphic encryption (HE) is ensuring the integrity of the encrypted computations. Although verifiable computation can address this in theory, making it practical is far from trivial. [Cascudo et al. CRYPTO 2025] recently proposed a solution to this problem for the CKKS scheme. In particular, they propose new succinct arguments that efficiently prove arithmetic circuits and range checks over the ring $R_q = \mathbb{Z}_q[Y]/(Y^N+1)$, and combine them to prove computations on CKKS ciphertexts. Despite the important progress, their work faces scalability challenges: the size of the polynomial commitment proofs, a large $O(N)$ overhead in range proofs, and the lack of an explicit method for efficient -- sublinear in circuit size -- verification. In this paper we present new techniques that remove all these bottlenecks. First, we provide a more efficient arithmetization of CKKS computations. Second, we introduce BatchFold, a new polynomial commitment for $R_q$ that supports batched evaluations and achieves shorter proofs. Third, we design packing, a novel algebraic technique that eliminates the need to commit to massive polynomials and removes the $O(N)$ overhead in range proofs. Finally, we introduce SparsePack, an efficient protocol for proving the evaluations of sparse, circuit-dependent polynomials, leveraging both packing and batched evaluations. We evaluate the efficiency of our solution on a generic neural network architecture, achieving proofs several orders of magnitude smaller and faster than prior approaches.
Last updated:  2026-11-16
Toward Efficient Post-Quantum Bitcoin Bridges
Stephen Duan, Vanhger Pham, Blake Hou, Ethan Zhu, and Jingping Yin
BitVM-style protocols verify succinct proofs on Bitcoin by garbling a proof verifier off-chain. What reaches the chain in a dispute is the proof itself: its bits under one-time keys, the scripts that authenticate them and the signatures that bind them to transactions. Existing designs garble elliptic-curve succinct non-interactive argument of knowledge (SNARK) verifiers, which a quantum adversary breaks. Our goal is a post-quantum alternative: a hash-based scalable transparent argument of knowledge (STARK) verifier, garbled and fed with hash-based one-time keys, with no number-theoretic assumption anywhere in the verifier; its price is a far larger proof, and this paper measures and reduces that on-chain data. We compile the complete verifier for WHIR-based STARK proofs from Ziren into a Boolean circuit using free-XOR gadgets for binary-tower arithmetic and Blake3. Our implementation uses Ziren’s binary-field proof stage and narrow recursion. For an Ethereum block proved through four recursion levels, the final recursive WHIR-proof verifier has 175.4M non-free gates and 520,832 input bits, corresponding to 2.81 GB of garbled tables, and publishing that input with translated Winternitz keys takes 3.93 million virtual bytes (MvB), in 41 standard transactions. The costs are coupled: on-chain cost grows linearly with the input bits, off-chain storage with the gate count, and proving time exponentially with the grinding that shortens the input. The WHIR schedule, the Merkle cap depth and the input encoding trade these costs against one another, and a model of proof size and proving time selects the setting, a step toward practical post-quantum Bitcoin bridges.
Last updated:  2026-11-12
Encrypted Authorship Attribution for Fraud Detection
Zita Baronnet and Leonard Schild
Authorship attribution techniques are routinely used to re- late anonymous or disputed texts to known authors through characteris- tic writing styles. Within the financial sector, such techniques may sup- port investigations of phishing campaigns, impersonation attempts, in- vestment scams, or other forms of fraud. More concretely, these methods can be leveraged to determine whether newly observed communications are linked to previously identified actors. In practice, however, both the communications under investigation and the intelligence databases used for attribution may contain sensitive information that cannot be shared across organizational boundaries. In this work, we investigate the privacy-preserving evaluation of sty- lometric authorship attribution through fully homomorphic encryption (FHE). We focus on Burrows’ Delta, a widely studied authorship attribu- tion method based on token frequency statistics and z-score comparisons. We present a homomorphic implementation of Burrows’ Delta, describe a motivating fraud-analysis scenario together with its threat model and trust assumptions, and then analyze the resulting computational com- plexity. Finally, we evaluate the practicality of the proposed approach us- ing the CKKS homomorphic encryption scheme and show that the com- plete pipeline can be executed without bootstrapping while maintaining high numerical accuracy. Our results demonstrate that stylometric au- thorship attribution constitutes a realistic target for privacy-preserving outsourced analytics and illustrate how homomorphic encryption can support confidential fraud investigations.
Last updated:  2026-11-12
Security Analysis of Anonymous Authentication in Apple's Private Cloud Compute
Callista Gratz, Anja Lehmann, and Andrey Sidorenko
Apple's Private Cloud Compute (PCC) offloads on-device computation, such as large language-model prompts, to the cloud while seeking to preserve the privacy users expect from local processing. At its core lies a custom authentication protocol that must reconcile three competing goals: restricting access to registered users within a rate limit, doing so without revealing user identities or linking their requests, and nonetheless retaining the ability to hold misbehaving users accountable. Apple's protocol combines blind RSA signatures in a hierarchical issuance with a salted-hash binding trick, but ships without any formal statement -- let alone proof -- of the guarantees it is meant to provide. In this work we close this gap by abstracting the desired authentication protocol as PORTA -- pseudonymously openable, rate-limited tokens for anonymous authentication. We formally define the desired privacy, security, and abuse-mitigation properties such a protocol should satisfy, including a new binding notion specific to the protocol's two-step issuance. We then cast Apple's protocol in this model and show that it achieves the rate-limiting goal and, with a small modification, all privacy goals. Its abuse-mitigation mechanism, which is not yet active in the deployed system, would however not provide the desired accountability guarantees even once enabled. Finally, we present an alternative construction based on anonymous credentials that provably achieves all properties and verifies the binding of tokens already at the gateway, so that a user's pseudonym is only revealed in case of abuse.
Last updated:  2026-11-12
Triads below the ISA: Optimizing Cryptographic Software in CPU Microcode
Sabrina Manickam, Rowan Fimmano, Peter Schwabe, and Yuval Yarom
Cryptographic software is typically optimized for the instruction set architecture exposed by the processor. Modern processors, however, contain deeper execution layers with computational capabilities and constraints that differ from those of the instruction set architecture (ISA). This work explores the programmable microcode layer in x86 as an implementation target. We characterize the microcode domain as a distinct target architecture for cryptographic computation and adapt implementations to the state, operations, invocation interface, capacity, and scheduling resources it exposes. We instantiate this methodology on Intel Goldmont with Keccak f [1600] and X25519, two case studies with substantially different computational structures. Our Keccak implementation reduces permutation latency by 7.36% relative to the fastest native implementation in our comparison, with the improvement remaining visible in incomplete SHA3-256 computations. For X25519, our microcode multiplication and squaring kernels free the multiplier from fixed operand registers and restrictive carry-flag semantics, outperforming the native implementations we evaluate. The resulting complete X25519 implementation requires 7.3% fewer cycles than s2n-bignum and 9.8% fewer cycles than OpenSSL. Together, these results demonstrate that looking below the ISA exposes a distinct design space for cryptographic implementation and provide a systematic methodology for exploring it.
Last updated:  2026-11-12
Optimized Solving Strategy and Two-Step Estimator for LWE with Hints
Hanbin Yang, Jinzheng Cao, Risheng Yin, and Qingfeng Cheng
Side-channel hints can reduce the cost of solving the Learning with Errors (LWE) problem. We optimize a two-step strategy for LWE with hints that uses BKZ reduction followed by final lattice sieving. Given a lattice constructed from the hints and a specified pair of reduction and sieving algorithms, the strategy jointly selects BKZ block sizes, tour counts, and a final sieving configuration. We also introduce a two-step estimator that predicts the reduced-basis profile and estimates the probability of secret recovery. We combine these estimates with cost models to select a strategy that meets the success-probability and resource constraints. Experiments show that our strategy significantly outperforms the methods of Cao et al. (CRYPTO 2025) and May and Nowakowski (ASIACRYPT 2023). For example, using BLASterBKZ for lattice reduction and the BGJ sieve for final sieving, our strategy recovers the secret for a CRYSTALS-KYBER 512 instance with 190 perfect hints in 7 minutes, compared with 1.6 hours reported by Cao et al. and 7.4 hours reported by May and Nowakowski. With 64 threads, our strategy recovers the secret with 170 perfect hints in 82 minutes. These results highlight the importance of accounting for side-channel leakage when assessing lattice-based cryptographic schemes.
Last updated:  2026-11-12
On the Security of the Cubic UOV Variant CML
Manit Gupta
CML is a cubic multivariate signature scheme proposed over $\mathbb{F}_q$ with $q = 2^8$. Earlier cubic Oil--Vinegar variants such as CUOV and CSSv were broken by differential and high-rank attacks. CML adds an $\ell$-invertible cycle system and a secret position-hiding map to hide the cubic positions. We show that the cubic homogeneous parts of the public key span a space of dimension at most two, so a publicly derived output combination has degree at most two. After restriction to the oil-direction space, the polar matrices of the publicly derived quadratic components span rank-two matrices associated with the edges of a path. This structure yields a procedure for recovering an equivalent key. Our implementation recovered an equivalent key in under 5~minutes for each tested parameter set, including the set targeting 256-bit security.
Last updated:  2026-11-11
The Price of Geometry for Private Distance-Sensitive Filters: $\ell_\infty$ versus $\ell_2$
Paul Cesaretti
A distance-sensitive set representation stores a set $S$ in a metric space and must accept points within distance $r$ of $S$ and reject points farther than $cr$, each with error probability at most $\alpha$. Under differential privacy, even exact membership costs a privacy loss of $\ln(1/\alpha)$; we ask how much \emph{more} the geometry of the space forces. Earlier lower bounds cover only restricted mechanisms, such as partition-based ones or those whose outputs contain no scattered false positives (``dust''). We prove lower bounds for every mechanism. In $\ell_\infty^d$ with $c<3$ the extra cost is $\Theta_c(d)$, which proves a recent conjecture in this range; when $\lfloor cr\rfloor-r+1$ divides $2r$, a randomly shifted grid is optimal up to $\tilde O(\alpha)$ per dimension. In $\ell_2^d$ the extra cost is instead $\Theta_c(\min(d,\ln(1/\alpha)))$: a new mechanism that outputs a single very large ball shows that dimensions beyond about $\ln(1/\alpha)$ are free, so partition-based constructions are optimal in $\ell_\infty$ but not in $\ell_2$. The same arguments bound the space of every correct representation of $k$-sets, private or not: $\Omega(k(\log(1/\alpha)+d))$ bits in $\ell_\infty^d$ with $c<3$, and $\Omega_c(k(\log(1/\alpha)+\min(d,\log(1/\alpha))))$ bits in every $\ell_p^d$.
Last updated:  2026-11-11
BMRaccoon: Blind Multi-Signatures from Lattices
Keerthi Aiswarya Varshini, Kanchan Bisht, Palkesh Jain, Maria Francis, and R. Kabaleeshwaran
Blind multi-signatures (BMS) allow a user to obtain a compact signature on a hidden message through the joint participation of multiple signers, providing a basis for decentralized issuance of anonymous tokens.We present BMRaccoon, the first lattice-based post-quantum BMS construction, with a two-round signing protocol secure under concurrent sessions and signatures syntactically compatible with Raccoon under the sum of the signers' verification keys. As a building block, we introduce MRaccoon, the first Raccoon-based multi-signature and prove its strong unforgeability under the Algebraic One-More MISIS (AOM-MISIS) and MSIS assumptions in the random oracle and and knowledge-of-secret-key (KOSK) model. Our modular security analysis establishes one-more unforgeability of BMRaccoon via a straight-line reduction to the strong unforgeability of MRaccoon, modelling the user's blinding contribution as an auxiliary signer with a zero verification key. We additionally prove blindness against malicious, colluding signers. For up to $q_s = 2^{32}$ signing sessions and $n = 32$ signers, our concrete instantiation yields signatures of approximately $67$ KB and verification keys of approximately $15$ KB.
Last updated:  2026-11-11
From Dependent Ciphertexts to Sharp Bounds for Polynomial Evaluation in BGV
Chiara Marcolla, Nadir Murru, and Matilda Urani
A central challenge in Fully Homomorphic Encryption (FHE) is the selection of ciphertext moduli, which depends on accurately estimating noise growth during homomorphic evaluation. Choosing excessively large moduli reduces the efficiency and scalability of the scheme, whereas underestimating noise can result in decryption failures and potential security vulnerabilities. Average-case analyses have provided promising probabilistic estimates of noise growth in practical FHE computations. However, recent studies indicate that reliable estimates must account for dependencies among ciphertext errors, as neglecting these correlations can systematically underestimate noise. This work presents the first average-case analysis for the BGV scheme that accounts for both correlations induced by secret/public keys and ciphertext dependencies. We propose new variance estimates for the noise coefficients in homomorphic additions and multiplications involving dependent ciphertexts, and extend our framework to the homomorphic evaluation of polynomial functions, which is widely employed in FHE applications. Our theoretical estimates closely align with experimental observations, exhibiting discrepancies smaller than 1.2 bits. Finally, these estimates are adopted to choose the initial BGV parameters, leading to significantly smaller ciphertext moduli compared to those currently adopted in widely used FHE libraries, thus improving the efficiency of the scheme. Compared to OpenFHE, we obtain an average reduction of about 11.5% in the ciphertext modulus size, while relative to HElib, we reduce the ratio between consecutive moduli up to 23 bits per level in practical settings.
Last updated:  2026-11-11
Bulletproofs are Optimal: Lower Bounds for Vector Commitments from Fiat-Shamir in Pairing-Free Groups
Marian Dietz and Emanuele Giunta
Vector Commitments allow parties to commit to an (ordered) vector and to later succinctly open it at any desired position. In plain (i.e., known order and pairing-free) prime-order groups, all state-of-the-art constructions rely on the combination of a generalized Pedersen commitment and an inner product argument. This includes the celebrated constructions of Bootle et al. (EUROCRYPT 2016) and Bünz et al. (S&P 2018), and subsequent improvements. All of these achieve proofs consisting of $\Theta(\log n)$ group elements, and further provide useful properties including malleability, subvector opening and transparent setup. However, breaking the $O(\log n)$ barrier in the plain discrete logarithm setting has proven to be a hard problem. This is in stark contrast with other settings, e.g. from pairing-friendly groups or groups of unknown order, where constructions with constant-size commitment and openings have been known for over a decade. In this work we investigate whether this limitation is inherent to constructions based on prime-order groups. Specifically we prove new lower bounds for any accumulator (a weaker object than vector commitments, thus making our result more general), with interactive public-coin membership proof in Maurer's Generic Group Model. An implication of our result is that in such setting at least one of the following must occur: (i) the commitment has super-constant size; (ii) the opening proof contains $\Omega(\log n)$ group elements; (iii) the opening proof has length $n^{1-o(1)}$. Our bound further extends to primitives that directly imply accumulators/VCs including polynomial/functional commitments and inner product arguments.
Last updated:  2026-11-11
Collision Attacks on SHA-2: 39-Step SHA-256 below the Birthday Bound
Jiaying Gong, Yongzhuang Wei, Fengrong Zhang, and Bohua Wei
SHA-2 is the most widely deployed family of hash functions, and its security margin is measured by the number of steps collision attacks reach. Li et al. gave the first classical collision attack on 38-step SHA-256, with an estimated complexity of $2^{104.3}$. The challenge is to extend the attack to more steps while retaining its advantage over generic collision search. In this paper, we show that collisions for 39-step SHA-256 can be found at an estimated cost below the $2^{128}$ birthday bound. We keep the published 39-step characteristic and change how its conditions are satisfied. We introduce joint message-word pinning, a technique that fixes two expanded message words, $W_{16}$ and $W_{17}$, to the values prescribed by the characteristic. For each chaining value, we solve for assignments to two state words that carry no direct condition, and every assignment returned gives both message words their prescribed values. To find these assignments, we first fix the value of a function with a small image and then solve the coupled equations for $W_{16}$ and $W_{17}$ in sequence. On 39-step SHA-256, pinning $W_{16}$ alone gives an estimated cost of $2^{123.4}$ scalar compressions per expected collision, and pinning both words reduces it by 14.6 bits to $2^{108.8}$. Under the uniform-chaining-value model, the measured probabilities and the cost of processing one first block give an upper bound of approximately $2^{124.6}$ on the expected cost of finding the first collision, even under worst-case clustering. For 38-step SHA-256, we reduce the estimated cost per expected collision from $2^{104.3}$ to $2^{90.9}$ by using a new differential characteristic and pinning $W_{16}$ alone. On SHA-512, pinning $W_{16}$ alone reduces this cost from $2^{125.4}$ to $2^{100.7}$ for 38 steps and from $2^{178}$ to $2^{131.3}$ for 39 steps.
Last updated:  2026-11-11
Anamorphic NIZK: Definition, Construction and More
Wenhui Kong, Gongxian Zeng, and Zhengan Huang
Anamorphic encryption enables covert communication despite disclosure of ordinary decryption keys~\cite{PersianoPY22}. Work on anamorphic signatures extends this capability to settings permitting only authentication and shows that Fiat-Shamir preserves anamorphism~\cite{kutylowski2023anamorphicSignatures,fiat1986prove}. However, this result assumes an already anamorphic protocol and does not by itself ensure witness privacy against the recipient, motivating anamorphism directly in non-interactive zero-knowledge proofs (NIZKs). We introduce anamorphic NIZK (ANIZK), in which publicly verifiable proofs carry covert messages recoverable with a double key. The framework formalizes anamorphic security, strong robustness, and recipient anamorphic zero knowledge and simulation extractability. A generic construction in the random oracle model combines suitable Sigma protocols with authenticated encryption with associated data through a salted Fiat-Shamir transform. Applying ANIZK within the Naor-Yung paradigm \cite{NaorYung90} yields recipient anamorphic encryption satisfying STE-xCCA1, SIND-aCCA1, and SIND-nCCA security under the notions of~\cite{choi2026unified}. Finally, an asymmetric variant of ANIZK, termed ASY-ANIZK, combines a labeled NIZK with public-key encryption satisfying ciphertext pseudorandomness and random ciphertext rejection. It separates public embedding from secret recovery and achieves weak robustness, as public embedding precludes strong robustness.
Last updated:  2026-11-11
HIT: Single-Pass Inference for Single-Trace NTT Side-Channel Attacks
Yihan Nie, Yuxuan Wang, Yubo Zhao, Zixin He, Wenjing Zheng, Jintong Yu, Shifeng Sun, Chi Zhang, Pei Cao, and Dawu Gu
In physical implementations of the post-quantum standards ML-KEM and ML-DSA, the Number-Theoretic Transform (NTT) directly processes secret polynomials and is a primary target for single-trace side-channel key recovery. Existing Soft Analytical Side-Channel Attacks (SASCA) apply loopy Belief Propagation (BP) over cyclic $\mathbb{Z}_q$ factor graphs, where BP fails under high noise and $O(q^2)$ updates make ML-DSA infeasible. We present the Hierarchical Inference Tree (HIT), a framework built on the insight that small secret inputs deterministically fix all NTT intermediates across the recursive butterfly network. Instead of loopy BP, HIT merges and prunes candidate inputs from leaves to root in a single pass on an acyclic binary tree. This approach eliminates belief oscillation, guarantees a constant runtime, and decouples complexity from $q$. On ML-KEM-768, HIT runs over $900\times$ faster than state-of-the-art SASCA and more than doubles noise tolerance. HIT also enables the first single-trace analytical attack on the ML-DSA NTT and recovers each polynomial in under one second. On physical ARM Cortex-M4 targets, HIT achieves over 98% polynomial recovery across both standards with only 20 to 80 profiling traces.
Last updated:  2026-11-11
Tightly Secure and Modular Post-Quantum TLS Handshakes
Biming Zhou, Jinrong Chen, Haodong Jiang, Rongmao Chen, and Yunlei Zhao
In the post-quantum (PQ) migration of the TLS~1.3 handshake, the classical Diffie--Hellman key exchange is replaced with a post-quantum key encapsulation mechanism (KEM). Furthermore, KEMTLS builds upon PQ TLS~1.3 by replacing signature-based authentication with KEM-based authentication. However, all existing analyses of PQ TLS~1.3 and KEMTLS incur at least quadratic reduction losses in the number of sessions, and achieving a tightly secure construction remains an open problem. To address this gap, we present the first unified, tight, and modular reduction framework for PQ TLS~1.3 in the standard model and KEMTLS in the random oracle model (ROM). Our framework tightly reduces the security of these protocols to the security of three core components: (i) the MUC-IND-1RCCA or MUC-IND-1CCA security of the underlying ephemeral KEM, (ii) the MU-(dual)-PRF security of HKDF (for PQ~TLS~1.3), and (iii) the MU-EUF-CMA$^c$ security of the signature scheme (for PQ TLS~1.3) or the MUC-OW-ChCCA$^*$ security of the static KEM (for KEMTLS). Furthermore, we establish the first concrete MU-(dual)-PRF bounds for HMAC and HKDF in the quantum-accessible random oracle model (QROM). Instantiating this framework with tightly secure LWE-based KEM and signature schemes yields the first (almost) tightly secure constructions of PQ TLS~1.3 and KEMTLS under the LWE assumption. Moreover, our framework demonstrates that the weaker IND-1RCCA security notion for the ephemeral KEM already suffices to achieve security for both PQ TLS~1.3 and KEMTLS, thereby enabling simpler instantiations.
Last updated:  2026-11-14
Affine Combiners for Reed-Solomon Proximity Gaps
Alessandro Chiesa, Guy Weissenberg, Eylon Yogev, and Kai Zhe Zheng
Reed–Solomon proximity gaps establish soundness guarantees for protocols that test received words through random combinations. For length-$n$ codes over $\mathbb{F}_q$, classical scalar combiners achieve error $O(n/q)$ in the unique-decoding regime, with larger known bounds near the Johnson radius. We prove smaller error bounds using affine combiners, which combine two received words $f,g$ as $f(x)+(\alpha+\beta x)g(x)$, where $\alpha,\beta$ are independent uniform elements of $\mathbb{F}_q$. For output degree bound $d=\rho n$, fixed $\rho\in(0,1)$ and $0<\eta<1-\sqrt{\rho}$, and sufficiently large block length $n$, we prove mutual correlated agreement (MCA) with one coordinate of agreement loss at threshold $A=\lceil(\sqrt{\rho}+\eta)n\rceil$, with error $O_{\rho,\eta}\left(\frac{1}{q}+\frac{n^2}{q^2}\right)$. The result holds over arbitrary evaluation domains in every finite field, including prime and binary extension fields. The agreement threshold can approach the Johnson threshold, beyond unique decoding. For $q\ge n^2$, our error is $O_{\rho,\eta}(1/q)$, an asymptotic factor-$n$ separation from scalar combiners: we prove that their worst-case MCA error is $\Omega_{\rho,\eta}(n/q)$ at the same agreement threshold and with the same one-coordinate loss. We also prove that affine combiners incur worst-case error $\Omega_{\rho,\eta}(n/q)$ when no agreement loss is allowed. Thus one coordinate of agreement loss is necessary for our guarantee; this relaxation of standard MCA reduces the guaranteed common agreement fraction by at most $1/n$. We also extend the result to $k$-variate Reed–Muller codes on subfield grids, obtaining MCA error $O_{\rho,\eta,k}(q^{-k})$ for fixed $\rho,\eta,k$, sufficiently large $n$, and $q\ge n^{k+1}$, with agreement loss $n^{1-1/k}$.
Last updated:  2026-11-16
An improvement to the KLPT2 algorithm
Abel Laval
In this short note, we present a tweak to the KLPT2 algorithm that reduces the size of the output from $O(p^{15.5})$ to $\tilde O(p^{14.5})$.Then, we show that the recent improvement by Nakagawa, Yoshizumi and Onuki to the KLPT algorithm is compatible with the Hermitian module splitting approach, further lowering the reduced degree bound to $\tilde O(p^{14})$.
Last updated:  2026-11-10
$\mathsf{SVP}_\infty$ Is NP-Hard for Power-of-two Cyclotomic Ideals
Yansong Feng, Jiaqi Liu, Hengyi Luo, and Yanbin Pan
We prove that exact decision-$\mathsf{SVP}$ in the coefficient $\ell_\infty$-norm is $\mathsf{NP}$-complete for principal ideals and free modules of rank two over the cyclotomic rings $R_n=\mathbb{Z}[X]/(X^n+1)$, where $n$ ranges over powers of two. For each case, we give a deterministic polynomial-time many-one reduction from the Subset Sum problem. For an instance with $s$ positive input integers, the output lattice has dimension $O(s)$. A solution to the original Subset Sum instance can be recovered in polynomial time from any nonzero output lattice vector of norm at most the specified bound. We also transfer these reductions from $R_n$ to the power-of-two cyclic rings $S_{2n}=\mathbb{Z}[X]/(X^{2n}-1)$. This gives $\mathsf{NP}$-completeness of decision-$\mathsf{SVP}$ in the coefficient $\ell_\infty$-norm for principal ideals and free modules of any fixed positive rank over these rings.
Last updated:  2026-11-10
Delegatable Keyed-Verification Anonymous Credentials
Omid Mirzamohammadi, Varesh Mishra, Jan Bobolz, Emad Heydari Beni, Aysajan Abidin, Dave Singelée, and Bart Preneel
Keyed-verification anonymous credentials (KVACs) are a variant of anonymous credentials (ACs) in which the issuer and the verifier are either the same entity or mutually trusted entities. Due to this design, KVACs can avoid some of the practical burdens of publicly verifiable ACs, such as requiring bilinear pairings, making them more practical in certain settings. Delegation of credentials is a powerful feature that enables applications where users, holding a credential, can delegate a restricted version of their credential to another user. This paper proposes the first delegatable keyed-verification anonymous credentials (DKVAC). We provide formal definitions of DKVAC, we design two pairing-free DKVAC constructions with delegation capability, we prove them secure, and we demonstrate their practicality with implementation benchmarks. Our two constructions present trade-offs between expressiveness and performance.
Last updated:  2026-11-10
A Single-Trace Side-Channel Attack on the KpqC Digital Signature Scheme AIMer v3
Jinnuo Li, Yiteng Sun, Chi Cheng, Weijia Wang, and Hao Cheng
The Korean Post-Quantum Cryptography (KpqC) competition selected AIMer, a post-quantum digital signature scheme based on the MPC-in-the-Head paradigm, as one of its final algorithms in 2025. However, detailed side-channel analysis (SCA) of AIMer remains limited, particularly for its latest version, AIMer v3. In this paper, we present, to the best of our knowledge, the first side-channel attack on AIMer v3. Specifically, we demonstrate a single-trace power analysis attack using deep learning to exploit power leakage from bits of the secret preimage during the computation of AIM3's input affine layer. Using a ChipWhisperer-HuskyPlus, we recover the full secret key from a single signature on an ARM Cortex-M4 processor with a success rate of 100%. We further evaluate the attack performance under different noise levels and propose potential countermeasures.
Last updated:  2026-11-10
Revisiting Fiat-Shamir NIZKPs and Signatures from Seed-Friendly Sigma Protocols
Andrea Flamini, Federico Pintore, and Edoardo Signorini
Seed-friendly sigma protocols have a small challenge space, and when compiled into NIZKP, they require parallel repetition to reduce extraction error. Fiat-Shamir proofs obtained from seed-friendly Sigma protocols can be made more compact with fixed-weight parallel repetitions, and seed-tree compression. So far, these have been presented as compression techniques for the proof size, but standard analysis of the extraction property of NIZKP still relies on the Forking Lemma and rewinding. In this work, we show that not only fixed-weight parallel repetition and seed-tree compression improve the compactness of the proofs, but also improve their security. Interestingly, when the prover randomness is generated from a salted seed tree, interacting with a random oracle, the standard Fiat-Shamir compilation is straight-line extractable in the classical random-oracle model, without any additional proof field or proof-of-work. We further show that the Fiat-Shamir NIZKP from seed-friendly Sigma protocols satisfies multi-proof zero knowledge, and that its straight-line extractability does not require the underlying seed-friendly Sigma protocol to have unique responses.
Last updated:  2026-11-10
When One Bit Is (Almost) Enough: A Low Leakage Chosen Plaintext Side Channel Attack on AES
Antoine Wurcker
In order to thwart Side Channel Attacks (SCA) and keep secret safe, countermeasures such as masking can be implemented to hide information. However, when a defect occurs in software or in hardware, a portion of the information may still leak. If the leak is sufficient, the state-of-the-art techniques can still be performed up to a potential brute force search to cover a missing part. However, if only a short portion of the information leaks, the completion of the attack can be hard, and considered as failed. In this paper, we describe a new chosen plaintext strategy on AES algorithm to recover the secret key even in very low leakage condition. As an example, but not limited to, we describe the methodology adapted to one of the worst case scenario: only one bit position leaks over the 128-bit output of SubBytes AES sub-operation along rounds. As a drawback, a heavier cost in terms of number of traces is required due to the chosen plaintext approach.
Last updated:  2026-11-10
A New Class of PRFs and Efficient VRFs from Isogeny-based Group Actions
Junbo Yang, Willy Susilo, Dung Hoang Duong, Partha Sarathi Roy, Yannan Li, Kazuhide Fukushima, and Shinsaku Kiyomoto
Polynomial-in-exponent pseudorandom functions (Poly-style PRFs) based on group actions have recently emerged as a promising framework for post-quantum cryptography, offering compact keys and efficient verifiability. However, the security of these constructions over composite-order class groups remains poorly understood. Prior work suggested that security is governed by the largest prime factor of the group order. In this work, we show that this intuition is flawed. We present two generic attacks demonstrating that the effective security of Poly-style PRFs is determined instead by the smallest prime factor of the group order. As a consequence, existing parameter choices, including CSIDH-512 and SCALLOP-based settings used in recent VRF constructions, are insecure. Our enhanced attack achieves advantage close to one with complexity $O(\sqrt{p})$, where $p$ is the smallest prime factor of the group order. To address this inherent vulnerability, we introduce a new design paradigm, {\em restrict-then-expand}, and formalize a general class of multivariate polynomial PRFs (\textsf{MP}-PRFs) from group actions. The key idea is to eliminate exploitable structure via carefully restricted input domains, and then recover expressiveness through a provably secure expansion technique. We show that \textsf{MP}-PRFs unify and generalize existing constructions, including Naor-Reingold-style and Poly-style PRFs (with restricted input domains), while achieving security in the generic group action model with twists ($\mathrm{GGAM}^{\mathsf{T}}$) for arbitrary composite-order groups. In addition to this, our construction supports flexible polynomial-size input spaces with fixed output length and admits efficient and compact proofs of correct evaluation. Building on this framework, we obtain new group-action-based VRFs that are both practical and provably secure. At a proof-soundness level close to 128 bits, our VRF instantiation requires 320 group-action evaluations for either proof generation or verification, compared with approximately 69,000--109,500 group-action evaluations in prior work, while retaining short keys and proofs. Overall, our results establish a robust and efficient approach to constructing post-quantum PRFs and VRFs from group actions, resolving fundamental limitations of existing Poly-style designs.
Last updated:  2026-11-10
DetTreeChain: Parallel Block Production on an N-ary Block Tree with Bounded Lane Divergence
Mahesh Karri and Nikhileswara Rao Sulake
Nakamoto-style blockchains append one block at a time to a single chain, and raising the block rate increases forking and weakens security. We present DetTreeChain, a ledger in which up to $N$ blocks are produced in parallel and placed without later merging or reordering. Blocks form an $N$-ary tree in which each block's slot follows from its parent and its lane. A locally derived Parent Queue Pool lets only two consecutive parents receive children, so lanes never drift more than one parent apart, and links between consecutive blocks of a lane make each lane a hash chain. As in several earlier designs, transactions are routed by what they spend, here a hash of the spent locking scripts, so blocks of different lanes cannot conflict and payments to other lanes need no cross-lane protocol. The rules are consensus-agnostic. Under proof of work, miners choose their lane, and an adversary with more than $1/(N+1)$ of the total hash power can outpace one lane. In a 25-minute run of our Rust prototype, six nodes converged on identical trees and difficulty targets, and 65% of slots were filled against 63% predicted. In simulation with delays of 5% of the lane interval, a single chain at the same block rate wasted 1.7 to 3.3 times as much work as 2 to 8 lanes, although nodes more often held later-discarded blocks. Among Bitcoin transactions whose spent scripts could be rebuilt, about 95% kept their inputs in one lane, mostly because they spend a single output.
Last updated:  2026-11-10
Homomorphism in Expectation: Leveled Homomorphic Encryption with Range-Relative Correctness
Zeyu Liu, Xianhui Lu, Ruida Wang, and Xinxuan Zhang
Lattices have dominated the development of homomorphic encryption for deep computation. We introduce $\textit{Homomorphism in Expectation (HIE)}$, a new construction showing that encrypted addition suffices for both addition and multiplication in deep real-valued computation. Given any additively homomorphic encryption scheme over $\mathbb{Z}_2$, we construct range-relatively correct leveled homomorphic encryption for arithmetic circuits $C$ of $\textit{arbitrary}$ polynomial depth. For depth bound $d$ and any chosen public input bound $r>0$, our scheme supports inputs in $[-r,r]$. Outputs lie in $[-\eta_C,\eta_C]$, where $\eta_C=C(r,\ldots,r)$ is the circuit's maximum output range magnitude over this input range. Decryption returns an answer with error at most $\varepsilon\cdot\eta_C$ except with probability $\delta$. Each input requires $\ell_{\mathsf{in}}=O(d+\log(1/\varepsilon))$ base ciphertexts, and each output requires $\ell_{\mathsf{out}}=O(\varepsilon^{-2}\log(1/\delta))$ base ciphertexts. For $n$ inputs, online evaluation uses only ${\sim}\ell_{\mathsf{out}}\cdot n\cdot\ell_{\mathsf{in}}$ ciphertext additions and ${\sim}\ell_{\mathsf{out}}\cdot |C|\cdot\ell_{\mathsf{in}}$ memory accesses. Our construction begins by encoding real-valued inputs as encrypted bitstreams, allowing multiplication through encrypted bit addition. The direct approach incurs costs exponential in circuit depth, limiting efficient evaluation to logarithmic depth and requiring non-compact input ciphertexts. We overcome these limitations with new encoding and circuit evaluation techniques, which eliminate the exponential overhead, enabling compact homomorphic arithmetic at arbitrary polynomial depth from additive encryption alone.
Last updated:  2026-11-10
ASCENT: Algebraic Structured Compilation of Exact Norms for Succinct Lattice Proofs
Lizhen Zhang, Shang Gao, and Bin Xiao
Norm bounds are semantic constraints in lattice cryptography: satisfying the modular equations is not enough unless the witness also satisfies the prescribed shortness bound. Existing norm reductions either introduce slack, or rely on general sumcheck style machinery whose transcript cost grows with the witness length. We introduce a reduction-of-knowledge compiler for exact $\ell_2$-norm constraints. It compiles the original norm language for a committed lattice witness into a narrow structured relation consisting only of commitment-opening constraints, tensor-structured witness-public inner-product claims, and relaxed admissible shortness bounds. Exact norm soundness is enforced inside the reduction, so the remaining proof obligation is structured and algebraic. The compiler adds only $O(1)$ prover-to-verifier communication, measured in ring and field elements, independent of the witness length $N$, and requires only $O(\log N)$ verifier work. The same techniques can also extend to a folding mechanism for broader quadratic relations, including R1CS-type circuits. At $128$-bit security, our concrete estimates give transcripts of about $27.69\mathrm{KB}$ for exact norm reduction and $27.75\mathrm{KB}$ for the R1CS folding application. This is about $3$--$4\times$ smaller than LatticeFold+, about $2$--$3\times$ smaller than SALSAA, and remains close to the compact estimates reported for Cyclo.
Last updated:  2026-11-12
A Tutorial on Oblivious Random Access Memory
Elaine Shi and Srinivas Devadas
Abstract—Oblivious RAM (ORAM) is a key technique for pro- tecting memory access patterns in systems with untrusted mem- ory, including secure processors, trusted execution environments, and multi-party computation. This article presents a tutorial overview of ORAM concepts and designs from an algorithmic and cryptographic perspective. We review the security goals and threat models underlying ORAM, describe the most popular ORAM constructions and their core mechanisms, and discuss practical considerations for implementing ORAM. The tutorial aims to provide readers with a clear foundation for understanding ORAM-based memory protection and its applications.
Last updated:  2026-11-10
Bounding the security of the Bromberg-Shpilrain-Vdovina hash function
Eilidh McKemmie
The Bromberg-Shpilrain-Vdovina hash functions are a family of Cayley hash functions indexed by an integer parameter $k\ge 2$. Hashes are matrices in $SL_2(p)$ where $p$ is a large prime. We present an attack which finds collisions of length $O(\log p)$ whose average-case time complexity is $O(p^{0.28})$ when $k=2$ and $O(p^{0.36})$ when $k=3$ under an assumption in the spirit of Zaremba's Conjecture on continued fractions. This is an improvement on the more general attacks of Mullan-Tsaban and Slaughter which have average-case time complexity $O(\sqrt{p})$. For any $k$, the average-case time complexity of our attack is $O(p^{1-\delta_k+o(1)})$ where $\delta_k$ is the Hausdorff dimension of a certain Cantor set. This tends to $O(\sqrt{p})$ as $k\to\infty$, so our attack has time complexity comparable to Mullan-Tsaban and Slaughter's attacks as $k$ grows. We give examples of collisions for large primes found by our attack when $k=2, 3$.
Last updated:  2026-11-10
Neural Cipher Bench: Cost and Portability of Corner-ReLU Cipher Implementation
Siwoo Eum, Minwoo Lee, Gyeongju Song, Seungwon Lee, Uijae Kim, Doyun Park, Minseo Kim, Wai Kong Lee, Zhe Liu, Anupam Chattopadhyay, and Hwajeong Seo
Edge and Internet of Things (IoT) devices run neural networks on GPUs, neural processing units (NPUs), and microcontrollers (MCUs) through machine learning (ML) runtimes. Deep Neural Cryptography (DNC, EUROCRYPT 2026) expressed AES as a bit-exact ReLU network with fixed weights, using a corner-ReLU construction that keeps the cipher inside the affine+ReLU operators such runtimes execute. What this construction costs on edge and IoT hardware, and whether real ML backends execute it correctly, had not been measured. We implement SM4, ARIA, Camellia, and ChaCha20 (spanning substitution–permutation, Feistel, and add–rotate–XOR structures) alongside AES on a shared corner-ReLU core under one construction policy, derive a cost model for width, depth, and neuron count, and measure five execution paths on four platforms. All ciphers admit bit-exact networks whose width and depth diverge with cipher structure, and the model's width predicted where GPU throughput drops. Every configuration passing the correctness check fell below its classical baseline (best 0.80×, SM4 on the GPU), by hundreds to thousands of times for the S-box ciphers on the MCU, and keeping the activations on chip through fusion raised throughput 1.4–3.5× and moved the peak past the predicted cache limit without closing the gap. Some AES configurations on the Apple Neural Engine returned valid-looking but incorrect outputs with no error or warning, a failure reproduced in a minimal graph without project code. Mathematical bit-exactness therefore does not guarantee backend-level bit-exactness, and exact workloads offloaded to edge NPUs require output validation.
Last updated:  2026-11-08
γ₁₁: Unequal Triangles and Adapted References — the macadamia 0050
Rémi Géraud-Stewart and David Naccache
This paper settles the ninth of the ten macadamias of the series on the Hermite constant in dimension 11: the perfect form $P$ = 0050:024468269 of rank 9, of determinant 8192/9 at minimum 4. The root paper reduces $\gamma_{11}$ to chains $L\supset M\supset N$ of lattices of ranks 11, 10, 9, each with minimum at least 4; we prove that every admissible chain whose rank-9 member is admissibly marked by $P$ has $\det L\ge 972$. No argument at rank 10 can do this, because an actual lattice of rank 10 with determinant $3328/3<4\cdot 972^{9/11}$ lies over $P$. The proof is computer-assisted, with explicit finite checks. Its decisive step is elementary: the three additive dual vectors of a section covector and the first normal usually have different lengths, and keeping the three lengths in the circle obstruction, instead of their maximum, gives a determinant cap that sharpens every subsequent contact and spectral bound. Adapted reference forms turn the contact conditions into exact rational tests, a common slack is retained throughout, and four computational results reduce the problem to a five-parameter root, exhausted by a finite cover of 6 993 terminal regions replayed in exact arithmetic.
Last updated:  2026-11-09
TUTTI: Parallel CKKS Bootstrapping in under 3 ms on CPU
Robin Köstler and Antonio Guimarães
This paper introduces TUTTI, a new CKKS bootstrapping procedure that outperforms previous low-latency solutions in multi-threaded latency for any number of messages and, most notably, has a lower latency than TFHE when bootstrapping a single one. Our bootstrapping builds upon SPRU (CK, TCHES 2027), improving it with new methods for exploiting parallelism and increasing the number of messages, as well as with a refined security analysis, of independent interest, of the block-binary secret keys of LMSS (AsiaCCS 2023). \tutti bootstraps $4096$ real-number messages in $46$ to $83.4$ ms on $192$ threads to restore $1$ to $9$ multiplicative levels, outperforming SHIP (CHKS, Eurocrypt 2025) by a factor of up to $3$ on the same machine. Unlike SHIP, TUTTI gains immediately from bootstrapping fewer messages, with a $256$-message bootstrapping taking just $15$ to $34$ ms on $32$ threads. For a single message, TUTTI takes $4.6$ ms on $32$ threads, whereas TFHE-rs needs $7.3$ ms for a $4$-bit bootstrapping on the same machine and thread count. We show that this advantage persists across different architectures: on an Apple M5 Pro laptop (ARM), TUTTI takes $2.4$ ms on $14$ threads, against $4.5$ ms for TFHE-rs. Differences between CKKS and lightweight schemes such as TFHE remain on several fronts, from functionality to key sizes and security assumptions, but our work shows that multi-threaded latency is no longer one of them, closing a long-standing gap in the practical FHE literature.
Last updated:  2026-11-09
Access Cost Tradeoffs in Mixed-Mode Oblivious RAM
Wojciech Ciszewski and Emanuele Ragnoli
A mixed-mode oblivious RAM (ORAM) lets each memory request be marked public or private: public requests disclose their addresses, private requests hide them. We ask how much work such a scheme must do, and which requests must do it, in the cell-probe model—with a passive server that only reads and overwrites addressed words. We examine the expected amortized per-request cost on randomized workloads with independent modes and uniformly random addresses. For array size $n$ and client memory $m\le n^{1-\varepsilon}$ words, let $H=\log_2(2+n/(m+1))$. Our main result is a tight tradeoff between the cost of public reads and private writes. We show that if a request is private with probability $0<p\le1/2$ and private requests cost at most $Q$ probes on average, then every scheme with $m\le n^{1-\varepsilon}$ has expected public-read cost\[ \Omega\!\left(\max\left\{1, \frac{H}{\log_2(2+1/p+Q/H)}\right\}\right), \]even when the server learns the kind (read/write) of each private request. For polynomial $m$, we provide constructions that match this bound whenever $Q$ exceeds a threshold that we identify for both $Q$ treated as an expectation over the workload and as the average cost for the worst-case workload. In particular, at constant private frequency $p$ a logarithmic private budget forces logarithmic public-read cost, and constant public-read cost requires private cost $(n/(m+1))^{\Omega(1)}$. This answers, for passive servers, the question posed by Zhang, Wang, and Weng, whose PIR-based scheme achieves constant public and logarithmic private bandwidth with server computation. Our lower bound proof fixes the public query and changes its private history; crucially, we charge them separately. Our constructions combine a public cache with linear merges of hash tables. Two further groups of results concern public writes and total work. Firstly, we give a cost tradeoff between public writes and private reads. Secondly, for workloads mixing private operations, public reads, and public writes with probabilities $p,r,a$, we show that every scheme with $m\le n^{1-\varepsilon}$ has total cost per request $\Omega(\max\{1,H/\log_2(2+1/p)\})$ when private request kinds are hidden, and a construction with polynomial client memory matches this bound with a constant independent of $p,r,a$. We also separately bound the costs of reads and writes in this workload. Lastly, public requests can in some cases be made cheaper by offloading their cost to preparation in earlier requests or cleanup in later ones. For both public reads and writes, we show localized tradeoffs constrained to a subset of requests, which demonstrate some of the limitations of such offloading.
Last updated:  2026-11-09
The isodual constant of the LLL potential: exact values and structure
Nick Howgrave-Graham
The LLL potential $\Psi^2(B)=\prod_k\det\mathrm{Gram}(b_1,\dots,b_k)$, minimized over the bases of a lattice $L$ and normalized by its determinant, defines an isodual lattice invariant $\eta(L)$. Its supremum $\eta_n$ over $n$-dimensional lattices, introduced in ePrint 2007/105, is the staircase case of the generalized Hermite constants of Watanabe and Meyer, for which explicit values were known only for $n\le4$. We prove that $\eta_5=6$, attained only by $D_5$ and its dual: the flag analogue of Korkine and Zolotarev's value of $\gamma_5$. The natural reduction to four-dimensional lattices, through a function $\Phi_5$, does not suffice: the global maximum of $\Phi_5$ is $2^{16}/(3^4\cdot5^3)\approx6.4727$, attained not at $D_4$ but at an even $135$-modular lattice $M_*$, which we have not found in the literature. A second stage, over the lifts of the remaining region, completes the proof; both stages are computer-assisted, with about $9\times10^9$ leaves, each re-proved in interval arithmetic by a separately written checker; code and data are public. We also prove $\eta_8=2304$, attained by $E_8$, and show that $E_6$, $E_7$, $E_8$ and their duals are strict local maxima of $\eta$ (for $n=6,7$ these are the conjectured extremal lattices). Asymptotically, $\log\eta_n=(\frac14+o(1))\,n^2\log n$. For lattice reduction we introduce the $\Psi$-Hermite constant $\mu_m$, the largest first Gram–Schmidt norm in a potential-minimal basis of an $m$-dimensional lattice, and bound it through $\eta_m$. This gives $\mu_m=\gamma_m$, Hermite's constant, for $m\le5$, and $\mu_m\le\exp(O(\log^2 m))$ in general.
Last updated:  2026-11-09
On Composing Oracle Separations
Willy Quach and Felix Rohrbach
Black-box separations constitute very powerful technical barriers against constructing primitives from specific building blocks. However, they give surprisingly little indication on the usefulness of \emph{combining} several such building blocks in a single construction. We propose a set of technical conditions, under which (fully) black-box separations compose with each other. That is, if two black-box separations $P_1 \stackrel{BB}{\nRightarrow} Q$ and $P_2 \stackrel{BB}{\nRightarrow} Q$ satisfy our conditions, then $Q$ is also separated from black-box combinations of $P_1$ and $P_2$. When applicable, these conditions can be established without unpacking the full technical details of the base separations. As our main application, we show that combining indistinguishability obfuscation (iO) with collision resistant hash functions is unlikely to yield hard problems in the complexity class $SZK$, and thus unlikely to suffice for primitives such as lossy functions or fully homomorphic encryption. Previous lower bounds on iO only applied to combinations of iO with one-way permutations (Asharov-Segev, FOCS '15 and Bitansky-Degwekar-Vaikuntanathan, SIAM Journal on Computing '21).
Last updated:  2026-11-09
Antipodal necessity for rotation symmetric bent functions of degree at most three
Filipe Martins Vono
The conjecture that every homogeneous rotation symmetric bent Boolean function has degree two remains open in general. We prove a necessary condition that settles the degree-three case of this conjecture. Let $n>0$ be even. If a rotation symmetric Boolean function of degree at most three in $n$ variables is bent, then its algebraic normal form contains the antipodal quadratic orbit $\sum_{i<n/2} x_i x_{i+n/2}$. A homogeneous cubic has no quadratic terms, so no homogeneous rotation symmetric cubic Boolean function is bent, in any even number of variables. The condition also applies to nonhomogeneous functions with arbitrary lower-degree terms compatible with rotation symmetry; it neither classifies these functions nor addresses degree four and higher. The proof uses only finite Fourier analysis and linear algebra over the binary field. Restriction to the fixed space of a rotation of odd order reduces the problem to a power-of-two number of variables. There, Parseval's identity and a rigidity property of rotation symmetric quadratic forms impose incompatible conditions on a single fiber of the function. A second proof replaces the final fiber argument by descent through a single unipotent Jordan block. Examples illustrate the hypotheses. A Lean formalization of the original proof is provided as supplementary material; the Jordan proof has not been formalized.
Last updated:  2026-11-09
Adaptively Secure (Threshold) Batched IBE from Static Assumptions
Sourav Das, Pratish Datta, Aditi Partap, and Swagata Sasmal
Batched identity-based encryption (batched IBE) lets a key authority release one short decryption key for a set of identities and a batch label/epoch. It has been used to mitigate maximal extractable value (MEV) attacks on public blockchains. Existing constructions either use the generic-group and/or random-oracle models, or rely on $q$-type assumptions whose size grows with the batch-size bound. In this paper, we present the first adaptively secure batched IBE scheme from static assumptions. Our scheme supports an exponential identity space and an exponential epoch space, and its ciphertexts, digests, and batch keys consist of a constant number of group elements independent of the batch size. Our scheme relies on composite-order bilinear groups, and we prove its adaptive security assuming hardness of static subgroup decision assumptions and a static pairing assumption, with a security loss polynomial in the security parameter $\lambda$ and the number of key queries. Our proof does not rely on $q$-type assumptions, random oracles, generic-group arguments, or complexity leveraging. We also present a threshold version with adaptive challenge security under static corruption, and translate our scheme to prime-order bilinear groups under the static MDDH assumption.
Last updated:  2026-11-09
Enabling Memory Encryption Using Ascon Derivatives
Sergej Deutsch, Christoph Dobraunig, David Durham, Simon Johnson, Krystian Matusiewicz, Carlos Rozas, and Alexander Tereschenko
Keeping data stored in memory confidential is a tough challenge when assuming an adversary with physical access to it. First, we have fine-grained access to typically 256 to 512 bits at once, so nonces or tags of the typical sizes used for authenticated encryption would lead to a sizeable overhead. Second, we have stringent performance requirements, including low latency that directly impacts CPU performance and, more generally, strict area and energy constraints, especially for the high bandwidth of memory interfaces. Currently, memory encryption solutions typically rely on the AES block cipher. In this paper, we explore ways of using Ascon as a building block for memory encryption. Our analysis shows that Ascon-based constructions achieve better performance than AES-based HCTR2 and can also compete with XTS-AES while providing larger block sizes.
Last updated:  2026-11-09
SEC: One-Share Everywhere-Short Secret Sharing from Lossless Expanders
Muhammad Arzaki, Muhammed F. Esgin, Amin Sakzad, and Ron Steinfeld
We introduce \(\mathsf{SEC}\), an expander-code-based ramp secret sharing scheme over \(\mathbb{Z}\)-modules, particularly suitable for lattice-based distributed cryptography. It is everywhere-short: bounded secret coefficients yield bounded share coefficients, and the integer reconstruction vectors have bounded entries. Moreover, each participant receives exactly one share, regardless of the number of parties and the privacy and reconstruction thresholds. This improves on prior schemes with bounded share coefficients and bounded entries in the integer reconstruction vectors, in which the number of sub-shares or shares per participant grows either with the number of parties and the threshold or with the security parameter. The construction rests on a coding-theoretic observation: in the bi-adjacency matrix of a lossless bipartite expander, unique-neighbor peeling completes every sufficiently small set of columns to a square unimodular submatrix. We prove correctness, everywhere-shortness, and linearity, and give a publicly computable entrywise bound on the reconstruction vector our algorithm returns for each authorized set. For privacy, we introduce hard-core local leakage resilience, which strengthens the leakage-resilience notion of Nielsen and Simkin (EUROCRYPT 2020) to protect a hard-core function of the secret, and we prove that \(\mathsf{SEC}\) satisfies it against correlated multi-query local leakage under the \(\mathsf{MatrixHint\text{-}MLWE}\) problem, which admits a reduction from the standard \(\mathsf{MLWE}\) problem. For \(n=60\) participants and security parameter \(\kappa = 128\), \(\mathsf{SEC}\) achieves privacy threshold \(6\) against \(2^{64}\) leakage queries and empirical reconstruction threshold \(46\). The ideal entropy-coded secret and share sizes are about \(3.5\) KiB and \(6.4\) KiB, respectively.
Last updated:  2026-11-09
MPCTM: MPC-Based Trajectory Matching on Unmanned Autonomous Systems
Dominik Roy George, Martin Zbudila, and Barry Van Leeuwen
Emerging technologies such as Unmanned Autonomous Systems (UASs) are increasingly being deployed across several application domains. Their deployment, however, introduces safety risks, especially when unmanned vehicles operate in shared operational spaces (e.g., air, land, or maritime) and may follow collision-prone paths. This creates the need for solutions that can detect possible collisions among pre-planned trajectories, thereby improving operational safety and reducing risk. At the same time, revealing trajectories in plaintext leaks sensitive information, such as traversal patterns, deployment and infrastructure locations, and potentially private user data. In this paper, we present a privacy-preserving trajectory matching protocol based on Multi-Party Computation (MPC). We introduce an end-to-end secure scheme for collision detection that reveals no information beyond the prescribed output. Our solution models the behaviour of UASs along their paths, accurately capturing collisions that may occur between discretely sampled points. We further propose a lightweight, MPC-friendly model and discuss the trade-off between accuracy and efficiency for the two approaches. We provide a proof-of-concept implementation of our scheme and compare it to the closest state-of-the-art solution. Our evaluation shows that our work MPCTM, in the dealer mode, improves the online latency upon previous work by over 2x in our modelled protocol and by 8x in our lightweight protocol. In autonomous mode, our protocol results in a slow-down of 2.5-3x, while providing a more expressive model with no false negatives and fully preserving privacy of the trajectory data.
Last updated:  2026-11-09
Practical Confidential Clustering for Federated Learning using Efficient Secret-Sharing
Cédric Prigent and Sonia Ben Mokhtar
Federated Learning (FL) often suffers from statistical heterogeneity, where diverging data distributions prevent a single global model from achieving high utility for all participants. Clustered Federated Learning (CFL) addresses this problem by grouping similar clients to train personalized sub-models, yet performing such clustering while ensuring strict confidentially with minimal communication overhead remains a significant challenge. This paper introduces CCFL, a framework for Confidential Clustering that executes clustering logic, including distance computations and centroid updates, entirely within the encrypted domain using Replicated Secret Sharing (RSS). CCFL orchestrates a unified pipeline that integrates client-side feature extraction, an anonymization server for oblivious shuffling, and Multi-Party Computation (MPC)-based clustering to ensure both input privacy and participant unlinkability. By employing a ring-based Euclidean distance optimization, CCFL significantly reduces interactive rounds, achieving up to $46.7\times$ computational speedup under realistic LAN and WAN constraints. Our one-shot clustering approach decouples heavy cryptographic computation from the training loop, allowing the system to scale seamlessly to thousands of clients with negligible edge overhead. Finally, downstream evaluations confirm that CCFL achieves a superior privacy-utility trade-off, matching or outperforming state-of-the-art personalized FL paradigms without exposing sensitive feature geometries.
Last updated:  2026-11-09
DKG: A Dual-Layer Knowledge Graph and LLM Co-Driven Framework for Fully Automated Side-Channel Analysis of Cryptosystems
Wenquan Zhou, An Wang, Yaoling Ding, Jiakun Li, Jingqi Zhang, and Liehuang Zhu
Cryptographic algorithms underpin billions of devices, from payment smartcards to smartphone secure enclaves and industrial controllers. Yet their physical implementations risk leaking secret keys. Non-profiled side-channel analysis (SCA) evaluates whether such leakage enables key recovery, but executing it end-to-end remains expert-intensive. Large language model (LLM) agents now automate complex workflows across many domains, yet reliable key recovery requires specialized SCA knowledge that must be extracted and organized from scattered technical literature. In this paper, we propose DKG, a dual-layer knowledge graph and LLM co-driven key-recovery agent framework. We introduce the first graph schema designed specifically for SCA: an upper layer of configuration components and a lower layer of diagnostic strategies, joined by cross-layer relationships. An LLM-driven three-step extraction pipeline (Locate & Rewrite, Triple Extraction, and Knowledge Fusion) builds the graph from raw technical documents without manual annotation, and at runtime the retrieved knowledge drives a closed-loop autonomous attack workflow. Built from a corpus of 166 technical documents, the graph contains 1,334 entities and 1,813 relationships. On eight datasets covering AES, DES, and SM4 across smartcards, FPGAs, and MCUs, DKG with DeepSeek-V3.2 achieves a 97.5% end-to-end key-recovery success rate. By comparison, ReAct-RAG, a text-retrieval-augmented agent, achieves only 68.8%. Across the open-weights backbones DeepSeek-V3.2, GLM-5, and Qwen3.5, DKG achieves an average success rate of 93.3%. To the best of our knowledge, DKG is the first framework to achieve consistent end-to-end automated key recovery across diverse implementations. Its automated pipeline lets the graph grow with new literature, and its dual-layer organization provides a basis for extending DKG to additional SCA techniques.
Last updated:  2026-11-09
Adaptive Leaky LWE and Its Security
Chuanqi Zhang, Muhammed F. Esgin, and Ron Steinfeld
The Leaky LWE problem, proposed by Lai, Swarnakar, and Woo (CiC '25), studies whether LWE samples remain pseudorandom in the presence of noisy linear information about their secrets and errors. In Leaky LWE, the leakage matrix may depend on the public matrix, but must be chosen before the LWE challenge is revealed. We study $t$-round adaptive Leaky LWE, where each leakage matrix may depend on the challenge and all preceding leakage answers. Under explicit norm, smoothing, and sampling conditions, we reduce Gaussian-secret LWE to this problem at the corresponding source parameters for polynomially many rounds. The reduction preserves the public-matrix distribution and access to its correlated oracle, and supports rectangular leakage matrices and non-spherical discrete Gaussians over arbitrary orders in number fields.
Last updated:  2026-11-09
Doubly-Efficient Private Information Retrieval from Modular Forms
Alexandra Henzinger and Seyoon Ragavan
We present new information-theoretic protocols for $s$-server, doubly-efficient private information retrieval (PIR) in sublinear server time and one extra bit of space on the servers, for every constant $s \geq 2$. On an $n$-bit database, each of the $s$ PIR servers first builds and stores a preprocessing data structure consisting of $n+1$ bits (which is unique to each server, and after which the server may discard the original database). Then, each server answers a PIR query in time $T_s(n)$, by reading at most $T_s$ bits of its data structure and sending them to the user. In the two server setting ($s=2$), our PIR protocols achieve $T_2 = n^{0.82}$, matching the server time of the state-of-the-art schemes of Henzinger and Ragavan (EUROCRYPT 2026) while shrinking their storage from $O(n\sqrt{\log n})$ to $n+1$ bits. With $s \geq 3$ servers, our PIR protocols retain the $n+1$ bits of storage and additionally improve on the server time of all prior information-theoretic $s$-server schemes with $n^{1+o(1)}$ storage: for example, achieving $T_3 = n^{0.74}$ and $T_{10} = n^{0.61}$ (previously $n^{0.79}$ and $n^{0.75}$). Asymptotically, as the server count $s$ grows, we shrink the number of servers required to achieve a given server-work exponent from $s^{3.9}$ to $s$. Our results draw inspiration from matching-vector techniques (Efremenko, STOC 2009), which we generalize to handle degree-two computations in the exponent. Using this generalization, we build doubly-efficient PIR from the new intermediate abstraction of Fourier-sparse cone-delta functions. Then, we construct such Fourier-sparse cone-delta functions via a connection to modular forms and complex analysis: if a Fourier-sparse cone-delta function does not exist, then there exists a modular form which has too many roots, contradicting the valence formula.
Last updated:  2026-11-13
Multi-Hop Functional Encryption
Pratish Datta, Jiaxin Guan, Alexis Korb, and Amit Sahai
In this paper, we initiate the study of multi-hop functional encryption ($\mathsf{MHFE}$), a new primitive for computing over encrypted data in recursive and multi-stage workflows while enabling controlled release of intermediate outputs. $\mathsf{MHFE}$ supports dynamic directed-acyclic computation graphs in which each node is labeled by a function and is equipped with a restricted secret key that reveals only that node's output, yet the computation can continue downstream on a forwardable encrypted state. In doing so, $\mathsf{MHFE}$ simultaneously overcomes (i) multi-hop fully homomorphic encryption's need for a globally trusted, always-online decryption key to reveal intermediate values, (ii) standard FE's lack of a native mechanism for forwarding reusable encrypted state across stages and handling evolving datasets without a fresh recomputation, and (iii) Multi Party Computation's deployment friction stemming from interaction and liveness/coordination requirements (at the cost of a central key-issuing authority). We formalize $\mathsf{MHFE}$ security via the simulation paradigm extending standard FE collusion resistance to the multi-hop setting; this simulation-based notion captures the intended information flow in recursive computations most accurately by characterizing an adversary's entire view as simulatable given only the authorized intermediate outputs. Our security games impose a natural topological-order on queries: a hop key for a node may be requested only after the ciphertexts/keys on all incoming edges to that node have been fixed. We then give the first generic simulation-secure construction of public-key $\mathsf{MHFE}$ for all polynomial-size circuits from any IND-secure standard FE for circuits.
Last updated:  2026-11-08
Undine: Distributed Extendable Merkle Tree Storage with Private Retrieval and Efficient Reconfiguration
Nicolas Alhaddad, Harry Eldridge, Julia Guskind, Eran Tromer, and Mayank Varia
Clients of transparency logs, public-key directories, and shielded blockchain pools require authenticated access to an ever-changing Merkle tree, without storing it in full or revealing which entry they open. We seek to distribute storage and query work across independent servers as the data grows and participants join, leave, change their shares, or misbehave. We present Undine, which combines a distributed Merkle tree encoding with private retrieval from independently-maintained fragments. Maintainers can choose and efficiently adjust the size of their stored fragments, to offer a flexible tradeoff against the number of maintainer replies needed for authenticated data reconstruction by clients. Maintainers can also perform authenticated updates and appends, at a write cost of just twice the number of modified Merkle nodes. Undine uses a linear encoding of the Merkle tree nodes to divide evenly the storage and retrieval load across maintainers. This is combined with a private information retrieval (PIR) protocol that operates directly over the linearly-encoded fragments. Undine avoids repeated storage and computation for nodes shared by Merkle paths across records, producing the same PIR replies with work over tree values linear in the filled prefix. Record sizes adapt as the prefix grows to balance query and reply sizes. Clients verify against the Merkle root, without commitments to individual PIR databases. Computational query privacy holds against any coalition. Undine is also secure against selective-failure leakage (i.e., deductions from acceptance), up to the PIR backend's correctness error, given enough timely honest replies, fixed public timing, and no reply-dependent follow-up. We evaluate UndineLog, our append-only implementation of Undine combined with YPIR. On a height-50 sparse Merkle tree with a 4GiB prefix of nonempty 32-byte leaves and a reconstruction threshold of 64, a maintainer replies in 100ms (single-core); a client can process 192 replies from maintainers and reconstruct a verified opening in 380ms, even with 64 corrupted replies. Scaled up to 1TiB and 256 threshold , a maintainer answers in 1.13s. Existing shielded pools can use this service without consensus changes.
Last updated:  2026-11-08
The Closest Vector Problem on Gadget Lattices: Efficient Algorithms and Voronoi Geometry
Daniele Micciancio
Gadget lattices are a prominent family of lattices widely used in lattice-based cryptography, error-correcting codes, and computational complexity. We present efficient algorithms for the Closest Vector Problem (CVP) on power and CRT gadget lattices and their duals, handling arbitrary real-valued target vectors. For the parity-check power gadget lattice, we give a practical, deterministic O(n) linear-time exact CVP solver based on a new, specialized "deferred greedy" graph-cut technique. Through an explicit characterization of the Voronoi cell, we provide a comprehensive analysis of existing decoders: we prove that the standard BDD algorithm of Micciancio and Peikert (2012) unexpectedly solves CVP exactly for odd base b and integer targets, but degrades to a worst-case approximation factor of n^0.5 for binary base b=2 and continuous targets. Furthermore, we prove that standard pruned sphere decoding requires exponential time exp(Omega(n)) even when using a geometrically optimal basis. For the dual (generator) power gadget lattice, we construct an obtuse superbasis---proving for the first time that it is a lattice of "Voronoi's first kind"---which yields a polynomial-time O(n^3) exact CVP algorithm via graph min-cut reductions. Geometrically, we determine all successive minima and enumerate the facets of their Voronoi cells. In particular, we show that while the parity-check lattice has a sparse Voronoi cell with n^2+n facets, the generator lattice reaches the theoretical upper bound of 2(2^n-1) facets. Finally, we observe that CRT gadget lattices and their duals admit an orthogonal basis, yielding trivial linear-time CVP algorithms.
Last updated:  2026-11-08
An Agile Homomorphic Encryption and ML-KEM Scheme for Privacy-Preserving Health Data Processing
Daniel RESENDE, Nadia El Mrabet, and Ulrich Kühne
The storage and processing of health data raise serious privacy con- cerns; therefore, the data must be encrypted. Fully Homomorphic Encryption (FHE) allows computations on encrypted data, which makes it a very promising technology in this context. However, although the efficiency of FHE algorithms has improved in recent years, they remain very complex. The security of several prominent FHE schemes is based on variants of the Learning With Errors (LWE) problem, which is also the basis of Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM), the new post-quantum standard for asymmetric encryption. In this paper, we propose an agile cryptographic scheme – combining ML-KEM and BGV – that allows efficient implementations in an embedded use case. We describe the parameter selection for the proposed scheme and show its feasibility with a proof-of-concept implementation.
Last updated:  2026-11-08
Twisted Towers: A Faster and Fully Costed SexTNFS Attack
Gautam Botrel
We study the Special exTNFS attack on discrete logarithms in the target group $\mathbb{G}_T$ of BLS12-381. We give a (6,2) design in which every step is priced in one instruction-level model: relation collection, cofactorisation, filtering, linear algebra, the Block Wiedemann generator and both individual logarithms, at success probability at least 0.39. The design rests on an explicit twisted tower. The sextic base field has an involution $\sigma$ and a unit $c$ with $c\,\sigma(c)=-1$, so $\tau:(y,x)\mapsto(\sigma y,cx)$ has order 4 and acts on $\mathbb{F}_{p^{12}}$ as $\mathrm{Frob}^3$. Relations and ideals then come in orbits of four. The quotient linear system has Gaussian-integer entries read modulo $r$, and ten Schirokauer maps suffice. A norm-2 element of the base field enables a coset sieve. We also observe that yield estimates over TNFS coefficient cubes count unit multiples $(\varepsilon a,\varepsilon b)$ as distinct relations. For the valid polynomial pair closest to the published BLS12-381 design, only $2^{-2.81}$ of the smoothness-weighted cube points give distinct relations. Under stated heuristics the ledger is $2^{115.72}$ dense $\mathbb{F}_{p^{12}}$-multiplication equivalents, about $2^{130}$ AArch64 instructions. Under our instruction model and transferred pricing assumptions, the design is estimated to cost 0.74 to 1.08 bit less (about 0.8) than a fundamental-domain version of the published design. Under the published cost models the difference ranges from 0.57 bit in our favour to 0.19 bit against. Nothing was run at full size, and the practical security of BLS12-381 is unchanged.
Last updated:  2026-11-08
γ₁₁: One Selected Contact, Two Linked Blocks — the macadamia 0030
Rémi Géraud-Stewart and David Naccache
This paper is one of five companion papers completing the proof of $\gamma_{11}=4/\sqrt[11]{972}$ announced in the root paper and assembled in “A Focus on Hermite Constant 11”. The root paper reduces a lattice of rank 11 with minimum 4 and determinant below 972 to a chain of sections of ranks 11, 10 and 9 whose rank-9 member is admissibly marked by one of 4 487 813 perfect forms; ten of them, the macadamias, lie under an actual lattice of rank 10 and need proofs of their own. We settle the first, the form 0030:030301719 of $\Lambda_9$ under $\Lambda_{10}$, where the bound has little margin. The argument selects one contact of the reference lattice from the actual metric, keeps the off-diagonal column shared by two eight-dimensional blocks of the section metric, applies one determinant–trace theorem to both blocks, and closes with a rational cover of three scalar parameters. The proof is computer-assisted: its finite inputs are three outer-range covers, two middle-range covers with 10 498 and 1 140 leaves, an annulus tree with 3 567 leaves and four smaller trees, every leaf checked in exact rational arithmetic.
Last updated:  2026-11-08
γ₁₁: Reduction by Sections — the macadamias 0019 and 0017
Rémi Géraud-Stewart and David Naccache
The root paper of this series reduces the value $\gamma_{11}=4/\sqrt[11]{972}$ of the Hermite constant in dimension 11 to a statement about chains $L\supset M\supset N$ of lattices of ranks 11, 10 and 9 whose rank-9 member lies over one of 4 487 813 perfect forms of rank 9; the $\gamma_{11}$ paper settles all of them but ten, the macadamias. This paper settles two of the ten: 0019:030884313 (the form $P_S$ of the root paper, an extension of $E_8$ by a simplex vector) and 0017:001746552 (the form $P_K$, KAPPA9.2). We prove that every admissible chain whose rank-9 member is admissibly marked by the form has $\det L\ge 972$. The method is a reduction by sections: for 0019 the nine simplex contacts turn the problem into one about an eight-dimensional covariance matrix, and a tree of 17 347 nodes with 7 743 scalar determinant witnesses covers the remaining box; for 0017 a two-vector flag bound and the decomposition of the section metric along a short-dual plane and its rank-seven kernel reduce the problem to five parameters, covered by a tree of 3 010 595 nodes. The proof is computer-assisted: every finite check is stated as a Computational result, and the verification records in the certificate archive are named.
Last updated:  2026-11-08
γ₁₁: A Finite Spectral Relaxation — the macadamia 0008
Rémi Géraud-Stewart and David Naccache
The root paper of this series reduces $\gamma_{11}=4/\sqrt[11]{972}$ to a statement about chains of lattices $L\supset M\supset N$ of ranks 11, 10 and 9, cut along shortest dual vectors, whose rank-9 member lies over one of 4 487 813 perfect forms. Ten of these forms, the macadamias, lie under an actual lattice of rank 10 of small determinant and need a proof at rank 11, where the bound 972 is attained. This paper settles the form 0008:022143116, which lies under a section of $K_{11}$ with 276 minimal vectors: every admissible chain whose rank-9 member is admissibly marked by this form has $\det L\ge 972$. In coordinates aligned with the form, the section metric is $S=I+E$ with three blocks of size three. Two sufficient flag tests come from short dual covectors and integral triangles; local reductions, proved from rational comparisons and Bernstein or Sturm certificates, remove explicit regions of the parameters; every remaining real spectrum is mapped, with explicit allowances, into a finite relaxation on 81 grid nodes, which a tree of 400 nodes with 1 091 rational certificates, replayed in two exact arithmetic implementations, excludes. The proof is computer-assisted, with explicit finite checks stated as one Computational result.
Last updated:  2026-11-08
γ₁₁: Contact Geometry — the macadamias 0001, 0014, 0059 and 0015
Rémi Géraud-Stewart and David Naccache
The root paper of this series reduces the value $\gamma_{11}=4/\sqrt[11]{972}$ of the Hermite constant to a statement about chains of lattices $L\supset M\supset N$ of ranks 11, 10 and 9 whose rank-9 member lies, in the sense of Voronoi, over one of 4 487 813 perfect forms; the $\gamma_{11}$ paper excludes all of them but ten, the macadamias. This paper settles four macadamias, the forms 0001:010488327, 0014:001749549, 0059:016902802 and 0015:030291998, by one method: the geometry of the contacts of the form. A section frame of short dual vectors forces the first gluing of $M$ over $N$ to lie near one of finitely many coherent centres; at such a centre the rank-10 metric is compared with an explicit reference lattice, whose Delaunay cells and contact identities give a uniform bound on its covering radius; and a primitive-extension inequality turns that bound into $\det L\ge 972$. The proof is computer-assisted: every finite check it uses is stated as a Computational result with the records of the certificate archive that certify it, and all comparisons are between explicit rational numbers.
Last updated:  2026-11-08
A Focus on Hermite Constant 11
Rémi Géraud-Stewart and David Naccache
This paper assembles the dimension-eleven argument in a series on the Hermite constants in dimensions ten, eleven and twelve. The root paper reduces a hypothetical lattice of minimum 4 and determinant below 972 to a chain of sections of ranks eleven, ten and nine. Its rank-nine section is marked by a perfect form below an explicit determinant cutoff. The global finite computation leaves 4 487 813 candidate forms and excludes all but ten by certificates. We state the mathematical content of these certificates, describe their data and checking rules, and prove why every valid certificate excludes the corresponding form. The four formats are trace, domain, glue and tree certificates; each tree must cover its entire stated domain. One of the ten remaining cases, 0052:005247066, is treated here by a complete gluing cover. Five companion papers settle the other nine. We also prove the common inequalities used by those local arguments. The resulting bound is $\gamma_{11}=4/\sqrt[11]{972}$, conditional on the attributed rank-nine classification, the rank-ten census and the stated global and local finite checks.
Last updated:  2026-11-08
The Hermite Constants in Dimensions 10, 11 and 12
Rémi Géraud-Stewart and David Naccache
This paper introduces a series of seven papers establishing $\gamma_{10}^{10}=4^{10}/768$, $\gamma_{11}^{11}=4^{11}/972$ and $\gamma_{12}=4/\sqrt{3}$, under the attributed classification of perfect forms of rank nine and the explicitly stated computational inputs. The argument treats the dimensions in order. In dimension ten, a section orthogonal to a shortest dual vector is compared with a perfect form. A completed exact census leaves three possible reference forms, and matrix inequalities exclude a determinant below 768 in each case. In dimension eleven, two successive sections give a chain of ranks eleven, ten and nine. The dimension-ten bound controls the determinant of the last section. The verified global census and preliminary certificates reduce the problem to ten local cases: nine are treated in five companion papers, and one in “A Focus on Hermite Constant 11”. The local arguments combine contact geometry, section bounds and finite rational covers. Mordell’s inequality then gives the dimension-twelve upper bound, matched by the Coxeter–Todd lattice. We prove the common reduction, explain the dependency between the papers, and state exactly which finite assertions must be checked. The accompanying Lean development verifies the complete analytic deduction from those inputs; external exact checkers verify the large certificate data.
Last updated:  2026-11-08
Incrementally Verifiable Oracle Aided Computation
Shafi Goldwasser and Yael Tauman Kalai
Incrementally verifiable computation ($\IVC$) allows a prover to maintain a short proof that can be efficiently updated after each computation step, without retaining or recomputing the preceding execution. In the context of AI safety, the need for incremental verification is particularly important, as AI systems interact with users over time and perform further computation after each interaction. However, standard $\IVC$ schemes do not directly address a crucial feature of AI tasks: their dependence on external information and expertise. Indeed, the UK AISI Alignment Team~\cite{IrvingM25} emphasizes that verification methods for AI safety should accommodate access to external information and human judgment. This is the topic of this paper. We construct $\IVC$ schemes for {\em oracle-aided} computations under the Learning with Errors ($\LWE$) assumption by first constructing succinct non-interactive arguments ($\SNARG$s), and then extending them to the incremental setting. We consider the following two settings, where below, $\lambda$ is the security parameter, $n$ is the input length, and $T$, $S$, and $Q$ are the time, space, and oracle-query bounds. \begin{itemize} \item \textbf{Robust computations.} For bounded-space computations, including non-deterministic computations, in which every accepting purported execution on a false input contains at least an $\varepsilon$-fraction of incorrect oracle answers, we construct {\em privately verifiable} $\SNARG$s and $\IVC$. For $\IVC$, the corresponding robustness condition is imposed on the claimed configuration. Public parameters, private verification keys, and proofs have length $\poly(\lambda,S,\log T,1/\varepsilon)$, and verification uses $O(\lambda/\varepsilon)$ oracle calls. We complement this result with a lower bound ruling out (deterministic) publicly verifiable $\SNARG$s and $\IVC$s with public parameters of length $o(n)$, and $o(Q)$ verifier oracle queries. \item \textbf{Signed oracles.} For oracles that digitally sign their query-answer pairs, we construct publicly verifiable $\SNARG$s and $\IVC$ without a robustness assumption, and with oracle-free setup and verification. Public parameters and proofs have length $\poly(\lambda,S,\log T)$. For deterministic computations with oracle query and answer lengths $\poly(\lambda,\log T)$, we remove the dependence on $S$, obtaining public parameter and proof lengths $\poly(\lambda,\log T)$. \end{itemize} All our constructions have adaptive completeness and soundness. Sub-exponential hardness of $\LWE$ suffices for all constructions; polynomial hardness suffices in the deterministic signed-oracle setting when $T$ is polynomially bounded in $\lambda$. All cryptographic assumptions are required to hold even given access to the underlying oracle.
Last updated:  2026-11-08
Revisiting the Security of OleF, t-OleF, and OlÆF
Tingting Guo, Peng Wang, Shuping Mao, Yan Jia, and Jiadong Han
We revisit the security of OleF, t-OleF, and \olaef\ and identify two independent security flaws. First, we establish a mask-compensation relation between continuation and termination processing in OleF and t-OleF. Exploiting this relation, we construct a two-encryption-query distinguisher against OleF with advantage $1-2^{-2n}$. We further give two concrete AXU hash families for which the same attack applies to t-OleF, revealing flaws in the original DOSPRP and SPRTOP security proofs. We extend these attacks to \olaef\ through valid encodings, breaking its privacy and integrity. In particular, the integrity forgery succeeds with probability $1$ under full-domain verification when the target expansion length is $1$ and extends to larger expansion lengths under suffix-only verification. Second, we refute the claimed ideal RUP integrity bound for variable-expansion online authenticated encryption. Even with an ideal tweakable online permutation, prior unverified decryption queries at smaller expansion lengths can reveal part of the target authentication suffix. We construct counterexamples showing that two such decryption queries and one forgery attempt achieve a success probability of $3/8$, exceeding the claimed bound of $1/4$. We also derive a general expression for the forgery success probability. Finally, we discuss the corresponding repairing
Last updated:  2026-11-08
Threshold Batched Attribute-Based Encryption from Succinct LWE
Shayeef Murshid, Ramprasad Sarkar, and Mriganka Mandal
Batched identity-based encryption (BIBE) enables a single compact key to decrypt ciphertexts associated with a designated batch of identities. Batched attribute-based encryption (B-ABE) extends this functionality to attribute-based access control, while threshold batched attribute-based encryption (TB-ABE) further distributes the decryption capability among multiple parties. Existing constructions of TB-ABE rely on bilinear pairings, motivating post-quantum alternatives. In this work, we give, to the best of our knowledge, the first lattice-based candidate construction of TB-ABE. Our construction combines the succinct polynomial-digest mechanism underlying lattice-based BIBE with key-homomorphic evaluation for arithmetic-circuit policies and linear secret sharing. We prove security under the ℓ-succinct LWE assumption, assuming the required share-uniformity property of the underlying ramp threshold sharing scheme.
Last updated:  2026-11-08
Designing Quantum-Safe Network Architectures via Certified Randomness Distribution
Filip-Ioan Ceară and Diana Maimuţ
We propose an alternative design for quantum-safe network architectures, based on distributing certified randomness generated by different trust-level QRNGs. Our modular methodology aggregates high-trust entropy from upper network layers with local contributions, enhancing the security guarantees of locally available random sequences. Leveraging the physical guarantees of QRNGs and symmetric-key cryptographic algorithms for node authentication, our approach enables immediately deployable, quantum-safe infrastructures. Such a paradigm bypasses the practical security limitations of current QKD-based solutions, while avoiding massive key sizes and latency inherent to asymmetric PQC implementations.
Last updated:  2026-11-08
The Minimum Bucket Capacity for Reliable Path ORAM
Yijia Chang and Man Ho Au
Path ORAM hides memory access patterns by storing $N$ data blocks in a binary tree whose buckets have capacity $Z$, using a client-side stash for blocks that cannot be placed in the tree. Smaller buckets reduce storage and communication costs but increase the risk of stash overflow. The revised Path ORAM analysis in 2014 established an exponentially decreasing stash overflow probability for $Z \geq 5$. Experiments suggest small stashes at $Z=4$ and substantially larger ones at $Z=3$. However, it remained unknown whether $Z=4$ admits a uniform exponential stash bound or whether such a bound is impossible at $Z=3$. We establish a sharp threshold at $Z=4$ for binary Path ORAM with tree depth $L=\lceil \log_2 N \rceil$. For $Z=4$, we prove that, uniformly over all database sizes and fixed access sequences, the stash size $S$ after the final refill satisfies \[ \Pr[S>R] \leq \frac{23}{28}\left(\frac{5}{7}\right)^R \] for every integer $R \geq 0$. For $Z=3$, we exhibit a family of instances on which a single sequential scan of all $N$ blocks produces a stash of size $\Omega(N)$ with probability bounded away from zero. Thus, four is the minimum bucket capacity admitting a uniform exponential stash bound: a logarithmic stash suffices for polynomial-length executions with inverse-polynomial failure probability at $Z=4$, whereas at $Z=3$ no sublinear stash can make the overflow probability vanish uniformly. Our proofs connect the actual Path ORAM process with dependent node loads to an auxiliary model with independent geometric node loads. This independence enables a recursive analysis of overflow that avoids the union bound over rooted subtrees used in the previous $Z=5$ proof. The main challenge is to transfer bounds from the auxiliary model to the actual process, which requires different techniques for the upper and lower bounds. For $Z=4$, we develop a two-stage randomization argument that bounds the actual process's exponential overflow moment by that of the auxiliary model. For $Z=3$, we develop a local continuous-time approximation with controlled errors that transfers an overflow surplus from the auxiliary model to the actual process, yielding the linear stash lower bound. Together, these arguments establish the sharp threshold at bucket capacity four.
Last updated:  2026-11-07
How to Revoke Users in Encryption Schemes?
Sanjam Garg, Dimitris Kolonelos, Benjamin Ostrovsky, and Guru-Vamsi Policharla
Revocation is essential for keeping encryption secure as keys leak, devices are compromised or users leave the system. We revisit the problem of revocation for encryption schemes and give, to our knowledge, the first approach combining anonymous, collusion-resistant revocation with unchanged keys and access rules, succinct ciphertext overhead and a trustless revocation authority, i.e. that cannot decrypt. Revoking a user publishes one random-looking pseudonym, without telling encryptors whose key was revoked. A party can decrypt future ciphertexts only if it is unrevoked and satisfies the original access decryption rule. Our core observation is that revocation is, at heart, witness encryption for the statement that one satisfies the access rule and that the pseudonym bound to one's key has not been revoked. Although general-purpose witness encryption remains far from practical, we observe that the statements arising from revocation are simple and algebraic, and we show that they fall within the special-purpose framework of Garg et al. (CRYPTO 2025), which compiles short arguments of knowledge (called ``gadgets'') into efficient witness encryption using bilinear groups. Our technical contribution is a pair of succinct non-membership gadgets for this framework, one for a single hidden pseudonym and one that certifies non-revocation jointly for all users selected by an access rule. Both gadgets are generic and modular, as they compose with the gadgets expressing a wide range of access rules, and thus provide a single revocation mechanism that is designed once and reused across different encryption schemes, without redesigning either the scheme or the revocation. These gadgets yield the following applications. First, we give a black-box transformation adding revocation to arbitrary independently instantiated public-key encryption, with constant-size cryptographic ciphertext overhead. For unrevoked users, confidentiality continues to rely only on the security of the underlying scheme. Then, we demonstrate applications to advanced encryption scheme, constructing revocable schemes for distributed broadcast, registered attribute-based, and registered threshold encryption, with succinct cryptographic ciphertext components and threshold decryption shares. We prove adaptive security of our schemes in the generic bilinear-group and random-oracle models.
Last updated:  2026-11-07
Round-Optimal Statistical Verifiable Secret Sharing with Polynomial Complexity
Chen-Da Liu-Zhang and Elisaweta Masserova
Verifiable secret sharing (Chor, Goldwasser, Micali, and Awerbuch; FOCS'85) is a central primitive in secure computation, and its round complexity has been studied extensively. Rabin and Ben-Or [STOC'89] established the feasibility of statistical security up to $t<n/2$ corruptions, and Patra, Choudhary, Rabin, and Rangan [Crypto'09] showed that three sharing rounds are necessary. The work of Applebaum, Kachlon and Patra [STOC'23] introduced the first round-optimal VSS with three rounds of sharing and one round for reconstruction, albeit with exponential communication in the number of parties. We give the first round-optimal statistical VSS that has polynomial communication and computation for $t<n/2$. This resolves the efficiency question left open by Applebaum, Kachlon and Patra. The protocol is obtained from a new notion of weak secret sharing, in which the reconstruction-time freedom of a corrupt dealer is limited to choosing verification keys, which is of independent interest.
Last updated:  2026-11-07
From Degree Three to Degree Two: Statistical Randomized Encodings for All Functions
Emmanuela Orsini and Arpita Patra
A randomized encoding represents a function by a simpler randomized map whose output allows recovery of the function value while revealing essentially no further information about the input. Perfectly correct and perfectly private encodings of degree three over $\F_2$ are known for every Boolean function, but degree two cannot provide these guarantees for all functions (Ishai and Kushilevitz, FOCS 2000 and ICALP 2002). Whether degree two suffices when small statistical errors are allowed in both correctness and privacy has remained open. We construct quadratic randomized encodings of every Boolean function with exponentially small correctness and statistical privacy errors. The degree bound holds jointly in the input bits and independent uniform random bits, and the construction, encoder, decoder and simulator have complexity polynomial in the total size of mod-2 branching programs computing the function's output bits and in the security parameter. Our encodings also achieve decomposability and output locality three, meaning that each encoded bit depends on at most three input and random bits. These results resolve the degree-two and locality-three questions for statistical randomized encodings (Ishai, 2013). As an application, we obtain one-way functions of optimal output locality three from one-way functions in polynomial-time uniform $\mathrm{NC}^1$, improving the previous locality-four result under the same assumption (Applebaum, Ishai and Kushilevitz, FOCS 2004). We also obtain quadratic multiparty randomized encodings with negligible correctness and statistical privacy errors against semi-honest corruption of any coalition of parties. Previous general constructions for $k\ge4$ parties provided perfect correctness and privacy against at most $\lfloor 2k/3\rfloor$ corruptions (Applebaum, Ishai, Karni and Patra, CRYPTO 2022). Through known reductions, our encodings yield non-interactive reductions of every functionality to a fixed three-party functionality and three-round protocols in the two-round OT-hybrid model, with negligible correctness and statistical privacy errors against every coalition. They also yield non-interactive client--server protocols for every function whenever a majority of the servers is honest, even when corrupted servers collude with any set of clients. This server threshold is optimal in this model when privacy is required against arbitrary client coalitions.
Last updated:  2026-11-07
SoK: Understanding Virtual Machines over Fully Homomorphic Encryption
Song Bian, Ziwei Ma, Yunhao Fu, Haowen Pan, Ruiyu Shen, Zhou Zhang, Ran Mao, Zaidong Li, Yintai Sun, Ruoyi Li, and Zhenyu Guan
We survey the current literature on fully homomorphic encryption (FHE) from a virtual machine (VM) perspective. We observe that programs behave in an intrinsically different way over FHE than on plaintext, forming a new paradigm of computation that is fundamentally constrained by the obliviousness of data. To better understand the computational properties, we compile more than 125 works to formulate a cross-layer systematic view of FHE VMs, with a special focus on understanding the concrete programming models over encrypted data. In particular, we identify three distinct forms of VMs over FHE, namely, the SISD VM, the SIMD VM, and the hybrid VM. To aid the cross-layer systematization, we also discuss how current FHE compilers and hardware accelerators can be applied to enhance the usability and performance of the respective VMs. In the experiment, we test eight VM instructions with varying precision as well as two end-to-end application programs to quantitatively assess the concrete design trade-offs for each of the VM paradigms. We conclude that FHE VMs of different types exhibit distinct utility and performance characteristics, necessitating new design methodologies to be developed in a cross-layer manner.
Last updated:  2026-11-07
Jazzline: Composable CryptoLine Functional Correctness Proofs for Jasmin Programs
José Bacelar Almeida, Manuel Barbosa, Gilles Barthe, Lionel Blatter, Gustavo Delerue, João Diogo Duarte, Benjamin Gregoire, Tiago Oliveira, Miguel Quaresma, Pierre-Yves Strub, Ming-Hsien Tsai, Bow-Yaw Wang, and Bo-Yin Yang
Jasmin is a programming language for high-speed and high-assurance cryptography. Correctness proofs of Jasmin programs are typically carried out deductively in EasyCrypt. This allows generality, modularity and composable reasoning, but does not scale well for low-level architecture-specific routines. CryptoLine offers a semi-automatic approach to formally verify algebraically-rich low-level cryptographic routines. CryptoLine proofs are self-contained: they are not integrated into higher-level formal verification developments. This paper shows how to soundly use CryptoLine to discharge subgoals in functional correctness proofs for complex Jasmin programs. We extend Jasmin with annotations and provide an automatic translation into a CryptoLine model, where most complex transformations are certified. We also formalize and implement the automatic extraction of the semantics of a CryptoLine proof
Last updated:  2026-11-07
Registration-based Encryption with Logarithmic Registration
Xingfu Yan, Guiqiu Liao, Fan Yang, Haining Yang, Zheng Gong, Fucai Luo, and Bowen Zhao
Registration-based encryption (RBE) preserves IBE's identity-only encryption interface while eliminating key escrow: users generate their own keys, and a Key Curator manages only registered public keys. However, this design introduces a new challenge: user registration, since every joining user rrequires KC to update the registry. Although theoretical RBE constructions achieve polylogarithmic registration, they rely on costly cryptographic techniques and remain impractical. In existing deployable black-box RBE, registration takes $O(\sqrt{N})$ time ($N$ denotes the maximum user capacity). This gap between theoretical registration efficiency and deployability makes registration a key performance bottleneck for large-scale deployments of pairing-based RBE. This work presents a black-box pairing-based RBE construction under the decisional $(R,S,T,f)$-Diffie-Hellman assumption. Build on the multilinear tree, when registering a user's public key, KC updates only the corresponding root-to-leaf path associated with the user. Therefore, registration in our construction takes $O(\log \sqrt{N})$ time for the maximum user capacity $N$. Moreover, we provides membership and non-membership verification, and their batch verification supports to check registration status of multiple users. Experiments show registration and key generation complete in milliseconds when $N=10^7$. Compared with Glaeser et al. (CCS'23), our scheme accelerates registration by up to \(158\times\) and key generation by up to \(230\times\) with practical overheads.
Last updated:  2026-11-07
Overcoming Padding in Cryptography via Hardness of Certifying Random Strings
Yao-Ching Hsieh, Abhishek Jain, Jiatu Li, and Surya Mathialagan
Modern cryptography relies on a provable security paradigm where the security of a primitive is established from the intractability of one or more computational problems. Hybrid arguments are central to this approach. Somewhat unexpectedly, many security proofs in the literature that use this methodology require hybrids with description-size larger than the real scheme. To argue security, the real scheme is artificially padded to match this size. This so-called “superfluous padding” phenomenon is surprisingly commonplace and poses a barrier to achieving succinct cryptographic primitives where the size of the scheme parameters does not grow with the input length. We present a framework to eliminate padding in cryptography. We demonstrate several applications, including rate-1 iO, succinct (and extractable) witness encryption and succinct non-interactive arguments with short CRS for subclasses of NP, and multi-input functional encryption for functions with unbounded arity. To obtain our results, we establish a new connection between cryptography and proof complexity. Central to our approach is the notion of proof-complexity generators (PCGs) [Krajíček'01, Alekhnovich, Ben-Sasson, Razborov, Wigderson'04], which, informally speaking, formalizes the hardness of certifying random (incompressible) strings with propositional proof systems. Our applications are derived from a master theorem that lifts cryptographic security on “compressible instances” to security on any instance under the existence of PCGs. Due to its broad scope, this theorem might find future application
Last updated:  2026-11-11
Constructions of Boolean Correctors with Optimal Nonlinearity and Vectorial Correctors Beyond Optimal Linear Correction Order
Zhaole Li and Deng Tang
Correctors are postprocessing functions that reduce or eliminate statistical bias in raw bitstreams produced by physical noise sources in true random number generators. In this paper, we develop a framework based on binary Krawtchouk polynomials for analyzing and constructing Boolean and vectorial correctors. This framework reformulates the Walsh-layer criterion into finite moment constraints on support-layer counts and preimage-layer counts. We also establish universal upper bounds on the nonlinearity of correctors, and necessary conditions on the achievable correction order. For Boolean functions, we prove that $(n-1)$-correctors are either the parity function or its complement. Then we characterize the support-layer profiles of $(n-2)$- and $(n-3)$-correctors and establish upper bounds on nonlinearity. For $n=2^k\ge 8$, a self-addressing construction yields $(n-2)$-correctors achieving the optimal nonlinearity $2^{n-1}-2^{n-1}/n$ with resiliency $n/2-2$ and algebraic degree $k+1$. Notably, this provides the first known infinite family of nonlinear correctors achieving both optimal correction order and optimal nonlinearity for that order, while having a resiliency strictly lower than the correction order. Furthermore, using constant-weight addressing, we construct $(n-d-1)$-correctors that asymptotically meet the nonlinearity upper bounds for every fixed $d\ge 1$. Our profile characterization also reveals inherent limitations of injective Maiorana--McFarland constructions at correction order $n-3$. For vectorial functions, we construct nonlinear $(s(2^m-1),m,s2^{m-1}+\ell-1)$-correctors for every $m\ge 2$ under certain conditions on $s$ and $\ell$, with resiliency at most $s2^{m-1}-2$. To the best of our knowledge, this is the first infinite family of nonlinear correctors whose correction order simultaneously exceeds that of optimal linear corrector and its own resiliency. Finally, we introduce a secondary construction that lifts these vectorial correctors to larger input dimensions while preserving their correction-order advantage. This approach yields a nonlinearity of $2^{n-1}-2^{n-n_0-1}$, where $n_0$ is the input dimension of the base corrector, along with explicit resiliency and a flexible algebraic degree.
Last updated:  2026-11-12
More Keys, Less Commitment: Key-Committing Attacks on BBB Accordions via Encode-then-Encipher and a Key-Committing Transform
Donghoon Chang, Yukihito Hiraga, Yusuke Naito, Yu Sasaki, and Takeshi Sugawara
Cryptographic accordions with beyond-birthday-bound (BBB) security are being actively studied in connection with NIST’s ongoing standardization effort. We show that BBB security of an accordion does not necessarily strengthen key commitment of AE built from it: in many BBB accordions, additional keys introduced for BBB security give an adversary extra degrees of freedom. Exploiting this observation, we present $O(1)$ key-committing attacks on a broad range of AE schemes built from BBB accordions, mostly via the Encode-then-Encipher (EtE) paradigm, including CHCTR2, eCTR-based accordions, THCTR, HCTR+, TCT2, and bbb-ddd-AES under a natural polynomial-hash instantiation. To address this issue, we propose CACH, a black-box transform from BBB-secure accordions to robust AE (RAE) with key-committing security. CACH achieves BBB multi-user RAE security and achieves $t/2$-bit key-committing security with a $t$-bit tag for $n \le t \le 2n$ in the ideal-cipher model. CACH uses only AES-based components and supports all AES key sizes, making it compatible with NIST’s design goals. We instantiate CACH with CHCTR2. CACH-CHCTR2 with AES-256 outperforms EtE-HCTR2 with Rijndael-256 and EtE-CHCTR2 for short messages.
Last updated:  2026-11-07
QUASI: Post-Quantum Quorum Attestation of Pre-Validated Statements
Maksym Ioffe and Dahlia Malkhi
We present QUASI, a newly conceived class of protocols that enable a group of parties to produce a publicly verifiable attestation about a pre-validated statement. Designed for quorum-based systems, QUASI enables parties to attest to external entities that the statement is valid. Surprisingly, each party need not sign the entire statement: authenticating only a small subset of symbols suffices for the quorum to attest to the whole. A simple deterministic construction illustrates this possibility. Built purely from hashing and error correction, QUASI achieves small per-party contributions and low attestation generation and verification costs, without relying on SNARKs for aggregation. Our main contribution is a randomized construction achieving reductions of more than $10\times$ in per-party contribution size and hash computations for generation and verification, compared with full hash-based signatures. QUASI is a generic primitive supporting diverse applications. Two principal use cases are external attestation for signature-free consensus, enabling clients to verify statements about committed state; and preprocessing for SNARK-based aggregation, compounding QUASI's savings with succinct-proof compression.
Last updated:  2026-11-07
Pastel: Single Secret Leader Election with Private Weights
Jung Hee Cheon, Kevin Choi, Intak Hwang, Jaehee Kang, Alireza Kavousi, Junho Lee, and Yongdong Yeo
A single secret leader election (SSLE) protocol allows an election of exactly one leader among $n$ parties in a secrecy-preserving manner, where only the elected leader knows it has won until it publicly announces and claims leadership. Motivated by proof-of-stake blockchains where stakes are stored in an encrypted or committed form for the sake of privacy, we design and implement the first SSLE protocol with private weights. Each party's probability of winning an election in our protocol is weighted by stake, and these weights are private. Prior schemes in the literature only allow probabilistic (i.e. expectation of one but can be zero or many leaders) elections in the same setting. Preserving privacy also means public verification is paramount in order for a protocol to be practically reliable. In this respect, our protocol achieves security against malicious adversaries with a concrete implementation. In particular, we concretely implement the needed zero-knowledge proofs and thus do not rely on slashing (financial penalties) to achieve end-to-end malicious security, though slashing can still serve as a performance optimization. Along the way, we observe that previous SSLE protocols in a setting without private weights (either unweighted or with public weights) are either maliciously secure with implementation or post-quantum secure but not both, while our protocol achieves both.
Last updated:  2026-11-06
An improved algorithm to solve the isogeny problem in dimension 2 with precomputation
Maria Corte-Real Santos
We give a new algorithm for the superspecial isogeny problem in dimension $2$. After a one-time precomputation depending only on $p$ (which succeeds with overwhelming probability), each instance is solved in expected time and memory $p^{3/4+o(1)}$. This result is unconditional, relying on no heuristics. Including the precomputation, a single instance is solved in time $p^{19/23+o(1)}$, improving on the $p^{1+o(1)}$ of the Costello-Smith algorithm. The improvement holds even with the same memory as (the rigorous version of) their algorithm. The key ingredient is an algorithm that computes the equations of the Humbert surfaces $\mathcal{H}_{N^2}$ modulo $p$ for all $N$ up to a bound $D$ growing with $p$. These equations give a membership test for optimally $(N,N)$-split surfaces, which we evaluate in batches using fast multipoint evaluation. This speeds up the bottleneck of the Costello-Smith algorithm: finding an isogeny from a superspecial principally polarised abelian surface to a product of supersingular elliptic curves.
Last updated:  2026-11-06
FirstSwap: Pre-Consensus Trade Approvals for Decentralized Market Design
William Diamond, Fatima Elsheimy, Dahlia Malkhi, Geoff Ramseyer, and Srivatsan Sridhar
Decentralized exchanges typically give traders no execution guarantee until a block is finalized. In the meantime, external prices move, traders strategically delay submission, and block producers can influence inclusion and ordering. We introduce FirstSwap, a DEX built on a constant-function market maker pricing curve that gives traders an early pre-approval before consensus, guaranteeing inclusion and execution within their submitted price limit, with final ordering determined by limit prices rather than by a block producer. We demonstrate the benefits of trade pre-approvals in an economic model combining auction theory with CEX-DEX arbitrage. When the CEX price changes gradually, FirstSwap rewards earlier traders with better prices, discouraging strategic delay and yielding higher social welfare and gains to AMM liquidity providers than a batch auction. When the CEX price jumps abruptly, FirstSwap yields higher welfare and smaller AMM losses than fair ordering. The central challenge is delivering fast trade pre-approvals without consensus. We introduce a decentralized, scaled admissibility protocol under which each validator reserves only a fraction of the available liquidity at every price. A trader obtains approval in a single round of messages with a quorum of validators. Somewhat surprisingly, despite Byzantine validators who may approve trades arbitrarily, we show that all quorum-certified trades are jointly admissible and execute within their limits. Our protocol extends naturally to a setting where buy and sell orders can be pre-approved against each other before a block is finalized.
Last updated:  2026-11-06
On Proximity Gaps for Expander Codes
Kobi Gurkan, Andrija Novakovic, and Ron D. Rothblum
Proximity gaps describe a phenomenon concerning random linear combinations of words and their distance from a linear error-correcting code. Informally, they address the following question: if a collection of words is jointly far from the code, is a random linear combination of those words likely to also remain far from the code? Motivated by applications to concretely efficient proof systems, in this note we study this question for expander codes, a class of low-density parity-check (LDPC) codes. Recent works of Goyal and Guruswami (STOC 2026) and Goyal, Guruswami, Sun, and Wootters (RANDOM 2026; arXiv 2026) establish proximity gaps approaching capacity for random LDPC ensembles, but only asymptotically and for very large degrees and field sizes, well beyond what is used in practical proof systems. We focus on general expander codes (not necessarily random) with small degree. Building on the smoothness property of expander codes due to Dinur, Sudan, and Wigderson (RANDOM 2006), we show that such codes have proximity gaps up to nearly half of the distance guaranteed by their expansion.
Last updated:  2026-11-06
SNARKs from LWE via Non-black-box Reductions
Zhengzhong Jin, Mingqi Lu, and Bo Peng
We construct the first succinct non-interactive arguments of knowledge (SNARKs) from the polynomial-hardness of Learning with Errors (LWE) for a subclass of UP languages whose witness unambiguity has a polynomial-size Extended Frege ($\mathcal{EF}$) proof. Our construction achieves the following soundness guarantee: For any fixed sequence of false instances $\{x_\lambda\}_{\lambda\in\mathbb{N}}$, there exists a (non-constructive) constant $c>0$ such that, whenever the uniform random CRS length exceeds $\lambda^c$, the construction achieves infinitely-often soundness for this sequence $\{x_\lambda\}_{\lambda\in\mathbb{N}}$: for any polynomial-time cheating prover $\{\mathcal{A}_\lambda\}_{\lambda\in\mathbb{N}}$, the probability that $\mathcal{A}_\lambda$ outputs an accepting proof for $x_\lambda$ is negligible for infinitely many $\lambda$. As intermediate results, we also obtain: - SNARGs for any NP language that has polynomial-size $\mathcal{EF}$ proofs of witness unambiguity for all instances outside of the language, based on polynomial-hard LWE, achieving the same style of soundness guarantee. - SNARKs for all true instances in any language $L \in \mathsf{UP}$ where every instance has a polynomial-size $\mathcal{EF}$ proof of witness unambiguity, under polynomial hardness of LWE, without soundness guarantees for false instances. To achieve our main result, we employ a non-black-box soundness reduction. Along the way, we introduce a new logical proof system, the \emph{Cryptographic Extended Frege} ($\mathcal{CEF}$) system, which extends $\mathcal{EF}$ with rules for formalizing the indistinguishability in cryptographic security proofs. Building on the Encrypt-hash-and-BARG framework of [Jin–Kalai–Lombardi–Vaikuntanathan, STOC’24], we further obtain SNARGs for NP languages that have $\mathcal{CEF}$ proofs of non-membership, which may be of independent interest.
Last updated:  2026-11-06
Actively Secure PIR from Verifiable Linear Relations over Rings
Louis Tremblay Thibault
Privately retrieving data from a database without revealing which element is being retrieved is a fundamental problem in cryptography with many diverse applications. State-of-the-art solutions to this problem are generally based on homomorphic encryption, which offers security only against passive adversaries. In this work, we contribute to the recently introduced notion of Verifiable Private Information Retrieval (vPIR), which leverages verifiable computation to achieve security against active adversaries. We present a new sum-check based interactive oracle proof for linear relations over power-of-two cyclotomic rings, and show how to instantiate it into a vPIR protocol using Ring-LWE. Our solution is concretely efficient, offers the best possible security guarantees and is plausibly post-quantum secure. We additionally provide an open-source Rust implementation. Our server time improves on prior work's IOP by more than an order of magnitude, leading to a factor two end-to-end performance improvement. Compared to vPIR prior work, on a 4 GiB database, our offline communication and client storage are of 128 MiB, against 3.29 GiB. Preprocessing is run once per database and amortized over an unbounded number of queries.
Last updated:  2026-11-06
The GGM PRF Construction is Optimal
Bar Alon, Itai Dinur, and Muthuramakrishnan Venkitasubramaniam
We study the complexity of fully black-box constructions of pseudorandom functions (PRFs) from pseudorandom generators (PRGs). The seminal work of Goldreich, Goldwasser, and Micali (JACM 1986), combined with Levin’s domain-extension technique, yields PRFs that make a superlogarithmic number of adaptive calls to a length-doubling PRG. A long-standing open problem is whether fewer calls suffice for fully black-box constructions. Despite progress for restricted classes of constructions and reductions, previous results have not been able to rule out even a single-call construction in full generality. A related question asks how many calls are needed to amplify a PRG’s stretch from \(r\) bits to \(\rho>r\) bits. Our main result establishes the asymptotic optimality of the GGM construction with domain compression, both in the number of calls and in adaptivity, for length-doubling PRGs. More generally, for a PRG with seed length \(n\) and stretch \(r(n)\), we rule out fully black-box PRF constructions with \(d(n)\) adaptive rounds whenever \(d(n)\log(2+r(n)/n)=O(\log n)\), even allowing polynomially many calls per round. Our bounds hold for one-bit weak PRFs on domains of superpolynomial size. In particular, they exclude all polynomial-query nonadaptive constructions from PRGs of arbitrary polynomial stretch and require superlogarithmically many rounds when the underlying PRG doubles its input length. We further show impossibility results for fully black-box non-adaptive PRG stretch amplification. First, we show that a non-adaptive construction of a $\rho$-bit stretch PRG from an $r$-bit stretch PRG requires $\Omega(\tfrac{\rho}{r+\log n})$ calls. Second, we show that it is impossible to construct a length-doubling PRG from an $o(n)$-bit stretch PRG with non-adaptive calls. Our techniques combine and extend two prior lines of work. First, we develop a sensitivity framework that measures the effect of changing a uniformly chosen oracle entry and transfers this stability through black-box reductions, extending the sensitivity arguments of Bitansky et al. (CRYPTO 2017) and Bitansky and Degwekar (TCC 2019). Second, we extend the scoring mechanism of Alon et al. (CRYPTO 2026) and integrate it with our framework. Finally, we show that the sensitivity framework applies to constructions from one-way permutations. Specifically, we show another proof of Simon's impossibility of basing collision-resistant hash functions on one-way permutations. Our new proof can be viewed as an abstraction of the argument by Bitansky and Degwekar.
Last updated:  2026-11-06
Filtered merges make deeper representation trees pay: Subset Sum and Meet-LWE
Nick Howgrave-Graham
Dubiner's bucketing codes, used as type-class filters on representation coordinates, let a merge avoid generating matched pairs with the wrong split pattern. We show that in representation trees their main effect is to make depth pay. For random density-one Subset Sum they improve the exponent of Bonnetain, Bricout, Schrottenloher and Shen from 0.2831 (our recomputation) to 0.2690, at depth 5; no better point was found up to depth 9. For May's Meet-LWE on ternary keys they improve the asymptotic exponent by 0.013–0.023 for key weights ω ≥ 0.375. Filters can pay only at merges where most matched pairs have the wrong split pattern, and do pay where such merges bind; we show both where this holds and where it fails. A survival recursion justifies the accounting, a symmetry lemma shows that the filters cannot bias the planted solution, and simulations support the remaining heuristics.
Last updated:  2026-11-06
Parallelizable modes for duplex-based authenticated encryption
Joan Daemen, Silvia Mella, and Gilles Van Assche
This note enriches the SHAKE and TurboSHAKE-based authenticated encryption schemes defined by Daemen et al. at EuroS&P 2025 with parallelizable ones, while keeping their security properties. The main contribution is a new deck cipher mode, called FlightDeck, that has the ability of processing input strings similarly to KangarooTwelve and producing output strings as in counter mode, so both parallelizable. We then instantiate FlightDeck on top of the overwrite duplex (OD) construction, in turn on top of a Keccak-p permutation. Combined with a deck cipher-based mode like Deck-BO, the security of the resulting authenticated encryption schemes reduces to the PRF security of keyed (Turbo)SHAKE and to the collision resistance of (Turbo)SHAKE. Compared to the schemes defined at EuroS&P 2025, replacing UpperDeck with FlightDeck greatly improves their software efficiency as one can implement them with Keccak-p permutations evaluated in parallel.
Last updated:  2026-11-06
Testing CCZ-equivalence to permutations via projections of Walsh zero spaces, with applications to APN functions
Emanuele Bellini
Whether almost perfect nonlinear (APN) permutations exist in even dimension $n\ge 8$ is a long-standing open question, the big APN problem. The only example known in even dimension, on six bits, was found from a quadratic APN function that is not itself a permutation, by Carlet--Charpin--Zinoviev (CCZ) equivalence. It is therefore natural to test APN functions for CCZ-equivalence to a permutation. This amounts to finding two complementary $n$-dimensional subspaces among the zeros of the Walsh transform, which lie in $\mathbb{F}_2^{2n}$. A known necessary condition only uses their projections to $\mathbb{F}_2^n$ and cannot decide every case. We give an exact test for functions whose Walsh supports are affine, including all quadratic functions. It reconstructs the subspaces from their projections, through searches for subspaces of $\mathbb{F}_2^n$ and for constrained bilinear maps. On the benchmarked functions in dimension twelve, it lists them $39$ to $55$ times faster than the generic search of the commonly used sboxU library. We then study the functions $x^3+a^{-1}\mathrm{Tr}(a^3x^9)$, which Göloğlu and Pavlů proved not to be CCZ-equivalent to permutations when $4$ divides $n$. With their result, our computations show that this holds for every even $n\le 24$. In dimension $18$ the necessary condition is satisfied, and the new test decides the case. We conjecture this for every even dimension. We also compile $25$ classes of quadratic APN functions in dimension ten from published instances, with equivalence certificates. No function in these classes or in their switching closure is CCZ-equivalent to a permutation. All code and data are public.
Last updated:  2026-11-06
Exploring the Set of APN Functions
Jules Baudrin, Pierre Galissant, and Léo Perrin
An Almost Perfect Nonlinear (APN) function $F : \mathbb{F}_2^n \to \mathbb{F}_2^n$ provides optimal protection against differential attacks, meaning that the equation $F(x+a)=F(x)+b$ has at most 2 solutions~$x$ when $a \neq 0$. Setting aside some sporadic examples, such functions are hard to find in practice, and whether there exists APN bijections of $ \mathbb{F}_2^n$ when $n > 6$ is even (the Big APN Problem) is still unknown. In this paper, we provide the tools needed to explore the complete set of known APN functions. Indeed, for a given APN function $F$, we in fact know many: all functions CCZ-equivalent to $F$ are also APN, and so are its switching neighbours. These notions have been in the literature for many years, but several unknowns remain that complicate the exploration of the corresponding functions in practice: a given function has too many switching neighbours, and the algorithms that are known to iterate through a CCZ-equivalence class return multiple representatives per extended-affine (EA) equivalence class. We solve both problems. First, we show how to partition precisely the CCZ-equivalence class of a quadratic APN function in practice, and thus obtain exactly one representative per EA-equivalence class. To achieve this, we carefully investigate the set of the automorphisms of the graph of a quadratic APN function, and show how to generate them very efficiently using the ortho-derivative. Second, we provide the first detailed investigation of the set of the switching neighbours of a function, show in particular how an overwhelming majority of them are trivial, and explain how to get rid of those. Incidentally, we build a new extended-affine equivalence class invariant using the resulting set of non-trivial switching neighbours. For both theoretical contributions, we pushed highly-efficient and easy to re-use implementations of the corresponding algorithms to the sboxU library. It allowed us to generate databases containing all known APN functions for $n=6$ and $n=7$. For $n=8$, our algorithms are efficient-enough that we can investigate the properties of the millions of quadratic APN function recently exhibited. In the process, we generate a few thousands of new CCZ-equivalence classes. In the light of our work, the successes of the exploration strategies for $n=6$ (i.e. finding an APN function inequivalent to any monomial and quadratic mapping, and finding an APN bijection in even dimension) seems to be an artifact due to the small dimension that we show not to work for dimension 8 and which we do not expect to work either when the dimension is greater.
Last updated:  2026-11-06
More Salt, Please: A Simple Compiler for Post-Quantum Strong aPAKE
William Riccardo Duro, Sebastian Faller, Julia Hesse, and Máté Horváth
Resistance to precomputation attacks is a central security goal in password-based cryptography, as it drastically increases the runtime of brute-force attacks on breached password hashes. Strong asymmetric password-authenticated key exchange (saPAKE), which enforces such precomputation resistance, is standardized by the IRTF and deployed today at large scale. Unfortunately, no practical and easy-to-deploy saPAKE exists yet that withstands quantum attackers. Current constructions use rate-limiting tools such as oblivious pseudo-random functions (OPRFs), of which post-quantum versions are significantly more costly and complex than their discrete-log based counterparts. In this paper, we take a new approach to precomputation resistance. Starting from the compilers from PAKE to aPAKE by Gentry-MacKenzie-Ramzan (Crypto 2006) and Liu-Lyu-Han (Asiacrypt 2024), we propose a password file ratchet that adds precomputation resistance to these compilers through continuously updating the password file. The update is a simple salted hash. With a variety of practical post-quantum PAKEs at hand, this yields a ready-to-deploy post-quantum saPAKE at the trade-off of a changing server state.
Last updated:  2026-11-11
The Maximum Possible Nonlinearity for a Balanced Boolean Function in 10 Variables is 492
Youle Xu and Qichun Wang
Determining the maximum nonlinearity of 10-variable balanced Boolean functions has been a long-standing open problem. In this paper, we resolve it by proving that the maximum nonlinearity is exactly 492, thereby confirming Dobbertin’s conjecture in dimension 10. To exclude nonlinearity 494, we derive a quadratic residue for the Walsh spectrum and refine a local energy table from four-block concatenation by retaining the signs of the Walsh coefficients. The resulting bounds exclude all but the largest polar rank; a product inequality and a parity argument eliminate the remaining case.
Last updated:  2026-11-06
Applying Combinatorial Techniques To Find Minimal Non-Complete Set Coverings
Enrico Piccione and Jan Vorloeper
One of the most prominent hardware countermeasures against side-channel attacks are threshold implementations (TIs). The technique uses masking to split the operations in a cryptographic algorithm into several ones operating on shares. The coverage and non-completeness requirements of TIs are mathematically described by the notion of non-complete set coverings (NCSCs). Importantly, the number of members inside an NCSC determines the number of output shares and therefore directly impacts the complexity of the resulting TI. In this work, we derive new lower bounds on the minimal number of members of NCSCs and obtain new upper bounds by explicit constructions. We present a group-theoretic construction of balanced NCSCs, in which the numbers of input and output shares coincide, together with a search algorithm based on intersections of group translates. Our methods determine the smallest balanced coverings in two previously unresolved cases and yield exact minima and classifications of optimal coverings for an infinite family of parameters. These results resolve all four explicit open problems posed by Farr\`as, Fidalgo and Lara-Nino.
Last updated:  2026-11-06
Exploiting Matrix-Vector Multiplication in AIMer: Single-Trace Attacks on Key Generation and Signing
Süleyman Emir Akın, Abdullah Talayhan, and Özcan Öztürk
This paper presents two side-channel attacks against AIMer v3.0, one of the two signature schemes selected in the Korean Post-Quantum Cryptography (KpqC) competition. Both are single-trace attacks that recover the full secret key without a profiling phase, one against key generation and one against signing. Both target the same routine: the matrix-vector multiplication invoked by either phase expands each bit of its secret operand into an all-zero or an all-one mask, which then gates the accumulation of the corresponding public matrix row. A single execution therefore leaks one distinguishable segment per secret bit. What makes the attacks non-profiled is that each attacked trace carries its own labelled training set. During key generation, creating the dense invertible public matrices invokes the matrix-vector multiplication routine hundreds of times, on operands that are public. In signing the same derivation takes place, and in addition the signature itself opens all but one of the $N$ parties of every repetition, so the bits of nearly every multiplication in the trace are public. In both attacks we use a supervised classifier to recover the unknown value. In key generation that value is the private key itself, whereas in signing there are three distinct routes to it: the key itself, a party's share of the key, and a party's share of an S-box output. Recovering any one of them is enough to recover the private key. We validate both attacks on an ARM Cortex-M4: one trace recovers the exact secret key from every capture we took, $100$ key generations for each of AES-128, AES-192 and AES-256, and $100$ signatures for each of AES-128f, AES-192f and AES-256f. We also discuss possible countermeasures.
Last updated:  2026-11-06
BeaverDam: A Post-Quantum Threshold Key Recovery Protocol from a One-Time Threshold Oblivious Random Function
Benedikt Auerbach, Shuichi Katsumata, Kaoru Takemure, and Ida Tucker
Secure backups are a practical necessity of E2EE messaging apps, typically relying on password-protected key-recovery (PPKR) protocols. These allow users to turn a human-memorable password into a cryptographic key with the help of a server. Recently, Signal and Juicebox proposed threshold PPKR (tPPKR) protocols, removing the trust on a centralized server. Unfortunately, known solutions are only classically secure, lagging behind the shift toward post-quantum (PQ), or to be more precise, hybrid secure E2EE. We present BeaverDam, a novel tPPKR protocol that is PQ secure with efficiency close to existing classical protocols. It also easily extends to hybrid security, standing as the first concretely efficient hybrid-secure tPPKR protocol. BeaverDam relies on a new primitive we introduce --- one-time threshold oblivious random functions (tORF). Unlike full-fledged OPRFs, which are notoriously difficult to construct in a PQ-secure manner, one-time tORF offers weaker but sufficient security guarantees tailored to the tPPKR setting. We then construct an efficient one-time tORF called Beaver, inspired by multi-party computation (MPC) techniques. Owing to the one-time feature, we only need to securely compute a 2-wise independent hash function, making our protocol very efficient. We conclude by presenting a practical instantiation of BeaverDam and comparing its performance to state-of-the-art classical tPPKR protocols, namely Signal's SVR3 and Juicebox.
Last updated:  2026-11-06
Weights Come Almost for Free in Ramp Threshold Cryptography
Aarushi Goel and Mingyuan Wang
A weighted threshold access structure assigns a weight to each party and authorizes a subset of parties whenever their total weight exceeds a prescribed threshold. Most existing approaches to designing multiparty cryptographic protocols in the weighted threshold setting, however, either incur complexity that grows with the total weight assigned to the parties or remain far from concretely efficient. Toward \emph{concretely efficient} weighted threshold primitives, we take a different route and relax to the \emph{ramp} setting, in which two thresholds are prescribed: a subset whose total weight falls below an $\alpha$ fraction of the total is unauthorized, while a subset whose total weight exceeds a $\beta$ fraction is authorized. Exploiting the gap between these two thresholds, we obtain the following results. 1. Given any weighted ramp threshold access structure with privacy threshold $\alpha$ and reconstruction threshold $\beta$, where $0\!<\!\alpha\!<\!\beta\!<\!1$, we present a weight compression technique that reduces the total weight to $\approx n/(2(\beta-\alpha))$ while preserving the authorized and unauthorized sets. Combined with the standard player-virtualization paradigm, this yields concretely efficient weighted threshold cryptographic protocols with only a multiplicative overhead of $\approx 1/(2(\beta-\alpha))$ over their unweighted counterparts. Previously, the best known compression technique in this setting, due to Benhamouda et al.~[ITC'23], achieved total weight $\approx 5n/(\beta-\alpha)$. 2. Player virtualization has an inherent drawback: a party's share size and workload grow in proportion to its (compressed) weight, so the parties in which the most trust is placed also bear the largest computational and communication costs. Thus, although the \emph{overall} overhead is $O(1)$, the cost borne by a single party can still be $O(n)$ times that in the unweighted setting. Our second result removes this imbalance. Building on our compression technique, we construct a linear secret-sharing scheme in which every party receives a share of size $\widetilde{O}(1)$, independent of its weight, for a total share size of $\widetilde{O}(n)$, nearly matching the $O(n)$ complexity of standard unweighted threshold secret sharing.
Last updated:  2026-11-09
Independent Leakage Does Not Save Evasive LWE: Refuting Folklore Fixes in the Private-Coin Setting
Yao-Ching Hsieh
The evasive learning with errors (evasive LWE) assumption has enabled a wide range of advanced cryptographic constructions from lattices in the past few years. The simple intuition that LWE remains secure even when additional ``non-zeroizing'' short preimages are given has proved highly versatile in applications. Unfortunately, recent counterexamples have refuted its general private-coin formulations, showing that having the short preimages along with arbitrary auxiliary leakage about the secret and target matrices can invalidate this intuition. To preserve important applications, particularly witness encryption, the community has sought to repair the assumption by restricting the allowed leakage. One folklore proposal requires the secret and target matrices, together with their respective leakage, to be generated independently. This restriction appears to preserve the application to witness encryption while ruling out all previously known counterexamples. In this work, we refute this proposal. Assuming LWE and indistinguishability obfuscation, we show that both the binding and hiding variants of private-coin evasive LWE are false even with the independent sampler restriction. Our counterexamples exploit only auxiliary leakage about the target matrix. We sample the secret honestly from a standard uniform or Gaussian distribution, independently of the target and its leakage, and we use no auxiliary information about the secret.
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.