From Newsgroup: sci.crypt

## In this issue
1. [2025/881] One-Way Homomorphic Encryption: A Composite Group ...
2. [2025/882] Leveled Homomorphic Encryption over Composite Groups
3. [2026/18] Multi-Instance Unrecoverability of iMHF-Based ...
4. [2026/20] HIC Is All You Need: Practical Post-Quantum ...
5. [2026/285] How (not) to Switch FHE Schemes: Framework and ...
6. [2026/335] Sumcheck-based zkSNARKs are Non-Malleable
7. [2026/1165] On the State-Compromise Security of End-to-End ...
8. [2026/1253] GumSwap: Griefing-Free Universal Multi-Party Atomic ...
9. [2026/1254] Top Gun: Degree Annihilation Attacks on Poseidon
10. [2026/1255] Bootstrapping is All You Need: Secure Transformer ...
11. [2026/1256] Problems in algebra inspired by tropical cryptography
12. [2026/1257] Stickel-type key exchange with hidden subspaces
13. [2026/1258] Beyond Anonymity Sets: A Security Model for ...
14. [2026/1259] Collaborative Rate Limiting Nullifier Signaling
15. [2026/1260] TruthTable: A Verifiable Query Engine
16. [2026/1261] RondoMPC: Asynchronous MPC with G.O.D. made More ...
17. [2026/1262] PQ-SMS: A Post-Quantum Sanitizable Multi-Signature ...
18. [2026/1263] LCPDTE: Low-Complexity Private Decision Tree ...
19. [2026/1264] The Power of Low Rank: Fast CKKS Functional ...
20. [2026/1265] A Billion Hard CRYSTALS: Exploring Practical ...
21. [2026/1266] Practical End-to-end Fault Attacks on PERK
22. [2026/1267] Efficient Private Set Intersection and Searchable ...
23. [2026/1268] Decentralized Multi-Authority (Attribute-Based) ...
24. [2026/1269] Gatling: Rapid-Fire Consensus from Parallel Composition
25. [2026/1270] Actively Secure MPC with $O(|C|)$ Computation and ...
26. [2026/1271] Boosting Efficiency and Security in ...
27. [2026/1272] Parameter-Aware and Instruction-Driven Dilithium ...
28. [2026/1273] Achieving Tight Space-Time Tradeoff and Practical ...
29. [2026/1274] Design and Performance Evaluation of Post-Quantum ...
30. [2026/1275] The Indifferentiability of the Duplex and its ...
31. [2026/1276] Forget-me-not Trees: Mass-scale Auditable Key ...
32. [2026/1277] On the Round Complexity of Dishonest-Majority MPC
33. [2026/1278] Barriers for Transparent Algebraic Generation of ...
34. [2026/1279] BootNet: Homomorphic CNN Inference with Convolution ...
35. [2026/1280] Public Parameters as a First-Class Cost: A Three- ...
36. [2026/1281] Resultants Meet Resultant: Improving CICO-1 and ...
37. [2026/1282] Physics-Aware Temporal Feature Engineering for ...
38. [2026/1283] Privacy-Preserving Outsourced Witness Updates for ...
39. [2026/1284] Zero-Knowledge Proofs of Generalized Regular ...
40. [2026/1285] Oblivious Priority Queue and Single-Source Shortest ...
## 2025/881
* Title: One-Way Homomorphic Encryption: A Composite Group Approach
* Authors: Mahdi Mahdavi, Helena Rif|a-Pous
* [Permalink](https://eprint.iacr.org/2025/881)
* [Download](https://eprint.iacr.org/2025/881.pdf)
### Abstract
Homomorphic Encryption (HE) is a fundamental Privacy-Enhancing Technology (PET) that enables computations on encrypted data without decryption. Despite its utility, designing an efficient and secure HE scheme is highly complex, requiring sophisticated cryptographic techniques. This paper introduces a novel approach to achieving homomorphic propertiesrCosupporting either one addition or one multiplicationrCowithin composite groups. While the proposed technique exhibits one-wayness, it has a good potential to serve as a foundational building block for constructing indistinguishable cryptosystems. This work contributes to the advancement of homomorphic encryption by providing a new perspective on secure computation within structured algebraic settings.
## 2025/882
* Title: Leveled Homomorphic Encryption over Composite Groups
* Authors: Mahdi Mahdavi, Ehsan Meamari, Emad Heydari Beni, Maryam Sheikhi
* [Permalink](https://eprint.iacr.org/2025/882)
* [Download](https://eprint.iacr.org/2025/882.pdf)
### Abstract
Homomorphic encryption is a powerful tool that enables computation on encrypted data without requiring decryption. While many Fully Homomorphic Encryption schemes, supporting arbitrary computations on encrypted data, have been developed using lattice-based and AGCD-based approaches, progress in composite groups has been limited to Partial Homomorphic Encryption schemes, which only support either addition or multiplication. This paper introduces the first $\ell$-leveled homomorphic encryption schemes over composite groups, based on factoring problem, that achieve both multiplicative and additive homomorphic properties. %Additionally, a modified version of RothblumrCOs transformation technique is developed to provide public key variants of the symmetric schemes.
Our novel design eliminates the need for relinearization operation, which is common in LWE-based HE schemes, and removes the requirement for the circular security assumption. For applications where the traffic must be indistinguishable as encrypted, a scrambled scheme is designed using a labeling technique. While the initial schemes offer an expanded message space, the introduction of the double-sized Message technique enables the encryption of messages up to twice the size without increasing the ciphertext size. Implementation results show that our schemes significantly outperform existing solutions, particularly in multiplication operations, achieving speeds up to 1000 times faster than well-known schemes such as BFV, BGV, CKKS, and TFHE.
## 2026/18
* Title: Multi-Instance Unrecoverability of iMHF-Based Password Hashing
* Authors: Charles Dodd, Pooya Farshim, Siamak F. Shahandashti, Karl Southern
* [Permalink](https://eprint.iacr.org/2026/018)
* [Download](https://eprint.iacr.org/2026/018.pdf)
### Abstract
The study of memory-hard functions (MHFs) so far has mainly focused on providing provable guarantees on the expected minimum cumulative memory complexity (CMC) required per evaluation when amortized over multiple instances. Such results, however, do not provide any guarantees for the security of compromised password banks in the sense of passwords remaining unrecoverable. Indeed, a construction can be memory-hard while still leaking information about its input. We provide the first formal treatment of the unrecoverability of graph-based data-independent MHFs (iMHFs) in the multi-instance setting. Multi-instance security is the accepted security model when inputs have low-entropy or are correlated, and require the adversarial effort to linearly scale with the number of instances broken.
To prove these results, we appropriately extend the ex-post-facto pebbling technique of Alwen and Serbinenko (STOC'15) and the unguessability reductions of Farshim and Tessaro (EUROCRYPT'21). We then use the resulting compatible frameworks to bound the number of guesses of adversaries with a given CMC in terms of the pebbling complexity of the graph underlying the iMHF. Combined with known lower bounds for the pebbling complexities of their graphs, we obtain, as corollaries, concrete unrecoverability bounds for the Argon2i, Catena, and Balloon hashing, showing in particular that the advantage indeed scales linearly with the number of instances and the cumulative memory complexity of the attacker.
## 2026/20
* Title: HIC Is All You Need: Practical Post-Quantum Password-Authenticated Public-Key Encryption
* Authors: Afonso Arriaga, David Mestel, Jan Oupick|+, Peter Browne R|+nne, Marjan +akrobot
* [Permalink](https://eprint.iacr.org/2026/020)
* [Download](https://eprint.iacr.org/2026/020.pdf)
### Abstract
Password-Authenticated Public Key Encryption (PAPKE) enables secure encryption using only a shared, human-memorable passwordrCoeliminating the need for trusted intermediaries or pre-established infrastructure. It allows a sender to encrypt a message for a recipient, using the recipient's password-authenticated public key and a shared password, while provably resisting man-in-the-middle and offline dictionary attacks. PAPKE's support for reusable password-authenticated public keys makes it especially suitable for asynchronous, PKI-free communication scenarios.
An important open problem is to construct PAPKE schemes that are secure against quantum adversaries, as existing instantiations rely on Diffie-Hellman assumptions. The PAPKE-IC construction (ACNS 2019) is generic and admits integration with post-quantum PKE schemes. However, the scheme assumes an Ideal Cipher (IC) over the public key domain, which is large for most post-quantum PKE schemes. While an IC is typically instantiated using a block cipher, standard block ciphers operate over much smaller domains (e.g., 128 or 256 bits). Alternatively, one can use an 8-round Feistel network, which achieves indifferentiability from an ideal cipher, or domain extenders. The latter are inefficient at the domain sizes required, making the efficient and secure instantiation of the IC in PAPKE-IC, in combination with post-quantum PKE, particularly challenging.
In this paper, we propose PAPKE-HIC, a UC-secure PAPKE scheme built from a PKE scheme and a Half-Ideal Cipher (HIC, introduced at EUROCRYPT 2023), which circumvents the challenges of instantiating ideal ciphers over large domains. We provide a detailed security proof of PAPKE-HIC and establish precise requirements for the underlying PKE: strong robustness, one-wayness, ciphertext anonymity, and pseudo-uniformity of public keys. Our analysis identifies a gap in the original PAPKE-IC security proof, motivating the introduction of a novel property, which we denote Decryption Robustness (DROB-CCA). Although DROB-CCA is implied by strong robustness (SROB-CCA), the reduction is not tight and incurs a quadratic security loss. We analyze which PKE schemes directly satisfy DROB-CCA, and conclude by presenting concrete instantiations of PAPKE-HIC. To our knowledge, this is the first practical, post-quantum instantiation of the PAPKE primitive.
## 2026/285
* Title: How (not) to Switch FHE Schemes: Framework and Attacks in the IND-CPA-D Model
* Authors: Giacomo Santato, Riccardo Zanotto
* [Permalink](https://eprint.iacr.org/2026/285)
* [Download](https://eprint.iacr.org/2026/285.pdf)
### Abstract
In this paper, we study the IND-CPA-D security of FHE schemes combined via scheme switching.
We introduce a formal framework for capturing security in this setting and identify sufficient conditions under which such combined schemes achieve IND-CPA-D security.
We then focus on the specific case of scheme switching from CKKS to exact FHE schemes.
We show that the PEGASUS construction [LHHMQ21] does not achieve IND-CPA-D security, and provide a proof-of-concept implementation of a key-recovery attack against the CKKS-to-FHEW switching mechanism in the OpenFHE library.
## 2026/335
* Title: Sumcheck-based zkSNARKs are Non-Malleable
* Authors: Antonio Faonio, Luigi Russo
* [Permalink](https://eprint.iacr.org/2026/335)
* [Download](https://eprint.iacr.org/2026/335.pdf)
### Abstract
Simulation extractability ensures that any adversary who produces a valid proof must possess a corresponding witness, even after seeing simulated proofs for potentially false statements. This property is vital for preventing malleability attacks and is therefore essential for securely deploying zero-knowledge succinct non-interactive arguments of knowledge (zkSNARKs) in distributed systems. While prior work, particularly the frameworks by Faonio et al. (CCSrCO24, TCCrCO23) and Kohlweiss et al. (TCCrCO23), has established simulation extractability for a wide class of pairing-based zkSNARKs using the KZG univariate polynomial commitment scheme (Kate et al., AsiacryptrCO10), we initiate a systematic study of simulation extractability for zkSNARKs based on the celebrated sumcheck protocol and the PST multivariate polynomial commitment scheme (Papamanthou et al., TCCrCO13). PST cannot be simulation extractable, due to its linear homomorphism, however, we show that it satisfies a refined notion of controlled malleability similar to the notion of Chase et al. (EUROCRYPTrCO12), which informally captures that linear homomorphism is essentially the only admissible malleability. We demonstrate that our notion of controlled malleability suffices to ensure security within the widely adopted design paradigm of compiling polynomial interactive oracle proofs into zkSNARKs, covering several state-of-the-art schemes such as HyperPlonk (EUROCRYPTrCO23), Spartan (CRYPTOrCO20) and Libra (CRYPTOrCO19).
## 2026/1165
* Title: On the State-Compromise Security of End-to-End Real-Time Group Communication
* Authors: Mang Zhao, Qian Wang
* [Permalink](https://eprint.iacr.org/2026/1165)
* [Download](https://eprint.iacr.org/2026/1165.pdf)
### Abstract
Real-time group communication protocols, such as Zoom and Microsoft Teams, aim to provide end-to-end security for audio and video conferences even in the presence of a malicious server. Despite their widespread deployment, particularly since the COVID-19 pandemic, their intended security guarantees lack comprehensive formalization. Prior work largely focuses on Zoom, and analyzes its security in models that rely on restrictive assumptions, such as the existence of a trusted server at certain points in time or a long-lived leader that never leaves the group. Moreover, existing analyses assume that group-specific session states of group members are secure and incorruptible, leaving the impact of potential full state compromise on group security unexplored.
In this work, we propose a set of essential security guarantees for real time group communication with state-compromise resilience against fully malicious servers and provide the first construction that provably satisfies all of these guarantees. To formally prove that our design achieves its goal, we formalize a novel continuous group key distribution protocol and introduce an associated security model that captures all the intended guarantees. We propose a generic construction that is provably secure in this model and suggest both classical and post-quantum secure instantiations.
Besides these main design goals, we introduce a novel multi-recipient authenticated key encapsulation mechanism, which serves as a building block for our generic construction. We define two core security notions for maKEM, propose both concrete and generic constructions, and prove their security in the random oracle model and the standard model, respectively.
## 2026/1253
* Title: GumSwap: Griefing-Free Universal Multi-Party Atomic Swaps
* Authors: Dongkun Hou, Yuanzhe Zhang, Shujie Cui, Tsz Hon Yuen, Joseph K. Liu, Jiangshan Yu
* [Permalink](https://eprint.iacr.org/2026/1253)
* [Download](https://eprint.iacr.org/2026/1253.pdf)
### Abstract
Universal multi-party swaps were proposed for secure cross-chain cryptocurrency exchanges across multiple blockchains that require only signature verification from the underlying blockchains. However, existing universal swap protocols remain vulnerable to griefing attacks, where a deviating party aborts the swap to lock a compliant partyrCOs assets for a long period, potentially causing indirect economic losses. A natural approach is to lift existing griefing-free solutions to the universal setting; however, we observe that this direct approach still faces three key challenges: (i) a timeout race attack, which arises from the absence of an upper bound on the transaction validity; (ii) a premium escape attack, which results from multiple refund transactions for the same assets being simultaneously valid; and (iii) a topological limitation, which implies that universal multi-party swaps can support only a special class of strongly connected digraphs, called reuniclus graphs.
In this paper, we propose GumSwap, a Griefing-free universal multi-party atomic Swap, which guarantees that a compliant party receives a premium if its asset is locked but not redeemed. To mitigate the timeout race attack and the premium escape attack, we impose minimum timeout intervals for the principal and premium timeouts, respectively, and introduce an asset migration mechanism that ensures that, during any time interval, at most one refund transaction is valid. Given the topological limitations of universal swap protocols, we further design a novel premium distribution mechanism that accommodates two classes of leaders in reuniclus graphs. Our experimental results demonstrate that GumSwap can be performed in less than 0.5 seconds per party, while reducing gas costs by 10.3X compared with existing contract-based solutions.
## 2026/1254
* Title: Top Gun: Degree Annihilation Attacks on Poseidon
* Authors: Antonio Sanso, Giuseppe Vitto
* [Permalink](https://eprint.iacr.org/2026/1254)
* [Download](https://eprint.iacr.org/2026/1254.pdf)
### Abstract
Poseidon is one of the most widely deployed arithmetization-oriented cryptographic permutations and plays a central role in modern zero-knowledge proof systems. Although several algebraic attacks on reduced-round variants have been proposed, the security of the recommended parameter sets remains intact. A central difficulty in such attacks is controlling the degree growth of the polynomial representations induced by the permutation.
In this work, we introduce degree annihilation, a new framework for algebraic cryptanalysis of Poseidon. Unlike round-skipping techniques, which reduce complexity by removing rounds from the algebraic model, degree annihilation reduces the contribution of existing rounds by imposing algebraic constraints that force dominant degree terms to vanish. This yields polynomial systems of substantially lower effective degree.
We first present a simple bivariate form of degree annihilation and show how it combines naturally with classical round-skipping techniques. The gain depends on the multiplicity with which the annihilated degree contribution propagates through the remaining nonlinear layers; when this multiplicity matches the contribution of one S-box layer, the effect is the same as skipping an additional nonlinear layer. We then generalize the technique to multivariate settings, where systems of control equations are used to annihilate successive partial-round degree contributions. These systems can be solved using elimination, resultants, and Gr||bner basis techniques.
As a proof of concept, we apply the framework to reduced-round Poseidon instances and obtain new CICO-2 attacks. More broadly, our results suggest that constructing algebraic varieties that actively control degree growth may provide a new direction for the cryptanalysis of arithmetization-oriented primitives.
## 2026/1255
* Title: Bootstrapping is All You Need: Secure Transformer Inference via Improved CKKS Functional Bootstrapping
* Authors: Pan Xiao, Rending Ouyang, Heng Zhang, Jiawen Zhang, Jian Liu
* [Permalink](https://eprint.iacr.org/2026/1255)
* [Download](https://eprint.iacr.org/2026/1255.pdf)
### Abstract
Fully homomorphic encryption (FHE) enables non-interactive secure transformer inference (NISTI).
Due to the high cost of bootstrapping, conventional approaches typically choose parameters that support a large multiplicative depth to reduce bootstrapping frequency. However, larger depth directly increases ciphertext size, resulting in higher communication and computation overheads.
In this paper, we introduce a novel functional bootstrapping (FBS) scheme that fundamentally reshapes the computation paradigm for NISTI: by fusing as many operations as possible into each bootstrapping operation, our approach significantly reduces the prescribed multiplicative depth.
Our FBS achieves a trigonometric minimax approximation for the target function, making it well suited for precision-sensitive components such as transformer nonlinear layers.
Furthermore, we incorporate linear layers into the slot-to-coefficient (S2C) transformation within FBS, thereby eliminating the need to evaluate them separately.
Building on these innovations, we present a complete NISTI framework that achieves a 1.9$\times$ speedup in runtime (from 662.3s to 349.5s) and a 3$\times$ reduction in communication (from 48.3MB to 16.1MB) compared with the state-of-the-art.
## 2026/1256
* Title: Problems in algebra inspired by tropical cryptography
* Authors: I. Buchinskiy, M. Kotov, A. Treier
* [Permalink](https://eprint.iacr.org/2026/1256)
* [Download](https://eprint.iacr.org/2026/1256.pdf)
### Abstract
In 2011, Grigoriev and Shpilrain proposed using tropical algebraic structures in cryptography. In recent years, numerous protocols based on tropical and related structures have been introduced, as well as many attacks on some of these protocols. This direction of research is now known as tropical cryptography. As a result of the efforts both to design secure schemes and to analyze their vulnerabilities, many purely algebraic and computational problems have emerged. In this paper, we give an overview of several results and open questions in this area. We discuss the complexity of solving certain classes of systems of equations over tropical and similar structures, as well as algorithms and approaches for solving such systems. We also present results on the asymptotic density of satisfiable systems of equations of special forms over tropical algebras. Furthermore, we discuss the discrete logarithm problem, the two-sided discrete logarithm problem, the knapsack problem, and the subset sum problem over tropical matrix structures. We consider a generalization of marginal sets for tropical semirings and semigroups. We also explore different classes of pairwise commuting matrices.
## 2026/1257
* Title: Stickel-type key exchange with hidden subspaces
* Authors: Fintan Costello, Paul Watts
* [Permalink](https://eprint.iacr.org/2026/1257)
* [Download](https://eprint.iacr.org/2026/1257.pdf)
### Abstract
We give a witness-finding cryptanalysis of Stickel-type key exchange schemes, which involve two-sided multiplication of $n \times n$ matrices over $\mathbb{F}_p$, where these matrices are drawn from public subspaces with a particular commuting structure. This analysis covers Stickel's original proposal, Shpilrain's polynomial extension of that scheme, Nager's algebraic extension of that scheme, and more generally all Stickel-type approaches using public subspaces over matrix algebra in finite fields: all such schemes can be broken in polynomial time. We also describe a new key establishment scheme using two-sided matrix multiplication in which the commuting subspaces used to form the key are hidden via conjugation by private terms, blocking this specific public-subspace analysis; the witness-finding problem in this new scheme has a direct reduction from a standard NP-hard problem (Edmonds' problem).
## 2026/1258
* Title: Beyond Anonymity Sets: A Security Model for Distributed Shuffling in Adversarial Environments
* Authors: Adrian Cinal, Oliwer Sobolewski, Gabriel Wechta, Filip Zagorski
* [Permalink](https://eprint.iacr.org/2026/1258)
* [Download](https://eprint.iacr.org/2026/1258.pdf)
### Abstract
Distributed shuffling is a core primitive underlying mix-nets, electronic voting, and, more recently, single secret leader election (SSLE) protocols for proof-of-stake blockchains. In these settings, a collection of resource-constrained parties jointly permutes a list of ciphertexts or commitments in order to conceal the correspondence between inputs and outputs. Existing security analyzes of such protocols typically rely on heuristic anonymity measures or implicitly assume honest behavior; therefore, they fail to capture statistical dependencies that arise when shuffling is partial and some participants are corrupted.
In this work, we introduce a new security model for distributed shuffling that explicitly accounts for adversarial corruption and information leakage. Our model allows an adversary to corrupt a subset of shufflers and to track selected elements throughout the execution, and defines anonymity in terms of statistical distance from the uniform distribution over permutations. This yields a quantitative, composable notion of security that subsumes commonly used anonymity-set arguments and aligns with standard cryptographic indistinguishability frameworks.
Using this model, we analyze Whisk, the shuffle-based SSLE mechanism proposed for Ethereum. We show that, under realistic protocol parameters and even in the absence of adaptive attacks, the induced distribution over permutations deviates significantly from the uniform distribution. Consequently, the resulting anonymity guaranties are substantially weaker than what is suggested by heuristic analyzes. We show how to modify the scheme parameters to meet the security requirements.
## 2026/1259
* Title: Collaborative Rate Limiting Nullifier Signaling
* Authors: Ya-fmur G|+rel, U-fur +Ren, O-fuz Yayla
* [Permalink](https://eprint.iacr.org/2026/1259)
* [Download](https://eprint.iacr.org/2026/1259.pdf)
### Abstract
Rate Limiting Nullifier (RLN) is a privacy-preserving and decentralized spam-prevention mechanism for anonymous broadcast networks: each member can emit at most $r$ signals per epoch, and any violation reveals a secret that enables the member's stake to be slashed. The standard construction binds each membership to a single secret key $\mathsf{sk}_G$, so the unit of identity, the unit of authorization, and the unit of slashing all coincide with one party. This rules out settings in which a group should speak with one voice, share one rate budget, and stand behind one collective bond without any single member being able to act unilaterally.
We introduce Collaborative RLN Signaling (coRLN), a protocol that lets $n$ parties register as a single RLN member and signal only by acting jointly. The group secret $\mathsf{sk}_G$ is held as additive shares under SPDZ and never reconstructed; the identity (or rate) commitment, the per-epoch RLN evaluation, and the broadcast proof are produced inside an MPC network using collaborative zk-SNARKs. The group occupies one leaf in the membership Merkle tree, locks one aggregated stake $\mathsf{stake}_G$, and is bound by one rate limit. We present the construction in both the rate-limit-1 and the general $r \geq 1$ settings, and we extend the protocol with a collaborative withdrawal procedure that lets the group exit without ever reconstructing $\mathsf{sk}_G$.
We prove three security properties of coRLN by reduction to the collaborative-SNARK composition and the standard primitives underneath: (i) no PPT adversary corrupting up to $n-1$ parties recovers $\mathsf{sk}_G$ as long as one party is honest; (ii) two signals in the same epoch with the same $\mathsf{messageId}$ yield an efficient extractor that recovers $\mathsf{sk}_G$ and triggers forfeiture of $\mathsf{stake}_G$; and (iii) no strict subset of $G$ can produce a verifying signal. The verifier interface and signal shape match classical RLN at the byte level, so coRLN deploys on existing RLN-aware infrastructure with only the verification key updated.
## 2026/1260
* Title: TruthTable: A Verifiable Query Engine
* Authors: Bharath Namboothiry, Alireza Shirzad, Spencer Solit, Ryan Marcus, Pratyush Mishra
* [Permalink](https://eprint.iacr.org/2026/1260)
* [Download](https://eprint.iacr.org/2026/1260.pdf)
### Abstract
We present TruthTable, a verifiable database engine that allows a prover to produce a succinct proof that convinces a verifier of the correct execution of the verifier's SQL query over the prover's committed database.
TruthTable supports a large subset of SQL, enabling it to prove 17 out of 22 queries in the standard TPC-H benchmark. To our knowledge, this is the widest support out of all prior work. Moreover, TruthTable's proofs are small, and fast to generate and verify: on the TPC-H benchmark with a database of a million rows, TruthTable's average proving time is $55$ seconds, average verification time is $32$ ms, and average proof size is $24$ kB. Compared to prior work, TruthTable's proving times are between $6.3\times$-$63\times$ better, while the verification times and proof sizes are competitive.
TruthTable achieves these properties via a codesign of cryptography and database techniques. On the cryptographic front, we propose a new polynomial representation of database tables, and design new subprotocols for proving the correct execution of various relational operators on these representations. On the database front, we propose a query planner that optimizes queries for minimal proving time, as opposed to minimal execution time. We also design new optimizations for this planner that reduce proving time by up to $2 \times$.
## 2026/1261
* Title: RondoMPC: Asynchronous MPC with G.O.D. made More Practical
* Authors: Xuanji Meng, Zhaoyang Xie, Zhaoxin Yang, Sisi Duan, Aggelos Kiayias * [Permalink](https://eprint.iacr.org/2026/1261)
* [Download](https://eprint.iacr.org/2026/1261.pdf)
### Abstract
Asynchronous multi-party computation (AMPC) en-
ables a set of mutually distrustful parties to securely compute
any joint function on their private inputs under arbitrary
network delays. The guaranteed output delivery (i.e., G.O.D.)
property is essential for availability, but can be very challenging
to achieve in practice. HoneyBadgerMPC (CCS 2019), the
first practical AMPC protocol, follows BeaverrCOs paradigm that
generates Beaver triples offline to simplify online computation.
One of the underlying building blocks, the random double
sharing protocol that generates random double shares, how-
ever, implicitly assumes a synchronous network. DumboMPC
(Usenix Sec 2025) overcomes the issue by adopting a two-phase
workflow where the underlying consensus protocol has to be
executed twice, and thus incurs high latency. Velox (CCS 2025)
achieves lower latency and weaker cryptographic assumptions
at the cost of sacrificing G.O.D. It remains an open question
whether there exists a more practical AMPC protocol with the
G.O.D. property.
In this paper, we present RondoMPC, a practical AMPC
protocol with G.O.D. with only one phase of consensus. To
achieve this goal, we build a practical asynchronous and
complete random double sharing (ACRDS) protocol. Our
ACRDS protocol supports batching, so a batch of random
double shares can be generated simultaneously. Furthermore,
ACRDS supports efficient verification of aggregated secret
shares, allowing the random double shares to be used for
Beaver triple generation using only one phase of consensus.
Our experimentation results show that RondoMPC is highly
practical, achieving both higher throughput and lower latency
for Beaver triple generation compared to existing protocols.
## 2026/1262
* Title: PQ-SMS: A Post-Quantum Sanitizable Multi-Signature Scheme for Satellite PKI
* Authors: Long Wang, Zhaoman Liu, Jing Fan, Yanhong Fan
* [Permalink](https://eprint.iacr.org/2026/1262)
* [Download](https://eprint.iacr.org/2026/1262.pdf)
### Abstract
Satellite communication systems, as critical long-lifecycle infrastructure, face a dual security challenge in the coming decades: the threat of quantum computers and the operational rigidity of traditional Public Key Infrastructure (PKI). While migrating to Post-Quantum Cryptography (PQC) addresses the former, it fails to solve the inefficiency of certificate management, where in-orbit policy updates require a prohibitively slow and complex multi-party re-issuance process.

To address these challenges, we introduce the concept of a Post-Quantum Sanitizable Multi-Signature ($\texttt{PQ-SMS}$), a novel primitive that enables controlled certificate adaptation across hierarchical trust while preserving the integrity of the root of trust. Building on this, we present $\texttt{Sat-APCS} $($\textbf{Sat}$ellite $\textbf{A}$daptable $\textbf{P}$ost-quantum $\textbf{C}$ertificate $\textbf{S}$cheme), which cryptographically decouple a certificate's immutable, multi-signed identity from its dynamic operational policies. This allows a delegated entity to perform lightweight, in-orbit policy updates while the foundational signature from the original consortium of authorities remains unchanged and valid.
We instantiate $\texttt{PQ-SMS}$ based on the NIST-standard CRYSTALS-Dilithium signature and a ISIS-based chameleon hash, and prove its security under standard lattice assumptions. Furthermore, Performance evaluation demonstrates that $\texttt{PQ-SMS}$ bypasses the interactive re-signing loop of traditional PKI, achieving an order-of-magnitude reduction in update bandwidth.
## 2026/1263
* Title: LCPDTE: Low-Complexity Private Decision Tree Evaluation over Homomorphic Encryption
* Authors: Dongjin Park, Gyeongwon Cha, Joon-Woo Lee
* [Permalink](https://eprint.iacr.org/2026/1263)
* [Download](https://eprint.iacr.org/2026/1263.pdf)
### Abstract
As machine-learning-as-a-service (MLaaS) becomes ubiquitous, protecting model queries via private inference is increasingly critical. Existing homomorphic encryption (HE)-based protocols for Private Decision Tree Evaluation (PDTE) have server complexity that scales at least as $O(2^D)$ in the tree depth $D$, so the cost of evaluating each tree grows exponentially with depth; in gradient boosted decision tree (GBDT) ensembles, where predictions aggregate the outputs of many trees, this per-tree cost is directly amplified.
In this paper, we present a non-interactive HE-based PDTE protocol built on the CKKS scheme with an end-to-end complexity of $O(p\sqrt{2^D})$, where $p$ is the input bit-length. To the best of our knowledge, this is the first HE-based PDTE scheme that asymptotically improves over the $O(2^D)$ dependence on $D$ while remaining non-interactive. We address two depth-driven sources of $O(2^D)$ dependence in existing protocols: we use the One-Branch-Only (OBO) paradigm from PROBONITE for comparisons, and we design the Baby-Step Giant-Step based Branch Selection algorithm for traversal. To further exploit the structure of GBDT ensembles, we deploy the batched bootstrapping technique by applying level-major tree evaluation.
Our experimental results show that, at depth $D=12$, our protocol reduces communication by $8.38\times$ and runtime by $7.74\times$ compared to FASTER, which is the fastest prior HE-based non-interactive PDTE baseline in our amortized setting, and the advantage increases as $D$ grows. These results suggest that our design provides a practical path toward depth-scalable HE-based PDTE for large boosted ensembles.
## 2026/1264
* Title: The Power of Low Rank: Fast CKKS Functional Bootstrapping for High-Precision Lookup Tables
* Authors: Zhihao Li, Xuan Shen, Cheng Hong, Ruida Wang, Xianhui Lu, Tao Wei
* [Permalink](https://eprint.iacr.org/2026/1264)
* [Download](https://eprint.iacr.org/2026/1264.pdf)
### Abstract
The CKKS fully homomorphic encryption scheme has traditionally been viewed as suitable only for approximate arithmetic. However, recent work (Alexandru et al., Crypto 2025) has introduced functional bootstrapping techniques that enable accurate lookup tables (LUTs) evaluation in CKKS. Nevertheless, to deal with the high precision problem, the state-of-the-art scheme (Dumezy et al., TCHES 2026) requires reshaping the LUTs into a matrix, which incurs $O(P)$ multiplications for a size-$P$ table and dominates runtime.
We first observe that LUT matrices for many practical functions are often highly structured, with exact or numerical rank much smaller than matrix dimension. We then develop a spectral framework for the LUT evaluation problem, which characterizes the relationship between function classes and the singular value decomposition. This framework yields exact rank bounds for structured function classes such as separable functions, and establishes exponential decay of singular values (implying low numerical rank) for smooth analytic functions. Building on this framework, we propose Low Rank Multiplexer Tree Functional Bootstrapping (LRMT-FBT), which evaluates the LUT via the singular values and singular vectors instead of direct matrix multiplication. This reduces the homomorphic multiplication cost from $O(P)$ to $O(r\sqrt{P})$, where $r$ denotes the rank of matrix, while also supporting extensions to multi-value and multi-input settings.
We implement LRMT-FBT in OpenFHE and evaluate it across different spectral classes. We also introduce implementation optimizations to improve the bootstrapping efficiency. At high precision, LRMT-FBT provides substantial performance improvements for common low rank functions compared with Dumezy et al. Typically, for $P = 2^{20}$, our method accelerates the LUT evaluation step by \(196.9\times\) for Step (\(r=1\)) and \(99.6\times\) for ReLU (\(r=3\)), yielding functional bootstrapping speedups of \(5.3\times\) and \(5.1\times\), respectively.
## 2026/1265
* Title: A Billion Hard CRYSTALS: Exploring Practical Aspects of Arithmetic Masking for PQC in Hardware
* Authors: Fabian Buschkowski, Niklas H||her, Pascal Sasdrich, Tim G|+neysu
* [Permalink](https://eprint.iacr.org/2026/1265)
* [Download](https://eprint.iacr.org/2026/1265.pdf)
### Abstract
Due to the complexity of modern cryptographic algorithms, especially in the area of Post-Quantum Cryptography (PQC), conceptualizing optimal hardware designs in relation to some target performance metric is increasingly time-consuming and error-prone, particularly when combined with the need for secure side-channel protection mechanisms. To solve this, Buschkowski et al. presented the HADES framework at CHES 2025 that efficiently automates the pre-synthesis Design Space Exploration (DSE) process and combines it with automated arbitrary-order masking capabilities. However, as their work focuses only on Boolean masking, PQC schemes that rely heavily on finite field arithmetic incur a significant overhead in latency and area, as demonstrated in their MLKEM (Kyber) case study.
In order to improve the performance of such primitives in hardware, we present a framework built upon HADES that supports both Boolean and arithmetic masking domains and can seamlessly and automatically convert between both types of secret sharing within the design hierarchy, while retaining the efficient DSE capabilities, extended by additional performance metrics. Even though the theoretical foundations of arithmetic masking are well-studied, some highly relevant implementation aspects, like the generation of non-power-of-2 masking randomness, are left largely unexplored. To help close this gap, we extensively analyze and systematically explore the cost associated with the secure and efficient generation of uniform randomness in hardware.
As an initial case study to highlight the capabilities of our modified HADES tool, we present a highly configurable and optionally fully-masked ML-KEM hardware design that improves upon state-of-the-art masked implementations by up to two orders of magnitude while also being competitive with unmasked designs from literature. To validate its practical security, we are the first to conduct practical leakage assessment measurements on the complete decapsulation algorithm, showing no signs of side-channel leakage after 500000 traces.
## 2026/1266
* Title: Practical End-to-end Fault Attacks on PERK
* Authors: Tanguy Stekke, Durba Chatterjee, Lejla Batina
* [Permalink](https://eprint.iacr.org/2026/1266)
* [Download](https://eprint.iacr.org/2026/1266.pdf)
### Abstract
This paper presents the first practical end-to-end fault injection attacks on the post-quantum signature scheme PERK, based on the MPC-in-the-Head paradigm and relies on GGM tree expansions for efficient randomness generation. While GGM trees reduce memory requirements, they introduce implementation-level deviations from the theoretical model. We show that these implementation choices fundamentally alter the fault surface and enable new attack vectors that are not captured by the original security assumptions. We propose two attacks targeting distinct stages of the GGM tree construction. The first attack fixes the root seed, resulting in deterministic tree generation and enabling full reconstruction of all leaf labels. The second attack induces reuse of GGM roots via an instruction skip, allowing recovery of hidden leaf values across consecutive rounds. Both attacks require only a single fault to recover the secret key.
We demonstrate both attacks end-to-end on the pqm4 reference implementation compiled with optimization levels -O3 as well as -Os for ARM Cortex-M4 microcontrollers. Our evaluation is performed on two hardware platforms (ChipWhisperer-Lite with STM32F303 and Nucleo-L4R5ZI-P) using clock glitching and electromagnetic fault injection (EMFI). We achieve success probabilities of 100% and 85% for the two attacks, respectively. Finally, we propose countermeasures for both attacks.
## 2026/1267
* Title: Efficient Private Set Intersection and Searchable Encryption using Homomorphic Bloom Filters
* Authors: Anil Kumar Pradhan, Killari Nandini, Harsh Kasyap, Sayantan Mukherjee
* [Permalink](https://eprint.iacr.org/2026/1267)
* [Download](https://eprint.iacr.org/2026/1267.pdf)
### Abstract
Existing encrypted search and private set intersection (PSI) protocols struggle to reconcile post-quantum security with practical efficiency, often leaking search and access patterns or requiring prohibitively deep fully homomorphic encryption (FHE) circuits. We address these limitations by introducing a new Homomorphic Bloom Filters (HBF) framework, a quantum-resilient framework that embeds length-$m$ Bloom filters directly into the plaintext space of an RLWE-based FHE scheme, enabling shallow homomorphic evaluation and matching without structural leakage.
Building on HBF, we construct a searchable encryption (SE) scheme and a private set intersection (PSI) protocol, both based on a depth-1 homomorphic missing-bit circuit. The SE scheme requires no rotations or bootstrapping at server side and incurs no additional computational cost as the number of query keywords increases.
The PSI protocol reduces each packed Bloom-filter comparison to a single ciphertext--plaintext multiplication, with cost depending on the Bloom-filter length rather than direct element-wise comparisons with the responder's set.
This framework confines leakage to benign dataset dimensions, tunable false-positive rates, and other public metadata, thereby eliminating explicit pattern leakage.
## 2026/1268
* Title: Decentralized Multi-Authority (Attribute-Based) Traitor Tracing
* Authors: Pratish Datta, Robert Sch|ndlich, Erkan Tairi
* [Permalink](https://eprint.iacr.org/2026/1268)
* [Download](https://eprint.iacr.org/2026/1268.pdf)
### Abstract
We initiate the study of multi-authority traitor tracing (MA-TT), a decentralized variant of traitor tracing in which tracing capabilities are distributed across multiple independent authorities rather than concentrated in a single trusted entity. Ciphertexts are associated with tracing policies over a collection of authorities, specifying which subsets of authorities are authorized to jointly accuse a user of contributing to a pirate decoder. This enables fine-grained control over tracing capabilities, prevents unilateral accusations, and reduces the surveillance risks inherent in centralized tracing systems. Our scheme naturally supports conjunction, disjunction, threshold, and more general monotone tracing policies.
We further introduce multi-authority attribute-based traitor tracing (MA-AB-TT), which combines distributed tracing in MA-TT with decentralized access control from multi-authority attribute-based encryption (MA-ABE). Ciphertexts are therefore equipped with two orthogonal policies: an attribute policy governing decryption and a tracing policy governing which tracing authorities may jointly identify traitors.
Our main contribution is a construction of MA-AB-TT for arbitrary monotone access structures from the standard matrix decisional Diffie-Hellman (MDDH) assumption in prime-order pairing groups. Our construction achieves adaptive security under static corruption of authorities in the random oracle model. All system parameters are independent of the number of authorities and users in the system, while ciphertexts grow linearly with the size of the associated policies. Our framework also yields a publicly traceable variant, in which tracing can be performed using only the authorities' public keys, albeit with weaker asymptotic efficiency guarantees.
Technically, we extend the blueprint for pairing-based traitor tracing based on private linear broadcast encryption (PLBE) [Boneh et al., Eurocrypt 2006] to the multi-authority setting. The key technical ingredient is a new multi-authority PLBE construction, which we instantiate from slotted inner-product function encryption (sIPFE) [Lin and Luo, Eurocrypt 2020]. As an intermediate step, we provide a new attribute-based sIPFE scheme supporting arithmetic branching programs, which may be of independent interest.
Our techniques also yield a new modular construction of adaptively secure MA-ABE under static corruptions from sIPFE, improving on a prior construction by Ambrona and Gay [PKC 2023]. Finally, when specialized to a single authority, our framework gives the first ciphertext-policy attribute-based traitor tracing scheme with asymptotically optimal parameters and exponentially large user spaces.
## 2026/1269
* Title: Gatling: Rapid-Fire Consensus from Parallel Composition
* Authors: Giulia Scaffino, Max Resnick, Joachim Neu
* [Permalink](https://eprint.iacr.org/2026/1269)
* [Download](https://eprint.iacr.org/2026/1269.pdf)
### Abstract
Consensus protocols form the core of blockchains and other replicated state machines, ensuring that all correct nodes process the same totally ordered log of input transactions. In fault-free executions, performance is driven by the good-case transaction latency -- the time between a transaction becoming known to all nodes and its confirmation by the consensus protocol -- which depends on both how frequently proposals are made and, once made, how quickly they are confirmed. While prior work has established tight lower bounds on confirmation latency that modern protocols already achieve, it remains open whether the inter-proposal time can be further reduced below the state-of-the-art of one network delay.
We introduce Gatling, an atomic broadcast protocol that achieves arbitrarily small inter-proposal times under rotating leader schedules; in particular, smaller than the network delay. Gatling runs multiple parallel instances of a black-box atomic broadcast protocol and staggers their proposal schedules to generate proposals in faster succession than state-of-the-art protocols. A deterministic interleaving rule merges the outputs of these instances into a single global log. We analyze the effects of head-of-line blocking caused by crashed leaders, and derive Gatling's optimal number of parallel instances. We further study the impact of Gatling on predictable validity and present two variants that retain this property. Finally, our experiments confirm that Gatling can be used with off-the-shelf component protocols to achieve low latency without fine-tuning the component protocol for minimum latency.
## 2026/1270
* Title: Actively Secure MPC with $O(|C|)$ Computation and Communication via CRT
* Authors: Alexander Bienstock, Daniel Escudero, Antigoni Polychroniadou
* [Permalink](https://eprint.iacr.org/2026/1270)
* [Download](https://eprint.iacr.org/2026/1270.pdf)
### Abstract
Secure multiparty computation (MPC) allows $n$ parties to compute a function of their private inputs, so that nothing beyond the output of the function is revealed.
In the sub-optimal honest majority setting in which the number of corrupted parties $t<(1/2-\varepsilon)n$, the works of Goyal et al. (CRYPTO'21 and CRYPTO'22), achieved $O(|C|)$ communication even against active adversaries, but with $\Omega(n\cdot|C|)$ computation, where $C$ is the arithmetic circuit computed by the MPC. Recent work by Garg et al. (CRYPTO'24) showed that both $O(|C|)$ communication and computation can be achieved in this regime, however, only against passive adversaries. In this work, we achieve the best-of-both-worlds by obtaining MPC with $O(|C|)$ communication and computation against active corruption of $t<(1/2-\varepsilon)n$ parties. To do this, we introduce novel techniques for actively-secure MPC constructed from Chinese Remainder Theorem based secret sharing.
## 2026/1271
* Title: Boosting Efficiency and Security in Arithmetization-Oriented Hashing for Zero-Knowledge Proof Systems
* Authors: Stefano Trevisani, Elena Andreeva, Rishiraj Bhattacharyya, Arnab Roy * [Permalink](https://eprint.iacr.org/2026/1271)
* [Download](https://eprint.iacr.org/2026/1271.pdf)
### Abstract
Cryptographic compression functions are a core component of vector commitment schemes, including Merkle tree commitments, which are widely used in modern ZK-SNARK and STARK frameworks. Arithmetization-Oriented (AO) compression functions minimize multiplicative complexity over the framework's native field F_p, making them significantly more efficient than bit-oriented designs in algebraic circuits. To date, AO compression functions have been almost exclusively constructed by applying the Sponge mode to an AO permutation.
In this work, we introduce two novel approaches for building permutation-based AO compression modes: the PA family, based on a Permutation with feedforward Addition, and PAX, as an eXtension of the PA family. We formally establish that, in contrast to the Sponge construction, our modes achieve optimal collision and preimage resistance. We also prove that PAX is indifferentiable from a random oracle, further strengthening its security and composability guarantees. We further show that variable-input-length hash functions can be safely instantiated from the PA(X) modes by applying appropriate domain extenders.
Beyond their strong security guarantees, our modes provide a framework that unifies and extends the description of several recently proposed modes that have been studied via cryptanalysis but do not come with provable security guarantees, including Jive and Trunc, as used in the AO designs Anemoi and Poseidon2.
Finally, through extensive experimental evaluation, we compare the concrete efficiency improvement that our modes offer compared to the Sponge approach over two popular AO permutation designs, Poseidon permutation and Rescue. For 128 bits of collision resistance, our modes can achieve up to a 2x speed-up over Sponge for equivalent compression rates in a software implementation. When considering R1CS arithmetization in the Groth16 framework, the PA(X) preimage-verification circuit can be 10% faster than Sponge. In the Plonky2 framework, PA(X) can achieve up to a 60% speed-up
## 2026/1272
* Title: Parameter-Aware and Instruction-Driven Dilithium Optimization on AVX2 and NEON
* Authors: Shi Ya, Liu Bingqian, Lu Xianhui, Qian Wenfei, Liu Ying, Wang Kunpeng
* [Permalink](https://eprint.iacr.org/2026/1272)
* [Download](https://eprint.iacr.org/2026/1272.pdf)
### Abstract
We improve the performance of the lattice-based cryptosystem Dilithium on AVX2 and NEON by deeply exploiting its algorithmic properties, such as small coefficient bounds and high sparsity, with the distinct instruction-level profiles of the underlying architectures. On AVX2, we deploy a single-modulus 16-bit NTT for $c \cdot \mathbf{s}_i$ and a multi-moduli 16-bit NTT coupled with a vectorized CRT reconstruction for $c \cdot \mathbf{t}_0$. These instruction-level optimizations accelerate the respective computations by $2.4$--$2.5\times$ and $1.2$--$1.3\times$ over official AVX2 baselines, ultimately reducing the overall Dilithium signature generation time by $7\%$ to $8\%$. Conversely, On ARMv8-A NEON, we retain the efficient 16-bit NTT for $c \cdot \mathbf{s}_i$, while proposing a Fast Sparse Polynomial Multiplication (Fast-SPM) method for $c \cdot \mathbf{t}_0$. By exploiting the extreme sparsity of the challenge polynomial, Fast-SPM entirely bypasses the NTT and converts the computation into highly efficient index-shifted additions. Across the tested NEON platforms (Cortex-A72 and Apple M1 Pro), this hybrid approach achieves a $1.9$--$2.1\times$ speedup for $c \cdot \mathbf{s}_i$ alongside a $1.1$--$1.9\times$ acceleration for $c \cdot \mathbf{t}_0$, which translates into a $10\%$ to $13\%$ reduction in the overall signature generation time.
## 2026/1273
* Title: Achieving Tight Space-Time Tradeoff and Practical Performance in Preprocessing PIR with Multi-level Recursion
* Authors: Chang Shi, Bo Peng, Zhechen Li, Cheng Hong, Mingxun Zhou
* [Permalink](https://eprint.iacr.org/2026/1273)
* [Download](https://eprint.iacr.org/2026/1273.pdf)
### Abstract
Client-specific preprocessing PIR supports sublinear online private queries after a linear-time offline phase that prepares client-specific hints. The relevant lower bound is tight: any scheme with $S$ bits of client storage and online cost $T$ must satisfy $S \cdot T = \Omega(n)$. Most practical random-set schemes fall short by a $\kappa$ factor in client storage, while the known constant-factor-optimal schemes, WR-PIR (Eurocrypt 2025) and Balanced PIR (S&P 2026), rely on complex hint-management machinery and incur high concrete costs.
We present Multi-level PIR, a preprocessing PIR scheme that matches this tight space-time tradeoff using only simple random-set components. The main idea is a multi-level composition: early levels are allowed to fail with noticeable probability, and later levels are invoked only when these query-independent failures occur. This 'waterfall' structure drives the overall failure probability down to negligible while keeping expected online cost and client storage at $O(\sqrt{n})$.
Our implementation shows that this simpler structure gives competitive concrete performance. Compared with Piano and S3PIR, two prior state-of-the-art practical schemes, \name achieves a $9$-$20\times$ client space reduction; compared with Balanced PIR, it reduces preprocessing time by about $8$-$45\times$ and online communication by about $5$-$67\times$ in our evaluated settings, while remaining competitive in other online metrics.
As an additional theoretical result, we give a more involved variant with $O(n^{1/4})$ online communication, the first constant-factor-optimal preprocessing PIR scheme with sub-$\sqrt{n}$ online communication.
## 2026/1274
* Title: Design and Performance Evaluation of Post-Quantum Authentication for Embedded Systems: A Case Study on PIV
* Authors: Emmanuelle Dottax, Rina Zeitoun
* [Permalink](https://eprint.iacr.org/2026/1274)
* [Download](https://eprint.iacr.org/2026/1274.pdf)
### Abstract
As the transition to post-quantum cryptography accelerates, security protocols must evolve to resist quantum threats while remaining practical, particularly on constrained devices where memory, bandwidth, and performance are limited. We consider the NIST Personal Identity Verification (PIV) system, where smart cards rely on digital signatures for authentication. Since post-quantum signatures introduce substantial computational and memory overhead, whereas post-quantum Key Encapsulation Mechanisms (KEMs) are generally lighter, we investigate KEM-based alternatives for authentication and assess the migration of secure messaging to post-quantum primitives. We propose post-quantum variants of the PIV authentication and secure messaging protocols and implement both signature-based and KEM-based approaches on a real smart card platform. We evaluate their computational and communication costs in a realistic embedded setting and present detailed performance metrics that enable assessing the impact of post-quantum migration across different hardware and communication configurations. Our results show that KEM-based authentication significantly reduces execution time and transmitted data compared to post-quantum signature-based designs, while KEM-based post-quantum secure messaging incurs moderate overhead compared to its classical counterpart. These findings highlight KEM-based authentication as a practical migration strategy for post-quantum secure embedded systems.
## 2026/1275
* Title: The Indifferentiability of the Duplex and its Practical Applications
* Authors: Jean Paul Degabriele, Marc Fischlin, J|-r||me Govinden
* [Permalink](https://eprint.iacr.org/2026/1275)
* [Download](https://eprint.iacr.org/2026/1275.pdf)
### Abstract
The Duplex construction, introduced by Bertoni et al. (SAC 2011), is the Swiss Army knife of permutation-based cryptography. It can be used to realise a variety of cryptographic objectsrCoranging from hash functions and MACs, to authenticated encryption and symmetric ratchets. Testament to this is the STROBE protocol framework which is a software cryptographic library based solely on the Duplex combined with a rich set of function calls. While prior works have typically focused their attention on specific uses of the Duplex, our focus here is its indifferentiability. More specifically, we consider the indifferentiability of the Duplex construction from an online random oraclerCoan idealisation which shares its same interface. As one of our main results we establish the indifferentiability of the Duplex from an online random oracle. However indifferentiability only holds for the standard Duplex construction and we show that the full-state variant of the Duplex cannot meet this notion. Our indifferentiability theorem provides the theoretical justification for the security of the Duplex in a variety of scenarios, amongst others, its use as a general-purpose cryptographic primitive in the STROBE framework. Next we move our attention to AEAD schemes based on the Duplex, namely SpongeWrap, which is the basis for NIST's Lightweight Cryptography standard Ascon. We harness the power of indifferentiability by establishing that SpongeWrap offers security against key-dependent message inputs, related-key attacks, and is also committing.
## 2026/1276
* Title: Forget-me-not Trees: Mass-scale Auditable Key Transparency from Hash Functions
* Authors: Gabriel Kaptchuk
* [Permalink](https://eprint.iacr.org/2026/1276)
* [Download](https://eprint.iacr.org/2026/1276.pdf)
### Abstract
Modern, deployed key transparency systems rely on auditors to ensure that updates to the set of keys are well-structured, allowing clients to efficiently monitor their own keys. In practice, the server's consistency proofs are very large, requiring computationally powerful auditors; as a result, real-world deployments have very few auditors.
We propose a new key transparency system based on a new data structure called Forget-me-not trees, which is a careful composition of Merkle trees and Bloom filters. The resulting system reduces the size of audit proofs by $\approx500\times$, from 15MB-30MB down to only 30KB-60KB. Our construction is the first mass-scale auditable key transparency system that relies only on hash functions.
## 2026/1277
* Title: On the Round Complexity of Dishonest-Majority MPC
* Authors: Ran Cohen, Daniel Collins, Pouyan Forghani, Juan Garay, Vassilis Zikas
* [Permalink](https://eprint.iacr.org/2026/1277)
* [Download](https://eprint.iacr.org/2026/1277.pdf)
### Abstract
What is the round complexity of MPC over point-to-point channels that is secure with unanimous/identifiable abort in the dishonest-majority setting?
Even after four decades of research, the answer to this question remains unclear. Although two-round MPC protocols exist in the broadcast-channel model, and, further, broadcast protocols with expected-constant rounds exist facing any constant fraction of corruptions, a na|>ve combination of the two yields MPC with expected $O(\log{n})$ rounds, where $n$ is the number of parties. The reason for this gap is the need to preserve the expected round complexity under parallel composition, yet existing techniques for the composition of broadcast protocols inherently rely on an honest majority of parties.
Further, when considering MPC with abort, one can also consider \emph{broadcast with abort}. However, existing lower bounds on the round complexity of broadcast do not translate to this relaxed notion of broadcast, with the end result that the existing lower bounds for MPC and broadcast do not apply to the question above.
In this work, we initiate the systematic study of this question and present the following positive and negative results for MPC over point-to-point channels:
- First, we prove the impossibility of (strict) constant-round MPC with unanimous abort. In fact, we show that any broadcast protocol with unanimous abort that is secure against super-constant corruptions requires super-constant rounds.
- Second, we present a round-preserving and black-box parallel composition construction of broadcast with unanimous abort, which leads to our main result: Assuming oblivious transfer (OT) and verifiable random functions (VRFs), MPC with unanimous abort and expected constant rounds is possible in the PKI model for signatures and VRFs, in the presence of any constant fraction of corruptions.
- Finally, we show that in the presence of slightly more corruptions---i.e., $n-o(n)$ corruptions---there is no expected-constant-round broadcast (and thus MPC) with identifiable abort.
## 2026/1278
* Title: Barriers for Transparent Algebraic Generation of Hard Supersingular Curves
* Authors: Anis Bkakria
* [Permalink](https://eprint.iacr.org/2026/1278)
* [Download](https://eprint.iacr.org/2026/1278.pdf)
### Abstract
We study transparent public generation of hard supersingular curves: a public, seeded, rerunnable algorithm outputs a supersingular curve while exposing the seed, verification transcript, and all algebraic information reconstructible from the implementation. This setting is distinct from trusted or distributed ceremonies, where a witness may be hidden, erased, or zero-knowledge protected. We define a transcript-security model for this setting and develop barriers for several modeled algebraic generation routes. For modular-conjugacy samplers, we analyze loci of supersingular invariants admitting an isogeny to their Frobenius conjugate; small public parameters give efficiently recognizable sparse support, while extractable high-parameter witnesses yield non-scalar endomorphisms by Frobenius composition. We extend this leakage principle to bounded correspondence witnesses, including kernel, rational-map, Hecke--Brandt, and elliptic-return detour traces. For direct samplers, we separate predicate-only search, local-neighbor exploration, bounded-relation witnesses, low-formal-degree ambient algebraic maps, and degree-one indexed maps from \(\F_p\) to \(\F_{p^2}\). The resulting theorems are deliberately model-bounded: they do not rule out hidden-witness ceremonies, higher-degree indexed maps, compact high-degree root indexing, endpoint-only mechanisms, or nonlocal aggregate sampling. Full proofs are deferred to the appendices.
## 2026/1279
* Title: BootNet: Homomorphic CNN Inference with Convolution and ReLU Fused in Bootstrapping
* Authors: Zhaomin Yang, Chao Niu, Cheng Hong, Tao Wei
* [Permalink](https://eprint.iacr.org/2026/1279)
* [Download](https://eprint.iacr.org/2026/1279.pdf)
### Abstract
Fully homomorphic encryption (FHE) enables privacy-preserving neural network inference but suffers from high overhead from homomorphic convolutions, polynomial activation approximations, and CKKS bootstrapping. This paper presents BootNet, a unified framework that fuses all three operations into a single bootstrapping invocation per CNN layer, achieving convolution, ReLU, and noise refresh simultaneously.
Prior works are able to fuse convolution into bootstrapping using CinS encoding (NeuJeans, CCS 2024) or ReLU into functional bootstrapping (RBOOT, USENIX Security 2026), but combining both for end-to-end ImageNet inference introduces numerous undocumented challenges. BootNet resolves these through a suite of corCadesign techniques and optimizations, including four representative solutions: (1) a splitrCaandrCamerge bootstrapping schedule that halves bootstrapping calls for ResNet shortcuts; (2) an improved RBOOT configuration paired with a model quantization method that complete the activation function with fewer multiplication depth; (3) a fusion of NeuJeans' masking layer with RBOOT's arcsin step that yields additional depth reduction; (4) tailoring EvalRound+ (IEEE Access 2025) to fit slim bootstrapping and RBOOT for further depth reduction.
We evaluate BootNet on multiple ResNet models on the ImageNet dataset. Compared to the state-of-the-art Orion (ASPLOS 2025), BootNet reduces end-to-end latency by 67-73% and storage by 76-90% while preserving plaintext accuracy. We also introduce BootNet-mini, enabling full ImageNet inference at ring degree $N=2^{15}$ (with over $120$-bit security via sparse-secret encapsulation) for the first time, while all previous works have to use $N=2^{16}$ or larger. BootNet-mini performs similarly in latency but reduces 30-55% storage requirement than BootNet, making it potentially more friendly for hardware acceleration.
## 2026/1280
* Title: Public Parameters as a First-Class Cost: A Three-Dimensional View of Updatable Vector Commitments, and a Group/Lattice Separation
* Authors: Kefan Liu
* [Permalink](https://eprint.iacr.org/2026/1280)
* [Download](https://eprint.iacr.org/2026/1280.pdf)
### Abstract
Updatable vector commitments are judged by how a k-position update affects the broadcast update information S and the per-proof update time T. We promote the public-parameter size P to a first-class metric, systematize known schemes in the resulting three-dimensional (S,T,P) space, and prove that every linear group-model vector commitment with position-binding requires P at least N, while the lattice homomorphic Merkle tree is simultaneously sublinear-update and pp-succinct. This turns the empirical group/lattice gap into a theorem, and we show the new axis is orthogonal to known lower bounds.
## 2026/1281
* Title: Resultants Meet Resultant: Improving CICO-1 and CICO-2 Attacks on ZK-Friendly Permutations
* Authors: Antoine Bak, Augustin Bariant, Ma|2l Hostettler, Vincent Neiger
* [Permalink](https://eprint.iacr.org/2026/1281)
* [Download](https://eprint.iacr.org/2026/1281.pdf)
### Abstract
The increasing usage of Zero-knowledge proof protocols has raised the need for cryptographic primitives that are efficient in that setting, called Arithmetization-oriented primitives. The security of such permutations is commonly evaluated with the CICO-$k$ problem.
The best known CICO-$1$ attack against ZK-Friendly permutations over $\mathbb{F}_q^t$ based on $\alpha$-inversions $x\mapsto x^{1/\alpha}$ exploits resultants (ASIACRYPT 2024, CRYPTO 2025). It starts from one input variable $x$ and introduces a temporary variable after each $\alpha$-inversion. With an efficient procedure to eliminate temporary variables, the attack reaches a time and memory complexity of $\tilde{\mathcal{O}}(D_I (2-1/\alpha)^n)$, where $D_I$ is the ideal degree of the CICO-$1$ modeling and $n$ is the number of $\alpha$-inversions. In this work, we study such an approach using two input variables $x_1 , x_2$, and we generalize the temporary variable elimination to that setting. Subsequently, we present a new CICO-$2$ attack framework and a new Start-From-The-Middle (SFTM) CICO-$1$ attack framework.
Both our attacks rely on fast bivariate resultants for their final bivariate system solving step. Using resultant algorithms with complexity almost linear in $D_I$, our CICO-$2$ and CICO-$1$ attacks reach a complexity almost linear in $\alpha^n D_I$ and in $D_I$, respectively, which is a first theoretical improvement. Designing an efficient implementation of these resultant algorithms remains a challenge, so for our practical contributions we turn to Villard's algorithm (ISSAC 2018). After adapting it to our context, we obtain practical complexities $\tilde{\mathcal{O}}((\alpha^n D_I)^{\gamma_2})$ and $\tilde{\mathcal{O}}(D_I^{\gamma_1})$ for CICO-$2$ and CICO-$1$ respectively, where $1.2 \le \gamma_1 \le 1.25 \le \gamma_2 \le 1.33$ depending on the chosen linear algebra exponent $2 \le \omega \le 3$.
Our attacks improve upon the best known ones against several instances of Anemoi, Rescue and Griffin, successfully breaking $128$-bit and $256$-bit security instances of Rescue in the CICO-$1$ setting and full-round instances of Anemoi and Griffin in the CICO-$2$ setting for the first time. Our implementation of the attack confirms the practicality of the approach.
## 2026/1282
* Title: Physics-Aware Temporal Feature Engineering for Eavesdropping Detection in BBM92 Quantum Key Distribution
* Authors: Saksham Gupta
* [Permalink](https://eprint.iacr.org/2026/1282)
* [Download](https://eprint.iacr.org/2026/1282.pdf)
### Abstract
Static Quantum Bit Error Rate (QBER) thresholding is the standard defense mechanism in deployed Quantum Key Distribution (QKD) systems. In noisy free-space optical (FSO) channels, however, natural atmospheric variations can camouflage short, low-intensity eavesdropping bursts, rendering fixed thresholds ineffective. This paper investigates physics-aware temporal feature engineering for machine learning-based anomaly detection in entanglement-based BBM92 QKD telemetry. A 24-dimensional feature space is computed over a 30-second sliding window, characterizing the temporal evolution and cross-observable correlations of QBER, the Bell S parameter, and photon coincidence rates. Evaluated on a simulated FSO telemetry dataset spanning 24 hours across five random seeds, static QBER thresholding achieves only 17.3% recall against blended sub-threshold attacks, while an XGBoost classifier trained on the proposed feature set achieves 96.9% recall and 97.6% precision within the same simulation framework. SHAP analysis suggests that detection is driven less by absolute error magnitude than by anomalous temporal decoupling between independent quantum observables. These results indicate that physics-aware temporal representations may improve resilience to stealthy attack strategies in simulated BBM92 environments, although validation on operational hardware and real telemetry remains an important direction for future work.
## 2026/1283
* Title: Privacy-Preserving Outsourced Witness Updates for Append-Only RSA Accumulators
* Authors: Hongzi He, Qianhong Wu, Bo Qin, Hao Gao, Willy Susilo
* [Permalink](https://eprint.iacr.org/2026/1283)
* [Download](https://eprint.iacr.org/2026/1283.pdf)
### Abstract
Append-only accumulators are a natural way to realize compact public-state registries, but under high-frequency updates, witness maintenance becomes a severe challenge because each insertion typically invalidates most existing witnesses. This challenge is particularly acute for intermittently online users in anonymous credential systems, who cannot continuously synchronize update information, while directly outsourcing witness updates may make repeated requests linkable. In this paper, we present a privacy-preserving outsourced witness-update protocol for append-only RSA accumulators. The protocol combines witness updates with Linear Integer Secret Sharing (LISS), enabling on-demand, client-stateless witness updates while preserving witness privacy and unlinkability against coalitions of update servers below the threshold, and providing accountability for malicious or malformed server responses. We formalize the system and threat models and analyze the security of the protocol. We further develop server-side optimizations for long catch-up windows and implement the full end-to-end protocol in Rust. Evaluation under multiple threshold settings and offline windows shows that the protocol supports practical one-shot witness updates after long offline periods, with client-side cost remaining independent of the number of missed updates and server-side cost being mainly determined by the catch-up span and the LISS distribution matrix.
## 2026/1284
* Title: Zero-Knowledge Proofs of Generalized Regular Expression Matching for Anonymized Email Verification
* Authors: Shreyas Londhe, Aayush Gupta, Sora Suegami, Yogesh Shahi, Rute Figueiredo, Parisa Hassanizadeh, Shahriar Ebrahimi
* [Permalink](https://eprint.iacr.org/2026/1284)
* [Download](https://eprint.iacr.org/2026/1284.pdf)
### Abstract
Digital communication increasingly underpins identity, financial transactions, and regulatory compliance. In many settings, possession of a DKIM-signed email serves as evidence of account control, transaction confirmation, or institutional affiliation. Yet demonstrating such properties typically requires revealing the full email or relying on centralized intermediaries, introducing privacy risks and additional trust assumptions. A framework called ZK Email addresses this limitation by applying zero-knowledge proofs (ZKPs) to email verification, enabling publicly verifiable proofs of authenticity while preserving message confidentiality. However, its existing implementations struggle to support complex, real-world messages due to the inefficiency of regular-expression verification over structured formats and rich alphabets.
We address this limitation with a new ZKP system for regex matching based on path verification over $\varepsilon$-free NFAs, yielding prover complexity linear in the captured path and independent of the original email's size. This approach enables practical validation of expressive standard structures required for full DKIM-signed email verification. To fully integrate our constructions into ZK Email, we design complete end-to-end ZK circuits that combine (i) DKIM signature verification, (ii) an arbitrary-length SHA-256 circuit with partial precomputation for $\texttt{rsa-sha256}$ under RFC 6376, and (iii) a general-purpose regex primitive enforcing structural constraints over email headers and body. We formalize the associated zero-knowledge relations and analyze their security under realistic adversary models. We implement the system (fully integrated with ZK Email and released under the MIT license) in $\texttt{Circom}$ and $\texttt{Noir}$, targeting $\texttt{Groth16}$ and $\texttt{UltraHonk}$ backends, and evaluate it in both client-side and zkVM (SP1) deployment settings. Experimental results on commodity hardware demonstrate substantial efficiency improvements over prior DFA-based approaches, achieving a $2$-$6\times$ speedup in proving time using the $\texttt{UltraHonk}$ backend, while supporting a significantly richer class of regex languages.
## 2026/1285
* Title: Oblivious Priority Queue and Single-Source Shortest Path in the External Memory Setting
* Authors: Arya Maheshwari, Elaine Shi
* [Permalink](https://eprint.iacr.org/2026/1285)
* [Download](https://eprint.iacr.org/2026/1285.pdf)
### Abstract
The study of oblivious algorithms is concerned with designing privacy-preserving algorithms whose memory access patterns reveal nothing about the secret inputs. Such algorithms have been deployed at scale in production systems, most notably in Signal's private contact discovery service. So far, all practical implementations of oblivious algorithms (e.g., those by Signal and Meta) rely on trusted hardware and operate within the external-memory model of computation. While it is known how to generically compile an arbitrary program to execute obliviously on an external-memory target machine, such generic oblivious simulations trade asymptotical efficiency for generality and therefore are rarely used in practice. Instead, customized oblivious algorithms tailored for the computational tasks of interest are almost always favored.
In this paper, we explore the single-source shortest path (SSSP) problem, a fundamental algorithmic building block with broad applications in scheduling, routing, graph mining, resource allocation and flow optimization. We present an external-memory oblivious SSSP algorithm for undirected graphs that achieves I/O efficiency $O(V + \frac{E}{B}\log\frac{E}{M})$ and total work $O(E\log E)$ assuming $E = \Omega(V)$, where $V$ denotes the number of vertices, $E$ denotes the number of edges, and $M$ and $B$ represent the target machine's cache size and block size, respectively. Our algorithm almost matches the best known non-private external-memory algorithm for SSSP, up to a $\log \log E$ factor in the second term of the I/O bound. The remaining $\log \log E$ gap is conjectured to be an inherent barrier, since making the underlying priority queue oblivious requires an $\Omega(\log \log n)$ blowup in I/O cost, which is known to be inherent.
As a by-product, we develop an improved external-memory oblivious priority queue that supports DecrKey operations. Specifically, while the construction of Jafargholi et al. attains optimal I/O efficiency, it is suboptimal in total work under a strong notion of obliviousnessrCowhere the adversary can observe both block-level and word-level accesses. This stronger security guarantee is the current industry norm and explicitly required by companies such as Signal. We present a new oblivious priority queue that achieves optimality in both dimensions. Specifically, we achieve an I/O cost of $O(\frac{1}{B}\log\frac{n}{M})$ and total work $O(\log n)$ per query where $n$ is the capacity of the priority queue.
--- Synchronet 3.22a-Linux NewsLink 1.2