Private histogram computation is a fundamental building block for many data analytics tasks, enabling frequency analysis without revealing individual inputs. Existing protocols achieving robustness against malicious clients and servers typically require three servers with limited adversarial tolerance, restricting practicality.

In this work, we present Paras, the first two-server protocol for private histogram computation that achieves robustness against collusion between a malicious server and arbitrarily many malicious clients. Paras builds upon distributed point function-based approaches and introduces novel consistency checks leveraging vector oblivious linear evaluation (VOLE) to enforce both input correctness and output integrity. To realize these checks, we design two new cryptographic primitives: (1) aBV, an authenticated bit verification protocol that ensures VOLE committed shares correspond to valid bits, and (2) adIPA, an authenticated double inner product argument that enables secure consistency checks across two different VOLE sessions. These primitives may be of independent interest for other secure computation tasks.

We show that Paras is highly efficient and scalable: clients incur minimal cost independent of domain size, while servers achieve low per-client runtime, communication, and storage even at scale. For example, with 8192 clients over a domain of 128 inputs, each server requires only 14 ms runtime and 24 KB communication per client.

In quantum cryptography, there could be a new world, Microcrypt, where cryptography is possible but one-way functions (OWFs) do not exist. Many quantum analogues of OWFs and pseudorandom generators (PRGs) that are potentially weaker than OWFs have been introduced, and their useful applications have been demonstrated. However, Microcrypt still lacks enough foundations on which they are based compared with the classical cryptographic world. In classical cryptography, many hardness assumptions on concrete mathematical problems have been introduced, such as the discrete logarithm (DL) problems or the decisional Diffie-Hellman (DDH) problems on concrete group structures related to finite fields or elliptic curves. They are then abstracted to generic hardness assumptions such as the DL and DDH assumptions over group actions. Finally, based on these generic assumptions, primitives and applications are constructed. The goal of the present paper is to introduce several abstracted generic hardness assumptions in Microcrypt, which could connect concrete mathematical hardness assumptions with applications. Our assumptions are based on a quantum analogue of group actions. A group action is a tuple $(G,S,\star)$ of a group $G$, a set $S$, and an operation $\star:G\times S\to S$. We introduce a quantum analogue of group actions, which we call quantum group actions (QGAs), where $G$ is a subgroup of unitary operators, $S$ is a set of states, and $\star$ is the application of a unitary on a state. By endowing QGAs with some reasonable hardness assumptions, we introduce a natural quantum analogue of the decisional Diffie-Hellman (DDH) assumption and pseudorandom group actions. As an application, we construct classical-query pseudorandom function-like state generators (PRFSGs) based on these assumptions. PRFSGs are a quantum analogue of pseudorandom functions (PRFs), and have many applications such as IND-CPA SKE, EUF-CMA MAC, and private-key quantum money schemes. We also show that those assumptions are implied by non-adaptive pseudorandom unitaries (PRUs). Because classical group actions are instantiated with many concrete mathematical hardness assumptions, our QGAs could also have concrete (even OWFs-free) instantiations. We provide some candidate instantiations based on random circuits and IQP circuits.

Password Authenticated Key Exchange (PAKE) establishes secure communication channels using passwords for authentication. Currently, standardized PAKEs rely on classical asymmetric cryptography. However, these PAKEs may become insecure should the expected quantum threat become a reality. Despite the growing interest in realizing quantum-safe PAKEs, they did not receive much attention from the ongoing Post-Quantum Cryptography (PQC) integration efforts. Hence, there is a significant awareness gap compared to PQC primitives subject to the official standardization processes. We provide a comprehensive overview of existing PQC PAKEs, classify their design rationales and authentication methods, and address aspects related to their security and performance. We identify PAKE designs that are still unexplored in the PQC realm and discuss the possibility of their adaptation. Thus, we offer a detailed reference for future work on PQC PAKEs.

The major Fully Homomorphic Encryption (FHE) schemes guarantee the privacy of the encrypted message only in the honest-but-curious setting, when the server follows the protocol without deviating. However, various attacks in the literature show that an actively malicious server can recover sensitive information by executing incorrect functions, tampering with ciphertexts, or observing the client's reaction during decryption.

Existing integrity solutions for FHE schemes either fail to guarantee circuit privacy, exposing the server's computations to the client, or introduce significant computational overhead on the prover by requiring proofs of FHE operations on ciphertexts.

In this work, we present Fherret, a novel scheme leveraging the MPC-in-the-Head (MPCitH) paradigm to provide a proof of correct-and-honest homomorphic evaluation while preserving circuit privacy. This proof guarantees that the client can safely decrypt the ciphertext obtained from the server without being susceptible to reaction-based attacks, such as verification and decryption oracle attacks. Additionally, this proof guarantees that the server's evaluation maintains correctness, thereby protecting the client from IND-CPA-D-style attacks.

Our solution achieves a prover overhead of approximately 110-170 homomorphic evaluations of random functions from the function space F, while retaining a competitive verifier overhead of approximately 58-93 homomorphic evaluations and a communication size proportional to approximately 40 times the size of a function from F.

Furthermore, Fherret is inherently parallelizable because its MPCitH views can be computed independently, achieving a parallel computation overhead similar to a homomorphic evaluation of a single random function from F for both the prover and the verifier.

