International Association
for Cryptologic Research

Secure multiparty computation (MPC) faces a fundamental efficiency trade-off between round complexity and communication complexity: without fully homomorphic encryption, protocols with constant round complexity (e.g., protocols based on garbled circuits) incur high communication cost, while communication-efficient approaches (e.g., protocols based on secret sharing) have round complexity linear in the depth of the circuit. In this work, we focus on reducing the communication complexity of constant-round MPC protocols in the honest majority setting. Existing results either rely on strong assumptions (e.g., random oracles, DDH, LPN) or incur high communication of $\Omega(|C|n^2\kappa)$ bits under one-way functions (OWFs). However, non-constant-round MPC protocols can achieve linear communication in the number of parties even with information-theoretic security. We resolve this gap by presenting the first \emph{constant-round} honest majority MPC protocol with \emph{linear} communication complexity of $O(|C|n\kappa + n^2\kappa^2+n^4\kappa)$ only from OWFs. We introduce novel techniques for computing garbled circuits via party virtualization and efficient local computation of virtual parties, which optimize the existing protocols on multiparty garbling. These allow us to overcome the $O(n^2\kappa)$ bit of communication per-gate bottleneck of prior protocols, matching the scalability of the best non-constant-round protocols in the same setting.

Random beacons play a critical role in blockchain protocols by providing publicly verifiable, unpredictable randomness essential for secure assignment of protocol roles such as block producers and committee membership. In the interest of efficiency, many deployed blockchains adopt beacon algorithms that suffer from grinding: an adversarial attack in which a party exploits freedom given by the protocol to bias the outcome of the random beacon by resampling it several times and picking the most desirable outcome. To compound the problem, beacons often operate in an iterative manner, where the beacon output produced during one protocol epoch serves as the random seed for the beacon’s invocation in the next epoch. This amplifies the security threat, as such attacks may then aggregate their power over many epochs. In this article, we formulate a generic framework for information-theoretic analysis of grinding in iterated randomness beacons. We define the natural grinding capacity of a beacon, intuitively corresponding to the amount of grinding it allows with a uniformly random seed. We then prove that sufficiently strong tail bounds on this quantity can be transformed into a guarantee on smooth min-entropy of the iterated beacon’s output, even conditioned on all past outputs and irrespective of the inner workings of the beacon. Such min-entropy guarantees can immediately be translated into corresponding statements about various applications of the beacon to committee selection, incentives, or underlying protocol security. Our main technical result concerns conventional longest-chain protocols, where we establish that the combinatorial structure of the forest of longest chains can be leveraged to control grinding. Instantiating the generic framework with these grinding upper bounds, we establish that the randomness beacon of the Ouroboros Praos protocol is secure against adversaries controlling up to about 12% of stake—even without any assumptions bounding the adversarial computational power invested into grinding. This is a qualitatively new guarantee for the protocol.

The ARX structure plays a crucial role in symmetric-key primitives, with differential-linear (DL) attacks being among the most effective cryptanalysis techniques against ARX ciphers. In this paper, we present a systematic re-decomposition technique for DL distinguishers of ARX ciphers and identify for the first time the hourglass(-like) structural commonalities among optimal DL distinguishers searched out by various deduction techniques, also supported through comprehensive experiments, which motivate us to develop an efficient and generalized approach to construct optimal hourglass(-like) structural DL distinguishers. Our method yields significant advances when applied to \speck, \alzette, and the underlying permutations of \siphash{} and \chaskey: (1) the first 11- to 14-round DL distinguishers of \alzette; (2) the first (valid) DL distinguishers for 11-round \speck32, 12-round \speck48, and 16-round \speck96; (3) \emph{deterministic} (correlation $\pm1$) 3-round DL distinguishers for \siphash-2-4 and significantly improved 4-round ones. All these distinguishers are equipped with both theoretical and experimental verifications. We further analyze ARX-based Latin dance stream ciphers, achieving improved DL distinguishers for 7/7.25-round \chacha, 8-round \salsa, and 5.5-round \forro. Though some of the improvements are not significant, we have verified the effectiveness of our method across a broader range of instances. This work provides new insights for DL distinguisher construction and enhances understanding of the security of ARX ciphers.

Granular Synchrony (Giridharan et al. DISC 2024) is a new network model where the network is viewed as a graph consisting of synchronous, partially synchronous and asynchronous communication links. It has been shown that Granular Synchrony allows deterministic Byzantine agreement protocols to achieve a corruption threshold $n/3 \leq t < n/2$ in between complete asynchrony and complete synchrony if and only if the network satisfies the right condition, namely, if no two groups of honest parties of size $n-2t$ can be partitioned from each other. In this work, we show that the same network condition is also tight for Agreement on a Common Subset (ACS), Verifiable Secret Sharing (VSS) and secure Multi-Party Computation (MPC) with guaranteed output delivery when the corruption threshold is between one-third and one-half. Our protocols, being randomized, assume that all links are either synchronous or asynchronous, and do not assume any partially synchronous links. Our ACS protocol incurs an amortized communication cost of $O(n^3\lambda)$ bits per inputs, and our VSS and MPC protocols incur amortized communication costs of $O(n^3)$ and $O(n^4)$ field elements per secret and per multiplication gate, respectively. To design our protocols, we also construct protocols for Reliable Broadcast and Externally Valid Byzantine Agreement (EVBA), which are of independent interest.

State-of-the-art actively secure multi-party computation protocols, like SPDZ (Damgård et al., CRYPTO 2012), use correlated randomness, like Beaver triples, to achieve a highly efficient online phase. For a long time, the generation of the correlated randomness in the offline phase relied on classical cryptographic primitives, like somewhat homomorphic encryption or oblivious transfer, that required significant communication. More recently, Boyle et al. (FOCS 2020) defined a new primitive called pseudorandom correlation functions (PCFs) to generate correlated randomness non-interactively. PCFs set up keys for each party in an initial interactive phase, which can then be used by the parties to generate a large number of shares of the correlated randomness without further communication. In the random oracle model (ROM), two-party PCFs can be generically constructed based on evaluating a weak pseudorandom function (WPRF) using a powerful-enough homomorphic secret sharing scheme. However, the concrete efficiency of instantiations of this approach has not been analyzed so far. There are also some works that construct PCFs based on other approaches, but they cannot be used for correlations of degree >= 2 (e.g., Beaver triples) over large rings/fields (such as those used in SPDZ). In this paper, we improve the complexity and concrete efficiency of PCFs over large rings/fields by presenting a new generic PCF based on the hardness of the ring-learning with rounding (Ring-LWR) problem and FHE. We only share BFV keys in the initial interactive phase. The two parties then use the random oracle to locally sample BFV (pseudo-)ciphertexts encrypting pseudorandom plaintexts. We use a new bootstrapping algorithm for these (pseudo-)ciphertexts that reduces initially saturated noise to a level where the parties can use the homomorphic properties of the BFV scheme to correlate the encrypted randomness locally. Both parties can then produce, without further interaction, shares of the correlated randomness with their secret key share. Our new PCF works with any form of correlated randomness that can be expressed as an arithmetic circuit over a base ring Z_t or field F_p^d, e.g., Beaver or matrix triples.

