International Association
for Cryptologic Research

We show that the widely-used Schnorr signature scheme meets existential unforgeability under chosen-message attack (EUF-CMA) in the random oracle model (ROM) if the circular discrete-logarithm (CDL) assumption holds in the underlying group. CDL is a new, non-interactive and falsifiable variant of the discrete-logarithm (DL) assumption that we introduce. Our reduction is completely tight, meaning the constructed adversary against CDL has essentially the same running time and success probability as the assumed forger. This serves to justify the size of the underlying group for Schnorr signatures used in practice. To our knowledge, we are the first to exhibit such a reduction. Indeed, prior work required interactive and non-falsifiable assumptions (Bellare and Dai, INDOCRYPT 2020) or additional idealized models beyond the ROM like the algebraic group model (Fuchsbauer, Plouviez and Seurin, EUROCRYPT 2020). To further demonstrate the applicability of CDL, we show that Sparkle+ (Crites, Komlo and Maller, CRYPTO 2023), a threshold signing scheme for Schnorr, is tightly secure (under static corruptions) assuming CDL. Finally, we justify CDL by showing it holds in two carefully chosen idealized models that idealize different aspects of the assumption.

Our work minimizes interaction in secure computation, addressing the high cost of communication rounds, especially with many clients. We introduce One-shot Private Aggregation $\mathsf{OPA}$, enabling clients to communicate only once per aggregation evaluation in a single-server setting. This simplifies dropout management and dynamic participation, contrasting with multi-round protocols like Bonawitz et al. (CCS'17) (and subsequent works) and avoiding complex committee selection akin to YOSO. $\mathsf{OPA}$'s communication behavior \emph{closely} mimics learning-in-the-clear where each client party speaks only once. $\mathsf{OPA}$, built on LWR, LWE, class groups, and DCR, ensures single-round communication for all clients while also achieving sub-linear overhead in the number of clients, making it asymptotically efficient and practical. We achieve malicious security with abort and input validation to defend against poisoning attacks, which are particularly relevant in Federated Learning, where adversaries attempt to manipulate the gradients to degrade model performance or introduce biases. We build two flavors of $\mathsf{OPA}$ (1) from (threshold) key homomorphic PRF and (2) from seed homomorphic PRG and secret sharing. The threshold Key homomorphic PRF addresses shortcomings observed in previous works that relied on DDH and LWR in the work of Boneh~\textit{et al.}(CRYPTO, 2013), marking it as an independent contribution to our work. Our other contributions include new constructions of (threshold) key-homomorphic PRFs and seed-homomorphic PRGs that are secure under the LWE, DCR Assumption, and other Class Groups of Unknown Order.

FROST and its variants are state-of-the-art protocols for threshold Schnorr signatures that are used in real-world applications. While static security of these protocols has been shown by several works, the security of these protocols under adaptive corruptions—where an adversary can choose which parties to corrupt at any time based on information it learns during protocol executions—has remained a notorious open problem that has received renewed attention due to recent standardization efforts for threshold schemes. We show adaptive security (without erasures) of FROST and several variants under different corruption thresholds and computational assumptions. Let n be the total number of parties, t+1 the signing threshold, and t_c an upper bound on the number of corrupted parties. 1. We prove adaptive security when t_c = t/2 in the random oracle model (ROM) based on the algebraic one-more discrete logarithm assumption (AOMDL)—the same conditions under which FROST is proven statically secure. 2. We introduce the low-dimensional vector representation (LDVR) problem, parameterized by t_c, t, and n, and prove adaptive security in the algebraic group model (AGM) and ROM based on the AOMDL assumption and the hardness of the LDVR problem for the corresponding parameters. In some regimes (including some t_c >t/2) we show the LDVR problem is unconditionally hard, while in other regimes (in particular, when t_c = t) we show that hardness of the LDVR problem is necessary for adaptive security to hold. In fact, we show that hardness of the LDVR problem is necessary for proving adaptive security of a broad class of threshold Schnorr signatures.

The leader election problem requires a set of $n$ parties, out of which up to $t$ can be Byzantine, to elect a leader uniformly at random such that no two parties disagree on the elected leader and an honest leader is elected with constant probability. The Scalable Leader Election protocol published in SODA'2006 is an important breakthrough in solving this problem efficiently for all but $o(1)$ of the parties. They achieve a protocol for $t < (\frac{1}{3} - \epsilon)n$ (for $\epsilon = o(1)$) in the full-information setting such that every party only sends $\polylog(n)$ bits. In this paper, we revisit their work and show that there are subtleties in the protocol that are not dealt with in the analysis. In particular, two mechanisms related to ``silencing'' parties and dealing with ``bad nodes'' are at odds with each other, which is why the existing analysis is insufficient. We present these concerns in detail and subsequently present a modification to their protocol with a corresponding analysis to solve leader election with the desired metrics.

Continuous Group Key Agreement (CGKA) is a primitive with which members of a group can continuously establish shared keys. With every interaction, these members also update their individual, local secrets such that temporary corruptions of these secrets only affect the security of shared keys established shortly before (Forward Security; FS) and after the corruption (Post-Compromise Security; PCS). Due to these interactive updates–possibly enriched by dynamic group membership changes–, CGKA is a very powerful but also very complex primitive. In this work, we limit the power of CGKA to identify and analyze its core components. More concretely, we consider the case that all members of a group are always either senders or receivers. Thus, the interaction is strictly unidirectional from the former to the latter: a group of senders Alice establishes shared keys with a group of receivers Bob. With every shared key, Alice updates her local state to achieve FS and PCS; when receiving an established key, each Bob also updates their local state to achieve FS. This notion naturally lifts the so called Unidirectional Ratcheted Key Exchange concept (Bellare et al., Crypto 2017; Poettering and Rösler, Crypto 2018) to the group setting and, thereby, captures and generalizes Signal's Sender Key Mechanism, which is the core of WhatsApp and Signal's group chat protocols. We modularize this concept of Group Unidirectional RKE (GURKE) by considering either single or multiple senders, single or multiple receivers, and static or dynamic membership on each of both sides of the group. To instantiate these new primitives, we develop a building block called Updatable Broadcast KEM (UB-KEM). Using UB-KEM, our GURKE constructions for static groups only use standard Key Encapsulation Mechanisms (KEMs) and induce only a constant communication overhead. Our GURKE constructions for dynamic groups are based on general Non-Interactive Key Exchange (NIKE) and offer a constant communication overhead as long as the set of members is unchanged; only for adding and removing users, a communication overhead logarithmic in the group size is induced. We discuss the benefits of replacing the Sender Key Mechanism in Signal and WhatsApp with our constructions, and demonstrate their practicality with a performance evaluation of our proof of concept UB-KEM implementation.

There is a gap between the security of constrained PRFs required in some applications and the security provided by existing definitions. This gap is typically patched by only considering nonadaptive security or manually mixing the CPRF with a random oracle (implicitly constructing a new CPRF) to achieve adaptive security. We fill this gap with a new definition for constrained PRFs with strong adaptive security properties and proofs that it is achieved by practical constructions based on the cascade PRF (which generalized GGM) and AMAC. We apply the definition for analyzing searchable symmetric encryption and puncturable key wrapping.

One of the main shortcomings of classical distributed cryptography is its reliance on a certain fraction of participants remaining honest. Typically, honest parties are assumed to follow the protocol and not leak any information, even if behaving dishonestly would benefit them economically. More realistic models used in blockchain consensus rely on weaker assumptions, namely that no large coalition of corrupt parties exists, although every party can act selfishly. This is feasible since, in a consensus protocol, active misbehavior can be detected and ``punished'' by other parties. However, ``information leakage'', where an adversary reveals sensitive information via, e.g., a subliminal channel, is often impossible to detect and, hence, much more challenging to handle. A recent approach to address this problem was proposed by Dziembowski, Faust, Lizurej, and Mielniczuk (ACM CCS 2024), who introduced a new notion called \emph{secret sharing with snitching}. This primitive guarantees that as long as no large coalition of mutually trusting parties exists, every leakage of the shared secret produces a ``snitching proof'' indicating that some party participated in the illegal secret reconstruction. This holds in a very strong model, where mutually distrusting parties use an MPC protocol to reconstruct any information about the shared secret. Such a ``snitching proof'' can be sent to a smart contract (modeled as a ``judge'') deployed on the blockchain, which punishes the misbehaving party financially. In this paper, we extend the results from the work of CCS'24 by addressing its two main shortcomings. Firstly, we significantly strengthen the attack model by considering the case when mutually distrusting parties can also rely on a trusted third party (e.g., a smart contract). We call this new primitive \emph{strong} secret sharing with snitching (SSSS). We present an SSSS protocol that is secure in this model. Secondly, unlike in the construction from CCS'24, our protocol does not require the \emph{honest} parties to perform any MPC computations on hash functions. Besides its theoretical interest, this improvement is of practical importance, as it allows the construction of SSSS from any (even very "MPC-unfriendly") hash function.

Modern efficient secure multi-party computation (MPC) protocols typically follow an offline-online design, where offline protocols produce a sufficient amount of correlated randomness that would be consumed during the online phases. The past decades have witnessed maturing of efficient online protocols, for computing circuits over either arbitrary finite fields or rings $\mathbb{Z}_{p^k}$. In particular, protocols tailored for $\mathbb{Z}_{2^k}$ arithmetic have achieved better concrete efficiency in most real-life applications, as it naturally captures modern CPU architectures. On the other hand, a recent paradigm of {\em pseudorandom correlation generator} (PCG) initiated by Boyle et al. (CCS'18, Crypto'19) opens a door to efficient preprocessing with sublinear communication. Since then, PCGs have been extensively studied and developed to produce various types of correlations required from online protocols. Although Li et al. (EuroCrypt'25) recently put a significant step forward and propose efficient PCGs for arbitrary finite fields, the current state of PCGs for rings is not satisfying at all. Towards the great demand for efficiently generating correlations over rings, we investigate PCGs for general Galois rings, which simultaneously unify finite fields and integer rings modulo $p^k$. In summary, we establish the following results: (i) We generalize the state-of-the-art PCG constructions for oblivious linear evaluations (OLE) over Galois fields to {\em arbitrary Galois rings}, basing on Galois theory and the Hensel lift. Moreover, our PCGs for Galois rings are as efficient as PCGs for fields. Concretely, for $mN$ OLE correlations over $\mathbb{Z}_{2^k}$, we require $O(m\log{N})$ communication and $O(m^2N\log{N})$ computation, where $m$ is an arbitrary integer $\geq 2$. In comparison, to our best knowledge, previous approaches incur communication at least linear in $N$. (ii) We extend the above OLE construction to provide various types of correlations over any Galois ring. One of the fascinating applications is an efficient PCG for two-party SPD$\mathbb{Z}_{2^k}$ authenticated multiplication triples (Crypto'18). For $mN$ SPD$\mathbb{Z}_{2^k}$ triples, our approach requires only $O(m\log{N})$ communication and $O(m^2N\log{N})$ computation. Concrete evaluations show that our method significantly outperforms existing schemes based on homomorphic encryption. (iii) In addition, our PCGs for Galois rings also enable multi-party multiplication triple generation, yielding the first efficient MPC protocol for arithmetic circuits over $\mathbb{Z}_{2^k}$ with \emph{silent} and \emph{sublinear} preprocessing. Additional applications include circuit-dependent preprocessing and matrix multiplication triples, etc, which are of independent interest.

The matrix code equivalence problem consists, given two matrix spaces $\mathcal{C},\mathcal{D} \subset \Fq^{m\times n}$ of dimension $k$, in finding invertible matrices $P\in\mathrm{GL}_m(\mathbb{F}_q)$ and $Q\in\mathrm{GL}_n(\mathbb{F}_q)$ such that $\mathcal{D}=P\mathcal{C} Q^{-1}$. Recent signature schemes such as MEDS and ALTEQ relate their security to the hardness of this problem. Recent works by Narayanan, Qiao and Tang on the one hand and by Ran and Samardjiska on the other hand tackle this problem. The former is restricted to the ``cubic'' case $k = m =n$ and succeeds in $\widetilde{\mathcal{O}}(q^{\frac k 2})$ operations. The latter is an algebraic attack on the general problem whose complexity is not fully understood and which succeeds only on $\mathcal{O}(1/q)$ instances. We present a novel algorithm which solves the problem in the general case. Our approach consists in reducing the problem to the matrix code conjugacy problem, \emph{i.e.} the case $P=Q$. For the latter problem, similarly to the permutation code equivalence problem in Hamming metric, a natural invariant based on the \emph{Hull} of the code can be used. Next, the equivalence of codes can be deduced using a usual list collision argument. For $k=m=n$, our algorithm achieves the same time complexity as Narayanan \emph{et al.} but with a lower space complexity. Moreover, ours extends to a much broader range of parameters.

Quasi-cyclic moderate-density parity check (QC-MDPC) code-based encryption schemes under iterative decoders offer highly-competitive performance in quantum-resistant cryptography, but their IND-CCA2 security is an open question because the decoding failure rate (DFR) of these algorithms is not well-understood. The DFR decreases extremely rapidly as the blocklength increases, then decreases much more slowly in regimes known as the waterfall and error floor, respectively. The waterfall behavior is rather well predicted by a Markov model introduced by Sendrier and Vasseur \cite{SV19} but it does not capture the error floor behavior. Assessing precisely for which blocklength this error floor begins is crucial for the low DFRs sought the context of cryptography. By enriching the Markov model \cite{SV19} with information about near codewords we are able to capture this error-floor behavior for a step-by-step decoder. This decoder displays worse decoding performance than the parallel decoders used in practice but is more amenable to a Markov chain analysis. We already capture the error floor with a simplified model. A refined model taking into account certain structural features of the secret key is even able to give accurate key dependent predictions both in the waterfall and error floor regimes. We show that the error floor behavior is governed by convergence to a near codeword when decoding fails. We ran this model for the BIKE cryptosystem with this simpler step by step decoder to better ascertain whether the DFR is low enough to achieve IND-CCA2 security. Our model gives a DFR below $2^{-131.2}$, using a block length $r=13477$ instead of the BIKE parameter $r=12323$. This paper gives some strong evidence that the IND-CCA2 requirement can be met at the cost of a modest increase of less than 10\% in the key size.

The dual attacks on the Learning With Errors (LWE) problem are currently a subject of controversy. In particular, the results of [28], which claim to significantly lower the security level of Kyber [35], a lattice-based cryptosystem currently being standardized by NIST, are not widely accepted. The analysis behind their attack depends on a series of assumptions that, in certain scenarios, have been shown to contradict established theorems or well-tested heuristics [19]. In this paper, we introduce a new dual lattice attack on LWE, drawing from ideas in coding theory. Our approach revisits the dual attack proposed by [28], replacing modulus switching with an efficient decoding algorithm. This decoding is achieved by generalizing polar codes over Z/qZ, and we confirm their strong distortion properties through benchmarks. This modification enables a reduction from small-LWE to plain-LWE, with a notable decrease in the secret dimension. Additionally, we replace the enumeration step in the attack by assuming the secret is zero for the portion being enumerated, iterating this assumption over various choices for the enumeration part. We make an analysis of our attack without using the flawed independence assumptions used in [28] and we fully back up our analysis with experimental evidences. Lastly, we assess the complexity of our attack on Kyber; showing that the security levels for Kyber-512/768/1024 are 3.5/11.9/12.3 bits below the NIST requirements (143/207/272 bits) in the same nearest-neighbor cost model as in [35,28]. All in all the cost of our attack matches and even slightly beat in some cases the complexities originally claimed by the attack of [28].

Oblivious Pseudorandom Functions (OPRFs) are fundamental cryptographic primitives essential for privacy-enhancing technologies such as private set intersection, oblivious keyword search, and password-based authentication protocols. We present the first fully adaptive, partially oblivious threshold pseudorandom function that supports proactive key refresh and provides composable security under the One-More Gap Diffie-Hellman assumption in the random oracle model. Our construction is secure with respect to a new ideal functionality for OPRFs that addresses three critical shortcomings of previous models--specifically, key refresh and non-verifiability issues that rendered them unrealizable. In addition, we identify a gap in a prior work's proof of partial obliviousness and develop a novel proof technique to salvage their scheme.

Randomness is a fundamental requirement in cryptographic systems, enabling secure encryption, commitments, and zero-knowledge proofs. However, real-world randomness sources often suffer from weaknesses that adversaries can exploit, leading to significant security vulnerabilities. While deterministic randomness extraction from a single min-entropy source is impossible, two-source extractors provide a robust solution by generating nearly uniform randomness from two independent weak sources. Moreover, cryptographic systems must also be resilient to leakage and tampering attacks, necessitating the development of non-malleable two-source extractors. In this work, we construct a two-source non-malleable extractor in the Common Reference String (CRS) model, where a random low-degree polynomial is sampled once and made accessible to independent random sources, the distinguisher, and the tamperer. Our extractor requires only linear min-entropy in both sources and doesn't rely on strong computational assumptions, in contrast to prior constructions requiring computational assumptions such as sub-exponential hardness of the Decisional Diffie-Hellman (DDH) problem. Notably, our construction builds upon and relies on the recent breakthrough proof of the polynomial Freiman-Ruzsa conjecture. Our results advance the state of non-malleable cryptographic primitives, with applications in secure storage, leakage-resilient cryptography, and privacy amplification. By eliminating the need for strong computational hardness assumptions, our techniques provide a more foundational and widely applicable method for randomness extraction.

Several recent works have shown lower bounds on the communication cost of secure messaging protocols based on specific primitives. However, these bounds no longer apply if stronger primitives are allowed, such as succinct multi-party non-interactive key exchange (SMNIKE). This is a setup-free primitive where all messages are independent of the number $N$ of parties. Boneh and Zhandry (BZ, CRYPTO'14) present an iO-based MNIKE whose setup (or one message from a designated party) depends on $N$, but all other messages are short. SMNIKE is a strengthening of their primitive that forgoes the setup and where no message depends on $N$, thereby enabling applications in secure messaging. Jain and Jin (JJ, FOCS'22) build indistinguishability obfuscation (iO) for Turing machines with unbounded input length, opening the possibility of SMNIKE via iO and puncturable PRFs (PPRFs). Unfortunately, the punctured keys of known PPRFs grow with their input length $n$; e.g., for the Goldreich--Goldwasser--Micali (GGM) PPRF they have size $n \lambda$. We introduce succinct PPRFs (SPPRFs), a weakened form of PPRFs satisfying a relaxed correctness notion. Notably, SPPRFs have punctured keys whose size is independent of the input size, as long as the punctured point has a short description. We then combine SPPRFs with JJ to show that a variant of the BZ construction is an SMNIKE. At the heart of our SPPRF construction is a novel memory-tight reduction for GGM. While the original GGM reduction requires space $q \lambda$, our proof only needs $5 \lambda$ memory, where $q$ is the number of PRF queries. Our technique allows to show that GGM is an SPPRF, and also that GGM as a (standard) PRF has a memory-tight reduction against adversaries that do not repeat oracle queries, a restriction we prove to be inherent.

This paper studies the security of {\em key derivation functions} (KDFs), a central class of cryptographic algorithms used to derive {\em multiple} independent-looking keys (each associated with a particular context) from a {\em single} secret. The main security requirement is that these keys are pseudorandom (i.e., the KDF is a pseudorandom function). This paper initiates the study of an additional security property, called {\em key control} (KC) security, first informally put forward in a recent update to NIST Special Publication (SP) 800-108 standard for KDFs. Informally speaking, KC security demands that, given a {\em known} key, it is hard for an adversary to find a context that forces the KDF-derived key for that context to have a property that is specified a-priori and is hard to satisfy (e.g., that the derived key consists mostly of 0s, or that it is a weak key for a cryptographic algorithm using it). We provide a rigorous security definition for KC security, and then move on to the analysis of the KDF constructions specified in NIST SP 800-108. We show, via security proofs in the random oracle model, that the proposed constructions based on XOFs or hash functions can accommodate for reasonable security margins (i.e., 128-bit security) when instantiated from KMAC and HMAC. We also show, via attacks, that all proposed block-cipher based modes of operation (while implementing mitigation techniques to prevent KC security attacks affecting earlier version of the standard) only achieve {\em at best} 72-bit KC security for 128-bit blocks, as with AES.

We present the first construction of multiparty distributed point functions based on one-way functions, where the share sizes remain sublinear in the domain size and grow only polynomially with the number of parties. In contrast, existing multiparty distributed point function constructions in Minicrypt have share sizes that grow exponentially with the number of parties.

Non-interactive zero-knowledge (NIZK) proofs enable a prover to convince a verifier of an NP statement’s validity using a single message, without disclosing any additional information. These proofs are widely studied and deployed, especially in their succinct form, where proof length is sublinear in the size of the NP relation. However, efficient succinct NIZKs typically require an idealized setup, such as a a common reference string, which complicates real-world deployment. A key challenge is developing NIZKs with simpler, more transparent setups. A promising approach is the random-oracle (RO) methodology, which idealizes hash functions as public random functions. It is commonly believed that UC NIZKs cannot be realized using a non-programmable global RO—the simplest incarnation of the RO as a form of setup—since existing techniques depend on the ability to program the oracle. We challenge this belief and present a methodology to build UC-secure NIZKs based solely on a global, non-programmable RO. By applying our framework we are able to construct a NIZK that achieves witness-succinct proofs of logarithmic size, breaking both the programmability barrier and polylogarithmic proof size limitations for UC-secure NIZKs with transparent setups. We further observe that among existing global RO formalizations put forth by Camenisch et al. (Eurocrypt 2018), our choice of setup is necessary to achieve this result. From the technical standpoint, our contributions span both modeling and construction. We leverage the shielded (super-poly) oracle model introduced by Broadnax et al. (Eurocrypt 2017) to define a UC NIZK functionality that can serve as a drop-in replacement for its standard variant—it preserves the usual soundness and zero-knowledge properties while ensuring its compositional guarantees remain intact. To instantiate this functionality under a non-programmable RO setup, we follow the framework of Ganesh et al. (Eurocrypt 2023) and provide new building blocks for it, around which are some of our core technical contributions: a novel polynomial encoding technique and the leakage analysis of its companion polynomial commitment, based on Bulletproofs-style folding. We also provide a second construction, based on a recent work by Chiesa and Fenzi (TCC 2024), and show that it achieves a slightly weaker version of the NIZK functionality.

Fully Homomorphic Encryption (FHE) enables computation on encrypted data without decryption, demonstrating significant potential for privacy-preserving applications. However, FHE faces several challenges, one of which is the significant plaintext-to-ciphertext expansion ratio, resulting in high communication overhead between client and server. The transciphering technique can effectively address this problem by first encrypting data with a space-efficient symmetric cipher, then converting symmetric ciphertext to FHE ciphertext without decryption.Numerous FHE-friendly symmetric ciphers and transciphering methods have been developed by researchers, each with unique advantages and limitations. These often require extensive knowledge of both symmetric cryptography and FHE to fully grasp, making comparison and selection among these schemes challenging. To address this, we conduct a comprehensive survey of over 20 FHE-friendly symmetric ciphers and transciphering methods, evaluating them based on criteria such as security level, efficiency, and compatibility. We have designed and executed experiments to benchmark the performance of the feasible combinations of symmetric ciphers and transciphering methods across various application scenarios. Our findings offer insights into achieving efficient transciphering tailored to different task contexts. Additionally, we make our example code available open-source, leveraging state-of-the-art FHE implementations.

It is a widely accepted standard practice to implement cryptographic software so that secret inputs do not influence the cycle count. Software following this paradigm is often referred to as “constant-time” software and typically involves following three rules: 1) never branch on a secret-dependent condition, 2) never access memory at a secret-dependent location, and 3) avoid variable-time arithmetic operations on secret data. The third rule requires knowledge about such variable-time arithmetic instructions, or vice versa, which operations are safe to use on secret inputs. For a long time, this knowledge was based on either documentation or microbenchmarks, but critically, there were never any guarantees for future microarchitectures. This changed with the introduction of the data-operand-independent-timing (DOIT) mode on Intel CPUs and, to some extent, the data-independent-timing (DIT) mode on Arm CPUs. Both Intel and Arm document a subset of their respective instruction sets that are intended to leak no information about their inputs through timing, even on future microarchitectures if the CPU is set to run in a dedicated DOIT (or DIT) mode.In this paper, we present a principled solution that leverages DOIT to enable cryptographic software that is future-proof constant-time, in the sense that it ensures that only instructions from the DOIT subset are used to operate on secret data, even during speculative execution after a mispredicted branch or function return location. For this solution, we build on top of existing security type systems in the Jasmin framework for high-assurance cryptography.We then use our solution to evaluate the extent to which existing cryptographic software built to be “constant-time” is already secure in this stricter paradigm implied by DOIT and what the performance impact is to move from constant-time to future-proof constant-time.

