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.

Data Availability Sampling (DAS) enables light clients to probabilistically verify that a large published object remains retrievable by sampling a small number of coded symbols and checking consistency. Most existing DAS designs are predicated on MDS-style global recovery thresholds and therefore yield an essentially binary availability signal: either sufficient evidence accumulates to enable global reconstruction, or it does not. In this work we introduce Locally Recoverable Data Availability Sampling (LR-DAS), which leverages locally recoverable codes with disjoint recovery groups to provide graded availability evidence. A verifier sequentially certifies groups: once it has verified $r$ distinct openings in a group, it can reconstruct the entire group locally and monotonically increase a certified availability fraction. The central cryptographic challenge is preventing splicing attacks, where an adversary mixes locally consistent views that do not arise from a single global codeword. We define locality-aware erasure-code commitments that formalize position binding, local binding, and an explicit local-global consistency requirement, and we give a construction that enforces local-global consistency using a single out-of-domain algebraic linking check per certified group. We prove graded soundness via overshoot bounds that decompose into a sampling term and a negligible cryptographic failure term, covering both missing-groups and missing-fraction withholding patterns. We provide two concrete instantiations: a succinct pairing-based realization and a transparent realization based on low-degree/proximity testing, and we evaluate the resulting trade-offs against representative DAS and repair-oriented approaches.

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.

We present a fully homomorphic encryption scheme which natively supports arithmetic and logical operations over large ``machine words'', namely plaintexts of the form $\mathbb{Z}_{2^n}$ (e.g.\ $n=64$). Our scheme builds on the well-known BGV framework, but deviates in the selection of number field and in the encoding of messages. This allows us to support large message spaces with only modest effect on the noise growth. Arithmetic operations (modulo $2^n$) are supported natively similarly to BGV-style FHE schemes, and we present an efficient bootstrapping procedure for our scheme. Our bootstrapping algorithm has the feature that along the way it decomposes our machine word into bits, so that during bootstrapping it is possible to perform logical operations (essentially addressing each bit in the message independently). This means that during a single bootstrapping cycle we can perform logical operations on $n$ bits. For example, a ``greater than'' operation (if $x> y$ output $1$, otherwise $0$), only requires a single subtraction and a single bootstrapping cycle. Along the way we present a number of new tools and techniques, such as a generalization of the BGV modulus switching technique to a setting where the plaintext and ciphertext moduli are ideals (and not numbers).

Is it possible to publicly certify that a string was sampled from a high min-entropy distribution? Certified randomness protocols, such as Brakerski et al. (FOCS 2018) enable private certification—Alice can convince Bob—but it does not yield public certification. We construct a certified min-entropy scheme with the following properties: (1) public certification, so Alice can convince Bob, Charlie, and Dave; (2) all prover–verifier communication is classical; (3) transferability—if Bob has already been convinced, he can subsequently convince Eve and Frank; and (4) classical verification—Grace can be convinced even without a quantum computer, at the cost of losing transferability. Assuming quantum one-shot signatures (and variants), we construct quantum fire with new properties and use it to obtain our publicly certifiable min-entropy scheme. Both primitives can be instantiated from sub-exponential iO and LWE, and our quantum fire scheme is the first standard-model construction of quantum fire.

Digital identity wallets are currently being developed around the globe, aiming to provide user-centric and secure authentication. Realizing this in a privacy-preserving manner is paramount, and even mandated in Europe which is developing the European Digital Identity Wallet with planned release in 2026. Current proposals to build these wallets are based on classic signature schemes such as ECDSA, but would benefit greatly from the use of anonymous credentials. Thus, there is currently a strong interest in developing the necessary standards to bring these cryptographic concepts into the real world. This work aims to inform ongoing standardization efforts by providing an overview of the mostprominent solutions, and the remaining open challenges. We split our overview among two fundamental architectural approaches: (1) dedicated multi-message signature schemes that allow for efficient ZKPs, and (2) general-purpose ZKPs used on top of legacy ECDSA. We also provide a comprehensive summary of the broad feature set that anonymous credentials can provide for identity wallets, in order to demonstrate that upgrading to these systems is a worthwhile endeavor and help to design standards that can leverage the rich existing body of work.

Amutha and Perumal recently proposed a two-party key exchange protocol based on \(\alpha\)-\(v\)-\(w\)-duo circulant matrices over the max-plus semiring, claiming resistance to known tropical attacks and suitability for IoT environments. This paper presents a complete cryptanalysis of this protocol. We uncover a fundamental structural weakness: the construction imposes an affine parameterization on the secret matrices, reducing each matrix to a single integer parameter. Consequently, the public messages become simple shifts of a publicly computable matrix, and the session key reduces to a constant shift of another public matrix. An eavesdropper can recover the shared secret in constant time after a one-time precomputation. The attack is deterministic, succeeds with probability 1, and requires only passive observation. We verify the attack on the authors' own example.

In this paper, we introduce a novel framework for meet-in-the-middle (MITM) attacks on ARX designs, termed \textit{dual-syncopation} MITM attack, which formalizes a compact, rule-based language for tracking deterministic and non-deterministic information for two independent propagations through ARX operations. The language provides an uniform abstraction for previous techniques, e.g., initial structure, partial matching, partial-fixing, and naturally supports automation. With the language, we additionally encode new technical insights that is not covered in literature and build an efficient automatic search tool for MITM attacks on ARX designs that can be fully optimized within hours. As a result, we obtain the first preimage attacks on 46- and 47-step SHA-256, extending the previous record of 45 steps by two steps. For SHA-512, we present the first preimage attack on 51 steps, extending the prior record of 50 steps by one step. In addition, we provide a collection of improved preimage attacks on 43-, 44-, and 45-step SHA-256; 46-, 47-, 48-, 49-, and 50-step SHA-512; as well as full-step MD5. The proposed attacks can be converted to free-start collision attacks with the technique proposed by Li, Isobe, and Shibutani at FSE 2012. Our results mark the first improvements on theoretical attacks on SHA-2 in a decade and push the boundary of cryptanalysis of ARX designs.

