Hints are a concept from side-channel analysis referring to small amounts of information that enable an adversary, via a potentially very efficient procedure, to extract the secret. We take this cryptanalytic concept and give it a constructive make-over. We formalize a short $\Sigma$-protocol based on the famous Goldreich, Micali, Wigderson protocol, in which the responses are not of the full witness size, but are only small hints. The hints can be used to extract the full response. We show that under our formalization, these protocols preserve the security properties of $\Sigma$-protocols. We instantiate a practical protocol using a group action from tensor isomorphism and an efficient extracting procedure borrowed from an attack by Narayanan et al. on the MEDS signature scheme. We derive a signature scheme, called miniMEDS, which demonstrates practically the benefits of our hint-based construction, allowing for 22%-24% reduction in signature size compared to the latest updated parameters of MEDS.

Fuzzy Labeled Private Set Intersection (FLPSI) lets a receiver learn the labels of enrolled records that are similar to its query, and nothing else. FLPSI can be built in several ways. Constructions based on a set-threshold reduction reach practical performance: a query matches a record when the two agree on a threshold number of components. These constructions delegate the private matching to an inner set-threshold kernel. We study its homomorphic form, which combines leveled-BFV homomorphic encryption (HE), a garbled circuit, and secret sharing to decide the match under encryption and release the record's label. We identify a composition gap in this kernel, an instance of a protocol-level problem: efficiency is bought with a per-trial false-accept probability, but one query runs a trial for every record, so the error compounds with the database size into the kernel's realization soundness error (RSE), the rate at which it accepts a query the plaintext matcher would reject. The RSE is a reliability property of the cryptographic matching layer, not the matcher's accuracy. On a spurious accept the kernel also returns a value the plaintext matcher would never produce. A sound kernel must contribute zero or negligible RSE of its own. We formalize this requirement as a composable security property, give a closed-form bound on the receiver's advantage, and close the gap with CSTPSI, a kernel that runs independent token rounds and raises the per-trial bound to a matching power. We prove CSTPSI secure in the semi-honest model. The closed-form bound sets the round count: two token rounds suffice for million-scale databases and three for billion-scale at the $10^{-6}$ engineering threshold. Our evaluation confirms the prediction. At a million records the baseline kernel's RSE reaches $100\%$ while CSTPSI holds it at $0$ in every measured configuration. CSTPSI decouples threshold-checking and upload costs from label size. For large labels at small to moderate scale it is more than $20\times$ faster than the baseline kernel, with up to $93\%$ less communication. It converges to the baseline only at the million-scale database size. Our implementation, with a one-command reproducibility harness, is publicly available.

Stateful hash-based signature schemes like LMS and XMSS are built on the Winternitz one-time signature. The effect of state reuse for these schemes has been shown to be disastrous [1][2]. This paper shows that the signer can mitigate this effect if a state is reused only once. This is achieved by repeating the randomized hashing step until a hash value with specific properties is found. Our results show that at least 80 bits of security can be achieved in 99% of the key reuses, an improvement of 49 bits. This requires the signer to repeat the randomized hashing step 1.4 million times on average. Slightly lower security can be reached with much less hashing.

Secure Multi-Party Computation (MPC) enables collaborative analytics without exposing raw data. Yet, complex data retrieval operations in relational databases (i.e., relational queries) remain limited by scalability bottlenecks: oblivious operators must pad intermediate results to worst-case sizes to prevent information leakage, thereby inflating communication and computation costs. We propose Resizer, a lightweight operator that can be inserted transparently into relational query plans to bound intermediate result sizes while preserving rigorous privacy guarantees. Resizer reduces intermediate results from fully-oblivious to noisy size bounds that satisfy differential privacy (DP). We propose two Resizer variants, shuffle-based and sort-based, and provide a formal analysis of the privacy guarantees and security in the semi-honest model. We evaluate the Resizer variants in the ORQ framework under semi-honest and honest-majority assumptions using TPC-H benchmark queries, demonstrating that Resizer incurs negligible overhead while reducing data volume. In both LAN and WAN settings, complex queries achieve speedups compared with state-of-the-art oblivious baselines, confirming that Resizer reduces the padding bottleneck and enables scalable, privacy-preserving relational analytics.

In 2020, a coordinated law-enforcement effort infiltrated Encrochat, an end-to-end encrypted service provider, exfiltrating historical and real-time data and metadata over months. Encrochat was used extensively by organised crime, and the data from the operation was used as supporting evidence in over 6,000 arrests and related prosecutions across Europe. Encrochat's architecture was vertically integrated, with the company acting as both a device vendor and service provider; Encrochat sold modified Android smartphones with its own PKI and custom applications, including encrypted messaging based on the Signal protocol. In this work, we give the most detailed public account to date of Encrochat's infrastructure and how it was compromised.