The topic of verifying postquantum cryptographic software has never been more pressing than today between the new NIST postquantum cryptosystem standards being finalized and various countries issuing directives to switch to postquantum or at least hybrid cryptography in a decade. One critical issue in verifying lattice-based cryptographic software is range-checking in the finite-field arithmetic assembly code which occurs frequently in highly optimized cryptographic software. For the most part these have been handled by Satisfiability Modulo Theory (SMT) but so far they mostly are restricted to Montgomery arithmetic and 16-bit precision. We add semi-automatic range-check reasoning capability to the CryptoLine toolkit via the Integer Set Library (wrapped via the python package islpy) which makes it easier and faster to verify more arithmetic crypto code, including Barrett and Plantard finite-field arithmetic, and show experimentally that this is viable on production code.

AES New Instructions (AES-NI) is a set of hardware instructions introduced by Intel to accelerate AES encryption and decryption, significantly improving efficiency across various cryptographic applications. While AES-NI effectively mitigates certain side-channel attacks, its resilience against faults induced by active or malicious fault injection remains unclear.In this paper, we conduct a comprehensive security analysis of AES-NI. By analyzing the opcodes of AES-NI, we identify six pairs of instructions with only a single-bit difference, making them susceptible to bit-flip-type attacks. This vulnerability allows attackers to recover AES keys in both Electronic Codebook (ECB) and Cipher Block Chaining (CBC) modes. We introduce a novel Opcode-based Fault Analysis (OFA) method, employing Gaussian elimination to reduce the search space of the last round key. In particular, with one pair of correct and faulty ciphertexts, OFA can reduce the key search space to 232 for a 128-bit key length. To further reduce the key space for AES-192 and AES-256, we propose the Enhanced Opcode-based Fault Analysis (EOFA), which, compared to exhaustive search, reduces the key space by factors of 2160 and 2192, respectively.Finally, we demonstrate the feasibility of our findings by conducting physical endto- end attacks. Specifically, Rowhammer is leveraged to flip vulnerable opcodes and OFA as well as EOFA techniques are applied to recover secret keys from AES implementations. Our experimental results for AES-ECB-128, AES-ECB-192, and AES-CBC-128 demonstrate that key recovery can be efficiently achieved within 1.03 to 1.36 hours, varying with the cipher. This work highlights a critical vulnerability in AES-NI and outlines a new and novel pathway for fault-based attacks against modern cryptographic implementations.

Implementation-level countermeasures like masking can be applied to any cryptographic algorithm in order to mitigate Differential Power Analysis (DPA). Leveraging re-keying with a Leakage-Resilient PRF (LR-PRF) is an alternative countermeasure that requires a change of primitive. Both options rely on different security mechanisms: signal-to-noise ratio amplification for masking, signal reduction for LRPRFs. This makes their general comparison difficult and suggests the investigation of relevant case studies to identify when to use one or the other as an interesting research direction. In this paper, we provide such a case study and compare the security that can be obtained by using an unprotected hardware coprocessor, to be integrated into a leakage-resilient PRF, and a certified one, protected with implementation-level countermeasures. Both are available on “commercial off-the-shelf” devices and could be used for lightweight IoT applications. We first perform an in-depth analysis of these targets. It allows us to put forward the different evaluation challenges that they raise, and the similar to slightly better cost vs. security tradeoff that the leakage-resilient PRF offers in our experiments. We then discuss the advantages and limitations of both types of countermeasures. While there are contexts where the higher flexibility of masking is needed, we conclude that there are also applications that would strongly benefit from the simplicity of the LR-PRF’s design and evaluation. Positing that the lack of standards is the main impediment to their more widespread deployment, we therefore hope that our results can motivate such standardization efforts.