We present a novel analysis of a quantum algorithm computing the S-unit group for a number field from Eisenträger et al. [EHKS14a] and Biasse and Song [BS16]. We prove that this quantum algorithm runs within polynomial time, where we explicitly quantify the polynomials of the quantum gate and memory complexity (under GRH). We do so by carefully analyzing an implementation of an Continuous Hidden Subgroup Problem (CHSP) oracle function whose period is the (logarithm of the) S-unit group, and provide it to an CHSP-solving algorithm as in [BDF19]. Our analysis is novel due to minimizing the use of the quantum memory-inefficient LLL-reduction, by resorting to strategically chosen precomputations of approximations of high powers of prime ideals. Additionally, we provide a new quantum algorithm computing a discrete Gaussian superposition analogue of the GPV algorithm by Gentry et al. [GPV08]. Lastly, we include a full and rigorous numerical analysis of all parts of the oracle-function computing algorithm, allowing to use fixed-point precision arithmetic and thus to precisely quantify the run-time and memory.

In 2006 de Graaf et al. devised a Lie-algebra-based strategy for finding a linear transformation $T \in PGL_{N+1}(\mathbb{Q})$ connecting two linearly equivalent projective varieties $X, X' \subseteq \mathbb{P}^N$ over $\mathbb{Q}$. The method succeeds for several families of "classical" varieties such as Veronese varieties, which have large automorphism groups. In this paper, we study the Lie algebra method over finite fields, which comes with new technicalities when compared to $\mathbb{Q}$ due to, e.g., the characteristic being positive. Concretely, we make the method work for Veronese varieties of dimension $r \geq 2$ and (heuristically) for secant varieties of Grassmannians of planes. This leads to classical polynomial-time attacks against two candidate-post-quantum key exchange protocols based on disguised Veronese surfaces and threefolds, which were recently proposed by Alzati et al., as well as a digital signature scheme based on secant varieties of Grassmannians of planes due to Di Tullio and Gyawali. We provide an implementation in Magma.

Zero-knowledge proofs allow to encode a computation so that it can be verified without revealing any additional information beyond its correctness. In this work we focus on proofs that are statistically sound meaning that even an unbounded prover cannot make the verifier accept a false statement, except with negligible probability, and computationally zero-knowledge. The seminal result of Goldreich, Micali and Wigderson (CRYPTO 1986) shows that, assuming the existence of a one-way function, such zero-knowledge proofs exist for all languages in NP. Some of the early protocols, such as that of GMW, have a large polynomial overhead in communication compared to the original NP witness. A line of works has shown that in many cases this communication overhead can be avoided. Most recently, Athamnah et al. (TCC 2024) constructed zero-knowledge proofs for all bounded-depth NP relations, where the communication complexity is only larger by an additive factor than the original NP witness. The main caveat of their result is that the protocol makes a non-blackbox use of the one-way function. In this work we show that such succinct zero-knowledge proofs exist for the same class of NP relations, where the protocol makes only a blackbox use of a one-way function. Our protocol achieves a negligible soundness error, in contrast to recent works which can achieve, at best, an inverse polynomial error.

Goldreich's pseudorandom generators (PRGs) with constant locality admit highly parallel implementations, yet the concrete security of instantiations based on the $\mathsf{XOR}\text{-}\mathsf{THR}$ predicate has remained unclear. In this work, we present novel seed recovery attacks on Goldreich's PRGs instantiated on $\mathsf{XOR}\text{-}\mathsf{THR}$ predicates with $m=n^s$, where $m$ and $n$ are the length of output and input, respectively. By partitioning the output bits into groups according to common input bits, high-biased noisy equations can be derived for the group whose common input bits are all 1s (or all 0s). Leveraging two solvers tailored to these equations, we achieve the seed recovery attacks, which needs roughly $2^{n(1-\log_2{(1 + \frac{2s}{\sqrt{2\pi (b-s)}})})}$ calls to Gaussian elimination when the input length of the $\mathsf{THR}$ predicate $b\geq (n-s)^{1/s}+s-1$ with small stretch $s$. Applying our attack to the $\mathsf{XOR}\text{-}\mathsf{MAJ}$ challenges in STOC 2016 yields complexity \(2^{\,n\!\left(1-\log_{2}\!\left(1+\sqrt{\frac{s}{18\pi}}\right)\right)} \le 2^{0.82n}\), i.e., at least a \(2^{0.18n}\) speedup over exhaustive search for any stretch \(s>1\). We also deploy our attack on an instance used in the construction of silent oblivious transfer protocols (Eurocrypt 2024) with \(n = 256\). This attack is capable of breaking the instance using approximately \(2^{31.3}\) calls to Gaussian elimination over 244 variables. We successfully implemented the attack on a cluster of 14 CPU cores, recovering the seed in 71 hours, demonstrating the attack's efficiency. Beyond PRGs, with appropriate adaptations our method extends to FiLIP stream ciphers instantiated with \mathsf{THR}-related predicates. Our evaluation indicates that most FiLIP instances do not meet their claimed security. For instance, the configuration \(\mathsf{XOR}_{100}\text{-}\mathsf{THR}_{11,22}\text{-}\mathsf{THR}_{11,22}\) is broken in about \(2^{59}\) calls to Gaussian elimination over 357 variables despite a 397-bit key and a claimed 80-bit security level.