HAWK is a signature scheme that was introduced in 2022, and uses the lattice isomorphism problem (LIP) as a basis for post-quantum cryptography. In this work, we describe a classical algorithm that recovers the HAWK secret key in probabilistic polynomial time, assuming four number-theoretic heuristics. The reduction from the rank-2 module-LIP instances underlying HAWK to nrdPIP (Eurocrypt '25) is central to our algorithm. At a high level, we first conjugate the HAWK public Gram matrix $G$ by a random lower-triangular unimodular matrix $U$ with `short' entries, forming a new Gram matrix $G':=U^\ast GU$, and then test whether the $\mathcal{O}$-nrdPIP instance attached to $G'$ is unusually easy. In particular, for a non-negligible proportion of such instances $G'$, one can use the Lenstra-Silverberg algorithm to solve the corresponding $\mathcal{O}$-nrdPIP instance using a subfield approach. By resampling $U$ until such an instance is uncovered and solved, which can be seen as `re-randomising' the $\mathcal{O}$-nrdPIP instance whilst fixing the corresponding module-LIP instance, we are then able to recover a valid HAWK private key. At the time of writing, we do not claim that HAWK is broken, as we have not yet verified these heuristics experimentally. On the other hand, these heuristics seem to be very plausible, and we hope to be able to verify this in the future with an implementation of our algorithm. Update (30/06): Following discussions with Daniel Apon and Markku-Juhani Saarinen, we acknowledge that Heuristic 4 is insufficient to conclude that the main algorithm runs in polynomial time, and in fact the main algorithm appears to run in super-polynomial time. This mistake originates from the count of ideals of norm $q’$ in $\mathcal{O}_F$: one must include fractional ideals in this count, of which there are many. We note as an aside that Heuristics 1-3 have been independently experimentally verified. We would also like to thank the HAWK team and Alice Pellet-Mary for their responses to our work.

Folding schemes are gaining traction recently as they unlock practical instantiations of incrementally verifiable computation (IVC) and proof-carrying data (PCD). In particular, there has been a growing interest in folding schemes for high-degree relations, as these can efficiently arithmetize complex computations. While the landscape is vast, all lattice-based constructions such as Latticefold+, (Super)Neo, and Cyclo heavily rely on the sumcheck protocol. Sumcheck gives efficient proving times, but the verifier circuits become very large, partially because of the many random oracle invocations required. These hinder the efficiency of IVC and PCD instantiations, as the prover must prove the execution of the verifier circuit at every iteration. We present ProtogaLattice, a new lattice-based folding scheme for general high-degree polynomial relations that drastically reduces the size of the verifier's circuits. We deviate from the sumcheck approach and instead take inspiration from Protostar [Bünz & Chen, Asiacrypt '23] and Protogalaxy [Eagen & Gabizon, '23], which fold witnesses using algebraic techniques in a constant number of rounds. Our contribution is threefold: (1) a novel technique to achieve PCD through Protogalaxy, which we find of interest also in the classical (i.e. pairing-based) setting, (2) a folding scheme that combines multiple instances of polynomial relations into accumulators, and (3) a bootstrapping protocol to reduce the norm of the witnesses underlying these accumulators. A full iteration of ProtogaLattice requires only four random oracle calls (not counting the overhead induced by the extra range proof used as a black-box). Our techniques open new directions towards building lattice-based proofs that support more expressive relations and that present smaller recursion overheads.

Multi-Scalar Multiplication is a critical operation in most pairing-based zero knowledge proofs. In a lot of studies, memory limitations have often been reported to be the primary bottleneck preventing the calculation of larger MSMs. In this paper, we are particularly interested in the acceleration of this operation on devices with limited memory. Pippenger’s algorithm (also known as bucket method) is the most efficient and, consequently, the most widely used method to calculate Multi-Scalar Multiplications. We propose an optimization of Pippenger’s algorithm which is at least as efficient as the original, and significantly more effective when operating under limited memory. The main idea is to use an adapted number of buckets depending on the available memory instead of $2^w −1$. We conducted tests on the curve BLS12-381 with Multi-Scalar Multiplications ranging from $2^8$ to $2^{14}$ points. The results obtained demonstrate that we have a very significant gain (up to $40\%$) for very limited memories. This gain gradually decreases as more memory becomes available, until we achieve performance comparable to Pippenger’s once memory is no longer limited. For example, in a Multi-Scalar Multiplication with $2^{13}$ points, we observe a gain of $40\%$ with only $1$ KB of memory, $20\%$ with $15$ KB, $15\%$ with $35$ KB, and so on, down to $1.5\%$ once memory is no longer a constraint.

Ensuring the integrity and traceability of data transformations in distributed systems presents significant challenges, particularly in environments where data privacy and decentralization are paramount. This paper introduces a novel secure lineage verification system based on Directed Acyclic Graphs (DAGs) and homomorphic hash functions, VERDICT. Our approach represents data artifacts and their transformations as two interconnected DAGs: a Data DAG tracking data dependencies and an Event DAG capturing causality between transformation events. We propose a level-based DAG compression technique that decomposes these graphs based on distance from genesis nodes, enabling efficient verification through skip DAG structures. The system incorporates bucket indexing and Merkle tree verification to provide cryptographic guarantees of data and event existence. We present formal algorithms for DAG construction, level-based hashing, skip DAG traversal, and verification processes. Security analysis demonstrates the system’s resistance to tampering and modification attacks while maintaining privacy. Replay attacks are prevented through an application-layer challenge-response mechanism. Our approach has significant applications in federated learning environments and decentralized architectures, where it can serve as a notary component for tracing events without compromising data confidentiality. Theoretical analysis shows that our method achieves verification in 𝑂(log𝑛) time in the number of DAG levels, independent of the number of nodes per level, making it suitable for large-scale distributed systems.

Hybrid Homomorphic Encryption (HHE) is emerging as a practical alternative to fully homomorphic encryption by offloading computational overhead to the cloud. Despite the growing number of HHE schemes and implementations, no unified evaluation methodology currently exists. In this work, we present a comprehensive and reproducible benchmarking framework covering both standard and HE-friendly HHE schemes. We analyze and evaluate 19 open-source HHE frameworks, comprising 218 distinct ciphers' benchmarks, across diverse HE libraries and programming languages. To ensure fair comparison, we interpret the main results under an HHE-128 security target, separating standardized or author-claimed 128-bit settings from below-target measurements. Our contributions include a unified repository, a language-agnostic benchmarking tool, and detailed metrics on runtime and memory usage. The results offer actionable insights into the security-aware performance trade-offs of each design and lay the groundwork for standardizing future HHE evaluations.

Post-quantum signatures built from Fiat--Shamir transforms of zero-knowledge identification protocols---including LESS, CROSS, and MEDS---use GGM-tree seed compression to shrink signatures, revealing only the seeds of public rounds while hiding the challenge-dependent ones. This mechanism introduces a fault-attack surface: faulting the seed-publication can expose hidden seeds alongside their zero-knowledge responses, enabling recovery of secret information. We introduce the Generic ZK Seed Tree (GZKST), a unified abstraction of GGM-tree generation, challenge partitioning, and seed publication across these schemes, and formalize its correctness and seed-hiding invariants. We show that prior attacks on LESS-v1 and LESS-v2 violate the same invariant despite targeting different implementation layers and tree constructions, derive generic key-recovery algorithms from this view, and bound the number of effective faulted signatures needed for full recovery---only a few successful queries suffice for every MEDS parameter set. We further demonstrate the attacks in practice through clock-glitch fault injection against the MEDS reference implementation on an ARM Cortex-M4 (ChipWhisperer-Lite), identifying multiple exploitable surfaces in tree traversal and path construction that enable complete tree disclosure, partial subtree recovery, or leakage of hidden leaves.

In this paper, we prove the post-quantum security of the Tweakable Key-Alternating Feistel cipher (TKAF) with a public random function in the Q1 model, under the assumption that the adversary is given quantum access to the internal primitive. Specifically, our target is the TKAF studied in the classical setting by Yan et al. (ACNS 2020), where the tweak is injected into the round-key XOR via a hash function of $\epsilon$-AXU family. Our proof draws on the post-quantum security proof for the (non-tweakable) key-alternating Feistel ciphers by Basak et al. (ASIACRYPT 2025), and adapts it to the tweakable setting and further to the multi-key setting, where an adversary can access multiple classical oracles. As a result, we prove that the 3-round TKAF is post-quantum TPRP-secure and the 4-round TKAF is post-quantum STPRP-secure. Specifically, under the assumption that the adversary is given classical access to $\ell$ independently specified oracles, at least $\mathrm{\Omega} (2^{n/3}/\ell^{2/3})$ classical and quantum queries or $\mathrm{\Omega}(\epsilon^{-1/2})$ classical queries are required to break the post-quantum TPRP security of the 3-round TKAF and to break the post-quantum STPRP security of the 4-round TKAF.

We prove a folklore characterization of the BN pairing subgroup as the kernel of a relative trace map on the $n$-torsion points.

Approval phishing is a form of Web3 phishing that exploits token approval mechanisms to trick users into granting attackers spending authority over their tokens. As attackers increasingly hijack legitimate websites, URL-based detection alone becomes insufficient, leaving crypto wallets as the last line of defense. Based on the characteristics of approval mechanisms, we propose four wallet-based interventions for mitigating approval phishing: Spending Cap Suggestion, Active Spender Warning, Passive Spender Warning, and Delayed Confirmation. We evaluate the interventions through a between-subjects experiment (n = 364) and semi-structured interviews (n = 23). Compared with the control group, the Spending Cap Suggestion condition significantly increases the likelihood that users set spending caps. The Active Spender Warning, Passive Spender Warning, and Delayed Confirmation conditions all increase cancellation rates of phishing tasks, although the increases are statistically significant only for Active Spender Warning and Delayed Confirmation conditions. The effectiveness of the interventions varies across users, as users may struggle to interpret suspicious cues and focus on transaction outcomes while overlooking approval details. Our findings highlight the need to strengthen defenses against such attacks by increasing users' awareness of post-approval consequences and supporting approval-parameter verification at the moment of authorization.

Nation State Agencies go to great lengths to obtain signal intelligence, including backdooring cryptographic standards and equipment. Although the existence of these backdoor efforts is common knowledge, only few of known backdoored systems have been publicly analysed. In this paper we present the first detailed $\textit{forensic cryptanalysis}$ of the backdoored UA-8295 message terminal and we try to answer questions how the UA-8295's backdoor was designed and for which attack. Towards a better understanding of real-world backdoor design, we posit a $\textit{Backdoor Conjecture}$ that provides handles to reason about the design of backdoors and the attacks they are designed for.

Audio recordings are often used as evidence, but modern forgery tools make their origin harder to verify. Existing authentication methods require releasing the original signed recording, which exposes sensitive source content as well as provenance information. Redacting the audio avoids that disclosure, but doing so also invalidates the original signature. Revealing the edit operations to prove edit compliance can also disclose the redacted content. This creates a conflict for existing approaches: authenticating a released audio file requires disclosing the original audio, edit operations, or identity of the recording device, but preserving privacy requires keeping all three hidden. In this work, we propose $\textit{Privacy-Preserving Audio Authentication Systems}$ (PPAAS). PPAAS uses a single relation that binds source provenance and edit correctness to the same hidden witness. This witness includes both the attested source recording and device attestation, so the verifier can be convinced that the released audio came from an authorized device and was obtained through allowed edits, without learning the source recording, the edit operations, or which enrolled device produced it. We formalize this notion and provide two constructions adapted to different editing scenarios. The first is a $\textit{segmentation-based}$ construction that requires zero-knowledge proofs only for actively edited segments and is therefore well-suited to sparse edits. The second is an $\textit{iteration-based}$ construction that uses Incrementally Verifiable Computation (IVC) with zero-knowledge compression to fold repeated checks into a single proof, which is efficient for dense edits. Our evaluations show the practicality of both constructions: the segmentation-based approach minimizes cost for sparse edits, whereas the iteration-based approach becomes preferable as edit density increases.

Secure Multi-Party Computation (MPC) is a cryptographic primitive that enables multiple parties to jointly compute a function over their inputs without revealing the inputs. An MPC protocol is required to provide security against adversarial behavior, typically considered in two classic models: the \textit{semi-honest} model, where adversaries follow the protocol but attempt to learn additional information from the transcript, and the \textit{malicious} model, where adversaries may arbitrarily deviate from the protocol. Protocols secure against semi-honest adversaries are often more efficient, but in many real-world applications the stronger guarantee of malicious security is required. In this work, we propose an efficient MPC protocol secure against static malicious adversaries controlling at most $t<n/3$ out of $n$ parties. Our protocol builds on Shamir's secret sharing and follows a compiler-based approach: the parties first evaluate the circuit using a semi-honest protocol and then run a verification procedure that enables honest parties to detect cheating except with small statistical error. Our construction injects fresh randomness into the verification procedure to detect cheating even in the presence of incorrect multiplication triples. It also reduces communication overhead by replacing several invocations of multiplication verification with local degree-$2t$ computations and a batched opening, while keeping the local verification cost comparable to or lower than that of prior protocols. We give a concrete instantiation of the compiler and prove that the resulting protocol is secure against malicious adversaries.

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.

SQIsign encodes its response isogeny via a two-dimensional representation on a product of elliptic curves, using the Kani construction. We analyze the algebraic structure of this encoding in detail, with a focus on the role of the auxiliary isogeny and its implications for strong unforgeability. We show that the anti-isometry $\psi$ determining the Kani kernel is publicly computable from the torsion-point images of the component and auxiliary isogenies alone, that the automorphism orbit $\{\psi, -\psi\}$ is the only torsion-level source of encoding non-uniqueness on a fixed product surface, and that every auxiliary of the correct degree is commitment-compatible by Kani's theorem. The sole barrier to producing an alternative encoding is the construction of a new auxiliary isogeny of the required (generically non-smooth) degree from the challenge curve. We demonstrate that this barrier falls whenever a single small prime divides the auxiliary degree $2^f - q$: the adversary reroutes the terminal $\ell$-isogeny step at the codomain of the honest auxiliary, preserving the total degree exactly. Since generic odd integers possess small prime factors with overwhelming probability, this establishes that canonicalization of the basis change matrix does not suffice for strong unforgeability. We analyze the signing algorithm's dependency structure to show that the auxiliary cannot be bound into the Fiat-Shamir hash without a protocol redesign, and conclude with a structural comparison of ECDSA (where canonicalization suffices), SQIsign (where it does not), and salt-PRISM (which achieves strong unforgeability via a salted hash-to-prime mechanism that eliminates the auxiliary freedom entirely).

We show that the certificateless signature scheme [IEEE ITJ, 26852-26865, 2024] is insecure against public key replacement attack. An adversary can forge signatures for any message by replacing the signer's public key. We find the two components $\delta_A$ and $T_A$ of signature $\sigma_A=(m_A, ID_A, \delta_A, T_A)$ are not tightly bound to the target message $m_A$ and the singer's identity $ID_A$. The inherent flaw results in that the adversary can find an efficient signing algorithm functionally equivalent to the valid signing algorithm. The findings could be helpful for researchers unfamiliar with the designing techniques for certificateless signatures.

The main contribution of this paper is to introduce Subspace Differential Uniformity (SDU) for S-boxes and block ciphers. The SDU is essentially a measure of how well any function spreads input differences clustered in affine subspaces away from affine clusters in output differences. We provide some lower bounds for the SDU and describe an efficient algorithm for computing the SDU. Moreover, we provide results for some popular classes of S-boxes up to $n=8$.

Secure computation allows multiple parties to jointly evaluate a function without leaking their individual inputs. An intrinsic issue with these techniques is that they do not offer any protection against parties which may contribute bad quality or even maliciously crafted data. We introduce TRIP, a protocol which protects against malicious manipulations of the input in secure computation of linear regression tasks. Linear regression is the cornerstone in many machine learning tasks, and hence creating secure protocols for this task is a crucial step towards secure machine learning. Our protocol utilizes a novel combination of techniques from secure computation, robust statistics, and differential privacy. On synthetic data, TRIP recovers the planted ground truth; on real-world datasets, its model remains close to the clean OLS baseline under up to 40\% target corruption. In terms of efficiency, our protocol runs up to $250\times$ faster than an MPC-only baseline for $10^6$ samples. Even in the smallest parameter setting, TRIP is $10\times$ faster than our baseline.

Euclidean lattices are an interesting object of study in many regards and can have a rich structure arising from various constructions, e.g., from number field extensions. A particularly interesting class is the one of well-rounded lattices, as they relate to the well-known densest sphere packing problem in geometry, theta function minimization, and the famous Minkowski and Woods conjectures. In addition to being an important mathematical object in their own right, lattices also play a central role in many applications. This paper offers a survey of structured lattices and discusses their recent applications in lattice-based cryptography and secure wireless communications. Our goal is to spark the interest of mathematicians and adjacent communities in these fascinating topics in the intersection of lattices, number theory, cryptography, and wireless communications.

Threshold signatures allow a quorum of parties to jointly produce a signature while preventing any smaller subset from doing so. Following NIST's post-quantum standardization, designing threshold schemes compatible with the newly selected primitives is a pressing task. In particular, no prior threshold signature scheme produces signatures verifiable under the unmodified FALCON verification algorithm - the NIST-selected post-quantum scheme with the smallest signatures and keys. In this work, we present the first such threshold FALCON signing protocol, establishing its feasibility. Our technical contributions are threefold. First, we adapt the MPC-based discrete Gaussian sampling protocol of Wei et al. [CCS:WYFCW23] to support private centers and standard deviations, as required by FALCON's signing process. Second, we carry out a Rényi divergence analysis of the Klein sampler under fixed-point arithmetic, showing that $73$ bits of precision suffice to achieve the same security as the FALCON specification. Third, we design an efficient MPC protocol for the Klein sampler that exploits the fixed trapdoor basis to construct a pseudorandom correlation generator for authenticated VOLE using only two-party DPFs, reducing per-signature communication significantly over standard authenticated triple generation. We implement and benchmark our protocol in two settings: $N$-party signing with all-but-one corruption, and 3-party signing with honest majority, demonstrating that threshold FALCON signing is feasible for applications where compatibility with the FALCON standard is required.

Let $E$ be an elliptic curve over a perfect field $K$. A function $f\in K(E)$ is a compression of degree 2 on $E$ if $f(-P) = f(P)$ for all $P\in E$, and the field extension $K(f)\subset K(E)$ is of degree 2. For a finite subgroup $G\subset E$ over $K$ a function $w\in K(E)$ we will call a $G$-compression if $w(\pm P +G) = w(P)$ for all $P\in E$, and the field extension $K(w)\subset K(E)$ is of degree $2|G|$. We will show that $w\in K(E)$ is a $G$-compression if and only if $w = f\circ \Phi$ for a separable isogeny $\Phi:E\to E'$ over $K$ with $\ker \Phi=G$, an elliptic curve $E'/K$, and a compression $f\in K(E')$ of degree 2 on $E'$. This allows to obtain a doubling, a differential addition, and a method for point recovery for $G$-compressions using known properties of compressions of degree 2. For $G$-compressions $w$ studied in the literature on an extended Jacobi quartic, a twisted Edwards curve, a twisted Jacobi intersection, and a twisted Hessian curve (for the first and third model additional conditions on coefficients are assumed) we will give the decomposition $w = f\circ \Phi$ as above, and the function induced by the dual isogeny $\widehat{\Phi}$ and compressions of degree 2, which can be used for point recovery. For the first three models this isogeny $\Phi$ is to a Montgomery curve over $K$, and has the first coordinate $x(\Phi)=1/w$. We also give isomorphisms from some models of elliptic curves to a Montgomery curve.

HAWK is a signature scheme based on the module lattice isomorphism problem, and the only lattice-based candidate in the third round of NIST's call for additional post-quantum signatures. Its specification claims that HAWK achieves the BUFF (Beyond UnForgeability Features) security properties "as is", without applying the generic BUFF transform, citing the analysis of Aulbach, Düzlü, Meyer, Struck, and Weishäupl (PQCrypto'24). We refute this claim for HAWK exactly as specified. Several of the BUFF games let the adversary register a public key of its own choosing, yet the HAWK reference verifier performs almost no validity check on a key beyond decoding it. We exhibit degenerate "weak" public keys under which the all-zero signature verifies for all random-oracle challenges except the negligible symmetry-breaking corner case, and use them to break the three BUFF properties whose games let the adversary supply both the verification key and the signature: message-bound signatures, malicious strong universal exclusive ownership, and weak non-resignability. We trace these breaks to gaps in the BUFF proofs for HAWK of Aulbach et al.: one missing case analysis, and three steps that silently assume properties of the adversarially chosen keys as if they come from honest key generation. Honest key generation already enforces bounds that would reject our weak-key family on the attacks we exhibit. We prove that enforcing this norm floor at verification yields message-bound security for constant keys, but we make no claim that it fully restores BUFF security.

In this paper, we study garbled circuits in the random oracle model against a computationally unbounded adversary with $T$ queries to a (programmable) random oracle. From Yao's garbled circuits (SFCS 1986) to Three-Halves (CRYPTO 2021), the garbled circuit size has been reduced from $8|C|(\log T+\kappa)$ bits to $1.5|C|(\log T+\kappa)$ bits for achieving a statistical error of $2^{-\kappa}$, where $|C|$ is the circuit size and $\kappa$ is the statistical security parameter. However, no known result achieves $o(|C|\kappa)$ bits of garbled circuit size by now, and it is widely believed that a garbled circuit must have $\Omega(|C|\kappa)$ bits in the random oracle model. In this work, we present the first garbling scheme that achieves $o(|C|\kappa)$ bits of garbled circuit size in the random oracle model. In particular, for a circuit $C$ of size $|C|$ and depth $D$, the achieved garbled circuit size is $O(|C|\log T+D\kappa^2\log T)$ bits. This breaks the long-standing $\Omega(|C|\kappa)$ barrier on the garbled circuit size. We extend our garbling scheme to a maliciously secure two-party computation protocol with communication of $O(|C|\log T+D(\log T+\kappa)^2\log T+{\sf poly}(\kappa,\log T))$ bits against any $T$-query adversary assuming parallel oblivious transfers and a (programmable) random oracle. The protocol only requires 1 OT round and 3 one-way communication rounds. If only requiring one of the two parties to have output, a similar communication complexity can be achieved for constructing a non-interactive secure computation (NISC) protocol, which only relies on the preprocessing of bit-OT correlations and a random oracle. Compared to a concurrent work on NISC by Ishai et al. (EUROCRYPT 2026) in the same setting, we achieve a better amortized communication cost per gate at the cost of an additional term related to the circuit depth. The NISC protocol with a similar communication cost can also be constructed from a (slightly stronger version of) semi-malicious 2-round OT protocol.

In this work, we study the communication complexity of constant-round MPC with guaranteed output delivery (GOD) in Minicrypt. We construct the first MPC protocol in this setting with linear communication complexity of $O(|C|n\kappa+Dn^3\kappa^3+W_I{\sf poly}(n,\kappa))$ bits under the assumption of a random oracle, where $|C|$ is the circuit size, $D$ is the circuit depth, $W_I$ is the number of input wires, and $\kappa$ is the security parameter. In comparison, the previously best-known construction with linear communication ($O(|C|n)$), presented by Goyal et al. (CRYPTO 2020), requires $O(D+n^2)$ round complexity. When targeting $O(D)$ round complexity, the best-known result by Agarwal et al. (ASIACRYPT 2024) still requires $O(|C|n^3)$ communication complexity. More communication is needed to achieve constant round complexity, even with non-black-box use of the underlying cryptographic primitives.

We give a new algorithm to attack RSA with small private exponent, when some partial information of $p + q$ is given. The algorithm is a very simple modification of original Wiener’s attack with continued fractions, and allows us to factor $n$ whenever $d<n^{(1+\delta)/2}$ if we know a $δ$-fraction of the most significant bits of $n$. The algorithm is unconditional, which is not the case in previous improvements that use Coppersmith method. As a simple example, our algorithm can be applied to break any cryptosystem with modulus $n$ of $512$ bits and $d < n^{0.3}$, given an improvement in the original. attack of Wiener.

In this paper, we present a Differential Fault Attack (DFA) on the lightweight stream cipher Atom, proposed by Banik et al. in IACR Transactions on Symmetric Cryptography (TOSC)-2021. It employs two key filters simultaneously during the pseudo-random generation algorithm phase, one of which depends on LFSR state bits. Due to this LFSR-dependent key filter, the authors claim that forming algebraic equations relating key and state bits as variables to the keystream bits is difficult unless the entire LFSR state is known. In contrast, we propose a method to formulate such algebraic equations without guessing any LFSR bits. This enables us to implement a successful DFA on Atom. To the best of our knowledge, this is the first successful DFA reported on Atom . In the proposed DFA, we identify the location of injected faults using a weighted ensemble of trained MLP and XGBoost models. To further improve accuracy, we filter out ML predictions with confidence below a predefined threshold. We found that this strategy significantly reduces the number of SAT solver invocations and improves the overall time complexity of the attack. Based on our experiments, we demonstrate a successful DFA on Atom within a practical time by injecting 18 faults, provided all are correctly identified. Obtaining a set of 18 correctly identified faults requires, on average, 52 fault injections. The attack requires a total of 70 keystream bits (normal and faulty combined) just after a fault injection and guessing two random key bits.

Non-committing encryption (NCE) is a key primitive for proving security against adaptive corruptions, enabling simulators to generate ciphertexts before the encrypted message is known. Existing non-committing constructions for attribute-based encryption primitives [Hiroka et al., ASIACRYPT 2021; Goyal et al., PKC 2025] typically rely on centralized trust that generate users' secret keys. However, modern cryptographic systems increasingly aim to eliminate such trust assumptions through decentralized frameworks such as registered encryption, where users independently generate and register their own keys. In this work, we initiate the study of non-committing registered functional encryption (NC-RFE) as a generalization of non-committing attribute-based encryption in the decentralized framework. We formalize the notion of NC-RFE by adapting classical non-committing security to the registered setting. We then present a generic construction based on indistinguishability obfuscation and zero-knowledge arguments, and prove its security assuming a secure underlying registered functional encryption (RFE) scheme. We further provide a lattice-based instantiation, yielding a post-quantum secure NC-RFE scheme based on the hardness of the plain LWE and equivocal LWE assumptions.

Transformer models have recently emerged as a game-changing technology for applications in content generation. However, severe privacy concerns and the scalability bottlenecks of existing secure protocols limit their large-scale deployment. To address these challenges, we present CRAfT, an innovative system designed for high-scalability and low-latency secure Transformer inference. The core contributions of CRAfT are threefold: First, we propose a novel ciphertext packing strategy tailored for multiple mutually distrustful users. This approach completely eliminates the need for ciphertext rotations in linear projections layer and effectively offloads massive communication traffic to the high-speed P2P network. Second, we introduce a novel branch-free iterative fitting strategy based on trigonometric functions, which accurately approximates sigmoid-like functions (e.g., Tanh, Sigmoid, and erf in GELU). In the interval $[-3, 3]$, its approximation accuracy exceeds that of the plaintext Tanh-based GELU, while requiring only 4 communication rounds without relying on polynomial approximations. Finally, for complex operations like Softmax that exhibit partial sigmoid-like characteristics, we transform them into standard sigmoid-like functions, allowing us to directly apply our fitting strategy to minimize cryptographic costs while maintaining model accuracy. Comprehensive evaluations on BERT-base demonstrate that CRAfT increases multi-client inference throughput by up to $8.5\times$ and reduces per-client WAN communication volume by 38.4% compared to the highly optimized baseline (BumbleBee).

The Rank Decoding (RD) problem lies at the core of rank-based cryptography. To enable efficient constructions, several variants have been introduced, notably the Non-Homogeneous RD (NHRD) problem and the Blockwise RD (BRD) problem. The \emph{quantum} security of these systems is currently considered to be determined by the complexity of combinatorial attacks such as AGHT, PRR, and Ourivski--Johansson (OJ) attacks. However, for the OJ attack, the modeling, soundness, and relative complexities remain poorly understood, particularly for the NHRD and BRD variants, thereby limiting confidence in security claims and hindering the design of compact schemes. In this work, we refine the modelings for the OJ attack (PIT, 2002) and the Improved OJ (IOJ, IEEE TIT 2025) attack, and obtain general and tight complexities on the RD, NHRD, and BRD problems. We show that the IOJ attack rests on optimistic assumptions that do not hold in practical random decoding scenarios, and thus its advantage over OJ should be disregarded in security assessments. For the RD problem, the OJ attack remains a strong candidate for the most powerful combinatorial attack in certain parameter regions, particularly when the code dimension $k$ is small and the extension degree $m$ is large. For the NHRD problem, we show that the OJ attack is the most powerful combinatorial attack for the parameters of NH-Multi-UR-AG, yielding up to a 100-bit improvement over the adapted AGHT attack (IEEE TIT 2024), while still preserving the claimed security level. For the BRD problem, we derive complexity formulas for general block structures, resolving questions posed in prior works (Asiacrypt 2023, IEEE TIT 2025, PQC 2024). Our analysis also reveals that the OJ attack is previously underestimated by about $\gamma^2$ bits, where $\gamma$ denotes the minimum block weight. We further show that the OJ attack outperforms AGHT and PRR attacks in certain parameter regions, achieving up to a 136-bit advantage over PRR (IEEE TIT 2025). Our work advances the understanding of decoding problems in the rank metrics and reinforces the security of related cryptosystems.

Constructing a post-quantum signature scheme that is simultaneously compact and efficient remains a central challenge in code-based cryptography. Existing schemes based on turning a zero-knowledge identification scheme into a signature exhibit either large signatures or slow verification procedures. On the other hand, the design of hash-and-sign code-based schemes initiated by Courtois, Finiasz and Sendrier in $2001$ has led to schemes such as Wave and MIRANDA, that provide small signatures at the cost of massive public key sizes, with comparatively demanding signature algorithms. In this work, we present ASTRA-Sign: a quASi-cyclic code-based full-distance decoding TRApdoor Signature Scheme, combining the hash-and-sign paradigm with quasi-cyclic moderate density generator matrix codes to obtain small signatures and small public keys. The security of our scheme is based on the hardness of finding low weight codewords in quasi-cyclic codes, and on the hardness of finding a codeword that has full Hamming distance from a given random vector. We analyse key recovery and signature forgery attacks against ASTRA, and we propose several parameter sets achieving $128$-, $192$- and $256$-bit security. Our scheme exhibits public keys and signatures below $1$kB for $128$ bits of security, with sub $50\mu$s verification times.

The development of proof systems whose security relies on the hardness of lattice problems has been a fruitful research area in recent years. By leveraging the techniques introduced in LaBRADOR (Beullens, Seiler, Crypto 2023), the state-of-the-art lattice-based schemes have very fast provers and have output sizes under 100KB for arbitrarily large statements. These proofs are in fact the smallest, and often have the fastest provers, out of all post-quantum schemes. In addition to succinctness, many applications also require witness privacy. Achieving this can, in theory, be done by combining LaBRADOR with a linear-size zero-knowledge proof. While such a combination has already been described in the LaBRADOR paper itself, as well as in the works of Albrecht et al. (Eurocrypt 2024) and del Pino et al. (Crypto 2025), its concrete costs remained unexplored. In this work, we provide the first concrete construction and implementation that adds zero-knowledge proofs to LaBRADOR by integrating the linear-size zero-knowledge proof from (Lyubashevsky, Nguyen, Plançon, Crypto 2022) into the protocol. We describe the non-trivial challenges that this entails and show practicality of the construction by benchmarking several use-cases. We make the proof system and primitives accessible by extending the LaZer library (Lyubashevsky, Seiler, Steuer, CCS 2024) in a way that they can easily be used in other applications.

Confidential transaction (CT) protocols are widely used to protect the privacy of blockchain-based cryptocurrency transactions. However, existing CT schemes primarily focus on ordinary users' anonymity and amount confidentiality, while overlooking miner privacy as a native objective. In particular, the privacy of miners' coinbase-receiving addresses has not been systematically considered in security models. In this paper, we identify two novel attacks against miner privacy in existing CT protocols, called miner privacy attacks and anonymity reduction attacks. These attacks arise from the transparency of the mining coinbase amounts and transaction fees in the underlying blockchain systems. When miners' accounts are included in a CT, our general solutions compatible with all schemes can prevent adversaries from identifying miners as the real spenders or excluding miners from the possible spender sets. We propose SuccinCT, the first CT protocol based on the DualRing structure to address the aforementioned attacks. Compared with existing schemes, SuccinCT achieves the smallest overall transaction size while protecting miner privacy. Specifically, the proof size of SuccinCT is about 20% smaller than the latest BulletCT (USENIX SEC'25). We implement SuccinCT and evaluate its performance for ring sizes from 128 to 1024. The results show that signature generation takes about 2-3 ms and verification takes about 1-2 ms. These results demonstrate that SuccinCT provides stronger privacy guarantees, novel construction, and practical efficiency for real-world deployment.

