• [digest] 2026 Week 44

    From IACR ePrint Archive@noreply@example.invalid to sci.crypt on Mon Nov 2 03:26:36 2026
    From Newsgroup: sci.crypt

    ## In this issue
    1. [2025/1232] OMIX: Offline Mixing for Self-Tallying Elections
    2. [2026/201] On Lifting AGM Security to the AGM with Oblivious ...
    3. [2026/236] Sharing a Secret Anamorphically: Secret Shares ...
    4. [2026/667] The Information-Theoretic Limits of Hiding Among ...
    5. [2026/1139] Exploiting the complexity of Lattice Isomorphism ...
    6. [2026/1202] Morphic Accumulators and Applications: Optimal ...
    7. [2026/1784] Faster Post-Quantum zkSNARK Provers Using the LCH ...
    8. [2026/2368] Low-Latency Parallel Digit Decomposition and Sign ...
    9. [2026/2462] Hybrid QuantumrCoComputational Key Distribution with ...
    10. [2026/2465] Snapshots of TEE-Based Encrypted Databases Leak ...
    11. [2026/2546] New IND-CPA-D Attacks on BFV and BGV
    12. [2026/2630] Exact Error Bootstrapping and Comb Bootstrapping in ...
    13. [2026/2639] Private Information Retrieval with Accountability ...
    14. [2026/2645] Isotaxis: Optimal Asynchronous Byzantine Consensus ...
    15. [2026/2646] Mikros: Bitwidth-Aware SNARKs over Extensions of ...
    16. [2026/2647] Revisiting ZMAC+: Birthday-Bound Attacks and a ...
    17. [2026/2648] Notes on BulletProofs++ Range Proofs
    18. [2026/2649] LINE-Break: Cryptanalysis and Reverse Engineering ...
    19. [2026/2650] On Robust Combiners for Pseudorandom Codes and PKE ...
    20. [2026/2651] HELLO, GOODBYE: Concurrent General Composition From ...
    21. [2026/2652] Reverse Substitution in Secret Sharing: The ...
    22. [2026/2653] Analyzing Compiler-induced Constant-time Violations ...
    23. [2026/2654] When Algebraic Structure Meets Too Many Hints
    24. [2026/2655] OblivDGL: Oblivious Deep Graph Learning Made Practical
    25. [2026/2656] Falcon Key Recovery from Joint Sampler Leakages
    26. [2026/2657] Poly2MsgLeaks: Certified Key Recovery from ...
    27. [2026/2658] Unshuffling Fisher-Yates: Practical Recovery of ...
    28. [2026/2659] Alg\{Ossa\}: Decentralized Secure Aggregation with ...
    29. [2026/2660] Towards Quantum Sensing for Side-Channel Analysis
    30. [2026/2661] Radical isogenies on every model
    31. [2026/2662] Tractable, Not Truncated: Colored-Noise TRNG ...
    32. [2026/2663] Quantum Multi-Collision Lower Bounds for Arbitrary ...
    33. [2026/2664] Rerandomizable Garbling Beyond BHHO-KMHE and a ...
    34. [2026/2665] Shor's algorithm compiled on cat qubits: 22 593 ...
    35. [2026/2666] Efficient SIMD SHAKE through Cost-Aware Permutation ...
    36. [2026/2667] Faster complete formulas and their application to ...
    37. [2026/2668] An Algebraic Polynomial Evaluation Datastructure ...
    38. [2026/2669] PIR through the Lens of Probabilistic Inference
    39. [2026/2670] Barriers to Identity-Based Encryption in Generic ...
    40. [2026/2671] Beyond the Event Horizon of Keccak, Extending the ...
    41. [2026/2672] Nenya: Efficient zkSNARKs for Integer Rings Z/2kZ ...
    42. [2026/2673] Beyond the Scope of This Paper: Practical Flash- ...
    43. [2026/2674] Sybil-Proofness of Generalized Adaptive Clinching ...
    44. [2026/2675] High Precision Noise Cleaning for CKKS with ...
    45. [2026/2676] Optimality and Efficiency of Higher-Order Rank- ...
    46. [2026/2677] Smoothness of Shortest Isogenies to Frobenius ...
    47. [2026/2678] From Quantum Mechanics to the Hidden Subgroup ...
    48. [2026/2679] Cryptanalysis and Enhancement of VTBSAE: Provably ...
    49. [2026/2680] (Balanced) Boolean Functions on 375 Variables with ...
    50. [2026/2681] Improving Code Rate and Query Complexity for the ...
    51. [2026/2682] A Quantitative Evaluation of Constant-Time Analysis ...
    52. [2026/2683] Stop Calling Them Provers: The Case for Calling ...
    53. [2026/2684] SoK: Multiple Concurrent Proposer Blockchains
    54. [2026/2685] Quasi-polynomial time algorithms for block basis ...
    ## 2025/1232
    * Title: OMIX: Offline Mixing for Self-Tallying Elections
    * Authors: S|-bastien Canard, Liam Medley, Duy Nguyen, Duong Hieu Phan
    * [Permalink](https://eprint.iacr.org/2025/1232)
    * [Download](https://eprint.iacr.org/2025/1232.pdf)
    ### Abstract
    In e-voting, a mix-net is a widely used system for shuffling votes in order to guarantee voter privacy. The core principle is as follows: (1) N voters cast their votes; (2) a sequence of mix-servers shuffles the N encrypted ballots, thereby randomly permuting the underlying votes; and (3) trustees jointly decrypt the shuffled ballots to compute the tally.
    This approach, however, relies heavily on trusted parties after the voting phase and raises serious robustness issues. For example, what happens if the mix-servers disrupt the protocol, or if trustees lose the decryption key during the tallying phase? A recent incident in the IACR board election illustrates this problem: one of the three trustees involuntarily lost their key, requiring the entire community to restart the vote.
    We introduce OMIX, an offline-mixing architecture for self-tallying elections: trustees prepare public functional decryption keys embedding a hidden random permutation before voting, voters then cast encrypted ballots, and anyone can compute the shuffled tally without further trustee participation. Function-hiding inner-product functional encryption supplies the key mechanism, and a voter-assisted correction phase accommodates dropouts.
    The main technical component is a verifiable offline shuffle of a matrix of encrypted functional keys. We extend linearly homomorphic signatures with tag-binding and two-dimensional tags: row tags support hidden row permutations, while column tags bind entries to their respective voters. In the certified-input model, these properties allow trustees to certify matrix transformations, with final proof size and verification cost independent of the number of mix-servers.
    Together, these components enable distributed preparation and public certification of permutation keys within a client-lightweight voting architecture. Each voter registers and casts a ballot with computation and communication independent of N, while preprocessing per trustee, public helper-key size, and tallying work are quadratic. This establishes a foundation for self-tallying elections with offline mixing and opens the way to further improvements in system-wide efficiency.
    ## 2026/201
    * Title: On Lifting AGM Security to the AGM with Oblivious Sampling
    * Authors: Juraj Belohorec, Pavel Hub|i-iek, Dominik Stejskal
    * [Permalink](https://eprint.iacr.org/2026/201)
    * [Download](https://eprint.iacr.org/2026/201.pdf)
    ### Abstract
    The Algebraic Group Model (AGM) is widely used to prove the security of cryptographic schemes involving groups and pairings. It requires adversaries to explain how their output group elements are obtained from the elements they have received. The AGM with Oblivious Sampling (AGMOS), introduced by Lipmaa, Parisella, and Siim (TCC 2023), additionally allows adversaries to sample group elements without learning their discrete logarithms. This models capabilities such as hashing to a group, but complicates security proofs: security in the AGM does not always imply security in the AGMOS.
    We give a framework for transferring AGM security proofs to the AGMOS for a broad class of pairing-based security games. Our results separate the existing AGM argument from the additional reasoning needed to handle obliviously sampled elements. Under the Find Polynomial Representation (FPR) and Tensor Oracle Find Representation (TOFR) assumptions, this additional reasoning can be handled by general reductions. Games with further requirements, such as extractability, also require a lifting condition that ensures these requirements are preserved.
    We first establish a lifting theorem for non-interactive games and apply it to KZG extractability, the multivariate Adaptive Rational Strong Diffie-Hellman assumption, and the special-soundness of the Polymath SNARK. We then extend the framework to interactive games that use random oracles and other oracles that depend on the trapdoor. In the interactive setting, we apply the theorem to the existential
    unforgeability of BLS signatures and strong unforgeability of BBS signatures under FPR/PDL and TOFR assumptions. For BLS, we also provide an AGM security proof for Type-3 pairings, adapting the original Type-1 analysis.
    Our framework allows existing AGM proofs to be reused in the AGMOS.
    To apply the framework, it is enough to check its requirements, including oracle simulation and, where needed, the lifting condition, without repeating the full security proof.
    ## 2026/236
    * Title: Sharing a Secret Anamorphically: Secret Shares Disguised as Signatures * Authors: Gennaro Avitabile, Vincenzo Botta, Daniele Friolo
    * [Permalink](https://eprint.iacr.org/2026/236)
    * [Download](https://eprint.iacr.org/2026/236.pdf)
    ### Abstract
    Anamorphic Encryption (Persiano, Phan and Yung, Eurocrypt '22) allows private communication in a challenging setting where encryption is severely controlled by a central authority (henceforth the dictator) who can demand the users to surrender their secret keys. Anamorphic Signatures (AS) (Kutylowski, Persiano, Phan, Yung, Zawada, Crypto '23) face the even more restrictive world where only authentication is allowed but users still want to send secret messages despite the repressive control of the dictator holding their signing key. Several constructions have been proposed so far, but they all come with some limitations.
    We propose a new flexible setting where digital signatures are used to covertly embed secret shares that $t$ out of $N$ designated receivers can combine to recover a covert secret. We formalize this new primitive called Anamorphic Secret Sharing Signatures (ASSS) together with new robustness, forward/backward secrecy, and private unforgeability notions and we give a construction for Schnorr-like signatures overcoming the limitations of previous constructions. ASSS additionally imply (regular single-receiver) AS, but two signatures (instead of one) are needed to recover the covert message.
    ## 2026/667
    * Title: The Information-Theoretic Limits of Hiding Among Decoys in the Shuffle Model
    * Authors: Pengcheng Su, Haibo Cheng, Ping Wang
    * [Permalink](https://eprint.iacr.org/2026/667)
    * [Download](https://eprint.iacr.org/2026/667.pdf)
    ### Abstract
    Hiding a genuine message among plausible decoys is a recurring principle in cryptography and privacy, underlying honeywords, symmetric encryption, and anonymous data collection. We study the information-theoretic security of mechanisms that release a uniformly shuffled sequence containing one genuine message and $n-1$ decoys over a $d$-symbol alphabet. We characterize how restrictions on decoy generation determine achievable secrecy.
    We distinguish four classes of decoy mechanisms: i.i.d., heterogeneous independent, correlated message-oblivious, and message-dependent. For every fixed $d\ge2$, the optimal worst-case mutual information over message priors is $\Theta_d(n^{-1})$ for both independent classes and $\Theta_d(n^{-2})$ for correlated message-oblivious mechanisms. A discrete spectral construction achieves the latter rate without knowledge of the prior. Message-dependent mechanisms achieve perfect secrecy when $n\ge d$. Moreover, even with $n=3$, heterogeneous decoys can improve upon i.i.d.\ decoys by an arbitrarily large multiplicative factor. These results quantify the distinct benefits of heterogeneity, correlation, and dependence on the genuine message.
    A key-symmetrization reduction shows that every perfectly correct symmetric encryption scheme with a key drawn uniformly from a key space of size $n$ admits a message-dependent shuffle construction without increasing plaintext leakage. This connects optimal message secrecy to preimage-constrained channel design and yields an exact characterization of key leakage for all message-leakage-optimal ciphers when the number of keys does not exceed the plaintext support size.
    For canonical mechanisms, whose decoys are drawn i.i.d.\ from a blanket distribution $Q$ independently of the genuine message, a unified likelihood-ratio representation yields exact expressions for mutual information, total-variation information, message recovery advantage, and expected posterior variance, together with explicit finite-sample remainder bounds for the mutual-information expansion. For a fixed non-degenerate message prior $P$, the leading asymptotic coefficient of message mutual information is minimized by $Q^*(y)\propto\sqrt{P(y)(1-P(y))}$, which generally differs from $P$. For binary alphabets, quasi-uniform blankets exactly minimize message total-variation information for every $n\ge2$, independently of the prior.
    ## 2026/1139
    * Title: Exploiting the complexity of Lattice Isomorphism Problem via Irreducible Decomposition
    * Authors: Kaijie Jiang, Yinchen Liu
    * [Permalink](https://eprint.iacr.org/2026/1139)
    * [Download](https://eprint.iacr.org/2026/1139.pdf)
    ### Abstract
    The Lattice Isomorphism Problem (LIP) is a computational problem that has recently been introduced into cryptography and is believed to be hard. Its search version, Search Lattice Isomorphism Problem (SLIP), is considered even harder than the Shortest Vector Problem (SVP), yet its complexity is still not well understood. Haviv and Regev (SODA 2014) showed that the decisional version (DLIP) lies in a statistical zero-knowledge class and is therefore unlikely to be NP-hard. This result does not apply to the search version, which motivates the question of whether NP can reduce to SLIP.
    Our main result answers this question negatively. We show that every language reducible to SLIP lies in AM and coAM, by analyzing the direct-sum structure of irreducible lattices. Consequently, NP cannot reduce to SLIP unless the polynomial hierarchy collapses, and there is no reduction from SVP to SLIP unless the polynomial hierarchy collapses.
    We also study several problems closely related to LIP and establish reductions between its search, counting, and decisional variants. These connections mirror known relationships for graph isomorphism. Finally, we propose a new algorithm that uses a KZ basis to compute an orthogonal decomposition of a lattice.
    ## 2026/1202
    * Title: Morphic Accumulators and Applications: Optimal Range Proofs, Polynomial Commitments, and Ring Signatures
    * Authors: Dimitrios Papadopoulos, Qiang Tang, Jiajun Xin
    * [Permalink](https://eprint.iacr.org/2026/1202)
    * [Download](https://eprint.iacr.org/2026/1202.pdf)
    ### Abstract
    Cryptographic accumulators based on groups of unknown order (GUO) provide constant-size set membership proofs. For security purposes, existing works require first encoding set elements via division-intractable (DI) hash functions, typically instantiated as random oracles that destroy any algebraic structure.
    This confines GUO-based accumulators to a purely set-membership role, making them "incompatible" with various existing cryptographic proof techniques over committed integers in the same groups as the GUO, such as constant-size proofs of exponentiation and modular exponent relations. We introduce the notion of morphic accumulators, which replaces the DI hash with a discrete logarithm encoding $H_g(x) = g^x$, mapping set elements to a group before accumulation. We prove, under a variant of the subset product assumption in the generic group model, that this encoding is inherently division intractable, achieving the same security guarantee as random-oracle DI hashes, while simultaneously being a group homomorphism: accumulated elements retain their group-algebraic relationships. This resolves a fundamental tension between compact representation and algebraic structure: the accumulator serves simultaneously as a binding commitment to a set and as a substrate for homomorphic computation over its elements.
    Morphic accumulators yield asymptotically optimal constructions across multiple domains: range proofs with $O(n)$ prover time, $O(1)$ proof size, $O(1)$ verification with transparent setups (the first scheme to simultaneously achieve these optimal bounds); polynomial commitments with $O(n)$ prover and $O(1)$ proof size, resolving the cubic bottleneck in prior constant-proof-size GUO-based schemes; and the first linkable ring signatures with $O(1)$ signature size, transparent setup, $O(n)$ offline signing and $O(1)$ online signing.
    ## 2026/1784
    * Title: Faster Post-Quantum zkSNARK Provers Using the LCH Polynomial Basis
    * Authors: Mohammadtaghi Badakhshan, Susanta Samanta, Guang Gong
    * [Permalink](https://eprint.iacr.org/2026/1784)
    * [Download](https://eprint.iacr.org/2026/1784.pdf)
    ### Abstract
    An important class of plausibly post-quantum zkSNARKs uses univariate-polynomial interactive oracle proofs (IOPs) over binary extension fields $\mathbb{F}_{2^k}$, relying on the Fast Reed--Solomon (RS) Interactive Oracle Proof of Proximity (FRI) for low-degree testing. Their provers fold RS codewords in FRI and perform polynomial arithmetic, notably division and multiplication by subspace vanishing polynomials. Constraint polynomials and RS codewords are in evaluation form, but existing implementations perform this arithmetic in the monomial basis, requiring inverse additive fast Fourier transforms (FFTs) for coefficient recovery and forward FFTs for evaluation. On a general basis, Gao--Mateer and Lin--Chung--Han (LCH) additive FFTs incur $O(n(\log n)^2)$ field additions and $O(n\log n)$ field multiplications for basis conversion per $n$-point transform, and Lagrange-based FRI folding performs a field inversion per coset.
    We carry out this arithmetic directly in the LCH polynomial basis for arbitrary $\mathbb{F}_2$-bases. We introduce a divide-and-conquer algorithm for division by subspace vanishing polynomials directly in the LCH basis. For $n$ input coefficients, it requires $O(n)$ field operations, and on a Cantor basis it requires no field multiplications. We also show that the multiples of vanishing polynomials used for zero-knowledge blinding can be sampled directly through their LCH coefficients. Together, these remove the basis-conversion stage of the LCH additive FFT, leaving only its butterfly. We further express the FRI fold in the LCH basis: on each coset, it is an LCH inverse butterfly followed by an evaluation at the verifier challenge, and for higher-arity folds, the challenge of each stage is the value of a normalized subspace vanishing polynomial at the verifier challenge. Given constants that depend only on the domain, this yields a fold without field inversions whose folding loop performs $n(1-1/\kappa)$ field multiplications for a length-$n$ codeword and arity $\kappa$; for every input word, it outputs the same next codeword as the classical fold.
    We integrate these algorithms into the Aurora prover without changing the proof or the verifier. At $2^{19}$ constraints over $\mathbb{F}_{2^{256}}$, when all configurations use our FRI fold, the LCH-basis arithmetic speeds up the prover by $2.80\times$ over \texttt{libiop} on a general basis and by $1.24\times$ over a Cantor-basis prover that uses the LCH additive FFT. Against these baselines with their Lagrange-based FRI fold, the speedups are $3.63\times$ and $2.05\times$.
    ## 2026/2368
    * Title: Low-Latency Parallel Digit Decomposition and Sign Evaluation for CKKS * Authors: Jung Hee Cheon, Kyungah Cho, Junyoung Jung, Junho Lim
    * [Permalink](https://eprint.iacr.org/2026/2368)
    * [Download](https://eprint.iacr.org/2026/2368.pdf)
    ### Abstract
    In CKKS, the sign is commonly evaluated by polynomial approximation, and nonlinear functions such as comparison, ReLU, and max are computed through the sign. However, the discontinuity of the sign makes it harder to approximate with a polynomial as the required input bit precision $p$ grows. Alternatively, the sign can be computed by first decomposing the input into radix-$B$ digits. Existing methods extract the $u \approx p/\log B$ digits one at a time, taking $u$ sequential bootstrappings. Instead, we approximately round $u$ copies of the input to each digit's grid and obtain all $u$ digits in parallel, up to carries, with a single bootstrapping. The carries are then corrected in $O(\log u)$ depth. For the sign, a scan of the same form returns the sign directly, without recovering the exact digits.
    We show that our method distinguishes inputs separated by about $2^{-p}$ with $\Theta(p)$ modulus bits, at the cost of $\Theta(u)$ slots per input. Neither the digits nor the carries need to be computed to high precision, so our circuit, including its bootstrapping, runs at low precision. We also analyze polynomial approximation under an explicit noise and scale model, and show that, in contrast, its modulus consumption grows to $\Omega(p^2)$ bits.
    Benchmarks show a 2.04$\times$ speedup over [AKP25] for coefficient-encoded integer digit decomposition at ten radix-64 digits and speedups of 5.37$\times$ over [LLNK22] and 7.83$\times$ over [CKK20] for sign evaluation on real input pairs at $2^{-60}$ separation. In the tested settings, the method of [AKP25] is faster for $u \leq 4$ and that of [LLNK22] for $p \leq 36$, while our method is faster at the larger tested settings.
    ## 2026/2462
    * Title: Hybrid QuantumrCoComputational Key Distribution with Reduced Assumptions (Short Paper)
    * Authors: Jean Snyman, Ioana Boureanu, Daniel Gardham
    * [Permalink](https://eprint.iacr.org/2026/2462)
    * [Download](https://eprint.iacr.org/2026/2462.pdf)
    ### Abstract
    The HM-QCT protocol, presented by Mazzoncini et al. in 2025, uses a unique feature of quantum information to achieve quantum key distribution (QKD) with secret-key rates beyond standard constructions. The protocol has been designed in the hybrid quantumrCocomputational time-lock (QCT) security model which imposes two independent (but related) restrictions on the attacker: (1) a computationally secure encryption scheme which a successful attacker must break within a narrow timeframe and (2) an assumption that the attacker can only store quantum information with low fidelity.
    We first review the protocol and its two-assumption model by presenting, in explicit form, the two natural rCLharvest now, decrypt laterrCY strategies against it, one using quantum memory and one using classical memory. We show how each is excluded by exactly one of the two assumptions, so that harvesting resistance rests on their conjunction and on the presumed existence of a technological gap: the adversary's quantum memory must decohere much faster than the time it takes to break the short-term encryption.
    Finally, we introduce HM-PRF, a variant that replaces the short-term encryption with a pseudorandom function (PRF), evaluated locally. By eliminating the transmission of enciphered classical information, the adversary does not need to race an impending expiry event. We compare the security of our construction against the original and argue that our PRF-based assumption yields a more realistic adversary. It simply requires the existence of one-way functions rather than a predicted lasting limitation of quantum computation and memory technology.
    ## 2026/2465
    * Title: Snapshots of TEE-Based Encrypted Databases Leak Plaintext Histograms via Dendrochronology
    * Authors: Zachary Espiritu
    * [Permalink](https://eprint.iacr.org/2026/2465)
    * [Download](https://eprint.iacr.org/2026/2465.pdf)
    ### Abstract
    Arborists use dendrochronology, or the study of tree "growth rings" (as in, the plant), to infer past environmental events. We identify an analogous, exploitable phenomenon in the indexes used by several encrypted databases (EDBs) based on trusted execution environments (TEEs). Such EDBs have been shown to leak the order of indexed values, but not the histogram (or frequency of each value), with respect to a weaker class of snapshot adversaries. This order-only leakage substantially reduces the impact of possible inference attacks.
    We show, in fact, frequency is recoverable in the snapshot model from many TEE-based EDBs, even if the TEE itself is "secure". Our insight is simple: practical storage engines impose a strict total order on indexed keys by augmenting each key with a unique tie-breaker. If the adversary learns information about the tie-breakers, they can recover the frequencies of plaintext keys. We show this enables stronger inference attacks on several TEE-based EDBs (including Microsoft SQL ServerrCOs Always Encrypted, StealthDB, and HeDB) to demonstrate this vulnerabilityrCOs ubiquity and point to broader lessons for TEE applications designed around legacy code.
    ## 2026/2546
    * Title: New IND-CPA-D Attacks on BFV and BGV
    * Authors: Hyeongmin CHOE, Minsik Kang, Damien Stehl|-
    * [Permalink](https://eprint.iacr.org/2026/2546)
    * [Download](https://eprint.iacr.org/2026/2546.pdf)
    ### Abstract
    IND-CPA-D security is an extension of IND-CPA security introduced in the context of Fully Homomorphic Encryption (FHE). It captures the situation where the computation result is known to the adversary; it is in particular necessary for FHE with threshold decryption. This work presents three new attacks in this situation on the BFV and BGV FHE schemes, when their parameters are instantiated with heuristic assumptions commonly used to enable correctness.
    We first extend the \emph{bootstrapping failure attacks} from Cheon \emph{et al.} [CCS'24] on the DM/CGGI and CKKS schemes, to both BFV and BGV. We focus on BGV when instantiated with the so-called powerful-basis representation of ring elements. The second attack relies on \emph{skewing the ciphertext noise} in BFV, making it outpace the heuristic noise bounds for plaintext-ciphertext multiplications. This is achieved by crafting plaintexts, for which the noise bounds do not hold. The third and last attack focuses on outpacing the noise growth in BFV ciphertext-ciphertext multiplications. For this purpose, we \emph{skew the mask} part of the ciphertext by selecting a random encryption of zero, whose addition yields a ciphertext with a sufficiently large mask norm. While the first two attacks successfully recover the secret key, the last attack instead breaks the IND-CPA-D indistinguishability game.
    We report experiments on all these attacks, based on the HElib and OpenFHE libraries, respectively, for BGV and BFV. Notably, the second attack implemented in OpenFHE fully recovers the secret key in a few minutes to a few hours, depending on the parameters.
    ## 2026/2630
    * Title: Exact Error Bootstrapping and Comb Bootstrapping in FHEW/TFHE
    * Authors: Philippe Chartier, Mohammed Lemou
    * [Permalink](https://eprint.iacr.org/2026/2630)
    * [Download](https://eprint.iacr.org/2026/2630.pdf)
    ### Abstract
    In FHEW and TFHE, bootstrapping evaluates the decryption function via a blind rotation, whose resolution limits
    the message space. We propose instead to bootstrap the \emph{error}. By rounding the ciphertext at a resolution that
    is a multiple of the message modulus, we preserve the message exactly. Reduction modulo a small integer then yields
    a noise-free encryption of the error, which a single blind rotation lifts exactly before it is subtracted. The
    message modulus is thus constrained solely by the noise and can be much larger than in standard TFHE. Since the
    error takes far fewer distinct values than the ring degree, a single blind rotation can also refresh several ciphertexts
    simultaneously. We call this procedure the comb bootstrap. Between refreshes, an integer remains encrypted
    in a single ciphertext, allowing additions modulo the message modulus and multiplications without programmable
    bootstrapping. Built on TFHE-rs, for $8$-bit integers on a single thread, our refresh is $3.5$ times faster than
    that of TFHE-rs, and $9.1$ times faster with the comb bootstrap; multiplication is $6.5$ times faster. In a residue number system, multiplication of
    integers modulo $\widehat P\ge 2^{32}$ is $19$ times faster than in TFHE-rs. The error bootstrap serves exclusively
    to refresh ciphertexts; evaluating any other function still requires programmable bootstrapping.
    ## 2026/2639
    * Title: Private Information Retrieval with Accountability at Erasure-Optimal Server Redundancy
    * Authors: Myeongjun Kim, Hyunseok Jeong, Mincheol Son, Young-Sik Kim
    * [Permalink](https://eprint.iacr.org/2026/2639)
    * [Download](https://eprint.iacr.org/2026/2639.pdf)
    ### Abstract
    Private information retrieval (PIR) hides which database item a client requests. We study PIR that also identifies servers that respond incorrectly. Against a coalition of at most $t$ corrupted servers, the client must retrieve the item and identify every deviating server when at most $d$ deviate. Above that threshold, it must abort and return an empty identification set, with a specified statistical error.
    We present SynTrace, a single-round compiler for linear PIR supporting audit queries whose honest answers belong to a public code. The client combines the retrieval query with $m$ audit queries using secret linear mixing and independent blinding. Audit syndromes identify deviations before reconstruction. We prove perfect query
    privacy, zero false-identification probability within the deviation threshold, and statistical realization of an accountable PIR functionality.
    For Shamir-based PIR, SynTrace uses $k=t+d+1$ servers. Under the stated privacy and download assumptions, tolerating $d$ missing responses already requires this many servers, so identification adds no server overhead. With this number of servers, $m=d$ audit queries suffice with a suitable field, and are necessary within the specified syndrome-span decoder class. Additional audit queries can reduce communication by allowing a smaller field. For one 32 KiB record from a 1 GiB database, with five servers, privacy and robustness against two corrupted servers, and error at most $2^{-40}$, SynTrace uses 2.25 MiB of communication, compared with 8.96 MiB for the homomorphic-MAC construction of Eriguchi, Kurosawa and Nuida (TCC 2022) under the same workload and thresholds. Batched retrievals can share the audit queries.
    ## 2026/2645
    * Title: Isotaxis: Optimal Asynchronous Byzantine Consensus with Ordering Linearizability
    * Authors: Vincent Gramoli, Zhenliang Lu, Qiang Tang, Pouriya Zarbafian, Xinrui Zhang
    * [Permalink](https://eprint.iacr.org/2026/2645)
    * [Download](https://eprint.iacr.org/2026/2645.pdf)
    ### Abstract
    Despite ensuring both consistency and liveness, state machine replication (SMR) protocols remain vulnerable to adversaries that manipulate transaction order, causing, e.g., MEV attacks. To mitigate this, researchers have proposed new variants augmented with order-fairness. However, existing protocols that employ dependency graphs, such as Aequitas (Crypto 2020), Themis (CCS 2023), and SpeedyFair (NDSS 2024), often suffer from suboptimal performance, limited resilience, or weakened security guarantees. Pomp-o (OSDI 2020) introduced a novel ordering notion called ordering linearizability (OL) that may circumvent those drawbacks. However, its guarantee holds only under favorable network conditions, making the protocol vulnerable to order fairness violations during network delays and susceptible to performance degradation in the presence of Byzantine faults. Also, implementing SMR under OL remains an open challenge in asynchronous settings, as no known protocol achieves this without sacrificing liveness of SMR.
    In this paper, we present $\mathsf{Isotaxis}$, a state machine replication with ordering linearizability; moreover, our protocol has communication complexity $\mathcal{O}(n\ell+\lambda n^2)$, where $n$ is the number of processes, $\ell$ is the input (transaction) size, and $\lambda$ is the security parameter. This is optimal when $\ell\geq \lambda n$, while previous works have cubic communication. To the best of our knowledge, $\mathsf{Isotaxis}$ is the first protocol to achieve ordering linearizability in the asynchronous setting, especially one with optimal communication complexity and optimal Byzantine resilience. We implemented $\mathsf{Isotaxis}$ and conducted extensive experiments using up to 100 EC2 c6a.2xlarge instances. The experimental results show that our protocol robustly outperforms Pomp-o across all system scales, ranging from 4 to 100 nodes.
    ## 2026/2646
    * Title: Mikros: Bitwidth-Aware SNARKs over Extensions of Small Fields
    * Authors: Mingshu CONG
    * [Permalink](https://eprint.iacr.org/2026/2646)
    * [Download](https://eprint.iacr.org/2026/2646.pdf)
    ### Abstract
    Provers for succinct non-interactive arguments of knowledge (SNARKs) perform arithmetic over a large field for soundness, even when the witness entries are a few bits wide, which inflates both prover time and memory usage. Recent work makes individual SNARK components bitwidth-aware, so that a lower witness bitwidth means faster proving and lower memory usage, but these techniques cover only part of the prover and exploit the structure of specific fields, typically binary ones.
    We introduce Mikros, a framework for end-to-end bitwidth-aware SNARK construction based on algebraic vector packing. We pack vectors of length \(N=m\kappa\) over a base field \(\mathbb{F}\) into length-\(m\) vectors over a degree-\(\kappa\) extension field \(\mathbb{E}\), which turns length-\(N\) relations over \(\mathbb{F}\) into length-\(m\) relations over \(\mathbb{E}\) and makes existing linear-time extension-field protocols bitwidth-aware. This technique thus unifies bitwidth-aware inner-product proofs, Hadamard-product proofs, and polynomial commitment schemes, previously obtained by separate constructions, and yields the first bitwidth-aware grand-product proof, hence the first bitwidth-aware permutation argument. Composing them gives bitwidth-aware SNARKs for circuit satisfiability over extensions of arbitrary small fields.
    For a single instance of circuit satisfiability, the prover cost is proportional to the effective bitwidth, the combined bitwidth of the witness entries and the wiring-position encodings; across instances of the same circuit, the position encoding is amortized and the per-instance cost is proportional to the witness bitwidth.
    Although Mikros does not rely on binary-field structure, its prover is \(2.19\times\), \(2.55\times\), and \(1.85\times\) faster on batches of \(256\) SHA-256 compressions, Keccak permutations, and BLAKE3 compressions than Flock (B\"unz \etal, IACR ePrint 2026), the state-of-the-art bitwidth-aware SNARK over binary-extension fields.
    ## 2026/2647
    * Title: Revisiting ZMAC+: Birthday-Bound Attacks and a Beyond-Birthday-Bound Repair
    * Authors: Yan Jia, Peng Wang, Lei Hu, Shuping Mao, Tingting Guo, Jiadong Han
    * [Permalink](https://eprint.iacr.org/2026/2647)
    * [Download](https://eprint.iacr.org/2026/2647.pdf)
    ### Abstract
    ZMAC+ is a tweakable-block-cipher-based MAC proposed by List and Nandi
    in ToSC 2017 with claimed beyond-birthday-bound security. We show that
    a tag-swap mechanism previously observed for a hypothetical two-output extension of DoveMAC also applies to the published ZMAC+ construction.
    For two-block tags, we give a distinguisher with constant advantage and
    a fresh-message forgery with constant success probability using
    $O(2^{n/2})$ queries in the ideal-TBC model, where $n$ is the block length.
    An internal collision between two message families exchanges their tag
    blocks; a common extension preserves this relation and leads to a forgery
    with one additional authentication query. We identify a counting error
    in the published Lemma~4 and prove a corrected aggregate differential
    bound. The resulting PRF and MAC upper bounds match the birthday query threshold for bounded message lengths and two-block tags, under explicit field-order conditions. The distinguisher extends to every legal fixed
    output length $d\ge2$, and the forgery to every legal even $d$.
    We also retain ZHash and separate the output domains. Under stated
    field-order, length, and domain-capacity conditions, this modification
    admits an adaptive PRF bound of order $q^2/2^{n+\min(n,t)}$ for bounded lengths. Finally, a one-query counterexample shows that the ZAE security theorem must retain the per-message length restriction required by its counter-in-tweak encryption component.
    ## 2026/2648
    * Title: Notes on BulletProofs++ Range Proofs
    * Authors: Philipp Jovanovic, Arnab Roy
    * [Permalink](https://eprint.iacr.org/2026/2648)
    * [Download](https://eprint.iacr.org/2026/2648.pdf)
    ### Abstract
    We review the Bulletproofs++ construction which replaces the bit-decomposition inner-product argument of Bulletproofs with a reciprocal set-membership argument over base-$16$ digits. We present a self-contained specification of the $64$-bit range proof as well as a general batched variant parametric in the batch size $M$ and bit width $b$ and prove honest-verifier zero-knowledge and exact-form knowledge soundness. We describe the evaluation and optimizations of our Rust implementation over Ristretto255, which proves up to $7.8\times$ and verifies up to $4.5\times$ faster than regular Bulletproofs. Finally, we correct two formulas of the original paper: the affine $T^3$ term of the scalar polynomial $p_s(T)$ carries a factor of $2$, and the slot-$0$ component of the blinding vector $r_S$ carries the opposite sign.
    ## 2026/2649
    * Title: LINE-Break: Cryptanalysis and Reverse Engineering of Letter Sealing
    * Authors: Diego F. Aranha, Adam Blatchley Hansen, Thomas Kingo T. Mogensen
    * [Permalink](https://eprint.iacr.org/2026/2649)
    * [Download](https://eprint.iacr.org/2026/2649.pdf)
    ### Abstract
    We present a security analysis of the messaging service known as
    LINE, a popular platform used daily by millions of users in East
    and Southeast Asia rCo most notably Japan, Taiwan, Thailand, and
    Indonesia. More specifically, we focus on its underlying custom
    end-to-end encryption (E2EE) protocol, known as Letter Sealing v2.
    Our findings show that Letter Sealing allows a TLS Machine-in-the-
    Middle attacker or malicious server to violate integrity, authenticity,
    and confidentiality of communications. The stateless design of the
    protocol allows message replay, reordering, and blocking attacks
    without the user being notified. The lack of origin authentication
    facilitates impersonation attacks, in which the authorship of mes-
    sages in one-to-one or group chats can be forged by malicious users
    colluding with the adversary. Lastly, stickers and URL previews
    present a notable leakage of plaintext, which leads to a violation
    of confidentiality. To verify the correctness of our findings, we
    mounted a Machine-in-the-Middle attack on an iOS device, yielding
    the devicerCOs outgoing traffic and the corresponding server responses. Utilizing this setup, we experimentally verified our attacks against
    the authentic LINE application and an independent implementation.
    We discuss our findings in comparison to the state-of-the-art E2EE
    protocols, and conclude that Letter Sealing does not satisfy the
    requirements expected from a modern E2EE messaging protocol.
    ## 2026/2650
    * Title: On Robust Combiners for Pseudorandom Codes and PKE with Pseudorandom Ciphertexts
    * Authors: Nico D||ttling, Venkata Koppula, Mahesh Sreekumar Rajasree, Felix Rohrbach
    * [Permalink](https://eprint.iacr.org/2026/2650)
    * [Download](https://eprint.iacr.org/2026/2650.pdf)
    ### Abstract
    Robust combiners are a standard way to hedge cryptographic assumptions: given several candidate constructions, they produce one construction that remains secure as long as one candidate is secure. In favorable cases, such combiners also yield universal constructions. We ask whether this paradigm applies to cryptographic primitives whose public outputs must be both pseudorandom and sparse.
    Our first result gives a negative answer for pseudorandom codes (PRCs), i.e., error-correcting codes whose codewords are computationally indistinguishable from uniform strings. We prove that secret-key PRCs admit no black-box robust combiner. The impossibility holds even for the weakest meaningful guarantee, where the combined scheme is required to be secure when all but one candidate
    PRC are secure.
    We then show that the obstruction is not specific to error correction. In the sparse ciphertext regime, public-key encryption with pseudorandom ciphertexts also admits no black-box robust combiner. This stands in contrast to ordinary IND-CPA encryption, for which robust combiners are easy to obtain. Thus the requirement that public outputs look uniformly random introduces a genuine barrier to black-box assumption hedging, and rules out the standard combiner route to universal constructions for these primitives.
    ## 2026/2651
    * Title: HELLO, GOODBYE: Concurrent General Composition From Super-Rushing Security
    * Authors: Anirudh Chandramouli
    * [Permalink](https://eprint.iacr.org/2026/2651)
    * [Download](https://eprint.iacr.org/2026/2651.pdf)
    ### Abstract
    Kushilevitz, Lindell, and Rabin (STOC `06, SIAM Journal on Computing `10), in their seminal result, showed that any standalone-secure synchronous multiparty computation (MPC) protocol can be compiled into one secure under concurrent general composition, by adding a synchronisation step after every round; thereby, at least doubling the round complexity. We show that for protocols that are secure against super-rushing adversaries, introduced by Asharov, Chandramouli, Cohen, and Ishai (EuroCrypt `25), two synchronisation rounds suffice. Specifically, for an $R$-round protocol that is secure against super-rushing adversaries with a black-box, straight-line simulator, adding a round of start synchronisation (saying ``HELLO'') and a round of end synchronisation (saying ``GOODBYE'') yields security under concurrent general composition with selective abort in $R+2$ rounds. If the end synchronisation is over a broadcast channel, the security is upgraded to unanimous abort. Both compilers incur no loss in the security reduction and preserve the flavour of security (perfect, statistical, or computational) of the underlying synchronous protocol. Moreover, combining with the sufficient conditions of Asharov et al. for perfect security, and the round-preserving super-rushing compilers of Ciampi, Ravi, and Zou (Cryptology ePrint Archive 2026/1745) for statistical and computational security, yields compilers from rushing security to security under concurrent general composition, with an additive overhead of at most $2$ rounds.
    We further extend our compilers to protocols with a trusted setup, such as a common reference string or a public-key infrastructure, which is necessary in the dishonest majority setting. We require two conditions. First, every execution of the protocol uses its own stateless copy of the setup, whose responses to the adversary do not depend on the interactions of the honest parties. In particular, this rules out setups that are shared across executions, such as a global common reference string or a single public-key infrastructure used by every execution. Second, the underlying protocol is secure against super-rushing adversaries with adaptive inputs, that is, even when the inputs are chosen after interacting with the setup. Under these conditions, the same compilers yield security under concurrent general composition. We also show that adaptive inputs cannot be relaxed to the usual notion of security in the setup-hybrid model. Specifically, we give a protocol that is statistically secure against super-rushing adversaries with guaranteed output delivery under the standard hybrid model, but is insecure under concurrent general composition after adding start and end synchronisation, even with selective abort.
    ## 2026/2652
    * Title: Reverse Substitution in Secret Sharing: The Critical One-Half Threshold and a Route to Superpolynomial Lower Bounds
    * Authors: Shahram Khazaei
    * [Permalink](https://eprint.iacr.org/2026/2652)
    * [Download](https://eprint.iacr.org/2026/2652.pdf)
    ### Abstract
    The contribution vector (convec) of a secret-sharing scheme is the vector of its normalized share sizes. The average and maximum coordinates of a convec give, respectively, the average and maximum information ratios of the scheme. Obtaining superlinear lower bounds on these quantities for unrestricted perfect secret sharing has remained a challenging open problem for about four decades.
    In this paper, we study substitution, a natural way to build complicated access structures from simpler ones: one participant of an outer access structure is replaced by an inner access structure. Given secret-sharing schemes for the two factors, the standard forward construction composes them into a scheme for the composite access structure. We study the converse question. Given an arbitrary scheme for the composite access structure, we ask to what extent its convec admits a reverse factorization into convecs for the outer and inner factors, up to a common multiplicative loss.
    Exact reversal is false: we give a counterexample whose optimal reverse factor is \(8/9\), with a composite scheme that is scalar-linear over every finite field. On the positive side, we prove that a factor \(1/2\) is always attainable, and that every fixed instance admits a strictly larger factor.
    For a recursive family built from CsirmazrCOs classical access structure \(\mathcal C_k\), whose distinguished set has size \(k\), we identify a critical reverse factor that determines when the resulting lower bound becomes superlinear. This critical factor exceeds one half by only an amount of order \((\log k)/k\). Crossing it yields superlinear lower bounds, while any fixed positive excess above one half gives a route to superpolynomial lower bounds. Using only Shannon inequalities, the corresponding recursive factor cannot cross the critical value. Thus any improvement sufficient to pass this threshold must exploit constraints beyond the Shannon inequalities.
    ## 2026/2653
    * Title: Analyzing Compiler-induced Constant-time Violations with Compiler at Scale
    * Authors: Jing Liu, Luc|!a Mart|!nez Gavier, Zhiyuan Zhang, Marcel B||hme, Gilles Barthe
    * [Permalink](https://eprint.iacr.org/2026/2653)
    * [Download](https://eprint.iacr.org/2026/2653.pdf)
    ### Abstract
    The constant-time programming policy is a de facto standard for cryptographic libraries to prevent timing side-channel attacks. However, compiler optimizations may break constant-time source code during compilation. Systematically preventing this requires understanding where a violation arises, how it is introduced, and which compiler configurations are problematic. Existing approaches analyze a single compilation point, either the final binary or one intermediate representation, and thus only partially answer the three questions.
    We propose CTGREP, a compiler-based framework that answers all three questions by applying differential analysis across the entire compilation chain. We use CTGREP to analyze seven complete cryptographic libraries across three Clang versions, six target platforms, and thousands of compiler configurations. We systematically detect compiler-induced constant-time violations in the wild and collaborate with library developers to address 48 cases. We further identify seven new problematic LLVM passes, bypass and improve the state-of-the-art compiler-flag-based mitigation. Finally, we quantify how the compiler version, target platform, and optimization configuration affect the violations. By covering entire libraries across the full compilation chain, CTGREP effectively detects remaining compiler-induced constant-time violations and complements the community's ongoing hardening efforts.
    ## 2026/2654
    * Title: When Algebraic Structure Meets Too Many Hints
    * Authors: Dongshu Cai, Yijian Liu, Xianhui Lu
    * [Permalink](https://eprint.iacr.org/2026/2654)
    * [Download](https://eprint.iacr.org/2026/2654.pdf)
    ### Abstract
    The hint framework of Dachman-Soled, Ducas, Gong, and Rossi (CRYPTO 2020), together with the later too-many-hints analyses from May and Nowakowski (ASIACRYPT 2023) and Cao, Jiang, and Cheng (CRYPTO 2025), gives a classification of secret-dependent hints and LLL-breaking hint thresholds for LWE schemes. These values are now frequently adopted as the default benchmark for side-channel security evaluation. We show that applying them as a security metric is problematic.
    DDGR categorizes hints based only on their local algebraic form, while the threshold analyses assume uniformly sampled hint vectors. Neither captures how the specific algebraic form of a hint governs the geometry of the resulting sparsified lattice. A hintrCOs class label and the corresponding uniform threshold therefore cannot, on their own, capture its real cryptanalytic power.
    We illustrate this mismatch with two forms of structured leakage that naturally appear in ring and module lattice implementations, validated via synthetic experiments on Kyber-512. NTT-domain residues qualify formally as mod-$q$ hints, yet they recover the full Kyber-512 secret with roughly half as many hints as the uniform mod-$q$ bound predicts. Finite-precision FFT samples fall into the weaker approximate-hint class, and still only need $25\%$--$55\%$ of the hint budget required for uniform perfect hints.
    The gap stems from algebraic structure: these hint families carry additional ring structure that enables tailored lattice recovery strategies, a distinction invisible under the uniform-sampling model.
    We do not propose new attack optimizations. Our findings indicate that DDGR hint classes and too-many-hints thresholds are syntactic descriptions, not standalone security metrics for real leakage traces. Evaluating a side-channel leak requires considering the algebraic structure of the hint vectors, not just their category and quantity.
    ## 2026/2655
    * Title: OblivDGL: Oblivious Deep Graph Learning Made Practical
    * Authors: Yiming Qin, Xiaoning Liu, Shangqi Lai, Joseph K. Liu, Xingliang Yuan * [Permalink](https://eprint.iacr.org/2026/2655)
    * [Download](https://eprint.iacr.org/2026/2655.pdf)
    ### Abstract
    The rapid deployment of Graph Neural Networks (GNNs) within Machine Learning as a Service (MLaaS) has opened up new privacy concerns. Both sensitive graph data and proprietary GNN models are submitted to and processed in third-party MLaaS platform for training and inference. To alleviate those concerns, recent efforts have been made to design tailored secure computation protocols for GNNs. Unfortunately, existing designs cannot accomplish security, functionality, and scalability simultaneously. They leak a certain degree of graph information, offer limited support on secure training of GNNs, and can hardly scale to large graphs.
    In this paper, we design and implement OblivDGL, an oblivious deep graph learning framework for secure GNN inference and training. Our design is inspired by Deep Graph Library (DGL), an industrial practice for graph learning. At its core, we distill the secure computational patterns of GNNs into a generalized form, and empower both secure GNN training and inference through a novel oblivious message passing paradigm. To realize such a paradigm, we design a new oblivious graph representation, and realize it by function secret sharing (FSS), a lightweight secure computation technique with low latency. Compared to prior secure GNN systems, OblivDGL achieves the most stringent privacy guarantees, i.e., revealing no private information except for the total number of edges and nodes. One standout feature of OblivDGL is the scalability of processing encrypted graphs by carefully tailored parallelization designs. Extensive evaluations on four benchmark graph datasets demonstrate that, compared to state-of-the-art secure GNN frameworks, OblivDGL reduces communication cost by up to 1024x and achieves up to 14.3x speedup in runtime during secure training. For secure inference, OblivDGL achieves up to 754x lower communication and a 4.19x speedup.
    ## 2026/2656
    * Title: Falcon Key Recovery from Joint Sampler Leakages
    * Authors: Youngchang Kim, Yongseong Park, Jaeho Jeon, Young-Sik Kim
    * [Permalink](https://eprint.iacr.org/2026/2656)
    * [Download](https://eprint.iacr.org/2026/2656.pdf)
    ### Abstract
    Falcon and the forthcoming FN-DSA standard based on it generate signatures via discrete Gaussian sampling, during which power consumption leaks information about secret-dependent intermediate values. While prior attacks exploit sampler leakages individually or in pairs, we present a unified key-recovery framework that fuses three observations from each SamplerZ call: the signed-exponent class e(k) of the integer center, the random-sign bit b, and a multi-class proposal magnitude z0. These fused observations define magnitude-preserving intervals or rays for accepted sampler outputs. Leveraging an exact public linear relation that holds in the absence of modular wraparound, we map these candidate sets directly into slab and halfspace constraints on the secret key. The resulting system is solved via smooth softplus interval regression and bounded integer reconstruction with public-key validation, entirely bypassing computationally intensive lattice reductions such as LLL or BKZ. For PQClean Falcon-512 running at-O3 on an ARM Cortex-M4, our 17-class center classifier achieves 99.34% call-level accuracy on held-out test signatures from the profiling keys. The resulting attack recovers all 50 disjoint evaluation keys using at most 34 signatures (median 11), with a median post-classification key-recovery runtime of 17.54s per key. Furthermore, on c-fn-dsa, where center conversion relies on a single constant-time CLZ instruction, a reduced-resolution 7-class classifier combined with proposal leakage still recovers 38 of 50 keys within 200 signatures. These findings demonstrate that instruction-level normalization alone cannot prevent key recovery, underscoring that side-channel countermeasures for FN-DSA must protect all sampler leakage channels jointly.
    ## 2026/2657
    * Title: Poly2MsgLeaks: Certified Key Recovery from Polynomial-to-Message Leakage
    * Authors: Yongseong Park, YoungChang Kim, Jeongdo Kim, Young-Sik Kim
    * [Permalink](https://eprint.iacr.org/2026/2657)
    * [Download](https://eprint.iacr.org/2026/2657.pdf)
    ### Abstract
    We present Poly2MsgLeaks, a profiled chosen-ciphertext power-analysis attack that recovers the complete 512-coefficient public-key encryption (PKE) secret of SMAUG-T in its TiMER parameter set. Each polynomial-to-message (P2M) decision depends on four ternary secret coefficients and therefore on one of 81 local states. We characterize all admissible P2M predicates and show that our six-query schedule maps the 81 states to 57 binary transcripts; even with both exact polynomial weights, noiseless transcripts leave a mean residual ambiguity of 27.2 bits. Poly2MsgLeaks retains waveform scores for all 81 states, couples the 128 local blocks through the exact weights, and enumerates a calibrated cost region against the public-key relation. Under a uniform-matrix model, we prove that an incorrect key is released with probability at most $2^{-2095.6}$; for exchangeable calibration and evaluation keys, the probability that the true key lies outside the searched region is bounded without a channel model. Using six physical P2M traces recorded on an STM32F415, Poly2MsgLeaks recovers 999 of 1,000 previously unseen secrets, and a verifier-driven policy recovers all 1,000 secrets of a second cohort at a mean cost of 7.021 traces, without false acceptances. With the same decoder and limits, equalizing the scores within each transcript class reduces recovery from 998 to 112 keys. Against single-write message assembly and a two-share masked P2M, the evaluated six-execution attack recovers no complete secret.
    ## 2026/2658
    * Title: Unshuffling Fisher-Yates: Practical Recovery of Length-128 Permutations and Application to ML-DSA
    * Authors: Jonas Schupp, Anna Baumeister, Antonia Wachter-Zeh, Georg Sigl
    * [Permalink](https://eprint.iacr.org/2026/2658)
    * [Download](https://eprint.iacr.org/2026/2658.pdf)
    ### Abstract
    Shuffling is a standard hiding countermeasure against (single-trace) side-channel attacks on the number-theoretic transform (NTT) of lattice-based post-quantum schemes, such as ML-DSA. The Fisher-Yates algorithm can be used to generate the underlying random permutation. Recovering this permutation itself from a single trace has so far only been studied for short sequences. We present a practical attack on a software implementation of Fisher-Yates for sequences of length 128, the number of butterfly operations in one layer of ML-DSArCOs NTT. We identify the exploitable leakage of the algorithm, detect and remove the timing variations caused by rejection sampling and extract Hamming weight and identity leakage from a single trace per shuffle. We encode these hints as a constraint-programming problem with a soft objective function and enumerate the most likely permutations in order of descending likelihood. Applied to a shuffled ML-DSA-44 NTT, the recovered permutations are used to re-order the butterfly leakage, and recover the secret polynomial s1 either directly or up to a few coefficients that are enumerated directly. Protecting ML-DSArCOs NTT with Fisher-Yates-based shuffling does, therefore, not, by itself, prevent side-channel-assisted key recovery.
    ## 2026/2659
    * Title: Alg\{Ossa\}: Decentralized Secure Aggregation with Rotating Committees and Eventual Delivery
    * Authors: Xiangyu Su, Yuma Tamagawa, Mario Larangeira, Zengpeng Li, Keisuke Tanaka
    * [Permalink](https://eprint.iacr.org/2026/2659)
    * [Download](https://eprint.iacr.org/2026/2659.pdf)
    ### Abstract
    Secure aggregation lets clients reveal only an aggregate of their private contributions, supporting a variety of applications, including privacy-preserving sensing, collaborative analytics, and federated learning.
    Building on the single-server, committee-aided model for one-shot clients used by OPA and Willow~(CRYPTO~'25), we present Ossa, a generic construction with a modular security analysis.
    Ossa realizes the standard secure aggregation functionality with non-selective abort against a malicious server, but leaves role selection unspecified and provides no delivery guarantee.
    We therefore present AlgOssa, which integrates Ossa into an Algorand-style consensus backbone in which cryptographic sortition selects fresh potential leaders and verifier committees in each round and refreshes the decryptor committee from finalized chain state at key epochs.
    AlgOssa further selects the server from among the potential leaders, and we establish an explicit lower bound on the probability that the selected server is honest.
    Consequently, the probability that a round delivers a non-empty aggregate is bounded below by a positive constant, yielding an eventual delivery guarantee across repeated rounds.
    This variable delivery cadence fits delay-tolerant statistical sensing and, with persistent buffering and staleness control, buffered asynchronous federated learning.
    Our generic core supports classical and post-quantum instantiation routes; we evaluate complete local classical rounds and demonstrate the feasibility of the post-quantum route.
    ## 2026/2660
    * Title: Towards Quantum Sensing for Side-Channel Analysis
    * Authors: Oliver Butowski, Paul Haas, Jonas Hasenkrug, Niklas Mathes, Emanuele Strieder, Michael Kunzer, Jan Jeske, Nisha Jacob Kabakci, Marc St||ttinger
    * [Permalink](https://eprint.iacr.org/2026/2660)
    * [Download](https://eprint.iacr.org/2026/2660.pdf)
    ### Abstract
    Side-Channel Analysis is an established field of research to assess implementation vulnerabilities of cryptographic algorithms. One typically exploited side-channel is the electromagnetic (EM) near-field, which is proportional to the data-dependent currents flowing through an Integrated Circuit (IC). The field of Quantum Sensing (QS) based on Nitrogen-Vacancy (NV) centers has shown promising approaches for different measurement configurations like scanning or spatially resolved wide-field imaging. Already today, QS has been used in the analysis of (quasi-)static magnetic fields on ICs in spatially-resolved wide-field magnetometers. In this work, we study the applicability of QS for the analysis of dynamic EM fields of ICs. For the first time, we demonstrate spectral-temporal analysis of the EM-side-channel using an NV-center-based Radio-Frequency spectrometer. Our sensor has a real-time bandwidth of 1.1 GHz with adjustable center frequency and directly probes the frequency spectrum via NV center interactions in the time domain. The approach circumvents any computations like Fourier transforms or performing frequency sweeps, enabling GHz-realtime bandwidths. We use this spectrometer to analyze the EM emanations of an RSA decryption and perform leakage detection of a software implementation of the Number Theoretic Transform - a building block of all current lattice based post-quantum algorithms - running on a Cortex M4 commercial off-the-shelf microcontroller.
    ## 2026/2661
    * Title: Radical isogenies on every model
    * Authors: Thomas Decru
    * [Permalink](https://eprint.iacr.org/2026/2661)
    * [Download](https://eprint.iacr.org/2026/2661.pdf)
    ### Abstract
    Radical isogeny formulae compute a cyclic chain of $N$-isogenies with one $N$th root per step and without sampling torsion points, but for general $N$ they were only known in Tate normal form. We give radical steps of every odd degree $N$ directly on short Weierstrass, Montgomery, twisted Edwards, Huff, extended Jacobi quartic, twisted Hessian, Legendre and Jacobi intersection curves, on Kummer lines, and on all curves with a rational point of order~$2$. Our approach is model-independent. The Tate normal form data is obtained from the $x$-coordinate of the kernel generator by a shifted recursion, and the codomain is recovered in the original model by locating the image of a distinguished torsion point, without square roots. In Tate normal form we lower the cost of a step from $12.5N$ to $10N$ multiplications plus one exponentiation, and short Weierstrass curves come close at $10N+35$. Montgomery and twisted Edwards curves cost $10.5N+O(1)$. However, pushing a point through their steps costs only $2N$ multiplications without precomputation, against $2N+16$ plus a shared $2N-7$ in Tate normal form, which makes them the cheapest models for chains that transport torsion points, e.g.\ for all $N\ge19$ when two points are pushed. The other models cost between $11.5N+O(\log N)$ and $15.5N+O(\log N)$ per step. All algorithms are inversion-free, with exact operation counts.
    ## 2026/2662
    * Title: Tractable, Not Truncated: Colored-Noise TRNG Security via Fractional Brownian Motion
    * Authors: Maciej Sk||rski, Nathalie Bochard, Licinius Benea
    * [Permalink](https://eprint.iacr.org/2026/2662)
    * [Download](https://eprint.iacr.org/2026/2662.pdf)
    ### Abstract
    Oscillator-based true random number generators derive randomness from timing fluctuations driven by thermal and flicker noise, and flicker gains weight as technology advances and transistors shrink. Its long memory leaks information about past, which existing models either discard or truncate, overstating security.
    We introduce a rigorous and tractable framework for colored noise, including the white and flicker noise of oscillators. We model the oscillator phase by fractional Brownian motion and prove a quasi-renewal property: the phase uncertainty left after conditioning on the entire past depends only on the elapsed time. This yields closed-form worst-case min-entropy and sampling requirements. We also extend spectral and Allan-variance analysis to finite samples, so the noise parameters are estimated consistently from a single timing trace. The pipeline from measurement to sampling requirement is closed-form and needs no simulation.
    Experiments across FPGA and ASIC platforms show that flicker dominates: its variance meets white noise within about 100 cycles and accounts for more than 99% of uncertainty behind the targeted 0.99 min-entropy rate. Methods relying exclusively on thermal noise require adjustment or redesign: incorporating flicker noise enables a two-to-three orders of magnitude increase in bitrate.
    ## 2026/2663
    * Title: Quantum Multi-Collision Lower Bounds for Arbitrary Bounded Types
    * Authors: Tianci Peng, Shiqi Hou, Xiaoyang Dong
    * [Permalink](https://eprint.iacr.org/2026/2663)
    * [Download](https://eprint.iacr.org/2026/2663.pdf)
    ### Abstract
    We study quantum collision finding for functions of prescribed
    exact type.
    For fixed constants $k\ge r\ge2$ and $N=kn$, consider functions $f:[N]\to\mathbb Z_q$ of type $(k^n)$, with exactly $n$
    distinct output values and $k$ preimages for each value.
    We prove that the worst-case bounded-error quantum query
    complexity of finding $r$-collisions in $\ell$ distinct
    equality classes is
    \[
    \Theta_{k,r}\!\left(
    \ell^{\,2^{r-1}/(2^r-1)}
    N^{(2^{r-1}-1)/(2^r-1)}
    \right)
    \]
    for $1\le\ell\le N^{2^{-r}}$.
    The result is uniform over all feasible alphabet sizes $q\ge n$.
    Our proof uses the compressed permutation oracle (CPO).
    We establish a recurrence for intermediate collision counts
    and control its accumulated error to obtain database tails
    exponentially small in $\ell$.
    The improved CPO soundness estimate then converts these
    database bounds into function-query lower bounds.
    Moreover, we extend the analysis to arbitrary exact types with bounded
    class sizes, without requiring any particular class size to
    occur linearly often.
    The resulting lower bounds are tight when forward permutation
    access is additionally available, although they need not be
    tight for the original function-query problem.
    Finally, a sampling reduction relates our collision bounds
    to sparse $k$-distinctness instances.
    A separate analysis using Belovs's transfer framework recovers
    the same lower-bound exponent, establishing a concrete
    connection between the two approaches.
    ## 2026/2664
    * Title: Rerandomizable Garbling Beyond BHHO-KMHE and a Construction from LWE
    * Authors: Raphael Heitjohann, Jonas von der Heyden, Tibor Jager
    * [Permalink](https://eprint.iacr.org/2026/2664)
    * [Download](https://eprint.iacr.org/2026/2664.pdf)
    ### Abstract
    Rerandomizable garbling schemes (RGS) are a fundamental primitive enabling advanced cryptographic constructions such as multi-hop homomorphic encryption (Gentry, Halevi, Vaikuntanathan, CRYPTO 2010), iO-combiners (Ananth, Jain, Naor, Sahai, Yogev, CRYPTO 2016), and YOSO-style MPC (Acharya, Hazay, Kolesnikov, Prabhakaran, TCC 2022 and CRYPTO 2024). All known RGS instantiations rely on discrete-logarithm-type assumptions, concretely via the BHHO scheme (Boneh, Halevi, Hamburg, Ostrovsky, CRYPTO 2008) and its recent pairing-based variant (Heitjohann, von der Heyden, Jager, CRYPTO 2025). This reliance stems from the use of key-and-message homomorphic encryption (KMHE) that supports rerandomization and strong "key-privacy under leakage", which hides the applied homomorphic transformations and is currently only achievable using BHHO-style bitwise encryption in combination with permutation-based homomorphisms.
    Our first main contribution is a new garbling technique that shifts the burden of hiding homomorphic transformations from the encryption scheme to the garbling itself. This allows us to construct RGS from KMHE schemes with substantially weaker properties, avoiding the need for bitwise encryption and permutation-based homomorphisms, and enabling the construction of RGS from KMHE with other homomorphisms, such as additively-homomorphic ones.
    As a second contribution, we give a concrete lattice-based instantiation of the required KMHE primitive, based on LWE. This construction is a variant of the GSW FHE scheme (Gentry, Sahai, Waters, CRYPTO 2013), which uses new techniques for rerandomization and is tailored to the requirements of our new garbling scheme by supporting a "homomorphic"/"lossy" mode. This yields the first RGS construction that does not rely on discrete-logarithm assumptions and may provide post-quantum security.
    ## 2026/2665
    * Title: Shor's algorithm compiled on cat qubits: 22 593 qubits for RSA-2048 in 3.14 days
    * Authors: Axel Pappalardo, Dahmun Goudarzi, Victor Hertz, Hugo Jacinto, Larissa Kroell, Andr|- Schrottenloher, Peter Shanahan, |elie Gouzien, R|-mi de La Vieuville, Vivien Londe
    * [Permalink](https://eprint.iacr.org/2026/2665)
    * [Download](https://eprint.iacr.org/2026/2665.pdf)
    ### Abstract
    We present an end-to-end resource estimation of Shor's algorithm on superconducting cat qubits, from its mathematical description to the allocation and scheduling of physical qubits on a chip layout. After proposing a comprehensive view of the modern versions of Shor's algorithm for RSA, ECDLP and FFDLP, we make explicit their logical circuits and the trade-offs they enable. We compile the dominant subroutines down to physical-qubit operations on two architectures: one based on repetition cat codes and one based on LDPC cat codes. We design a parity-Cnot gate for cat qubits, extend a multi-target Cnot gate to the LDPC-cat architecture, and adapt an active injection procedure to cat-qubit architectures. Building on these primitives, we adapt to cat-qubit architectures the adder from GidneyrCOs 2025 resource estimate for factoring RSA-2048. We combine our adder compilation and a coarser resource estimate for the phaseup with the factory designs and lookup compilation from the FeMoco resource estimation of Kroell et al. Together, these compilations lead to chip layouts and schedules for factoring RSA-2048.

    Assuming a 1$\mu$s error-correction cycle time, a 10$\mu$s reaction time, circuit-level phase-flip noise with probability $p_Z = 5 \times 10^{-4}$ and no bit-flips, factoring RSA-2048, the configuration we compile in full, requires about 23 000 cat qubits and 3.14 days. Reusing the operations compiled for RSA-2048, solving ECDLP on secp256k1 requires at most 30 000 cat qubits and 1 hour, and FFDLP-512, which we propose as an intermediate benchmark, about 6\,700 cat qubits and 21~minutes. Trading space for time, RSA-2048 runs in 1.25 hours on about 611 000 cat qubits. The requirement on no bit-flips (which corresponds to a bit-flip time of about 100 years) can be relaxed to a bit-flip time of about one hour by using an additional concatenation layer into a distance-3 bit-flip error-correcting code. In that case, we estimate that the cost of RSA-2048 increases to about 45 000 cat qubits.
    ## 2026/2666
    * Title: Efficient SIMD SHAKE through Cost-Aware Permutation Scheduling
    * Authors: Hang Zhang, Ya Shi, Ying Liu, Xianhui Lu
    * [Permalink](https://eprint.iacr.org/2026/2666)
    * [Download](https://eprint.iacr.org/2026/2666.pdf)
    ### Abstract
    Lattice-based cryptography uses SHAKE to expand seeds into byte strings for matrix generation and sampling. SIMD Keccak implementations process multiple hash streams in parallel. Differences in stream lengths and input dependencies can prevent full SIMD utilization. We present a cost-aware method for scheduling Keccak permutations across hash streams during a single execution of a cryptographic algorithm. The method groups ready streams and divides long streams into segments for regrouping. A model of permutation calls, state movement, initialization, and input preparation guides the selection of stream groups, segment lengths, and state placements. We evaluate ML-KEM and HAETAE on an Apple M5, a Cortex-A72, and an Intel Core i5-11500, using Keccak kernels that process two, four, or eight streams per call. ML-KEM achieves speedups of up to $1.31\times$ for encapsulation and $1.44\times$ for decapsulation, while HAETAE achieves up to $1.28\times$ for signing and $1.26\times$ for verification.
    ## 2026/2667
    * Title: Faster complete formulas and their application to curves with efficient endomorphisms
    * Authors: Diego F. Aranha, Paulo L. Barreto
    * [Permalink](https://eprint.iacr.org/2026/2667)
    * [Download](https://eprint.iacr.org/2026/2667.pdf)
    ### Abstract
    We revisit scalar multiplication on prime curves $y^2 = x^3 + b$ with $p \equiv 1 \pmod 3$, the family including secp256k1, BN, and BLS curves. We apply a 15-year-old technique in a novel way to improve the best complete addition from $12$ to $11$ multiplications (or $10$ for mixed coordinates) for the first time in 10 years: its final stage is a 3D cross product, which needs only five multiplications.
    We implement the new formulas on the \texttt{libsecp256k1} library, with an improvement of $5.2$\% in constant-time fixed-base scalar multiplication.
    Furthermore, we propose a complete tripling formula with the same cost as incomplete tripling in Jacobian coordinates, and combine both formulas into an exception-free width-3 $\tau$-NAF with $\tau = 1 - \omega$ and a six-point precomputed table. In an operation-count model it is about 14\% faster than exception-free GLV-based scalar multiplication at 256 bits and 3--7\% faster than the fastest incomplete GLV.
    A constant-time implementation in RELIC confirms the model on the BLS families: in $\mathbb{G}_1$ of BLS12-381, BLS24-509 and BLS48-575 the $\tau$-NAF is 9--13\% faster than GLV with the same complete formulas, and the regular variant is 10--12\% faster than regular GLV with complete formulas and 5--9\% faster than regular GLV with incomplete Jacobian formulas.
    In $\mathbb{G}_2$ of the same curves, where GLS gives the baseline, the $\tau$-NAF stays 10--11\% faster than GLS with complete formulas and 7--9\% faster with Jacobian formulas, while the regular variant gains at most 6\%.
    We also develop an `imaginary' version of Toom-Cook that is useful for the $\mathbb{G}_T$ extension field arithmetic, yielding a 4--6\% improvement in $\mathbb{G}_T$ exponentiation for BLS24-509 and BLS48-575. A cyclotomic cube at 0.77 multiplications carries the $\tau$-adic method over to $\mathbb{G}_T$, where it makes exponentiation 3\% faster on BLS24-509 and 11\% faster on BLS48-575.
    ## 2026/2668
    * Title: An Algebraic Polynomial Evaluation Datastructure for Fields of Large Characteristic
    * Authors: Hiroki Okada, Rachel Player, Simon Pohmann
    * [Permalink](https://eprint.iacr.org/2026/2668)
    * [Download](https://eprint.iacr.org/2026/2668.pdf)
    ### Abstract
    In this work, we study (multivariate) polynomial evaluation datastructures, i.e. algorithms that can evaluate a multivariate polynomial at any input point, using random access to some precomputed encoding of the polynomial. Multiple constructions have been proposed in the literature, with the work by Bhargava, Ghosh, Guo, Kumar and Umans (2024) achieving optimal datastructure size and query complexity, up to polynomial factors. For $n \in d^{o(1)}$ this is equivalent to having datastructure size $d^{n + o(n)} (d n \log q)^{O(1)}$ and query complexity $(d n \log q)^{O(1)}$ for an $n$-variate polynomial of total degree $d$ over $\mathbb{F}_q$. However, the algorithm of Bhargava et al. is not algebraic, since it requires lifting prime field elements to $\mathbb{Z}$. An algebraic algorithm would be desirable, as an algebraic model of computation is natural for studying polynomial evaluation and is the standard model in algebraic complexity theory.
    One approach to finding algebraic polynomial evaluation datastructures is to use univariate polynomial interpolation to reconstruct the polynomial along algebraic curves. This approach was first made explicit by Bhargava, Ghosh, Kumar and Mohapatra (2023), who used it to build an essentially optimal algebraic polynomial evaluation datastructure for fields of small characteristic $p = \mathrm{char}(\mathbb{F}_q) \in d^{o(1)}$. Over these fields, their construction refutes a previous conjecture by Miltersen. For fields of larger characteristic, it remains an open problem to find an algebraic algorithm with optimal datastructure size and query complexity.
    In this work, we propose a new way to construct algebraic curves over prime fields that allow polynomial interpolation: by deriving curves from the base-$\beta$ representation of (lifts of) prime field elements, we are able to recursively reduce the evaluation problem to points in boxes of decreasing size. This leads to a datastructure whose performance scales much more favourably with $p$. Concretely, we improve the dependency of the query complexity on $p$ from $p^{O(1)}$ to $d^{2\log_2 \ln\ln p} \ln p$, and completely remove the dependency on $p$ from the datastructure size. Its query complexity is still slightly super-polynomial in $d \log p$. Nevertheless, a variant of our results is enough to disprove Miltersen's conjecture for all finite fields, including prime fields.
    We further show that for a certain class of datastructures, which captures natural generalizations of our approach, the query complexity is lower-bounded by $d^{(1 - o(1))\log_3\ln\ln p}$. Consequently, within this class, our construction is optimal up to a constant in the exponent.
    ## 2026/2669
    * Title: PIR through the Lens of Probabilistic Inference
    * Authors: Dana Dachman-Soled
    * [Permalink](https://eprint.iacr.org/2026/2669)
    * [Download](https://eprint.iacr.org/2026/2669.pdf)
    ### Abstract
    Private Information Retrieval (PIR) allows a client to retrieve an entry of a database while revealing no information about the requested index to the servers. Classic information-theoretic PIR protocols of Chor et al. (FOCS '95, JACM '98) and Ambainis (ICALP '97) achieve sublinear client computation and communication complexity with a constant number of servers, but require each server to perform computation linear in the database size. In this work, we ask for which classes of structured databases the server computation can be substantially reduced while preserving the communication complexity and privacy guarantees of these protocols.
    Our main contribution is a new connection between server computation in information-theoretic PIR and probabilistic inference. We show that the computation performed by every server in both the Chor et al. protocol and the recursive protocol of Ambainis can be viewed as computing a marginal probability of a product distribution. Consequently, efficient exact probabilistic inference algorithm immediately yields a faster server algorithm for PIR. We formalize this connection through the notion of inference complexity, which captures the complexity of evaluating these marginals.
    Using this framework, we obtain improved server computation for several broad classes of functions, including read-once arithmetic formulas, graphical models of bounded treewidth (and consequently arithmetic circuits of bounded treewidth), functions with low communication complexity, and functions with sparse Fourier representations. The resulting protocols preserve the communication complexity, client computation, and number of servers of the underlying PIR constructions while substantially reducing server computation for these structured function classes.
    Finally, we complement our algorithms with conditional lower bounds.
    Assuming the randomized Circuit Strong Exponential Time Hypothesis (rCSETH), we show that, for every constant \(\varepsilon>0\), there exists a constant \(c\) such that no uniform algorithm can compute the first (virtual) server's response in the Chor et al. or Ambainis protocol on all \(n\)-input Boolean circuits of size at most \(n^c\) in time \(O(N^{1-\varepsilon})\), where \(N=2^n\). Thus, under rCSETH, substantially sublinear server computation cannot be achieved uniformly for all polynomial-size Boolean circuits.
    ## 2026/2670
    * Title: Barriers to Identity-Based Encryption in Generic Group-Action Models
    * Authors: Sikhar Patranabis
    * [Permalink](https://eprint.iacr.org/2026/2670)
    * [Download](https://eprint.iacr.org/2026/2670.pdf)
    ### Abstract
    Identity-based encryption (IBE) is required to support a superpolynomial-size identity space using only polynomial-size public parameters. This compression requirement underlies known barriers to IBE in the generic (pairing-free) group model. Cryptographic group actions, motivated prominently by isogeny-based cryptography, support many advanced primitives beyond public-key encryption. However, no generic construction of IBE from the basic group-action interface is known. Existing generic-group barriers do not resolve this question as they do not translate to generic group-action models.
    We establish the first tight barriers to IBE in two variants of the generic group-action model. In the type-safe generic group-action model, we prove that an IBE scheme with negligible correctness error and $n$ non-origin action-set element-handles in its public parameters can support at most $n$ identities, even for a weak notion of fully selective security. We show that this bound holds irrespective of the number of action-set element-handles in identity secret keys. We further establish that this bound is tight by demonstrating a matching construction.
    We then extend this tight characterization to a natural class of IBE schemes in the random-representation generic group-action model (including against representation-sensitive adversaries) under conditions ensuring that identity keys retain no hidden action-set encodings and discarded private encodings leave no residual information. We give a natural syntactic condition for the latter property. For actions additionally equipped with an inversion-like twist, we obtain a more general upper bound (including the same tight bound for odd-order actions).
    Our results provide the first formal evidence that IBE is likely to require additional algebraic structure or non-black-box techniques beyond the generic group-action interface. More broadly, we provide a new framework for proving lower bounds in generic group-action models.
    ## 2026/2671
    * Title: Beyond the Event Horizon of Keccak, Extending the Observation from 2011 and applications
    * Authors: Danilo Gligoroski
    * [Permalink](https://eprint.iacr.org/2026/2671)
    * [Download](https://eprint.iacr.org/2026/2671.pdf)
    ### Abstract
    In 2011 we observed that a single path in the Keccak sponge from a state whose capacity has all zero bits back to such a state yields an explicit, infinite family of second preimages for every message of at least one full rate block. Finding such a path costs about 2^(c/2), which lies "beyond the event horizon" for SHA3-256 (c=512). In this paper we give three novel theorems around that observation. First, the capacity can have any value x: a two-block meet-in-the-middle loop from x back to x, found at heuristic cost about 2*2^(c/2), gives the same unlimited family of second preimages requiring no further search, with connectors to and from x at about the same cost again (Theorem 1). Theorem 2 extends this to k-block loops and to cycles of the capacity map. A single-state bridge, a state S with cap(f(S)) = cap(f^-1(S)), where cap denotes the capacity part of the state, also gives such a family but costs about 2^c. Theorem 3 gives cheap collisions and a bridge-amplified multicollision: one inner collision and one connector yield equal-length Joux-style 2^k-multicollisions for every k, instead of Joux's k collision searches; to our knowledge this is the first such construction for generic sponges with search cost independent of k. We give verified full-round examples on Keccak-f[200] and on Keccak-f[1600] with c=32. The second part of the paper offers novel protocols built on the asymmetry between minting and forging Keccak bridges. They include proof of work with hardness-adaptive capacity, dual-capacity commitments anchored by the real SHA3-256 digest, bridges as zero-knowledge-committed tokens, and a self-enforcing bounty market for reduced-round security. To our knowledge, these are the first unkeyed Keccak-based protocols that deliberately set the capacity so that the generic bridge cost is a feasible, tunable hardness parameter. We prove the three theorems, machine-check the stated algebraic results in Lean 4, and provide reproducible experiments and open-source proof-of-concept code. The applications are design proposals whose end-to-end security remains open.
    ## 2026/2672
    * Title: Nenya: Efficient zkSNARKs for Integer Rings Z/2kZ via Reverse Multiplication-Friendly Embeddings
    * Authors: Tianyu Zhang, Nikita Borisov, Yupeng Zhang
    * [Permalink](https://eprint.iacr.org/2026/2672)
    * [Download](https://eprint.iacr.org/2026/2672.pdf)
    ### Abstract
    Zero-knowledge succinct non-interactive arguments of knowledge (zkSNARKs) are powerful cryptographic tools for certifying the correctness of computations with short proofs, fast verification, and zero-knowledge privacy guarantees. However, most existing zkSNARK schemes support arithmetic only over finite fields defined by large primes or their extensions. This creates substantial overhead when proving computations written in high-level programming languages, which typically operate on fixed-width integer types such as 32-bit and 64-bit integers.
    In this paper, we introduce Nenya, the first practical SNARK scheme that supports native arithmetic over the integer ring $\mathbb{Z}/2^k\mathbb{Z}$. At the core of Nenya are new reductions from rank-1 constraint systems (R1CS) over $\mathbb{Z}/2^k\mathbb{Z}$ to constraints over Galois rings via reverse multiplication-friendly embeddings (RMFEs). We also design a polynomial commitment scheme based on suitable classes of error-correcting codes, which supports well-formedness checks and packing rotations on committed witnesses essentially for free, resulting in sublinear verifier time.
    Experimental results demonstrate that Nenya achieves strong concrete performance. For a rank-1 constraint system of size $2^{25}$ for data-parallel computations over 32-bit integers, Nenya achieves a prover time of only 4.8 seconds. This is four orders of magnitude faster than the state-of-the-art SNARK scheme over $\mathbb{Z}/2^k\mathbb{Z}$, and only 1.06$\times$ slower than a SNARK over a field with the same number of constraints.
    For general computation, the prover time of Nenya is 34.6 seconds. Moreover, for proving pixel-level image transformations that arise in media-provenance workflows, such as filtering that operates natively modulo $2^8$, Nenya proves the same computation 12$\times$ faster than a field-based SNARK.
    ## 2026/2673
    * Title: Beyond the Scope of This Paper: Practical Flash-Accelerator and Cache-Collision Timing Attacks on Microcontrollers
    * Authors: Colin O'Flynn
    * [Permalink](https://eprint.iacr.org/2026/2673)
    * [Download](https://eprint.iacr.org/2026/2673.pdf)
    ### Abstract
    Cache and cache-collision attacks against AES are well-known since 2005, but their application to small (Cortex-M sized) microcontrollers has been limited in prior work, and in many cases the devices are assumed to be immune when they do not have a cache. However, the flash architecture of almost all microcontrollers introduces the same timing collision required for the well-known attacks and as a greatly underestimated channel.
    Recovery of AES keys using as little as 750 traces will be demonstrated on six popular cryptographic libraries across eight architectures and over twenty devices. Practical recovery on high-level applications is demonstrated against SPI bootloaders, Ethernet applications, CTAP2 over USB, and 802.15.4. wireless protocols.
    In addition, a new open-source tool called FlashWhisperer is introduced to assist with evaluation of microcontrollers, cryptographic libraries, and applications. Countermeasures already exist in the form of bitsliced implementations, and this work also discusses other countermeasures that existing libraries offer.
    ## 2026/2674
    * Title: Sybil-Proofness of Generalized Adaptive Clinching and Implications for Blockchain Mechanism Design
    * Authors: Chengkai Zhang, Yuhao Li, Elaine Shi, Mengqian Zhang, Lirong Xia, Qishen Han
    * [Permalink](https://eprint.iacr.org/2026/2674)
    * [Download](https://eprint.iacr.org/2026/2674.pdf)
    ### Abstract
    The adaptive clinching auction of Dobzinski, Lavi, and Nisan (FOCS'08) is a cornerstone of mechanism design with budget-constrained bidders, and it has since inspired a broad range of extensions to substantially richer market settings. Adaptive clinching enjoys compelling guarantees: it is Pareto optimal, and truthful bidding is a dominant strategy whenever budgets cannot be overreported. In many real-world environments, however, identities are cheap to create, making resilience to Sybil attacks an additional requirement. Whether the guarantees of adaptive clinching survive when a bidder can split its budget across fake identities has remained open. We introduce a generalized framework for adaptive clinching and prove that it satisfies Sybil-robust incentive compatibility: a bidder cannot benefit from splitting into any finite number of identities with arbitrary value reports, provided their aggregate reported budget does not exceed the bidder's enforceable true budget. Sybil resilience thus joins the list of ideal properties of adaptive clinching.
    Our work is motivated by practical mechanism-design problems in blockchain-based decentralized finance, where two-asset automated market makers (AMMs) are among the most widely used applications. We design a new AMM adaptive clinching mechanism that extends classical adaptive clinching in two ways: it supports a two-sided market and protects against two-sided strategies, and it allows the supply function to depend on the auction state. Its one-sided special case is captured by our generalized adaptive clinching framework, and we further extend our proof techniques to show that the full two-sided mechanism simultaneously satisfies Sybil-robust incentive compatibility and a relaxed notion of Pareto optimality. In light of known impossibility results, together with a new impossibility proved in this paper, we argue that these guarantees are essentially the best possible. More broadly, our work reveals new connections between classical algorithmic game theory and modern decentralized blockchains.
    ## 2026/2675
    * Title: High Precision Noise Cleaning for CKKS with Application to Asynchronous Threshold CKKS
    * Authors: Zhihao Li, Cheng Hong, Tao Wei
    * [Permalink](https://eprint.iacr.org/2026/2675)
    * [Download](https://eprint.iacr.org/2026/2675.pdf)
    ### Abstract
    Noise cleaning in discrete CKKS uses Hermite interpolation to reduce the input error while preserving the encrypted discrete message. Cryptographic applications based on noise flooding require the error after cleaning to be sufficiently small for the added noise to provide statistical hiding without preventing exact recovery. This requirement is more stringent than decryption correctness alone, but the achievable noise reduction is limited by errors introduced during homomorphic evaluation. In particular, key switching and rescaling can dominate the output error even when a higher interpolation order substantially reduces the polynomial residual.
    We propose a high precision noise cleaning method for CKKS that preserves encrypted integer messages while attaining a prescribed bound on normalized output noise. We jointly select the cleaning polynomials and evaluation parameters according to a complete error bound that accounts for the input noise and the errors introduced during homomorphic evaluation. By composing Hermite polynomials of lower degree, we can achieve the same output noise bound with a smaller ciphertext modulus and lower evaluation cost than a single higher degree polynomial. In addition, to reduce the ciphertext tensor degree, we construct polynomial representations with noisy auxiliary powers that cancel selected auxiliary error terms. For integer messages, we extract the bits through multi-value functional bootstrapping, then clean and recombine them into a single ciphertext. Finally, we apply high precision noise cleaning to construct an asynchronous threshold CKKS scheme that achieves strong simulation security in the random oracle model.
    We implement binary and integer noise cleaning in OpenFHE. For binary messages and a normalized output noise target of $2^{-300}$, the selected composition reduces cleaning time from $9.63$ to $1.54$ seconds compared with a single Hermite evaluation under the same input error bound and security requirements. The composition also requires a smaller input ciphertext modulus and less evaluation key storage. We also evaluate the complete construction on 8 bit integers packed into all $32{,}768$ slots. The maximum measured normalized output noise is below $2^{-300}$ with either leveled digit extraction or functional bootstrapping.
    ## 2026/2676
    * Title: Optimality and Efficiency of Higher-Order Rank-Based Side-Channel Attacks against Inner Product Masking Schemes
    * Authors: Haitao Zhan, Wei Cheng, Yuejun Liu, Jingdian Ming, Sylvain Guilley, Yongbin Zhou
    * [Permalink](https://eprint.iacr.org/2026/2676)
    * [Download](https://eprint.iacr.org/2026/2676.pdf)
    ### Abstract
    Higher-Order Spearman Coefficient Analysis (HO-SPA) is of particular interest in non-profiling Side-Channel Attacks (SCA) due to its effectiveness against monotonic nonlinear leakage. However, the optimal form, effective order combinations, and performance of HO-SPA (or its variants) remain underexplored. This work systematically revisits HO-SPA in the presence of Boolean Masking (BM) and Inner Product Masking (IPM). Specifically, we propose a new variant of HO-SPA, called HO-ASPA (Higher-Order Adjusted Spearman Coefficient Analysis), and derive the optimal form of HO-ASPA for two-share BM and IPM across a wide range of order combinations under the Hamming weight (HW) leakage model. We first derive the optimal form of HO-ASPA by extending the Spearman Coefficient Analysis to higher-order moments, while preserving the centered-product combination of the share leakages. We then establish an upper bound on the maximal correlation induced by the rank transformation and characterize the relationship between the signal-to-noise ratio and the optimal correlation coefficient in the rank-domain, and extend these analyses to IPM. To enable a fair comparison, we also derive the optimal forms of Higher-Order Correlation Power Analysis (HO-CPA) and HO-ASPA for both BM and IPM under the Least-Significant-Bit (LSB) leakage model. Our analysis highlights a key distinction: unlike HO-CPA, where higher orders often outperform the lowest feasible order, HO-ASPA shows no significant performance gap between higher-order and lower-order attacks. Moreover, under the HW leakage model, our HO-ASPA not only aligns with existing results and succeeds in counteracting the security order amplification, but also significantly outperforms Kruskal-Wallis Analysis (KWA)-based attacks at various order combinations. We further validate the effectiveness of the proposed HO-ASPA through simulated and real-world experimental evaluations.
    ## 2026/2677
    * Title: Smoothness of Shortest Isogenies to Frobenius Conjugatess
    * Authors: Yi Ouyang, Wei Wei, Zheng Xu
    * [Permalink](https://eprint.iacr.org/2026/2677)
    * [Download](https://eprint.iacr.org/2026/2677.pdf)
    ### Abstract
    Let \(E\) be chosen uniformly from the geometric isomorphism classes of supersingular elliptic curves over \(\overline{\mathbb{F}}_p\) and \(\delta_E\) be the minimum degree of isogenies from \(E\) to its Frobenius conjugate \(E^{(p)}\). We establish bounds for the smoothness probability of $\delta_E$ and hence affirm Wesolowski's \(p^{1/3+o(1)}\) attack on the supersingular endomorphism ring problem is unconditional. We also establish a uniform asymptotic formula, with a main term expressed in terms of Dirichlet \(L\)-values, for the probability that a connection isogeny of degree $n$ exists between $E$ and $E^{(p)}$.
    ## 2026/2678
    * Title: From Quantum Mechanics to the Hidden Subgroup Problem: an Overview from Finite to Infinite Groups
    * Authors: Federico Di Concilio, Ram||n Flores, Delaram Kahrobaei, Marialaura Noce
    * [Permalink](https://eprint.iacr.org/2026/2678)
    * [Download](https://eprint.iacr.org/2026/2678.pdf)
    ### Abstract
    The Hidden Subgroup Problem (HSP for short) is an important problem in quantum computing and computational group theory, which has connections with several quantum algorithms, including Shor's algorithm for integer factorization and the discrete logarithm problem. The HSP can be stated as follows: given a function on a group that is constant and distinct on cosets of a hidden subgroup, determine the hidden subgroup efficiently. The problem captures the essence of exploiting group structures for computational advantage and provides insights into the power of quantum algorithms over classical approaches. While abelian instances of HSP are well-understood and efficiently solvable using the quantum Fourier transform, non-abelian cases remain challenging and are active areas of research.
    The goal of this survey is to put together all the basic background needed to understand well the Hidden Subgroup Problem in groups, reviewing recent results and discussing open problems.
    ## 2026/2679
    * Title: Cryptanalysis and Enhancement of VTBSAE: Provably Secure Verifier-Based PAKE Protocols for the Industrial Internet of Things
    * Authors: Jiahui Gao, Zhiqiang Zhao, Xuexian Hu
    * [Permalink](https://eprint.iacr.org/2026/2679)
    * [Download](https://eprint.iacr.org/2026/2679.pdf)
    ### Abstract
    VerifierrCabased passwordrCaauthenticated key exchange (PAKE) enables a client and a server to establish highrCaentropy session keys from lowrCaentropy passwords without requiring the server to store plaintext passwords. This asymmetric design reduces the risk that leakage of serverrCaside credentials directly leads to client impersonation, making verifierrCabased PAKE well suited to authentication and sessionrCakey establishment for Industrial Internet of Things (IIoT) devices. In this paper, we analyze the recently proposed VTBSAE, a verifierrCabased PAKE protocol, and reveal that it fails to provide the claimed resistance against serverrCacompromise clientrCaimpersonation attacks. To fix this vulnerability, we propose ErCaVTBSAEv1. While preserving the lightweight structure of VTBSAE, ErCaVTBSAEv1 binds the clientrCagenerated point \(E_{1}\) to fresh serverrCaside randomness. We also briefly discuss ErCaVTBSAEv2 as a challengerCabased variant. We provide a formal security proof for ErCaVTBSAEv1 in the randomrCaoracle model under the CDH assumption, covering AKE security, forward secrecy, and resistance to serverrCacompromise clientrCaimpersonation attacks after serverrCaside verifierrCafile leakage. We evaluate ErCaVTBSAEv1 under two practical deployment settings: a Raspberry Pi 4B server with an AutoDL client, and a Raspberry Pi 4B server with a Raspberry Pi 4B client. The experimental results show that ErCaVTBSAEv1 preserves the communication and storage overheads of VTBSAE and achieves runtime performance comparable to that of VTBSAE.
    ## 2026/2680
    * Title: (Balanced) Boolean Functions on 375 Variables with Nonlinearity Exceeding the Patterson-Wiedemann Direct-Sum Bound
    * Authors: Deng Tang, Subhamoy Maitra
    * [Permalink](https://eprint.iacr.org/2026/2680)
    * [Download](https://eprint.iacr.org/2026/2680.pdf)
    ### Abstract
    Patterson and Wiedemann [IEEE-IT 1983] constructed Boolean functions on 15 variables with nonlinearity 16276, which is strictly greater than the bent concatenation bound.
    Taking their direct sum with a bent function gives nonlinearity $2^{n-1}-27\cdot2^{(n-11)/2}$ for every odd $n\ge15$. Much later, Schmidt [JCT-A 2019] proved that the asymptotic maximum nonlinearity is $2^{n-1}-(1+o(1))2^{n/2-1}$ as $n\to\infty$. In this work, we construct Boolean functions $f$ on 375 variables such that the nonlinearity is greater than $2^{374}-442367\cdot2^{168}=2^{374}-2^{187}+81921\cdot2^{168}$, which exceeds the direct sum of a 15-variable Patterson-Wiedemann function and a bent function on 360 variables. To be specific, the direct sum of a 15-variable Patterson-Wiedemann function and a 360-variable bent function has nonlinearity $2^{374}-2^{187}+20\cdot2^{180}=2^{374} 2^{187}+81920\cdot2^{168}$. Thus our construction improves on this direct-sum value by more than $2^{168}$. Our construction idea is as follows. Let $H$ be the multiplicative subgroup of order $(2^{375}-1)/751$ in $\mathbb F_{2^{375}}^*$. The support of $f$ is the disjoint union of 375 prescribed cosets and a subset $B\subseteq H$. The evaluation of Gauss sums reduces the contribution of the prescribed cosets to a computation of 751 integers. The conditions on $B$ form a $0$-$1$ linear feasibility problem. Using a potential criterion for simultaneous linear constraints, we prove the existence of a single subset $B\subseteq H$ satisfying the constraints at all frequencies. Taking direct sums with bent functions extends the result to every odd $n\ge375$. The support construction does not require balancedness. As a natural follow-up, we also obtain balanced functions with the same strict lower bound by changing the minimum possible number of values, using sampling without replacement. The subsets $B$ and the sets of modified points are obtained by existence proofs.
    ## 2026/2681
    * Title: Improving Code Rate and Query Complexity for the Ligero-IOP System
    * Authors: Ignacio Cascudo, Carmit Hazay, Muthu Venkitasubramaniam
    * [Permalink](https://eprint.iacr.org/2026/2681)
    * [Download](https://eprint.iacr.org/2026/2681.pdf)
    ### Abstract
    This work presents two main contributions to the analysis and design of Ligero-style zero-knowledge proof systems. First, we analyze the original Ligero IOP in the list-decoding regime and show that mutual correlated agreement suffices to obtain improved soundness guarantees and lower query complexity, without modifying the protocol. Second, we propose a new variant of Ligero that incorporates out-of-domain sampling, leading to further soundness improvements and enabling Reed--Solomon code rates above $1/2$. The new protocol preserves the constant-round structure of the Ligero IOP and its compatibility with memory-efficient proving, while achieving perfect honest-verifier zero knowledge.
    ## 2026/2682
    * Title: A Quantitative Evaluation of Constant-Time Analysis Tools
    * Authors: Zhenzhi Lai, Zhiyuan Zhang, Tian Qiu, Van-Thuan Pham, Udaya Parampalli
    * [Permalink](https://eprint.iacr.org/2026/2682)
    * [Download](https://eprint.iacr.org/2026/2682.pdf)
    ### Abstract
    The constant-time programming policy protects cryptographic code from timing side-channels. However, writing constant-time code remains challenging even for experienced developers. Therefore, over 50 CT analysis tools have been published to help them identify constant-time violations. While several studies have examined those tools, they predominantly rely on qualitative observations and case studies, rather than quantitative assessments.
    Therefore, we present AutoBench-CT, a modular benchmark that manually verified per-violation ground truths across 64 cryptographic tasks and the first unified quantitative metrics to quantify the Operational Performance, Detection Quality, and Usability for seven such tools. With the results, we quantitatively show why CT-grind, the first tool published in 2010, is still the most popular tool in the wild. Based on the quantitative findings, we further provide new insights into recurring limitations across tools and propose a composite pipeline to maximize the security guarantees of constant-timeness in practice.
    ## 2026/2683
    * Title: Stop Calling Them Provers: The Case for Calling ProVerif and Tamarin Symbolic Protocol Analyzers
    * Authors: Nadim Kobeissi
    * [Permalink](https://eprint.iacr.org/2026/2683)
    * [Download](https://eprint.iacr.org/2026/2683.pdf)
    ### Abstract
    A claim that a cryptographic protocol has been proved secure depends on the theory, the analysis software, the protocol model, and the security property being checked. I examine each of these for ProVerif and Tamarin. An audit of their published soundness arguments finds false statements, missing proofs, and gaps between the procedures justified on paper and those the tools run. I also reproduce previously reported bugs that cause Tamarin to accept false claims about the submitted models. ProVerif supplies no certificate for its full analysis, while Tamarin replays its proof tree with its own solver, leaving the correctness of that code to be trusted.
    A correct symbolic result can still fall short of the security claim made for a protocol. Models can omit behavior in parsers and state machines; secrecy queries can allow information to leak; and equations for cryptographic primitives need justification before they support computational guarantees. Better models, stronger queries and computational soundness arguments can address these problems, but someone must establish that they apply to the protocol at hand.
    For these reasons and more, I argue that calling ProVerif and Tamarin "provers" is misleading: we should call them symbolic protocol analyzers and report their results with the models, assumptions and evidence that support them. They remain useful for finding attacks and establishing symbolic properties, including for unbounded sessions.
    ## 2026/2684
    * Title: SoK: Multiple Concurrent Proposer Blockchains
    * Authors: Benjamin Marsh, Alejandro Ranchal-Pedrosa, Max Resnick
    * [Permalink](https://eprint.iacr.org/2026/2684)
    * [Download](https://eprint.iacr.org/2026/2684.pdf)
    ### Abstract
    Multiple concurrent proposer (MCP) protocols let several parties contribute transactions to the same ledger update. They can distribute communication and reduce one proposer's control over inclusion and order, but these benefits depend on how the contributions are combined. We describe a common architecture from transaction receipt through proposal formation, agreement, data recovery, ordering, execution, and state finality. Within it, we identify four direct MCP families: fixed proposal vectors, selected proposal collections, persistent proposal streams, and causal proposal DAGs. We compare them with constrained assembly, where several parties restrict a block assembled by one party. Across 39 configurations, we distinguish agreement and progress from service for a particular transaction, and compare hiding, ordering, communication, throughput, and latency at explicitly named endpoints. The comparison shows why additional proposers alone do not guarantee inclusion, why hiding does not settle who can react last, and why parallel disseminations need not improve useful execution. It also identifies the recovery, payment, and organizational assumptions needed to turn independent proposal rights into reliable transaction service.
    ## 2026/2685
    * Title: Quasi-polynomial time algorithms for block basis reduction of linear codes
    * Authors: Kolesnikov N.S., Novoselov S.A.
    * [Permalink](https://eprint.iacr.org/2026/2685)
    * [Download](https://eprint.iacr.org/2026/2685.pdf)
    ### Abstract
    The block code basis reduction algorithm (BKZ) proposed by Ghentiyala and Stephens-Davidowitz requires an exponential number of calls to the minimum weight codeword (MWC) oracle according to the weak complexity bounds established in the original paper. In almost all cases these bounds are worse than plain enumeration of codewords, despite the fact that in practice the algorithm works much better. In this work we propose block code basis reduction algorithms with polynomial and quasi-polynomial complexity for fixed $\beta$. Our algorithms are relaxations and modifications of the original algorithm. First, we show that the truncated version of the BKZ algorithm requires heuristic quasi-polynomial time of calls to MWC-oracle with the same basis quality as in the full BKZ algorithm. Second, we add some weak restrictions on the code basis that enables the algorithm to run in polynomial number of calls to the oracle. Third, we introduce the DeepBKZ algorithm which is adapted from lattice reduction. Under some relaxations (analogs of PotBKZ from the lattices) it also runs in quasi-polynomial number of calls to the MWC-oracle. We provide an implementation of proposed algorithms which is capable to process block sizes $2-24$ and more. Based on this implementation, we provide concrete complexity estimates and an analysis of the approximation factors achieved for the low-weight codeword problem on random linear codes.
    --- Synchronet 3.22a-Linux NewsLink 1.2