Transciphering (or Hybrid-Homomorphic Encryption, HHE) is an established technique for avoiding ciphertext expansion in HE applications, saving communication and storage resources. Recently, it has also been shown to be a fundamental component in the practical construction of HE-based multi-party computation (MPC) protocols, being used both for input data and intermediary results (Smart, IMACC 2023). In these protocols, however, ciphers are used with keys that are jointly generated by multiple (possibly malicious) parties, which may require additional security assumptions that have been so far overlooked in the HHE literature. In this paper, we formalize this issue as a security against related-key attacks (RKA) problem and provide efficient solutions for it. We start by presenting an efficient method for homomorphically evaluating Mixed-Filter-Permutator (MFP) ciphers in leveled mode, enabling speedups of up to thousands of times compared to previous literature. For the multi-party scenario, we focus specifically on the Margrethe cipher (Hoffmann et al., INDOCRYPT 2023). We show that, contrary to other commonly used HHE ciphers (e.g. FLIP), Margrethe is out-of-the-box secure for any protocols that allow malicious parties to learn up to two related key streams, enabling security for the vast majority of static MPC protocols. For other cases, we quantify the loss of security based on the number of related key streams (which often depends on the number of malicious parties and specific protocol). Performance-wise, our implementation of Margrethe takes just 3.9 ms to transcipher 4-bit messages, being significantly faster than the state of the art in terms of latency.

Hardware intellectual property (IP) blocks have been subjected to various forms of confidentiality and integrity attacks in recent years due to the globalization of the semiconductor industry. System-on-chip (SoC) designers are now considering a zero-trust model for security, where an IP can be attacked at any stage of the manufacturing process for piracy, cloning, overproduction, or malicious alterations. Hardware redaction has emerged as a promising countermeasure to thwart confidentiality and integrity attacks by untrusted entities in the globally distributed supply chain. However, existing redaction techniques provide this security at high overhead costs, making them unsuitable for real-world implementation. In this paper, we propose HIPR, a fine-grain redaction methodology that is robust, scalable, and incurs significantly lower overhead compared to existing redaction techniques. HIPR redacts security-critical Boolean and sequential logic from the hardware design, performs interconnect randomization, and employs multiple overhead optimization steps to reduce overhead costs. We evaluate HIPR on open-source benchmarks and reduce area overheads by 1 to 2 orders of magnitude compared to state-of-the-art redaction techniques without compromising security. We also demonstrate that the redaction performed by HIPR is resilient against conventional functional and structural attacks on hardware IPs. The redacted test IPs used to evaluate HIPR are available at: https://github.com/UF-Nelms-IoT-Git-Projects/HIPR.

In this work, we introduce ToFA, the first fault attack (FA) strategy that attempts to leverage the classically well-known idea of impossible differential cryptanalysis to mount practically verifiable attacks on bit-oriented ciphers like GIFT and BAKSHEESH. The idea stems from the fact that truncated differential paths induced due to fault injection in certain intermediate rounds of the ciphers lead to active SBox-es in subsequent rounds whose inputs admit specific truncated differences. This leads to a (multi-round) impossible differential distinguisher, which can be incrementally leveraged for key-guess elimination via partial decryption. The key-space reduction further exploits the multi-round impossibility, capitalizing on the relations due to the quotient-remainder (QR) groups of the GIFT and BAKSHEESH linear layer, which increases the filtering capability of the distinguisher. Moreover, the primary observations made in this work are independent of the actual SBox. Clock glitch based fault attacks were mounted on 8-bit implementations of GIFT- 64/GIFT-128 using a ChipWhisperer Lite board on an 8-bit ATXmega128D4-AU micro-controller. Unique key recovery was achieved for GIFT-128 with 3 random byte faults, while for GIFT-64, key space was reduced to 232, the highest achievable for GIFT-64, with a single level fault due to its key-schedule. To the best of our knowledge, this work also reports the highest fault injection penetration for any variant of GIFT and BAKSHEESH. Finally, this work reiterates the role of classical cryptanalysis strategies in fault vulnerability assessment by showcasing the most efficient fault attacks on GIFT.

In this paper we provide new theoretical and empirical evidences that gradient-based deep learning profiling attacks (DL-SCA) suffer from masking schemes. This occurs through an initial stall of the learning process: the so-called plateau effect. To understand why, we derive an analytical expression of a DL-SCA model targeting simulated traces which enables us to study an analytical expression of the loss. By studying the loss landscape of this model, we show that not only do the magnitudes of the gradients decrease as the order of masking increases, but the loss landscape also exhibits a prominent saddle point interfering with the optimization process. From these observations, we (1) propose the usage of a second-order optimization algorithm mitigating the impact of low-gradient areas. In addition, we show how to leverage the intrinsic sparsity of valuable information in SCA traces to better pose the DL-SCA problem. To do so, we (2) propose to use the implicit regularization properties of the sparse mirror descent. These propositions are gathered in a new publicly available optimization algorithm, Scoop. Scoop combines second-order derivative of the loss function in the optimization process, with a sparse stochastic mirror descent. We experimentally show that Scoop pushes further the current limitations of DL-SCA against simulated traces, and outperforms the state-of-theart on the ASCADv1 dataset in terms of number of traces required to retrieve the key, perceived information and plateau length. Scoop also performs the first nonworst- case attack on the ASCADv2 dataset. On simulated traces, we show that using Scoop reduces the DL-SCA time complexity by the equivalent of one masking order.

Bit-wise Fully Homomorphic Encryption schemes like FHEW and TFHE offer efficient functional bootstrapping, enabling concurrent function evaluation and noise reduction. While advantageous for secure computations, these schemes suffer from high data expansion, posing significant performance challenges in practical ap- plications due to massive ciphertexts. To address these issues, we propose VeloFHE, a CUDA-accelerated design to enhance the efficiency of FHEW and TFHE schemes on GPUs. We develop a novel hybrid four-step Number Theoretic Transform (NTT) approach for fast polynomial multiplication. By decomposing large-scale NTTs into highly parallelizable submodules, incorporating cyclic and negacyclic convolutions, and introducing several memory-oriented optimizations, we significantly reduce both the computational complexity and memory requirements. For blind rotation, besides the gadget decomposition approach, we also apply a recent proposed modulus raising technique to both schemes to alleviate memory pressure. We further optimize it by refining computational flow to reduce noise from scaling and maintain accumulator compatibility. For key switching, we address input-output parallelism mismatches, and offloading suitable computations to the CPU, effectively hiding latency through asynchronous execution. Additionally, we explore batching in bootstrapping, de- veloping a general framework that accommodates both schemes with either gadget decomposition or modulus raising method.Our experimental results demonstrate significant performance improvements. The proposed NTT implementation shows over 35% improvement compared to recent GPU implementations. On an RTX 4090 GPU, we achieve speedups of 371.86x and 390.44x for FHEW and TFHE gate bootstrapping, respectively, compared to OpenFHE running on a 48-thread CPU at a 128-bit security level. The corresponding throughputs are 7,007 and 11,378 operations per second. Furthermore, relative to the state-of-the-art GPU implementation [XLK+25], our approach provides speedups of 2.56x, 2.24x, and 2.33x for TFHE gate bootstrapping, homomorphic evaluation of arbitrary functions, and homomorphic flooring operation, respectively. Our VeloFHE surpasses some current hardware designs, offering an effective solution for more practical and efficient privacy-preserving computations.

Trusted Execution Environments (TEEs) have become a pivotal technology for securing a wide spectrum of security-sensitive applications. With modern computing systems shifting to heterogeneous architectures, integrating TEE support into these systems is paramount. One promising line of research has proposed leveraging FPGA technology to provide promising TEE solutions. Despite their potential, current implementations of FPGA-based TEEs have a set of drawbacks. Some solutions (i.e., MeetGo and ShEF) prioritize the secure loading of reconfigurable modules but lack compatibility with established legacy TEE specifications and services. On the other hand, those that aim to establish legacy compatibility (i.e., TEEOD and BYOTee) fail to fully utilize the dynamic reconfigurability and parallel processing capabilities inherent in FPGAs. In this context, we introduce Trusted Reconfigurable Execution Environments (TREE), a novel framework that fulfills the gaps existing in current FPGA-based TEE approaches. TREE enables system designers to fully leverage the reconfigurability capabilities of FPGAs without compromising compatibility with existing TEE specifications. Our reference TREE implementation ensures secure execution of user-customized hardware, legacy software trusted applications (TAs), and TAs that combine both custom hardware and software components, by fully exploiting the FPGA’s dynamic partial reconfiguration capabilities. TREE’s root of trust relies on conventional SoC-FPGA mechanisms including secure initial reconfiguration and memory protection, to ensure the initial bitstream integrity is kept after loaded and that reconfiguration access is restricted to the FPGA fabric after boot. Additionally, TREE provides essential TEE services within the FPGA fabric, including secure storage and cryptographic functions, enabling TAs to securely store sensitive data and perform critical operations in an isolated environment. Our evaluation on an entry-level FPGA, involved assessing TREE using microbenchmarks and real-world applications to compare its hardware costs and performance speedups against OP-TEE. The results showed that TREE’s hardware costs are minimal, while it achieves significant performance speedups, especially when compared to hardware TAs. For empirical demonstrations, we assess two real-world TA examples on TREE: an access control authenticator and a Bitcoin wallet.

Compared to elliptic curve cryptography, a primary drawback of latticebased schemes is the larger size of their public keys and ciphertexts. A common procedure for compressing these objects consists essentially of dropping some of their least significant bits. Albeit effective for compression, there is a limit to the number of bits to be dropped before we get a noticeable decryption failure rate (DFR), which is a security concern. To address this issue, this paper presents a family of error-correction codes that, by allowing an increased number of dropped bits while preserving a negligible DFR, can be used for both ciphertext and publickey compression in modern lattice-based schemes. To showcase the impact and practicality of our proposal, we use the highly optimized ML-KEM, a post-quantum lattice-based scheme recently standardized by NIST. We provide detailed procedures for tailoring our codes to ML-KEM’s specific noise distributions, and show how to analyze the DFR without independence assumptions on the noise coefficients. Among our results, we achieve between 4% and 8% ciphertext compression for MLKEM. Alternatively, we obtain 8% shorter public keys compared to the current standard. We also present isochronous implementations of the decoding procedure, achieving negligible performance impact in the full ML-KEM decapsulation even when considering optimized implementations for AVX2, Cortex-M4, and Cortex-A53.

The benefits of using Deep Learning techniques to enhance side-channel attacks performances have been demonstrated over recent years. Most of the work carried out since then focuses on discriminative models. However, one of their major limitations is the lack of theoretical results. Indeed, this lack of theoretical results, especially concerning the choice of neural network architecture to consider or the loss to prioritize to build an optimal model, can be problematic for both attackers and evaluators. Recently, Zaid et al. addressed this problem by proposing a generative model that bridges conventional profiled attacks and deep learning techniques, thus providing a model that is both explicable and interpretable. Nevertheless the proposed model has several limitations. Indeed, the architecture is too complex, higher-order attacks cannot be mounted and desynchronization is not handled by this model. In this paper, we address the first limitation namely the architecture complexity, as without a simpler model, the other limitations cannot be treated properly. To do so, we propose a new generative model that relies on solid theoretical results. This model is based on conditional variational autoencoder and converges towards the optimal statistical model i.e. it performs an optimal attack. By building on and extending the state-of-the-art theoretical works on dimensionality reduction, we integrate into this neural network an optimal dimensionality reduction i.e. a dimensionality reduction that is achieved without any loss of information. This results in a gain of O(D), with D the dimension of traces, compared to Zaid et al. neural network in terms of architecture complexity, while at the same time enhancing the explainability and interpretability. In addition, we propose a new attack strategy based on our neural network, which reduces the attack complexity of generative models from O(N) to O(1), with N the number of generated traces. We validate all our theoretical results experimentally using extensive simulations and various publicly available datasets covering symmetric, asymmetric pre and post-quantum cryptography implementations.

Masking is one of the most prevalent and investigated countermeasures against side-channel analysis. As an alternative to the simple (e.g., additive) encoding function of Boolean masking, a collection of more algebraically complex masking types has emerged. Recently, inner product masking and the more generic codebased masking have proven to enable higher theoretical security properties than Boolean masking. In CARDIS 2017, Poussier et al. connected this “security order amplification” effect to the bit-probing model, demonstrating that for the same shared size, sharings from more complex encoding functions exhibit greater resistance to higher-order attacks. Despite these advantages, masked gadgets designed for code-based implementations face significant overhead compared to Boolean masking. Furthermore, existing code-based masked gadgets are not designed for efficient bitslice representation, which is highly beneficial for software implementations. Thus, current code-based masked gadgets are constrained to operate over words (e.g., elements in F2k ), limiting their applicability to ciphers where the S-box can be efficiently computed via power functions, such as AES. In this paper, we address the aforementioned limitations. We first introduce foundational masked linear and non-linear circuits that operate over bits of code-based sharings, ensuring composability and preserving bit-probing security, specifically achieving t-Probe Isolating Non-Interference (t-PINI). Utilizing these circuits, we construct masked ciphers that operate over bits, preserving the security order amplification effect during computation. Additionally, we present an optimized bitsliced masked assembly implementation of the SKINNY cipher, which outperforms Boolean masking in terms of randomness and gate count. The third-order security of this implementation is formally proven and validated through practical side-channel leakage evaluations on a Cortex-M4 core, confirming its robustness against leakages up to one million traces.