We show that every language in PSPACE decidable by a Turing machine in time $T(n)=n^{O(\log n)}$ admits a doubly efficient interactive proof system: the prover runs in time polynomial in T(n), and the verifier runs in time polynomial in n. This extends the best previously known regime for such proof systems from $T(n)=n^{O(\sqrt{\log n / \log\log n})}$, established by Berger, Goyal, Hong, and Kalai (FOCS 2025), to $T(n)=n^{O(\log n)}$. Beyond improving the range of T, our protocol is substantially simpler than previous doubly efficient proofs for time-bounded PSPACE. Earlier constructions proceed indirectly: they first build batch interactive proofs and then invoke them as a black box to obtain doubly efficient protocols. In contrast, we give a direct construction. This not only simplifies the proof but also points to a more promising route for future improvements.

A key-independent secret-key distinguisher identifies inherent structural deviations of a block cipher from an ideal random permutation without recovering any information about the secret key. For the Advanced Encryption Standard (AES), various key-independent secret-key distinguishers have been proposed on reduced-round versions. In this paper, we study related-differential distinguishers for 5-round AES that combine a 1-round related differential trail with the 4-round generalized zero-difference property. We prove that the number of valid quartets satisfying the underlying property takes the multiple-of form, N_q = 2^{2-n_z}(2^w)^{n_z} A + 8B, where A, B are non-negative integers, w is the cell size, and n_z is the number of inactive bytes of Delta X_2 (the difference at the second-round input) under the chosen pairing of the 4-plaintext quartet into two pairs. The pairing fixes the bundle size 2^{2-n_z}(2^w)^{n_z}, which sets the variance of the valid-quartet count. We compare the three pairings n_z in {0, 1, 2}. In the chosen-plaintext setting, where a single structure is examined as a whole, a smaller bundle keeps the count closer to its mean, so n_z=0 is the most reliable single-structure distinguisher, n_z=1 is close behind, and n_z=2 almost fails. The pairing n_z=1 is that of Yan et al. Its 2*2^w bundle raises the variance, so it reaches 63% only at 2^{27.2}, rather than at the 2^{27} where one valid quartet is expected. At the same 2^{27.2}, the smaller bundle of n_z=0 reaches 65%. In the adaptively chosen-plaintext setting the bundle does not form across the separate base collisions, so n_z=1, which produces more valid quartets, is the better pairing. All claims are verified experimentally on both small-AES (w=4) and the standard AES (w=8).

The study of oblivious algorithms is concerned with designing privacy-preserving algorithms whose memory access patterns reveal nothing about the secret inputs. Such algorithms have been deployed at scale in production systems, most notably in Signal's private contact discovery service. So far, all practical implementations of oblivious algorithms (e.g., those by Signal and Meta) rely on trusted hardware and operate within the external-memory model of computation. While it is known how to generically compile an arbitrary program to execute obliviously on an external-memory target machine, such generic oblivious simulations trade asymptotical efficiency for generality and therefore are rarely used in practice. Instead, customized oblivious algorithms tailored for the computational tasks of interest are almost always favored. In this paper, we explore the single-source shortest path (SSSP) problem, a fundamental algorithmic building block with broad applications in scheduling, routing, graph mining, resource allocation and flow optimization. We present an external-memory oblivious SSSP algorithm for undirected graphs that achieves I/O efficiency $O(V + \frac{E}{B}\log\frac{E}{M})$ and total work $O(E\log E)$ assuming $E = \Omega(V)$, where $V$ denotes the number of vertices, $E$ denotes the number of edges, and $M$ and $B$ represent the target machine's cache size and block size, respectively. Our algorithm almost matches the best known non-private external-memory algorithm for SSSP, up to a $\log \log E$ factor in the second term of the I/O bound. The remaining $\log \log E$ gap is conjectured to be an inherent barrier, since making the underlying priority queue oblivious requires an $\Omega(\log \log n)$ blowup in I/O cost, which is known to be inherent. As a by-product, we develop an improved external-memory oblivious priority queue that supports DecrKey operations. Specifically, while the construction of Jafargholi et al. attains optimal I/O efficiency, it is suboptimal in total work under a strong notion of obliviousness—where the adversary can observe both block-level and word-level accesses. This stronger security guarantee is the current industry norm and explicitly required by companies such as Signal. We present a new oblivious priority queue that achieves optimality in both dimensions. Specifically, we achieve an I/O cost of $O(\frac{1}{B}\log\frac{n}{M})$ and total work $O(\log n)$ per query where $n$ is the capacity of the priority queue.

Digital communication increasingly underpins identity, financial transactions, and regulatory compliance. In many settings, possession of a DKIM-signed email serves as evidence of account control, transaction confirmation, or institutional affiliation. Yet demonstrating such properties typically requires revealing the full email or relying on centralized intermediaries, introducing privacy risks and additional trust assumptions. A framework called ZK Email addresses this limitation by applying zero-knowledge proofs (ZKPs) to email verification, enabling publicly verifiable proofs of authenticity while preserving message confidentiality. However, its existing implementations struggle to support complex, real-world messages due to the inefficiency of regular-expression verification over structured formats and rich alphabets. We address this limitation with a new ZKP system for regex matching based on path verification over $\varepsilon$-free NFAs, yielding prover complexity linear in the captured path and independent of the original email's size. This approach enables practical validation of expressive standard structures required for full DKIM-signed email verification. To fully integrate our constructions into ZK Email, we design complete end-to-end ZK circuits that combine (i) DKIM signature verification, (ii) an arbitrary-length SHA-256 circuit with partial precomputation for $\texttt{rsa-sha256}$ under RFC 6376, and (iii) a general-purpose regex primitive enforcing structural constraints over email headers and body. We formalize the associated zero-knowledge relations and analyze their security under realistic adversary models. We implement the system (fully integrated with ZK Email and released under the MIT license) in $\texttt{Circom}$ and $\texttt{Noir}$, targeting $\texttt{Groth16}$ and $\texttt{UltraHonk}$ backends, and evaluate it in both client-side and zkVM (SP1) deployment settings. Experimental results on commodity hardware demonstrate substantial efficiency improvements over prior DFA-based approaches, achieving a $2$-$6\times$ speedup in proving time using the $\texttt{UltraHonk}$ backend, while supporting a significantly richer class of regex languages.

Append-only accumulators are a natural way to realize compact public-state registries, but under high-frequency updates, witness maintenance becomes a severe challenge because each insertion typically invalidates most existing witnesses. This challenge is particularly acute for intermittently online users in anonymous credential systems, who cannot continuously synchronize update information, while directly outsourcing witness updates may make repeated requests linkable. In this paper, we present a privacy-preserving outsourced witness-update protocol for append-only RSA accumulators. The protocol combines witness updates with Linear Integer Secret Sharing (LISS), enabling on-demand, client-stateless witness updates while preserving witness privacy and unlinkability against coalitions of update servers below the threshold, and providing accountability for malicious or malformed server responses. We formalize the system and threat models and analyze the security of the protocol. We further develop server-side optimizations for long catch-up windows and implement the full end-to-end protocol in Rust. Evaluation under multiple threshold settings and offline windows shows that the protocol supports practical one-shot witness updates after long offline periods, with client-side cost remaining independent of the number of missed updates and server-side cost being mainly determined by the catch-up span and the LISS distribution matrix.