We present a practical, non-interactive threshold decryption scheme. It can be proven CCA secure with respect to adaptive corruptions in the random oracle model under the decisional Diffie-Hellman assumption. Our scheme, called TDH2a, is a minor modification of the TDH2 scheme presented by Shoup and Gennaro at Eurocrypt 1998, which was proven secure against static corruptions under the same assumptions. The design and analysis of TDH2a are based on a straightforward extension of the simple information-theoretic argument underlying the security of the Cramer-Shoup encryption scheme presented at Crypto 1998. We also present another variant, TDH2abc, which offers a higher degree of backward compatibility with TDH2, allowing one to effectively "hot swap" TDH2abc in to replace TDH2 in a "live" system, without changing the public encryption key, so that any extant ciphertexts remain decryptable.

We initiate the study of (n out of n) threshold signatures built from MPC-in-the-Head signatures. While recent impossibility results (Doerner, Kondi and Rosenbloom, CRYPTO'24) show that any such construction must have a signature size that grows with the number $n$ of users (or else require a prohibitive non-black-box use of cryptography), we outline a general strategy to confine the dependency in the number of users to a term of the form $\lambda^2 n + O(1)$, where $\lambda$ is a security parameter and $O(1)$ a constant that depends on the signature scheme. We provide a concrete instantiation of our strategy by building a threshold signature on top of the scheme of (Carozza, Couteau, and Joux, EUROCRYPT'23).

The Möbius transform converts the truth table of a Boolean function to its algebraic normal form. It can be implemented efficiently by algorithms that operate similarly to the Fast Fourier Transform (FFT). It plays a useful role in cryptology, either to study properties of concrete Boolean functions, or in the implementation of cryptographic attacks that require building the truth table of Boolean functions given as low-degree polynomials. Because of this last application, Banik and Regazzoni presented hardware designs to implement the Möbius transform operation in TCHES, 2024(2). The proposed hardware implementations are claimed to compute the Möbius transform of $n$-bit Boolean functions with area-time product $AT = \mathcal{O}\left(n 2^n\right)$, where $A$ is the area of the logic gates of the circuit and $T$ is the runtime measured in clock cycles.

We study the communication complexity of the Möbius transform, using a slightly non-standard notion of “best-case” communication complexity for functions with large inputs. This directly leads to an $AT^2$ lower bound for hardware circuits, and using standard arguments from one-way communication complexity, to an area lower bound. We conclude that $AT = \Omega\left(2^{1.5n} / n^{1.5}\right)$ for any circuit that computes the Möbius transform, where $A$ is the area of the circuit including wires. Thus, a circuit implementing the Möbius transform can be asymptotically larger than the area of just its logic cells.

We also derive concrete version of these asymptotic statements, in which the constants are made explicit, based on physical properties of the circuit production process.

A data availability sampling scheme (DAS) allows a network of verifiers to collectively ensure that an untrusted party is correctly storing and distributing some committed data. Importantly, the protocol should not require that the verifiers coordinate or store the full data individually.

In this paper, we initiate the study of privacy in DAS schemes: we ask whether the DAS guarantees can be upheld while keeping the committed data secret. We define a natural notion of zero-knowledge for DAS and show that no secure DAS scheme can satisfy this notion. In doing so, we motivate the need to study privacy-preserving variants of DAS.

We define eDAS as DAS schemes over encrypted data and introduce the necessary security notions; namely, completeness, soundness and consistency. We additionally define a notion of privacy (zero-knowledge) and compliance (policy-enforcing). We then present two constructions of eDAS schemes. The first uses a DAS scheme as a black box and can be deployed on top of existing production-ready DAS systems with only minor modifications. The second is a more efficient construction that relies on the same principles but removes various layers of abstraction.

Indifferentiability is an important cryptographic paradigm for analyzing the security of ideal objects—both in a classical and quantum world. It is typically stated in the form of a composable and simulation-based definition, and captures what it means for a construction to be “as good as” an ideal object. A paradigmatic application of the framework is showing that a hash function does not have structural weaknesses, by proving it to be indifferentiable from a random oracle.

Despite its generality, indifferentiability is not known to offer security against pre-processing attacks, in which the adversary gains access to classical or quantum advice that is relevant to the particular construction. In this work, we show that indifferentiability is generically insufficient for capturing pre-computation. To accommodate this shortcoming, we propose a strengthening of indifferentiability which is not only composable but also takes arbitrary pre-computation into account. As an application, we show that the one-round sponge is indifferentiable with pre-computation from a random oracle. This yields the first, and tight, quantum space-time trade-offs for one-round sponge inversion.

In a functional encryption (FE) scheme, a user that holds a ciphertext and a function-key can learn the result of applying the function to the plaintext message. Security requires that the user does not learn anything beyond the function evaluation. We extend this notion to the quantum setting by providing definitions and a construction for a quantum functional encryption (QFE) scheme which allows for the evaluation of polynomially-sized circuits on arbitrary quantum messages. Our construction is built upon quantum garbled circuits [BY20].

We also investigate the relationship of QFE to the seemingly unrelated notion of unclonable encryption (UE) and find that any QFE scheme universally achieves the property of unclonable functional encryption (UFE). In particular we assume the existence of an unclonable encryption scheme with quantum decryption keys which was recently constructed by [AKY24]. Our UFE guarantees that two parties cannot simultaneously recover the correct function outputs using two independently sampled function secret keys. As an application we give the first construction for public-key UE with variable decryption keys.

Lastly, we establish a connection between quantum indistinguishability obfuscation (qiO) and quantum functional encryption (QFE); showing that any multi-input indistinguishability-secure quantum functional encryption scheme unconditionally implies the existence of qiO.