A true random number generator (TRNG) is a critical component in ensuring the security of cryptographic systems. Among TRNG implementations, the phase-locked loop-based TRNG (PLL-TRNG) is a widely adopted solution for FPGA platforms due to the availability of a stochastic model. In the previous study, this stochastic model was based on analog noise signals, which potentially led to an oversimplification of the PLL physical process and resulted in an overestimation of entropy. To address this limitation, we extract key platform-specific parameters of the PLL and develop a new stochastic model tailored for multi-output PLL-TRNGs. For the first time, we reveal the effect of the PLL’s bandwidth on the correlation of sampling points and introduce a method for quantitatively controlling sampling point correlations. Finally, we validate the model through on-chip jitter measurements. Experimental results show that the proposed stochastic model accurately describes the behavior of the PLL-TRNG and provides the most conservative entropy lower bound, with a 1.8-fold improvement in jitter resolution.

With the rapid development and deployment of machine learning (ML) and big data technologies, which rely heavily on sensitive user data for training and inference, ensuring privacy and data security has become a pressing challenge. Addressing this issue requires methods that safeguard sensitive information while maintaining the correctness of computational results. Secure multi-party computation (MPC), as a representative application of cryptographic techniques, offers a technical solution to this challenge by enabling privacy-preserving computations. It has been widely applied in scenarios such as cloud-based inference and other privacy-sensitive tasks. However, MPC also introduces significant performance overhead, thus limiting its further application. Our analysis reveals that the foundational element of MPC, the oblivious transfer (OT) protocol collectively account for up to 96.64% of the execution time. It is because the OT protocols are constrained by low network band- width and weak compute engines. To address these challenges, we propose POTA, a high-performance pipelined OT hardware acceleration architecture supporting the silent OT protocol. In the POTA design, we develop efficient subsystems targeting the two most compute-intensive parts: the construction of puncturable pseudoran- dom function (PPRF), and large matrix-vector multiplications under the learning parity with noise (LPN) assumption within the silent OT protocol. In addition, to address the performance overhead caused by data transfer between POTA and the host CPU, we design a host-accelerator execution pipeline to hide the considerable transmission latency. Furthermore, we design a modular multiplication module over a finite field to generate the more complex correlations required by MPC protocols. Finally, we implement a POTA prototype on Xilinx VCU129 FPGAs. Experimental results demonstrate that under various network settings, POTA achieves significant speedups, with maximum improvements of 192.57x for basic operations and 597.57x for convolutional neural networks (CNN).

This work showcases Quatorze-bis, a state-of-the-art Number Theoretic Transform circuit for TFHE-like cryptosystems on FPGAs. It contains a novel modular multiplication design for modular multiplication with a constant for a constant modulus. This modular multiplication design does not require any DSP units or any dedicated multiplier unit, nor does it require extra logic when compared to the state-of-the-art modular multipliers. Furthermore, we present an implementation of a constant multiplier Number Theoretic Transform design for TFHE-like schemes. Lastly, we use this Number Theoretic Transform design to implement a FINAL hardware accelerator for the AMD Alveo U55c which improves the Throughput metric of TFHE-like cryptosystems on FPGAs by a factor 9.28x over Li et al.’s NFP CHES 2024 accelerator and by 10-25% over the absolute state-of-the-art design FPT [vBDTV23] while using one third of FPTs DSPs.

The XEX/XE scheme has been widely used to realize authenticated encryptions (AEs), message authentication codes (MACs), and storage encryptions, such as OCB, PMAC, and XTS. Although these schemes have been extensively deployed in the real world, limited studies have evaluated side-channel attacks (SCAs) on them. In this study, we propose an efficient SCA that can be applied to the XEX/XE scheme. Despite the fact that the offset generated in these modes is guaranteed to have no full offset collision with an overwhelming probability, we analyze their offset-generating routines to exploit the partial offset collisions. Then, we propose a new profiled SCA named XOR-convoluting collision analysis (XCCA), which estimates the sum of keys from two leakages by XOR-convoluting probability distributions that model the leakages. The proposed collision SCA effectively erases the effect of random offsets by using XOR-convolution, whereas conventional collision SCAs are ineffective in this scenario. We validated the proposed SCA through simulations and experimental attacks using real traces. The results confirmed that the proposed SCA reduces the number of traces by up to 90% to achieve a success rate identical to that of a state-of-the-art SCA on OCB in TCHES 2022. Furthermore, we show that the proposed SCA distinguisher (XCCA distinguisher) is a generalization of higher-order SCAs, including non-collision SCAs on masked implementations. The profiled higher-order SCAs on masked implementations can be written in the form of an XCCA distinguisher using XOR-convolution with the new concept of leaking and target selection functions. The generalized representation clarifies how and why a higher-order SCA has better or worse performance from the theoretical viewpoint of noise amplification, which is also demonstrated through experiments and a spectrum analysis based on Walsh–Hadamard transform (WHT). Our analysis reveals that the random offsets of XEX/XE would work as masking from an SCA perspective, and XEX/XE-based encryption would have an inherent first-order SCA resilience under certain conditions.

In this paper, we have designed and implemented a massively parallel FPGA architecture for exhaustive key search on the A5/3 encryption algorithm. A5/3 is based on KASUMI, it has an effective key of 64 bits, and it is used in GSM (2G) mobile telephony systems. Despite the widespread adoption of more advanced technologies (4G, 5G), 2G networks remain as fallback options. In our novel hardware architecture, we use an AMD-Xilinx Alveo U250 card, with its FPGA configured to operate with 104 cores clocked at 496.7 M Hz, that can evaluate 235.59 keys/sec. Our results show that the $1 million attack can be achieved with 128 Alveo U250 cards, on average, in 16 days.

Side-channel attacks exploit unintended information leakage emitted by cryptographic devices to extract sensitive data. Hiding techniques are a cost-effective countermeasure designed to obfuscate the side-channel leakage and hinder these attacks. Available open datasets rely on artificial models to simulate hiding effects, preventing a realistic assessment of these countermeasures and, thus, leaving a pressing need for datasets offering real-world, obfuscated side-channel measurements. Chameleon introduces the first comprehensive dataset of real-world, obfuscated power traces collected from a RISC-V-based System-on-Chip. The traces are obfuscated using four state-of-the-art hiding techniques: dynamic frequency scaling, random delay, morphing, and chaffing. Chameleon captures real leakage deformations introduced by actual hardware implementations, making it a realistic and valuable tool for evaluating side-channel countermeasures. A key feature of Chameleon is its dual focus on the segmentation and attack stages of the side-channel analysis process. It is the first dataset designed to facilitate the challenging task of segmenting cryptographic operations from obfuscated traces, offering precise metadata that pinpoints the start and end of each operation. The high-quality metadata enables systematic research into segmentation techniques, a critical step often overlooked in previous datasets. Chameleon provides an essential platform for researchers to develop and test new side-channel attacks, highlighting the vulnerabilities of current hiding techniques. By offering a more realistic assessment of countermeasure effectiveness, Chameleon is an invaluable tool for advancing the state-of-the-art in the side-channel evaluation.

The lattice-based Raccoon scheme is one of the candidates in Round 1 of the National Institute of Standards and Technology (NIST) post-quantum cryptography (PQC) additional digital signatures standardization process. As a scheme with built-in masking features, Raccoon is also a viable candidate for NIST’s Masking Circuit and Threshold Cryptography project. Current Raccoon implementations are limited to software or software-hardware co-designs only and consequently lacking in terms of high throughput performance that hardware implementations can generally promise. To achieve this, we are the first to propose a configurable and high-performance pure hardware architecture for Raccoon. The proposed FPGA architecture features extensive optimizations in key modules for Raccoon such as the modular reduction, polynomial operations, and sampling. The segmentation and loop-based scheduling scheme interacts with the defined BRAM-based memory access pattern to ensure efficient and coherent data flow under the three security levels and two masking modes (non- and first-order masking). Implementation results of Raccoon on an AMD Artix- 7 FPGA device show that our proposed architecture achieves a 1.4–2.1x speedup compared to software implementations and a 20–42x speedup compared to softwarehardware co-designs for the three security levels, despite its hardware area being comparable to that of the lightweight CRYSTALS-Dilithium architecture. Finally, a TVLA test is demonstrated on Raccoon-128 with non-masking and first-order masking to evaluate its resilience to side-channel attacks.

Authenticated encryption (AE) is a fundamental tool in today’s secure communication. Numerous designs have been proposed, including well-known standards such as GCM. While their performance for long inputs is excellent, that for short inputs is often problematic due to high overhead in computation, showing a gap between the real need for IoT-like protocols where packets are often very short. Existing dedicated short-input AEs are very scarce, the classical Encode-then-encipher (Bellare and Rogaway, Asiacrypt 2000) and Manx (Adomnicăi et al., CT-RSA 2023), using up to two block cipher calls. They have superior performance for (very) short inputs, however, security is up to n/2 bits, where n is the block size of the underlying block cipher. This paper proposes a new family of short-input AEs, dubbed Cymric, which ensure beyond-birthday-bound (BBB) security. It supports a wider range of input space than EtE and Manx with the help of one additional block cipher call (thus three calls). In terms of the number of block cipher calls, Cymric is the known minimum construction of BBB-secure AEs, and we also prove this is indeed minimal by presenting an impossibility result on BBB-secure AE with two calls. Finally, we show a comprehensive benchmark on microcontrollers to show performance advantage over existing schemes.

Template attacks build a Gaussian multivariate model of the side-channel leakage signal generated by each value of a targeted intermediate variable. Combined with additional steps, such as dimensionality reduction, such models can help to infer a value with nearly 100% accuracy from just a single attack trace. We demonstrate this here by reconstructing the output of the binomial sampler of a Cortex-M4 imple- mentation of the Kyber768 post-quantum key-encapsulation mechanism. However, this performance is usually significantly diminished if the device, or even just the ad- dress space, used for profiling differs from the attacked one. Here we introduce a new technique for adapting templates generated from profiling devices in order to attack another device where we are also able to record many traces, but without knowledge of the random value held by the targeted variable. We interpret the model from the profiling devices as a Gaussian mixture and use the Expectation–Maximization (EM) algorithm to adapt its means and covariances to better match the unlabelled leakage distribution observed from the attacked setting. The Kyber binomial sampler turned out to be a particularly suitable target, for two reasons. Firstly, it generates a long sequence of values drawn from a small set, limiting the number of Gaussian components that need to be adjusted. Secondly, the length of this sequence requires particularly well-adapted templates to achieve a high key-recovery success rate from a single trace. We also introduce an extended point-of-interest selection method to improve linear discriminant analysis (LDA).

This paper establishes that the extended Euclidean algorithm (EEA) implemented in a division-free manner is faster than the Lagrange algorithm with a similar level of optimization when it comes to halving the size of scalars found in the equations of elliptic curve signature verification. Our implementation results show that our EEA based method achieves roughly 4x speed-up for generating half- size scalars used in EdDSA. For the first time ever, EEA generated half-size scalars are used for verification of individual Ed25519 signatures yielding timing results that outperform ed25519-donna, a highly optimized open source implementation, by 16.12%. We also propose a new randomization method applied with half-size scalars to batch verification of Ed25519 signatures for which we report speed-ups compared to the well-known Bernstein et al. method for batch sizes larger than six, specifically, our method achieves 11.60% improvement for batch size 64.

This paper presents dCTIDH, a CSIDH implementation that combines two recent developments into a novel state-of-the-art deterministic implementation. We combine the approach of deterministic variants of CSIDH with the batching strategy of CTIDH, which shows that the full potential of this key space has not yet been explored. This high-level adjustment in itself leads to a significant speed-up. To achieve an effective deterministic evaluation in constant time, we introduce WOMBats, a new approach to performing isogenies in batches, specifically tailored to the behavior required for deterministic CSIDH using CTIDH batching. Furthermore, we explore the two-dimensional space of optimal primes for dCTIDH, with regard to both the performance of dCTIDH in terms of finite-field operations per prime and the efficiency of finite-field operations, determined by the prime shape, in terms of cycles. This allows us to optimize both for choice of prime and scheme parameters simultaneously. Lastly, we implement and benchmark constant-time, deterministic dCTIDH. Our results show that dCTIDH not only outperforms state-of-the-art deterministic CSIDH, but even non-deterministic CTIDH: dCTIDH-2048 is faster than CTIDH-2048 by 17%, and is almost five times faster than dCSIDH-2048.

The increasing prevalence of security breaches highlights the importanceof robust hardware security measures. Among these breaches, physical attacks– such as Side-Channel Analysis ( SCA) and Fault Injection (FI ) attacks – posea significant challenge for security-sensitive applications. To ensure robust systemsecurity throughout its lifecycle, hardware security updates are indispensable alongsidesoftware security patches. Programmable hardware plays a pivotal role in establishinga robust hardware root-of-trust, serving to effectively mitigate various hardwaresecurity threats. In this paper, we propose a methodology for the design of areconfigurable fabric and the corresponding mapping toolchain, specifically tailoredto hardware security. This approach offers resistance to various malicious physicalattacks, including SCA and FI , addressing each threat individually. As a case study,we propose a resulting fabric that implements a combination of first-order BooleanMasking and hiding countermeasures to provide strong protection against SCA attacksand enables the detection of fault injection attempts. In particular, we present howreconfigurable secure gadgets can be realized employing a reformed variant of theLUT-based Masked Dual-Rail with Pre-charge Logic (LMDPL) hardware maskingscheme and a modified version of Wave Dynamic Differential Logic ( WDDL) tobe composed into a fabric. We also show how any basic Hardware DescriptionLanguage ( HDL) design is automatically mapped to the primitives of our fabric,embedding provable hardware security, and bypassing the necessity for hardwaresecurity proficiency in this process. It is worth mentioning that our fabric requiresapproximately 85% less area to map a secure design compared to conventional FieldProgrammable Gate Arrays ( FPGAs). A practical security evaluation of our securefabric implementation on a real FPGA target board, using Test Vector LeakageAssessment (TVLA), demonstrated no SCA leakage over 100 million traces.