Static Quantum Bit Error Rate (QBER) thresholding is the standard defense mechanism in deployed Quantum Key Distribution (QKD) systems. In noisy free-space optical (FSO) channels, however, natural atmospheric variations can camouflage short, low-intensity eavesdropping bursts, rendering fixed thresholds ineffective. This paper investigates physics-aware temporal feature engineering for machine learning-based anomaly detection in entanglement-based BBM92 QKD telemetry. A 24-dimensional feature space is computed over a 30-second sliding window, characterizing the temporal evolution and cross-observable correlations of QBER, the Bell S parameter, and photon coincidence rates. Evaluated on a simulated FSO telemetry dataset spanning 24 hours across five random seeds, static QBER thresholding achieves only 17.3% recall against blended sub-threshold attacks, while an XGBoost classifier trained on the proposed feature set achieves 96.9% recall and 97.6% precision within the same simulation framework. SHAP analysis suggests that detection is driven less by absolute error magnitude than by anomalous temporal decoupling between independent quantum observables. These results indicate that physics-aware temporal representations may improve resilience to stealthy attack strategies in simulated BBM92 environments, although validation on operational hardware and real telemetry remains an important direction for future work.

The increasing usage of Zero-knowledge proof protocols has raised the need for cryptographic primitives that are efficient in that setting, called Arithmetization-oriented primitives. The security of such permutations is commonly evaluated with the CICO-$k$ problem. The best known CICO-$1$ attack against ZK-Friendly permutations over $\mathbb{F}_q^t$ based on $\alpha$-inversions $x\mapsto x^{1/\alpha}$ exploits resultants (ASIACRYPT 2024, CRYPTO 2025). It starts from one input variable $x$ and introduces a temporary variable after each $\alpha$-inversion. With an efficient procedure to eliminate temporary variables, the attack reaches a time and memory complexity of $\tilde{\mathcal{O}}(D_I (2-1/\alpha)^n)$, where $D_I$ is the ideal degree of the CICO-$1$ modeling and $n$ is the number of $\alpha$-inversions. In this work, we study such an approach using two input variables $x_1 , x_2$, and we generalize the temporary variable elimination to that setting. Subsequently, we present a new CICO-$2$ attack framework and a new Start-From-The-Middle (SFTM) CICO-$1$ attack framework. Both our attacks rely on fast bivariate resultants for their final bivariate system solving step. Using resultant algorithms with complexity almost linear in $D_I$, our CICO-$2$ and CICO-$1$ attacks reach a complexity almost linear in $\alpha^n D_I$ and in $D_I$, respectively, which is a first theoretical improvement. Designing an efficient implementation of these resultant algorithms remains a challenge, so for our practical contributions we turn to Villard's algorithm (ISSAC 2018). After adapting it to our context, we obtain practical complexities $\tilde{\mathcal{O}}((\alpha^n D_I)^{\gamma_2})$ and $\tilde{\mathcal{O}}(D_I^{\gamma_1})$ for CICO-$2$ and CICO-$1$ respectively, where $1.2 \le \gamma_1 \le 1.25 \le \gamma_2 \le 1.33$ depending on the chosen linear algebra exponent $2 \le \omega \le 3$. Our attacks improve upon the best known ones against several instances of Anemoi, Rescue and Griffin, successfully breaking $128$-bit and $256$-bit security instances of Rescue in the CICO-$1$ setting and full-round instances of Anemoi and Griffin in the CICO-$2$ setting for the first time. Our implementation of the attack confirms the practicality of the approach.

Updatable vector commitments are judged by how a k-position update affects the broadcast update information S and the per-proof update time T. We promote the public-parameter size P to a first-class metric, systematize known schemes in the resulting three-dimensional (S,T,P) space, and prove that every linear group-model vector commitment with position-binding requires P at least N, while the lattice homomorphic Merkle tree is simultaneously sublinear-update and pp-succinct. This turns the empirical group/lattice gap into a theorem, and we show the new axis is orthogonal to known lower bounds.

Fully homomorphic encryption (FHE) enables privacy-preserving neural network inference but suffers from high overhead from homomorphic convolutions, polynomial activation approximations, and CKKS bootstrapping. This paper presents BootNet, a unified framework that fuses all three operations into a single bootstrapping invocation per CNN layer, achieving convolution, ReLU, and noise refresh simultaneously. Prior works are able to fuse convolution into bootstrapping using CinS encoding (NeuJeans, CCS 2024) or ReLU into functional bootstrapping (RBOOT, USENIX Security 2026), but combining both for end-to-end ImageNet inference introduces numerous undocumented challenges. BootNet resolves these through a suite of co‑design techniques and optimizations, including four representative solutions: (1) a split‑and‑merge bootstrapping schedule that halves bootstrapping calls for ResNet shortcuts; (2) an improved RBOOT configuration paired with a model quantization method that complete the activation function with fewer multiplication depth; (3) a fusion of NeuJeans' masking layer with RBOOT's arcsin step that yields additional depth reduction; (4) tailoring EvalRound+ (IEEE Access 2025) to fit slim bootstrapping and RBOOT for further depth reduction. We evaluate BootNet on multiple ResNet models on the ImageNet dataset. Compared to the state-of-the-art Orion (ASPLOS 2025), BootNet reduces end-to-end latency by 67-73% and storage by 76-90% while preserving plaintext accuracy. We also introduce BootNet-mini, enabling full ImageNet inference at ring degree $N=2^{15}$ (with over $120$-bit security via sparse-secret encapsulation) for the first time, while all previous works have to use $N=2^{16}$ or larger. BootNet-mini performs similarly in latency but reduces 30-55% storage requirement than BootNet, making it potentially more friendly for hardware acceleration.

We study transparent public generation of hard supersingular curves: a public, seeded, rerunnable algorithm outputs a supersingular curve while exposing the seed, verification transcript, and all algebraic information reconstructible from the implementation. This setting is distinct from trusted or distributed ceremonies, where a witness may be hidden, erased, or zero-knowledge protected. We define a transcript-security model for this setting and develop barriers for several modeled algebraic generation routes. For modular-conjugacy samplers, we analyze loci of supersingular invariants admitting an isogeny to their Frobenius conjugate; small public parameters give efficiently recognizable sparse support, while extractable high-parameter witnesses yield non-scalar endomorphisms by Frobenius composition. We extend this leakage principle to bounded correspondence witnesses, including kernel, rational-map, Hecke--Brandt, and elliptic-return detour traces. For direct samplers, we separate predicate-only search, local-neighbor exploration, bounded-relation witnesses, low-formal-degree ambient algebraic maps, and degree-one indexed maps from \(\F_p\) to \(\F_{p^2}\). The resulting theorems are deliberately model-bounded: they do not rule out hidden-witness ceremonies, higher-degree indexed maps, compact high-degree root indexing, endpoint-only mechanisms, or nonlocal aggregate sampling. Full proofs are deferred to the appendices.

What is the round complexity of MPC over point-to-point channels that is secure with unanimous/identifiable abort in the dishonest-majority setting? Even after four decades of research, the answer to this question remains unclear. Although two-round MPC protocols exist in the broadcast-channel model, and, further, broadcast protocols with expected-constant rounds exist facing any constant fraction of corruptions, a naïve combination of the two yields MPC with expected $O(\log{n})$ rounds, where $n$ is the number of parties. The reason for this gap is the need to preserve the expected round complexity under parallel composition, yet existing techniques for the composition of broadcast protocols inherently rely on an honest majority of parties. Further, when considering MPC with abort, one can also consider \emph{broadcast with abort}. However, existing lower bounds on the round complexity of broadcast do not translate to this relaxed notion of broadcast, with the end result that the existing lower bounds for MPC and broadcast do not apply to the question above. In this work, we initiate the systematic study of this question and present the following positive and negative results for MPC over point-to-point channels: - First, we prove the impossibility of (strict) constant-round MPC with unanimous abort. In fact, we show that any broadcast protocol with unanimous abort that is secure against super-constant corruptions requires super-constant rounds. - Second, we present a round-preserving and black-box parallel composition construction of broadcast with unanimous abort, which leads to our main result: Assuming oblivious transfer (OT) and verifiable random functions (VRFs), MPC with unanimous abort and expected constant rounds is possible in the PKI model for signatures and VRFs, in the presence of any constant fraction of corruptions. - Finally, we show that in the presence of slightly more corruptions---i.e., $n-o(n)$ corruptions---there is no expected-constant-round broadcast (and thus MPC) with identifiable abort.

Modern, deployed key transparency systems rely on auditors to ensure that updates to the set of keys are well-structured, allowing clients to efficiently monitor their own keys. In practice, the server's consistency proofs are very large, requiring computationally powerful auditors; as a result, real-world deployments have very few auditors. We propose a new key transparency system based on a new data structure called Forget-me-not trees, which is a careful composition of Merkle trees and Bloom filters. The resulting system reduces the size of audit proofs by $\approx500\times$, from 15MB-30MB down to only 30KB-60KB. Our construction is the first mass-scale auditable key transparency system that relies only on hash functions.

The Duplex construction, introduced by Bertoni et al. (SAC 2011), is the Swiss Army knife of permutation-based cryptography. It can be used to realise a variety of cryptographic objects—ranging from hash functions and MACs, to authenticated encryption and symmetric ratchets. Testament to this is the STROBE protocol framework which is a software cryptographic library based solely on the Duplex combined with a rich set of function calls. While prior works have typically focused their attention on specific uses of the Duplex, our focus here is its indifferentiability. More specifically, we consider the indifferentiability of the Duplex construction from an online random oracle—an idealisation which shares its same interface. As one of our main results we establish the indifferentiability of the Duplex from an online random oracle. However indifferentiability only holds for the standard Duplex construction and we show that the full-state variant of the Duplex cannot meet this notion. Our indifferentiability theorem provides the theoretical justification for the security of the Duplex in a variety of scenarios, amongst others, its use as a general-purpose cryptographic primitive in the STROBE framework. Next we move our attention to AEAD schemes based on the Duplex, namely SpongeWrap, which is the basis for NIST's Lightweight Cryptography standard Ascon. We harness the power of indifferentiability by establishing that SpongeWrap offers security against key-dependent message inputs, related-key attacks, and is also committing.

As the transition to post-quantum cryptography accelerates, security protocols must evolve to resist quantum threats while remaining practical, particularly on constrained devices where memory, bandwidth, and performance are limited. We consider the NIST Personal Identity Verification (PIV) system, where smart cards rely on digital signatures for authentication. Since post-quantum signatures introduce substantial computational and memory overhead, whereas post-quantum Key Encapsulation Mechanisms (KEMs) are generally lighter, we investigate KEM-based alternatives for authentication and assess the migration of secure messaging to post-quantum primitives. We propose post-quantum variants of the PIV authentication and secure messaging protocols and implement both signature-based and KEM-based approaches on a real smart card platform. We evaluate their computational and communication costs in a realistic embedded setting and present detailed performance metrics that enable assessing the impact of post-quantum migration across different hardware and communication configurations. Our results show that KEM-based authentication significantly reduces execution time and transmitted data compared to post-quantum signature-based designs, while KEM-based post-quantum secure messaging incurs moderate overhead compared to its classical counterpart. These findings highlight KEM-based authentication as a practical migration strategy for post-quantum secure embedded systems.

Client-specific preprocessing PIR supports sublinear online private queries after a linear-time offline phase that prepares client-specific hints. The relevant lower bound is tight: any scheme with $S$ bits of client storage and online cost $T$ must satisfy $S \cdot T = \Omega(n)$. Most practical random-set schemes fall short by a $\kappa$ factor in client storage, while the known constant-factor-optimal schemes, WR-PIR (Eurocrypt 2025) and Balanced PIR (S&P 2026), rely on complex hint-management machinery and incur high concrete costs. We present Multi-level PIR, a preprocessing PIR scheme that matches this tight space-time tradeoff using only simple random-set components. The main idea is a multi-level composition: early levels are allowed to fail with noticeable probability, and later levels are invoked only when these query-independent failures occur. This 'waterfall' structure drives the overall failure probability down to negligible while keeping expected online cost and client storage at $O(\sqrt{n})$. Our implementation shows that this simpler structure gives competitive concrete performance. Compared with Piano and S3PIR, two prior state-of-the-art practical schemes, Multi-level PIR achieves a $9$-$20\times$ client space reduction; compared with Balanced PIR, it reduces preprocessing time by about $8$-$45\times$ and online communication by about $5$-$67\times$ in our evaluated settings, while remaining competitive in other online metrics. As an additional theoretical result, we give a more involved variant with $O(n^{1/4})$ online communication, the first constant-factor-optimal preprocessing PIR scheme with sub-$\sqrt{n}$ online communication.

We improve the performance of the lattice-based cryptosystem Dilithium on AVX2 and NEON by deeply exploiting its algorithmic properties, such as small coefficient bounds and high sparsity, with the distinct instruction-level profiles of the underlying architectures. On AVX2, we deploy a single-modulus 16-bit NTT for $c \cdot \mathbf{s}_i$ and a multi-moduli 16-bit NTT coupled with a vectorized CRT reconstruction for $c \cdot \mathbf{t}_0$. These instruction-level optimizations accelerate the respective computations by $2.4$--$2.5\times$ and $1.2$--$1.3\times$ over official AVX2 baselines, ultimately reducing the overall Dilithium signature generation time by $7\%$ to $8\%$. Conversely, On ARMv8-A NEON, we retain the efficient 16-bit NTT for $c \cdot \mathbf{s}_i$, while proposing a Fast Sparse Polynomial Multiplication (Fast-SPM) method for $c \cdot \mathbf{t}_0$. By exploiting the extreme sparsity of the challenge polynomial, Fast-SPM entirely bypasses the NTT and converts the computation into highly efficient index-shifted additions. Across the tested NEON platforms (Cortex-A72 and Apple M1 Pro), this hybrid approach achieves a $1.9$--$2.1\times$ speedup for $c \cdot \mathbf{s}_i$ alongside a $1.1$--$1.9\times$ acceleration for $c \cdot \mathbf{t}_0$, which translates into a $10\%$ to $13\%$ reduction in the overall signature generation time.

Cryptographic compression functions are a core component of vector commitment schemes, including Merkle tree commitments, which are widely used in modern ZK-SNARK and STARK frameworks. Arithmetization-Oriented (AO) compression functions minimize multiplicative complexity over the framework's native field F_p, making them significantly more efficient than bit-oriented designs in algebraic circuits. To date, AO compression functions have been almost exclusively constructed by applying the Sponge mode to an AO permutation. In this work, we introduce two novel approaches for building permutation-based AO compression modes: the PA family, based on a Permutation with feedforward Addition, and PAX, as an eXtension of the PA family. We formally establish that, in contrast to the Sponge construction, our modes achieve optimal collision and preimage resistance. We also prove that PAX is indifferentiable from a random oracle, further strengthening its security and composability guarantees. We further show that variable-input-length hash functions can be safely instantiated from the PA(X) modes by applying appropriate domain extenders. Beyond their strong security guarantees, our modes provide a framework that unifies and extends the description of several recently proposed modes that have been studied via cryptanalysis but do not come with provable security guarantees, including Jive and Trunc, as used in the AO designs Anemoi and Poseidon2. Finally, through extensive experimental evaluation, we compare the concrete efficiency improvement that our modes offer compared to the Sponge approach over two popular AO permutation designs, Poseidon permutation and Rescue. For 128 bits of collision resistance, our modes can achieve up to a 2x speed-up over Sponge for equivalent compression rates in a software implementation. When considering R1CS arithmetization in the Groth16 framework, the PA(X) preimage-verification circuit can be 10% faster than Sponge. In the Plonky2 framework, PA(X) can achieve up to a 60% speed-up

