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

Last updated:  2026-08-20
UM-PSO: A Unified Multi-Party Framework for Private Set Operations against a Dishonest Majority
Yaxi Yang, Xiaojian Liang, Weizhan Jing, Ye Dong, Xiangfu Song, Fangyuan Sun, Pu Duan, and Tianwei Zhang
Private Set Operations (PSO) enable mutually untrusted parties to securely compute arbitrary functions (e.g., union, intersection, and cardinality) over their private input sets. These operations have wide applications in many real-world scenarios. Existing PSO protocols fall short of practical deployment for several reasons. (1) \textit{Function-specific}. Real-world privacy-preserving applications often require multiple set operations within the same task, while existing solutions typically address individual functionalities (e.g., intersection or union) in isolation, making it difficult and costly to support diverse set operations in a unified and efficient manner. (2) \textit{Lacking malicious security}. As PSO is commonly employed in highly sensitive applications, it is often necessary to provide strong security guarantees against malicious adversaries. Unfortunately, most existing works only achieve semi-honest security, which limits their practical applicability. (3) \textit{Restricted settings}. The majority of existing works focus exclusively on the two-party setting. How to extend them securely and efficiently to the multi-party setting while tolerating a malicious majority remains unclear. To date, designing a maliciously secure multi-party PSO (mPSO) framework that efficiently supports diverse set operations remains an open challenge. This paper presents the \textit{first} maliciously secure mPSO framework, named UM-PSO, that supports a broad range of set operations with practical efficiency. At the core of our framework is a function-independent preprocessing phase that prepares a reusable pool of secret-shared items, which can then be leveraged to securely compute diverse set functionalities in the online phase. To achieve malicious security efficiently, we design verification mechanisms on top of SPDZ-based authenticated secret sharing, along with tailored techniques and optimizations to further improve practical performance. We implement our protocols and report concrete performance results. For a representative setting with 5 parties and a total of $2^{12}$ 128-bit items, our framework achieves an online running time of $0.627$ seconds and incurs $3.35$ MB of communication. Compared to the baselines, our framework achieves up to $51\times$ speedup and up to a $76\times$ reduction in communication.
Last updated:  2026-08-20
CAKE-HI - Compact Authenticated Key Exchange Hiding Identities
Uri Blumenthal, Gene Itkis, Roger Khazan, Brandon Luo, Sean O'Melia, Brian Proulx, David Stott, Gabriel Torres, and David A. Wilson
Modern public-key cryptography is threatened by advances in quantum computing. As a result, there has been a shift towards cryptographic algorithms that can resist attacks by a quantum computer. However, these algorithms use significantly longer keys, and produce larger ciphertexts and digital signatures than their classical counterparts. These bigger sizes pose problems for devices that are bandwidth- and/or power-limited, and wish to establish a secure, quantum resistant communication channel with another device. In order to reduce the overhead of using these algorithms in challenging environments while maintaining security posture, we present Compact Authenticated Key Exchange – Hiding Identities (CAKE-HI). To evaluate our protocol, we compare the key exchange handshake size and computational efficiency of mutual authenticated TLS and CAKE-HI. Measurements show that CAKE-HI significantly reduces the handshake size and the computational overhead of establishing a quantum-secure link. In addition, we formalize and prove security properties about CAKE-HI in the symbolic and computational model using the protocol analysis frameworks Verifpal and CryptoVerif.
Last updated:  2026-08-20
SafeHub: End-to-end encrypted Git hosting system
Easwar Vivek Mangipudi
Private repositories remain readable to Git hosts despite transport and at-rest encryption. We present SafeHub, an end-to-end encrypted Git hosting system. It encrypts repository contents and semantic metadata - file names, commit messages, authors, branches, issues, pull requests, and refs - so the host sees only ciphertext, opaque identifiers, lengths, and order. Each repository is a Messaging Layer Security (MLS) group, providing admin-mediated membership, post-compromise healing, and per-invite history windows. Ordinary Git behavior is preserved within each member's window: branches, merges, and blame still work. Forward-only members start from a join shallow snapshot rather than the full past. Confidentiality alone is not enough: Git's hash-linked objects do not protect mutable refs. SafeHub records refs in an encrypted, device-signed, hash-chained manifest that detects rollback against a member's own anchor and host forks when members compare checkpoints; force-pushes require administrator co-signatures. We specify a single ideal functionality F_safehub for the system and prove that SafeHub universally composably realizes it against a malicious server and adaptive member corruptions, in a hybrid model over group key agreement and certification, assuming secure erasure in the quantum random oracle model. Our NIST PQ Category-5 Rust prototype measures full-stack push, pull, fetch, clone, merge, rebase, and force-push on a client-server pair of AWS Graviton4 hosts, together with the epoch rotation and consolidation that Git has no counterpart for. Against Git on its lowest-overhead native transport, wall-clock push runs 1.45x plain Git at a 0.05 MB delta and 0.98x at a 5 MB one, its marginal cost 46.7 ms/MB against Git's 49.3. We compare SafeHub with five other systems - plain Git, git-crypt, git-remote-gcrypt, and a reimplementation of the closest peer - over a single transport, with clients and remotes on separate hosts. The comparison separates designs whose cost follows the edit from designs whose cost follows the whole file. For a fixed 1 KiB edit, with the edited file growing from 10 KiB to 8 MiB, SafeHub's cost per update remains constant at 6.7 kB, because it seals the packfile Git has already built, whereas the systems that encrypt each file individually grow with the file and reach 8.39 and 13.4 MB. On that shared transport SafeHub is the fastest of the six at push, pull, fetch, merge, rebase, and force-push, each constant in history depth, and its stored size matches plain Git to within 0.2%, whereas the per-file encryption used by the other systems costs 13 to 21 times as much. The cost that does not amortize is clone, which grows with sealed history: a host that cannot read a repository cannot repack it.
Last updated:  2026-08-20
Compressed Post-Quantum Silent OT from Isogenies
Pouria Fallahpour, Arthur Herlédan Le Merdy, and Mahshid Riahinia
Oblivious transfer (OT) is a foundational tool in secure computation. Random OT-correlated pairs of the form $(r_0,r_1)$ and $(b,r_b)$, where $r_0,r_1,b \stackrel{{}_\$}{\leftarrow} \{0,1\}$, significantly speed up secure computation protocols. Pseudorandom correlation functions (PCFs), introduced by Boyle et al. (FOCS 2020), are an efficient means of non-interactively generating correlated pairs. In a PCF, two parties store short keys that are used to locally generate large amounts of correlated pairs. While pre-quantum PCFs for OT achieve highly compact key sizes (e.g., $30$ kB), a significant gap remains in the post-quantum regime, where existing solutions rely on lattices or learning-parity-with-noise-style assumptions and yield much larger keys. We construct compact post-quantum PCFs for OT. Our construction has key sizes in the range of $100$ kB, approaching the compactness of pre-quantum PCFs and seven times smaller than the most compact state-of-the-art post-quantum alternatives. The key size of our PCF remains invariant regardless of the target number of OTs, in contrast to prior alternatives. We estimate a throughput of $7$ OTs per second for our PCF. We additionally provide a security proof in the quantum random oracle model, constituting the first such analysis of a post-quantum PCF. The core of our construction is a new, compact constrained pseudorandom function (CPRF) for inner-product membership predicates. Its security is based on a natural extension of the parallelization problem, which we introduce as the parallelization problem with auxiliary inputs. We provide an extensive analysis of this assumption as well as an implementation of our construction.
Last updated:  2026-08-20
Code-based Distributed Polynomial Commitment Scheme with Linear Prover Time and Polylogarithmic Communication
Zesheng Li, Xinzhen Chen, Yuejia Cheng, Zixing Wang, Yihang Du, Xinxuan Zhang, and Yi Deng
We present the first fully distributed, code-based polynomial commitment scheme (PCS) that achieves linear prover time and polylogarithmic communication for multilinear polynomials. Our construction builds on Brakedown with proof composition. We design a distributed proof of correct linear encoding. Codeword validity is reduced to a sumcheck relation over the sparse parity-check matrix, whereas systematic consistency is verified through multilinear evaluation checks. These techniques preserve linear prover complexity while reducing the communication size between sub-provers to polylogarithmic scale. We implement our construction and evaluate it on multilinear polynomials ranging in size from $2^{22}$ to $2^{28}$. The prover exhibits near-linear parallel scalability. Compared with existing evaluated distributed PCS implementations with 8 parties, it reduces communication by at least $13\times$ at every tested polynomial size, while its prover time remains within $1.31\times$ of the fastest implementation. These results demonstrate that our asymptotic communication improvements translate into substantial concrete savings while retaining efficient proving.
Last updated:  2026-08-20
Symphony: Scalable SNARKs in the Random Oracle Model from Lattice-Based High-Arity Folding
Binyi Chen
Folding/Accumulation schemes are a powerful tool for building scalable proof systems. However, standard approaches for leveraging folding schemes, such as IVCs or PCDs, require embedding hash functions (modeled as random oracles) into recursive circuits, introducing both security concerns and significant proving overhead. We re-envision how to use folding schemes, and introduce Symphony, the first proving paradigm that leverages folding schemes as a black box without embedding hashes in SNARK circuits. It is memory-efficient, parallelizable, and plausibly post-quantum secure, with polylogarithmic proof size and verification. The (low-memory) prover requires O(log log n) passes of the input data and its computation is dominated by committing to the input witnesses. A core component of our construction is a new lattice-based folding scheme that compresses a large number of NP-complete statements into one in a single shot. Furthermore, we design a generic compiler that converts a folding scheme into a SNARK without embedding the Fiat-Shamir circuit into proven statements.
Last updated:  2026-08-20
Chasing QuOCCAs in a Quantum World: Type-2 Oracles for CCA-Secure PKE
Barbara Jiabao Benedikt, Tommaso Gagliardoni, and Patrick Struck
In the context of PKE schemes, Gagliardoni et al. proposed at PQCrypto 2021 a qIND-qCPA security notion (a superposition-based analogue of the classical IND-CPA security notion), by using the theory of so-called type-2 unitary operators. On one hand, this notion is very natural, closely mirrors the classical intuition, and can be handled without relying on complex techniques such as Zhandry’s compressed oracles. On the other hand, it is restricted to a certain class of PKE schemes (so-called isometric). Moreover, it is not immediately clear how to extend the definition to chosen-ciphertext attack (CCA) scenarios, mainly due to the possibility of decryption failures – something that is entailed by most quantum-resistant PKE schemes. In this work, we use the theory of type-2 operators to extend superposition-based security notions to any PKE schemes, in the CPA and CCA setting, without Zhandry’s compressed oracle technique. We start first by showing that a trivial extension of Gagliardoni et al.’s techniques to the general case is not possible, even for the CCA1 case, by identifying barriers preventing the realization of a ‘natural’ type-2 decryption operator. Then we define a subclass of PKE schemes (which we call ‘strongly decryptable’ ), for which it is easy to circumvent the aforementioned barriers and to define superposition-based CCA1 and CCA2 notions. Further, we introduce a novel transformation (that we call ‘purification’) which applies to any PKE scheme, producing a ‘quasi-PKE’ scheme, for which it is possible to define properties that mimic the security notions defined for strongly decryptable schemes; we can thus ‘unload’ the security definitions for an arbitrary PKE scheme on its purification. Finally, we show implications and separations between our security notions, as well as constructions.
Last updated:  2026-08-20
Round-Preserving Compilers for Super-Rushing Secure MPC
Michele Ciampi, Divya Ravi, and Mingrui Zou
Practical implementations of synchronous MPC protocols typically require each party to advance to the next round as soon as they have received all expected messages. This deviates from the theoretical synchronous round-based model, where instead each party advances in the next round after a timeout. To capture this gap between theory and practice, Asharov, Chandramouli, Cohen and Ishai in Eurocrypt 2025 proposed a new model where the adversary is super-rushing. In this, the adversary can see future messages of some honest parties before delivering current-round messages to slower ones. In this work, we study super-rushing security in both the computational and statistical settings, and design round-preserving compilers that transform standard synchronous MPC protocols into ones secure against super-rushing adversaries. Ours is the first work to investigate the security of computational MPC protocols against a super-rushing adversary.
Last updated:  2026-08-20
STARK-based Signatures from the RPO Permutation
Shahla Atapoor, Cyprien Delpech de Saint Guilhem, and Al Kindi
This work describes a digital signature scheme constructed from a zero-knowledge proof of knowledge of a pre-image of the Rescue Prime Optimized (RPO) permutation. The proof of knowledge is constructed with the DEEP-ALI interactive oracle proof combined with the Ben-Sasson--Chiesa--Spooner (BCS) transformation in the random oracle model. The EUF-CMA security of the resulting signature scheme is established from the UC-friendly security properties of the BCS transformation and the pre-image hardness of the RPO permutation. The implementation of the scheme computes signatures in 13 ms and verifies them in 1 ms on a single core when the BCS transform is implemented with the Blake3 hash function. (The multi-threaded implementation signs in 9.2 ms and also verifies in 1 ms.) These speeds are obtained with parameters achieving 122 bits of average-case security for \( 2^{122} \)-bounded adversaries with access to at most \( 2^{64} \) signatures.
Last updated:  2026-08-20
Compact Quaternion Algorithms for SQIsign
Won Kim, Changmin Lee, and Hyunwoo Yoo
SQIsign is an isogeny-based post-quantum signature scheme whose public keys and signatures are remarkably compact. However, since SQIsign relies on arithmetic in quaternion algebras over the field of rational numbers, no fixed-precision integer arithmetic for SQIsign had been established until recently, hindering constant-time implementation and deployment on memory-constrained devices. Recent work by Kim et al. instantiated an SQIsign implementation with fixed-precision integer arithmetic by deriving uniform worst-case bounds for the quaternion algorithms used in key generation and signing. Nevertheless, the resulting precision budget remains large, exceeding 13 times the public key size. Consequently, this forces implementations to reserve wide integer buffers throughout the computation. This increases the memory footprint and reduces the suitability of fixed-precision SQIsign for constrained platforms. In this work, we present compact quaternion algorithms that substantially reduce the fixed-precision memory requirements of SQIsign. First, we modify and analyze quaternion algorithms for SQIsign, in which large intermediate integer values appear. Then, we derive the improved uniform worst-case size bound on integers during the key generation and signing procedures. As a result, we reduce the required precision budgets from 7026/10713/14150 bits to 1665/2521/3319 bits for the NIST-I/III/V security levels, respectively, corresponding to improvements of $76.30\%$, $76.47\%$, and $76.54\%$. We also provide a fixed-precision implementation of SQIsign applying these improved precision budgets and accelerating previous inefficient implementation of fixed-precision integer arithmetic. Compared with the previous fixed-precision implementation, our implementation achieves performance improvements larger than $99\%$ for both key generation and signing procedures at each security level.
Last updated:  2026-08-20
Improved Collision Attack on RIPEMD-160
Zhengrong Lu, Hongbo Yu, Yingxin Li, Xindi Zhang, and Xiaoen Lin
RIPEMD-160 is an ISO/IEC hash function standard based on the Merkle-Damgård structure with a double-branch compression function. There have been many attempts at modular differential attacks on reduced RIPEMD-160, with the best previous result being a 40-step practical collision attack achieved in 2023. That attack constructs a simple local collision in round 2 of the left branch to minimize uncontrolled conditions. To achieve this, differences must be introduced into many message words, which constrains the maximum number of steps that can be attacked. To overcome this limitation and target more steps, we propose a new differential characteristic structure that abandons the sparse local collision in round 2 and instead uses a single continuous differential characteristic spanning rounds 1 to 2 for each branch. This structure allows us to inject a difference into only one message word. Using an automatic search tool based on the high-performance parallel SAT-solver PRS, we identify suitable differential characteristics by imposing more control over conditions, differences, and the probability of proper propagation. Based on the differential characteristics, we identify three colliding message pairs for 42-step RIPEMD-160 with theoretical time complexity of approximately $2^{47.4}$, thereby improving the best practical collision attack by 2 steps on this hash function.
Last updated:  2026-08-20
On the Impossibility of Robust Combiners for Cryptographic Groups
Cong Zhang, Wenli Wang, Taiyu Wang, Hong-Sheng Zhou, Pengfei Chen, Zhihong Jia, Jian Liu, Jinfei Liu, Moti Yung, and Kui Ren
A $(k,n)$-robust combiner for a primitive $\mathcal{P}$ combines $n$ candidate instantiations of $\mathcal{P}$ into a single scheme that remains secure as long as at least $k$ of them remain secure. Robust combiners have been extensively studied for primitives such as hash functions, public-key encryption, and oblivious transfer, but much less is known in the setting of cryptographic groups. In this work, we initiate the study of robust combiners for cryptographic groups in Maurer's generic group model (GGM), where algorithms access group elements only through abstract algebraic operations. We ask whether one can combine $n$ candidate groups into a single group that remains secure provided that at least $k$ of the underlying groups remain secure. A natural baseline is the direct-product construction, which preserves search hardness but fails for decisional assumptions and incurs substantial representation overhead. We show that these limitations are in fact inherent. Our first result is a complete impossibility for the decisional Diffie--Hellman assumption: for every polynomially bounded $n$ and $k$ with $k<n$, there is no generic $(k,n)$-robust combiner for cryptographic groups that preserves DDH security. Our second result gives a tight threshold for search assumptions in the regime where $n$ and $k$ are fixed constants. For the discrete logarithm problem, robust generic combination is possible when the combined group order is large enough to encode the secrets of $n-k+1$ components; concretely, if $\log N \ge (n-k+1)\lambda$, where the component groups have distinct $\lambda$-bit prime order, then a robust combiner exists. Conversely, if $\log N \le (n-k)\lambda$, then no generic $(k,n)$-robust DLog-secure combiner exists. These results identify a fundamental limitation of robust hedging at the group level. Decisional assumptions such as DDH cannot be robustly combined in the GGM, while search assumptions admit robustness only at essentially optimal representation cost. Consequently, robustness for group-based cryptography must in general be achieved at higher layers, such as protocol design or key derivation.
Last updated:  2026-08-20
Hermine: An Efficient Lattice-based FROST-like Threshold Signature
Giacomo Borin, Sofía Celi, Rafael del Pino, Thomas Espitau, Shuichi Katsumata, Guilhem Niot, Thomas Prest, and Kaoru Takemure
Threshold signatures have regained a strong interest recently, driven by applications in cryptocurrencies and NIST's ongoing call for threshold schemes. Among them, FROST - a classical threshold Schnorr signature scheme already in real-world deployment - stands out. Its appeal lies in three core features: partially non-interactive signing, non-interactive identifiable abort (IA), and proactive security. In contrast, while post-quantum (PQ) threshold signatures have seen significant advances in recent years, no existing scheme simultaneously provides even two of these features. Considering the imminent need to migrate to PQ cryptography, this state-of-the-art remains unsatisfactory. In this work, we propose Hermine, a lattice-based threshold signature that offers the full feature set of FROST under standard lattice assumptions. Hermine is designed to efficiently support the Medium scale of parties ($N \le 64$) as defined in the NIST threshold call, producing a small \Raccoon signature of size $11$ KB. Our main technical contribution is introducing an everywhere-short secret sharing, which splits a short secret vector $\mathbf{s} \in R_q^\ell$ into short shares and admits a short linear reconstruction algorithm. While the resulting construction appears intuitive, its security proof requires a non-trivial, fine-grained analysis of the information on $\mathbf{s}$ that is inherently leaked by the short shares. Furthermore, we formalize game-based unforgeability and IA definitions with proactive security, which may be of independent interest.
Last updated:  2026-08-20
ZEE200: Zero Knowledge for Everything and Everyone @ 200 KHz
Sunghyeon Jo, Vladimir Kolesnikov, and Yibin Yang
Zero-knowledge execution of high-level programs proceeds by repeatedly evaluating CPU steps. Each such step privately selects and evaluates an instruction (possibly involving memory access) from a rich instruction set. Building on this paradigm, ZEE (Heath et al., S&P'21) realized a full toolchain supporting arbitrary $\texttt{ANSI C}$ programs, demonstrating this capability by proving SIR- and CVE-reported bugs in off-the-shelf Linux programs $\texttt{sed}$ and $\texttt{gzip}$. We revamp the state of the art by building a new constant-round ZK system ZEE200, which is about $20\text{-}40\times$ faster than ZEE. ZEE200 is built on a novel and convenient cryptographic framework for efficiently proving general statements represented as real-world programs. Our framework integrates several crucial recent advances, such as Tight ZK CPU (Yang et al., CCS'24) and fast ZK RAM (Yang and Heath, USENIX Security'24). We develop better encodings for $\mathbb{Z}_{2^{32}}$ arithmetic, and numerous low-level optimizations. Compared to ZEE's $\approx 10$ KHz CPU speed on a limited ISA, ZEE200 runs at $\approx 200$ KHz (still on a commodity laptop and a LAN!), while supporting a much richer ISA. For example, we rerun a ZEE's benchmark, proving a SIR-reported vulnerability in off-the-shelf Linux utility $\texttt{sed}$. On a 2021 ThinkPad X1 Carbon Gen 9 under a simulated $1$Gbps LAN (single-threaded), ZEE200 completed the proof in $1.5$ seconds, compared to ZEE's $30.1$ seconds, a $20\times$ improvement.
Last updated:  2026-08-19
Interleaving Stability for Mutual Correlated Agreement and Curve Decodability
Sunghyeon Jo
We prove that row-wise interleaving does not impose a linear loss on two coding-theoretic soundness properties used in recent IOP/SNARK analyses: generator mutual correlated agreement and curve decodability. For generator-MCA, let $G:\Omega\to\mathbb{F}_q^\ell$ be a coefficient generator over a finite seed set and let $C$ be an $\mathbb{F}_q$-additive code. For every interleaving width $s$ and distance parameter $\delta$, we show $$ \varepsilon_G(C,\delta) \le \varepsilon_G(C^{\equiv s},\delta) \le \left(1+\frac1q+\cdots+\frac1{q^{s-1}}\right)\varepsilon_G(C,\delta). $$ Moreover, if $|\Omega|\le q$, then the transfer is exact: $$ \varepsilon_G(C^{\equiv s},\delta)=\varepsilon_G(C,\delta). $$ In particular, affine-line MCA is invariant under row-wise interleaving. This answers the known interleaving-loss question and removes the linear interleaving factor from the affine-line MCA bound. It also implies that polynomial-generator MCA bounds transfer to interleaved codes without an additional interleaving-width factor. We further establish interleaving stability for curve decodability. We introduce a marked formulation, prove its equivalence to the standard definition for $\mathbb{F}_q$-additive codes and $1\le b\le a\le q$, and use it to transfer curve decodability to row-wise interleavings. If $C$ is $(\ell,\delta,a,b)$-curve-decodable and $\binom{a}{b}\le q$, then $C^{\equiv s}$ is also $(\ell,\delta,a,b)$-curve-decodable for every $s$. We also give a field-size-weighted variant that transfers larger base-code witness parameters to smaller interleaved-code witness parameters.
Last updated:  2026-08-19
Efficient Two-Online-Round Secure Comparison in the Plain Model
Koji Nuida and Satsuya Ohata
Secure comparison is a fundamental building block frequently employed in various applications of secure multiparty computation, such as secure machine learning. Such protocols based on secret sharing (SS) typically excel in throughput, but they historically suffer from higher (online) round complexity. To address this issue, Attrapadung et al. (AsiaCCS 2022) proposed a protocol with two online rounds in the client-aided model (i.e., assuming a trusted third party in the offline phase), and Lu et al. (USENIX Security 2025) proposed a protocol with three online rounds in the plain model. In this paper, we propose a plaintext comparison protocol with two online rounds in the plain model. While keeping the lowest online round complexity, our protocol also reduces the total bit complexity. For example, for the case of 64-bit integers, the total bit complexity of our protocol is 25.7% of Lu et al.'s protocol and 23.3% of Attrapadung et al.'s protocol adjusted to the plain model.
Last updated:  2026-08-19
A Key-Recovery Attack on TALUS-MPC in TALUS v4
Sunghyeon Jo
We give a two-transcript key-recovery attack on TALUS-MPC in TALUS v4. TALUS was presented in the second round of the NIST Threshold Call Preview Talks. In Algorithm 3 of TALUS v4, the committee's nonce polynomials are evaluated at all $N$ points so that any $T$ parties can sign. An adversary controlling the coordinator and $T-1$ parties can reuse the same pooled nonce with two quorums whose only common members are corrupt. Each participating honest party uses its signing share once, yet the coordinator obtains $\mathbf{z}_0=\mathbf{y}+c_0\mathbf{s}_1$, $\mathbf{z}_1=\mathbf{y}+c_1\mathbf{s}_1$. The nonce cancels on subtraction. Moreover, no invertibility assumption in $R_q$ is needed: the response equations lift to $\mathbb{Z}[X]/(X^{256}+1)$, and every nonzero $c_0-c_1$ is invertible in the cyclotomic field $\mathbb{Q}[X]/(X^{256}+1)$. Thus two distinct challenges recover $\mathbf{s}_1$ exactly; since the TALUS v4 public key includes the full $\mathbf{t}=\mathbf{A}\mathbf{s}_1+\mathbf{s}_2$, the adversary also recovers $\mathbf{s}_2$ and forges signatures.
Last updated:  2026-08-19
Notes on Short-Limb Modular Multiplication Techniques: Barrett, Montgomery, Plantard, and the Explicit CRT
Bo-Yin Yang
This note collects, in compressed form, some techniques for modular multiplication with word-size (“short-limb”), or at most a-handful-of-words sized moduli as they are used in implementations of lattice-based cryptography: Barrett reduction and multiplication (in signed and unsigned flavors, with exact error, range, and canonicality analyses), Montgomery reduction and multiplication (including the folded-constant form, the precise equivalence with Barrett multiplication, even moduli, the multi-limb case, and the k-reduction), Plantard multiplication (the original unsigned algorithm, the signed variant, and a variant taking signed inputs to the canonical unsigned representative in [0,q)), and modular multiplication via the explicit Chinese remainder theorem. These are compressed out of my lecture slides in the class Post-Quantum Cryptography at National Taiwan University 2020--2025 (EE 5176/921 U2540). All numerical examples, ranges, and windows stated here have been verified by exhaustive or randomized machine search; several constants and ranges correct typos and miscalculations that circulated after lectures.
Last updated:  2026-08-19
Reed–Solomon Mutual Correlated Agreement Beyond the Johnson Radius
Sunghyeon Jo
Mutual correlated agreement (MCA) bounds how many points on an affine line of received words can agree with codewords on many coordinates when the line does not admit a common codeword explanation on those coordinates; the corresponding line parameters are called bad. MCA arises in the soundness analysis of code-based proof systems. For Reed-Solomon codes with arbitrary prescribed evaluation sets, existing deterministic bounds apply only at integer error budgets strictly below the exact Johnson boundary. Fix integers $r\ge2$ and $h\ge1$. For every sufficiently large $K$, let $L\subseteq\mathbb{F}_q$ be any set of $n=rK$ distinct points and set $C=\operatorname{RS}_{<K}(\mathbb{F}_q,L)$. At error budget $E=\left\lfloor{n-\sqrt{n(K-1)}}\right\rfloor+h$, we prove that every affine line has at most $O_{r,h}(K^6)$ bad parameters. Hence \[ \varepsilon_{\mathrm{mca}}(C,E)=O_{r,h}(K^6/q). \] Thus, at each fixed rate $1/r$, any fixed number of integer steps beyond Johnson admits a deterministic polynomial bound on the number of bad parameters; in relative-radius units, the gain is $O(1/n)$. We also derive a MCA upper bound for maximum distance separable (MDS) codes from a sharp lower bound on the number of rejected local membership tests. For Reed-Solomon codes over sufficiently large fields, the resulting endpoint bound is exact whenever at most $K+1$ agreements are required. It yields exact $2^{-128}$ thresholds for four explicit smooth-domain codes of length $64$: we identify the largest safe integer budget and prove that the next one is unsafe. As a concrete application to the Grand MCA Challenge, we exhibit a single prime field $\mathbb{F}_Q$, with $Q<2^{256}$, that supports the required smooth domains at all four target rates. With $K=2^{18}$, the first post-Johnson budget has MCA error below $2^{-128}$ at rates $1/2,1/4,1/8,$ and $1/16$, as does the second such budget at rate $1/8$.
Last updated:  2026-08-19
Cryptanalysis of a Candidate Witness Encryption Scheme for Affine Determinant Programs
Sunghyeon Jo
At ITCS 2020, Bartusek, Ishai, Jain, Ma, Sahai, and Zhandry proposed a framework for witness encryption based on affine determinant programs and gave a concrete witness encryption candidate. Yao, Chen, and Yu later broke the separate ADP-based indistinguishability-obfuscation candidate, while noting that their attack did not apply to the witness-encryption construction. More recently, Soukhanov et al. proposed witness encryption from arithmetic affine determinant programs. Soukhanov subsequently described a commutator attack on that construction and noted that the original ADP construction is also subject to the attack for sparse circuits. The recovery of hidden column spaces in our attack uses this commutator technique. We give a deterministic polynomial-time attack that recovers the encrypted bit from the public ciphertext matrices of this candidate. It covers every $q\geq 1$ in the theorem's recovery range, including $q(n)=\lceil n^\varepsilon\rceil$ for all sufficiently large $n$. Outside a fixed finite set of primes, it applies to every SUBSET-SUM instance whose coefficient vector is nonzero modulo $p$ and that has no Boolean solution modulo $p$. On an explicit efficiently generated family of integer NO instances, the encrypted bit is recovered with probability $1-\mathrm{negl}(n)$ under the field-size convention of the original paper.
Last updated:  2026-08-19
Unclonable encryption from BB84 states: a simultaneous Goldreich-Levin reduction
Andrea Coladangelo, Qipeng Liu, and Ziyi Xie
Goldreich-Levin reductions are ubiquitous in cryptography: they convert an algorithm capable of guessing $\langle r, m \rangle$ (mod $2$) for a hidden string $m$ and a random challenge $r$, to one that is capable of extracting the entirety of $m$. Here, we describe a "simultaneous" Goldreich-Levin reduction for two entangled parties who are capable of guessing $\langle r, m \rangle$ given uniformly random identical challenges $r$. This allows to upgrade any unclonable encryption scheme satisfying "search" security to one satisfying the gold standard of unclonable "indistinguishability". As a corollary, we show that the simplest candidate unclonable encryption scheme from BB84 states satisfies unclonable indistinguishability. This result was discovered by GPT-5.6 Ultra after a few interactions. Our prompts included recent results on unclonable encryption by Ananth and Sahai, and Ragavan.
Last updated:  2026-08-19
Block-Accumulate Codes: Accelerated Linear Codes for PCGs and ZK
Vladimir Kolesnikov, Stanislav Peceny, Rahul Rachuri, Srinivasan Raghuraman, Peter Rindal, and Harshal Shah
Linear error-correcting codes with fast encoding and high minimum distance are a central primitive across modern cryptography. They appear prominently in at least two domains: (1) pseudorandom correlation generators (PCGs), which enable sublinear-communication generation of correlations such as oblivious transfer and vector oblivious linear evaluation, and (2) zero-knowledge proof systems, where linear-time encoders underpin proof soundness and scalability. In both settings, the prover or sender must multiply by a large generator matrix $\mathbf{G}$, often with dimensions in the millions, making computational efficiency the dominant bottleneck. We propose a generalized paradigm for building crypto-friendly binary codes with provable minimum distance. Roughly speaking, these codes are based on randomized turbo codes such as repeat-accumulate codes. We prove linear asymptotic minimum distance and compute the exact expected weight spectrum for concrete sizes. We observe that our codes approach the Gilbert-Varshamov distance bound and outperform prior constructions. We construct several novel codes, the most promising of which we call Block-Accumulate codes. Among codes with provable distance, our code is $8\times$ faster than the state of the art on a CPU and $50\times$ faster on a GPU; even against aggressive parameters with conjectured distance, it is $3\times$ and $20\times$ faster, respectively. Under these parameters, this yields overall PCG speedups of $2.5\times$ on the CPU and $15\times$ on the GPU, achieving a projected 200$+$ million OTs per second, or about 100 million binary Beaver triples per second, on the GPU (excluding the one-time 10 ms GGM seed expansion). We also observe a $2\times$ encoding speedup and half the peak memory consumption in the Blaze zero-knowledge (PCS) scheme of Brehm et al. (EUROCRYPT~'25).
Last updated:  2026-08-19
Prop RFQ: Proprietary Request for Quote as Pressure-Aware Exit Pricing for Redeemable Real-World Asset Tokens
Daniel Rolnik, Theodore Georgas, and Ivan Homoliak
Redeemable real-world asset tokens can trade onchain faster than their backing assets can be sold or settled. An immediate-exit facility cannot treat reported net asset value (NAV) as fully liquid. Within our scope, the mechanisms we compare do not jointly provide permissionless access, order-splitting resistance, and favorable small exits. In this paper, we propose a Proprietary Request for Quote (Prop RFQ), an onchain facility that prices exits against available reserves and mitigates, but does not eliminate, split-order incentives. Its quote combines NAV, an order-size curve, a funded-liquidity wall, decaying sell pressure, and a cadence response to repeated sells. The design seeks to keep isolated small exits useful while limiting reserve depletion and gains from splitting a concentrated exit. We evaluate the implemented Solana pricing path with fixed workloads and ablations, then sweep 15,120 parameter configurations. At the reference parameters, cadence reduces aggregate split advantage by 9.67% against matched pressure-only pricing, improves 34 of 40 split workloads, and raises worst-case reserve remaining from 10.49% to 17.66%. No simple policy or Prop RFQ ablation in our comparison dominates the reference configuration on common metrics. After correcting epoch rollover, implementation quotes match the explicitly rolled model at every tested recovery point. However, low-value sells enable cheap cadence griefing.
Last updated:  2026-08-19
Noisy Subset Product
Trey Li
In 1978, Yao studied the subset product problem and proved its NP-completeness. Later, Galbraith, Zobernig, and Li considered a prime-based modular variant and studied its average-case hardness. More recently, Li introduced the general problem of unknown-coefficient multivariate exponential system solving and studied its hardness systematically in an abstract setting. Li's framework implies a noisy modular variant of subset product as a special case. In this paper, we study this noisy subset product problem in a concrete setting, prove equivalence relations among several related variants, and use these results to construct a post-quantum non-alternating key exchange scheme, with a natural one-sided interpretation as a key encapsulation mechanism. Unlike other noise-based schemes, such as lattice-based schemes, our construction does not rely on an additional reconciliation plaintext. Instead, the receiver is able to recover the sender's ephemeral secret key itself. Moreover, we reduce indistinguishability security directly to the search version of the noisy subset product problem, without relying on a separate decisional assumption.
Last updated:  2026-08-19
AutoDiVer: Automatically Verifying Differential Characteristics and Learning Key Conditions
Marcel Nageler, Shibam Ghosh, Marlene Jüttler, and Maria Eichlseder
Differential cryptanalysis is one of the main methods of cryptanalysis and has been applied to a wide range of ciphers. While it is very successful, it also relies on certain assumptions that do not necessarily hold in practice. One of these is the hypothesis of stochastic equivalence, which states that the probability of a differential characteristic behaves similarly for all keys. Several works have demonstrated examples where this hypothesis is violated, impacting the attack complexity and sometimes even invalidating the investigated prior attacks. Nevertheless, the hypothesis is still typically taken for granted. In this work, we propose AutoDiVer, an automatic tool that allows to thoroughly verify differential characteristics. First, the tool supports calculating the expected probability of differential characteristics while considering the key schedule of the cipher. Second, the tool supports estimating the size of the space of keys for which the characteristic permits valid pairs, and deducing conditions for these keys. AutoDiVer implements a custom SAT modeling approach and takes advantage of a combination of features of advanced SAT solvers, including approximate model counting and clause learning. To show applicability to many different kinds of block ciphers like strongly aligned, weakly aligned, and ARX ciphers, we apply AutoDiVer to GIFT, PRESENT, RECTANGLE, SKINNY, WARP, SPECK, and SPEEDY.
Last updated:  2026-08-19
Trapdoor one-way functions from tensors
Anand Kumar Narayanan
Update: We retract the claim that main construction in the paper is cryptographically secure. In particular, the trapdoor functions generated in Algorithm 1 from three dimensional tensors are efficiently distinguishable from random tensors, since their two dimensional slices (in the longest dimension) are rank deficient. We leave the article as a record, in hopes that some of the techniques are useful in other contexts. Weyman and Zelevinsky generalised Vandermonde matrices to higher dimensions, which we call Vandermonde-Weyman-Zelevinsky tensors. We generalise Lagrange interpolation to higher dimensions by devising a nearly linear time algorithm that given a Vandermonde-Weyman-Zelevinsky tensor and a sparse target vector, finds a tuple of vectors that hit the target under tensor evaluation. Tensor evaluation to us means evaluating the usual multilinear form associated with the tensor in all but one chosen dimension. Yet, this interpolation problem phrased with respect to a random tensor appears to be a hard multilinear system. Leveraging this dichotomy, we propose preimage sampleable trapdoor one-way functions in the spirit of Gentry-Peikert-Vaikuntanathan (GPV) lattice trapdoors. We design and analyse ``Hash-and-Sign'' digital signatures from such trapdoor one-way functions, yielding short signatures whose lengths scale nearly linearly in the security parameter. We also describe an encryption scheme. Our trapdoor is a random Vandermonde-Weyman-Zelevinsky tensor over a finite field and a random basis change. We hide the Vandermonde-Weyman-Zelevinsky tensor under the basis change and publish the resulting pseudorandom tensor. The one way function is the tensor evaluation derived from the public tensor, restricted so as to only map to sparse vectors. We then design the domain sampler and preimage sampler demanded by the GPV framework. The former samples inputs that map to uniform images under the one-way function. The latter samples preimages given supplementary knowledge of the trapdoor. Preimage sampling is a randomised version of interpolation and knowing the basis change allows efficient translation between interpolation corresponding to the public and trapdoor tensors. An adversary seeking a preimage must solve a pseudorandom multilinear system, which seems cryptographically hard.
Last updated:  2026-08-19
From Mechanical Lock-Picking to Autonomous Driving Deception: A Comprehensive Review of Vehicle Attacks, Cyberattacks, and Defenses
Karim Lounis
Modern vehicles have evolved into highly interconnected Software-Defined Cyber-Physical Systems (CPS), integrating embedded electronics, wireless communications, artificial intelligence, and Advanced Driver Assistance Systems (ADAS). While these technological advances have significantly improved vehicle safety, efficiency, and driving automation, they have also introduced a rapidly expanding cyber-physical attack surface. Consequently, automotive cybersecurity has become an active research area encompassing attacks on physical vehicle components, access and authentication mechanisms, electronic and software systems, and autonomous driving technologies. Although numerous studies and surveys have investigated these security threats, the existing literature remains fragmented, often focusing on specific vehicle subsystems or individual technologies. This paper presents a comprehensive survey of attacks and defense mechanisms targeting modern vehicles through a unified and orthogonal taxonomy that classifies the literature into four research directions: attacks on vehicle body and physical systems, vehicle access and engine start systems, electronic and software systems, and ADAS and autonomous driving systems. For each direction, the associated security issues, representative attacks, and existing countermeasures are systematically reviewed and analyzed. Furthermore, the survey identifies current research trends, highlights existing research gaps, and discusses future challenges toward the development of comprehensive and resilient automotive security solutions.
Last updated:  2026-08-19
Copy-Protection with Correlated Challenges: Point Functions and More via Decisional Coset Monogamy
Amit Behera, Alper Çakan, and Vipul Goyal
Copy-protection is one of the main applications of quantum information in cryptography. In copy-protection, we encode a functionality in a reusable quantum state so that it cannot be split into two states (called freeloader adversaries) that remain simultaneously useful. Despite a long line of research, previous works have only been able to show security with respect to independently sampled challenges in the plain-model. However, arguably a more natural security notion considers the two freeloader adversaries receiving the same challenge. This so-called identical-challenge security notion is also connected to other fundamental quantum cryptographic primitives such as unclonable bits (i.e. unclonable encryption) and copy-protection of point functions. In this work, first we make progress on the definitional foundations of these primitives, and then prove security in the plain model for our new stronger definitions, in particular also resolving the question of copy-protection with identical challenges and copy-protection of point functions. In more detail, we obtain the following results. -- Copy-protecting decryption keys (Single-decryptor encryption).} We define a new natural security notion for single-decryptor encryption (SDE) called {correlated challenge security}, and show that implies all previous security definitions for SDE, including identical-challenge security. Then, we prove that, assuming indistinguishability obfuscation (iO) and one-way functions, the SDE construction of Kitagawa and Yamakawa (TCC'25) satisfies correlated challenge security. We also provide an almost complete characterization of the relationship among previous SDE security notions. --Copy-Protecting General Functionalities with Correlated Challenges. We define correlated challenge unclonable puncturable obfuscation (UPO), allowing arbitrary correlations among challenge points and puncturing bits, plus auxiliary information before and after splitting. Security requires only conditionally uniform bits and $\lambda^c$ average conditional min-entropy in each point separately, for any constant $c>0$; thus, in particular the challenge points may be identical. Assuming polynomially secure post-quantum iO and quantum-hard LWE, we construct correlated UPO for arbitrary polynomial-size keyed circuits with input length at least $\lambda^c$, answering the open question of Ananth, Behera, Huang, Kitagawa, Yamakawa (EUROCRYPT'26) and Çakan-Goyal (EUROCRYPT'26). --Applications Our results yield the first plain-model copy protection for point functions, $k$-point functions, and compute-and-compare programs under natural security definitions, and identical-challenge copy protection for general puncturable functionalities. The technical core of our results is a new decisional monogamy theorem for coset states, which both simplifies the proofs and generalizes the results of existing copy-protection constructions, which may be of independent interest.
Last updated:  2026-08-19
A Descent to Hades: Attacks on PKP and PEP over Extension Fields
Alessandro Budroni, Jesús-Javier Chi-Domínguez, Jorge Chavez-Saab, and Andre Esser
The Permutation Code Equivalence Problem (PEP) and Permuted Kernel Problem (PKP) are two notorious computational problems over linear codes used for building post-quantum digital signature schemes. Although traditionally analyzed over prime fields, recent proposals, such as the signature schemes PERK and SETH, have considered extension fields to improve efficiency and compactness. In this work, we analyze the hardness of solving PKP and PEP when instantiated over field extensions. For binary field extensions, by exploiting a reduction to a structured variant of the Regular Syndrome Decoding Problem (RSD), we uncover new polynomial-time parameter regimes for both PKP and PEP, including families of self-orthogonal PEP instances and all self-dual instances over extensions of degree $\nu>4$. We also adapt the permutation-based Regular-ISD algorithm of Esser and Santini for RSD (CRYPTO '24) to PKP-derived instances, and uncover regimes of parameters for which it improves upon the state-of-the-art. Moreover, we present a reduction from a broad family of PEP instances over extension fields with odd characteristic to the Graph Isomorphism Problem, yielding a polynomial-time algorithm to solve those instances. Overall, our results invalidate the use of PEP over extension fields for most of the scenarios, and provide novel insights into the security of PKP over extension fields.
Last updated:  2026-08-19
Adapting AES-Oriented Optimizations to Rijndael-256: Cortex-M4, ARMv8-A, and CUDA
Siwoo Eum, Minho Song, Minjoo Sim, Anupam Chattopadhyay, and Hwajeong Seo
Rijndael-256 (R256), the 256-bit block variant of the Rijndael family, is practically relevant in ongoing NIST draft discussions on wider-block standardization and in several NIST post-quantum signature candidates. Relative to AES, R256 combines a wider $4\times8$ state with non-standard ShiftRows offsets $(0,1,3,4)$, invalidating key assumptions behind many AES-oriented optimizations. We study how these mismatches manifest on three targets and develop three corresponding adaptation strategies: wider classical bitslicing on Cortex-M4, Reuse with Reshuffling on AArch64, and Amortize the Mismatch on CUDA. This yields a bitsliced Cortex-M4 implementation with secret-independent control flow and memory access patterns (4,962 cycles/block), an AArch64 pre-shuffle design that reuses the AESE instruction with AddRoundKey folded in (up to 6,520 MB/s), and a CUDA shared-memory T-table implementation reaching 81.16 GiB/s; we report throughput on AArch64 and CUDA because per-block cycle measurement is not directly available on those platforms. Replacing the R256 cryptographic core in four NIST PQC reference codebases on Apple M2, with minimal integration changes where needed, yields signing speedups of $1.18\times$--$114.3\times$ and verification speedups up to $155.6\times$, with the end-to-end gain governed by each scheme's R256 fraction.
Last updated:  2026-08-19
Key Recovery from Residue-Confined Errors in the Pradhan CRT-RLWE Construction
Lukasz Olejnik and Bartosz Naskrecki
We show that the CRT-FHE scheme of Pradhan et al. is insecure for laws within its assumed error distribution range. The secret key follows from the public key by a single ring inversion whenever the public multiplier is a unit. The plaintext is recovered from any ciphertext under such a law without the secret key, for every multiplier, giving chosen-plaintext advantage $1/2$. We further show that the transformation from ordinary Ring-LWE to CRT-RLWE does not preserve the error distribution, so it does not establish that CRT-RLWE is at least as hard as Ring-LWE. One mechanism underlies both. The Chinese remainder theorem (CRT) function is reduced modulo $p_1p_2$ while its output is used modulo a coprime modulus $q$, so under every zero-preserving section an error in $p_2\mathcal{R}$ encodes to zero. The law $p_2B_1$ is so confined, meets the stated conditions, and decrypts correctly. Confinement is not a weakness of scale: scaling any baseline law by $p_2$ leaves its ordinary Ring-LWE problem exactly equivalent, while the reduced encoder destroys every error it produces. The reduction discrepancy is a multiple of $p_1p_2$ and not of $q$, so the small-error premise of the proof cannot remove it, and at the reported parameters a single error coefficient refutes the identity while satisfying that premise. The centered binomial $B_2$ separates the coefficient laws at total variation distance $3/8$, and at the reported dimension that distance between the induced polynomial laws is exponentially close to one.
Last updated:  2026-08-19
Pacmann: Efficient Private Approximate Nearest Neighbor Search
Mingxun Zhou, Elaine Shi, and Giulia Fanti
We propose a new private Approximate Nearest Neighbor (ANN) search scheme named Pacmann that allows a client to perform ANN search in a vector database without revealing the query vector to the server. Unlike prior constructions that run encrypted search on the server side, Pacmann carefully offloads limited computation and storage to the client, no longer requiring computationally-intensive cryptographic techniques. Specifically, clients run a graph-based ANN search, where in each hop on the graph, the client privately retrieves local graph information from the server. To make this efficient, we combine two ideas: (1) we adapt a leading graph-based ANN search algorithm to be compatible with private information retrieval (PIR) for subgraph retrieval; (2) we use a recent class of PIR schemes that trade offline preprocessing for online computational efficiency. Pacmann achieves significantly better search quality than the state-of-the-art private ANN search schemes, showing up to 2.5$\times$ better search accuracy on real-world datasets than prior work and reaching 90\% quality of a state-of-the-art non-private ANN algorithm. Moreover on large datasets with up to 100 million vectors, Pacmann shows better scalability than prior private ANN schemes with up to $63\%$ reduction in computation time and $24\%$ reduction in overall latency.
Last updated:  2026-08-19
How Compact Can NTRU Encryption Be? Heuristic Frontiers and Practical Schemes
Yijian Liu, Yu Zhang, Xianhui Lu, Yao Cheng, and Yongjian Yin
NTRU is one of the longest-tested lattice-based public-key encryption families and is often viewed as a compact alternative to (R/M)-LWE. Yet, after three decades of research, its potential for compactness remains an open area for further exploration: recent designs such as NEV (Asiacrypt 2023) and DAWN (Asiacrypt 2025) suggest that there is still room for improvement. This raises a natural question: Has NTRU reached its compactness limit? If not, how compact can it be while still remaining secure and efficient? Motivated by this question, we aim to formalize a unified relationship between compactness and efficiency under the required security level. We present a common two-stage view of NTRU decryption. In the first stage, the decoder constructs a small set of candidate wrap-around errors. In the second stage, it verifies these candidates using either algebraic redundancy or trapdoor-derived distributional information. We introduce Free Candidate Localization (FCL), a generic first-stage method that ranks coordinates by their proximity to the centered boundary. FCL could be used in most lattice-based encryptions; we instantiate it in ML-KEM to achieve a $10\%$ smaller ciphertext at the cost of a $5\%$ slower overall runtime in the reference C implementation under NIST-I. We organize modern NTRU encryptions into two frameworks. NTRU with Encoding leverages algebraic structure via auxiliary quotient rings. NTRU with Trapdoor exploits geometric structure through the NTRU trapdoor, then verifies candidate corrections using distributional tests. These frameworks give a common language for existing NTRU designs and for the compactness searches in this paper. Within an explicit search model, we derive heuristic compactness frontiers for both frameworks. At NIST-I, the encoding frontier yields a total public-key plus ciphertext size of 812 bytes, and the trapdoor frontier yields a size of 754 bytes, $15\%$/$21\%$ smaller than the previous lowest size of 964 bytes in DAWN. Furthermore, we propose END, an instantiation of NTRU with Trapdoor plus FCL. At NIST-I, \textsf{END} has a 384-byte ciphertext, which is exactly half the size of the 768-byte ciphertext of ML-KEM-512, and is $12-19\%$ smaller than the shortest prior NTRU-style ciphertexts in BAT (TCHES 2022) and DAWN. In our reference C implementation, the combined encapsulation and decapsulation cost of END-512 is about $3\%$ higher than that of ML-KEM-512.
Last updated:  2026-08-19
Indifferentiability of Public-Key Encryption: Theory Meets Practice
Taiyu Wang, Cong Zhang, Hong-Sheng Zhou, Jiayi Ai, Zhihong Jia, Wenli Wang, Jian Liu, Xin Wang, Li Lin, Kui Ren, and Chun Chen
Public-key encryption (PKE) is a fundamental primitive in modern cryptography, and many PKE schemes have been standardized and widely deployed. To reason about security in complex and highly compositional environments, Zhandry and Zhang (CRYPTO 2020) initiated the study of indifferentiability for public-key cryptosystems. However, their construction for PKE departs substantially from the design paradigms used in practice, and to date no practical public-key encryption schemes are known to achieve indifferentiability. In this work, we further investigate indifferentiability for public-key encryption, asking whether it can be achieved for practical, standardized schemes. We provide evidence that the answer is yes: slightly augmented standardized group-based encryption schemes can indeed achieve provable indifferentiability. Our contributions are threefold: -- Identifying a barrier in the existing ideal PKE model: We revisit the ideal PKE definition of Zhandry and Zhang and identify an artificial requirement---namely, pseudorandom public keys and ciphertexts---that constitutes an inherent barrier to achieving indifferentiability from groups. -- Redefining the idealized model for PKE: We propose a revised ideal PKE model that removes this pseudorandomness requirement, thereby opening the possibility of achieving indifferentiable public-key encryption from practical group-based schemes. --Making standardized PKE indifferentiable: We consider two public-key encryption schemes standardized in ISO/IEC 18033-2---Elliptic Curve Integrated Encryption Scheme (ECIES) and Public-Key Secure Encryption (PSEC)---and show that, under slight augmentation, both are indifferentiable from our revised ideal PKE. In conclusion, our work advances the development of indifferentiable yet practical public-key encryption schemes, enabling future research and protocol design to build on standard PKE schemes while enjoying strong composability guarantees.
Last updated:  2026-08-18
New Techniques for Fast and Shallow FHE Bootstrapping and Beyond
Aayush Jain, Huijia Lin, Zeyu Liu, and Sagnik Saha
The main barrier to practical fully homomorphic encryption remains the latency and cost of bootstrapping, the ciphertext refresh step that enables unbounded computation. We design new methods that reduce both the latency and the circuit depth of bootstrapping in the FHEW/TFHE framework, which represents the state-of-the-art for lightweight bootstrapping and for computing deep and unstructured Boolean functions over encrypted data. Our first contribution leverages LWE with a sparse small-norm secret, an assumption known to be equivalent to standard LWE and already widely used in FHE constructions. For an LWE secret of dimension $n$ and Hamming weight $h$, we obtain bootstrapping procedures whose arithmetic complexity decreases from $\tilde O(n^2)$ to $\tilde O(n h)$ $\mathbb{Z}_q$ multiplications while preserving the same asymptotic number of additions. Concretely, this yields a $4.5$--$7.5\times$ practical speedup for gate and functional bootstrapping over the state-of-the-art OpenFHE implementation. Our second contribution introduces a new RLWE variant with structured secrets, called \emph{\mainrlwevarianttext}, and uses it to significantly reduce the circuit depth of FHEW/TFHE bootstrapping via a new relinearization-free BV multiplication technique. In concrete parameter settings, this reduces the number of sequential NTT/INTT layers required for bootstrapping to just 3, compared to more than 500 in standard FHEW/TFHE, while keeping the overall number of unit 32 or 64-bit word operations comparable to standard FHEW/TFHE bootstrapping. This substantial depth reduction suggests the potential for significantly lower bootstrapping latency on parallel, high-throughput architectures such as GPUs. Finally, we analyze the security of the new RLWE assumption underlying our depth reduction, including worst-case-to-average-case and search-to-decision reductions, as well as evaluations against concrete attacks.
Last updated:  2026-08-18
Controlled Differentials in Key-Then-Hash Functions: No Absolute Weak-Key Classes and Key Recovery through MACs
Jonathan Fuchs
In their CRYPTO 2023 paper, Fuchs, Rotella, and Daemen reduced the universality of key-then-hash (KTH) functions built from public permutations to differential properties of the underlying permutation. Subsequent work analyzed KTH Parallel with fixed-length public functions and related variable-length universality bounds [12,13]. We develop a corresponding framework for key-recovery attacks on KTH-based MACs. We first revisit the weak-key classes identified by Handschuh and Preneel for NH, NMH*, WH, and Square Hash. For the KTH attacks considered here, these classes are solution sets of controlled differentials. These translated sets may still satisfy HP08's broad operational weak-key criterion. Our claim is different: KTH offset invariance translates every such solution set through every absolute key with unchanged probability and oracle-query cost, so the attacks do not identify intrinsically exceptional absolute keys. For these controlled attacks, this gives a strong KTH form of the UHF "regularity" sought by Handschuh and Preneel: the complete attack profile is homogeneous over absolute key space. We then show that, for every fixed-length KTH map with no probability-one nonzero differential, any two distinct key-prefix candidates can be distinguished by a generalized differential test. If its generalized derivatives are affine, one retained successful fixed-output equal-length differential leaves an affine coset and at most \(\lceil \log_2 \#S_0 \rceil\) further suitably chosen successful events determine the prefix, under the stated computational and interface assumptions. Finally, we apply the framework to NH and Xoodoo[3]. Under reusable-reference WC(S), unequal-length NH image tests simultaneously test one candidate for each word of a multiplication pair and recover both \(w\)-bit words with one generation query and at most \(2^w+1\) verification queries, approximately half the verification-query cost of the Handschuh-Preneel recovery. For Serial[Xoodoo[3]], published three-round trails yield recovery of a reusable 384-bit KTH key block in \(2^{42}\) expected differential trials, or \(2^{43}\) MAC-oracle calls.
Last updated:  2026-08-18
A Unified Framework for Contract-Validated Benchmarking of Zero-Knowledge Proving Systems
Matej Hulek, Martin Peresini, and Ivan Homoliak
Zero-knowledge proofs are an operational infrastructure for rollups, private payments, verifiable execution, and zkVM applications. We treat them as succinct proofs of validity whose privacy properties depend on the system and the mode of use. Published benchmarks often compare different workloads, proof modes, and hardware paths, which makes their results hard to interpret. This work presents a unified host-agent framework for benchmarking heterogeneous proving systems under a common execution and reporting method. Each prover runs in an isolated containerized agent and is selected through a scheme-adapter layer. The agent reports canonical JSON artifacts linked to a hashed run manifest and workload-specific semantic contracts. The host checks the public semantic fields and the agent's verification flag to ensure backends are compared on the same declared public claim, even when their circuits, traces, or guest pipelines differ. We evaluate circuit-based, transparent, GPU-accelerated, folding, and zkVM systems: Groth16, ICICLE, Halo2, Plonky3, Winterfell, Nova, RISC Zero with CUDA and Groth16 wrapping, and SP1 with and without AVX. The suite uses six primary workloads with comparable semantics, together with secondary hash workloads that expose specialization. No prover family dominates all deployment criteria. At 8 CPU cores, Plonky3 and Winterfell have the smallest across-case proving-time and RAM figures. Groth16 and ICICLE produce sub-kilobyte proofs. Winterfell has the lowest host verification time. zkVM systems trade larger proofs and higher memory for programmability. On the Merkle-path micro-benchmark, pairing artifacts remain sub-kilobyte, whereas wrapping a zkVM receipt yields a Groth16-sized artifact at a high proving cost. GPU acceleration helps most after fixed setup costs are amortized. The main contribution is methodological: validate the statement being proved, disclose the security profile, and report resource limits in addition to proving time.
Last updated:  2026-08-18
A Controlled Case Study of Design Trade-offs in DeFi Lending Protocols
Jan Findra, Zdenek Lapes, and Ivan Homoliak
Decentralized lending protocols encode credit markets as smart contracts whose design choices affect gas cost, capital efficiency, liquidation behavior, and risk allocation. We compare Aave V3, SparkLend, Compound III, and Morpho Blue in matched Ethereum fork tests with wstETH collateral, USDC debt, and one fixed chain state. The tests measure call-path gas, annualized rates, thirty-day debt growth, maximum borrow capacity, and liquidation outcomes. It is important to note that the observed orderings for gas costs and rates are specific to this test artifact and could change under different collateral assets or utilization regimes. Within this setting, Morpho Blue has the lowest measured interaction call-path gas and highest borrow capacity, while shifting risk selection to isolated permissionless markets. Furthermore, Morpho Blue's evaluation uses a deployed market for rate measurements but a constructed market for liquidation testing. Aave V3 and SparkLend provide broader pooled-market abstractions with higher measured call-path gas. Compound III simplifies borrowing around one base asset per market; its low-gas absorb step is offset by a separate buy collateral liquidation path. We provide a Foundry-based Ethereum-fork test suite for reproducing these measurements and comparing lending-design trade-offs.
Last updated:  2026-08-18
Jacobi Signatures, Revisited
Yansong Feng
We remove the Boneh--Lipton conjecture from the proof of Corrigan-Gibbs and Wu (CRYPTO~2024) that Jacobi signatures modulo $N=p^2q$ are one-way. This relates the one-wayness of the pseudorandom generator proposed by Damg{\aa}rd in 1988 to a standard number-theoretic problem alone.
Last updated:  2026-08-18
Proof-of-Uniqueness: Sybil-Resistant Privacy-Preserving Decentralized Identity through Threshold-OPRF and zk-SNARK Registry
Adam Vozda, Martin Peresini, Juraj Mariani, and Ivan Homoliak
Several decentralized applications and blockchains, such as blockchain-based voting systems or Proof-of-Social-Capital, require a strict one-account-per-person policy, yet public identity records often expose sensitive attributes or enable offline attribution. This work presents a Proof-of-Uniqueness blockchain-based registry that composes an issuer-signed verifiable credential, two zero-knowledge proofs, a threshold verifiable oblivious pseudorandom function (vOPRF), and a smart contract. The first proof authorizes a blinded evaluation of an issuer's certified canonical identifier, and the second validates the OPRF transcript and binds the resulting global nullifier to a wallet. The design further binds issuer authorization, credential status, validity bounds, canonical encoding, and replay state. Its person-level guarantee is conditional on a stable injective identifier within a coordinated issuance namespace and a stable, valid OPRF key. Confidentiality holds against public observers and against fewer than the OPRF threshold of nodes, but not against an issuer that actively probes its own identifiers. Our prototype couples Noir and UltraPlonk circuits, three local threshold OPRF nodes, and a Solidity contract. For one fixed-schema credential input, it derives a single wallet-bound deterministic nullifier, verifies a real 2,144-byte proof on-chain, and rejects a repeated nullifier with $O(1)$ lookups. One real enrollment consumes 615k gas, and proof construction takes about 65 seconds on one desktop software thread.
Last updated:  2026-08-18
Data-Dependent Memory-Hard Functions: Sustained Space and Cumulative Complexity Trade-offs in the Parallel Random Oracle Model
Jeremiah Blocki and Blake Holman
Memory-Hard Functions (MHFs) are a cryptographic primitive designed to protect passwords and other low-entropy secrets against brute-force attacks. The strongest and most natural formalization of memory-hardness is sustained space complexity (SSC), which measures how long an attacker's memory remains above a given threshold. Ideally, one would like to ensure that any parallel attacker must sustain $\Theta(N)$ memory for $\Theta(N)$ steps, while the function can also be computed in sequential time $\Theta(N)$. Unfortunately, this goal is impossible to achieve. Thus, the appropriate objective is to establish strong tradeoffs between sustained space complexity and cumulative memory complexity (CMC), another strong notion of memory hardness. Blocki and Holman (CRYPTO 2022) achieved strong SSC/CMC tradeoffs in the dynamic pebbling model, but their construction relied on expensive combinatorial graphs, and the pebbling abstraction does not rule out more efficient attacks in the stronger Parallel Random Oracle Model (PROM). We address both limitations. We construct a new data-dependent MHF (dMHF), DEGSample, and prove the first SSC/CMC tradeoff for dMHFs directly in the PROM. In the dynamic pebbling model, DEGSample achieves the same ideal tradeoff as prior work: any dynamic pebbling strategy either sustains $\Omega(N)$ memory for $\Omega(N)$ steps or incurs a maximal CMC penalty $\Omega(N^{3-\epsilon})$. In the PROM, we prove that any attacker either sustains $\Omega(N)$ memory for $\Omega(N)$ steps or incurs a steep CMC penalty of at least $\Omega(N^{2.5-\epsilon})$. To prove this, we introduce a new graph property called ancestral robustness and show that, together with another property called fractional depth-robustness, it suffices to obtain strong PROM tradeoffs via a natural dynamization procedure to turn the graph into a dMHF. The PROM lower bound combines a time-space trade-off argument with an extraction procedure that converts any PROM execution into a cost-equivalent pebbling of the realized graph.
Last updated:  2026-08-18
NeutronNova: Group-based folding done right
Abhiram Kothapalli and Srinath Setty
A folding scheme reduces the task of checking multiple NP instances into checking a single instance, providing an efficient route to incrementally verifiable computation (IVC). We identify five desirable properties of a practical folding scheme: constant recursion overheads, multi-folding, linear scaling with the number of instances, no extraneous commitments, and modularity. No existing scheme achieves all five simultaneously. We introduce NeutronNova, the first folding scheme to achieve all five. The prover's work is dominated by the cost to commit to its witness -- with no extraneous commitments -- and the recursive verifier performs only three group scalar multiplications and a constant number of hash computations. We construct NeutronNova modularly using the reductions of knowledge (RoK) framework around a core relation called zero-check, and build folding schemes for circuit satisfiability (CCS), grand products, and lookups by reducing each to zero-check. In experiments, NeutronNova folds a SHA-256 circuit with $2^{20}$ constraints in 91 ms, a ${\approx}10\times$ improvement over Nova. Several subsequent works have used NeutronNova to achieve new results, including space-efficient SNARKs with optimal prover time, packed sum-check protocols over small fields, and client-side zero-knowledge proofs with low end-to-end latency.
Last updated:  2026-08-18
Elementary-Vector Modeling for Shorter VOLE-Based Signatures from SD and PKP
Boyuan Gao, Zongyang Zhang, Weihan Li, Jianwei Liu, and Jianting Ning
Zero-knowledge proofs based on VOLE have recently become a promising approach for designing post-quantum signature schemes. Such schemes are constructed by having a signer prove knowledge of a secret input for a prescribed one-way function. In this work, we optimize VOLE-based signature schemes from syndrome decoding (SD) and the permuted kernel problem (PKP). Despite relying on different one-way functions, these schemes share a common modeling method. Elementary vectors are compressed into shorter witnesses and then reconstructed through low-degree polynomials. We propose a unified framework for elementary-vector encoding and reconstruction. By choosing different parameters, this framework captures previous modeling approaches for SD and PKP as special cases. Based on this framework, we propose an optimized encoding and reconstruction approach that reduces the extended witness size and hence the final signature size. At NIST Level I security, our SD- and PKP-based schemes achieve “signature + public key” sizes of 3,496 and 3,341 bytes, respectively, improving over the corresponding 3,775 bytes of SDitH v2.0 and 3,577 bytes of PERK v2.2. Furthermore, we construct a 3,673-byte post-quantum ring signature for rings of 2^20 members, which is 27% and 70% smaller than those of Chiang et al. (CCS ’25) and BLOOM (ASIACRYPT ’22), respectively.
Last updated:  2026-08-18
Efficient Private Set Union from Multi-Query Oblivious Membership Transfer
Yewei Guan, Hua Guo, Man Ho Au, Jiarong Huo, and Renheng Wang
Private Set Union (PSU) allows two parties to compute the union of their private sets while revealing nothing beyond the union. Existing PSU protocols mainly follow two paradigms: reverse private membership test (RPMT) and invertible Bloom lookup table (IBLT). IBLT-based protocols achieve linear complexity using lightweight symmetric-key operations and offer excellent concrete efficiency. RPMT, on the other hand, provides a more general membership-testing functionality that can serve as a reusable building block for PSU and other private-set computations. However, existing RPMT-based protocols either rely on costly building blocks, such as public-key operations and generic secure two-party computation, or incur super-linear complexity. This raises a natural question: can the generality of the RPMT paradigm be retained while matching the asymptotic and concrete efficiency of IBLT-based PSU? In this work, we answer this question affirmatively by introducing a lightweight mechanism for multi-query membership testing. Our mechanism yields a concretely efficient multi-query RPMT (mqRPMT) protocol that is useful beyond PSU and may be of independent interest. Building on this protocol, we construct a PSU protocol with linear computation and communication complexity. Our construction avoids expensive public-key operations and generic secure two-party computation, relying instead on efficient symmetric-key primitives. We extensively evaluate our protocol against state-of-the-art PSU protocols from both the RPMT and IBLT paradigms. Compared with the leading RPMT-based PSU protocol from PKC 2024, our construction is $41.7\times$ $-$ $48.9\times$ faster in the LAN setting and up to $4.5\times$ faster in WAN settings. Compared with the leading IBLT-based PSU protocol from EUROCRYPT 2026, our protocol achieves competitive and, in several metrics, superior performance: it is $1.9\times$ $-$ $2.5\times$ faster in LAN settings and reduces communication by up to $1.4\times$. These results demonstrate that the broader applicability of the RPMT abstraction need not come at the cost of asymptotic or concrete efficiency.
Last updated:  2026-08-18
A New CRT-based Fully Homomorphic Encryption
Anil Kumar Pradhan, Abhraneel Dutta, Hansraj Jangir, and Dipayan Das
The idea of computing on encrypted data without decryption dates back to the notion of privacy homomorphisms introduced by Rivest, Adleman, and Dertouzos (1978). Their proposals built using the elegant structure of Chinese Remainder Theorem (CRT), were later shown to be insecure under simple known-plaintext attacks. Subsequent CRT-based fully homomorphic encryption (FHE) over the integers addresses this algebraic transparency by injecting noise and basing security on approximate common divisor–type assumptions, but the resulting designs are burdened by large public keys and costly ciphertext refresh procedures. In this work, we develop a new CRT-based FHE scheme whose security relies on the Ring-LWE (RLWE) hardness assumption. For this purpose, we introduce the CRT-RLWE problem. We show that the problem is at least as hard as the RLWE, thereby positioning our construction within the established post-quantum security landscape of RLWE-based cryptography. Our scheme retains an explicit CRT embedding, separating a message component modulo a prime-power plaintext modulus and an auxiliary CRT component, while using RLWE-style key and ring arithmetic for compactness and efficiency. Finally, we make it fully homomorphic by using a new bootstrapping procedure, that adopts the recryption paradigm for BGV/BFV schemes utilizing the linear transformation and digit extraction techniques.
Last updated:  2026-08-18
UFOs: An Ultra-fast Toolkit for Multiparty Computation of Small Elements
Jiacheng Gao, Moyang Xie, Yuan Zhang, and Sheng Zhong
In many secure multiparty computation (MPC) applications, the semantic domains of some operands are much smaller than the underlying arithmetic field or ring. The arithmetic domain is typically chosen to meet computation and security requirements (e.g., a 128-bit prime field), whereas the actual data may consist of only a few bits, such as 4-bit values in a 16-category classification task. This mismatch can lead to substantial communication and computation overhead in existing MPC protocols, which typically treat data of different ranges uniformly. We introduce UFO$_\mathrm{s}$, an ultra-fast toolkit for MPC on small elements, with optimized protocols for one-hot encoding, comparison, and digit decomposition. For $t=2^k$, our random one-hot vector generator attains, in the fan-in-two arithmetic-circuit model, the lower bounds of $t-\log t-1$ multiplication gates and $\lceil\log\log t\rceil$ multiplication depth. Our comparison protocol applies to any public small domain, while DigitDecomp avoids binary expansion and supports any public base $t>1$. Using these primitives, we construct a higher-radix sorting protocol for large field elements. Experiments confirm the resulting gains in random one-hot vector generation, digit decomposition, and sorting. In particular, our sorting protocol achieves a $3.4\times$ online and $1.4\times$ offline speedup over Hamada et al.'s radix-sort baseline when sorting $2^{16}$ elements among five parties.
Last updated:  2026-08-18
Improved Polynomial-Memory Algorithms via Nested Collision Search: Applications to Small Max-Norm LWE and Subset-Sum
Abul Kalam, Sudeshna Karmakar, and Santanu Sarkar
The Learning With Errors (LWE) problem with small max-norm secrets and errors forms the foundation of several practical lattice-based cryptographic schemes, including NTRU-based constructions and the recently standardized CRYSTALS-Kyber and CRYSTALS-Dilithium. While recent combinatorial attacks have significantly improved the asymptotic complexity of solving small max-norm LWE, the fastest known methods require prohibitively large memory, often comparable to their runtime. To address this issue, Esser et al. (ASIACRYPT~2023) introduced the first substantially improved polynomial-memory algorithms for recovering small max-norm LWE secrets via nested collision search. In this work, we further improve the asymptotic complexity of polynomial-memory attacks on small max-norm LWE. We introduce a refined nested collision search framework together with new representation structures that increase the number of valid representations while preserving polynomial-memory complexity. This leads to improved asymptotic runtimes across the entire range of relative secret weights. For uniformly random ternary secrets of length $n$, our best algorithm reduces the polynomial-memory runtime from $2^{0.926n}$ to $2^{0.8595n}$, corresponding to an asymptotic speedup of approximately $2^{0.0665n}$. We further extend our framework to the secret distributions used in CRYSTALS-Kyber and CRYSTALS-Dilithium, obtaining improved complexity exponents. Additionally, we apply the proposed refinement to the polynomial-memory nested collision search framework of Esser and May~(EUROCRYPT~2020) for random subset-sum problem, reducing its asymptotic runtime from $2^{0.645n}$ to $2^{0.6432n}$. Although the latter improvement is modest, it provides an independent application of our framework and demonstrates its applicability beyond the LWE setting.
Last updated:  2026-08-18
Matrix Hoeffding and Bernstein Bounds with Sharp Constants for Markov Chains
Zhao Song
Matrix concentration for Markov chains was initiated in the expander-walk setting by Garg, Lee, Song, and Srivastava'18 [GLSS18]. However, the constant obtained in [GLSS18] is quite loose, and it is natural to ask whether a tighter proof can yield the same constant as in the independent matrix concentration setting. In this paper, we provide a positive answer to this question. Our Hoeffding exponent is sharp, as shown by a scalar obstruction. Our Chernoff and Bernstein constants improve upon those in [GLSS18] and Neeman, Shi, and Ward'24 [NSW24], respectively.
Last updated:  2026-08-18
AFS: A Family of ARX-Based Large-State S-boxes with Exceptional Properties
Zhiguang Yan, Yongzhuang Wei, René Rodríguez-Aldama, and Enes Pasalic
Large-state ARX-based S-boxes have become a key component of modern lightweight cryptographic designs, yet deriving tight security bounds for their differential and linear properties remains challenging. In this paper, we study the security of Alzette, the 64-bit ARX-based S-box used in the SPARKLE permutation, and present a general framework for the analysis and design of large-state ARX S-boxes. We introduce SMCS, a hybrid search strategy that combines MILP-based optimization with SMT-based model checking, enabling the computation of tight bounds on maximum expected differential probabilities and linear correlations. Using SMCS, we refine existing bounds for Alzette and, for the first time, establish tight linear bounds (resp. differential bounds) for up to 15 rounds (resp. 14 rounds). Building on these results, we propose S-box configurational encoding, an automated design method for ARX-based S-boxes, and introduce a new family of S-boxes called AFS (ARX-Feistel Structure) with 32-bit and 64-bit instances. We show that selected AFS instances achieve strictly better resistance to single-trail differential and linear cryptanalysis than SPECKEY and Alzette, respectively, while preserving comparable hardware and software costs. Finally, we present the first bit-based SMT model for optimal long-trail decomposition and apply it to derive more accurate bounds for SPARX-128 and SPARKLE. Our results show that replacing the S-boxes with AFS instances yields substantial improvements in cryptanalytic security margins.
Last updated:  2026-08-17
On the Distribution of the Distances of Random Words
Benjamin E. Diamond and Angus Gruen
For each positive integer $c^*$, we construct an infinite sequence of Reed–Solomon codes $C \subset \mathbb{F}_q^n$, together with ball radii $z$, for which the proportion of $\mathbb{F}_q^n$ collectively covered by the radius-$z$ Hamming balls decays asymptotically more slowly than $\frac{n^{c^*}}{q}$ does. To pinpoint this decay rate, we develop various new, sharp combinatorial estimates, pertaining to the volumes of balls and their intersections. Our result proves that the capacity conjecture of Ben-Sasson, Carmon, Ishai, Kopparty and Saraf (J. ACM '23) is false. Our code families' relative rates converge to 0 and their relative radii converge to 1. We suggest avenues by the means of which the capacity conjecture might be resuscitated; roughly, we suggest that that conjecture be restricted to the case of families whose relative rates are bounded from below by a positive constant. Our work shows that many deployed SNARKs may be less secure than they were formerly—optimistically—assumed to be.
Last updated:  2026-08-17
Verifiable Compression of Images
Yue Zhang, Mingxun Zhou, and Benedikt Bünz
AI image generation has made image misinformation a serious concern. To address this issue, the Coalition for Content Provenance and Authenticity (C2PA) standard adopts digital signatures to attest that an image originates from an authorized source, such as an attested camera or authorized AI provider. In practice, however, raw images are rarely published directly: photos are typically compressed before publication, which invalidates any C2PA signature. Recent works have proposed the use of zero-knowledge proofs (zk-SNARKs) to prove that only allowed edits were applied to a C2PA-signed original image. Unfortunately, prior works only support simple edits (e.g. cropping, blurring, and resizing) and do not support lossy image compression like JPEG, which is ubiquitous. The purpose of compression is to save communication. Therefore, unlike other edits, it cannot be verified directly, requires small proof sizes, and is unsuitable to outsourcing. To address these limitations, we present SPEG, the first practical proof system that supports the full image-transmission pipeline on personal devices. We present two protocols that support JPEG compression, while proving validity of the C2PA signature on the original image. The two modes are incomparable: the first is compatible with an arbitrary hashing algorithm (we use Poseidon for efficiency), whereas the second is significantly faster but requires the C2PA to use a polynomial commitment (e.g., KZH) instead of a conventional hash. Our key optimizations are handling the non-algebraic JPEG Encoding outside the proving circuit, and avoiding range checks in our floating-point arithmetic. We can prove the JPEG compression of an FHD(1080p) image in 47s in the Poseidon mode and in 2s in the fast mode. The fastest prior work (VerITAS) which only handles simple resizing, requires 227s on the same consumer hardware. Additionally, we identify a security gap in VIMz (PETS 25) that enables forgery of proofs for unauthorized images and provide a fix. We also prove that we can securely use the popular powers-of-tau SRS with the polynomial commitment scheme KZH.
Last updated:  2026-08-17
Silent Threshold Encryption from Lattices
Jeffrey Champion, David J. Wu, and Shota Yamada
Silent threshold encryption is a generalization of threshold encryption where the public encryption key associated with a group of users is a deterministic function of their individual public keys. The main efficiency requirement is that the ciphertext size should be sublinear in (and ideally, independent of) the size of the decryption quorum $N$. Existing constructions of silent threshold encryption for arbitrary threshold policies have either relied on bilinear maps or on heavyweight tools such as witness encryption and indistinguishability obfuscation. Recently, several works have shown how to support constant thresholds from the decomposed learning with errors (LWE) problem. In this work, we show how to construct a silent threshold encryption scheme from the decomposed LWE assumption where the ciphertext size for encrypting a single bit is $\tilde{O}(T) + \mathsf{poly}(\lambda, \log N)$. Here, $N$ is the total number of users, $T$ is the threshold, and $\lambda$ is the security parameter. Our scheme achieves non-trivial succinctness for all thresholds $T = N^\varepsilon$ for any constant $\varepsilon < 1$. More generally, our scheme extends beyond threshold policies to any monotone policy family that has a succinct (computational) secret sharing scheme; the ciphertext in this case scales with the maximum number of corrupted shares. The core building block in our work is a new bounded-collusion registered functional encryption (FE) scheme with succinct ciphertexts. Specifically, for $N$ users and a collusion bound $Q$, we obtain a registered FE scheme that supports depth-$d$ Boolean circuits on $\ell$-bit inputs and single-bit output with ciphertext size $Q \cdot \tilde{O}(d) + \ell \cdot \mathsf{poly}(\lambda, d, \log N)$. Security relies on the decomposed LWE assumption in the random oracle model. Previously, bounded-collusion registered FE for general circuits was known only from bilinear maps, evasive LWE, or indistinguishability obfuscation.
Last updated:  2026-08-17
On Canonical Liftings, Group Actions, and Linkable Ring Signatures
Alessandro Budroni, Giuseppe D'Alconzo, Leonardo Errati, and Edoardo Persichetti
We introduce the notion of canonical lifting for group actions. This generalises existing techniques for reducing the size of group-action-based signatures, such as the canonical forms used in the LESS signature scheme. Building on this framework, we construct Sigma protocols and a linkable ring signature scheme. Notably, our approach avoids the key-reuse mechanism for linkability used in the framework of Beullens et al. (ASIACRYPT'20), which was shown to be insecure for group actions arising from linear code equivalence (ASIACRYPT'24) and lattice isomorphism (CiC'25). The resulting signatures have size logarithmic in the ring size. We provide security proofs at the level of the abstract canonical-lifting framework, which are then inherited by concrete instantiations satisfying the required assumptions. Finally, we instantiate our approach using the linear code equivalence group action and obtain a linkable ring signature scheme CELeReS, achieving signature sizes that compare favourably with the state of the art, and our AVX2-optimised C implementation demonstrates its practical applicability.
Last updated:  2026-08-17
Rigorous Statements and Proofs of the Lemmas in Simon's Algorithm for the Dihedral Coset Problem and Their Underlying Hypothesis
Yuchen Guo and Shuo Yang
In a recent preprint, Simon proposed a polynomial-time quantum algorithm for the Dihedral Coset Problem and rested the analysis on four lemmas. Three of them carry only proof sketches, and this paper gives each of those three a statement that admits a single reading together with a complete proof. Lemma 1 follows from an exact second-moment computation for the subset-sum counts, and it holds with probability tending to one in place of the constant originally claimed. The amplitude bound of Lemma 3 follows from an exact Parseval identity on the cube of measurement outcomes and holds at every threshold with no well-behavedness hypothesis, so that predicate leaves the argument entirely. For Lemma 4, we compute both balls-in-bins covariances exactly and find that the second carries a term a fixed ball count leaves out. The assumption that the distinguished group contains no faulty samples can also be dropped. The two branch amplitudes share a signed prefactor, so the counting estimates control their difference and not the ratio the lemma states. We prove the additive form and show that the closing argument consumes nothing more than that. A single hypothesis survives all of this. It asks that the partition into the two sides be fixed independently of the measured string, and the rule the algorithm gives for choosing that partition does not supply it. Establishing these four lemmas therefore does not by itself establish the correctness of the algorithm.
Last updated:  2026-08-17
Private Delegation of (Non-)Membership Proof Updates in Cryptographic Accumulators
Bence Soóki-Tóth, Botond Glasz, Alireza Kavousi, and István András Seres
A universal, dynamic accumulator is a verifiable data structure that compresses a set of elements (e.g., unspent coins, issued public key certificates, etc.) into a succinct digest while supporting addition and deletion of elements alongside efficient proving of (non-)membership in that set. In many applications, valid (non-)membership proofs are a prerequisite to accessing a service (e.g., sending a private payment transaction, establishing a TLS connection, etc.). Typically, newly added or deleted elements necessitate updating all existing (non-)membership proofs per update. Thus, intermittently connected clients will possess invalid (non-)membership proofs whenever they reconnect. In this work, we design, implement, and evaluate algorithms for the RSA and bilinear accumulators that allow a resource-constrained client to privately delegate the updates of its (non-)membership proofs to an untrusted server. We define and prove security in a game-based framework under standard assumptions. We also study proof delegation in the batch setting. The online client algorithms are constant-time, i.e., independent of the updated set size $k$, compared to prior $\mathcal{O}(k),\mathcal{O}(\sqrt{k})$ works. The private delegation algorithms for membership proofs incur an asymptotically constant computational overhead for the server (e.g., $6.12\times$ overhead when $2^{10}$ elements were added in the offline phase to the RSA accumulator) compared to the non-private membership proof creation algorithms.
Last updated:  2026-08-17
Exposing SIMD Parallelism in SQIsign: An AVX-512 Implementation
Weize Wang, Chutong Wang, Yu Wu, Qifan Xue, Jieyu Zheng, and Yunlei Zhao
Modern isogeny-based cryptosystems spend much of their running time in finite-field, elliptic-curve, and higher-dimensional isogeny arithmetic. Exploiting SIMD parallelism in these computations is nevertheless nontrivial: central routines such as Montgomery ladders contain loop-carried dependencies, while point, pairing, and theta-coordinate formulas expose only irregular fine-grained parallelism. We show that substantial SIMD parallelism can be recovered by reorganizing the arithmetic dependency graphs of these higher-level primitives rather than vectorizing field multiplication in isolation. We develop an end-to-end AVX-512IFMA implementation of SQIsign in which data remain in a radix-$2^{51}$ vector representation across most of the curve-side computation. Our redesign includes projective xDBLADD schedules for Montgomery ladders, batched point doubling in several coordinate systems, a vectorized biscalar ladder, fused cubical-arithmetic pairing steps, and batched one- and two-dimensional isogeny evaluation. Relative to the reference C implementation, our implementation achieves end-to-end speedups of $1.76\times$, $1.71\times$, and $3.18\times$ for key generation, signing, and verification, respectively, at NIST security level~I; combining the same implementation with Qlapoti increases the key-generation and signing speedups to $2.90\times$ and $2.69\times$. To test whether these techniques are specific to SQIsign, we further apply the same AVX-512IFMA backend and higher-dimensional vectorization methodology to CORAL, a recent isogeny group action for post-quantum non-interactive key exchange based on two-dimensional $2$-isogenies. Across the five parameter sets in our experiments, this yields $1.28$--$1.40\times$ speedups for key generation and $1.92$--$2.46\times$ speedups for shared-key computation over the reference C implementation. These results provide cross-scheme evidence that algorithm-level SIMD scheduling is a reusable optimization dimension for higher-dimensional isogeny cryptography.
Last updated:  2026-08-17
Z-SCAPE: Zero-Knowledge Self-Custodial Credential Operation for Privacy-Preserving Asset Protection under Entropy-Source Failure
Mehmet Sabir Kiraz and Suleyman Kardas
Motivated by the 2026 COLDCARD incident, this paper studies cryptographic asset recovery after self-custodial seed-generation failures. Self-custodial hardware wallets depend on secure entropy sources for seed generation. If an RNG implementation or design failure reduces seed entropy, an adversary may reconstruct wallet signing keys through offline search. Such weaknesses may also be discovered long after wallet creation, placing existing self-custodial assets at risk. To prevent large-scale exploitation after such a failure is identified, a hardware manufacturer or security response team may perform a protective sweep of affected assets into a protected recovery treasury. Asset redistribution then creates a fundamental authentication problem: once the signing key can be reconstructed by both the legitimate owner and an adversary, possession of that key no longer uniquely identifies the legitimate controller. We propose Z-SCAPE, a zero-knowledge recovery-credential protocol for privacy-preserving asset recovery after seed-generation failures and protective sweeps. Before compromise, the user commits to a recovery credential consisting of a 256-bit recovery secret $r$ generated from an entropy source intended to be independent of the transaction-signing seed, and an RNG-independent personal record $P$. After an incident, the prover proves knowledge of $(P,r)$ in zero knowledge for the pre-bound wallet identifier $W$, while binding the proof to the incident-specific protected-asset reference, a fresh verifier nonce, an expiry value, and a fresh recovery destination. The verifier derives the protected-asset reference from authenticated protective-transfer records rather than accepting an arbitrary asset set from the claimant. The protocol enables recovery claims without revealing $P$, $r$, or the compromised wallet private keys, while preventing replay, destination substitution, and cross-wallet protected-asset substitution. Z-SCAPE provides concrete integration mechanisms for Bitcoin and Ethereum and enables only assets recorded as protectively transferred from the proved wallet to be returned to the fresh destination bound to an accepted recovery proof.
Last updated:  2026-08-17
TETRIS: Automated Design Space Exploration of Randomness–Latency Trade-offs in Masked Hardware
Nilotpola Sarma, Tapish Patidar, Nupur Brahamanya, and Chandan Karfa
Given a fixed security order, the randomness and latency of masked hardware present a trade-off. This trade-off has not been structurally examined well enough to enable an efficient search for a user-optimal (randomness/latency-efficient) masked design. Gadget-based masking simplifies masking by replacing each unmasked primitive circuit with a corresponding masked circuit, called a \textit{gadget}, to realize a larger masked design. These gadgets, in turn, have masking-order-dependent latency-randomness costs, lending a structure to the randomness and latency of gadget-based masked hardware. This structure enables automated Design-Space Exploration (DSE) of gadget-based masked hardware that takes in a user's constraints on randomness (or latency) to arrive at the latency (or randomness) optimal assignment of gadgets with less area and vice versa. This article introduces a software-level DSE approach, the basis of which is the two DSE algorithms - Minimize Latency under Randomness Constraints (MLRC) and Minimize Randomness under Latency Constraints (MRLC), which are duals of each other. While prior work optimizes masked hardware by formulating a global optimization based on the Boolean Satisfiability Problem (SAT), our results show that gadget-based masked hardware using Probe-Isolating Non-Interference (PINI) gadgets embodies a structured trade-off, enabling efficient heuristic-based solutions rather than relying on heavy global optimizations. This gives our tool comparable or superior area results in under a millisecond - a speedup of up to several orders of magnitude to the State-of-the-Art tools.
Last updated:  2026-08-17
Statistical Inference from Noisy Randomness Leakage for ML-DSA Attacks
Niklas Paskarbeit, Carsten Schubert, Marian Margraf, and Jean-Pierre Seifert
ML-DSA is a NIST post-quantum signature standard whose security argument rests on rejection sampling making released signatures independent of the secret key. Liu et al. and Damm et al. showed that a single leaked bit of the masking randomness per signature breaks this guarantee, making ML-DSA subkeys recoverable from a number of so-called informative relations, and the resulting attacks were sharpened by Schubert et al. and Bashiri et al.. All of them treat every leaked bit as equally trustworthy. We show that they need not. After the $j$-independence transformation introduced by al., the values extracted from a clean and from a flipped bit are exact complements in absolute value, so the observable relation $|\tilde z|$ follows a two-component mixture whose components we determine in closed form for all leakage regimes. This yields, first, a method-of-moments estimator for the bit-error rate $p$ that requires only the informative relations an attack already collects and that, unlike the estimator of Schubert et al., also works in the low-leakage regime, down to leakage index $4$ for ML-DSA-44 and ML-DSA-87 and $5$ for ML-DSA-65, the same indices at which the attack itself remains feasible. However lower leakage indices come with a lower accuracy, at $25{,}000$ informative relations the mean absolute error for the lowest cases is about $0.022$ to $0.040$ compared to values below $0.002$ in the high-leakage regime. The noise estimator is also adjustable to estimate asymmetric noise rates. Second, it yields a posterior probability, for each individual relation, that its leaked bit is correct. Thresholding this posterior gives an $O(\alpha)$ preprocessing step that corrects relations classified as noisy and that any downstream attack can use unchanged, where $\alpha$ is the amount of informative relations. Applied to the attack of Schubert et al., the preprocessing reduces the number of informative relations required for key recovery by about $20\%$ to $44\%$ across all three parameter sets, leakage indices $6$ to $9$, and error rates $20\%$ and $40\%$. Applied to the attack of Bashiri et al. for ML-DSA-44 at leakage index $8$, it improves key recovery across the noise range we tested: at $p = 0.45$ from $1{,}900{,}000$ informative relations, at $p = 0.40$ from $450{,}000$ informative relations, at $p = 0.20$ from $40{,}000$ informative relations, a single fixed threshold chosen in hindsight succeeds for $20$, $22$, and $23$ of $30$ seeds against $16$, $18$, and $19$ of $30$ without the preprocessing, and a parallel search over ten thresholds succeeds for $23$, $25$, and $29$ of $30$.
Last updated:  2026-08-17
NAIBI: Binding Reconciliation KEMs and Ephemeral Key Agreement over Non-Split Commutative Algebras
Sidoine Djimnaibeye, Djiby Sow, Mahamat Borgou Hassan, Daniel Tieudjo, and Ganga Tchawa
We propose NAIBI-Full, a lattice-based key encapsulation mechanism (KEM) together with its forward-secure ephemeral key-agreement protocols, built on the regular representation $\rho$ of the non-split commutative algebra $\mathcal{A}_\alpha = R_q[y]/(y^k - \alpha)$ over $R_q = \mathbb{Z}_q[x]/(x^n + 1)$, with $k \in \{2,3\}$ and $\alpha$ a non-$k$-th power. Each party publishes the full matrix $\mathbf{t} = A\rho(\mathbf{s}) + \mathbf{e} \in R_q^{k \times k}$; because $\rho(\mathcal{A}_\alpha)$ is commutative, the cross-product collapses to small noise and a Peikert hint closes the gap to exact agreement, even though the public matrix $A$ is fully generic in $M_k(R_q)$. Hardness rests on a single, well-localised assumption: structured-secret Module-LWE $\mathrm{MLWE}_\rho$, which we identify exactly with a $\rho(y)$-linked $k$-sample MLWE problem via column decomposition, placing it inside the well-cryptanalysed MLWE landscape of ML-KEM. NAIBI-Full is the conservative member of the family: a clean account in terms of a standard lattice assumption, at the cost of $k^2$-element public keys and ciphertexts. Three primitives follow from this single core: an IND-CCA2 KEM (the $\mathrm{FO}^{\not\bot}$ transform, i.e. with implicit rejection, in the ROM and QROM) and two forward-secure ephemeral protocols, ephemeral-static and ephemeral-ephemeral. For the KEM we prove in addition a statistical, decapsulation-level binding correctness guarantee, with collision probability at most $(2/3 + 1/(3q))^{\lceil n/2 \rceil} + (8/q)^{n/2} + 2^{-256}$, below $2^{-148}$ at every parameter set. That binding survives in the malicious-key model on the public-key axis (MAL-BIND-K-PK, with a $q_H$ factor on the mechanism term), with no distributional assumption on the adversarial keys: the property ML-KEM is known to lack, and which the seed key format of FIPS 203 (which does restore the ciphertext axis) still leaves unattained. The statistical modality attaches to the accept branch; on the rejection branch, where no KEM admits a statistical guarantee, the rejection key hashes the public key, without which the notion falls to a one-line attack reusing a single $z$ across two malicious keys. We deliberately offer no static-static mode, since it would inherit the active key-mismatch attacks of the Ding/Peikert/NewHope family; NAIBI-Full is confined to its key-mismatch-resistant deployments. Parameter sets cover NIST security Categories 1, 3 and 5, all with $\delta \le 2^{-128}$.
Last updated:  2026-08-17
Updatable Signature with Public Tokens
Haotian Yin, Jie Zhang, Wanxin Li, Yuji Dong, Eng Gee Lim, and Dominik Wojtczak
The Updatable Signature (US) allows valid signatures to be updated by an update token without accessing the newly generated signing key. Cini et al. (PKC’21) formally defined this signature and gave several constructions. However, their security model requires the secrecy of the update token, which is not applicable in many common application scenarios where existing signatures have been distributed to many parties. In addition, one can use the same token to update both the signing key and signatures, and all signatures can be updated by a single token, whereas the adversarial signature generated by an adversary might also be updated. This work explores the (im)possibility of constructing an Updatable Signature with public tokens (USpt). Specifically, we first define the updatable signature with public tokens and present its security model. Then, from considering existing US schemes, we found that a secure USpt must properly handle a transform function from signature-update token to key-update token. We further formally proved the impossibility of constructing a secure USpt if (1) there is no transform function between key pairs and signatures, or (2) the signature-update token can be derived from the public keys of adjacent epochs. Finally, we present a concrete USpt scheme based on the BLS signature.
Last updated:  2026-08-17
Ultra short signatures with Dragon $HFE_{LL'}$
Jacques Patarin, Jan Vacek, and Alexandre Roullet
We study HFE-based multivariate signatures with an \(LL'\) perturbation. The resulting scheme \(HFE_{LL'}\) gives short signatures, and its Dragon variant \(D\text{-}HFE_{LL'}\) gives ultra-short signatures by separating the hash length from the number of signature variables. We discuss the relation with \(\mathrm{HFE}^{\widehat{+}}\), the applicability of known attacks, and propose explicit parameter sets.
Last updated:  2026-08-17
Auditable Continuous Group Key Agreement
Easwar Vivek Mangipudi, Maddie Gorman, and Sasha Levinshteyn
Continuous group key agreement (CGKA), the cryptographic core of Messaging Layer Security (MLS, RFC 9420), provides key management for large end-to-end encrypted group chats. It refreshes the group's keys as members join and leave, but offers no way for a designated auditor to recover past epoch keys, and no way to check that such recovery remains possible. Regulated deployments in finance, healthcare, and government therefore resort to plaintext server logging, abandoning end-to-end encryption entirely. Simply adding a key escrow admits a silent escrow failure: the group accepts an epoch whose escrow holds unrecoverable material, with no visible anomaly until a later audit. Addressing this, we introduce auditable CGKA (Au-CGKA), an MLS-shaped protocol in which every admitted epoch carries a proof. The proof binds that epoch's key material to a well-defined secret recoverable by a threshold auditor committee. Every member checks that binding against the epoch secret it derives and refuses the commit if the two disagree, so auditability guarantees that the secret of every epoch an honest member accepts is threshold-recoverable. We give a post-quantum protocol, Π_A, realizing this property with STARK proofs. The committer escrows the epoch secret to an auditor committee, and the escrow ciphertext is a STARK-friendly encryption of Shamir shares. Its well-formedness is proven in-circuit at MLS commit time. We prototype Au-CGKA in Rust with the proofs on a zero-knowledge, post-quantum custom multi-stage STARK. On an Apple M5 Pro, an auditability proof takes 1.38 s with proof-size 15.31 MB and verifies in 0.17 s, at every group size; the relation it proves is independent of the group size. The proof is checked at admission and then discarded, so it costs bandwidth on the commit and nothing in storage; the only persistent overhead is the fixed-size escrow. Adaptive post-quantum security holds in the secure-erasure model with straight-line reductions in the quantum random-oracle model, and carries to the implemented backend under a stated assumption; privacy and escrow soundness follow as game-based guarantees.
Last updated:  2026-08-17
Ring Signatures with Personalized Anonymity
Kyosuke Yamashita and Keisuke Hara
Ring signatures have long struggled to balance absolute anonymity with traceability. While various extensions, such as traceable and accountable ring signatures, have been proposed, they typically apply a uniform anonymity or traceability rule to all potential signers. This paper introduces personalized-anonymity ring signatures (PARS), a novel primitive in which users are certified with different anonymity rights according to their roles or authority. Unlike ordinary ring signatures, PARS involves a group manager at key issuance; however, the group manager does not determine a fixed signing group. Instead, signers retain the ring-signature feature of choosing the ring at signing time, while the manager certifies whether each user's key permits fully anonymous signing or only traceable signing. This model is particularly suited for organizational governance, where ordinary members may require strong anonymity for internal reporting or expressing dissenting opinions, while users with institutional authority must remain accountable for official approvals or authorizations. We provide a formal syntax and rigorous security definitions for PARS, capturing both standard ring-signature requirements and traceability-related guarantees. We then present a generic construction from standard cryptographic primitives, including digital signatures, one-time signatures, public-key encryption, and non-interactive zero-knowledge proofs of knowledge.
Last updated:  2026-08-17
Prepared Episodes for Short Online Hash Based Signatures
Chongxu Ren, Kaiyi Zhang, Haorui Cui, and Hongbo Yu
SPHINCS+ provides stateless signing and self-contained verification, but its signatures are large: every message carries a FORS signature and a complete WOTS+/Merkle authentication chain to the long-term root. This cost is repeated even when messages arrive in a bounded episode whose maximum size is known in advance. We introduce prepared-episode signatures and instantiate them as SPHINCS-PE. The construction splits a globally addressed hypertree at an episode boundary into upper and lower trees. Preparation authenticates the boundary root through the upper tree, while each online signature traverses the lower tree back to that root. Because the upper tree is computed before messages arrive, it can use fewer, taller layers. This removes WOTS+ blocks from full signatures at the cost of more preparation work. Full signatures remain self-contained, while recurring verifiers may cache the upper certificate. Our fixed-count exposure analysis pools colliding preparations and bounds post-selection of the target episode. The end-to-end theorem reduces unforgeability to PE-ITSR and explicit PRF and hash-component games. Compared with the matched FIPS 205 SLH-DSA profiles, SPHINCS-PE reduces full-signature sizes by 3% to 12% for the short profiles and by 25% to 40% for the fast profiles. With the upper certificate cached, online signatures are 24% to 48% smaller for short profiles and 56% to 70% smaller for fast profiles. These results show that prepared episodes can shorten hash-based signatures without giving up self-contained verification.
Last updated:  2026-08-17
Quantum Resource Optimization for CSIDH
Uncategorized
Yan Huang, Yongjie Li, Xiuyu Qiu, Zijian Zhou, Fangguo Zhang, Chao Chen, and Wei Yu
Show abstract
Uncategorized
The quantum resource analysis of CSIDH has remained an active research topic. At Eurocrypt 2020, Peikert raised three open problems concerning the optimization of the corresponding quantum resources. In this work, we primarily focus on the first two: optimizing quantum resources for ideal class groups and choosing the collimation arity. Specifically, we reduce the T-gate complexity of class group actions for CSIDH-512 from $2^{52.6}$ to $2^{51.7}$. Furthermore, within our four-way permutation construction model and under a specified classical memory budget, we provide a detailed analysis of the classical and quantum resources associated with different collimation arities $r$. Among the evaluated configurations, $r = 4$ emerges as the optimal choice. By incorporating the hidden-shift quantum algorithms proposed by Peikert, we achieve a T-gate reduction of at least 85\% for solving CSIDH-512.
Last updated:  2026-08-16
Qlapoti+ and More: Optimizing Isogeny-based Signatures
Yi-Fu Lai
This paper presents several optimizations to Qlapoti (Asiacrypt'25), an ideal-finding procedure at the heart of modern isogeny-based signature schemes. We apply these optimizations to the Qlapoti-based NIST Round-2 SQIsign implementation from Asiacrypt'25. Together, they accelerate the Qlapoti procedure by approximately \(1.6\times\) to \(5.3\times\), depending on the parameter set and implementation. Under the Broadwell benchmark, compared with the baseline implementation in Asiacrypt'25, our optimizations achieve key-generation speedups of \(1.29\times\), \(2.23\times\), and \(1.54\times\), and signing speedups of \(1.23\times\), \(1.79\times\), and \(1.43\times\), at NIST security levels~1, 3, and~5, respectively. Our techniques also apply to the Qlapoti-optimized PRISM implementation (PKC'25, Journal of Cryptology), for which we introduce an additional tailored optimizations. Under the Broadwell benchmark, compared with the baseline implementation in JoC using Qlapoti, our improvements translate into key-generation speedups of \(1.22\times\), \(1.87\times\), and \(1.46\times\), and signing speedups of \(1.47\times\), \(1.90\times\), and \(1.60\times\), at NIST security levels~1, 3, and~5, respectively.
Last updated:  2026-08-16
Secret-Subspace Recovery in MAYO via Linearization of Errors from a Single Fault
Alberto Marcos
We present fault injection attacks against MAYO in which a single faulty execution reveals structural information about the secret. We consider two closely related single-block fault models. In the first one, a controlled perturbation affects one oil coordinate of a signature block and induces an error $e \in \mathcal{O}$. In the second one, the perturbation may affect several oil coordinates of the same block. In both cases, we show that the observable verification mismatch can be written as the image of the induced error under a publicly derivable linear operator. This yields two recovery strategies. In the linear route, when the relevant oil part of the error can be identified, recovery reduces to solving a linear system over $\mathbb{F}_q$. In the reduced-quadratic route, the same linear relation is combined with the constraint $P(e)=0$, which leaves, in the generic full-rank case, a reduced system of $m$ quadratic equations in $n-m$ variables. For the MAYO parameter sets, $n-m=o$ is small, and the resulting reduced quadratic systems can be solved over the base field. Recovering $e$ yields a nonzero vector of the secret subspace and provides a starting point for key-recovery techniques against the oil space. We also discuss the practical cost of both approaches and explain why the attack applies to randomized MAYO.
Last updated:  2026-08-16
HasteBoots: Proving FHE Bootstrapping in Seconds
Fengrun Liu, Haofei Liang, Xiang Xie, Yu Yu, Wenting Zheng, and Yuncong Hu
Fully Homomorphic Encryption (FHE) enables computations on encrypted data, ensuring privacy for outsourced computation. However, verifying the integrity of FHE computations remains a significant challenge, especially for bootstrapping, the most computationally intensive operation in FHE. Prior approaches, including zkVM-based solutions and general-purpose SNARKs, suffer from inefficiencies, with proof generation time ranging from several hours to days. In this work, we propose HasteBoots, a succinct argument tailored for TFHE with programmable bootstrapping. By designing efficient protocols for arithmetic operations over quotient rings, HasteBoots achieves proof generation in a few seconds for TFHE evaluation with programmable bootstrapping, significantly outperforming the state-of-the-art, Zama (CCS'25). Moreover, HasteBoots supports batching multiple TFHE evaluations and bootstrappings, a feature that prior work cannot practically support due to prohibitive proving cost. HasteBoots can prove a batch of 16 operations within one minute, while maintaining succinct verification, requiring only 126 ms and a proof size of 0.28 MB. Our approach demonstrates the potential for scalable and efficient verifiable FHE, paving the way for practical, privacy-preserving computations.
Last updated:  2026-08-16
New Attacks on Mersenne Number-Based Cryptosystems: Relaxing Size Constraints
Mengce Zheng and Abderrahmane Nitaj
In 2017, Aggarwal, Joux, Prakash, and Santha proposed an integer analogue of the NTRU cryptosystem, known as the AJPS cryptosystem. This scheme is based on Mersenne numbers, and is believed to be resistant to quantum attacks. This paper revisits the security of AJPS by reexamining its inherent hard problems. We propose novel attacks that apply the continued fraction-based method and the lattice-based solving strategy for modular polynomial equations, rather than directly using lattice reduction algorithms. Our methods significantly relax the size constraints on the unknown private key. Specifically, we either eliminate the need to estimate upper bounds on the unknowns or extend the attack range of vulnerable weak keys, while enhancing the success probability under unbalanced parameter settings. To validate our theoretical findings, we conduct extensive numerical experiments with parameters of various sizes. The experiments confirm both the practicality and the effectiveness of our proposed attacks.
Last updated:  2026-08-16
A decrementally-improved algorithm for Boolean MQ
Charles Bouillaguet and Julia Sauvage
The MQOM signature scheme is currently a third-round candidate in the NIST competition for additional signatures. It is based on the ``MPC-in-the-Head'' paradigm and relies on the hardness of the MQ problem. Some of its parameter sets expose a Boolean quadratic system in the public key. While the situation for MQ over larger fields has been relatively quiescent over the last decade, Boolean MQ has seen active progress, culminating with Dinur's algorithms at SODA 2021 and Eurocrypt 2021. We propose yet another algorithm for Boolean MQ. It is a hybrid between the ``polynomial-method'' of Lokshtanov, Paturi, Tamaki, Williams and Yu from SODA 2017 and Dinur's ``second algorithm'' from Eurocrypt 2021. We remove some machinery from the latter to obtain a modest improvement of 1--4 bits in performance for MQOM parameters (``decremental improvement''). MQOM optionally uses the ``correlated GGM trees'' technique to shorten signatures; in that case, its security also relies on the hardness of the ``Partial-Guessing One-Wayness'' problem for MQ (PGOW-MQ): given an MQ system supposed to offer $\lambda$ bits of security, the adversary has to find the first $\lambda$ bits of a solution, and they have access to an oracle that enables them to check candidate prefixes. The designers of MQOM implicitly assumed that PGOW-MQ is as hard as MQ itself. Our algorithm can exploit the availability of the solution-testing oracle to solve PGOW-MQ 2 to 4 times faster than it solves MQ, thus showing that the two problems are marginally different. This yields attacks against MQOM that are 3--4 bits below the expected security level, but that suffer from huge memory complexities. Lastly, we survey old and new techniques to find an invertible linear change of variables that puts a few arbitrary polynomials in UOV shape. This leads to a small acceleration of our algorithm, and also incidentally improves upon the Thomae-Wolf and Furue-Nakamura-Takagi algorithms to solve underdetermined Boolean systems. A new idea based on matrix pencils was used to solve the largest underdetermined Boolean Fukuoka MQ challenges and may be of independent interest.
Last updated:  2026-08-16
Post-Quantum TLS Migration: A Systematization of Hybrid Handshakes, PSKs, KeyUpdate, and Certificate Strategies
Hridoy Roy
Post-quantum migration of Transport Layer Security (TLS) is often described as replacing a classical key-exchange algorithm with a post-quantum alternative. This framing is incomplete: TLS distributes security across key establishment, authentication, resumption and pre-shared keys (PSKs), traffic-secret evolution, and the X.509/PKIX ecosystem. These functions have different security objectives, failure modes, lifecycle dependencies, and deployment constraints. This Systematization of Knowledge (SoK) develops a functional framework for analyzing post-quantum TLS migration as an architectural problem rather than a single algorithm transition. We systematize classical, pure post-quantum, and hybrid key establishment; TLS 1.3 PSK modes and resumption; KeyUpdate; ML-KEM; ML-DSA and SLH-DSA; hybrid and composite authentication; X.509/PKIX and trust-anchor migration; HSM dependencies; interoperability; performance; deployment environments; cryptographic inventory; and crypto-agility. We classify evidence by mechanism, security objective, source of keying material, forward-secrecy behavior, quantum threat, post-compromise behavior, communication and computational cost, interoperability dependency, standardization status, deployment evidence, and migration complexity. We explicitly separate finalized standards from evolving Internet-Drafts and implementation-specific evidence. The systematization produces four analytical conclusions. First, confidentiality migration and authentication migration are coupled operationally but distinct security programs. Second, hybrid ECDHE-ML-KEM is a strong transitional architecture for confidentiality migration when the relevant TLS integration and implementation support are available, because its security objective can tolerate failure of one component; the exact security claim nevertheless depends on the standardized construction and its assumptions. Third, PSKs, resumption, and KeyUpdate are not interchangeable forms of rekeying: their security depends on the provenance and role of the secret, while KeyUpdate remains within an existing traffic-secret lineage and does not create an independent post-quantum secret. Fourth, deployment readiness is constrained as much by certificates, trust stores, HSMs, middleboxes, inventory, and interoperability as by primitive availability. We therefore derive a migration decision framework that prioritizes HNDL-sensitive data, controlled hybrid deployment, interoperability testing, staged authentication and PKI migration, and observable retirement of classical-only mechanisms.
Last updated:  2026-08-16
Parallel Repetition for Entangled Games with Gap Exponent Three
Zhao Song
We prove that every finite two-player game $G$ with entangled value $\omega^*(G)=1-\epsilon$ satisfies \[ \omega^*(G^{\otimes n}) \le\exp(-\Omega(\frac{\epsilon^3}{\epsilon+ \ell }n)) \] for every $n\ge1$, where $\ell:=\log(|A| |B|)$, and $A$ and $B$ are the answer alphabets. Compared with Chapter 6 of the OpenAI report [Ope26], this improves the gap exponent from thirteen to three and matches the cubic gap dependence in Holenstein's general classical bound [Hol09]: \[ \omega(G^{\otimes n})\le\exp(-\Omega( \frac{ (1-\omega(G))^3}{1+\ell} n)). \] The proof replaces the randomly shifted logarithmic grid used in quantum correlated sampling by smooth soft labels. This makes the relevant label infidelity quadratic in the distance between state descriptions and avoids a Jensen loss when averaging over questions. Together with the postselection argument, these improvements yield the cubic gap dependence stated above.
Last updated:  2026-08-16
Information-Theoretic SFE and PFE with Reduced Communication
Shuaishuai Li, Cong Zhang, Juntong Lin, Anyu Wang, and Xiaoyun Wang
Secure function evaluation (SFE) and private function evaluation (PFE) are fundamental primitives in multiparty computation. In SFE, multiple parties jointly compute a \textit{public} function over private inputs while revealing nothing beyond the output, whereas in PFE the function itself is \textit{private} and known only to a designated party. In this work, we focus on the semi-honest setting and present more efficient information-theoretic constructions for both SFE and PFE. For SFE, the classical BGW protocol incurs $O(n^2)$ communication per multiplication gate. The DN protocol (Damg\aa rd and Nielsen, Crypto 2007) reduces the amortized communication to linear but still require an additional $O(n^2)$ term, yielding $O(m^* n + n^2)$ communication for $m^*$ multiplication gates. This becomes suboptimal in the regime $m^*= o(n)$. We introduce a simple technique that removes this quadratic overhead, achieving strictly linear $O(m^* n)$ communication. For PFE, the only existing information-theoretic approach relies on universal circuits, which results in $O(m^5n+n^2)$ complexity for arithmetic circuits. We develop new techniques that avoid universal circuits entirely. Combined with our SFE improvements, this yields an honest-majority PFE protocol achieving $O(m^2n)$ communication for circuit size $m$. We further obtain improved efficiency in special cases, including a three-party protocol with $O(m^{4/3})$ communication, and an $n$-party protocol tolerating one corruption with $O(m^{(2n-2)/(2n-3)}n)$ communication.
Last updated:  2026-08-16
The Most Efficient Protocol for PAKE: What Exact Stuff Do You Need to Hash at the End?
Jiayu Xu
A Password-Authenticated Key Exchange (PAKE) protocol allows two parties to jointly establish a cryptographic session key, in the "password-only" setting where the only information shared in advance is a low-entropy password. In recent years, the One-encryption EKE with 2-round Feistel cipher (OEKE-2F) protocol, a compiler from Key Encapsulation Mechanism (KEM) to PAKE, has received much attention, for the following reasons: (1) When instantiated with the Diffie–Hellman KEM, it is the most computationally efficient PAKE protocol to date that is secure in the Universal Composability (UC) framework; and (2) When instantiated with a post-quantum KEM, it provides a generic way to construct efficient PAKE protocols based on post-quantum assumptions. Unfortunately, the community cannot agree upon what the OEKE-2F protocol exactly is: part of the second protocol message is an RO hash of the KEM key, together with any number of the following: - The password, - The KEM public key, - The first protocol message, and - The KEM ciphertext. This yields 16 potential variants of OEKE-2F; only two of them have been studied in the literature, and their pros and cons are poorly understood. In this work, we present a comprehensive analysis of *all 16 variants* of OEKE-2F, proving the UC-security of each of them. The general takeaway is that the "hash everything" version requires the fewest security properties of the underlying KEM scheme, and the more items we remove from the hash, the more security requirements the KEM scheme has to satisfy — although all of the additional KEM properties are still mild. We pinpoint the exact KEM properties each version of OEKE-2F needs, and thoroughly explain the rationales. The significance of this work lies in that it helps the community converge upon the "right" version of OEKE-2F, and perhaps also in that this is the first paper by the author that is over 100 pages.
Last updated:  2026-08-16
Note on Number-Theoretic Transforms for Implementers -- Butterflies, Twisting, Incompleteness, and Good's Trick
Bo-Yin Yang
We develop (mostly) the radix-2 number-theoretic transform (NTT) and its butterflies, the twisting trick and why it never changes the transform, the freedom to use Cooley--Tukey butterflies in both directions, incomplete NTTs, Good's trick, and the ways all of these combine---closing with the coefficient-bound bookkeeping that motivates the whole toolkit. This note is intended to help implementers of postquantum cryptography, and is compressed from the author's lecture notes and slides in his Postquantum Cryptography class at National Taiwan University (2020--2025). It may be otherwise trivial for FFT experts who know the DIT--DIF equivalence inside out---except that they tend not to encounter incomplete NTTs (a term which, to the best of his knowledge, he originated in 2020) and negacyclic.
Last updated:  2026-08-15
On the Hardness of some Vandermonde Knapsack problems
Dipayan Das and Arindam Mukherjee
The Vandermonde Knapsack problem comprises a family of algebraic variants of the Knapsack problem. This includes the Partial Vandermonde $(\mathsf{PV})$ Knapsack problem (DCC’15, ACNS’14, ACISP’18, DCC’20, Indocrypt'25), the Vanishing $\mathsf{SIS}$ $(\mathsf{vSIS})$-based commitment problem (Crypto’23, PKC'25), and related assumptions. These problems have played an important role in enabling efficient lattice-based cryptographic constructions. Recently, two independent works by Boudgoust, Gachon, and Pellet-Mary (Crypto’22), and by Das and Joux (Eurocrypt’24), proposed attacks demonstrating that certain instances of the $\mathsf{PV}$ Knapsack problem are weak. In this paper, we present new attacks on the $\mathsf{PV}$ Knapsack problem for power-of-two cyclotomic rings. By combining our techniques with the attack of Das and Joux, we show that a substantially larger fraction of keys are weak in this setting than was previously known. We then extend our attack to the integer variant of the $\mathsf{vSIS}$ commitment problem, demonstrating that certain instances are also weak for specific parameter regimes.
Last updated:  2026-08-15
PhantomCrypt: Composing Existence and Content Deniability with Post-Quantum Envelope
Shahzad Ahmad, Stefan Rass, and Zahra Seyedi
Traditional deniable encryption denies the \emph{content} of secret communications by allowing plausible alternative plaintexts under coercion. But the recognizable use of a deniable-encryption tool can itself defeat the purpose: a revealed plaintext becomes suspicious once a coercer detects that a non-standard tool was used, and fully encrypted, format-anomalous traffic is already detected and acted upon by deployed censorship systems. This motivates a second axis of deniability, the deniability of the mechanism's \emph{use}, which we call \emph{second-order deniability} (2OD) and treat as a design goal rather than a single achievable primitive. We decompose 2OD into two formally separate properties: \emph{content deniability} (CD), that a coercer holding all disclosed keys cannot identify the true message among decoys, and \emph{existence deniability} (ED), that the transmitted ciphertext is indistinguishable from the output of a fixed, standard reference protocol. We give game-based definitions of CD and ED, prove that the two are logically independent, and present PhantomCrypt, a construction that composes False-Bottom Encryption (CD) with Invisible Encryption (ED) under a post-quantum hybrid KEM/AEAD envelope. We are deliberate about what each guarantee buys. ED, as we define and prove it, is the indistinguishability of the transmitted ciphertext \emph{object} from a single, explicitly specified reference distribution (a standard hybrid KEM/AEAD wrapper over an unmodified cover string); it reduces to KEM and AEAD security. It is \emph{not} a claim of traffic-analysis resistance, and it is conditional on an assumption we make explicit rather than prove: that the chosen cover string is itself unremarkable to the observer. CD we prove negligible in the random-oracle model, conditioned on the secrecy of a pre-shared seed, with the residual advantage controlled by two explicit quantities: the seed's entropy relative to the field size, and a cover-concentration term that we introduce here and bound by a min-entropy admissibility condition validated on real text. Post-quantum security enters through the envelope only: ED reduces to ML-KEM and AEAD security against a quantum distinguisher, whereas the CD argument is statistical and stated in the classical random-oracle model, so we claim a post-quantum \emph{envelope} rather than post-quantum deniability wholesale and leave a QROM treatment of composed CD open. We further show that this coupling is sharp: a feasibility threshold separates a regime where strong deniability holds from one where it is information-theoretically impossible, governed by the seed-entropy margin relative to the plausible-message entropy. We are explicit about the boundary throughout: ED is object-level indistinguishability, not a defense against traffic analysis or device-side software forensics, and we state where full 2OD does and does not hold. A proof-of-concept implementation encrypts a 32-byte message with three decoys in under 10\,ms on commodity hardware, with scaling measured across cover-text length and decoy count.
Last updated:  2026-08-15
Secret-Sharing Schemes for General Access Structures: An Introduction
Amos Beimel
A secret-sharing scheme is a method by which a dealer distributes shares to parties such that only authorized subsets of parties can reconstruct the secret. Secret-sharing schemes are an important tool in cryptography and they are used as a building block in many secure protocols, e.g., secure multiparty computation protocols for arbitrary functionalities, Byzantine agreement, threshold cryptography, access control, attribute-based encryption, and weighted cryptography (e.g., stake-based blockchains). The collection of authorized sets that should be able to reconstruct the secret is called an access structure. The main goal in secret sharing is to minimize the share size in a scheme realizing an access structure. In most of this monograph, we will consider secret-sharing schemes with information-theoretic security, i.e., schemes in which unauthorized sets cannot deduce any information on the secret even when the set has unbounded computational power. Although research on secret-sharing schemes has been conducted for nearly 40 years, we still do not know what the optimal share size required to realize an arbitrary 𝑛-party access structure is; there is an exponential gap between the best known upper bounds and the best known lower bounds on the share size. In this monograph, we review the most important topics on secret sharing. We start by discussing threshold secret-sharing schemes in which the authorized sets are all sets whose size is at least some threshold 𝑡; these are the most useful secret-sharing schemes. We then describe efficient constructions of secret-sharing schemes for general access structures; in particular, we describe constructions of linear secret-sharing schemes from monotone formulas and monotone span programs and provide a simple construction for arbitrary 𝑛-party access structures with share size 2^0.5𝑛. To demonstrate the importance of secret-sharing schemes, we show how they are used to construct secure multi-party computation protocols for arbitrary functions. We next discuss the main problem with known secret-sharing schemes – the large share size, which is exponential in the number of parties. We present the known lower bounds on the share size. These lower bounds are fairly weak, and there is a big gap between the lower and upper bounds. For linear secret-sharing schemes, which are a class of schemes based on linear algebra that contains most known schemes, exponential lower bounds on the share size are known. We then turn to study ideal secret-sharing schemes in which the share size of each party is the same as the size of the secret; these schemes are the most efficient secret-sharing schemes. We describe a characterization of the access structures that have ideal schemes via matroids. Finally, we discuss computational secret-sharing schemes, i.e., secret-sharing schemes that are secure only against polynomial-time adversaries. We show computational schemes for monotone and non-monotone circuits; these constructions are more efficient than the best known schemes with information-theoretic security.
Last updated:  2026-08-15
Aegon: Self-Auditable Key Transparency
Hossein Hafezi, Alireza Shirzad, Benedikt Bünz, Kevin Lewi, Dillon George, and Joseph Bonneau
Key transparency enables a centralized encrypted messaging provider to publicly commit to the public keys it distributes, allowing clients to detect potentially malicious keys. Recent deployments by WhatsApp and iMessage demonstrate the promise of this approach, but they rely on third-party global auditors to detect misbehavior by the key server. No existing system supports auditing efficiently enough to be done by lightweight end users while also providing scalability to billions of users and short epoch latency. We present $\mathsf{Aegon}$, a key transparency scheme designed for global-scale encrypted messaging. Building on ideas from $\mathsf{IronDict}$, $\mathsf{Aegon}$ avoids per-epoch work that scales with the full dictionary size: its server computation depends only on the number of updates in the current epoch, eliminating global invariance proofs and enabling epoch latency of under a minute ($500\times$ reduction compared to $\mathsf{IronDict}$). $\mathsf{Aegon}$ further introduces a sharded dictionary design that reduces global parameters to shard-dependent sizes and enables horizontal scaling. To control long-term storage, $\mathsf{Aegon}$ uses proof caching to safely discard historical dictionary snapshots, so storage grows only with retained history. We provide a production-grade Rust implementation of $\mathsf{Aegon}$ and demonstrate practical scalability to a dictionary with $4$ billion entries, comparing it against the public codebase of WhatsApp Key Transparency ($\mathsf{AKD}$). At the throughput of $1{,}250$ updates per second, $\mathsf{Aegon}$ produces constant-size auditor proofs of under $30$ KB, verifiable in under $65$ ms and independent of the number of updates per epoch or of the directory fill. At a fully-populated $2^{32}$-entry directory, this is roughly an $80{,}000\times$ reduction in audit proof size and a $370\times$ reduction in verify time relative to $\mathsf{AKD}$. All other server and client operations remain highly efficient and comparable to $\mathsf{AKD}$, while $\mathsf{Aegon}$ achieves stronger privacy guarantees.
Last updated:  2026-08-15
Actively Secure Two-Party Function Secret Sharing with Dynamic Cross-Phase Verification
Yujie Xue, Lin Liu, Rongmao Chen, Yizhen Jiang, Yuchuan Luo, Bing Sun, and Shaojing Fu
Function secret sharing (FSS) gives two parties succinct keys whose local evaluations add up to a hidden function value. Removing the dealer is the natural next step for preprocessing-based secure computation, but malicious security then requires more than checking a finished key: the generation transcript, the function the key actually computes, and every released evaluation share must all be bound to one execution. We call this the cross-phase binding problem, and we solve it. We present VeriFSS, a dealer-free two-party FSS scheme with active security, proved in the standard simulation-based framework against one static malicious corruption. The construction rests on a two-plane key: the distributed generator produces a key for the paired function $x\mapsto(f_\theta(x),\Lambda f_\theta(x))$, where $\Lambda$ is a secret global authentication scalar. The second plane makes every local evaluation an authenticated sharing for free, which yields online report binding without vector commitments, extractable hashing, or per-point interaction. It also supplies the ingredient the audit was missing: we prove a moment-fidelity lemma showing that a corrupted party cannot misreport the full-domain moments of its own sealed key except with probability $3/|E|$ over the challenge set $E$, and a shape-identification lemma showing that three moment equations pin a point function down exactly, with error $2n/|E|$ over any field. The proof isolates the coefficient of the square monomial in the support polynomial and is therefore characteristic-free; in characteristic two an odd-size equal-weight support defeats the support equation on its own, and we show the position equation takes over. A discrete-derivative reduction carries both lemmas to comparison functions, and a Galois-ring variant covers fixed-point payloads over $\mathbb{Z}_{2^k}$ by a $2$-adic valuation argument, so no non-additive lift into a binary field is ever needed. Generation costs two rounds and five field elements per party per level; certification adds $O(n)$ elements with no dependence on the domain size, and a dynamic cross-domain aggregation certifies arbitrarily many heterogeneous instances under one challenge and a constant number of rounds. We then lift the general-purpose FSS gates of Boyle et al. (EUROCRYPT 2021): every gate that is a public affine post-processing of a constant number of DPF/DCF evaluations---interval containment, splines, ReLU, arithmetic shift, bit decomposition, zero test, table lookup---inherits active security at no additional online cost. We evaluate our construction using a C++ implementation that certifies keys over $\mathbb{F}_{p^2}$ ($p=2^{61}-1$) and $\mathrm{GF}(2^{128})$, realises the gate layer, and agrees bit‑for‑bit on every exported test vector. A certified DPF key at $n=16$ takes $5.7$ ms to generate and $3.3$ ms to certify. Certified DPF keys are $5.4\%$ larger than the semi-honest dealer-free baseline at $n=16$, and aggregated certification traffic converges to $1{,}282$ bytes per instance while the round count stays constant. Replaying the certified execution between two processes over TCP shows what that constancy is worth: at a $50$ ms round trip a session takes $1.15$ s, and the figure is unchanged whether one key or sixty-four are certified together, so wide-area certification of a whole preprocessing session is latency-bound by a single key. A campaign of $1{,}400$ injected generation deviations plus shape, moment and release forgeries is rejected without exception in six of seven deviation classes; the seventh is rejected in exactly the $105$ of $200$ trials in which the attacked index bit is one, which is a quantitatively exact confirmation of the single-bit selective-failure predicate that we model explicitly in the ideal functionality, matching the leakage profile of the best known actively secure distributed DPF.
Last updated:  2026-08-15
Cryptanalytic Extraction of Multi-Head Softmax Attention Models
Sunan Wang, Hao Lei, Longxiang Wei, Qun Liu, Kai Hu, and Meiqin Wang
Since the seminal work of Carlini et al. at CRYPTO 2020, cryptanalytic model extraction has shown neural-networks parameters can be recovered from black-box queries. Existing attacks are largely built around piecewise-linear phenomena. Softmax attention, as the key component of the transformer architecture, presents a different extraction landscape: its nonlinearity is smooth and sequence-dependent, which renders the existing piecewise-linear-based method inapplicable. Recent work has investigated the learnability of a single-head attention model, while in the multi-head case, the parameters of the multi-head attention layer cannot be uniquely identified from value queries alone. In this paper, we propose the first attack against multi-head attention models. We formalize the extractable representative of multi-head attention and give a polynomial-time algorithm for extracting the parameters of the canonical representative model. We also test our algorithm end to end under finite precision, and successfully extract the parameters of a softmax attention model with token dimension 8 and 6 heads to accuracy $2^{-51}$. Moreover, we overcome the limitation that existing parameter extraction algorithms for one-layer single-head Transformers fail when the ReLU feedforward networks (FFNs) include bias terms. The effectiveness of our approach is demonstrated through model extraction attacks in finite-precision experiments. These results show that softmax normalization itself exposes exploitable algebraic structure, extending cryptanalytic extraction beyond ReLU-centric techniques.
Last updated:  2026-08-15
UC, Categorically: Rigorous Diagrammatic Proofs
Pooya Farshim, Martti Karvonen, Andre Knispel, Markulf Kohlweiss, and Philip Wadler
Category theory is a mathematical theory of composition, widely used in logic, computing, and physics. Here we apply it to give a theory of secure composition. In particular, we provide a categorical treatment of Canetti's Universal Composability (UC) framework for systems with a static number of parties and sessions, often termed UC for static systems, yielding four benefits. First, we present our results graphically yet retain rigor by applying a standard categorical technique known as string diagrams. In particular, our formulation of the composition theorem can be graphically verified with a short sequence of diagrams, while remaining translatable to equations and amenable to formal verification. Second, categories let us generalize so that our results extend beyond interactive Turing machines to other forms of computation, such as quantum computation or domain-specific languages. Third, categories help us drop some unnecessary restrictions of UC (e.g., our adversary can be a computational network rather than a single Turing machine); we prove equivalence between our variant and the usual UC, showing no expressiveness is lost. Finally, the categorical perspective leads us to identify and correct some minor technical oversights in the standard formulation of simple UC.
Last updated:  2026-08-15
From Rerandtopia to Interceptopia, the Anamorphic Encryption Saga Rises
Vincenzo Botta, Dario Catalano, Emanuele Giunta, Francesco Migliaro, Daniele Venturi, and Ivan Visconti
Nowadays, governments are world-wide pushing towards building infrastructures to intercept, decrypt and prevent communications among citizens with the goal of catching criminals. The recent notion of anamorphic encryption proposed by Persiano et al. [Eurocrypt 2022] faces the risks of abuses derived from such infrastructures that could be maliciously leveraged to realize the phantom menace of large-scale mass-surveillance programs. Several recent papers showed positive results on the existence of anamorphic encryption schemes, mostly confined to basic settings. In this work we consider extreme scenarios where in addition to obtaining secret keys, the authority actively tries to sanitize ciphertexts removing covert communication. Despite anamorphic encryption might look impossible to achieve in the above settings, we give new definitions and somewhat surprising positive results in two scenarios: Rerandtopia and Interceptopia. Our main construction consists of two layers of encryption. Interestingly, when carefully instantiated, our scheme achieves a notion of re-randomizable CCA encryption that outperforms the state of the art in terms of assumptions and efficiency.
Last updated:  2026-08-15
Toward Secure Compilation: Leakage Detection for Masked Implementations in Jasmin
Nicolai Schmitt, Sven Wroblewski, Fabio Campos, and Andreas Heinemann
Masking is a well-established software countermeasure against side-channel attacks, yet even algorithmically correct masked implementations can leak on real hardware once the compiler has performed instruction selection, register allocation, and stack allocation. Existing approaches either rely on leakage simulation, which is tied to a specific power model and computationally expensive, or on formal verification of the source program, which does not capture the effects introduced by the subsequent compilation stages. We address this gap from within the compiler and propose a leakage detection pass for the Jasmin language, integrated into its formally verified pipeline and operating on the intermediate representation before register and stack allocation. Rather than simulating power traces, the pass implements a configurable, microarchitecture-oriented leakage model that tracks the contact between shares, secrets, random values, and public values, making the root causes of the detected leakage explicit and enabling the detection of masking-order reductions. We validate the pass on 60 dedicated Jasmin test snippets covering all considered leakage sources and category combinations, and intend it as the foundation for a subsequent compiler stage that automatically removes the detected leakage, thus constituting a first step toward secure compilation.
Last updated:  2026-08-15
Relations Between the Uniform MQ Assumption and Other Multivariate Assumptions
Zijun Zhuang, Yingjie Zhang, and Jintai Ding
The uniform multivariate quadratic (UMQ) assumption states that it is hard to find a zero of a uniformly generated MQ function. It is the average-case hardness assumption about the MQ problem. In this paper, we investigate the relations among the UMQ assumption, the MQ one-wayness (MQOW) assumption, and the MQ second-preimage resistance (MQSPR) assumption. We show that UMQ and MQSPR tightly imply each other, and MQOW tightly implies UMQ. Then, we show that UMQ implies MQOW when $m\leq n+O(\log\lambda)$, where $n$ is the number of variables, $m$ is the number of MQ equations, and $\lambda$ is the security parameter. In particular, when $m\leq n+O(1)$, this implication is tight. As a corollary, we show that MQSPR implies MQOW under the same condition $m\leq n+O(\log\lambda)$, which is weaker than the compression condition $n=m+\omega(\log\lambda)$ required for the implication from SPR to OW for general function families. In particular, our result covers the square case $m=n$ as well as mildly overdetermined MQ systems satisfying $m=n+O(\log\lambda)$.
Last updated:  2026-08-15
Fully-Fluctuating Participation in Sleepy Consensus
Uncategorized
Yuval Efron, Joachim Neu, and Toniann Pitassi
Show abstract
Uncategorized
Proof-of-work allows Bitcoin to boast security amidst arbitrary fluctuations in participation of miners throughout time, so long as, at any point in time, a majority of hash power is honest. In recent years, however, the pendulum has shifted in favor of proof-of-stake-based consensus protocols. There, the sleepy model is the most prominent model for handling fluctuating participation of nodes. However, to date, no protocol in the sleepy model rivals Bitcoin in its robustness to drastic fluctuations in participation levels, with state-of-the-art protocols making various restrictive assumptions. In this work, we present a new adversary model, called external adversary. Intuitively, in our model, corrupt nodes do not divulge information about their secret keys. In this model, we show that protocols in the sleepy model can meaningfully claim to remain secure against fully fluctuating participation, without compromising efficiency or corruption resilience. Our adversary model is quite natural, and arguably naturally captures the process via which malicious behavior arises in protocols, as opposed to traditional worst-case modeling. On top of which, the model is also theoretically appealing, circumventing a barrier established in a recent work of Malkhi, Momose, and Ren.
Last updated:  2026-08-14
High-Precision Exact FHE Made Simple, General, and Fast
Chris Peikert, Doron Zarchy, and Guy Zyskind
Many important applications of fully homomorphic encryption (FHE) require arithmetic on *high-precision* plaintexts, e.g., from the ring $\mathbb{Z}_p$ for a huge prime or power-of-two modulus $p$. The classic FHE schemes are poorly suited to this, because the inverse error rate of fresh ciphertexts, and the error growth under homomorphic multiplication, are both larger than $p$, which results in large and inefficient parameters. While there are now several works addressing this problem, the landscape for *exact* (as opposed to approximate) FHE is highly fragmented: known solutions either work only for certain rare plaintext moduli having very special forms (sometimes using non-standard ciphertext rings that lack other important features for FHE), or have quite complicated and high-latency constructions. This work gives a very simple, general, and efficient technique for high-precision exact FHE, in which the error rates and growth match those of classic schemes for *exponentially smaller* precision. The runtimes can scale only *quasi-linearly* (versus quadratically for classic schemes) with the plaintext precision $\log p$, and are fast in practice. Also in contrast to all prior works, our technique works for *any integer modulus* and over *any underlying (number) ring*---or even with no structured ring at all, making it the first solution that can be based on plain LWE. Moreover, it is *fully compatible with prior FHE techniques* for fast ring arithmetic, plaintext packing and SIMD operations, bootstrapping, etc. For typical parameters and security levels, our (preliminary, unoptimized, single-threaded) implementation does homomorphic $\mathbb{Z}_{2^{64}}$-multiplication in just tens of milliseconds, and obtains a four- to five-fold increase in multiplicative depth versus classic FHE schemes.
Last updated:  2026-08-14
Post-Quantum Internet Key Exchange via Authenticated Forward-Secure KEM
Yunlei Zhao, Biming Zhou, Zhixiang Zhao, Yifan Dong, Cheng Huang, and Haodong Jiang
In this work, we present a new framework for signature-free, post-quantum secure authenticated key exchange (AKE) that simultaneously satisfies: (1) exchanging at most two standard ciphertexts of a key encapsulation mechanism (KEM); (2) computational symmetry; (3) perfect forward secrecy (PFS); (4) strong resilience to secret-state exposure; (5) strong resistance to decryption-error attacks; (6) admitting instantiations based on the native structure of \textsf{ML-KEM} under the \textsf{MLWE} assumption; and (7) provable security in both the random oracle model (ROM) and the quantum-accessible random oracle model (QROM) under the post-id $\mathsf{eCK}\mbox{-}\mathsf{PFS}$ framework. This resolves several fundamental open questions in the literature. The core technical building block is a new cryptographic primitive, called an \emph{authenticated forward-secure} KEM (AFS-KEM), which unifies authentication and forward secrecy within a single KEM abstraction and may be of independent interest.
Last updated:  2026-08-14
Equivalence Between Average-Case Hardness of Learning and Cryptography for Mixed Quantum States
Alexandru Cojocaru and Laura Lewis
The relationship between cryptography and learning theory has long been a central theme in the foundations of theoretical computer science: cryptographic primitives can imply hardness of learning, while hardness of learning can in turn be used to construct cryptographic schemes. Recent works have begun exploring analogous connections in the quantum setting, relating the average-case hardness of learning quantum states (AHL) to cryptographic primitives such as one-way state generators (OWSG). Despite recent progress exploring this for pure states, the relationship for mixed states has remained an open question. In this work, we prove that the existence of AHL for mixed quantum states is equivalent to the existence of inefficiently verifiable one-way state generators (IV-OWSGs). As a consequence, this relates mixed-state AHL to EFI pairs. Moreover, as a corollary of existing results, we obtain a separation between IV-OWSGs and OWSGs relative to the SWAP oracle.
Last updated:  2026-08-14
Concurrently Secure Compact Blind Signatures from Module-SIS
Olivier Blazy, Lola-Baie Mallordy, and Weiqiang Wen
A blind signature scheme allows a user to interact with a signer to obtain a valid signature on a message, while ensuring that the signer cannot learn any information on the message being signed, nor link a given couple message-signature to the specific interaction that produced it (blindness). In round-optimal (i.e., two-move) blind signature schemes, a user sends a request (typically a commitment) for a message, and the signer responds with a signature. To achieve blindness, the resulting blind signature usually consists of a zero-knowledge proof of knowledge of a valid signature from the signer on a request. This reliance on zero-knowledge proofs has become the main bottleneck in reducing the blind signature size. In particular, state-of-the-art lattice-based blind signature schemes are instantiated based on the zero-knowledge proof system from [Lyubashevsky et al., EUROCRYPT, 2022], which results in blind signatures of at least 22 KB. In this work, we carefully design a blind signature protocol following the classical lattice-based Σ-protocol as in [Ducas et al., CRYPTO, 2013], so that the last component naturally forms a short preimage of the hash of the message, as a classical GPV signature. As a result, this removes the need for zero-knowledge proofs in the blind signature. Eventually, this design allows us to obtain a significantly more compact blind signature of size 4.7 KB, with concurrent security under the Module-SIS assumption. As a trade-off, our protocol may require more than one round with small probability, due to the rejection sampling in lattice-based Σ-protocols. Under our proposed parameters, however, the expected number of rounds for honest users can be as small as 1.1, which is very close to optimal. To minimize the number of rounds, we require users to prove that they failed to derive a blind signature in the previous round, before starting a new one. This technique yields a moderately looser bound on the expected number of rounds for malicious users, who will be forced to terminate in at most 2.6 rounds.
Last updated:  2026-08-14
A Hybrid Post-Quantum Encryption Architecture with Self-Hosted Key Management for SME Cloud Data Protection
Uncategorized
Muhammad Shaheer Bin Junaid
Show abstract
Uncategorized
Harvesting ciphertext from cloud storage needs no quantum computer; decrypting it later does. That gap is the harvest-now-decrypt-later exposure: anything protected by RSA or ECDH today that must stay secret for decades is already compromised. Small and medium-sized enterprises are least able to respond: they neither run the infrastructure on which their data sits on nor employ a cryptographer. Bespoke migration suits firms with security budgets; a managed key service relocates trust rather than removing it. The obstacle is architectural, not cryptographic. We present Quantum Cloud Guard (QCG), a software-only three-layer architecture. No prior SME-oriented system combines its three elements: client-side hybrid post-quantum encryption, self-hosted key custody with client-verifiable ML-DSA-87 signatures on served keys, and an integrated application-layer abuse-prevention gateway. Files never leave the client: each is sealed under AES-256-GCM, its key wrapped to an ML-KEM-1024 public key from the enterprise’s key service. The enterprise alone administers it; it signs every key with ML-DSA-87, so a client that pinned it detects substitution. Separating key custody from data custody is the point: a provider holding both can read the data. On a 24 MHz STM32F407, ML-KEM-1024 key generation takes 40.8 ms and decapsulation 44.0 ms; on the server every post-quantum operation stays sub-millisecond, signing adding 0.24 ms per request. The service runs on a 4.49 EUR/month virtual server. Under sustained flooding, the in-process gateway Sentinel Gate rejected 98.8% of attack traffic while a legitimate client’s median latency moved from 621 to 625 ms. Being single-source, this shows filtering effectiveness, not DDoS resilience.
Last updated:  2026-08-14
A Torus-Structured Generalisation of NTRU: the NTC Assumption, its Cryptanalysis, and a Compact KEM
Sidoine Djimnaibeye, Djiby Sow, and Mahamat Borgou Hassan
We introduce Noisy Torus Conjugation (NTC), a lattice assumption in which a short secret is confined to a non-split maximal torus of $GL_k(R_q)$ and acts by conjugation on a uniform matrix, the result being masked by a short additive error. NTRU is the $k=1$ member of the family. Passing to $k \ge 2$ changes the geometry of the underlying lattice in two specific ways. The planted module occupies a fraction $1/(2k)$ of the published lattice's dimension, against NTRU's $1/2$; and the norm-map shortcut that governs the overstretched regime is blocked once the conjugated matrix is required to be uniform over the full matrix algebra instead of the torus. We develop the structure theory of the assumption: marginal uniformity of each component, invariance along the torus orbit, a rigidity theorem identifying the full set of short solutions, and a reduction from search to decision. On it we build an IND-CCA key encapsulation mechanism whose passive security reduces tightly to NTC together with one isolated decisional assumption. At NIST categories 1, 3 and 5 it reaches public keys within 1.08 to 1.16 times Kyber's and ciphertexts 2.0 to 2.1 times Kyber's. The new assumption is not load-bearing but purchasable. Widening the key distribution to the smoothing parameter of the key lattice would make the public key statistically uniform and remove it altogether, leaving IND-CPA on module-LWE and hence on a worst-case problem. We price that variant at a factor 3.4 on the public key and 4.0 on the ciphertext. It rests, however, on a regularity statement not established for the completely split rings our transform uses; we isolate that statement as a conjecture and give a modulus class for which it is not needed. Concrete parameters are selected with an estimator calibrated against the published core-SVP figures of Kyber, and validated against a hybrid meet-in-the-middle model whose single free constant is fitted on Kyber. The fatigue predictions underlying the modulus window are tested further by lattice reduction. We reduce small instances of the published lattice against NTRU controls of identical dimension, determinant and planted-vector norm, and at every modulus the NTRU plant is discovered as a dense sublattice while the sparser NTC plant is not. A companion paper builds a Fiat-Shamir-with-aborts signature from the same assumption. The assumption is new and has no worst-case reduction; we state throughout what is proved, what is heuristic, what is measured, and what remains open.
Last updated:  2026-08-14
Finding Dense Submodules with Algebraic Lattice Reduction
Alexander Karenin and Elena Kirshanova
We prove an algebraic analogue of Pataki-Tural lemma (Pataki-Tural, arXiv:0804.4014, 2008) -- the main tool in analysing the so-called overstretched regime of NTRU. Our result generalizes this lemma from Euclidean lattices to modules over any number field enabling us to look at NTRU as rank-2 module over cyclotomic number fields with a rank-1 dense submodule generated by the NTRU secret key. For Euclidean lattices, this overstretched regime occurs for large moduli $q$ and enables to detect a dense sublattice in NTRU lattices leading to faster NTRU key recovery. We formulate an algebraic version of this event, the so-called Dense Submodule Discovery (DSD) event, and heuristically predict under which conditions this event happens. For that, we formulate an algebraic version of the Geometric Series Assumption -- an heuristic tool that describes the behaviour of algebraic lattice reduction algorithms. We verify this assumption by implementing an algebraic LLL -- an analog of classical LLL lattice reduction that operates on the module level. Our experiments verify the introduced heuristic, enabling us to predict the algebraic DSD event. UPD: minor notation fixes.
Last updated:  2026-08-14
Theoretical Open Problems in Symmetric Cryptography: Verifiable LLM-Guided Analysis
Yufei Yuan, Yaoda Hu, Yixin Zhang, Lei Zhang, and Wenling Wu
We present the Pilot--Sailor Framework, an LLM-guided system for studying theoretical open problems in symmetric cryptography. Pilot proposes intermediate statements and proof plans. Sailor attempts formal proofs, and the proof assistant admits only checked declarations to the verified context. We apply this methodology to Boolean-function theory and symmetric cryptanalysis through fourteen mathematical case studies, comprising complete resolutions, corrected formulations, counterexamples, and scoped quantitative advances. In particular, we prove the original pointwise Tu--Deng conjecture for all word lengths and admissible residues. We further characterize equality in this bound: if \(t\) has \(z\) zero bits, equality holds exactly when every cyclic gap between consecutive zeros is at least \(z\). This criterion also gives a closed formula for the number of equality cases for each \(z\). We also prove that, for \(n=2k\geq6\) and \(k<m<2k\), every mapping \(F:\mathbb F_2^n\to\mathbb F_2^m\) satisfies \(\operatorname{NL}(F)\leq2^{n-1}-2^{n/2-1}-2\). This improves both the covering-radius estimate and the bound obtained from Nyberg's obstruction and integrality. Using an exact computer-assisted spectral classification, we also prove that the maximum nonlinearity of a balanced Boolean function in eight variables is 116, resolving whether the value 118 can occur. Beyond the well-known long-standing problems highlighted above, we also establish new results for ten further research questions in symmetric cryptography.
Last updated:  2026-08-14
A Unifying Umbrella for Circular-Secure Cryptographic Primitives
Fuyuki Kitagawa and Takahiro Matsuda
The main message of this paper is that several seemingly different circular-style primitives are existentially equivalent. In particular, somewhat surprisingly, we show that hinting PRGs (Koppula and Waters, CRYPTO 2019) are equivalent to secret-key encryption (SKE) schemes satisfying key-dependent-message (KDM) security. As a conceptual centerpiece, we introduce key-dependent-shift (KDS) security for weak pseudorandom functions (PRFs), and show that they serve as a convenient hub connecting these primitives. We also show that KDS secure weak PRFs imply other cryptographic primitives with circular-style security, such as linear-resistant PRGs (Hajiabadi et al., ITC 2023) and hinting weak PRFs (Alamati and Patranabis, ASIACRYPT 2022), all of which are thus existentially equivalent to KDM secure SKE and hinting PRGs as well. Hence, KDS secure weak PRFs can be thought of as a unifying umbrella for circular-secure cryptographic primitives. As another application of our new notion, we show that KDS security enables new constructions of public-key encryption (PKE) satisfying randomness-dependent-message (RDM) security and correlated-product secure trapdoor functions (TDFs). Our key technical contribution is a generic construction of KDS secure weak PRFs from any KDM secure SKE.
Last updated:  2026-08-14
Pruning Merkle-Tree Consistent Accumulator
Anna Mendonca, Hudson Shi, Ivan Pryvalov, and Amir Herzberg
Authenticated data structures are widely used to compute compact digests of evolving collections of elements and to support efficient verification of element inclusion. However, the authenticated collection often should not grow forever: older elements may expire and no longer require verification. Many implemented append-only approaches, for example used in Certificate Transparency (CT), do not directly support this setting, since previously accumulated elements remain part of the authenticated state indefinitely. In this work, we introduce a pruning accumulator, a stateful accumulator that supports both incremental addition of new elements and pruning of an old prefix of previously accumulated elements. The resulting digest represents the unpruned sequence, while pruned elements are removed from the authenticated state. Unpruned elements continue to support proof-of-inclusion verification, proof updates, update verification, and consistency checks. This captures applications that require authenticated, incrementally maintained state over a moving window of elements. We present two constructions of Merkle-tree-based pruning accumulators, both with efficient accumulation, prefix pruning, proof generation, proof updating, and verification. The constructions preserve the standard Merkle-tree style of verification for active elements while reducing long-term storage requirements. We provide formal definitions, correctness and security analysis, an open-source implementation, and experimental evaluation demonstrating the performance benefits of pruning.
Last updated:  2026-08-13
Non-Interactive Translation of Winternitz Signatures to Lamport Signatures via Secret Sharing
Mikhail Sergeevitch, Konrad Staniec, David Tse, Nikhil Vanjani, and Robin Linus Woll
BitVM2 brought arbitrary program execution to Bitcoin, yielding the first light-client-based bridge to its second layers and reducing the trust required at setup to a single honest participant. Its successors, BitVM3 and BABE, move the disputed computation off-chain into Garbled Circuits (GCs), cutting worst-case on-chain dispute costs by roughly three orders of magnitude and so opening participation beyond well-capitalized operators; BABE in turn cuts the off-chain storage and setup costs of BitVM3's garbled circuits by a comparable factor. What still reaches the chain, however, is bulkier than it need be. BitVM2 commits its data with compact Winternitz one-time signatures (WOTS), whereas BitVM3 and BABE must reveal GC input labels on-chain and so fall back on far bulkier Lamport signatures, which play two roles at once: GC input labels and Bitcoin-verifiable commitments. WOTS cannot simply be substituted, because its hash chains are monotonic---an evaluator holding one state's preimage can hash forward and obtain several active labels on a single input wire, destroying the circuit's privacy. Recovering BitVM2's compactness therefore calls for a practical GC whose input labels are WOTS signatures---a construction that has remained out of reach. We close this gap with a non-interactive \emph{WOTS-to-Lamport translation gadget}: the garbler commits on-chain using compact WOTS chains, and the evaluator expands them off-chain into exactly the orthogonal Lamport labels the GC consumes, learning nothing about the mutually exclusive ones. A naive translation table that enumerated messages would be exponentially large. Two symmetries bring it down to quadratic: reconstruction from a Shamir sharing depends only on \emph{how many} shares are held and not on \emph{which}, which collapses the exponentially many messages onto the single checksum weight WOTS already computes; and monotonicity, the very property that made WOTS unusable, orders an evaluator's access by inclusion. We model the gadget as a garbling scheme and prove it adaptively private. Applied to BABE, it restores WOTS-scale commitments to a GC-based protocol, cutting total on-chain script size by more than $3\times$ and bringing dispute transactions within Bitcoin's standardness limit.
Last updated:  2026-08-13
Incomplete Ciphertext Comparison in ML-KEM: From an IND-CCA2 Break to Key Recovery
Bhabani Sankar Das
ML-KEM is IND-CCA2 secure only because of one check inside decapsulation: the receiver re-encrypts the message it recovered and returns the true shared secret only if the result matches the received ciphertext exactly. This is the Fujisaki–Okamoto (FO) check. wolfSSL implemented it in hand-written SIMD assembly, and on two backends it compared fewer than all of the ciphertext bytes. The x86-64 AVX2 path compared 1536 of 1568 bytes; the ARM64 NEON path compared roughly half. These bugs were documented as a weakening of IND-CCA2 security, in that a tampered ciphertext can slip past the check. We show they are worse than that. The bytes the check skips carry the tail of the decryption noise, and that noise is an exact linear function of the secret key. An attacker who varies those unchecked bytes and watches the decapsulation output reads the noise off one coordinate at a time. Stacking the measurements gives an overdetermined linear system in the secret, which we solve by ordinary least squares with no lattice reduction. The measurement is a plaintext-checking oracle, the same primitive that key-mismatch attacks use. What is new is where it comes from. Reading it off the unchecked v-tail, rather than from chosen sparse-u ciphertexts, means it survives even when u is fully validated, as on AVX2, so the standard "validate all of u" hardening does not close it. The price is queries, 10⁵ to 10⁶ against a few thousand for key-mismatch, so the contribution is reach rather than efficiency. We recover most of the ML-KEM-1024 private key end-to-end against the shipped binaries on both backends: 98.0% of the 2048 secret coefficients at 400 ciphertexts on AVX2, and 98.5% at 600 on NEON, reaching the full key with more ciphertexts (the verified reference model recovers all 2048 at about 1300 ciphertexts). The cost appears to track the geometry of which bytes go unchecked more than their number: NEON leaves about 2.5× more coordinates unchecked than AVX2 yet needs more ciphertexts. We conclude that an incomplete FO comparison is a key-recovery vulnerability, and should be triaged as one.
Last updated:  2026-08-13
New Results on the Density of Irreducible NFSRs
Daoyuan Zhang and Dongdai Lin
Nonlinear feedback shift registers (NFSRs) are fundamental building blocks for modern stream-cipher constructions. An $n$-stage NFSR $f$ is classified as irreducible when the output sequence set of $f$ does not contain the output family of any NFSR of order less than $n$. Existing research has established upper and lower bounds for the density of irreducible NFSRs, confining this value within the range of 0.4461 to 0.4834. This study tightens these bounding intervals with high accuracy, reducing the original 0.04 gap down to only $8\times10^{-6}$.
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.