We investigate the notion of untelegraphable encryption (UTE), a quantum encryption primitive that is a special case of uncloneable encryption (UE), where the adversary’s capabilities are restricted to producing purely classical information rather than arbitrary quantum states. We present an unconditionally secure construction of UTE that achieves untelegraphable-indistinguishability security, together with natural multi-ciphertext and bounded collusion-resistant extensions, without requiring any additional assumptions. We also extend this to the unbounded case, assuming pseudo-random unitaries, yielding everlasting security. Furthermore, we derive results on UE using approaches from UTE in the following ways: first, we provide new lower bounds on UTE, which give new lower bounds on UE; second, we prove an asymptotic equivalence between UTE and UE in the regime where the number of adversaries in UE grows. These results suggest that UTE may provide a new path toward achieving a central open problem in the area: indistinguishability security for UE in the plain model.

In 2021, Masson, Sanso, and Zhang introduced the Bandersnatch curve associated to the BLS12-381 pairing-friendly curve, an elliptic curve designed for zero-knowledge proofs requiring circuits with a curve arithmetic. This type of curve is useful for privacy-preserving protocols, and more generally for succinct validity proof using pairing-based SNARKs. An embedded curve is defined over a field whose order is the group order of its associated curve. In this way, the pairing-friendly curve is used to express a zero-knowledge proof (such as a SNARK) of a statement taking place on the embedded curve. Contrary to the previous embedded curves (such as CØCØ, JubJub), Bandersnatch was built with the complex multiplication (CM) method, in order to ensure a very small discriminant (-8, whose magnitude is small), and thus efficient scalar multiplication thanks to the GLV technique. The algorithm provided by Masson, Sanso, and Zhang for searching this type of curves requires computation of Hilbert class polynomials, making the search of curve slow. It was not known whether Bandersnatch was an exceptional curve or whether comparable curves exist, of larger discriminants. This paper highlights the technicalities of the CM method already in use in the 90s to generate curve parameters of chosen order. This old technique allows revisiting the curve search of Bandersnatch, providing a dramatic speed-up improvement. This paper presents two algorithms: one to generate embedded elliptic curves of SNARK-friendly elliptic curves, with a variable discriminant; a second to generate families (parameterized by polynomials) with a fixed discriminant. When the (negative) discriminant is -3 modulo 4, it is possible to obtain a prime-order curve, and form a cycle. To illustrate this, we apply the technique first to generate more embedded curves like Bandersnatch with BLS12-381, such as a curve of discriminant -6673027, defining a plain twist-secure cycle. We also comment on the scarcity of Bandersnatch-like CM curves, and recall that with this generic algorithm, it is only a question of core-hours to find them. Second, we show the link between a paper of Ben Smith in 2015 and the work of Dai, Lin, Zhao, and Zhou in 2023, obtaining prime-order parameterized families of embedded curves of fixed discriminant, such as -3 for BLS and KSS18 curves. With KSS16 curves, the discriminant -4 is also possible (the curve has an even order). The technique can work with any KSS, Scott–Guillevic, Gasnier–Guillevic, or other fixed-discriminant parameterized family of pairing-friendly curves. This paper provides a more general point of view on embedded curves such as Bandersnatch, putting into perspective the works of Masson, Sanso, and Zhang, and Sanso and El Housni. The Python/SageMath scripts are available at https://gitlab.inria.fr/zk-curves/cm-embedded-curves/.

Function-hiding functional commitment schemes allow one party to commit to a private function f and later prove f(x)=y for public x and y without revealing additional information about the function. We construct efficient function-hiding functional commitment schemes for arithmetic circuits of bounded size that achieve proof sizes below 1.6 kB—over an order of magnitude smaller than previous constructions—while simultaneously reducing proving and verification times. We achieve these results by introducing a novel information-theoretic interactive proof system called Polynomial Interactive Oracle Proofs with Randomized Indexer (rPHPs). By compiling rPHPs with commit-and-prove zkSNARKs, we are able to leverage relaxed zero-knowledge notions for our building blocks. This approach eliminates the overhead of strict privacy requirements of prior work, directly translating into improved efficiency in both communication and computation.

Zero-knowledge proofs (ZKPs) are a fundamental building block in cryptography, enabling powerful privacy-preserving and verifiable computations. In the post-quantum era, hash-based ZKPs have emerged as a promising direction due to their conjectured resistance to quantum attacks, along with their simplicity and efficiency.

In this work, we introduce SmallWood, a hash-based polynomial commitment scheme (PCS) and zero-knowledge argument system optimized for relatively small instances. Building on the recent degree-enforcing commitment scheme (DECS) from the Threshold-Computation-in-the-Head (TCitH) framework, we refine its formalization and combine it with techniques from Brakedown. This results in a new hash-based PCS that is particularly efficient for polynomials of relatively small degree –typically up to $2^{16}$– outperforming existing approaches in this range.

Leveraging this new PCS, we design a hash-based zero-knowledge argument system that outperforms the state-of-the-art in terms of proof sizes for witness sizes ranging from $2^6$ to $2^{16}$. Additionally, we present exact zero-knowledge arguments for lattice-based problems using SmallWood, demonstrating highly competitive performance: our scheme yields proof sizes under 25 KB across a wide range of lattice parameters, including Kyber and Dilithium instances.