Secure multiparty computation (MPC) allows $n$ parties to compute a function of their private inputs, so that nothing beyond the output of the function is revealed. In the sub-optimal honest majority setting in which the number of corrupted parties $t<(1/2-\varepsilon)n$, the works of Goyal et al. (CRYPTO'21 and CRYPTO'22), achieved $O(|C|)$ communication even against active adversaries, but with $\Omega(n\cdot|C|)$ computation, where $C$ is the arithmetic circuit computed by the MPC. Recent work by Garg et al. (CRYPTO'24) showed that both $O(|C|)$ communication and computation can be achieved in this regime, however, only against passive adversaries. In this work, we achieve the best-of-both-worlds by obtaining MPC with $O(|C|)$ communication and computation against active corruption of $t<(1/2-\varepsilon)n$ parties. To do this, we introduce novel techniques for actively-secure MPC constructed from Chinese Remainder Theorem based secret sharing.

Consensus protocols form the core of blockchains and other replicated state machines, ensuring that all correct nodes process the same totally ordered log of input transactions. In fault-free executions, performance is driven by the good-case transaction latency -- the time between a transaction becoming known to all nodes and its confirmation by the consensus protocol -- which depends on both how frequently proposals are made and, once made, how quickly they are confirmed. While prior work has established tight lower bounds on confirmation latency that modern protocols already achieve, it remains open whether the inter-proposal time can be further reduced below the state-of-the-art of one network delay. We introduce Gatling, an atomic broadcast protocol that achieves arbitrarily small inter-proposal times under rotating leader schedules; in particular, smaller than the network delay. Gatling runs multiple parallel instances of a black-box atomic broadcast protocol and staggers their proposal schedules to generate proposals in faster succession than state-of-the-art protocols. A deterministic interleaving rule merges the outputs of these instances into a single global log. We analyze the effects of head-of-line blocking caused by crashed leaders, and derive Gatling's optimal number of parallel instances. We further study the impact of Gatling on predictable validity and present two variants that retain this property. Finally, our experiments confirm that Gatling can be used with off-the-shelf component protocols to achieve low latency without fine-tuning the component protocol for minimum latency.

We initiate the study of multi-authority traitor tracing (MA-TT), a decentralized variant of traitor tracing in which tracing capabilities are distributed across multiple independent authorities rather than concentrated in a single trusted entity. Ciphertexts are associated with tracing policies over a collection of authorities, specifying which subsets of authorities are authorized to jointly accuse a user of contributing to a pirate decoder. This enables fine-grained control over tracing capabilities, prevents unilateral accusations, and reduces the surveillance risks inherent in centralized tracing systems. Our scheme naturally supports conjunction, disjunction, threshold, and more general monotone tracing policies. We further introduce multi-authority attribute-based traitor tracing (MA-AB-TT), which combines distributed tracing in MA-TT with decentralized access control from multi-authority attribute-based encryption (MA-ABE). Ciphertexts are therefore equipped with two orthogonal policies: an attribute policy governing decryption and a tracing policy governing which tracing authorities may jointly identify traitors. Our main contribution is a construction of MA-AB-TT for arbitrary monotone access structures from the standard matrix decisional Diffie-Hellman (MDDH) assumption in prime-order pairing groups. Our construction achieves adaptive security under static corruption of authorities in the random oracle model. All system parameters are independent of the number of authorities and users in the system, while ciphertexts grow linearly with the size of the associated policies. Our framework also yields a publicly traceable variant, in which tracing can be performed using only the authorities' public keys, albeit with weaker asymptotic efficiency guarantees. Technically, we extend the blueprint for pairing-based traitor tracing based on private linear broadcast encryption (PLBE) [Boneh et al., Eurocrypt 2006] to the multi-authority setting. The key technical ingredient is a new multi-authority PLBE construction, which we instantiate from slotted inner-product function encryption (sIPFE) [Lin and Luo, Eurocrypt 2020]. As an intermediate step, we provide a new attribute-based sIPFE scheme supporting arithmetic branching programs, which may be of independent interest. Our techniques also yield a new modular construction of adaptively secure MA-ABE under static corruptions from sIPFE, improving on a prior construction by Ambrona and Gay [PKC 2023]. Finally, when specialized to a single authority, our framework gives the first ciphertext-policy attribute-based traitor tracing scheme with asymptotically optimal parameters and exponentially large user spaces.

Existing encrypted search and private set intersection (PSI) protocols struggle to reconcile post-quantum security with practical efficiency, often leaking search and access patterns or requiring prohibitively deep fully homomorphic encryption (FHE) circuits. We address these limitations by introducing a new Homomorphic Bloom Filters (HBF) framework, a quantum-resilient framework that embeds length-$m$ Bloom filters directly into the plaintext space of an RLWE-based FHE scheme, enabling shallow homomorphic evaluation and matching without structural leakage. Building on HBF, we construct a searchable encryption (SE) scheme and a private set intersection (PSI) protocol, both based on a depth-1 homomorphic missing-bit circuit. The SE scheme requires no rotations or bootstrapping at server side and incurs no additional computational cost as the number of query keywords increases. The PSI protocol reduces each packed Bloom-filter comparison to a single ciphertext--plaintext multiplication, with cost depending on the Bloom-filter length rather than direct element-wise comparisons with the responder's set. This framework confines leakage to benign dataset dimensions, tunable false-positive rates, and other public metadata, thereby eliminating explicit pattern leakage.

This paper presents the first practical end-to-end fault injection attacks on the post-quantum signature scheme PERK, based on the MPC-in-the-Head paradigm and relies on GGM tree expansions for efficient randomness generation. While GGM trees reduce memory requirements, they introduce implementation-level deviations from the theoretical model. We show that these implementation choices fundamentally alter the fault surface and enable new attack vectors that are not captured by the original security assumptions. We propose two attacks targeting distinct stages of the GGM tree construction. The first attack fixes the root seed, resulting in deterministic tree generation and enabling full reconstruction of all leaf labels. The second attack induces reuse of GGM roots via an instruction skip, allowing recovery of hidden leaf values across consecutive rounds. Both attacks require only a single fault to recover the secret key. We demonstrate both attacks end-to-end on the pqm4 reference implementation compiled with optimization levels -O3 as well as -Os for ARM Cortex-M4 microcontrollers. Our evaluation is performed on two hardware platforms (ChipWhisperer-Lite with STM32F303 and Nucleo-L4R5ZI-P) using clock glitching and electromagnetic fault injection (EMFI). We achieve success probabilities of 100% and 85% for the two attacks, respectively. Finally, we propose countermeasures for both attacks.

Due to the complexity of modern cryptographic algorithms, especially in the area of Post-Quantum Cryptography (PQC), conceptualizing optimal hardware designs in relation to some target performance metric is increasingly time-consuming and error-prone, particularly when combined with the need for secure side-channel protection mechanisms. To solve this, Buschkowski et al. presented the HADES framework at CHES 2025 that efficiently automates the pre-synthesis Design Space Exploration (DSE) process and combines it with automated arbitrary-order masking capabilities. However, as their work focuses only on Boolean masking, PQC schemes that rely heavily on finite field arithmetic incur a significant overhead in latency and area, as demonstrated in their MLKEM (Kyber) case study. In order to improve the performance of such primitives in hardware, we present a framework built upon HADES that supports both Boolean and arithmetic masking domains and can seamlessly and automatically convert between both types of secret sharing within the design hierarchy, while retaining the efficient DSE capabilities, extended by additional performance metrics. Even though the theoretical foundations of arithmetic masking are well-studied, some highly relevant implementation aspects, like the generation of non-power-of-2 masking randomness, are left largely unexplored. To help close this gap, we extensively analyze and systematically explore the cost associated with the secure and efficient generation of uniform randomness in hardware. As an initial case study to highlight the capabilities of our modified HADES tool, we present a highly configurable and optionally fully-masked ML-KEM hardware design that improves upon state-of-the-art masked implementations by up to two orders of magnitude while also being competitive with unmasked designs from literature. To validate its practical security, we are the first to conduct practical leakage assessment measurements on the complete decapsulation algorithm, showing no signs of side-channel leakage after 500000 traces.

The CKKS fully homomorphic encryption scheme has traditionally been viewed as suitable only for approximate arithmetic. However, recent work (Alexandru et al., Crypto 2025) has introduced functional bootstrapping techniques that enable accurate lookup tables (LUTs) evaluation in CKKS. Nevertheless, to deal with the high precision problem, the state-of-the-art scheme (Dumezy et al., TCHES 2026) requires reshaping the LUTs into a matrix, which incurs $O(P)$ multiplications for a size-$P$ table and dominates runtime. We first observe that LUT matrices for many practical functions are often highly structured, with exact or numerical rank much smaller than matrix dimension. We then develop a spectral framework for the LUT evaluation problem, which characterizes the relationship between function classes and the singular value decomposition. This framework yields exact rank bounds for structured function classes such as separable functions, and establishes exponential decay of singular values (implying low numerical rank) for smooth analytic functions. Building on this framework, we propose Low Rank Multiplexer Tree Functional Bootstrapping (LRMT-FBT), which evaluates the LUT via the singular values and singular vectors instead of direct matrix multiplication. This reduces the homomorphic multiplication cost from $O(P)$ to $O(r\sqrt{P})$, where $r$ denotes the rank of matrix, while also supporting extensions to multi-value and multi-input settings. We implement LRMT-FBT in OpenFHE and evaluate it across different spectral classes. We also introduce implementation optimizations to improve the bootstrapping efficiency. At high precision, LRMT-FBT provides substantial performance improvements for common low rank functions compared with Dumezy et al. Typically, for $P = 2^{20}$, our method accelerates the LUT evaluation step by \(196.9\times\) for Step (\(r=1\)) and \(99.6\times\) for ReLU (\(r=3\)), yielding functional bootstrapping speedups of \(5.3\times\) and \(5.1\times\), respectively.

As machine-learning-as-a-service (MLaaS) becomes ubiquitous, protecting model queries via private inference is increasingly critical. Existing homomorphic encryption (HE)-based protocols for Private Decision Tree Evaluation (PDTE) have server complexity that scales at least as $O(2^D)$ in the tree depth $D$, so the cost of evaluating each tree grows exponentially with depth; in gradient boosted decision tree (GBDT) ensembles, where predictions aggregate the outputs of many trees, this per-tree cost is directly amplified. In this paper, we present a non-interactive HE-based PDTE protocol built on the CKKS scheme with an end-to-end complexity of $O(p\sqrt{2^D})$, where $p$ is the input bit-length. To the best of our knowledge, this is the first HE-based PDTE scheme that asymptotically improves over the $O(2^D)$ dependence on $D$ while remaining non-interactive. We address two depth-driven sources of $O(2^D)$ dependence in existing protocols: we use the One-Branch-Only (OBO) paradigm from PROBONITE for comparisons, and we design the Baby-Step Giant-Step based Branch Selection algorithm for traversal. To further exploit the structure of GBDT ensembles, we deploy the batched bootstrapping technique by applying level-major tree evaluation. Our experimental results show that, at depth $D=12$, our protocol reduces communication by $8.38\times$ and runtime by $7.74\times$ compared to FASTER, which is the fastest prior HE-based non-interactive PDTE baseline in our amortized setting, and the advantage increases as $D$ grows. These results suggest that our design provides a practical path toward depth-scalable HE-based PDTE for large boosted ensembles.

Satellite communication systems, as critical long-lifecycle infrastructure, face a dual security challenge in the coming decades: the threat of quantum computers and the operational rigidity of traditional Public Key Infrastructure (PKI). While migrating to Post-Quantum Cryptography (PQC) addresses the former, it fails to solve the inefficiency of certificate management, where in-orbit policy updates require a prohibitively slow and complex multi-party re-issuance process. To address these challenges, we introduce the concept of a Post-Quantum Sanitizable Multi-Signature ($\texttt{PQ-SMS}$), a novel primitive that enables controlled certificate adaptation across hierarchical trust while preserving the integrity of the root of trust. Building on this, we present $\texttt{Sat-APCS} $($\textbf{Sat}$ellite $\textbf{A}$daptable $\textbf{P}$ost-quantum $\textbf{C}$ertificate $\textbf{S}$cheme), which cryptographically decouple a certificate's immutable, multi-signed identity from its dynamic operational policies. This allows a delegated entity to perform lightweight, in-orbit policy updates while the foundational signature from the original consortium of authorities remains unchanged and valid. We instantiate $\texttt{PQ-SMS}$ based on the NIST-standard CRYSTALS-Dilithium signature and a ISIS-based chameleon hash, and prove its security under standard lattice assumptions. Furthermore, Performance evaluation demonstrates that $\texttt{PQ-SMS}$ bypasses the interactive re-signing loop of traditional PKI, achieving an order-of-magnitude reduction in update bandwidth.

Asynchronous multi-party computation (AMPC) en- ables a set of mutually distrustful parties to securely compute any joint function on their private inputs under arbitrary network delays. The guaranteed output delivery (i.e., G.O.D.) property is essential for availability, but can be very challenging to achieve in practice. HoneyBadgerMPC (CCS 2019), the first practical AMPC protocol, follows Beaver’s paradigm that generates Beaver triples offline to simplify online computation. One of the underlying building blocks, the random double sharing protocol that generates random double shares, how- ever, implicitly assumes a synchronous network. DumboMPC (Usenix Sec 2025) overcomes the issue by adopting a two-phase workflow where the underlying consensus protocol has to be executed twice, and thus incurs high latency. Velox (CCS 2025) achieves lower latency and weaker cryptographic assumptions at the cost of sacrificing G.O.D. It remains an open question whether there exists a more practical AMPC protocol with the G.O.D. property. In this paper, we present RondoMPC, a practical AMPC protocol with G.O.D. with only one phase of consensus. To achieve this goal, we build a practical asynchronous and complete random double sharing (ACRDS) protocol. Our ACRDS protocol supports batching, so a batch of random double shares can be generated simultaneously. Furthermore, ACRDS supports efficient verification of aggregated secret shares, allowing the random double shares to be used for Beaver triple generation using only one phase of consensus. Our experimentation results show that RondoMPC is highly practical, achieving both higher throughput and lower latency for Beaver triple generation compared to existing protocols.

We present TruthTable, a verifiable database engine that allows a prover to produce a succinct proof that convinces a verifier of the correct execution of the verifier's SQL query over the prover's committed database. TruthTable supports a large subset of SQL, enabling it to prove 17 out of 22 queries in the standard TPC-H benchmark. To our knowledge, this is the widest support out of all prior work. Moreover, TruthTable's proofs are small, and fast to generate and verify: on the TPC-H benchmark with a database of a million rows, TruthTable's average proving time is $55$ seconds, average verification time is $32$ ms, and average proof size is $24$ kB. Compared to prior work, TruthTable's proving times are between $6.3\times$-$63\times$ better, while the verification times and proof sizes are competitive. TruthTable achieves these properties via a codesign of cryptography and database techniques. On the cryptographic front, we propose a new polynomial representation of database tables, and design new subprotocols for proving the correct execution of various relational operators on these representations. On the database front, we propose a query planner that optimizes queries for minimal proving time, as opposed to minimal execution time. We also design new optimizations for this planner that reduce proving time by up to $2 \times$.

Rate Limiting Nullifier (RLN) is a privacy-preserving and decentralized spam-prevention mechanism for anonymous broadcast networks: each member can emit at most $r$ signals per epoch, and any violation reveals a secret that enables the member's stake to be slashed. The standard construction binds each membership to a single secret key $\mathsf{sk}_G$, so the unit of identity, the unit of authorization, and the unit of slashing all coincide with one party. This rules out settings in which a group should speak with one voice, share one rate budget, and stand behind one collective bond without any single member being able to act unilaterally. We introduce Collaborative RLN Signaling (coRLN), a protocol that lets $n$ parties register as a single RLN member and signal only by acting jointly. The group secret $\mathsf{sk}_G$ is held as additive shares under SPDZ and never reconstructed; the identity (or rate) commitment, the per-epoch RLN evaluation, and the broadcast proof are produced inside an MPC network using collaborative zk-SNARKs. The group occupies one leaf in the membership Merkle tree, locks one aggregated stake $\mathsf{stake}_G$, and is bound by one rate limit. We present the construction in both the rate-limit-1 and the general $r \geq 1$ settings, and we extend the protocol with a collaborative withdrawal procedure that lets the group exit without ever reconstructing $\mathsf{sk}_G$. We prove three security properties of coRLN by reduction to the collaborative-SNARK composition and the standard primitives underneath: (i) no PPT adversary corrupting up to $n-1$ parties recovers $\mathsf{sk}_G$ as long as one party is honest; (ii) two signals in the same epoch with the same $\mathsf{messageId}$ yield an efficient extractor that recovers $\mathsf{sk}_G$ and triggers forfeiture of $\mathsf{stake}_G$; and (iii) no strict subset of $G$ can produce a verifying signal. The verifier interface and signal shape match classical RLN at the byte level, so coRLN deploys on existing RLN-aware infrastructure with only the verification key updated.

Distributed shuffling is a core primitive underlying mix-nets, electronic voting, and, more recently, single secret leader election (SSLE) protocols for proof-of-stake blockchains. In these settings, a collection of resource-constrained parties jointly permutes a list of ciphertexts or commitments in order to conceal the correspondence between inputs and outputs. Existing security analyses of such protocols typically rely on heuristic anonymity measures or implicitly assume honest behavior; therefore, they fail to capture statistical dependencies that arise when shuffling is partial and some participants are corrupted. In this work, we introduce a new security model for distributed shuffling that accurately reflects the setting of real-world attacks by explicitly accounting for adversarial corruption and information leakage. Our model allows an adversary to corrupt a subset of shufflers and track selected elements throughout the execution, as well as query the resulting permutation afterwards. We then turn to studying Whisk in this model, the shuffle-based SSLE mechanism proposed for Ethereum. Leveraging Markov-chain techniques, we show that security can only be guaranteed for more stringent parameters than currently proposed. We evaluate the performance impact of changing these parameters on the Ethereum network.

We give a witness-finding cryptanalysis of Stickel-type key exchange schemes, which involve two-sided multiplication of $n \times n$ matrices over $\mathbb{F}_p$, where these matrices are drawn from public subspaces with a particular commuting structure. This analysis covers Stickel's original proposal, Shpilrain's polynomial extension of that scheme, Nager's algebraic extension of that scheme, and more generally all Stickel-type approaches using public subspaces over matrix algebra in finite fields: all such schemes can be broken in polynomial time. We also describe a new key establishment scheme using two-sided matrix multiplication in which the commuting subspaces used to form the key are hidden via conjugation by private terms, blocking this specific public-subspace analysis; the witness-finding problem in this new scheme has a direct reduction from a standard NP-hard problem (Edmonds' problem).

