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.%their non-post-quantum counterparts. 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 maliciously-crafted recipient public keys, these attacks completely break semantic security and key privacy, and are inherently undetectable. We then introduce the first lattice-based mmKEM scheme that maintains full privacy even in the presence of maliciously-generated public keys. Concretely, the ciphertext size of our mmKEM for 100 recipients is ${\sim} 8\times$ smaller than naively using Crystals-Kyber. We also show how to extend our mmKEM to mmPKE, achieving a scheme that outperforms all prior lattice-based mmPKE schemes in terms of both security and efficiency. We additionally show a similar efficiency gain when applied to batched random oblivious transfer, and to group oblivious message retrieval. Our scheme is proven secure under a new Module-LWE variant assumption, Oracle Module-LWE, which can be of its own independent interest. 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.

Multi-key fully homomorphic encryption (MK-FHE) enables secure computation over ciphertexts under different keys, but its practicality is hindered by inefficient bootstrapping. In this work, we propose \ours, a new MK-FHE scheme with highly efficient bootstrapping. Our bootstrapping framework improves upon the best-known complexity, reducing it from ${O}(dkn)$ to ${O}(kn)$, and further to ${O}(\sqrt{kn})$ under parallelization, where $d$ is the gadget length (typically scaling with the number of parties $k$) and $n$ is the LWE dimension. The framework consists of two main components: (i) a ciphertext conversion algorithm that transforms a multi-key LWE ciphertext into $k$ vectorized RLWE ciphertexts via $k$ optimized blind rotations and $dk$ key-switching operations, and (ii) a hybrid accumulator that aggregates these into a single multi-key RLWE ciphertext. We implemented HERDS on both CPU and GPU platforms to demonstrate its practicality. For $k=16$, we achieve $3.3\times$ and $7.2\times$ improvements on CPU, compared to the state-of-the-art schemes by Kwak et al. (PKC 2024) and by Xiang et al. (ASIACRYPT 2024), respectively. We further achieve a $195\times$ GPU acceleration, compared to our CPU runtime. As a byproduct, we design a new distributed-decryption protocol, which allows us to obtain a ciphertext with a small noise bound, and thus does not blow up the parameters.

Despite improvements to authentication mechanisms, account compromise remains frequent and users need a trustworthy way to determine what devices have accessed their accounts. Doing so, however, is in tension with privacy goals on the modern web, which mandate that web services not learn static device identifiers. Recent work aims to address this tension via client-side encrypted access logging (CSAL), but their approach does not allow retrieving all log entries and users may miss information about adversarial accesses. We present Trace, a new CSAL system that achieves complete logging while preserving privacy. Trace records verifiable evidence of each authentication in an encrypted log stored by an independent logging service, ensuring that only the user can inspect it. The web service remains unaware of the logging, preserving backward compatibility with existing authentication infrastructures. Unlike prior approaches, Trace simultaneously achieves verifiable device attribution, backward compatibility, and formally-analyzed security against malicious adversaries. Our prototype implementation reaches over 10 K authentications per second on a single core, suggesting it can scale efficiently for large services.

A holy grail in blockchain infrastructure is a trustless bridge between Bitcoin and its second layers or other chains. We make progress toward this vision by introducing the first light-client-based Bitcoin bridge. At its heart lies BITVM2-CORE, a novel paradigm that enables arbitrary program execution on Bitcoin, combining Turing-complete expressiveness with the security of Bitcoin consensus. BITVM2-BRIDGE advances prior approaches by reducing the trust assumption from an honest majority (t-of-n) to existential honesty (1-of-n) during setup. Liveness is guaranteed with only one rational operator, and any user can act as a challenger, enabling permissionless verification. A production-level implementation of BITVM2 has been developed, and a full challenge verification has been executed on the Bitcoin mainnet.

Post-quantum cryptography focuses on research of cryptographic primitives, including public key encryption and signatures, that can resist the attacks mounted by an adversary with an access to a quantum computer. An alternative is to employ quantum cryptography to protect communication links by employing principles of quantum physics to protect security of the key exchange. Recently, a group key establishment protocol that combines these approaches in a secure way was presented by Steinwandt and Gonzales Vasco. We have successfully imple- mented and employed this protocol in a prototype application. In this article we describe the overall architecture and specific details of the implementation that can be of interest for scientific community. We conclude with a discussion of specific challenges, options and open problems that can accompany similar imple- mentation task.

SMAUG-T and HAETAE, designated as target algorithms for national standardization via the Korean Post-Quantum Cryptography (KpqC) competition, run efficiently on general-purpose platforms. On ARM Cortex-M4 class microcontrollers, however, peak stack usage becomes a key constraint: while SMAUG-T can be executed on typical Cortex-M4 boards, the baseline HAETAE implementation exceeds the available SRAM (e.g., 91{,}176\,B stack for signing), motivating dedicated memory optimization. To address this problem, we propose a suite of memory optimization techniques for SMAUG-T and HAETAE that enable their practical operation within the strict memory budget of the Cortex-M4. Experimental results demonstrate that, compared to the KpqClean\_ver2 baseline, peak stack usage was reduced by 73--83~\% for SMAUG-T5 (e.g., 24{,}300\,B$\rightarrow$4{,}240\,B in decapsulation) and by about 90~\% for HAETAE5 (e.g., 91{,}176\,B$\rightarrow$8{,}092\,B in signing). Furthermore, a branchless constant-time design was applied throughout to ensure that the optimized implementations remain robust against side-channel threats such as timing attacks. This work provides a practical methodology for deploying KpqC lattice-based cryptography in memory-constrained embedded environments.

The transition to post-quantum cryptography (PQC) significantly increases the computational cost of TLS~1.3 handshakes. In particular, hybrid handshakes incur even greater overhead, as they require performing both classical and PQC algorithms for key exchange and authentication. This paper systematically analyzes the performance of hybrid PQC TLS~1.3 handshakes using a POSIX thread pool-based parallel execution model. We evaluate a total of 135 combinations comprising 3 classical KEMs, 3 ML-KEM variants, 3 classical DSAs, and 5 PQC DSAs. Sequential execution times range from 429.2 to 1,907.0~$\mu$s, while parallel execution times range from 356.7 to 1,380.8~$\mu$s, achieving speedups of 1.08$\times$ to 1.40$\times$ across all combinations. The highest speedup is observed in P-384-based configurations, where the overlap between classical and PQC operations is most pronounced. Furthermore, we recommend both throughput-oriented combinations based on FN-DSA and currently standardized ML-DSA combinations for each NIST security level. These results provide practical design guidance for mitigating performance degradation in hybrid PQC TLS deployments.

Private set intersection (PSI) has become extremely practical, in large part due to the fact that modern protocols rely almost exclusively on cheap, symmetric-key cryptography. The same cannot be said for the variant of PSI called updatable PSI (UPSI; Badrinarayanan et al., PoPETS 2022), where parties’ input sets evolve over time, and the cost of re-computing the intersection depends only on the changes to their sets. In existing UPSI protocols, the number of public-key operations scales with the number of items. In this work, we introduce the first UPSI protocol that largely avoids public-key operations. In fact, our protocol uses mostly the same protocol tools/techniques that have been so successful in making (plain) PSI truly practical. By leveraging symmetric-key primitives, our implementation achieves orders-of-magnitude improvements over prior work. Additionally, we observe that existing UPSI security proofs do not consider an adversary who can choose protocol inputs adaptively (i.e., choose which items to add to the set the current epoch based on the adversary’s view in previous epochs). We observe that several existing UPSI protocols are trivially broken by such adaptive input selection (even with semi-honest corruption). Several variants of our protocol are secure in the presence of adaptively chosen inputs. Along the way, we also introduce a new and cleaner abstraction for a common idiom of using an oblivious key-value store (OKVS; Garimella et al., Crypto 2021) to represent a set of items. Our new abstraction, called affine set encoding, may be of independent interest.

Succinct non-interactive arguments of knowledge (SNARK) is a powerful cryptographic primitive with diverse real-world applications. The rank-one constraint system (R1CS), an intermediate representation of SNARK, has been widely used for proving arithmetic circuits. Distributed SNARKs allow multiple provers to jointly generate proofs for improving prover efficiency. However, state-of-the-art distributed SNARKs for R1CS, i.e., DIZK (USENIX Sec. '18) and Hekaton (CCS '24), fail to simultaneously achieve scalable prover efficiency and constant proof sizes. In this paper we propose Soloist, a distributed SNARK for R1CS with constant proof size, amortized communication and verification. For a size-O(n) R1CS, its prover complexity is $O(n/\ell · \log(n/\ell))$ given $\ell$ sub-provers. Experiments show that the concrete prover time of Soloist is $\ell$× as fast as the non-distributed R1CS-targeted Marlin (Eurocrypt '20) given $\ell$ sub-provers. Compared with Hekaton, Soloist features a 100× smaller communication overhead, and has a 7× faster prover time when proving general circuits. For R1CS-friendly zkRollups, Soloist outperforms the Plonk-targeted Pianist (S&P '24) with a 2.5× smaller memory cost, a 2.8× faster preprocessing, and a 1.8× faster prover when proving general circuits. To build Soloist, we design a distributed polynomial oracle proof (PIOP) for R1CS. Its core techniques include an improved (and distributed) inner product PIOP, and a distributed preprocessing PIOP via lookup tables. To instantiate the PIOPs, we propose a (distributed) batch scheme for bivariate KZG, which enables opening multiple points on multiple polynomials with a proof size irrelevant to polynomial size or point number.

PRISM is an isogeny-based cryptographic framework that relies on the hardness of computing a large prime-degree isogeny from a supersingular elliptic curve with an unknown endomorphism ring. It includes both an identification scheme PRISM-id and a signature scheme PRISM-sig. In this work, we present two attacks on PRISM-id. First, we analyze the probability that a randomly sampled prime $q$ in PRISM-id results in a $q$-torsion subgroup defined over a small extension field, and we show that this probability is higher than claimed in the original proposal. Exploiting this observation, we construct classical forgery attacks on PRISM-id. The first attack addresses the scenario in which the attacker cannot reject a challenge. It succeeds with probability $\tilde{\Theta}(2^{-(\lambda + \log\lambda)(1-\varepsilon)})$ and runs in expected time $\tilde{O}(\max\{2^{3\lambda\varepsilon}, 2^{\lambda(\varepsilon + 1/2)}\})$ for any positive real number $\varepsilon < 1/3$. Setting $\varepsilon = 1/4$ yields success probability $\tilde{\Theta}(2^{-3(\lambda + \log\lambda)/4})$ and expected time complexity $\tilde{O}(2^{3\lambda/4})$. The second forgery attack covers the scenario in which the attacker is allowed to reject challenges. It always succeeds and runs in expected time $\tilde{O}(2^{6\lambda/7})$. Finally, we describe an attack against the underlying hardness assumption of PRISM-id that runs in expected time $\tilde{O}(2^{\lambda/2})$. Note that our results do not affect the security of PRISM-sig.

This paper presents the first round-optimal threshold blind signature without random oracles. Our construction achieves security in the algebraic group model (AGM) for asymmetric pairing groups, and tolerates adaptive corruption of up to $t-1$ signers, where $t$ is the threshold. We improve upon the recent threshold blind signatures of Lehmann, Nazarian and Özbay (EUROCRYPT 2025) and Jarecki and Nazarian (ASIACRYPT 2025) in two ways: we eliminate both the reliance on random oracles and the need for $q$-type assumptions in the AGM. As a core building block, we introduce a new pairing-based round-optimal blind signature without random oracles, based on the $2$-DL assumption in the AGM. Both blind signature schemes achieve communication and computation costs only twice that of the celebrated blind BLS signature.

The processing of ML-KEM (formerly CRYSTALS-Kyber), a key encapsulation mechanism with post-quantum security, is performed by multiplication, addition, and subtraction of polynomials whose coefficients lie in the finite field ${\mathbb F}_{3329}$. To reduce the number of such operations, it is common to use the Number Theoretic Transform (NTT). This paper focuses on arithmetic over ${\mathbb F}_{3329}$ and proposes the use of a logarithmic representation with respect to a primitive element $\alpha$ of ${\mathbb F}_{3329}^*$ for implementing multiplication, addition, and subtraction over ${\mathbb F}_{3329}$. In this representation, multiplication in ${\mathbb F}_{3329}^*$ can be reduced to addition in $\mathbb{Z}_{3328}$. Furthermore, addition and subtraction in ${\mathbb F}_{3329}^*$ can be computed in the logarithmic domain by using Zech's logarithm. However, special treatment is required when $0 \in {\mathbb F}_{3329}$ is involved in the operations. This paper proposes a new implementation method of the logarithmic representation for arithmetic over ${\mathbb F}_{3329}$, including the handling of such exceptional cases.

Attribute-based signatures (ABS) allow users to simultaneously sign messages and prove their possession of some attributes while hiding the attributes and revealing only the fact that they satisfy a public policy. In this paper, we propose a generic construction of ABS for circuits of unbounded depth and size, with optimal parameter size—meaning the lengths of public parameters, keys, and signatures are all constant. Our construction can be instantiated from various standard assumptions, including LWE and DLIN. This substantially improves the state-of-the-art ABS scheme by Boyle, Goldwasser, and Ivan (PKC 2014), which, while achieving optimal parameter size, relies on succinct non-interactive arguments of knowledge that can only be constructed from non-standard assumptions. Our generic construction is based on RAM delegations. At a high level, we leverage the fact that the circuit associated with the signature can be made public and compress it using the power of RAM delegation. This allows us to achieve an overall optimal parameter size while simultaneously hiding the user’s attribute.

