International Association
for Cryptologic Research

Recently, Hövelmanns, Hülsing, and Majenz introduced a security notion called Find Failing Plaintext – Non Generic (FFP-NG), which captures the ability of an adversary to find decryption failures by making non-trivial use of the public key. A first analysis of this property for lattice-based schemes was presented by Majenz and Sisinni, who showed that the Learning With Errors (LWE) problem reduces to breaking the FFP-NG security of the PVW scheme with discrete Gaussian noise. In this work, we generalize their result by analysing the FFP-NG security of widely used schemes based on Ring-LWE and Module-LWE. To keep our analysis as general as possible, we consider a family of subgaussian distributions that includes, among others, discrete Gaussians and centered binomials.

Key-dependent attacks are effective only for specific weak-key classes, limiting their practical impact. We present a generic statistical framework that combines multiple key-dependent distinguishers into universal attacks covering the full key space. Using log-likelihood ratio statistics, our framework tests the secret key against multiple weak-key distinguishers, aggregates their evidence to determine whether the key is weak or strong for each distinguisher, and exploits this classification to reduce the effective key entropy for key recovery.

We apply this to Orthros-PRF, a sum-of-permutations (SoP) design where any differential-based distinguisher holds only for a fraction of keys. This yields the first universal 8-round differential-linear (DL) key-recovery attack with median time complexity $2^{119.58}$, whereas prior work reached at most 7 rounds in the weak-key setting. To discover the required distinguishers, we extend the open-source S-box Analyzer tool with MILP support for deterministic propagation and develop a model integrating distinguisher search with key recovery. This enables automated discovery of multidimensional DL distinguishers covering up to 10 rounds in each Orthros branch, improving prior work by 4 rounds.

Our results demonstrate that statistical aggregation of multiple weak-key distinguishers enables effective universal cryptanalysis. Our framework is generic and is applicable to other primitives with multiple identifiable weak-key classes.

Anonymous credentials enable unlinkable and privacy-preserving user authentication. To ensure non-transferability of credentials among corrupt users, they can additionally be device-bound. Therein, a credential is tied to a key protected by a secure element (SE), usually a hardware component, and any presentation of the credential requires a fresh contribution of the SE. Interestingly, despite being a fundamental aspect of user credentials, device binding for anonymous credentials is relatively unstudied. Existing constructions either require multiple calls to the SE, or need the SE to keep a credential-specific state -- violating core design principles of shielded SEs. Further, constructions that are compatible with the most mature credential scheme BBS rely on the honesty of the SE for privacy, which is hard to vet given that SEs are black-box components. In this work, we thoroughly study and solve the problem of device-bound anonymous credentials (DBACs). We model DBACs to ensure the unforgeability and non-transferability of credentials, and to guarantee user privacy at the same time. Our definitions cover a range of SE trust levels, including the case of a subverted or fully corrupted SE. We also define blind DBACs, in which the SE learns nothing about the credential presentations it helped compute. This targets the design of a remote, cloud-based SE which is a deployment model considered for the EU Digital Identity (EUDI) wallet to address the fact that most user phones are not equipped with a sufficiently secure SE. Finally, we present three simple and round-optimal constructions for device binding of BBS credentials, and prove their security in the AGM+ROM and privacy unconditionally. The SE therein is extremely lightweight: it only has to compute a BLS or Schnorr signature in a single call. We also give the BLS-based construction in a blind variant, yielding the first protocol that enables privacy-preserving device binding for anonymous credentials when being used with a remote SE.

Pseudorandom generators (PRGs) are a foundational primitive in classical cryptography, underpinning a wide range of constructions. In the quantum setting, pseudorandom quantum states (PRSs) were proposed as a potentially weaker assumption that might serve as a substitute for PRGs in cryptographic applications. Two primary size regimes of PRSs have been studied: logarithmic-size and linear-size. Interestingly, logarithmic PRSs have led to powerful cryptographic applications, such as digital signatures and quantum public-key encryption, that have not been realized from their linear counterparts. However, PRGs have only been black-box separated from linear PRSs, leaving open the fundamental question of whether PRGs are also separated from logarithmic PRSs.

In this work, we resolve this open problem. We establish a quantum black-box separation between (quantum-evaluable) PRGs and PRSs of either size regime. Specifically, we construct a unitary quantum oracle with inverse access relative to which no black-box construction of PRG from (logarithmic or linear) PRS exists. As a direct corollary, we obtain separations between PRGs and several primitives implied by logarithmic PRSs, including digital signatures and quantum public-key encryption.