In 2011, Grigoriev and Shpilrain proposed using tropical algebraic structures in cryptography. In recent years, numerous protocols based on tropical and related structures have been introduced, as well as many attacks on some of these protocols. This direction of research is now known as tropical cryptography. As a result of the efforts both to design secure schemes and to analyze their vulnerabilities, many purely algebraic and computational problems have emerged. In this paper, we give an overview of several results and open questions in this area. We discuss the complexity of solving certain classes of systems of equations over tropical and similar structures, as well as algorithms and approaches for solving such systems. We also present results on the asymptotic density of satisfiable systems of equations of special forms over tropical algebras. Furthermore, we discuss the discrete logarithm problem, the two-sided discrete logarithm problem, the knapsack problem, and the subset sum problem over tropical matrix structures. We consider a generalization of marginal sets for tropical semirings and semigroups. We also explore different classes of pairwise commuting matrices.

Fully homomorphic encryption (FHE) enables non-interactive secure transformer inference (NISTI). Due to the high cost of bootstrapping, conventional approaches typically choose parameters that support a large multiplicative depth to reduce bootstrapping frequency. However, larger depth directly increases ciphertext size, resulting in higher communication and computation overheads. In this paper, we introduce a novel functional bootstrapping (FBS) scheme that fundamentally reshapes the computation paradigm for NISTI: by fusing as many operations as possible into each bootstrapping operation, our approach significantly reduces the prescribed multiplicative depth. Our FBS achieves a trigonometric minimax approximation for the target function, making it well suited for precision-sensitive components such as transformer nonlinear layers. Furthermore, we incorporate linear layers into the slot-to-coefficient (S2C) transformation within FBS, thereby eliminating the need to evaluate them separately. Building on these innovations, we present a complete NISTI framework that achieves a 1.9$\times$ speedup in runtime (from 662.3s to 349.5s) and a 3$\times$ reduction in communication (from 48.3MB to 16.1MB) compared with the state-of-the-art.

Poseidon is one of the most widely deployed arithmetization-oriented cryptographic permutations and plays a central role in modern zero-knowledge proof systems. Although several algebraic attacks on reduced-round variants have been proposed, the security of the recommended parameter sets remains intact. A central difficulty in such attacks is controlling the degree growth of the polynomial representations induced by the permutation. In this work, we introduce degree annihilation, a new framework for algebraic cryptanalysis of Poseidon. Unlike round-skipping techniques, which reduce complexity by removing rounds from the algebraic model, degree annihilation reduces the contribution of existing rounds by imposing algebraic constraints that force dominant degree terms to vanish. This yields polynomial systems of substantially lower effective degree. We first present a simple bivariate form of degree annihilation and show how it combines naturally with classical round-skipping techniques. The gain depends on the multiplicity with which the annihilated degree contribution propagates through the remaining nonlinear layers; when this multiplicity matches the contribution of one S-box layer, the effect is the same as skipping an additional nonlinear layer. We then generalize the technique to multivariate settings, where systems of control equations are used to annihilate successive partial-round degree contributions. These systems can be solved using elimination, resultants, and Gröbner basis techniques. As a proof of concept, we apply the framework to reduced-round Poseidon instances and obtain new CICO-2 attacks. More broadly, our results suggest that constructing algebraic varieties that actively control degree growth may provide a new direction for the cryptanalysis of arithmetization-oriented primitives.

Universal multi-party swaps were proposed for secure cross-chain cryptocurrency exchanges across multiple blockchains that require only signature verification from the underlying blockchains. However, existing universal swap protocols remain vulnerable to griefing attacks, where a deviating party aborts the swap to lock a compliant party’s assets for a long period, potentially causing indirect economic losses. A natural approach is to lift existing griefing-free solutions to the universal setting; however, we observe that this direct approach still faces three key challenges: (i) a timeout race attack, which arises from the absence of an upper bound on the transaction validity; (ii) a premium escape attack, which results from multiple refund transactions for the same assets being simultaneously valid; and (iii) a topological limitation, which implies that universal multi-party swaps can support only a special class of strongly connected digraphs, called reuniclus graphs. In this paper, we propose GumSwap, a Griefing-free universal multi-party atomic Swap, which guarantees that a compliant party receives a premium if its asset is locked but not redeemed. To mitigate the timeout race attack and the premium escape attack, we impose minimum timeout intervals for the principal and premium timeouts, respectively, and introduce an asset migration mechanism that ensures that, during any time interval, at most one refund transaction is valid. Given the topological limitations of universal swap protocols, we further design a novel premium distribution mechanism that accommodates two classes of leaders in reuniclus graphs. Our experimental results demonstrate that GumSwap can be performed in less than 0.5 seconds per party, while reducing gas costs by 10.3X compared with existing contract-based solutions.