In this work, we study the hybrid key establishment protocol TutaCrypt as a concrete case of post-quantum cryptographic migration in practice. The protocol was developed by the end-to-end encrypted email provider Tuta and has been deployed to more than ten million users worldwide. We present the protocol in a form that enables rigorous cryptographic analysis and define two Bellare–Rogaway-style security models that precisely characterize the provided security guarantees. The two models capture that the security properties achieved in the pre-quantum setting are slightly stronger than in the post-quantum setting. We then give reduction-based security proofs that clarify under which assumptions the construction achieves security, and how its guarantees degrade if either the classical or the post-quantum component is compromised.

Our results illustrate how formally grounded cryptographic models can capture real-world migration strategies and hybrid deployments. Such analyses help to understand the security properties of deployed cryptographic systems and help move cryptographic migration from best practice toward principled, verifiable design.

Field trace evaluation has emerged as a powerful tool in fully homomorphic encryption, with broad applications ranging from bootstrapping algorithms to privacy-preserving protocols. Recent advances have significantly reduced its noise growth by combining tower-based evaluation strategies with rescaling operations. However, existing analyses rely on uniform noise bounds that fail to capture the actual noise behavior across different coefficients, leading to substantial gaps between theoretical estimates and empirical observations.

In this work, we present a refined algebraic analysis of trace evaluation over power-of-two cyclotomics that uncovers structured cancellation effects among noise coefficients induced by subsequent linear operators, in particular the trace mappings of subextensions. We show that, except for the constant term, the variance of each output noise coefficient depends on the 2-adic valuation of its index, yielding bounds that improve upon prior uniform estimates by a factor of $O(\log n)$ both for non-constant coefficients and after a subsequent plaintext-ciphertext multiplication, where $n$ is the ring degree. We further extend our analysis to two typical algorithmic applications of trace evaluation. For ciphertext packing, we derive a non-recursive formulation that admits a cleaner structure and slightly tighter noise estimates. For coefficient extraction, our coefficient-wise analysis improves upon prior uniform variance bounds by factors ranging from $\Theta(n)$ to $\Theta(n^2)$ for non-constant coefficients and by a factor of $O(n)$ after post-multiplication. Experimental results confirm that the observed noise variances follow the coefficient-wise pattern predicted by our analysis and demonstrate pronounced improvements over existing estimates, providing effective guidance for parameter selection and system configuration in practice.

Proxy re-encryption (PRE) allows a semi-trusted party (called a proxy) to transform ciphertexts under one user's public key into ciphertexts under another user's public key, without revealing any information about the underlying messages or the secret keys. On the other hand, post-quantum cryptography (PQC) is one of the most active areas, and in particular, many lattice-based PRE schemes have been proposed so far in the area of PQC. However, there is no post-quantum PRE satisfying security against adaptive chosen ciphertext attacks ($\mathsf{CCA}2$ security), while $\mathsf{CCA}2$ security is one of the most desirable security notions for PRE.

In this paper, we propose a group-action-based PRE scheme that achieves $\mathsf{CCA}2$ security for the first time. We give security proofs for our PRE in the random oracle model (ROM) and the quantum random oracle model (QROM). In particular, we can obtain the CSIDH-instantiation of this PRE scheme as the first post-quantum PRE. Our result contributes to the developments of post-quantum cryptography, and shows further potential of isogeny-based cryptography.

In this work, we present the first lattice-based construction of batched IBE in the standard model, whose security is proven under the succinct LWE assumption. Prior batched IBE schemes are only known either based on pairing-based assumptions or in the random oracle model. Moreover, our scheme is shown to be highly efficient, as the master public key, decryption key, and ciphertext are independent of the batch size B.

Technically, we mainly rely on an insightful observation: batched IBE can be obtained solely from Inner-Product Encryption (IPE). To satisfy the efficiency requirements of batched IBE, we require an IPE scheme that owns two important features: decomposable key generation and compact components. Finally, we show how to construct such an IPE scheme from the well-known BGG+14 IPE scheme via careful modification.

Privacy-preserving machine learning and encrypted statistics increasingly require evaluating long chains of matrix products directly on ciphertexts. In the CKKS homomorphic encryption scheme, however, every multiplication amplifies noise and enlarges ciphertexts, so the available precision budget is exhausted after only a few products. This work establishes $\mathsf{cFHE}$ (compressed FHE), a unified analytical and empirical framework that integrates low-rank matrix factorization techniques into the CKKS homomorphic encryption scheme. Its central idea is a co-design: instead of tuning the low-rank approximation and the cryptographic parameters in isolation, $\mathsf{cFHE}$ balances the two error sources against each other so that neither wastes precision. Theoretical bounds are derived for the accumulation of relative error across sequences of factorized matrices, leading to an explicit expression for the attainable computation depth as a function of target accuracy, norm amplification behavior, and per-layer approximation quality. Extensions to tree-based evaluation structures are also formulated, allowing depth to scale logarithmically with the number of factors.

Concretely, this co-design is realized as a precision-balancing model that, for a target accuracy, automatically selects the CKKS parameters: the polynomial modulus degree, the modulus chain, and the scaling factor.

Experimental evaluations demonstrate that encrypted low-rank matrix multiplications achieve both significant runtime improvements and reduction of ciphertext sizes over direct or tree-based encrypted multiplications while maintaining the prescribed accuracy. $\mathsf{cFHE}$ is agnostic to other CKKS optimizations and can be combined with them for further gains.