This paper introduces {\em truncated inner $c$-differential cryptanalysis}, a novel technique that for the first time enables the practical application of $c$-differential uniformity to block ciphers. While Ellingsen et al. (IEEE Trans. Inf. Theory, 2020) established the notion of $c$-differential uniformity by analyzing the equation $F(x\oplus a) \oplus cF(x) = b$, a key challenge remained: the outer multiplication by $c$ disrupts the structural properties essential for block cipher analysis, particularly key addition. We resolve this challenge by developing an \emph{inner} $c$-differential approach where multiplication by $c$ affects the input: $(F(cx\oplus a), F(x))$, thereby going back to the original idea of Borisov et al. (FSE, 2002). We prove that the inner $c$-differential uniformity of a function $F$ equals the outer $c$-differential uniformity of $F^{-1}$, establishing a fundamental duality. This modification preserves cipher structure while enabling practical cryptanalytic applications. Our main contribution is a comprehensive multi-faceted statistical-computational methodology, implementing truncated $c$-differential analysis against a 9-round Kuznyechik variant without initial key whitening (which preserves the essential $(cx \oplus a, x)$ differential structure required for our analysis). Through extensive computational analysis involving millions of differential pairs, we demonstrate statistically significant non-randomness across all tested round counts. For the full 9-round cipher, we identify multiple configurations triggering critical security alerts, with bias ratios reaching $1.7\times$ and corrected p-values as low as $1.85 \times 10^{-3}$, suggesting insufficient security margin against this new attack vector. The data complexity of our attack is about $2^{33}$ chosen plaintext pairs, time complexity $2^{34}$ and (negligible) memory complexity $2^{16}$. This represents the first practical distinguisher against a full 9-round (and reduced rounds) Kuznyechik variant.

This paper studies the concrete security of BBS signatures (Boneh, Boyen, Shacham, CRYPTO '04; Camenisch and Lysyanskaya, CRYPTO '04), a popular algebraic construction of digital signatures which underlies practical privacy-preserving authentication systems and is undergoing standardization by the W3C and IRTF. Sch\"age (Journal of Cryptology '15) gave a tight standard-model security proof under the $q$-SDH assumption for a less efficient variant of the scheme, called BBS+--here, $q$ is the number of issued signatures. In contrast, the security proof for BBS (Tessaro and Zhu, EUROCRYPT '23), also under the $q$-SDH assumption, is \emph{not} tight. Nonetheless, this recent proof shifted both standardization and industry adoption towards the more efficient BBS, instead of BBS+, and for this reason, it is important to understand whether this tightness gap is inherent. Recent cryptanalysis by Chairattana-Apirom and Tessaro (ASIACRYPT '25) also shows that a tight reduction to $q$-SDH is the best we can hope for. This paper closes this gap in two different ways. On the positive end, we show a novel tight reduction for BBS in the case where each message is signed at most once--this case covers in particular the common practical use case which derandomizes signing. On the negative end, we use a meta-reduction argument to prove that if we allow generating multiple signatures for the same message, then {\em no} algebraic reduction to $q$-SDH (and its variants) can be tight.

We introduce HyperNova, a new recursive argument for proving incremental computations whose steps are expressed with CCS (Setty et al. ePrint 2023/552), a customizable constraint system that simultaneously generalizes Plonkish, R1CS, and AIR without overheads. HyperNova makes four contributions, each resolving a major problem in the area of recursive arguments. First, it provides a folding scheme for CCS where the prover's cryptographic cost is a single multi-scalar multiplication (MSM) of size equal to the number of variables in the constraint system, which is optimal when using an MSM-based commitment scheme. The folding scheme can fold multiple instances at once, making it easier to build generalizations of IVC such as PCD. Second, when proving program executions on stateful machines (e.g., EVM, RISC-V), the cost of proving a step of a program is proportional only to the size of the circuit representing the instruction invoked by the program step ("a la carte" cost profile). Third, we show how to achieve zero-knowledge for "free" and without the need to employ zero-knowledge SNARKs: we show that Nova's folding scheme has a blinding property that can be used to "randomize" IVC proofs and, more generally, to add zero-knowledge to non-ZK SNARKs, via a protocol we call NovaBlindFold. This highlights a new application of folding schemes. Fourth, we show how to efficiently instantiate HyperNova over a cycle of elliptic curves. For this, we provide a general technique, which we refer to as CycleFold, that applies to all modern folding-scheme-based recursive arguments.

Garbled RAM is a promising technique for scaling secure two-party computation to large datasets. It features an efficient two-round protocol and supports each memory access with polylogarithmic overhead, thereby avoiding the prohibitive cost of RAM-to-circuit conversion. While earlier works on Garbled RAM primarily focused on establishing theoretical feasibility, recent research has increasingly emphasized concrete efficiency, culminating in constructions that achieve approximately $O(\lambda T W \log N)$ bandwidth cost (up to super-constant factors) for garbling a RAM with running time $T$, memory size $N$, and word size $W$. We ask whether it is possible to further improve the bandwidth cost of Garbled RAM. In contrast, the Garbled Circuit literature has developed a rich set of techniques that remove the bandwidth's dependence on the security parameter $\lambda$, leading to constant-rate or even sub-constant-rate garbling schemes. However, no comparable methods are currently known for Garbled RAM. We propose a new garbling scheme for arithmetic RAM, called Zebra (short for ``Zero Exposure B-bounded Random Accesses''). Specifically, we show that when the word size $W$ is suitably large, we can eliminate the $\lambda$-factor dependence and achieve a bandwidth cost of $O(T W \log N)$. In this sense, our scheme can also be viewed as the RAM analogue of ``constant-rate garbling for arithmetic circuits''. Further, we show how to extend our techniques to support the garbling of boolean RAMs, achieving a bandwidth cost of $O(T W (\log N + \lambda))$ when the word size is suitably large. We implemented Zebra and released our code through open source. Our evaluation shows a $10.1\times$ concrete improvement in bandwidth and a $3.5\times$ improvement in end-to-end time relative to the state-of-the-art Garbled RAM schemes on a 256MB database with 4kB entries.