It has been a very long standing open question whether the CFS signature scheme whose security is basically that of a McEliece scheme based on very high rate binary Goppa codes could be attacked or not. There was a first cryptanalytic result by Faugère et al in 2011 consisting in finding a distinguisher for the binary Goppa codes used in this scheme showing that these codes can be distinguished in polynomial time from a random binary linear code. However despite numerous cryptanalytic attempts and even if the original distinguisher has been significantly improved, no attack on the McEliece scheme based on binary Goppa codes has been found so far except for very peculiar Goppa codes of degree $2$. We show here that the Pfaffian modeling used in the distinguishing attack of Couvreur, Mora and Tillich of Asiacrypt 2023 can actually be used together with a shortening trick and looking for squares in the corresponding ideal to find a polynomial attack on the CFS scheme based on very high rate binary Goppa codes.This breaks this 25 years old signature scheme. We demonstrate the effectiveness of this approach by recovering the key of TII McEliece challenges with a claimed key security of up to 210 bits.

Range queries can filter, aggregate, and retrieve database entries that lie in a specified multi-dimensional rectangle. Private range queries allow a client to query a server's public database while keeping the client's multi-dimensional rectangle hidden. We construct RangeR, a constant-round private range query scheme that supports any associative aggregation function (e.g., SUM, MAX, TOP-K) and works with any number of servers. In the single-server setting, RangeR is orders of magnitude faster and uses 50%-90% less communication than HADES (VLDB 2025), a prior single-server private range query scheme that only supports linear aggregation functions. We describe how RangeR can be used to implement a privacy-preserving map application that can return the highest-rated restaurants near a user. Using data from $\mathtt{OpenStreetMaps}$, we estimate that a user can find the highest-rated restaurants within one kilometer of their location within $2$ seconds, while revealing only that the user is somewhere in the USA.

Attribute-Based Signatures (ABS) enable users to authenticate messages under expressive attribute policies while remaining anonymous. Existing ABS variants, however, treat linkability as a static, system-wide property: signatures are either always unlinkable, as in standard ABS, or globally linkable, as in traceable or accountable extensions. This rigid dichotomy fails to capture scenarios where correlation should arise only under explicitly declared conditions. This work introduces Conditionally Linkable Attribute-Based Signatures (CLABS), a framework extending ABS with programmable, context-dependent linkability. Each certified user with attribute $x$ is associated with a linking set $L_x$ over a public context space $\mathcal{T}$. For each context $\tau\in\mathcal{T}$, a public function $f_\tau$ specifies how attributes are compared. Two signatures are publicly linkable if and only if $\tau\in L_x\cap L_{x'}$ and $f_\tau(x)=f_\tau(x')$; otherwise they remain unlinkable. This enables selective, verifiable correlation without central trust and with leakage limited to the opt-in bit. We formalize the syntax and security notions of CLABS, capturing conditional linkability and context-aware anonymity, thereby ensuring privacy and verifiable linkage under voluntary participation. CLABS unifies global unlinkability and fine-grained, context-specific linkage within a single formal framework. We realize CLABS generically using three modular components: a pseudorandom function for deterministic tag generation, a conventional signature for attribute certification, and a signature of knowledge (SoK) proving correct tag computation and Boolean policy satisfaction without revealing $x$. Finally, we instantiate CLABS under standard lattice assumptions in the quantum random oracle model (QROM), achieving post-quantum security while supporting arbitrary Boolean policies. The techniques we employ to prove circuit satisfiability and tag correctness may be of independent interest.

The distributed nature of federated learning systems makes them vulnerable to backdoor attacks in which malicious clients manipulate local training data using trigger-dependent behaviors to cause targeted misclassification. Although homomorphic encryption preserves the privacy of model updates during aggregation, it limits the application of conventional defenses that require access to plaintext updates. Moreover, distinguishing poisoned models from benign variations becomes more challenging under non-independent and identically distributed (non-IID) data distributions.To address this challenge, we introduce a defense strategy that operates at inference time by identifying abnormal internal activation patterns within the aggregated global model, rather than filtering encrypted individual updates during training. The proposed approach analyzes neurons that exhibit low activation on clean inputs, referred to as "dormant" neurons, but become disproportionately active in the presence of trigger patterns. By constructing a statistical activation baseline using a small clean dataset, we derive class-specific thresholds that serve as decision boundaries to detect and reject suspicious predictions. Since the proposed method relies on global model behavior at inference time instead of inspecting individual client updates, it does not introduce additional training overhead and remains robust under non-IID data settings. Our approach maintains a strong balance between privacy, security, and accuracy by defending against backdoor attacks without requiring access to client updates. Experimental results demonstrate that even with a 99% attack success rate and 90% main-task accuracy, the proposed defense method successfully detects 100% poisoned images.

We revisit Group Encryption (GE)—an encryption analogue of group signatures introduced by Kiayias et al. (Asiacrypt 2007). A GE system simultaneously provides anonymity and traceability for receivers who are certified group members, enabling a range of privacy-preserving applications. While prior work has extensively addressed \emph{how} to trace receivers in GE, the question of \emph{why} a ciphertext should be traceable remains unexplored. Unlike group signatures, where opening can be justified by the signed content, tracing in GE poses a dilemma because the underlying plaintext is confidential. To address this gap, we introduce Group Encryption with Oblivious Traceability (GEOT), an enhanced form of GE in which the traceability of a ciphertext $\psi$ intended for receiver $\mathsf{id}$ and containing message $\mathbf{w}$ is governed by a public tracing policy $P(\mathsf{id},\mathbf{w}) \in {0,1}$. Here, $P(\mathsf{id},\mathbf{w})=0$ denotes traceability, whereas $P(\mathsf{id},\mathbf{w})=1$ ensures non-traceability. The traceability status is known to the sender but remains hidden from all parties except the opening authority, which learns nothing about $\mathsf{id}$ in the non-traceable case. GEOT further supports message filtering and dynamic membership, following Nguyen et al. (PKC 2021). Filtering enforces that valid ciphertexts satisfy a public policy $F(\mathbf{w})=1$, while dynamicity enables users to join and leave the system over time. We formalize GEOT with concise syntax and rigorous security notions, and present a modular construction based on standard cryptographic primitives: signatures, public-key encryption, and non-interactive zero-knowledge proofs. We also give a concrete instantiation from code-based assumptions supporting arbitrary tracing and filtering policies represented by polynomial-size Boolean circuits. In addition to expressive filtering and tracing functionalities, our scheme achieves significant efficiency improvements over existing post-quantum GE constructions.