The VOX signature scheme is a multivariate signature scheme which was submitted to the Round 1 Additional Digital Signature Schemes NIST process. VOX relies on the Hat Plus perturbation and the Quotient-Ring transform (QR). We formalize a dimension criterion enabling the direct attack to be used as a key recovery attack against UOV schemes. This enables a practical cryptanalysis of the Round 1 VOX parameters. Next, we show that some of the alternative parameters proposed for VOX after attacks on the Round 1 submission are still vulnerable. More precisely, these parameters were chosen to defeat an attack of Furue and Ikematsu in the field extension defined by the QR parameter. We observe that one may use a smaller field extension of any degree dividing the QR parameter, in which case the attacks apply again. These attacks are relevant for a subset of the parameter sets proposed for VOX: I, Ic, III, IIIa, V, Vb. In particular, we apply the subfield framework to our previous dimension criterion for the direct attack. We estimate the cost of our attack on these parameter sets and find costs of at most 2^67 gates, and significantly lower in most cases. In practice on a commercial laptop, our attack requires 0.3s, 1.35s, 0.56s for parameter sets I, III, V for VOX, and 56.7s, 6.11s for the alternative parameter sets IIIa, Vb. Our analysis also improves the cryptanalysis of some alternative parameters proposed by Guo and Ding, and of the “Minus” variant of VOX.

At CRYPTO 2019, A. Gohr introduced Neural Differential Cryptanalysis and used deep learning to improve the state of the art in cryptanalysis of 11-round SPECK32. As of February 2025, Gohr’s article has been cited 238 times on Google Scholar. The variety of targeted cryptographic primitives, techniques, settings, and evaluation methodologies that appear in these follow-up works provides a basis for a careful survey, which we provide in this paper. More specifically, we propose a taxonomy of these 238 publications and systematically review the 71 papers focusing on neural differential distinguishers, pointing out promising directions and recent advances in explainability and key-recovery attacks. We then highlight future challenges in the field, particularly the need for improved comparability of neural distinguishers and advancements in scaling. This holistic survey helps researchers and engineers to identify the leading neural differential attacks, compare their performance, and highlight the outstanding open problems in AI-assisted cryptanalysis.

CSIDH is an isogeny-based Non-Interactive Key Exchange (NIKE) proposed at ASIACRYPT'18. In this work, we present the first masked version of CSIDH and, in fact, any isogeny-based scheme. We develop gadgets to efficiently mask all arithmetics in the underlying finite field and prove them secure in the $d$-probing model. In particular, we develop new gadgets for the Montgomery ladder using the fact that projective values already represent a multiplicative sharing in two variables. The technique (dubbed quotient masking) might be of independent interest. Lastly, we provide an efficient implementation based on High-Security CSIDH (Communications in Cryptology 2024). We show that the relative computational overhead of masking the latter—compared to other state-of-the-art CSIDH implementations—is similar to other masked implementations of post-quantum cryptography primitives.

We prove that the supersingular \(\ell\)-isogeny path problem and the endomorphism ring problem are equivalent via polynomial-time reductions given access to a factoring oracle. Prior work related the endomorphism ring problem to the general isogeny path problem, but the \(\ell\)-isogeny path case remained open unconditionally. We show that a factoring oracle suffices to solve the quaternion path problem of Kohel, Lauter, Petit, and Tignol, replacing previous heuristic or GRH-based assumptions in the core reduction. Combined with Shor's factoring algorithm, this gives quantum polynomial-time equivalences between \(\ell\)-isogeny path and endomorphism ring, with substantially lower polynomial degree, whereas the original reduction incurs a polynomial overhead of impractically high degree.

We give an explicit algorithm to evaluate an efficiently computable cubic genus invariant on ideal class groups of non-maximal imaginary quadratic orders in $K=\mathbb{Q}(\sqrt{-3})$. Concretely, we consider the order $\mathcal{O}_{\Delta}$ of discriminant $\Delta=-3f^{2}$ with conductor $f>1$. We assume that $f$ is known as an integer, but its prime factorization is not; instead, we are given only a single nontrivial factor $a\mid f$ arising in Dedekind's parametrization of these discriminants (so that the complementary factor needed in the cubic-residuosity test can be recovered as an integer from $(f,a)$, without factoring it).

Under these assumptions, our method computes a nontrivial two-valued genus invariant on the ideal class group of $\mathcal{O}_{\Delta}$, taking values $+1$ and $-1$, whose $+1$-fiber is a distinguished index-$3$ subgroup singled out by classical work of Dedekind; equivalently, the invariant takes the value $+1$ if and only if the ideal class lies in that subgroup.

The construction is inspired by work of Dedekind and Shanks on index-$3$ subgroups of quadratic form class groups and their characterization via cubic residuosity of primes represented by form classes. We prove correctness and analyze the running time of the resulting evaluation procedure, and we validate the approach with a SageMath implementation. As an application, we obtain an explicit Decisional Diffie–Hellman (DDH) distinguisher in cyclic subgroups of the class group generated by an element outside the distinguished index-$3$ subgroup, under the same partial-factorization assumption.

