Threshold RSA signatures face a fundamental obstacle: reconstructing the private exponent from Shamir shares requires Lagrange coefficients whose computation involves modular division by values tied to $\phi(N)$, which must remain hidden. This obstacle is particularly acute for critical deployments such as Intel SGX code signing, which mandates $e=3$. Existing $e=3$-compatible approaches incur substantial overhead, increased share sizes, or sacrifice security properties such as perfect secrecy. This work introduces the integer coordinate framework, achieving $e=3$ support with EUF-CMA security under the standard RSA assumption alone. By carefully selecting interpolation coordinates that yield integer-valued Lagrange coefficients, we eliminate all modular inversions modulo $\phi(N)$, requiring only standard integer arithmetic and modular exponentiation. The framework achieves $O(\kappa)$-bit share sizes, perfect secrecy, and computational efficiency previously unattained for $e=3$-compatible schemes. Although we currently lack an efficient general algorithm for constructing coordinate sets for arbitrary $(t,n)$—a challenging open problem for future work—the coordinate families found via heuristic search achieve coverage for $2 \leq t \leq n \leq 9$ and selected $n=10$ configurations, sufficient for small boardroom-size deployments. The resulting online protocol is extremely simple and immediately enables practical $e=3$ threshold RSA for Intel SGX and similar applications.

Obliviousness has been regarded as an essential property in encrypted databases (EDBs) for mitigating leakage from access patterns. Yet despite decades of work, practical oblivious graph processing remains an open problem. In particular, all existing approaches fail to enable the design of index-free adjacency (IFA), i.e., each vertex preserves the physical positions of its neighbors. However, IFA has been widely recognized as necessary for efficient graph processing and is fundamental in native graph databases (e.g., Neo4j). In this work, we propose a core technique named delayed duplication to resolve the conflict between IFA and obliviousness. To the best of our knowledge, we are the first to address this conflict with both practicality and strict security. Based on the new technique, we utilize elaborate data structures to develop a new EDB named Grove for processing expressive graph queries. The experimental results demonstrate that incorporating IFA makes Grove impressively outperform the state-of-the-art work across multiple graph-processing tasks, such as the well-known neighbor query and $t$-hop query.