The confidentiality of cryptographic keys is essential for the security of protection schemes used for communication, file encryption, and outsourced compu- tation. Beyond cryptanalytic attacks, adversaries can steal keys from memory via software exploits or side channels, enabling them to, e.g., manipulate confidential information or impersonate key owners. Therefore, existing defenses protect keys in dedicated devices or isolated memory, or store them only in encrypted form. However, these designs often provide unfavorable tradeoffs, sacrificing performance, fine-grained access control, or deployability.In this paper, we present KeyVisor, a lightweight Instruction Set Architecture ( ISA) extension that securely offloads the handling of symmetric crypto keys to the CPU. KeyVisor provides CPU instructions that enable applications to request protected key handles and perform AEAD cipher operations on them. The underlying keys are accessible only by KeyVisor, and thus never leak to memory. KeyVisor’s direct CPU integration enables fast crypto operations and hardware-enforced key usage restrictions, e.g., keys usable only for de-/encryption, with a limited lifetime, or with a process binding. Furthermore, privileged software, e.g., the monitor firmware of TEEs, can revoke keys or bind them to a specific process/TEE. We implement KeyVisor for RISC-V based on RocketChip, evaluate its performance, and demonstrate real-world use cases, including key-value databases, automotive feature licensing, and a read-only network middlebox.

Masking is one of the main countermeasures against side-channel analysis since it relies on provable security. In this context, “provable” means that a security bound can be exhibited for the masked implementation through a theoretical analysis in a given threat model. The main goal in this line of research is therefore to provide the tightest security bound, in the most realistic model, in the most generic way. Yet, all of these objectives cannot be reached together. That is why the masking literature has introduced a large spectrum of threat models and reductions between them, depending on the desired trade-off with respect to these three goals. In this paper, we focus on three threat models, namely the noisy-leakage model (realistic yet hard to work with), the random probing (unrealistic yet easy to work with), and more particularly a third intermediate model called average random probing. Average random probing has been introduced by Dziembowski et al. at Eurocrypt 2015, in order to exhibit a tight reduction between noisy-leakage and random probing models, recently proven by Brian et al. at Eurocrypt 2024. This milestone has strong practical consequences, since otherwise the reduction from the noisy leakage model to the random probing model introduces a prohibitively high constant factor in the security bound, preventing security evaluators to use it in practice. However, we exhibit a gap between the average random probing definitions of Dziembowski et al. (denoted hereafter by DFS-ARP) and Brian et al. (simply denoted by ARP). Whereas any noisy leakage can be tightly reduced to DFS-ARP, we show in this paper that it cannot be tightly reduced to ARP, unless requiring extra assumptions, e.g., if the noisy leakage is deterministic. Our proof techniques do not involve more tools than the one used so far in such reductions, namely basic probability facts, and known properties of the total variation distance. As a consequence, the reduction from the noisy leakage to the random probing — without high constant factor — remains unproven. This stresses the need to clarify the practical relevance of analyzing the security of masking in the random probing model since most of the current efforts towards improving the constructions and their security proofs in the random probing model might be hindered by potentially unavoidable loss in the reduction from more realistic but currently less investigated leakage models.

The standard notion of security for threshold signature schemes is static security, where the set of corrupt parties is assumed to be fixed before protocol execution. In this model, the adversary may corrupt up to t−1 out of a threshold of t parties. A stronger notion of security for threshold signatures considers an adaptive adversary, who may corrupt parties dynamically based on its view of the protocol execution, learning the corrupted parties’ secret keys as well as their states. Adaptive security of threshold signatures has become an active area of research recently due to ongoing standardization efforts. Of particular interest is full adaptive security, the analogue of static security, where the adversary may adaptively corrupt a full t−1 parties. We present a plausible attack on the full adaptive security of threshold Schnorr signature schemes with public key shares of the form pk_i = g^{sk_i}, where all secret keys sk_i lie on a polynomial. We show that a wide range of threshold Schnorr signature schemes, including all variants of FROST, Sparkle, and Lindell’22, cannot be proven fully adaptively secure without modifications or assuming the hardness of a search problem that we define in this work. We then prove a generalization that extends below t−1 adaptive corruptions.

The Signal protocol is the most widely deployed end-to-end-encrypted messaging protocol. Its initial handshake protocol X3DH allows parties to asynchronously derive a shared session key without the need to be online simultaneously, while providing implicit authentication, forward secrecy, and a form of offline deniability. The X3DH protocol has been extensively studied in the cryptographic literature and is acclaimed for its strong "maximum-exposure" security guarantees, hedging against compromises of users' long-term keys and medium-term keys but also the ephemeral randomness used in the handshake. This maximum-exposure security is achieved by deriving keys from the concatenation of 3-4 Diffie-Hellman (DH) secrets, each combining two long-term, medium-term, or ephemeral DH shares. Remarkably, X3DH's approach of concatenating plain DH combinations is sub-optimal, both in terms of maximum-exposure security and performance. Indeed, Krawczyk's well-known HMQV protocol (Crypto '05) is a high-performance, DH-based key exchange that provides strong security against long-term and ephemeral key compromise. One might hence wonder: why not base Signal's initial handshake on HMQV? In this work, we study this question and show that a carefully adapted variant of HMQV, which we call XHMQV, indeed enables stronger security and efficiency while matching the constraints of Signal's initial handshake. Most notably, HMQV does not work as a drop-in replacement for X3DH, as the latter's asynchronicity requires the protocol to handle cases where one party runs out of ephemeral keys (pre-uploaded to the Signal server). Our XHMQV design hence augments HMQV with medium-term keys analogous to those used in X3DH. We prove that XHMQV provides security in all 3-4 compromise scenarios where X3DH does and additionally in 1-2 further scenarios, strengthening the handshake's maximum-exposure guarantees while using more efficient group operations. We further confirm that our XHMQV design achieves deniability guarantees comparable to X3DH. Our security model is the first to capture Signal's long-term key reuse between DH key exchange and signatures, which may be of independent interest.

Provable security bounds of Feistel ciphers have been a significant research topic since the seminal work by Luby and Rackoff in 1986. While the field of research started by abstracting round functions with ideal random functions, the research community has extended provable security to encompass more realistic models. These models include key-alternating Feistel (KAF) ciphers that separate random functions into round keys and public primitives, which is further extended to utilizing a single primitive across all rounds, correlated subkeys, and in the multi-user (mu) setting. This paper advances this field by presenting new mu security bounds for a notable variant, a KAF with a single public permutation based on the Even-Mansour (EM) construction. With an $n$-bit public permutation and $(r-2)$-wise independent subkeys, with respect to the round number $r$, our new proof establishes a general bound of $n(r-2)/(r-1)$ bits, offering improvements over the current state-of-the-art. We also provide a new information-theoretic matching attack, confirming its tightness. Technical innovation include extending the resampling method to Feistel ciphers and devising an information-theoretic variant of the meet-in-the-middle attack applicable to large $r$.

The Dilithium signature scheme – recently standardized by NIST under the name ML-DSA – owes part of its success to a specific mechanism that allows an optimizaion of its public key size. Namely, among the data of the MLWE instance $\bf (A,\bf{t})$, which is at the heart of the construction of Dilithium, the least significant part of $\bf{t}$ -- denoted by $\bf{t}_0$ -- is not included in the public key. The verification algorithm had been adapted accordingly, so that it should not require the knowledge of $\bf{t}_0$. However, since it is still required to compute valid signatures, it has been made part of the secret key. The knowledge of $\bf{t}_0$ has no impact on the black-box cryptographic security of Dilithium, as can be seen in the security proof. Nevertheless, it does allow the construction of much more efficient side-channel attacks. Whether it is possible to recover $\bf{t}_0$ thus appears to be a sensitive question. In this work, we show that each Dilithium signature leaks information on $\bf{t}_0$, then we construct an attack that retrieves it from Dilithium signatures. Experimentally, depending on the Dilithium security level, between $200\,000$ and $500\,000$ signatures are sufficient to recover $\bf{t}_0$ on a desktop computer.

Cryptographic group actions are a leading contender for post- quantum cryptography, and have also been used in the development of quantum cryptographic protocols. In this work, we explore quantum state group actions, which consist of a group acting on a set of quantum states. We show the following results: – If enough copies of each state are provided, statistical (even query bounded) security is impossible. – We construct quantum state group actions and prove them secure in the bounded-copy regime for many computational problems that have been proposed by cryptographers. Depending on the construc- tion, our proofs are either unconditional, rely on LWE, or rely on the quantum random oracle model. While our analysis does not di- rectly apply to classical group actions, we argue it gives at least a sanity check that there are no obvious flaws in the post-quantum assumptions made by cryptographers. – Our quantum state group actions allows for unifying two existing quantum money schemes: those based on group actions, and those based on non-collapsing hashes. We also explain how they can unify classical and quantum key distribution.

Black-box separations are a cornerstone of cryptography, in- dicating barriers to various goals. A recent line of work has explored black-box separations for quantum cryptographic primitives. Namely, a number of separations are known in the Common Haar Random State (CHRS) model, though this model is not considered a complete separa- tion, but rather a starting point. A few very recent works have attempted to lift these separations to a unitary separation, which are considered complete separations. Unfortunately, we find significant errors in some of these lifting results. We prove general conditions under which CHRS separations can be generically lifted, thereby giving simple, modular, and bug-free proofs of complete unitary separations between various quantum primitives. Our techniques allow for simpler proofs of existing separations as well as new separations that were previously only known in the CHRS model.

Existing fully homomorphic encryption (FHE) schemes primarily support a plaintext space defined over a relatively small prime. However, in some important applications of FHE one needs arithmetic over a large prescribed prime. In this paper we construct a new FHE system that is specifically designed for this purpose. Our system composes three layers of residue systems to enable much better performance than was previously possible. Our experiments show that for arithmetic modulo a 256-bit integer, when compared to the TFHE-rs implementation of 256-bit arithmetic, our new system achieves a factor of two thousand better multiplication throughput and a factor of twenty better latency. Moreover, for a 2048-bit prime modulus we achieve far better performance than was previously possible.

Ever since the introduction of encryption, society has been divided over whether the government (or law enforcement agencies) should have the capability to decrypt private messages (with or without a war- rant) of its citizens. From a technical viewpoint, the folklore belief is that semantic security always enables some form of steganography. Thus, adding backdoors to semantically secure schemes is pointless: it only weakens the security of the “good guys”, while “bad guys” can easily circumvent censorship, even if forced to hand over their decryption keys. In this paper we put a dent in this folklore. We formalize three worlds: Dictatoria (“dictator wins”: no convenient steganography, no user co- operation needed), Warrantland (“checks-and-balances”: no convenient steganography, but need user’s cooperation) and Privatopia (“privacy wins”: built-in, high-rate steganography, even if giving away the decryp- tion key). We give strong evidence that all these worlds are possible, thus reopening the encryption debate on a technical level. Our main novelty is the definition and design of special encryp- tion schemes we call anamorphic-resistant (AR). In contrast to so called “anamorphic schemes”, — which were studied in the literature and form the basis of Privatopia, — any attempt to steganographically communi- cate over an AR-encryption scheme will be either impossible or hugely slow (depending on the definitional details).

Throughput, i.e., the amount of payload data processed per unit of time, is a crucial measure of scalability for blockchain consensus mechanisms. This paper revisits the design of secure, high-throughput proof-of-stake (PoS) protocols in the permissionless setting. Existing high-throughput protocols are either analyzed using overly simplified network models or are designed for permissioned settings, leaving the task of adapting them to a permissionless environment while maintaining both scalability and adaptive security (which is essential in permissionless environments) as an open question. Two particular challenges arise when designing high-throughput protocols in a permissionless setting: message bursts, where the adversary simultaneously releases a large volume of withheld protocol messages, and—in the PoS setting—message equivocations, where the adversary diffuses arbitrarily many versions of a protocol message. It is essential for the security of the ultimately deployed protocol that these issues be captured by the network model. Therefore, this work first introduces a new, realistic network model based on the operation of real-world gossip networks—the standard means of diffusion in permissionless systems, which may involve many thousands of nodes. The model specifically addresses challenges such as message bursts and PoS equivocations and is also of independent interest. The second and main contribution of this paper is Leios, a blockchain protocol that transforms any underlying low-throughput base protocol into a blockchain achieving a throughput corresponding to a $(1-\delta)$ fraction of the network capacity—while affecting latency only by a related constant. In particular, if the underlying protocol has constant expected settlement time, this property is retained under the Leios overlay. Combining Leios with any permissionless protocol yields the first near-optimal throughput permissionless layer-1 blockchain protocol proven secure under realistic network assumptions.

We establish new lower bounds on the size of practical garbled circuits, which hold against any scheme satisfying the following simple properties: (1) Its security is based on symmetric-key cryptography only. More formally, security holds in Minicrypt, a model in which a random oracle is the only available source of cryptography. (2) The evaluation algorithm makes non-adaptive queries to the random oracle. (3) The evaluation algorithm ``knows'' which of its oracle queries are made by which other input combinations. These restrictions are reasonable for garbling single gates. In particular, unlike prior attempts at lower bounds, we make no assumptions about the internal behavior of the garbling algorithms --- i.e.,how it uses random oracle outputs and wire labels to compute the garbled gate, etc. We prove separate lower bounds depending on whether the scheme uses the free-XOR technique (Kolesnikov & Schneider, ICALP 2008). In the free-XOR case, we prove that a garbled AND-gate requires $1.5\lambda$ bits; thus, the garbling scheme of Rosulek & Roy (Crypto 2022) is optimal. In the non-free-XOR case, we prove that a garbled AND-gate requires $2\lambda$ bits and a garbled XOR-gate requires $\lambda$ bits; thus, the garbling scheme of Gueron, Lindell, Nof, and Pinkas (CCS 2015) is optimal. We prove our lower bounds using tools from information theory. A garbling scheme can be characterized as a joint distribution over various quantities: wire labels, garbled gate information, random oracle responses. We show that different properties of a garbling scheme imply certain Shannon-type information inequalities about this distribution. We then use an automated theorem prover for Shannon-type inequalities to prove that our inequalities imply lower bounds on the entropy---hence, size---of the garbled gate information.

