IACR News
If you have a news item you wish to distribute, they should be sent to the communications secretary. See also the events database for conference announcements.
Here you can see all recent updates to the IACR webpage. These updates are also available:
30 August 2026
John Baena, Javier Verbel, Luis Villota
The wedge attack of Ran (EUROCRYPT 2026) recovers the secret oil space of a UOV public key over fields of characteristic two by exploiting the fact that the polar forms of the public map are alternating. It has since been generalized in several directions, each carrying its own algebraic tools, e.g., Jin et al. (PKC 2026). Working directly with the polynomials of an oil and vinegar map, we give a simpler description of the attack, based on a dual decomposition of oil-vinegar polynomials, and we recover the original wedge attack and its odd-characteristic analogue as special cases. This framework leads to a generalization, which we call the extended wedge attack. We identify two explicit conditions on the parameters that guarantee that the attack terminates with the recovery of the secret space. We also prove that the matrix of the extended wedge attack is permutation equivalent to the truncated Macaulay matrix in the attack by Furue-Ikematsu (CRYPTO 2026).
Damiano Abram, Gal Arnon, Valerio Cini, Paul Lou, Giulio Malavolta, Lawrence Roy
We prove that the Succinct Learning with Errors assumption, introduced by Wee (CRYPTO '24), and the Decomposed Learning with Errors assumption, introduced by Abram, Malavolta, and Roy (CRYPTO '25), are equivalent under appropriate parameter settings. Abram, Malavolta, and Roy proved that Succinct LWE implies Decomposed LWE. We establish the converse implication, showing that Decomposed LWE implies Succinct LWE.
Ganqin Liu, Hao Cheng, Jipeng Zhang
Mutual TLS (mTLS) authenticates both peers and therefore incurs post-quantum
signature costs on every connection. Concurrent handshakes expose independent
ML-DSA operations, but executing them jointly is difficult: signing is
rejection-divergent, verification uses heterogeneous keys, and synchronous TLS
APIs expose authentication work one connection at a time.
We present WeaveTLS, a wire-transparent architecture that executes ML-DSA authentication across concurrent TLS connections. Its primitive interface combines rejection-aware slot refill with per-request expanded-key handles, supporting both unrelated client keys and shared issuer keys. A stackless OpenSSL continuation lets an nginx worker suspend authentication, expose work from other connections, and execute compatible operations through optimized single-request, four-request, or eight-request AVX-512 kernels without fibers or cross-thread handoff. WeaveTLS preserves the TLS authentication barrier, certificate validation, and wire protocol.
On an AMD Ryzen 9 9950X3D, WeaveTLS improves one-core nginx mTLS throughput by 2.81-4.31$\times$ over OpenSSL's default ML-DSA path and by 2.19-3.29$\times$ over a synchronous reference-C control in the same provider across ML-DSA-44/65/87. At the primitive boundary, expanded-key eight-request verification is 1.65-2.23$\times$ faster than matched cached AVX2, and rejection-aware refill makes ML-DSA-65 signing 1.90$\times$ faster than otherwise identical lockstep scheduling. Cohort publication also weakens client-visible rejection timing under load, reducing attempt-count/latency correlation to 0.063 at concurrency 16 and 0.008 at 64; singleton execution retains the signal.
We present WeaveTLS, a wire-transparent architecture that executes ML-DSA authentication across concurrent TLS connections. Its primitive interface combines rejection-aware slot refill with per-request expanded-key handles, supporting both unrelated client keys and shared issuer keys. A stackless OpenSSL continuation lets an nginx worker suspend authentication, expose work from other connections, and execute compatible operations through optimized single-request, four-request, or eight-request AVX-512 kernels without fibers or cross-thread handoff. WeaveTLS preserves the TLS authentication barrier, certificate validation, and wire protocol.
On an AMD Ryzen 9 9950X3D, WeaveTLS improves one-core nginx mTLS throughput by 2.81-4.31$\times$ over OpenSSL's default ML-DSA path and by 2.19-3.29$\times$ over a synchronous reference-C control in the same provider across ML-DSA-44/65/87. At the primitive boundary, expanded-key eight-request verification is 1.65-2.23$\times$ faster than matched cached AVX2, and rejection-aware refill makes ML-DSA-65 signing 1.90$\times$ faster than otherwise identical lockstep scheduling. Cohort publication also weakens client-visible rejection timing under load, reducing attempt-count/latency correlation to 0.063 at concurrency 16 and 0.008 at 64; singleton execution retains the signal.
Ganqin Liu, Hao Cheng, Georgios Fotiadis, Jipeng Zhang, Chen Qian
Ethereum Proof-of-Stake (PoS) clients must verify large volumes of
Boneh--Lynn--Shacham (BLS) signatures for attestations, sync-committee messages,
and other consensus-critical objects within fixed slot deadlines. This recurring
cost competes with state transition, fork choice, and message propagation for
client CPU time, so reducing it increases the verification headroom available
under bursty load. Prior cryptographic-engineering work has shown that SIMD can
substantially accelerate BLS verification kernels, but these gains do not
automatically survive client software boundaries, runtime scheduling, and
irregular verification ranges.
We present AVXPoS, a client-aware batching framework for BLS verification in the Prysm Ethereum PoS client. AVXPoS treats batched verification as a client-level systems problem: it preserves Prysm's verification semantics while reorganizing protocol-shaped requests into native batched states that expose SIMD parallelism across API, worker, and native-backend boundaries. We instantiate AVXPoS with an AVX-512 backend for BLS12-381, combining Go-side range formation with C-side width-adaptive dispatch. On a resource-constrained two-core Intel host, AVXPoS gains $1.44$--$2.10\times$ over Prysm's production \texttt{blst} backend at selected small batch sizes that bracket the post-aggregation $p50/p95/p99$ batch-size quantiles of an all-subnets steady-state mainnet stress trace, and reaches up to $3.18\times$ in controlled capacity sweeps. On a 16-core AMD host, a production checkpoint-backfill verifier at Ethereum's 128-block request cap improves by $1.81\times$. Cross-platform results indicate that the relative speedup depends in part on Prysm's worker budget, because worker partitioning determines how much SIMD parallelism remains within each native range.
We present AVXPoS, a client-aware batching framework for BLS verification in the Prysm Ethereum PoS client. AVXPoS treats batched verification as a client-level systems problem: it preserves Prysm's verification semantics while reorganizing protocol-shaped requests into native batched states that expose SIMD parallelism across API, worker, and native-backend boundaries. We instantiate AVXPoS with an AVX-512 backend for BLS12-381, combining Go-side range formation with C-side width-adaptive dispatch. On a resource-constrained two-core Intel host, AVXPoS gains $1.44$--$2.10\times$ over Prysm's production \texttt{blst} backend at selected small batch sizes that bracket the post-aggregation $p50/p95/p99$ batch-size quantiles of an all-subnets steady-state mainnet stress trace, and reaches up to $3.18\times$ in controlled capacity sweeps. On a 16-core AMD host, a production checkpoint-backfill verifier at Ethereum's 128-block request cap improves by $1.81\times$. Cross-platform results indicate that the relative speedup depends in part on Prysm's worker budget, because worker partitioning determines how much SIMD parallelism remains within each native range.
Jan Bormet, Hussien Othman, Benedikt Wagner
In recent years, threshold encryption has gained a lot of interest, particularly due to its potential use in encrypted mempools in blockchains.
Standard security models allow the adversary to corrupt parties either statically (i.e., fixed at the onset of the game) or adaptively (i.e., via an oracle one-by-one, depending on keys and ciphertexts).
In this work, we observe that neither of these models captures the case in which a party decides to become corrupted based on secret information. For instance, in an encrypted mempool application with randomly rotating committees, an adversary may set up a smart contract that pays parties who reveal their decryption share, and parties decide whether to claim it based on, say, whether they are on the next committee. Such corruptions are not fixed in advance, but they are also not chosen solely by an external adversary based on public information.
We initiate the formal study of such internally motivated corruptions and partial decryptions. We introduce a security framework in which each party's corruption behavior may depend on its local secret state. That is, on a corruption, the adversary can submit a motivation function and all parties for which this motivation function outputs $1$ (on their secret information) are corrupted. A similar internally motivated behavior is allowed for releasing partial decryptions. We then study threshold encryption under this stronger notion of security. In particular, we show: - Negative Results: We show that for certain classes of motivation functions and number of queries, no threshold encryption scheme can satisfy security. We also show a concrete practical attack with internally motivated corruptions against a scheme that has been proven secure with standard corruptions. - Positive Results: We give two efficient classes of constructions from the (Bilinear) Diffie-Hellman assumptions. The first is secure when partial decryptions on the challenge ciphertext are internally motivated. The second additionally allows internally motivated corruptions.
In this work, we observe that neither of these models captures the case in which a party decides to become corrupted based on secret information. For instance, in an encrypted mempool application with randomly rotating committees, an adversary may set up a smart contract that pays parties who reveal their decryption share, and parties decide whether to claim it based on, say, whether they are on the next committee. Such corruptions are not fixed in advance, but they are also not chosen solely by an external adversary based on public information.
We initiate the formal study of such internally motivated corruptions and partial decryptions. We introduce a security framework in which each party's corruption behavior may depend on its local secret state. That is, on a corruption, the adversary can submit a motivation function and all parties for which this motivation function outputs $1$ (on their secret information) are corrupted. A similar internally motivated behavior is allowed for releasing partial decryptions. We then study threshold encryption under this stronger notion of security. In particular, we show: - Negative Results: We show that for certain classes of motivation functions and number of queries, no threshold encryption scheme can satisfy security. We also show a concrete practical attack with internally motivated corruptions against a scheme that has been proven secure with standard corruptions. - Positive Results: We give two efficient classes of constructions from the (Bilinear) Diffie-Hellman assumptions. The first is secure when partial decryptions on the challenge ciphertext are internally motivated. The second additionally allows internally motivated corruptions.
Zhengting Li, Lin Ding, Xinhai Wang, Honglei Wang, Jiang Wan, Fan Zhang
ARX-based design is a major building block of modern cryptographic ciphers due to its efficiency in software. Forr\'{o} is an ARX-based stream cipher proposed by Coutinho et al. at ASIACRYPT 2022, which was designed to provide higher security margin than the ChaCha stream cipher. In this paper, we propose a full automated MILP model called \textit{MinForr\'{o}}, to derive linear approximations for the Forr\'{o} stream cipher. For the differential part, a two-stage strategy to search for single-bit differential trails with high differential correlations is presented, which helps us to find the first-ever 3-round differential trails for Forr\'{o}. By combining the linear approximations obtained by \textit{MinForr\'{o}} and 3-round differential trail for Forr\'{o}, we propose improved differential-linear distinguishers for 4-, 5-, 5.25-, 5.5-, 5.75-, 6-, 6.25- and 6.5-round Forr\'{o} with complexities ${2^{32.44}}$, ${2^{46}}$, ${2^{50}}$, ${2^{64.32}}$, ${2^{87.12}}$, ${2^{117.92}}$, ${2^{174.92}}$ and ${2^{226.88}}$, respectively. The proposed differential-linear distinguishers for 4-, 5-, 5.25- and 5.5-round Forr\'{o} significantly improve the existing distinguishers by factors of ${2^{4.11}}$, ${2^{83.68}}$, ${2^{127.64}}$ and ${2^{178.20}}$, respectively. To the best of our knowledge, this is the first differential-linear distinguisher for Forr\'{o} that reaches 6.5 rounds, which is a significant advancement over the existing record of 5.5 rounds. We have implemented the differential-linear distinguishers for 4- and 5-round Forr\'{o} on a common PC, and the experimental
results confirm the correctness of these distinguishers. Furthermore, when combined with the \textit{Probabilistic Neutral Bits} (PNB) technique, we obtain key recovery attacks on 5.5-, 6-, 6.5- and 6.75-round Forr\'{o} with time complexities ${2^{149.20}}$, ${2^{151.84}}$, ${2^{213.49}}$ and ${2^{251.97}}$, respectively. The proposed key recovery attack on 5.5-round Forr\'{o} significantly improves the time complexity of the existing attack by a factor of ${2^{75.84}}$. To the best of our knowledge, this is the first key recovery attack on Forr\'{o} that reaches 6.75 rounds, which is a significant advancement over the existing record of 5.5 rounds.
Andrea Flamini, Anja Lehmann, Giada Sciarretta, Mario Scuro, Nicola Smaniotto, Alessandro Tomasi, Silvio Ranise
The European Digital Identity Wallet has integrated anonymous credentials into its technical specifications, and singles out four constructions for privacy-preserving revocation, drawn from two families: positive dynamic accumulators and signed-pairs. The two families are described in the literature in substantially different terms, and no common basis for comparing them exists, which currently prevents informed and quantitative decision making. In this work, we give a unified treatment of both families, showing that signed-pairs, despite their very different presentation, can be expressed in the standard accumulator syntax. We use this to define a single revocation mechanism that any of the four constructions instantiates, which in turn allows us to compare the resulting mechanisms both at the protocol level and empirically. We measure the performance of all four across the full credential lifecycle, on server-class hardware for the Status Manager and on a smartphone for the Holder and Verifier, with parameters taken from a live national eID scheme. No construction dominates in every aspect, and we make the resulting trade-offs explicit, showing which construction suits which deployment, and identify promising avenues for further improvement at the protocol level.
28 August 2026
Lorenz Panny, Ryan Rueger, Alessandro Sferlazza, Aleksei Udovenko
We present a new variant of the memoryless Delfs-Galbraith algorithm for finding an isogeny path from any given supersingular elliptic curve to a curve with known endomorphism ring. Through existing polynomial-time reductions, our algorithm allows one to solve the supersingular endomorphism-ring problem which lies at the heart of isogeny-based cryptography.
For arbitrary characteristics $p$ our algorithm asymptotically outperforms the previous best Delfs-Galbraith variant by a logarithmic factor; and matches the best previous asymptotic for characteristics with favourable structure.
In addition to the asymptotic analysis, we also calculate a concrete cost estimate for our algorithm in terms of finite-field operations, which indicates that our expected cost is lower than all previous Delfs-Galbraith variants, even concretely. By substituting bit-operation counts for the cost of arithmetic, we can deduce concrete bit-security estimates for isogeny-based cryptographic primitives, including (but not limited to) SQIsign.
As part of the calculation of the expected cost, we also provide a novel analysis of the probability of encountering "distinguished" subgraphs in an expander graph when relying various modes of graph exploration, whose potentially counterintuitive behaviour had apparently remained unnoticed thus far.
Finally, we provide a complete implementation of our algorithm(s), with the asymptotic bottleneck being attacked on GPUs, and the easier post-processing done on CPU using C++ as well as SageMath. Preliminary experimental results suggest that we can solve $100$-bit instances of the problem within less than $100$ GPU hours.
For comparison, the current cryptanalytic record for ECDLP (which has a comparable classical attack complexity) stands at $114$ bits, achieved using significantly more hardware and time.
For arbitrary characteristics $p$ our algorithm asymptotically outperforms the previous best Delfs-Galbraith variant by a logarithmic factor; and matches the best previous asymptotic for characteristics with favourable structure.
In addition to the asymptotic analysis, we also calculate a concrete cost estimate for our algorithm in terms of finite-field operations, which indicates that our expected cost is lower than all previous Delfs-Galbraith variants, even concretely. By substituting bit-operation counts for the cost of arithmetic, we can deduce concrete bit-security estimates for isogeny-based cryptographic primitives, including (but not limited to) SQIsign.
As part of the calculation of the expected cost, we also provide a novel analysis of the probability of encountering "distinguished" subgraphs in an expander graph when relying various modes of graph exploration, whose potentially counterintuitive behaviour had apparently remained unnoticed thus far.
Finally, we provide a complete implementation of our algorithm(s), with the asymptotic bottleneck being attacked on GPUs, and the easier post-processing done on CPU using C++ as well as SageMath. Preliminary experimental results suggest that we can solve $100$-bit instances of the problem within less than $100$ GPU hours.
For comparison, the current cryptanalytic record for ECDLP (which has a comparable classical attack complexity) stands at $114$ bits, achieved using significantly more hardware and time.
Antonio Faonio, Lili Tong
Non-malleability for non-interactive zero-knowledge proofs requires that, given a proof for a statement, it is infeasible to derive a valid proof for a related statement without knowing a corresponding witness. We introduce a modular framework for analyzing non-malleable reductions of knowledge (RoKs).
A reduction of knowledge transforms the task of proving knowledge for a source relation into proving knowledge for a target relation, often simpler or more structured. RoKs are an extremely useful tools for compositions. We identify different settings in which the composition of two RoKs, and in particular two non-interactive RoKs obtained via the Fiat-Shamir transform, preserves simulation extractability, and thus non-malleability. Our framework isolates simple and concrete properties required from each component, including novel forms of zero knowledge and new security notions that are easier to verify than full simulation extractability. This yields a systematic toolbox for establishing non malleability in modular proof systems.
Finally, we illustrate the power of our approach by analyzing LaBRADOR (Beullens and Seiler, CRYPTO’23), a lattice based proof system for R1CS. We provide the first analysis of its simulation extractability and, since LaBRADOR is not zero knowledge, we design a zero knowledge variant that preserves its practical efficiency and sublinear proof size. Our results show that non-malleability for advanced proof systems can be achieved modularly, significantly simplifying the security analysis.
Finally, we illustrate the power of our approach by analyzing LaBRADOR (Beullens and Seiler, CRYPTO’23), a lattice based proof system for R1CS. We provide the first analysis of its simulation extractability and, since LaBRADOR is not zero knowledge, we design a zero knowledge variant that preserves its practical efficiency and sublinear proof size. Our results show that non-malleability for advanced proof systems can be achieved modularly, significantly simplifying the security analysis.
Maher Mamah
Very recently, Wesolowski (ePrint 2026/1486) proposed a heuristic
algorithm for solving the supersingular isogeny-path problem in time and
memory \(p^{1/3+o(1)}\), where \(p\) is the characteristic of the underlying
field. Although this constitutes an asymptotic improvement over the previous
best-known complexity of \(p^{1/2}\log^{O(1)}(p)\), its concrete impact on
the security of isogeny-based cryptographic schemes, particularly SQIsign,
remains unclear due to the superpolynomial overhead hidden in the
\(p^{o(1)}\) factor and the algorithm's exponential memory requirement.
In this work, we assess the concrete cost of Wesolowski's attack, study its time--memory tradeoffs, and investigate optimizations based on the van Oorschot--Wiener (vOW) technique. Our analysis shows that, over the practical memory ranges considered, neither the optimized full-list attack nor its vOW variants outperform the previous state-of-the-art low-memory algorithm for computing supersingular endomorphism rings. We further study quantum claw-finding improvements. While Grover search can essentially remove the large memory requirement, it offers little improvement in running time, whereas Tani's algorithm provides a stronger gate--memory tradeoff at the cost of substantial coherent quantum memory. Overall, our results show that the asymptotic \(p^{1/3+o(1)}\) improvement does not directly translate into a comparable reduction in concrete security.
In this work, we assess the concrete cost of Wesolowski's attack, study its time--memory tradeoffs, and investigate optimizations based on the van Oorschot--Wiener (vOW) technique. Our analysis shows that, over the practical memory ranges considered, neither the optimized full-list attack nor its vOW variants outperform the previous state-of-the-art low-memory algorithm for computing supersingular endomorphism rings. We further study quantum claw-finding improvements. While Grover search can essentially remove the large memory requirement, it offers little improvement in running time, whereas Tani's algorithm provides a stronger gate--memory tradeoff at the cost of substantial coherent quantum memory. Overall, our results show that the asymptotic \(p^{1/3+o(1)}\) improvement does not directly translate into a comparable reduction in concrete security.
Yifei He, Zheng Zhou, Yu Chen, Zhi Guan, Zhong Chen
Silent threshold signatures (STS) and encryption (STE) enable threshold cryptography without interactive distributed key generation, allowing a group of $N$ parties to non-interactively generate a joint public signature verification key or an encryption key. However, modern distributed systems (such as Ethereum) rely on small, dynamically changing committees of size $n \ll N$ for efficiency, and existing silent threshold schemes either fail to support this dynamic setting or suffer from severe scalability issues. The only known STS construction for dynamic committees, Dyna-hinTS, requires an aggregation time of $O(N\log N)$ per epoch, tightly coupling the cost to the global system size rather than the small active committee. Furthermore, no STE scheme for dynamic committees has been proposed yet.
In this work, we present practical silent threshold signature and encryption schemes for dynamic committees, bringing the aggregation cost down to strictly depend only on the committee size $n$. For signatures, we redesign the Dyna-hinTS framework by replacing its Plonk-style SNARKs with linear pairing checks and a new polynomial commitment for representing the committee, yielding an aggregation time of $O(n\log^2n)$. We also introduce the first silent threshold encryption scheme for dynamic committees with matching efficiency. We further significantly optimize the silent setup phase common to prior STS and STE schemes, reducing each party’s one-time setup (i.e., generating the setup data, referred to as a "hint") cost from $O(N^2)$ to $O(N)$.
We implement our schemes in Rust, and the results demonstrate practicality at scale. For a system parameterized with $N = 2^{20}$ and $n = 2^{10}$, the per-party hint generation takes 197 seconds, and signature aggregation takes 0.153 seconds, achieving a $>1900\times$ improvement over Dyna-hinTS. At the same time, our aggregated signature size, verification key size, and verification time remain constant.
Jintai Ding, Hao Guo, Bo-Yin Yang
We estimate the intrinsic undercounting in the free-memory-access,
Macaulay coefficient-on-demand RAM modeling when applied to the
Parallelized Wiedemann-based XL in the Ran Wedge attack and in the
Furue--Ikematsu intersection attack, under some optimistic but still
feasible-sounding assumptions for the attackers.
We believe that this shows the memory effects makes UOV secure
enough for Ip, Is, and III. If NIST considers our original
parameters insufficiently convincing, we do not take Furue's
suggested replacements; we offer instead the following
perturbations, which hold $m$ --- and hence the compressed public key
--- fixed and spend only on the vinegar count: uov-Ip\# (256,116,44),
uov-III\# (256,186,72) and uov-V\# (256,250,96).
JP Aumasson
MERIDIAN is a 128-bit blockcipher proposed as a lightweight AES alternative. We show that its “Directional Substitution” layer is not injective by giving an explicit collision. This yields a full 12-round collision for every key. Consequently, no keyed instance of MERIDIAN is a permutation, so no decryption function can invert encryption on all plaintexts, and its blockcipher and PRP security claims fail. We additionally identify a one-round differential that exceeds the claimed bound by a factor 13.37.
Jianhang Xie, Sicheng Tan, Vishnu Naresh Boddeti, Zhichao Lu
Fully homomorphic encryption (FHE) lets a server run inference on encrypted data with strong privacy guarantees, but running a Transformer under FHE is expensive. Its non-linear operations, such as softmax, normalization, and activation, must be replaced with polynomial approximations that the CKKS scheme supports, and the depth of these approximations dominates inference cost. Existing FHE Transformers use hand-tuned approximation settings, such as iteration count and polynomial degree, applied uniformly across layers, models, and tasks. Hand-tuning is slow and error-prone. Even a single uniform setting has about $10^7$ choices, and manual search cannot exploit layer-wise variation.
AutoFHE, the only automated method with multi-objective search, targets ReLU-only CNNs and needs full fine-tuning per candidate, which is too costly for Transformers. Per-layer settings also push the search space to about $10^{85}$ for BERT and ViT and $10^{228}$ for LLaMA3, beyond both manual and fine-tuning-based search. We present ATLAS, a training-free framework that automates this search by treating each layer's approximation setting as a multi-objective optimization over latency and accuracy. The problem is hard: the decision space is large (96 or 256 variables), each configuration takes 70 to 1,000 seconds to evaluate even in cleartext, and 85 to 90 percent of configurations are invalid. ATLAS handles this with a two-stage optimization strategy and a surrogate model, completing the search in about one hour. Compared to an iterative softmax baseline, ATLAS cuts multiplicative depth and end-to-end latency by about 35 percent with little accuracy loss, and works across encoder-only, decoder-only, and vision Transformers, complementing parallel work on packing and matrix multiplication.
Sidaarth Sabhnani, David J. Wu
This work introduces SandwichPIR, the first single-server PIR protocol that implements the overwhelming majority of the server computation as dense 8-bit integer matrix multiplications on GPU tensor cores and requires no offline communication. For a 4 GB database with 32 KB records, SandwichPIR answers a query in 8.2 ms and communicates 688 KB of data. This amounts to a server throughput of 488 GB/s and is $88\times$ faster than the best CPU-based protocol that does not rely on offline communication.
The performance of SandwichPIR shines when processing a batch of queries from many independent clients. This moves the server from a memory-bandwidth-bound regime into a compute-bound regime. A single Nvidia L40S GPU can process a batch of 128 queries to the same 4 GB database in 21.0 ms. This gives an amortized per-query processing time of 0.16 ms and an effective throughput of roughly 24 TB/s. This is $50\times$ higher than the single-query throughput. With a fleet of 8 GPUs, SandwichPIR can process a batch of 128 queries to a 256 GB database in 119 ms and achieves an effective throughput of nearly 270 TB/s.
Finally, we show how to use SandwichPIR to enable private access to (text-only) English Wikipedia (8 GB compressed). Retrieving an article (up to 128 KB) requires 768 KB of client-server communication, with an estimated total end-to-end latency under 200 ms over a broadband network connection. By processing 64 queries at a time, a single GPU can handle over 2,500 queries per second (with a computational cost of \$0.20 per million queries based on current AWS pricing).
The performance of SandwichPIR shines when processing a batch of queries from many independent clients. This moves the server from a memory-bandwidth-bound regime into a compute-bound regime. A single Nvidia L40S GPU can process a batch of 128 queries to the same 4 GB database in 21.0 ms. This gives an amortized per-query processing time of 0.16 ms and an effective throughput of roughly 24 TB/s. This is $50\times$ higher than the single-query throughput. With a fleet of 8 GPUs, SandwichPIR can process a batch of 128 queries to a 256 GB database in 119 ms and achieves an effective throughput of nearly 270 TB/s.
Finally, we show how to use SandwichPIR to enable private access to (text-only) English Wikipedia (8 GB compressed). Retrieving an article (up to 128 KB) requires 768 KB of client-server communication, with an estimated total end-to-end latency under 200 ms over a broadband network connection. By processing 64 queries at a time, a single GPU can handle over 2,500 queries per second (with a computational cost of \$0.20 per million queries based on current AWS pricing).
Youbo Guo, Fengrong Zhang, Lei Liao, Yongzhuang Wei, Baocang Wang, Xiaogang Zhou
In recent years, quantum circuit optimization has become an important research topic. Motivated by the fact that quantum gates act on fixed physical wires and modify only their target wires, we propose two SMT encodings: an exact-G encoding and an at-most-G encoding with null gates. Our method speeds up most tested 4-bit S-box instances, achieving up to approximately 130x speedup on the ELEPHANT S-box. Importantly, our method enables automated synthesis of practical 5-bit S-box quantum circuits, such as KECCAK and ASCON. For the KECCAK S-box, in the no-ancilla setting, our model obtains concrete implementations with 17 NCT gates and full depth 51, and with 16 NCT gates and full depth 52, improving the EUROCRYPT 2025 result of Huang et al. It further finds a 13-gate implementation with full depth 55, which is gate-count optimal in the no-ancilla setting under the NCT gate set. In addition, when one ancilla qubit is allowed, our model obtains KECCAK implementations with Toffoli count 5, matching the theoretical lower bound. Finally, our model can also be applied to small-scale linear-layer implementation; for example, it finds a 24-CNOT implementation with depth 3 for the 16x16 linear matrix of MIDORI.
Baoyu Li, Kang Yang, Qi Liu, Binwu Xiang, Xiaogang Zhou, Xiang Xie, Yu Yu
Keyword private information retrieval (PIR) allows a client to retrieve a record associated with a keyword from a database without revealing any information about the keyword.
In the standard single-server setting, existing hintless keyword PIR protocols incur substantial communication and computation costs.
In this paper, we propose an efficient approach to generate $k$-hot vectors (i.e., vectors with exactly $k$ non‑zero components) in homomorphic-encryption form, and present a bucket-merging technique to decrease the maximum size of buckets. Based on these techniques, we construct LetoPIR, a hintless keyword PIR protocol that outperforms previous PIR protocols in the same setting. Compared to the state-of-the-art hintless keyword PIR scheme, SparsePIR (USENIX'23), LetoPIR achieves a $12.4\times \sim 17.0\times$ improvement in communication cost for databases ranging from $256$ MB to $4$ GB with records of $256$ bytes, and more than $3.0\times$ improvement in computation cost for the $256$ MB database.
Compared to the state-of-the-art keyword PIR scheme with client hint, KPIR (USENIX'25), LetoPIR reduces the communication cost by $51.4\times \sim184.8\times$, while achieving a similar (even better) computation cost.
Baoyu Li, Binwu Xiang, Kang Yang, Yu Yu, Xiaogang Zhou
Private information retrieval (PIR) enables a client to retrieve a record without revealing the index.Among existing PIR protocols with database-independent preprocessing, for each query, the protocols with low communication often take from several seconds to tens of seconds, while the faster protocols require hundreds of kilobytes for communication.
In this paper, we propose three techniques for different-type ciphertext conversions: (1) the first one is to generate a two-orbit SIMD selector from encrypted bits; (2) the second one is to convert a packed $\mathsf{RLWE}$ ciphertext into an aligned monomial $\mathsf{RGSW}$ ciphertext; (3) the third one is to produce an arbitrary monomial $\mathsf{RGSW}$ ciphertext from encrypted bits.
Building on these techniques, we design a new PIR protocol (called Atom), achieving the best of both worlds (i.e., having not only low communication but also fast computation). We implemented Atom and evaluated its performance for $256$ B records and databases from $256$ MB to $8$ GB. Specifically, Atom takes $3.0 \sim 3.8$ KB of online communication (i.e., the total communication, excluding the setup phase that can be run only once and reused for multiple queries), and takes $0.4 \sim 5.0$ seconds per query.
Compared to the state-of-the-art KsPIR (CCS'24), Atom reduces the online communication cost by a factor of $40.5\times \sim 51.3\times$, while its running time is comparable to KsPIR ($0.2 \sim 5.2$ seconds per query).
Yunqing Sun, Xinran Cai, Hanlin Liu, Xiao Wang, Wei Dong
Private Join and Compute (PJC) enables two parties to compute aggregates over matching records from their private datasets. In this work, we focus on the inner-product variant of PJC, which computes the inner product over matching records from their private datasets. It has important applications such as privacy-preserving ad conversion measurement. However, existing PJC protocols assume each party holds the entire dataset, which is often unrealistic in practice, where relevant datasets are distributed across multiple data owners. No existing PJC protocols directly support distributed input sets across multiple clients, while straightforward generic approaches introduce substantial overhead.
We propose an efficient approximate PJC protocol for distributed input sets while keeping the communication sublinear in the input size. Our protocol works in the semi-honest setting and uses two non-colluding servers that learn nothing beyond the final approximation. The core technical contribution is a novel adaptation of the G\"odel Prize-winning AMS sketch redesigned for efficient evaluation under fully homomorphic encryption. Concretely, we show a new structured randomness that can be homomorphically generated from short seeds using just 3 levels of multiplication while maintaining the best plaintext accuracy bound. Based on our optimized implementation, clients can insert each input element into an encrypted sketch in 30 ms, which has a size of 250 KB, independent of input size. The servers can recover the final output within seconds, orders of magnitude faster than the generic method.
We propose an efficient approximate PJC protocol for distributed input sets while keeping the communication sublinear in the input size. Our protocol works in the semi-honest setting and uses two non-colluding servers that learn nothing beyond the final approximation. The core technical contribution is a novel adaptation of the G\"odel Prize-winning AMS sketch redesigned for efficient evaluation under fully homomorphic encryption. Concretely, we show a new structured randomness that can be homomorphically generated from short seeds using just 3 levels of multiplication while maintaining the best plaintext accuracy bound. Based on our optimized implementation, clients can insert each input element into an encrypted sketch in 30 ms, which has a size of 250 KB, independent of input size. The servers can recover the final output within seconds, orders of magnitude faster than the generic method.
Yiteng Sun, Zhuo Huang, Yan Zhuang, Shuo Sun, Xinyu Li, Yu Yu, Weijia Wang
Soft Analytical Side-Channel Attacks (SASCA) combine leakage-derived priors from multiple intermediate variables with their functional dependencies through belief propagation (BP).However, when applying SASCA to large-scale cryptographic computations where algorithms are abstracted into extensive factor graphs with large candidate sets per variable node, the memory and computational complexity of SASCA become prohibitive. A natural first choice for large-domain variables is to fragment them into smaller-domain variables when the underlying computation decomposes accordingly. For modular addition and multiplication, however, preserving cross-fragment dependencies can introduce short cycles and coupled factor updates, motivating alternative inference strategies. We consider the Number Theoretic Transform (NTT) in ML-DSA as a representative large-scale cryptographic computation, where standard SASCA (with FFT optimization) requires approximately 122~GB of memory for message propagation in an unprotected single-trace setting, even for a 6-layer sub-NTT component, while masking further amplifies the graph size and inference cost.
\vspace{0.3em}
To address this limitation, we propose Greedy Region-Wise Pruning SASCA (GRWP-SASCA), a practical and efficient framework that enables scalable inference by dividing the global factor graph into manageable regions. The core idea is to replace global BP with a sequence of localized inference steps, where regions are incrementally merged, and the search space is reduced via greedy pruning of redundant structures and low-confidence candidates, thereby significantly reducing the memory and computational complexity of the BP algorithm. This design provides a flexible attack strategy for large-domain arithmetic factor graphs. Our results show that GRWP-SASCA transforms previously infeasible SASCA attacks on large-scale cryptographic computations into practical ones. Theoretical analysis of single-trace attacks on unprotected ML-DSA shows that GRWP-SASCA reduces the memory overhead associated with message propagation by a factor of up to $151$ compared to the standard SASCA, while achieving an estimated speedup by a factor of $68$. For $d$-order masked ML-DSA with multiple (say, $t$) traces, GRWP-SASCA achieves an estimated reduction in memory overhead associated with message propagation by a factor of up to $388.13t(d+1.14)/(d+2.44)$, while achieving a speedup by a factor of approximately $2d + 4$. Real-device experiments on an ARM Cortex-M4 platform demonstrate that the secret can be recovered from an unprotected implementation within approximately $15$ minutes with a single trace, with a peak message memory usage of approximately 0.9 GB. For first-order masked ML-DSA, the secret can be recovered within 3.2 hours using 8 traces, with a peak message memory usage of approximately 8.1 GB.
\vspace{0.3em}
To address this limitation, we propose Greedy Region-Wise Pruning SASCA (GRWP-SASCA), a practical and efficient framework that enables scalable inference by dividing the global factor graph into manageable regions. The core idea is to replace global BP with a sequence of localized inference steps, where regions are incrementally merged, and the search space is reduced via greedy pruning of redundant structures and low-confidence candidates, thereby significantly reducing the memory and computational complexity of the BP algorithm. This design provides a flexible attack strategy for large-domain arithmetic factor graphs. Our results show that GRWP-SASCA transforms previously infeasible SASCA attacks on large-scale cryptographic computations into practical ones. Theoretical analysis of single-trace attacks on unprotected ML-DSA shows that GRWP-SASCA reduces the memory overhead associated with message propagation by a factor of up to $151$ compared to the standard SASCA, while achieving an estimated speedup by a factor of $68$. For $d$-order masked ML-DSA with multiple (say, $t$) traces, GRWP-SASCA achieves an estimated reduction in memory overhead associated with message propagation by a factor of up to $388.13t(d+1.14)/(d+2.44)$, while achieving a speedup by a factor of approximately $2d + 4$. Real-device experiments on an ARM Cortex-M4 platform demonstrate that the secret can be recovered from an unprotected implementation within approximately $15$ minutes with a single trace, with a peak message memory usage of approximately 0.9 GB. For first-order masked ML-DSA, the secret can be recovered within 3.2 hours using 8 traces, with a peak message memory usage of approximately 8.1 GB.