The syndrome decoding problem (SDP) for random linear codes is a fundamental NP‑hard problem in coding theory, forming the security foundation for many code‑based post‑quantum cryptographic schemes. Information Set Decoding (ISD) algorithms, especially those using the representation technique (e.g., MMT and BJMM), and dual decoding are important methods for solving SDP. Esser et al. presented an evaluation framework for the ISD algorithms and formed a helpful open-source Syndrome Decoding Estimator (SDE), which is used to estimate the security of concrete parameters for code-based schemes. In this work, we present two improvements to the analysis of SDP. First, we provide a refined concrete complexity analysis for BJMM in SDE without altering the BJMM algorithm or its asymptotic complexity analysis. In particular, we improve the concrete estimated number of iterations in concrete time and space estimation. We achieve this improvement by distinguishing three key lists in the tree-based enumeration process. Experimental results confirm that our estimation is more precise. As an application, we obtain an updated time and space estimate for Classic McEliece. Second, we propose preprocessing variants of advanced ISD algorithms and dual decoding algorithms, enabling a trade-off between offline storage and online computation. This approach is advantageous in multi-instance attack settings to reduce amortized complexity. We also emphasize the limitations of the preprocessing variants in practice and propose practical countermeasures.

Key ranking is a critical subject for evaluators since it measures the remaining complexity after a side-channel attack without the need to implement the key enumeration algorithm. This paper proposes a novel method based on the knapsack counting problem. While the existing literature proposes a solution of this problem with an algorithm originating from linear programming, we propose a new computation inspired by a recent work in statistical physics. The partition function of the knapsack problem, which is equivalent to the key rank, is derived with an analytic expression. This is used to prove the mathematical equivalence between the knapsack and histogram-based methods. In addition, a saddle-point approximation of the key rank is computed from the analytic expression. A very simple mathematical formula is derived. Simulation results show that the approximation is very tight. In addition, the execution time of the approximation is fast and linear in the key size, making it suitable for scaling to very large keys.

With the recent standardisation of several post-quantum cryptographic (PQC) algorithms, there is an increased focus within the hardware research community to investigate efficient accelerator designs. However, it is difficult to determine whether the reported results are directly comparable due to differences in hardware prototyping platforms, integration contexts, and evaluation methodologies. This creates a gap between reported performance claims and their interpretability across works.

In this paper, we survey the reported evaluation metrics across 50 PQC accelerators. We identify a reporting asymmetry across the literature in the evaluations of cryptographic hardware, limiting fair comparison and obscuring system-level trade-offs. To resolve this, we design a homogeneous, FPGA-based benchmarking framework to appropriately evaluate cryptographic hardware. We replicate five recent accelerators as a case study in the same RISC-V system-on-chip environment to fairly compare their design approaches and compromises.

Isogeny-based cryptography relies its security on the hardness of the supersingular isogeny problem: finding an isogeny between two supersingular curves defined over a quadratic field extension of Fₚ.

The Delfs-Galbraith algorithm is one of the most efficient procedures for solving the supersingular isogeny problem with a time complexity of Õ(√p) operations. The bottleneck of the Delfs-Galbraith algorithm is the so-called subfield curve search (i.e., finding an isogenous supersingular elliptic curve defined over the prime field), which determines the time complexity of the aforementioned algorithm.

Given that, for efficiency, most recent isogeny-based constructions propose using finite fields with field characteristics equal to p = 2ᵃ • f - 1 for some positive integers a and f. This work primarily focuses on primes of that particular form and presents two heuristic algorithms for finding subfield curves with a time complexity of O(√p) operations and a memory complexity polynomial in log₂p. We show how to adapt these algorithms to primes of the form p = dᵃ • f - 1 with d being a small integer, with a particular focus on d=12. We provide concrete time-complexity bounds for both kinds of primes p = 2ᵃ • f - 1 and p = (12)ᵃ • f - 1. Our algorithms exploit the existence of large dᵃ-torsion points and extend the subfield root detection algorithm of Corte-Real Santos, Costello, and Shi (Crypto, 2022) to a projective scenario where one can work with the curve coefficients instead of their explicit j-invariants.

We highlight that our algorithms easily extend to primes of the form p = 2ᵃ • f + 1, p = 4 • d₁ • dₙ ••• dₙ - 1 for small odd primes dᵢ's, and primes such that p - 1 and p + 1 are B-smooth for some integer B.

The Large Norm attacks of Ducas-Espitau-Postlethwaite (CRYPTO 2023) on the ISIS problem showed that small moduli q can be exploited to recover short solutions, as applied to Falcon and Mitaka. Two gaps remained: the cost model oversimplifies the BDGL sieve, ignoring how sieve-output lengths are distributed and treating two dependent probabilistic events as independent, which overestimates the attack cost; and the analysis is restricted to the l2 norm and was not extended to ISIS-infinity, which underlies Dilithium-type systems.

In this work, we address both. First, we sharpen the cost model by integrating the success probability over the full sieve length distribution and by using a joint rather than an approximate probability, reusing the existing theta-convolution framework. This yields an about 11 times cheaper cost model on Falcon-256 and forges a Mitaka-512 signature in about 4.5 seconds at a higher success rate. Second, we introduce a closed-form l-infinity Z-shape attack against Dilithium-type ISIS-infinity at small-to-moderate modulus, which succeeds in under 1.6 seconds across three scaled-down presets.

Neural differential distinguishers are widely used to evaluate round-reduced symmetric primitives, yet it remains unclear whether performance improvements arise primarily from larger neural models or from more informative input representations. We present a systematic study of this trade-off using ciphertext-only features under a chosen-plaintext differential sampling model on four lightweight block ciphers: the SPN ciphers GIFT-64, RECTANGLE-64, and PRESENT-64, together with the ARX cipher SPECK-64/128. We compare a standard single-difference representation, denoted R1, with a multi-difference matrix representation, denoted R2, and evaluate three common model families, namely MLP, CNN, and ResNet, under a fixed and uniform training protocol. Our results show that, in this setting, representation choice is a more consistent driver of performance than architecture choice. Across the main experiments, R2 generally yields stronger distinguishers than R1, whereas deeper models often provide only limited additional gains and can overfit in harder regimes. This conclusion is reinforced by supplementary experiments showing that the representation gap remains visible under an alternative shared difference set, persists for a simple linear baseline, and often survives under an equal-ciphertext budget. The results support the view that, for neural distinguishers in this setting, designing information-dense ciphertext representations can matter at least as much as scaling model capacity, and often more.

