Papers updated in last 183 days (Page 20 of 2708 results)

Last updated:  2026-08-03
Fair Multiparty Coin Tossing from Minimal Assumptions
Marshall Ball, Miranda Christ, Yevgeniy Dodis, and Rachit Garg
Coin flipping in the presence of a dishonest majority is a fundamental cryptographic primitive whose requirements lack a clean characterization. Recent work (Bonneau et al., Eurocrypt 2025) showed a lower bound that fair dishonest-majority coin-flipping implies delay functions. However, until now known upper bounds exhibited a significant gap: All existing protocols rely on assumptions that we do not know how to instantiate in the plain model. In this work, we close this gap. Specifically, we show that fair $n$-party coin flipping in the presence of up to $n-1$ malicious corruptions follows from the minimal assumption of delay functions. This completes the equivalence between delay functions and fair dishonest-majority coin-flipping protocols.
Last updated:  2026-08-03
High-Performance FPGA Accelerator for the Post-quantum Signature Scheme CROSS
Patrick Karl, Francesco Antognazza, Alessandro Barenghi, Gerardo Pelosi, and Georg Sigl
In October 2024, the National Institute of Standards and Technology announced the second round candidates of its standardization effort for additional post-quantum signatures. One of these candidates is CROSS, a code-based scheme relying on the restricted syndrome decoding problem. In this work, we present the first hardware design of CROSS, delineating efficient implementation strategies for the critical components of the cryptographic scheme. Our architecture parallelizes rejection sampling in two dimensions, enabling to simultaneously generate multiple vectors, as well as multiple entries of these vectors. We implement hardware friendly modular reduction circuits requiring only shifts and additions to obtain a DSP-free design, and carefully schedule operations enabling to hide them behind more computationally intensive tasks. Depending on the chosen security level, our design generates a key pair in 8 to 148 µs, signs a message in 338 µs to 4.62 ms, and verifies a signature in 303 µs to 3.27 ms on a Xilinx Artix-7 device. We show that our design is among the fastest and smallest when compared with other on-ramp candidates, namely LESS, MEDS, MAYO, Raccoon and SDitH, and comparable to current standard-selected ML-DSA, FN-DSA, and SLH-DSA in terms of efficiency.
Last updated:  2026-08-03
Anchor-DKG: Distributed Key Generation with Repeating Parties
Hanwen Feng, Qiang Tang, and Sri AravindaKrishnan Thyagarajan
A party may participate in multiple threshold cryptosystems. For example, it may serve on multiple overlapping threshold committees in a proof-of-stake blockchain or a distributed oracle network, or act as a client of multiple cryptocurrency wallet services built on threshold cryptography. With conventional distributed key generation (DKG), each threshold system independently generates its key shares, imposing significant key-management overhead on such a repeating party. In contrast, modern key-management practice favors deriving all cryptographic material deterministically from a single master key, raising a fundamental question: Can DKG be reconciled with key derivation while preserving security and compatibility with legacy threshold systems? We present Anchor-DKG, a new DKG protocol that allows up to $t^{\mathsf{rec}}$ (the reconstruction threshold) parties to deterministically fix their secret key shares while retaining standard security guarantees. Anchor-DKG supports concurrent executions with overlapping participants across multiple DKG instances and remains fully compatible with legacy threshold schemes, including ECDSA, BLS, Schnorr, and ElGamal. At the core of Anchor DKG lies a new technique: fixed-point distributed polynomial sampling (FpDpS). FpDpS allows parties to jointly sample a random $(t^{\mathsf{rec}}-1)$-degree polynomial $f$ such that $f(i) = s_i$ at designated points $i$, where each $s_i$ can be a private input, e.g., a key derived from a master secret. The final secret key remains $f(0)$, ensuring compatibility with existing discrete-log-based threshold systems. We provide an efficient construction of Anchor DKG under standard cryptographic assumptions, which, compared to classical constructions such as Gennaro et al. (J.Cryptol. 2007), only incurs one more point-to-point round and marginal computation. Experimental results show that, for a network size of $n=128$, our protocol incurs a per-party computation cost of $1.59$ s, compared to $1.36$ s for GJKR.
Last updated:  2026-08-03
CAKE requires programming - On the provable post-quantum security of (O)CAKE
Uncategorized
Kathrin Hövelmanns, Andreas Hülsing, Mikhail Kudinov, and Silvia Ritsch
Show abstract
Uncategorized
We revisit the post-quantum security of Password-Authenticated Key Ex- change (PAKE) from Key Encapsulation Mechanisms (KEM), focusing on (O)CAKE. Despite extensive study, these protocols still lack a security proof against quantum adversaries. We pinpoint exactly why by identifying the precise remaining obstacle. Most game-hopping arguments extend to the quantum setting via standard QROM techniques. The difficulty lies with ideal ciphers: adaptive programming and query recording are well understood classically, but no analogous tools exist for ideal ciphers in quantum superposition. To isolate the issue, we formalize programming for PAKE via a programming simulator, which captures adaptive programming on a family of permutations from an arbitrary distribution. We prove this notion is both necessary and sufficient for a proof. For necessity, we present a meta-reduction showing that any reduction-based proof for (O)CAKE must use programming in exactly this sense. We exhibit a class of KEMs – including practical schemes such as Kyber/ML-KEM – for which any successful reduction must either program or directly break the KEM challenge. The existence of this class implies that no fully generic KEM-based PAKE proof can avoid programming. For sufficiency, we show that this is the only remaining barrier: assuming the existence of our simulator and using known QROM tools, we give a complete post-quantum security proof for OCAKE. Together, our results explain why generic KEM-based PAKEs have so far resisted quantum security proofs and pinpoint the open problem whose resolution would complete the proof.
Last updated:  2026-08-03
The Role of Regular Integers Modulo n in RSA Cryptography
Klaus Dohmen and Mandy Lange-Geisler
We investigate a multi-prime multi-power generalization of the RSA cryptosystem for arbitrary moduli $n>1$, which under reasonable cryptographic assumptions works correctly for almost all messages $m<n$. Based on a new sharpening of Carmichael's theorem, tailored to regular integers modulo $n$, we prove that this generalization is correct precisely for messages represented by regular integers modulo $n$, thereby generalizing the original RSA correctness theorem. As in the original RSA scheme, decryption can be accelerated by Chinese remaindering, yielding a corresponding generalization of CRT-RSA.
Last updated:  2026-08-03
Cryptanalysis of LDPC-Based Pseudorandom Error-Correcting Codes
Tianrui Wang, Anyu Wang, Tianshuo Cong, Delong Ran, Jinyuan Liu, and Xiaoyun Wang
Pseudorandom error-correcting codes (PRCs), a novel cryptographic primitive recently proposed at CRYPTO 2024, are primarily applied in undetectable watermarking schemes for large generative models. However, the security of PRCs has not yet been systematically analyzed. To fill this gap, we present the first cryptanalysis of PRCs. Specifically, focusing on LDPC-PRC, the only known practical instantiation of PRCs, we propose three novel attacks that challenge its undetectability and robustness. To rigorously demonstrate the practical threat, we analyze the concrete attack complexity under realistic parameters and validate the attack effectiveness on both real-world large language models and generative image models, including DeepSeek and Stable Diffusion. Our analysis shows that the claimed security guarantees of LDPC-PRC are undermined across all practically feasible regimes. For example, our attacks can detect the presence of a watermark with overwhelming probability at a cost of $2^{22}$ operations. Beyond attacks, we further propose three defenses: parameter recommendation, implementation suggestion, and a revised key generation function. However, PRC-based watermarking schemes still fail to achieve 128-bit security due to inherent constraints of large generative models, such as the maximum output length of large language models. Overall, our work clarifies the concrete security limits of PRCs in real-world watermarking applications.
Last updated:  2026-08-03
Strided Frobenius Additive FFT and its Application to HQC
Ming-Shing Chen, Tun-You Chien, Chun-Ming Chiu, Cesare Huang, Han-Hsuan Lin, Chun-Tao Peng, and Bo-Yin Yang
Boolean polynomial multiplication is the primary computational bottleneck of the Hamming Quasi-Cyclic (HQC) key encapsulation mechanism. In this paper, we reframe the Frobenius Additive FFT (FAFFT) in ring-theoretic terms, via quotient-ring homomorphisms and the Chinese Remainder Theorem. This perspective shows that a complete decomposition into evaluation points is unnecessary for multiplication, and naturally yields the Strided FAFFT (SFAFFT), which operates over smaller finite fields with fewer butterfly stages and admits a much sparser CRT modulus for the non-power-of-two degrees in HQC. Our SFAFFT implementations outperform all previous FAFFT-based multiplications on every tested platform (x86 AVX2, GFNI, Apple M1, ARM Cortex-A72, and Cortex-M4), and set new overall speed records for HQC in nearly all settings except plain AVX2, where Toom-Cook-Karatsuba remains faster for the two smaller parameter sets.
Last updated:  2026-08-03
Dimension Reduction for SVP in Hawk: A Trace-Zero Approach
Guilhem Mureau and Alice Pellet-Mary
Let $E=\mathbb Q(\zeta_m)$ be a power-of-two cyclotomic field, with maximal totally real subfield $K=\mathbb Q(\zeta_m+\zeta_m^{-1})$. In previous work, Chevignard et al. (Eurocrypt'25) gave a reduction from module-LIP for rank-two module lattices over $\mathcal O_E$ to the norm-reduced Principal Ideal Problem (nrdPIP) in a quaternion algebra. We derive two consequences of this reduction. First, we obtain a polynomial time reduction from rank-$2$ module-LIP over $\mathcal O_E$ to rank-$3$ module-LIP over $\mathcal O_K$. Note that rank-$2$ modules over $\mathcal O_E$ are naturally seen as rank-$4$ modules over $\mathcal O_K$, so this is indeed an improvement. Our second result is specific to the module $\mathcal O_E^2$, underlying the Hawk signature scheme. In this setting, we also obtain a reduction to a rank-$3$ module-LIP instance over $\mathcal O_K$, but we can additionally show that these modules have a simple geometric shape: they are isomorphic to $\mathbb Z^{m/2+1} \perp \sqrt{2}\, \mathbb Z^{m/4-1}$. We then adapt Ducas' result (ePrint'23) to this setting. Putting everything together we obtain an algorithm breaking Hawk's key recovery by making polynomially many exact-SVP calls in lattices of dimension at most $3m/8+1$. This improves upon the previous analysis from Ducas (ePrint'23) which required exact-SVP calls in lattices of dimension at most $m/2+1$.
Last updated:  2026-08-03
Beyond Quadratic: Unlocking Pseudorandomness with Quartic Character
Mriganka Dey, Sampa Dey, Sampurna Pal, Subhabrata Samajder, and Rana Barua
We study pseudorandomness arising from quartic Dirichlet characters and obtain results that connect analytic and cryptographic perspectives. From an analytic perspective, and following the framework of Mauduit and Sárközy, we define a Boolean function $\psi_\pi$ from the quartic character $\chi_\pi$ modulo a Gaussian prime $\pi$ and analyze sequence $E_{p-1}=(\psi_\pi(1),\ldots,\psi_\pi(p-1))$ for $p=\pi\bar\pi \equiv 1 \bmod{4}$. Using classical character-sum bounds (Pólya-Vinogradov and refinements of Mauduit-Sárközy and Oon), we show that $E_{p-1}$ satisfies $W(E_{p-1}) =O(\sqrt{p}\log p)$ and $C_{\mu}(E_{p-1}) \leq 2^{\frac{\mu}{2}+1} \mu \sqrt{p}\log p,$ which imply strong pseudorandomness for small $\mu$. From the cryptographic side, we resolve an open question posed by Damgård by proving that quartic characters yield the secure pseudorandom generators and weak pseudorandom functions (wPRFs). Adapting similar techniques of Corrigan-Gibbs and Wu, we have shown that distinguishing quartic wPRF implies solving quadratic residuosity, via a chain of polynomial-time reductions. Our results show that under the Quadratic Residuosity Assumption, the quartic character also yields cryptographically secure wPRFs whose one-wayness was assumed in the construction of $\mathsf{Quartapus}$ signature scheme by Brier et al. and the post-quantum secure signature scheme $\mathsf{PorcRoast}_{4}$ by Beullens et al. that are more efficient and secure than legacy schemes based on the Legendre character.
Last updated:  2026-08-03
Perturbation of Hankel moment singular values and supersingular endomorphism rings via CVP: a $p$-adic super-resolution law and a fully computed pipeline
Radmir Isyanov
We give two rigorous results in post-quantum algebra with a $p$-adic strengthening and a complete reproducible pipeline. Part I proves an explicit sufficient noise bound under which the Hankel matrix of the power moments of supersingular $j$-invariants deterministically recovers the nodes, with the propagation constant written through the Vandermonde condition number (Weyl, Bauer-Fike); non-archimedeanly, the Teichmüller lift makes the Vandermonde matrix unimodular ($\mathrm{cond}_p = 1$ for every $L$) and an exact super-resolution law gives the $p$-adic precision loss as $2\sum_{i<j} v_p(x_i - x_j) + \sum_i v_p(c_i)$, a sharp analogue of Moitra's bound. Part II reduces a $\mathbb{Z}$-basis of $\mathrm{End}(E)$ to a rank-4 CVP and recovers the exact Gram matrix of the norm form in $\mathrm{poly}(\log p)$ time via Weil-pairing discrete logs (Shor; in the smooth regime actually run, the logs are classical Pohlig-Hellman), after which fixed-dimension LLL yields a canonical basis and a $\lambda_1$-criterion reads the node type. Both parts are joined by an end-to-end theorem and fully computed on real numbers: node recovery, real Vélu chains with measured degree, deterministic KLPT construction with the ideal-to-isogeny and smoothing steps, reading the torsion action in $\mathbb{F}_{p^4}$ and via Weil pairing + Pohlig-Hellman without an $O(N)$ table, true LLL + Fincke-Pohst, and the classification of all three nodes of $B_{23,\infty}$. The last KLPT heuristic (polynomial running time) is replaced by an explicit hypothesis PRH and a conditional theorem; PRH is shown to be exactly a Titchmarsh-type shifted-prime divisor sum with positive singular series, provable under GRH for fixed $p$, with uniformity in $p$ an identified open problem. Companion code (23 modules) verifies every numerical claim.
Last updated:  2026-08-03
RoK, Paper, SISsors – Toolkit for Lattice-based Succinct Arguments
Michael Klooß, Russell W. F. Lai, Ngoc Khanh Nguyen, and Michał Osadnik
Lattice-based succinct arguments allow to prove bounded-norm satisfiability of relations, such as $f(\vec{s}) = \vec{t} \bmod q$ and $\|\vec{s}\|\leq \beta$, over specific cyclotomic rings $\mathcal{O}_\mathcal{K}$, with proof size polylogarithmic in the witness size. However, state-of-the-art protocols require either 1) a super-polynomial size modulus $q$ due to a soundness gap in the security argument, or 2) a verifier which runs in time linear in the witness size. Furthermore, construction techniques often rely on specific choices of $\mathcal{K}$ which are not mutually compatible. In this work, we exhibit a diverse toolkit for constructing efficient lattice-based succinct arguments: (i) We identify new subtractive sets for general cyclotomic fields $\mathcal{K}$ and their maximal real subfields $\mathcal{K}^+$, which are useful as challenge sets, e.g. in arguments for exact norm bounds. (ii) We construct modular, verifier-succinct reductions of knowledge for the bounded-norm satisfiability of structured-linear/inner-product relations, without any soundness gap, under the vanishing SIS assumption, over any $\mathcal{K}$ which admits polynomial-size subtractive sets. (iii) We propose a framework to use twisted trace maps, i.e. maps of the form $\tau(z) = \frac{1}{N} \cdot \mathsf{Trace}_{\mathcal{K}/\mathbb{Q}}( \alpha \cdot z )$, to embed $\mathbb{Z}$-inner-products as $\mathcal{R}$-inner-products for some structured subrings $\mathcal{R} \subseteq \mathcal{O}_\mathcal{K}$ whenever the conductor has a square-free odd part. (iv) We present a simple extension of our reductions of knowledge for proving the consistency between the coefficient embedding and the Chinese Remainder Transform (CRT) encoding of $\vec{s}$ over any cyclotomic field $\mathcal{K}$ with a smooth conductor, based on a succinct decomposition of the CRT map into automorphisms, and a new, simple succinct argument for proving automorphism relations. Combining all techniques, we obtain, for example, verifier-succinct arguments for proving that $\vec{s}$ satisfying $f(\vec{s}) = \vec{t} \bmod q$ has binary coefficients, without soundness gap and with polynomial-size modulus $q$.
Last updated:  2026-08-03
PRISM with a pinch of salt: Simple, Efficient and Strongly Unforgeable Signatures from Isogenies
Andrea Basso, Giacomo Borin, Wouter Castryck, Maria Corte-Real Santos, Riccardo Invernizzi, Antonin Leroux, Luciano Maino, Frederik Vercauteren, and Benjamin Wesolowski
The problem of computing an isogeny of large prime degree from a supersingular elliptic curve of unknown endomorphism ring is assumed to be hard both for classical as well as quantum computers. In this work, we first build a two-round identification protocol whose security reduces to this problem. The challenge consists of a random large prime $q$ and the prover simply replies with an efficient representation of an isogeny of degree $q$ from its public key. Using the hash-and-sign paradigm, we then derive a signature scheme with a very simple and flexible signing procedure and prove its security in the standard model. The most efficient variant of our signature schemes features a signing which is $1.4\times$ to $1.6\times$ faster than the most recent implementaion of SQIsign, whereas verification ranges from $1.2\times$ slower to $1.01\times$ faster depending on the security level. The sizes of public key and signature are comparable to existing schemes.
Last updated:  2026-08-03
`ANSA-IBKEM`: Practical Quantum-Safe Identity-Based Key Encapsulation via Annular NTRU Trapdoors and Standardized PQC Arithmetic Reuse
Zhaohui Cheng and Kaixin Xiong
Identity-based key encapsulation remains attractive for managed systems, but practical post-quantum instantiations must balance compact ciphertexts, low decryption-failure rate (DFR), high-throughput and protection-friendly private-key extraction, and meaningful concrete security reductions. Existing NTRU-based IBE schemes satisfy these requirements only partially: compact DLP-style constructions lack a satisfactory reduction and have high failure rates, while LATTE's higher-rank structure and correctness treatment come with larger private keys, larger ciphertexts, and additional encapsulation/decapsulation work. These lines also use moduli and transform roots distinct from those of standardized PQC schemes, complicating deployment in implementations already built around standardized arithmetic. We introduce `ANSA-IBKEM`, a practical single-level identity-based KEM that retains the compact DLP-style identity relation while redesigning the trapdoor, extraction, correctness, and implementation layers around standardized post-quantum arithmetic. The construction combines annular NTRU trapdoors, Hybrid-Sampling extraction, a BCH-based message layer, and ciphertext compression over the ML-DSA modulus $q=8380417$. At the selected compressed points $(d_u,d_v)=(21,4)$ and $(23,5)$, the resulting ciphertext sizes are $3200\,\mathrm{B}$ and $7168\,\mathrm{B}$, with BCH-tail DFR estimates below $2^{-164}$ and $2^{-248}$ after applying one-sided $95\%$ upper bounds to the measured nonzero-error rates. We present a layered random-oracle-model security reduction for `ANSA-IBKEM` with an explicit concrete advantage bound and separate accounting for birthday-style collision terms. The proof accounts for the transform layer with explicit HHK-style losses in the identity-based setting, passes from exact extraction to ideal conditional extraction using Rényi divergence, and reduces to a programmed single-user encryption experiment connected to annular-NTRU/RLWE-style assumptions. This route separates transform losses, extraction-distribution losses, correctness terms, message-space terms, collision terms, and lattice-assumption terms, and it gives a proof template for DLP-style lattice IBKEMs. We also give a method for deep arithmetic reuse, with full low-level ML-DSA arithmetic reuse on the $N=1024$ line.
Last updated:  2026-08-03
Trapdoor-Free Multivariate One-Time Signatures in the Standard Model
Zijun Zhuang, Yingjie Zhang, and Jintai Ding
Constructing a multivariate signature scheme that is both trapdoor-free and provably secure in the standard model has been a long-standing challenge. In this paper, we present MQ-based W-OTS$^+$, the first multivariate one-time signature scheme to achieve these properties, and prove its \emph{existential unforgeability under chosen-message attack} via reductions to the \emph{MQ one-wayness (MQOW) assumption}. Our analysis focuses on the three properties that the MQ function family must satisfy within the W-OTS$^+$ framework: \emph{one-wayness} (OW), \emph{second-preimage resistance} (SPR), and \emph{undetectability} (UD). For SPR, we give a tight reduction from SPR to its OW. For UD, we provide a tighter reduction from UD to its OW, reducing the security loss from the previous bound of $O(\epsilon^{-4})$ to $O(\epsilon^{-2})$ over arbitrary finite fields. MQ-based W-OTS$^+$ consolidates the three assumptions required by W-OTS$^+$ (OW, SPR, and UD) into one standard multivariate assumption (MQOW). This shows that we can leverage some desirable properties of the MQ function family to construct a multivariate one-time signature in the standard model, instead of relying on trapdoors or zero-knowledge proofs.
Last updated:  2026-08-02
OpenLLM: Modular and Scalable zkSNARKs for Verifiable LLM Inference
Yunbo Yang, Yupeng Ren, Changtong Xu, Rui Zhang, Xuanming Liu, Jin Tan, Tao Wei, Bingsheng Zhang, and Kui Ren
Large language model (LLM) is increasingly deployed as a remote service, where users rely on third-party servers to perform computation. However, such settings introduce critical integrity concerns, as an untrusted server may deviate from the prescribed computation, skip expensive operations, or return incorrect results, while users lack practical approaches to verify execution correctness. Ensuring the correctness of LLM inference under untrusted execution remains a fundamental challenge. Zero-knowledge proofs (ZKPs) provide a principled approach verifying computation correctness, but applying them to LLM inference remains challenging. Modern LLMs involve a large number of non-linear operations and require modeling real-valued computation in finite fields, introducing substantial computational and memory overhead and potential loss of numerical precision. Moreover, the large scale of LLMs makes end-to-end verification difficult to scale, limiting the practicality of existing approaches. This paper presents OpenLLM, an efficient and modular system for verifiable LLM inference. Our key idea is to decompose large-scale LLM inference into a set of reusable atomic operators, each equipped with efficient ZKP protocols, enabling scalable verification at the operator level. Based on this abstraction, we design succinct non-interactive zero-knowledge proof constructions for representative non-linear functions, which can be composed into end-to-end inference pipelines independent of model architectures. We further evaluate OpenLLM across operator-level performance, end-to-end inference, layer-wise scaling, larger models, and approximation accuracy. The results show that OpenLLM achieves smaller proof sizes, lower verification cost, and improved numerical fidelity while scaling from individual operators to full-model inference. Compared with state-of-the-art interactive protocols, OpenLLM eliminates communication overhead through a fully non-interactive design while maintaining competitive efficiency. Building on this operator-level efficiency, it further enables a scalable and modular framework for end-to-end verifiable LLM inference, outperforming prior end-to-end approaches.
Last updated:  2026-08-02
SONIC: Concurrent Oblivious RAM & Data Structures for Low-Latency and High-Throughput
Nihal Talur and Ioannis Demertzis
Relying solely on encryption for privacy-preserving computations is prone to leakage-abuse/access-pattern attacks. TEEs, while cost-effective, are also vulnerable to side-channel attacks. Oblivious primitives, such as oblivious memory (ORAM) and data structures (ODS), are effective building blocks to mitigate these risks by concealing memory access patterns and side-channel information. Applications range from private contact discovery (Signal) to anonymous key transparency, encrypted email search, encrypted/oblivious databases, anonymous communication (Sparta/SP'25), private federated learning, LLM privacy (Compass/OSDI'25), and broader confidential computing efforts. Tree-based ORAMs (EnigMap (USENIX'23), GraphOS (PVLDB'23), Oblix (SP'18)) offer low latency but limited parallelism. Partition-based solutions like Snoopy (SOSP'21) shard data across subORAMs (which build oblivious hashtables on incoming requests, then linearly scan them), achieving high throughput by trading off latency, theoretically enabling linear scalability. In practice, Snoopy’s performance hinges on how quickly each subORAM can build the oblivious hashtable and complete its linear scan before exceeding latency targets, constraining server utilization and throughput. While supporting a TB-scale dataset with Snoopy is theoretically feasible, we estimate it would require 1000+ servers. In this work, we reconcile the fractured landscape between low-latency and high-throughput ORAM designs. We introduce SONIC: the first parallel/concurrent doubly-oblivious tree-based ORAM for TEEs. SONIC achieves 156K-3.3M req/s with a single server, tackling the core challenges of all tree-ORAM constructions: overcoming the sequential eviction bottleneck, enabling efficient batch evictions, and providing lock-free access/reshuffle/stash operations. SONIC achieves throughput 29-104$\times$ higher than EnigMap, and 158-560$\times$ higher than GraphOS, with lower latency. In the distributed, high-throughput setting, our SONIC-powered OMAP PMChain can replace Snoopy's subORAM, supporting higher throughput and $64\times$ larger datasets using the same hardware (reducing Snoopy's server requirements).
Last updated:  2026-08-02
A New Insight into Constructing Cryptographic Boolean Functions via Walsh Spectral Analysis
Shaozheng He, Jiongjiong Ren, Shaozhen Chen, Jiaxin Yan, and Jianhua Hou
Given that the Walsh spectrum directly determines key cryptographic properties of Boolean functions, the construction of such functions with desired spectral features has been a major research focus for decades. In this study, we first establish a unified framework for a class of specific Boolean function construction problems corresponding to Walsh transform, which we formally define as \textbf{Problem}. To tackle the \textbf{Problem}, we first designed the Iterative Walsh Recovery (IWR) algorithm as a framework, then added Forgetting and Greedy strategies for heuristic optimization to obtain the FG-IWR algorithm, and finally proved a necessary condition for optimization, ultimately proposing the Optimized Iterative Walsh Recovery (OIWR) algorithm. Through rigorous theoretical analysis and experimental validation, our algorithm simultaneously achieves theoretical guarantees, design flexibility, and computational efficiency. For application, we further present a novel construction method for low-weight correlation immune functions using the OIWR algorithm. Experimental results show that our method successfully addresses two fundamental constraints of Mesnager-Su's approach: limited construction capacity and power-of-two weight restrictions.
Last updated:  2026-08-01
CoSecRAG: Efficient Vector Similarity Search with Database and Query Privacy for RAG
Moyang Xie, Jiacheng Gao, Yuan Zhang, and Sheng Zhong
Retrieval-augmented generation (RAG) grounds large language models on external knowledge by using vector similarity search over document embeddings to identify relevant documents and supplying their contents as generation context. However, its retrieval stage creates privacy risks: user queries may reveal sensitive intents, while the database may contain proprietary or confidential records. Existing secret-sharing-based solutions that protect both query and database privacy remain costly. To make private vector similarity search more efficient, we present CoSecRAG, a two-server system for RAG that protects both database and query embeddings. CoSecRAG introduces Inner Product Preserving Query Mask (IPQ-Mask) to lower similarity-scoring costs by avoiding online secure multiplications and Post-Scoring Cluster Pruning (PSCP) to reorganize the execution pipeline for approximate retrieval, reducing private-extraction volume and secure top-K selection costs. We implement CoSecRAG and evaluate it on six BEIR datasets and large-scale synthetic benchmarks. CoSecRAG maintains strong retrieval quality while substantially reducing the cost of private vector similarity search. Compared with P²RAG, the most recent two-server baseline for private vector similarity search in RAG, CoSecRAG achieves up to 181× online score-computation speedup and 81× online speedup in secure top-K computation. End-to-end, it achieves up to 99× online and 34× offline runtime speedups. Compared with PRAG, CoSecRAG achieves 19×–58× online and 2×–16× offline end-to-end speedups.
Last updated:  2026-08-01
Resource Estimation of the Distributed Quantum Algorithm for the Elliptic Curve Logarithm Problem
MohamadAli Khajeian
Elliptic Curve Cryptography (ECC) underpins modern public-key infrastructure, relying on the computational hardness of the Elliptic Curve Discrete Logarithm Problem (ECDLP). While monolithic quantum architectures running Shor's algorithm threaten ECC, their physical realization is bottlenecked by massive logical qubit demands for modular inversion. Distributed Quantum Computing (DQC) offers a scalable pathway by interconnecting smaller, cooperative Quantum Processing Units (QPUs). In this paper, we adapt two state-of-the-art distributed quantum frameworks, namely a zero-quantum-communication paradigm and a sequential teleportation-based protocol, to the elliptic curve setting. We provide the first rigorous resource estimation of distributed ECDLP solvers. By incorporating the compact, register-sharing Extended Euclidean Algorithm (EEA) formulation, we quantify the physical design trade-offs for a cryptographically secure 256-bit elliptic curve on fault-tolerant architectures. Specifically, the zero-quantum-communication variant operates with 1094 to 1154 logical qubits per node, whereas the teleportation-based variant requires as few as 856 to 1098 logical qubits per node. Furthermore, optimizing the arithmetic window size ($\omega = 16$) over $k = 22$ nodes reduces the single-node Toffoli gate count to $2^{26.84}$, which represents an approximate $14\times$ reduction compared to the $2^{30.63}$ baseline of monolithic schemes. Our results delineate the architectural boundaries between inter-QPU communication, classical coordination, and single-chip hardware floors, mapping out an efficient design space for distributed quantum cryptanalysis.
Last updated:  2026-07-31
Solving the supersingular isogeny problem in time $p^{2/5+o(1)}$ using bivariate multipoint evaluation
Aleksei Udovenko
This note presents a new unconditional attack on the supersingular isogeny problem, with time and memory complexity $p^{2/5+o(1)}$. It builds on the approach by Eisenträger-Hallgren-Leonardi-Morrison-Park (2020) and Fuselier-Iezzi-Kozek-Morrison-Namoijam (2025), and is related to the recent heuristic attack with complexity $p^{1/3+o(1)}$ by Wesolowski (ePrint 2026/1486): all of these search for a separable isogeny from a curve to its Galois conjugate to form a non-scalar endomorphism. Our attack is based on highly theoretical multivariate multipoint evaluation algorithms from Kedlaya-Umans (2008, 2011), Bhargava-Ghosh-Guo-Kumar-Umans (2022), and Ghosh-Harsha-Herdade-Kumar-Saptharishi (2023), and therefore does not threaten isogeny cryptosystems in practice; it is of theoretical interest.
Last updated:  2026-07-31
Cryptanalysis of the Subfield Bilinear Collision Problem
Pierre Briaud and Romaric Neveu
The security of a recent MPC-in-the-Head signature scheme introduced at Crypto 2024 by Huth and Joux required the introduction of a new ad hoc hardness assumption called the Subfield Bilinear Collision (SBC) problem. By relying on the VOLE-in-the-Head framework, the authors further improved the performance of this scheme at Asiacrypt 2025, resulting in a very compact construction. In this paper, we improve the original cryptanalysis of SBC in several ways. First, we describe a link between the SBC problem and the decoding problem in the rank metric for codes linear over an extension field $\mathbb{F}_{q^m}$, strengthening its theoretical hardness and expanding the range of attacks on the SBC problem. Second, we analyze Gröbner basis algorithms applied to the bilinear modeling of SBC proposed by Huth and Joux and formulate conjectures on the behavior of this system. Finally, we describe another algebraic modeling of SBC obtained by using the Plücker relations between the maximal minors of a matrix. While we do not threaten the parameters of the proposed signature schemes relying on SBC, our work opens the door to a more accurate analysis. In particular, we were not able to analyze the inclusion of the field equations of $\mathbb{F}_{q}$ in the Gröbner basis algorithm, which is especially relevant since $q=2$ in these parameters. We leave this task for future work.
Last updated:  2026-07-31
Privacy-Preserving Multi-Signatures: Achieving Transcript-Aware Privacy
Yanzibo Zhou, Fuchun Guo, Willy Susilo, and Nan Li
Multi-signatures with key aggregation provide compact signatures verifiable under a single aggregated public key, but protect signer privacy only when public keys are used in a one-time manner. To address this limitation, recent privacy-preserving constructions provide stronger privacy guarantees under public-key reuse. However, they only guarantee privacy in the signature-only setting, where adversaries observe only the final aggregated public key and signature. In practical deployments, multi-signature protocols may be executed over public channels, where externally visible signing transcripts are exposed. These transcripts may link signing messages to public keys, thereby leaking signer identities and undermining existing privacy guarantees. In this paper, we formalize this gap by introducing transcript-aware privacy, a new framework that captures signer privacy in the presence of transcript exposure. Within this framework, we identify the strongest achievable privacy notion, in which signer identities remain hidden while the size of the signer set may be revealed. Our formulation departs from prior signature-only privacy models by explicitly modeling adversarial access to signing transcripts and allowing only inherent leakage such as the signer-set size. We present a new construction based on the MuSig2-H scheme of Tessaro and Zhu (EUROCRYPT'23). Our scheme achieves UNF-3 unforgeability in the AGM+ROM under the DL assumption and preserves full privacy in the signature-only setting. In the transcript-aware setting, it achieves weak set privacy in the ROM under the DDH assumption. In addition, we provide a concrete realization of the key-aggregation proof sharing procedure over public channels, eliminating the need for secure channels and improving practical deployability.
Last updated:  2026-07-31
The Non-Intersecting Codewords Problem and its Application to MPC-in-the-Head Signatures
Pierre Briaud, Philippe Gaborit, Romaric Neveu, and Gilles Zémor
Since McEliece introduced the first code-based encryption scheme in 1978, most code-based cryptographic constructions have relied on hard problems related to decoding random linear codes (or variants thereof) or code equivalence. More recently, the use of the MPC-in-the-Head paradigm has enabled the construction of a new class of very competitive digital signature schemes relying on such assumptions, including the NIST submissions Mirath, PERK, RYDE, and SDitH, as well as a recent proposal based on the so-called Subfield Bilinear Collision problem by Huth and Joux (Crypto 2024). In this work, we enrich the portfolio of code-based MPC-in-the-Head signature schemes by introducing a new hard problem to cryptography, referred to as the Non-Intersecting Codewords (NIC) problem. In this problem, one has to find two codewords of a given linear code such that their supports in the Hamming metric do not intersect. After discussing how to generate hard instances and studying several attacks on it, we show that the NIC problem can be used to construct a competitive MPC-in-the-Head signature scheme. Using generic constructions, we obtain smaller signature sizes than SDitH and PERK, attaining a signature size of 2~934~Bytes for NIST security level I.
Last updated:  2026-07-31
Secure Computation against $\mathsf{NC^1}$ Leakage without Secure Hardware
Yuyu Wang
In this work, we construct (stateful) leakage-resilient circuits (LRCs) secure against bounded-output-length leakage functions computable by \(\mathsf{NC}^1\) circuits under the mild worst-case assumption \(\mathsf{NC}^1 \subsetneq \oplus\mathsf{L}/\mathsf{poly}\), without relying on any leak-free hardware components, thereby resolving the open problem left by Bogdanov, Ishai, and Srinivasan (CRYPTO 2019; Journal of Cryptology, 2021) and Wang (CRYPTO 2025). Concretely, we first construct a leakage-tolerant circuit with succinct setup (sAI-LTC) secure against 2-adaptive \(\mathsf{NC}^1\) leakage, and then generically combine it with a 2-adaptive leakage-resilient composable encoding scheme to obtain the desired LRC. We further give a direct non-black-box instantiation that optimizes the compiled circuit size at the cost of a slightly larger setup, matching the circuit size of Wang's construction that relies on leak-free hardware while using a more compact setup. Finally, we show that our sAI-LTC generically implies a fine-grained multi-theorem non-interactive proof system for all \(\mathsf{NP}\), with compact common reference strings, perfect soundness, and multi-theorem zero-knowledge with offline simulation against \(\mathsf{NC}^1\) adversaries.
Last updated:  2026-07-31
Tensor Encodings for SIMD HSS
Jaehyung Kim
We study SIMD packing for the lattice-based homomorphic secret sharing scheme of Boyle-Kohl-Scholl (BKS) over dimension-$N$ cyclotomic rings. A trace construction with alternating tensor encodings matches the $\Theta(\sqrt N)$ packing of SIMD-HSS by Kim et al. (ePrint 2026/485). Its addition-closed mode uses $O(\log N)$ authenticated automorphisms, two BKS multiplications, and two constant multiplications; an alternating fast path roughly halves these costs. A second construction uses a three-term-progression-free slot set $A$: homomorphic traces isolate the product coefficients at $2a$ for $a\in A$, and a halving automorphism returns them to $a$. For fixed $k$ and conductor primes, with balanced prime-power factors, this packs $N^{1-o(1)}$ slots with one BKS multiplication, $O(kN^{1/(2k)})$ authenticated automorphisms, and $O(kN^{1/k})$ constant multiplications. Both constructions support standard (non-entropic) secrets. Two-party executions at 162 and 495 slots confirm the algebra and exact call counts.
Last updated:  2026-07-31
Antichain Winternitz: Guaranteed Garbled-Circuit Label Revelation on Bitcoin with Permissionless Recovery
Mukesh Tiwari and Aaron Feickert
Trust-minimized bridges on Bitcoin move SNARK verification off chain by evaluating the verifier as a garbled circuit. The bridge's on-chain spending condition obliges the Garbler to reveal the labels for one input without enabling the Evaluator to derive labels for any other input. Existing designs commit to each input bit with a Lamport signature which is costlier on chain, or with adaptors where there is no guarantee that the spend actually reveals the labels. We present Antichain Winternitz, a parametrized hash-chain construction whose admissible codewords form a constant-sum antichain. The on-chain locking script accepts an opening witness only if it encodes a valid codeword consistent with the committed chain terminals. Every accepted opening witness yields a valid codeword while the public off-chain table, verified during setup, maps every admissible codeword to its garbled-circuit labels, so any observer can recover them. Depending on the parameter set, we can obtain up to a 52.9% saving over Lamport signatures with only added off-chain storage of 43.8 kB per message bit.
Last updated:  2026-07-30
Zero Knowledge Barcode Decoding with Application to Private Online Attribute Verification
Kelsey Merrill, Anna Woo, Wenting Zheng, and Sarah Scheffler
Online attribute checking (e.g. proving age, residency) is increasingly common, yet standard implementations reveal far more personal information than necessary (e.g. all ID contents). Privacy-preserving alternatives exist but require digital inputs: anonymous-credentials or zero-knowledge (ZK) proofs of signature possession over a bitstring. However, it is challenging to gain integrity guarantees on the bitstring itself. C2PA offers a partial solution: C2PA-enabled cameras cryptographically attest to image origins with an embedded signing key, so a smartphone could provide a signed image of an ID barcode. However, since C2PA signs the image rather than the bitstring of the decoded barcode, the prover must additionally prove correct execution of the PDF417 barcode decoding algorithm on the signed image. Two barriers block this approach: images are large, yielding large proofs and long prover runtimes, and the PDF417 barcode decoding algorithm is highly data-dependent, making compilation into a ZK-friendly constraint systems non-trivial. We present an end-to-end ZK proof system for PDF417 barcode decoding, built on an adaptation of zkSNARK system Dorian (itself based on Spartan) with modifications: (1) adjusting Dorian's polynomial commitment to validate C2PA signatures more efficiently while cheaply checking consistency with the main Dorian proof, and (2) incorporating additional technical gadgets for set disjointness, data-dependent processing in R1CS, and state machines for greater efficiency. Implementing the PDF417 decoding algorithm as R1CS constraints is also nontrivial, as the algorithm is highly data-dependent and requires modifications to ensure soundness. Our system is the first to enable efficient barcode decoding in ZK. The best previous option was a zkVM, requiring prohibitively high computation and memory. We demonstrate that our system is significantly faster and uses far less memory. Furthermore, we suggest changes to the C2PA framework that would make future private verifiable image processing tasks more efficient. Though not yet ready for practical deployment, our system presents an alternative approach to private online attribute verification and demonstrates techniques of independent interest for data-dependent ZK computation.
Last updated:  2026-07-30
On the Security of Rotational (Non-)linearity in Sbox
Yadi Zhong
Recently, zero-knowledge proof protocols have gained much popularity due to the adoption in blockchain applications, e.g., zero-knowledge virtual machines. However, using the current standardized hash functions inside the generation of zero-knowledge proofs would incur much overhead in proof size, as well as prover and verifier’s runtime. In the past few years, various circuit-friendly hash functions has been proposed. Skyscraper-v2 is one example of such hash functions applying the split-and-lookup approach for better performance. In this paper, we expand the linear approximation definitions by extending it with circular shifts embedded in the approximation. Specifically, we consider the rotation of bits at both the input and output sides. We demonstrate it with Skyscraper-v2 Sbox. It allows us to better capture the recurring sequence in nonlinear Skyscraper-v2 SBox.
Last updated:  2026-07-30
Accelerating TFHE: Scalable Multiplication Algorithms and Efficient Carry Handling
Rostin Shokri and Nektarios Georgios Tsoutsos
Fully Homomorphic Encryption (FHE) enables private data processing on untrusted servers. However, FHE performance remains a critical bottleneck for applications such as machine learning, which rely heavily on non-linear operations, such as comparisons, and numerous ciphertext-ciphertext (CxC) and ciphertext-plaintext (CxP) multiplications. While modern FHE schemes such as TFHE efficiently handle non-linear operations, multiplication remains a significant performance bottleneck. This paper introduces new algorithms for CxC and CxP multiplication, as well as a ciphertext-plaintext dot-product algorithm, a critical kernel in machine-learning inference and convolution. Our approach uses Circuit Bootstrapping and Vertical Packing to generate partial products for CxC and CxP multiplication. The dot-product algorithm instead accumulates contributions from many multiplications directly, avoiding the cost of computing and adding each product separately. All three algorithms organize terms by output bit position, reduce them in parallel using carry-save compression or bound-driven reduction trees, and defer carry propagation to an efficient CMux-based final stage. We evaluate our algorithms and their parallel implementations against the default implementation in TFHE-rs and recent state-of-the-art approaches. Our results demonstrate speedups of up to $31.65\times$ on CPUs and $31.22\times$ on GPUs relative to TFHE-rs, and accelerate real-world neural network layers by up to $4.81\times$ over the fastest prior methods.
Last updated:  2026-07-30
Splitting Bilinear Groups: New Translations from Composite- to Prime-Order with Applications to Batch Arguments for NP
David Balbás, Dario Fiore, and Duy Nguyen
Bilinear groups, also known as pairing groups, are a versatile tool that enables many efficient cryptographic constructions. Among bilinear groups, those with a composite order (N = p · q for two large, secret primes p, q) offer an additional algebraic structure which is advantageous in many applications. They are however dramatically less efficient than their prime-order counterparts, so multiple translation frameworks for constructions from composite- to prime-order groups have been introduced in the literature. Motivated by the recent construction of Batch Arguments for NP (BARGs) with linear-size CRS by Chen, Elias and Wu [Asiacrypt ’25], based on composite-order groups, we notice that these previous frameworks fail to transfer their scheme to the prime-order setting. In this work, we identify and close this gap by introducing a new translation framework based on a new abstraction called dual encodings. The crucial feature of these objects is a security property called indistinguishability that allows embedding hidden subgroups, emulating composite-order groups more faithfully and thus enabling more powerful translations. Then, we realize dual encodings using functional encryption for function-hiding inner products. Finally, we apply our framework to build the first BARG with linear-size CRS from prime-order groups, while preserving the (statistical) somewhere extractability of previous constructions. Our result represents a significant step toward practically efficient BARGs and showcases a surprising application of functional encryption which we find of independent interest.
Last updated:  2026-07-30
Privacy Preserving Opinion Aggregation
Aggelos Kiayias, Vanessa Teague, and Orfeas Stefanos Thyfronitis Litos
There are numerous settings in which people’s preferences are aggregated outside of formal elections, and where privacy and verification are important but the stringent coercion-resistant properties of government elections do not apply, a prime example being social media platforms. In contrast to the centrally organised, single-shot elections on which most of the literature is focused, our settings of interest often have no trusted authority and are iterative, i.e., publish partial tallies before all votes are received. In this work, we explore opinion aggregation in a decentralised, iterative setting. In our novel protocol,randomly-chosen parties take turns to decrypt aggregated votes in an incentive-driven manner. Our simple construction leverages homomorphic encryption and secret sharing in a novel manner to provide security of the tally, public and individual verifiability, as well as vote privacy and liveness guarantees. Contrary to existing voting schemes, our protocol is ideal for the iterative setting.
Last updated:  2026-07-30
A Generalized Framework for Conditional Linear Cryptanalysis and Its Application to AES-Like Ciphers
Cheng Che, Tian Tian, Jing Yang, and Fan Yang
Conditional linear cryptanalysis represents an extension of linear cryptanalysis and has been applied to DES and AES. Notably, it enables the construction of a linear distinguisher for 4-round AES, which is considered unattainable through standard linear cryptanalysis. The underlying principle is that the correlation of a linear approximation can be improved when the data is restricted to a specific subspace or subset, thereby allowing more effective linear cryptanalysis. The critical challenge in conditional linear cryptanalysis lies in identifying appropriate conditions to impose on the data; however, previous methods rely on ad hoc strategies that depend heavily on expert intuition, which limits their generalization and application. In this paper, we propose a generalized framework for conditional linear cryptanalysis. The core tool is the conditional linear approximation table (CLAT), which quantifies linear correlations within constrained data subspaces. We further define a metric termed conditional linear weight, which balances the gain in correlation against the overhead of data filtering, thereby offering a quantitative measure of resistance against conditional linear cryptanalysis. Based on the CLAT and conditional linear weight, we develop an MILP-based automatic search model for conditional linear trails and devise systematic approaches for mounting distinguishing and key recovery attacks using these trails. Applying our framework to AES, Rijndael-256, ARIA, LED, Midori-128, and SKINNY-128, we demonstrate that conventional full-space bounds do not guarantee resistance against conditional linear cryptanalysis, and we propose improved linear attacks. Our framework provides systematic approaches and automatic tools for conditional linear cryptanalysis. It enables cryptanalysts to gain deeper insights into the statistical linear properties of cryptographic primitives and serves as a useful evaluation technique for new designs.
Last updated:  2026-07-30
Optimized One-Dimensional SQIsign Verification on Intel and Cortex-M4
Marius A. Aardal, Gora Adj, Arwa Alblooshi, Diego F. Aranha, Isaac A. Canales-Martínez, Jorge Chavez-Saab, Décio Luiz Gazzoni Filho, Krijn Reijnders, and Francisco Rodríguez-Henríquez
SQIsign is a well-known post-quantum signature scheme due to its small combined signature and public-key size. However, SQIsign suffers from notably long signing times, and verification times are not short either. To improve this, recent research has explored both one-dimensional and two-dimensional variants of SQIsign, each with distinct characteristics. In particular, SQIsign2D's efficient signing and verification times have made it a focal point of recent research. However, the absence of an optimized one-dimensional verification implementation hampers a thorough comparison between these different variants. This work bridges this gap in the literature: we provide a state-of-the-art implementation of one-dimensional SQIsign verification, including novel optimizations. We report a record-breaking one-dimensional SQIsign verification time of 8.55 Mcycles on a Raptor Lake Intel processor, closely matching SQIsign2D on the same processor. For uncompressed signatures, the signature size doubles and we verify in only 5.6 Mcycles. Taking advantage of the inherent parallelism available in isogeny computations, we present 5-core variants that can go as low as 1.3 Mcycles. Furthermore, we present the first implementation that supports both 32-bit and 64-bit processors. It includes optimized assembly code for the Cortex-M4 and has been integrated with the pqm4 project. Our results motivate further research into one-dimensional SQIsign, as it boasts unique features among isogeny-based schemes.
Last updated:  2026-07-30
Breaking Optimized HQC: The First Cache-Timing Full Decryption Oracle Key-Recovery Attack in Post-Quantum Cryptography
Haiyue Dong and Qian Guo
Hamming Quasi-Cyclic (HQC) has been selected by NIST for standardization in the post-quantum landscape. As deployment approaches, implementation security becomes as critical as mathematical hardness. In this work, we demonstrate that source-level constant-time coding is not a standalone guarantee: the compiled binary must inherently preserve this behavior. We identify a severe compiler-induced vulnerability within the official AVX2-optimized implementation of HQC, despite its claims of being constant-time. Although the C source code relies on secure, mask-based conditional selection, certain compiler optimizations rewrite this logic systematically. This transformation silently introduces secret-dependent control flow into the inner Reed-Muller decoding process, resulting in secret-dependent cache access patterns. Exploiting this vulnerability, we mount, to the best of our knowledge, the first cache-timing Full-Decryption-style oracle attack against a post-quantum cryptosystem. Using Flush+Reload on shared libraries, an unprivileged co-located adversary can extract fine-grained predicates of the decoder's internal state. To achieve full key recovery, we develop a novel, reliability-aware Soft Information Set Decoding (Soft-ISD) post-processing framework. Leveraging a GPU-accelerated meet-in-the-middle strategy optimized for heterogeneous platforms (including Apple Silicon), we demonstrate end-to-end secret key recovery for hqc-1 with less than 10 seconds of online trace collection.
Last updated:  2026-07-30
Power Analysis and Countermeasures on the MiMC Block Cipher
Elena Andreeva, Stefan Mangard, Rishub Nagpal, Arnab Roy, and Stefano Trevisani
Modern zero-knowledge (ZK), fully homomorphic encryption (FHE) and Multi-party Computation (MPC) protocols have motivated research interest in Arithmetization-Oriented (AO) cryptographic primitives. The use of these protocols on embedded platforms requires consideration for protection against side-channel analysis (SCA), including timing and power attacks. Compared to traditional bit-oriented block ciphers, the design of side-channel countermeasures for AO-based ciphers poses unique challenges due to their different mathematical properties and computation requirements. In this work, we perform side-channel analysis of MiMC, a well-known AO block cipher. We first consider its constant-time implementation over the BN254 prime field for both x86 and ARM-v7 targets. Next, we demonstrate both profiled (SASCA) and unprofiled (linear regression) power analysis of our implementation on the ARM Cortex-M4 microcontroller, showing that a DPA adversary can reduce the key-guessing space to just \(2^{30}\) candidates using only \(\approx\) 32000 power measurements, and the profiling adversary can perform full key recovery in as few as 100 measurements. Hence, we consider and compare two side-channel countermeasures: a classical ISW masking approach, and the redundant number representation (RNR) adapted for large prime fields. For the RNR countermeasure, we show that \(\approx 64\) bits of redundancy are sufficient to reduce the information leakage enough to make DPA attacks impractical. Our claim is supported both by a standard fixed-vs-random leakage assessment with 10 million collected traces and by quantitative analysis via SASCA attacks. Finally, we compare the performance of the RNR countermeasure with first-order masking. While masking incurs in a \(\approx 8.3\times \) overhead on a Cortex-M4 MCU and in an \(\approx 81\times \) overhead on an x86-64 CPU, the RNR approach only introduces a \(\approx 50\%\) overhead on both targets.
Last updated:  2026-07-30
Leakage-Resilient Circuits against $\mathsf{NC^1}$, Revisited
Yuyu Wang
In this study, we revisit leakage-resilient circuits (LRCs) against $\mathsf{NC}^1$-leakage and propose new constructions that minimize the reliance on leak-free hardware. Specifically, we first present a stateless LRC scheme that is resilient to $\mathsf{NC}^1$-leakage, and then extend it to a leakage-tolerant circuit with auxiliary input (AI-LTC). By integrating this with a 2-adaptive leakage-resilient encoding scheme, we achieve a stateful LRC scheme that uses a secure hardware component. In comparison to the state-of-the-art constructions against $\mathsf{NC}^1$-leakage by Miles and Viola (STOC 2013), both the encoder during the leak-free phase in our stateless LRC and the secure hardware component in our stateful LRC are typically much smaller, as their sizes are independent of the original circuit size. Additionally, we provide a non-black-box instantiation of stateful LRC, resulting in a smaller compiled circuit. The security of all our constructions is based on the very mild worst-case assumption $\mathsf{NC}^1 \subsetneq \oplus\mathsf{L}/\mathsf{poly}$, which is strictly weaker than the assumption $\mathsf{NC}^1 \subsetneq \mathsf{L}$ used by Miles and Viola. Furthermore, we propose a generic conversion from AI-LTCs to non-interactive zero-knowledge proofs with offline simulation (oNIZK) for all $\mathsf{NP}$ in the fine-grained setting. Our instantiation derived from it has small common reference strings, perfect soundness, zero-knowledge against adversaries in $\mathsf{NC}^1$ under $\mathsf{NC}^1 \subsetneq \oplus\mathsf{L}/\mathsf{poly}$, and minimal verification complexity. Finally, we show that any fine-grained oNIZK cannot simultaneously achieve perfect soundness and verifiable common reference strings, thereby ruling out the possibility of constructing stateful LRCs without secure hardware by eliminating the trusted setup of our AI-LTC.
Last updated:  2026-07-30
Class-Average Differential Uniformity and Fixed-Instance Constraints in Modular and Rounded Feistel Components
Yu Morishima and Masahiro Kaminaga
This paper analyzes differential probabilities in one Feistel round with binary-encoded modular-linear maps or rounded linear maps as internal components. For any fixed round key and any nonzero input difference chosen independently of the matrix instance, the output-difference distribution is uniform after averaging over the instance distribution. For a fixed instance, the 2-adic valuations of the relevant matrix entries deterministically fix certain output-difference bits. We consider an adversary that selects a low-weight input difference maximizing the number of fixed bits and derive lower bounds on the restricted maximum differential probability and its average over instances. The matrix-averaged lower bound is expressed in terms of the exponential moment of the maximum fixed-bit count and is compared with the generic lower bound induced by differential-pair symmetry.
Last updated:  2026-07-30
Revisiting Shamir Secret Sharing for Threshold Fully Homomorphic Encryption
Jiseung Kim, Seunghu Kim, and Hyung Tae Lee
Recent advances in lattice-based threshold cryptography, including threshold fully homomorphic encryption (ThFHE) and threshold public key encryption (ThPKE), commonly employ Shamir secret sharing over rings. While conceptually simple, these schemes suffer from rapidly growing denominator-clearing factors required for secret reconstruction as the number of parties $N$ increases, which in turn necessitates larger ciphertext moduli and complex reconstruction procedures. In this work, we revisit the notion of subtractive sets underlying ring-based Shamir secret sharing and present a refined framework for constructing integer-reconstructible sharing over cyclotomic rings. To that end, we introduce a new geometric analysis of Lagrange coefficients and show that the resulting reconstruction factors can be made significantly smaller under specific settings. In particular, our framework enables smaller ciphertext sizes in $(t,N)$-threshold settings, and yields improved correctness and efficiency when applied to any ring-based threshold construction employing Shamir secret sharing over cyclotomic rings. Specifically, in lattice-based one-round $(t, N)$-ThFHE schemes, our approach reduces the bit-size of ciphertext moduli from $O(N)$ to $O(t\log (N/t^2))$ while ensuring efficient denominator handling. For lattice-based ThPKE, our method yields a new bound on reconstruction factors that improves upon the recent state-of-the-art result of Pilvi. Moreover, we implement ThFHE schemes over cyclotomic rings based on our framework and demonstrate their practical efficiency. Our experimental results show that each algorithm completes within $0.2$ seconds for $N=64$ and remains scalable for larger configurations with $N\geq 256$.
Last updated:  2026-07-30
LEAF: A Low-Latency Evaluation Architecture for Feedforward Block in Privacy-Preserving Transformer Inference
Linru Zhang, Xiangning Wang, Xianhui Lu, Huaxiong Wang, and Kwok Yan Lam
Fully homomorphic encryption (FHE) is an appealing and promising solution for privacy-preserving transformer inference to protect users' privacy. However, the huge computational overhead makes it unrealistic to apply FHE in real-world transformers for large language models (LLM). Current FHE-based approaches to secure transformer inference face significant performance challenges, with total latency exceeding 5 hours for 32-input batches. The feedforward block, comprising a large-scale matrix multiplication followed by a GELU evaluation, is widely recognized as one of the most computationally intensive components in privacy-preserving transformer inference. In the state-of-the-art system NEXUS, evaluating the feedforward block incurs a total latency of 5,378 seconds, processing up to 32 inputs per batch. We aim to reduce the latency and propose LEAF, a low-latency evaluation architecture for the feedforward block. LEAF introduces a novel combination of fast matrix multiplication and an asymptotically efficient algorithm for computing non-polynomial activations. When evaluated on the BERT-base model, LEAF reduces total latency to 53.4 seconds, offering a $100\times$ speedup over the state-of-the-art method in the same environment. Our implementations are available.
Last updated:  2026-07-30
Verifiable Outsourced BTE with Silent Setup: Achieving Constant-Rate Batched Delegation
Kwangsu Lee
Batched threshold encryption (BTE) is a novel public-key paradigm in which, once a batch of $B$ ciphertexts is designated, a decrypter evaluates them using decryption key shares generated by decryption committee nodes via threshold reconstruction. To mitigate Miner Extractable Value (MEV) attacks in fully decentralized environments like blockchains, it is essential to guarantee mempool privacy while supporting a silent setup that allows decentralized key generation among decryption nodes. Furthermore, to efficiently process large batches of ciphertexts, an outsourcing mechanism that delegates heavy decryption computations to a cloud server is indispensable. In this paper, we observe that naively adding decryption outsourcing to a threshold batched identity-based encryption with silent setup (TBIBE-SS) scheme of Gong et al.~(EUROCRYPT 2026) causes the outsourcing communication overhead to scale undesirably with the number of decryption nodes. To overcome this limitation, we introduce a partial re-randomization technique--replacing conventional full re-randomization--and incorporate a handle-based oracle query mechanism into the security model. Based on these techniques, we propose a communication-efficient outsourced TBIBE-SS (O-TBIBE-SS) scheme and formally prove its security. We then combine our O-TBIBE-SS scheme with additional cryptographic primitives to construct a verifiable outsourced BTE-SS (VOBTE-SS) scheme, which supports both delegated decryption and verifiability of outsourced computation, proving its security under an augmented threat model. Our VOBTE-SS scheme represents the first construction to achieve efficient batched decryption outsourcing in terms of both communication and computation overhead within decentralized environments.
Last updated:  2026-07-30
Zero-Knowledge Proof-Carrying Data from Accumulation Schemes
Tianyu Zheng, Shang Gao, and Xun Liu
Proof-carrying data (PCD) is a powerful cryptographic primitive for ensuring computational integrity in distributed settings. State-of-the-art PCD constructions based on accumulation schemes achieve practical prover efficiency and support a wide range of applications. However, realizing zero-knowledge for accumulation-based PCD remains challenging, particularly for high-degree relations. Existing solutions often incur substantial overhead due to the need for zero-knowledge in both the underlying non-interactive arguments of knowledge (NARKs) and accumulation schemes. In this work, we present new theoretical and practical improvements for zero-knowledge PCD. First, we propose a novel construction that eliminates the need for zero-knowledge NARKs by separating the compliance predicate and accumulation verification, thereby reducing proof size and improving efficiency. Second, we design an efficient zero-knowledge accumulation scheme for special sound protocols, introducing techniques such as masking vectors and zero-knowledge sum-check protocols to ensure privacy with minimal overhead. The theoretical analysis demonstrates that our construction achieves logarithmic proof size and verification time for d-degree NP relations, and outperforms existing solutions in both asymptotic and concrete complexity.
Last updated:  2026-07-29
Scribe: Low-memory SNARKs via Read-Write Streaming
Anubhav Baweja, Pratyush Mishra, Tushar Mopuri, Karan Newatia, and Steve Wang
Succinct non-interactive arguments of knowledge (SNARKs) enable a prover to produce a short and efficiently verifiable proof of the validity of an arbitrary NP statement. Recent constructions of efficient SNARKs have led to interest in using them for a wide range of applications, but unfortunately, deployment of SNARKs in these applications faces a key bottleneck: SNARK provers require a prohibitive amount of time and memory to generate proofs for even moderately large statements. While there has been progress in reducing prover time, prover memory remains an issue. In this work, we describe Scribe, a new low-memory SNARK that can efficiently prove large statements even on cheap consumer devices such as smartphones by leveraging a plentiful, but heretofore unutilized, resource: disk storage. Instead of storing its (large) intermediate state in RAM, Scribe's prover instead stores it on disk. To ensure that accesses to state are efficient, we design Scribe's prover in a read-write streaming model of computation that allows the prover to read and modify its state only in a streaming manner. We implement and evaluate Scribe's prover, and show that, on commodity hardware, it can easily scale to circuits of size $2^{28}$ gates while using less than 750 MB of memory and incurring only $10$% proving latency overhead compared to a state-of-the-art memory-intensive baseline (HyperPlonk [EUROCRYPT 2023]) that requires much more memory.
Last updated:  2026-07-29
Certified in Theory, Broken in Practice: Assumption Gaps in Cryptographic Model Certification
Uncategorized
Carter Luck, Olive Franzese-McLaughlin, Elisaweta Masserova, Akira Takahashi, Antigoni Polychroniadou, and Nicolas Papernot
Show abstract
Uncategorized
Privacy-preserving machine learning auditing protocols allow auditors to assess models for properties such as accuracy or fairness, without revealing their internals or training data. This makes them especially attractive for auditing models deployed in sensitive domains such as healthcare or finance. For these protocols to be meaningful in real-world audit settings, though, their guarantees must reflect how the model will behave once deployed, rather than merely certifying its behavior during an audit. Existing security definitions often miss this mark: most certify model behavior only on a fixed audit dataset, without ensuring that the same guarantees generalize to other datasets drawn from the same distribution. As we show, this gap allows a model provider to attack many cryptographic model certification (CMC) schemes built on secure zero knowledge proofs (ZKP) by carefully engineering training data, resulting in models that exhibit benign behavior during an audit, but pathological behavior in practice. For example, we empirically demonstrate that an attacker can certify that a model achieves over 99% accuracy on an audit dataset, but less than 30% accuracy on fresh samples from the same distribution. To address this gap, we formalize rigorous cryptographic security notions tailored to CMC frameworks, introduce a generic protocol template, and prove that it satisfies these requirements. Our results thus offer both cautionary evidence about existing approaches and constructive guidance for designing secure, privacy-preserving ML auditing protocols.
Last updated:  2026-07-29
FLOSS: Fast Linear Online Secret-Shared Shuffling
Ian Chang, Sela Navot, Alex Ozdemir, and Nirvan Tyagi
Randomly permuting secret data vectors is a core building block in many privacy-preserving protocols, including those for analytics, advertising, and communication. Existing approaches either rely on computation-heavy public key cryptography and zero-knowledge proofs or scale poorly for large vectors due to use of a quasilinear-sized permutation network. This work presents a preprocessing approach to enable fast linear-time online shuffles in the malicious-secure two-party computation (2PC) setting. We propose FLOSS, a 2PC protocol for securely computing any interactive arithmetic permutation circuit, a notion we introduce to capture how higher level protocols are built on secret-shared field arithmetic and permutations. We show how secret-shared sorting (a subprotocol in data analytics) can be described as an arithmetic permutation circuit, and can thus be compiled to an efficient online 2PC protocol using FLOSS. Our implementation and evaluation confirm FLOSS performs online shuffles fast: shuffling $2^{20}$ elements in under 500ms, greater than $800\times$ faster than state-of-the-art alternatives.
Last updated:  2026-07-29
Privacy-Preserving Identifier Checking in 5G
Marcel D.S.K. Gräfenstein, Stefan Köpsell, and Maryam Zarezadeh
Device identifiers like the International Mobile Equipment Identity (IMEI) are crucial for ensuring device integrity and meeting regulations in 4G and 5G networks. However, sharing these identifiers with Mobile Network Operators (MNOs) brings significant privacy risks by enabling long-term tracking and linking of user activities across sessions. In this work, we propose a privacy-preserving identifier checking method in 5G. This paper introduces a protocol for verifying device identifiers without exposing them to the network while maintaining the same functions as the 3GPP-defined Equipment Identity Register (EIR) process. The proposed solution modifies the PEPSI protocol [USENIX, 2024] for a Private Set Membership (PSM) setting using the BFV homomorphic encryption scheme. This lets User Equipment (UE) prove that its identifier is not on an operator’s blacklist or greylist while ensuring that the MNO only learns the outcome of the verification. The protocol allows controlled deanonymization through an authorized Law Enforcement (LE) hook, striking a balance between privacy and accountability. Implementation results show that the system can perform online verification within five seconds and requires about 15 to 16 MB of communication per session. This confirms its practical use under post-quantum security standards. The findings highlight the promise of homomorphic encryption for managing identifiers while preserving privacy in 5G, laying the groundwork for scalable and compliant verification systems in future 6G networks.
Last updated:  2026-07-29
Non-Interactive Secure Computation with Constant Communication Overhead
Yuval Ishai, Ziyang Jin, Naty Peter, and Akshayaram Srinivasan
We study the communication complexity of non-interactive secure computation (NISC) protocols with security against malicious adversaries. We give a general NISC protocol for any two-party function computed by a Boolean circuit $C$ using only $O(|C|\lambda)$ bits of communication, where $\lambda$ is a computational security parameter. This protocol is unconditionally secure in the random oracle model, assuming a standard random bit OT correlations setup. Compared to Yao's semi-honest protocol, our protocol incurs only a constant communication overhead and achieves security against malicious parties with no additional interaction. Prior works achieved such constant overhead by either using a larger number of rounds or more structured correlations.
Last updated:  2026-07-29
Security Analysis on UOV Families with Odd Characteristics: Using Symmetric Algebra
Yi Jin, Yuansheng Pan, Xiaoou He, Boru Gong, and Jintai Ding
UOV and its variants have been submitted to NIST's PQC Standardization Project. And security analysis against UOV families (i.e., UOV and its variants) are typically categorized into key-recovery attacks and forgery attacks, with the XL algorithm serving as one of the most significant methods for mounting key-recovery attacks. Recently, Lars Ran introduced a novel key-recovery attack against UOV families that could be seen as an XL attack using exterior algebra; nevertheless, this new XL attack is applicable only when the underlying (finite) field of UOV instances is of characteristic $2$. In this work, we address this limitation by generalizing Lars Ran's approach, and our contributions are three-fold. First, we generalize the notion of exterior algebra and propose the notion of reduced symmetric algebra over any field, which is essentially symmetric algebra when the characteristic $p$ of the underlying field is $0$ and is exterior algebra when $p=2$. Moreover, based upon the reduced symmetric algebra, we propose a new XL attack against all UOV families: as a generalization of Lars Ran's attack, our XL attack also works for those UOV instances with odd characteristic; for instance, it works for those $12$ recommended QR-UOV instances submitted to NIST's PQC Standardization Project, although its performance does not outperform those of the existing key-recovery attacks. Finally, analysis on our XL attack reveals the connection between the characteristic $p$ and the concrete hardness of UOV instances.
Last updated:  2026-07-29
Fine-Grained and Runtime-Configurable Precision for Exact FHE Inference
Wun-Ting Lin and Ja-Ling Wu
Privacy-preserving machine learning under fully homomorphic encryption (FHE) faces a structural limitation: numerical precision is bound to cryptographic parameters and key material, forcing precision to be fixed at scheme initialization. Existing frameworks must regenerate keys or recompile circuits whenever bit-width changes, eliminating precision as a deployment-time performance knob and making mixed-precision strategies - widely used in plaintext machine learning - impractical under encryption. We present $\mathtt{Tailor}$, a backend-agnostic framework for exact, runtime-configurable mixed-precision neural inference over bitwise FHE. By representing signed integers as vectors of independently encrypted bits and constructing all arithmetic and neural-network operators from precision-parametric Boolean circuits, $\mathtt{Tailor}$ decouples bit-width from cryptographic state. Per-layer precision becomes a runtime parameter under a single keygen, and nonlinear operators, including ReLU, absolute value, and comparisons, are evaluated exactly rather than via polynomial approximation. A fused saturating requantize - ReLU produces compact unsigned activations, and each accumulator is provisioned at its provably minimal width. A $\mathtt{Scheme<Backend>}$ abstraction makes the framework portable across bitwise FHE families; we instantiate it for both TFHE and FINAL, along with a plaintext reference backend for functional validation and exact gate accounting. Our evaluation of an MNIST classifier shows that mixed-precision configurations strictly Pareto-dominate uniform deployment. Reducing only the output-layer weights to 2 bits while keeping inputs, activations, and hidden-layer weights at 4 bits yields the highest accuracy among all evaluated settings, 96.44% in 222.0s. This is both more accurate and faster than uniform 4-bit inference (96.17% in 236.1s) and $2.8\times$ faster than uniform 8-bit (96.14% in 632.4s). Reducing the hidden-layer weights to 2 bits instead trades 0.4 accuracy points for a $1.5\times$ speedup over uniform 4-bit (95.80% in 158.2s).
Last updated:  2026-07-29
Algorithms for Sparse LWE and LPN with Small Secrets
Shashwat Agrawal, Amitabha Bagchi, and Rajendra Kumar
We present new sample-runtime tradeoffs for the decisional sparse Learning With Errors (LWE) and sparse Learning Parity with Noise (LPN) problems over $\mathbb{Z}_q$, specifically in regimes where the secret vector is constrained by a small $l_{\infty}$ norm. While small-secret constraints are useful for the practical efficiency of lattice-based cryptography—such as homomorphic encryption and zero-knowledge proofs—the extent to which an adversary can exploit these bounds when the coefficient matrix is sparse is an open question. We address this by reducing the distinguishing task to a relaxed variant of the Short Integer Solution (SIS) problem, where the strict $A^\text{T} \mathbf{c} = 0$ requirement is replaced with an $l_1$-norm bound on $A^\text{T} \mathbf{c}$. To solve this relaxed SIS problem, we design an algorithm that samples distinct, non-trivial walks on a Kikuchi graph having close end points. For LWE, this approach directly separates planted from random instances. For LPN, where the noise is uniformly distributed over non-zero elements, the proof is more involved. We first derive a different reduction from LPN to (relaxed) SIS and then extend the anti-concentration framework given by Gupta, He, O'Donnell, and Singer (SODA 2026).
Last updated:  2026-07-29
The Cross-ratio Property and Its Use for Cryptanalysis of Round-reduced AES
Zhenzhen Bao, Jian Guo, Eik List, and Haoyang Wang
In this work, we propose three techniques for advancing cryptanalysis of round-reduced AES, two of which exploit the multiplicative inverse, and a third, structural, property that generalizes the S-box switch to multiple quartets. Firstly, we formalize the cross-ratio property for tracing a nonlinear equation over $F_{2^8}$ from the differences of four distinct inputs or their respective outputs through the key-wrapped multiplicative inverse. While the underlying properties of the multiplicative inverse have been well-studied, their usefulness for non-algebraic attacks has surprisingly remained unexamined. We demonstrate that it allows a more efficient matching between the sets of many related texts in a Demirci-Selçuk Meet-in-the-middle attack, leading to reductions in time and memory of both the online and offline phases for the seminal seven-round AES-128 by Derbez et al. from Eurocrypt 2013. Secondly, we show that the cross-ratio property gives rise to a relevant special case: when its inputs to the multiplicative inverse span a two-dimensional space, one can almost always recover the input differences of a quartet from only their output differences, or, in an alternative formulation, even the key applied before the outputs. We show how this can lead to new reduced-data three-round distinguishers. Thirdly, we define the mixture-quartet switch, an event that a mixture plaintext structure of 16 texts allows a partitioning into four quartets that all produce a related difference after two rounds. While most recent advances of the analysis of AES had focused on structural properties, we can trace partially active diagonals through a Super-S-box. Thus, by combining structural and algebraic properties, we describe a new distinguisher on four AES rounds with lower data complexity. Our applications do not threaten the security of the full AES, but advance the understanding of the building blocks of the AES further, and are likely applicable to similar settings and ciphers.
Last updated:  2026-07-29
Threshold FHE with Short Decryption Shares without a Semi-trusted Server
Hiroki Okada and Tsuyoshi Takagi
Threshold fully homomorphic encryption (ThFHE) enables decryption by collecting decryption shares from any T-out-of-N parties. A major drawback of previous ThFHE schemes is that they require a super-polynomial modulus (or are subject to other limitations), resulting in long ciphertexts, keys, and decryption shares. Passel`egue and Stehl´e (Asiacrypt 2024) proposed a ThFHE scheme in which a semi-trusted server rounds the input ciphertexts to produce polynomially short ciphertexts and sends them to the parties, thereby making the rest of the decryption process efficient. Although the input ciphertexts are still super-polynomially large, the communication cost of sending them from the parties to the server can be reduced to polynomial size via the transciphering technique; as a result, an entirely low-communication ThFHE is achieved. However, if even a single party colludes with the server (contrary to the assumption), the secret key can be efficiently recovered. Such a risky scenario would be unsuitable for practical deployment. In this paper, we tackle this issue. We propose two serverless ThFHE schemes with polynomially short decryption shares. The core idea is to let the parties directly round the decryption shares, rather than rely on the semi-trusted server to round the ciphertexts. We can also achieve low-communication ThFHE by reducing the communication required to send input ciphertexts to the parties to polynomial size via transciphering. Our first scheme, based on binary coefficient linear secret sharing ({0,1}-LSS), strictly improves upon Boneh et al. (CRYPTO 2018), achieving short decryption shares without any trade-offs. Our second scheme, based on Shamir secret sharing, adapts the technique of Okada and Takagi (Asiacrypt 2025) to eliminate the $O(N^{4.3})$ overhead in share size of our first scheme, further reducing communication costs.
Last updated:  2026-07-28
ELLMo: Packing- and Depth-Aware Encrypted Transformer Inference
Seyda Nur Guzelhan, Lohit Daksha, Carlos Agulló Domingo, Gilbert Jonatan, John Kim, Jose L. Abellan, David Kaeli, and Ajay Joshi
Cloud-based Large Language Model (LLM) inference processes sensitive user inputs, yet current deployments offer limited confidentiality guarantees. Fully Homomorphic Encryption (FHE) can provide strong privacy, but it clashes with transformer architectures, where rigid ciphertext packing demands expensive rotations, and deep polynomial circuits for nonlinearities necessitate costly bootstrapping. Although recent work has reported promising speed-ups, maintaining model accuracy is a challenge. We address these issues with ELLMo, a packing- and depth-aware encrypted transformer design. ELLMo introduces a novel matrix multiplication algorithm to reduce the ciphertext rotations. Further, head-split and merge steps are fused into this new algorithm at no additional cost. To reduce the depth of nonlinear layers, our contributions, Statistical-max Softmax and DelayNorm, help bypass deep comparison trees and homomorphic divisions to reduce bootstrapping by up to 46%. On encrypted BERT-Tiny, ELLMo achieves a $1.4\times$ speedup over state-of-the-art baselines with 0-1.5% accuracy loss across SST-2, MRPC, and RTE downstream tasks.
Last updated:  2026-07-28
Efficient Single-Round Obfuscation of Search and Result Patterns in Searchable Encryption
Tung Le and Thang Hoang
Searchable Symmetric Encryption (SSE) enables data owners to securely store encrypted data on untrusted cloud servers while retaining the ability to perform secure searches and retrieve relevant documents. However, standard SSE schemes expose search patterns (whether two queries are identical), and result patterns (which documents are returned), making them susceptible to leakage-abuse attacks that can infer sensitive information such as the queried keywords and/or document contents. While Oblivious RAM (ORAM) and Private Information Retrieval (PIR) can hide these patterns, their high computation and communication overhead often render them impractical for real-world search workloads. A more efficient alternative is to obfuscate search and result patterns using Differential Privacy (DP). Unfortunately, existing DP-based SSE schemes either provide insufficient query privacy protection, or still incur substantial performance overhead. In this paper, we propose FROST, a novel differentially private SSE scheme that efficiently obfuscates both search and result patterns, while providing strong resilience against all known statistical leakage-abuse attacks. The core component of FROST is our new rerandomized PIR (RePIR) scheme designed for private databases, which allows server-side rerandomization of encrypted PIR query responses. In FROST, we also introduce a novel method for applying DP noises to SSE for search result obfuscation using only simple arithmetic operations. An important property of FROST is that it requires only a single round of communication, with small user-side storage as an additional benefit. We fully implemented FROST and conducted extensive experiments over real-world datasets to rigorously assess its practical performance and resilience. Our experiments showed that FROST not only effectively mitigates pattern-leakage attacks while maintaining reasonable utility, but also achieves up to four orders of magnitude faster keyword search and three orders of magnitude lower bandwidth overhead than prior DP-based SSE schemes.
Last updated:  2026-07-28
Zero-Knowledge Proofs of Isogeny Diamonds
Leonardo Colò, Maher Mamah, Youcef Mokrani, Bruno Sterner, and Nicolas Swanson
Commutative diagrams of isogenies between supersingular elliptic curves, which are called isogeny diamonds, have become fundamental to isogeny-based cryptography for both constructive and cryptanalytic purposes. In parallel, proofs of knowledge of isogenies have been widely studied and have found many applications. In this work, we combine these two directions and introduce zero-knowledge proofs of isogeny diamonds, namely, we prove knowledge of isogenies that form a commutative diagram between four curves. We present four constructions that work in various settings. The first, Windmill-ZKP assumes that the prover knows only two parallel isogenies in the diamond. The second, Cube-ZKP assumes the prover has knowledge of four of specified degree isogenies. Finally, Kube-ZKP and Kani-ZKP prove knowledge of isogeny diamonds whose degree sum is smooth. We also provide proof-of-concept implementations of the proposed constructions and compare their performance. Our results demonstrate the trade-offs between security, efficiency and compactness in these constructions.
Last updated:  2026-07-28
Unclonable Cryptography in Linear Quantum Memory
Omri Shmueli and Mark Zhandry
Quantum cryptography is a rapidly-developing area which leverages quantum information to accomplish classically-impossible tasks. In many of these protocols, quantum states are used as long-term cryptographic keys. Typically, this is to ensure the keys cannot be copied by an adversary, owing to the quantum no-cloning theorem. Unfortunately, due to quantum state's tendency to decohere, persistent quantum memory will likely be one of the most challenging resources for quantum computers. As such, it will be important to minimize persistent memory in quantum protocols. In this work, we consider the case of one-shot signatures (OSS), and more general quantum signing tokens. These are important unclonable primitives, where quantum signing keys allow for signing a single message but not two. Naturally, these quantum signing keys would require storage in long-term quantum memory. Very recently, the first OSS was constructed in a classical oracle model and also in the standard model, but we observe that the quantum memory required for these protocols is quite large. In this work, we significantly decrease the quantum secret key size, in some cases achieving asymptotically optimal size. To do so, we develop novel techniques for proving the security of cryptosystems using coset states, which are one of the main tools used in unclonable cryptography.
Last updated:  2026-07-28
SoK: Confidential Transformer Inference and Retrieval-Augmented Generation
Timofey Yaluhin
Running Transformer inference and retrieval-augmented generation (RAG) over confidential data forces a choice: either expose prompts and documents to a cloud operator, or keep the data on-premises, which confines the deployment to weaker self-hosted models. Existing defenses span five mechanism families: secure computation (MPC and FHE), trusted execution environments (TEEs), static obfuscation, differential privacy, and hybrid TEE-and-obfuscation splits. No prior systematization compares them on a common footing of mechanism, threat model, and deployment cost, and none covers the RAG retrieval layer. We organize the field by deployment readiness: the likelihood a scheme is adopted in practice, scored on performance, utility, and threat-model fit. The scoring spans inference and RAG retrieval, both dense and graph. We find that no family dominates: each attains at most two of the three criteria, and which one it sacrifices is fixed by its security basis, so the deployable choice is set by the constraint an application can least afford to relax. Even trusted hardware is no exception, since every surveyed scheme ignores the side channels to which it is most exposed. We further surface hidden deployment costs, such as client reliance and a custom serving path, identify private graph-RAG as the least-served setting, and find that no design yet keeps a pipeline confidential from query to answer.
Last updated:  2026-07-28
Efficient Private Filtering and Aggregation for Weighted Set Intersection via Oblivious Encrypted Weight Transfer
Xiaodong Wang, Shengzhe Meng, Zijie Lu, and Bei Liang
Private Set Intersection (PSI) enables parties to compute the intersection of their input item sets while preserving privacy. In many real-world applications, however, each item is accompanied by a sensitive weight, and the ability to privately compute over such weights is crucial. Existing research in this direction is fragmented and driven by application-specific goals, with representative examples including PI-Sum (computing the sum of weights over the intersection), inner-product Private Join and Compute (computing the inner product of weight vectors over the intersection), and Item with Maximum Weight Sum (identifying the intersection item with the maximum combined weight). In this work, we propose a unified framework for private computation on weighted set intersection. We formalize \textit{Private Filtering and Aggregation for Weighted Set Intersection} (PFA-WSI) as an ideal functionality parameterized by a joint scoring function $f$ and a predicate $P$, supporting two output modes: (i) \emph{predicate-filtered output}, which reveals a predicate-selected subset of intersection items, and (ii) \emph{aggregated output}, which reveals only aggregate statistics over matched items. By instantiating $f$ and $P$ appropriately, PFA-WSI captures deployed and studied tasks such as PI-Sum, inner-product PJC, and IMWS, and also accommodates richer metrics arising in practice, such as $L_1$- and $L_2$-type distance statistics on matched item weights. To realize PFA-WSI efficiently, we introduce a novel core building block, Oblivious Encrypted Weight Transfer (OEWT), which enables a receiver to obtain encryptions of the sender's weights for intersection items and random-looking ciphertexts otherwise. Building on OEWT and additively homomorphic encryption, we present modular protocol constructions for different instantiations of $f$ and for both output modes. We prove simulation-based security in the semi-honest model and provide detailed communication and computation analyses. Our experiments show that our constructions scale to million-sized sets with practical performance that matches or surpasses the state-of-the-art.
Last updated:  2026-07-28
Refined Humbert Invariants in Supersingular Isogeny Degree Analysis
Eda Kırımlı and Gaurish Korpal
We focus on refined Humbert invariants of principally polarized superspecial abelian surfaces, introduced by Kani in 1994. The main contributions are to enumerate principal polarizations on a superspecial surface, and for each polarization, to compute the refined Humbert invariant of a principally polarized superspecial abelian surface. Then, we present several applications of computing this invariant for isogeny-based cryptography. First, we provide a decision algorithm to check if two given polarizations are isomorphic. Second, we present an efficient algorithm to determine the geometric type of a principally polarized superspecial surface. Third, we prove an upper bound on the largest minimal isogeny degree among pairs of supersingular elliptic curves, independent of their endomorphism-ring structures, and our experimental evidence verifies this claim up to $p=659$, $p\equiv 11\pmod{12}$. Fourth, we present experimental evidence for a minimum isogeny frequency within the proven upper bounds. Lastly, we provide a different perspective on the fixed isogeny degree problem using refined Humbert invariants and analyze it without explicit endomorphism rings.
Last updated:  2026-07-28
Homomorphic Signature-based Witness Encryption and Applications
Alireza Kavousi and István András Seres
Signature-based witness encryption (SWE) schemes recently emerged as a viable alternative to instantiate timed-release cryptography in the honest majority setting. In particular, assuming threshold trust in a set of parties that release signatures at a specified time, one can ``encrypt to the future'' using an SWE scheme. It offers stateless decryption, where parties producing the signatures do not need to know the ciphertexts in advance to perform decryption. This statelessness makes SWE vastly superior to regular threshold encryption for decentralized blockchain applications such as sealed-bid auctions and voting. However, the lack of homomorphism in existing SWE schemes severely bottlenecks their throughput and limits their deployment. In this work, we formally introduce Homomorphic SWE (HSWE) to resolve these limitations. We present a systematic suite of HSWE constructions designed to scale across varying message spaces without sacrificing statelessness. We first establish foundational HSWE schemes for binary messages using Cocks IBE and standard Learning With Errors (LWE). To support polynomially-sized message spaces, we construct a pairing-based scheme that features an efficient multi-pairing optimization for cross-tag aggregation. For exponentially large message spaces, we transition to a Ring-LWE construction that achieves high-throughput polynomial packing with post-quantum security. Moreover, we address the inherent privacy limitation of public stateless aggregation by proposing a framework that perfectly hides individual plaintexts and only reveals the final aggregated result. We also present an empirical performance evaluation in Rust to highlight the impact of homomorphism in practical deployments.
Last updated:  2026-07-28
Advanced cryptography from lattice isomorphism—new constructions of IBE and FHE
Huck Bennett, Zhengnan Lai, and Noah Stephens-Davidowitz
We show how to translate some of the more advanced techniques used in LWE-based cryptography to the setting of lattice-isomorphism-based cryptography, which was recently introduced by Ducas and van Woerden [Eurocrypt, 2022]. In particular, we show constructions of two powerful cryptographic primitives, identity-based encryption (IBE) and leveled fully homomorphic encryption (FHE). We then prove their security under the assumption that a suitable version of the Lattice Isomorphism Problem is hard. Our constructions use quite general and modular techniques, and we expect them to have other applications. Specifically, we show that the now-ubiquitous techniques introduced by Gentry, Peikert, and Vaikuntanathan [STOC, 2008] to build IBE and Gentry, Sahai, and Waters [Crypto, 2013] to build FHE can be made to work in our setting using any sufficiently ``nice'' lattice.
Last updated:  2026-07-28
Lattice-Based Shuffle Arguments using Subset Checking
Behzad Abdolmaleki, Prastudy Fauzi, Jiaqi Gu, Toomas Krips, and Nahid Roustaeifar
Shuffle arguments are a fundamental building block in mix-nets and related privacy-preserving systems, where they are used to prove that a set of ciphertexts or commitments is a permutation and rerandomization of another set without changing the underlying messages. Existing communication-efficient shuffle arguments rely on classical assumptions, whereas known lattice-based constructions are still significantly less efficient. In this paper, we present a lattice-based shuffle argument with short proofs by using the subset-checking approach of Abdolmaleki et al. (SCN 2024) in the lattice setting. Our main construction proves correct shuffles of Ajtai commitments and is built on the ABDLOP commitments and lattice-based zero-knowledge framework of Lyubashevsky et al. (Crypto 2022). The protocol is secure under the Module-SIS and Module-LWE assumptions in the random oracle model. A key technical ingredient is a rerandomization method for the derived commitment key, which restores the distributional properties needed for soundness even when the input commitments may depend on the prover. We further extend our approach to obtain shuffle arguments for ciphertexts and public keys, yielding applications to lattice-based mix-nets and single secret leader election. Finally, we implement our construction and compare it with prior lattice-based shuffle protocols, obtaining substantial improvements in communication, proving time, and verification time.
Last updated:  2026-07-27
Falcon Verify on AVX-512: Speed Records
David Rubin and Emanuele Cesena
We present a fast implementation of Falcon (FN-DSA) signature verification with AVX-512. On a modern AMD Zen5 core, it completes a Falcon-512 verification in 3.6 microseconds, 2.6 times faster than an already optimized baseline, with comparable gains on Zen4, and consistent results across clang 21 and gcc 15. The speedup comes from rewriting the Number-Theoretic Transform (NTT) and from vectorising all other stages of the verification algorithm. The novelty is to use a 32-bit Barrett-style representation, instead of the reference 16-bit Montgomery, and adopt Shoup-Harvey precomputed multipliers for twiddle reduction. With all optimizations applied, hash-to-point (and specifically Keccak) is the dominant cost. We therefore propose a non-standard Falcon variant that replaces SHAKE256 with KTP256, an XOF based on KangarooTwelve with parallel squeeze. It cuts verification to 2.2 microseconds on Zen5, yielding 4.2 times over the baseline, and is of independent interest for any post-quantum scheme that uses a Keccak sponge to sample large amounts of data from a fixed seed. All code is open source.
Last updated:  2026-07-27
An Attack on High Rate McEliece Cryptosystems Using Generalized Reed Solomon Codes with Weight 2 Mask
Julia Lieb, Abhinaba Mazumder, and Michael Schaller
Due to the insecurity of McEliece cryptosystems instantiated with Generalized Reed-Solomon codes, there have been several proposals of McEliece type systems that replace the permutation matrix by a matrix $M$ with larger row and column weight. In many of them, the secret key is still a GRS code. There have been successful attacks on some of those schemes with row and column weight between $1$ and $1 + R$, where $R$ is the rate of the code. The case of weight two and larger has been left open in these works. Subsequently, several authors proposed schemes with weight exactly two and with even higher weight. We provide distinguishers for the public codes appearing in these cryptosystems in the high rate regime. In addition, we give a framework to turn a good enough distinguisher into a key-recovery attack. In the case where the matrix $M$ has row and column weight $2$, we can successfully attack the scheme in the high rate regime using a cube code distinguisher.
Last updated:  2026-07-27
Anamorphic Monero Transactions: the Threat of Bypassing Anti-Money Laundering Laws
Adrian Cinal, Przemysław Kubiak, Mirosław Kutyłowski, and Gabriel Wechta
In this paper, we analyze the clash between privacy-oriented cryptocurrencies and emerging legal frameworks for combating financial crime, focusing in particular on the recent European Union regulations. We analyze Monero, a leading "privacy coin" and a major point of concern for law enforcement, and study the scope of due diligence that must be exercised under the new law with regard to Monero trading platforms and how it translates to the technical capabilities of the Monero protocol. We both recognize flaws in the legislation and identify technical pitfalls threatening either the effective compliance of, say, Monero exchanges or the anonymity endeavour of Monero itself. Of independent interest is that we turn to anamorphic cryptography (marking one of the first practical applications of the concept) and leverage it to build a hidden transaction layer embedded in the Monero blockchain that obfuscates illegal money flow and circumvents transaction-level attempts at enforcing the EU law.
Last updated:  2026-07-27
Cryptanalytic Properties of Mealy Machines
Zhongfeng Niu, Tim Beyne, Kai Hu, and Meiqin Wang
This paper proposes a systematic approach to compute cryptanalytic properties of arbitrary Mealy machines or S-functions. Based on the geometric approach to cryptanalysis, we provide a uniform formula for any cryptanalytic property of such a function, as long as the property is compatible with the way its input and output are split into chunks. Examples include linear, (quasi) differential, (ultrametric) integral, differential-linear, and boomerang properties. To illustrate our results, we compute these properties for several important examples, including modular additions, the Chi- and ChiChi-functions, and the SHA-1 step function. As proof-of-concept applications, we construct a boomerang distinguisher for the Subterranean permutation, and show how to compute the correlations of conditional linear approximations in partitioning-based differential-linear attacks more accurately. Our results also lead to a new approach to compute the algebraic normal form of the inverse of the Chi-function.
Last updated:  2026-07-27
Practical Zero-Trust Threshold Signatures in Large-Scale Asynchronous Networks
Offir Friedman, Avichai Marmor, Dolev Mutzari, Yehonatan Cohen Scaly, and Yuval Spiizer
Threshold signatures are a fundamental primitive in applied cryptography, primarily used to mitigate the custodial risk involved in managing keys. However, existing constructions rely on synchronous communication assumptions and fixed participant sets, limiting their applicability to real-world networks. In addition, as the committees managing those keys serve an ever-growing number of clients and assets, they become lucrative targets for attacks. This issue is often called the Honeypot Problem. A recent work proposed the 2PC-MPC paradigm, in which a client and a decentralized network jointly generate signatures, aiming to mitigate this issue. In this work, we present the first asynchronous 2PC-MPC protocol for ECDSA signatures, designed to operate over reliable broadcast channels as implemented in modern blockchains. Our protocol tolerates dynamic, post-determined quorums whose participants may change between rounds. This allows the protocol to align with asynchronous consensus layers while providing identifiable abort, public verifiability, guaranteed output delivery (assuming completeness of the broadcast channel) and censorship resistance for the client. We introduce global presigns, which are generated autonomously by the network and remain client-agnostic until signing. This enables effective background preprocessing, and results in sub-second online signing network-side latency for dozens of concurrent clients. From a technical perspective, our asynchronous design eliminates commitment rounds, yielding one-round client interaction for both key generation and signing. We also remove the need for zero-knowledge proofs toward the client. This results in a client complexity independent of network size, without proof aggregation (which is particularly challenging over asynchronous channels). Our constructions are proven UC-secure in the asynchronous setting. To achieve concrete security over 256-bit elliptic curves, we introduce the Slightly-Enhanced ECDSA Unforgeability assumption and provide a tight reduction in the EC-GGM model. Beyond theoretical analysis, we implement our protocols and evaluate them in both a local benchmark and a live permissionless deployment with dozens of validators, demonstrating practical performance and robustness under heterogeneous execution speeds.
Last updated:  2026-07-27
Validity in Responsive Byzantine Agreement
Diana Ghinea, Simon Holmgaard Kamp, and Chen-Da Liu-Zhang
Byzantine Agreement (BA) protocols must ensure not only agreement and termination, but also validity: the value agreed upon should meaningfully reflect the honest parties' inputs. The choice of validity condition can change the exact resilience threshold at which BA is solvable. Tight characterizations for BA with general validity conditions are known in the partially synchronous model (PODC'23), in the synchronous model (PODC'24), and in the network-agnostic model (DISC'25). We focus on general validity for synchronous BA with responsive termination. Such protocols remain secure against up to $t_s$ byzantine corruptions, but incur a running time that depends on the actual network delay $\delta$, rather than the conservative delay bound $\Delta \gg \delta$, whenever at most $t_r \leq t_s$ parties are corrupted. We present a tight characterization of the validity properties solvable in this setting. We prove that every non-trivial validity property requires $n>2 t_r+t_s$ in authenticated settings, where a public-key infrastructure and digital signatures are available, and $n>3 t_s$ in unauthenticated settings. These threshold conditions are accompanied by a validity-dependent requirement, the responsive similarity condition: roughly, for any concrete configuration of honest inputs, there is a value that is valid for any view that a protocol could obtain from this initial configuration. We then present matching protocols in both settings, showing that these conditions are sufficient. The main technical contribution is an authenticated responsive Core-Set Agreement protocol requiring $n>2 t_r+t_s$. This threshold may place the protocol in an honest-minority regime, where prior constructions for general validity do not apply and where standard Synchronous Broadcast is not responsive. Finally, we instantiate the characterization for several standard validity notions -- weak validity, strong unanimity, convex validity, and honest-input validity.
Last updated:  2026-07-27
Privacy-Preserving Identity Management and Software Bill of Materials Vulnerability Detection: Practical Use Cases from the PRIVIDEMA Project
Mariya Georgieva Belorgey, Benoit Cogliati, Simon Demarty, Lois Huguenin-Dumittan, Özcan Öztürk, Salma Rasti Samiei, and Oana Stan
PRIVIDEMA project (Privacy-Preserving Identity Management for Digital Wallets and Secure Data Sharing and Processing for Cyber Threat Intelligence Data) advances the state of the art in cryptographic and Privacy-Enhancing Technologies (PETs) to enable secure, interoperable, and trustworthy data exchange across sectors, with a focus on the domains of Cyber Threat Intelligence and Digital Identity Management. This paper presents two representative real-world use-cases: (1) privacy-preserving digital identity management based on the European Digital Identity (EUDI) Wallet, and (2) privacy-preserving Cyber Threat Intelligence (CTI) sharing for Software Bill of Materials (SBOMs) and vulnerability datasets. Both use cases showcase how advanced PETs, including Fully Homomorphic Encryption (FHE), Federated Learning (FL), and Differential Privacy (DP), can be composed to protect sensitive data throughout its lifecycle while maintaining analytical and operational utility. Together, these use cases chart a practical course toward more scalable, standards-compliant, and privacy-preserving data ecosystems that align with Europe’s vision for secure and trustworthy digital services.
Last updated:  2026-07-27
Lether: Practical Post-Quantum Account-Based Private Blockchain Payments
Hongxiao Wang, Muhammed F. Esgin, Ron Steinfeld, and Siu-Ming Yiu
We introduce Lether, the first practical account-based private block-chain payment protocol based on post-quantum lattice assumptions, following the paradigm of Anonymous Zether (FC '19, IEEE S&P '21). The main challenge in building such a protocol from lattices lies in the absence of core building blocks: unbounded-level additively-homomorphic multi-message multi-recipient public key encryption (mmPKE), and event-oriented linkable ring signatures with support for multiple tags (events). To address these issues, we propose a verifiable refreshable additively-homomorphic mmPKE scheme and a plug-and-play event-oriented linkable tag scheme from lattices. We believe both to be of independent interest To achieve unbounded-level homomorphic evaluation in the lattice-based setting without relying on heavy techniques such as bootstrapping or large moduli (e.g., over 60 bits) in fully homomorphic encryption (FHE), we introduce a simple yet blockchain-friendly mechanism called refresh. Namely, each user is required to verifiably refresh their account after a certain number of transactions. With our tailored parameter settings, the amortized per-refresh costs of communication and computation are only about 1.3% and 1.5%, respectively, of the cost of a transaction. We also optimize the implementations of LNP22 lattice-based zero-knowledge proof system (Crypto '22) in the LaZer library (CCS ’24), to support efficient batching of various proof components.Overall, for a typical transaction, the total communication cost becomes about 68 KB, with the associated zero-knowledge proof accounting for about 51 KB of this total. Each of proof generation and verification take a fraction of a second on a standard PC. As an additional contribution, we formalize new definitions for Anonymous Zether-like protocols that more accurately capture real-world blockchain settings. These definitions are generic and are expected to benefit the broader development of account-based private blockchain payment protocols, beyond just lattice settings.
Last updated:  2026-07-27
ViNET: Connecting the Unconnected using Video over LTE
Manav Mittal, Yogesh Kaushik, Anirudh S Kumar, Mukulika Maity, and Sambuddho Chakravarty
Internet shutdowns are used authoritarian regimes to suppress communication that end up crippling essential Internet-driven services, besides the obvious silencing of dissent. Traditional tools like VPNs and Tor, dependent on active Internet connections, falter during these blackouts. Earlier solutions, such as Dolphin, delivered meagre bandwidth and weak privacy safeguards, exposing a glaring weakness in the battle against digital oppression. ViNET, a system that cleverly repurposes Video over LTE (ViLTE) calls, often operational during shutdowns, into a stealthy conduit for real-time Internet access. By ingeniously embedding network traffic in ViLTE packets, ViNET achieves robust 60 to 400 Kbps transmission rates, matching 2G speeds and surpassing previous solutions like Dolphin by 1500x–4000x, while ensuring end-to-end TLSbased confidentiality and integrity. This performance enables text-based web browsing with page loads in seconds to minutes, 1 MByte file downloads in ≈30s, and seamless messaging over Telegram. ViNET also outsmarts machine learning-based traffic classifiers, achieving a remarkable false positive rate, at times as high as 40%, when attempting to detect ViNET using SOTA models. With such standout metrics, ViNET emerges as a formidable ally, offering a performant, reliable and privacy-first lifeline, in the face of Internet shutdowns.
Last updated:  2026-07-27
RoK and Roll – Verifier-Efficient Random Projection for $\tilde{O}(\lambda)$-size Lattice Arguments
Michael Klooß, Russell W. F. Lai, Ngoc Khanh Nguyen, and Michał Osadnik
Succinct non-interactive arguments of knowledge (SNARKs) based on lattice assumptions offer a promising post-quantum alternative to pairing-based systems, but have until now suffered from inherently quadratic proof sizes in the security parameter. We introduce RoK and Roll, the first lattice-based SNARK that breaks the quadratic barrier, achieving communication complexity of $\tilde{O}(\lambda)$ together with a succinct verification time. The protocol significantly improves upon the state of the art of fully-succinct argument systems established by ``RoK, Paper, SISsors'' (RPS) [ASIACRYPT'24] and hinges on two key innovations, presented as reductions of knowledge (RoKs): - Structured random projections: We introduce a new technique for structured random projections that allows us to reduce the witness dimensions while approximately preserving its $\ell_2$ norm and maintaining the desired tensor structure. In order to maintain succinct communication and verification, the projected image is further committed and adjoined to the original relation. This procedure is recursively repeated until dimension of the intermediate witness becomes $\mathsf{poly}(\lambda)$, i.e. independent of the original witness length. - Unstructured random projection: When the witness is sufficiently small, we let the unstructured projection (over coefficients $\mathbb{Z}_q$) be sent in plain, as in LaBRADOR [CRYPTO'23]. We observe, however, that the strategy from prior works to immediately lift the projection claim to $\mathcal{R}_q$, and into our relation, would impose a quadratic communication cost. Instead, we gradually batch-and-lift the projection a the tower of intermediate ring extensions. This reduces the communication cost to $\tilde{O}(\lambda)$ while maintaining a succinct verification time. These two techniques, combined with existing RoKs from RPS, yield a succinct argument system with communication complexity $\tilde{O}(\lambda)$ and succinct verification for structured linear relations.
Last updated:  2026-07-27
An analysis of a weakened version of PRISM
Jolijn Cottaar, Steven D. Galbraith, Luciano Maino, and Monika Trimoska
PRISM (PKC25) is a hash-and-sign signature scheme whose security relies on the hardness of computing large-prime-degree isogenies originating from a curve of unknown endomorphism ring. In PRISM, the degree of such isogenies is obtained by hashing messages onto a set of large odd integers that pass a primality test. In this work, we investigate the impact of the choice of primality test on the security of PRISM. We first show that when a weak primality test is used, the assumption underlying the security proof in the standard model does not hold. We then extend our analysis to the assumption used in the security proof in the (quantum) random oracle model. In this setting, we argue that the Miller-Rabin test suffices and estimate the minimal number of iterations required for PRISM to achieve the desired security level, thus minimising signing costs.
Last updated:  2026-07-27
Limits on the Power of Private Constrained PRFs
Mengda Bi, Chenxin Dai, and Yaohua Ma
Private constrained PRFs are constrained PRFs where the constrained key hides information about the predicate circuit. Although there are many constructions and applications of PCPRF, its relationship to basic cryptographic primitives, such as one-way functions and public-key encryptions, has been unclear. For example, we don't know whether one-way functions imply PCPRFs for general predicates, nor do we know whether 1-key secure PCPRF for all polynomial-sized predicates imply public-key primitives such as public-key encryption and secret-key agreement. In this work, we prove the black-box separation between a 1-key secure PCPRF for any predicate and a secret-key agreement, which is the first black-box separation result about PCPRF. Specifically, we prove that there exists an oracle relative to which 1-key secure PCPRFs exist while secret-key agreement does not. Our proof is based on the simulation-based technique proposed by Impagliazzo and Rudich (STOC 89). The main technical challenge in generalizing the simulation-based technique to PCPRF is the issue of \textit{unfaithfulness} of Eve's simulation to the real world because our oracle is more complicated than a random oracle. We introduce a new technique which we call the ``weighting" technique and show how to leverage it to circumvent the issue of unfaithfulness in the proof framework of Impagliazzo and Rudich.
Last updated:  2026-07-27
MIFA: An MILP-based Framework for Improving Differential Fault Attacks
Hanbeom Shin, Insung Kim, Sunyeop Kim, Byoungjin Seok, Deukjo Hong, Jaechul Sung, Seokhie Hong, Sangjin Lee, and Dongjae Lee
At ASIACRYPT 2021, Baksi et al. introduced DEFAULT, a block cipher designed to algorithmically resist Differential Fault Attack (DFA), claiming 64-bit DFA security regardless of the number of injected faults. At EUROCRYPT 2022, Nageler et al. demonstrated that DEFAULT's claimed DFA resistance can be broken by applying an information-combining technique. More recently, at ASIACRYPT 2024, Jana et al. improved DFA by searching for differential trails with a single solution. They showed that, for DEFAULT with a simple key schedule, injecting five faults at the fifth-to-last round reduces the key space to one, and for BAKSHEESH, injecting twelve faults at the third-to-last round achieves the same result. In this paper, we propose a new DFA framework that utilizes a Mixed-Integer Linear Programming (MILP) solver. This framework makes it possible to attack deeper rounds than previously achieved, reducing the number of fault injections required for key recovery. Furthermore, we present a method to determine the most efficient fault injection bit positions by systematically analyzing the input differences from all possible single bit-flip faults, thereby further reducing the required number of faults. This systematic analysis has the significant advantage of allowing us to theoretically calculate the required number of faults. Applying our framework, for DEFAULT, injecting three faults at the sixth-to-last round and two faults at the seventh- and eighth-to-last rounds reduces the key space to one.
Last updated:  2026-07-26
Just-in-Time-OPRFs and a Modular Framework for Fast Private Set Intersection
Mihir Bellare, Rishabh Ranjan, and Doreen Riepel
This paper gives a modular and unified framework within which to derive fast protocols for Private Set Intersection (PSI). At the core of this is a new primitive, that we define, and that we call a Just-In-Time OPRF (JIT-OPRF). We show how to obtain PSI generically from any JIT-OPRF, and then how to obtain JIT-OPRFs from Oblivious Transfer (OT) and Vector Oblivious Linear Evaluation (VOLE). We recover as special cases PSI protocols in the literature based on these two assumptions. Our results and proofs throughout are concrete rather than asymptotic, with explicit bounds that allow one to determine security parameters to achieve a desired level (e.g.~128 bits) of proven security in practice. Our results show interesting differences in the concrete security of OT and VOLE based PSI. Beyond the practical contribution of concrete-security, our work adds conceptual simplicity to this area, and opens the door to new PSI protocols via the construction of new JIT-OPRFs.
Last updated:  2026-07-26
Toward a Secure Fixed-Point Implementation of the Falcon Signature Scheme
Daniel De Almeida Braga, Pierre-Alain Fouque, Bachir Lachguel, and Thomas Prest
Falcon was selected by NIST in 2022 for standardization as a post-quantum digital signature scheme. Among all standardized signature schemes, Falcon achieves the smallest signature size. Its main drawback, however, is its reliance on floating-point arithmetic, which plays a critical role in the security analysis. This reliance poses significant challenges for practical implementations: some platforms lack floating-point units, floating-point division is not constant time on many processors, and protecting floating-point computations against side-channel attacks using masking techniques is particularly difficult on embedded devices. To address portability issues, Pornin (ePrint 2019/893) proposed an implementation of \falcon that emulates floating-point arithmetic using integer operations. While it enables deployment on a wider range of platforms, this approach incurs a substantial performance penalty compared to the native floating-point implementation. This work studies the theory and practice of implementing Falcon's signing procedure in fixed-point arithmetic. This requires a specific analysis of the boundedness and precision of intermediate variables. 1. Our boundedness analysis revolves around a key fact: almost every intermediate variable arising during key expansion and signing is bounded by a function of four quantities that can be computed at key generation time. Our modified key generation enforces thresholds on these quantities through a light rejection step that rejects less than 50% of initial Falcon keys. This then yields sharp, unconditional bounds on all fixed-point variables. Establishing these bounds is highly nontrivial, and relies on Gaussian concentration arguments as well as on symplectic pairs, a generalization of symplecticity. 2. Our precision analysis remains, for now, partly empirical. Following a Rényi divergence argument, our main theorem proves the security of fixed-point Falcon conditioned on error bounds of certain intermediate values. These error bounds are derived empirically based on extensive experiments. We provide a C fixed-point implementation. It is approximately a factor of two slower than the original floating-point \falcon implementation, but achieves a speedup of an order of magnitude compared to emulated floating-point implementations.
Last updated:  2026-07-26
Rich Input Representations in Neural Differential Cryptanalysis: A Taxonomy and Survey
Alireza Gholizadeh Shahrbejari and Reza Ebrahimi Atani
Neural differential distinguishers have become an active research direction in​ symmetric-key cryptanalysis since the introduction of deep-learning-based attacks on​ round-reduced SPECK. Early neural distinguishers typically used a single ciphertext pair​ or ciphertext difference as input. Recent studies, however, show that richer input​ representations can substantially affect the information available to the classifier, the data​ cost of each labeled sample, and the relevance of the distinguisher to practical attacks.​ Examples include multi-pair, multi-difference, matrix-style, multi-round,​ structured-encoding, and score-aggregation based inputs.​ This paper provides a taxonomy and survey of rich input representations in neural​ differential cryptanalysis. We introduce a representation-centric framework that describes​ an input representation by its difference set, number of observations per sample, sharing​ structure, encoding function, and ciphertext cost. Using this framework, we organize​ existing works into representation families and compare their motivations, benefits, and​ limitations. We also argue that representation-rich distinguishers require cost-aware​ evaluation: fixed-sample comparisons and fixed-ciphertext comparisons answer different​ questions and may lead to different conclusions. Finally, we identify open problems related​ to automated representation search, theoretical explanation of representation gain,​ cipher-family transferability, interpretability, reproducibility, and key-recovery integration.​ The survey highlights that rich input representations should be treated as first-class​ cryptanalytic design choices rather than secondary implementation details.
Last updated:  2026-07-26
Typing High-Speed Cryptography against Spectre v1
Basavesh Ammanaghatta Shivakumar, Gilles Barthe, Benjamin Grégoire, Vincent Laporte, Tiago Oliveira, Swarn Priya, Peter Schwabe, and Lucas Tabary-Maujean
The current gold standard of cryptographic software is to write efficient libraries with systematic protections against timing attacks. In order to meet this goal, cryptographic engineers increasingly use high-assurance cryptography tools. These tools guide programmers and provide rigorous guarantees that can be verified independently by library users. However, high-assurance tools reason about overly simple execution models that elide micro-architectural leakage. Thus, implementations validated by high-assurance cryptography tools remain potentially vulnerable to micro-architectural attacks such as Spectre or Meltdown. Moreover, proposed countermeasures are not used in practice due to performance overhead. We propose, analyze, implement and evaluate an approach for writing efficient cryptographic implementations that are protected against Spectre v1 attacks. Our approach ensures speculative constant-time, an information flow property which guarantees that programs are protected against Spectre v1. Speculative constant-time is enforced by means of a (value-dependent) information flow type system. The type system tracks security levels depending on whether execution is misspeculating. We implement our approach in the Jasmin framework for high assurance cryptography, and use it for protecting all implementations of an experimental cryptographic library that includes highly optimized implementations of symmetric primitives, of elliptic-curve cryptography, and of Kyber, a lattice-based KEM recently selected by NIST for standardization. The performance impact of our protections is very low; for example, less than 1% for Kyber and essentially zero for X25519.
Last updated:  2026-07-26
Improved Concurrent-Secure Blind Schnorr Signatures
Pierpaolo Della Monica and Ivan Visconti
Since the work of Chaum in ’82, the problem of designing secure blind signature protocols for existing signature schemes has been of great interest. In particular, when considering Schnorr signatures, nowadays used in Bitcoin, designing corresponding efficient and secure blind signature schemes is very challenging in light of the ROS attack (Eurocrypt’21), which affected all previous efficient constructions. Currently, the main positive result about concurrent-secure blind Schnorr signatures is the one of Fuchsbauer and Wolf (Eurocrypt’24). Their construction is quite demanding, indeed it requires trusted parameters, non-interactive zero-knowledge arguments and CPA-secure public-key encryption. Moreover, it is proven secure under a game-based definition only, is limited to computational blindness and is vulnerable to harvest now “link” later quantum attacks. Nicely, their construction is also a predicate blind signature (PBS) scheme, allowing signers to have some partial control on the content of the blindly signed message. In this work, we show neat improvements to the state-of-the-art presenting a new construction for concurrent-secure blind Schnorr signatures that relies on milder/reduced cryptographic assumptions, enjoys statistical blindness, replaces the problematic trusted setup with a non-programmable random oracle (NPRO), and satisfies also a one-sided simulation-based property providing deniability in PBSs.
Last updated:  2026-07-26
Round-Optimal GUC-Secure Blind Signatures from Minimal Computational and Setup Assumptions
Michele Ciampi, Pierpaolo Della Monica, and Ivan Visconti
A blind signature scheme is an interactive protocol that enables a user to obtain a signature on a message without revealing any information about the message–signature pair to the signer. Despite more than 40 years of research, all existing constructions suffer from at least two of the following limitations. 1. The protocol is not round-optimal, requiring more than two messages to be exchanged during the signature phase. 2. There is only game-based security and/or lack of composability with global and observable setup (i.e., there is a need for trusted parameters or to program random oracles). 3. Security (unlike regular signatures) is based on demanding hardness assumptions, especially when considering quantum attacks. In this work, we show how to blindly sign a message, simultaneously overcoming all of the above three limitations. Specifically, we construct a Universally Composable (UC), two-round (optimal) blind signature protocol that relies only on one-way functions (optimal), without trusted parameters. The only deviation from the plain model is the need for a global non-programmable random oracle (NPRO). Nicely, our scheme can be instantiated from a variety of assumptions believed to be post-quantum secure (e.g., AES). A central technical component of our scheme is the construction of a novel commitment scheme that enjoys a special (mild) form of composability, which may be of independent interest. We also discuss a concrete instantiation of our scheme that is suitable for practical applications.
Last updated:  2026-07-26
Generalized Wiener-Type Attacks on Two RSA-Like Cryptosystems
Abdoulaye Faye, Michel Seck, Abdoul Aziz Ciss, Papa Cheikhou Diop, and Oumar Niang
In AfricaCrypt 2025, Seck et al. proposed a new generalized Wiener-type attack on an RSA-like cryptosystem proposed by Cotan and Teseleanu (NordSec 2023). In their attack, they studied the generalized key equation $eu - (p^4 - 1)(q^4 - 1)v = w$ and showed that a private exponent $d$ which is too large or too small can be recovered in polynomial time. Another RSA variant based on cubic Pell curves with key equation $ed - (p - 1)^2(q - 1)^2 k = 1$, was examined by Rahmani and Nitaj in AfricaCrypt 2025. Note that these two attacks are valid for a balanced modulus $N = pq$ ($q < p < 2 q$). In this paper, we extend these two attacks by showing that for a modulus $N=pq$ product of arbitrary primes $p$, $q$, one can efficiently factor $N$ by studying the two key equations $ex - (p^4 - 1)(q^4 - 1)y = \omega$ and $ex - (p - 1)^2(q - 1)^2 y = \omega$ under certain conditions on $x,y$ and $\omega$. Our new attacks are based on Coppersmith method and continued fractions.
Last updated:  2026-07-25
Encifher: A Trusted-Execution Coprocessor for Confidential Computation on Solana
Nitanshu Lokhande, Rishabh Gupta, Rachit Chahar, Arun Jangra, Aniket Prajapati, and Muskan Kumari
Public blockchains expose all state and computation by default, which is incompatible with financial applications that require confidentiality. Solana achieves high throughput and sub-second confirmation, making it an attractive settlement layer, yet it offers no general mechanism for computing over encrypted state: fully homomorphic encryption (FHE) remains orders of magnitude too slow for interactive use, secure multi-party computation (MPC) incurs heavy communication, and Solana’s native confidential-transfer extension hides only token amounts and supports no programmable logic. We present Encifher, a confidentiality coprocessor for Solana that brings general, programmable computation over encrypted state to a high-throughput chain. Encifher adopts the ciphertext-handle and symbolic-execution interface of confidential-computing coprocessors (e.g., Zama’s fhEVM), but resolves it inside a Trusted Execution Environment (TEE) rather than with a fully homomorphic evaluator: on-chain Solana programs manipulate only 128-bit handles to ciphertexts, while an off-chain coprocessor running inside a hardware enclave fetches the corresponding ciphertexts from a public data availability layer, decrypts and computes on plaintext within the enclave, re-encrypts, and commits attested, Merkle-anchored results back on chain. A key observation is that Solana’s account model and parallel (Sealevel) scheduler turn the transaction’s declared read/write set into the dependency graph of the confidential computation, yielding parallel, correctly-ordered execution of encrypted operations without a bespoke scheduler. To avoid the single-point-of-failure of an enclave holding a master decryption key, Encifher distributes trust across a threshold-decryption committee and verifies enclave attestation on chain. Encifher is deployed in production, powering confidential payments, swaps, and a cross-chain bridge. In production, a confidential swap settles in a single Solana transaction costing 157,000 compute units; the AES-256-GCM symmetric-encryption layer runs at over a million operations per second and threshold decryption completes in single-digit to tens of milliseconds (near-plaintext speed, against the many-orders-of-magnitude overhead of FHE), and Encifher has served over 5,000 users and 50,000 confidential operations. We are explicit about the cost of this design point: Encifher reduces the trust base to TEE integrity, honest threshold key management, and the cloud attestation root, rather than to cryptographic hardness alone.
Last updated:  2026-07-25
Revisiting Automated Quantum Periodic Distinguisher Construction
Jian Guo and Yiran Yao
Simon's algorithm can detect hidden XOR periods in functions derived from symmetric ciphers. Finding such functions becomes difficult when nonlinear layers and diffusion spread the relevant expressions across many branches, so recent work has used symbolic search to automate the construction. We refine the algebraic SMT model of Liu et al. in two ways. Prefix realization checks whether a symbolic starting state can be reached through preceding rounds and records the round-key nibbles needed to produce it. DDT Filtering restricts a local S-box input to a DDT bucket so that the symbolic path can cross an additional nonlinear layer. The latter condition is key-dependent: the target period need not lie in the translation space of the selected bucket, and our results state this condition explicitly. We report the maximum round counts found for GFS-2F, GFS-4F, Skipjack-B, LBlock, TWINE, CRAFT, and SKINNY, with Liu et al.'s automated model as the main comparison. We also combine selected witnesses with partial round-key guesses in the Grover–meet–Simon setting, yielding reduced-round key-recovery candidates below the corresponding comparison budgets.
Last updated:  2026-07-25
Shuffling is Not Enough: Breaking Permutation-Based Model Confidentiality in Hybrid FHE Inference
Jiseung Kim and Hyung Tae Lee
Hybrid fully homomorphic encryption (FHE) inference improves the practicality of private inference by letting the server evaluate linear layers homomorphically while the client decrypts and applies nonlinearities. Recent schemes attempt to protect model confidentiality by returning noisy, output-permuted responses and appealing to shuffle-model differential privacy (DP). We show that this protection fails in the correctness regime required by hybrid FHE systems. For a $d$-input linear layer, $d+1$ admissible queries suffice for exact recovery of a permutation-invariant layer summary, hence for perfect model distinguishability. We further show that input DP is orthogonal to model confidentiality and that the local-DP premise required for shuffle amplification cannot hold under correctness-bounded noise. We recover all linear layers of a SAFHIRE-style ResNet-20 end-to-end from TFHE transcripts with zero error, using $d+1$ queries per layer for a total of $5{,}712$ direct queries. Under the same query model, we also confirm exact per-layer recovery on pretrained ImageNet-scale CNNs and ViT-B/16. The leaked spectra enable fingerprinting, lineage attribution, and improved logit-based extraction, while suppressing them destroys inference utility.
Last updated:  2026-07-25
Linear-Time, Constant-Depth Blind Polynomial Commitments from Generalized RAA Codes, with an End-to-End Blind SNARK Implementation
Kexi Huang, Yanpei Guo, Wenjie Qu, and Jiaheng Zhang
In this work, we construct a new and highly efficient blind polynomial commitment scheme (PCS) over non-binary fields. Our scheme is specifically designed to handle encrypted coefficients without requiring expensive bootstrapping operations, achieving a breakthrough in the "complexity-depth" trade-off. The proposed scheme features an extremely efficient prover both asymptotically and concretely. The commitment and evaluation phases are dominated by a strictly linear $O(n)$ number of field operations. Furthermore, the construction maintains a constant multiplicative depth, which is a critical requirement for efficiency in homomorphic encryption settings. Concretely, for large-scale circuit sizes, our prover is significantly faster than prior state-of-the-art schemes such as phalanx and laminate. Our underlying technique is the Generalized RAA code, an extremely efficient error-correcting code that extends the binary RAA code structure to arbitrary non-binary prime fields $\mathbb{F}_{p}$. We analyze the bounds over non-binary fields, which demonstrate that this code maintains a linear minimum distance property with high probability. By combining Ligero’s IOPP framework, we obtain the first asymptotically and concretely good blind PCS that achieves strictly linear $O(n)$ encoding complexity for the prover while avoiding the expensive bootstrapping operations.
Last updated:  2026-07-25
Floor-IT: Information-Theoretic BFT in Partial Synchrony with Two Round Good Case Latency and Optimal Resilience
Ittai Abraham, Yuval Efron, Jovan Komatovic, and Alejandro Ranchal-Pedrosa
In the information-theoretic model, parties communicate over sender-authenticated point-to-point channels, but use no digital signatures or other transferable cryptographic certificates; the adversary is otherwise computationally unbounded. We present \name, an information-theoretic Byzantine agreement protocol for partial synchrony with a good-case latency of two rounds that achieves the optimal resilience bound of $n = 5f - 1$ in this setting. When the actual network delay after GST is at most $\delta \le \Delta$, our protocol achieves a \emph{robust} good-case latency of $2\delta$. The protocol proceeds in views and guarantees a worst-case view latency of at most $2\Delta + 2\delta$. Moreover, each party requires only $O(1)$ words of persistent storage, and each view incurs $O(n^2)$ messages of $O(1)$ words each.
Last updated:  2026-07-25
Efficient Unclonable Encryption from Pauli Eigenstates
Seyoon Ragavan
We give, to our knowledge, the first plain-model, one-time information-theoretically secure, efficient unclonable encryption scheme for one classical bit. Previous work by Bhattacharyya and Culf (Nature Physics, 2026) and Bhattacharyya, Broadbent, and Culf (arXiv:2603.08916) either only showed $1/\mathsf{poly}(\lambda)$ security loss or required inefficient encryption/decryption operations. We avoid both of these caveats; in doing so, we obtain (to our knowledge) the first plain-model construction of many-time secure $1 \to 2$ unclonable encryption for arbitrary polynomial-length messages, assuming the existence of pseudorandom function-like states (Bartusek and Goldin, arXiv:2605.27647). The key is a uniformly random non-identity phase-free Pauli on $n$ qubits, and bit $a$ is encrypted as a random $(-1)^a$ eigenstate of that Pauli. Encryption and decryption use $O(n)$ single-qubit operations and $O(n)$ time classical computation; key generation uses only $O(n)$ time classical computation. The scheme is exponentially secure; we prove that the probability that both receivers recover the bit is at most $\frac{1}{2}+\frac{1}{2}\sqrt{{2^n}/({4^n-1})} = \frac{1}{2} + O\left(2^{-n/2}\right).$ By a lower bound due to Broadbent, Culf, and Rochette, this is the best probability bound achievable with $n$-qubit ciphertexts (up to the constant hidden in the $O(\cdot)$). The main conceptual idea is to leverage, in a precise spectral sense, the balanced commutation-anticommutation structure of the Pauli group. The proof is intricate but completely elementary and makes use of standard spectral bound techniques. The main technical workhorse is a standalone linear-algebraic lemma which we present in its own section: informally, it relates the positivity of two different operators, each capturing the intuition that if the two receivers can individually decrypt unusually often then they must also disagree often. GPT-5.6 Sol Ultra found this proof in an extended conversation with the author and drafted a preliminary version of this paper. The author is fully accountable for the correctness of this paper.
Last updated:  2026-07-25
A Note on Single-Server QPIR from One-Way Functions
Prabhanjan Ananth, Divyanshu Bhardwaj, and Aditya Gulati
We observe that there exists a single-server quantum private information retrieval with polylogarithmic communication assuming post-quantum one-way functions. Our observation follows immediately from the compilation technique of [Kerenidis-Wolf STOC'03] when combined with distributed point functions by [Gilboa-Ishai EUROCRYPT'14].
Last updated:  2026-07-24
Breaking the Myth of MPCitH Inefficiency: Optimizing MQOM for Embedded Platforms
Ryad Benadjila and Thibauld Feneuil
Signature schemes based on the MPC-in-the-Head (MPCitH) paradigm play an important role in enabling cryptosystems founded on a wide diversity of hardness assumptions. While the design of such schemes is currently stabilizing, providing efficient implementations on embedded devices remains a critical challenge, as MPCitH frameworks are known to manipulate large data structures and to rely heavily on symmetric primitives. In this work, we present a highly optimized implementation of the NIST candidate MQOM (version 2) targeting embedded microcontrollers. Our implementation significantly outperforms existing MPCitH implementations on such platforms, both in terms of memory footprint and execution time. In particular, for the L1 parameter set, we can achieve an SRAM usage below 10 KB, including the key and signature buffers, while preserving practical signing and verification performance (on the order of a few hundred megacycles). We further explore time-memory trade-offs, achieving execution times below 100 Mc for certain variants at the cost of an additional 5-10 KB of memory. We also provide the first memory-friendly implementation of the one-tree technique, which is used to reduce signature sizes in several MPCitH-based schemes. This enables a comparative analysis of the implementation costs of correlated trees (used in MQOM) versus the one-tree technique (used in other candidates). We then demonstrate how streaming and precomputation techniques can further mitigate the impact of the running time and the signature size. For instance, these approaches enable overlapping computation with data reception, for example by starting computations before all inputs are available, thereby reducing overall latency.
Last updated:  2026-07-24
Efficient Ternary Computation of Optimal Ate Pairing on BLS27 Curves
Walid Haddaji
The computation of optimal Ate pairings on elliptic curves with embedding degree $k=27$ (BLS27) is highly relevant for achieving the 256-bit security level, especially in the context of recent advances in the Number Field Sieve (NFS) and its variants (exTNFS, SexTNFS). Traditional binary approaches fail to fully exploit the degree-3 extension tower of $\Fpk{27}$. In this work, we propose an efficient ternary version of the Miller loop, restricting the seed representation to sparse ternary digits $\{0, 1\}$ to streamline point operations and eliminate costly inversions. Furthermore, we generate two new parameter seeds tailored for exTNFS and SexTNFS security levels. These seeds feature sparse ternary representations that simultaneously guarantee the efficiency of the Miller loop and allow the full exploitation of cyclotomic cubing in $\mathbb{F}_{p^{27}}$ during the hard part of the final exponentiation. Compared to the state of the art binary approach by Fouotsa et al. (2020), our exTNFS seed yields a $22\%$ improvement in the overall optimal Ate pairing computation cost. Concurrently, our proposed SexTNFS seed ensures a higher level of security against the most advanced NFS variants.
Last updated:  2026-07-24
Swarm in EM Hay: Particle Swarm-guided Probe Placement for EM SCA
Dev Mehta, Seyedmohammad Nouraniboosjin, Maryam S. Safa, Shahin Tajik, and Fatemeh Ganji
Despite decades of research in electromagnetic (EM) side-channel analysis (SCA), practical attacks still require manual effort and domain expertise to identify informative probe locations on target devices. Existing approaches rely heavily on exhaustive grid scanning or handcrafted alignment, limiting attack scalability and realism. In this work, we present the first automated and adaptive EM SCA framework that uses particle swarm optimization (PSO) to navigate the probe. Particles are guided by mutual information (MI) leakage maps, enabling efficient recovery of secret-dependent emissions. We introduce a novel application of the Nyström approximation to accelerate MI estimation across EM trace windows, allowing real-time swarm guidance without full kernel computations. Unlike prior work, our method requires no leakage templates, manual tuning, or alignment assistance, enabling automated attacks with minimal assumptions. We validate our framework on both microcontroller and FPGA platforms running AES-128. PSO-guided scanning identifies high-leakage points faster than grid search and reduces the number of traces required for successful CPA-based key recovery by up to a factor of 16, i.e., saving tens of thousands of traces.
Last updated:  2026-07-24
Multi-round Dependency Identification: Theoretical Construction and Automatic Search of Impossible Boomerang Distinguishers
Xichao Hu, Lin Jiao, Dengguo Feng, Yongqiang Li, Yonglin Hao, and Xinxin Gong
The impossible boomerang (IB) attack is one of the most powerful cryptanalytic techniques for block ciphers, with notable successes against AES. However, constructing IB distinguishers—the core component of IB attack—remains a fundamental challenge: existing methods are restricted to specific cipher structures, cannot detect contradictions spanning more than two rounds, and lack a unified framework across attack settings. To solve these issues, this paper introduces three hierarchically complementary methods for constructing IB distinguishers: (1) a GEBCT-based method breaking the 2-round contradiction barrier; (2) a state-based method proven exactly equivalent to the definition of IB distinguishers (the most precise available); and (3) a structural method for fast security evaluation. We prove their inclusion relations, unify all prior methods, and connect the state-based method to the Quasidifferential Framework within IB distinguishers. Furthermore, we develop a unified SAT/SMT-based framework that automatically searches distinguishers under single-key, two-related-key, and four-related-key settings. We evaluate on seven representative block ciphers covering almost major design paradigms: We present the first IB distinguishers for ARX cipher SPECK (ISO/IEC standard) and CHAM, bit-permutation cipher GIFT-64 (CHES'17, an example with 5-round contradictions), and key-dependent Sbox cipher PRINTcipher48 (CHES'20). We obtain the first 5-round related-key IB distinguishers for AES-128 (NIST's standard with nonlinear key schedule, first automatically searched), and 1-round improvements over prior IB distinguishers for tweakable cipher SKINNY-64/192 (CRYPTO'16) and SKINNYee (CRYPTO'22). All IB distinguishers outperform the best impossible differentials by 1--4 rounds, including a PRINTcipher48 result that disproves the long-standing claim about single-key IB distinguisher limitations. Finally, we present a 31-round related-key IB attack on SKINNYee, the best result to date.
Last updated:  2026-07-24
Beyond Blockchain Ballots: UC-Secure Layer-2 Voting and Governance
Raghav Bhaskar, Pooya Farshim, Matthias Fitzi, and Aggelos Kiayias
Maintaining a decentralized system requires a collective governance mechanism that allows participants to agree on changes to the system. In particular, the governance mechanism should offer a voting functionality for casting, collecting, and tallying votes in a confidential yet verifiable manner. Scaling this functionality for millions of participants in a cost-effective manner is a critical requirement for permissionless blockchains that remains unmet. We put forward a "layer-2" approach to meet this requirement in a setting where a permissionless blockchain acts as the fallback "layer-1" mechanism. Specifically, our approach to scalability realizes the protocol in a layer-2 fashion: the bulk of the protocol is executed off-chain, but secured on the blockchain with a minimal footprint. We prove our protocol secure in the Universal Composability (UC) framework. First, we formalize a governance ideal functionality $\mathcal{F}_{\mathsf{L2Gov}}$. Our definition offers high levels of confidentiality and verifiability. Moreover, in the case of misbehavior, it allows faults to be attributed so that appropriate action (such as the slashing of on-chain funds) can be taken. Second, we demonstrate that our protocol UC-realizes the $\mathcal{F}_{\mathsf{L2Gov}}$ functionality based on a blockchain, an off-chain bulletin board, a distributed homomorphic encryption functionality ($\mathcal{F}_{\mathsf{DHE}}$), and other standard hybrids. To the best of our knowledge, this work presents the first layer-2 blockchain voting protocol with a rigorous security analysis. We also point out some challenges that arise when applying the UC framework to layer-2 protocols.
Last updated:  2026-07-24
Classic Full Plaintext Recovery Attacks on Low Round Generalized Feistel Networks
Yubing Zhu, Jianhong Shi, Yunteng Yang, and Yonghui Yang
The Generalized Feistel Network (GFN) underpins widely standardized block ciphers, yet its resistance to full plaintext recovery remains largely unexplored. This paper extends the full-plaintext attack framework for standard Feistel ciphers to multi-branch scenarios, mainly makes the following $3$ research contributions: (1) Developed classic full plaintext recovery attacks on $d$-round Type-I GFN ($d\ge 3$) under CPA with $d+1$ encryption queries and $2d$-round Type-I GFN under CCA with $d$ decryption queries. Query complexity depends on d, increasing branches can enhance anti-interference capability. (2) Developed classic full plaintext recovery attack on 2-round Type-II GFN ($d\ge 4$) under CPA with $3$ encryption queries and 3-round Type-II GFN under CCA with $1$ encryption plus $2$ decryption queries. Query complexity is independent of $d$, increasing branches does not improve resistance. (3) Finded that all attacks treat round functions as black boxes, confirming that the weakness resides in the GFN topology rather than specific round-function designs. Strengthening S-boxes or diffusion matrices cannot mitigate it, only increasing rounds beyond the security threshold provides effective defense.
Last updated:  2026-07-24
Hybrid hash function based on the DLP and SIS problems
Dimitri Koshelev and Francesc Sebé
This short note discusses in detail a folklore but little-known hybrid hash function grounded on both the discrete logarithm and short integer solution problems. In particular, specific satisfactory parameters are provided to ensure the standard $128$-bit security level for the lattice problem with $256$-bit module, which may be useful in its own right. The hash function is a natural generalization of the classical Pedersen and Ajtai ones. Nevertheless, to the authors' knowledge, no one has previously explicitly analysed their hybrid version. Besides, the obtained result is probably prone to significant further optimizations by applying many tricks from elliptic curve and lattice cryptographies. Hashing is known to be a basic operation for constructing more complex and important cryptographic schemes. The authors intend to explore such hybrid ones in future articles. However, the hash function under consideration may be precious by itself due to its double provable security. Thus, this introductory work represents a kind of reincarnation of curve-based cryptography whose development has been severely and unfairly undermined by the potential but still vague quantum threat.
Last updated:  2026-07-24
Practical Equivalent-Key Recovery in GRAFHEN
Remi Geraud-Stewart
GRAFHEN is a group-based homomorphic-encryption proposal whose public key is a rewriting system and whose secret key is a permutation representation. We present Maverick, an equivalent-key recovery attack. Maverick breaks every released GRAFHEN challenge, including the recommended two-copy $S_{11}$ instance: it reconstructs an equivalent key from public rules and correctly decrypts all $20{,}000$ supplied labelled ciphertexts. On $12$ independently generated recommended-parameter keys, the median end-to-end time is $552$ s and the median peak memory use is $11.28$ GB on an Apple M3 Pro. The attack converts selected public rewrite rules into group relators, reconstructs a regular action by Todd-Coxeter enumeration, recognizes the resulting permutation representations, and aligns the two sides through the public mixed relations. Public labelled encryptions then calibrate an equivalent decryptor. We prove a proof-carrying version of this procedure: a target-order table with a replayable trace certifies the recovered regular action. The reported $S_{11}$ experiments use target-order closure checks, complete-corpus verification, and decryptor validation. We also give an output-sensitive analysis and state the hypotheses needed to extrapolate beyond the measured instances. Following an independent key-recovery attack, GRAFHEN proposed in July 2026 to replace $S_{11}$ by $\mathrm{PSL}_2(343)$. We adapt Maverick to this setting and demonstrate complete public-rule recovery, alignment, certification, and calibration on generated $\mathrm{PSL}_2(169)$ instances. The two-side $q=169$ run decrypts all $5{,}000$ held-out ciphertexts in a $103$~s critical path using $0.93$ GiB peak memory; a $k=2$ admissibility-filtered corpus also succeeds. Under GRAFHEN's stated worst-case estimate for Dumezy's degree-based search, this degree $170$, $d=5$ setting already has cost $O(2^{850})$, well beyond the intended reach of that attack. At the target group, the post-enumeration recovery path from a generated regular action takes $35.0$ s and $1.92$ GiB peak memory. These results suggest that the proposed platform-group change is insufficient to rule out Maverick; recovery from an admissibility-filtered corpus at $q=343$ remains to be measured because the pre-filter KeyGen enumeration exceeded $32$ GiB of memory before it could produce a corpus.
Last updated:  2026-07-24
LWE with Side Information: Attacks and Concrete Security Estimation
Dana Dachman-Soled, Léo Ducas, Huijing Gong, and Mélissa Rossi
We propose a framework for cryptanalysis of lattice-based schemes, when side information---in the form of ``hints''--- about the secret and/or error is available. Our framework generalizes the so-called primal lattice reduction attack, and allows the progressive integration of hints before running a final lattice reduction step. Our techniques for integrating hints include sparsifying the lattice, projecting onto and intersecting with hyperplanes, and/or altering the distribution of the secret vector. Our main contribution is to propose a toolbox and a methodology to integrate such hints into lattice reduction attacks and to predict the performance of those lattice attacks with side information. While initially designed for side-channel information, our framework can also be used in other cases: exploiting decryption failures, or simply exploiting constraints imposed by certain schemes (LAC, Round5, NTRU). We implement a Sage 9.0 toolkit to actually mount such attacks with hints when computationally feasible, and to predict their performances on larger instances. We provide several end-to-end application examples, such as an improvement of a single trace attack on Frodo by Bos et al (SAC 2018). In particular, our work can estimates security loss even given very little side information, leading to a smooth measurement/computation trade-off for side-channel attacks.
Last updated:  2026-07-24
ConvertInput-Free Vector Homomorphic Secret Sharing and Its Applications
Fan Yang, Fucai Luo, Xingfu Yan, Haining Yang, Zheng Gong, and Wing W. Y. Ng
This work presents ConvertInput-Free Vector Homomorphic Secret Sharing (Vector-HSS), a novel HSS primitive based on the Decisional Composite Residuosity (DCR) assumption. Our construction enables efficient high-dimensional vector computations while avoiding the costly $\texttt{ConvertInput}$ operation. As a unified framework, Vector-HSS can be used as a building block for Private Information Retrieval (PIR), Secure Multi-Party Computation (MPC), Privacy-Preserving Machine Learning (PPML), etc. The key idea behind Vector-HSS is to introduce a vector-centric computation paradigm. Unlike traditional approaches, this design allows the server to perform natural and efficient vector computations without the $\texttt{ConvertInput}$ operation while keeping client-side overhead comparable to that of state-of-the-art solutions. To further improve efficiency, we develop a batching mechanism based on the Chinese Remainder Theorem (CRT) that enables parallel computation across multiple vectors. Building on these techniques, we further design a suite of protocol modules to securely support Euclidean/cosine distance computation, comparison, and matrix-vector multiplication in practical applications. Experiments show that our scheme achieves $280\times$ and $70\times$ speedups over prior HSS schemes (EUROCRYPT 2021 and S&P 2026, respectively) for batched inner product evaluation. When applied to privacy-preserving image retrieval, our method achieves sub-second retrieval time, outperforming state-of-the-art solutions under similar security requirements.
Last updated:  2026-07-24
Complex-Multiplication Terminals for Supersingular Isogeny Path-Finding
Zheng Tao, Zhi Hu, Yijing Zhang, and Changan Zhao
We propose a complementary stopping strategy based on complex multiplication (CM) for the subfield-search stage of supersingular isogeny path-finding, a bottleneck in the Delfs-Galbraith/SuperSolver algorithm. The original search performs a non-backtracking walk in the supersingular \(2\)-isogeny graph until it reaches the subfield terminal set \(S_p\). Our idea is to enlarge the set of recognizable terminals, by adding a precomputed set of CM supersingular vertices. For a discriminant bound \(M\), we construct \(S_{\mathrm{CM}}(M)\) from roots of Hilbert class polynomials \(H_D(X)\) over \(\mathbb F_{p^2}\), where \(D\) ranges over inert negative fundamental discriminants with \(|D|<M\). The walk then stops upon reaching \(S_p\cup S_{\mathrm{CM}}(M)\). The only additional per-visit cost is an expected \(O(1)\) hash-table membership query in the precomputed CM terminal table. We estimate the size and preprocessing cost of \(S_{\mathrm{CM}}(M)\), obtaining the heuristic growth \(|S_{\mathrm{CM}}(M)|=\Theta(M^{3/2})\), and show that the overlap \(S_{\mathrm{CM}}(M)\cap S_p\) is lower order. We also give terminal-connection procedures showing how searches that stop at CM vertices can be converted into full isogeny paths under the standard quaternionic and KLPT heuristics. The method does not change the asymptotic exponent of the underlying Delfs-Galbraith search; instead, it provides a complementary technique for existing subfield-search methods by adding efficiently recognizable CM terminals. Experiments on small parameters show that enlarging the terminal union reduces both visited vertices and field multiplications, while lookup benchmarks at SQIsign parameters confirm that the additional table membership test has stable and moderate per-visit overhead.
Last updated:  2026-07-24
Distributed Vector Commitments and Their Applications
Rui Gao, Huaqun Wang, Zhiguo Wan, and Yuncong Hu
Vector commitment (VC) schemes enable a prover to commit to a vector and later open any position with a short proof. However, existing VC schemes are designed for centralized settings, and cannot work in decentralized systems, where the input vector is distributed across multiple machines. Similarly, traditional VC schemes cannot leverage distributed parallel computation across multiple machines for acceleration. To tackle this issue, we introduce a new notion—distributed VC (DVC), which allows multiple machines, each holding only a subvector of the input vector, to collectively commit to the entire vector and generate position proofs in a distributed manner. To the best of our knowledge, there is no prior work on DVCs and no existing work can trivially derive an efficient DVC scheme. The key challenge is that both commitments and proofs depend on the entire vector, while no single machine holds the complete vector in distributed settings. We propose the first DVC scheme, HLE-DVC, which leverages $M$ machines to process the distributed vector $\mathbf{v}$ of length $N$ in parallel, with each machine holding a subvector of length $\frac{N}{M}$. HLE-DVC achieves compact proof size-$\text{O}(\log M)$ and allows each machine to generate all its position proofs in a single communication round, with communication cost $\text{O}(\log M)$ and computation cost $\text{O}(\frac{N \log N}{M})$. Moreover, HLE-DVC supports batch proving, proof aggregation, and efficient updates. We conduct the experiments and open-source the code. Using 256 machines to generate all proofs for a committed vector of length $2^{30}$ takes 17,515 seconds. This achieves a $256\times$ parallel speedup over HLE-DVC on a single machine, and is $142\times$ faster than Hyperproofs (a famous single machine VC scheme). The communication cost per machine is 0.768 KB.
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.