One-sided linear systems of the form ``$Ax=b$'' are well-known and extensively studied over the tropical (max-plus) semiring and wide classes of related idempotent semirings. The usual approach is to first find the greatest solution to such system in polynomial time and then to solve a much harder problem of finding all minimal solutions. We develop an extension of this approach to the same systems over two well-known extensions of the tropical semiring: symmetrized and supertropical, and discuss the implications of our findings for the tropical cryptography.

We propose a novel algorithm to solve underdetermined systems of multivariate quadratic (MQ) equations over finite fields. In modern MQ signature schemes such as MAYO, QR-UOV and SNOVA finding solutions to such systems is equivalent to signature forgery. The current benchmark for estimating forgery bit complexity is Hashimoto’s algorithm which transforms the original underdetermined MQ system $P$ into a more tractable system $\tilde{P}$. A hybrid combination of solving $\tilde{P}$ via Gröbner basis and exhaustive search eventually solves $P$. We introduce a novel transformation that pushes the hybrid approach to its extreme. Specifically, we reduce the underdetermined MQ system to a sequence of quadratic equations in a single variable at the cost of a larger exhaustive search. As a consequence, signature forgery no longer relies on the hardness of MQ solving but becomes pure guessing via exhaustive search. This in turn implies that signature forgery is significantly more vulnerable against quantum attacks via Grover search. We provide accurate estimates for the classical and quantum bit complexity of forging signatures for MAYO, QR-UOV and SNOVA using our novel algorithm. We reduce the quantum security of all security levels of MAYO, QR-UOV and SNOVA.

Physical attacks are a well-known threat for otherwise secure implementations of cryptographic algorithms. Although attacks and countermeasures for Side-Channel Analysis (SCA) and Fault-Injection Analysis (FIA) are well studied and individually understood, their combined exploitation and the corresponding countermeasures remain a relatively new area of research. Just recently, Feldtkeller et al. presented Combined Private Circuit (CPC) gadgets at CCS 2022 and CCS 2023 which were the first provably secure combined hardware gadgets that adhere to the notion of Combined-Isolating Non-Interference (CINI). The definition of the CINI notion has been a milestone for the development and formal verification of combined secure gadgets. However, it is also specifically tailored to the realization of side-channel resistance via plain masking and redundancy via replication, without further considerations of other constructions, e.g., those based on coding theory. In this work, we extend the existing definition of CINI to the notion of generalized Combined Isolated Non-Interfering (gCINI). Our generalizations allow to capture a much wider range of possible encodings, including - but not limited to - Boolean masking and replication, and provide a formal basis for the analysis of more general gadget constructions. We formally prove the combined security and composability of our new gCINI definition and give an explicit way to build such gadgets. The significance of our proposed construction is demonstrated through the implementation of several use cases, including an AES S-box design that outperforms comparable CPC-based approaches while maintaining the same level of combined security. Finally, we formally verify the security of our gadget constructions using an adapted version of VERICA.

The Middle Product Learning With Errors (MP-LWE) problem was introduced in 2017 by Rosca, Sakzad, Steinfeld, and Stehlé (Crypto 2017). In their work and in a follow up work by Rosca, Stehlé, and Wallet (Eurocrypt 2018), the authors proved that MP-LWE is at least as hard as the Ring-LWE problem over the field $\mathbb{Q}[x]/f(x)$, for an exponentially large class of polynomials $f$ (with fixed degree and bounded coefficients). A few years later, Peikert and Pepin gave a new reduction from Ring-LWE to MP-LWE (Journal of Cryptology 2024). This new reduction improved the results of Rosca et al. by increasing the set of polynomials $f$ for which the reduction holds. However, even though the sets of polynomials covered by both reductions have exponential size, they remain negligible among the set of all polynomials of fixed degree and bounded coefficients. In this work, we provide a refined analysis of the reduction of Rosca et al. Our new analysis shows that the reduction of Rosca et al. actually covers a much larger class of polynomials than what was known before, containing (experimentally) at least $90\%$ of all polynomials of fixed degree and bounded coefficients.