Efficient realizations of succinct non-interactive arguments of knowledge (SNARKs) have gained popularity due to their practical applications in various domains. Among existing schemes, those based on error-correcting codes are of particular interest because of their good concrete efficiency, transparent setup, and plausible post-quantum security. However, many existing code-based SNARKs suffer from the disadvantage that they only work over specific finite fields. In this work, we construct a code-based SNARK that does not rely on any specific underlying field; i.e., it is field-agnostic. Our construction follows the framework of Brakedown (CRYPTO '23) and builds a polynomial commitment scheme (and hence a SNARK) based on recently introduced expand-accumulate codes. Our work generalizes these codes to arbitrary finite fields; our main technical contribution is showing that, with high probability, these codes have constant rate and constant relative distance (crucial properties for building efficient SNARKs), solving an open problem from prior work. As a result of our work we obtain a SNARK where, for a statement of size $M$ , the prover time is $O(M \log M )$ and the proof size is $O(\sqrt{M} )$. Under reasonable conjectures, we obtain proofs thatt are $1.9\text{-}2.8\times$ smaller than the original Brakedown result (which is also field agnostic), while only introducing $20\%$ overhead in the prover time. Our work suggests that there is a rich tradeoff space in SNARK design offered by different codes, and indicates that a detailed study of such tradeoffs is warranted.

Hash-based succinct non-interactive arguments (SNARGs) are widely used in practice, owing to their ease of deployment, notable efficiency, and post-quantum properties. They are constructed via the BCS transformation, which combines an interactive oracle proof (IOP) and a hash-based vector commitment. This success has motivated the study of hash-based succinct non-interactive reductions (SNRDXs), used for recursively ensuring the correctness of distributed computations, by extending the BCS transformation to work with an interactive oracle reduction (IOR) rather than an IOP. We prove that hash-based SNRDXs constructed from IORs are secure in the quantum random oracle model (QROM), provided the IOR satisfies a natural post-quantum analogue of state-restoration security; moreover, we show that (classical) round-by-round security implies post-quantum state-restoration security. Our results thus achieve a post-quantum analogue of the classical security of SNRDXs in the ROM, and generalize a prior result about SNARGs in the QROM to cover recent SNRDXs constructions. Moreover, for SNRDXs we propose and achieve an adaptively-secure straightline quantum extraction property in the QROM, while prior work obtains non-adaptive security for SNARGs in the QROM. Along the way, we develop a modular framework for proving the security of the (extended) BCS transformation based on a new quantum extraction property for vector commitments (which we prove is achieved by Merkle commitments), mirroring classical security analyses and departing from prior "monolithic" post-quantum analyses. This demands a new commutator bound that shows the almost-commutativity between quantum extraction and quantum oracle queries, by bounding a natural classical extraction property.

Committing security has recently emerged as an essential property for message authentication codes (MACs), driven by applications such as abuse reporting in end-to-end encrypted messaging systems. Traditional notions, such as unforgeability or pseudorandomness, are insufficient in these contexts, prompting the introduction of stronger security notions. Bhaumik et al. (CRYPTO'24) initiated this line of research by formalizing the notions of commitment and context-discovery for MACs and analyzing several standardized birthday-bound secure constructions. We extend this line of work to beyond-birthday-bound (BBB) secure MACs. In particular, we examine the class of constructions identified by Chen et al. (ASIACRYPT'21), which employ two block ciphers and a single block hash function, together with well-studied BBB MACs from the DbHtS paradigm. Our findings depict a heterogeneous picture: while several constructions succumb to simple attacks, others exhibit some resilience, highlighting that committing and context-discovery security for BBB MACs depends strongly on structural design choices.

FuncCPA is a recent security notion in which the CPA game is extended by a functional re-encryption oracle in order to model setups in which a server performing FHE computations is allowed to interactively delegate part of the computation back to the client. In this paper, we study funcCPA-style variants of several CCA security notions, including CCA1 and the more recent vCCA security. Contrary to the CPA case where a strict separation holds between CPA and funcCPA, we show that these new variants are equivalent to their respective originating CCA security notions. Interestingly, funcCPA-style security notions also model setups where, rather than delegating part of the encrypted domain computation all the way back to the client, the server has the ability to perform this delegation towards a honest or semi-honest client proxy it hosts, such as a secure enclave. We then provide a number of blueprints for achieving both FHE-like capabilities and advanced CCA security properties which may then meaningfully be implemented by leveraging on the combination of a partially homormophic scheme and a semi-honest non-colluding enclave hosted within the server performing the encrypted domain calculations itself.

The selection of shift polynomials is a pivotal yet challenging step in Coppersmith's method for computing modular roots of multivariate polynomials. We propose a novel, determinant-based strategy for generating these polynomials, thereby presenting an improved variant of Coppersmith's method tailored for certain multivariate modular equations. Our approach is first validated on solving the Modular Inversion Hidden Number Problem (MIHNP) and predicting the Inversive Congruential Generator (ICG), where it is shown to outperform prior methods both in theory and in practice. Furthermore, when applied to the Modular Inversion Double Hidden Numbers Problem (MIDHNP), our analysis reveals that MIDHNP is not harder than MIHNP, thereby disproving a conjecture by Boneh et al. (Asiacrypt 2001).

Falcon is a winner of NIST’s six-year post-quantum cryptography standardisation competition. Based on the celebrated full-domain-hash framework of Gentry, Peikert and Vaikuntanathan (GPV) (STOC’08), Falcon leverages NTRU lattices to achieve the most compact signatures among lattice-based schemes. Its security hinges on a Rényi divergence-based argument for Gaussian samplers. However, the GPV proof, which uses statistical distance to argue closeness of distributions, fails when applied naively to Falcon due to parameter choices resulting in statistical distances as large as $2^{−34}$. Additional implementation-driven deviations from the GPV framework further invalidate the original proof, leaving Falcon without a security proof despite its selection for standardisation. In this work, we provide the first formal security proof of Falcon in the random oracle model, achieved through a few conservative modifications, now incorporated into the forthcoming standard. At the heart of our analysis lies an adaptation of the GPV framework to work with the Rényi divergence, along with an optimised method for parameter selection under this measure. We also analyse the FFO Sampler that is used in Falcon. Further, we prove the equivalence of plain unforgeability to a multi-target inhomogeneous SIS problem, and strong unforgeability to a second-preimage version of this problem, providing clear targets for cryptanalysis. Assuming these problems are as hard as standard SIS, we demonstrate that Falcon-512 barely satisfies the claimed 120-bit security target, while Falcon-1024 achieves the claimed security level.

We propose an efficient and numerically stable sign evaluation over the Cheon–Kim–Kim–Song (CKKS) homomorphic encryption (HE) scheme by introducing a new bootstrapping. Sign evaluation underpins applications such as comparison, sorting, and machine learning. Extensive studies exist, such as the polynomial-composition method by Lee et al. (IEEE TDSC'22). A critical oversight in the literature is that evaluating composite polynomials consumes substantial multiplicative depth, necessitating intermediate bootstrapping. Such bootstrapping introduces considerable noise, which harms convergence and degrades accuracy. Inspired by bootstrapping bits (Eurocrypt'24), we propose a new white-box bootstrapping for sign evaluation. We prove that our bootstrapping, unlike traditional bootstrapping, intrinsically reduces noise. Consequently, (i) it admits an interpretation as a polynomial composition, accelerating convergence “for free,” and (ii) it removes the bootstrapping-induced noise that disrupts convergence in prior art. Our implementation validates that the proposed method achieves approximately 40-bit precision—bounded only by the fundamental rescaling noise—doubling the $\approx$ 20 bits of prior work under identical parameters. Moreover, our approach requires less depth and is numerically more stable.

This paper gives the first lattice-based two-round threshold signature scheme that tolerates the adaptive corruption of up to $T -1$ out of $N$ signers. Our construction is based on the MLWE and MSIS assumptions. We substantially improve upon the only existing adaptively secure lattice-based construction, recently given by Katsumata, Reichle, and Takemure (CRYPTO '24), which requires five rounds.

Federated Learning is an emerging machine learning paradigm that enables distributed model training directly at data sources and transmitting only model updates, thereby reducing communication bottlenecks and mitigating risks associated with raw data exposure. Despite these advantages, recent advances have demonstrated that privacy in federated learning remains limited and subject to inference attacks that exploit shared model updates to extract sensitive information. To address this limitation, we propose Robust and Resilient Federated Learning using Distributed Homomorphic Encryption (RRFL-DHE), a privacy-preserving federated learning framework that combines a distributed homomorphic encryption scheme with threshold linear secret sharing. The framework enables clients to encrypt their model updates to allow secure aggregation without exposing individual contributions. To maintain resilience against client dropouts, RRFL-DHE incorporates a dropout management protocol, maintaining training continuity and accurate global model reconstruction. To assess our framework, we provide a rigorous security proof against a semi-honest server model and evaluate RRFL-DHE on non-IID MNIST and Fashion MNIST datasets using SVM and CNN models. The results show that RRFL-DHE preserves model utility with less than 1% deviation compared to the FedAvg approach, while outperforming the xMK-CKKS approach by approximately 15% in accuracy. These findings highlight the importance of RRFL-DHE as a promising solution for distributed computing, while preserving privacy, maintaining utility, and ensuring resilience against dropouts.

This paper presents an improved Plantard's modular arithmetic (Plantard arithmetic) tailored for Lattice-Based Cryptography (LBC). Based on the improved Plantard arithmetic, we present faster implementations of two LBC schemes, Kyber and NTTRU, running on Cortex-M4. The intrinsic advantage of Plantard arithmetic is that one multiplication can be saved from the modular multiplication of a constant. However, the original Plantard arithmetic is not very practical in LBC schemes because of the limitation on the unsigned input range. In this paper, we improve the Plantard arithmetic and customize it for the existing LBC schemes with theoretical proof. The improved Plantard arithmetic not only inherits its aforementioned advantage but also accepts signed inputs, produces signed output, and enlarges its input range compared with the original design. Moreover, compared with the state-of-the-art Montgomery arithmetic, the improved Plantard arithmetic has a larger input range and smaller output range, which allows better lazy reduction strategies during the NTT/INTT implementation in current LBC schemes. All these merits make it possible to replace the Montgomery arithmetic with the improved Plantard arithmetic in LBC schemes on some platforms. After applying this novel method to Kyber and NTTRU schemes using 16-bit NTT on Cortex-M4 devices, we show that the proposed design outperforms the known fastest implementation that uses Montgomery and Barrett arithmetic. Specifically, compared with the state-of-the-art Kyber implementation, applying the improved Plantard arithmetic in Kyber results in a speedup of 25.02% and 18.56% for NTT and INTT, respectively. Compared with the reference implementation of NTTRU, our NTT and INTT achieve speedup by 83.21% and 78.64%, respectively. As for the LBC KEM schemes, we set new speed records for Kyber and NTTRU running on Cortex-M4.

Mahadev [SIAM J. Comput. 2022] introduced the first protocol for classical verification of quantum computation based on the Learning-with-Errors (LWE) assumption, achieving a 4-message interactive scheme. This breakthrough naturally raised the question of whether fewer messages are possible in the plain model. Despite its importance, this question has remained unresolved. In this work, we prove that there is no quantum black-box reduction of non-interactive classical verification of quantum computation of $\textsf{QMA}$ to any falsifiable assumption. Here, “non-interactive” means that after an instance-independent setup, the protocol consists of a single message. This constitutes a strong negative result given that falsifiable assumptions cover almost all standard assumptions used in cryptography, including LWE. Our separation holds under the existence of a $\textsf{QMA-QCMA}$ gap problem. Essentially, these problems require a slightly stronger assumption than $\textsf{QMA}\neq \textsf{QCMA}$. To support the existence of such problems, we present a construction relative to a quantum unitary oracle.

Registered attribute-based encryption (Reg-ABE) is a new variant of attribute-based encryption (ABE) that was introduced to resolve the notorious key escrow problem. In a Reg-ABE system, there is no authority that generates secret keys, and each user joins the system by generating its own public/secret key pair. Because of its public-key infrastructure-like model and versatile access control functionality, Reg-ABE is a promising alternative of ABE. In this work, we present a highly space efficient non-monotone Reg-ABE scheme with strong security. Specifically, the sizes of MPK and ciphertext of our scheme are both about 7.5KB, which could be more than 2000$ \times $ and 5$ \times $ smaller than those of the state-of-the-art scheme by Garg \textit{et al.}~(Crypto'24, GLWW), respectively, in a realistic parameter setting. The sizes of other elements such as helper secret key and a state that the system maintains could also become more than 40$ \times $ smaller. Furthermore, our scheme supports non-monotone policies and CCA-security, neither of which GLWW supports. We implement our scheme together with GLWW and show that encryption of ours outperforms that of GLWW even with the above features, while decryption of ours is a few times less efficient than that of GLWW but still takes less than 0.1 seconds with a laptop. Our scheme is proven secure in the generic group model. We also present a dual system variant of our main scheme, which is CPA-secure under the MDDH assumption in the plain model. The variant is much simpler and more efficient than the only known non-monotone Reg-ABE scheme by Attrapadung \textit{et al.}~(Crypto'24).

Deduplication of encrypted data is a feasible way to optimize cloud storage against cloud curious. However, encrypted data is prone to incurring the attention for its chaotic form. In this work, we focus on the improvement of security and efficiency of deduplication technology. We introduce a notion of Visual Fuzzy Deduplication to hide the sensitive multi-media data (i.e., images) to retain only one copy of cloud storage. Moreover, our deduplication realizes batch detection for duplicates and Brute Force Attacks (BFA) resistance without server aided. We simulate our experiments on three datasets to achieve the desired results, which shows our scheme is practical and efficient to optimize privacy-preserving cloud storage.

This paper proposes a built-in framework that embeds a dedicated ``Crypto Expert" directly into large language models (LLMs) architecture. As an initial attempt, we design a differentiable proxy tailored to the Advanced Encryption Standard (AES) algorithm, using our customized neuron units, including SoftXOR, SoftLUT and GF conv neurons. These units provide functional equivalence to the AES within the Boolean domain, while enabling stable gradients for backpropagation. By integrating this differentiable proxy as a specialized expert within a Mixture-of-Expert (MoE) LLM, the LLM learns to autonomously route and encrypt sensitive tokens during the training phase. After training, the differentiable proxy is seamlessly swapped for a real and discrete AES implementation to guarantee provable security at inference. Our empirical evaluations demonstrate that our approach significantly reduces neuron counts and latency compared to prior ReLU-based representation, mitigates continuous differential attacks, and enforces end-to-end data protection without degrading downstream task utility. We expect this attempt to serve as a catalyst for future research into the seamless fusion of formal cryptographic guarantees and deep learning computation graphs.

Collaborative zkSNARKs allow multiple mutually distrustful parties to jointly prove the correctness of a computation without revealing their private inputs. This enables a new class of exciting secure applications, such as privacy-preserving healthcare data aggregation, privacy preserving audits, and jointly trained machine learning models. Unfortunately, existing collaborative zkSNARKs still struggle to support many target applications in practice, which operate over large-scale datasets. This is due to prohibitive memory and communication overheads, both of which may be orders of magnitude larger than the original datasets, as well as the lack of updatability: If a dataset is updated, then the computation must be proved again from scratch. As any one of these limitations can be a bottleneck, we address them simultaneously with collaborative incrementally verifiable computation, which enables multiple mutually distrustful parties, each with its own private inputs, to jointly update a running succinct proof alongside each step of a streaming computation. For each step of computation, our construction features only constant communication overhead per party (assuming a broadcast channel), and memory overhead that only scales with the memory costs of a single step.

Poseidon[GKR+19 ] and its successor Poseidon2[GKS23] are arithmetization-oriented permutations proposed for hashing inside algebraic proof systems. While there is extensive prior work on cryptanalysis of reduced-round Poseidon/Poseidon2 and theoretical and practical weaknesses of the Fiat-Shamir transform, these two attacks are typically studied in isolation. This work asks whether combining them i.e., instantiating Fiat-Shamir with Poseidon can enable new attacks. We design and implement multiple candidate attacks that encode verifier checks together with reduced-round Poseidon-based challenge derivation as explicit polynomial systems, targeting settings such as Sigma protocols and FRI-like degree enforcement. We evaluate these approaches using Gr¨obner bases. We use this model to derive Gr¨obner-basis attack formulations aimed at constructing verifier-accepting transcripts that violate the intended low-degree bound, and we report the computational bottlenecks encountered in representative parameter regimes. We also document additional explored directions, including retry-style challenge biasing and reduced-round investigations, in order to clarify which attacks appear more or less promising. Across our implementations, we do not obtain meaningful forgeries: even with heavily reduced Poseidon parameters, Gr¨obner-basis computations do not find solutions for random instances of the constructed systems. Our results provide negative evidence for several natural algebraic attack routes on Poseidon-based Fiat-Shamir instantiations, and help clarify which known Fiat-Shamir weaknesses do and do not transfer to well-structured, fully transcript-bound deployments.

Following the announcement of the first winners of the NIST post-quantum cryptography standardization process in 2022, cryptographic protocols are now undergoing migration to the newly standardized schemes. In most cases, this transition is realized through a hybrid approach, in which algorithms based on classical hardness assumptions, such as the discrete logarithm problem, are combined with post-quantum algorithms that rely on quantum-resistant assumptions, such as the Short Integer Solution (SIS) problem. A combiner for signature schemes can be obtained by simply concatenating the signatures of both schemes. This construction preserves unforgeability of the underlying schemes; however, it does not extend to stronger notions, such as strong unforgeability. Several applications, including authenticated key exchange and secure messaging, inherently require strong unforgeability, yet no existing combiner is known to achieve this property. This work introduces three practical combiners that preserve strong unforgeability and all BUFF (beyond unforgeability features) properties. Each combiner is tailored to a specific class of classical signature schemes capturing all broadly used schemes that are strongly unforgeable. Remarkably, all combiners can be instantiated with any post-quantum signature scheme in a black-box way making deployment practical and significantly less error prone. The proposed solutions are further highly efficient and have signatures that are at most the size of the (insecure) concatenation combiner. For instance, our most efficient combiner enables the combination of EdDSA with ML-DSA, yielding a signature size that is smaller than the sum of an individual EdDSA signature and an individual ML-DSA signature. Additionally, we identify a novel signature property that we call random-message validity and show that it can be used to replace the BUFF transform with the more efficient Pornin-Stern transform. The notion may be of independent interest.

Hierarchical deterministic (HD) wallets, standardized as BIP32, allow users to manage a tree of cryptographic key pairs from a single master seed. A defining feature is non-hardened derivation: child public keys can be derived from a parent public key alone, enabling watch-only wallets where a server generates fresh receiving addresses while the signing key remains offline. Existing constructions rely on the algebraic structure of elliptic curve public keys, and recovering this functionality in the post-quantum setting is an open problem. We present two post-quantum HD wallet constructions. The first uses ML-DSA and supports hardened (private-key-dependent) derivation with proofs of unlinkability and unforgeability. The second, our primary contribution, uses Raccoon-G, a variant of the Raccoon signature scheme with Gaussian-distributed secrets. We modify Raccoon-G to publish full, unrounded public keys, preserving linearity. Since the sum of Gaussians is again Gaussian with predictable wider variance, derived keys remain statistically close to freshly generated ones, enabling non-hardened public key derivation. We prove unlinkability and unforgeability under standard lattice assumptions, and introduce a method for generating rerandomizable Raccoon-G key pairs from fixed randomness with provable existential unforgeability. Both constructions are implemented in Rust. To our knowledge, this is the first post-quantum HD wallet construction that recovers BIP32's full public key derivation functionality with provable security under standard assumptions.

The Unbalanced Oil and Vinegar (UOV) construction has been a central framework in multivariate cryptography since its appearance in 1999. In fact, four schemes in the second round of NISTs additional call for signatures are UOV-based. For efficiency considerations, most of these schemes are defined over a field of characteristic 2. This has as a side effect that the polar forms of the UOV public maps are not only symmetric, but also alternating. In this work, we propose a new key-recovery attack on UOV over fields of characteristic 2 that exploits this alternating property. We interpret the polar forms of the UOV public map as elements of the exterior algebra. Moreover, we show that these forms exhibit a structure that is dependent on the secret oil space. Using the Plücker embedding, we also express the dual of the secret oil space as an element of the exterior algebra. Utilizing the structure of the public maps, we can formulate relations on this secret element in this algebra. Finally, we demonstrate that the secret oil space can be recovered using sparse linear algebra techniques. This new attack has a lower time complexity than previous methods and reduces the security of $\texttt{uov-Ip}$, $\texttt{uov-III}$, and $\texttt{uov-V}$, by 4, 11, and 20 bits respectively. In addition, the attack is applicable to MAYO$_2$ and reduces its security by 28 bits.

The beyond unforgeability features formalize additional security properties for signature schemes. We develop a general framework of binding properties for signature schemes that encompasses existing beyond unforgeability features and reveals new notions. Furthermore, we give new results regarding various transforms: We show that the transform by Cremers et al. (SP’21) achieves all of our security notions; we give a modified definition of so-called weak keys, and show that the Pornin–Stern transform (ACNS’05) also achieves all notions if there are no weak keys. Finally, we connect our framework to unforgeability notions.

Non-interactive blind signatures (NIBS; Eurocrypt '23) allow a signer to asynchronously generate presignatures for a recipient, ensuring that only the intended recipient can extract a "blinded" signature for a random message. We introduce a new generalization called non-interactive batched blind signatures (NIBBS). Our goal is to reduce the computation and communication costs for signers and receivers, by batching multiple blind signature queries. More precisely, we define the property of 'succinct communication' which requires that the communication cost from signer to receiver be independent of the batch size. NIBBS is very suitable for large-scale deployments requiring only minimal signer-side effort. We design a NIBBS scheme and prove its security based on the hardness of lattice assumptions (in the random oracle model). When instantiated with the low-depth PRF candidate "Crypto Dark Matter" (TCC '18) and the succinct lattice-based proof system for rank-1 constraint systems (Crypto '23), our final signature size is 308 KB with <1 KB communication.

Homomorphic encryption (HE) for high-precision integers has been steadily researched through various schemes; however, these approaches incurred severe overhead as the bit-width grew, requiring larger parameters to support integers of several hundred to a thousand bits. A significant breakthrough was recently made by Boneh and kim (Crypto'25). Their scheme constructs a residue number system from the different slots of a single CKKS ciphertext. This enables arithmetic on thousand-bit integers without increasing parameters. However, RNS approach in Boneh et al., which performs approximate reduction, fundamentally cannot support non-arithmetic operations. Alternatively, radix-based approach proposed by Kim (CHES'25) can perform non-arithmetic operations, but they require $O(k)$ bootstraps for a bit-width $k$. This makes them highly inefficient, and thus impractical, for non-arithmetic operations requiring thousand-bit precision. This paper proposes an improved radix-based CKKS scheme, centered on a 2-step algorithm that optimizes the number of bootstraps required for the digit carry operation to $O(\log k)$. The proposed scheme requires only 3-6 bootstraps to restore the result of a 32-2048 bit integer multiplication to its unique representation, which enables the efficient implementation of non-arithmetic operations such as comparison. Furthermore, our scheme extends the radix-based system, previously limited to prime-power moduli, to support an efficient homomorphic reduction algorithm for arbitrary moduli. Furthermore, our experiments demonstrate substantial efficiency gains compared to Boneh et al. For example, for moduli used in homomorphic signatures (Curve25519, P-384, and 2048-bit RSA), our scheme can process up to 4$\times$ more integers in a single ciphertext. Specifically for Curve25519, we also reduce the latency by 1.4$\times$, shortening the amortized time by 5.6$\times$ compared to Boneh et. al. and achieving a final processing time of 1.34 seconds per data point.

Threshold encryption distributes decryption capability across $n$ parties such that any $t$ of them can jointly decrypt a ciphertext, while smaller coalitions learn nothing. However, once $t$ or more parties collude, traditional threshold schemes provide no accountability: a coalition of $t$ or more parties can pool its keys into a pirate decoder that enables unrestricted decryption, all without any risk of being exposed. To address this, Boneh, Partap, and Rotem [CRYPTO '24] introduced threshold traitor tracing (TTT), which equips threshold encryption with traceability. Yet, all known TTT schemes either suffer from parameter sizes growing with at least $n^{1/3}$, or rely on indistinguishability obfuscation to achieve optimal parameters. In this paper, we present the first TTT schemes with optimal parameters, where public keys, secret keys, and ciphertexts are all bounded by ${\sf poly}(\lambda,\log n)$, built solely from standard cryptographic tools and assumptions. Our first construction relies on the decisional Bilinear Diffie–Hellman (DBDH) assumption in prime order bilinear groups. Our second scheme is a candidate construction based on the Learning with Errors (LWE) assumption, which relies on the existence of secret sharing schemes with certain properties. This construction is plausibly post-quantum secure, and supports ramp-thresholds where decryption requires a larger coalition than those tolerated by security. Both of our constructions provide traceability against coalitions of arbitrary sizes. To achieve these results, we introduce a new primitive, Attribute-Based Threshold Encryption (ABTE), which generalizes both threshold and attribute-based encryption. We then combine ABTE with Mixed Functional Encryption through a new compiler to obtain our TTT schemes. We believe ABTE is a powerful primitive that may have independent applications beyond optimal TTT.

This paper presents a pioneering approach to constructing sidechains on the Ethereum network with a focus on post-quantum security. Our framework integrates a novel quantum-resistant version of a non-interactive random oracle proof of knowledge (NIROPoK) scheme, alongside a quantum-resistant proof-of-stake mechanism and a post-quantum bridge based on the Dilithium digital signature scheme. By harnessing these advanced cryptographic techniques, we establish a robust defense against quantum computing threats while ensuring enhanced privacy for blockchain transactions. By conducting a thorough analysis and implementing our approach, we demonstrate the feasibility and effectiveness of creating quantum-resistant sidechains within the Ethereum ecosystem. Our proposed sidechain is also capable of securing Ethereum transactions from quantum threats using Ethereum’s current architecture and security measures.

Non-interactive blind signatures (NIBS) capture the minimal setting of blind signatures where the message space is restricted to unstructured random strings. They enable a signer to pre-compute presignatures without prior interaction, while ensuring that only the intended recipient can derive the corresponding blind signature. In this work, we consider the problem of threshold issuance of NIBS. Specifically, we introduce the notion of non-interactive threshold blind signatures (NITBS), where a user obtains partial presignatures from a threshold of signers and locally combines them into a valid blind signature. We provide a formal treatment of this primitive by defining the corresponding security notions of blindness and one-more unforgeability. We then present the first concrete construction of NITBS, obtained by adapting the Pointcheval-Sanders (PS) signature scheme, and establish its security in the algebraic group model. Our micro-benchmarking results show that our construction attains the smallest presignature and signature sizes and the fastest issuance among all existing NIBS schemes.

Post-quantum signature schemes are becoming increasingly important due to the threat of quantum computers to classical cryptographic schemes. Among the approaches considered in the literature, the MPC-in-the-head paradigm introduced by Ishai et al. (STOC'07) provides an innovative solution for constructing zero-knowledge proofs by exploiting Multi-Party Computation (MPC). This technique has proven to be a versatile tool in order to design efficient cryptographic schemes, including post-quantum signatures. Building on the MPC-in-the-head paradigm, we introduce Bittersweet signatures, a new class of signature schemes based on the Learning With Rounding (LWR) assumption. Their main advantage is conceptual simplicity: by exploiting (almost) key-homomorphic pseudorandom functions (PRFs), a cryptographic object that preserves pseudorandomness while allowing linear operations on keys, we obtain a very regular design offering nice opportunities for parallel implementations. Theoretically, analyzing Bittersweet signatures requires addressing significant challenges related to the (carry) leakage that almost key-homomorphic operations lead to. Concretely, Bittersweet signatures natively lead to competitive signature sizes, trading moderate software performance overheads for hardware performance gains when compared to state-of-the-art MPC-in-the-head schemes (e.g., relying on code-based assumptions), while admittedly lagging a bit behind recent algorithms based on the VOLE-in-the-head or Threshold-Computation-in-the-head frameworks. Besides, their scalability and algebraic structure makes them promising candidates for leakage-resilient implementations. The new abstractions we introduce additionally suggest interesting research directions towards further optimization and generalization.

X-Wing (Barbosa et al., CiC Volume 1, Issue 1) is a hybrid key encapsulation mechanism (KEM) currently considered for standardization by IETF and deployed by major companies such as Google to ensure a secure transition to post-quantum cryptography. It combines a classical X25519 KEM with the post-quantum ML-KEM-768. In this paper, we propose the first analysis of the anonymity of X-Wing. We are interested in tight and memory-tight reductions that offer stronger security guarantees. We first establish in the standard model that for any IND-CCA secure KEM, weak anonymity implies full anonymity, and our reduction is tight not only in success probability and time but also in memory consumption. We then prove in the random oracle model that X-Wing achieves weak anonymity if both X25519 and ML-KEM-768 are weakly anonymous. The former can even be proven without a hardness assumption. Our proof on the weak anonymity of X-Wing does not preserve the memory-tightness of the underlying KEMs. To improve it, we propose a slight variant of X-Wing that preserves memory-tightness. Finally, we improve the existing IND-CCA proof of the original X-Wing by Barbosa et al. using our new memory-tight analysis.

In this work, we investigate the application of Barnes-Wall lattices in post-quantum cryptographic schemes. We survey and analyze several constructions of Barnes-Wall lattices, including subgroup chains, the generalized $k$-ing construction, and connections with Reed-Muller codes, highlighting their equivalence over both $\mathbb{Z}[i]$ and $\mathbb{Z}$. Building on these structural insights, we introduce a new algorithm for efficient sampling from discrete Gaussian distribution on $BW_{2^n}$ lattices. Our approach exploits the $k$-ing and squaring constructions to achieve low-variance sampling, which is particularly relevant for cryptographic applications such as digital signature schemes. We further examine the cryptographic hardness of Lattice Isomorphism Problem (LIP), showing that Barnes-Wall lattices provide inherent resistance to hull-based and other known attacks. Our results on sampling algorithms, combined with existing advances in the cryptanalysis of the LIP, indicate that Barnes-Wall lattices hold strong potential for the design of post-quantum schemes based on the LIP problem.

The multistep solving strategy consists in a divide-and-conquer approach: when a multivariate polynomial system is computationally infeasible to solve directly, one variable is assigned over the elements of the base finite field, and the procedure is recursively applied to the resulting simplified systems. In a previous work by the same authors (among others), this approach proved effective in the algebraic cryptanalysis of the Trivium cipher. In this paper, we present a new formulation of the corresponding algorithm based on a Depth-First Search strategy, along with a novel complexity analysis leveraging tree structures. We also introduce the notion of an ``oracle function'', which is intended to determine whether evaluating a new variable is required to simplify the current polynomial system. This notion allows us to unify all previously proposed variants of the multistep strategy, including the classical hybrid approach, by appropriately selecting the oracle function. Finally, we employ the multistep solving strategy in the cryptanalysis of the NSA's recently introduced low-latency block cipher Aradi, achieving a first full-round algebraic attack that exposes structural features in its symbolic model.

Proposed in EUROCRYPT~2025, \chilow is a family of tweakable block ciphers and a related PRF built on the novel nonlinear $\chichi$ function, designed to enable efficient and secure embedded code encryption. The only key-recovery results of \chilow are from designers which can reach at most 4 out of 8 rounds, which is not enough for a low-latency cipher like \chilow: more cryptanalysis efforts are expected. Considering the low-degree $\chichi$ function, we present three kinds of cube-like attacks on \chilow-32 under both single-tweak and multi-tweak settings, including \begin{itemize} \item[-] a \textit{conditional cube attack} in the multi-tweak setting, which enables full key recovery for 5-round and 6-round instances with time complexities $2^{32}$ and $2^{120}$, data complexities $2^{23.58}$ and $2^{40}$, and negligible memory requirements, respectively. \item[-] a \textit{borderline cube attack} in the multi-tweak setting, which recovers the full key of 5-round \chilow-32 with time, data, and memory complexities of $2^{32}$, $2^{18.58}$, and $2^{33.56}$, respectively. For 6-round \chilow-32, it achieves full key recovery with time, data, and memory complexities of $2^{34}$, $2^{33.58}$, and $2^{54.28}$, respectively. Both attacks are practical. \item [-] an \textit{integral attack} on 7-round \chilow-32 in the single-tweak setting. By combining a 4-round borderline cube with three additional rounds, we reduce the round-key search space from $2^{96}$ to $2^{73}$. Moreover, we present a method to recover the master key based on round-key information, allowing us to recover the master key for 7-round \chilow-32 with a time complexity of $2^{127.78}$. \end{itemize} All of our attacks respect security claims made by the designers. Though our analysis does not compromise the security of the full 8-round \chilow, we hope that our results offer valuable insights into its security properties.

Git services such as GitHub, have been widely used to manage projects and enable collaborations among multiple entities. Just as in messaging and cloud storage, where end-to-end security has been gaining increased attention, such a level of security is also demanded for Git services. Content in the repositories (and the data/code supply-chain facilitated by Git services) could be highly valuable, whereas the threat of system breaches has become routine nowadays. However, existing studies of Git security to date (mostly open source projects) suffer in two ways: they provide only very weak security, and they have a large overhead. In this paper, we initiate the needed study of efficient end-to-end encrypted Git services. Specifically, we formally define the syntax and critical security properties, and then propose two constructions that provably meet those properties. Moreover, our constructions have the important property of platform-compatibility: They are compatible with current Git servers and reserve all basic Git operations, thus can be directly tested and deployed on top of existing platforms. Furthermore, the overhead we achieve is only proportional to the actual difference caused by each edit, instead of the whole file (or even the whole repository) as is the case with existing works. We implemented both constructions and tested them directly on several public GitHub repositories. Our evaluations show (1) the effectiveness of platform-compatibility, and (2) the significant efficiency improvement we got (while provably providing much stronger security than prior ad-hoc treatments).

The sumcheck protocol is a fundamental building block in the design of probabilistic proof systems, and has become a key component of recent work on efficient succinct arguments. We study time-space tradeoffs for the prover of the sumcheck protocol in the streaming model, and provide upper and lower bounds that tightly characterize the efficiency achievable by the prover. $\bullet{}$ For sumcheck claims about a single multilinear polynomial we demonstrate an algorithm that runs in time $O(kN)$ and uses space $O(N^{1/k})$ for any $k \geq 1$. For non-adaptive provers (a class which contains all known sumcheck prover algorithms) we show that this tradeoff is optimal. $\bullet{}$ For sumcheck claims about products of multilinear polynomials, we describe a prover algorithm that runs in time $O(N(\log \log N + k))$ and uses space $O(N^{1/k})$ for any $k \geq 1$. We show that, conditioned on the hardness of a natural problem about multiplication of multilinear polynomials, any ``natural'' prover algorithm that uses space $O(N^{1/2 - \varepsilon})$ for some $\varepsilon > 0$ must run in time $\Omega(N(\log \log N + \log \varepsilon))$. We implement and evaluate the prover algorithm for products of multilinear polynomials. We show that our algorithm consumes up to $120\times$ less memory compare to the linear-time prover algorithm, while incurring a time overhead of less than $2\times$. The foregoing algorithms and lower bounds apply in the interactive proof model. We show that in the polynomial interactive oracle proof model one can in fact design a new protocol that achieves a better time-space tradeoff of $O(N^{1/k})$ space and $O(N(\log^* N + k))$ time for any $k \geq 1$.

We present WOTS-Tree, a stateful hash-based signature scheme for Bitcoin that combines WOTS+ one-time signatures with a binary Merkle tree, supporting up to $2^{21}$ independent signatures per address. The construction instantiates XMSS with parameters specifically optimized for Bitcoin's UTXO model, using a dual hash function design: SHA-256 truncated to 128 bits ($n=16$, $w=256$) for WOTS+ chain evaluations, and full 256-bit SHA-256 for Merkle tree compression. Deployed as dual leaves within BIP-341 Taproot (compatible with the proposed BIP-360 Pay-to-Merkle-Root), the default (hardened) mode provides: (i) a fast-path for single-use UTXOs at 353 bytes, and (ii) a fallback tree for Replace-By-Fee and address reuse at 675 bytes ($K=1{,}024$). For Lightning channels, $K=2^{21}$ yields 1,028-byte witnesses with a 19-second one-time setup. An opt-in compact mode using truncated 128-bit Merkle nodes reduces witnesses to 515--692 bytes at the cost of reduced Merkle binding security ($\approx 60$ bits). WOTS-Tree achieves strict L1 verification bounds of 4,601 hashes ($\approx 0.009$ ms on SHA-NI hardware). The default parameterization provides 115.8-bit classical and 57.9-bit quantum forgery resistance, with the Merkle binding at $\approx 124$ bits, exceeding the WOTS+ forgery bound in both classical and quantum settings. We provide a complete security reduction with concrete bounds, a dual hash instantiation analysis, and a reference implementation with comprehensive test coverage. Default-mode witnesses are $4$--$7\times$ smaller than hypertree variants while aligning naturally with Bitcoin's spend-once transaction model.

Succinct arguments based on interactive oracle proofs (IOPs) have achieved remarkable efficiency improvements and are now widely adopted in applications. State-of-the-art IOPs involve protocols for testing proximity to constrained interleaved linear codes, and enjoy essentially optimal parameters. However, recent IOP constructions provide no privacy guarantees, which remain a must for many applications. We present an IOP of proximity for testing constrained interleaved linear codes that achieves (honest-verifier) zero-knowledge, while incurring a negligible overhead compared to the (non-zero-knowledge) state of the art. In line with recent constructions, our construction satisfies round-by-round knowledge soundness with a straightline extractor and negligible error. We propose a definition of (honest-verifier) zero-knowledge for interactive oracle reductions (IORs) that we prove is compatible with composition, and then obtain our result by constructing and modularly composing several lightweight zero-knowledge IORs. Our key technical contributions are a zero-knowledge sumcheck IOR and a zero-knowledge code-switching IOR that fit the strict efficiency requirements of our setting; these contributions and other technical complications entailed overcoming several challenges with new notions and protocols. Finally, along the way, we highlight the efficiency benefits of high-distance codes obtained from dispersers, which may be of independent interest.

We study the problem of minimizing round complexity in the context of succinct classical argument systems for quantum computation. All prior works either require at least 8 rounds of interaction between the quantum prover and classical verifier, or rely on the idealized quantum random oracle model (QROM). We design: 1. A 4-round public-coin (except for the first message) argument system for batchQMA lan- guages. Our results come in two flavors: (a) Under the post-quantum hardness of functional encryption and learning with errors (LWE), we achieve optimal communication complexity (i.e., all message sizes are independent of batch size). (b) Under the post-quantum hardness of LWE, we achieve optimal communication com- plexity except for the verifier’s first message. 2. A 6-round private-coin argument system for monotone policy batchQMA languages, under the post-quantum hardness of LWE. The communication complexity is independent of the batch size as well as the monotone circuit size. One of our main technical contributions is a new approach to prove soundness without rewind- ing cheating provers. We bring the notion of straight-line partial extractability to argument systems for quantum computation. All previous works crucially relied on rewinding cheating provers, thus needed “state-preserving” succinct arguments of knowledge (AoKs) for NP to prove soundness.

Side-channel attacks (SCAs) represent an important threat for the implementation of cryptographic algorithms. These attacks exploit the information leakage found in the physical magnitudes of hardware devices (e.g. current draw, electromagnetic emanation). Threshold Implementations (TIs) aim to mitigate SCAs by implementing a modified version of the algorithm that operates over randomized shares of its input and intermediate values. This strategy relies on the possibility of splitting the algorithm to be protected into sub-functions that satisfy certain properties about their dependence structure on the randomized shares. Non-complete set coverings (NCSCs) are combinatorial objects that can provide this dependence structure and guide the design of TIs. Given the desired order of protection $d$ and the algebraic degree $t$ of the functions to be implemented, for an NCSC to be useful, its cardinality $r$ should be small and similar to the number of input shares $s$. This work contributes to the study of NCSCs for efficient TIs by finding smaller coverings and proving novel theoretical bounds on their cardinality. We present a new NCSC for the case $t=3,d=2$ that is optimal and NCSCs for the cases $t=3,d=3$ and $t=4,d=2$ whose sizes are close to the lower bounds. We also present new combinatorial properties of these coverings and an algorithm for the search of small NCSCs.

We report on a novel authenticated key-exchange (AKE) protocol where the authentication is achieved entirely by key-encapsulation mechanisms (KEMs). Techniques to achieve AKE with KEMs have been known for some time, but have received renewed attention in a post-quantum world; in contrast to classical cryptography, the data corresponding to the NIST post-quantum KEM standard is a significant save on bandwidth compared to the signature standard. Previous KEM-authenticated AKE protocols are not known to be composable; our protocol offers similar security guarantees, plus composability, while being more efficient in terms of bandwidth compared to non-composable KEM-based AKE protocols, and composable signature-based AKE protocols. Our protocol features a modular design, and a full security proof in the Constructive Cryptography (CC) framework, one of the major composable security frameworks. We also prove the forward secrecy of our protocol, and introduce generic techniques to prove forward secrecy in CC, which may be of independent interest.

Traditional Secure Multi-Party Computation (MPC) requires parties to stay online through the whole computation, which compromises scalability when dealing with large-scale and complex tasks. The notion of fluid MPC, introduced by Choudhuri et al. (Crypto 2021), aims to address this challenge by presenting a dynamic participation model where parties have the flexibility to join and leave as needed. The best-known honest-majority MPC protocol by Bienstock et al. (Crypto 2023) in the fluid setting achieves linear communication complexity, but still incurs a substantially higher communication overhead than MPC in the classical setting. In this paper, we present two concretely efficient fluid MPC protocols in the honest-majority setting. The first, Velora, is an unconditionally secure maximal-fluid MPC protocol, which achieves the lowest communication cost among maximally fluid MPC protocols by introducing a new approach of transferring the output sharings held by the current committee to the next committee. To eliminate the inherent overhead of Velora, we also propose a separation-generation approach for random double sharings and integrate it into the second protocol as Ion. As a trade-off, Ion relaxes the fluidity requirement to the submaximal fluidity, allowing an extra internal communication round for each committee. Both protocols Velora and Ion enable us to extend the ATLAS technique from the classical setting to the fluid setting for further lowering communication overhead. Compared to the best-known fluid MPC protocol, our protocols reduce the communication cost per multiplication gate by a factor of 5.4 ∼ 7.5× (resp., 20.7 ∼ 28×) for semi-honest security (resp., malicious security). Compared to the state-of-the-art ATLAS protocol by Goyal et al. (Crypto 2021) in the classical setting, our semi-honest protocols only introduce a 1 ∼ 1.5× larger communication overhead for securely computing multiplication gates.

Learning problems have become a foundational element for constructing quantum-resistant cryptographic schemes, finding broad application even beyond, such as in Fully Homomorphic Encryption. The increasing complexity of this field, marked by the rise of physical learning problems due to research into side-channel leakage and secure hardware implementations, underscores the urgent need for a more comprehensive analytical framework capable of encompassing these diverse variants. In response, we introduce Learning With Error with Output Dependencies (LWE-OD), a novel learning problem defined by an error distribution that depends on the inner product value and therefore on the key. LWE-OD instances are remarkably versatile, generalizing both established theoretical problems like Learning With Errors (LWE) or Learning With Rounding (LWR), and emerging physical problems such as Learning With Physical Rounding (LWPR). Our core contribution is establishing a reduction from LWE-OD to LWE. This is accomplished by leveraging an intermediate problem, denoted qLWE. Our reduction follows a two-step, simulator-based approach, yielding explicit conditions that guarantee LWE-OD is at least as computationally hard as LWE. While this theorem provides a valuable reduction, it also highlights a crucial distinction among reductions: those that allow explicit calculation of target distributions versus weaker ones with conditional results. To further demonstrate the utility of our framework, we offer new proofs for existing results, specifically the reduction from LWR to LWE and from Learning Parity with Noise with Output Dependencies (LPN-OD) to LPN. This new reduction opens the door for a potential reduction from LWPR to LWE.

The Module Learning With Errors (M-LWE) problem has become a fundamental hardness assumption for lattice-based cryptography. It offers an attractive trade-off between strong robustness guarantees, sometimes directly based on worst-case lattice problems, and efficiency of the subsequent cryptographic primitives. Different flavors of M-LWE have then been introduced towards improving performance. Such variants look at different secret-error distributions and might allow for additional hints on the secret-error vector. Existing hardness results however only cover restricted classes of said distributions, or are tailored to specific leakage models. This lack of generality hinders the design of efficient and versatile cryptographic schemes, as each new distribution or leakage model requires a separate and nontrivial hardness evaluation. In this work, we address this limitation by establishing the hardness of MLWE under general distributions. As a first step, we show that MLWE remains hard when the error vector follows an arbitrary bounded distribution with sufficient entropy, with some restriction on the number of samples. Building on this, we then reduce to the Hermite Normal Form (HNF) where the secret-error vector follows said arbitrary distribution. Overall, our result shows the actual shape of the distribution does not matter, as long as it keeps sufficient entropy. To demonstrate the versatility of our framework, we further analyze a range of leakage scenarios. By examining the residual entropy given the leakage, we show that our results of M-LWE with general distributions encompass various types of leakage. More precisely, we cover exact and approximate linear hints which are widely used in recent cryptographic designs, as well as quadratic, and even non-algebraic forms, some of which were not yet covered by any theoretical hardness guarantees. The generality of our results aims at facilitating future cryptographic designs and security analyses.

Determining whether an arbitrary access structure can be realized by an ideal linear secret sharing scheme is an important research topic. we use linear codes as the main tool to construct matrices $H$ and $G$ over a finite field $\mathbb{F}_q$ for a given access structure $\Gamma_{\min}$, and show that a necessary and sufficient condition for the existence of an ideal linear secret sharing scheme realizing $\Gamma_{\min}$ is that the equation $GH^{\mathsf{T}}=0$ has a solution. If this equation has a solution, then $H$ serves as the parity-check matrix of a linear code that realizes $\Gamma_{\min}$, and $G$ is the corresponding generator matrix. Furthermore, we prove that the result is equivalent to the following statement: there exists an ideal linear code for realizing the $\Gamma_{\min}$ if and only if it is the port of a matroid that is representable over $\mathbb{F}_q$.

Domain-informed deep learning integrates specialized knowledge into deep neural networks through modifications to inputs, architectures, loss functions, or training processes. Such approach is usually employed to improve model performance in low/noisy data regime via domain-specific priors. Side-channel analysis is such a domain and even though straight deep learning has become a powerful tool for profiled side-channel, it still struggles on more complex datasets because of weak signals distributed across many datapoints. Initial attempts at integrating specific knowledge into models have been extremely successful to pushing boundaries of what can be achieved with deep learning. For example, integrating knowledge about the masking scheme in Masure et al provides significant improvements in decreasing the profiling complexity. Marquet et Oswald went further by leveraging redundant features across multiple tasks, such as shared randomness or common masking flow. In this work, we continue the discussion by using belief propagation on a larger graph to guide the learning. We introduce a multi-task learning model that explicitly integrates a factor graph reflecting the algebraic dependencies among intermediates in the computations of Kyber's inverse Number Theoretic Transform (iNTT). Such framework allow the model to learn a joint representation of the related tasks that is mutually beneficial. For the first time, we show that one can perform a belief propagation during training even when one does not have access to the internal randomness, on the masked shares, potentially improving greatly the performances of the attack.

In this paper, we present Interstellar, a novel folding and IVC framework built on a technique we call circuit interpolation, tailored for circuit satisfiability. By incorporating the GKR protocol, our approach avoids commitments to full computation traces and cross-term vectors, requiring instead only commitments to the actual circuit witness and optionally a small subset of intermediate gate values. This substantially reduces the size of the vectors to be committed to in each folding round, which is highly advantageous compared to existing schemes, as vector commitments involve expensive multi-scalar multiplications. We evaluate Interstellar using two representative workloads: product of matrices which models highly parallel computation, and MiMC hash chains which captures highly serialized computation. Our analysis shows that Interstellar achieves 1.59x to 6.74x prover speedup per folding round for matrix multiplication and up to 2.93x speedups for MiMC chains compared to alternative methods. Beyond efficiency, Interstellar is highly flexible. It can be extended to support high-degree and lookup gates, multi-instance folding, and non-uniform IVC, making it well-suited for practical applications such as zkML and zkVM. Finally, we formalize, for the first time, a new notion called collaborative folding/IVC, which allows folding/IVC proof generation with multiple provers holding disjoint private witnesses for the same public statement. This new primitive enables distributed IVC proof generation while preserving witness privacy across folding rounds, making Interstellar a compelling fit for distributed and privacy-sensitive applications.

This paper investigates the algebraic structure of SNOVA, a NIST PQC Round 2 candidate, with a specific focus on the kernel dimension of the wedge map. We employ lifting techniques to transform the public key from the matrix ring $\mathbb{F}_q^{l \times l}$ to an equivalent representation over the extension field $\mathbb{F}_{q^l}$, establishing that the rank of the wedge map is a structural invariant. A key contribution of this work is the derivation of a generating function that explicitly characterizes the wedge map's kernel dimension. This algebraic analysis provides a rigorous understanding of SNOVA's geometry, verifying the safety of specific parameter sets and enabling future refined adjustments to guarantee structural security.

The protection of executable code in embedded systems requires efficient mechanisms that ensure confidentiality and integrity. Belkheyar et al. recently proposed the Authenticated Code Encryption (ACE) framework, with ChiLow-(32 + $\tau$) as the first instantiation of ACE2 at EUROCRYPT 2025. The design of ChiLow-(32 + $\tau$) is based on a 32-bit tweakable block cipher with a quadratic nonlinear layer, known as ChiChi (denoted by $\chi\!\!\chi$), and a nested tweak key schedule optimized for secure code execution under strict query limits. In this work, we study the resistance of ChiLow to integral cryptanalysis. We identify new integral distinguishers in both the single-tweak and related-tweak models. Using these results and a nested strategy to recover all round tweaks, we present a key-recovery attack on 7 out of 8 rounds of ChiLow. The central contribution of our work is that it resolves the challenge of deriving the master key from the recovered round tweaks, an open problem highlighted by the designers and in a recent cryptanalysis by Peng et al. The attack on 7 rounds requires $2^{6.32}$ chosen ciphertexts, has a time complexity of about $2^{121.75}$ encryptions, and requires negligible memory.

The studies by Gohr et al. at Crypto 2019 and subsequent related works have demonstrated that neural networks can offer new insights for cryptanalysis. Building on this insight, we leverage neural networks to learn features closely associated with integral properties and use neural network-derived distinguishers as a benchmark for the automatic search. This approach not only confirms the value of deep learning in feature discovery but also shows that neural-guided insights can improve the performance of classical cryptanalytic methods. Neural networks motivate the development of a more effective framework for identifying integral distinguishers. Comparative results show that existing automated methods, limited by search efficiency and the large search space, often fail to locate optimal distinguishers. In contrast, neural networks can directly identify high-quality integral distinguishers and reveal associated non-random structural features that are typically missed by traditional approaches. Based on these neural-network results, we refine the meet-in-the-middle search framework, thereby improving the trade-off between accuracy and computational cost. Notably, under the assumption of full-state key XOR with independent round keys, the refined framework achieves the known theoretical upper bound for key-independent integral distinguishers on non-standard SKINNY. Integral distinguishers identified by neural networks, whose underlying non-random features are successfully interpreted through Boolean function analysis, are translated into classical forms, enhancing integral key-recovery attacks. In particular, we propose a 16-round key-recovery attack on SKINNY-n-n based on a general integral key-recovery approach, improving the best-known result by two rounds under the single-tweakey setting. Furthermore, we present key-recovery attacks on 18-round SKINNY-n-2n and 20-round SKINNY-n-3n using integral distinguishers under the single-tweakey setting for the first time.

Secret sharing is a foundational cryptographic primitive for sharing keys in distributed systems. In a classical $(n,t)$-threshold setting, it involves a dealer who has a secret, a set of $n$ users to whom shares of the secret are sent, and a threshold $t$ which is the minimum number of shares required to recover the secret. These schemes offer an all-or-nothing security approach where less than $t$ shares reveal no information about the secret. But these guarantees are threatened by side-channel attacks which can leak partial information from each share. Initiated by Benhamouda et al. (Crypto'18), the security of linear secret sharing schemes has been studied for bounded leakage attack models, which assume that the adversary can leak bounded functions of each share. However, this model does not translate into real-world attacks, as physical side-channels are inherently noisy. The $\delta$-noisy channel model, proposed by Prouff and Rivain (Eurocrypt’13), is a general leakage framework which captures the noisy behavior of side-channels. In this work, we study the security of linear secret sharing schemes with $\delta$-noisy leakage, and show bounds on the mutual information (MI) and statistical bias ($\Delta^{\mathrm{TV}}$) security metrics. Our results are based on the Fourier analytical framework, first used by Benhamouda et al. (Crypto'18), adapted to the $\delta$-noisy leakage model. To give security bounds, we introduce a security parameter $\eta\le \min{\{1,2\delta\}}$, determined by the Fourier linear biases of the posterior distributions of the leaked secret shares. Then, the Poisson summation formula enables us to bound the ratio between the observed leakage for some given secret, and leakage under independence as $(1\pm \eta^t)$. This is then used to show a) $(n,t \ge \tau (n+1))$-threshold schemes over $\mathbb{F}_q$ have at most $\mathcal{O}(q^{-t(\gamma+1-1/\tau)})$ leakage, given $\eta \le q^{-\gamma}$; and consequently b) for $(n,n)$-threshold schemes the guessing advantage is at most $(q-1) \cdot \eta^n \le (q-1)\cdot (2 \delta)^n$. This work can be viewed as a next step towards closing the gap between theory and practice in leakage resilient cryptography.

Distributed monotone-policy encryption augments public-key encryption with fine-grained decryption capabilities in a trustless manner. In this scheme, users independently generate a public/private key-pair and post their public key to a public-key directory. Thereafter, anyone can encrypt a message to a set of public keys together with an access policy. Any set of users that satisfies the access policy can decrypt the ciphertext while the message should remain computationally hidden to any unsatisfying set of users. The primary efficiency requirement is succinctness: namely, the size of the ciphertext should be sublinear (or polylogarithmic) in the description length of the policy. Distributed monotone-policy encryption directly generalizes recent trustless cryptographic notions like threshold encryption with silent setup and distributed broadcast encryption. In this work, we show how to construct distributed monotone-policy encryption for Boolean formulas in disjunctive normal form (DNF formulas) that supports an unbounded number of users. Security relies on the decomposed learning with errors (LWE) assumption, a simple and falsifiable lattice assumption, in the random oracle model. Previously, such a scheme was only known from plain witness encryption in the random oracle model. Our scheme has a transparent setup and the ciphertext size is $\mathsf{poly}(\lambda, \log N)$, where $N$ is the number of variables in the DNF formula.

Yao's famous protocol for secure 2-party computation, based on garbled circuits, is well-known to be insecure against an actively corrupt garbler. We introduce a new and extremely simple variant of Yao's protocol that is fully secure against active adversaries, for a certain class of functions that we call conditionally input-revealing. We then show how to use this new protocol as the basis for fuzzy password authenticated key exchange (fuzzy PAKE). In fuzzy PAKE, two parties each hold a low-entropy secret (e.g., a password), and they interact to obtain a secure high-entropy key if and only if the passwords are sufficiently ``close.'' Our new fuzzy PAKE protocol supports completely arbitrary predicates for password ``closeness''. Compared to prior fuzzy PAKE protocols, ours is roughly $2\times$ cheaper in communication, computation, and round complexity.

This paper introduces the structured generic-group model, an extension of Shoup’s generic-group model (from Eurocrypt 1997) to capture algorithms that take advantage of some non-generic structure of the group. We show that any discrete-log algorithm in a group of prime order $q$ that exploits the structure of at most a $\delta$ fraction of group elements, in a way that we precisely define, must run in time $\Omega(\min(\sqrt{q},1/\delta))$. As an application, we prove a tight subexponential-time lower bound against discrete-log algorithms that exploit the multiplicative structure of smooth integers, but that are otherwise generic. This lower bound applies to a broad class of index-calculus algorithms. We prove similar lower bounds against algorithms that exploit the structure of small integers, smooth polynomials, and elliptic-curve points.

The wide adoption of deep neural networks (DNNs) raises the question of how can we equip them with a desired cryptographic functionality (e.g, to decrypt an encrypted input, to verify that this input is authorized, or to embed a secret backdoor which alters the DNN's normal operation). The problem is that cryptographic primitives are typically designed to run on digital computers that use Boolean gates to map sequences of bits to sequences of bits, whereas DNNs are a special type of analog computer that uses linear mappings and ReLUs to map vectors of real numbers to vectors of real numbers. This discrepancy between the discrete and continuous computational models raises two fundamental questions: How can we implement standard cryptographic primitives as DNNs, and whether DNN implementations of secure cryptosystems remain secure in the new setting, in which an attacker can ask the DNN to process a message whose ``bits'' are arbitrary real numbers. In this paper we lay the foundations of this new area of research, defining the meaning of correctness and security for implementations of cryptographic primitives as ReLU-based DNNs. We then show that the natural implementations of block ciphers as DNNs can be broken in linear time by using such nonstandard inputs (this attack was experimentally tested in the case of full round AES-128, and had 100% success rate). Finally, we develop a new method for implementing any desired cryptographic functionality as a standard ReLU-based DNN in a provably secure and correct way. Our novel protective technique has very low overhead (a constant number of additional layers and a linear number of additional neurons), and is completely practical.

Distributed cryptography serves as a cornerstone for building trustless systems, yet existing solutions for distributed policy encryption typically require either a trusted dealer or complex interactive setup protocols. Recent advances have introduced the concept of $silent~setup$, where users independently generate keys and a joint public key is derived deterministically. However, all current silent-setup constructions rely on bilinear pairings, leaving them vulnerable to quantum adversaries. In this work, we present the first distributed monotone-policy encryption scheme with silent setup based on lattices. Our construction supports arbitrary monotone policies represented as Disjunctive Normal Forms (DNFs) and provides a robust, post-quantum foundation for decentralized access control.

Onion routing is a popular and practical approach to anonymous communication, and the subject of a growing body of work on designing efficient schemes with provable anonymity, the strongest notion being full anonymity. However, all prior schemes achieving full anonymity assume a synchronous communication setting, which is unrealistic since real networks suffer from message loss and timing attacks. Recently, Ando, Lysyanskaya, and Upfal (TCC’24) made progress toward the asynchronous setting by introducing bruisable onion encryption and constructing an efficient protocol with the weaker guarantee of differential privacy. In this paper, we construct the first efficient fully anonymous onion routing protocol in the asynchronous setting. To do so, we address two main challenges: (1) we develop the first bruisable onion encryption scheme that does not leak information about the onion’s position on the routing path, and (2) we design an onion routing protocol using this primitive to achieve full anonymity, rather than only differential privacy. Along the way, we also give a new fully anonymous protocol in the synchronous setting, improving the state-of-the-art in both communication and round complexity. Both protocols are secure against an active adversary that corrupts a constant fraction of nodes (up to < 1 in the synchronous case, and < 1/2 in the asynchronous case), and rely on standard cryptographic assumptions (CCA-secure public-key encryption and collision-resistant hash functions).

Multi-signatures enable multiple parties to create a joint signature on the same message. Such schemes aggregate several individual signatures and public keys into a short signature and aggregated public key, and verification is performed on these combined values. Interestingly, all existing notions of unforgeability for multi-signatures are designed with a single honest user in mind, overlooking the multi-user setting that multi-signatures are built for. While multi-user security can be bootstrapped from any single-user secure scheme, the straightforward adoption implies a security loss that is linear in the number of signers n. In this work we therefore start the investigation of multi-signatures with tight multi-user security. We show that none of the existing multi-signatures with tight single-user security seems amendable to the multi-user setting, as all their proofs and design choices exploit the fact that there is only a single honest user. Based on this insight, we then propose two new constructions built from scratch with multi-user security in mind: Skewer-NI, a non-interactive and pairing-based scheme, and Skewer-PF, a pairing-free and two-round construction. We prove both schemes tightly secure under the DDH assumption in the ROM. Both schemes also improve the state-of-the-art in another aspect: they support the feature of key aggregation. Skewer-NI is the first non-interactive tightly secure multi-signature with this feature. In the pairing-free two-round setting, Skewer-PF is the first to combine tight multi-user security with key aggregation where the only prior result, due to Bacho and Wagner (CRYPTO’25), achieved aggregation but only in the single-user case.

We use tropical algebras as platforms for a very efficient digital signature protocol. Security relies on computational hardness of factoring a given tropical matrix in a product of two matrices of given dimensions; this problem is known to be NP-complete. We also offer a secret sharing scheme with an arbitrary access structure where security of the shared secret is based on computational hardness of the same problem.

In this work, we investigate the security assumptions required to prove the adaptive security of threshold signatures. Adaptive security is a strong notion of security that allows an adversary to corrupt parties at any point during the execution of the protocol, and is of practical interest due to recent standardization efforts for threshold schemes. Towards this end, we give two different impossibility results. We begin by formalizing the notion of a key-unique threshold signature scheme, where public keys have a unique correspondence to secret keys and there is an efficient algorithm for checking that public keys are well-formed. Key-uniqueness occurs in many threshold schemes that are compatible with standard, single-party signatures used in practice, such as BLS, ECDSA, and Schnorr signatures. Our first impossibility result demonstrates that it is impossible to prove the adaptive security of any key-unique threshold signature scheme under any non-interactive computational or decisional assumption for a broad class of reductions, in the range ⌊t/ℓ⌋ < t_c ≤ t, where t+1 is the threshold out of n parties, t_c is the number of corrupted parties (polynomially related with the security parameter), and ℓ is a constant. Such assumptions include, but are not limited to, the discrete logarithm (DL), recently introduced circular DL (CDL), computational Diffie-Hellman (CDH), decisional DH (DDH), and q-Strong DH (q-SDH) assumptions. Our second impossibility result applies specifically to key-unique threshold Schnorr signatures, currently an active area of research. We demonstrate that, even under the interactive computational assumptions one-more DL (OMDL), algebraic OMDL (AOMDL) and algebraic one-more CDH (AOMCDH), it is impossible to prove adaptive security for ⌊t/2⌋ < t_c ≤ t in the ROM for a natural class of rewinding reductions. Taken together, our results underscore the difficulty of achieving adaptive security for key-unique threshold signatures, but at the same time, they open a new line of research, by indicating assumptions and properties to aim for when constructing adaptively secure threshold schemes, or informing new attacks.

We develop formal code-based security definitions for blockchain bridges and apply them to several bridge architectures deployed in practice. We derive both traditional pen-and-paper proofs and on the other, automated guarantees against bounded counterexamples. The latter is achieved via bounded model checking of our formally specified properties, implemented in Quint, a specification language and model checker closely related to TLA+. Our definitions are expressed in a precise, code-based variant of the Universal Composition (UC) framework. This enables the modular use of hybrid functionalities—even for property-based definitions—and is essential for bounded model checking, where underlying primitives must be idealized. Accordingly, we idealize and model-check all building blocks used in our protocols. Notably, we formulate a novel UC ideal functionality for Advanced Threshold Signatures (ATS) and modelcheck it for attacks to ensure its robustness

We present One Round "Cheating" Adaptor Signatures (OR- CAS): a novel and efficient construction of adaptor signature schemes from CSI-FiSh. Our protocol improves substantially on existing group action-based schemes: Unlike IAS (Tairi et al., FC 2021), our scheme does not require expensive non-interactive zero-knowledge proofs, and unlike adaptor MCSI-FiSh (Jana et al., CANS 2024) our construction does not require any modification to the underlying digital signature scheme. We prove the protocol’s security under the strong security no- tions of Dai et al. (Indocrypt 2022) and Gerhart et al. (Eurocrypt 2024).

Leftover Hash Lemma (LHL) states that \(\mathbf{X} \cdot \mathbf{v}\) for a Gaussian \(\mathbf{v}\) is an essentially independent Gaussian sample. It has seen numerous applications in cryptography for hiding sensitive distributions of \(\mathbf{v}\). We generalise the Gaussian LHL initially stated over \(\mathbb{Z}\) by Agrawal, Gentry, Halevi, and Sahai (2013) to modules over number fields. Our results have a sub-linear dependency on the degree of the number field and require only polynomial norm growth: \(\lVert\mathbf{v}\rVert/\lVert\mathbf{X}\rVert\). To this end, we also prove when \(\mathbf{X}\) is surjective (assuming the Generalised Riemann Hypothesis) and give bounds on the smoothing parameter of the kernel of \(\mathbf{X}\). We also establish when the resulting distribution is independent of the geometry of \(\mathbf{X}\) and establish the hardness of the \(k\)-SIS and \(k\)-LWE problems over modules (\(k\)-MSIS/\(k\)-MLWE) based on the hardness of SIS and LWE over modules (MSIS/MLWE) respectively, which was assumed without proof in prior works.

Functional commitments (FCs) enable a prover to commit to a message and later produce a succinct proof of its image under any given admissible function. Unlike succinct non-interactive arguments (SNARGs), secure FCs can be realised under falsifiable assumptions in the standard model, making them attractive alternatives when fully algebraic constructions are desired. All known algebraic constructions of FC are either lattice-based or pairing-based. While a lattice-based FC for circuits with almost optimal complexities has been recently achieved [Wee, CRYPTO'25], state-of-the-art pairing-based FCs for bounded-width $w$ [Balbás-Catalano-Fiore-Lai (BCFL), TCC'23] and bounded-size $s$ circuits [Wee-Wu, EUROCRYPT'24] require prohibitive public parameter sizes $O(\lambda w^5)$ and $O(\lambda s^5)$, respectively. In this work, we present a new algebraic pairing-based FC which achieves $O(\lambda w^3)$ public parameter size for bounded-width $w$ and unbounded depth $d$ circuits. The construction preserves all nice properties of BCFL: $O(\lambda)$ commitment size, $O(\lambda d^2)$ proof size, additive homomorphism, efficient verification, and chainability. For bounded-size $s$ circuits, we alternatively obtain $O(\lambda s^3)$ public parameters with $O(\lambda d)$ proofs. At the core of our scheme lies a new chainable FC for quadratic functions with commitments computed with respect to a power basis, as well as techniques for switching between different commitment bases.

Network-agnostic MPC protocols tolerate simultaneously a higher number of corruptions $t_s < n/2$ when the network is synchronous, and a lower number $t_a < n/3$ when the network is asynchronous. As such, they provide strong resilience, irrespective of the type of underlying communication network. We focus on improving the communication complexity of network-agnostic MPC with optimal resilience $2t_s + t_a < n$. In this regime, there are no polynomial-time information-theoretic solutions and current computational protocols (without fully-homomorphic encryption) communicate $O(n^2)$ elements per multiplication gate. In this work, we significantly advance the landscape by introducing the first information-theoretic protocol with quadratic communication per multiplication gate and the first computational protocol with linear communication per multiplication gate based solely on signatures and symmetric-key encryption.

Traceable secret sharing complements traditional schemes by enabling the identification of parties who sell their shares. In the model introduced by Boneh, Partap, and Rotem [CRYPTO’24], a group of corrupted parties generates a reconstruction box $R$ that, given enough valid shares as input, reconstructs the secret. The goal is to trace $R$ back to at least one of the corrupted parties using only black-box access to it. While their work provides efficient constructions for threshold access structures, it does not apply to the general case. In this work, we extend their framework to general access structures and present an information-theoretic traceable scheme supporting them. In the course of our construction, we also contribute to the study of anonymous secret sharing, a notion recently introduced by Bishop et al. [CRYPTO’25], which strengthens classical secret sharing by requiring that shares do not reveal the identities of the parties holding them. We further advance this area by proposing new and stronger definitions, and presenting an anonymous scheme for general access structures that satisfies them.

This work presents the first third-party cryptanalysis of \textsf{Blink}, a recent tweakable block cipher built on the Three-Hash Framework with a long-key design. Leveraging the idea of Superbox, we develop a lightweight theoretical model capturing the value correlations, weak-key conditions, fixed-key probabilities and the local clustering behaviors inside a \textsf{Blink} Superbox when the value spaces are affine. This model is intended as a concrete, easy-to-follow specialization of existing generic frameworks adapted to the structure of \textsf{Blink}. We then build a simple pattern-based automatic tool to search for weak tweak-key differentials. The main results are as follows: For \textsf{Blink-64} with 448-bit key size, we obtain a 10-round distinguisher with probability $2^{-50.42}$ for up to $2^{442}$ weak keys (equivalently $2^{-6}$ of the full key space); For \textsf{Blink-128} with 1024-bit key size, we obtain a 10-round distinguisher with probability $2^{-68.83}$ for up to $2^{1010}$ weak keys (equivalently $2^{-14}$ of the full key space), which can be extended to a 12-round multiple differential distinguisher with probability $2^{-96.83}$. Based on the weak tweak-key distinguisher, we further mount a 13-round key recovery attack on \textsf{Blink-64}, recovering the full 448-bit master key with time complexity $2^{114.02}$ and $2^{56}$ chosen plaintexts. All these distinguishers and key recovery attacks work within the data and time bounds claimed by the designers. And our analysis remains consistent with the security of the full-round design of \textsf{Blink}, while offering additional insight into the edge-case behaviors arising from the tweak-key interaction in \textsf{Blink}, and could be potentially informative for future refinements of tweakable block cipher constructions.

Liquid democracy is a transitive vote delegation process. Previously, the advantages of liquid democracy over direct voting have been studied in settings where there is a ground truth “good” voting outcome. In this work, we analyse liquid democracy in a realistic setting with two opposing factions without a ground truth and under uncertainty. Formally, we consider 𝑛 voters who want to decide on some binary issue by voting. Each voter has a preference in {0, 1} that represents the opinion of the voter on these issues. That is, a voter with preference 0 prefers to vote for option 0. We refer to voters with the same preference as being in the same faction. The goal is for voters in the same faction to cooperatively decide on vote delegation strategies that maximise their probability of winning the election. In this setting, we present a practical distributed algorithm under realistic assumptions to decide on an approximately vote delegation strategy that involves minimal interaction and communication, and under incomplete information about the opposing faction. We then provide a complete analytical characterisation of optimal vote delegation strategies under complete information about the opposing faction. Finally, we show that finding optimal delegation strategies in the general setting is PSPACE-complete.

Interoperation across distributed ledger technology (DLT) networks hinges upon the secure transmission of ledger state from one network to another. This is especially challenging for private networks whose ledger access is limited to enrolled members. Existing approaches rely on a trusted centralized proxy that receives encrypted ledger state of a network, decrypts it, and sends it to members of another network. Though effective, this approach goes against the founding principle of DLT, namely avoiding single points of failure (or single sources of trust). In this paper, we leverage fully-distributed broadcast encryption (FDBE in short) to build a fully decentralized protocol for confidential information-sharing across private networks. Compared to traditional broadcast encryption (BE), FDBE is characterized by distributed setup and key generation, where mutually distrusting parties agree on a BE’s public key without a trusted setup, and securely derive their decryption keys. Given any FDBE, two private networks can securely share information as follows: a sender in one network uses the other network’s FDBE public key to encrypt a message for its members; and the resulting construction is secure in the simplified universal composability framework. To further demonstrate the practicality of our approach, we present the first instantiation of an FDBE that enjoys constant-sized decryption keys and ciphertexts, and evaluate the resulting performances through a reference implementation that considers two private Hyperledger Fabric networks within the Hyperledger Cacti interoperation framework.

Over the past two decades, several works have used (almost) $k$-wise independence as a proxy for pseudorandomness in block ciphers, since it guarantees resistance against broad classes of statistical attacks. For example, even the case $k = 2$ already implies security against differential and linear cryptanalysis. Hoory, Magen, Myers, and Rackoff (ICALP ’04; TCS ’05) formulated an appealing conjecture: if the sequential composition of $T$ independent local randomized permutations is (close to) four-wise independent, then it should also be a pseudorandom permutation. Here, "local" means that each output bit depends on only a constant number of input bits. This conjecture offers a potential strong justification for analyses of block ciphers that establish (almost) $k$-wise independence of this type of constructions. In this work, we disprove the conjecture in full generality by presenting an explicit local randomized permutation whose sequential composition is four-wise independent, but not a pseudorandom permutation. Our counterexample in fact extends to $k$-wise independence for any constant $k$.

In this paper, we revisit the recent Pegasis algorithm that computes an effective group action of the class group of any imaginary quadratic order $R$ on a set of supersingular elliptic curves primitively oriented by $R$. Although Pegasis was the first algorithm showing the practicality of computing unrestricted class group actions at higher security levels, it is complicated and prone to failures, which leads to many rerandomizations. We present a new algorithm, qt-Pegasis, which is much simpler, but at the same time faster and removes the need for rerandomization of the ideal we want to act with, since it never fails. It leverages the main technique of the recent Qlapoti approach. However, Qlapoti solves a norm equation in a quaternion algebra, which corresponds to the full endomorphism ring of a supersingular elliptic curve. We show that the algorithm still applies in the quadratic setting, by embedding the quadratic ideal into a quaternion ideal using a technique similar to the one applied in KLaPoTi. This way, we can reinterpret the output of Qlapoti as four equivalent quadratic ideals, instead of two equivalent quaternion ideals. We then show how to construct a Clapoti-like diagram in dimension $2$, which embeds the action of the ideal in a $4$-dimensional isogeny. We implemented our qt-Pegasis algorithm in SageMath for the CSURF group action, and we achieve a speedup over Pegasis of $1.8\times$ for the 500-bit parameters and $2.6\times$ for the 4000-bit parameters.

Byzantine Agreement is a fundamental primitive in cryptography and distributed computing, and minimizing its round complexity is of paramount importance. The seminal works of Karlin and Yao [Manuscript'84] and Chor, Merritt and Shmoys [JACM'89] showed that any randomized $r$-round protocol must fail with probability at least $(c\cdot r)^{-r}$, for some constant $c$, when the number of corruptions is linear in the number of parties, $t = \theta(n)$. The work of Ghinea, Goyal and Liu-Zhang [Eurocrypt'22] introduced the first \emph{round-optimal BA} protocol matching this lower bound. However, the protocol requires a trusted setup for unique threshold signatures and random oracles. In this work, we present the first round-optimal BA protocols without trusted setup: a protocol for $t<n/3$ with statistical security, and a protocol for $t<(1-\epsilon)n/2$ with any constant $\epsilon > 0$, assuming a bulletin-board PKI for signatures.

In this paper we introduce a rank $2$ lattice over a polynomial ring arising from the public key of the BIKE cryptosystem. The secret key is a sparse vector in this lattice. We study properties of this lattice and generalize the recovery of weak keys from "Weak keys for the quasi-cyclic MDPC public key encryption scheme". In particular, we show that they implicitly solved a shortest vector problem in the lattice we constructed. Rather than finding only a shortest vector, we obtain a reduced basis of the lattice which makes it possible to check for more weak keys.

The two groups $\mathbb{G}_1$ and $\mathbb{G}_2$ on pairing-friendly curves typically have nontrivial cofactors, which may give rise to security vulnerabilities (e.g., small subgroup attacks) in pairing-based protocols. In order to avoid the pitfalls of cofactors, it is necessary to perform subgroup membership testing. Previous testing methods for such curves relied on efficiently computable endomorphisms. In 2023, Koshelev introduced a novel technique of subgroup membership testing for a list of non-pairing-friendly curves, requiring at most two small Tate pairings. In fact, this technique can also be applied to certain pairing-friendly curves, such as those from the BLS and BW13 families. In this paper, we revisit Koshelev's method and propose simplified formulas for computing the two Tate pairings. Compared to the original formulas, ours reduce both the number of Miller's iterations and the storage requirements. Moreover, we provide a high-speed software implementation on a 64-bit processor. Our experimental results show that the new method outperforms the state-of-the-art one by up to $62.0\%$ and $41.2\%$ on for singular $\mathbb{G}_1$ membership testing on the BW13-310 and BLS48-575 curves, respectively. When precomputation is utilized, the improvements increase to $110.6\%$ and $74.4\%$ on the two curves, respectively.

A vast body of work studies how to build a pseudorandom function (PRF) from a pseudorandom permutation (PRP) with beyond-the-birthday-bound (BBB) security. Often, such constructions are also expected to offer some security in keyless settings, for example in the context of committing security or to substitute a parallelizable short-input random oracle (RO) if used in counter mode. This has spurred several works on keyless variants of PRP-to-PRF constructions. However, recent works (Gunsing et al., CRYPTO 2022, 2023) reveal flaws in almost all existing proofs, painting a grim picture. This paper clarifies the situation with an in-depth analysis of RP-based short-input RF constructions. First, we categorize all two-call short-input/output RP-to-RF constructions and evaluate their indifferentiability level. We introduce the "chaining attack'', a powerful, widely applicable differentiability attack. When applied to the sum of a permutation and its inverse, it invalidates an earlier result (Dodis et al., EUROCRYPT 2008). On the positive side, we show that only the Sum Of Permutations and Encrypted Davies-Meyer Dual, when instantiated with independent permutations, achieve BBB security and could potentially yield a parallelizable short-input RO. Second, we study the indifferentiability of expanding RP-to-RF constructions and show that $\mathtt{XORP}_w$, the core PRF underlying $\textsf{CENC}$, achieves BBB security. As side effects, we obtain a simplified proof of indifferentiability for Sum of Permutations, and the committing security of $\textsf{CENC}$.

Masking typically relies on fresh online randomness to prevent higher-order side-channel leakage, which is costly to generate on constrained devices. We study the extreme setting of deterministic masking, where a circuit can only recycle the entropy already present in the input sharing, and we address the key obstacle of building nonlinear gadgets that are both higher-order secure and uniform. Our main tool is a share-clustering framework inspired by finite affine geometry, which for $n=s^2$ shares (with $s$ a prime power) yields structured families of clusters with tightly controlled overlaps. Using these clusters, we construct deterministic multiplication gadgets over $\mathbb{F}_{2^u}$: a first gadget, $\mathbb{S}\mathsf{Mul\text{-}DN}$, achieves $(d=s-1)$-order security in the glitch-extended probing model, and a second gadget, $\mathbb{S}\mathsf{Mul\text{-}DU}$, restores output uniformity by adding a deterministically generated zero-sharing—without consuming any online randomness. Finally, leveraging a diffusion-based composition rule for bricklayer ciphers, we implement a fully deterministic third-order masking of Ascon in software under the standard probing model. Experiments on a Cortex-M4 target (ChipWhisperer) show no third-order leakage detected by Welch $t$-tests in our measurement setting over up to $2\times 10^6$ traces.

The Shortest Vector problem (SVP) is the most important problem in lattice-based cryptanalysis. There is currently a gap in the understanding of this problem with respect to its worst-case complexity and its average-case behaviour. For instance, SVP on an n-dimensional lattice has worst-case complexity $2^{n+o(n)}$ [ADRS15]. However, in practice, people rely on heuristic (unproven) sieving algorithms of time complexity $2^{0.292n+o(n)}$ [BDGL16] to assess the security of lattice-based cryptography schemes. Those heuristic algorithms are experimentally verified for lattices used in cryptography, which are usually random in some way. In this paper, we try to bridge the gap between worst-case and heuristic algorithms. Using the formalism of random real lattices developed by Siegel, we show a tighter upper bound on an important lattice parameter called the smoothing parameter that applies to almost all random lattices. Using a known discrete Gaussian sampler at the smoothing parameter, we can then directly sample short vectors. This allows us to provably solve an approximation version of the SVP on almost all random lattices with a small constant approximation factor $1.123$, in time $2^{n/2+o(n)}$. With further analysis, we can provably solve the exact SVP in time $2^{0.63269n+o(n)}$ on most random lattices as well. We also provide a smooth time approximation factor tradeoff between these two cases. All our algorithms work in space $2^{n/2+o(n)}$.

The Multidimensional Approximate Agreement problem ($D$-AA) considers a setting with $n$ parties with inputs in $\mathbb{R}^D$. Out of the $n$ parties, up to $t$ may be byzantine (malicious). The goal is for the honest parties to obtain $\varepsilon$-close outputs that lie in the honest inputs' convex hull. While tight bounds on the resilience of $D$-AA have been found for the purely synchronous and asynchronous models, this is still an open question for the network-agnostic model. Here, the type of network is not known a priori: it may be synchronous, and then the number of byzantine parties is up to $t_s$, or asynchronous, and then the number of byzantine parties is up to $t_a \leq t_s$. In this model, it is known that $n > (D + 1) \cdot t_s + t_a$ is sufficient for deterministic protocols [GLW, SPAA'23], tight for $D = 1$ [GLW, PODC'22], while $n > \max\{(D + 1) \cdot t_s, t_s + (D + 1) \cdot t_a\}$ is tight for randomized protocols concerned with exact agreement [CGWW, DISC'24]. In this work, we establish that, for $D > 1$ the condition $n > \max\{(D + 1) \cdot t_s, t_s + (D + 1) \cdot t_a\}$ is tight for deterministic protocols as well. We identify that the gap in prior deterministic protocols is not geometric, but stems from an asymmetry in the communication primitive that produces parties' "views". The core technical contribution of our work is hence a strengthened network-agnostic Gather primitive that enforces a global structural property on the number of values received by honest parties, eliminating the problematic asymmetry - so that standard safe-area geometric convergence arguments apply under the optimal thresholds.

We define and analyze the Leveled Isogeny Problem with Hints (LIPH), which is a generalization of the Isogeny Problem with Level Structure first introduced by De Feo, Fuoutsa and Panny at EUROCRYPT'24. In a LIPH instance we are tasked to recover a secret isogeny \(\varphi\) given masked torsion point images \(M\cdot(\varphi(P),\varphi(Q))^\top\) for some \((P,Q)\) of order \(N\) and unknown \(M\in GL_2(N)\). Additionally, we are provided a \emph{hint} on \( M \), revealing some bits of its entries. Instances of LIPH occur naturally in the case of modern isogeny-based key exchanges that use masked torsion points as part of their public key, when additionally some parts of the masking matrix \( M \) are revealed due to, for instance, a side-channel attack. We provide efficient algorithms that solve various instances of LIPH, leading to efficient \emph{partial key recovery attacks} in practice. More specifically, we present Coppersmith-type attacks that are able to recover an M-SIDH/POK\'E secret key given \(50\%\) (resp. \(86\%\)) of the most-significant bits of an entry of \( M \), and a FESTA secret key given the 67\% of the most-significant bits of \( M \). In the case of FESTA we also present a tailored combinatorial attack running in subexponential time $O(2^{\sqrt{n}})$ with probability of $84\%$ when $50\%$ of the bits of $M$ leak at random.

Cryptographic group actions provide a basis for simple post-quantum generalizations of many cryptographic protocols based on the discrete logarithm problem (DLP). However, many advanced group action-based protocols do not solely rely on the core group action problem (the so called vectorization problem), but also on variants of this problem, to either improve efficiency or enable new functionalities. For example, the security of the CSI-SharK threshold signature protocol relies on the hardness of the Vectorization Problem with Shifted Inputs where (in DLP formalism) the adversary not only receives g and g^x, but also g^(x^c) for multiple known values of c. A natural open question is whether the additional data allows adversaries to solve the underlying problem more efficiently. We revisit the concrete quantum security of this problem. We start from a quantum multiple hidden shift algorithm of Childs and van Dam, which to the best of our knowledge was never applied in cryptography before. We describe and analyze a variant of this algorithm, and we specify and analyze all its subroutines to provide concrete complexity estimates. We then apply our analysis to the CSI-SharK protocol. In prior analyses based on Kuperberg’s algorithms, group action evaluations contributed to a significant part of the overall T-gate cost. For CSI-SharK’s suggested parameters, our new approach requires significantly fewer calls to the group action evaluation subroutine, leading to significant complexity improvements overall. We describe two instances of our approach, one minimizing the T-gate complexity, and the other one keeping qubit requirements small, both of them resulting in significant complexity improvements over previous works. More generally, we quantify the quantum security degradation resulting from additional published data in the CSI-SharK protocol.

The protection of executable code in embedded systems requires efficient mechanisms that ensure confidentiality and integrity. Belkheyar \emph{et al.} recently proposed the Authenticated Code Encryption (ACE) framework, with \chilow as the first ACE-2 instantiation at EUROCRYPT~2025. \chilow-(32 + $\tau$) is a 32-bit tweakable block cipher combined with a pseudorandom function, featuring quadratic nonlinear layers called ChiChi (\dchi) and a nested tweak/key schedule optimized for low-latency \emph{decryptions} in secure code execution under strict query limits. In this paper, we exploit the algebraic structure of \dchi and study the resistance of \chilow-(32 + $\tau$) to cube-like and integral cryptanalysis in single- and multiple-tweak settings. In the multiple-tweak setting, we present conditional attacks that can recover the full key for 5-round \chilow-(32 + $\tau$) with practical complexity, and extend the analysis to 6 rounds at a still non-trivial but purely theoretical cost below brute force. We additionally construct borderline cube attacks on 5- and 6-round \chilow-(32 + $\tau$), each capable of recovering the full key with practical complexity. Specifically, we recover the full key for 5-round \chilow-(32 + $\tau$) using $2^{32}$ decryptions, $2^{18.58}$ chosen ciphertext data, and $2^{33.56}$ bits of memory, and for 6-round \chilow-(32 + $\tau$) using $2^{34}$ decryptions, $2^{33.58}$ chosen ciphertext data, and $2^{54.28}$ bits of memory. We then focus on integral cryptanalysis and the challenge of extending the analysis to 7 rounds. We identify integral distinguishers in the single- and multiple-tweak models and extend suitable 2-round and 3-round integral distinguishers to build a 7-round attack. We present a nested strategy to recover all round tweaks and tackle the problem of deriving the master key from round-tweak and key information. Our key-recovery method exploits high-degree monomials that arise in the integral key-recovery phase to reduce the average number of guessed key bits and hence reduce the time complexity. As a result, we mount a 7-round key-recovery attack on \chilow-(32 + $\tau$) that requires $2^{6.32}$ chosen ciphertext data, has a time complexity of about $2^{108.55}$ encryptions, and needs negligible memory. Notably, all our attacks remain consistent with the security claims of the design.

Zero-knowledge simulators, initially developed for proving the security of proof systems, turned out to be also useful in constructing advanced protocols from simple three-move interactive proofs. However, in the context of multi-round public-coin protocols, the interfaces of these auxiliary algorithms become more complex, introducing a range of technical challenges that hinder the generalization of these constructions. We introduce a framework to enhance the usability of zero-knowledge simulators in multi-round argument systems for protocol designs. Critical-round zero-knowledge relies on the ability to perform complete zero-knowledge simulations by knowing the challenge of just one specific round in advance. We show that these notions are satisfied by diverse protocols based on MPC-in-the-Head, interactive oracle proofs, and split-and-fold arguments. We demonstrate the usefulness of the critical round framework by constructing proofs of partial knowledge (Cramer, Damgård, and Schoenmakers, CRYPTO’94) and trapdoor commitments (Damgård, CRYPTO’89) from critical-round multi-round proofs.

Ring signatures are one of the crucial cryptographic primitives used in the design of privacy-preserving systems. Such a signature scheme allows a signer to anonymously sign a message on behalf of a spontaneously formed group. It not only ensures the authenticity of the message but also conceals the true signer within the group. An important extension of ring signatures is linkable ring signatures, which prevent a signer from signing twice without being detected (under some constraints). Linkable ring signatures offer advantages in applications where full anonymity might jeopardise the intended purpose, such as privacy-oriented cryptocurrencies like Monero. In this work, we introduce post-quantum ring signature (DualRing-PRF) and linkable ring signature (DualRingL-PRF) schemes whose security solely rely on symmetric-key primitives (namely, Legendre PRF and power residue PRF). Our construction of the ring signature departs from previous approaches with similar security assumptions, offering the most competitive signature sizes for small and medium-sized rings. In particular, for a ring size of 16, DualRing-PRF has a communication overhead 1.4 times smaller than the state-of-the-art scheme proposed by Goel et al. (PETS’21). Furthermore, we demonstrate the extension of DualRing-PRF to incorporate linkability and non-slanderability. Compared to the existing one-time traceable ring signature (a variant of linkable ring signature) by Scafuro and Zhang (ESORICS’21), our construction supports many-time signing and achieves significantly smaller signature sizes when ring size exceeds 16. This advantage becomes more pronounced as the ring size increases.

Fully Homomorphic Encryption (FHE) offers strong cryptographic guarantees for secure outsourced computation, yet the performance of modern schemes like TFHE remains a barrier for complex applications. Existing TFHE approaches relying on programmable bootstrapping (PBS) are inefficient for large circuits, as they are limited to evaluating small (3-4 bit) lookup tables (LUTs). Our work introduces a novel compiler framework that overcomes this limitation by integrating circuit bootstrapping (CBS) and vertical packing (VP) to enable the evaluation of circuits composed of LUTs up to 12 bits. Our framework, built upon MLIR, introduces new dialects for CBS and VP and leverages Yosys for circuit synthesis, automating the translation from high-level programs to optimized TFHE circuits. Furthermore, we propose bespoke optimization passes that combine shared LUTs to minimize the overall cryptographic operations required. Experimental results demonstrate that our CBS-based design achieves execution times several times faster than the baseline PBS-only approach, highlighting the practical benefits of combining CBS and VP with compiler-driven circuit-level optimizations.

First, we correct certain omissions in the literature on the complexity analysis of Crossbred and give a full analysis of this algorithm. Secondly, we propose a criterion to reduce the number of polynomials generated in the preprocessing step for a set of admissible parameters $D$, $d$ and $k$, whenever this step of the algorithm produces more polynomials than necessary. We conclude by applying this criterion to the security of MQOM.

Non-interactive key exchange (NIKE) is a fundamental but much-overlooked cryptographic primitive. It appears as a major contribution in the ground-breaking paper of Diffie and Hellman, but NIKE has remained largely unstudied since then. In this paper, we provide different security models for this primitive and explore the relationships between them. We then give constructions for secure NIKE in the Random Oracle Model based on the hardness of factoring and in the standard model based on the hardness of a variant of the decisional Bilinear Diffie Hellman Problem for asymmetric pairings. We also study the relationship between NIKE and public key encryption (PKE), showing that a secure NIKE scheme can be generically converted into an IND-CCA secure PKE scheme. This conversion also illustrates the fundamental nature of NIKE in public key cryptography.