Universal atomic swaps [Oakland'22] replace hashed timelock contracts with adaptor signatures and verifiable timed dlogs, enabling secure cross-chain cryptocurrency exchanges that only require basic signature verification from the underlying blockchains. However, existing universal swap protocols remain vulnerable to griefing attacks, where a deviating party aborts the swap to lock a compliant party's assets for a long period. A natural approach is to lift existing contract-based solutions to the universal setting, but we identify that this straightforward solution faces two key challenges: (i) timeout race attacks, first identified in PipeSwap [Oakland'25], which arises from the absence of an upper bound on the transaction validity; (ii) a timeout overlap dilemma, which results from multiple overlapping refund periods. In this paper, we propose HedgeSwap, a universal hedged atomic swap protocol against griefing attacks, which compensates a compliant party with a premium if its asset is locked but not redeemed. To mitigate the timeout race attacks and timeout overlap dilemma, HedgeSwap eliminates the premium timeout and instead relies on a hard relation to refund the premium. For high-value asset swaps where the parties acceptable premium ranges do not overlap, we further propose a round-based HedgeSwap that utilizes a premium migration mechanism to solve these two timeout challenges, where parties iteratively increase the premium until the lock-up risk premium acceptable to both. Our experimental results show that our HedgeSwap can complete in under 0.5 seconds, and round-based HedgeSwap completes in under 1.3 seconds for a five-round setting, while HedgeSwap reduces gas cost by 2.69X compared to existing contract-based solutions.

A pair of differences $(x,y)$ is a \emph{related differential} for a linear layer $M$ if, for every coordinate at both the input and the output, at least one of the two values vanishes or the two values coincide. Related differentials underlie the zero-difference attack on AES of Bardeh and Rijmen, and the question of which maximum distance separable (MDS) matrices admit them was raised by Daemen and Rijmen, who showed that every $4\times4$ circulant MDS matrix does while some Hadamard ones do not. In earlier work the $3\times3$ MDS matrices over $\mathbb{F}_{2^r}$ admitting related differentials were characterized by fifteen explicit equations. In this paper we settle the $4\times4$ case completely: an MDS matrix $M=DNE$ over $\mathbb{F}_{2^r}$ admits a related differential if and only if at least one of $280$ explicit polynomial equations in the nine free entries of its reduced form $N$ holds. The equations, $70$ quadratic and $210$ cubic, are pairwise distinct, irreducible and pairwise coprime, and fall into $27$ orbits under the natural symmetries. We further determine the structure of the equation set: the fifteen equations of the $3\times3$ case are exactly the points of $\mathrm{PG}(3,2)$, while the $280$ equations span a $14$-dimensional $\mathbb{F}_2$-space, satisfy exactly $560$ additive relations, and contain exactly $840$ pairs that can never hold simultaneously on an MDS matrix. The discarded zero patterns split into $525$ whose determinant condition is equivalent to the failure of MDS-ness and $289$ vacuous cases. Over $\mathbb{F}_8$, the smallest field carrying $4\times4$ MDS matrices, exhaustive enumeration shows that there are exactly $720$ reduced MDS matrices; each satisfying exactly $28$ of the equations and each equation being satisfied by exactly $72$ matrices; in particular every $4\times4$ MDS matrix over $\mathbb{F}_8$ admits a related differential. Over $\mathbb{F}_{2^{10}}$ we exhibit an explicit MDS matrix admitting none. All results are verified by exact computation against an independent exhaustive search.

GPU Tensor Cores, specialized hardware units designed to accelerate matrix multiplication, have served as the primary engine behind the AI revolution. Given the exponential performance gains they have delivered, aligning cryptographic implementations with this hardware evolution is critical. This is particularly acute for zero-knowledge proofs (ZKPs), a cryptographic primitive that currently grapples with high proof generation costs. Existing GPU implementations for ZKPs rely exclusively on general-purpose SIMT cores, leaving the massive computational power of Tensor Cores untapped. In this paper, we introduce TensorZKP, the first GPU framework to harness Tensor Cores for ZKP acceleration. Since Tensor Cores are designed for low-precision matrix multiplication, mapping ZKP's arithmetic to this hardware is non-trivial. To bridge this gap, we develop Tensor-Core-compatible finite field arithmetic and reformulate ZKP modules, specifically sum-check protocols and Spielman code, into matrix multiplication tasks. Furthermore, we design an asynchronous warp-specialized framework that pipelines memory access, Tensor Core matrix operations, and SIMT-based modular reductions. We instantiate these optimizations with HyperPlonk as the Polynomial Interactive Oracle Proof (PIOP) and Brakedown as the Polynomial Commitment Scheme (PCS) to enable end-to-end proof generation. The evaluation results show that TensorZKP exhibits remarkable efficiency. At a $2^{25}$ scale, the underlying building blocks complete in $0.85$ ms for inner product, $0.91$ ms for scalar-vector multiplication, $4.04$ ms for degree-2 sum-check, and $11.58$ ms for the encoder. For a circuit with $2^{25}$ multiplication gates, TensorZKP achieves a proof generation time of only $215.28$ milliseconds, representing a $955\times$ speedup over the CPU baseline and a $36.2\times$ improvement over state-of-the-art SIMT-based GPU implementations.

Shift-invariant maps have been employed to design nonlinear layers in many symmetric cryptographic schemes, such as the $\chi$-map used in Keccak. In this paper, we study a family of shift-invariant maps on $\mathbb{F}_2^n$ which exhibit strong arithmetic properties with respect to the composition. The set of their defining functions, which we denote by $\Omega_{\underline{a}}$, is induced by a so-called ``bifix-free'' sequence $\underline{a}=(a_1,a_2,\ldots,a_m)\in \mathbb{F}_2^m$ with $2\leq m<n$. It is shown that $\Omega_{\underline{a}}$ forms a commutative monoid with respect to the composition. If $m\nmid n$, then $\Omega_{\underline{a}}$ is isomorphic to the unit group of $\mathbb{F}_2[x]/ (x^{\lceil \frac{n}{m} \rceil})$; if $m\mid n$, then the unit group of $\Omega_{\underline{a}}$ is isomorphic to that of $\mathbb{F}_2[x]/ (x^{ \frac{2n}{m}}+x^{ \frac{n}{m}})$. The isomorphic relation transforms the composition of functions in $\Omega_{\underline{a}}$ into the multiplication of polynomials in the quotient ring of $\mathbb{F}_2[x]$, where the algebraic properties of the latter are well-understood. As a straightforward application, we focus on the algebraic properties of a particular class of functions in $\Omega_{\underline{a}}$, denoted by $\rho_k$ for $k\geq 1$, which include the $\chi$-map as well as several other known maps studied in earlier literature. It is shown that $\rho_k$ is invertible if and only if $m\nmid n$. Also the inverse and the cycle structure of $\rho_k$ (if invertible) can be fully characterized. As different bifix-free sequences $\underline{a}$ typically induce different families of functions $\Omega_{\underline{a}}$ with pairwise trivial intersections, this work offers abundant parameter flexibility for designing invertible shift-invariant maps as well as deep insights into their algebraic properties.

Anonymous tokens with private metadata bit (ATPM) allow an issuer to embed a hidden trust flag, as a single bit, within issued tokens. The bit remains hidden from the clients, but verifiers can read the bit and rate-limit or discard tokens marked suspect. A series of ATPM constructions exist in the literature, however all current constructions rely on classical hardness assumptions such as RSA groups, pairings, or elliptic-curve VRFs and do not provide any post-quantum security guarantees. In this work we present, the first ATPM scheme based on lattice assumptions. Tokens generated with our scheme are publicly verifiable, and privately bit-extractable given partial knowledge of the issuing authority's secret. Our design follows the Fischlin blind-signature paradigm and enriches it with lattice-based linearly-homomorphic encryption to carry the hidden bit. We also instantiate our scheme from Falcon-512 and the efficient LNP22 lattice NIZK proof system (Lyubashevsky et. al, Crypto '22). The resulting protocol, which we call $\textsf{Atlantis}$, requires 70 KB of client-issuer communication and yields 129 KB tokens.

Session is a widely deployed decentralized messenger application that emphasizes user anonymity and privacy through end-to-end encryption. Session currently employs its own uniquely designed messaging protocol, Session Protocol V1, having migrated from the extensively studied Signal Protocol. In this paper, we conduct a comprehensive, implementation-driven security analysis of the Session Protocol V1, focusing on its 1-to-1 and closed-group communication mechanisms. Our analysis reveals two fundamental design vulnerabilities: the absence of mutual public key authentication and the lack of cryptographic bindings to monotonic sequence counters. Exploiting these weaknesses within the context of actual application environments, we demonstrate three practical attacks: an impersonation attack, a message timestamp forgery attack, and message dropping and replay attacks. These attacks allow malicious server nodes or unprivileged malicious insiders to substitute public keys, silently suppress or duplicate messages, and manipulate the perceived chronological order of conversations. The findings highlight that these exploits severely undermine the fundamental security guarantees of the messenger. Finally, we propose immediate, actionable mitigation strategies to address the identified flaws and secure the protocol against these threats.

Leakage-resilient rekeying schemes aim to maintain cryptographic security in the presence of side-channel leakage by periodically refreshing ephemeral keys before sufficient information can be accumulated by an adversary. Fallen Sanctuary (LR4) is a recent higher-order leakage-resilient rekeying construction that achieves exponential security amplification with respect to the number of primitive encryption invocations and the number of traces required to compromise the physical security of the implementation. Its security, however, relies on the correct maintenance of internal counters and cached intermediate keys that enforce the prescribed trace bounds. In this work, we investigate the security of LR4 under a combined fault and side- channel attack model. We show that transient faults targeting the counter-update and counter-validation mechanism can prevent the advancement of the rekeying state, causing repeated reuse of temporal keys that are intended to be short-lived. As a consequence, the bounded-trace assumptions underlying the LR4 security proof no longer hold. We demonstrate that an adversary can accumulate an arbitrary number of leakage traces corresponding to the same secret state, effectively reducing the security of the protected primitive to that of a conventional implementation without rekeying. We evaluate the attack on a fault simulated implementation and analyze its impact on the leakage-resilience guarantees claimed by LR4. Our findings emphasize that leakage-resilient rekeying schemes must consider fault- induced violations of state evolution assumptions in addition to conventional side- channel leakage.

In non-synchronous networks, classic partition arguments imply that any $t\text{-resilient}$ protocol among $n$ parties cannot ensure safety for many meaningful functionalities once the number of corruptions reaches $f \geq n - 2t$. This motivates building in accountability to detect (and deter) safety violations. We present the first accountable asynchronous MPC (AAMPC) protocol that securely evaluates any arithmetic circuit $\mathcal{C}$ (asynchronously computable by a trusted third party). Our protocol: (1) Ensures all target hyperproperties (correctness, privacy, input-independence, and guaranteed output delivery) whenever $f \leq t < n/3$. (2) Provides strong accountability for $f \in (t,\,t_{\mathrm{acc}}]$ with $t_{\mathrm{acc}} < n - t$: either (i) all hypersafety properties continue to hold (without guaranteed output delivery), or (ii) every honest party obtains publicly verifiable evidence implicating at least $n - 2t$ faulty processes. The construction follows the standard offline/online paradigm and assumes only a transparent setup: a bulletin-board public key infrastructure (PKI) and a common random string (CRS). Our main technical contribution is an accountable additively homomorphic high-threshold asynchronous complete (verifiable) secret sharing functionality with amortized linear communication for both sharing and reconstruction. This yields an efficient online phase with $O\big(\mathsf{Depth}(\mathcal{C})\big)$ latency and amortized $O(|\mathcal{C}|n)$ communication. We additionally provide a constant-round offline phase with cubic communication per generated Beaver triple. Our results are formalized and proven in the Accountable Universal Composability (AUC) framework (S&P 2023), an extension of UC designed to support modular analysis of accountability guarantees.

Elliptic Curve Cryptography (ECC) underpins modern public-key infrastructure, relying on the computational hardness of the Elliptic Curve Discrete Logarithm Problem (ECDLP). While monolithic quantum architectures running Shor's algorithm threaten ECC, their physical realization is bottlenecked by massive logical qubit demands for modular inversion. Distributed Quantum Computing (DQC) offers a scalable pathway by interconnecting smaller, cooperative Quantum Processing Units (QPUs). In this paper, we adapt two state-of-the-art distributed quantum frameworks, namely a zero-quantum-communication paradigm and a sequential teleportation-based protocol, to the elliptic curve setting. We provide the first rigorous resource estimation of distributed ECDLP solvers. By incorporating the compact, register-sharing Extended Euclidean Algorithm (EEA) formulation, we quantify the physical design trade-offs for a cryptographically secure 256-bit elliptic curve on fault-tolerant architectures. Specifically, the zero-quantum-communication variant operates with 1094 to 1154 logical qubits per node, whereas the teleportation-based variant requires as few as 856 to 1098 logical qubits per node. Furthermore, optimizing the arithmetic window size ($\omega = 16$) over $k = 22$ nodes reduces the single-node Toffoli gate count to $2^{26.84}$, which represents an approximate $14\times$ reduction compared to the $2^{30.63}$ baseline of monolithic schemes. Our results delineate the architectural boundaries between inter-QPU communication, classical coordination, and single-chip hardware floors, mapping out an efficient design space for distributed quantum cryptanalysis.

Digital library lending is a critical resource for access to information. Currently prevalent models of digital lending, however, involve opaque licensing schemes that entail serious drawbacks to reader privacy and freedom of expression. In popular modern library apps, publishers and hidden intermediaries control a wealth of informa- tion about readers and reading habits, at a scale and level of detail that would be essentially impossible in physical library lending. To understand digital lending needs in practice, our work begins with a series of interviews with library professionals (𝑁= 11). We present thematic findings on their concerns with existing systems, including privacy, surveillance, preservation, and lack of library control over resources. Many of the concerns raised are inherently unproblematic in the context of physical library lending—leading us to our central technical question: Can digital lending achieve privacy and transparency at least as strong as physical library lending? Based on our qualitative findings, we provide the first rigorous modeling of security, privacy, and transparency requirements in digital library lending. As existing systems fall short of the strong guarantees we model, we propose a new system design, LendLocked, based on cryptography and trusted hardware, and prove it achieves these guarantees in the random oracle model. We micro-benchmark our design’s key cryptographic functionalities, s

Constant time programming patterns is the primary defense against timing attacks on cryptographic implementations, yet what "constant time" means varies across academia and industry. This work systematizes constant time models and their evolution, identifies a recurring gap between what models protect and what specifications assume, and distills an offensive methodology for discovering timing vulnerabilities that originate outside the cryptographic primitive boundary. Applying this methodology, we locate a specification-level vulnerability related to private key loading, and confirm the leak in both OpenSSL and BoringSSL. Counterintuitively, BoringSSL's per-observation signal is several orders of magnitude stronger than OpenSSL's, despite an explicitly stricter threat model.

Following the cryptographic security analyses of proof-of-work (PoW) blockchain protocols, a line of research has focused on their economic robustness. The two core questions asked are: How resilient is the system to rational attacks, and how profitable it is for miners to execute it. However, to our knowledge, no work to date has attempted to address them considering the full complexity of the blockchain protocol, including difficulty readjustment, which is needed to handle dynamic participation, price fluctuations, and the impact of risk. In this work, we provide a fine-grained game-theoretic analysis for Nakamoto-style PoW blockchains, which takes into account both incentives of parties to deviate and complications introduced by difficulty readjustment. Our results employ the Rational Protocol Design framework of Garay et al. [FOCS’13] and extend recent works on the economic robustness of the Bitcoin backbone protocol to the variable difficulty setting. Notably, our fine-grained specification of miners’ utility incorporates variable difficulty adjustment alongside factors like the average cost of mining and the depreciation factor, which, despite being common in economics, are typically either abstracted as exogenous parameters or ignored in the blockchain literature. We showcase the expressivity and usefulness of our formulation of utilities by using it to provide estimates and trends for such factors across several real-world cryptocurrencies.

FESTA is an isogeny-based trapdoor function proposed as a high-performance alternative in isogeny-based cryptography. Its core design principles have inspired a number of related constructions, collectively referred to as FESTA variants. The MOXZ attack is an adaptive attack that exploits malicious ciphertexts together with access to a checking oracle, aiming to compromise FESTA and its variants. This attack applies to FESTA variants whose secret keys are derived from isogenies of known degree; however, it does not extend to variants employing masked-degree isogenies. In this work, we present a novel adaptive attack that generalizes the MOXZ attack. Our attack successfully targets several FESTA variants even when their secret keys are isogenies of masked degree. We also identify POKE-4D as an exception for which our attack does not appear to be applicable.

Shuffle differential privacy (shuffle DP) offers an attractive distributed alternative to standard differential privacy. It uses a secure shuffler to permute users' randomized encodings, providing individual data privacy without a central trusted entity. A key challenge, however, is to achieve both generality and client efficiency. Under information-theoretic shuffle-DP guarantees, protocols that nearly match central-model utility are restricted to statistical tasks such as summation and histograms. In contrast, in the computational setting, additive randomized encodings (ARE), introduced by Halevi et al. (CRYPTO 2023), yield a generic compiler that achieves central-model utility for arbitrary mechanisms. However, their construction incurs prohibitive worst-case computation and communication costs for clients, making it impractical for resource-constrained devices such as mobile phones, IoT sensors, and web browsers. In this work, we present a client-efficient one-round compiler from central DP to non-robust computational shuffle DP. To achieve this, we first construct a new balanced ARE scheme, where all the clients almost equally share the computational burden in the protocol. For a mechanism $M$ over $n$ clients, this reduces the worst-case per-client computation from $O(|M|)$ in prior work to $O(|M|/n)$, where $|M|$ denotes the circuit complexity of the mechanism. The key technical ingredient is a new permute-XOR ARE primitive that enables wire splicing across independently generated garbled subcircuits. Secondly we design a more efficient ARE-to-shuffle compiler, whose client bandwidth scales with the sparsity and cross-partition structure parameter of the ARE encoding - a quantity that is always sublinear in $n$. This is an improvement over Halevi et al. (CRYPTO 2023) where each client bandwidth is $\Omega(n)$. At a high level, the first contribution improves client computation while the second improves client bandwidth. We provide an implementation of our generic compiler for differentially private tasks including selection, distinct elements, and linear contextual bandits. We obtain shuffle protocols that match the utility of their central-model counterparts with reasonable client overhead. We evaluate our method across a range of practical settings, and observe substantial gains over the compiler of Halevi et al., with per-client computational and bandwidth speedups increasing linearly in the number of clients.

We revisit the problem of mitigating information leakage in the widely used but insecure compress-then-encrypt paradigm. While encryption hides message contents, the ciphertext length is directly related to the length of the compressed message, which may, in turn, leak information about the {\em content} of the message itself. Recent work of Blocki et al. (TCC 2025) proposed an $(\varepsilon,\delta)$-differentially private approach that adds randomized padding calibrated to the global sensitivity of the compression algorithm, and showed that the global sensitivity of LZ77 is $O(W^{2/3}\log n)$, where $n$ is the input length and $W$ is the sliding window size. However, prior analysis focused only on sensitivity with respect to single-character edits, which leads to limited privacy guarantees when protecting longer substrings such as passwords, passphrases, cookies, or confidential user records. A natural attempt to handle longer secrets is to appeal to group privacy, but for approximate differential privacy, this leads to very poor parameter degradation: in particular, the effective value of $\delta$ can grow exponentially with the group size $g$. In this work, we introduce and study the sensitivity of compression schemes under block edits. Specifically, we define two strings to be $g$-neighbors if they differ only within a contiguous interval of length $g$. Our main technical contribution is a nearly tight characterization of the $g$-consecutive sensitivity of LZ77. We show that the $g$-consecutive sensitivity of both LZ77 variants (with and without self-referencing) is at most $O((W^{2/3}+g+\sqrt{Wg})\log n)$. In particular, when $g \leq W^{1/3}$, the bound simplifies to $O(W^{2/3}\log n)$, matching the known bound for single-character edits. Thus, calibrating noise to the single-character sensitivity of LZ77 already suffices to protect much longer contiguous substrings. We provide matching lower bounds to demonstrate that our upper bound is tight, e.g., when $n=W=O(g^2)$, the $g$-consecutive sensitivity of LZ77 is at least $\tilde{\Omega}(g^{1.5})$, matching the $\sqrt{Wg}=O(g^{1.5})$ term from our upper bound up to a logarithmic factor.

Secure Multi-Party Computation (MPC) enables private computation, but has significantly higher overhead than plaintext execution. Hybrid MPC compilers improve concrete efficiency by mapping distinct computation parts to contextually optimal MPC protocols. However, state-of-the-art systems like Silph (Chen et al., S&P’23) depend on deployment-specific cost models that are cumbersome to retune, and compute mappings via brittle heuristics or costly Integer Linear Programming (ILP), limiting scalability and portability across protocols and deployment settings. We present SING, the first machine-learning-based framework for hybrid MPC share assignment. SING leverages Graph Neural Networks (GNNs) for: (1) imitation of Silph’s assignments, accelerating share assignment by up to $76,697\times$ with comparable quality; and (2) cost-driven learning, where we train a GNN cost predictor on synthetic or empirical costs (e.g., runtime or communication), freeze it, and train the share-assigning GNN to minimize predicted costs. The latter supports expressive non-linear cost models, avoiding ILP's linearity constraints, and enables retargeting to new protocol suites and deployment settings by re-fitting the predictor. Finally, we release our synthetic benchmark resources, including a dataset of 704 MPC circuits with wide-ranging hybrid assignments.

In the private simultaneous message (PSM) setting, $k$ players obtain inputs $x_i\in\{0,1\}^n$ and then independently send messages to a referee, who should learn $f(x_1,...,x_k)$ but no other information about $(x_1,...,x_k)$. The PSM setting was introduced as a minimal model for secure multiparty computation. In the quantum setting, PSM has been related to non-local quantum computation (NLQC), and has several connections to the complexity of Boolean functions. The communication and correlation cost of implementing private simultaneous message passing may be much larger than the cost without privacy, and the cost of privacy in this setting remains poorly understood. Here, we give new upper and lower bounds on the PSM model, in both the quantum and classical settings. Concretely, we prove two lower bounds: 1) Nečiporuk's measure lower bounds the entanglement required for $k$-player quantum PSM with perfect correctness. This can be evaluated to give quadratic lower bounds for some explicit functions. 2) The rank of the communication matrix of $f(x_1,x_2)$ lower bounds 2-player quantum PSM with perfect privacy but imperfect correctness. This implies a previously unknown lower bound on classical PSM with imperfect correctness. When allowing both quantum communication and shared entanglement, these two bounds are the first lower bounds on quantum PSM that make use of the privacy condition. Regarding upper bounds, we show: 1) Letting $s$ be the size of a quantum circuit computing $f$, $d_f$ be the circuit depth, $k$ the number of players, $n$ the number of bits received by each player, and $\epsilon$ the correctness parameter of the PSM protocol, we obtain the upper bound $\mathsf{PSM}_k^*(f) \leq (kn +s) \cdot \log^{O( d_f)}(s/\epsilon)$. 2) The square of the Fourier 1 norm of $f$, $\Vert \hat{f}\Vert_1^2$, upper bounds the classical PSM complexity, $\mathsf{PSM}(f)\leq O(\Vert \hat{f} \Vert^2_1)$. In proving the first upper bound, we also generalize existing $T$-depth based techniques for NLQC from $2$ to $k\geq 2$ parties, and consider cases where the Clifford layers are restricted to having small light cones. These generalizations may be of independent interest.