In a TLS session, the user is granted access solely to the encryption and decryption oracles, $\mathcal{E}(K, \cdot)$ and $\mathcal{D}(K, \cdot)$, of a symmetric-key encryption scheme, which are treated as black boxes. Here, $\mathcal{E}$ denotes the encryption algorithm, $\mathcal{D}$ the decryption algorithm, and $K$ the secret key. In this paper, by utilizing any secure symmetric-key encryption scheme as a black-box primitive, we demonstrate a method for constructing a symmetric-key encryption scheme that remains secure even in the presence of partial key leakage. This approach can, for example, enhance the security of TLS sessions.

Our construction employs the All-Or-Nothing Transform (AONT) in the pre-processing phase. Therefore we provide a tighter security analysis of existing AONT constructions, and establish a lower bound on their security. Finally we propose a new AONT construction that achieves security beyond this lower bound.

PRISM (PKC25) is a hash-and-sign signature scheme whose security relies on the hardness of computing large-prime-degree isogenies originating from a curve of unknown endomorphism ring. In PRISM, the degree of such isogenies is obtained by hashing messages onto a set of large odd integers that pass a primality test.

In this work, we investigate the impact of the choice of primality test on the security of PRISM. We first show that when a weak primality test is used, the assumption underlying the security proof in the standard model does not hold. We then extend our analysis to the assumption used in the security proof in the (quantum) random oracle model. In this setting, we argue that the Miller-Rabin test suffices and estimate the minimal number of iterations required for PRISM to achieve the desired security level, thus minimising signing costs.

Multi-party matrix invertibility testing over finite fields of small order or characteristic is a pivotal operation for thresholdizing multivariate quadratic (MQ) signature schemes. However, achieving perfect privacy in a constant number of rounds remains a challenge: existing solutions either suffer from information leakage, failing to provide perfect privacy, or require high computational and communication overhead, in particular, when p <= n, where p and n denote the characteristic of the underlying field and the matrix size, respectively.

To address this limitation, we propose two protocols for multi-party testing of matrix invertibility. The first protocol extends the Cramer-Damgård protocol to fields of small order by employing the field lifting technique. The second protocol is based on multi-party computation of the Samuelson-Berkowitz algorithm, specifically designed for fields of small characteristic. Both protocols are formalized in the arithmetic black-box (ABB) model with Shamir's secret sharing scheme.

We show that both protocols achieve perfect privacy while allowing for a tradeoff between input-independent offline rounds and input-dependent online rounds, where the input corresponds to the shared matrices. Specifically, the first protocol runs in 7 offline rounds with communication complexity O(Nn^4) and in 3 online rounds with communication complexity O(n^4), and the second protocol runs in 3 offline rounds with communication complexity O(n^4) and in 9 online rounds with communication complexity O(n^4), where n is the matrix size and N is the number of parties.

While a well-established fact for NTRU, it is widely believed that other lattice-based primitives such as MLWE and NTWE do not suffer from overstretching, a phenomenon where discovering a lattice vector strictly longer than the secret key(s) in a dense sublattice spanned by the secrets results in a substantially easier attack than the conventional secret key recovery attack. Nevertheless, MLWE and NTWE, similarly to NTRU, yield q-ary lattices that have a relatively dense sublattice spanned by the secrets, which makes it possible that an overstretched regime could exist for all three of the above-mentioned primitives. We generalise and apply the methodology developed in the work of Ducas and van Woerden in 2021 to MLWE and NTWE to investigate the possibility of an overstretched regime. We discover that any lattice with this structure is expected to suffer from the dense sublattice attack. For MLWE, the asymptotic fatigue point is predicted to be so large that it is not of practical concern. For NTWE, we predict it may be of practical concern and demonstrate the attack experimentally, providing the first evidence for a dense sublattice attack on NTWE.

We propose a novel multi-server threshold oblivious retrieval system (ThORY). Our construction extends DORY (a two-server non-threshold oblivious retrieval system proposed in USENIX OSDI 2020) to support arbitrary threshold access structures. The technical centrepiece of ThORY is threshold function secret sharing (TFSS) – an extension of traditional FSS that allows the key to be secret-shared across multiple servers following any arbitrary threshold access structure. We present novel constructions of TFSS based on either purely symmetric-key cryptoprimitives, or any seed-homomorphic pseudorandom generator (for the latter, we present two concrete instantiations from standard group-theoretic assumptions and plausibly quantum-safe lattice-based assumptions). Leveraging TFSS, ThORY achieves leakage-free keyword search and document identifier retrieval under a (t,p)-threshold model, hiding access, search, and volume patterns against any adversary corrupting fewer than t servers. We analyse and evaluate the security and performance of end-to-end implementations of ThORY based on each of these TFSS constructions. Our experiments demonstrate that ThORY scales efficiently with threshold size, outperforming state-of-the-art literature in query latency over large databases.

Password-based authentication remains widespread, and large-scale sets of leaked hashes enable practical offline brute-force attacks. Multi-target attacks, which check candidates against large sets of hashes simultaneously, are particularly effective. Understanding the capabilities of low-cost platforms for such attacks is important to assess real-world password security risks.