End-to-end authenticity in public networks plays a significant role. Namely, without authenticity, the adversary might be able to retrieve even confidential information straight away by impersonating others. Proposed solutions to establish an authenticated channel cover pre-shared key-based, password-based, and certificate-based techniques. To add confidentiality to an authenticated channel, authenticated key exchange (AKE) protocols usually have one of the three solutions built in. As an amplification, hybrid AKE (HAKE) approaches are getting more popular nowadays and were presented in several flavors to incorporate classical, post-quantum, or quantum-key-distribution components. The main benefit is redundancy, i.e., if some of the components fail, the primitive still yields a confidential and authenticated channel. However, current HAKE instantiations either rely on pre-shared keys (which yields inefficient end-to-end authenticity) or only support one or two of the three above components (resulting in reduced redundancy and flexibility). In this work, we present an extension of a modular HAKE framework due to Dowling, Brandt Hansen, and Paterson (PQCrypto'20) that does not suffer from the above constraints. While their instantiation, dubbed Muckle, requires pre-shared keys (and hence yields inefficient end-to-end authenticity), our extended instantiation called Muckle+ utilizes post-quantum digital signatures. While replacing pre-shared keys with digital signatures is rather straightforward in general, this turned out to be surprisingly non-trivial when applied to HAKE frameworks (resulting in a significant model change with adapted proof techniques).

We present our work-in-progress approach to computable contracts, where all roles in a computation may be outsourced, from the servers performing computations, to those providing input, to those performing verifications (on input and on output), including all related communications. Varying levels of confidentiality can be chosen on both data and calculations. Although the largest part of the computational and communication effort is performed off-chain, our contracts require a specialized underlying blockchain where they are encoded as transactions. This enables decentralized handling and enforces correct execution through a combination of cryptographic techniques and economic security. Our delegation architecture allows for the execution of very complex collaborative tasks, such as decentralized AI.

Zero-Knowledge (ZK) protocols have been a subject of intensive study due to their fundamental importance and versatility in modern cryptography. However, the inherently different nature of quantum information significantly alters the landscape, necessitating a re-examination of ZK designs. A crucial aspect of ZK protocols is their round complexity, intricately linked to $\textit{simulation}$, which forms the foundation of their formal definition and security proofs. In the $\textit{post-quantum}$ setting, where honest parties and their communication channels are all classical but the adversaries could be quantum, Chia, Chung, Liu, and Yamakawa [FOCS'21] demonstrated the non-existence of constant-round $\textit{black-box-simulatable}$ ZK arguments (BBZK) for $\mathbf{NP}$ unless $\mathbf{NP} \subseteq \mathbf{BQP}$. However, this problem remains widely open in the full-fledged quantum future that will eventually arrive, where all parties (including the honest ones) and their communication are naturally quantum. Indeed, this problem is of interest to the broader theory of quantum computing. It has been an important theme to investigate how quantum power fundamentally alters traditional computational tasks, such as the $\textit{unconditional}$ security of Quantum Key Distribution and the incorporation of Oblivious Transfers in MiniQCrypt. Moreover, quantum communication has led to round compression for commitments and interactive arguments. Along this line, the above problem is of great significance in understanding whether quantum computing could also change the nature of ZK protocols in some fundamentally manner. We resolved this problem by proving that only languages in $\mathbf{BQP}$ admit constant-round $\textit{fully-quantum}$ BBZK. This result holds significant implications. Firstly, it illuminates the nature of quantum zero-knowledge and provides valuable insights for designing future protocols in the quantum realm. Secondly, it relates ZK round complexity with the intriguing problem of $\mathbf{BQP}$ vs $\mathbf{QMA}$, which is out of the reach of previous analogue impossibility results in the classical or post-quantum setting. Lastly, it justifies the need for the $\textit{non-black-box}$ simulation techniques or the relaxed security notions employed in existing constant-round fully-quantum BBZK protocols.

This paper investigates a recent, claimed state-of-the-art attack on the ASCADv2 dataset, a higher-order masked and shuffled AES implementation, which we demonstrate to be a false positive. Despite successful validation using classical metrics, including a converging Guessing Entropy (GE), we prove that the model learned no actual side-channel leakage. Instead, it exploited a statistical bias in the intermediate value distribution. We argue that the usual scoring function used in the GE is an unreliable metric in the presence of such biases. To address this critical evaluation flaw, we propose a set of methods to avoid falling in this pitfall. First, we introduce pre-emptive methods to detect significant biases in the target's value distribution before profiling, as well as post-mortem ones to examine the resulting model. Second, we present guidelines to avoid regimes where the GE is unreliable, and we derive the Asymptotically Optimal Distinguisher, a new, lightweight distinguisher that provably neutralizes the influence of learned priors in the GE metric, thereby isolating the information gained purely from the side-channel leakage. We demonstrate our methodology by successfully identifying the ASCADv2 false positive and applying it to synthetically biased versions of the ASCADv1 dataset.

Secure Multiparty Computation (MPC) computes on private input data, but generally does not guarantee correctness of the output towards third parties. This property, also called public auditability, was first studied explicitly by Baum et al. (SCN 2014). Their work and its follow-ups generate a Non-Interactive Zero-Knowledge proof of correctness of the MPC outcome during the MPC protocol, ensuring validity of the output even if all parties are corrupted. In this work, we revisit and improve the MPC with Public Auditability blueprint. While the original work uses a version of the SPDZ MPC protocol with expensive lattice-based preprocessing, our construction combines any generic OLE-based preprocessing with a publicly verifiable somewhat linearly homomorphic commitment scheme from VOLE-in-the-head in a non-trivial way. Our commitment scheme relies solely on random oracle calls instead of previously used linearly homomorphic commitments based on structured Public-Key assumptions.

Sigma protocols are fundamental cryptographic tools, serving as the foundation of many practical schemes—most notably, the Schnorr identification and signature schemes. To prove the security of Sigma protocols, one typically reduces breaking a Sigma protocol to solving a presumed hard problem (e.g., computing the discrete logarithm in a certain group). In many settings, however, these reductions are not tight: given an adversary that breaks a Sigma protocol with probability $\varepsilon$, the reduction only yields an adversary for the underlying problem with probability $\varepsilon^2$. This quadratic loss affects efficiency, as it forces choosing larger security parameters to reach a target security level. In this work, we show that this quadratic loss is inherent for two natural classes of reductions. For interactive protocols, we prove it for uniform-challenge, black-box reductions, which query the adversary using uniformly sampled challenges. For non-interactive protocols (i.e., in the random-oracle model), we prove it for weakly programmable, black-box reductions, which answer the adversary’s oracle queries with uniformly sampled outputs. Applying our bounds to the reductions from Schnorr identification and signatures to discrete logarithm yields lower bounds that match known positive results—namely, the classical worst-case reduction of Pointcheval and Stern (Journal of Cryptology, 2000) and the higher-moment reduction of Rotem and Segev (Journal of Cryptology, 2024). Our approach reduces the analysis of such reductions to the values of simple hitting games—combinatorial games that we introduce. Bounding these games is our main technical contribution, and we believe these bounds can enable more modular proofs of related results.

We study lattice enumeration in rank-$n$ modules over number fields. Building on the refined Euclidean analysis of Hanrot and Stehl\'e (CRYPTO~2007), we develop a module analogue of Kannan--Hanrot--Stehl\'e enumeration. Our approach works directly with pseudo-bases and introduces module counterparts of HKZ reduction and quasi-HKZ reduction. We also extend the notion of a lattice \emph{profile} to the module setting and prove tail-product bounds for the $\mathbb{Z}$-basis obtained from a module-HKZ-reduced pseudo-basis. These bounds yield a strictly improved asymptotic enumeration complexity compared to the naive reduction that views a rank-$n$ module as an $(nd)$-dimensional Euclidean lattice. As a representative consequence, for $K=\mathbb{Q}[x]/\langle x^d+1\rangle$ with $d$ a power of two and a rank-$n$ module $M\subset K^n$ with $n\ge 3$, we show that module-SVP can be solved in time $\Delta_K\cdot n^{\frac{nd}{2e}+o(nd)}$, where $\Delta_K$ is the discriminant of $K$. This improves over the Euclidean enumeration bound $(nd)^{\frac{nd}{2e}+o(nd)}$. As an application, for $R=\mathbb{Z}[x]/\langle x^t+1\rangle$ with $t$ a power of two and an ideal $I\subset R$, we obtain an ideal-SVP algorithm running in time $\exp\!\bigl(\frac{t}{2e}\ln\ln t + O(t)\bigr)$, improving upon the worst-case enumeration bound $\exp\!\bigl(\frac{t}{2e}\ln t + o(t)\bigr)$.

In a batched identity-based encryption (IBE) scheme, ciphertexts are associated with a batch label $\mathsf{tg}^\ast$ and an identity $\mathsf{id}^\ast$ while secret keys are associated with a batch label $\mathsf{tg}$ and a set of identities $S$. Decryption is possible whenever $\mathsf{tg} = \mathsf{tg}^\ast$ and $\mathsf{id}^\ast \in S$. The primary efficiency property in a batched IBE scheme is that the size of the decryption key for a set $S$ should be independent of the size of $S$. Batched IBE schemes provide an elegant cryptographic mechanism to support encrypted memory pools in blockchain applications. In this work, we introduce a new algebraic framework for building pairing-based batched IBE. Our framework gives the following: First, we obtain a selectively-secure batched IBE scheme under a $q$-type assumption in the plain model. Both the ciphertext and the secret key consist of a constant number of group elements. This is the first pairing-based batched IBE scheme in the plain model. Previous pairing-based schemes relied on the generic group model and the random oracle model. Next, we show how to extend our base scheme to a threshold batched IBE scheme with silent setup. In this setting, users independently choose their own public and private keys, and there is a non-interactive procedure to derive the master public key (for a threshold batched IBE scheme) for a group of users from their individual public keys. We obtain a statically-secure threshold batched IBE scheme with silent setup from a $q$-type assumption in the plain model. As before, ciphertexts and secret keys in this scheme contain a constant number of group elements. Previous pairing-based constructions of threshold batched IBE with silent setup relied on the generic group model, could only support a polynomial number of identities (where the size of the public parameters scaled linearly with this bound), and ciphertexts contained $O(\lambda / \log \lambda)$ group elements, where $\lambda$ is the security parameter. Finally, we show that if we work in the generic group model, then we obtain a (threshold) batched IBE scheme with shorter ciphertexts (by 1 group element) than all previous pairing-based constructions (and without impacting the size of the secret key). Our constructions rely on classic algebraic techniques underlying pairing-based IBE and do not rely on the signature-based witness encryption viewpoint taken in previous works.

Delegating the Quantum Approximate Optimization Algorithm (QAOA) to an untrusted quantum cloud can leak sensitive instance structure: for graph objectives, the connectivity of the cost unitary directly reveals which edges are present. We propose a selectively blind protocol that hides only the instance-dependent cost Hamiltonian while keeping the mixer public and unmodified. Our approach combines (i) the native measurement-based implementation of the MAX $K$-CUT cost layer from Proietti \emph{et al.} (MBQC-QAOA) and (ii) selective masking techniques inspired by Selectively Blind Quantum Computation (SBQC). The client pads the private graph into a public candidate supergraph by adding dummy edges/vertices. During the measurement-based cost evolution, the server prepares a fixed public MBQC resource over the candidate edges and streams the corresponding cost ancillas to the client for measurement (measurement-only delegation). By choosing either the intended interaction angle (real edge) or the identity angle (dummy edge) \emph{locally}, the client privately prunes dummy edges while revealing no cost-layer angles to the server; one-time-padded correction bits preserve a leakage-free Pauli-frame interface to a standard gate-model mixer. We prove correctness and selective edge blindness, show that padding does not alter the QAOA optimization landscape (hence does not worsen barren plateaus), and provide proof-of-concept numerical validations for MAX-CUT ($K=2$) (exact state-vector equivalence tests and shot-based circuit emulation with feed-forward), together with an asymptotic resource analysis for general MAX $K$-CUT and an explicit dummy-vertex invariance check under full-register mixers.

Cryptographic implementations are inherently vulnerable to side-channel attacks, which exploit physical leakages such as power consumption. Masking has become the most widely adopted countermeasure to mitigate these threats, as it randomizes intermediate values and makes the leakage less exploitable. Yet, a central challenge remains: how to rigorously assess the concrete security level of masked implementations. To tackle this issue, the random probing model has emerged as a powerful abstraction. It formalizes leakage as random probes in the circuit and, importantly, the security in the noisy leakage model, which closely reflects the behavior of real embedded devices, reduces to security in the random probing model. Hence, proving security in the random probing model provides sound guarantees of practical resistance against side-channel attacks. Yet, the current state of the art on random probing compilers and verifiers suffers from a clear limitation: scalable approaches yield prohibitively large and inefficient circuits, while tighter methods do not scale to practical circuit sizes. In this work, we bridge this gap by introducing a new methodology that directly estimates the random probing security of large circuits through Monte Carlo sampling, combined with a pruning strategy that drastically reduces the sampling space. We implement our approach in a new tool, PERSEUS, which supports both gate and wire leakage models. Our experiments demonstrate that PERSEUS can efficiently evaluate masked implementations of AES-128 with $n=8$ shares, achieving security levels beyond 32 bits, thereby significantly advancing the state of the art in practical verification of side-channel countermeasures.

Oblivious ciphertext compression and decompression transform encrypted dense vectors of length $n$ with at most $t$ non-zero entries into compact encrypted sparse representations, and vice versa. These primitives appear in the context of efficient protocols for encrypted search, PIR, and oblivious message retrieval. Existing schemes suffer from large ciphertext sizes or high computational cost. We present new deterministic and perfectly correct constructions based on linear codes, yielding encrypted sparse representations of optimal size with near-linear compression and decompression times. Our results improve both communication and computation over prior work. A central ingredient of our work is to show that, for carefully chosen generalized Reed–Solomon codes, variants of classical decoding algorithms combined with efficient algebraic techniques enable to recover the error vector directly from the syndrome in quasi-linear time in the syndrome length, rather than in the full block length of the code.

In a recent preprint, Grigoriev, Monico, and Shpilrain proposed a digital signature protocol based on the use of matrices over the tropical integer semiring. We show some design flaws of the proposed scheme, together with an efficient attack to forge signatures for an arbitrary message, and a key-recovery attack when given access to a list of honest signatures.

Interactive arguments often combine polynomial IOPs with polynomials commitment schemes (PCSs). Frequently, the interactive argument is proven to be knowledge sound, but this incurs a high security loss when applying the Fiat-Shamir transformation to obtain a non-interactive argument in the random oracle model (ROM). We introduce the notion of special soundness for polynomial IOPs, which surprisingly has not been considered before. We study relations between various binding properties of univariate PCSs. In the case of the KZG PCS, these properties can be based on falsifiable assumptions. We prove that a special-sound polynomial IOP plus a PCS under suitable binding notions gives a computationally special-sound interactive argument. By Attema, Fehr, and Klooss (TCC 2022), applying Fiat-Shamir to this argument yields a tightly knowledge-sound argument (or zk-SNARK) in the ROM under the same assumptions. In the case of the KZG PCS, we add various batching optimizations to our compiler and prove that they preserve computational special soundness. This yields a generic approach for achieving efficient zk-SNARKs with constant proof size and tight knowledge soundness in the ROM under falsifiable assumptions.

A data availability sampling scheme (DAS) allows a network of verifiers to collectively ensure that an untrusted party is correctly storing and distributing some committed data. Importantly, the protocol should not require that the verifiers coordinate or store the full data individually. In this paper, we initiate the study of privacy in DAS schemes: we ask whether the DAS guarantees can be upheld while keeping the committed data secret. We define a natural notion of zero-knowledge for DAS and show that no secure DAS scheme can satisfy this notion. In doing so, we motivate the need to study privacy-preserving variants of DAS. We define eDAS as DAS schemes over encrypted data and introduce the necessary security notions; namely, completeness, soundness and consistency. We additionally define a notion of privacy (zero-knowledge) and compliance (policy-enforcing). We then present two constructions of eDAS schemes. The first uses a DAS scheme as a black box and can be deployed on top of existing production-ready DAS systems with only minor modifications. The second is a more efficient construction that relies on the same principles but removes various layers of abstraction.

Hybrid arguments are prevalent in cryptographic security proofs, however, existing mechanizations in proof assistants are not as general as they could be. In this paper, we prove a general theorem about the admissibility of hybrid arguments that encompasses the query-counting, multi-instance, and nested case. We present three case studies about public-key encryption, which demonstrate the generality of the theorem. The results of this paper are achieved in the setting of state-separating proofs and the theory is integrated into and the case studies are mechanized in Nominal-SSProve.

Federated Learning (FL) is a collaborative Machine Learning (ML) process where clients locally train an ML model on their private inputs, and send it to a server that aggregates the local model updates to obtain a global model update. FL is widely used in applications where the training data is distributed among several clients, e.g., for next word prediction in Google keyboard (Gboard). Nevertheless, FL faces several challenges concerning privacy and security. 1) Client privacy needs to be preserved by employing defenses against inference attacks using Secure Aggregation (SA) protocols. 2) The security of the model has to be defended against poisoning and backdoor attacks, e.g., by using clustering or filtering algorithms. In this work, we present FLiPD, an optimised SA protocol for FL that protects against several attacks via a combination of Multi-Party Computation (MPC) and Differential Privacy (DP) mechanisms. We provide defenses against both inference and backdoor attacks. Moreover, by applying distributed DP noise generation, we show that our protocol is secure even when the majority of the clients collude with a server. As opposed to existing solutions, in FLiPD, the client-server communication cost is essentially the same as in unprotected FL, which sends plaintext updates. Furthermore, the server-server communication cost is slightly lower (by 11%) than the state-of-the-art Prio+ (Addanki et al., SCN'22). In addition, we examine the accuracy of FLiPD both in the presence and absence of attacks. We achieve 87% accuracy for a Linear Regression model trained on the HAR dataset, and 90% for a Convolution Neural Network trained on the MNIST dataset.

We present the first algorithm for computing class groups and unit groups of arbitrary number fields that provably runs in probabilistic subexponential time, assuming the Extended Riemann Hypothesis (ERH). Previous subexponential algorithms were either restricted to imaginary quadratic fields, or relied on several heuristic assumptions that have long resisted rigorous analysis. The heart of our method is a new general strategy to provably solve a recurring computational problem in number theory (assuming ERH): given an ideal class $[\mathfrak a]$ of a number field $K$, sample an ideal $\mathfrak b \in [\mathfrak a]$ belonging to a particular family of ideals (e.g., the family of smooth ideals, or near-prime ideals). More precisely, let $\mathcal{S}$ be an arbitrary family of ideals, and $\mathcal{S}_B$ the family of $B$-smooth ideals. We describe an efficient algorithm that samples ideals $\mathfrak b \in [\mathfrak a]$ such that $\mathfrak b \in \mathcal{S}\cdot\mathcal{S}_B$ with probability proportional to the density of $\mathcal{S}$ within the set of all ideals. The case where $\mathcal{S}$ is the set of prime ideals yields the family $\mathcal{S}\cdot\mathcal{S}_B$ of near-prime ideals, of particular interest in that it constitutes a dense family of efficiently factorable ideals. The case of smooth ideals $\mathcal{S} = \mathcal{S}_B$ regularly comes up in index-calculus algorithms (notably to compute class groups and unit groups), where it has long constituted a theoretical obstacle overcome only by heuristic arguments.

Threshold signatures are an important tool for trust distribution, and preserving the interface of standardized signatures, such as Schnorr signatures, is crucial for their adoption. In practice, latency dominates end-to-end signing time, so minimizing the number of interaction rounds is critical. Ideally, this is achieved under minimal assumptions and with adaptive security, where the adversary can corrupt signers on-the-fly during the protocol. While Schnorr signatures are proven secure under the Discrete Logarithm (DL) assumption in the random oracle model, the most round-efficient adaptively-secure threshold Schnorr protocols rely on stronger assumptions such as Decisional Diffie-Hellman (DDH), the Algebraic One-More Discrete Logarithm (AOMDL) or even the Low-Dimensional Vector Representation (LDVR) assumptions. The only adaptively-secure threshold Schnorr signature from the DL assumption requires five rounds, leaving a significant gap in our understanding of this fundamental primitive. Achieving low-round protocols with adaptive security from the DL assumption has remained an open question. We resolve this question by presenting the first adaptively-secure threshold Schnorr scheme in three rounds (two online, one offline) in the random oracle model under the DL assumption. Our result demonstrates that achieving both low round complexity and adaptive security is possible while preserving the (so far) minimal assumptions for Schnorr signatures. To achieve this, we introduce new techniques, including a novel use of an equivocal commitment scheme paired with a simulation-extractable NIZK, and a masking-based aggregated opening strategy for homomorphic commitments. Our work also makes several contributions that might be of independent interest, including a formalization of a strong adaptive security notion, a stronger commitment equivocation property, and an analysis of the simulation-extractability of the randomized Fischlin transformation.

Cryptographic operations are momentary. Typically, the verification of a digital signature validates the signer's intervention at a specific moment in the past whereas a successful $\Sigma$-protocol round validates a prover's present existence. While cryptography handles very well the notions of "before" and "after" (typically in the blockchain), it remains blind to physical time. In many practical situations it is important to assess the probability that the legitimate user is still present as time elapses. The situation is even more complex when the system needs to provide an assessment based on both cryptographic and non-cryptographic (e.g. biometric) inputs. This paper draws an analogy between Continuous User Authentication (CUA) and pharmacokinetics, a branch of pharmacology that studies how drugs interact with the body over time using differential equations. We relate CUA events to two modes of drug administration: injection and infusion. We compare password logins or digital signatures to injection, where trust is immediately established while $\Sigma$-protocols or facial recognition are analogized to intravenous infusion, where trust is maintained continuously as long as rounds succeed or as long as the user is in view of the camera. We introduce mathematical models blending data from heterogeneous security inputs (that we call "sensors") to estimate the overall level of trust at any time. The models take into account the presence of the legitimate user, attackers and the absence of incoming information.

Isogeny-based cryptography is cryptographic schemes whose security is based on the hardness of a mathematical problem called the isogeny problem, and is attracting attention as one of the candidates for post-quantum cryptography. A representative isogeny-based cryptography is the signature scheme called SQIsign, which was submitted to the NIST PQC standardization competition for additional signature. SQIsign has attracted much attention because of its very short signature and key size among candidates for the NIST PQC standardization. Recently, many new signature schemes using high-dimensional isogenies have been proposed, such as: SQIsignHD, SQIsign2D-West, SQIsgn2D-East, and SQIPrime. Last year, SQIsign advanced to Round 2 of the NIST competition and was updated to version 2.0 (we call it SQIsign-v2.0), which is based on SQIsign2D-West. SQIsign-v2.0 achieves smaller signature sizes and faster verification. However, the signing costs are relatively high. In this paper, we propose a new signature scheme `SQIsign2DPush', which has a smaller signing cost than SQIsign-v2.0 while the signature size and the verification cost are almost the same.

We study the communication complexity of information-theoretic asynchronous multiparty computation (AMPC) with optimal resilience $n=3t+1$ and malicious security. In this setting, the only known result with linear communication per gate is due to Goyal, Liu-Zhang, and Song [CRYPTO ’24]. However, their construction incurs a large communication overhead of $\Omega(n^{14})$ elements that is independent of the circuit size, rendering their result only of theoretical interest. By additionally assuming a random oracle, Bandarupalli et al. [CCS ’25] reduce the communication overhead to $\mathcal{O}(n^3)$ while maintaining the linear communication per gate, at the cost of only achieving malicious security with fairness. In this work, we remove the random oracle assumption and design an information-theoretic AMPC protocol that achieves malicious security with abort. The communication complexity of our construction is $\mathcal{O}(|C|n + Dn^2 + n^3)$ field elements for an arithmetic circuit of size $|C|$ and depth $D$, assuming a functionality for Agreement on Common Set (ACS). Our main technical contribution is a novel verification mechanism with the following guarantee: whenever verification succeeds, there exists a subset of at least $t+1$ honest parties whose local computations are mutually consistent, and the final output is correct with respect to their computation. In contrast to prior approaches that require all honest parties to hold consistent states and execute identical computations before verification, our mechanism tolerates inconsistencies among honest parties while still ensuring that the verified computation is correct for at least one such honest subset, if the verification succeeds.