The FRI protocol (ICALP '18) is one of the most influential and widely deployed building blocks at the core of modern SNARK systems. While its concrete security is well understood, existing security proofs are intricate and technically complex.

In this work, we present a significantly simpler security analysis of FRI, in particular its round-by-round soundness. Our approach is more accessible to a broader audience, lowering the barrier to understanding this fundamental protocol. Furthermore, the simplicity of our analysis may pave the way for future formal verification efforts of modern SNARK constructions.

Since the work of Chaum in ’82, the problem of designing secure blind signature protocols for existing signature schemes has been of great interest. In particular, when considering Schnorr signatures, nowadays used in Bitcoin, designing corresponding efficient and secure blind signatures is very challenging in light of the ROS attack [BLL+21] (Eurocrypt’21), which affected all previous efficient constructions. Currently, the main positive result about concurrent-secure blind Schnorr signatures is the one of Fuchsbauer and Wolf [FW24] (Eurocrypt’24). Their construction, is quite demanding, indeed it requires trusted parameters, non-interactive zero-knowledge arguments and CPA-secure public-key encryption. Moreover, it is proven secure under a game-based definition only, is limited to computational blindness and is vulnerable to harvest now “link” later quantum attacks. Nicely, their construction is also a predicate blind signature (PBS) scheme, allowing signers to have some partial control on the content of the blindly signed message. In this work, we show neat improvements to the state-of-the-art presenting a new construction for concurrent-secure blind Schnorr signatures that relies on milder/reduced cryptographic assumptions, enjoys statistical blindness, replaces the problematic trusted setup with a non-programmable random oracle, and satisfies also a one-sided simulation-based property providing deniability guarantees to users. Finally, we show that the above improvements come at a very modest additional cost, achieving essentially the same performance of [FW24].

The post-quantum signature scheme Falcon is an attractive scheme for constrained devices due to its compactness and verification performance. However, it relies on floating-point arithmetic for signature generation, which - alongside physical security concerns - introduces two additional drawbacks:

Firstly, if implemented using the standard double-precision format, Falcon does not satisfy the formally proven error bounds required for a secure Gaussian sampler implementation. Although no practical attacks exploiting this limitation are currently known, it does give future attack concerns. Secondly, when looking at constrained devices, 32-bit constrained devices can lack hardware support for high-precision floating-point arithmetic and its use introduces significant performance overhead, as it must be emulated using integers.

In this work we present a novel method to address these limitations: We show that Falcon can be implemented using $\textit{single-precision}$ floating-point numbers. Our proposed method uses Triple-Word Floating-Point (TW) arithmetic and achieves a precision of at least 72 bits, compared to the 53 bits of double-precision floating-point arithmetic. We show our implementation achieves error bounds that meet the formal security requirements for a secure Gaussian sampler implementation, while maintaining other security guarantees. This way, Falcon can run on constrained devices equipped only with a single-precision Floating-Point Unit (FPU) without the need for integer emulation.

We demonstrate the feasibility of our approach on the Nucleo-L4R5ZI board, which features a Cortex-M4F processor enabled with a single-precision FPU. More precisely, we show the cost of increasing the precision of Falcon in this way only increases the computational effort by a factor of approximately 1.84 compared to the CPU cycles required for an implementation using emulated double-precision arithmetic via integers.

Although the lattice-estimator predicts that Learning with Errors instances having small and very sparse secrets can be broken by hybrid attacks with modest computational resources, no efficient open-source implementation of these attacks exists. This work implements the so-called Guess + Verify attack (G+V) analysed by Albrecht et al. (SAC'19), containing three improvements: (1) cuBLASter, a GPU-based implementation of the lattice basis reduction software BLASter by Ducas et al. (ASIACRYPT'25); (2) a dimension reduction technique for the BDD instance; and (3) a batched variant of Babai’s Nearest Plane algorithm.

On bases of dimension 512 and above, cuBLASter outperforms BLASter. We also integrate the GPU implementation of the General Sieve Kernel by Ducas et al. (EUROCRYPT'21) into cuBLASter’s BKZ framework.

Running G+V on the benchmark instances by Wenger et al. (IEEE SP'25), we show that G+V achieves significantly higher success rates than the Cool&Cruel attack (C+C) by Nolte et al. (AFRICACRYPT'24) on almost all instances, and G+V's average CPU and GPU utilization is substantially lower than the minimum reported by C+C.

Indistinguishability Obfuscation (iO) renders indistinguishable any pair of same-sized and functionally identical circuits. Since its introduction by Barak et al. (Crypto ’01), iO has become the holy grail of modern cryptography due to the myriad of applications it enables. Despite several theoretical constructions (including recent breakthrough results from well-studied assumptions), practically efficient frameworks for iO have remained out of reach. In this paper, we formally introduce the notion of Hardware-based indistinguishability obfuscation (HiO) with an aim to make iO practical. Further, we present a novel framework called Hardware-based Circuit Obfuscation from Data Encryption (HardCODE) for realizing highly efficient HiO.

Given a simple tamper-proof hardware to store a fixed size secret key, our proposed HardCODE framework yields a provably secure hardware module that achieves iO for all poly-sized circuits, while additionally relying on any one-way function and certain (heuristic but widely studied) assumptions on substitution-permutation networks (used extensively in the design of secure block ciphers). We practically instantiate HardCODE from widely deployed realizations of a simple HSM (Hardware Security Module), and the substitution-permutation network underlying the PRESENT block cipher (an ISO standard for lightweight cryptography). We then use this instance of HardCODE to obfuscate, without loss of generality, the C-17 circuit of the ISCAS-85 benchmark suite, while incurring very small practical overheads. To the best of our knowledge, this constitutes the first practical demonstration of iO.

NTRU is one of the most extensively studied lattice-based cryptographic schemes and is widely regarded as a strong candidate for post-quantum security. The most effective attacks on NTRU are lattice-based or lattice-related, which naturally guide the choice of parameters to achieve the desired security levels. In 1997, Hoffstein and Silverman proposed a variant of NTRU based on a noncommutative algebraic structure, claiming that it would mitigate lattice attacks. However, their scheme was later shown to be vulnerable to an algebraic attack by Coppersmith. Although several subsequent attempts have been made in the literature to develop noncommutative variants of NTRU, most of these designs have either been shown to be vulnerable to algebraic attacks or have failed to directly address lattice-based attacks.

In this work, we revisit the problem of constructing a noncommutative analog of NTRU that offers stronger resistance against direct lattice attacks. Firstly, we conceptualize the problem by introducing an almost unstructured variant, and then refine this idea towards a more compact instantiation, culminating in a fully structured construction defined over the group ring of the dihedral group. Our proposal may be viewed as a follow-up to the early noncommutative construction of Hoffstein and Silverman.

We further provide a complete reference implementation of the structured construction under two proposed parameter sets, Plausible and Paranoid, demonstrating both the efficiency and compactness of our scheme in comparison with NTRU-HPS and the state-of-the-art non-commutative NTRU variant.

As the Hamming Quasi-Cyclic (HQC) cryptosystem was recently selected by NIST for standardization, a thorough evaluation of its implementation security is critical before its widespread deployment. This paper presents single-trace side-channel attacks that recover the full long-term secret key of HQC, experimentally evaluated on a protected Cortex-M4 implementation. We introduce two distinct attacks that significantly advance the state of the art: a passive attack that uniquely models key recovery as a moderate-density parity-check (MDPC) decoding problem from a single valid ciphertext, and an active chosen-ciphertext attack employing a new probing strategy on a linear combination of secret key components for significantly improved efficiency. Both attacks are enabled by a new information set decoding (ISD) variant that exploits soft side-channel information, a contribution of broader importance to code-based cryptography. Our experiments show that a single trace suffices for full key recovery under realistic conditions, effectively defeating countermeasures such as codeword masking for the first time. We also show that several existing defenses are ineffective against the new attacks.

In NDSS 2024, Yu~et al. proposed AAKA, an Anonymous Authentication and Key Agreement scheme designed to protect users' privacy from mobile tracking by Mobile Network Operators (MNOs). AAKA aims to provide both anti-tracking privacy and traceability (lawful de-anonymization), allowing subscribers to access the network via anonymous proofs while enabling a Law Enforcement Agency (LEA) to trace the real identity if misbehaviors are detected. However, we identify that the AAKA scheme in NDSS 2024 is insecure since the subscriber's identity is exposed within the protocol, thereby failing to achieve the claimed privacy and traceability.

Building on the repair of AAKA, we propose AAKA+, Anonymous Authentication and Key Agreement with Verifier-Local Revocation, a new mobile authentication scheme, to ensure privacy against mobile tracking. In addition to the privacy and traceability introduced in NDSS 2024, AAKA+ additionally allows the MNO to immediately assert whether the associated subscriber has been traced and revoked upon receiving an anonymous proof. We formally define the syntax and the security model of AAKA+ and propose two concrete schemes, AAKA+BB and AAKA+PS, based on the Boneh-Boyen signature and the Pointcheval-Sanders signature schemes, respectively. Both AAKA+BB and AAKA+PS are pairing-free on the user equipment side and compatible with existing cellular infrastructure. Experimental results show that our schemes are practical, with anonymous proof generation taking approximately 18 milliseconds for a constrained device.

The growing need for secure computation has spurred interest in cryptographic techniques that operate on encrypted data without revealing its content. Fully Homomorphic Encryption (FHE), especially LWE-based schemes, enables such processing while preserving confidentiality. Decentralized computing offers scalable resources without requiring in-house servers, but it relies heavily on the confidentiality guarantees of underlying schemes. While many existing protocols successfully protect input privacy, function confidentiality remains a largely overlooked but crucial aspect of secure delegated computation.

In this work, we present a novel Oblivious Universal Function (OUF) scheme that enables a client to outsource computation of an arbitrary function to an untrusted server while hiding both the input data and the function being applied. Our construction leverages LWE-based FHE and a virtual-tape evaluation model to support composable, non-interactive, and reusable function execution. Crucially, the server remains oblivious not only to the encrypted inputs but also to the structure, type, and identity of the function it is executing. OUF thus bridges the gap between theoretical privacy guarantees and practical secure computation in decentralized environments.

In a secret sharing scheme for a monotone access structure $\mathcal{A}:\{0,1\}^n\rightarrow \{0,1\}$, a dealer can share a secret $s$ to $n$ parties such that any authorized subset of parties $A\in\mathcal{A}$ can recover $s$ while all other subsets learn nothing about $s$. In this work, we study fully anonymous secret sharing (FASS), which strengthens standard secret sharing by requiring the following properties:

- Share Anonymity. The shares belonging to any unauthorized set of parties not only hide the secret, but also all identifiable information such as party identities and whether or not the shares were generated together. In particular, it suffices that such shares be uniform and independent.

- Anonymous Reconstruction. The reconstruction algorithm does not need to know the reconstructing set of parties.

Efficient FASS exists for threshold access structures. For general access structures, the only known construction relies on a monotone DNF representation of $\mathcal{A}$ and has per-party share size $\Omega(\ell n)$ where $\ell$ is the number of minterms of $\mathcal{A}$. This leaves an exponential gap between standard secret sharing and FASS even for simple access structures. Moreover, even in the threshold case, known schemes could not achieve optimal robust reconstruction when mixing shares of multiple secrets.

Motivated by a recent work of Eldridge et al. [USENIX'24], who demonstrated an application of FASS to stalker detection, we initiate a systematic study of FASS, obtaining the following main results.

- Near-Optimal Information-Theoretic FASS. We obtain strong lower bounds, showing that the dependence on the DNF size is generally inherent. In particular, the share size can be exponential in the number of parties or even in the minimum CNF size. This stands in sharp contrast to standard secret sharing, where no super-polynomial lower bounds are known, and where the share size is upper bounded by the CNF size. For DNF with $\ell$ small minterms, we improve the previous upper bound to $\tilde O(\ell)$, matching our lower bound up to a polylogarithmic factor.

- Computational FASS. We show that the above negative results can be circumvented in the computational setting, obtaining FASS schemes with succinct shares. Under the learning with errors (LWE) assumption, we present a general compiler from standard secret sharing to FASS that preserves the share size of the underlying scheme. For natural graph access structures, we directly construct succinct FASS from either one-way functions or bilinear maps.

- Robust FASS. We show that simple modifications of our computational FASS schemes can allow for robust reconstruction of a polynomially unbounded number of secrets from any mixture of their authorized shares.

We present SCORE, a modified version of the SlotToCoeff operation tailored to encrypted real vectors in the CKKS scheme, where SCORE stands for “SlotToCoeff Optimization for Real-Vector Encryption”. This approach accelerates CKKS bootstrapping algorithms that employ the SlotToCoeff operation as their final step, provided the inputs are encryptions of real vectors. We demonstrate its utility through proof-of-concept implementations for two such algorithms: the conventional bootstrapping algorithm and the SPRU algorithm. Our results indicate notable performance gains of up to 2× compared to the original formulations of the algorithms.

Anonymous communication networks (ACNs) aim to thwart an adversary, who controls or observes chunks of the communication network, from determining the respective identities of two communicating parties. We focus on low-latency ACNs such as Tor, which target a practical level of anonymity without incurring an unacceptable transmission delay.

While several definitions have been proposed to quantify the level of anonymity provided by high-latency, message-centric ACNs (such as mix-nets and DC-nets), this approach is less relevant to Tor, where user–destination pairs communicate over secure overlay circuits. Moreover, existing evaluation methods of traffic analysis attacks on Tor appear somewhat ad hoc and fragmented. We propose a fair evaluation framework for such attacks against onion routing systems by identifying and discussing the crucial components for evaluation, including how to consider various adversarial goals, how to factor in the adversarial ability to collect information relevant to the attack, and how these components combine to suitable metrics to quantify the adversary's success.

Anonymous credentials enable the unlinkable presentation of previously attested information, or even only predicates thereof. They are a versatile tool and currently enjoy attention in various real-world applications, ranging from the European Digital Identity project to Privacy Pass. While each application usually requires their own tailored variant of anonymous credentials, they all share the same common blueprint. So far, this has not been leveraged though, and currently several proposals either targeting monolithic variants of core components such as BBS signatures, or application-specific protocols undergo standardization. This is clearly not optimal, as the same work gets repeated multiple times, while still risking ending up with many slight modifications of the same main idea and protocols. In this work we present our vision to use a modular approach to build anonymous credential systems: they are built from a core component – consisting of a commitment, signature and NIZK scheme – that can be extended with additional commitment-based modules in a plug-and-play manner. We sketch modules for pseudonyms, range proofs and device binding. Importantly, apart from the committed input, all modules are entirely independent of each other. We use this modularity to propose a concrete instantiation that uses BBS signatures for the core component and ECDSA signatures for device binding, addressing the need to bind modern credential schemes to legacy signatures in secure hardware elements.

In a secret sharing scheme for a monotone access structure $\mathcal{A}$, one can share a secret among a set of parties such that all subsets of parties authorized by $\mathcal{A}$ can reconstruct the secret while all other subsets learn nothing. However, what if an unauthorized subset of parties collude and offer their shares for sale? Specifically, suppose that the parties pool their shares to create a reconstruction box that reveals the secret upon receiving enough additional shares as input. To deter this behavior, Goyal et al. (CRYPTO'21) introduced the notion of traceable secret sharing (TSS), where it is possible to provably trace reconstruction boxes containing leaked secret shares back to their respective parties. Goyal et al. and subsequent work presented definitions and constructions of TSS for the threshold access structure.

In this work, we revisit the notion of TSS. - We identify shortcomings in previous formulations of TSS and present new, strengthened definitions that are not achieved by known constructions. We show that it is easy to build reconstruction boxes for which the tracing guarantees of all previous works fail. - We extend the study of TSS beyond threshold to general access structures. Our new definitions are, in fact, necessary for this setting as natural adaptations of existing definitions become vacuous for general access structures. - We present new constructions of TSS that satisfy our definitions for all access structures captured by monotone circuits. One of our constructions relies solely on one-way functions while the other additionally relies on indistinguishability obfuscation.

Singh et. al. recently uploaded a preprint describing a new hash function inspired by the Collatz Conjecture. After performing some cursory tests, the proposed function appears to be completely unsuitable for cryptographic purposes, and should not be used.

We initiate a systematic study of information-theoretic cryptography with {\em weak privacy}, only requiring that the adversary cannot rule out any possible secret. For a parameter $00$. We obtain the following main results.

Positive results. We present efficient WP constructions for generalized secret sharing, decomposable randomized encodings, and the related notions of garbling schemes and PSM protocols, as well as interactive secure multiparty computation protocols in the plain model and in the OT-hybrid model.

For secret sharing, we settle a question of Beimel and Franklin (TCC 2007), showing that every $n$-party access structure admits a WP scheme with per-party share size $O(n)$. When all unauthorized sets have constant size, we get a $p$-WP scheme with constant share size and $p\ge 1/poly(n)$.

Negative result. For decomposable randomized encodings, we show that a previous lower bound technique of Ball et al.\ (ITCS 2020) applies also to the WP notion. Together with our upper bound, this shows that the optimal WP garbling size of the worst-case $f:\{0,1\}^n\to\{0,1\}$ is $\tilde{\Theta}(n^2)$.

Application. While WP may seem like an unrealistically weak security notion, we demonstrate its usefulness towards achieving traditional security guarantees. Concretely, under the standard LPN assumption, we show that any $p$-WP secret-sharing scheme with inverse-polynomial $p$ implies a {\em computationally secure} secret-sharing scheme for a related access structure. Together with our positive results for WP secret sharing, this implies a super-polynomial improvement of the share size for a natural class of access structures.