Therefore, we present BF2, a modular and scalable FPGA–CPU framework that accelerates multi-target password recovery. BF2 combines a password-candidate generator, a fully-pipelined NT hash core, a Bloom filter stage to filter non-matching candidates, and a multi-threaded host-side component that performs exact membership check using a perfect hash function. We implement BF2 on the low-cost, $199 NiteFury II board. With 16 parallel pipelines running at a 100 MHz clock frequency, our FPGA implementation generates 1.6×10^9 hashes/s. In our experiments, BF2 demonstrates up to 7.5× higher throughput than John the Ripper, and reduces power consumption by as much as 90% compared to Hashcat on an RTX 5000.

PARI is a recent SNARK based on equifficient polynomial commitments, giving an exceptionally compact proof of just 1280 bits over the BLS12-381 curve, which is the smallest among all the known SNARKs in the literature. However, PARI does not achieve the zero-knowledge property; despite being very efficient, it is therefore less suitable for applications requiring witness privacy. In this work, we propose a zero-knowledge extension of PARI making it ideal for privacy-centric applications yet keeping the proof size compact. We prove perfect completeness, perfect zero-knowledge in the random-oracle model with challenge space $\mathbb{F}\setminus K$, and knowledge soundness in the algebraic group model with random oracles under the SDH assumption.

This work describes a digital signature scheme constructed from a zero-knowledge proof of knowledge of a pre-image of the Rescue Prime Optimized (RPO) permutation. The proof of knowledge is instantiated using the DEEP-ALI interactive oracle proof and made non-interactive via the Ben-Sasson–Chiesa–Spooner (BCS) transformation in the random oracle model. The resulting construction yields a signature scheme with transparent setup. Our design is motivated by recursive zero-knowledge applications, in which signature verification must itself be efficiently provable inside larger proof systems. To this end, the choice of the RPO permutation, the use of a simple algebraic intermediate representation (AIR), and working over the Goldilocks field are made with the goal of enabling efficient recursive verification and aggregation. The implementation of the scheme computes signatures in 4.6–7.2 ms and verifies them in 0.46–0.52 ms when the BCS transform is implemented with Blake3. When the BCS transform is instead instantiated with the RPO permutation itself, the configuration required when signature verification is to be proven recursively inside a proof system, signing takes 20.9–30.4 ms with Metal acceleration and 59.2–229.2 ms on CPU, while verification takes 5.09–5.79 ms. We validate the recursion-friendliness claim end to end by proving one signature verification inside the Miden zkVM and reporting the recursive prover time and proof size. These speeds are obtained with parameters achieving 113 or 122 bits of average-case security, depending on the chosen preset, against adversaries that can obtain up to \( 2^{64} \) signatures.

The idea of computing on encrypted data without decryption dates back to the notion of privacy homomorphisms introduced by Rivest, Adleman, and Dertouzos (1978). Their proposals built using the elegant structure of Chinese Remainder Theorem (CRT), were later shown to be insecure under simple known-plaintext attacks. Subsequent CRT-based fully homomorphic encryption (FHE) over the integers addresses this algebraic transparency by injecting noise and basing security on approximate common divisor–type assumptions, but the resulting designs are burdened by large public keys and costly ciphertext refresh procedures.

In this work, we develop a new CRT-based FHE scheme whose security relies on the Ring-LWE (RLWE) hardness assumption. For this purpose, we introduce the CRT-RLWE problem. We show that the problem is at least as hard as the RLWE, thereby positioning our construction within the established post-quantum security landscape of RLWE-based cryptography. Our scheme retains an explicit CRT embedding, separating a message component modulo a prime-power plaintext modulus and an auxiliary CRT component, while using RLWE-style key and ring arithmetic for compactness and efficiency.

Finally, we make it fully homomorphic by using a new bootstrapping procedure, that adopts the recryption paradigm for BGV/BFV schemes utilizing the linear transformation and digit extraction techniques.

Softmax is widely used in deep learning to map some representation to a probability distribution. As it is based on the exponential function, which is relatively expensive in multi-party computation, Mohassel and Zhang (Oakland, 2017) proposed a simpler replacement based on ReLU (the maximum of the input and zero) to be used in secure computation. Later works (e.g., Wagh et al., PETS 2019 and 2021) used the softmax replacement not for computing the output probability distribution but for approximating the gradient in backpropagation. In this work, we analyze the two uses of the replacement and compare them to softmax, both in terms of accuracy and cost in multi-party computation. We found that the replacement only provides a significant speed-up for a one-layer network, while it always reduces accuracy, sometimes significantly. Thus, we conclude that its usefulness is limited, and one should use the original softmax function instead. We also present a novel protocol for secure exponentiation that reduces communication up to fourfold while preserving accuracy when used for softmax.

At EUROCRYPT 2024, Flórez-Gutiérrez and Todo introduced the puncturing technique for linear key recovery attacks. Puncturing works by modifying the map which evaluates the linear approximation as a function of the plaintext, ciphertext and key, by setting carefully chosen coordinates of its Fourier transform to zero. These modifications are intended to reduce the time complexity of the attack at the cost of an increase in data complexity. In this note, we revisit the model which is used to estimate the data complexity, clarify some of its underlying assumptions, and improve its accuracy. This leads to a revision of the cost estimates for several applications of puncturing in the literature, most notably for attacks whose data complexity is close to the full codebook.