Witness Encryption (WE) is a powerful cryptographic primitive, enabling applications that would otherwise appear infeasible. While general-purpose WE requires strong cryptographic assumptions, and is highly inefficient, recent works have demonstrated that it is possible to design special-purpose WE schemes for targeted applications that can be built from weaker assumptions and can also be concretely efficient. Despite the plethora of constructions in the literature that (implicitly) use witness encryption schemes, there has been no systematic study of special purpose witness encryption schemes. In this work we make progress towards this goal by designing a modular and extensible framework, which allows us to better understand existing schemes and also enables us to construct new witness encryption schemes. The framework is designed around simple but powerful building blocks that we refer to as "gadgets". Gadgets can be thought of as witness encryption schemes for small targeted relations (induced by linearly verifiable arguments) but they can be composed with each other to build larger, more expressive relations that are useful in applications. To highlight the power of our framework we methodically recover past results, improve upon them and even provide new feasibility results. The first application of our framework is a Registered Attribute-Based Encryption Scheme [Hohenberger et al. (Eurocrypt 23)] with linear sized common reference string (CRS). Numerous Registered Attribute-Based Encryption (R-ABE) constructions have since emerged though a black-box R-ABE construction with a linear--in the number of users--CRS has been a persistent open problem, with the state-of-the-art concretely being $\approx N^{1.58}$ (Garg et al. [GLWW, Crypto 24]). Empowered by our Witness Encryption framework we provide the first construction of black-box R-ABE with linear-sized CRS. Our construction is based on a novel realization of encryption for DNF formulas that leverages encryption for set membership. Our second application is a feasibility result for Registered Threshold Encryption. This is an analogue of the recently introduced Silent Threshold Encryption (Garg et al. [GKPW, Crypto 24]) placed in the Registered Setting. We formalize Registered Threshold Encryption and provide an efficient construction, with constant-sized encryption key and ciphertexts, that makes use of our WE framework.

We consider the question of whether worst-case hardness of the time-bounded Kolmogorov complexity problem, ${\sf MINK^{poly}}$---that is, determining whether a string is time-bounded Kolmogorov random ($K^t$-random) or not---suffices to imply the existence of one-way functions (OWF). Roughly speaking, our main result shows that under standard derandomization assumptions, worst-case hardness of the \emph{boundary} version of this classic problem characterizes OWFs. In more detail, let ${\sf boundry-MINK^{t_1, t_2}}$ denote the problem of, given an instance $x$, deciding whether (a) $K^{t_2}(x)\geq n-1$, or (b) $K^{t_1}(x) < n-1$ \emph{but} $K^{t_2}> n - \log n$; that is, deciding whether $x$ is $K^t$-random, or just ``near" $K^t$-random. We say that ${\sf boundry-MINK^{poly}} \notin \ioBPP$ if ${\sf boundry-MINK^{t_1, t_2}} \notin \ioBPP$ for all polynomials $t_1,t_2$. Our main result shows that under standard derandomization assumptions, OWF exist iff ${\sf boundry-MINK^{poly}} \notin \ioBPP$. Along the way, we also demonstrate that if we consider the probabilistic version of Kolmogorov complexity (referred to as $pK^t$) instead, then the characterization holds unconditionally. We finally observe that for most standard optimization problems, hardness ``along boundary" is equivalent to ``plain" worst-case hardness, indicating that assuming hardness along the boundary may be WLOG.

We present a simple counterexample to all known variants of the private-coin evasive learning with errors (LWE) assumption. Unlike prior works, our counterexample is direct, it does not use heavy cryptographic machinery (such as obfuscation or witness encryption), and it applies to \emph{all variants} of the assumption. Our counterexample can be seen as a "zeroizing" attack against evasive LWE, calling into question the soundness of the underlying design philosophy.

Incrementally verifiable computation (IVC) [Valiant, TCC'08] allows one to iteratively prove that a configuration $x_0$ reaches another configuration $x_T$ after repeated applications of a (possibly non-deterministic) transition function $\mathcal{M}$. The key requirement is that the size of the proof and the time to update the proof is sublinear in the number of steps $T$. IVC has numerous applications such as proving correctness of virtual machine executions in blockchains. Currently, IVC for $\mathsf{NP}$ is only known to exist in idealized models, or based on knowledge assumptions. No constructions are known from standard assumptions, or even in the random oracle model. Furthermore, as observed in prior works, since IVC for $\mathsf{NP}$ implies adaptive succinct non-interactive arguments for $\mathsf{NP}$, the work of Gentry-Wichs [STOC `11] seemingly poses barriers to constructing IVC for $\mathsf{NP}$ from falsifiable assumptions. In this work, we observe that the Gentry-Wichs barrier can be overcome for IVC for NP. We show the following two results: * Assuming subexponential $i\mathcal{O}$ and LWE (or bilinear maps), we construct IVC for all $\mathsf{NP}$ with proof size $\mathsf{poly}(|x_i|,\log T)$. * Assuming subexponential $i\mathcal{O}$ and injective PRGs, we construct IVC for \emph{trapdoor IVC languages} where the proof-size is $\mathsf{poly}(\log T)$. Informally, an IVC language has a trapdoor if there {\em exists} a (not necessarily easy to find) polynomial-sized circuit that determines if a configuration $x_i$ is reachable from $x_0$ in $i$ steps.

Indistinguishability obfuscation (iO) stands out as a powerful cryptographic primitive but remains notoriously difficult to realize under simple-to-state, post-quantum assumptions. Recent works have proposed lattice-inspired iO constructions backed by new “LWE-with-hints” assumptions, which posit that certain distributions of LWE samples retain security despite auxiliary information. However, subsequent cryptanalysis has revealed structural vulnerabilities in these assumptions, leaving us without any post-quantum iO candidates supported by simple, unbroken assumptions. Motivated by these proposals, we introduce the \emph{Circular Security with Random Opening} (CRO) assumption—a new LWE-with-hint assumption that addresses structural weaknesses from prior assumptions, and based on our systematic examination, does not appear vulnerable to known cryptanalytic techniques. In CRO, the hints are random ``openings'' of zero-encryptions under the Gentry--Sahai--Waters (GSW) homomorphic encryption scheme. Crucially, these zero-encryptions are efficiently derived from the original LWE samples via a special, carefully designed procedure, ensuring that the openings are marginally random. Moreover, the openings do not induce any natural leakage on the LWE noises. These two features---{\em marginally random hints and the absence of (natural) noise leakage}---rule out important classes of attacks that had undermined all previous LWE-with-hint assumptions for iO. Therefore, our new lattice-based assumption for iO provides a qualitatively different target for cryptanalysis compared to existing assumptions. To build iO under this less-structured CRO assumption, we develop several new technical ideas. In particular, we devise an \emph{oblivious LWE sampling} procedure, which succinctly encodes random LWE secrets and smudging noises, and uses a tailored-made homomorphic evaluation procedure to generate secure LWE samples. Crucially, all non-LWE components in this sampler, including the secrets and noises of the generated samples, are independently and randomly distributed, avoiding attacks on non-LWE components.

The Rowhammer attack is a fault-injection technique lever aging the density of RAM modules to trigger persistent hardware bit flips that can be used for probing or modifying protected data. In this paper, we show that Falcon, the hash-and-sign signature scheme over NTRU lattices selected by NIST for standardization, is vulnerable to an attack using Rowhammer. Falcon’s Gaussian sampler is the core component of its security, as it allows to provably decorrelate the short basis used for signing and the generated signatures. Other schemes, lacking this guarantee (such as NTRUSign, GGH or more recently Peregrine) were proven insecure. However, performing efficient and secure lattice Gaussian sampling has proved to be a difficult task, fraught with numerous potential vulnerabilities to be exploited. To avoid timing attacks, a common technique is to use distribution tables that are traversed to output a sample. The official Falcon implementation uses this technique, employing a hardcoded reverse cumulative distribution table (RCDT). Using Rowhammer, we target Falcon’s RCDT to trigger a very small number of targeted bit flips, and prove that the resulting distribution is sufficiently skewed to perform a key recovery attack. Namely, we show that a single targeted bit flip suffices to fully recover the signing key, given a few hundred million signatures, with more bit flips enabling key recovery with fewer signatures. Interestingly, the Nguyen-Regev parallelepiped learning attack that broke NTRUSign, GGH and Peregrine does not readily adapt to this setting unless the number of bit flips is very large. However, we show that combining it with principal component analysis (PCA) yields a practical attack. Variants combining PCA with non-convex optimization or lattice reduction are also consid- ered. This vulnerability can also be triggered with other types of persistent fault attacks on memory like optical faults. We suggest cheap countermeasures that largely mitigate it, including rejecting signatures that are unusually short.

We construct $t$-non-malleable extractors---which allow an attacker to tamper with a source $t$ times---for high min-entropy sources samplable by poly-time hierarchy circuits and for tampering classes corresponding to poly-time hierarchy functions from derandomization-type assumptions. We then show an application of this new object to ruling out constructions of succinct, non-interactive, arguments (SNARGs) secure against \emph{uniform} adversaries from \emph{uniform} falsifiable assumptions via a class of black-box reductions that has not been previously considered in the literature. This class of black-box reductions allows the reduction to arbitrarily set the \emph{coins}, as well as the input, of the uniform adversary it interacts with. The class of reductions we consider is restricted in allowing only non-adaptive queries to the adversary.

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) argumentfor 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).