We introduce the Huffman-Merkle Tree (HMT), an authenticated data structure (ADS) optimized for dynamic workloads where some items may be more frequently accessed than others, and access frequencies change over time. An ADS allows proving item membership against a short commitment to a large mutable state, with applications including verifiable storage, Internet transparency services, and blockchains. Optimizing ADS performance under continuously changing access frequencies has not been fully addressed before, neither in theory nor in practice. HMT tackles access skew via tiering: "hot" items are stored according to a Huffman coding layout where frequently accessed items are closer to the root and thus contribute less to overall costs, while a binary Merkle Tree (MT) is used for cold and new elements to lower their update overhead. To efficiently handle dynamic workloads, we incrementally apply and batch layout changes, track access frequencies via count-min sketch, use a tier promotion cache, and consider various tier migration policies. We implement HMT and compare it on real-world data against Ethereum's Merkle Patricia Trie (MPT) ADS and its proposed replacement, the Unified Binary Tree (UBT). Our evaluation considers two metrics: the amount of hashing per ADS update and access-weighted membership-proof size. The latter metric captures both the cost of accessing each item and its access frequency. We find that the best HMT policy uses about 2.4x and 0.34x less average hash operations than MPT and UBT respectively, while featuring proofs shorter by 0.18x than MPT and 0.55x than UBT.

Modern consensus protocols often aspire to be responsive---that is, to confirm transactions in time proportional to the actual network delays as opposed to a (typically much larger) worst-case bound on network delays. Responsiveness can yield substantial practical improvements in both protocol latency and throughput. In blockchain settings, however, block proposers commonly have economic incentives (most notably MEV) to delay their blocks, a phenomenon repeatedly observed in practice, e.g., in the block production supply chains for Ethereum and Solana. Such incentives clash with responsiveness in existing protocol designs. This paper develops a rigorous framework for designing incentive-compatible responsive consensus protocols. We first consider the canonical case of single-leader protocols and establish feasibility results characterizing the conditions on the distribution of network latency under which responsiveness can be incentivized through a suitable reward function. We further quantify the amount of stake required from the leader to deter dishonest delays. We then show strong positive results for protocols with multiple leaders, demonstrating that the multi-leader approach is fundamentally superior to single-leader designs for resolving the tension between responsiveness and incentive-compatibility: by forcing leaders to compete for rewards, much of the burden otherwise placed on the incentive mechanism is alleviated. Notably, this results in simpler reward mechanisms with no stake requirements that also remain feasible in parameter regimes which are provably impossible under a single leader.

In this paper, we demonstrate a way to generalize learning with errors (LWE) to the family of so-called modular-maximal cyclic groups which are non-commuting. Since the group $\mathbb{M}_{2^t}$ has two cycles of maximal multiplicative order, we use this fact to construct an accurate criterion for restoring the message bit with overwhelming probability. Furthermore, we implement the original idea by O. Regev in the considered group to gain benefits from the non-commutativity of $\mathbb{M}_{2^t}$. Also we prove that using this approach we can achieve a level of security comparable to the original idea.

We provide a new way of performing an algebraic attack on the McEliece cryptosystem based on binary Goppa codes. It also applies in general to the case where the field over which the Goppa code is defined is of even characteristic. It is based on a new algebraic modeling for finding as in [CMT23,M25,BLT26] matrices of rank $2$ in the code of quadratic relations related to the Goppa code that is attacked. Such matrices are then used to recover the secret algebraic structure of the code, from which an equivalent secret key can be efficiently derived, leading to a full key-recovery attack. A byproduct of our approach is a new distinguisher for Goppa codes in even characteristic which is as the syzygy distinguisher of [R25] subexponential in the security parameter of the scheme. We demonstrate the effectiveness of our attack on McEliece TII challenges, some of which having been studied in [BLT26], and aimed at having $83$,$89$,$119$,$166$, $210$ and even $248$ bit security respectively and CFS keys with parameters $r=9$ and $m=16$, corresponding to a security of $74.9$ bits according to [LS12]. This CFS key was not attacked in practice in [BLT26] and took us 14 hours of computation and 24GB of RAM. We make the conjecture that this attack has a complexity which is of the same nature as the distinguisher, namely subexponential in the security parameter.

Post-Quantum Cryptography (PQC) and Quantum Key Distribution (QKD) are both contenders for securing communication against quantum adversaries, but are at different stages of maturity. For hedging security risks, hybridization is the default approach. Unlike previous research on classical–post-quantum hybrids, we propose a QKD-PQC hybrid for Authenticated Key Exchange (AKE). To minimize the attack surface, we completely remove the requirement for digital signature schemes and propose a Hybrid Authenticated Key Exchange (HAKE) that combines Post-Quantum (PQ) AKE and QKD key agreement, leveraging Key Encapsulation Mechanisms (KEMs) for both key exchange and authentication. Our fully modular security analysis, based on the recent multi-input Key Derivation Function (KDF) framework by Backendal et al. (Eurocrypt 2025), establishes AKE security in the CK01 model and yields a conditional information-theoretic security guarantee when the QKD component is uncompromised; a property not achieved by prior hybrid protocols. We demonstrate the protocol’s practical feasibility with benchmarks using ML-KEM, FrodoKEM, and Classic McEliece.

Hybrid post-quantum migration is entering deployed handshake designs, but hybrid KEM security protects only one shared-secret input. It does not by itself say whether handshake, application, exporter, or resumption material remains pseudorandom after branch reveals, stage-key reveals, selective corruptions, or late corruptions. We characterize these staged claims through branch-formula freshness: each stage receives a monotone formula over branch exposure, authentication freshness, transcript binding, KDF ancestry, and explicit non-reveal atoms. Secrecy follows by replacing a surviving branch contribution and then using a labelled HKDF/PRF-style target-hiding argument along a fresh KDF cut; agreement follows separately from authentication binding and injective transcript representation. We also give selector-local accounting, where a fixed admissible witness selector determines which surviving branches and KDF cuts are charged. For scoped TLS 1.3 ECDHE--ML-KEM 1-RTT, we identify the branch-replacement, HKDF-path, and binding assumptions that imply concrete preservation bounds for handshake, application, exporter, and resumption targets.

All EU member states are required to roll out a digital identity system - the European Digital Identity (EUDI) wallet - by the end of 2026. Strong privacy is at the core of the underlying regulation, which mandates the EUDI wallet to support selective disclosure and unlinkability. The wallet currently being developed relies on the batch issuance of one-time ECDSA credentials that sign attributes through individually salted hashes for selective disclosure. This solution is known to achieve only a weak form of unlinkability, where the credential issuer must be honest: a malicious issuer could trace users through the salted hashes it signs and the signature value itself. But such a tracing attack requires the issuer to store all signed data and communicate with the verifying parties for tracing, which can be argued to be too cumbersome or obvious to happen in reality. In this work, we therefore initiate the study of a more subtle type of subversion attacks. Therein, the issuer can deviate from the issuance protocol, with two goals: (i) enabling verifiers in possession of a short tracing key to de-anonymize users and (ii) keeping this deviation undetectable from users. We formalize unlinkability against such subversion attacks, and show that batch-issued credentials with salted hashes do not achieve that form of privacy. We present several undetectable subversion attacks against batch-issued ECDSA credentials and suggest lightweight mechanisms to provably mediate them.

Pseudorandom codes (PRCs) are error-correcting codes whose codewords are computationally indistinguishable from uniform random strings, a primitive motivated by the need to robustly watermark generative AI models. While recent breakthroughs have established the feasibility of PRCs, critical challenges remain regarding the diversity of their underlying cryptographic assumptions and their security against active adversaries. This work advances the study of PRCs on two complementary fronts: structural diversity and advanced security. On the structural side, we propose a novel PRC template that departs from the prior one based on sparse parity-check trapdoors. We introduce a new LPN-type assumption, formalized as Dense-Planted LPN, which postulates $(\mathbf{M}\mathbf{T}, \ \mathbf{M}\mathbf{T}\mathbf{s}+\mathbf{e})\ \approx_c\ (\mathbf{M}\mathbf{T}, \ \mathbf{u})$, where $\mathbf{T}$ is a random dense matrix and $\mathbf{M}$ is sampled from a distribution containing a planted structure. This hidden structure enables a completely new decoding mechanism based on a local-window search rather than global parity checks. Notably, this template provides a viable path toward constructing PRCs from assumptions beyond code-based ones, including Learning with Errors (LWE) assumptions. On the security side, we construct the first public-key PRC secure against pre-challenge chosen-codeword attacks (CCA1) in the standard model. In realistic watermarking deployments where detectors are exposed as public services, CCA security is essential. However, prior CCA-secure PRCs were only achievable in the random oracle model. By formally introducing and instantiating a robust tag-based equivocal bit commitment scheme combined with robust hinting PRGs, we demonstrate that CCA1 security can be achieved in the standard model without sacrificing decoding robustness.

Pseudorandom codes (PRCs), recently proposed by Christ and Gunn (CRYPTO'24), are encryption schemes that have pseudorandom ciphertexts and a decryption algorithm which is resilient against a bounded number of Hamming errors. This notion provides a significant strengthening over standard PKE and has exciting applications in, e.g., watermarking LLMs. The recent work of Alrabiah et al. (STOC'25) initiated the study of CCA-secure public-key PRCs, where the adversary is additionally given access to a decoding oracle. In terms of realizations, they provide one that can be proven secure in the random oracle model. Constructing CCA-secure public-key PRCs in the standard model remained an open problem. In this work, we resolve this problem and provide the first construction of CCA-secure public-key PRCs in the standard model. Our construction achieves a constant rate and can decode from a constant fraction of adversarial errors. In fact, our construction is a general blueprint that can be instantiated from a broad range of standard cryptographic assumptions. As an additional contribution, we construct a strong adaptively robust public-key pseudorandom code with conjectured sub-exponential security based on a new family of assumptions we call Noisy McEliece. In a nutshell, these assumptions mask a scrambled generator matrix from an efficiently decodable inner-code family with sparse Bernoulli noise; this additional error is meant to obscure the algebraic structure targeted by known attacks and thereby permits candidate instantiations from broader classes of codes.

Masking stands as one of the most effective countermeasures against side-channel attacks. While a number of recent works have investigated first-order masking schemes that eliminate the need for fresh randomness, most existing solutions trade off this randomness reduction against increased latency or area overhead. This paper targets the simultaneous achievement of low latency and zero fresh randomness. To this end, we make the following contributions. First, we identify a security flaw in the round-based design proposed by Askeland et al.\ at CARDIS 2022, which builds upon the Changing of the Guards (COTG) technique. Second, we propose a revised construction that rectifies this vulnerability without incurring any additional randomness or latency penalty. Finally, by integrating the Time Sharing Masking (TSM) S-box introduced at CHES 2025, we present a first-order masked AES implementation with a latency of 20 clock cycles that requires no fresh randomness.

The eSIM specification enables remote SIM provisioning without the need to hand out a physical SIM card. Instead of a physical SIM card, the subscriber downloads a SIM profile, which contains a subscriber's identity and authentication key material, to their embedded UICC, a discrete, embedded chip in the user's phone. This provisioning process is specified in the remote SIM provisioning (RSP) protocol and is secured through contemporary public-key cryptography. However, the potential advent of general-purpose quantum computers threatens the security of RSP. This paper provides a quantum threat analysis of the RSP protocol, considering both Harvest Now, Decrypt Later attacks and active quantum attacks. To alleviate this threat, this paper introduces PQC-RSP, a post quantum secure version of the RSP protocol. The main challenge we address is the introduction of key encapsulation mechanisms (KEMs) into the RSP protocol, both in a PQC-only and hybrid version, and the security implications of this modification. We prove the security of PQC-RSP and review the performance overhead introduced through the usage of post quantum cryptography.

We initiate the study of arithmetic private information retrieval (APIR) schemes, in which the database is a vector of field elements and the scheme makes a black-box use of the field. We obtain the following results. 1. Our main result is a negative one: We show that no single-server APIR scheme can achieve non-trivial download cost smaller than $n$ field elements. We observe that recent proposals for code-based PIR (Holzbaur et al., ISIT'20; Verma and Hollanti, ISIT'24) are arithmetic, and show how to break them within a few minutes on a standard workstation for all suggested parameters. 2. We complement the above by positive results in alternative models. Concretely, we show that with either two servers or a single server with secret-key preprocessing, it is possible to construct computationally secure APIR schemes based on well-studied coding assumptions. This is achieved by arithmetizing the distributed-point-function-based PIR of Boyle et al.(CCS'16), and by observing that the recent construction of secret-key single-server PIR by Chen et al.(STOC'26) also arithmetizes. 3. Finally, we characterize the existence of information-theoretic two-server APIR schemes in linear-algebraic terms, and show that communication of $O(n^{1/3})$ can be achieved in this setting based on the original approach of Chor et al.(FOCS'95). The optimality of this result remains an interesting open question.