Sublinear proof sizes have recently become feasible in verifiable machine learning (VML), yet no approach achieves the trio of strictly linear prover time, logarithmic proof size and verification time, and architecture privacy. Hurdles persist because we lack a succinct commitment to the full neural network and a framework for heterogeneous models, leaving verification dependent on architecture knowledge. Existing limits motivate our new approach: a unified proof-composition framework that casts VML as the design of zero-knowledge succinct non-interactive arguments of knowledge (zkSNARKs) for matrix computations. Representing neural networks with linear and non-linear layers as a directed acyclic graph of atomic matrix operations enables topology-aware composition without revealing the graph. Modeled this way, we split proving into a reduction layer and a compression layer that attests to the reduction with a proof of proof. At the reduction layer, inspired by reduction of knowledge (Crypto '23), root-node proofs are reduced to leaf-node proofs under an interface standardized for heterogeneous linear and non-linear operations. Next, a recursive zkSNARK compresses the transcript into a single proof while preserving architecture privacy.

In its decisional form, the module-Lattice Isomorphism Problem (decision module-LIP) has received first attention recently in a paper by Ling, Liu and Mendelsohn. The authors gave a polynomial-time algorithm to distinguish spinor genera within the genus of a quadratic binary $\mathcal{O}_F$-lattice, assuming that $\mathcal{O}_F$ is a principal ideal domain. However, this algorithm would not impact cryptographic schemes based on decision module-LIP for lattices such as those employed in HAWK, i.e., for binary $\mathcal{O}_K$-lattices equipped with an Hermitian form (with $K$ a cyclotomic number field). Motivated by HAWK's framework, we investigate a concept that serves as an analogue of the spinor genus for Hermitian lattices, called special genus. This notion was studied by Shimura who provided a complete set of invariants for describing special genera. Building on this result, we propose an algorithm to determine whether two Hermitian lattices belong to the same special genus. Specifically for HAWK's lattice and siblings, our algorithm runs in classical polynomial-time. Nevertheless we provide numerical evidence suggesting that the ability to distinguish special genera does not, in practice, constitute a significative advantage for solving decision module-LIP.

Fully Homomorphic Encryption (FHE) enables secure computation over encrypted data, offering a breakthrough in privacy-preserving computing. Despite its promise, the practical deployment of FHE has been hindered by the significant computational overhead, especially in general-purpose bootstrapping schemes. In this work, we build upon the recent advancements of~\cite{LY23} to introduce a variant of the functional/programmable bootstrapping. By carefully sorting the steps of the blind rotation, we reduce the overall number of external products without compromising correctness. To further enhance efficiency, we propose a novel modulus-switching technique that increases the likelihood of satisfying pruning conditions, reducing computational overhead. Extensive benchmarks demonstrate that our method achieves a speedup ranging from 1.75x to 8.28x compared to traditional bootstrapping and from 1.26x to 2.14x compared to~\cite{LY23} bootstrapping techniques. Moreover, we show that this technique is better adapted to the $\indcpad$ security model by reducing the performance downgrade it implies.

Incrementally verifiable computation (IVC) is a powerful cryptographic primitive, particularly suited for proving long-running machine computations. Previous work shows that IVC can be constructed by recursively composing SNARKs. Unfortunately, theoretical challenges limit the provable security of known IVC constructions. Recursive composition may quickly lead to a blowup in extraction time and may require arithmetic circuits to enforce constraints about random oracle calls. Furthermore, composition presents a practical challenge: proofs are often expressed in a form that is not friendly to the arithmetic circuits that produce them. To mitigate the theoretical challenges, we present the Open-and-Sign Random Oracle Model (osROM) as an extension to the signed random oracle of Chiesa and Tromer (ICS `10). This model, while strictly harder to instantiate than the Random Oracle Model, allows the design of protocols that can efficiently verify calls to the oracle and support straight-line extractors. As a result, IVC constructions in the osROM can be shown to have provable security for polynomial depths of computation. Under our new model, we construct a framework to build secure IVC schemes from simple non-interactive reductions of knowledge. Our construction natively supports cycles of elliptic curves in the style of Ben-Sasson \textit{et al}. (CRYPTO `14), thus answering the practical challenge outlined above. Finally, we analyze the HyperNova (CRYPTO `24) IVC scheme in the osROM and show that it is secure over a two-cycle of elliptic curves, for polynomial depths of computation.

Hashing to elliptic curve groups is a fundamental primitive underlying numerous cryptographic applications, including multiset hashing and BLS signatures. With the recent rise of zero-knowledge applications, these primitives are increasingly used in constraint programming settings. For example, multiset hashing enables memory consistency checks in zkVMs, while BLS signatures are widely used in zkPoS protocols. In such cases, it becomes critical for hash-to-elliptic-curve-group constructions to be constraint-friendly. However, existing constructions rely on cryptographic hash functions that are expensive to represent in arithmetic constraint systems, resulting in high proving costs in these applications. We propose a constraint-efficient alternative: a map-to-elliptic-curve-group relation that bypasses the need for cryptographic hash functions and can serve as a drop-in replacement for hash-to-curve constructions in practical settings, including the aforementioned applications. Our relation naturally supports witness-based instantiations within constraint programming frameworks, enabling efficient integration into zero-knowledge circuits. We formally analyze the security of our approach in the elliptic curve generic group model (EC-GGM). Our implementation in Noir/Barretenberg demonstrates the efficiency of our construction in constraint programming: it achieves over 60x fewer constraints than the best hash-to-elliptic-curve-group alternatives, and enables 50-100x faster proving times at scale.

Tamper-detection codes (TDCs) are fundamental objects at the intersection of cryptography and coding theory. A TDC encodes messages in such a manner that tampering the codeword causes the decoder to either output the original message, or reject it. In this work, we study quantum analogs of one of the most well-studied adversarial tampering models: the so-called $t$-split-state tampering model, where the codeword is divided into $t$ shares, and each share is tampered with ``locally". It is impossible to achieve tamper detection in the split-state model using classical codewords. Nevertheless, we demonstrate that the situation changes significantly if the message can be encoded into a multipartite quantum state, entangled across the $t$ shares. Concretely, we define a family of quantum TDCs defined on any $t\geq 3$ shares, which can detect arbitrary split-state tampering so long as the adversaries are unentangled, or even limited to a finite amount of pre-shared entanglement. Previously, this was only known in the limit of asymptotically large $t$. As our flagship application, we show how to augment threshold secret sharing schemes with similar tamper-detecting guarantees. We complement our results by establishing connections between quantum TDCs and quantum encryption schemes.

As a theoretical cornerstone of post-quantum cryptography, the Learning With Errors (LWE) problem serves as the security foundation for standardized algorithms such as Kyber and Dilithium. Recently, a framework for provable dual attacks on LWE has been proposed by Pouly et al. in Eurocrypt 2024, addressing the limitations in effectiveness caused by existing methods' reliance on heuristic assumptions in LWE dual attacks. Their paper also poses an open problem on how to formally integrate modulus switching into this framework to reduce attack costs. The main purpose of this paper is to give a solution of this open problem by presenting an improved provable dual attack method that incorporates modulus switching and Chinese Remainder Theorem (CRT) techniques. First, we design a modulus switching mechanism that eliminates practical errors via the Poisson summation formula. By embedding the inherent noise from modulus switching into a rational lattice framework, our approach effectively preventing the risk of attack failure caused by the merging of such errors with LWE noise. Theoretical guarantees (Theorems \ref{main_theorem} and \ref{main_theorem_entire}) rigorously quantify the parameter ranges for successful attacks. Second, we introduce a CRT-based secret recovery method that aggregates partial secrets from independent sub-attacks. By leveraging the Chinese Remainder Theorem to reconstruct full secrets from congruence relations, our method adapts to arbitrary secret distributions. Furthermore, by using a tighter variant of Banaszczyk's measure inequality, we obtain a precise parameter range for the dual attack's efficacy through rigorous mathematical proof, and achieve the same complementary gap with the contradictory regime (proposed by Ducas et al.) as in Pouly et al.'s work. Experiments show $15$-$29$ bit superior performance in attack estimation compared to the original framework.

The block cipher (BC) mode for realizing a variable-input-length strong tweakable pseudorandom permutation (VIL-STPRP), also known as the accordion mode, is a rapidly growing research field driven by NIST's standardization project, which considers \textsf{AES} as a primitive. Widely used VIL-STPRP modes, such as \textsf{HCTR2}, have birthday-bound security and provide only 64-bit security with \textsf{AES}. To provide higher security, NIST is considering two directions: to develop new modes with beyond-birthday-bound (BBB) security and to use \textsf{Rijndael-256-256} with \textsf{HCTR2}. This paper pursues the first direction while maintaining compatibility with \textsf{HCTR2}. In particular, we provide two solutions to achieve BBB security for two different approaches: (i) general cases without any conditions on the tweak and (ii) under the condition that the same tweak is not repeated too often as adopted in \textit{bbb-ddd-AES} recently presented at Eurocrypt 2025. For the first approach, we propose a new mode, \textsf{CHCTR}, that iterates \textsf{HCTR2} with two independent keys, which achieves $2n/3$-bit security in the multi-user (mu) setting and satisfies NIST's requirements. For the second approach, we prove mu security of \textsf{HCTR2}, which allows us to apply the tweak-based key derivation (\textsf{TwKD}) to \textsf{HCTR2} in a provable manner. When the number of BC calls processed by a single tweak is upper-bounded by $2^{n/3}$, \textsf{HCTR2-TwKD} achieves $2n/3$-bit mu security. By benchmarking optimized software implementations, we show that \textsf{CHCTR} with \textsf{AES-256} outperforms \textsf{HCTR2} with \textsf{Rijndael-256-256}, in all the twelve processor models examined. Similarly, \textsf{HCTR2-TwKD} outperforms \textit{bbb-ddd-AES} in general cases, and it is even comparable to \textit{bbb-ddd-AES} rigorously optimized for tweak-repeating use cases using precomputation.

In this paper, we develop a new framework for vectorial fast correlation attacks, which exploits the vector-wise correlation in a novel and different approach from the previous Goli$\acute{c}$'s attack and gives the complete theoretical predictions of the attack complexities. First, the concept of correlation profile is introduced to characterize both the correlation of some linear approximation and the number of approximations having this correlation, which is not captured by the current notion of capacity or the Squared Euclidean Imbalance (SEI). It is shown how to construct the attack vector by carefully selecting the component-wise linear approximations to make a maximal usage of the inherent correlations. Second, we show how to transform and deliver the secret key information in the constructed vector by sequentially deriving linear subspaces from the original vector when the correlation profile is favorable. We further devise an efficient decoding algorithm to restore the partial secret key information retained in the last linear subspace, which allows for the recovery of the full secret information subsequently. Last, we present improved state recovery attacks on the ISO/IEC 29167-13 standard Grain-128a, the eSTREAM finalists Grain v1 and Sosemanuk, respectively by the new method. We resolve the open problem of detecting the output masks for Grain-like ciphers other than MILP at Crypto 2018 and propose a new algorithm based on graph theory to dissect complicated Boolean functions with many variables and compute its distribution efficiently. For Grain-128a, given around $2^{106.3}$ bits of keystream, the time complexity is $2^{107.7}$, while for Grain v1, given $2^{67.0}$ bits of keystream, the attack has a time complexity of $2^{69.6}$. These attacks are around $2^{12}$ times better than the best published results at Crypto 2018. For Sosemanuk, we propose a flexible assign-and-solve strategy to mount the first attack faster than exhaustive search of the 128-bit secret key.

The efficiency of Public Key Encryption (PKE) and Key Encapsulation Mechanism (KEM), and in particular their large ciphertext size, is a bottleneck in real-world systems. This worsens in post-quantum secure schemes (e.g., lattice-based ones), whose ciphertexts are an order of magnitude larger than prior ones. The work of Kurosawa (PKC '02) introduced multi-message multi-recipient PKE (mmPKE) to reduce the amortized ciphertext size when sending messages to more than one recipient. This notion naturally extends to multi-message multi-recipient KEM (mmKEM). In this work, we first show concrete attacks on existing lattice-based mmPKE schemes: Using malicious public keys, these attacks fully break semantic security and key privacy, and are inherently undetectable. We then introduce the first lattice-based mmKEM scheme (thereby mmPKE) that maintains full privacy even in the presence of maliciously-generated public keys. Concretely, the ciphertext size of our mmKEM for 100 recipients is >10x smaller than naively using Crystals-Kyber. We additionally show a similar efficiency gain when applied to batched random oblivious transfer and group oblivious message retrieval. Our scheme is proven secure under a new Module-LWE variant assumption, Oracle Module-LWE. We reduce standard MLWE to this new assumption for some parameter regimes, which also gives intuition on why this assumption holds for the parameter we are interested in (along with additional cryptanalysis). Furthermore, we show an asymptotically efficient compiler that removes the assumption made in prior works, that recipients know their position in the list of intended recipients for every ciphertext.

We give a new approach for constructing statistical ZAP arguments (a two-message public-coin statistically witness indistinguishable argument) from quasi-polynomial hardness of the learning with errors (LWE) assumption with a polynomial modulus-to-noise ratio. Previously, all ZAP arguments from lattice-based assumptions relied on correlation-intractable hash functions. In this work, we present the first construction of a ZAP from LWE via the classic hidden-bits paradigm. Our construction matches previous lattice-based schemes by being public-coin and satisfying statistical witness indistinguishability. Moreover, our construction is the first lattice-based ZAP that is fully black-box in the use of cryptography. Previous lattice-based ZAPs based on correlation-intractable hash functions all made non-black-box use of cryptography.

We initiate the holistic study of Policy Compliant Secure Messaging (PCSM). A content policy is a predicate over messages deciding which messages are considered harmful and which not. A PCSM protocol is a type of end-to-end encrypted (E2EE) messaging system that guarantees E2EE privacy and authenticity for all policy compliant messages but detects and verifiably reports harmful content prior to its delivery. This stands in contrast to prior content moderation systems for E2EE messaging where detection relies on receivers reporting the harmful content themselves which makes them unsuited for most PCSM applications (e.g., for preventing the wilful distribution of harmful content). Our holistic PCSM notion explicitly captures several new roles such as policy creator, auditor and judge, to more accurately separate and model the different goals and security concerns of stakeholders when deploying PCSM. We present efficient PCSM constructions for arbitrary policy classes, as well as for hash-based ones, achieving various levels of security, while maintaining the core security properties of the underlying E2EE layer. For hash-based PCSM, we encapsulate Apple's recent PSI protocol used in their content moderation system, and we properly adapt it to realize the desired PCSM functionality, and analyze the resulting protocol's security. To our knowledge, our work is the first that rigorously study Apple’s PSI for server-side content moderation within the broader context of secure messaging, addressing the diverse goals and security considerations of stakeholders when deploying larger systems.

Proxy Re-Encryption (PRE) enables a proxy to transform ciphertexts encrypted under Alice's key into ciphertexts under Bob's key, allowing Bob to decrypt them. As a powerful cryptographic primitive, PRE has been extensively studied over the past two decades. However, an open problem remains unresolved, namely constructing an adaptively secure PRE scheme where the security reduction is tight. In this paper, we present the first PRE scheme that achieves adaptive security in a multi-challenge setting, with a tight security reduction, i.e., constant security loss O(1). In our setting, the adversary can obtain multiple challenge ciphertexts for multiple target users, capturing a more realistic and powerful adversary. In contrast, previous works established adaptive security only under the single-challenge setting, where the adversary is restricted to a single challenge query, and such schemes incur security losses of n^{O(log n)} for trees and chains, and n^{O(n)} for general graphs, where n is the number of users. Our construction is based on composite-order bilinear groups, and we prove the security in the standard model. The results indicate that our security guarantees do not degrade with respect to either the number of users or the number of ciphertexts, thanks to the tight reduction.

Since Kuwakado and Morii's work (ISIT 2010 \& ISITA 2012), it is known that the classically secure 3-round Luby-Rackoff PRP and Even-Mansour cipher become insecure against an adversary equipped with \emph{quantum} query access. However, while this query model (the so-called Q2 model) has led to many more attacks, it seems that restricting the adversary to classical query access prevents such breaks (the so-called Q1 model). Indeed, at EUROCRYPT 2022, Alagic et al. proved the Q1-security of the Even-Mansour cipher. Notably, such a proof needs to take into account the dichotomy between construction queries, which are classical, and primitive queries, which are quantum (since the random oracle / permutation models a public function that the adversary can compute). In this paper, we focus on Feistel ciphers. More precisely, we consider Key-Alternating Feistels built from random functions or permutations. We borrow the tools used by Alagic et al. and adapt them to this setting, showing that in the Q1 setting: $\bullet$~the 3-round Key-Alternating Feistel, even when the round functions are the same random oracle, is a pseudo-random permutation; $\bullet$~similarly the 4-round KAF is a strong pseudo-random permutation.

An important proof technique in the random oracle model involves reprogramming it on hard to predict inputs and arguing that an attacker cannot detect that this occurred. In the quantum setting, a particularly challenging version of this considers adaptive reprogramming wherein the points to be reprogrammed (or the output values they should be programmed to) are dependent on choices made by the adversary. Some quantum frameworks for analyzing adaptive reprogramming were given by Unruh (CRYPTO 2014, EUROCRYPT 2015), Grilo-Hövelmanns-Hülsing-Majenz (ASIACRYPT 2021), and Pan-Zeng (PKC 2024). We show, counterintuitively, that these adaptive results follow from the non-adaptive one-way to hiding theorem of Ambainis-Hamburg-Unruh (CRYPTO 2019). These implications contradict beliefs (whether stated explicitly or implicitly) that some properties of the adaptive frameworks cannot be provided by the Ambainis-Hamburg-Unruh result.

We study secure computation in the plain model against fully concurrent quantum adversaries. While classical simulation-based notions --- such as Super-Polynomial Simulation (SPS) security --- have enabled meaningful forms of concurrent security, very little is known about their quantum counterparts, particularly under standard polynomial-time hardness assumptions. Our main result is the first post-quantum two-party computation protocol that achieves concurrent SPS security, based solely on the minimal assumption of semi-honest post-quantum oblivious transfer (PQ-OT). Moreover, our protocol has constant round complexity when the underlying PQ-OT protocol is constant-round. This can be viewed as a post-quantum analog of the classical result by Garg et al. [Eurocrypt'12], but with a crucial difference: our security proof completely avoids rewinding, making it suitable for quantum settings where rewinding is notoriously challenging due to the no-cloning principle. By leveraging a compiler of Bartusek et al. [Crypto'21], we further extend our result to the fully quantum setting, yielding the first constant-round concurrent SPS two-party computation for {\em quantum} functionalities in the plain model. Additionally, we construct a two-round, public-coin, concurrent SPS post-quantum zero-knowledge protocol for languages in $\NP \cap \coNP$, under the quantum polynomial-time hardness of LWE. This result is notable even in the classical setting.

Public-coin protocols are cryptographic protocols in which all messages sent by a specific party (typically the receiver or verifier) consist solely of random bits. These protocols have been extensively studied in the classical setting due to their advantageous properties in several scenarios, such as the parallel repetition of interactive arguments, and the design of secure multi-party computation with low round complexity, among others. Curiously, post-quantum constructions of public-coin protocols remain limited, particularly when optimization is sought in additional factors like round complexity or hardness assumptions. We introduce the concept of almost-total puzzles, a novel cryptographic primitive characterized by two key properties: (i) hardness against any efficient adversary, and (ii) an ``almost-total'' guarantee of the existence of solutions, even when the puzzle generator is malicious. We demonstrate that this primitive can be derived from one-way functions in public-coin, requiring only two rounds. By leveraging this primitive, we obtain a family of new public-coin results in both the classical and post-quantum settings, based on the minimal assumption of (post-quantum) one-way functions, including: five-round post-quantum extractable commitments and witness-indistinguishable arguments of knowledge, where the (knowledge) extractors achieve the coherently expected quantum-polynomial-time ($\EQPT_c$) simulation proposed by Lombardi, Ma, and Spooner [FOCS'22]; five-round classical extractable commitments that do not suffer from over extraction; five-round classical delayed-input strong witness-indistinguishable arguments of knowledge, and delayed-input witness-hiding arguments of knowledge; the five-round post-quantum analogue of the last item, but with the difference that (1) the input can be delayed until the third round, and (2) post-quantum arguments of knowledge are again defined w.r.t.\ $\EQPT_c$-simulation; $O(\log^* \secpar)$-round post-quantum non-malleable commitments.

Password-Hardened Encryption (PHE) protects against offline brute-force attacks by involving an external ratelimiter that enforces rate-limited decryption without learning passwords or keys. Threshold Password-Hardened Encryption (TPHE), introduced by Brost et al. (CCS’20), distributes this trust among multiple ratelimiters. Despite its promise, the security foundations of TPHE remain unclear. We make three contributions: (1) We uncover a flaw in the proof of Brost et al.’s TPHE scheme, which invalidates its claimed security and leaves the guarantees of existing constructions uncertain; (2) We provide the first universal composability (UC) formalization of PHE and TPHE, unifying previous fragmented models and supporting key rotation, an essential feature for long-term security and related primitives such as updatable encryption; (3) We present the first provably secure TPHE scheme, which is both round-optimal and UC-secure, thus composable in real-world settings; and we implement and evaluate our protocol, demonstrating practical efficiency that outperforms prior work in realistic WAN scenarios.

The state-test technique, originally introduced in the context of impossible-differential cryptanalysis and recently used as an improvement for truncated-differential Meet-in-the-Middle attacks, has proven to be useful for reducing the complexity of attacks. In essence, the idea is to guess parts of the state instead of the key during the key-guessing stage of an attack, ultimately reducing the number of guesses needed. We generalize the idea of the state-test technique, allowing it to be applied not only to impossible-differential and (truncated-)differential Meet-in-the-Middle, but also to differential and differential-linear cryptanalysis, proposing also a new performant technique exploiting the state-test technique and probabilistic key-recovery. Additionally, we provide insights on the interaction between cipher and difference needed for the state-test technique to be applicable, finding it to be a promising option for many ciphers. To illustrate our findings, we provide 3 new applications of the state-test technique: we show how it can be used to improve the best known attack on the block cipher Pride, how it can be used to improve a step in the best known attack on Serpent, and use it to present the first known attacks on 24, 25 and 26 rounds of CRAFT (out of 32), improving by up to three rounds over the previous best ones.

In this paper, we define a special class of systems of linear equations over finite fields that arise in the security analysis of various MAC and PRF modes. We establish lower bounds on the number of solutions for these systems under specific restrictions and use them to derive tight PRF security for several constructions. Specifically, we prove security up to $O(2^{3n/4})$ queries for the single-keyed variant of the Double-block Hash-then-Sum (DBHtS) construction, called 1k-DBHtS, assuming appropriate hash function properties. We show that the single-keyed variants of PMAC+ and LightMAC+, called 1k-PMAC+ and 1k-LightMAC+ satisfy these properties, achieving security up to $O(2^{3n/4})$ queries. Additionally, we show that the sum of $r$ independent Even-Mansour ciphers is secure up to $O(2^{\frac{r}{r+1}n})$ queries.

Threshold public-key encryption (tPKE) enables any subset of $t$ out of $K$ parties to decrypt non-interactively, while any ciphertext remain secure if less that $t$ decryption shares are known. Despite recent progress, existing lattice-based tPKEs face at least one of the following drawbacks: (1) having large decryption share size -- polynomial in $K$ and some even exponential in $t$, (2) proven secure only against relaxed security models where the adversary is not allowed to see decryption shares of challenge ciphertexts, and (3) lack of concrete efficiency, in particular due to the requirement of super-polynomial modulus for noise flooding. We present $\Pilvi$, a new thresholdised variant of Regev’s public-key encryption scheme, which achieves both small decryption shares and a strong form of simulation-based security under the Learning with Errors (LWE) assumption. Our construction has decryption share size $t \cdot \log K \cdot \poly$ and allows the use of a polynomial-size modulus assuming an a priori bound on the number of queries $Q$. It remains secure even when an adaptive adversary requests partial decryptions of both challenge and non-challenge ciphertexts, as long as for each ciphertext the number of corrupt parties plus the number of shares obtained is less than $t$. We provide concrete parameter suggestions for 128-bit security for a wide range of $(t,K,Q)$, including cases where $t \approx K/2$ for up to $K \leq 32$ users and $Q \leq 2^{60}$ partial decryption queries. The ciphertext size ranges from $14$ to $58$ KB and the partial decryption share size ranges from $1$ to $4$ KB. Along the way, we abstract out a general purpose tool called the threshold-LWE assumption, which we prove to follow from LWE. The threshold-LWE assumption captures the core steps in security proofs of schemes involving Shamir's secret-sharing the LWE secret with carefully chosen evaluation points, the algebraic structures from the latter being what enabling the efficiency of our tPKE scheme. As an additional application, we also show how to construct distributed pseudorandom functions (dPRFs) from the threshold-LWE assumption.

The best attacks known against the McEliece cryptosystem have cost growing exponentially with the number of errors corrected by the error-correcting code used in the cryptosystem. One can modify the cryptosystem to asymptotically increase this number of errors, for the same key size and the same ciphertext size, by generalizing classical binary Goppa codes to subfield subcodes of algebraic-geometry codes, and then moving from genus 0 to higher genus. This paper introduces streamlined algorithms for code generation and decoding for a broad class of these codes; shows that this class includes classical binary Goppa codes; and shows that moving to higher genus within this class decodes more errors than classical binary Goppa codes for concrete sizes of cryptographic interest. A notable feature of this paper's algorithms is the use of arithmetic on the Jacobian variety of the underlying curve.

A privately constrained pseudorandom function (pCPRF) is a PRF with the additional property that one can derive a constrained key that allows evaluating the PRF only on inputs satisfying a constraint predicate $C$, without revealing $C$ itself or leaking information about the PRF’s output on inputs that do not satisfy the constraint. Existing privately constrained PRFs face significant limitations: either (1) they rely on assumptions known to imply fully-homomorphic encryption or indistinguishability obfuscation, (2) they support only highly restricted classes of constraints—notably, no known group-based pCPRF even supports the simple class of puncturing constraints (where the constrained key permits evaluation on all but one point while hiding the punctured point), or (3) they are limited to polynomial-size input domains. A long-standing open question has been whether one can construct a privately constrained PRF from group-based assumptions for more expressive classes of constraints. In this work, we present a pCPRF based on the decisional composite residuosity (DCR) assumption that supports a highly expressive class of predicates, namely constraints whose degree and Waring rank are both polynomially bounded, which includes puncturing. From a technical perspective, our work follows the general template of Couteau, Meyer, Passelègue, and Riahinia (Eurocrypt'23), who constructed a pCPRF from group-based homomorphic secret-sharing but were limited to inner-product constraints in the constraint-hiding setting. Leveraging novel techniques for computing with distributed discrete logarithms (DDLog), we enable the non-interactive authentication of powers of linear combinations of shares of some value. This, in turn, allows us to express constraints with polynomially bounded Waring rank. Our construction is single-key, selectively secure, and supports an exponential-size domain.

Designing practically secure masked circuits remains a central problem in the field of cryptographic implementation. While most masking schemes have been proven secure in the classical probing model, this model fails to capture more advanced side-channel attacks such as horizontal attacks. In recent years, the community has shifted toward the more realistic random probing model, which offers stronger guarantees. Yet, balancing strong security with practical efficiency continues to be a significant challenge. In this work, we introduce new tools and constructions that significantly improve the design and analysis of random probing secure circuits. First, we formalize new security notions that combine the benefits of cardinal and general Random Probing Composability (RPC), two recently introduced notions enabling more flexible and efficient composition of secure gadgets. We then show how uniformly random permutations can be applied to transform any cardinal or general RPC gadget into a so-called uniformly cardinal RPC gadget, thereby enhancing security at low cost. Using these techniques, we propose the first non-linear multiplication gadget, inspired by the recursive construction from CHES 2016, that achieves concrete cardinal RPC security. We provide a detailed comparison with state-of-the-art multiplication gadgets in terms of both random probing advantage and implementation complexity. Building upon this gadget, we design a tighter random probing compiler that strategically uses permutations to improve security bounds while preserving efficiency. Finally, we apply our compiler to the AES and demonstrate improved performance and security compared to existing methods.

We introduce a new and efficient pseudorandom correlation function whose security reduces to the sparse LPN assumption in the random oracle model. Our construction is the first to achieve high concrete efficiency while relying on well-established assumptions: previous candidates either required introducing new assumptions, or had poor concrete performances. We complement our result with an in-depth analysis of the sparse LPN assumption, providing new insight on how to evaluate the strength of concrete sets of parameters.

Passwords remain the dominant form of authentication on the Internet. The rise of single sign-on (SSO) services has centralized password storage, increasing the devastating impact of potential attacks and underscoring the need for secure storage mechanisms. A decade ago, Facebook introduced a novel approach to password security, later formalized in Pythia by Everspaugh et al. (USENIX'15), which proposed the concept of password hardening. The primary motivation behind these advances is to achieve provable security against offline brute-force attacks. This work initiated significant follow-on research (CCS'16, USENIX'17), including Password-Hardened Encryption (PHE) (USENIX'18, CCS'20), which was introduced shortly thereafter. Virgil Security commercializes PHE as a software-as-a-service solution and integrates it into its messenger platform to enhance security. In this paper, we revisit PHE and provide both negative and positive contributions. First, we identify a critical weakness in the original design and present a practical cryptographic attack that enables offline brute-force attacks -- the very threat PHE was designed to mitigate. This weakness stems from a flawed security model that fails to account for real-world attack scenarios and the interaction of security properties with key rotation, a mechanism designed to enhance security by periodically updating keys. Our analysis shows how the independent treatment of security properties in the original model leaves PHE vulnerable. We demonstrate the feasibility of the attack by extracting passwords in seconds that were secured by the commercialized but open-source PHE provided by Virgil Security. On the positive side, we propose a novel, highly efficient construction that addresses these shortcomings, resulting in the first practical PHE scheme that achieves security in a realistic setting. We introduce a refined security model that accurately captures the challenges of practical deployments, and prove that our construction meets these requirements. Finally, we provide a comprehensive evaluation of the proposed scheme, demonstrating its robustness and performance.

We describe an algorithm to efficiently evaluate class group actions on supersingular elliptic curves that are oriented by an imaginary quadratic order of arbitrarily large discriminant. Contrary to CSIDH, this allows to increase the post-quantum security of the group action without increasing the size of the base field. In particular, we describe instances where Kuperberg's algorithm loses to generic supersingular isogeny path finding. Our algorithm is fully deterministic, strictly constant time, dummy free, and can be implemented without conditional branches. We show that the (restricted effective) group action can be employed in a non-interactive key exchange protocol, that we argue is asymptotically more efficient than CSIDH.

The k-Tree algorithm [Wagner 02] is a non-trivial algorithm for the average-case k-SUM problem that has found widespread use in cryptanalysis. Its input consists of k lists, each containing n integers from a range of size m. Wagner's original heuristic analysis [Wagner 02] suggested that this algorithm succeeds with constant probability if n = m^{1/(\log{k}+1)}, and that in this case it runs in time O(kn). Subsequent rigorous analysis of the algorithm [Lyubashevsky 05, Shallue 08, Joux-Kippen-Loss 24] has shown that it succeeds with high probability if the input list sizes are significantly larger than this. We present a broader rigorous analysis of the k-Tree algorithm, showing upper and lower bounds on its success probability and complexity for any size of the input lists. Our results confirm Wagner's heuristic conclusions, and also give meaningful bounds for a wide range of list sizes that are not covered by existing analyses. We present analytical bounds that are asymptotically tight, as well as an efficient algorithm that computes (provably correct) bounds for a wide range of concrete parameter settings. We also do the same for the k-Tree algorithm over Z_m. Finally, we present extensive empirical evaluation of the k-Tree algorithm and demonstrate the tightness of our results.

Deployments of cryptographic protocols with thousands of participants are becoming more and more common. In these large-scale, permissionless settings, communication complexity is often a limiting factor. In practice, two tools are commonly used to address this challenge: committee sampling and gossip networks. Committee sampling reduces complexity by restricting most of the communication to a small, randomly sampled committee of participants. Gossip protocols replace a fully connected communication network (which is impractical on an Internet scale) with a sparse communication graph. Existing committee-sampling protocols either require a setup assumption (which is problematic in a fully decentralized setting) or have high communication complexity themselves. In this work, we construct a communication-efficient setup-free protocol for committee sampling. Our starting point is the protocol of Andrychowicz and Dziembowski (CRYPTO'15), who showed how to construct a setup-free random beacon based on proofs-of-work (PoWs) in the random-oracle model (ROM). Our protocol works in a similar setting, and samples a committee in which parties are chosen proportionally to their resource expenditure. We improve upon their construction in two ways: (1) we construct a formal framework for general resource proofs (RPs), and use it to generalize from PoWs to a larger class of resources, and (2) for a subset of RPs (including PoWs), we construct a much more efficient committee-sampling protocol that requires subquadratic communication. Our protocol is designed in the ROM and makes use of VDFs, as well as gossip techniques in the spirit of Cohen, Loss, and Moran (FC'24).

A leakage suppressor is a compiler that transforms a structured encryption (STE) scheme into a new scheme with an improved leakage profile. General-purpose suppressors for the query equality (qeq) pattern---which reveals if and when two queries are the same---were given for both static (Kamara et. al, \emph{Crypto '18}) and dynamic (George et. al, \emph{Eurocrypt '19}) encrypted structures. While the schemes that result from these suppressors are asymptotically efficient, they are not practical due to large constants in their query complexity. In this work, we propose a new query equality suppressor for dictionary encryption schemes that results in practical qeq-hiding encrypted dictionaries at the cost of revealing the distribution of the queries. The resulting constructions are \emph{distribution-aware}, in the sense that they make use of the query distribution, and \emph{distribution-leaking} in the sense that they also reveal it. We show how to instantiate and optimize our suppressor for query distributions that are Zipf-distributed, resulting in a scheme with $O(1)$ online query complexity at the cost of a rebuild with $O(m \log^2 m/\log\log m)$ complexity, where $m$ is the size of the input dictionary.

The YOSO (You Only Speak Once) model, introduced by Gentry et al. (CRYPTO 2021), helps to achieve strong security guarantees in cryptographic protocols for distributed settings, like blockchains, with large number of parties. YOSO protocols typically employ smaller anonymous committees to execute individual rounds of the protocol instead of having all parties execute the entire protocol. After completing their tasks, parties encrypt protocol messages for the next anonymous committee and erase their internal state before publishing ciphertexts, thereby enhancing security in dynamically changing environments. In this work, we consider the problem of secure multi-party computation (MPC), a fundamental problem in cryptography and distributed computing. We assume honest majority among the committee members, and work in the online-offline, i.e., preprocessing, setting. In this context, we present the first YOSO MPC protocol where efficiency---measured as communication complexity---\emph{improves} as the number of parties \emph{increases}. Specifically, for $0<\epsilon<1/2$ and an adversary corrupting $t0$, the sizes of the committees are only marginally increased, while online communication is significantly reduced. Furthermore, we explicitly consider fail-stop adversaries, i.e., honest participants who may inadvertently fail due to reasons such as denial of service or software/hardware errors. In prior YOSO work, these adversaries were grouped with fully malicious parties. Adding explicit support for them allows us to achieve even better scalability. \keywords{Multi-party computation \and Packed Secret-Sharing \and Blockchains.}

Recently, Benhamouda et al. proposed a framework to evaluate the local leakage resilience of the n shares of (k,n)-threshold scheme. Lletting (X_1,X_2, ... ,X_n) be the n shares, the leakage is defined as (Y_1, Y_2, ..., Y_n) , where Y_i is the output of a deterministic mapping belonging to {0,1, ..., L-1} with the input X_i. We evaluate the worst-case total variational distance V between the conditional probability distributions of two leakages given two secrets s and s'. In this paper, we propose a new method to evaluate V more precisely than the existing methods for the (n,n)-threshold scheme over a finite field with p elements, where p>= 3 is an arbitrary prime number. For the case of L=2, we show that V converges to zero of order O(( sin (\pi / 2p ))^{-n}). We also characterize the class of leakage functions that attains V. For the case of L > 2, we succeed in obtaining an upper bound of V by using the theory of majorization. The order of the obtained upper bound is smaller than the existing upper bound and is proved to be tight under a certain assumption.

Aggregate signatures allow compressing multiple single-signer signatures into a single short aggregate signature. This primitive has attracted new attention due to applications in blockchains and cryptocurrencies. In multisig addresses, which is one of such applications, aggregate signatures reduce the sizes of transactions from multisig addresses. Security of aggregate signatures under adaptive corruptions of signing keys is important, since one of the motivations of multisig addresses was a countermeasure against signing key exposures. We propose the first aggregate signature scheme tightly secure under adaptive corruptions using pairings. An aggregate signature includes two source group elements of bilinear groups plus a bit vector whose length is equal to the number of single-signer signatures being aggregated. To construct a scheme, we employ a technique from quasi-adaptive non-interactive zero-knowledge arguments. Our construction can be seen as modularization and tightness improvement of Libert et al.'s threshold signature scheme supporting signature aggregation (Theor. Comput. Sci. 645).

Private set intersection (PSI) allows two parties to jointly compute the intersection of their private sets without revealing any additional information. Structure-aware PSI (sa-PSI), introduced by Garimella et al. (Crypto'22), is a variant where Alice's input set has a publicly known structure and Bob's input set remains unstructured, enabling new applications like fuzzy PSI. Their construction relies solely on lightweight cryptographic primitives such as symmetric-key primitives and oblivious transfer (OT) extension. Since then, there has been active research on sa-PSI based on lightweight cryptography. Notably, recent work by Garimella et al. (Crypto'24) achieves sa-PSI with both communication and computation costs only scaling with the description size of Alice's set, rather than its potentially large cardinality. However, this line of work remains largely theoretical, lacking efficient concrete implementations. In this work, we close this gap by presenting a new framework for sa-PSI that achieves practical efficiency. We identify and eliminate a hidden multiplicative overhead proportional to the security parameter (e.g., 128) in prior symmetric-key-based sa-PSI constructions. A key building block of our new framework is a distributed Function Secret Sharing (dFSS) key generation protocol tailored to the structure of Alice's set, which may be of independent interest. To demonstrate the practicality of our framework, we extend our dFSS protocol to support incremental evaluation, introduce new techniques for spatial hashing, and develop several new optimization techniques, including reducing the exponential dependence on dimension and enabling load balancing between the two parties. We instantiate our framework for structured sets defined by unions of $d$-dimensional $\ell_\infty$ balls, and implement our protocols using only lightweight symmetric-key primitives and OT extension. Our experiments show concrete performance improvements of up to $27\times$ speedup in computation and $7.7\times$ reduction in communication in low-dimensional, large-radius settings compared to existing public-key-based fuzzy PSI protocols by van Baarsen \& Pu (Eurocrypt'24) and Gao et al. (Asiacrypt'24).

Witness encryption allows one to encrypt a message to an $\mathsf{NP}$ relation $\mathcal{R}$ and a statement $x$. The corresponding decryption key is any valid $\mathsf{NP}$ witness $w$. In a succinct witness encryption scheme, we require that the size of the ciphertext be sublinear in the size of the $\mathsf{NP}$ relation. Currently, all realizations of succinct witness encryption for $\mathsf{NP}$ rely on strong assumptions such as pseudorandom obfuscation, extractable witness encryption, or differing-inputs obfuscation. Notably, none of these notions are known from standard assumptions. In this work, we consider a relaxation of succinct witness encryption for $\mathsf{NP}$ to the setting of batch $\mathsf{NP}$. In this setting, one encrypts to an $\mathsf{NP}$ relation $\mathcal{R}$ together with $K$ statements $x_1, \ldots, x_K$. In the basic version, one can decrypt if they have a witness $w_1, \ldots, w_K$ for all $K$ statements. The succinctness requirement is that the size of the ciphertext should be sublinear in the number of instances $K$, but is allowed to grow with the size of the $\mathsf{NP}$ relation (i.e., the size of a single instance). More generally, we can also impose a (monotone) policy $P \colon \{0,1\}^K \to \{0,1\}$ over the $K$ instances. In this case, decryption is possible only if there exists $w_1, \ldots, w_K$ such that $P(\mathcal{R}(x_1, w_1), \ldots, \mathcal{R}(x_K, w_K)) = 1$. In this work, we initiate a systematic study of succinct witness encryption for batch languages. We start with two simple constructions that support CNF and DNF policies based on plain witness encryption in conjunction with a somewhere statistically sound batch argument for $\mathsf{NP}$ or a function-binding hash function. Then, using indistinguishability obfuscation, we show how to support policies that can be computed by read-once bounded-space Turing machines. The latter construction is in fact a unique witness map for monotone-policy batch $\mathsf{NP}$, and as such, also gives a SNARG for monotone-policy batch $\mathsf{NP}$ where the size of the common reference string is sublinear in the number of instances. Finally, we demonstrate some immediate applications of succinct witness encryption for batch languages. We construct new succinct computational secret sharing schemes for CNFs, DNFs, and weighted threshold policies. We also show how to build distributed monotone-policy encryption, a notion that generalizes recent trustless primitives like distributed broadcast encryption and threshold encryption with silent setup.

Is module-lattice reduction better than unstructured lattice reduction? This question was highlighted as 'Q8' in the Kyber NIST standardization submission (Avanzi et al., 2021), as potentially affecting the concrete security of Kyber and other module-lattice-based schemes. Foundational works on module-lattice reduction (Lee, Pellet-Mary, Stehlé, and Wallet, ASIACRYPT 2019; Mukherjee and Stephens-Davidowitz, CRYPTO 2020) confirmed the existence of such module variants of LLL and block-reduction algorithms, but focus only on provable worst-case asymptotic behavior. In this work, we present a concrete average-case analysis of module-lattice reduction. Specifically, we address the question of the expected slope after running module-BKZ, and pinpoint the discriminant $\Delta_K$ of the number field at hand as the main quantity driving this slope. We convert this back into a gain or loss on the blocksize $\beta$: module-BKZ in a number field $K$ of degree $d$ requires an SVP oracle of dimension $ \beta + \log(|\Delta_K| / d^d)\beta /(d\log \beta) + o(\beta / \log \beta)$ to reach the same slope as unstructured BKZ with blocksize $\beta$. This asymptotic summary hides further terms that we predict concretely using experimentally verified heuristics. Incidentally, we provide the first open-source implementation of module-BKZ for some cyclotomic fields. For power-of-two cyclotomic conductors, we have $|\Delta_K| = d^d$, and observe that module-BKZ needs a blocksize larger than its unstructured counterpart. On the contrary, for all other cyclotomic fields, $|\Delta_K| < d^d$, so module-BKZ provides a sublinear $\Theta(\beta/\log \beta)$ gain on the required blocksize, yielding a subexponential speedup of $\exp(\Theta(\beta/\log \beta))$.

Lattice-based signatures like Dilithium (ML-DSA) prove knowl- edge of a secret key $s \in \mathbb{Z}_n$ by using Integer LWE (ILWE) samples $z = \langle \vec c, \vec s \rangle +y $, for some known hash value $c \in \mathbb{Z}_n$ of the message and unknown error $y$. Rejection sampling guarantees zero-knowledge, which makes the ILWE problem, that asks to recover s from many z’s, unsolvable. Side-channel attacks partially recover y, thereby obtaining more informative samples resulting in a—potentially tractable—ILWE problem. The standard method to solve the resulting problem is Ordinary Least Squares (OLS), which requires independence of $y$ from $\langle c, s \rangle$ —an assumption that is violated by zero-knowledge samples. We present efficient algorithms for a variant of the ILWE problem that was not addressed in prior work, which we coin Concealed ILWE (CILWE). In this variant, only a fraction of the ILWE samples is zero-knowledge. We call this fraction the concealment rate. This ILWE variant naturally occurs in side-channel attacks on lattice-based signatures. A case in point are profiling side-channel attacks on Dilithium implementations that classify whether $y = 0$. This gives rise to either zero-error ILWE samples $z = \langle c, s \rangle$ with $y = 0$ (in case of correct classification), or ordinary zero-knowledge ILWE samples (in case of misclassification). As we show, OLS is not practical for CILWE instances, as it requires a prohibitively large amount of samples for even small (under 10\%) concealment rates. A known integer linear programming-based approach can solve some CILWE instances, but suffers from two short-comings. First, it lacks provable efficiency guarantees, as ILP is NP-hard in the worst case. Second, it does not utilize small, independent error y samples, that could occur in addition to zero-knowledge samples. We introduce two statistical regression methods to cryptanalysis, Huber and Cauchy regression. They are both efficient and can handle instances with all three types of samples. At the same time, they are capable of handling high concealment rates, up to 90\% in practical experiments. While Huber regression comes with theoretically appealing correctness guarantees, Cauchy regression performs best in practice. We use this efficacy to execute a novel profiling attack against a masked Dilithium implementation. The resulting ILWE instances suffer from both concealment and small, independent errors. As such, neither OLS nor ILP can recover the secret key. Cauchy regression, however, allows us to recover the secret key in under two minutes for all NIST security levels.

When investigating the round-complexity of multi-party computation protocols (MPC) protocols, it is common to assume that in each round parties can communicate over broadcast channels. However, broadcast is an expensive resource, and as such its use should be minimized. For this reason, Cohen, Garay, and Zikas (Eurocrypt 2020) investigated the tradeoffs between the use of broadcast in two-round protocols assuming setup and the achievable security guarantees. Despite the prolific line of research that followed the results of Cohen, Garay, and Zikas, none of the existing results considered the problem of minimizing the use of broadcast while relying in a 𝘣𝘭𝘢𝘤𝘬-𝘣𝘰𝘹 way on the underlying cryptographic primitives. In this work, we fully characterize the necessary and sufficient requirements in terms of broadcast usage in the 𝘥𝘪𝘴𝘩𝘰𝘯𝘦𝘴𝘵 𝘮𝘢𝘫𝘰𝘳𝘪𝘵𝘺 setting for round-optimal MPC with black-box use of minimal cryptographic assumptions. Our main result shows that to securely realize any functionality with 𝘶𝘯𝘢𝘯𝘪𝘮𝘰𝘶𝘴 𝘢𝘣𝘰𝘳𝘵 in the common reference string model with black-box use of two-round oblivious transfer it is necessary and sufficient for the parties to adhere to the following pattern: in the first two rounds the parties exchange messages over peer-to-peer channels, and in the last round the messages are sent over a broadcast channel. We also extend our results to the correlated randomness setting where we prove that one round of peer-to-peer interaction and one round of broadcast is optimal to evaluate any functionality with unanimous abort.

Proxy re-encryption (PRE) allows a proxy with a re-encryption key rk_{A→B} to transform Alice's ciphertext to Bob's ciphertext without revealing the underlying message. Since its introduction, numerous PRE schemes and variants have been studied, but almost all of them assume that both Alice and Bob use a public-key encryption (PKE) system. However, it is more likely that Alice and Bob use different encryption systems like identity-based encryption (IBE), attribute-based encryption (ABE) and functional encryption (FE). This limitation restricts the broader applicability of PRE. In particular, Döttling and Nishimaki [PKC 2021] leave defining and realizing re-encryptions between different primitives as an open problem. In this paper, we explore the feasibility of re-encryptions across different encryption systems. To this end, we first define a primitive named generalized functional encryption (GFE) that unifies PKE, IBE, ABE and FE, and formalize the syntax and security models for re-encryptions from one GFE to another GFE (GFE_1 → GFE_2). Then, we present two generic constructions of GFE_1 → GFE_2 and show how to instantiate them. -- The core technical tool underlying our generic constructions is a new variant of functional encryption (FE) named {\it Key-Splittable} FE (KSFE), which splits the functional secret key into two pieces and divides the decryption process into two steps. By adapting the FE schemes in [Agrawal et al., CRYPTO 2016], we present three KSFE schemes from the LWE, DDH and DCR assumptions, respectively. -- With KSFE serving as a core building block, we propose a generic construction that achieves re-encryptions PKE → PKE/IBE/ABE/FE, and another generic construction that achieves re-encryptions FE → PKE/IBE/ABE/FE. By combining the concrete KSFE schemes with existing PKE/IBE/ ABE/FE schemes, we can obtain various concrete re-encryption schemes PKE/FE → PKE/IBE/ABE/FE, where FE is for bounded linear functions. This achieves re-encryptions across different encryption systems (PKE/IBE/ABE/FE) {\it for the first time}. -- Our generic construction PKE → PKE/IBE/ABE/FE even achieves {\it fine-grained} re-encryptions, where the re-encryption key rk_{A→B}^h is also associated with a function h. With rk_{A→B}^h, Alice's ciphertext encrypting m can be transformed to Bob's ciphertext encrypting h(m), thus achieving a flexible control of message spread by re-encryptions. This extends the recent work of fine-grained PRE [Zhou et al., ASIACRYPT 2023] from PKE to more encryption systems. Our concrete PKE → PKE/IBE/ABE/FE achieves fine-grained re-encryptions w.r.t. bounded linear functions h, the same as the functions supported by [Zhou et al., ASIACRYPT 2023]. As a complement, we also propose a generic construction of PKE/IBE/ABE/FE → PKE/IBE/ABE from garbled circuits, by extending the techniques in [Döttling and Nishimaki, PKC 2021]. This supports arbitrary PKE, IBE, ABE, FE schemes, but only achieves {\it non-fine-grained} re-encryption.} Overall, our fine-gained re-encryptions GFE_1 → GFE_2 allow Alice and Bob to use different encryption systems, broadening the applicability of re-encryption techniques to real-world scenarios, and resolving the open problem raised by Döttling and Nishimaki [PKC 2021].

To more accurately capture real-world network and adversarial behaviors, recent research has explored Byzantine Agreement (BA) under various mixed fault models. The breakthroughs by Loss et al.~(TCC'23, TCC'24) have established the feasibility of optimally resilient BA in these settings. Specifically, their protocols tolerate up to $t$ byzantine parties, $r$ receive faulty parties, and $s$ send faulty parties in a network of $n > 2t + r + s$ parties. Initially, Loss et al. (TCC'23) considers a model that a party will be either receive faulty or send faulty but not at the same time (called {\em non-overlapping model}). The extended model in Loss et al.~(TCC'24) further accommodates the \textit{overlapping model}, where a party can simultaneously exhibit both receive faulty and send faulty behaviors. However, despite this flexibility, {\em both} protocols incur a prohibitively high $O(n^5)$-bit communication cost, leaving open the fundamental question of whether the optimal $O(n^2)$-bit complexity achieved by many classical BA protocols is attainable in the optimally resilient mixed fault model (with overlapping faults or not). In this work, we answer these open questions affirmatively. We present a mixed-fault BA protocol that achieves the optimal expected $O(n^2\lambda)$ communication complexity while maintaining expected $O(1)$ round complexity and optimal (strongly adaptive) resilience. Our protocol supports the strongest overlapping model, while matching the best-known complexity of classical BA protocols. To achieve this, we develop a series of novel techniques, carefully designed to ensure efficient and secure agreement even under mixed faults. Beyond binary BA, we extend our protocol to a multi-valued BA setting, achieving an expected communication complexity of $O(\frac{n^2}{t}L + n^2\lambda^2)$ and a round complexity of $O(\kappa)$, where $t$ is the number of byzantine faults, $L$ is the bit-length of the input values, $\lambda$ is the computational security parameter, and $\kappa$ is the statistical security parameter. In particular, for $t = O(n)$, the communication reduces to $O(nL + n^2\lambda^2)$. Notably, our protocols operate under the same setup and cryptographic assumptions as those in Loss et al.

We study the problem of provably-secure format-preserving authenticated encryption scheme for images, where decryption is successful even when ciphertexts undergo compression. This novel primitive offers users more control and privacy when sharing and storing images on social media and other photo-centric, compressing platforms like Facebook and Google Photos. Since compression is usually lossy, we cannot expect the decrypted image to be identical to the original. But we want the decrypted image to be visually as close to the original image as possible. There is a vast number of works on image encryption, mostly in the signal processing community, but they do not provide formal security analyses. We formally define security, covering the goals of image confidentiality and integrity. While we first treat the problem generically, we are particularly interested in the construction for the most common compression format, JPEG. We design a scheme for JPEG compression using the standard symmetric cryptographic tools and special pre- and post-processing. We formally assess the security guarantees provided by the construction, discuss how to select the parameters using empirical experiments, and study performance of our scheme in terms of computational efficiency and decryption quality. We also build a browser plug-in that helps users store and share photos privately.

We present a simple IND-CCA lattice-based threshold KEM. At a high level, our design is based on the BCHK transform (Canetti et al., EUROCRYPT 2004), which we adapt to the lattice setting by combining it with the FO transform (Fujisaki and Okamoto, PKC 1999) in order to achieve decryption consistency. As for the BCHK transform, our construction requires a threshold identity-based encryption (TIBE) scheme with suitable properties. We build such an IBE by combining the ABB IBE (Agrawal, Boneh, Boyen, EUROCRYPT 2010) with recent advances in lattice threshold cryptography, such as the threshold-friendly signature Plover (Esgin et al., EUROCRYPT 2024) and a variant of the Threshold Raccoon scheme (Katsumata et al., CRYPTO 2024). The security proof of our scheme relies on a new assumption which we call the Coset-Hint-MLWE assumption, and which is a natural generalisation of the Hint-MLWE assumption (Kim et al., CRYPTO 2023). We prove the hardness of Coset-Hint-MLWE under standard assumptions. We believe this new assumption may be of independent interest. Unlike prior works on IND-CCA lattice-based threshold KEMs, our construction only relies on simple algorithmic tools and does not use heavy machinery such as multi-party computation or threshold fully homomorphic encryption.

In the area of white-box cryptography implementations, many existing protections are susceptible to attacks derived from physical cryptanalysis, which can be applied with minimal human effort and no prior design knowledge. The absence of a clear and comprehensive security model hinders the development of effective countermeasures against these attacks. We introduce the Haystack ciphers, a formal model for the security of white-box countermeasures against such attacks. In this model, the countermeasures are represented simply as symmetric-key encryption schemes. We show that their chosen-plaintext (IND-CPA) security is closely related to the resistance of the countermeasures against computational trace-based attacks. Similarly, their chosen-ciphertext (IND-CCA) security is closely associated with the resistance against fault injection attacks in the white-box model. Secure Haystack ciphers constitute the next formal milestone for advancing white-box designs and countermeasures, the minimal requirement that is not currently clearly achieved but is plausibly feasible with available tools. We review the white-box literature with respect to our model and bridge the gap between white-box and fault attacks, which are very powerful but were only partially considered in the white-box literature so far. We study known fault protections from the physical cryptography literature and present new fault attacks in the white-box setting, which raises the need and shapes the requirements for future secure countermeasures against fault attacks.

Quasi-Abelian Syndrome Decoding (QA-SD) was introduced by Bombar et al (Crypto 2023) in order to obtain pseudorandom correla- tion generators for Beaver triples over small fields. This theoretical work was turned into a concrete and efficient protocol called F4OLEage by Bombar et al. (Asiacrypt 2024) that allows several parties to generate Beaver triples over GF(2). We propose efficient algorithms to solve the decoding problem under- lying the QA-SD assumption. We observe that it reduces to a sparse multivariate polynomial interpolation problem over a small finite field where the adversary only has access to random evaluation points, a blind spot in the otherwise rich landscape of sparse multivariate interpolation. We develop new algorithms for this problem: using simple techniques, we interpolate polynomials with up to two monomials. By sending the problem to the field of complex numbers and using convex optimization techniques inspired by the field of “compressed sensing”, we can inter- polate polynomials with more terms. This enables us to break in practice parameters proposed by Bombar et al. at Crypto’23 and Asiacrypt’24, as well as Li et al. at Eurocrypt’25 (IACR flagship conferences Grand Slam). In the case of the F4OLEage protocol, our implementation recovers all the secrets in a few hours with probability 60%. This not only invalidates the security proofs, but it also yields real-life privacy attacks against multiparty protocols using the Beaver triples generated by the broken pseudorandom correlation generators.

Masking is a commonly used countermeasure against side-channel attacks, encoding secrets into multiple shares such that each share leaks only partial information. A longstanding question is under what noise conditions masking guarantees security, and how this security scales with the number of shares. While sufficient conditions have been known for binary fields and in high-noise regimes, the borderline and low-noise cases have remained poorly understood. In this work, we close this gap through a decomposition-based analysis. Our approach reduces leakage in extended fields to binary projections, enabling tight bounds on the adversary’s success rate and yielding an optimal reduction from the noisy leakage model to the random probing model—even in regimes where classical reductions fail. As a central theoretical result, we prove a conjecture of Dziembowski et al.\ (TCC 2016), showing that for any additive group $\mathbb{G}$ with largest proper subgroup $\mathbb{H}$, masking strictly improves security whenever the leakage is $\delta$-noisy with $\delta < 1 - \tfrac{|\mathbb{H}|}{|\mathbb{G}|}$. We additionally demonstrate the practical relevance of our framework for leakage certification and for determining the required masking order under realistic low-noise conditions. Our results unify and sharpen the understanding of noise requirements for masking, advancing both the theoretical foundations and the practical evaluation of side-channel countermeasures.

Succinct non-interactive arguments of knowledge (SNARKs) based on lattice assumptions offer a promising post-quantum alternative to pairing-based systems, but have until now suffered from inherently quadratic proof sizes in the security parameter. We introduce RoK and Roll, the first lattice-based SNARK that breaks the quadratic barrier, achieving communication complexity of $\tilde{O}(\lambda)$ together with a succinct verification time. The protocol significantly improves upon the state of the art of fully-succinct argument systems established by ``RoK, Paper, SISsors'' (RPS) [ASIACRYPT'24] and hinges on two key innovations, presented as reductions of knowledge (RoKs): - \emph{Structured random projections:} We introduce a new technique for structured random projections that allows us to reduce the witness dimensions while approximately preserving its $\ell_2$ norm and maintaining the desired tensor structure. Such a projection does not reduce the dimensions sufficiently so the image can be sent in plain, but instead, the projection is further committed and adjoined to the original relation. - \emph{Unstructured random projection:} Similarly to projections used in LaBRADOR [CRYPTO'23], when the witness is sufficiently small, we let the projection (over coefficients $\ZZ_q$) be sent in plain. However, immediately lifting the projection claim to $\mathcal{R}_q$ and into our relation (as in LaBRADOR) would impose a quadratic communication cost. Instead, we gradually batch-and-lift the projection over the tower of intermediate extensions.This allows us to reduce the communication cost to $\tilde{O}(\lambda)$, while maintaining a succinct verification time. These two techniques, combined with existing RoKs from RPS, yield a succinct argument system with communication complexity $\tilde{O}(\lambda)$ and succinct verification for structured linear relations.

The increasing use of multi-party computation (MPC) has spurred the design of symmetric key primitives specifically suited for MPC environments. Recently, weak pseudorandom functions (wPRFs) based on the alternating moduli paradigm have been proposed as a promising class of MPC-friendly primitives. The wPRF proposed at CRYPTO 2024, in its One-to-One parameter set, has been shown to be vulnerable to a key recovery attack dubbed Zeroed-Out, exploiting collisions in the queries. In this paper, we show a different, general key recovery attack on wPRFs with similar structure. This method, applied to wPRFs in the One-to-One parameter set attacked by ZeroedOut, improves upon the complexity and achieves an attack with complexity below the birthday bound, and stays effective against the proposed countermeasures. For the first time, it succeeds in attacking one of the two Many-to-One parameter sets and stays effective against one of the proposed countermeasures. We also consider its applicability to the alternative wPRF of similar structure proposed by Boneh et al. at TCC 2018.

Functional encryption (FE) which covers the notion of attribute-based encryption (ABE), is the cryptographic tool to realize fine-grained control on the accessibility of encrypted data. The traditional FE requires a central trusted authority to issue secret keys. It depends on the full-trust model, and is vulnerable to the security issue caused by key-escrow. While the registered FE (Reg-FE) achieves the zero-trust model and addresses the security issue by removing the use of central authority. It allows users to generate secret keys themselves and join the system by registering corresponding public keys to a curator. This work introduces delegated Reg-FE, which is a primitive with a new registration paradigm. It allows the registration of certain authorities that can issue secret keys for their respective classical FE sub-systems, beyond the prior work of registering plain users. Delegated Reg-FE implements a hybrid trust model within a two-level hierarchy. By redefining key escrow as a functional mechanism rather than a security concern, this model employs a zero-trust upper level which removes key-escrow, while the subsystem of each authority is locally full-trust and retains key-escrow mechanism. We construct four delegated Reg-FE schemes for functionalities that can be described as the 2\times 2 combinations of linear function and policy check. Namely, Delegated Reg-IPFE, Delegated Reg-ABE, Reg-IPFE with delegated ABE, and Reg-ABE with delegated IPFE. All concrete schemes support bounded registrations and delegations, and achieve standard adaptive security under MDDH assumption on prime-order bilinear group. Furthermore, these schemes only rely on black-box techniques. Technically, these schemes relies on dual-system techniques as prior registration-based works. And we devise a new "hierarchically invoked dual-system" technique on schemes which have sub-ABE delegation systems. Furthermore, we present a generic construction of Delegated Reg-FE from the combination of Reg-FE and FE. The instantiations of this generic construction demonstrate the feasibility of delegated Reg-FE, supporting arbitrary functions as well as unbounded numbers of registrations and delegations. However, this approach requires non-black-box techniques and achieves weaker semi-adaptive security without malicious registration, where the semi-adaptive means the adversary claims the challenge after seeing common reference string but before making any query. Its security relies solely on the underlying assumptions of the Reg-FE and FE components.

The notion of Best-of-Both-Worlds introduced in the work of Ishai et al. (CRYPTO 2006) investigated whether an MPC protocol can simultaneously provide two incomparable security guarantees: guaranteed output delivery against an honest majority and security with abort against a dishonest majority and provided tight upper and lower bounds in the presence of computationally bounded, i.e., PPT adversaries. Another line of works starting from the work of Chaum (CRYPTO 1989) considered protocols that simultaneously achieved security against an unbounded adversary corrupting a minority of the parties and security against arbitrary corruption by a PPT adversary. In this work, we generalize previous work to investigate a fundamental challenge of designing an MPC in a \emph{multiverse} where security is specified with respect to (1) GOD, (2) fairness, (3) security w.r.t. unbounded adversaries, and (4) security with abort. The work of Lucas et al. (PODC 2010) resolved this question when considering threshold adversaries; however, the case of general adversary structures remains open. Our main result completely characterizes when a protocol can simultaneously achieve all properties. Namely, given adversary structures $Z_{GOD}, Z_{fair}, Z_{Stat}$ and $Z_{Comp}$, we provide tight upper and lower bounds for when an MPC protocol can provide GOD, fairness, and security with abort respectively for unbounded and PPT adversaries w.r.t. these adversary structures.

Subversion-resilient cryptography has garnered increasing attention in recent years due to growing concerns about cryptographic subversions in real-world applications. Among the existing countermea sures, the notion of cryptographic reverse firewalls (RFs), initially pro posed by Mironov and Stephens-Davidowitz (EUROCRYPT 2015) and later extended by Chakraborty et al. (EUROCRYPT 2022) to the univer sally composable (UC) model, has proven to be a powerful tool for build ing subversion-resilient cryptographic protocols. In this work, we focus on designing subversion-resilient authenticated key exchange (AKE) pro tocols, which are critical components of secure Internet communication. Wepresent the first generic framework for subversion-resilient UC-secure AKE protocols leveraging RFs. Inspired by the state-of-the-art advance ments by Chakraborty et al. (ASIACRYPT 2024), we address subver sions: where a party’s implementation is covertly altered to exfiltrate secrets or behave unpredictably when triggered by adversarial inputs. A key contribution of our work is the introduction of a new AKE function ality which, for the first time, incorporates security against key control, an essential aspect of achieving subversion resilience. We also provide a concrete instantiation of our framework, demonstrating its feasibility in practice. Notably, the RFs in our proposed AKE protocol are transparent, an important property of RF as defined originally, which allows deploy ment of RF without all parties explicitly knowing about it and allows robust security. Achieving transparency for RFs has been widely regarded as challenging, particularly when addressing broader subversion attacks (e.g., input-trigger attacks) in the UC model. Our approach, thus, not only advances the state of AKE protocol design, but also offers insights into building other subversion-resilient protocols in the UC model using transparent RFs.

Message franking is an indispensable abuse mitigation tool for end-to-end encrypted (E2EE) messaging platforms. With it, users who receive harmful content can securely report that content to platform moderators. However, while real-world deployments of reporting require the disclosure of multiple messages, existing treatments of message franking only consider the report of a single message. As a result, there is a gap between the security goals achieved by constructions and those needed in practice. Our work introduces transcript franking, a new type of protocol that allows reporting subsets of conversations such that moderators can cryptographically verify message causality and contents. We define syntax, semantics, and security for transcript franking in two-party and group messaging. We then present efficient constructions for transcript franking and prove their security. Looking toward deployment considerations, we provide detailed discussion of how real-world messaging systems can incorporate our protocols.

The GINX method in TFHE enables low-latency ciphertext bootstrapping with relatively small bootstrapping keys but is limited to binary or ternary key distributions. In contrast, the AP method supports arbitrary key distributions, albeit at the cost of significantly large bootstrapping keys. Building on AP, automorphism-based methods, introduced in LMK⁺ (EUROCRYPT 2023), achieve smaller key sizes. However, each automorphism application necessitates a key switch, introducing additional computational overhead and noise accumulation. This paper advances automorphism-based methods in two important ways. First, it proposes a novel traversal blind rotation algorithm that optimizes the number of key switches for a given key material. Second, it introduces a new external product that is automorphism-parametrized and seamlessly applies an automorphism to one of the input ciphertexts. Together, these techniques substantially reduce the number of key switches, resulting in faster bootstrapping and improved noise control. As an independent contribution, we introduce a comprehensive theoretical framework for analyzing the expected number of automorphism key switches. The predictions of this framework perfectly align with the results of extensive numerical experiments, demonstrating its practical relevance. In typical settings, by leveraging additional key material, the LLW⁺ approach (TCHES 2024) reduces the number of key switches by 17% compared to LMK⁺. Our combined techniques achieve a 46% reduction using similar key material and can eliminate an arbitrary large number (e.g., more than 99%) of key switches with only a moderate (9x) increase in key material size. As a result, the total bootstrapping runtime decreases by more than 34%.

The study of lattice-based group signatures has been a prominent research direction since 2010. While recent advances in the field have yielded schemes in the random oracle model with strong security properties and nearly practical efficiency, the current state of affairs for lattice-based group signatures in the standard model is still much less satisfactory. Existing schemes, proposed by Katsumata and Yamada (EUROCRYPT’19) or implied by generic non-interactive zero-knowledge proofs for NP (by Peikert and Shiehian at CRYPTO’19 and by Waters at STOC’24), either only fulfil a weak notion of anonymity called selfless anonymity, or require a strong lattice assumption, or suffer from extremely large signatures and/or public keys. This work aims to enhance the state of affairs for lattice-based group signatures in the standard model. We provide improved constructions that simultaneously achieves: (i) signature and public key sizes significantly smaller than those of known schemes; (ii) full anonymity in the CPA and CCA senses; (iii) security based on standard SIS and LWE assumptions with polynomial approximation factors regarding worst-case lattice problems (in general lattices). Our design approach slightly departs from that of existing pairing-based and lattice-based constructions. In the design process, we adapt and develop several lattice-based cryptographic ingredients that may be of independent interest. At the heart of our constructions is a reasonably efficient non-interactive zero-knowledge proof system for relations typically appearing in advanced privacy-preserving lattice-based cryptographic protocols. These relations are addressed by a trapdoor Σ-protocol with an inverse polynomial soundness error, which is made non-interactive via the standard-model Fiat-Shamir transform of Canetti et al. (STOC’19) and a compiler by Libert et al. (ASIACRYPT’20).

Orion (Xie et al. CRYPTO’22) is a recent plausibly post-quantum zero-knowledge argument system with a linear time prover. It improves over Brakedown (Golovnev et al. ePrint’21 and CRYPTO’23) by reducing the proof size and verifier complexity to be polylogarithmic and additionally adds the zero-knowledge property. The argument system is demonstrated to be concretely efficient with a prover time being the fastest among all existing succinct proof systems and a proof size that is an order of magnitude smaller than Brakedown. Since its publication in CRYPTO 2022, two revisions have been made to the zk-SNARK. First, there was an issue with how zero-knowledge was handled. Second, Orion was discovered to be unsound, which was then repaired through the use of a commit-and-prove SNARK as an “outer” SNARK. As we will show in this paper, unfortunately, Orion in its current revision is still unsound (with and without the zero-knowledge property) and we will demonstrate practical attacks on it. We then show how to repair Orion without additional assumptions, with the resulting polynomial commitment denoted as Scorpius, which requires non-trivial fixes when aiming to preserve the linear time prover complexity. The proposed fixes lead to an even improved efficiency, i.e., smaller proof size and verifier time, over the claimed efficiency of the initial version of Orion. We also apply the recent ideas of Diamond and Posen (CiC’24) to make the challenge in Orion logarithmically sized. Moreover, we provide the first rigorous security proofs and explicitly consider multi-point openings and non-interactivity. While revisiting Orion we make some additional contributions which might be of independent interest, most notable an improved code randomization technique that retains the minimum relative distance.

Following Mumford's theory, theta structures on products of elliptic curves are induced by symmetries whose eigenvectors correspond to 4-torsion points on the Kummer line. These symmetries introduce a rich pattern of self-similarities within the theta structure that we exploit to enhance the computation of gluing isogenies. Focusing on the dimension-2 case, we show how theta structures can be computed projectively, thereby avoiding costly modular inversions. Moreover, by leveraging the sparsity of certain specific 4-torsion points and the action of the canonical 2-torsion points in the Kummer line, we derive new formulae for the evaluation of (2,2)-gluing isogenies. These formulae require significantly fewer precomputations and arithmetic operations than previous methods. Additionally, our formulae also support the evaluation of points on the quadratic twist at negligible additional cost, without requiring operations in an extended field.

We study the practicality of a primal hybrid lattice attack on LWE. Despite significant research efforts, the state-of-the-art in practical LWE record computations so far is the plain primal attack with Kannan's embedding. Building on an idea by Espitau and Fouque, Bernstein proposed in 2023 an LWE hybrid attack that asymptotically outperforms the primal attack. In a nutshell, Bernstein's attack enumerates some coordinates of an LWE key and uses the sophisticated Batch-CVP (Randomized) Slicer algorithm to solve LWE in a dimension-reduced lattice. The practical implications of this attack however remain widely unclear. One of the major obstacles for judging practicality is the lack of a fast, fully functional Slicer implementation. For the first time, we provide an efficient Slicer implementation that includes all required algorithmic ingredients like locality sensitive hashing. Building on our Slicer implementation, we implement a generalization of Bernstein's algorithm. While Bernstein's attack works only for LWE, ours also applies to a more general BDD setting. Let (B,t) be a BDD instance, where the target t is off from the d-dimensional lattice L(B) by some error e, sampled coordinate-wise from a distribution D. We show that for hard BDD instances, our BDD hybrid asymptotically speeds up primal's complexity of T=2^{0.292d + o(d)} down to T^{1-K}, where K \approx (1+H(D)/0.058)^{-1} with H(D) the Shannon entropy. Depending on D, the constant K can be small, making practical improvements difficult. We test our Slicer-based implementation inside an implementation of our BDD hybrid lattice attack to tackle LWE instances. We choose two ternary LWE secrets with different entropies H(D) as used in NTRU, and the centered binomial distribution as used in Kyber. For all three distributions in all tested LWE dimensions n \in [160, 210], our Slicer-based implementation practically demonstrates measurable speedups over the primal attack, up to a factor of 5. We also show that for parameters as originally suggested by Regev, the hybrid attack cannot improve over primal.

Differential-linear cryptanalysis was introduced by Langford and Hellman at CRYPTO'94 and has been an important cryptanalysis method against symmetric-key primitives. The current primary framework for constructing differential-linear distinguishers involves dividing the cipher into three parts: the differential part $E_0$, the middle connection part $E_m$, and the linear part $E_1$. This framework was first proposed at EUROCRYPT 2019, where DLCT was introduced to evaluate the differential-linear bias of $E_m$ over a single round. Recently, the TDT method and the generalized DLCT method were proposed at CRYPTO 2024, respectively, to evaluate the differential-linear bias of $E_m$ covering multiple rounds. Unlike the DLCT framework, the DATF technique could also handle $E_m$ with more rounds. In this paper, we enhance the DATF technique in differential-linear cryptanalysis from three aspects. First, we improve the precision of the differential-linear bias estimation by introducing new transitional rules, the backtracking strategy, and the partitioning technique to DATF. Second, we present a general bias computation method for Boolean functions that substantially reduces computational complexity compared with the exhaustive search used by Liu et al. in the previous DATF technique. Third, we propose an effective method for searching for differential-linear distinguishers with good biases based on DATF. Besides, the bias computation method has independent interests with a wide application in other cryptanalysis methods such as differential cryptanalysis and cube attacks. Notably, all these enhancements to DATF are equally applicable to HATF. To show the validity and versatility of our new techniques, we apply the enhanced DATF to the NIST standard Ascon, the AES finalist Serpent, the NIST LWC finalist Xoodyak, and the eSTREAM finalist Grain v1. In all applications, we either present the first differential-linear distinguishers for more rounds or update the best-known ones.

SNOVA is a multivariate-based signature scheme constructed as a variant of unbalanced oil and vinegar over a non-commutative ring. This scheme has been selected as one of the second-round candidates for the NIST PQC competition for additional signatures and is attracting much attention due to its efficiency and compactness. Various security analyses have been conducted on SNOVA, and some have improved the efficiency of attacks by exploiting the structure of extension fields. In particular, Cabarcas et al. showed that the forgery and reconciliation attacks can be made more efficient by utilizing the multi-homogeneous structure derived from transformed public keys over an extension field.However, it has not been clarified whether other key recovery attacks can be improved by using the multi-homogeneous structure over the extension field. In this work, we first clearly describe the transformation of public key systems to an extension field, which has been used in some previous analysis, as a concrete form of matrix transformation. We can construct multi-homogeneous systems from the matrices obtained through this transformation. We then provide a way of improving the intersection and rectangular MinRank attacks, which are key recovery attacks on UOV, solving the resulting multi-homogeneous systems. Further, to estimate the complexity of the proposed rectangular MinRank attack, we analyze the solving degree of the multi-homogeneous version of the MinRank problem. As a result, we show that the proposed attacks are more efficient than known attacks for some parameters of SNOVA.

At Eurocrypt 2025, a new key recovery method for attacks against ChaCha was proposed. It uses bit puncturing to approximate the key recovery map with a simpler pseudoboolean function which is highly correlated. This approximation is obtained by examining the Walsh spectrum of the key recovery map: in trail enumeration puncturing, this is done by considering a limited set of linear trails. There are limitations to this approach. First, running trail enumeration in practice sometimes requires simplifications which lead to inefficient attacks, as with the 7.5-round ChaCha attack of the previous work. Second, the attacks are often limited by their offline complexity, as is the case when applying the technique to Salsa. Finally, trail enumeration puncturing relies on assumptions which are often impossible to verify in practice by checking the correlation due to the huge offline complexity. To solve these problems, we propose a divide-and-conquer approach which leverages some properties of the Walsh spectrum and can construct the pseudoboolean function with practical time and memory. We improve the complexity of attacks on 7 and 8.5-round Salsa and 7.5-round ChaCha and propose the first attack on 8-round Salsa with 128-bit key, which is the first improvement to the number of rounds since Aumasson et al.'s 2008 work.

Verifiable Homomorphic Encryption (VHE) is a cryptographic technique that integrates Homomorphic Encryption (HE) with Verifiable Computation (VC). It serves as a crucial technology for ensuring both privacy and integrity in outsourced computation, where a client sends input ciphertexts ct and a function f to a server and verifies the correctness of the evaluation upon receiving the evaluation result f(ct) from the server. At CCS, Chatel et al. introduced two lightweight VHE schemes: Replication Encoding (REP) and Polynomial Encoding (PE). A similar approach to REP was used by Albrecht et al. in Eurocrypt to develop a Verifiable Oblivious PRF scheme (vADDG). A key approach in these schemes is to embed specific secret information within HE ciphertexts to verify homomorphic evaluations. This paper presents efficient attacks that exploit the homomorphic properties of encryption schemes. The one strategy is to retrieve the secret information in encrypted state from the input ciphertexts and then leverage it to modify the resulting ciphertext without being detected by the verification algorithm. The other is to exploit the secret embedding structure to modify the evaluation function f into f' which works well on input values for verification purposes. Our forgery attack on vADDG demonstrates that the proposed 80-bit security parameters in fact offer less than 10-bits of concrete security. Our attack on REP and PE achieves a probability 1 attack with linear time complexity when using fully homomorphic encryption.

The Legendre signature of an integer $x$ modulo a prime~$p$ with respect to offsets $\vec a = (a_1, \dots, a_\ell)$ is the string of Legendre symbols $(\frac{x+a_1}{p}), \dots, (\frac{x+a_\ell}{p})$. Under the quadratic-residuosity assumption, we show that the function that maps the pair $(x,p)$ to the Legendre signature of $x$ modulo $p$, with respect to public random offsets $\vec a$, is a pseudorandom generator. Our result applies to cryptographic settings in which the prime modulus $p$ is secret; the result does not extend to the case—common in applications—in which the modulus $p$ is public. At the same time, this paper is the first to relate the pseudorandomness of Legendre symbols to any pre-existing cryptographic assumption.

Secret sharing is a cornerstone of modern cryptography, underpinning the secure distribution and reconstruction of secrets among authorized participants. In these schemes, succinctness—measured by the size of the distributed shares—has long been an area of both great theoretical and practical interest, with large gaps between constructions and best known lower bounds. In this paper, we present a novel computational secret sharing scheme for monotone Boolean circuits that achieves substantially shorter share sizes than previously known constructions in the standard model. Our scheme attains a public share size of n + poly(λ, log |C|) and a user share size of λ, where n denotes the number of users, C is the monotone circuit and λ is the security parameter, thus effectively eliminating the dependence on the circuit size. This marks a significant improvement over earlier approaches, which exhibited share sizes that grew with the number of gates in the circuit. Our construction makes use of indistinguishability obfuscation and injective one-way functions.

Non-interactive blind signatures (NIBS), introduced by Hanzlik (Eurocrypt'23), enable the issuance of blind signatures on random messages without requiring interaction and have found applications in a variety of privacy-preserving protocols. Despite recent progress, all known constructions of NIBS rely on the random oracle model and/or the common reference string model, or on complexity-leveraging techniques. As a result, constructing such schemes in the plain model under standard assumptions remains an open problem. In this work, we present new results showing that it is hard to construct NIBS in the plain model from standard assumptions, as long as the adversary is used in a black-box manner. Specifically, we first focus on black-box reductions for basing the security of statistically blind NIBS on any non-interactive assumption. We then extend this limitation to the computationally blind setting under conditions inspired by the known impossibility results for standard blind signatures, introduced by Fischlin and Schröder (Eurocrypt'10). As an independent contribution, we study the relationship between two strong notions of blindness—strong recipient blindness and strong nonce blindness—recently introduced by Baldimtsi et al. (Asiacrypt'24). We show the separation result by constructing schemes that satisfy strong recipient blindness but not strong nonce blindness, and vice versa. Our results suggest that both notions are independently necessary for the provable security of NIBS schemes.

A common issue with using secure computation in practice is that its security does not place any restrictions on what an adversary can use as input in the protocol. In this work, we focus on the practically-motivated setting of (two-message, labeled) \emph{private set intersection} (PSI), and advocate for a clean and versatile solution to this problem: PSI on authenticated inputs. Our central contributions are summarized as follows. - We formulate a novel definition of PSI on authenticated inputs that has the potential for use in several applications, from content moderation in end-to-end encrypted systems to watchlists in anonymous e-cash systems. - We design a concretely-efficient and laconic (i.e. the size of the receiver's message is independent of its set size) protocol for PSI on authenticated inputs. - We build on our PSI protocol to obtain the first laconic set pre-constrained group signature scheme, improving on that of Bartusek et al. (Eurocrypt 23). We also explore various optimizations to our basic protocol, including reducing the receiver's concrete run time, and a tradeoff between crs size and message size.

Message authentication (MA) in the Short Authenticated String (SAS) model, defined by Vaudenay [28], allows for authenticating arbitrary messages sent over an insecure channel as long as the sender can also transmit to the receiver a short authenticated message, e.g. d = 20 bits. The flagship application of SAS-MA is Authenticated Key Exchange (AKE) in the SAS model (SAS-AKE), which allows parties communi- cating over insecure network to establsh a secure channel without prior source of trust except an ability to exchange d-bit authenticated strings. SAS-AKE is applicable e.g. for device pairing, i.e. creating secure chan- nels between devices capable of displaying d-bit values, e.g. encoded as decimal strings, verified by a human operator, or to secure messaging applications like Signal or WhatsApp, where such short values can be read off by participants who trust each others’ voices. A string of works [28,26,20] showed light-weight SAS-MA schemes, using only symmetric-key crypto and 3 communication flows, which is opti- mal [28]. In [21] this was extended to group SAS-(M)MA, for (mutual) message authentication among any number of parties, using two simulta- neous flows. We show a new two simultaneous flows SAS-(M)MA proto- col, based on Verifiable Random Functions (VRF), with a novel property that the first flow, which consists of exchanging VRF public keys, can be re-used in multiple SAS-MA instances. Moreover, instantiated with ECVRF, these keys have the same form vk = gsk as Diffie-Hellman keys exchanged in DH-based (A)KE protocols like X3DH. We show that X3DH keys can be re-used in our SAS-MA, implying SAS-AKE which adds a minimal overhead of a single flow to X3DH. Crucially, while X3DH is secure only if participants’ public keys are certified by a shared source of trust, e.g. a Public Key Infrastructure (PKI) or a trusted Key Distribution Center (KDC) ran by Signal or WhatsApp, if X3DH is amended by our SAS-AKE then the established channel is secure even if PKI or KDC is compromised, assuming trust in user-assisted authentication of short d-bit strings.

We construct an efficient pseudorandom correlation generator (PCG) (Boyle et al., Crypto'19) for two-party {\it programmable oblivious linear evaluation (OLE)} functionality over $\mathbb{F}_2$. Our construction (i) has an efficient seed expansion phase, and (ii) comes with a concretely efficient protocol for distributing the seeds that makes black-box use of cryptography and runs in a constant number of rounds. PCGs for programmable OLE are known to imply PCGs for generating $n$-party Beaver triples over $\mathbb{F}_2$. The resultant PCG has a seed setup phase whose communication cost is $n(n-1)$ times than that of the programmable OLE protocol. The per-party seed size and the seed expansion time have a multiplicative overhead of $2(n-1)$. Prior constructions for efficiently generating multiparty Beaver triples only worked for finite fields $\mathbb{F}_q$ where $q \geq 3$ or required one bit of per-party communication for each triple generated (and hence, do not satisfy the PCG definition). Thus, ours is the first concretely efficient PCG for generating Beaver triples over $\mathbb{F}_2$ in the multiparty setting. Our distributed seed generation protocol generates $N = 2^{30}$ two-party programmable OLEs in 3.5 minutes with 255 MB of communication over a LAN network. The PCG seed size is around 55 MB and the expansion phase requires 10 PRG calls and around 229 thousand XOR and AND operations per triple, producing roughly 31,000 triples per second. Our PCG for generating multiparty Beaver triples has lower concrete communication cost than the state-of-the-art for small number of parties. When compared to the FOLEAGE protocol (Bombar et al, Asiacrypt 2024) which requires one bit of per-party communication per triple that is generated, our communication cost is lower by $2.4\times$ when generating $N = 2^{36}$ triples between three parties and is $1.2 \times $ lower for the case of five parties. At a conceptual level, our protocol deviates from the prior approaches which relied on variants of dual learning parity with noise (LPN) assumption. Instead, our construction combines both the primal and dual versions of LPN to achieve the aforementioned efficiency.

We revisit decentralized multi‑authority attribute‑based encryption (MA‑ABE) through the lens of fully adaptive security -- the most realistic setting in which an adversary can decide on‑the‑fly which users and which attribute authorities to corrupt. Previous constructions either tolerated only static authority corruption or relied on highly complex “dual system with dual‑subsystems” proof technique that inflated ciphertexts and keys. Our first contribution is a streamlined security analysis showing -- perhaps surprisingly -- that the classic Lewko–Waters MA-ABE scheme [EUROCRYPT 2011] already achieves full adaptive security, provided its design is carefully reinterpreted and, more crucially, its security proof is re-orchestrated to conclude with an information-theoretic hybrid in place of the original target-group-based computational step. By dispensing with dual subsystems and target-group-based assumptions, we achieve a significantly simpler and tighter security proof along with a more lightweight implementation. Our construction reduces ciphertext size by 33 percent, shrinks user secret keys by 66 percent, and requires 50 percent fewer pairing operations during decryption -- all while continuing to support arbitrary collusions of users and authorities. These improvements mark a notable advance over the state-of-the-art fully adaptive decentralized MA-ABE scheme of Datta et al. [EUROCRYPT 2023]. We instantiate the scheme in both composite‑order bilinear groups under standard subgroup‑decision assumptions and in asymmetric prime‑order bilinear groups under the Matrix‑Diffie–Hellman assumption. We further show how the Kowalczyk–Wee attribute‑reuse technique [EUROCRYPT 2019] seamlessly lifts our construction from ``one‑use’’ boolean span programs (BSP) to ``multi‑use’’ policies computable in $\mathsf{NC^{1}}$, resulting in a similarly optimized construction over the state-of-the-art by Chen et al. [ASIACRYPT 2023]. Going beyond the Boolean world, we present the first MA-ABE construction for arithmetic span program (ASP) access policies, capturing a richer class of Boolean, arithmetic, and combinatorial computations. This advancement also enables improved concrete efficiency by allowing attributes to be handled directly as field elements, thereby eliminating the overhead of converting arithmetic computations into Boolean representations. The construction -- again presented in composite and prime orders -- retains decentralization and adaptive user‑key security, and highlights inherent barriers to handling corrupted authorities in the arithmetic setting.

The LowMC-based post-quantum signature scheme Picnic was selected as a third-round candidate for NIST PQC, attracting wide attention to the design of efficient and secure post-quantum signature schemes using Symmetric Techniques for Advanced Protocols (STAP). Symmetric primitives designed for advanced protocols such as secure multi-party computation (MPC), fully homomorphic encryption (FHE), and zero-knowledge (ZK) proof systems, with the goal of reducing the number of multiplication operations, are referred to as arithmetic-oriented (AO) primitives. These cryptographic primitives are typically constructed over large finite fields, which makes classical statistical analysis methods like differential and linear cryptanalysis inefficient. Due to their inherent algebraic properties, the mainstream security evaluation approaches are based on algebraic attacks. In this paper, we analyze the security of the MPC-friendly primitives \textsc{Rain} (CCS 2022) and AIM (CCS 2023) used in the post-quantum signature schemes Rainier and AIMer. Existing algebraic attacks on \textsc{Rain} and AIM were conducted over $\mathbb{F}_2$. We propose a novel algebraic attack over $\mathbb{F}_{2^n}$ that uses the polynomial decomposition to reduce degrees of equations. By further combining with the guess-and-determine technique, meet-in-the-middle modeling, and resultant, we are able to attack \textsc{Rain} and the full AIM. Specifically, we successfully attacked 2-round \textsc{Rain} with $2^{73.7}/2^{107.0}/2^{138.9}$ primitive calls, 3-round \textsc{Rain} with $2^{160.6}/2^{236.0}/2^{311.1}$ primitive calls, for the $128/192/256$-bit key. For the full AIM, we successfully attacked it with $2^{114.0}/2^{163.2}/2^{228.3}$ primitive calls for the $128/192/256$-bit key. The attack complexities mainly lie in solving univariate polynomial equations and computing resultants, and hence the complexity evaluations are accurate. \keywords{Polynomial Decomposition\and MITM \and \textsc{Rain} \and AIM \and Guess-and-determine \and Resultant.}

We show the first threshold blind signature scheme and threshold Oblivious PRF (OPRF) scheme which remain secure in the presence of an adaptive adversary, who can adaptively decide which parties to corrupt throughout the lifetime of the scheme. Moreover, our adaptively secure schemes preserve the minimal round complexity and add only a small computational overhead over prior solutions that offered security only for a much less realistic static adversary, who must choose the subset of corrupted parties before initializing the protocol. Our threshold blind signature scheme computes standard BLS signatures while our threshold OPRF computes the 2HashDH OPRF [52], and we prove adaptive security of both schemes in the Algebraic Group Model (AGM). Our adaptively secure threshold schemes are as practical as the underlying standard (i.e. single-server) BLS blind signature [15] and 2HashDH OPRF, and they can be used to add cryptographic fault-tolerance and decentralize trust in any system that relies on blind signatures, like anonymous credentials and e-cash, or on OPRF, like the OPAQUE password authentication and the Privacy Pass anonymous authentication scheme, among many others.

Fair multi-party coin toss protocols are fundamental to many cryptographic applications. While Cleve's celebrated result (STOC'86) showed that strong fairness is impossible against half-sized coalitions, recent works have explored a relaxed notion of fairness called Cooperative-Strategy-Proofness (CSP-fairness). CSP-fairness ensures that no coalition has an incentive to deviate from the protocol. Previous research has established the feasibility of CSP-fairness against majority-sized coalitions, but these results focused on specific preference structures where each player prefers exactly one outcome out of all possible choices. In contrast, real-world scenarios often involve players with more complicated preference structures, rather than simple binary choices. In this work, we initiate the study of CSP-fair multi-party coin toss protocols that accommodate arbitrary preference profiles, where each player may have an unstructured utility distribution over all possible outcomes. We demonstrate that CSP-fairness is attainable against majority-sized coalitions even under such arbitrary preferences. In particular, we give the following results: \begin{itemize} \item We give a reduction from achieving CSP-fairness for arbitrary preference profiles to achieving CSP-fairness for structured split-bet profiles, where each player distributes the same amount of total utility across all outcomes. \item We present two CSP-fair protocols: (1) a \emph{size-based protocol}, which defends against majority-sized coalitions, and (2) a \emph{bets-based protocol}, which defends against coalitions controlling a majority of the total utilities. \item Additionally, we establish an impossibility result for CSP-fair binary coin toss with split-bet preferences, showing that our protocols are nearly optimal. \end{itemize}

Laconic cryptography focuses on designing two-message protocols that allow secure computation over large datasets while minimizing communication costs. While laconic cryptography protocols achieve asymptotically optimal communication complexity for many tasks, their concrete efficiency is prohibitively expensive, due to heavy use of public-key techniques or non-black-box cryptographic primitives. In this work, we initiate the study of {\it laconic cryptography with preprocessing}, introducing a model that includes an offline phase to generate database-dependent correlations, which are then used in a lightweight online phase. These correlations are conceptually simple, relying on linear-algebraic techniques. This enables us to develop a protocol for private laconic vector oblivious linear evaluation (plvOLE). In such a protocol, the receiver holds a large database $\mathsf{DB}$, and the sender has two messages $v$ and $w$ along with an index $i$. The receiver learns the value $v \cdot \mathsf{DB}_i + w$ without revealing other information. Our protocol, which draws from ideas developed in the context of private information retrieval with preprocessing, serves as the backbone for two applications of interest: laconic private set intersection (lPSI) for large universes and laconic function evaluation for RAM programs (RAM-LFE). Based on our plvOLE protocol, we provide efficient instantiations of these two primitives in the preprocessing model.

Homomorphic Encryption (HE) enables the secure computation of functions on ciphertexts without requiring decryption. Specifically, AP-like HE schemes exploit an intrinsic bootstrapping method called blind rotation. In existing blind rotation methods, a look-up table is homomorphically evaluated on the input ciphertext through iterative multiplication of monomials. However, the algebraic structure of the multiplicative group of monomials imposes certain limitations on the input plaintext space, as it can bootstrap only a fraction of the input plaintext space. In this work, we introduce a new HE scheme, Carousel, that solves this problem. The key idea of our approach is to utilize the automorphism group instead of monomials. More specifically, the look-up table is encoded into a single polynomial that can be rotated via a series of homomorphic multiplications and automorphisms. We instantiate Carousel with subring encoding proposed by Arita and Handa (ICISC '17) and provide a proof-of-concept implementation. Our benchmark result shows that Carousel can bootstrap 4-bit integers in under 30ms.

Fault attacks pose a significant threat to cryptographic implementations, motivating the development of countermeasures, primarily based on a combination of redundancy and masking techniques. Redundancy, in these countermeasures, is often implemented via duplication or linear codes. However, their inherent structure remains susceptible to strategic fault injections bypassing error checks. To address this, the CAPA countermeasure from CRYPTO 2018 leveraged information-theoretic MAC tags for protection against fault and combined attacks. However, a recent attack has shown that CAPA does not achieve protection against combined attacks and offers only limited fault protection, while also incurring significant hardware overhead. Its successor, M\M, improves efficiency but fails to protect against ineffective faults. In this paper, we introduce StaMAC, a framework for securely integrating MAC tags against both side-channel and fault attacks in a non-combined setting. Building on the security notions from StaTI (TCHES 2024), we propose the notion of \textit{MAC-stability}, which ensures fault propagation in masked and MACed circuits while requiring only a single error check at the end of the computation. We further show that the stability notion from StaTI is arbitrarily composable (whereas it was previously thought to be only serially composable), making it the first arbitrary composable fault security notion which does not require intermediate error checks or corrections. Then, we establish the improved protection of masking combined with MAC tags compared to linear encoding techniques by showing bounds on the advantage considering several fault adversaries: a gate/register faulting adversary, an arbitrary register faulting adversary, and a random register faulting adversary. Then, we show how to transform any probing secure circuit to protect against fault attacks using the proposed MAC-stable gadgets implementing field operations. Finally, we demonstrate StaMAC on an AES implementation, evaluating its security and hardware costs in comparison to MAC-based countermeasures.

CKKS is a homomorphic encryption (HE) scheme that supports approximate arithmetic over complex numbers. While it is widely used in privacy-preserving machine learning (PPML) protocols, the approximate nature of the scheme makes it challenging to formally define the security guarantees of those protocols. In particular, in a sender-receiver protocol, where the sender performs homomorphic evaluation using a private circuit, characterizing the sender's privacy remains an important open problem. Moreover, there are currently no known methods for handling malicious receivers due to the absence of a zero-knowledge argument of knowledge (ZKAoK) for the CKKS scheme. In this paper, we address these open challenges. First, we introduce a new security definition, called Differentially Private Homomorphic Evaluation (DPHE), to formalize sender privacy in CKKS-based protocols. Next, we present a general compilation method that transforms a plain CKKS protocol into a DPHE protocol. Finally, we construct a zero-knowledge argument of knowledge (ZKAoK) for CKKS to achieve the DPHE property in the presence of malicious receivers, and provide concrete benchmarks of our ZKAoK implementation. To the best of our knowledge, this is the first work to formally address security and privacy issues in CKKS-based protocols through the lens of differential privacy. We also remark that our ZKAoK is the first construction to ensure the well-formedness of CKKS public keys and ciphertexts.

The fundamental assumption in $t$-out-of-$n$ threshold encryption is that the adversary can only corrupt fewer than $t$ parties. However, this may be unrealistic in practical scenarios where shareholders could have financial incentives to collude. Boneh, Partap, and Rotem (Crypto'24) addressed the case where $t$ or more shareholders collude, adding a traceability mechanism to identify at least one colluder. Their constructions require a trusted dealer to distribute secret shares, but it is unclear how to achieve traceability without this trusted party. Since threshold encryption aims to avoid a single point of failure, a natural question is whether we can construct an efficient, traceable threshold encryption scheme without relying on a trusted dealer. This paper presents two dealerless, traceable threshold encryption constructions by extending the PLBE primitive of Boneh et al. (Eurocrypt'06) and combining it with the silent setup threshold encryption construction of Garg et al. (Crypto'24). Our first construction achieves an amortized ciphertext size of $O(1)$ (for $O(n)$ ciphertexts), and the second achieves constant ciphertext size in the worst case but with a less efficient preprocessing phase. Both have constant secret key sizes and require no interaction between parties. A limitation of Boneh et al.’s constructions is that they only guarantee identifying one colluder, leaving the problem of tracing more traitors unsolved. We address this by applying a technique to our first construction that enables tracing up to $t$ traitors.

One-more problems like One-More Discrete Logarithm (OMDL) and One-More Diffie--Hellman (OMDH) have found wide use in cryptography, due to their ability to naturally model security definitions for interactive primitives like blind signatures and oblivious PRF. Furthermore, a generalization of OMDH called Threshold OMDH (TOMDH) has proven useful for building threshold versions of interactive protocols. However, due to their complexity it is often unclear how hard such problems actually are, leading cryptographers to analyze them in idealized models like the Generic Group Model (GGM) and Algebraic Group Model (AGM). In this work we give a complete characterization of widely used group-based one-more problems in the AGM, using the $Q$-DL hierarchy of assumptions defined in the work of Bauer, Fuchsbauer and Loss (CRYPTO '20). - Regarding (T)OMDH, we show (T)OMDH is part of the Q-DL hierarchy in the AGM; in particular, Q-OMDH is equivalent to Q-DL. Along the way we find and repair a flaw in the original GGM hardness proof of TOMDH, thereby giving the first correct proof that TOMDH is hard in the GGM. - Regarding OMDL, we show the Q-OMDL problems constitute an infinite hierarchy of problems in the AGM incomparable to the Q-DL hierarchy; that is, Q-OMDL is strictly harder than Q'-OMDL if Q < Q', and Q-OMDL is incomparable to Q'-DL (i.e., there are no reductions either way) unless Q = Q' = 0.

In this paper, we revisit the security of randomized hash & sign. More precisely, we present an improved security analysis for the underlying hash function property multi-target extended target collision resistance (M-eTCR) in the quantum random oracle model (QROM). While prior work relied on reprogramming techniques to handle adversarial challenge queries, we leverage the hybrid compressed oracle framework of Hamoudi, Liu, and Sinha to formulate an adaptive search problem. To do so, we had to extend their framework to cover partially randomized classical adversary queries. We conjecture that this extension will also allow to analyze further hash function properties that allow adversaries to define challenges via a classical oracle. By applying the extended framework to M-eTCR, we give an improved upper bound on the adversary's success probability. Our results show that the required key size for M-eTCR can be reduced by more than half (from 192 to 72 bits), and we prove the tightness of our bound in the number of queries via matching attacks. To illustrate practical impact, we optimize parameters for Falcon in the hash & sign paradigm, enabling more efficient instantiations with reduced salt sizes resulting in smaller signature lengths. For the example of multiple signatures aggregation, we achieve a signature size improvement of 30 kB for typical parameters.

\emph{Anonymous rate-limited tokens} are a special type of credential that can be used to improve the efficiency of privacy-preserving authentication systems like Privacy Pass. In such a scheme, a user obtains a ``token dispenser'' by interacting with an issuer, and the dispenser allows the user to create up to a pre-determined number $k$ of unlinkable and publicly verifiable tokens. Unlinkable means that one should not be able to tell that two tokens originate from the same dispenser, but also they cannot be linked to the interaction that generated the dispenser. Furthermore, we can limit the rate at which these tokens are created by linking each token to a context (e.g., the service we are authenticating to), and imposing a limit $N \leq k$ such that seeing more than $N$ tokens for the same context will reveal the identity of the user. Constructions of such tokens were first given by Camenisch, Hohenberger and Lysyanskaya (EUROCRYPT '05) and Camenisch, Hohenberger, Kohlweiss, Lysyanskaya, and Meyerovich (CCS '06). In this work, we present the first construction of \emph{everlasting} anonymous rate-limited tokens, for which unlinkability holds against computationally \emph{unbounded} adversaries, whereas other security properties (e.g., unforgeability) remain computational. Our construction relies on pairings. While several parameters in our construction unavoidably grow with $k$, the key challenge we resolve is ensuring that the complexity of dispensing a token is \emph{independent} of the parameter $k$. We are motivated here by the goal of providing solutions that are robust to potential future quantum attacks against the anonymity of previously stored tokens. A construction based on post-quantum secure assumptions (e.g., based on lattices) would be rather inefficient---instead, we take a pragmatic approach dispensing with post-quantum security for properties not related to privacy.

BBS/BBS+ signatures are the most promising solution to instantiate practical and lightweight anonymous credentials. They underlie standardization efforts by the W3C and the IRTF. Due to their potential for large scale deployment, it is paramount to understand their concrete security, but a number of questions have been left open by prior works. To this end, the security proofs by Au et al. (SCN '06), Camenisch et al. (TRUST '16), and Tessaro and Zhu (EUROCRYPT '23) show reductions from $q$-SDH in groups of prime order $p$, where $q$ is the number of issued signatures. However, these prior works left the possibility open that BBS/BBS+ is {\em even more secure} than what can be guaranteed by such proofs. Indeed, while the $q$-SDH assumption is subject to an attack that uses $O(\sqrt{p/q})$ group exponentiations (Cheon, EUROCRYPT '06) for several choices of $q$, no attack with a similar complexity appears to affect either of BBS+ and {\em deterministic} BBS, for which the best known attacks amount to recovering the secret key by breaking the discrete logarithm problem. The assumption that this attack is best possible also seemingly justifies the choice of parameters in practice. Our result shows that this expectation is not true. We show new attacks against BBS+ and {\em deterministic} BBS which, after seeing $q$ signatures, allow us to recover the secret key with the same complexity as solving the $\Theta(q)$-Discrete Logarithm problem, which in turn is proportional to $O(\sqrt{p/q})$ for many choices of $q$. Further, we also extend the attack to a reduction showing that the security of BBS+ and deterministic BBS implies the $\Theta(q)$-SDH assumption.

Provable security is a cornerstone of modern cryptography, aiming to provide formal and precise security guarantees. However, for various reasons, security proofs are not always properly verified, possibly leading to unwarranted security claims and, in the worst case, deployment of insecure constructions. To further enhance trust and assurance, machine-checked cryptography makes these proofs more formal and rigorous. Unfortunately, the complexity of writing machine-verifiable proofs remains prohibitively high in many interesting use-cases. In this paper, we investigate the sources of this complexity, specifically examining how the style of security definitions influences the difficulty of constructing machine-verifiable proofs in the context of game-playing security. Concretely, we present a new security proof for the generic construction of a PKAE scheme from a NIKE and AE scheme, written in a code-based, game-playing style `a la Bellare and Rogaway, and compare it to the same proof written in the style of state-separating proofs, a methodology for developing modular game-playing security proofs. Additionally, we explore a third “blended” style designed to avoid anticipated difficulties with the formalization. Our findings suggest that the choice of definition style impacts proof complexity—including, we argue, in detailed pen- and-paper proofs—with trade-offs depending on the proof writer’s goals.

While consistency and liveness are the defining properties of ledger consensus, fair ordering has emerged as an independent consideration whose importance is underscored by the observation of real world transaction inclusion strategies that manipulate fairness such as Miner Extractable Value. Receiver-order fairness is a fine-grain notion of fairness that determines the order of any two submitted transactions based on the two sequences of reception timestamps for the two transactions across all nodes in the network. Given this information, ledger serialization can be viewed as the social choice problem of producing the most agreeable transaction order based on the "preferences" of the miners or validators. In this work, our contribution is three-fold: (i) We put forward a formal Universally Composable definition for order fairness that encompasses receiver order fairness as well as input causality. (ii) We design a novel ledger protocol that preserves input causality and receiver order fairness. (iii) We capture in our composable definition and construction the role that transaction fees play when dealing with fairness. Our protocol is based on a novel YOSO-style approach that allows encrypting transactions for a short period of time. Notably, the communication complexity required to decrypt the transactions is independent of the number of encrypted transactions. To the best our our knowledge, we are the first to provide a YOSO-style approach with such asymptotic complexity while relying on standard cryptographic assumptions.

White-box cryptography aims to protect cryptographic implementations against adversaries with full access to execution environments. The encoding-based white-box implementations in {\sffamily SASAS} and {\sffamily ASA} constructions without the external encodings are vulnerable to automated side-channel analysis such as \textit{differential computation analysis} (DCA) and \textit{differential fault analysis} (DFA). The proposed countermeasures for encoding-based white-box implementations, such as \textit{masking} and \textit{table redundancy}, are designed to provide one-side defense against either DCA or DFA. However, these approaches are insecure, and no unified countermeasure capable of simultaneously defending against both DCA and DFA has been proposed. This paper proposes the first encoding-based white-box implementation with an {\sffamily ASASA} structure against both DCA and DFA attacks. By decomposing and recombining Sbox layers across rounds, our construction conceals round boundaries while enabling efficient representation via multivariate polynomials. Without the external encoding, the {\sffamily ASA}-based first and last rounds inherently resist DFA while remaining vulnerable to DCA. To enhance the DCA resistance, we introduce a cipher-level defense framework integrating anti-DCA Sboxes and anti-DCA/DFA layers. This unified approach provides $n$-bit security for an $n$-bit block length cipher against both DCA and DFA attacks. Our work bridges critical gaps in white-box cryptography by enabling {\sffamily ASASA}-based encodings and offering combined DCA and DFA countermeasures through novel cipher-level constructions.

The machine learning problem of model extraction was first introduced in 1991 and gained prominence as a cryptanalytic challenge starting with Crypto 2020. For over three decades, research in this field has primarily focused on ReLU-based neural networks. In this work, we take the first step towards the cryptanalytic extraction of PReLU neural networks, which employ more complex nonlinear activation functions than their ReLU counterparts. We propose a raw output-based parameter recovery attack for PReLU networks and extend it to more restrictive scenarios where only the top-m probability scores are accessible. Our attacks are rigorously evaluated through end-to-end experiments on diverse PReLU neural networks, including models trained on the MNIST dataset. To the best of our knowledge, this is the first practical demonstration of the PReLU neural network extraction across three distinct attack scenarios.

We make progress on the foundational problem of determining the strongest security notion achievable by homomorphic encryption. Our results are negative. We prove that a wide class of semi-homomorphic public key encryption schemes (SHPKE) cannot be proven IND-PCA secure (indistinguishability against plaintext checkability attacks), a relaxation of IND-CCA security. This class includes widely used and versatile schemes like ElGamal PKE, Paillier PKE, and the linear encryption system by Boneh, Boyen, and Shacham (Crypto'04). In contrast to CCA security, where the adversary is given access to a decryption oracle, in a PCA attack the adversary solely has access to an oracle that decides for a given ciphertext/plaintext pair (c,m) if c indeed encrypts m. Since the notion of IND-PCA security is weaker than IND-CCA security, it is not only easier to achieve, leading to potentially more efficient schemes in practice, but it also side-steps existing impossibility results that rule out the IND-CCA security. To rule out IND-PCA security we thus have to rely on novel techniques. We provide two results, depending on whether the attacker is allowed to query the PCA oracle after it has received the challenge (IND-PCA2 security) or not (IND-PCA1 security -- the more challenging scenario). First, we show that IND-PCA2 security can be ruled out unconditionally if the number of challenges is smaller than the number of queries made after the challenge. Next, we prove that no Turing reduction can reduce the IND-PCA1 security of SHPKE schemes with O(\kappa^3) PCA queries overall to interactive complexity assumptions that support t-time access to their challenger with t=O(\kappa). To obtain our second impossibility results, we develop a new meta-reduction-based methodology that can be used to tackle security notions where the attacker is granted access to a decision oracle. Previous works on meta-reduction-based impossibility results focused on definitions that allow the attacker to access an inversion oracle (e.g. long-term key corruptions or a signature oracle) making the corresponding techniques generally not applicable in our scenario. To obtain our result, we have to overcome several technical challenges that are entirely novel to the setting of public key encryption.

We study linear-time prover SNARKs and make the following contributions: We provide a framework for transforming a univariate polynomial commitment scheme into a multilinear polynomial commitment scheme. Our transformation is generic, can be instantiated with any univariate scheme and improves on prior transformations like Gemini (EUROCRYPT 2022) and Virgo (S&P 2020) in all relevant parameters: proof size, verification complexity, and prover complexity. Instantiating the above framework with the KZG univariate polynomial commitment scheme, we get SamaritanPCS -- the first multilinear polynomial commitment scheme with constant proof size and linear-time prover. The proof size is just 368 bytes, which is the smallest among all multilinear polynomial commitment schemes. Our scheme also has excellent batching properties, wherein proving k evaluations over the hypercube of size n incurs O(n+k\sqrt{n}) cryptographic work, resulting in substantially amortized prover work over several evaluations. We construct LogSpartan -- a new multilinear PIOP for R1CS based on recent techniques for lookup arguments. Compiling this PIOP using SamaritanPCS gives Samaritan -- a SNARK in the universal and updatable SRS setting. Samaritan has linear-time prover, logarithmic verification and logarithmic proof size. Concretely, its proof size is one of the smallest among other known linear-time prover SNARKs without relying on concretely expensive proof recursion techniques. For an R1CS instance with 1 million constraints, Samaritan (over the BLS12-381 curve) has a proof size of 6.2KB. We compare Samaritan with other linear-time prover SNARKs in the updatable setting. We asymptotically improve on the \log^2(n) proof size of Spartan. Unlike Libra (CRYPTO 2019), the argument size of Samaritan is independent of the circuit depth. Compared to Gemini (EUROCRYPT 2022), SamaritanPCS achieves 3x smaller argument size at 1 million constraints. We are competitive with the very recently proposed MicroSpartan (S&P 2025) and linear-time SNARKs for the Plonkish constraint system such as HyperPlonk (EUROCRYPT 2023).

Many design strategies and differential attacks rely on the so-called hypothesis of stochastic equivalence, which states that the differential behaviour of a cipher for any fixed key can be approximated by its average behaviour over all keys. However, this assumption is known to be invalid in general. For instance, all two-round differential characteristics of AES are plateau, meaning that their probabilities highly depend on the key. While such discrepancies were traditionally expected to occur only for a small number of rounds, several counter-examples have been exhibited recently thanks to the quasi-differential framework. This paper aims to show why the divergence between fixed-key and average behaviour can be even more pronounced and is definitely harder to anticipate, when analyzing differentials, rather than individual characteristics, which is the quantity actually relevant in differential cryptanalysis. Indeed, when a differential aggregates many characteristics that do not satisfy the hypothesis of stochastic equivalence, several scenarios may arise: the sets of weak keys may be identical across all characteristics, resulting in a strong clustering effect, or entirely disjoint, eliminating any such effect. Focusing on (truncated) differentials that include plateau characteristics, we demonstrate how this mechanism explains the unexpected differential behaviour observed in Midori64 and Scream over an arbitrary number of rounds, as recently reported by Baudrin et al. We also clarify how this situation differs from invariant subspaces, except in a few specific cases. Furthermore, we identify the properties of the Sbox that give rise to this weakness and identify all vulnerable Sboxes among the optimal 4-bit functions.

In a threshold decryption system a secret key is split across a number of parties so that any threshold of them can decrypt a given ciphertext. We introduce a new concept in threshold decryption called a {\em decryption context}, which is an additional argument that is used during decryption. The context ensures that decryption shares that are generated for a ciphertext using different contexts are isolated from each other and cannot be jointly used to decrypt the ciphertext. For example, suppose the decryption threshold is~$t$. Further, suppose that less than~$t$ decryption shares are generated for a ciphertext~$c$ under one context, and less than~$t$ decryption shares are generated for~$c$ under a different context. Then this set of shares is insufficient to decrypt~$c$ even if the total number of shares exceeds~$t$. This new concept has several important applications, most notably for implementing an encrypted mempool in a consensus protocol. We give two CCA-secure threshold decryption constructions that support context. One is based on ElGamal encryption, and the other is generic showing how to add context to any CCA-secure threshold decryption system without changing the encryption algorithm.

We propose a Polynomial Commitment Scheme (PCS), called BrakingBase, which allows a prover to commit to multilinear (or univariate) polynomials with n coefficients in O(n) time. The evaluation protocol of BrakingBase operates with an O(n) time-complexity for the prover, while the verifier time-complexity and proof-complexity are O(λ log n), where λ is the security parameter. Notably, BrakingBase is field-agnostic, meaning it can be instantiated over any field of sufficiently large size. Additionally, BrakingBase can be combined with the Polynomial Interactive Oracle Proof (PIOP) from Spartan (Crypto 2020) to yield a Succinct Non-interactive ARgument of Knowledge (SNARK) with a linear-time prover, as well as poly-logarithmic complexity for both the verifier runtime and the proof size. We obtain our PCS by combining the Brakedown and Basefold PCS. The commitment protocol of BrakingBase is similar to that of Brakedown. The evaluation protocol of BrakingBase improves upon Brakedown’s verifier work by reducing it through multiple instances of the sum-check protocol. Basefold PCS is employed to commit to and later evaluate the multilinear extension (MLE) of the witnesses involved in the sum-check protocol at random points. This includes the MLE corresponding to the parity-check matrix of the linear-time encodable code used in Brakedown. We show that this matrix is sparse and use the Spark compiler from Spartan to evaluate its multilinear extension at a random point. We implement BrakingBase and compare its performance to Brakedown and Basefold over a 128 bit prime field.

Homomorphic Secret Sharing (HSS) allows clients to split their inputs among several servers, and supports the servers to homomorphically evaluate public functions over their local shares, such that the function value of the inputs can be efficiently reconstructed from the output shares of the servers. For all existing schemes, all servers are required to participate in the reconstruction process, and the reconstruction will fail even if one server is missing. In this work, we study HSS that supports threshold reconstruction, where the reconstruction still works even if a few servers fail. We first formalize the syntax and security notions of threshold HSS in the public-key setup model, which is a popular model in the literature. Then we present a new generic construction of HSS, which is the first construction that enjoys both threshold reconstruction and public reconstruction. To this end, we introduce a refined version of functional encryption, named HSS-friendly functional encryption. Furthermore, we instantiate our construction with quadratic functional encryption schemes modified from existing works. Compared with the state-of-the-art, our concrete scheme achieves the threshold reconstruction at the expense of slightly increasing the communication complexity.

Bootstrapping remains the primary bottleneck in most FHE schemes, significantly impacting their efficiency. To enhance both the speed and precision of bootstrapping, sparse secrets have been widely adopted, particularly in SIMD-style FHE schemes such as BGV, BFV, and CKKS. However, the security of sparse LWE secrets is not well understood, leading to their exclusion from standardization efforts. To address this gap between the potential security risks of sparse secrets and the inefficiency of dense-secret bootstrapping, we introduce the subring secret encapsulation method. This approach involves switching to a dense secret in a subring before bootstrapping, thereby improving bootstrapping performance while still basing security on dense secret LWE. The EvalMod and digit removal steps are accelerated due to the smaller Hamming weight of the subring secret. Furthermore, the algebraic structure of the subring secret enables faster CoeffsToSlots and SlotsToCoeffs operations through hoisted key switchings. When applied to the CKKS scheme, our method achieves a bootstrapping throughput increase of 46\%–51\% compared to state-of-the-art dense secret bootstrapping techniques. For BGV/BFV schemes, our approach demonstrates a 2.48x improvement in throughput when bootstrapping $2^{15}$ slots modulo $65537$.

Leakage-resilient secret sharing is a fundamental building block for securing implementations against side-channel attacks. In general, such schemes correspond to a tradeoff between the complexity of the resulting masked implementations, their security guarantees and the physical assumptions they require to be effective. In this work, we revisit the Inner-Product (IP) framework, where a secret s is encoded by two vectors (w,y), such that their inner product is equal to s. So far, the state of the art is split in two. On the one hand, the most efficient IP masking schemes (in which w is public but random) are provably secure with the same security notions (i.e., in the abstract probing model) as Boolean masking, yet at the cost of a slightly more expensive implementation. Hence, their theoretical interest and practical relevance remain unclear. On the other hand, the most secure IP masking schemes (in which w is secret) lead to expensive implementations. We improve this state of the art by investigating the leakage resilience of IP masking with public w coefficients in the bounded leakage model, which depicts well implementation contexts where the physical noise is negligible. Furthermore, we do that without assuming independent leakage from the shares, which may be challenging to enforce in practice. In this model, we show that if m bits are leaked from the d shares y of the encoding over an n-bit field, then, with probability at least 1 - 2^{-\lambda} over the choice of w, the scheme is O(\sqrt{2^{-(d-1). n + m + 2\lambda)-leakage resilient. We additionally show that in large Mersenne-prime fields, a wise choice of the public coefficients w can yield leakage resilience up to O(n \cdot 2^{-d . n + n+d), in the case where one physical bit from each share is revealed to the adversary. The exponential rate of the leakage resilience we put forward significantly improves upon previous bounds in additive masking, where the past literature exhibited a constant exponential rate only. We additionally discuss the applications of our results, and the new research challenges they raise.

Approximate Homomorphic Encryption (AHE), introduced by Cheon et al.~\cite{AC:CKKS17} offers a powerful solution for encrypting real-valued data by relaxing the correctness requirement and allowing small decryption errors. Existing constructions from (Ring) Learning with Errors achieve standard IND-CPA security, but this does not fully capture scenarios where an adversary observes decrypted outputs. Li and Micciancio~\cite{EC:LiMic21} showed that when decryptions are passively leaked, these schemes become vulnerable to practical key recovery attacks even against honest-but-curious attackers. They formalise security when decryptions are shared with new notions of IND-CPA-D and KR-D security. We propose new techniques to achieve provable IND-CPA-D and KR-D security for AHE, while adding substantially less additional decryption noise than the prior provable results. Our approach hinges on refined ``game-hopping" tools in the bit-security framework, which allow bounding security loss with a lower noise overhead. We also give a noise-adding strategy independent of the number of oracle queries, removing a costly dependence inherent in the previous solution. Beyond generic noise-flooding, we show that leveraging the recently introduced HintLWE problem~\cite{C:KLSS23b} can yield particularly large security gains for AHE ciphertexts that are the result of “rescaling,” a common operation in CKKS. Our analysis uses the fact that that rescale-induced noise amounts to a linear ``hint" on the secret to enable a tighter reduction to LWE (via HintLWE). In many practical parameter regimes where the rescaling noise dominates, our results imply an additional precision loss of as little as two bits is sufficient to restore a high level of security against passive key-recovery attacks for standard parameters. Overall, our results enable a provably secure and efficient real-world deployment of Approximate Homomorphic Encryption in scenarios with realistic security requirements.

Blind signatures are fundamental cryptographic primitives enabling privacy-preserving authentication and have seen renewed interest in the post-quantum literature. Existing efficient constructions predominantly rely on Fischlin’s generic paradigm instantiated over lattice assumptions, while blinding techniques for $\Sigma$-protocol-based blind signatures remain sparse beyond lattices. Moreover, achieving provable concurrent security under polynomially many sessions has been a longstanding open challenge for this approach in the post-quantum literature as evidenced by the recent attacks in EC’24 and PKC’24. This work broadens the landscape of post-quantum blind signatures by introducing novel techniques and proposing four frameworks based on general cryptographic group actions, without requiring commutativity. Our constructions admit instantiations under diverse post-quantum assumptions, including CSIDH (isogeny-based), LESS (code-based, NIST round-two), and more. These frameworks offer flexible trade-offs in assumptions (from interactive one-more to the standard inversion problem) and key/signature sizes, and culminate in a construction that achieves security under polynomially many concurrent sessions. This enables the first efficient blind signatures from isogenies and codes with provable concurrent security with 4.5 and 64.7 KB respectively. We also outline several directions for optimization and further instantiations for future work.

Fiat-Shamir signatures replace the challenge in interactive identification schemes by a hash value over the commitment, the message, and possibly the signer’s public key. This construction paradigm is well known and widely used in cryptography, for example, for Schnorr signatures and CRYSTALS-Dilithium. There is no “general recipe” for constructing Fiat-Shamir signatures regarding the inputs and their order for the hash computation, though, since the hash function is usually modeled as a monolithic random oracle. In practice, however, the hash function is based on the Merkle-Damgård or the sponge design. Our work investigates whether there are advisable or imprudent input orders for hashing in Fiat-Shamir signatures. We examine Fiat-Shamir signatures with plain and nested hashing using Merkle-Damgård or sponge-based hash functions. We analyze these constructions in both classical and quantum settings. As part of our investigations, we introduce new security properties following the idea of quantum-annoyance of Eaton and Stebila (PQCrypto 2021), called annoyance for user exposure and signature forgeries. These properties ensure that an adversary against the hash function cannot gain a significant advantage when attempting to extend a successful attack on a single signature forgery to multiple users or to multiple forgeries of a single user. Instead, the adversary must create extra forgeries from scratch. Based on our analysis, we derive a simple rule: When using Fiat-Shamir signatures, one should hash the commitment before the message; all other inputs may be ordered arbitrarily.

We propose BLASter, a proof of concept LLL implementation that demonstrates the practicality of multiple theoretical improvements. The implementation uses the segmentation strategy from Neumaier–Stehlé (ISSAC 2016), parallelism and Seysen's reduction that was proposed by Kirchner–Espitau–Fouque (CRYPTO 2021) and implemented in OptLLL, and the BLAS library for linear algebra operations. It consists of only 1000 significant lines of C++ and Python code, and is made publicly available. For q-ary lattices that fplll can handle without multiprecision (dimension <180), BLASter is considerably faster than fplll, OptLLL and Ryan–Heninger's flatter (CRYPTO 2023), without degrading output reduction quality. Thanks to Seysen's reduction it can further handle larger dimension without resorting to multiprecision, making it more than 10x faster than flatter and OptLLL, and 100x faster than fplll in dimensions 256 to 1024. It further includes segmented BKZ and segmented deep-LLL variants. The latter provides bases as good as BKZ-15 and has a runtime that is only a couple of times more than our LLL baseline. This remains a proof of concept: the effective use of higher precision — which is needed to handle all lattices — has further obstacles and is left for future work. Still, this work contains many lessons learned, and is meant to motivate and guide the development of a robust and modern lattice reduction library, which shall be much faster than fplll.