State-of-the-art protocols that achieve constant-round secure multiparty computation currently present a trade-off: either consume an amount of communication that scales quadratically in the number of parties, or achieve better asymptotics at the cost of high constant factors (e.g. schemes based on LPN or DDH). We construct a constant-round MPC protocol where communication scales *linearly* in the number of parties `n'. Our construction relies only on OT and RO, and it leverages packed secret sharing. Due to building on simple primitives, our protocol offers concrete improvement over asymptotically-efficient LPN-based schemes. We consider security in the presence of a dishonest majority where the malicious (with abort) adversary corrupts an arbitrary constant fraction of parties. Our scheme is proved secure in the OT hybrid/random oracle model. By leveraging *tri-state circuits* (Heath et al. Crypto 2023), we extend our protocol to the RAM model of computation. For a RAM program that halts within T steps, our maliciously-secure protocol communicates O(n . T . log^3 T . log log T . \kappa) total bits, where \kappa is a security parameter.

One-shot signatures (OSS) were defined by Amos, Georgiou, Kiayias, and Zhandry (STOC'20). These allow for signing exactly one message, after which the signing key self-destructs, preventing a second message from ever being signed. While such an object is impossible classically, Amos et al observe that OSS may be possible using quantum signing keys by leveraging the no-cloning principle. OSS has since become an important conceptual tool with many applications in decentralized settings and for quantum cryptography with classical communication. OSS are also closely related to separations between classical-binding and collapse-binding for post-quantum hashing and commitments. Unfortunately, the only known OSS construction due to Amos et al. was only justified in a classical oracle model, and moreover their justification was ultimately found to contain a fatal bug. Thus, the existence of OSS, even in a classical idealized model, has remained open. We give the first standard-model OSS, with provable security assuming (sub-exponential) indistinguishability obfuscation (iO) and LWE. This also gives the first standard-model separation between classical and collapse-binding post-quantum commitments/hashing, solving a decade-old open problem. Along the way, we also give the first construction with unconditional security relative to a classical oracle. To achieve our standard-model construction, we develop a notion of permutable pseudorandom permutations (permutable PRPs), and show how they are useful for translating oracle proofs involving random permutations into obfuscation-based proofs. In particular, obfuscating permutable PRPs gives a trapdoor one-way permutation that is \textit{full-domain}, solving another decade-old-problem of constructing this object from (sub-exponential) iO and one-way functions.

Homomorphic encryption (HE) is a popular cryptographic primitive with wide ranging applications. While many HE schemes have been proposed over the years, schemes that support general or even more than degree-two homomorphism are known only from lattice-based assumptions or program obfuscation. In particular, constructions based solely on group-based assumptions remain elusive.          We propose the notion of sometimes-decryptable homomorphic encryption s-HE --- a relaxation of HE that allows very high decryption error for homomorphically evaluated ciphertexts. We present a construction of s-HE for constant-depth (resp., logarithmic depth) threshold circuits based on the sub-exponential (resp., exponential) Decisional Diffie-Hellman (DDH) assumption.  We demonstrate several applications of s-HE: - We construct SNARGs for all NP languages that have a TC0-Frege proof of non-membership. Namely, for every instance that is not in the language, we require that there exists a polynomial-size proof in propositional logic proving the non-membership of the instance. Moreover, each line of the proof is a TC0 formula. Our SNARG proof size is a fixed polynomial in the security parameter, and the CRS size grows polynomially in the size of the propositional proof. Previously, such a result was known either from FHE [Jin et al, STOC'24], or using indistinguishability obfuscation [Jain-Jin, FOCS'22]. - We construct predicate extractable hash for bit-fixing functions and monotone-policy batch arguments [Brakerski et al, CRYPTO 2023] from s-HE. Previously, these primitives were only known from FHE. - Finally, we demonstrate a simple construction of correlation-intractable hash (CIH) functions from s-HE, subsuming the previous result of [Jain-Jin, EUROCRYPT 2021].

We propose a new cryptographic primitive called "batched identity-based encryption'' (Batched IBE) and its thresholdized version. The new primitive allows encrypting messages with specific identities and batch labels, where the latter can represent, for example, a block number on a blockchain. Given an arbitrary subset of identities for a particular batch, our primitive enables efficient issuance of a single decryption key that can be used to decrypt all ciphertexts having identities that are included in the subset while preserving the privacy of all other ciphertexts. At the heart of our construction is a new technique that enables public aggregation (i.e. without knowledge of any secrets) of any subset of identities, into a succinct digest. This digest is used to derive, via a master secret key, a single *succinct* decryption key for all identities that were digested in this batch. In a threshold system, where the master key is distributed as secret shares among multiple authorities, our method significantly reduces the communication (and in some cases, computation) of the authorities. It achieves this by making their costs for key issuance independent of the batch size. We present a concrete instantiation of a Batched IBE scheme based on the KZG polynomial commitment scheme by Kate et al. (Asiacrypt'10) and a modified form of the BLS signature scheme by Boneh et al. (Asiacrypt'01). The construction is proven secure in the generic group model (GGM). In a blockchain setting, the new construction can be used for achieving mempool privacy by encrypting transactions to a block, opening only the transactions included in a given block and hiding the transactions that are not included in it. With the thresholdized version, multiple authorities (validators) can collaboratively manage the decryption process. Other possible applications include scalable support via blockchain for fairness of dishonest majority MPC, and conditional batched threshold decryption that can be used for implementing secure Dutch auctions and privacy preserving options trading.

Indistinguishability obfuscation (iO) turns a program unintelligible without altering its functionality and is a powerful cryptographic primitive that captures the power of most known primitives. Recent breakthroughs have successfully constructed iO from well-founded computational assumptions, yet these constructions are unfortunately insecure against quantum adversaries. In the search of post-quantum secure iO, a line of research investigates constructions from fully homomorphic encryption (FHE) and tailored decryption hint release mechanisms. Proposals in this line mainly differ in their designs of decryption hints, yet all known attempts either cannot be proven from a self-contained computational assumption, or are based on novel lattice assumptions which are subsequently cryptanalysed. In this work, we propose a new plausibly post-quantum secure construction of iO by designing a new mechanism for releasing decryption hints. Unlike prior attempts, our decryption hints follow a public Gaussian distribution subject to decryption correctness constraints and are therefore in a sense as random as they could be. To generate such hints efficiently, we develop a general-purpose tool called primal lattice trapdoors, which allow sampling trapdoored matrices whose Learning with Errors (LWE) secret can be equivocated. We prove the security of our primal lattice trapdoors construction from the NTRU assumption. The security of the iO construction is then argued, along with other standard lattice assumptions, via a new Equivocal LWE assumption, for which we provide evidence for plausibility and identify potential targets for further cryptanalysis.

An $(\epsilon_s, \epsilon_{zk})$-weak non-interactive zero knowledge (NIZK) proof system has soundness error at most $\epsilon_s$ and zero-knowledge error at most $\epsilon_{zk}$. We show that as long as NP is hard in the worst case, the existence of $(\epsilon_s, \epsilon_zk)$-weak NIZK arguments for NP with $\epsilon_{zk} + \sqrt{\epsilon_s} < 1$ for constants $\epsilon_{zk}$ and $\epsilon_s$ implies the existence of one-way functions. As an application, we obtain NIZK amplification theorems based on very mild worst-case complexity assumptions. Specifically, [Bitansky-Geier, CRYPTO'24] showed that $(\epsilon_s, \epsilon_{zk})$-weak NIZK proofs can be amplified to make their errors negligible, but needed to assume the existence of one-way functions. Our results can be used to remove the additional one-way function assumption and obtain NIZK amplification theorems that are (almost) unconditional; only requiring the mild worst-case assumption that if NP $\subseteq$ ioP/poly, then NP $\subseteq$ BPP.

Over two decades since their introduction in 2005, all major verifiable pairing delegation protocols for public inputs have been designed to ensure information-theoretic security. However, we note that a delegation protocol involving only ephemeral secret keys in the public view can achieve everlasting security, provided the server is unable to produce a pairing forgery within the protocol’s execution time. Thus, computationally bounding the adversary’s capabilities during the protocol’s execution, rather than across its entire lifespan, may be more reasonable, especially when the goal is to achieve significant efficiency gains for the delegating party. This consideration is particularly relevant given the continuously evolving computational costs associated with pairing computations and their ancillary blocks, which creates an ever-changing landscape for what constitutes efficiency in pairing delegation protocols. With the goal of fulfilling both efficiency and everlasting security, we present AmorE, a protocol equipped with an adjustable security and efficiency parameter for sequential pairing delegation, which achieves state-of-the-art amortized efficiency in terms of the number of pairing computations. For example, delegating batches of 10 pairings on the BLS48-575 elliptic curve via our protocol costs to the client, on average, less than a single scalar multiplication in G2 per delegated pairing, while still ensuring at least 40 bits of statistical security.

We introduce a general template for building garbled circuits with low communication, assuming decisional composite residuosity (DCR) and a circular security assumption. For the case of layered Boolean circuits, we can garble a circuit of size $s$ with communication proportional to $O(s/\log\log s)$ bits, plus an additive factor that is polynomial in the security parameter. For layered arithmetic circuits with $B$-bounded integer computation, we obtain a similar result: the garbled arithmetic circuit has size $O(s/\log\log s) \cdot (\secpar + \log B)$ bits, where $\secpar$ is the security parameter. In both cases, we can remove the circular security assumption by adding a term proportional to the circuit depth. These are the first constructions of general-purpose, garbled circuits with sublinear size, without relying on heavy tools like indistinguishability obfuscation or attribute-based and fully homomorphic encryption. To achieve these results, our main technical tool is a new construction of a form of homomorphic secret sharing (HSS) where some of the inputs are {semi-private}, that is, known to one of the evaluating parties. Through a new {relinearisation} technique that allows performing arbitrary additions and multiplications on semi-private shares, we build such an HSS scheme that supports evaluating any function of the form $C(x) \cdot C'(y)$, where $C$ is any polynomially-sized circuit applied to the semi-private input $y$, and $C'$ is a restricted-multiplication (or, NC1) circuit applied to the private input $x$. This significantly broadens the expressiveness of prior known HSS constructions.

The meteoric rise in power and popularity of machine learning models dependent on valuable training data has reignited a basic tension between the power of running a program locally and the risk of exposing details of that program to the user. At the same time, fundamental properties of quantum states offer new solutions to data and program security that can require strikingly few quantum resources to exploit, and offer advantages outside of mere computational run time. In this work, we demonstrate such a solution with quantum one-time tokens. A quantum one-time token is a quantum state that permits a certain program to be evaluated exactly once. One-time security guarantees, roughly, that the token cannot be used to evaluate the program more than once. We propose a scheme for building quantum one-time tokens for any randomized classical program, which include generative AI models. We prove that the scheme satisfies an interesting definition of one-time security as long as outputs of the classical algorithm have high enough min-entropy, in a black box model. Importantly, the classical program being protected does not need to be implemented coherently on a quantum computer. In fact, the size and complexity of the quantum one-time token is independent of the program being protected, and additional quantum resources serve only to increase the security of the protocol. Due to this flexibility in adjusting the security, we believe that our proposal is parsimonious enough to serve as a promising candidate for a near-term useful demonstration of quantum computing in either the NISQ or early fault tolerant regime.

Proof-Carrying Data (PCD) is a foundational tool for ensuring the correctness of incremental distributed computations that has found numerous applications in theory and practice. The state-of-the-art PCD constructions are obtained via accumulation or folding schemes. Bunz, Mishra, Nguyen, and Wang recently introduced the first hash-based accumulation scheme, which is secure in the random oracle model and instantiable with any linear error-correcting code. However, their construction only supports a bounded number of accumulation steps. We present Arc, a hash-based accumulation scheme that supports an unbounded number of accumulation steps. The core technique underlying our approach is a method for accumulating proximity claims to a Reed–Solomon code. Unlike prior work, we work in the list-decoding regime to obtain concrete efficiency improvements. We introduce the notion of Interactive Oracle Reductions (IORs) to enable a modular and simple security analysis. These extend prior notions of Reductions of Knowledge to the setting of Interactive Oracle Proofs.

A common drawback of secure vector summation protocols in the single-server model is that they impose at least one synchronization point between all clients contributing to the aggregation. This results in clients waiting on each other to advance through the rounds of the protocol, leading to large latency (or failures due to too many dropouts) even if the protocol is computationally efficient. In this paper we propose protocols in the single-server model where clients contributing data to the aggregation (i) send a single message to the server and (ii) can join aggregation sessions dynamically whenever they have resources, i.e., without the need for synchronizing their reporting time with any other clients. Our approach is based on a committee of parties that aid in the computation by running a setup phase before data collection starts, and a verification/decryption phase once it ends. Unlike existing committee-based protocols such as Flamingo (S&P 2023), the cost for committee members can be made sub-linear in the number of clients, and does not depend on the size of the input client vectors. Our experimental evaluation shows that our protocol, even while allowing dynamic client participation, is competitive with the state of the art protocols that do not have that feature in both computation and communication.

Garbling schemes are a fundamental cryptographic tool for enabling private computations and ensuring that nothing leaks beyond the output. As a widely studied primitive, significant efforts have been made to reduce their size. Until recently, all such schemes followed the Lindell and Pinkas paradigm for Boolean circuits (JoC 2009), where each gate is represented as a set of ciphertexts computed using only symmetric-key primitives. However, this approach is inherently limited to O(λ) bits per gate, where λ is the security parameter. Recently, it has been shown that achieving smaller garbled circuit size is possible under stronger assumptions, such as variants of Learning with Errors (LWE) or Indistinguishability Obfuscation (iO). In addition to requiring high-end cryptography, none of these constructions is black-box in the underlying cryptographic primitives, a key advantage of prior work. In this paper, we present the first approach to garbling Boolean circuits that makes a black-box use of a group and uses o(λ) bits per gate. Building on a novel application of the Reverse Multiplication-Friendly Embeddings (RMFE) paradigm (Cascudo et al., CRYPTO 2018), we introduce a new packing mechanism for garbling schemes. Our results introduce two new succinct schemes that achieve improved rates by a factor of √log(λ), retaining the black-box usage. (1) Our first scheme is proven in the Generic Group model (GGM) for circuits with Ω(√log(λ)) width, obtaining a garbled circuit size of λ . |C| / √log(λ). (2) Our second scheme is proven in the plain model under the Power-DDH assumption, attaining a garbled circuit size of λ . |C| / √log(λ) + poly(λ) . |C| . depth(C), but is restricted to layered circuits. **Our schemes are the first to achieve sublinear (in λ) cost per gate under assumptions that do not imply fully homomorphic encryption**; in addition, our scheme is also the first to achieve this while making a black-box use of cryptography.

The quantum Haar random oracle model is an idealized model where every party has access to a single Haar random unitary and its inverse. We construct strong pseudorandom unitaries in the quantum Haar random oracle model. This strictly improves upon prior works who either only prove the existence of pseudorandom unitaries in the inverse-less quantum Haar random oracle model [Ananth, Bostanci, Gulati, Lin, EUROCRYPT 2025] or prove the existence of a weaker notion (implied by strong pseudorandom unitaries) in the quantum Haar random oracle model [Hhan, Yamada, 2024]. We also provide an alternate method of joining Haar random unitaries from the gluing lemma from [Schuster, Haferkamp, Huang, QIP 2025] that is secure against adversaries with inverse query access to the joined unitary.Taken together, our results have the following implication for the plain model: strong pseudo-random unitaries can generically have their length extended, and can be constructed using only O(n^(1/c)) bits of randomness, for any constant c, if strong pseudorandom unitaries exists.Our results also present a viable approach for building quantum pseudorandomness from random quantum circuits and analyzing pseudo-random objects in nature. As part of our analysis, we formalize a “strong path-recording framework'', which generalizes the path-recording framework of [Ma, Huang, QIP 2025].

We introduce the notion of \emph{pseudorandom obfuscation}, a way to obfuscate (keyed) pseudorandom functions $f_K$ in an average-case sense. We study several variants of pseudorandom obfuscation and show a number of applications. \begin{enumerate} \item \textbf{Applications in the iO World:} Our weakest variant of pseudorandom obfuscation, named obfuscation for identical pseudorandom functions (iPRO), is weaker than indistinguishability obfuscation (iO): rather than obfuscating arbitrary circuits as in iO, iPRO only obfuscates circuits computing pseudorandom functions. We show that iPRO already enables several applications of iO, such as unleveled fully homomorphic encryption (without assuming circular security) and succinct randomized encodings. \item \textbf{From iPRO to iO:} Despite being a weaker notion than iO, we show two transformations from iPRO to iO. Our first (and main) construction builds iO from iPRO plus standard assumptions on cryptographic bilinear maps. Our second construction builds iO, and even ideal obfuscation, from iPRO alone in the pseudorandom oracle model (Jain, Lin, Luo and Wichs, CRYPTO 2023). \end{enumerate} We also formulate stronger variants of pseudorandom obfuscation that help us go beyond the applications of indistinguishability obfuscation. \begin{enumerate} \setItemnumber{3} \item \textbf{Applications outside the iO World:} We show how to construct a succinct witness encryption scheme from a strong version of PRO, where the size of the ciphertext is independent of the witness size. Such a witness encryption scheme is not known to exist even assuming iO. \item \textbf{Construction:} We show a {\em heuristic} construction of the strongest version of PRO, secure under the sub-exponential hardness of the learning with errors (LWE) problem, and the private-coin evasive LWE heuristic (Wee, EUROCRYPT 2022; Tsabary, CRYPTO 2022). \end{enumerate} \noindent Finally, we highlight some barriers in achieving the strongest version of pseudorandom obfuscation.

Continuous Group Key Agreement (CGKA) is the primitive underlying group messaging. It allows group members to issue updates, by which they rotate their key material in order to achieve forward secrecy and post compromise security. The MLS IETF working group proposed TreeKEM as a CGKA. It arranges the N users in a binary tree, where each node is associated with a public-key, and a user knowns the corresponding secret keys from their leaf to the root. To update, a user must just replace keys at \log(N) nodes, which requires them to create and upload \log(N) ciphertexts. Such updates must be processed sequentially by all users, which for large groups is impractical. To allow for concurrent updates, TreeKEM uses the ``propose and commit'' approach, where multiple users can concurrently propose to update (by just sampling a fresh leaf key), and a single user can then commit all proposals at once. Unfortunately this process destroys the binary tree structure as the tree gets pruned and some nodes must be ``blanked'' at the cost of increasing the in-degree of others, which can make future updates more costly. In the worst case, the update cost (in terms of uploaded ciphertexts) per user can grow from \log(N) to \Omega(N). Our first contribution is to show that the efficiency is terrible already if the proposers and committers are chosen at random (and not worst case): even if there's just one commit for every proposal the cost is already over \sqrt{N}, and it approaches $N$ as this ratio changes towards more proposals. Our main contribution is a new variant of propose and commit for TreeKEM which provably achieves an update cost of \Theta(\log(N)) assuming the proposers and committers are chosen at random. To achieve this we put a slightly higher cost on the proposers, which now upload \log(N) ciphertexts. This allows the committer to keep the tree mostly intact as pruning mostly happens at the very top layers.

Today, many auctions are carried out with the help of in- termediary platforms like Google and eBay. These platforms serve as a rendezvous point for the buyers and sellers, and charge a fee for its ser- vice. We refer to such auctions as platform-assisted auctions. Tradition- ally, the auction theory literature mainly focuses on designing auctions that incentivize the buyers to bid truthfully, assuming that the platform always faithfully implements the auction. In practice, however, the plat- forms have been found to manipulate the auctions to earn more profit, resulting in high-profile anti-trust lawsuits. We propose a new model for studying platform-assisted auctions in the permissionless setting, where anyone can register and participate in the auction. We explore whether it is possible to design a dream auction in this new model, such that honest behavior is the utility-maximizing strategy for each individual buyer, the platform, the seller, as well as platform-seller or platform-buyer coalitions. Through a collection of fea- sibility and infeasibility results, we carefully characterize the mathemat- ical landscape of platform-assisted auctions. Interestingly, our work reveals exciting connections between cryptogra- phy and mechanism design. We show how cryptography can lend to the design of an efficient platform-assisted auction with dream properties. Al- though a line of works have also used multi-party computation (MPC) or the blockchain to remove the reliance on a trusted auctioneer, our work is distinct in nature in several dimensions. First, we initiate a sys- tematic exploration of the game theoretic implications when the service providers (e.g., nodes that implement the MPC or blockchain protocol) are strategic and can collude with sellers or buyers. Second, we observe that the full simulation paradigm used in the standard MPC literature is too stringent and leads to high asymptotical costs. Specifically, because every player has a different private outcome in an auction protocol, to the best of our knowledge, running any generic MPC protocol among the players would incur at least n 2 total cost where n is the number of buyers. We propose a new notion of simulation called utility-dominated emulation that is sufficient for guaranteeing the game-theoretic proper- ties needed in an auction. Under this new notion of simulation, we show how to design efficient auction protocols with quasilinear efficiency, which gives an n-fold improvement over any generic approach.

Fully Homomorphic Encryption (FHE) allows computations on encrypted data without requiring decryption, ensuring data privacy during processing. However, FHE introduces a significant expansion of ciphertext sizes compared to plaintexts, which results in higher communication. A practical solution to mitigate this issue is transciphering, where only the master key is homomorphically encrypted, while the actual data is encrypted using a symmetric cipher, usually a stream cipher. The server then homomorphically evaluates the stream cipher to convert the encrypted data into a homomorphically encrypted form. We introduce Transistor, a stream cipher specifically designed for efficient homomorphic evaluation within the TFHE scheme, a widely-used FHE framework known for its fast bootstrapping and ability to handle low-precision data. Transistor operates on F_{17} which is chosen to optimize TFHE performances. Its components are carefully engineered to both control noise growth and provide strong security guarantees. First, a simple TFHE-friendly implementation technique for LFSRs allows us to use such components to cheaply increase the state size. At the same time, a small Finite State Machine is the only part of the state updated non-linearly, each non-linear operation corresponding in TFHE to a rather expensive Programmable Bootstrapping. This update is done using an AES-round-like transformation. But, in contrast to other stream ciphers like SNOW or LEX, our construction comes with information-theoretic security arguments proving that an attacker cannot obtain any information about the secret key from three or fewer consecutive keystream outputs. These information-theoretic arguments are then combined with a thorough analysis of potential correlations to bound the minimal keystream length required for recovering the secret key. Our implementation of Transistor significantly outperforms the state of the art of TFHE transciphering, achieving a throughput of over 60 bits/s on a standard CPU, all while avoiding the need for an expensive initialization process.

In the last decade, the introduction of advanced crypto- graphic protocols operating on large finite fields F_q has raised the need for efficient cryptographic primitives in this setting, commonly referred to as Arithmetization-Oriented (AO). The cryptanalysis of AO hash functions is essentially done through the study of the CICO problem on the underlying permutation. Two recent works at Crypto 2024 and Asiacrypt 2024 managed to solve the CICO problem much more efficiently than traditional Gröbner basis methods, respectively using advanced Gröbner basis techniques and resultants. In this paper, we propose an attack framework based on resultants that applies to a wide range of AO permutations and improves significantly upon these two recent works. Our improvements mainly come from an efficient reduction procedure that we propose and rigorously analyze, taking advantage of fast multivariate multiplication. We present the most efficient attacks on Griffin, Arion, Anemoi, and Rescue. We show that most variants of Griffin, Arion and Anemoi fail to reach the claimed security level. For the first time, we successfully break a parameter set of Rescue, namely the 512-bit security in 2^{475}. The presented theory and complexity estimates are backed up with experimental attacks. Notably, we practically find CICO solutions for 8 out of 10 rounds of Griffin, and 11 out of 20 rounds of Anemoi, and 6 out of 18 rounds of Rescue, improving by respectively 1, 3 and 1 rounds on the previous best practical attacks.

Tweakable enciphering modes (TEMs) provide security in various storage and space-critical applications, including disk and file-based encryption and packet-based communication protocols. XCB-AES (originally introduced as XCBv2) is specified in the IEEE 1619.2 standard for encryption of sector-oriented storage media and comes with a formal security proof for block-aligned messages. In this work, we present the \textit{first} plaintext recovery attack on XCB-AES -- \textit{the shared difference attack}, demonstrating that the security of XCB-AES is fundamentally flawed. Our plaintext recovery attack is highly efficient and requires only two queries (one enciphering and one deciphering), breaking the claimed $\mathsf{vil\text{-}stprp}$, $\mathsf{stprp}$ as well as the basic $\mathsf{sprp}$ security. Our shared difference attack exploits an inherent property of polynomial hash functions called \textit{separability}. We pinpoint the exact flaw in the security proof of XCB-AES, which arises from the separability of polynomial hash functions. We show that this vulnerability in the XCB design strategy has gone unnoticed for over 20 years and has been inadvertently replicated in many XCB-style TEM designs, including the IEEE 1619.2 standard XCB-AES. We also apply the shared difference attack to other TEMs based on XCB -- XCBv1, HCI, and MXCB, invalidating all of their security claims, and discuss some immediate countermeasures. Our findings are the first to highlight the need to reassess the present IEEE 1619.2 standard as well as the security and potential deployments of XCB-style TEMs.

Following Ibukiyama, Katsura and Oort, all principally polarized superspecial abelian surfaces over $\overline{\mathbb{F}}_p$ can be represented by a certain type of $2 \times 2$ matrix $g$, having entries in the quaternion algebra $B_{p,\infty}$. We present a heuristic polynomial-time algorithm which, upon input of two such matrices $g_1, g_2$, finds a "connecting matrix" representing a polarized isogeny of smooth degree between the corresponding surfaces. Our algorithm should be thought of as a two-dimensional analog of the KLPT algorithm from 2014 due to Kohel, Lauter, Petit and Tignol for finding a connecting ideal of smooth norm between two given maximal orders in $B_{p, \infty}$. The KLPT algorithm has proven to be a versatile tool in isogeny-based cryptography, and our analog has similar applications; we discuss two of them in detail. First, we show that it yields a polynomial-time solution to a two-dimensional analog of the so-called constructive Deuring correspondence: given a matrix $g$ representing a superspecial principally polarized abelian surface, realize the latter as the Jacobian of a genus-$2$ curve (or, exceptionally, as the product of two elliptic curves if it concerns a product polarization). Second, we show that, modulo a plausible assumption, Charles-Goren-Lauter style hash functions from superspecial principally polarized abelian surfaces require a trusted set-up. Concretely, if the matrix $g$ associated with the starting surface is known then collisions can be produced in polynomial time. We deem it plausible that all currently known methods for generating a starting surface indeed reveal the corresponding matrix. As an auxiliary tool, we present an efficient method for converting isogenies of powersmooth degree into the corresponding connecting matrix, a step for which a previous approach by Chu required super-polynomial (but sub-exponential) time.

Threshold signatures are one of the most important cryptographic primitives in distributed systems. Of particular interest is the threshold Schnorr signature, a pairing-free signature with efficient verification, compatible with standardized EdDSA (non-threshold) signature. However, most threshold Schnorr signatures have only been proven secure against a static adversary, which has to declare its corruptions before the protocol execution. Many existing adaptively secure constructions require either secure erasures or non-standard assumptions, such as the algebraic group model or hardness of the algebraic one-more discrete logarithm problem. The latest adaptively secure threshold Schnorr signature schemes under standard assumptions require five rounds of communication to create a single signature, limiting its practicality. In this work, we present Gargos, a three-round, adaptively secure threshold Schnorr signature scheme based on the hardness of the decisional Diffie-Hellman (DDH) problem in the random oracle model (ROM). Our protocol supports full corruption threshold t < n, where t is the signing threshold and n is the total number of signers. We achieve our result with an enhanced proof technique that enables us to eliminate two rounds of communication from the recent Glacius scheme (Eurocrypt 2025). We believe our techniques are of independent interest to further research in improving the round complexity of multi-party signing protocols.

SQIsign is the leading digital signature from isogenies. Despite the many improvements that have appeared in the literature, all its recents variants lack a complete security proof. In this work, we provide the first full security proof of SQIsign, as submitted to the second round of NIST’s on-ramp track for digital signatures. To do so, we introduce a new framework, which we call Fiat--Shamir with hints, that captures all those protocols where the simulator needs additional information to simulate a transcript. Using this framework, we show that SQIsign is EUF-CMA secure in the ROM, assuming the hardness of the One Endomorphism problem with hints, or the hardness of the Full Endomorphism Ring problem with hints together with a hint indistinguishability assumption; all assumptions, unlike previous ones in the literature, are non-interactive. Along the way, we prove several intermediate results that may be of independent interest.

HQC is a code-based cryptosystem that has recently been announced for standardization after the fourth round of the NIST post-quantum cryptography standardization process. During this process, the NIST specifically required submitters to provide two kinds of implementation: a reference one, meant to serve lisibility and compliance with the specifications; and an optimized one, aimed at showing the performance of the scheme alongside other desirable properties such as resilience against implementation misuse or side-channel analysis. While most side-channel attacks regarding PQC candidates running in this process were mounted over reference implementations, very few consider the optimized, allegedly side-channel resistant (at least, constant-time), implementations. Unfortunately, HQC optimized version only targets x86-64 with Single Instruction Multiple Data~(SIMD) support, which reduces the code portability, especially for non-generalist computers. In this work, we present two power side-channel attacks on the optimized HQC implementation with just the SIMD support deactivated. We show that the power leaks enough information to recover the private key, assuming the adversary can ask the target to replay a legitimate decryption with the same inputs. Under this assumption, we first present a key-recovery attack targeting standard Instruction Set Architectures~(ARM T32, RISC-V, x86-64) and compiler optimization levels. It is based on the well known Hamming Distance model of power consumption leakage, and exposes the key from a single oracle call. During execution on a real target, we show that a different leakage, stemming from to the micro-architecture, simplifies the recovery of the private key. This more direct second attack, succeeds with a 99\% chance from 83 executions of the same legitimate decryption. While the weakness leveraged in this work seems quite devastating, we discuss simple yet effective and efficient countermeasures to prevent such a key-recovery.

In this paper, we present the first practical algorithm to compute an effective group action of the class group of any imaginary quadratic order $\qO$ on a set of supersingular elliptic curves primitively oriented by $\qO$. Effective means that we can act with any element of the class group directly, and are not restricted to acting by products of ideals of small norm, as for instance in CSIDH. Such restricted effective group actions often hamper cryptographic constructions, e.g.\ in signature or MPC protocols. Our algorithm is a refinement of the Clapoti approach by Page and Robert, and uses $4$-dimensional isogenies. As such, it runs in polynomial time, does not require the computation of the structure of the class group, nor expensive lattice reductions, and our refinements allows it to be instantiated with the orientation given by the Frobenius endomorphism. This makes the algorithm practical even at security levels as high as CSIDH-4096. Our implementation in SageMath takes 1.5s to compute a group action at the CSIDH-512 security level, 21s at CSIDH-2048 level and around 2 minutes at the CSIDH-4096 level. This marks the first instantiation of an effective cryptographic group action at such high security levels. For comparison, the recent KLaPoTi approach requires around 200s at the CSIDH-512 level.

Hiding the metadata in Internet protocols serves to protect user privacy, dissuade traffic analysis, and prevent network ossification. Fully encrypted protocols require even the initial key exchange to be obfuscated: a passive observer should be unable to distinguish a protocol execution from an exchange of random bitstrings. Deployed obfuscated key exchanges such as Tor's pluggable transport protocol obfs4 are Diffie-Hellman-based, and rely on the Elligator encoding for obfuscation. Recently, Günther, Stebila, and Veitch (CCS '24) proposed a post-quantum variant pq-obfs, using a novel building block called obfuscated key encapsulation mechanisms (OKEMs): KEMs whose public keys and ciphertexts look like random bitstrings. For transitioning real-world protocols, pure post-quantum security is not enough. Many are taking a hybrid approach, combining traditional and post-quantum schemes to hedge against security failures in either component. While hybrid KEMs are already widely deployed (e.g., in TLS 1.3), existing hybridization techniques fail to provide hybrid obfuscation guarantees for OKEMs. Further, even if a hybrid OKEM existed, the pq-obfs protocol would still not achieve hybrid obfuscation. In this work, we address these challenges by presenting the first OKEM combiner that achieves hybrid IND-CCA security with hybrid ciphertext obfuscation guarantees, and using this to build Drivel, a modification of pq-obfs that is compatible with hybrid OKEMs. Our OKEM combiner allows for a variety of practical instantiations, e.g., combining obfuscated versions of DHKEM and ML-KEM. We additionally provide techniques to achieve unconditional public key obfuscation for LWE-based OKEMs, and explore broader applications of hybrid OKEMs, including a construction of the first hybrid password-authenticated key exchange (PAKE) protocol secure against adaptive corruptions in the UC model.

Parallel Byzantine broadcast (PBC) (also known as Interactive Consistency), is a fundamental problem in distributed computing and cryptography which asks that all parties reliably distribute a message to all other parties. We give the first communication-efficient protocol for PBC in the model with plain public keys (i.e., no trusted dealer) which achieves security against an adaptive adversary that can corrupt up to $t