Private Information Retrieval (PIR), a set of techniques from the literature on cryptography, enables the retrieval of data from a public database while concealing the intent of those querying it, even when the database itself is untrusted. While the scalability of PIR has improved in recent years, its applicability remains limited due to the assumption that databases cooperate with users. PIR schemes usually require the database or website administrators to perform costly operations beyond servicing requests, which they have little incentive to do. In this paper, we introduce a new direction of PIR research that eliminates requirement of any special cooperation from the database and assumes the presence of a strong adversary that controls not only the database but also any third parties involved in the system. We present Zeal, the first `non-cooperative' PIR scheme that defends against a strong adversary. We also implement Zeal on AWS and evaluate its performance. Zeal has roughly three to four minutes of latency for a database with one million records, improving upon the latency of a naive solution by a factor of 50. We also prove and quantify Zeal's security using a differential privacy guarantee.

Theoretical treatments of leakage-resilient cryptography typically work under the assumption that the leakage learned by the adversary (e.g., about an n-bit secret key) is arbitrary but bounded, in the sense that the leakage is an l-bit string for some threshold l significantly smaller than n. On the other hand, real-world side-channel attacks on physical implementations of cryptographic protocols produce leakage transcripts that are much longer than n. However, unlike the bounded leakage model, these transcripts are inherently noisy. We would like to generically claim that cryptographic schemes resilient to bounded leakage are also resilient to realistic noisy leakages. This boils down to showing that noisy leakages can be simulated using only one bounded leakage query. Prior work (EUROCRYPT 2021 and CRYPTO 2024) made important progress on this problem. Yet, barriers to applicability and interpretability remain, such as the need for large noise levels, the difficulty to estimate the necessary parameters of the leakage distributions, undesirable independence assumptions, and inefficient simulation in certain regimes. In this work, we resolve (or make progress towards resolving) these shortcomings: 1. We show that simple modifications to the simulation strategies in prior work simultaneously allow a cheaper computation of simulation parameters and better parameters than previous results. 2. Leveraging the first item, we obtain a reduction whose amount of extra bounded leakage to simulate correlated signals only increase very mildly. This captures the limited incentive for an adversary to oversample a side-channel signal leading to correlated signal, improving previous results treating these samples as independent. 3. We establish a new ``bounded leakage vs.\ simulation efficiency'' tradeoff, roughly trading $\mathcal{O}(\Delta)$ bits leaked by the bounded leakage query for a $\frac{2^{\Delta}}{\mathrm{poly}(\Delta)}$-factor reduction in simulation complexity. This widens the applicability of our results in the context of computational security, as former simulators were only efficient when simulating from $\mathcal{O}(\log \lambda)$ bits of bounded leakage, with $\lambda$ the security parameter.

The assumed hardness of the Linear Code Equivalence problem (LCE) lies at the core of the security of the LESS signature scheme and other signature schemes with advanced functionalities. The LCE problem asks to determine whether two linear codes are equivalent. This equivalence is represented by a monomial matrix $Q$, i.e. the product of a diagonal matrix $D$ and a permutation matrix $P$. The recovery of $Q=DP$ is known to be reduced to the recovery of the permutation matrix $P$ alone. Exploiting this fact, we construct an algebraic model for LCE involving only the matrix $P$. To this end, we study the action of monomial matrices on linear codes using tools from algebraic geometry, including Plücker coordinates and fields of invariant rational functions. In particular, we analyse the action of diagonal matrices on linear codes, which can be interpreted as diagonal scaling of the coordinates of elements of the Grassmannian. We propose a method to determine algebraically independent generators of the field of rational functions invariant under this action, without relying on Reynolds operators or Gröbner basis computations. Furthermore, given two equivalent codes, we apply our results to explicitly construct, for each invariant function, a polynomial having $P$ as a root. However, the resulting polynomials are not of practical use: their degrees are high for cryptographically relevant parameters, and the number of monomials grows exponentially, making them infeasible to manipulate. Despite this limitation, our results are of theoretical interest, as they constitute the first application of these tools to the cryptanalysis of LCE and provide insight into how algebraic geometry and invariant theory can be employed in Cryptography.

In this paper we study the cryptographic complexity of non-trivial witness-indistinguishable (WI) arguments of knowledge. We establish that: - Assuming that $NP\not\subseteq P/poly$, the existence of a constant-round computational WI argument of knowledge for $NP$ implies that (infinitely-often) auxiliary-input one-way functions exist. - Assuming that $ NP\nsubseteq P^{Sam}/poly$, there is no black-box construction of a constant-round (unbounded-verifier) statistical WI argument of knowledge from one-way permutations. Here, $Sam$ is the collision finder oracle of Haitner, Hoch, Reingold, and Segev [FOCS '07]. Moreover, we identify a natural class of knowledge extractors for which stronger versions of the above implications hold (e.g., even if the protocols have many rounds).

In a previous paper [Shoup 2023], we presented a modular toolkit for analyzing threshold Schnorr signature schemes, built around "enhanced attack modes" in the non-distributed setting. In this note, we revisit the random oracle analysis of the combination of batch randomness extraction with re-randomized presignatures. We make the simulation argument fully explicit --- in particular, giving a careful analysis of what is leaked through the presignatures, the programmed hash values, and the signature values --- and fill in a gap in the treatment of batch re-randomization. We also give a simpler path to tight security bounds in the combined random oracle plus generic group model (ROM+GGM): rather than reducing to somewhat convoluted (if concrete) assumptions about the hash function within the GGM, we reduce in the ROM to an attack on the Schnorr interactive identification scheme, and then observe that the identification scheme is easily seen to be hard in the GGM.

Hax is a verification pipeline that translates a subset of Rust into F*, enabling machine-checked proofs of panic freedom and functional correctness for cryptographic implementations being developed in partnership with Google and tested in Signal's post-quantum protocol. We study whether hax's translation preserves the security properties it claims to verify. Through a structural analysis of its 35-phase transformation engine, F* proof libraries, and specification API, we identify three classes of semantic gap between the Rust source and the F* verification target: translation infidelity, where pipeline transformations distort security-relevant semantics; unverifiable trust boundaries, where operations are axiomatized without postconditions; and specification gaming, where escape hatches inject unproven facts into the verification context. We demonstrate each class through five proof-of-concept exploits against ML-DSA (FIPS 204), ML-KEM (FIPS 203), Ed25519 (FIPS 186-5), and ChaCha20 (RFC 8439). Every exploit meets a strict criterion: the Rust code compiles, passes functional tests, and extracts to F* without warnings, while harboring a security gap invisible to testing. We distinguish three gradations: facade gaps where the F* model actively diverges from Rust semantics, a conditional gap dependent on the compilation mode, and a scope gap where the model is faithful but cannot cover a critical property. We call the resulting phenomenon a verification facade: verification that is performed but covers less than it appears to cover.

Fully Homomorphic Encryption (FHE) is a groundbreaking technology that allows for arbitrary computations to be performed on encrypted data. State-of-the-art schemes such as Brakerski Gentry Vaikuntanathan (BGV) are based on the Learning with Errors over rings (RLWE) assumption, and each ciphertext has an associated error that grows with each homomorphic operation. For correctness, the error needs to stay below a certain threshold, requiring a trade-off between security and error margin for computations in the parameters. Choosing the parameters accordingly, for example, the polynomial degree or the ciphertext modulus, is challenging and requires expert knowledge specific to each scheme. In this work, we improve the parameter generation process across all steps of its process. We provide a comprehensive analysis for BGV in the Double Chinese Remainder Theorem (DCRT) representation providing more accurate and better bounds than previous work on the DCRT, and empirically derive a closed formula linking the security level, the polynomial degree, and the ciphertext modulus. Additionally, we introduce new circuit models and combine our theoretical work in an easy-to-use parameter generator for researchers and practitioners interested in using BGV for secure computation. Our formula results in better security estimates than previous closed formulas, while our DCRT analysis results in reduced prime sizes of up to 42% compared to previous work.

In recent years, the research community has made great progress in improving techniques for privacy-preserving computation, such as fully homomorphic encryption (FHE). Despite the progress, there remain open challenges, mainly in performance and usability, to further advance the adoption of these technologies. This work provides multiple contributions that improve the current state-of-the-art in both areas. More specifically, we significantly simplify the multi-value bootstrapping by Carpov, Izabachène, and Mollimard [CIM19] for Boolean-based FHE schemes such as FHEW or TFHE, making the concept usable in practice. Based on our simplifications, we implement an easy-to-use interface for multi-value bootstrapping in the open-source library FHE-Deck [fhe23], derive new parameter sets for multi-bit encryptions with state-of-the-art security, and build a toolset that translates high-level code to multi-bit operations on encrypted data using circuit synthesis. We propose and integrate the first non-trivial FHE-specific optimizations for privacy-preserving circuit synthesis: look-up table (LUT) grouping and adder substitution. Using LUT grouping, we reduce the number of bootstrapping operations by almost 40% on average, while for adder substitution, we reduce the number of required bootstrappings by up to 85% for certain use cases. Overall, the execution time is up to 4.2x faster with all optimizations enabled compared to previous state-of-the-art circuit synthesis.

Fully homomorphic encryption is a promising approach when computing on encrypted data, especially when sensitive data is involved. For BFV, BGV, and CKKS, three state-of-the-art encryption schemes, the most costly homomorphic primitive is the so-called key switching. While a decent amount of research has been devoted to optimizing other aspects of these schemes, key switching has gone largely untouched. One exception has been a recent work [26] introducing a new double-decomposition technique. Their contributions are an important addition to the current state-of-the-art with one flaw: They take a limited perspective on key switching parameters and their asymptotic complexity which leads to incorrect conclusions about how effective their approach really is. In our work, we deep dive into key switching and correct, enhance, and improve the current state-of-the-art. We provide a new perspective on key switching parameters for the single- and double-decomposition techniques, respectively, and show that the former outperforms the latter in most scenarios. Additionally, we revisit an idea by Gentry, Halevi, and Smart [17] and reduce the number of multiplications.

Verifiable Random Functions (VRFs) play a fundamental role in modern blockchain designs because of their applications in leader election protocols. In such contexts, however, the original definition by Micali, Rabin and Vadhan (FOCS 99), falls short at guaranteeing fairness when keys are sampled maliciously. The elegant notion of unbiasable VRF, recently proposed by Giunta and Stewart (Eurocrypt 24), addresses these concerns while remaining simple to state and easy to realize, at least in the random oracle model. Achieving unbiasability in the standard model is a different story, though: all known constructions rely on compilers that invariably reduce the efficiency of the VRF from which one starts. In this paper, we look at the unbiasability of existing VRFs in the standard model. Our findings are mostly negative; we show that, essentially, all known constructions are not natively unbiasable. We do so by showing classes of attacks that (almost) completely cover the set of existing VRF constructions. On the positive side, we show that some concrete schemes (and notably the well-known Dodis-Yampolskiy VRF) can be modified to achieve meaningful notions of unbiasability, while retaining their original efficiency.

KEM-to-PAKE compilers have been recently proposed to leverage post-quantum KEM standardization efforts. These typically follow the Encrypted Key Exchange (EKE) paradigm, where the KEM public key is encrypted under a password. While KEM implementations generally aim to execute all secret-dependent computations in constant time, such guarantees do not always extend to computations that depend only on the public key, as public keys are generally assumed to be public. A notable example is ML-KEM, where public keys include a short seed from which a large matrix is expanded prior to algebraic computations. This expansion procedure relies on rejection sampling which is, typically, implemented as a variable-time algorithm. However, compilers that follow the EKE paradigm must treat the public key as secret, since knowledge of the public key hidden in a ciphertext enables an offline dictionary attack on the password; therefore, instantiating these compilers with off-the-shelf implementations of ML-KEM or encrypting the public key under a password using variable-time methods (e.g., cycle walking or rejection sampling, as proposed in related PAKE literature) can be problematic. In this paper we show two approaches which yield ML-KEM-based PAKEs resilient to timing attacks. First, we explore constant-time alternatives to ML-KEM rejection sampling, but as one might expect, such methods impose a performance penalty on ML-KEM. Our second approach introduces a new ML-KEM-to-PAKE compiler that mitigates this issue by design: our proposal transmits the seed in the clear, decoupling password-dependent computations from the seed expansion step. This means that off-the-shelf implementations of ML-KEM can be used. Our new protocol Tempo builds on an idea from CHIC (Asiacrypt'24), which considered splitting the KEM public key, and extends the NoIC protocol and proof (ePrint:2025/231) to show protocol simulation in the UC framework, assuming ML-KEM security under adversarially chosen seeds. We justify this assumption via a new hardness assumption, which we call Oracle-MLWE, and show that it is asymptotically equivalent to the MLWE problem in the Random Oracle Model.

We revisit the quantum security (in the QROM) of digital signature schemes that follow the Fiat-Shamir-with-aborts (FSwA) or the probabilistic hash-and-sign with retry/abort (HSwA) design paradigm. Important examples of such signature schemes are Dilithium, SeaSign, Falcon+ and UOV. In particular, we are interested in the UF-CMA-to-UF-NMA reduction for such schemes. We observe that previous such reductions have a reduction loss that is larger than what one would hope for, or require a more stringent notion of zero-knowledge than one would hope for. We resolve this matter here by means of a novel UF-CMA-to-UF-NMA reduction that applies to FSwA and HSwA signature schemes simultaneously, and that offers an improved reduction loss (without making the zero-knowledge assumption more stringent).

We present a new method for merging short computationally sound proofs (SNARGs). Intuitively, this means going from short proofs of two statements to a short proof of a statement that is a ``logical consequence'' of the two. Our work is the first to handle an unbounded polynomial number of recursive merges with arbitrary topology. Unlike prior works, the running time of our security reduction grows only with the depth of the merging process, and not with the associated ``tree size", which could be exponentially larger. Our method is only applicable to so-called ``trapdoor languages'', where the validity of a statement can be decided in polynomial time given a trapdoor. Importantly, this trapdoor needs not be known for generating or verifying proofs, and is only used in the security reduction. We present constructions from sub-exponential iO and from LWE, where the former yields fully compact proofs, while in the latter the proof size scales with the depth of the merging process. We show the usefulness of our method by presenting the first CCA1-secure multi-hop fully homomorphic encryption, from either iO or LWE. We also present the first adaptive multi-hop aggregate signature scheme from LWE.

Threshold signatures have recently seen a renewed interest due to applications in cryptocurrency while NIST has released a call for multi-party threshold schemes, with a deadline for submission expected for the first half of 2025. So far, all lattice-based threshold signatures requiring less than two-rounds are based on heavy tools such as (fully) homomorphic encryption (FHE) and homomorphic trapdoor commitments (HTDC). This is not unexpected considering that most efficient two-round signatures from classical assumptions either rely on idealized model such as algebraic group models or on one-more type assumptions, none of which we have a nice analogue in the lattice world. In this work, we construct the first efficient two-round lattice-based threshold signature without relying on FHE or HTDC. It has an offline-online feature where the first round can be preprocessed without knowing message or the signer sets, effectively making the signing phase non-interactive. The signature size is small and shows great scalability. For example, even for a threshold as large as 1024 signers, we achieve a signature size roughly 11 KB. At the heart of our construction is a new lattice-based assumption called the algebraic one-more learning with errors (AOMMLWE) assumption. We believe this to be a strong inclusion to our lattice toolkits with an independent interest. We establish the selective security of AOMMLWE based on the standard MLWE and MSIS assumptions, and provide an in depth analysis of its adaptive security, which our threshold signature is based on.

Modern processors are largely fixed at the time of fabrication, rendering post-silicon security updates infeasible. This lack of flexibility is especially problematic for speculative execution attacks, which exploit microarchitectural optimizations to leak sensitive information through transient execution. However, existing defenses are typically hardwired, narrowly scoped, and non-adaptive. Once deployed, these defenses lack the flexibility to respond to new attack variants, creating a critical security gap. This paper presents SPLASH, a novel and adaptive framework for comprehensively mitigating speculative execution vulnerabilities across processor components. SPLASH introduces two primary contributions: (i) we introduce Speculative Information Flow Tracking (SIFT), which enables fine-grained tracking of speculative data propagation throughout the microarchitecture; (ii) the reconfigurable speculative table provides, for the first time, enforceable and fully configurable control over speculative behavior across the processor pipeline. SPLASH is runtime-configurable, allowing dynamic security policy adjustments post-fabrication, such as tuning the speculative window size or selectively protecting specific microarchitectural structures, without requiring hardware redesign. We implement SPLASH on both the small and medium BOOM processors and evaluate its effectiveness in mitigating speculative leakage vulnerabilities. SPLASH successfully mitigates all types of speculative execution attacks. In terms of computation overhead, SPLASH incurs only 0.05% overhead on small BOOM and 1.23% on medium BOOM on average compared with the baseline. Compared to the best performing state-of-the-art defenses, SPLASH reduces overhead by 129.2X and 1.2X, respectively, with negligible hardware cost.

Decentralized Finance (DeFi) lending protocols implement programmable credit markets without intermediaries. This paper systematizes the DeFi lending ecosystem, spanning collateralized lending (including over- and under- collateralized designs, and zero-liquidation loans), uncollateralized primitives (e.g., flashloans), and yield aggregation protocols which allocate capital across underlying lending platforms. Beyond a taxonomy of mechanisms and comparing protocols, we provide empirical on-chain measurements of lending activity and user behavior, using Compound V2 and AAVE V2 as case studies, and connect empirical observations to protocol design choices (e.g., interest-rate models and liquidation incentives). We then characterize vulnerabilities that arise due to notable designs, focusing on interest-rate setting mechanisms and time-measurement approaches. Finally, we outline open questions at the intersection of mechanism design, empirical measurement and security for future research.

The Fiat-Shamir transform [11] is a fundamental technique for converting sound public-coin interactive protocols into sound non-interactive protocols. While the theoretical transformation is conceptually simple, implementation-level deviations—often motivated by performance optimisations—can introduce catastrophic security flaws. In this work, we present the Last Challenge Attack (LCA), a vulnerability arising from such a deviation in a real-world KZG-based SNARK verifier implementation. The vulnerability stems from an incorrect computation of the final KZG [17] protocol challenge, which is a batching challenge derived independently of the evaluation proofs. This flaw potentially affects any KZG implementation of batched proofs for multiple evaluation points. We demonstrate that a malicious prover can exploit this deviation to forge proofs of false statements. We provide a proof-of-concept implementation demonstrating the forgery of a proof for an arbitrary public input. This vulnerability was discovered during a security audit, responsibly disclosed, and fixed.

Web3 applications, such as on-chain gaming, require unbiased and publicly verifiable randomness that can be obtained quickly and cost-effectively whenever needed. Existing services, such as those based on Verifiable Random Functions (VRF), incur network delays and high fees due to their highly interactive nature. FlexiRand [CCS 2023] addressed these problems by hiding the output of the VRF and using that as a seed to derive many randomnesses locally. These randomnesses are instantly available for usage. However, these randomnesses can not be verified independently (or instantly) without disclosing the seed, leaving scope for malicious actors to cheat. To solve this problem, we introduce a new notion, called instantly-verifiable VRF (iVRF), which enables the generation of many randomnesses from one VRF output seed, such that each of them is verifiable independently - this enables the $first$ solution to $cost-effectively$ generate randomnesses, such that they are $instantly$ $available$ and also $independently/instantly$ $verifiable$. To instantiate we propose a generic construction called InstaRand - it combines any (possibly distributed) VRF at the server's end with another VRF at the client's end to construct an iVRF. Our specific instantiation uses the BLS-based GLOW-DVRF [Euro S&P 2021] at the server's end and the DDH-based VRF of Goldberg et al. [RFC 2023] at the client's end. We use the universal composability framework to analyze the security. Moreover, due to its generality, InstaRand can be instantiated with any post-quantum secure VRF to yield a post-quantum secure iVRF. Our experiments demonstrate that our instantiation of InstaRand is $highly$ $practical$. The client incurs a $one-time$ cost to generate the seed (server's VRF output) by querying the GLOW-dVRF servers once. Once the seed is set up, the client locally generates the pseudorandom value on demand in $0.18~ms$, avoiding the client-server round-trip delay. Each value can be independently verified in $0.22~ms$. This yields a $400\times$ improvement in terms of output generation and $20\times$ improvement in verification cost over existing solutions.

Payment channel networks (PCNs) are a leading method to deal with the scalability limitations of blockchain networks. PCNs allow users to execute transactions without committing them to the blockchain by relying on predefined payment channels. Transactions between pairs of users without a connecting channel are also supported through a path of multiple channels. Serving such transactions involves fees paid to intermediate users. In this paper, we uncover the potential existence of the Braess paradox in payment networks: Sometimes, establishing a new payment channel can increase the fees paid for serving some fixed transactions. We study conditions for the paradox to appear under two different models of fees: Liquidity-based fees as a function of the transaction value jointly with the channel liquidity values and proportional fees which are based only on the transaction value. We also provide indications for the appearance of the paradox based on real data from Lightning, a popular payment channel network of Bitcoin. Last, we discuss methods to mitigate the paradox upon establishing a new payment channel.

We consider the worst-case hardness of the gap version of the classic time-bounded Kolmogorov complexity problem—$Gap_pMK^tP[s_1,s_2]$—where the goal is to determine whether for a given string x, $K^t(x) ≤s_1(n)$ or $K^{p(t)}(x) > s_2(n)$, where $K^t(x)$ denotes the t-bounded Kolmogorov complexity of x. As shown by Hirahara (STOC’18), if $Gap_pMK^tP[s_1,s_2] \notin prBPP$ for every polynomial p, then (under appropriate derandomization assumption) $Gap_pMK^tP$ is errorless average-case hard with respect to BPP heuristics. The notion of errorless average-case hardness, however, is seemingly insufficient for cryptographic applications where one needs to consider average-case hardness against attacks that simply may err with some probability (i.e., two-sided error hardness). In this work, we present several new consequences of the assumption that $Gap_pMK^tP[s_1,s_2]\notin P/poly$ for all polynomials p, for appropriate choices of $s_1$,$s_2$, and under appropriate (worst-case) derandomization assumptions. In particular, we show that this assumption implies: - The existence of an (inefficient-prover) zero-knowledge proof system for NP with a non-uniform simulator w.r.t. adversaries with a-priori bounded-length auxiliary-input. - The existence of a hard disjoint NP pair, defined as a promise problem $(Y,N)$ where both $Y,N\in NP$; this provides a barrier towards showing that $Gap_pMK^tP$ is NP-complete. The above results are proven via first showing that the above assumption implies the existence of a so-called conditional PRG—roughly speaking, a cryptographic PRG where indistinguishability only needs to hold for some (potentially not efficiently sampleable) distribution over the seed to the PRG. (In fact, this notion of a PRG also almost directly implies average-case hardness of $Gap_pMK^tP$, and as such, this provides a modular explanation to Hirahara’s results.) Finally, we show that for the results on conditional PRGs and Zero-knowledge Proofs, unconditional results can be obtained (that is, without making any derandomization assumptions), if considering an appropriate version of $Gap_pMK^tP$ concerning randomized $K^t$.

In recent years, the shuffle model has emerged as a prevalent paradigm in privacy-preserving data analysis, centered on the principle of \textit{privacy amplification via shuffling}: an individual user's report is obscured by the ``background noise'' of other users' messages, a phenomenon intuitively known as the \textit{privacy blanket}. This paper initiates a foundational and systematic study of this mechanism from an information-theoretic perspective. We investigate the following optimal noise-design problem: given that a target user's message $Y_1$ follows a distribution $P$, what is the optimal blanket noise distribution $Q$ that maximizes privacy? Specifically, when $Y_1 \sim P$ and the remaining messages $Y_2, \dots, Y_n \stackrel{\text{i.i.d.}}{\sim} Q$ are shuffled to produce an output $\boldsymbol{Z} = (Y_{\sigma(i)})_{i=1}^n$, we seek the $Q$ that affords the strongest protection for $Y_1$ under various metrics, including mutual information $I(Y_1; \mathbf{Z})$, total-variation-information $I_{\mathrm{TV}}(Y_1; \mathbf{Z})$, message recovery advantage, and expected posterior variance. Our analysis reveals a series of non-intuitive results that challenge the conventional heuristic of setting $Q=P$. First, we prove that the optimal noise distribution $Q$ generally \textit{deviates} from the target distribution $P$. For binary alphabets, we show that the (near-)uniform distribution is optimal in a strong sense. For general finite alphabets, we derive an explicit analytical form $Q \propto \sqrt{P(1-P)}$ that achieves asymptotic optimality for mutual information. Furthermore, we demonstrate that our analytical framework transcends the shuffle model, yielding new security insights into broader cryptographic primitives such as the \textit{ideal cipher model} and \textit{honey encryption}. Finally, we extend our results to the shuffle-DP paradigm, where messages $Y_i = \mathcal{R}(X_i)$ are outputs of $\varepsilon_0$-locally differentially private mechanisms. We establish a new, tight information-theoretic upper bound $I(X_1; \mathbf{Z} \mid (X_i)_{i=2}^n) \le \frac{(e^{\varepsilon_0/2}-1)^2}{2n} + \mathcal{O}(n^{-3/2})$. This result provides a sharp characterization that matches the optimal privacy-amplification parameters known in the literature, while offering a novel interpretation of the shuffling gain.

Private Information Retrieval (PIR) is a crucial component in many privacy-preserving systems, with Offline/Online PIR attracting significant attention. Recent works have focused on eliminating offline communication overhead. However, existing constructions incur high online communication costs as a trade-off. To address this, we propose VIA, a single-server PIR scheme that eliminates offline communication while achieving $O{_\lambda}(\log N)$ online communication complexity. Experimental evaluations demonstrate that for a 32 GB database, VIA requires only 690 KB of online communication---a $3.7\times$ reduction compared to state-of-the-art schemes without offline communication---while attaining a throughput of 3.11 GB/s. Furthermore, we introduce VIA-C, a variant of VIA that allows offline communication. Compared to previous communication-efficient schemes, VIA-C achieves a $24.5\times$ reduction in online communication, requiring only 2.1 KB for a 32 GB database (with 14.8 MB offline communication). Moreover, VIA-C can naturally extend to VIA-B that supports batch queries. Compared to previous communication-efficient batch PIR schemes, VIA-B achieves a $3.5\times$ reduction in query size and a $127\times$ reduction in response size for a 1 GB database of 1-byte records. The designs of our schemes rely on a novel DMux-CMux structure and LWE-to-RLWE conversion techniques.

We introduce metric-aware code-based cryptography by moving beyond the Hamming metric to the Niederreiter-Rosenbloom-Tsfasman (NRT) and sum-rank metrics and by exploiting their linear isometry groups via Bruhat-Chevalley-Renner decompositions. On the structural side, we give isometry-invariant distance tests: a parity-check prefix-rank test for single-chain NRT, its multi-prefix extension for block-NRT, and a block rank-profile test for sum-rank. We also analyze orbit structure under the relevant isometry subgroups and prove NP-hardness of a block-NRT canonicalization problem via a reduction from Exact-3-Cover, pinning down the difficulty of public ``structure recovery.'' On the design side, we propose an inner-outer Niederreiter cryptosystem that couples a short rowwise single-chain NRT inner code with $k_V$ outer binary Goppa codes across columns. For the resulting matrix code we prove a distance guarantee $d_{\mathrm{NRT}}\!\ge\!\delta_V\cdot \min_t d^{(t)}$ and give a simple two-stage decoder (outer Goppa per coordinate, then inner per column). Public keys are dense, obfuscated parity-checks $M=S H_{\mathrm{sys}} (PD)$ drawn from a metric-preserving subgroup, preserving decodability while hiding structure. Finally, we reduce NRT and sum-rank syndrome decoding to classical Hamming/Rank decoding, yielding one-wayness of the public syndrome map at standard regimes.

ECDSA is a widely deployed digital signature scheme used in securing communications and distributed systems but its structure prevents efficient batch verification. This limitation is impactful in high-throughput applications such as blockchain transaction validation. In this paper, we consider two modified versions of standard ECDSA, namely ECDSA_rec and ECDSA_ast, which embed additional bits in the signature, that enable efficient batch verification. We contribute the first publicly available C implementations of ECDSA_ast on secp256k1 and of both ECDSA_ast and ECDSA_rec on secp256r1, built on top of Bitcoin and OpenSSL codebases, respectively. We evaluate both variants on the two curves and demonstrate batch verification using the two established randomization techniques, NMVR-rand and HSS-rand. The results of our software implementation indicate that batch verification of modified ECDSA signatures usingHSS-rand generally outperforms individual verification of standard ECDSA. Furthermore, the HSS-rand technique provides more efficient batch verification than NMVR-rand in the majority of cases. For a batch of 32 ECDSA_ast (ECDSA_rec resp.) signatures on secp256k1, HSS-rand batch verification improves individual verification by approximately 30.9% (17.2% for ECDSA_rec) and outperforms NMVR_rand batch verification, which achieves improvements of 10.6% (9.8% for ECDSA_rec). The improvements achieved by HSS-rand on secp256r1 are even more pronounced, reaching 53.9% for ECDSA_ast and 40.5% for ECDSA_rec over individual verification of standard ECDSA signatures. In comparison, HSS-rand yields improvements of 27.6% for ECDSA_ast and 22.9% for ECDSA_rec over NMVR-rand, respectively.

Succinct non-interactive arguments (SNARGs) for P are a powerful tool for verifiably outsourcing a computation to a single entity. In this work, we study verifiable outsourcing in a distributed divide-and-conquer setting: a party tasked with solving a large computational problem divides it into smaller subproblems, delegates each subproblem to a different party, and then combines their solutions. Moreover, each party may recursively apply the same strategy, further delegating its computation. Verifying such recursive outsourcing requires SNARGs that are \emph{mergeable}, so that proofs for subproblems can be efficiently combined into a single proof for the original problem. While mergeable proofs have been known for nearly two decades (either based on heuristic assumptions such at SNARKs or, more recently, on standard hardness assumptions), in all existing approaches security degrades exponentially with the number of recursive merges. In this work, we overcome this barrier. Assuming the Learning with Errors (LWE) assumption, we construct a mergeable SNARG for P that supports an unbounded polynomial number of recursive merges. The proof size grows only linearly with the depth of the merge tree, and is independent of its total size.

The advancement of quantum computing poses a serious threat to widely-used public-key cryptographic systems, leaving organizations with the challenge of identifying quantum-vulnerable (QV) executables within their systems and migrating to post-quantum cryptography (PQC). The prior work QED achieves high detection precision through angr-based static call graph analysis (P3), but its processing time of a few to over ten minutes per dataset and RAM consumption of up to 5 GB pose practical limitations on exhaustive screening in largescale environments. In this paper, we propose QED-Lite, a lightweight approximation tool that lightens the analysis stages that incur high computational overhead relative to their detection precision, replacing them with version-based PQC support determination of cryptographic libraries. QED-Lite introduces a newly built PQC risk classification database for 11 major cryptographic libraries and is implemented with a single dependency on pyelftools. Experimental results on the Network dataset show that QED-Lite achieves an execution time up to 855× faster (0.84 seconds) and reduces memory usage by 228× (22.9 MB) compared to QED, while maintaining a TPR of 100%. QED-Lite delivers practical value relative to its cost as a first-pass screening tool that is operationally viable in large-scale organizational environments.

Hash-based signatures are a strong candidate for post-quantum scenarios requiring authentication and integrity. Their security relies only on (well-studied) properties of hash functions, so they may be thought as being more robust than other schemes that (today) resist quantum attacks, like those based on lattices, coding or isogenies. Recent works also study hash-based signature schemes with additional properties, such as group, ring, threshold, or aggregate signature schemes. In this work, we do the same for the important case of blind signatures. We describe a secure (in the programmable random oracle model) modification of Fischlin's generic construction of blind signatures that can be instantiated with different hash-based protocols. As a result, we obtain the first blind signature schemes whose security relies only on the collision resistance of hash functions. Finally, as a proof of concept, we have implemented one (highly non-optimized) of the possible instantiations.

In this note, we review the formulation of SNOVA in three different languages: the ring-equation form, the whipping form, and the tensor form. Based on this, we propose a reformulation of SNOVA and discuss the security analysis of the resulting reformulated scheme. As a conclusion, we find that this new framework allows for greater flexibility in parameter selection and enables us to obtain parameter sets that remain competitive. In particular, as shown in the appendix, parameter sets over odd characteristic $\mathbb{F}_{q}$ lead to smaller key sizes and may offer improved resistance against certain attacks. This makes parameter sets over odd characteristic $\mathbb{F}_{q}$ especially interesting from a practical perspective. We propose a number of parameter sets that have certificate sizes below one kilobyte.

In incentivized outsourced computation,an outsourcer hands a computation to multiple contractors, and in return expects the same computation output from each. The state-of-the-art proposals succeed in incentivizing all contractors for honest computation by setting this behavior as the unique Nash equilibrium of the system. Yet, they are either limited to the two-contractor case or the multi-contractor case without security proof against fully collaborating coalitions. Further, employing a smart contract for managing submissions from the contractors has been a non-trivial task due to the copy attack. In this work, we target this issue and propose a smart contract based multi-contractor incentivized outsourced computation protocol Delegate, which is provably secure against coalitions. We further mitigate the copy attack by a universally composable response submission protocol based on commitments, in contrast to previous solutions which only disincentivize it.

The study of coin-tossing protocols lies at the intersection of cryptography and game theory, where parties with potentially conflicting interests aim to jointly generate an unbiased random bit. Classical cryptographic results establish that strong fairness is achievable with an honest majority in the statistical setting, but impossible with a dishonest majority. In parallel, game-theoretic approaches [TCC 2018, Eurocrypt 2022 \& CRYPTO 2024] have demonstrated that weaker equilibrium-based fairness guarantees can sometimes circumvent cryptographic lower bounds, raising the question of whether such techniques can overcome impossibility in the statistical regime. In this work, we answer this question negatively. - We show that for $n$ parties and $t \geq n/2$ corruptions, there exists no statistically secure, game-theoretic coin-tossing protocol, even assuming broadcast and bounded round complexity—with the sole exception of the case $n=4$ where all but one party share the same preference. This complements known feasibility results for $t < n/2$, thereby completing the statistical feasibility landscape. - We further consider the setting without broadcast. Here we prove that no computationally secure game-theoretic coin-tossing protocol exists for $t \geq n/3$ and polynomial-round complexity, except for the corner case $n=6$ where all but one party share the same preference. To establish these results, we refine existing frameworks for game-theoretic fairness to capture both broadcast and point-to-point communication models. Together, our results establish the boundaries of game-theoretic fairness in multi-party coin tossing: while it extends feasibility in the computational setting, it offers no advantage in the statistical setting once an honest majority is lost.

We present $\mathsf{HyperVerITAS}$, a new zero-knowledge proof (ZKP) system for image provenance that enables scalable, efficient, and privacy-preserving verification of image transformations. $\mathsf{HyperVerITAS}$ builds upon the same minimal trust model as $\mathsf{VerITAS}$ (IEEE S&P '25), requiring trust only in the image source device, while treating the editing software as untrusted. Unlike $\mathsf{VerITAS}$, which relies on FFT-intensive SNARKs and suffers from high memory overhead (up to 120 GB), $\mathsf{HyperVerITAS}$ leverages multilinear polynomial encodings over the Boolean hypercube to dramatically reduce both proving time and memory usage. Our design cleanly separates signature verification from image transformation, supports modular integration of multiple polynomial commitment schemes (including post-quantum constructions) and naturally extends to a wide range of affine image transformations. We implement $\mathsf{HyperVerITAS}$ with two distinct commitment schemes (Brakedown and multilinear KZG) and evaluate it on full-system pipelines involving cropping and grayscaling. On commodity hardware (Apple M3, 36 GB RAM), $\mathsf{HyperVerITAS}$ generates proofs for 33 MP images using only 27 GB of RAM and 6.6 minutes of proving time, whereas $\mathsf{VerITAS}$ fails to scale beyond 4 MP. These results establish $\mathsf{HyperVerITAS}$ as a practical and scalable ZKP system for secure and efficient image provenance.

Secure multiparty computation (MPC) enables mutually distrustful parties to jointly compute over private data without revealing their inputs. While protocols in both synchronous and asynchronous settings have achieved impressive efficiency in either communication or round complexity, combining the two has remained challenging. Only recently, Abraham, Asharov, Patil, and Patra (Eurocrypt’23, Eurocrypt’24) achieved protocols that combine low communication complexity ($O((Cn + Dn^2 + n^4)\log n)$) with fast execution ($O(D)$ rounds) in both synchronous and asynchronous models, for circuits of size $C$ and depth $D$, in the perfect setting with optimal resilience. However, both protocols crucially assume advanced knowledge of the network type and are fragile under mismatched or varying network conditions. The fragility of protocols under mismatched network assumptions highlights the need for network-agnostic MPC, where security and correctness are preserved in both synchronous and asynchronous settings. Yet, all known perfect network-agnostic protocols incur $\Omega(D+n)$ rounds and communication complexity in the order of $n^3$ or higher, far worse than their network-specific counterparts. In this work, we present the first network-agnostic MPC protocol in the perfect security setting, achieving expected round complexity $O(D)$. Our protocol has expected communication complexity $O((Cn^2 + Dn^2 + n^4)\log n)$, improving on the state of the art by a factor of $n^3$ for small circuits and $n^2$ for large circuits in communication, in addition to an additive $O(n)$ improvement in round complexity. Our design departs from the structure of prior network-agnostic protocols and introduces several new technical ideas that enable both round and communication efficiency.

We design a fully homomorphic encryption for moduli of the form $b^k$ with small $b$. Our construction asymptotically improves upon Kim [TCHES'25]: for fixed $b$, the multiplication latency decreases from $O(k \log k)$ to $O(\log k)$ while preserving amortized latency. Our experiments show that our $64$-bit multiplication achieves $\approx 6 \times$ lower latency than Kim and slightly lower latency than TFHE-rs, while improving amortized latency by three orders of magnitude over TFHE-rs. The performance gap widens for larger precision. For instance, our $512$-bit multiplication achieves $\approx 49 \times$ lower latency and four orders of magnitude lower amortized latency than TFHE-rs. We also outperform Boneh and Kim [Crypto'25] with $4.70 \times$ lower latency and $75.3 \times$ lower amortized latency for $256$-bit multiplication.

The Brakerski-Gentry-Vaikuntanathan (BGV) scheme is one of the most significant fully homomorphic encryption (FHE) schemes. It belongs to a class of FHE schemes whose security is based on the presumed intractability of the Learning with Errors (LWE) problem and its ring variant (RLWE). Such schemes deal with a quantity, called noise, which increases each time a homomorphic operation is performed. Specifically, in order for the scheme to work properly, it is essential that the noise remains below a certain threshold throughout the process. For BGV, this threshold strictly depends on the ciphertext modulus, which is one of the initial parameters whose selection heavily affects both the efficiency and security of the scheme. For an optimal parameter choice, it is crucial to accurately estimate the noise growth, particularly that arising from multiplication, which is the most complex operation. In this work, we propose a novel average-case approach that precisely models noise evolution and guides the selection of initial parameters, improving efficiency while ensuring security. The key innovation of our method lies in accounting for the dependencies among ciphertext errors generated with the same key, and in providing general guidelines for accurate parameter selection that are library-independent. Our parameter selection methodology leads to a significant improvement over the parameter choices currently adopted in major FHE libraries.

The BBS+ signature scheme is a widely used foundation for anonymous credential systems. It is favored for its support of selective disclosure and its efficiency in proving credential possession. However, in traditional settings, credentials are typically issued by a single authority, creating a single point of failure and potential security risk. This limitation can be mitigated by adopting a distributed variant, known as the threshold BBS+ scheme. In this work, we present \textit{Robot}, the first two-round threshold BBS+ signature scheme. Robot is round-minimal and achieves robustness, ensuring that every signing execution successfully completes as long as there exist $t+1$ parties behaving honestly. To achieve this, we employ a threshold verifiable random function (TVRF) to robustly generate the public nonces within a single round. Specifically, we utilize an efficient DDH-based TVRF construction, which not only provides our scheme with a round advantage but also enhances its overall performance. Then, by carefully invoking the threshold Castagnos-Laguillaumie and threshold ElGamal homomorphic encryptions, we complete all remaining non-linear operations within the second round. Asymptotically, Robot achieves a constant per-party upload communication and linear computation overhead with respect to the number of signers. Compared with the four-round robust scheme of Wong et al. (NDSS'24, WMC24), which has the same asymptotic complexity, Robot achieves a smaller constant communication cost (2.02 KB vs. 3.23 KB) and nearly halves the runtime. Compared with the three-round robust scheme of Tang and Xue (S\&P'25, TX25), which has linear communication overhead, Robot exhibits better communication and computational efficiency when the number of signers is five or more.

Recent work by Houben (Asiacrypt'25) introduced a new formulation for class group actions on supersingular elliptic curves oriented by an imaginary quadratic order for an arbitrarily large discriminant. The algorithm is not only constant-time but also fully deterministic, dummy-free, and branch-free. As a result, it gives the fastest isogeny-based non-interactive key exchange (NIKE) in theory, referred to as OSIDH-LD in this paper. However, the current proof-of-concept SageMath implementation remains substantially slower than mainstream post-quantum key-exchange candidates. In this paper, we develop an efficient implementation of OSIDH-LD with several approaches. First, we provide algorithmic-level optimizations: (i) we develop the ``tail pruning'' approach such that key agreement avoids redundant orientation updates. This optimization maintains the fully deterministic and dummy-free feature of OSIDH-LD; (ii) we adapt a faster codomain isomorphism identification adapted from the technique used in the SQIsign implementations; and (iii) we present effective isogeny-computation strategies tailored to the cost profile of OSIDH-LD. Second, we adapt the parallelism technique. We apply the fork-join parallel execution model to optimize the class group action performance, and achieve near-perfect parallelism in key generation, as well as improved performance in key agreement. We provide two kinds of implementations to show the impacts of our improvements. The first one is in C with assembly language for field arithmetic, which verifies the correctness of our optimization techniques targeting OSIDH-LD. The experimental results show that our techniques lead to an overall $1.56\times$ and $1.87\times$ acceleration for key generation and key agreement, respectively. On an Intel Core i7 CPU, the resulting costs are 12.8~Gcycs (KeyGen) and 10.57~Gcycs (KeyAgree) at a conjectured CSIDH-4096 security strength. Second, we provide parallel implementations that exploit multi-threading and AVX-512 vector extensions, respectively, by batching independent subroutines in the class group action. In particular, the AVX-512 vectorized implementation is $4.97\times$ faster than the improved C+assembly implementation in key generation, which is close to the theoretical optimum.

Sparse Learning With Errors (sLWE), introduced at CRYPTO 2024 by Jain et al., is a recent hardness assumption aimed at improving the efficiency–security trade-off of lattice-based cryptography in the post-quantum setting. In their paper, the authors posed the open problem of understanding the security of sparse instances with small secrets. Motivated by this question, we study a bounded variant of sLWE in which both the secret and error vectors are restricted to the interval $\{-B,\ldots, B\}$. We develop a combinatorial cryptanalytic framework based on subsystem extraction combined with a meet-in-the-middle strategy, enabling recovery of bounded secret vectors. Our analysis provides a detailed complexity evaluation across different sparsity and modulus regimes and yields concrete security estimates for the bounded setting. Our work does not claim any attack on the proposal of Jain et al.; instead, it provides a concrete analysis of sparse LWE with bounded secrets and errors, together with explicit complexity bounds showing reduced security margins in this setting. Our results indicate that security levels comparable to dimension-1024 LWE for the proposed parameter sets do not necessarily carry over to bounded sLWE, with the ternary case ($B=1$) providing a representative example. In this ternary setting, for modulus $2^{64}$ the secret can be recovered within practical complexity bounds, while for moduli $2^{32}$ and $2^{16}$ we observe a substantial reduction in the effective security margin. These findings provide a systematic cryptanalytic study of bounded sLWE and clarify how sparsity influences the security of LWE-type constructions.

We design DiStefano: an efficient, maliciously-secure framework for generating private commitments over TLS-encrypted web traffic, for verification by a designated third-party. DiStefano provides many improvements over previous TLS commitment systems, including: a modular protocol specific to TLS 1.3, support for arbitrary verifiable claims over encrypted data, client browsing history privacy amongst pre-approved TLS servers, and various optimisations to ensure fast online performance of the TLS 1.3 session. We build a permissive open-source implementation of DiStefano integrated into the BoringSSL cryptographic library (used by Chromium-based Internet browsers). We show that DiStefano is practical in both LAN and WAN settings for committing to facts in arbitrary TLS traffic, requiring \(<\) 1 s and \(≤\) 80 KiB to execute the complete online phase of the protocol.

Registration-based Encryption ($\mathsf{RBE}$) is an emerging paradigm to remove the key escrow problem in identity-based encryption (IBE) systems. $\mathsf{RBE}$ represents a promising alternative to a public-key infrastructure, attaining the best of both worlds between IBE and traditional public-key encryption. Despite a lot of recent progress, existing constructions of $\mathsf{RBE}$ are not yet on-par with other approaches in terms of practical efficiency. To make things worse, all known concretely efficient constructions are based on bilinear pairings and are broken by quantum algorithms. In this work, we make progress on this problem. We construct a lattice-based, and therefore with plausible post-quantum security, $\mathsf{RBE}$ scheme with compact ciphertexts and fast encryption/decryption algorithms. Compared to the state-of-the-art lattice-based $\mathsf{RBE}$, our scheme reduces ciphertext size to $0.148$\,MB, down from $9$\,MB, for $1000$ users, and improves the encryption/decryption runtime by an order of magnitude. To the best of our knowledge, this is the first lattice-based $\mathsf{RBE}$ construction with ciphertexts well below one megabyte and competitive end-to-end performance, representing a significant step toward the practical adoption of $\mathsf{RBE}$.

Remote attestation is a fundamental security mechanism for assessing the integrity of remote devices. In practice, widespread adoption of attestation schemes is hindered by a lack of public verifiability and the requirement for interaction in existing protocols. A recent work by Ebrahimi et al. (NDSS'24) constructs publicly verifiable, non-interactive remote attestation, disregarding another important requirement for attesting sensitive systems: privacy protection. Similar needs arise in IoT swarms, where many devices, potentially processing sensitive data, should produce a single attestation. In this paper, we take on both challenges. We present PIRANHAS, a publicly verifiable, asynchronous, and anonymous attestation scheme for individual devices and swarms. We leverage zk-SNARKs to transform any classical, symmetric remote attestation scheme into a non-interactive, publicly verifiable, and anonymous one. Verifiers only ascertain the validity of the attestation, without learning any identifying information about the involved devices. For IoT swarms, PIRANHAS aggregates attestation proofs for the entire swarm using recursive zk-SNARKs. Our system supports arbitrary network topologies and allows nodes to dynamically join and leave the network. We provide formal security proofs for the single-device and swarm setting, showing that our construction meets the desired security guarantees. Further, we provide an open-source implementation of our scheme using the Noir and Plonky2 framework, achieving an aggregation runtime of just 356ms.

Fault injection attacks pose a significant threat to the security of embedded devices. While their effects are commonly modeled as instruction skips or data corruption, characterizing these faults requires programs that expose software-visible faulty behavior. However, many fault effects originate from microarchitectural elements, making them difficult to identify using existing approaches. On one hand, Register Transfer Level (RTL) analyses provide fine-grained insights but rely on abstract models that may not fully reflect the physical circuit. On the other hand, empirical characterization captures real faults but requires extensive experimentation and often reveals multiple fault models simultaneously, complicating precise identification. To address this gap, we propose an automated methodology that synthesizes characterization programs specifically designed to expose targeted microarchitectural fault models using a model-checking algorithm. Our methodology also assesses additional fault models revealed by these programs. Applied to two RISC-V processor cores, CV32E40P and Ibex, our methodology synthesizes programs that expose bit-flip faults for approximately 70 % of microarchitectural signals, using two days of computation on 10 parallel cores. For 25 % of the control signals in CV32E40P, we synthesize programs enabling the precise attribution of a bit-flip to a targeted signal. Such programs could facilitate the use of fault injection to deduce the placement of microarchitectural elements and help design more effective countermeasures. To the best of our knowledge, this work represents the first systematic methodology for building fault characterization pro- grams, marking a significant step beyond empirical approaches.

SSLE-DAG Proof-of-Stake (PoS) blockchains with publicly visible leader schedules expose future proposers to targeted Denial-of-Service (DoS) attacks. Single Secret Leader Election (SSLE) techniques address this problem by hiding the leader's identity until block publication. However, existing SSLE techniques are difficult to integrate with high-throughput Directed Acyclic Graph (DAG)-based Proof-of-Stake consensus protocols. We introduce SSLE-DAG, a PoS consensus protocol that combines a zk-SNARK-based SSLE commitment scheme with the adaptive DAG-based consensus protocol that splits or merges parallel chains (and thus regulates throughput) upon transaction demand. The commitment scheme uses EdDSA signatures, MiMC hashing, and Merkle proofs to guarantee uniqueness, fairness, and unpredictability while keeping leader identities private. We implement SSLE-DAG in Go (gnark) and evaluate it in a geo-distributed simulation using real-world latency traces. In a 60-node network, we achieve about 990 TPS, and in a 40-node network with shorter rounds, we reach about 1,600 TPS with low variance in block rewards.

Threshold variants of the Schnorr signature scheme have recently been at the center of attention due to their applications to cryptocurrencies. However, existing constructions for threshold Schnorr signatures among a set of $n$ parties with corruption threshold $t_c$ suffer from at least one of the following drawbacks: (i) security only against static (i.e., non-adaptive) adversaries, (ii) cubic or higher communication cost to generate a single signature, (iii) strong synchrony assumptions on the network, or (iv) $t_c+1$ are sufficient to generate a signature, i.e., the corruption threshold of the scheme equals its reconstruction threshold. Especially (iv) turns out to be a severe limitation for many asynchronous real-world applications where $t_c < n/3$ is necessary to maintain liveness, but a higher signing threshold of $n-t_c$ is needed. A recent scheme, ROAST, proposed by Ruffing et al. (ACM CCS 2022) addresses (iii) and (iv), but still falls short of obtaining subcubic communication complexity and adaptive security. In this work, we present HARTS, the first threshold Schnorr signature scheme to incorporate all these desiderata. More concretely: - HARTS is adaptively secure and remains fully secure and operational even under asynchronous network conditions in the presence of up to $t_c < n/3$ malicious parties. This is optimal. - HARTS outputs a Schnorr signature of size $\lambda$ with a near-optimal amortized communication cost of $O(\lambda n^2 \log{n})$ bits and a single asynchronous online round per signature. - HARTS is high-threshold: no fewer than $t_r+1$ signature shares can be combined to yield a full signature, where any $t_r\in [t_c,n-t_c)$ is supported. This especially covers the case $t_r \geq 2n/3 > 2t_c$. This is optimal. We prove our result in a modular fashion in the algebraic group model. At the core of our construction, we design a new simple and adaptively secure high-threshold asynchronous verifiable secret sharing (AVSS) scheme which may be of independent interest.

In a dictatorial setting where the receiver’s secret key may be exposed to an adversary, anamorphic encryption enables secure communication. Since its introduction in 2022, anamorphic cryptography has attracted considerable attention in the cryptographic literature. Anamorphic extension (AE) strengthens this paradigm by providing deniability: although the receiver can participate in covert communication, it can plausibly deny the existence of such communication to the dictator. The security of an AE of a public key encryption (PKE) is captured by the indistinguishability between its normal and anamorphic modes of operation, formalized by the IND-NA notion. In this paper, we have introduced two concrete constructions of AE from the number-theoretic assumptions-based indistinguishability against chosen plaintext attack (IND-CPA)-secure Goldwasser-Micali PKE and Benaloh PKE. We have proved the IND-NA security of our proposed AEs assuming the existence of secure pseudo-random function (PRF). To the best of our knowledge, our proposed Goldwasser-Micali based construction is the first AE that achieves natural robustness, attains bandwidth rate 1 and has small key-sizes where bandwidth rate is determined by the ratio of the covert and normal plaintext. The bandwidth rate of the Benaloh PKE-based construction is >> 1. Our proposed AEs are efficient due to small key size, low computation costs mostly involving computations of PRF and modular operations, high bandwidth rate, low anamorphic ciphertext expansion rate (ratio of the ciphertext size and the covert plaintext size) and deniability.

Ordered multi-signatures allow multiple signers to sign a common message sequentially, and anyone to verify the signing order of signers with a public-key list. Recently, Baum et al. (PKC 2025) proposed an ordered multi-signature scheme over a pairing-free group by modifying the multi-signature scheme MuSig2 by Nick et al. (CRYPTO 2021). The security of their ordered multi-signature scheme was proven under the algebraic one-more discrete logarithm (AOMDL) assumption in the random oracle model (ROM). The AOMDL assumption is stronger than the discrete logarithm (DL) assumption. To strengthen the assurance of security, it is desirable either to prove their scheme under the DL assumption or give a construction whose security is proven under the DL assumption. In this paper, we give an ordered multi-signature scheme from linear hash function families. Our scheme is obtained by generalizing Baum et al.’s scheme via linear hash function families. The security of our scheme is proven under the algebraic one-more preimage resistance (AOMPR) property of a linear hash function in the ROM. There is a linear hash function whose AOMPR property can be proven under the DL assumption. Thus, by using this linear hash function, we obtain the first DL- based ordered multi-signature scheme.

In federated learning (FL), secure aggregation (SA) allows a server to compute aggregate model updates (gradients) without accessing individual client gradients. SA is intended to protect clients’ local dataset from being inferred through individual gradients. However, recent NDSS 2025 work shows that even state-of-the-art SA protocols can be vulnerable, as a malicious server may reconstruct clients’ datasets from aggregated gradients. This demonstrates that protecting dataset privacy requires not only gradient confidentiality but also aggregation hiding. Moreover, a malicious server may deviate from the protocol and return manipulated results, making authenticity an additional critical security goal. Supporting one-shot clients, which send a single message per iteration to reduce synchronization overhead, further increases design complexity. To address these challenges, we propose FOVA, a fast one-shot verifiable aggregation protocol that simultaneously achieves aggregation hiding and authenticity against an actively malicious server. Notably, authenticity, defined under full participation, must be relaxed for dropout robustness due to the indistinguishability between adversarial omissions and legitimate dropout. FOVA is built upon the verifiable linearly homomorphic encryption scheme, for which we give a new construction based solely on the Paillier cryptosystem. This design enables high efficiency and allows FOVA to be integrated into existing Paillier-based FL frameworks with minimal modifications. We implement FOVA on top of an industrial FL framework. Experimental results show that, compared to the most relevant prior protocols, FOVA achieves up to three orders-of-magnitude speedup while providing stronger security guarantees.

As digital transformation accelerates, securing communication through hierarchical Public Key Infrastructures (PKIs) is increasingly critical. Yet, this centralized trust architecture remains inherently vulnerable. As a Systematization of Knowledge (SoK), this paper maps the threat landscape of hierarchical PKIs, demonstrating how a compromise at any single node from a Root CA breach to an operational revocation failure can trigger a cascading loss of global trust. Grounded in the Weakest-Link Principle, our analysis reveals that a PKI ecosystem is only as resilient as its least protected vector. Traditional revocation mechanisms, particularly CRLs and OCSP, exhibit significant operational and privacy flaws, and are often rendered ineffective by client-side "soft-fail" policies. To address these vulnerabilities, we advocate for a shift: replacing unconditional trust in individual entities with decentralized,verifiable protocols. We evaluate Certificate Transparency (CT) as a core mitigation strategy, illustrating how append-only Merkle trees make misissuance publicly visible and cryptographically auditable. Finally, we synthesize essential operational hardening measures such as strict key cryptoperiods and procedural policies to ensure long-term ecosystem resilience.

When large AI models are deployed as cloud-based services, clients have no guarantee that responses are correct or were produced by the intended model. Rerunning inference locally is infeasible for large models, and existing cryptographic proof systems—while providing strong correctness guarantees—introduce prohibitive prover overhead (e.g., hundreds of seconds per query for billion-parameter models). We present a verification framework and protocol that replaces full cryptographic proofs with a lightweight, sampling-based approach grounded in statistical properties of neural networks. We formalize the conditions under which trace separation between functionally dissimilar models can be leveraged to argue the security of verifiable inference protocols. The prover commits to the execution trace of inference via Merkle-tree-based vector commitments and opens only a small number of entries along randomly sampled paths from output to input. This yields a protocol that trades soundness for efficiency, a tradeoff well-suited to auditing, large-scale deployment settings where repeated queries amplify detection probability, and scenarios with rationally incentivized provers who face penalties upon detection. Our approach reduces proving times by several orders of magnitude compared to state-of-the-art cryptographic proof systems, going from the order of minutes to the order of milliseconds, with moderately larger proofs. Experiments on ResNet-18 classifiers and Llama-2-7B confirm that common architectures exhibit the statistical properties our protocol requires, and that natural adversarial strategies (gradient-descent re-construction, inverse transforms, logit swapping) fail to produce traces that evade detection. We additionally present a protocol in the refereed delegation model, where two competing servers enable correct output identification in a logarithmic number of rounds.

We give a down to earth and elementary introduction to the isogeny based cryptography protocol MIKE.

Privacy-preserving machine learning (PPML) has become increasingly important due to the need to protect sensitive data during training and inference. Secure multiparty computation (MPC) and homomorphic encryption (HE) have emerged as foundational technologies, enabling secure computation over private data. In this work, we provide a systematic comparative overview of MPC frameworks for PPML, focusing on protocols that introduce novel approaches rather than incremental improvements. Frameworks are analyzed based on computational and communication complexity, throughput, security guarantees, and applicability in small-party settings. Each underlying primitive in PPML is examined from an MPC perspective, highlighting its role and trade-offs. We also emphasize the diversity of secret-sharing schemes and associated interoperability challenges, proposing scheme conversions to facilitate efficient hybrid solutions. This Systematization of Knowledge guides researchers in identifying open problems and practitioners in selecting effective MPC-based frameworks for real-world PPML deployment.

Synchronous Byzantine fault tolerant (BFT) protocols offer stronger security guarantees, increasing resilience from one third to one half. However, existing constructions suffer from three drawbacks that are critical in blockchain settings. First, blockchain systems require rotating leaders, but the existing constructions are not optimized for low latency under leader rotation. Second, blockchain systems require provable commitments that can be forwarded to clients or offchain entities. Third, modern blockchains optimize for low latency in the good case, and often further optimize for a fast path under even milder adversarial conditions. In this work, we formalize and study fast paths in the context of provable synchronous BFT. Our first result is that for $n \le 2t + 2p + c -1$, it is impossible to obtain a provable synchronous BFT protocol that tolerates $t$ Byzantine and $c$ crash faults while also achieving a two round fast path resilient to $p$ Byzantine faults. Guided by this bound, we then present four provable synchronous protocols tailored to two deployment paradigms: optimistic responsivness and fixed view schedules. For optimistic responsiveness, we present $\Delta$-Sync Simplex and $2\Delta$-Sync Simplex, which for $n = 2t + 2p + c + 1$, produce provable commit certificates in time $2\delta$ under a correct leader when the number of faulty parties $f$ satisfies $f \le p$. $2\Delta$-Sync Simplex also achieves $3\delta$ commit latency when the total number of faulty parties is $f \le \lfloor (p + t)/2 \rfloor$ with Byzantine faults $f_b \le t$ and crash faults $f_c \le c$. Outside these optimistic regimes, the protocols remain safe and live for $t$ Byzantine and $c$ crash faults, and output provable commitments within $2\Delta + 2\delta$ and $1\Delta + 3\delta$, respectively. Under faulty leaders, the protocols guarantee a worst case view length of $6\Delta + \delta$ and $5\Delta + \delta$ respectively. For fixed view schedules, we present two additional protocols, TenderSync and SyncMint, that trade off commit latency and view duration. They achieve either $3\Delta$ provable commit with $4\Delta$ views, or $4\Delta$ provable commit with $3\Delta$ views. Both protocols obtain a provable commit in $2\delta$ under a correct leader when $f \le p$.

Ring signatures, a cryptographic primitive introduced by Rivest, Shamir and Tauman (ASIACRYPT 2001), offer signer anonymity within dynamically formed user groups. Recent advancements have focused on lattice-based constructions to improve efficiency, particularly for large signing rings. However, current state-of-the-art solutions suffer from significant overhead, especially for smaller rings. In this work, we present a novel NTRU-based ring signature scheme, Gandalf, tailored towards small rings. Our post-quantum scheme achieves a 50% reduction in signature sizes compared to the linear ring signature scheme Raptor (ACNS 2019). For rings of size two, our signatures are approximately a quarter the size of DualRing (CRYPTO 2021), another linear scheme, and remain more compact for rings up to size seven. Compared to the sublinear scheme Smile (CRYPTO 2021), our signatures are more compact for rings of up to 26. In particular, for rings of size two, our ring signatures are only 1236 bytes. Additionally, we explore the use of ring signatures to obtain deniability in authenticated key exchange mechanisms (AKEMs), the primitive behind the recent HPKE standard used in MLS and TLS. We take a fine-grained approach at formalising sender deniability within AKEM and seek to define the strongest possible notions. Our contributions extend to a black-box construction of a deniable AKEM from a KEM and a ring signature scheme for rings of size two. Our approach attains the highest level of confidentiality and authenticity, while simultaneously preserving the strongest forms of deniability in two orthogonal settings. Finally, we present parameter sets for our schemes, and show that our deniable AKEM, when instantiated with our ring signature scheme, yields ciphertexts of 2004 bytes.

Retrieval-Augmented Generation (RAG) is widely used to enhance Large Language Models (LLMs), yet the "hallucination" characteristic allows malicious providers to bypass retrieval or claim non-existent data quality. To address these challenges, we present VeriRAG, a framework that leverages Zero-Knowledge Proofs (ZKP) to provide efficient integrity guarantees for RAG systems without compromising dataset privacy. Leveraging the robustness of AI inference, our framework supports Approximate Nearest Neighbor Search (ANNS)-based retrieval to avoid exhaustive searches. For the verification of top-$k$ sorting, we propose an innovative protocol that bypasses the intricate verification of sorting processes. To further enhance performance, we introduce a joint optimization leveraging vector lookup and chunk-merging strategies, which collectively drive down verification overhead while maintaining high generation accuracy. Experimental results demonstrate that VeriRAG scales efficiently to a 37GB dataset, achieving a prover time of 96s and a verifier time of 3s.

Feedback shift registers, such as Linear Feedback Shift Registers (LFSRs), Multi-Recursive Matrix Methods (MRMMs), and Lagged Fibonacci Generators (LFGs), are fundamental components in stream cipher-based cryptographic systems. In this paper, we investigate systems composed of LFSRs under two distinct configurations. First, we study the cascade connection of LFSRs and demonstrate that it represents a special case of the first configuration. Under specific conditions, we derive the exact period of these cascaded systems. Second, we analyze a system comprising two LFSRs in the second configuration, where carry bits are introduced into the feedback computation of the second LFSR. We examine the periodicity of both the carry bits and the overall system. Furthermore, we generalize this construction to word size $m$, and show that an additive LFG can be represented by an equivalent system of LFSRs. This approach enables efficient LFG implementation in resource-constrained environments by using multiple LFSRs and a simple adder, thus eliminating the need for large word sizes.

In this technical note, we discuss a new direction in the design of privacy-preserving and scalable Layer-2 (L2) protocols by presenting a concrete construction, PlasmaBlind. To minimize the L2 users’ overhead for achieving privacy while enabling efficient creation of compact blocks, PlasmaBlind is built upon a novel architecture that leverages folding schemes’ powerful and flexible properties. On the user side, we utilize their blinding property to shield and prove transaction data without expensive succinct zero-knowledge proofs. On the aggregator side, their low accumulation cost allows efficient aggregation of user instances into a constant size proof of block validity. We further improve our proof aggregation performance by proposing an optimization technique that efficiently links two different verification tasks with shared input while eliminating the need for cumbersome proof composition of non-uniform circuits, which could be of independent interest. The practicality of PlasmaBlind is validated by our preliminary benchmarks, which demonstrate that, with consumer hardware, PlasmaBlind achieves sub-100ms proving time on the client side and sub-300ms per-transaction time on the aggregator side.

Information set decoding (ISD) algorithm is the main tool to estimate the concrete bit security of code-based cryptographic schemes including Classic McEliece, HQC and BIKE. Inspired by sieving methods in lattice-based cryptoanalysis, a new type of ISD algorithm (called sieving-ISD) based on locality sensitive filter (LSF) was recently proposed by Guo, Johansson, and Nguyen [GJN24, TIT], which has been shown to achieve comparable complexity with the BJMM/MMT algorithm when attacking Classic McEliece. At EUROCRYPT 2024, Ducas, Esser, Etinski and Kirshanova extended [GJN24, TIT]'s deterministic LSF to probabilistic LSFs and provided an asymptotic worst-case complexity analysis for sieving-ISD with different LSFs in the full-distance setting, which indicates that the sieving-ISD with probabilistic LSFs can achieve better time complexity than the ones with [GJN24, TIT]'s deterministic LSF. In this paper, we first propose a generalized sieving-ISD framework (called progressive sieving-ISD), which allows for more freedom in parameter configuration. In particular, we present a concrete complexity analysis for both our progressive sieving-ISD and its ``decoding one out of many'' (DOOM) variant under a binary sieve heuristic, whose validity can be verified via experiments. Then, by searching the optimal parameter configuration, we show that our progressive sieving-ISD can achieve attack time complexity improvements over the previous non-progressive version by 5-12 bits. In particular, for all the three categories of HQC to be standardized by NIST, we show that the state-of-the-art complexity results can be reduced by 7-9 bits using our progressive sieving-ISD, making their security levels 5.1/2.1/5.7 bits below the NIST requirements (143/207/272 bits). Interestingly, our results show that when considering the concrete security of Classic McEliece/HQC/BIKE, the progressive sieving-ISD with [GJN24, TIT]'s deterministic LSF can achieve a better performance than the ones with probabilistic LSFs in [DEEK24, EC]. Finally, we show the connection between progressive sieving-ISD and BJMM, and hence explain why progressive sieving-ISD can achieve a better time complexity than BJMM.

Lightweight keystream generators are widely used in resource-constrained digital systems, where implementation efficiency in area, power, and logic structure is a primary design concern. Conventional designs predominantly employ shift-register-based state propagation, in which diffusion is inherently coupled with sequential data movement. This work investigates an alternative architectural approach in which state mixing is achieved through sparse interaction among state variables, enabling a decoupling between diffusion and register propagation. We present \emph{SIR}, a sparse-interaction keystream generator with a 128-bit internal state composed of a nonlinear 64-bit primary state and a 64-bit auxiliary linear state. The primary state is updated using a compact four-input Boolean function applied over a fixed sparse neighbourhood, while the auxiliary state provides lightweight round-dependent perturbation. This structure realizes diffusion through parallel combinational interaction, leading to a distinct hardware profile characterized by reduced reliance on sequential storage and increased distributed logic. The architectural behaviour is evaluated through diffusion and statistical experiments, showing rapid propagation of local perturbations across the state within 14--15 rounds and no observable low-order dependence between internal state variables and output in the tested regime. Hardware implementation on a Xilinx Artix-7 FPGA requires 183 LUTs and 177 flip-flops, while ASIC synthesis using a 45\,nm standard-cell library results in an area of 3079 gate equivalents. Comparative evaluation with Grain-128, Trivium, and Espresso under identical implementation conditions demonstrates that the proposed architecture provides a competitive trade-off between combinational logic and sequential resources. The results indicate that sparse-interaction-based state evolution constitutes a viable architectural alternative for lightweight keystream generation, particularly in hardware-oriented and FPGA-based design settings.

Threshold signatures split the secret key among $n$ parties, where any subset of at least $t$ parties can collaboratively produce a valid signature. They have been widely deployed in applications such as blockchain systems. Lattice-based threshold signatures have also attracted considerable attention due to their post-quantum security guarantees. However, existing lattice-based constructions still face significant efficiency challenges, particularly when the number of parties becomes large. Recent lattice-based threshold signatures such as TRaccoon (Eurocrypt’24) and Ringtail (S\&P’25) support large thresholds, but they either require three interaction rounds or incur heavy communication costs in the two-round setting, limiting their practicality. In this paper, we present $\mathsf{TalonG}$, a novel two-round lattice-based threshold signature that overcomes these limitations via a new trapdoor semi-commitment technique. This variant of commitment relaxes the standard binding requirement to a weaker form, allowing an efficient instantiation from the NTRU assumption and enabling a compact two-round signing protocol with low communication. For $t=1024$ and 128-bit security, $\mathsf{TalonG}$ achieves significant improvements among existing lattice-based threshold signatures: its total communication per party and public key size are both minimal, at 26.9 KB and 2.0 KB, respectively. While the resulting signature size is larger (17.7 KB), it remains practical and highly competitive. $\mathsf{TalonG}$ is thus well-suited for real-world large-scale deployments where both round efficiency and communication load are critical.

The SPHINCS+ framework, recently standardized by NIST as SLH-DSA (FIPS 205), is a leading stateless hash-based signature scheme for the post-quantum era. Concrete-security evaluation of SPHINCS+ faces a trade-off: tight bounds require a conjectural multi-target decisional second-preimage resistance (SM-DSPR), while fully proven bounds incur substantial looseness. In this paper, we refine the concrete security analysis of SPHINCS+ by eliminating this heuristic reliance. In our approach, we analyze the SM-openPRE and SM-PRE properties instead of relying on SM-DSPR. By utilizing a precise probabilistic simulation technique, we restrict the multi-target tightness degradation exclusively to the maximum number of practically revealed targets rather than the total theoretical targets. When applied to the SLH-DSA parameter sets, our conjecture-free approach bridges the theoretical gap, recovering up to 18 bits of classical security and 9 bits of quantum security compared to the NIST loose evaluation. Our results establish a provable bound for the practical security of SLH-DSA without relying on optimistic multi-target assumptions.

Among the schemes in the second round of NIST's additional call for Post-Quantum signatures, PERK builds its security on the intractability of the Permuted Kernel Problem (PKP). In its original formulation, this problem asks, on input three matrices $\mathbf H,\mathbf X,\mathbf Y$, to find a permutation matrix $\mathbf P$ such that $\mathbf H \mathbf P \mathbf X = \mathbf Y$. To achieve better performance and smaller signatures, in its first proposal, the PERK signature modified the security assumption in the following way: given a PKP instance, the matrix $\mathbf P$ does not have to verify the exact previous equation but a relaxed one, taking care of a non-null vector $\mathbf v$ such that $(\mathbf H \mathbf P \mathbf X)\mathbf v = \mathbf Y \mathbf v$. In this work, we rephrase the relaxed problem so that it no longer depends on the PKP instance nor the vector $\mathbf v$. We show that it suffices to find $\mathbf P$ such that $\mathbf H\mathbf P \mathbf X - \mathbf Y$ has rank deficiency. This generalized formulation is easier to model and allows us to design an algebraic attack inspired by those of MinRank and Rank Syndrome Decoding, writing a polynomial system in the entries of $\mathbf P$. Moreover, we can consider it as linear in the minors of $\mathbf P$ and provide some results on them, which may be of independent interest.

We present an asymptotic analysis of the ternary variant of Sparse Learning with Errors (spLWE), a structured LWE variant proposed by Jain--Lin--Saha (CRYPTO'24) in which each equation involves only $k \ll n$ of the $n$ secret coordinates, enabling significantly more efficient computation than dense LWE. Unlike standard LWE, the small-secret regime of spLWE is not automatically reducible to its large-secret counterpart, leaving asymptotic hardness unclear, particularly when $k$ is very small. We develop a two-pronged attack framework that depends explicitly on the sparsity parameter $k$. In the geometric regime $q > 3^k$, each sparse row reduces to a short-vector problem in a $k$-dimensional lattice, yielding complexity $2^{0.292k}$ via a sieving algorithm. In the statistical regime $q \leq 3^k$, we propose a greedy coordinate-recovery attack with running time $O(m \cdot k \cdot 3^k)$, where $m$ is the number of samples. Heuristically, under mild assumptions, full recovery holds with high probability once the sample size is large enough; the resulting complexity is exponential only in $k$ and otherwise mild (up to polylogarithmic factors), i.e., polynomial in $n$, which makes very small $k$ vulnerable even at large dimensions. Experiments on toy instances confirm the predicted sharp transition. Complexity comparisons with prior works indicate lower complexity on a few of their parameter sets, while identifying regimes where our method is not applicable.

This paper presents a novel zero-trust anonymous reputation update protocol for IoT crowd-sensing applications. We use a suite of cryptographic functions to achieve anonymity, including unlinkability of sensing reports to the principals that submit them, and of reports to one another, while enabling the infrastructure to reliably quantify the degree of trust expressed as a reputation level. The protocol is low-cost for the anonymous participant due to the use of cheap standard functions: low-exponent modular exponentiation and cryptographic hashing, which makes it quite suitable for IoT. Despite that, uniquely it does not require anonymous clients to trust the servers even if the latter could collude in an attempt to de-anonymise the former. Furthermore under the protocol, selective onboarding does not require trust either, as the gate keeper issues tickets assuredly blindly after examining the real user's credentials. On the other hand, reputation values versus time can be, and are, linked, enabling statistical analysis for accurately assessing reports without jeopardising anonymity. The protocol has been benchmarked on an off-the-shelf microcontroller broadly used in IoT solutions, with the latency measured at less than 30ms per round for the 4K RSA modulus that NIST recommends until the year 2035. The power drain has been calculated to be low enough for an implementation as a key fob using actual components and their manufacturer guaranteed data, with an embedded disc battery supporting the solution for in excess of 3 years.

This note describes a weak-key attack on the tweakable block cipher Blink, which was recently introduced at FSE 2026. Specifically, it is shown that two rounds of Blink admit several nonlinear invariants. To illustrate that these invariants indeed lead to attacks, we describe a partial key-recovery attack on Blink-64 with data and time complexity $2^{23}$, for a fraction of $2^{-96}$ weak keys or tweaks. There is a trade-off between the fraction of weak keys and the data complexity, e.g., with $2^{56}$ data the fraction of weak keys increases to $2^{-63}$. The attack is based on the same strategy as our attack on Midori-64 from Asiacrypt 2018.

Design-hiding (DH) schemes, such as logic locking, aim to protect circuit-design intellectual property (IP) in the integrated-circuit (IC) supply chain. While many practical DH schemes have been proposed over the past 15 years, nearly all have been broken by efficient attacks. Security and efficiency claims for these schemes have been based primarily on evaluations using benchmark circuits from legacy test-suites such as ISCAS’85 and MCNC. Recent work suggests that some circuits are fundamentally unhideable, as their functionality can be approximately learned using classical blackbox (BB) learning-theoretic (LT) algorithms. In this work, we ask: How prevalent are unhideable circuits in standard DH benchmarks? To answer this, we identify properties—such as sparse Fourier spectra—that make circuits unhideable. However, since BB Fourier-analytic algorithms are often slow and inaccurate for large-domain circuits, we shift to a whitebox (WB) setting. We develop new, efficient WB variants of Fourier-analytic algorithms that leverage WB access to a circuit and advances in model counting to efficiently evaluate whether the circuit has properties that make it unhideable. Upon applying these algorithms to standard DH benchmarks, we find that most circuits in the ISCAS'85 and MCNC test-suites are fundamentally unhideable, whereas newer benchmarks exhibit stronger resistance to Fourier-analytic algorithms and merit broader use in DH evaluation.

We consider (almost) $k$-wise independent hash functions, whose evaluations on any $k$ inputs are (almost) uniformly random, for very large values of $k$. Such hash functions need to have a large key that grows linearly with $k$. However, it may be possible to evaluate them in sub-linear time by only reading a small subset of $t \ll k$ locations during each evaluation; we call such hash functions $t$-local. Local hash functions were previously studied in several works starting with Siegel (FOCS'89, SICOMP'04). For a hash function with $n$-bit input and output size, we get the following new results: * There exist (non-constructively) perfectly $k$-wise independent $t$-local hash functions with key size $O(kn)$ and locality of $t = O(n)$ bits. An analogous prior result of Larsen et al. (ICALP '24) had a locality of $t=O(n)$ words consisting of $w= O(n)$ bits each, and hence a suboptimal $O(n^2)$ bits total. Furthermore, we show that such hash functions could be made explicit if we had explicit optimal constructions of unbalanced bipartite lossless expanders. Plugging in currently best known suboptimal explicit expanders yields correspondingly suboptimal hash functions. * Perfectly $k$-wise independent local hash functions generically yield expanders with corresponding parameters. This is true even if the locations accessed by the hash function can be chosen adaptively and shows that progress on explicit hash functions inherently requires progress on explicit expanders. * We initiate the study of $\epsilon$-almost $k$-wise independent hash functions, where any $k$ adaptive queries to the hash function are $\epsilon$-statistically indistinguishable from $k$ queries to a random function. We construct an explicit family of such hash functions with optimal key size $O(kn)$ bits, optimal locality $t = O(n)$ bits, and $\epsilon= 2^{-n}$, significantly improving over the best known parameters for explicit perfectly independent hashing. * More generally, if we consider a word model with larger word size $w$, then we get an explicit, efficient construction of $\epsilon$-almost $k$-wise independent hash functions with key size $O(kn/w)$ words, locality $t = O(n/\sqrt{w})$ words, and statistical distance $\epsilon= 2^{-n}$, which we show to be nearly optimal. Such parameters go beyond what is possible for perfect independence. We discuss applications to nearly optimal bounded-use information-theoretic cryptography.

We present a Number Theoretic Transform (NTT) hardware architecture based on the Prouhet-Thue-Morse (PTM) code, enabling NTT implementations relying only on single-port RAMs (SPRAMs), rather than using dual-port RAMs (DPRAMs) as usually done in the literature. We show that the PTM code supports a conflict-free, transactional, and streamlined pipeline across all NTT computation stages, as well as scalable parallelism through multiple butterfly units. Using this approach, we design single- and dual-butterfly NTT modules for ML-DSA that are compliant with reference software and can be packaged as a standalone AXI-Stream peripheral, allowing the forward and inverse NTT operations to be offloaded from software via DMA transfers. Experimental results show that the proposed PTM-based NTT designs achieve near one-cycle-per-butterfly and half-cycle-per-butterfly performance for the single- and dual-butterfly configurations, respectively. At the same time, it maintains FPGA resource utilization comparable to state-of-the-art compact NTT implementations relying on mixed SPRAM/DPRAM architectures or SPRAM-only designs requiring coefficient reordering.

We present AHAB, a suite of protocols for threshold Schnorr signatures in the asynchronous communication setting with guaranteed output delivery (robustness). We build on the AVSS and GoAVSS protocols of Shoup–Smart and Groth–Shoup, which allow t < n/3 static corruptions. First, we provide protocol enhancements and a full security proof in the adaptive corruption model with erasures. Second, we introduce a signature production pipeline with a player elimination framework that bounds the damage from actively misbehaving parties: if t* corrupt parties disrupt a presignature batch, the total communication overhead is at most O(t*) times the happy-path cost, and all t* parties are identified and eliminated, after which the system runs at the happy-path rate until further active misbehavior occurs. Third, we present a simplified protocol variant for t < n/4 adaptive corruptions that achieves worst-case linear communication complexity by eliminating the complaint mechanism entirely and using star-finding at the pipeline level to agree on which dealers and receivers to use. Fourth, we present a hiding variant of GoAVSS that yields an unbiased distributed key generation protocol, preventing an adaptive adversary from biasing the signing key. We also give new and more efficient star-finding algorithms, including an ILP-based optimization that should improve the yield of presignatures per batch in practice. For the main protocol (t < n/3), with t=16 and n=49, on a 1 Gbps network with commodity hardware, we estimate a throughput of 100K signatures per second; for the simplified protocol (t < n/4), with t=16 and n=65, the estimate is 160–250K signatures per second.

Blind signatures are a versatile cryptographic primitive with many applications, especially in privacy-preserving technologies. Threshold blind signature schemes (TBS) enhance blind signatures with a signing procedure distributed among up to n signers to reduce the risk attached to the compromise of the secret key. So far, TBS constructions over groups rely on strong assumptions, e.g., the algebraic group model (AGM) or interactive assumptions. In this work, we propose two TBS based on the computational Diffie-Hellman assumption (CDH) in the ROM: – The first TBS over pairing-free groups without the AGM. – The first round-optimal TBS over pairing-based groups that does not rely on interactive assumptions. The starting point for both constructions is the pairing-based signature scheme derived from Boneh-Boyen IBE (Eurocrypt’04), and their recent blind signature variants by Katsumata et al. (Asiacrypt’23) and Klooß et al. (Asiacrypt’24) based on the decisional Diffie-Hellman assumption (DDH). We first remove the reliance on DDH in their schemes, then provide careful adaptations to the threshold setting.

In this paper, we examine the One-time signature scheme using run-length encoding, as proposed by Steinwandt et al., under the scenario where an adversary is allowed to obtain signatures on two messages before attempting to forge a signature on a third message. Our analysis follows the line of security discussion presented by Groot Bruinderink et al. in their paper “Oops, I Did It Again – Security of One-Time Signatures under Two-Message Attacks.” By considering various attack models and different strategies, we estimate both the attack complexity and the probability of forging a signature. Our results indicate that the signature scheme performs well under a two-message attack, making it an interesting candidate for a few-time signature scheme. Few-time signature schemes such as HORS are a fundamental building block of stateless hash-based signature schemes.

Attribute-based encryption can be considered a generalization of public key encryption, enabling fine-grained access control over encrypted data using predetermined access policies. In general, we distinguish between key-policy and ciphertext-policy attribute-based encryption schemes. Our new scheme is built upon the multi-authority attribute-based encryption with an honest-but-curious central authority scheme in a key-policy setting presented earlier by Božović et al., and it can be considered an extension of their scheme. In their paper, trust was shared between the central authority and the participating authorities, who were responsible for issuing attribute-specific secret keys. The central authority was not capable of decrypting any message as long as there exists an honest attribute authority. In our new scheme, we maintain this feature, and add another level of security by allowing users to participate in the key generation process and contribute to the final user-specific attribute secret keys. Users gain more control over their own secret keys, and they will be the only parties with access to the final user-specific secret keys. Furthermore, no secure channels, only authenticated communication channels are needed between users and authorities. After the modifications our scheme will be closer to the registered multi-authority attribute-based encryption. We refer to our scheme as a partially registered type of multi-authority attribute-based encryption scheme. We prove the security of our scheme in the Selective-ID model.

This paper presents fault‑injection attacks on six candidates of the Round‑2 NIST post‑quantum digital signatures call: code-based schemes CROSS and LESS, multivariate schemes MAYO, and MPC-in-the-Head schemes Mirath, RYDE, and PERK. These schemes rely on SHA‑3‑based hash functions to securely embed secret-dependent values in the signature construction. We show that a single instruction skip fault targeting the Keccak-f permutation during the sponge squeezing phase can reveal these secret values and enable full key recovery. The attacks break the one‑way property of the affected SHA‑3 implementation, as the fault allows recovering the function's input from its output. We experimentally validate the attacks on the optimised pqm4 ARM Cortex-M4 CROSS implementation via instruction-skipping using voltage glitching, and present practical countermeasures.

We present a new approach for constructing non-interactive zero-knowledge (NIZK) proof systems from vector trapdoor hashing (VTDH) -- a generalization of trapdoor hashing [Döttling et al., Crypto'19]. Unlike prior applications of trapdoor hash to NIZKs, we use VTDH to realize the hidden bits model [Feige-Lapidot-Shamir, FOCS'90] leading to black-box constructions of NIZKs. This approach gives us the following new results: - A statistically-sound NIZK proof system based on the hardness of decisional Diffie-Hellman (DDH) and learning parity with noise (LPN) over finite fields with inverse polynomial noise rate. This gives the first statistically sound NIZK proof system that is not based on either LWE, or bilinear maps, or factoring. - A dual-mode NIZK satisfying statistical zero-knowledge in the common random string mode and statistical soundness in the common reference string mode assuming the hardness of learning with errors (LWE) with polynomial modulus-to-noise ratio. This gives the first black-box construction of such a dual-mode NIZK under LWE. This improves the recent work of Waters (STOC'24) which relied on LWE with super-polynomial modulus-to-noise ratio and required a setup phase with private coins. The above constructions are black-box and satisfy single-theorem zero-knowledge property. Building on the works of Feige et al.(FOCS'90) and Fishclin and Rohrback (PKC'21), we upgrade these constructions (under the same assumptions) to satisfy multi-theorem zero-knowledge property at the expense of making non-black-box use of cryptography.

Sampling a non degenerate (that is, invertible) square matrix over a finite field is easy, draw a random square matrix and discard if the determinant is zero. We address the problem in higher dimensions, and sample non degenerate boundary format tensors, which generalise square matrices. Testing degeneracy is conjectured to be hard in more than two dimensions, precluding the "draw a random tensor and discard if degenerate'' recipe. The difficulty is in computing hyperdeterminants, higher dimensional analogues of determinants. Instead, we start with a structured random non degenerate tensor and scramble it by infusing more randomness while still preserving non degeneracy. We propose two kinds of scrambling. The first is multiplication in each dimension by random invertible matrices, which preserves dimension and format. Assuming pseudo randomness of this action, which also underlies tensor isomorphism based cryptography, our samples are computationally indistinguishable from uniform non degenerate tensors. The second scrambling employs tensor convolution (that generalises multiplication by matrices) and can increase dimension. Inspired by hyperdeterminant multiplicativity, we devise a recursive sampler that uses tensor convolution to reduce the problem from arbitrary to three dimensions. Our sampling is a candidate solution for drawing public keys in tensor isomorphism based cryptography, since non degenerate tensors elude recent weak key attacks targeting public key tensors either containing geometric structures such as "triangles" or being deficient in tensor rank. To accommodate our sampling, tensor isomorphism based schemes need to be instantiated in boundary formats such as (2k+1) x (k+1) x (k+1), away from the more familiar k x k x k cubic formats. Our sampling (along with the recent tensor trapdoor one-way functions) makes an enticing case to transition tensor isomorphism cryptography to boundary formats tensors, which are true analogues of square matrices.

Arithmetic correlation is a critical performance measure for pseudorandom sequences generated by feedback with carry shift registers (FCSRs), extending classical correlation by accounting for carry propagation. Chen et al. proved that for binary sequences with coprime periods, the arithmetic crosscorrelation is constant, and established bounds for Legendre sequences and $m$-sequences. In this paper, we further investigate the arithmetic crosscorrelation of sequences with coprime periods. We derive upper bounds for sequences constructed from the Legendre symbol, which generalize classical Legendre sequences, and for sequences generated by trace functions. In addition, we show that the constant property of arithmetic crosscorrelation extends to non-binary sequences with coprime periods.

A $K$-multi-collision-resistant hash function ($K$-MCRH) is a shrinking keyed function for which it is computationally infeasible to find $K$ distinct inputs that map to the same output under a randomly chosen hash key; the case $K = 2$ coincides with the standard definition of collision-resistant hash function (CRH). A natural question is whether $K$-MCRH implies CRH for $K \geq 3$, as noted by Komargodski, Naor, and Yogev (EUROCRYPT 2018) and also by Jain, Li, Robere, and Xun (FOCS 2024). We resolve this question for all constant $K$, showing that there is no black-box construction of $K$-MCRH from $(K + 1)$-MCRH for all constant $K \geq 2$. We also show that there is no black-box construction of distributional CRH (which is another relaxation of CRH) from 3-MCRH, answering an open question posed by Komargodski and Yogev (CRYPTO 2018) and also by Berman, Degwekar, Rothblum, and Vasudevan (EUROCRYPT 2018). Besides applications in cryptography, our separation also implies black-box separations between TFNP search problems, which are related to problems in proof complexity and other areas.

Witness encryption (WE) (Garg et al, STOC’13) is a powerful cryptographic primitive that is closely related to the notion of indistinguishability obfuscation (Barak et, JACM’12, Garg et al, FOCS’13). For a given NP-language $L$, WE for $L$ enables encrypting a message $m$ using an instance $x$ as the public-key, while ensuring that efficient decryption is possible by anyone possessing a witness for $x \in L$, and if $x\notin L$, then the encryption is hiding. We show that this seemingly sophisticated primitive is equivalent to a communication-efficient version of one of the most classic cryptographic primitives—namely that of a zero-knowledge argument (Goldwasser et al, SIAM’89, Brassard et al, JCSS’88): for any NP-language $L$, the following are equivalent: - There exists a witness encryption for L; - There exists a laconic (i.e., the prover communication is bounded by $O(\log n)$) special-honest verifier zero-knowledge (SHVZK) argument for $L$. Our approach is inspired by an elegant (one-sided) connection between (laconic) zero-knowledge arguments and public-key encryption established by Berman et al (CRYPTO’17) and Cramer-Shoup (EuroCrypt’02), and the equivalence between a notion of so-called “predictable arguments” and witness encryption by Faonio, Nielsen, and Venturi (PKC’17).

Recent MPC-in-the-Head techniques enable the construction of signature schemes with compact signature sizes from various hardness assumptions. These techniques rely on commitments based on GGM trees, which have been optimized to further reduce the signature size with the so-called one-tree or correlated tree optimizations. While the one-tree technique has no incidence on the security of the scheme, this is not obvious for the correlated tree technique, and a formal security analysis of this technique has been missing in the literature. In this work, we fill this gap and provide the first formal security analysis of MPC-in-the-Head signature schemes based on correlated trees. We first exhibit a potential security flaw of this technique which rules out any hope for a security reduction to the underlying hardness assumption. In particular, we show that recovering the first $\lambda$ bits of the secret witness is sufficient to achieve a full key recovery (where $\lambda$ is the security level). The underlying assumption should hence be such that recovering these $\lambda$ bits is as hard as recovering the full witness. Some state-of-the-art schemes do not satisfy this condition, which prevents a direct application of the correlated tree technique. We then provide a formal security proof for signature schemes based on the correlated tree technique under this degraded hardness assumption. Our proof comes in several variants, in the random oracle mode or in the ideal cipher model, depending on the specific correlated tree construction. We also introduce a tweak for the instantiation of the leaf seed expansion in the ideal cipher model, which allows us to achieve a tighter security reduction. Our result shows that MPC-in-the-Head signatures based on correlated trees can achieve strong security guarantees and provides the first formal security proof for the MQOM v2 signature scheme, the on-going candidate in the NIST post-quantum standardization process with the shortest signature size in the MPC-in-the-Head family.

The Learning with Errors (LWE) problem is a hard math problem in lattice-based cryptography. In the simplest case of binary secrets, it is the subset sum problem, with error. Effective ML attacks on LWE were demonstrated in the case of binary, ternary, and small secrets, succeeding on fairly sparse secrets. The ML attacks recover secrets with up to 3 active bits in the "cruel region" (Nolte et al. 2024) on samples pre-processed with BKZ. We show that using larger training sets and repeated examples enables recovery of denser secrets. Empirically, we observe a power-law relationship between model-based attempts to recover the secrets, dataset size, and repeated examples. We introduce a stepwise regression technique to recover the "cool bits" of the secret.

Keyed-verification anonymous credentials (KVACs) have demonstrated their practicality through large-scale deployments in privacy-critical systems like Signal and Tor. Despite their widespread adoption, the theoretical framework underlying KVACs lacks the flexibility needed to support diverse applications, which in general require different security properties. For instance, rate-limiting credentials only need a weaker unforgeability notion (one-more unforgeability), yet the framework cannot easily accommodate this relaxation. Similarly, identity-based applications require stronger properties than unforgeability -—specifically, extractability for security proofs when adversaries can observe other users' credentials. In this work, we address these limitations, introducing new notions of extractability and one-more unforgeability. We improve two foundational works in the space: - The scheme by Chase et al. (CCS 2014), commonly referred to as CMZ or PS MAC can be made statistically anonymous, and issuance cost reduced from \(O(2n)\) to \(O(1)\). We update the proof of Chase et al. in the algebraic group model. - The scheme by Barki et al. (SAC 2016), known as BBDT or BBS MAC can be issued more efficiently (one less group element). Finally, we note that for KVACs, designated-verifier proofs suffice since the verifier is known in advance. We introduce designated-verifier polynomial commitment schemes and instantiate a variant of the popular KZG commitment scheme without pairings. Any interactive oracle proof can be used in tandem with it, leading to designated-verifier fully-succinct zk-SNARKs without pairings for algebraic groups. Our model can improve the deployment of larger protocols relying on KVACs. We show this with some examples that benefit from our approach.

DATA [22] and Microwalk [23] are two advanced dynamic binary instrumentation (DBI) tools for detecting constant-time (CT) violations in software implementations. This paper presents a comparative evaluation of these tools' findings using a common test setup and several cryptographic implementations that are included in the libraries LibTomCrypt, OpenSSL, and liboqs. Our experiments yield reliable results for symmetric ciphers. For asymmetric cryptographic schemes, however, internal random numbers cause a high number of reported findings that also differ among the tools. In order to make the tools' results more comparable our test setup is adapted to externally inject random numbers that are otherwise generated internally by the cryptographic libraries. We discuss the differences of the tools' design and their impact on practical results of cryptographic implementations as well as their resource consumption in terms of memory and runtime.

By construction, Fully Homomorphic Encryption schemes have probabilistic correctness due to their underlying cryptographic assumptions. The family of Learning With Errors (LWE) problems assumes that a random error term is added during encryption. Statistically, this error grows as homomorphic computation proceeds. While predicting the noise evolution was initially only a correctness issue, recent works have shown a direct link with the security of FHE schemes in the IND-CPA-D model. Here, we present a framework that provides practical guarantees that the probabilities extrapolated from theoretical models satisfy bounds as small as $2^{-128}$. We show how to obtain strong experimental guarantees that the usual Gaussian model for noise is conservative and that a refined model based on Irwin-Hall distribution is valid. This is realized through an algorithm called importance splitting, which we adapt here to the cryptographic setting. We provide a detailed study in the context of TFHE bootstrapping and its variants. We believe our framework can serve as a baseline to be extended to other schemes, thereby ensuring both correctness and security across all FHE schemes.

We analyze a variant of the Fiat–Shamir transformation based on an ideal permutation. The transformation relies on the popular duplex sponge paradigm, and minimizes the number of calls to the permutation (given the information to absorb/squeeze). This closely models deployed variants of the Fiat–Shamir transformation, and our analysis provides concrete security bounds to guide security parameters in practice. Our results contribute to the ongoing community-wide effort to achieve rigorous, and ultimately formally verified, security proofs for deployed cryptographic proofs. Along the way, we find that indifferentiability (a property proven for many modes of operation, including the duplex sponge) is ill-suited for establishing the knowledge soundness and zero knowledge of a non-interactive argument. We additionally contribute spongefish, an open-source Rust library implementing our Fiat–Shamir transformation. The library is interoperable across multiple cryptographic frameworks, and works with any choice of permutation. The library comes equipped with Keccak and Poseidon permutations, as well as several "codecs" for re-mapping prover and verifier messages to the permutation's domain.

Blockchains intend to provide long-term integrity guarantees through cryptographic primitives that may become vulnerable over time due to algorithmic advances or paradigm shifts such as quantum computation. While cryptographic agility, the ability to transition between algorithms without disrupting operation, is recognized as essential, existing blockchain systems lack comprehensive support for such transitions. We address this gap by designing an Ethereum virtual machine (EVM) compatible blockchain that introduces support for cryptographic agility from genesis. We first propose a flexibility framework that characterizes how algorithm choice can be distributed across blockchain components. We then present two technical contributions aligned with this framework: (1) cryptographically agile transactions (CATX), a new transaction format that decouples body and signature to enable user-selected signature schemes; and (2) a consensus-layer key registration mechanism that allows validators to migrate between signature schemes as operational upgrades without hard forks. We exemplify the agility of our design with ECDSA, Falcon-512, and ML-DSA signatures by conducting experimental evaluations over 30,000 blocks and 11 million transactions, showing that the CATX format introduces no measurable overhead.

Privacy-preserving smart contracts (PPSCs) extend blockchain computation from transparent execution to confidential applications, enabling mutually distrustful parties to jointly compute contract logic on private inputs. Existing PPSC designs can be categorized into two main paradigms: trusted hardware–based systems and cryptographic systems. Trusted hardware-based systems provide general programmability and the performance is usually close to non-confidential computation, but the hardware has to be trusted. In contrast, cryptographic systems require much lower trust on the hardware but the performance is usually much lower. In this paper, we propose a hybrid PPSC framework that combines trusted hardware with cryptographic techniques, achieving both general programmability and reduced reliance on trusted hardware. Specifically, the TEE executes the smart contracts, but needs to authenticate the computation. A proof of the encrypted computational results is sent on-chain, and the blockchain authenticates the computational and aggregates the computational results using cryptographic approaches such as homomorphic encryption. In this way, the confidential smart contract via TEE is both efficient and general programmable, without being trusted. Meanwhile, the on-chain cryptographic approach does not introduce high overhead as it only authenticates and aggregates the results. We formalize the system model and security goals, and prove the correctness using the Universal Composability framework. Our implementation and evaluation on Intel SGX as the trusted hardware and Solidity as the smart contract show that our approach achieves nearly no degradation on the performance compared to non-confidential computation.

The bottleneck complexity of a (secure) multiparty computation protocol is one measure of its communication-efficiency. It captures how well the communication load is balanced, and is defined as the maximum communication complexity required by any one party within the protocol execution. Prior works on this topic restricted attention to protocols with fixed communication graphs, i.e. whether or not a given party communicates to another only depends on the round number. We demonstrate the power of adaptively choosing communication graphs by developing various bottleneck-efficient protocols, both with and without security. Done naÏvely, protocols with adaptive communication graphs can exploit unnatural tricks, such as "communicating with silence." To ensure our protocols are meaningful, we additionally stipulate that they should run correctly even in asynchronous networks (where we make no assumption on the adversarial message-delays other than being finite). [Bottleneck complexity of arbitrary functions.] With fixed communication graphs, Boyle, Jain, Prabhakaran, and Yu (ICALP'18) established the existence of a function $f\colon\{0,1\}^n\to\{0,1\}$ requiring $\Omega(n)$-bit bottleneck complexity, which is matched by the trivial protocol of having all parties send their inputs to one party. By adaptively choosing communication graphs, we show that any function $f\colon\{0,1\}^n\to\{0,1\}$ can be computed (securely) with bottleneck $O(n/\log n)$ (which we prove is essentially optimal), even in \emph{asynchronous} networks. [Bottleneck complexity of symmetric functions.] Prior works have demonstrated that special classes of symmetric functions, such as additive [Eriguchi, Asiacrypt'23] or abelian [Keller, Orlandi, Paskin-Cherniavsky, Ravi, ITC'23] functions can be computed bottleneck-efficiently with fixed communication graphs. We both expand the class of symmetric functions achievable with low bottleneck complexity, as well as show how input-adaptive communication graphs can be leveraged to further reduce the bottleneck complexity of some of our protocols.

Heterogeneous cross-device side-channel attacks remain a critical yet underexplored challenge, as models trained on one device often fail to generalize across architectures. This paper presents PD-Net, a domain generalization framework that learns device-invariant features by disentangling algorithmic content from device-specific style and aligning feature distributions using prototypical and Maximum Mean Discrepancy (MMD) losses. PD-Net is trained on nine heterogeneous source domains spanning ARM/AVR/FPGA and power/electromagnetic leakage modalities, including 32-bit ARM Cortex-M0/M1/M3/M4, 8-bit AVR ATmega (three series), and 128-bit Xilinx Virtex-5 FPGA, and evaluated in a zero-shot setting without target-specific adaptation. Experimental results demonstrate robust zero-shot cross-architecture transfers between 8-bit and 32-bit devices, with consistent gains over existing generalization and transfer-learning approaches. In particular, PD-Net delivers 29 successful attacks with only 10 divergences across 70 settings, markedly outperforming the state of the art, which succeeds in only 4 cases and diverges 19 times. To the best of our knowledge, this is the first domain generalization (DG)-based deep learning framework to systematically demonstrate practical zero-shot heterogeneous cross-device side-channel attacks.

We describe the methodology and scope of CatCrypt, a library for machine-checked cryptographic security proofs in Lean. CatCrypt provides an end-to-end pipeline from Rust reference implementations to security proofs in the computational model in Lean. The translation from Rust to Lean is done using the Hax tool. CatCrypt covers 172 cryptographic protocols and constructions with machine-checked security theorems in the computational model. Of these, 110 have the full Rust-to-Lean pipeline. All bounds have been systematically cross-referenced against their published sources (IETF RFCs, NIST standards, and academic papers). Some proofs were ported from SSProve (Rocq), EasyCrypt, ProVerif, CryptoVerif and Squirrel; most are independent formalisations with no prior machine-checked treatment. CatCrypt also includes a verified Lean implementation of a substantial part of the hax transpiler pipeline. This work is an experiment of what can be done by a researcher working with GenAI. Until recently, the formalization of one protocol required months of expert effort. In contrast, the whole of CatCrypt was developed in a period of two months. Because it was developed with AI, we develop a new methodology to increase confidence that the specifications are correct. Moreover, we will continue to audit the code in the coming months to gain even more confidence in the specification of the results. We hope this work will facilitate the adoption of formal methods in the development of security-critical software. This is especially urgent due to AI's increased hacking capabilities, the explosion of AI generated software and the ongoing post-quantum transition, which requires the development of new cryptographic protocols and their secure implementation.

We present HyperFrog, a lattice-based Key Encapsulation Mechanism (KEM) targeting post-quantum security levels. The construction instantiates a variant of the Learning With Errors (LWE) problem in which the secret vector is derived from high-genus topological structures embedded in a three-dimensional grid. Unlike standard LWE schemes that draw secrets from uniform or Gaussian distributions, HyperFrog uses a topology-mining procedure to generate sparse binary secret keys corresponding to connected subgraphs with cyclomatic number (genus) >= 8, introducing geometric constraints while preserving combinatorial hardness. To achieve practical robustness, the scheme applies the Fujisaki-Okamoto (FO) transform, attaining IND-CCA2 security under standard assumptions. The reference implementation, internally codenamed "Topological Obsidian", includes a constant-time decoding routine based on branchless arithmetic to eliminate secret-dependent control flow during decryption and re-encryption. We provide benchmark results on an AMD Ryzen 9 5950X implementation using AVX2 vectorization for polynomial arithmetic, and demonstrate the integration of the KEM into a high-performance AES-256-GCM hybrid encryption pipeline.

Privacy‑preserving aggregation is a cornerstone for AI systems that learn from distributed data without exposing individual records, especially in federated learning and telemetry. Existing two‑server protocols (e.g., Prio and successors) set a practical baseline by validating inputs while preventing any single party from learning users’ values, but they impose symmetric costs on both servers and communication that scales with the per‑client input dimension $L$. Modern learning tasks routinely involve dimensionalities $L$ in the tens to hundreds of millions of model parameters. We present TAPAS, a two‑server asymmetric private aggregation scheme that addresses these limitations along four dimensions: (i) no trusted setup or preprocessing, (ii) server‑side communication that is independent of $L$ (iii) post‑quantum security based solely on standard lattice assumptions (LWE, SIS), and (iv) stronger robustness with identifiable abort and full malicious security for the servers. A key design choice is intentional asymmetry: one server bears the $O(L)$ aggregation and verification work, while the other operates as a lightweight facilitator with computation independent of $L$. This reduces total cost, enables the secondary server to run on commodity hardware, and strengthens the non‑collusion assumption of the servers. One of our main contributions is a suite of new and efficient lattice-based zero-knowledge proofs; to our knowledge, we are the first to establish privacy and correctness with identifiable abort in the two-server setting.

Heavy-hitter detection is a fundamental primitive in stream analytics, with applications in network monitoring, telemetry, and large-scale data systems. In many practical deployments, this computation must be maintained continuously on remote infrastructure that offers higher availability and centralized operational control, even when the underlying streams contain sensitive identifiers or proprietary activity patterns. Existing privacy-preserving approaches either incur substantial statistical noise or rely on multi-server trust assumptions. Fully Homomorphic Encryption (FHE) offers an attractive alternative by enabling exact computation over encrypted data on a single untrusted server, but the high cost of encrypted comparisons has historically made stateful stream processing impractical. We present Oblivious SpaceSaving, a privacy-preserving reformulation of the classical Space-Saving algorithm for fully encrypted execution. Our central idea is the Moving Floor abstraction, which exploits a monotonicity invariant in the summary state to replace repeated magnitude comparisons with equality-based selection against a tracked encrypted floor. We further combine this with parallel victim selection and a hierarchical asynchronous ingestion pipeline, yielding an end-to-end encrypted heavy-hitter architecture that preserves the deterministic accuracy guarantees of the original algorithm. Our design reduces the cost of encrypted updates by up to $2.74\times$ over a naive oblivious baseline and sustains end-to-end encrypted ingestion throughputs of up to 4.30 items/s with sub-second amortized latency. These results show that, with the right algorithmic reformulation, classical streaming summaries can be made practically viable under fully encrypted execution, bringing privacy-preserving stream analytics significantly closer to deployment.

We introduce Confidential Transfers for Multi-Purpose Tokens (Confidential MPTs) on the XRP Ledger, a cryptographic extension of the XLS-33 token standard that enables confidential balances and hidden transfer amounts while preserving public supply verifiability. The protocol replaces plaintext per-account balances with EC–ElGamal ciphertexts and employs non-interactive zero-knowledge proofs to enforce transfer correctness, balance sufficiency, and the invariant OutstandingAmount ≤ MaxAmount without requiring decryption by validators. Confidentiality is scoped to transaction amounts and account balances; sender and receiver identities remain public, preserving XRPL’s account-based execution model. Our design maintains full compatibility with existing MPT semantics: public and confidential balances coexist, issuance rules remain unchanged, and theissuer’s designated second account is treated identically to other holders. The protocol further supports issuer-controlled operations, including freeze and clawback, without weakening supply soundness. To accommodate regulatory and institutional requirements, Confidential MPTs provide cryptographic auditability through an on-chain selective-disclosure model based on multi-ciphertext balance representations and equality proofs, while remaining compatible with simpler issuer-mediated audit models. We present a complete protocol specification, a security analysis under standard discrete-logarithm assumptions, and an open-source reference implementation (mpt-crypto) that realizes the required cryptographic primitives. Experimental evaluation demonstrates that confidential transfers can be verified within XRPL validator performance constraints, with proof sizes and verification costs suitable for production deployment.

This paper presents a security evaluation of the RRSC lightweight stream cipher in its 64-bit and 128-bit variants. The analysis examines the key update process, internal component interactions, and diffusion behavior during initialization, supported by an avalanche study. Based on these observations, several cryptanalytic scenarios are explored, including time-memory-data trade-off attacks, full key-recovery attacks in the known-plaintext setting, and partial key-recovery attacks targeting the linear feedback shift register and nonlinear feedback shift register components. It is shown that the effective key space is reduced from \(2^{128}\) to \(2^{96}\) for the 128-bit variant and from \(2^{64}\) to \(2^{48}\) for the 64-bit variant.

Threshold fully homomorphic encryption (ThFHE) is a multi-party extension of FHE; any subset of at least $T$ out of $N$ parties can decrypt the ciphertexts by combining their decryption shares. Recently, Passelègue and Stehlé (Asiacrypt 2024) presented a ThFHE scheme with polynomially short decryption shares from the ``known-norm'' variant of learning with errors (LWE) assumption, in which the norm of the secret key is leaked to the adversary. While known-norm LWE is reduced from standard LWE, its module extension, known-covariance module-LWE (MLWE), lacks a known reduction from standard MLWE. Hence, extending their ThFHE scheme to the MLWE-based construction remains an open question. In this paper, we address this open problem: We construct a ThFHE scheme with polynomially small decryption shares from standard LWE/MLWE. Our core technique, which we call noise padding, eliminates the need of known-norm variants of LWE. We distribute shares of a padding noise and use them to adjust the distribution of decryption noise so that no information about the secret key is leaked. Furthermore, our ThFHE efficiently realizes arbitrary $T$-out-of-$N$ threshold decryption via simple Shamir secret sharing instead of $\{0,1\}$-linear secret sharing. Hence, the sizes of the keys, ciphertexts and decryption shares in our scheme are compact: they are $O(1)$ w.r.t. the number of parties $N$.

We explore distributed training in a setting where features are held by one party and labels are held by another. In this context, we focus on label Differential Privacy (DP), where the labels require privacy protection from the other party who learns the trained model. Previous approaches struggle to train accurate models in high-privacy settings (i.e. when $\epsilon \leq 1$), or typically require a trusted third party. To eliminate this trusted party while preserving model utility, we present PostScale, a novel Homomorphic Encryption (HE)-based protocol suited for high-privacy regimes with ciphertext multiplicative depth of two. Our protocol is suitable for a wide variety of models in the semi-honest setting and avoids leaking the model architecture as well as costly ciphertext operations like bootstrapping and rotations. We also present a multi-party sampling protocol for generating DP noise, and Hadal, a general-purpose dataflow-based framework for encrypted computation implementing our protocols. Hadal repurposes existing tools for use with HE, including comprehensive performance profiling capabilities, dual execution modes (eager and deferred), graph compiler-based optimization, and hyperparameter tuning. Our techniques achieve model utility similar to centralized DP while reducing communication by over 90% (from 1 TB to 8 GB per batch) and training time by 99% (from 54 minutes to 33 seconds) compared to related work that protects both features and labels. These improvements unlock larger models; we train Bert-tiny of Devlin et al. (2019), with 6.5 MB of parameters, in 20 ms per example in a LAN setting.

We show that there is a discrepancy between the emulated floating-point multiplication in the submission package of the digital signature Falcon and the claimed behavior. In particular, we show that some floating-point products with absolute values the smallest normal positive floating-point number are incorrectly zeroized. However, we show that the discrepancy doesn’t affect the complex fast Fourier transform in the signature generation of Falcon by modeling the floating-point addition, subtraction, and multiplication in CryptoLine. We later implement our own floating-point multiplications in Armv7-M assembly and Jasmin and prove their equivalence with our model, demonstrating the possibility of transferring the challenging verification task (verifying highly-optimized assembly) to the presumably more readable code base (Jasmin).

In code-based cryptography, dual attacks for solving the decoding problem have recently been improved. They are now competitive and beat information set decoders for a significant regime. These recent dual attacks, starting from Carrier et al. (Asiacrypt 2022), work by reducing decoding to an LPN problem where the secret and the noise involve parts of the error vector coming from the decoding problem. However, currently, the analysis of all these dual attacks is heuristic. In the original Asiacrypt 2022 work, a simple LPN modeling was used to carry out the analysis but Meyer-Hilfiger and Tillich (TCC 2023) showed that this assumption could not be used. Consequently, they proposed an alternative analysis based on Fourier theory and on heuristically modeling the weight enumerator of a random linear code as a Poisson variable. The analysis of the newest and most efficient dual attack, doubleRLPN, introduced by Carrier et al. (Eurocrypt 2024) also relies on this technique and on this model. Our main contribution is to devise a variant of doubleRLPN that we can fully prove without using any model. We show that our variant has the same performance, up to polynomial factors, as the original doubleRLPN algorithm. The final algorithm and its analysis are also simpler. Our technique involves flipping the coordinates of the noisy codeword and observing the fine changes in the amount of noise in the related LPN problem to reconstruct the entire error. The analysis is based on the second-order behavior of the bias of the noise which was already used in the original analysis. Secondly, the performance of our algorithm, as it was the case for doubleRLPN, heavily depends on having access to a good code along with an efficient decoder. We instantiate this code by choosing a Cartesian product of a constant (instead of sublinear in the original proposal by Carrier et al.) number of random linear codes. We use a decoder based on blockwise error enumeration that was already used by Guo et al. (Asiacrypt 2014). We show that our approach is optimal up to polynomial (instead of superpolynomial) factors.

To penetrate more rounds with Meet-in-the-Middle (MitM) attack, the neutral words are usually subject to some linear constraints, e.g., Sasaki and Aoki's initial structure technique. At CRYPTO 2021, Dong et al. found the neutral words can be nonlinearly constrained. They introduced a table-based method to precompute and store the solution space of the neutral words, which led to a huge memory complexity. In this paper, we find some nonlinearly constrained neutral words can be solved efficiently by Khovratovich et al.'s triangulation algorithm (TA). Furthermore, motivated by the structured Gaussian elimination paradigm developed by LaMacchia et al. and Bender et al., we improve the TA to deal with the case when there are still many unprocessed equations, but no variable exists in only one equation (the original TA will terminate). Then, we introduce the new MitM attack based on our improved TA, called triangulating MitM attack. As applications, the memory complexities of the single-plaintext key-recovery attacks on 4-/5-round AES-128 are significantly reduced from $2^{80}$ to the practical $2^{24}$ or from $2^{96}$ to $2^{40}$. Besides, a series of new one/two-plaintext attacks are proposed for reduced AES-192/-256 and Rijndael-EM, which are the basic primitives of NIST PQC candidate FAEST. A partial key-recovery experiment is conducted on 4-round AES-128 to verify the correctness of our technique. For AES-256-DM, the memory complexity of the 10-round preimage attack is reduced from $2^{56}$ to $2^{8}$, thus an experiment is also implemented. Without our technique, the impractical memories $2^{80}$ or $2^{56}$ of previous attacks in the precomputation phase will always prevent any kind of (partial) experimental simulations. In the full version, we extend our techniques to sponge functions.

Fully homomorphic encryption (FHE) is a cryptographic scheme that can take ciphertexts as inputs and compute a new ciphertext of a function of the underlying messages without decryption. FHE has been attracting attention along with the growing interest in privacy-preserving technologies. In terms of privacy-preserving technology, deniable encryption is also important. Deniable encryption enables a user, who may be forced to reveal the messages corresponding to the user's public ciphertexts, to lie about which messages the user encrypted. Agrawal et al. (CRYPTO 2021) introduced deniable FHE (DFHE) that combines FHE with deniable encryption, and proposed a transformation from an FHE scheme that satisfies specific special requirements, called special FHE, to a DFHE scheme. They also showed a construction of a special FHE scheme based on the BGV (Brakerski--Gentry--Vaikuntanathan) scheme. However, in the construction by Agrawal et al., one must store all the extensive randomness used for encryption in order to lie, and a bootstrapping operation, which takes a long time to execute, is a bottleneck in execution speed. In this paper, we show that by providing a tighter upper bound on deniability, we can reduce the size of the stored randomness and the required number of bootstrapping in the construction by Agrawal et al. In addition, we show that TFHE (Chillotti et al., J. Cryptol., 2020; Joye, CT-RSA 2024), which is known as a FHE scheme with fast bootstrapping, satisfies the requirements of special FHE, and thus can realize a faster DFHE scheme than the BGV-based construction.