All papers in 2026 (2899 results)

Last updated:  2026-11-15
Bounds of Falcon's Fast Fourier Sampler with Fixed-Point Arithmetic
Vincent Hwang
Falcon was selected by NIST for standardization as FN-DSA in the forthcoming FIPS 206, and its signature generation is driven by the fast Fourier sampler, defined over the complex numbers. This report bounds the Rényi divergence between the sampler in real arithmetic and its fixed-point implementation, on the tail-cut event, where every sample stays within a fixed number of standard deviations of its center. For a reference bit security λ = 128 at n = 512 and λ = 256 at n = 1024 over 2^64 signatures, the bound keeps 126.28 and 248.78 bits at the plain center, and 126.70 and 253.53 bits at the fractional center, for every key the key generation accepts. The floating-point signer's analysis is left open: it stopped at a numerical contradiction while closing its hypotheses. We propose four changes to the fixed-point implementation. (i) The one-dimensional sampler SamplerZ rejects a candidate at a saturated shift instead of saturating the shift. (ii) The key generation runs three new checks on the tree: it bounds the largest relative deviation of a leaf standard deviation, the multiplicative perturbation of the tree map, and the largest remainder on the tail-cut event. The first two changes carry the proof: dropping (i) costs the saturated leaves' term, and dropping (ii) leaves no security level at any number of signatures for our proof. (iii) The root node is computed with the NTRU identity, and (iv) an inversion followed by a multiplication becomes a division; these two simplify the proofs. The bits rest on machine-checked proofs and on three code-alignment hypotheses. The sampler's kernels and its recursion are proved in CryptoLine on the aarch64 objects of the C code, compiled at -O3 and traced under QEMU's Cortex-A72, and composed in Lean. The analysis is carried in Lean where its model reaches, every proof line it does not reach recorded as such, and the Lean theorems take the summability of their series as a hypothesis. The bound samples nothing. This report was written with agents under the human author's detailed guidance, a blend of formal verification of machine code, the Rényi divergence argument of lattice sampling, and the engineering of an agent harness; the tree map's perturbation is a multiplicative one, in the sense of relative perturbation theory. The compiled objects have known timing side channels: in the key generation's arithmetic the compiler turned constant-time C into key-dependent branches in the Cortex-A72 build, so that arithmetic is verified on the object compiled for the Apple M1, which selects, and a branchless assembly reference is future work with the agents.
Last updated:  2026-11-15
A Bleichenbacher bit-by-bit oracle attack from partial message knowledge
Juan Carlos García Escartín
Oracle attacks show the importance of a correct implementation of cryptographic standards when translated into code. A notable example is the Bleichenbacher attack on RSA with PKCS#1 v1.5 padding and all the improvements that have been suggested over the decades. This paper shows how an attacker knowing a few least significant bytes of an RSA message can take advantage of a server with an oracle side-channel to decrypt the full message bit by bit. We will consider two oracles that can be tested with chosen ciphertexts: one revealing whether the decrypted message starts with the 00 02 bytes and a second one revealing if the decrypted message is fully PKCS compliant. For an attacker knowing the three least significant bytes of the message, the first oracle provides an attack where one oracle call gives the next least significant bit of the message and the second an attack which requires, with high probability, a small constant number of oracle calls to the oracle, with a constant which depends on the length of the message and the desired probability of success. The attack divides the message bits into two sections, one with the known part and one with the unknown part, and then chooses transformations that will keep the unknown part, except for the last unknown bit, orders of magnitude below the integer coming from the known part. The resulting string either gives a valid padding or not depending on the value of the unknown bit. The attacker can minimize the number of oracle calls at the cost of some local computation. Finally, the same method is adapted to show how it can also be used to extract the few least significant bytes of the message with an increased cost where the main complexity is finding a second valid message with a correct padding starting from the original captured ciphertext.
Last updated:  2026-11-15
Modular Walsh rigidity for Boolean functions of degree at most four
Filipe Martins Vono, André Oliveira Naufel de Toledo, and Valéria Gonzaga Santos
In sixteen variables, a Boolean function of degree at most four is bent as soon as every Walsh coefficient is $4$ or $5$ modulo $9$. More generally, let $m\ge4$ and $M=2^m$. We prove that a function of degree at most four on $4m$ variables is bent if all its Walsh coefficients are congruent to $\pm M^2$ modulo a single odd integer $p\ge9M/16$. The sign may vary with the frequency. This improves the earlier sufficient bound $p>7M/12$ and includes the endpoint $M=16,\ p=9$. The proof uses the degrees of the low binary digits of the normalized spectrum, low-weight Reed-Muller words, and bounds on groups of Fourier coefficients. As an application, a rotation-symmetric bent function of degree at most four in $888$ variables remains bent on the $24$-variable subspace obtained by repeating a block $37$ times.
Last updated:  2026-11-19
Aker: Efficient Two-Party SLH-DSA
Yaron Salman, Ben Riva, and Dmitry Kogan
Threshold signing is widely deployed to protect cryptographic keys, but extending these deployments to post-quantum signatures remains challenging. While NIST's lattice-based signatures now have efficient threshold protocols, distributed signing for SLH-DSA (FIPS 205), NIST's stateless hash-based signature standard, has been considered prohibitively expensive because it lacks the algebraic structure those protocols typically exploit. We present Aker, a maliciously secure two-party signing protocol compatible with an unmodified FIPS 205 verifier. Our approach combines generic secret-sharing MPC with four optimizations that leverage the structure of the SLH-DSA hypertree. Evaluating active layers concurrently collapses sequential hashing depth to that of a single chain. Caching public keys allows authentication paths to be computed locally, so that only the signing leaf is evaluated in MPC. Fixing path prefixes lets signers reuse entire upper-layer signatures across messages. Finally, one-time subtrees sample lower-layer signature components locally rather than deriving them from the secret key, further reducing MPC work. Some of these gains come at the cost of stateful signers and a lower limit on the total number of signatures per key. We implement and evaluate our protocols using SHAKE-based SLH-DSA in two deployment settings. For server--server deployments, we combine these techniques with a new GPU engine for maliciously secure Boolean GMW. Between two single-GPU servers in separate cloud providers over the public Internet, online signing for SLH-DSA-128f takes $2.09$ seconds, or $0.76$ seconds with a lower signature limit, while input-independent Beaver triple generation runs offline and scales horizontally across keyless CPU workers. For client--server deployments, a periodic offline session prepares a reserve of over a hundred signatures, after which online signing requires only four low-bandwidth communication rounds and local hashing. These results show that maliciously secure distributed signing for SLH-DSA is within reach today in the two-party setting, while our optimizations extend directly to more parties.
Last updated:  2026-11-15
LEASH: When LaBRADOR’s Guarantees Go Astray
Xiang Wang and Ji Xiang
Succinct arguments enable efficient verification of large computations, while lattice-based constructions offer a promising path toward post-quantum security. LaBRADOR advances this direction through recursive reductions of knowledge that achieve compact proofs. However, these reductions require careful control of witness norms, relation preservation, and knowledge extraction to maintain their claimed guarantees. In this paper, we revisit the correctness and security analysis of LaBRADOR. We construct explicit counterexamples showing that its concrete parameter-selection strategy can fail to preserve completeness, even for valid binary R1CS witnesses. We further identify inconsistencies in recursive relation transformations and inaccuracies in the probability bounds underlying its knowledge extraction analysis. We develop targeted repairs and provide corresponding mathematical analyses, examining how changes to norm bounds, decomposition parameters, and challenge distributions affect the resulting security and efficiency guarantees. Our results highlight the importance of rigorous parameterization and compositional reasoning in lattice-based succinct proof systems.
Last updated:  2026-11-15
Communication-Efficient Threshold-CKKS Aggregation for Secure Cross-Silo Federated Learning
Jihyung Kook, Dokyeong Kang, and Eunsang Lee
Federated learning (FL) enables collaborative training without sharing raw data, but exchanged model updates may reveal sensitive information. Homomorphic encryption (HE) protects these updates, yet combining collusion resistance, flexible aggregation, dropout handling, and communication efficiency remains challenging. We propose a communication-efficient threshold-CKKS protocol for cross-silo FL with Full and Sparse profiles, without a trusted key-distribution center. Independent local encryption keys enable server-side weighting and dropout-aware reaggregation without ciphertext retransmission. Sparse uses RLWE-MLWE conversion for fine-grained chunk-wise aggregation while retaining compact RLWE packing. Seeded ciphertext reconstruction, selective coefficient transmission, and compressed collective decryption further reduce communication. We establish whole-view simulation security for fixed-cohort executions without dropout or retry against a semi-honest server colluding with up to $c$ clients, under explicitly permitted leakage and a minimum cohort requirement of $\tau\ge c+2$. Experiments on CIFAR-10 and CIFAR-100 show that Full incurs only 0.32 and 0.29 percentage-point accuracy losses, with 1.78$\times$ and 1.76$\times$ the online communication of plaintext, respectively. At matched accuracy levels, Sparse reduces online communication by factors of approximately 79 and 84 compared with FedPHE. At accuracy targets five percentage points below full-transmission plaintext, Sparse requires only 2.5$\times$ and 2.1$\times$ the online communication of plaintext, respectively. These results narrow the communication gap between encrypted and plaintext FL.
Last updated:  2026-11-15
Four Ciphers in One: Full-Round Attacks on the Reference Implementation of LLBC
Sei Kofuku and Yasutaka Igarashi
LLBC is a 128-bit low-latency block cipher for IoT applications, proposed in the IEEE Internet of Things Journal in 2025. The designers release a reference implementation in C and Verilog for reproducibility. The test vectors in the proposal are outputs of this implementation. We show that the reference implementation differs from the specification of the peer-reviewed proposal in eight points. In particular, its round function uses the rotation amounts $(32,16)$ instead of $(3,19)$. We prove that an LLBC-type cipher with rotation amounts $(b_1,b_2)$ is a product of $g/4$ independent ciphers when $g=\gcd(64,b_1,b_2)$ is a multiple of 4. Hence the cipher splits when $g$ is a multiple of 8. As a result, the reference implementation splits into four 32-bit ciphers that never mix. With this split, we attack all 20 rounds. We give a distinguisher with probability 1 from two chosen plaintexts. We decrypt any ciphertext with $2^{32}$ chosen plaintexts. We recover the master key from three known plaintexts with $2^{80}+3\cdot 2^{16}$ encryptions, which is below exhaustive search by a factor of $2^{48}$. The designers estimated that the best attack on the specification reaches nine rounds. On a single PC, our decryption attack on all 20 rounds of the reference implementation took 175.5 seconds. We also study standard techniques. A standard automatic search returns 20-round impossible differentials and zero-correlation approximations. In contrast, the classical differential and linear characteristics and the integral properties that we examined distinguish only 9, 10, and 8 rounds, respectively, inside one part. We also show that the assumption of the usual models, which treat the S-boxes as independent, does not hold for the reference implementation. Finally, we recommend that designers check the released code against test vectors made independently from the specification and check the diffusion of the released code itself before publication.
Last updated:  2026-11-14
Concrete Quantum Circuit Implementations and Resource Estimates for the Quantum 3 and 4-Sieves
MohamadAli Khajeian
Chailloux and Loyer (2023) introduced quantum 3- and 4-sieve algorithms for the Shortest Vector Problem (SVP) with asymptotic analyses, but concrete circuit implementations remain unexplored. We present the first complete reversible circuits for both algorithms, designing inner-product predicates with signed symmetric squaring across three architectures (low-qubit, balanced, and low-depth). We validate these circuits using exact sparse state-vector simulations that match an independent mathematical model to a precision of \(10^{-13}\). Crucially, we show that the original amplitude-amplification oracle fails when inner Grover searches are approximate and correct it to test the full configuration. Applying our arithmetic techniques to the published NV 2-sieve oracle reduces its T-count by \(9.4-14\times\) and T-depth by over three orders of magnitude. Finally, we provide exact per-call logical resource estimates for the configuration predicates and the NV oracle at cryptographic dimensions, detailing the architectural trade-offs for the core predicates used in quantum tuple sieving.
Last updated:  2026-11-14
BMuSig-L: Blind Multi-Signature from Lattice
Anirban Chakraborty, Mriganka Dey, Nikita Dey, Avijit Dutta, and Subhabrata Samajder
Blind signatures and multi-signatures are two fundamental cryptographic primitives for privacy-preserving decentralized protocols. A blind signature enables a user to obtain a signature on a message from a signer while keeping the message hidden from the signer. Moreover, the signer cannot subsequently link the resulting signature to the corresponding signing session. In contrast, a multi-signature scheme allows a group of signers to jointly generate a single signature on a message. Blind multi-signatures, a primitive recently introduced by Karantaidou et al. (AsiaCCS 2024), combine the advantages of both techniques. They enable a user to obtain a joint signature from a group of signers while ensuring that the message remains hidden from every signer and that colluding signers cannot later link the final signature to the corresponding signing session. Recently, Bisht et al. proposed $\textsf{BMuSig2}$ (AsiaCCS 2026), a Schnorr-compatible blind multi-signature scheme whose security is based on the hardness of the discrete logarithm problem. In this paper, we present $\textsf{BMuSig-L}$, a lattice-based, two-round, concurrently secure blind multi-signature scheme. Our construction builds upon the lattice-based multi-signature scheme $\textsf{MuSig-L}$ (CRYPTO 2022), the concurrently secure blind signature scheme of Fuchsbauer and Wolf (CRYPTO 2024), which employs non-interactive zero-knowledge arguments and public-key encryption, and a knowledge-sound non-interactive argument system. We prove that $\textsf{BMuSig-L}$ is one-more unforgeable under the assumptions of the unforgeability of $\textsf{MuSig-L}$, the computational soundness of the underlying non-interactive zero-knowledge proof system, and the knowledge soundness of the employed non-interactive argument of knowledge. Finally, we present a prototype implementation of $\textsf{BMuSig-L}$ and evaluate its performance in terms of signature size and verification time.
Last updated:  2026-11-14
Circulant Diffusion Layers: Cost Bounds and Rectangle Reuse
Enyan Li and Gaoli Wang
We study the addition complexity of sparse invertible circulant matrices over $\mathbb{F}_2$ and odd prime fields. Diffusion is measured by branch numbers, and prime field coefficients are restricted to $\{0,\pm1\}$. Finding optimal general circuits is often difficult, particularly at large matrix orders. Rectangle reuse offers a simpler alternative for explicit circuit construction. We compare the general circuit cost $C_g$ with the rectangle reuse cost $C_{\mathrm{rect}}$, and show that rectangle reuse can approach, and sometimes attain, the general circuit optimum while providing shallow implementations in practical cryptographic parameter settings. To the best of our knowledge, we establish the first lower bounds on both $C_g$ and $C_{\mathrm{rect}}$ for general matrices in terms of matrix order and branch numbers. We then exploit cyclic structure to obtain cost classifications, sharper bounds, and explicit constructions at minimum weight. Over $\mathbb{F}_2$, we give a complete classification of rectangle costs over all invertible weight-three circulants and determine their exact minima at every order $n\ge4$. The minimum costs in both the general circuit and rectangle reuse models equal $3n/2$ at every even order, with connected constructions attaining these minima. Over every odd prime field, connected weight-three constructions likewise attain both minima, namely $\lceil3n/2\rceil$, for every $n\ge4$. For branch number five, we prove the rectangle lower bound $2n$ and give connected families attaining it at infinitely many orders. For branch number six, we exploit cyclic structure to sharpen the general rectangle bounds and determine certified exact rectangle minima at selected orders. Finally, we characterize the effects of connectivity and circuit depth. For weight-three circulants over $\mathbb{F}_2$ or $\mathbb{F}_p$ with $p\ge5$, the minimum gate count at depth two equals the rectangle cost. These results provide theoretical cost benchmarks and explicit constructions for designing circulant diffusion layers with low gate counts and shallow circuits.
Last updated:  2026-11-14
Phase-Hiding Programmable Bootstrapping with Online Client Assistance
Xingke Chai
Programmable bootstrapping in Fast Fully Homomorphic Encryption over the Torus (TFHE) uses a bootstrapping key (BSK) to control successive external products during blind rotation, incurring computational cost and introducing and propagating error. We introduce Phase-Hiding Programmable Bootstrapping (PH-PBS), in which the key-holding client precomputes single-use phase tokens encrypting randomly shifted monomials and assists refresh online. Through phase sharing and a small garbled circuit, the parties compute a masked rotation correction that lets the server align a token for lookup, replacing BSK-driven blind rotation. Using the aligned monomial, the server evaluates private lookup tables, retains ciphertexts for further computation, and delivers only prescribed terminal plaintexts to the client. To reduce token preparation and transmission costs, we construct a projection independent of table values that, under matched randomness and quantization, produces the same complete learning-with-errors (LWE) output ciphertext as the full quantized-token path, coefficientwise. We analyze error propagation in both fixed key-switching orders and derive numerical failure-probability bounds for finite sequential tasks with fixed public schedules and shared key-switching material, under the specified finite-precision model and conditional on successful initialization. Under the stated cryptographic assumptions, we simulate each party's complete session view in the classical static semi-honest model and bound the distinguishing advantage. On a four-bit workload where PH-PBS and the TFHE-rs baseline both use 32-bit coefficients in their key-switching keys and matched decomposition parameters, mean local refresh time with pre-core key switching decreases from 18.392 ms to 3.713 ms, a 79.8% reduction, including both parties' computation and consumed-token preparation. Separate measurements with pre-core key switching place PH-PBS's normalized core-output error variance at approximately one three-thousandth of the corresponding baseline variance. Across the examined modes and network scenarios, estimated refresh-stage times are 46.3%–80.1% lower than those of the corresponding TFHE-rs baselines; these estimates assume serial computation and communication, completed initialization, and sufficient initial correlated oblivious-transfer material.
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-17
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. We call producing such a key \emph{opening} the codewords, and ask how many key bits it takes. We first show that every adaptively secure PRC yields a \emph{$q$-use code} with the same key length, namely its opened key together with the $q$ uniform strings it opens. Lower bounds for these information-theoretic objects therefore hold unconditionally and apply to every adaptively secure PRC, including current designs based on hardness assumptions. We then show that every opening costs key bits beyond the opened message: $\omega(\log\lambda)$ without errors, $\frac{1}{\rho^2}\cdot\omega(\log\lambda)$ under random noise of correlation $\rho$, and, for every alphabet, a constant fraction of the codeword if every error pattern up to a constant fraction of the length must be corrected, even when an unbounded adversary chooses it with the key. We call the last cost the robustness tax. As for non-committing encryption, adaptively secure PRCs thus need an a-priori bound on the number of openings, but each opening costs more, because of the tension between soundness and robustness: a sound key must reject almost all strings, yet accept a region around each uniformly random codeword. We show simple stateful codes meet these bounds and yield stateful PRCs with perfect bounded adaptive security. Finally, unlike for non-committing encryption, a programmable random oracle cannot pay this cost under noise. Errors move the decoder's queries away from any programmed point, so for decoders with non-adaptive oracle queries, every opening must still be paid for in key bits or in programmed points that the decoder reads on a noticeable fraction of inputs.
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-17
Twisted Towers: Fully Costed Special Tower NFS Attacks on BLS12-381 and BN254
Gautam Botrel
BLS12-381 is commonly said to offer "126 bits" of security and BN254 "about 100 bits". Both figures are estimates of the special tower number field sieve (STNFS) in the target group $\mathbb{F}_{p^{12}}^*$, and both count abstract operations in models that leave out whole phases of the attack. We replace them by complete ledgers in which every step is priced in machine instructions: relation collection, cofactorisation, filtering, linear algebra, both individual logarithms and all failures. Under explicitly listed heuristics, a complete attack executes $2^{127.5}$ instructions for BLS12-381 and $2^{103.2}$ for the BN254 curve used in Ethereum, with success probability above $0.998$. For BLS12-381 this is $9.6$ bits below Pollard's rho on the curve counted the same way, where operation counts suggested one bit: the target group is clearly the weaker side. It is also $9.8$ bits below what the published design costs when it is completed with standard components and charged in full ($2^{137.3}$ instructions, level with rho). For BN254 our figure confirms the accepted level and gives it a concrete meaning. The method rests on three ideas and on a systematic reduction of the work per sieved cell. First, a twisted tower: a unit $c$ of the sextic base field with $c\,\sigma(c)=-1$ turns the usual sign symmetry into a symmetry of order four that acts as a Frobenius power, so that relations and ideals come in orbits of four and the linear system has Gaussian-integer entries. Second, counting each relation once: coefficient-cube estimates count unit multiples of a relation as distinct; for the published BLS12-381 design only $2^{-2.8}$ of the counted relations are distinct, and we sieve a fundamental domain instead. Third, a sieve organised around reuse: only the harder side is sieved, tiny primes are handled by batch arithmetic, and the hits of a prime ideal are replayed from lists shared by all slices. A product-form linear algebra and a planned descent complete the method. Each technique is stated for a general special pair of tower shape $(6,2)$ and then instantiated on the two curves. Nothing was run at full size; the final designs assume up to $2^{112}$ bytes of storage, which the cost model does not charge; and the practical security of both curves 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-18
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 OlÆF 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 OlÆF 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 a single unverified decryption query or a single non-target verification query, followed by one forgery attempt, achieves a success probability of $3/8$, exceeding the claimed bound of $1/4$. We also derive generalized expressions for the forgery success probabilities of both attacks. Finally, we discuss the corresponding repair requirements.
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-19
QUASI: Post-Quantum Quorum Attestation of Pre-Validated Statements
Maksym Ioffe and Dahlia Malkhi
We present QUASI, a newly conceived class of hash-based, post-quantum-secure protocols that enable a group of parties to produce a publicly verifiable attestation about a pre-validated statement. QUASI produces attestations that reduce the size and verification cost to a fraction of a full hash-based signatures collection, without relying on SNARKs or a trusted setup. QUASI rests on a surprising discovery: each party need not sign the entire statement. Authenticating only a small subset of symbols suffices for a quorum to attest to the whole. We turn this insight into a randomized construction that achieves reductions of more than 10x 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. Operationally, QUASI requires no additional interactive setup or preprocessing beyond independent key generation by parties for the underlying hash-based authentication scheme. 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.
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.