Secure backups are the Achilles' Heel of the E2EE ecosystem if they do not provide the same strong security properties as the E2EE messaging systems they support. They constitute a set of servers that, if compromised, would expose nearly all user messages. Unfortunately, state-of-the-art and deployed secure backup systems fail to consider forward secrecy and post-compromise security of these servers as first-order design constraints. Additionally, some proposals, in limited deployment, implicitly rely on the PKIs of trusted execution environments in order to provide security, creating a small number of keys whose compromise would be catastrophic. We develop an elegant, efficient, and simple secure backup system that naturally addresses these issues by regularly rotating backup servers, each of which samples independent key material. To make this approach scalable, we design a silent backup procedure, reducing server load compared to state-of-the-art designs while providing improved security. Our design can be trivially extended to incorporate \emph{social key recovery}, enabling more flexible deployment configurations. We carefully prove the security of our construction and benchmark it to show that it is deployment-ready. Our approach works on commodity hardware making it deployable without the resources needed for WhatsApp or Apple's Encrypted Backups.

Verifiable Random Functions (VRFs) provide publicly verifiable pseudorandomness uniquely determined by a secret key and an input. While widely used in decentralized protocols, standard VRF verification reveals the signer's identity, exposing them to targeted adversarial disruption once their eligibility is known. We study Ring VRFs(RVRFs), which allow a member of a public key set (a ring) to publish a VRF value along with a proof of correct generation while hiding the signer's index within the set. We formalize an algorithmic RVRF interface that binds the ring into the evaluated input to prevent cross-ring reuse and ring grinding (i.e., the malicious selection of a specific ring configuration to manipulate the pseudorandom outcome). Diverging from existing UC-based treatments, we propose a comprehensive suite of game-based security notions tailored to verifiable randomness under anonymity: correctness, anonymity, pseudorandomness, and a novel corruption-aware uniqueness notion called $T$-uniqueness. Our main technical result is a modular compiler that transforms any provable VRF into an RVRF by proving a one-out-of-many statement for the induced ring relation. We instantiate the OR layer via an optimized Fiat--Shamir OR (FS-OR) composition in the random oracle model, where the prover utilizes prover-side simulation for all non-witness branches and completes the witness branch only after a global consistency constraint is fixed. Focusing on post-quantum resilience, we provide concrete instantiations of our RVRF framework based on two state-of-the-art lattice VRFs: the long-term lattice VRF $\mathsf{LaV}$ by Esgin et al. (Crypto'23) and the few-time lattice VRF $\mathsf{LB}\text{-}\mathsf{VRF}$ by Esgin et al. (FC'19). We provide a detailed analysis of concrete parameters across various ring sizes for both constructions and perform a comprehensive side-by-side comparison of their communication costs and security trade-offs. Our instantiations are modular, with their security reducing cleanly to (i) the base VRF's correctness, pseudorandomness, and per-key uniqueness, and (ii) standard FS-OR properties (simulatability and extractability).

We analyze the security of RSA keys where the public exponent $e$ is larger than $\varphi(N)$. While nearly all real-world applications of RSA use a small set of pre-determined constant values for $e$, the literature contains a number of constructions involving large special-form exponents. Examples include proposed countermeasures against Wiener's attack on small RSA private exponents, exponent masking against side channels, a 2018 proposal by Joye and Michalevsky to extend the usefulness of hardware security modules, and a 2023 RSA blind signature construction by Amjad, Yeo, and Yung. We give an efficient algorithm to factor an RSA modulus $N$ given an integer $a$ that is "close" to a multiple of $\varphi(N)$. That is, we can factor $N$ in polynomial time given $\varphi(N) < a \le N^{3/2}$ if there is an integer $y$ with $|y| \le a N^{-3/4}$ such that $a - y \equiv 0 \bmod \varphi(N)$. Our attack is a special case of Blömer and May's 2004 algorithm using Coppersmith's method that enables us to give stronger bounds for our application range of interest. We instantiate our attack against several constructions and exhibit families of weak public exponents that do not appear to have been analyzed in the literature. In particular, the Joye and Michalevsky exponent transform permits full key recovery if used for small public exponents. While it is well known that RSA is vulnerable for small private exponent $d$, our work suggests that care must also be taken when generating large public exponents, or when publishing transformed exponents.

Trapdoor constructions are an active research area in Multivariate Cryptography. The presented work studies trapdoors based on factor decomposition in algebraic structures, with emphasis on polynomial rings over $F_p$. The main contribution is the formulation of a general property: if an algebraic structure admits a hidden factor decomposition then this property can be used as a trapdoor principle. Based on this approach, two constructions are given: one signature scheme and one encryption scheme.

A central challenge in data security is not just preventing theft, but detecting whether it has occurred. Classically, this is impossible because a perfect copy leaves no evidence. Quantum mechanics, on the other hand, forbids general duplication, opening up new possibilities. We introduce Proofs of No Intrusion, which enable a classical client to remotely test whether a quantum server has been hacked and the client's data stolen. Crucially, the test does not destroy the data being tested, avoiding the need to store a backup elsewhere. We define and construct proofs of no intrusion for ciphertexts assuming fully homomorphic encryption. Additionally, we show how to equip several constructions of unclonable primitives with proofs of non-intrusion, such as unclonable decryption keys and signature tokens. Conceptually, proofs of non-intrusion can be defined for essentially any unclonable primitive. At the heart of our techniques is a new method for non-destructively testing coset states with classical communication. It can be viewed as a non-destructive proof of knowledge of a measurement result of the coset state.

Secure messaging groups in applications such as Signal, Telegram, and Whatsapp are nowadays used for rapid and widespread dissemination of information to large groups of people. This is common even in sensitive contexts, involving the organisation of protests, activist groups, and internal company dialogues, for instance. Manual administration of who has access to such groups quickly becomes infeasible, in the presence of even hundreds of members. We construct a practical, privacy-preserving reputation protocol, that automates the approval of new group members based on their reputation amongst the existing membership. We prove security against malicious adversaries in a single-server model, with no further trust assumptions required, while supporting arbitrary reputation calculations even when almost all group members are offline (as is likely). We demonstrate the practicality of the approach experimentally: for groups of size 50 (resp. 500), admitting a user that received 40 (resp. 80) scores requires 1312.2 KiB (resp. 13086.3 KiB) of communication, and 3.4 s (resp. 42.3 s) of single-threaded computation. While our protocol design matches existing secure messaging applications, we believe it can have value in distributed reputation computation beyond this problem setting.

Cryptography based on error correction codes has gained significant interest due to its ability to provide security against both classical and quantum adversaries. In 2025, the U.S. National Institute of Standards and Technology selected the Hamming Quasi-Cyclic (HQC) key encapsulation mechanism for standardization. A key aspect of HQC is the possibility of decryption failures, which reveal information about the private key. To address this issue, the HQC authors developed a probabilistic model for the decoding failure rate (DFR) of the underlying error-correcting code, and adjusted the cryptosystem parameters to thwart attacks based on decryption failures. However, the DFR model relies on the assumption of independence between coordinates of the error vector, which does not hold in HQC. This approximation yields conservative DFR estimates in regimes where failure probabilities can be simulated, and it is hypothesized to remains conservative for cryptographic-grade parameter sets. In this work, we eliminate the independence assumptions and derive a new closed-form DFR model for HQC. We demonstrate that the previous approximation remains conservative in the cryptographic regime and that HQC's current decoding failure rates are lower than the required ones. We describe optimization techniques that enable our probabilistic model to serve as a parameter-tuning tool, and demonstrate how the size of HQC public keys and ciphertexts can be slightly reduced without compromising security.

We present a new compact and tightly secure (anonymous) identity-based encryption (IBE) scheme based on the module learning with errors (MLWE) assumption, known as the standard lattice assumption, in the (quantum) random oracle model. Our IBE scheme is the first to achieve the asymptotically most compact and tight security under the standard lattice assumption. We design our IBE scheme by instantiating the framework of Gentry, Peikert, and Vaikuntanathan (STOC`08) using the compact trapdoor proposed by Yu, Jia, and Wang (CRYPTO'23). The tightness of our IBE scheme is achieved by extending the proof technique of Katsumata et al. (ASIACRYPT'18, JoC'21) to the Hermite normal form setting. To achieve this, we develop some new results on module lattices that may be of independent interest.

Inspired by the advancements in (fully) homomorphic encryption during the last decades and its practical applications, we conduct a preliminary study on the underlying mathematical structure of the corresponding schemes. Hence, this paper focuses on investigating the challenge of deducing bivariate polynomials constructed using homomorphic operations, namely repetitive additions and multiplications. To begin with, we introduce an approach for solving the previously mentioned problem using Lagrange interpolation for the evaluation of univariate polynomials. This method is well-established for determining univariate polynomials that satisfy a specific set of points. Moreover, we propose a second approach based on modular knapsack resolution algorithms. These algorithms are designed to address optimization problems where a set of objects with specific weights and values is involved. Finally, we give recommendations on how to run our algorithms in order to obtain better results in terms of precision.

Private Set Union (PSU) protocol allows parties, each holding an input set, to jointly compute the union of the sets without revealing anything else. In the literature, scalable PSU protocols follow the “split-execute-assemble” paradigm (Kolesnikov et al., ASIACRYPT 2019); in addition, those fast protocols often use Oblivious Transfer as building blocks. Kolesnikov et al. (ASIACRYPT 2019) and Jia et al. (USENIX Security 2022), pointed out that certain security issues can be introduced in the “split-execute-assemble” paradigm. In this work, surprisingly, we observe that the typical way of invoking Oblivious Transfer also causes unnecessary leakage, and only the PSU protocols based on additively homomorphic encryption (AHE) can avoid the leakage. However, the AHE-based PSU protocols are far from being practical. To bridge the gap, we also design a new PSU protocol that can avoid the unnecessary leakage. Unlike the AHE-based PSU protocols, our new construction only relies on symmetric-key operations other than base OTs, thereby being much more scalable. The experimental results demonstrate that our protocol can obtain at least 873.74× speedup over the best-performing AHE-based scheme. Moreover, our performance is comparable to that of the state-of-the-art PSU protocol (Chen et al., USENIX Security 2023), which also suffers from the unnecessary leakage.

Quantum Homomorphic Encryption (QHE) addresses Quantum Cloud Computing (QCC) security concerns by ensuring the privacy of a client’s data and algorithms when outsourced to untrusted third-party quantum servers. However, current QHE schemes face significant challenges: scaling computational resources introduces overhead and hardware noise, degrading accuracy and compromising security. This paper imple- ments and analyses a non-interactive AUX-QHE scheme that employs pre-generated auxiliary states for universal computation. We identify three critical computational bottlenecks: exponential growth in auxiliary state count, complex homomorphic evaluation, and extensive symbolic key updates. Through experimental evaluation on IBM Quantum hardware, we quantify the impact of NISQ noise on AUX-QHE performance and establish practical resource thresholds for deployment. Our results bridge the gap between theoretical QHE frameworks and their practical implementation on noisy quantum devices, providing concrete benchmarks for future noise mitigation efforts.

This work presents a round optimal identity-based blind signature scheme based on module lattices. Our construction extends Fischlin's two-round blind signature framework [CRYPTO'06] to the identity-based setting. The construction uses the GPV signature scheme based on Micciancio and Peikert's G-trapdoor techniques and NIZK proofs [CRYPTO'22] in the random oracle model. The scheme is secure under the MLWE and MSIS assumptions. The optimised parameters are also provided targeting $128$-bit security. To the best of our knowledge, this scheme is the first-round optimal identity-based blind signature scheme whose security relies on module lattice problems.

Ongoing advances in quantum computing represent a growing risk to modern cryptography (potentially threatening both asymmetric and symmetric encryption protocols), thereby challenging the foundations of digital security. In response, global cybersecurity communities, led by standardization bodies such as NIST and ETSI, launched initiatives to establish migration pathways toward post-quantum cryptography (PQC). However, the migration of legacy systems to quantum-safe cryptography presents many challenges that have not yet been addressed due to their limited cryptographic agility, outdated infrastructure, and regulatory constraints. These legacy environments, even though they rely on aging technologies and constrained hardware, are still vital to major sectors (such as finance, energy, healthcare, and government). This paper explores some obstacles to the implementation of PQC in these environments, such as hard-coded cryptographic functions, outdated programming languages, hardware limitations, vendor lock-in, interoperability constraints, and certification issues. This shows that, in contrast to contemporary systems, legacy systems cannot be readily modified or easily re-engineered. A critical review of existing standards and academic publications revealed key limitations: their focus on algorithms specifications, the abstract guidance provided without operational depth, the lack of empirical validations, and the insufficient risk modeling and attention to legacy constraints. These gaps prevent effective planning and secure execution of the PQC migration in legacy systems. Consequently, this position paper argues that existing deliverables remain insufficient to address the specific challenges of PQC migration in legacy systems. It proposes the elaboration of a field-informed risk-based framework for PQC Migration in Legacy Systems to guide this transition. This proposed framework combines three interdepedent layers: a diagnostic characterization of legacy system constraints, a qualitative risk assessment grounded in those constraints, and a quantitative evaluation of migration options through an ROI-based analysis to support decision-making. Unlike existing approaches that treat legacy as generic labels, this framework begins by exploring what makes each system legacy in its specific context before applying the risk model. Its development is informed by an empirical survey conducted among large organizations across critical sectors, ensuring relevance beyond theoretical assumptions. Future work will focus on elaborating the framework through applied research, tool development, and real-world case studies in collaboration with financial institutions and critical infrastructure operators. In addition, continued engagement with cyber authorities and standardization bodies will help us ensure alignment with emerging regulations.

Many blockchain-based applications can be seen as instances of fair exchange of two signatures. Adaptor signatures (AS) and, more concretely, their extractability property, are commonly combined with blockchain-based economic incentives to achieve fairness in the exchange of two signatures in the blockchain. Certain blockchain applications require unique signatures (e.g., BLS), but it is formally impossible to build AS from unique signatures. Other applications need blind signatures, however, we found a tension between extractability and blindness. To address these limitations, we observe that fair exchange protocols based on AS only require extractability for one of the two exchanged signatures. This observation allows the other AS to be replaced with a primitive that provides similar security guarantees without inheriting the limitations of AS with respect to unique and blind signatures. A natural candidate is verifiably encrypted signatures (VES), introduced by Boneh et al. (Eurocrypt'03). However, this primitive predates blockchain systems and relies on a trusted party, the adjudicator. Our first contribution is to eliminate the need for an adjudicator by shifting trust to the blockchain and redefining the VES security model accordingly. We introduce two new security notions and prove that our notions imply existing guarantees. We revisit classical VES constructions by Boneh et al. (Eurocrypt'03) for unique signatures and by Hanser et al. (ESORICS'15) for probabilistic signatures, and show that they satisfy our new definitions. Furthermore, we compare our new notions with AS, and conclude that our revised VES is equivalent in terms of security to AS without extractability. Our second contribution extends VES to support blind and non-interactive blind signatures, introducing a new primitive: Verifiably Encrypted Blind Signatures (VEBS). We present a novel construction for non-interactive blind signatures and prove its security. We implement our construction and demonstrate its practical efficiency: encryption requires 3 ms, verification 6 ms, and decryption 13 ms, with a communication cost of 912 bytes. Finally, we discuss how VES/VEBS apply to diverse use cases, including anonymous credentials, contingent payments, atomic swaps, intermediated payments, coin mixing, and applications involving blind signatures.

In this work, we introduce the concept of Obliviously Checkable Secret-Carrying Puzzles (OxSP) and build proof-friendly Garbled Circuits (GCs) to enable their practical implementation. OxSPs allow one to publicly pose puzzles and verify purported solutions received in response, keeping the desired parts of the puzzles and the responses hidden. We show how OxSPs can be based on Garbled Circuits (GCs). However, this requires ZK-SNARK proofs of correctness of garbling. We note that combining existing GC and ZK-SNARK constructions results in very large computational costs for the OxSP solvers. Our main technical contribution is to design a new proof-friendly GC construction which cuts down the cost of generating a proof of correct garbling to almost a third, without resorting to non-standard cryptographic assumptions. Beyond its use in OxSP, we expect our proof-friendly GCs to be of significant independent interest, as a tool for auditable secure 2-party computation.

Abstract—Anonymous token schemes are cryptographic protocols for limiting the access to online resources to credible users. The resource provider issues a set of access tokens to the credible user that they can later redeem anonymously, i.e., without the provider being able to link their redemptions. When combined with credibility tests such as CAPTCHAs, anonymous token schemes can significantly increase user experience and provider security, without exposing user access patterns to providers. Current anonymous token schemes such as the Privacy Pass protocol by Davidson et al. rely on oblivious pseudorandom functions (OPRFs), which let server and user jointly compute randomly looking access tokens. For those protocols, token issuing costs are linear in the number of requested tokens. In this work, we propose a new approach for building anonymous token schemes. Instead of relying on two-party computation to realize a privacy-preserving pseudorandom function evaluation, we propose to offload token generation to the user by using group verifiable random functions (GVRFs). GVRFs are a new cryptographic primitive that allow users to produce verifiable pseudorandomness. Opposed to standard VRFs, verification is anonymous within the group of credible users. We give a construction of group VRFs from the Dodis-Yampolskiy VRF and Equivalence- Class Signatures, based on pairings and a new Diffie- Hellman inversion assumption that we analyze in the Generic Group Model. Our construction enjoys compact public keys and proofs, while evaluation and verification costs are only slightly increased compared to the Dodis-Yampolskiy VRF. By deploying a group VRF instead of a OPRF, we obtain an anonymous token scheme where communication as well as server-side computation during the issuing phase is constant and independent of the number of tokens a user requests. Moreover, by means of our new concept of updatable token policies, the number of unspent tokens in circulation can retrospectively (i.e., even after the credibility check) be decreased or increased in order to react to the current or expected network situation. Our tokens are further countable and publicly verifiable. This comes at the cost of higher computational efforts for token redemption and verification as well as somewhat weaker unlinkability guarantees compared to Privacy Pass.

BBS+ signatures are widely adopted in privacy-preserving systems such as anonymous credentials and Direct Anonymous Attestation (DAA). To strengthen key security and eliminate single points of failure, threshold variants of BBS+ signatures have become increasingly important. However, existing constructions suffer from notable inefficiencies: some entail excessive communication overhead (e.g., DKL+23, S&P 2023), while others impose substantial computational costs and require additional interaction rounds (e.g., WMC24, NDSS 2024). In this work, we present a novel and efficient three-round threshold BBS+ signature scheme from the Castagnos–Laguillaumie (CL) cryptosystem. Our construction achieves best communication–computation trade-offs than previous works. Specifically, compared to the four-round WMC24 scheme, our protocol reduces communication by $77.4\%$ and demonstrates faster computation, with benchmarks indicating speedups of $10.6$--$16.6\times$ in single-threading and $3.3$--$5.4\times$ in multi-threading. Against the three-round protocol DKL+23, our scheme exhibits an asymptotic slowdown factor of $4\times$, but enhances communication by two orders of magnitude. We further extend our techniques to threshold BBS signatures, Dodis-Yampolskiy verifiable random functions (DY VRFs), and multiplication protocols (DNP25 and LLZ+25, CCS'25). This yields: (1) a three-round threshold protocol for the original BBS scheme; (2) two-round threshold protocols for both DY VRFs (focusing on its oblivious variant) and the AGM-secure BBS variant; and (3) one fewer group element in broadcasts for the multiplication protocol with reduced ZKP costs via simplified relations.

The integral-resistance property provides strong arguments against integral distinguishers. Recently, Zeng and Tian proposed a new method to show this property for AES. In this paper, we provide a generalized framework and tool called intres to extend and apply this method to other ciphers with complex linear layers. We derive properties that a cipher must fulfill in order for the method to be applicable. Furthermore, we introduce a degree propagation model which helps us determine the valid key masks for the integral-resistance matrix. The degree model can also be used to upper-bound the algebraic degree of cipher constructions. This allows us to provide tighter upper bounds for the degree of Rijndael-256. We propose algorithmic improvements to substantially decrease the runtime of the offline phase with the intres framework. As a result, we are able to show the integral-resistance property for 7 rounds of PRINCE and 6 rounds of Beanie. Finally, we develop a heuristic MILP-based approach to search for lower-latency alternatives to the MixColumns matrices of PRINCE while maintaining integral resistance. After showing that using this new matrix we still achieve 7-round integral resistance, we validate our method with SAT-based trail counting. While using a MixColumns matrix only optimized for integral resistance might affect security against other types of attacks, we believe these lower-latency matrices have their place in constructions similar to ZIP-ciphers, where integral resistance is particularly critical.

Cleve (STOC 86) shows that an honest majority is necessary for MPC with guaranteed output delivery. In this paper, we show that while an honest majority is indeed necessary, its involvement can be minimal. We demonstrate an MPC protocol with guaranteed output delivery, the majority of which is executed by a sequence of committees with dishonest majority; we leverage one committee with an honest majority, each member of which does work independent of the circuit size. Our protocol has the desirable property that every participant speaks only once (YOSO, Crypto 2021). As a building block of independent interest, we introduce public computation, which is essentially privacy-free MPC with guaranteed output delivery (akin to smart contracts realized on blockchains). We instantiate public computation on a public bulletin board in three different ways (with different assumption / round / space utilization trade-offs).

MPC-in-the-Head protocols enable post-quantum digital signatures based solely on symmetric primitives, with PICNIC being a prominent example built on the LowMC block cipher. While existing analyses assume exact Boolean circuit semantics, recent advances in neural representations suggest that piecewise-linear implementations may introduce activation boundary leakage. In this work, we investigate whether such leakage can be exploited in the context of LowMC and MPC-in-the-Head transcripts. We propose a perturbation-based probing methodology that models neural leakage and reduces round-key recovery to independent binary hypothesis tests via majority voting. Exploiting the linear structure of the LowMC key schedule, we demonstrate that recovery of the first-round key enables efficient reconstruction of the master key with linear complexity. Experimental results confirm successful recovery of 128-, 192-, and 256-bit keys under the proposed model, highlighting a new dimension in symmetric cryptanalysis and the need to consider learning-based leakage in future designs.

FrodoKEM is a conservative lattice-based KEM based on the Learning With Errors problem. While it was not selected for NIST standardization, it remains a strong candidate for high-security applications and is recommended by several national agencies, including BSI, ANSSI, and the EUCC. Its reliance on CDT-based Gaussian sampling presents a significant challenge for side-channel secure implementations. While recent work by Gérard and Guerreau [GG25] has shown that masking FrodoKEM is feasible, the Gaussian sampler remains a major bottleneck, accounting for between 34% and 65% of the execution time. In this work, we introduce a new high-order masking gadget for CDT sampling, provably secure in the ISW probing model and significantly more efficient than previous approaches. We instantiate and evaluate our design on a real-world setup to assess its side-channel resistance in the context of FrodoKEM, using a complete first-order masked implementation on Cortex-M3, which reflects the most relevant practical threat model. Compared with [GG25] at first order, the cost of the sampler is reduced by at least 82% and the number of random generations by at least 69%. Higher-order security is also fully supported through a generic C implementation, with some selected gadgets hand-optimized in assembly to improve efficiency.

We introduce a simple pairing-based vector commitment with subvector opening where, after a one-time preprocessing, the prover can open a subvector of size $\ell$ in linear time. Our focus is on practically relevant solutions compatible with already deployed setups—specifically, the powers-of-$\tau$ setup used by KZG and many popular SNARKs. We achieve substantial concrete speedups over aSVC (Tomescu et al., SCN 2020), the state of the art in deployable subvector commitments with $O(\ell \log^2 \ell)$ prover and verifier time: our opening is over $60\times$ faster on subvectors of any size; on large subvectors ($\ell \approx$ 64K) our opening and verification achieve $\approx 4000\times$ and $170\times$ speedups respectively (and four times as much with parallelism). Our main result is a construction where: - A commitment is a single $\mathbb{G}_2$ element; a proof is a single $\mathbb{G}_1$ element; - Opening requires $\ell$ point additions in $\mathbb{G}_1$; - Verification is dominated by $2\ell$ $\mathbb{G}_1$ operations. We also describe two variants of our main design that are directly compatible with deployed schemes and where the commitment is a $\mathbb{G}_1$ element; these two schemes show similar speedups over prior work. We additionally support cross-commitment and distributed aggregation, and provide an open-source implementation.

We explore the design of blind schemes based on the Lattice Isomorphism Problem (LIP), a recently proposed group-action-based assumption for post-quantum cryptography. Our work highlights both the potential and the limitations of LIP-based constructions. In particular, we analyze the Abe–Okamoto framework and demonstrate that it does not yield a secure instantiation under LIP. We further present an attack on the double LIP problem, allowing from two generic distinct instances of a LIP problem to recover the secret unimodular matrix. Finally, we propose a new blind signature scheme that combines LIP with the Closest Vector Problem (CVP) and a modular version of the Short Integer Solution (SIS) problem, offering a fresh direction for lattice-based blind constructions.

A $t$-out-of-$n$ robust non-interactive zero-knowledge (NIZK) combiner is a construction that, given access to $n$ candidate instantiations of a NIZK for some language, itself implements a NIZK for the same language. Moreover, the combiner is secure, assuming at least $t$ of the given candidates are secure. In this work, we provide the first definition of combiners for NIZK, and prove that no robust NIZK combiner exists assuming $t \le \lfloor n/2 \rfloor$ (unless the polynomial hierarchy collapses). On the positive side, we provide different constructions of robust NIZK combiners for $t > \lfloor n/2 \rfloor$. In particular, we show how to obtain: 1) A black-box combiner working for a special class of {\em homomorphic} languages where $n,t$ are polynomial and $t > \lfloor n/2 \rfloor$. 2) A non-black-box combiner working for any language, where $n,t$ are constant and $t > \lfloor n/2 \rfloor$. 3) A non-black-box combiner working for any language, where $n,t$ are polynomial and $t > \lfloor 2n/3 \rfloor$.

Homomorphic Encryption (HE) enables computation on encrypted data while preserving privacy. We explore its application in the multi-party setting, where data is stored in the cloud under several distinct keys. For $n$ parties, Multi-Key HE (MKHE) supports such scenarios but incurs $O(n)$ space and computational overhead, making it impractical for large-scale use. Conversely, Multi-Party HE (MPHE) achieves constant $O(1)$ overhead but is typically limited by a static group structure: ciphertexts are traditionally tied to a fixed set of parties, which poses challenges for dynamically joining new members or reusing existing ciphertexts for different party sets. To address these limitations, we first construct a Dynamic MPHE (dMPHE) scheme that allows new parties to join, while the original parties are not required to remain online. Our construction bridges the gap between existing MPHE and MKHE frameworks while achieving superior efficiency compared to prior dynamic MPHE attempts. Building on this, we introduce Reusable Dynamic MPHE (rdMPHE), a new primitive that simultaneously supports dynamicity and ciphertext reusability. We implement both schemes based on the RLWE assumption. Our analyzes and experiments demonstrate that rdMPHE maintains $O(1)$ efficiency while overcoming the scalability and static constraints of previous MKHE and MPHE. To support open research, our code has been made publicly available.

In this paper, we explore the use of Montgomery multiplication with a multi-limb redundant representation of integers, in particular in combination with signed reduction factors. We develop techniques that are particularly suited to software platforms on which carry propagation is expensive, in particular RISC-V CPUs which lack hardware support for carries. We also show how to perform a whole-primitive range analysis that demonstrates that overflows are not possible, thus allowing liberal use of unreduced limb-wise additions and subtractions, which are small and fast. The implementation and analysis techniques are illustrated in a codegolfing exercise, to produce size-optimized implementations of ECDSA signature verification over NIST curve P-256; use of a virtual CPU with a custom instruction set with byte-size encoding ("bytecode") allows the production of an implementation as small as 848 bytes on x86 CPUs (in 64-bit mode); RISC-V (984 bytes), Armv8-A (1136 bytes) and portable C implementations (about 2200 to 2800 bytes) are also provided. In the process, an AI is utterly discomfited.

The plausible threat of a Cryptographically Relevant Quantum Computer (CRQC) has rightly stimulated a move away from traditional methods of asymmetric cryptography to new post-quantum secure equivalents. Digital signature is the cryptographic primitive that authenticates an internet server’s identity by signing each certificate in an X.509 certificate chain. A suggested response to the CRQC threat is to deploy a hybrid classical/post-quantum digital signature, combining a traditional tried-and-tested scheme with a post-quantum alternative, where certificates are signed using both methods. Here we propose a fused signature scheme that adopts the same approach, but introduces minimal friction into existing TLS architectures

We examine the relationship between correctness definitions for Fully Homomorphic Encryption (FHE) and the associated security definitions. We show that reactive notions of correctness imply INDCPA-D and sINDCPA-D security. But that to obtain both INDCPA-D and sINDCPA-D security we need to use a randomized version of the evaluation procedure. Such randomized evaluation procedures cause problems in real life deployments of FHE solutions, so we then go on to show how one can de-randomize the evaluation procedure and still obtain sINDCPA-D security in the random oracle model for the specific FHE scheme of TFHE.

Evaluating the usefulness of data before purchase is essential when obtaining data for high-quality machine learning models, yet both model builders and data providers are often unwilling to reveal their proprietary assets. We present PrivaDE, a privacy-preserving protocol that allows a model owner and a data owner to jointly compute a utility score for a candidate dataset without fully exposing model parameters, raw features, or labels. PrivaDE provides strong security against malicious behavior and can be integrated into blockchain-based marketplaces, where smart contracts enforce fair execution and payment. To make the protocol practical, we propose optimizations to enable efficient secure model inference, and a model-agnostic scoring method that uses only a small, representative subset of the data while still reflecting its impact on downstream training. Evaluation shows that PrivaDE performs data evaluation effectively, achieving online runtimes within 15 minutes even for models with millions of parameters. Our work lays the foundation for fair and automated data marketplaces in decentralized machine learning ecosystems.

This paper presents a comprehensive analysis of modular addition from a cryptanalytic perspective, focusing on both linear and differential cryptanalysis techniques. We examine the probability distribution of carry bits in modular addition operations and demonstrate how these probabilities affect linear approximations. The paper provides detailed algorithms for constructing Linear Approximation Tables (LAT) and Difference Distribution Tables (DDT) for modular addition operations, along with theoretical proofs and practical examples. Our analysis reveals that the probability of carry bits approaches 1/2 as the bit position increases, which significantly impacts the effectiveness of linear cryptanalysis. Furthermore, we demonstrate how to extend DDTs for larger bit sizes by leveraging smaller tables and carry bit relationships. The findings have direct implications for the cryptanalysis of ARX ciphers.

Masking is a representative side-channel countermeasure that provides provable security. Among masking schemes, Boolean masking (BM) is widely adopted due to its simple sharing structure, while inner product masking (IPM) and code-based masking (CM) have been studied as alternatives that achieve a higher security order with the same number of shares---a property known as security order amplification in the bit-probing model. Recent work by Gaspoz and Dhooghe (TCHES 2025) proposed an IPM multiplication gadget and CM gadgets with provable bit-level security; however, the overhead of CM gadgets for linear operations, the overhead of IPM multiplication, and the lack of a complete provably secure implementation exploiting IPM security order amplification remain open challenges. In this paper, we address all three challenges. First, we propose BM-to-IPM and IPM-to-BM conversion gadgets satisfying bit $t$-MIMO-SNI in the bit-probing model, enabling composable and provably secure interoperation between the two masking domains. Second, we optimize the TCHES 2025 IPM multiplication gadget via Row Packing and Reduction in Rows, reducing the fresh random bit requirement from $\frac{1}{2}t(n^2-1)k^2(k+1)$ to $tk(n-1)(kn+W)$ bits with a proportional reduction in XOR gates, while maintaining bit $t$-SNI security. Third, we present a hybrid IPM-BM framework in which multiplications are performed in IPM with fewer shares and all Boolean linear operations are handled share-wise in BM at no additional randomness cost, and show that this hybrid approach requires significantly fewer gates and random bits than a pure CM approach. As a concrete instantiation, we implement a second-order masked AES-128 with a 2-share IPM / 3-share BM hybrid architecture, prove that the implementation satisfies bit 2-PINI, and evaluate its practical side-channel security via first- and second-order TVLA on an ARM Cortex-M4 with up to one million traces. To the best of our knowledge, this is the first end-to-end cryptographic implementation that provably preserves IPM's security order amplification in the bit-probing model.

Session is a decentralised secure (anonymous) messenger that combines onion routing with the Oxen Proof-of-Stake blockchain to provide metadata-private communication. Our study presents the first comprehensive analysis of Session's messaging protocol and its integration with the Oxen blockchain. In analysing Session and the underlying Oxen blockchain, we uncovered seven vulnerabilities. Most notably we discovered flaws in the Oxen consensus protocol which could allow network takeover in a realistic setting, thereby undermining the integrity guarantees on which Session's anonymity layer depends. We also discovered serious vulnerabilities in Version 1 of Session's group chat protocol. We conducted extensive simulations to analyse the impact of these vulnerabilities and provide recommendations to reinforce both the Oxen protocol and the Session client to mitigate these attacks.

This paper presents vector-input keyed hashing modes that construct collision-resistant pseudorandom functions (CR PRFs) using a keyed hash function, where a vector refers to a sequence of variable-length strings. The proposed vector-input keyed hashing modes, VIM1 and VIM2, originate from the intuition that a string-input keyed hashing mode using a compression function results in a vector-input keyed hashing mode by replacing the compression function with a hash function. Combined with the recently proposed string-input keyed hashing modes KHC1 or KHC2, VIM1 and VIM2 are shown to yield CR PRFs from a compression function satisfying extended collision resistance and being a secure PRF under related-key attacks. Extended collision resistance means that it is intractable to find a distinct input pair whose output difference falls within a small set. This paper also introduces a keyed hashing mode, PVIM, which allows parallel processing of strings in a vector. However, it requires more calls to the underlying keyed hash function than VIM1 and VIM2 do. To the best of our knowledge, this is the first proposal of dedicated vector-input CR PRFs.

Restricted Syndrome Decoding (ResSD) is a variant of linear code decoding problem where each of the error's entries must belong to a fixed small set of values. This problem underlies the security of CROSS, a post-quantum signature scheme that is one of the Round~2 candidates of NIST's ongoing additional signatures call. We show that solutions to this problem can be deduced from vectors of a particular structure and a small norm in newly constructed codes, in both Hamming and Euclidean metrics. This allows us to reduce Restricted Syndrome Decoding to both code-based (Regular Syndrome Decoding) and lattice-based problems (Closest Vector Problem, List of Short/Close Vectors), increasing the attack surface and providing new insights into the security of ResSD. We evaluate our attacks on CROSS instances both theoretically and experimentally on reduced parameters.

We give a passive attack on the Hecke-KE key-exchange scheme. The scheme proposes using products of Hecke operators on $S_k(\Gamma_0(N))$ as a one-way function. We show that the Hecke algebra acting on any fixed $S_k(\Gamma_0(N))$ is simultaneously diagonalizable over an explicit number field computable from the public parameters alone, and that this diagonalization reduces shared-key recovery to $d$ scalar divisions over that number field, where $d=\dim S_k(\Gamma_0(N))$. Our main theorem shows that enlarging $d$ does not rescue the scheme. The precomputation is a one-time public computation (eigenbasis of $S_k(\Gamma_0(N))$, costing $\widetilde{O}(B\cdot d^3)$ rational operations, where $B=O(N)$ is the Sturm bound); the per-session attack cost is then $O(d^2)$ field operations, entirely independent of the pool size $r$ and the number of Hecke factors $s$. We verify the attack in SageMath 10.7 against all parameter sets from the paper; in every case the recovered key satisfies $K'=K$. Furthermore, we prove that the attack runs in time polynomial in $d=\dim S_k(\Gamma_0(N))$ for every level $N$ (prime or composite) and every weight $k$, while the honest protocol's public-key size is $\Omega(d)$ rationals. Consequently there is no choice of $(N,k)$ for which Hecke-KE is secure and implementable: the scheme is unfixable within its design framework.

This paper presents the first high-order fully-shared masking construction for MQOM v2.1, a candidate in NIST's additional digital signature standardization process. We provide a baseline high-order masked signing design for MQOM v2.1, prove its security in the standard probing leakage model, and validate the implementation through a comprehensive TVLA campaign. To mitigate the online-time bottleneck in masked signing, we further introduce an optional Rijndael LUT-based acceleration mode that decouples offline precomputation from online signing. Although this accelerated mode incurs higher offline time and memory costs, it can run during idle periods and significantly reduce online signing latency. We implement and benchmark all 36 MQOM v2.1 signing variants over GF(2), GF(16), and GF(256), and report comprehensive performance and leakage-evaluation results for both the baseline and accelerated designs.

We construct non-interactive zero-knowledge arguments for circuit satisfiability with perfect completeness, perfect zero knowledge and computational soundness. The non-interactive zero-knowledge arguments have sublinear size and very efficient public verification. Their size can even be reduced to a constant number of group elements if we allow the common reference string to be large. Our constructions rely on groups with pairings, and security is based on two new cryptographic assumptions; we do not use the Fiat-Shamir heuristic or random oracles.

The Double Ratchet (DR) protocol is a core security component of several end-to-end encrypted communications services, primarily Signal Messenger, WhatsApp, and Facebook Messenger, servicing billions of users. In this work, we provide the first formal analysis of the DR covering all of its features, including out-of-order message arrivals. This analysis is highly automated, allows for all possible key compromises and notably proves Post-Compromise Security (PCS). We also provide partial results for the security of more complex protocol variants, these being the extension of the DR with encrypted headers, and composition with PQXDH as the initial key-exchange. Our analysis uncovered three attacks on the protocol, two of which we confirmed to be present in the main implementation, and a third which exists in the specification. Each of these attacks weakened or broke Forward Secrecy, and are to the best of our knowledge the first such known attacks. In each case, the issues were reported to the Signal developers and subsequently fixed. Overall, our analysis provides new guarantees of the security of Signal Messenger, and demonstrates the high level of security provided by the DR under a variety of strong threat models.

Registration-based encryption (RBE) effectively addresses the key escrow problem in identity-based encryption. However, existing post-quantum RBE schemes suffer from prohibitive ciphertext sizes in the gigabyte range for systems with $2^{10}$ registered users. This poor scalability is a major obstacle to the large-scale implementation of RBE in society. In this work, we propose a framework for constructing efficient RBE schemes that can be instantiated from the learning with errors (LWE) assumption. Specifically, the ciphertext size remains around 221 MB even as the number of registered users increases. The core techniques involve introducing decomposable laconic encryption and integrating it with a refined snapshotting trick. Our work represents an important milestone towards achieving practical post-quantum RBEs.

Fully homomorphic encryption (FHE) is a powerful and widely used primitive in lots of real-world applications, with IND-CPA as its standard security guarantee. Recently, Li and Micciancio [Eurocrypt'21] introduced IND-CPA-D security, which strengthens the standard IND-CPA security by allowing the attacker to access a decryption oracle for honestly generated ciphertexts (generated via either an encryption oracle or an honest homomorphic circuit evaluation process). Recently, Cheon et al. [CCS'24] and Checri et al. [Crypto'24] have shown that even exact FHE schemes like FHEW/TFHE/BGV/BFV may still not be IND-CPA-D secure, by exploiting the bootstrapping failure. However, such existing attacks can be mitigated by setting negligible bootstrapping failure probability. On the other hand, Liu and Wang [Asiacrypt'24] proposed relaxed functional bootstrapping, which has orders of magnitude performance improvement and furthermore allows a free function evaluation during bootstrapping. These efficiency advantages make it a competitive choice in many applications but its ``relaxed'' nature also opens new directions of IND-CPA-D attack. In this work, we show that the underlying secret key could be recovered within 10 minutes against all existing relaxed functional bootstrapping constructions, and even within 1 minute for some of them. Moreover, our attack works even with a negligible bootstrapping failure probability, making it immune to existing mitigation methods. Additionally, we propose a general fix that mitigates all the existing modulus-switching-error-based attacks, including ours, in the IND-CPA-D model. This is achieved by constructing a new modulus switching procedure with essentially no overhead. Lastly, we show that IND-CPA-D may not be sufficient for some applications, even in the passive adversary model. Thus, we extend this model to IND-CPA-D with randomness (IND-CPA-DR).

Group time-based one-time passwords (GTOTP) is a novel lightweight cryptographic primitive for achieving anonymous client authentication, which enables the efficient generation of time-based one-time passwords on behalf of a group without revealing any information about the actual client's identity beyond their group membership. The security properties of GTOTP regarding anonymity and traceability have been formulated in a static group management setting (where all group members should be determined during the group initialization phase), yet, a formal treatment for real-world dynamic groups (i.e., group members may join and leave at any time) is still an open question. It is non-trivial to construct an efficient GTOTP scheme that can provide a lightweight password generation procedure run by group members and support dynamic group management, allowing group members to join and leave without affecting other members' states (non-disruptively). To address the above challenge, we first define the notion and the security model of dynamic group time-based one-time passwords (DGTOTP) in this work. We then present an efficient DGTOTP construction that can generically transform an asymmetric time-based one-time passwords scheme into a DGTOTP scheme utilizing a chameleon hash function family and a Merkle tree scheme. Within our construction, we particularly tailor an outsourcing solution realizing an issue-first-and-join-later (IFJL) strategy, enabling smooth joining and revocation without disrupting other group members. Moreover, our scheme minimizes symmetric cryptographic operations and maintains constant storage for group members, compared to the linear storage cost that grows rapidly with respect to the lifetime of the GTOTP instance in the previous static GTOTP scheme. Our DGTOTP scheme satisfies stronger security guarantees in a dynamic group management setting without random oracles. Our experimental results confirm the efficiency of our DGTOTP scheme.

After more than four decades of research, multi-party computation (MPC) has achieved remarkable success in handling 2-variable multiplication and comparison-based functions (e.g., ReLU) with practical efficiency. However, for general non-linear functions—such as multiplication of many variables, power, exponential, trigonometric functions, sigmoid, softmax, and GeLU—no native MPC algorithm exists as Beaver-based mutiplication that is constant-round, scalable and exact. Existing solutions rely on either polynomial approximations (trading precision for efficiency), iterative multi-round protocols like Multiplication-to-Addition (M2A) conversion (requiring \(\log_2 k\) rounds for \(k\) parties), or Function Secret Sharing (FSS) with lookup tables (introducing quantization errors and large storage, mainly limited to 2-4 parties). These approaches suffer from fundamental trade-offs among accuracy, communication rounds, and scalability. In this work, we propose a unified \emph{mask-broadcast-unmask} design pattern that enables constant-round, scalable and \emph{approximation-free} evaluation of a wide range of non-linear functions. Our contributions include: \begin{itemize} \item A \textbf{general multiplication} protocol for \(k\) variables in \emph{one round} with optimal \(O(kn)\) communication. When \(k=2\), it reduces to the classic Beaver triple multiplication; when each secret has only one non-zero share and \(k=2\), it becomes the well-known M2A protocol. \item \textbf{Power functions} (\(x^k\)) in one round. \item \textbf{Trigonometric functions} (\(\sin x, \cos x\)) and \textbf{exponential functions} (\(a^x\)) in 4 rounds. \item \textbf{Sigmoid, softmax} in 6 rounds. \end{itemize} All these protocols are provably secure in the semi-honest model, support arbitrary number of parties, introduce \textbf{no approximation error} beyond plaintext floating-point rounding, and require only constant communication rounds (1–6) independent of function complexity. Furthermore, by restricting the random mask to a suitable range (e.g., $0 \le r <2^l-2^{l_x}$), we can reduce the rounds from 1-6 to 1-3. This work fills the long-standing gap for general non-linear functions in standard MPC settings, making privacy-preserving machine learning more practical for modern DNNs.

The rapid development of quantum computing has driven a new wave of cryptographic innovation: Post-Quantum Cryptography (PQC), a class of algorithms that resist quantum attacks. In particular, the National Institute of Standards and Technology (NIST) has initiated the PQC standardization process, selecting five algorithms. Notably, HQC (the newest selection) is a code-based PQC scheme that has not been widely studied in the literature, especially with respect to its hardware acceleration. This paper follows the current trend to design CEDAR, a Compact and Efficient Decoder Architecture for Reed-Solomon Reed-Muller (RS-RM) code in HQC. We have proposed three layers of contributions in total: (i) an optimized RM decoder is designed; (ii) an efficient low-complexity RS decoder is also presented; (iii) a complete HQC decoder is implemented, along with a comprehensive evaluation (it is shown that CEDAR outperforms the existing approach). We hope this outcome will facilitate a more efficient hardware acceleration of HQC and impact the ongoing NIST PQC standardization process.

The advent of quantum computing poses a significant threat to modern cryptography. To address this challenge, the National Institute of Standards and Technology (NIST) has initiated the Post-Quantum Cryptography (PQC) standardization process, with several algorithms being selected for standardization, including the recent code-based scheme HQC (Hamming Quasi-Cyclic). Meanwhile, a good number of research works in the field have switched to efficient hardware acceleration for PQC schemes. Following this trend, in this paper, we present a novel PQC hardware acceleration work, i.e., a Lightweight and Efficient hardware Accelerator for HQC (LEAH). Our design consists of three innovative hardware architectures for Key Generation, Encapsulation, and Decapsulation of HQC, respectively, while supporting all security levels. In total, we have proposed three layers of contributions, including: (i) dedicated design processes to obtain highly optimized major components for HQC, i.e., sparse polynomial multiplier, sampler, encoder, and decoder; (ii) novel data flow arrangement to design three operational phases of HQC that supports all parameter sets; (iii) a detailed comparison based on Field-Programmable Gate Array (FPGA) implementation to showcase the significant efficiency of the proposed design over the competing ones, e.g., Decapsulation architecture has at least 13.66\% (at most 49.87\%) less Equivalent Area-Delay Product (EADP) than the existing ones. We hope this outcome can facilitate the deployment of HQC in various applications and impact the ongoing NIST PQC standardization.

The sum-check protocol underpins SNARKs with the fastest known provers. For an $n$-variate polynomial $g$ defined over a finite field $\mathbb{F}$, the protocol enables an untrusted prover to convince a verifier of the sum of all evaluations of $g$ over a product set $H^n$ with $H \subset \mathbb{F}$. The standard choice for $H^n$ is the Boolean hypercube $\{0,1\}^n$, which serves as a natural interpolating set for multilinear polynomials. We propose a projective variant of the sum-check protocol, obtained by changing the interpolating set from $\{0,1\}^n$ to the infinity hypercube $\{0,\infty\}^n$. Under a suitable notion of evaluation at $\infty$, evaluating a multilinear polynomial at a point in $\{0,\infty\}^n$ directly extracts its corresponding monomial coefficient. This projective viewpoint is a near-drop-in replacement for applications of sum-check, requiring only local changes to polynomial representations, round identities, and evaluation formulas. It yields a ${\approx}\,10\%$ end-to-end speedup for the sum-check prover on BN254 and on a pseudo-Mersenne 128-bit prime field, against a fair baseline. It eliminates all field subtractions when binding a multilinear polynomial, and for structured polynomials such as equality and less-than, the projective interpolants admit evaluation procedures with fewer field operations. Moreover, the monomial-coefficient form aligns naturally with polynomial commitment schemes like WHIR, removing a basis mismatch that these schemes otherwise need to work around. Finally, we describe an optimization for sum-check over $\approx 256$-bit prime fields. When targeting $\approx 128$ bits of security, it suffices to sample challenges from a subset of size $\approx 2^{128}$. We show that a suitable choice of this subset, interpreted as upper-limb values in Montgomery form, yields a $1.92\times$ speedup for field multiplication. Combined with the projective binding formula, this gives a $1.82\times$ speedup for sum-check binding (a key component of fast sum-check proving).

This paper introduces a logarithmic-size membership proof, Lin2Selector, obtained by iterating a new OR-reduction step, formalized as a standalone argument Lin2Xor. Our main technical contribution is the Lin2-Xor lemma, which establishes the required special soundness for this reduction and thereby enables a clean proof that Lin2Selector is a zero-knowledge argument of knowledge. As an application, we instantiate two setup-free linkable ring signatures via the Fiat–Shamir transform in the ROM: minimalistic L2S-LRS, of length 2(log n)+4 group/scalar elements, and multisignature-friendly L2S-LRS-MS, of length 2(log n)+5, supporting an LSAG-style key image. Both schemes rely only on the standard DLR/DDH assumptions in a black-box prime-order group and allow efficient verification dominated by a single multi-exponentiation, enabling standard batching optimizations. The OR-reduction step Lin2Xor suggests a natural generalization to higher arity. This may enable even more compact one-out-of-many proofs/signatures with lengths approaching (log n)+O(log log n), as well as compact k-out-of-many variants; we leave these as open directions.

Many important code-based cryptographic schemes such as the NIST post-quantum competition finalist BIKE and the to be standardized HQC scheme rely on Quasi-Cyclic Moderate-Density Parity-Check codes (QC-MDPC). A very important issue here is to predict accurately the Decoding Failure Rate (DFR). This DFR is intimately connected to the syndrome weight distribution of the QC-MDPC codes used in these schemes. This problem is treated in HQC by modeling the syndrome bits by Bernoulli variables which is known to be inaccurate. The rationale is that it gives a pessimistic estimate of the DFR. In BIKE the syndrome weight is modeled by the syndrome weight of a regular MDPC code which is itself computed by a simplified model. The accuracy of this modeling is not well understood. NIST perceived that BIKE DFR estimation lacked maturity. This led to its dismissal in the competition. The purpose of this paper is to advance on this difficult issue of understanding the syndrome weight distribution of quasi-cyclic codes. Our contribution here is threefold. First we provide a rigorous tool for computing the syndrome weight of a regular code through a generating function and a saddle point approximation. We use this approach to show that the Markov chain model used for estimating the syndrome weight in [ABP24] is remarkably accurate. Second, we also prove that the regular model is not accurate for very low syndrome weights and provide a complete model of the syndrome weight distribution of a QC-MDPC code which can at the same time be computed quickly and fits remarkably well the experiments. We use this to show that for BIKE the probability of the events where the regular model differs from the QC-MDPC syndrome distribution is too low to be of concern. We also show that the variance of the syndrome weight distribution of a QC-MDPC code can be computed efficiently and is a handy tool for estimating accurately the syndrome weight distribution in the moderate deviation regime. We use it to give an accurate prediction of the DFR for a given key of HQC. This gives compelling evidence that the DFR of a typical secret key of HQC is significantly below $2^{- \lambda}$ where $\lambda$ is the security parameter and that weak keys for HQC are too rare to be of concern.

We introduce compressed caching, a scalable and parameterizable countermeasure against grafting tree fault attacks on SLH-DSA. Unlike standard caching, which entails fully caching the WOTS+ signatures and public keys, compressed caching achieves significant memory savings while maintaining strong fault detection capabilities. It can be tuned to achieve a trade-off between caching memory size, fault resilience, and performance, making it well-suited for deployment across devices with varying resource and security constraints. We provide a security and performance analysis of compressed caching and show that it can be configured to achieve high fault detection probability and outperform standard caching, mainly in terms of memory but also in terms of performance. Additionally, we explore granular variants of both standard and compressed caching and study on a finer scale the memory-performance trade-off of both standard and compressed caching. Our results demonstrate that compressed caching is especially advantageous for constrained devices, outperforming standard caching when less than approximately 256 kB of caching memory is available.

Permissionless Decentralized networks, such as blockchains, are typified by self-determined participation. Unfortunately, this has resulted in lack of geographic diversity in several blockchains due to benefits emanating from network proximity between nodes and the higher availability of computing infrastructure in certain areas. Lack of diversity in the resulting network can make it susceptible to eopolitical events, blockchain or cryptocurrency-adverse law-making, and natural disasters. While there exists a growing body of work in verifiable localization in distributed systems, very little exists on mechanisms promoting geographic diversity in distributed systems. Our work sets out to initiate the study of the incentivization of geographic diversity in permissionless distributed systems. We design a family of mechanisms that incentivize network nodes to truthfully declare and diversify their locations. In particular, we provide a game theoretic analysis to derive the conditions under which truthful location reporting is an equilibrium. The conditions relate the offered rewards (for geo-diversity) and the success probability of the underlying localization protocol to detect falsely claimed locations. Our proposed mechanisms assume an underlying secure node localization protocol based solely on round-trip times (RTT) measurements from participants of the protocol. We initiate a formal model to reason about such localization protocols and identify network topologies that are ideal for resisting location spoofing attempts. We evaluate effectiveness of our incentive mechanisms in different scenarios of node placement and underlying network structure. Our validation is based on two RTT data sets we use to derive maximal spoofing distance and attack success rates that adversarial nodes can achieve when operating alone or in collusion with other nodes.

Cryptographic security proofs are the invisible backbone of modern digital systems, yet they remain fragmented across multiple paradigms—game-based proofs, Universal Composability (UC), formal verification, and ad hoc insecurity arguments—each with its own language, assumptions, and limitations. This paper introduces the \textbf{Market-Theoretic Security Framework (MTSF)}, a unified paradigm that reinterprets all security proofs as economic markets. In this view, the defender acts as a seller offering \emph{security goods} (such as confidentiality or unforgeability), while the adversary acts as a buyer bidding computational resources to break them. Security emerges naturally as \emph{market equilibrium}, where no efficient adversary can afford to win, while insecurity is characterized as \emph{market collapse}, where attacks succeed at negligible cost. For cryptographers, MTSF provides a rigorous and expressive framework that unifies four major proof paradigms into a single formal language. It introduces key technical innovations such as the \textbf{extended difference lemma} for handling multiple simultaneous failure events, \textbf{bidding-based reductions} that explicitly model adversarial strategies, a \textbf{dual methodology that treats proofs and disproofs symmetrically within the same structure}, and a \textbf{session pinging mechanism} for unbounded session verification. The framework seamlessly extends to classical and post-quantum primitives, real-world protocols (including TLS~1.3 and Signal), and even quantum-adversarial settings, while preserving quantitative security bounds and composability guarantees. MTSF offers an intuitive, accessible, and powerful meta model: security is like a marketplace where attackers try to ``buy'' a break, and defenders ensure the price is prohibitively high. Each proof becomes a sequence of small price adjustments, and each attack corresponds to a failed or successful bid. By combining mathematical rigor with economic intuition, MTSF transforms security proofs from opaque technical artifacts into transparent, auditable, and universally understandable arguments, enabling both experts and practitioners to reason about security with clarity and confidence.

Kuznyechik is a 128-bit block cipher standardized in GOST~R~34.12--2015. In this paper We study Kuznyechik from the viewpoint of integral cryptanalysis, i.e., we track how structured multisets of chosen plaintexts propagate through the round functions. Starting from a first-order structure of $2^8$ plaintexts (one byte takes all $256$ values while the remaining bytes are fixed), we obtain a 2-round distinguisher: after two rounds, every byte position is balanced, meaning that the XOR-sum over the $256$ texts equals zero. Next, in the setting without initial key-whitening, we extend this distinguisher to three rounds by applying one inverse round to the original structure to construct a new input set. Finally, we turn the 3-round balanced property into a 4-round key-recovery attack by partially inverting the last round and filtering last-round key-byte guesses using the balanced test; multiple independent structures remove false candidates.

We study integral cryptanalysis of the Ukrainian block cipher Kalyna and focus on constructing reduced-round distinguishers and key-recovery attacks with low data, time, and memory complexities. Although Kalyna has an SPN-type round structure, its pre-whitening and post-whitening layers use column-wise addition modulo $2^{64}$, which makes the propagation of integral properties more delicate than in XOR-only designs. By combining carefully chosen input multisets with backward extension through inverse round transformations, we obtain integral distinguishers for Kalyna-128, Kalyna-256, and Kalyna-512 in the standard setting, under weak-key assumptions, and in variants without pre-whitening. These distinguishers require as few as $2^8$ or $2^{16}$ chosen texts, substantially improving the data complexity of previously reported public integral results on Kalyna. We further extend them to key-recovery attacks on reduced-round Kalyna by partial decryption and balancedness tests on suitable intermediate states. For example, we obtain a $5$-round key-recovery attack on Kalyna-128/128 with data complexity $2^9$ chosen plaintexts, time complexity $2^{74}$ encryptions, and negligible memory. To the best of our knowledge, this is the first work to provide integral cryptanalysis of Kalyna-256/256 and Kalyna-512/512. Overall, our results give a unified integral analysis of Kalyna across its standard block sizes and clarify the effect of modular whitening on reduced-round distinguishers and key-recovery attacks.

An essential requirement for the large-scale adoption of Web3 is enabling users to benefit from their data even within already deployed systems. This raises an important open question: how can existing, widely adopted software verify that a user has retrieved specific data from a TLS server? Impressive scientific results (e.g., DECO [CCS20] and the work of Xie et al. [USENIX24]) and industrial products (TLSNotary) have recently made progress in the above challenging direction. However, while they nicely leave TLS servers untouched, the retrieved data is then used in computations with verifiers that are required to run some advanced non-standardized cryptographic schemes (e.g., ZK-SNARKs), which clearly limit the large-scale adoption of the proposed technologies. In this paper, building on top of previous approaches and relying on the recent concept of Predicate Blind Signatures of Fuchsbauer and Wolf [Eurocrypt24], we bypass the limits of prior work by presenting ACTS, a distributed architecture that, while still leaving TLS servers untouched, it allows a user to show possession of data retrieved from TLS servers simply requiring that the software of the verifier can check a standard signature. Our contributions include a round-optimal predicate blind signature protocol that produces standard RSA-PSS signatures. We show how this primitive can be integrated into the DECO architecture (and its successors) to certify data retrieved from TLS servers. Furthermore, we have optimized our construction to make it practical on commodity hardware for a large and significant class of policies implemented by the notary (i.e., the actor that is in charge of obliviously certifying TLS data, therefore preserving data confidentiality). We provide an experimental evaluation on the simple but powerful enough use case of a PDF document downloaded from a TLS server and encoded into an AES-GCM ciphertext. The user will then get a certified PDF through a standard PADES signature added obliviously to the PDF along with some metadata by a notary service. The resulting standard signed PDF document can be transparently verified using off-the-shelf PDF readers. Our experimental validation demonstrates that our architecture is suitable for real-world deployment in concrete scenarios.

Batched threshold encryption (BTE) enables a committee of servers to jointly decrypt any chosen subset of ciphertexts from a large pool, while all remaining ciphertexts stay private. BTE is a key building block for encrypted mempools, where transactions are encrypted until block inclusion to mitigate maximal extractable value (MEV). Existing epochless BTE constructions either require user-chosen ciphertext indices that create coordination and censorship concerns or are computationally inefficient. In this paper, we present BTX, a simple and concretely efficient BTE construction that is both epochless and collision-free: encryption does not require a user-chosen batch index. Our scheme achieves the shortest ciphertext size among all known BTE constructions having the same size as a standard elgamal ciphertext. By making the scheme amenable to FFT, we reduce the decryption cost to $O(B\log B)$ group exponentiations and $O(B)$ pairings, where $B$ is the size of the dynamically chosen batch of ciphertexts. We implement BTX and two baselines in a shared, aggressively optimized C++ codebase over BLS12-381 with AVX-512 vectorization, FFT-based backends where applicable, and additional low-level engineering throughout. At batch size $B = 512$, using a single core, BTX requires approximately $598$ ms total for decryption, compared with $1197$ ms for the FFT optimized version of partial-fraction evaluation baseline of Boneh et al., an overall $2.0\times$ improvement.

Searchable Symmetric Encryption (SSE) schemes enable efficient keyword searches over encrypted documents at the cost of some leakage. An SSE scheme is said to be system-wide secure if it resists cryptanalysis by an adversary with access to leakage from retrieval of both encrypted indices and encrypted documents. The vast majority of state-of-the-art SSE schemes are, in fact, not system-wide secure (Gui et al., IEEE S&P 2023). Currently, the only efficient system-wide secure SSE scheme is SWiSSSE (Gui et al., PoPETS 2024). However, SWiSSSE requires a client state that is updated per query (which hinders adoption in various practical settings), and its leakage is hard to characterize precisely (thus making security analysis harder). In this paper, we present DDR-SSE – a practically efficient, system-wide secure SSE scheme that only requires a static client state, and has a simple leakage profile. Technically, we introduce a novel encrypted document retrieval scheme that uses duplicated document storage and randomized document retrieval to suppress access pattern leakage without compromising on practical efficiency. A remarkable feature of our scheme is its conceptual simplicity (unlike SWiSSSE, which uses an extremely involved document retrieval mechanism). We present a simulation-based security proof for DDR-SSE with respect to a rigorously formal system-wide leakage profile. Through extensive leakage cryptanalysis, we establish that DDR-SSE is resilient to query reconstruction attacks (even under “unrealistically” strong attack assumptions). Finally, we benchmark a prototype implementation of DDR-SSE and show that it scales smoothly to large databases of the size seen in real-world applications.

Polynomial commitment schemes (PCS) are a fundamental building block of modern proof systems. As proof system applications scale to increasingly large workloads, distributed PCS become essential for reducing prover time and memory pressure. Among existing PCS constructions, code-based PCS achieve significantly better concrete prover performance than group-based schemes by avoiding expensive elliptic-curve operations and operating over small-characteristic fields. However, despite these advantages, code-based PCS are notoriously difficult to distribute. In this work, we present LigeSIS, the first distribution-friendly code-based multilinear PCS. LigeSIS achieves sublinear cross-node communication while keeping the final proof size independent of the number of machines. Our key insight is to replace Merkle-tree hashing with a homomorphic subset-sum hash over Goldilocks64, enabling algebraic aggregation of partial commitments produced by different nodes. To make this approach practical, we further introduce a preprocessing-accelerated subset-sum hash that reduces hashing overhead by up to $8\times$. Our evaluation shows that, on a single node, LigeSIS achieves performance comparable to the state-of-the-art RS-based PCS WHIR (Eurocrypt’25). In distributed settings, LigeSIS exhibits near-linear scalability in prover time. Compared with distributed MKZG (S\&P’25), LigeSIS achieves a $24 \times$ improvement in prover time. Compared with PIP (Security’26), LigeSIS reduces cross-node communication by up to $20\times$.

FALCON (Prest et al. NIST submission) is a lattice-based digital signature scheme that is intended to be standardized by NIST under the name FN-DSA. This scheme has smaller signature and public key sizes than the "primary" NIST scheme, ML-DSA, but is more complicated to implement due to floating-point requirements. For this reason, NIST has recommended the scheme be used in special situations where smaller key and signature sizes are particularly important. There are certain situations, where one can make small modifications to FALCON which results in even shorter outputs, which is particularly interesting for FALCON's intended use cases where smaller outputs are important. In the scenario where one would like to minimize the total public key plus signature length, one could use FALCON in key recovery mode, which is a fairly straight-forward procedure specified in the FALCON document. In the scenario where one would like to minimize the total signature plus message length, one could use the message recovery mode (which is a somewhat less straight-forward modification) as described in (del Pino et al. SCN 2017). The purpose of this note is to fully specify the details of this latter mode for developers wishing to implement it. The savings of using FALCON in message recovery mode is up to 226 bytes as compared to FALCON-512 and up to 434 bytes compared to FALCON-1024 for the same security levels (i.e. NIST levels 1 and 5, respectively). We also sketch how the same technique can be applied to the ring signature version of FALCON from (Gajland et al. Crypto 2024). The main algorithmic building blocks of FALCON, such as key generation and trapdoor sampling, remain exactly the same. The only algorithmic changes are in the hashing and parsing of the messages, randomness, and the hash function.

Determining bounds on the differential probability of differential trails and the squared correlation contribution of linear trails forms an important part of the security evaluation of a permutation. For Xoodoo, such bounds were proven using the trail core tree search technique, with a dedicated tool (XooTools) that scans the space of all r-round trails with weight below a given threshold $T_r$. The search space grows exponentially with the value of $T_r$ and XooTools appeared to have reached its limit, requiring huge amounts of CPU time to push the bounds a little further. The bottleneck was the phase called trail extension where short trails are extended to more rounds, especially in the backward direction. In this work, we present a number of techniques that allowed us to make extension much more efficient and as such to increase the bounds significantly. Notably, we prove that the minimum weight of any 4-round trail is 80, the minimum weight of any 6-round trail is at least 132 and the minimum weight of any 12-round trail is at least 264, both for differential and linear trails. As a byproduct we found families of trails that have predictable weight once extended to more rounds and use them to compute upper bounds for the minimum weight of trails for arbitrary numbers of rounds.

Blind signatures are a central tool for privacy-preserving protocols. They allow users to obtain signatures from a signer without the signer seeing the signed message. For instance, it enables electronic cash: signatures correspond to coins which can be issued by the bank in a privacy-preserving manner via blind signing. To mitigate the risk of key compromise, threshold blind signatures allow the distribution of the signing key amongst N parties. While recent works have focused on improving the security of this primitive in the classical setting, no construction is known to date in the post-quantum setting. We present the first construction of a threshold blind signature secure in the post-quantum setting, based on lattices. We prove its security under an interactive variant of the SIS assumption introduced in [Agrawal et al., CCS’22]. Our construction has a reasonable overhead of a factor of roughly 1.4 X to 2.5 X in signature size over comparable non-threshold blind signatures over lattices under heuristic but natural assumptions.

The advent of quantum computing poses a fundamental threat to classical cryptographic assumptions. While algorithms such as RSA and Elliptic-Curve Cryptography are secure against classical adversaries, they would be efficiently broken by a sufficiently powerful quantum adversary. Yet, despite rapid industrial and academic progress, the timeline for achieving a Cryptographically Relevant Quantum Computer (CRQC) remains uncertain and opaque. In this work, we propose a mechanism to monitor quantum capabilities through economic incentives. We introduce QCAP, a trustless distributed protocol for deploying a quantum canary address alert. QCAP enables the creation of publicly auditable cryptographic challenges whose solutions would reveal the existence of quantum computers capable of breaking the Elliptic Curve Discrete Logarithm problem. The protocol is decentralized, secure, efficient, and verifiable, featuring adjustable difficulty and native Bitcoin compatibility. A proof-of-concept implementation demonstrates the feasibility of QCAP as a Bitcoin-based early-warning system for the emergence of quantum computational power.

This paper systematically analyzes the security of the two-branch Unified Feistel Lai Massey (UFLM) structure with independent random round functions under chosen plaintext and chosen ciphertext attacks, focusing on its indistinguishability from a random permutation. UFLM uses an invertible linear layer represented as a $2 \times 2$ block matrix $\varphi$ with blocks $A_{11}, A_{12}, A_{21}, A_{22}$. Previously, Dai et al. proved that when $A_{12}$ is invertible, $4$-round UFLM achieves CCA security and resists up to $\mathcal{O}(2^{n/2})$ queries, where the UFLM input is $2n$ bits. Our work imposes no restriction on $A_{12}$. We determine the minimal number of rounds for UFLM to achieve CPA and CCA security, fully determined by the parameters $T(A_{12}^{\top}, A_{11}^{\top})$ and $T(A_{12}, A_{22})$. For UFLM with enough rounds to be secure, the query bound is primarily determined by the rank of $A_{12}$. For all UFLM with too few rounds to be secure, we present successful distinguishing attacks that require at most four queries. Our results rigorously show, for the first time, that when $A_{12}$ has full rank, UFLM requires the fewest rounds to achieve CPA and CCA security and attains the highest query bound. Nevertheless, when $A_{12}$ is not full rank, CPA and CCA security can still be achieved by increasing the number of rounds unless $T(A_{12}^{\top}, A_{11}^{\top}) = \infty$ or $T(A_{12}, A_{22}) = \infty$. At last, for involutory $\varphi$, we find UFLM achieves CPA and CCA security if and only if $A_{12}$ has full rank.

The security of lattice-based cryptography relies critically on the concrete hardness of the approximate shortest vector problem (Approx-SVP). For cryptographic-sized instances, existing Approx-SVP rank reduction conditions may be overly aggressive, as they implicitly assume access to a large number of extremely short lattice vectors. In this work, we systematize and refine Approx-SVP rank reduction conditions from a feasibility perspective. We identify that, in the context of the dimension-for-free (D4f) technique, the existence of a single sufficiently short vector is the essential requirement, and we derive two refined and compact rank reduction conditions accordingly. The first condition is based on geometric properties of lattice sieving, while the second incorporates a basis-quality-dependent probabilistic bound. These results are validated through extensive experiments on high-dimensional lattices, where the compact condition outperforms prior methods by up to a factor of $60$ in dimensions $850$ and $925$. To reliably realize these conditions in high dimensions, we present APBKZ, an adaptive Pump-based lattice reduction strategy that dynamically selects the blocksize and D4f parameters according to the evolving Gram-Schmidt profile. We further introduce HeadAPBKZ, a head-focused execution mode that restricts reduction to a critical prefix once the rank reduction condition is satisfied. Combining these advances, we develop an improved concrete security estimation framework for the MSIS problem. Applied to Dilithium, our analysis indicates that, when compact rank reduction behavior is integrated with the D4f technique, the estimated concrete security of Dilithium is reduced by 3.65-6.09 bits relative to the conservative Core-SVP baseline, providing a more realistic concrete assessment. We also derive an analytic approximation whose closed-form estimates remain close to the numerical estimation, with discrepancies of only about 1.1 bits.

Reed–Solomon (RS) codes underpin a wide range of cryptographic protocols, from verifiable secret sharing (VSS) to blockchain data availability (DA). An RS code commitment enables a prover to distribute codeword fragments among many parties while allowing each recipient to verify that its fragment is consistent with a RS code. Existing constructions either rely on homomorphic polynomial commitments, which incur redundant commitments and expensive group operations, or use FRI-based interactive proofs, which achieve fast proving but suffer from prohibitively large communication. We present UltraProofs, a new RS code commitment framework that achieves linear-time proof generation while remaining compatible with any multilinear polynomial commitment. Our key technical contribution is an evaluation-consolidation protocol that reduces $n$ evaluation proofs at distinct RS points to a single randomized evaluation, eliminating redundant commitments and removing the need for homomorphic structure. We further design a tailored multilinear PCS, LightLigero, which achieves $O(\lambda \log n)$ proof size and maintains $O(n \log n)$ prover time. UltraProofs attains asymptotically optimal prover complexity with concrete speedups in practice: in VSS, it reduces prover time by $2.4\times$ and proof size by $4\times$ compared to HydraProofs (S&P'25); in DA, it cuts per-node communication by up to $2{\sim}5\times$ relative to FRIDA (Crypto'24) while retaining similar prover cost. By decoupling verifiable RS encoding from any specific PCS instantiation, UltraProofs provides a flexible, efficient, and modular foundation for large-scale verifiable storage and distributed cryptographic systems.

HiAE is a well-designed AEAD scheme using AES round functions, delivering outstanding performance on both ARM and x86 processors. Some existing AEAD schemes such as Rocca (ToSC 2021) have been shown to be vulnerable when attackers can repeatedly query the decryption oracle with forged ciphertexts and random tags until a valid tag is accepted. Motivated by this, we use algebraic techniques to analyze the security of HiAE under the same setting. Firstly, we employ the meet-in-the-middle technique and guess-and-determine technique to recover the state and derive a key-related equation resulting from two layers of AES round functions. Secondly, by adopting an algebraic approach to study the properties of the round function, we decompose the equation into byte-level equations for divide-and-conquer. Finally, we utilize the guess-and-determine technique to recover the key. Collectively, these techniques enable us to present the full key-recovery attack on HiAE. Our attack achieves a data complexity of $2^{130}$ and a time complexity of approximately $2^{209}$, leveraging both encryption and decryption oracles with a success probability of 1. We emphasize that our attack considers a stronger scenario than HiAE's original security model, and thus does not invalidate its original security claims.

Threshold signatures distribute trust across multiple parties, eliminating single points of failure and reducing insider and key-exfiltration risks—properties that are increasingly important for high-assurance deployments and recently emphasized by NIST’s Multi-Party Threshold Cryptography (MPTC) initiative. We present a practical t-out-of-n threshold variant and emulation of MAYO, a post-quantum signature candidate to NIST’s call for additional signatures. Our proposal builds upon the threshold MAYO design of Celi, Escudero and Niot (PQCrypto2025), which we significantly refine to achieve practical performance. To this end, we introduce two algorithmic modifications to MAYO tailored for the distributed setting: (1) Explicit-Salt MAYO, which allows for pre-determined salts to enable a single-round online phase; and (2) Depth-Reduced MAYO, which restructures the signing algorithm to minimize the depth of secret-dependent operations. We then propose a unified protocol framework that integrate these techniques, plus other MPC specific optimizations, with the goal of minimizing online latency. Finally, we provide a concrete instantiation and local emulation in the dishonest majority setting, secure against active adversaries. Our emulation shows that threshold signing is practical at typical threshold sizes and amenable to deployment. By releasing an open-source implementation and reporting end-to-end performance, this work offers a concrete reference for the thresholdization of post-quantum signatures. Clearly the aforementioned framework is not limited to MAYO, and can be applied to the UOV family of signatures more generally.

Private BitTorrent trackers enforce upload-to-download ratios to prevent free-riding, but suffer from three critical weaknesses: reputation cannot move between trackers, centralized servers create single points of failure, and upload statistics are self-reported and unverifiable. When a tracker shuts down, users lose their contribution history and cannot prove their standing to new communities. We address these problems by storing reputation in smart contracts and replacing self-reports with cryptographic attestations. Peers sign receipts for received pieces; the tracker aggregates them via BLS signatures and updates reputation. If a tracker is unavailable, peers fall back to an authenticated distributed hash table (DHT): stored reputation acts as a public key infrastructure (PKI), preserving access control without the tracker. Reputation is portable across tracker failures through single-hop migration in factory-deployed contracts. We also address the privacy implications of publishing public keys and reputations tied to private trackers on a public ledger: we propose ephemeral session keys to prevent linking peer identities, zero-knowledge membership proofs for anonymous DHT participation, and confidential reputation using homomorphic commitments. We formalize the security requirements, prove four security properties under standard cryptographic assumptions, and evaluate a prototype. Measurements show that transfer receipts add less than 5\% end-to-end overhead with typical piece sizes. To minimize signing overhead, we adopt a hybrid signature scheme: ECDSA signs individual piece receipts at transfer time for low per-operation latency, while BLS serves as the overarching scheme, enabling compact aggregation of many receipts into a single proof at report time. This design reduces client-side signing cost by an order of magnitude compared to using BLS throughout.

The expected emergence of cryptographically relevant quantum computers (CRQCs) will represent a singular discontinuity in the history of digital security, with wide ranging impacts. This whitepaper seeks to elucidate specific implications that the capabilities of developing quantum architectures have on blockchain vulnerabilities and potential mitigation strategies. First, we provide new resource estimates for breaking the 256-bit Elliptic Curve Discrete Logarithm Problem over the secp256k1 curve, the core of modern blockchain cryptography. We demonstrate that Shor's algorithm for this problem can execute with either $\leq 1200$ logical qubits and $\leq 90$ million Toffoli gates or $\leq 1450$ logical qubits and $\leq 70$ million Toffoli gates. In the interest of responsible disclosure, we use a zero-knowledge proof to validate these results without disclosing attack vectors. On superconducting architectures with $10^{-3}$ physical error rates and planar connectivity, those circuits can execute in minutes using fewer than half a million physical qubits. We introduce a critical distinction between "fast-clock" (such as superconducting and photonic) and "slow-clock" (such as neutral atom and ion trap) architectures. Our analysis reveals that the first fast-clock CRQCs would enable "on-spend" attacks on public mempool transactions of some cryptocurrencies. We survey major cryptocurrency vulnerabilities through this lens, identifying systemic risks associated with advanced features in some blockchains such as smart contracts, Proof-of-Stake consensus, and Data Availability Sampling mechanism, as well as the enduring concern of "abandoned" assets. We argue that technical solutions would benefit from accompanying public policy and discuss various frameworks of "digital salvage" to regulate the recovery or destruction of dormant assets while preventing adversarial seizure. We also discuss implications for other digital assets and tokenization as well as challenges and successful examples of the ongoing transition to Post-Quantum Cryptography (PQC). Finally, we urge all vulnerable cryptocurrency communities to join the migration to PQC without delay.

Atomic swaps allow two parties to exchange coins across blockchains without trust. Most existing solutions support a 1-to-1 transaction; however, the value ratio of two cryptocurrencies is usually not 1-to-1. In addition, these solutions often rely on blockchains with explicit support structures for atomic swaps, typically hashed timelocks (HTLCs) or smart-contract scripting. Thyagarajan et al. (SP'22) provide a solution for n-to-m swaps utilizing adaptor signatures instead, which offer better privacy for the participants. Significantly, all these approaches need timed transactions or a similar substitute on both sides, but not every blockchain supports timed transactions. Hoenisch et al. (ESORICS'22) demonstrate a concrete swap procedure between Bitcoin and Monero, where only one side needs timed transactions. We build upon both of these ideas to provide a generic solution for any blockchain, where only one side needs timed transactions. We introduce a generic adaptor-signature protocol for n-to-m swaps. In doing so, we minimize assumptions compared to current solutions. Both sides lock their coins in shared (two-party signature) addresses, where they can only access the coins together. To prevent deadlocks, both parties are able to refund their coins from these addresses with pre-signed transactions. Our solution works with all relevant blockchains because it needs only standard signatures and a joint public key. Further, only one side needs timed transactions, and if each party acts in its best interest, there are two possible outcomes: If progress stalls, the side with timelocks refunds after a certain time, and the other side refunds immediately. Otherwise, one party redeems the other party's coins with pre-signed transactions, and the other party completes the swap after a timeout to prevent race conditions. We prove security in the universal composability framework and show privacy preservation via unlinkability and fungibility.

Multivariate quadratic (MQ) signatures offer fast signing and verification with short signatures, but their practicality is often limited by large public keys. Recent schemes, such as MAYO, address this limitation by employing the "whipping" technique. This method utilizes emulsifier matrices—the core component underlying Beullens' MAYO scheme—to expand a mini-UOV map into a larger one while ensuring that signing reduces to solving a linear system that is full-rank with high probability. In this work, we focus on modifying these fundamental emulsifier matrices themselves to achieve better performance and smaller key sizes. First, we propose lifting the emulsifier matrices to an extension field while maintaining the base UOV map over the ground field. By leveraging the whipping technique to keep the variable-to-equation ratio close to one, this structural modification effectively avoids known lifted system attacks. Second, we enhance rectangular emulsifier matrices—originally introduced in prior work—with a structured block design that accelerates signing and verification while preserving the necessary full-rank behavior. This approach allows the underlying UOV instance to utilize fewer equations, yielding significantly smaller public keys and potentially faster operations. By combining both techniques, we design a new variant MAYO$^−_L$ and provide a detailed security analysis against known forgery and key-recovery attacks, and propose parameter sets that improve public key and signature sizes at comparable security levels. Finally, we discuss the applicability of our lifting improvement to SNOVA, demonstrating that this enhancement can be integrated into other UOV-based schemes employing the whipping technique.

Several modern applications, such as Signal or WireGuard, use efficient Noise-like implicit authentication key exchanges that require only a small number of exponentiations and two interactions. These protocols have been proven to be secure under the 'strong Diffie–Hellman' (SDH) assumption in the random oracle model (ROM). At ESORICS 2021, Ramacher, Slamanig and Weninger presented an extension to the implicit authenticated key exchange security model, which enables strong privacy properties to be captured in addition to key-secrecy, including man-in-the-middle privacy (ensuring privacy even if a session is interrupted) and forward privacy. They also proposed a protocol to instantiate their model. In this paper, we present an efficient Noise-like protocol that achieve privacy in this model. Our protocol is as efficient as Noise-like protocols that do not guarantee privacy in terms of exponentiations. Moreover, our protocol requires three interactions, which is optimal for this privacy model. It is also more efficient than the ESORICS 2021 protocol in terms of both exponentiations and interactions. Finally, we propose another round-optimal protocol, slightly less efficient in terms of exponentiations, but secure under the CDH assumption in the ROM.

Searchable encryption enables efficient querying over outsourced data while limiting server-side leakage. Existing methods for associative aggregation queries on multidimensional array data suffer from significant limitations: * Use range structures that precompute ranges yielding either: ** Storage size proportional to the total domain size (Demertzis et al., TODS 2018/Falzon et al., PVLDB2022). ** Or linear-time search in the worst case (Chang et al., IEEE TKDE 2021). * Bucket-based methods (Espiritu, Markatou, Tamassia, PoPETS 2022) are only practical when the largest bucket is small. Fully homomorphic encryption (FHE) approaches (Kushnir, Moskowich, Shaul, PoPETS 2024) remain computationally impractical. Due to strong attacks on range schemes with access pattern leakage (Falzon et al., CCS 2020), we consider the task of oblivious search. We propose oblivious segment trees, which offer efficient storage and search. Our approach achieves polylogarithmic query complexity. Storage depends on the number of distinct values per dimension, not on the domain size. Under typical data distributions, segment trees are provably shorter than standard alternatives. We evaluate performance on datasets with 1–3 dimensions and up to $5$ million entries. Across multidimensional datasets, our method reduces the number of stored items by $10$ to $10^{10}$ compared to prior non-FHE approaches. On a 32-thread machine, server-side query processing remains under $1.2$ seconds.

Non-malleable codes allow a sender to transmit a message to a receiver, while providing a ``best-possible'' integrity guarantee to ensure that no attacker---who cannot already decode the message---can meaningfully tamper the message in transit. If tampered, the received message should either be invalid or unrelated to the original message. Non-malleable time-lock puzzles (TLPs) are a special case of non-malleable codes for bounded polynomial-depth tampering with very efficient encoding. In this work, we give generic techniques for constructing non-malleable codes and non-malleable TLPs with improved rate, which captures the ratio of a message's length to its encoding length. A key contribution of our work is identifying a security notion for non-malleability, which we term ``CCA-hiding'', sufficient for our compilers. CCA-hiding is a relaxation of CCA-security for encryption or commitments to the fine-grained setting of codes, and requires that the encoded message remains hidden, even given a decoding oracle for any other codeword. Intriguingly, CCA-hiding does not imply non-malleability in the fine-grained setting, as is the case for encryption and commitments. Using our new techniques, we give the following constructions: -- Rate-1 CCA-hiding TLPs in the plain model. -- Rate-1 non-malleable codes for bounded polynomial-depth tampering in the auxiliary-input random oracle model (AI-ROM). -- Rate-(1/2) non-malleable TLPs in the AI-ROM.

Threshold Schnorr signatures enable $t$-out-of-$n$ parties to collaboratively produce signatures that are indistinguishable from standard Schnorr signatures, ensuring compatibility with existing verification systems. While static-secure constructions are well understood and achieve optimal round complexity, obtaining full adaptive security - withstanding up to $t-1$ dynamic corruptions under standard assumptions has proven elusive: Recent impossibility results (CRYPTO’25) either rule out known proof techniques for widely deployed schemes or require speculative assumptions and idealized models, while positive examples achieving full adaptivity from falsifiable assumptions incur higher round complexity (EUROCRYPT’25, CRYPTO’25). We overcome these barriers with the first round-optimal threshold Schnorr signature scheme that, under a slightly relaxed security model, achieves full adaptive security from DDH in the random oracle model. Our model is relaxed in the sense that the adversary may adaptively corrupt parties at any time, but each signer must refresh part of their public key after a fixed number of signing queries. These updates are executed via lightweight, succinct, stateless tokens, preserving the aggregated signature format. Our construction is enabled by a new proof technique, equivocal deterministic nonce derivation, which may be of independent interest.

Designing dynamic searchable symmetric encryption (DSSE) supporting conjunctive keyword queries over encrypted document collections is an important research area. Unfortunately, state-of-the-art conjunctive DSSE schemes such as ODXT (Patranabis et al., NDSS '21), and SDSSE-CQ and its variants (Zuo et al., PoPETS '25) either fail to achieve the desired levels of security (in particular, forward and/or backward privacy), or incur prohibitively large communication requirements and client-side computational overheads, which is undesirable for practical applications. In addition, all known conjunctive DSSE schemes that are both forward and backward private are quantum-broken due to their inherent reliance on discrete log-hard, prime-order cyclic groups. In this paper, we address the open question of designing practically efficient, low-leakage, forward and backward private conjunctive DSSE with small communication requirements and small client-side overheads. Towards this goal, we introduce the first systematic and rigorously formal notions of backward privacy for conjunctive queries that naturally extend the corresponding notions of backward privacy for single-keyword DSSE. Next, as our main contribution, we propose a new framework for conjunctive DSSE called fp-GA-ODXT that improves upon both ODXT and SDSSE-CQ-variants by achieving full-fledged forward privacy and strong backward privacy guarantees, while incurring small client-side computation and low communication overheads. We then demonstrate two instantiations of our fp-GA-ODXT framework: 1) A concretely efficient, classically secure instance based on discrete log-hard groups and an RSA-based trapdoor permutation, which we implement and benchmark. Our experiments demonstrate that we achieve smaller communication overheads and client-side computation for both updates and conjunctive searches as compared to both ODXT and SDSSE-CQ-variants. These come at the cost of a mild increase in server computation (which we view as an acceptable tradeoff in practice). 2) A post-quantum instantiation based on lattices and isogenies of supersingular elliptic curves, thus solving the longstanding open question of designing asymptotically efficient, forward and backward private conjunctive DSSE schemes with post-quantum security.

AI agents and custodial services are increasingly being entrusted as intermediaries to conduct transactions on behalf of institutions. The stakes are high: The digital asset market is projected to exceed \$16 trillion by 2030, where exchanges often involve proprietary, time-sensitive goods. Although industry efforts like Google’s Agent-to-Payments (AP2) protocol standardize how agents authorize payments, they leave open the core challenge of fair exchange: ensuring that a buyer obtains the asset if and only if the seller is compensated without exposing sensitive information. We introduce proxy adaptor signatures (PAS), a new cryptographic primitive that enables fair exchange through delegation without sacrificing atomicity or privacy. A stateless buyer issues a single request and does not need to manage long-term cryptographic secrets while proxies complete the exchange with a seller. The seller is guaranteed payment if the buyer can later reconstruct the purchased witness; meanwhile, the proxies remain oblivious to the witness throughout the protocol. We formalize PAS under a threshold model that tolerates the collusion of up to $t-1$ proxies. We also present an efficient construction from standard primitives that is compatible with Bitcoin, Cardano, and Ethereum. Finally, we evaluate a Rust implementation that supports up to 30 proxies. Our prototype is concretely efficient: buyer and seller computations take place in microseconds, proxy operations in milliseconds, and on-chain costs are equivalent to those of a standard transaction without fair exchange.

Threshold blind signatures (TBS) allow any set of issuers whose size exceeds a predefined threshold to jointly generate a signature without learning the message. Adaptively secure TBS schemes allow the adversary to corrupt issuers at any point during protocol execution, capturing realistic threat models. Adaptive security methods rely on the algebraic group model (AGM) in security proofs to extract the discrete logarithm of the blinded protocol message. However, as a strong idealized assumption, AGM requires the adversary, upon outputting any group element, to also provide an explicit linear representation in terms of previously seen group elements. Constructing an adaptively secure TBS scheme without AGM remains challenging. In this paper, we propose $\mathsf{Rainblind}$, the first TBS scheme achieving adaptive security without AGM. The core idea is to apply OR compilation between a discrete logarithm equality (DLEQ) statement and a decisional Diffie-Hellman (DDH) tuple statement such that the security proof does not need the AGM to extract the discrete logarithm of the blinded protocol message and instead only needs to extract the group element. Concretely, the DLEQ statement concerns the secret key, while the DDH-tuple statement is derived from a hash function. In real execution, it fails to satisfy the DDH-tuple statement by the uniform hash randomness, forcing the DLEQ branch. In security proof, by programming OR compilation into the DDH-tuple branch, we can leverage random elements to replace the DLEQ elements during the signing queries. To extract the group element, we design a non-interactive proof system $\mathsf{NIPS_{ped}}$. $\mathsf{Rainblind}$ is built from the tagged linear function ($\mathsf{TLF}$), so that the proof can answer adaptive corruption queries via the inversion oracle in the $t$-algebraic translation resistance assumption of $\mathsf{TLF}$, which implies DDH assumption. We also provide a plain signature $\mathsf{Sig_m}$ and a blind signature $\mathsf{BS_m}$ for transitioning to $\mathsf{Rainblind}$.

FHEW/TFHE bootstrapping suffers from a structural rigidity: the accumulator's ring dimension $N$ is limited by the input ciphertext modulus $q$ (typically $q \le 2N$), and thus the message space $t$. This coupling forces $N$ to grow with $t$, leading to inflated parameters and thereby high computational costs. In this work, we overcome this limitation by replacing the ring structure with a free $\mathcal{R}_N$-module $\bigoplus_{i=0}^{\tau-1}\mathcal{R}_N \cdot X^i$. This generalization decouples $N$ from $q$ through a flexible parameter $\tau$. We prove that computation in this extended algebra efficiently reduces to base-ring operations, enabling a new bootstrapping algorithm with improvements in both performance and precision. Theoretically, our approach reduces the asymptotic complexity of standard FHEW/TFHE bootstrapping from quadratic $\tilde{O}(t^2)$ to quasi-linear $\tilde{O}(t)$ in the message space $t$. Compared with prior Extended Bootstrapping methods over discrete cyclotomic ring [PKC'23, TCC'25, Asiacrypt'25], our framework constitutes an algebraic generalization that enables more flexible parameter selection. Experimental results demonstrate that our method achieves speedups of 1.40$\times$--2.77$\times$ over the state-of-the-art sorted extended bootstrapping [Asiacrypt'25].

This paper presents an optimized implementation of the Hamming Quasi-Cyclic (HQC) key encapsulation mechanism, leveraging the additive fast Fourier transform (FFT) for polynomial multiplication. A primary challenge in applying FFT-based multiplication to HQC is that the polynomial degrees slightly exceed powers of two, making standard FFT approaches inefficient. To address this, we propose a new method combining the Frobenius additive FFT (FAFFT) with the Chinese Remainder Theorem (CRT) to efficiently multiply polynomials of these specific degrees. Such a combination is made possible by our new interpretation of FAFFT's Encode step as ring isomorphisms, from which we derive an exact formula for the modulus of any FAFFT-based polynomial multiplier. In addition to the multiplication algorithm, we replace the Berlekamp-Massey decoder with an Extended Euclidean Algorithm (EEA) based method. The regular data flow of EEA facilitates the use of our highly optimized GF(256) SIMD arithmetic, leading to a faster execution speed. Benchmarks demonstrate that our FFT-based approach significantly outperforms traditional Toom-Karatsuba methods, even at lower degrees, on the Arm Cortex-M4 platform. Our integrated optimizations result in a 19.5% and 20.4% speedups for the encapsulation and the decapsulation processes compared to the current state-of-the-art HQC-1 implementation.

A proof of knowledge certifies that the prover “knows” a secret. This property is established by the existence of an extractor that, given access to the prover, can extract the secret. Unfortunately, this does not imply that a single entity has access to the secret in the clear, as it may be secret-shared among several parties and the proof computed using multiparty computation (MPC), or the secret may be embedded in a trusted execution environment (TEE) that only allows limited access to it. Often, the ability to encumber a secret in this way breaks the security of a system; vote selling in e-voting schemes is one example. To address this, two recent papers introduced the notions of “Proofs of Complete Knowledge” (PoCK) [Kelkar et al., CCS’24] and “Individual Cryptography” [Dziembowski et al., CRYPTO’23]. While the goals and constructions in those works differ, both rely on the same key idea to prevent encumbrance. To compute a proof, the prover must evaluate a hash function on a huge number of inputs. One then assumes that only a fraction of those can be encumbered, while for the rest the prover must know the inputs in the clear, and these clear inputs are sufficient to extract the secret. Computing a huge number of hashes is a challenge even for an honest prover (who has the secret in the clear), so those works suggest using outdated Bitcoin mining hardware to make the scheme practical. By forcing the prover to evaluate the hashes in a sequential manner, we could get meaningful security against encumbrance with far fewer hashes, especially against MPC, where round complexity is a major bottleneck. As a concrete instantiation of this idea, we define and construct Sequential Proofs of Complete Knowledge (SPoCK). Our construction uses the PoCK of Kelkar et al. (which are based on Fischlin’s straight-line extractable proofs of knowledge). The computation of this PoCK is then embedded into the computation of the Proof of Sequential Work from [Cohen&Pietrzak, EUROCRYPT’18]. SPoCK thus have the potential to enable complete-knowledge or individual-cryptography primitives where honest parties can use standard hardware. We also propose a variant of this scheme that requires a large amount of memory throughout the evaluation, providing better security also against TEEs.

A verifiable delay function (VDF), introduced by Boneh et al. [CRYPTO’18], on input $(x,T)$ produces an output $(y,\pi)$ where computing $y$ requires $T$ inherently sequential steps, and $\pi$ is a proof certifying correctness. VDFs have found numerous applications, and many of these rely on the assumption that honest parties can evaluate the VDF nearly as fast as adversaries. To support this assumption, significant effort has been invested in developing dedicated VDF hardware (ASICs). However, such devices are expensive and produced in limited quantities, leaving only a small number of parties with access to fast VDF evaluation. A natural workaround is to offer “VDFs as a service,” where a server equipped with specialized hardware evaluates instances on behalf of clients. This approach, however, is unsuitable when the VDF input must remain private. In this work, we introduce and construct blind VDFs, enabling secure VDF outsourcing without revealing the input. Inspired by blind signatures, our protocol allows a client to transform an input $x$ into a blinded instance $\alpha$, which is evaluated by the server. The server returns a result $\beta$, from this and its local state, the client can unblind to recover the correct output $(y,\pi)$, while the server learns nothing about $x$. We realize this notion by constructing a blinded version of Pietrzak’s VDF [ITCS’19]. In the original scheme, computing $y$ requires $T$ sequential steps, while generating the proof $\pi$ can be done in $O(T/S)$ parallel time using $O(S)$ space (e.g., $O(\sqrt{T})$ time and space). In our blind variant, the server performs the $T$ sequential steps and sends $O(S)$ data to the client, who completes the unblinding in $O(T/S)$ time. By allowing slightly more interaction, we obtain a protocol where the client’s work is small, while the server performs essentially the same computation as in the unblinded VDF.

In this work, we propose the first code-based $\mathsf{uPKE}$ from the hamming quasi-cyclic public key encryption scheme $(\mathsf{hqcPKE})$ of Gaborit et al. by integrating an efficient key-update mechanism utilizing a carefully designed deterministic sampling algorithm. Our sampling algorithm exploits a structured permutation set preserving Hamming weight and satisfying specific algebraic properties that is of independent interest. More positively, our protocol allows unbounded key updates free from the cumulative error issues inheriant to lattice based designs and supports asynchronous key updates, authorizing senders to update the public key independently. We formally establish the security of the proposed construction against indistinguishability under chosen-randomness and chosen-plaintext attack $(\mathsf{IND}\text{-}\mathsf{CR}\text{-}\mathsf{CPA})$ in standard model considering decisional quasi-cyclic syndrome decoding with parity $(\mathsf{DQCSDP})$ assumption. We emphasize that in comparison with existing post-quantum secure asynchronous schemes supporting unbounded updates, our construction achieves in the standard model instead of random oracle model significantly improved storage and communication efficiency, particularly in terms of public key size, ciphertext size and update ciphertext size. From a computational perspective, our design enables a more efficient public key update procedure and exhibits comparable performance for key generation, encryption, decryption and secret key update.

Functional encryption generates sophisticated keys for users so that they can learn specific functions of the encrypted message. We provide a generic construction of chosen ciphertext attacks (CCA) secure public-key functional encryption (PKFE) for all polynomial-size circuits. Our PKFE produces succinct ciphertexts that are independent of the size and depth of the circuit class under consideration. We accomplish our goal in two steps. First, we define a new cryptographic tool called constrained witness pseudorandom function (CWPRF) which is motivated by combining WPRF of Zhandry (TCC 2016) and constrained PRF of Boneh and Waters (ASIACRYPT 2013). More specifically, CWPRF computes pseudorandom values associated with NP statements and generates constrained keys for boolean functions. We can recompute the pseudorandom value corresponding to a particular statement either using a public evaluation key with a valid witness for the statement or applying a constrained key for a function that satisfies the statement. We construct CWPRF by coupling indistinguishability obfuscation (iO) and CPRF supporting all polynomial-size functions. In the second and main technical step, we show a generic construction of a CCA secure PKFE for all circuits utilizing our CWPRF. It has been observed that obtaining PKFE supporting all circuits is already a complex task and iO-based constructions of PKFEs are only proven to be chosen plaintext attacks (CPA) secure. On the other hand, existing CCA secure functional encryption schemes are designed for specific functions such as equality testing, membership testing, linear function etc. We emphasize that our construction presents the first CCA secure PKFE for all circuits along with succinct ciphertexts.

We present CLAASP-MP, a monomial prediction (MP) tool based on the three-subset division property without unknown subset (3SDP-woU), integrated into CLAASP, a library for automated analysis of symmetric key cryptographic primitives. The propagation rules of 3SDP-woU are encoded as a Mixed Integer Linear Programming (MILP) model generated directly from the CLAASP component graph, covering the main building blocks used in modern symmetric designs, including S-boxes, linear layers, Boolean word operations, modular addition and multiplication, and linear and nonlinear feedback shift register updates. Using this model for selected output bits, CLAASP-MP computes algebraic normal form (ANF) (for a small number of rounds), derives superpolies for a chosen cube, and computes a tight upper bound on the algebraic degree with respect to plaintext, key, or IV variables. A monomial is absent if its ANF coefficient is zero, if it does not appear in the superpoly, or if the algebraic degree is too small for it to occur; in all such cases, the output is balanced and yields an integral distinguisher. We evaluate \name{} on block ciphers, permutations, and stream ciphers implemented in \claasp{}. We introduce an exact bit-level MILP modeling technique for modular multiplication and apply it to provide the first independent algebraic analysis of the MSX block cipher, identifying integral properties that persist up to 7 rounds for MSX-128. Furthermore, we reproduce known distinguishers and identify new cubes for several block ciphers and extend the best-known integral distinguishers of ChaCha and Salsa permutations from 6 and 5 rounds, respectively, to 6.75 rounds. We also discovered new integral distinguishers for Bivium using several 36-dimensional cubes and extended the exact computation of the algebraic degree of Trivium to later initialization clocks while reproducing many published superpolies. These results show that CLAASP-MP provides a unified and practical MILP-based framework for monomial prediction and algebraic analysis across a wide range of symmetric primitives.

In this paper, we propose an enhanced variant of the F4 algorithm specifically designed for efficiently solving multivariate quadratic (MQ) problems, which are central to many post-quantum cryptographic schemes. Our approach overcomes a major inefficiency of conventional F4 by integrating a Hilbert-driven strategy that determines the optimal number of S-polynomials to generate at each degree, thereby reducing unnecessary zero reductions. We further introduce refined pair selection techniques that prioritize candidates yielding S-polynomials with smaller leading terms, which in turn minimizes the dimensions of intermediate matrices used during reduction. Experimental results show that our implementation outperforms state-of-the-art systems such as M4GB and Magma's F4 in both single-core and multi-core environments. Notably, our method sets new records in the Fukuoka MQ Challenge for Type VI problems over F(31) with m = 21,22,23,24 demonstrating the robustness and practical impact of our approach in solving highly challenging MQ instances. According to the computational complexity estimation formula], the problem with m = 24 is approximately 47,627 times harder than the previous record case with m = 20.

Lattice-based cryptography, as an active branch of post-quantum cryptography (PQC), has drawn great attention from side-channel analysis researchers in recent years. Despite the various side-channel targets examined in previous studies, detail on revealing the secret-dependent information efficiently is less studied. In this paper, we propose adaptive EM side-channel attacks with carefully constructed ciphertexts on Kyber, which is a finalist of NIST PQC standardization project. We demonstrate that specially chosen ciphertexts allow an adversary to modulate the leakage of a target device and enable full key extraction with a small number of traces through simple power analysis. Compared to prior research, our techniques require fewer traces and avoid building complex templates. We practically evaluate our methods using both a reference implementation and the ARM-specific implementation in pqm4 library. For the reference implementation, we target the leakage of the output of the inverse NTT computation and recover the full key with only four traces. For the pqm4 implementation, we develop a message-recovery attack that leads to extraction of the full secret key with between eight and 960 traces, depending on the compiler optimization level. We discuss the relevance of our findings to other lattice-based schemes and explore potential countermeasures.

Distributed Key Generation (DKG) is a vital security foundation for decentralized technologies like blockchain and threshold signatures. However, existing asynchronous DKG (ADKG) protocols face bottlenecks in rigid configuration, limited throughput, and poor scalability, failing to meet the dynamic security management demands of large-scale services.In this paper, we propose an efficient suite of ADKG protocols that support flexible threshold configurations. First, we design a Flexible-Threshold Asynchronous Complete Secret Sharing (FT-ACSS) protocol using bivariate polynomials and zero-knowledge proofs. In an $n \ge 3f+1$ network, FT-ACSS enables dealers to freely configure the threshold $t \in [f, n-f)$, surpassing the limitations of traditional fixed $f$ or $2f$ thresholds. Furthermore, FT-ACSS implements a batch processing mechanism to share up to $t$ secrets simultaneously with $O(\lambda n^2)$ communication cost. We additionally extend the Schnorr protocol into $m$-Schnorr to support multi-secret commitments, significantly reducing amortized resource overhead.Combined with RBC and ABA, these components form a complete FT-ADKG protocol. Theoretical and experimental evaluations demonstrate that our scheme offers superior flexibility and efficiency compared to state-of-the-art protocols, providing a practical security management solution for large-scale asynchronous distributed systems.

We investigate the security of AES-128/192/256 when implemented as ReLU-based neural networks via the natural sum-of-corners construction. Although these implementations are bit-exact on Boolean inputs, they extend AES into a continuous piecewise-linear function over $\mathbb{R}^{128}$. We show that under real-valued oracle access, such neural realizations admit deterministic linear-time master-key recovery. The attack exploits a geometric property of the natural XOR (AddRoundKey) layer: for corner parameter c < 1, ReLU activations partition the input space into key-dependent linear regions. Using symmetric perturbations, exactly one key hypothesis preserves linear-region membership, enabling bitwise recovery through simple output-equality tests. We formalize this phenomenon via a local separability lemma and obtain attack complexity O(128R) neural queries for R rounds. Experiments over 1,000 independent random keys for AES-128, AES-192, and AES-256 achieve 100% recovery success. The vulnerability is independent of key size and round count; it stems solely from exposing a key-dependent XOR layer inside a continuous neural architecture. Our results reveal a fundamental gap between Boolean security and geometric security in neural implementations of cryptographic primitives.

The security of multivariate public-key cryptography, a major approach to post-quantum cryptography, is based on the computational hardness of solving systems of multivariate quadratic equations over finite fields (the MQ problem). The MQ problem consists of solving a system of quadratic equations over a finite field of size $q$, with $n$ variables and $m$ polynomials. The existence probability of solutions to the MQ problem plays a central role in analyzing the security of multivariate cryptography. However, explicit bounds for fixed parameters $(q,n,m)$ have not been sufficiently studied. In this work, we evaluate the existence probability for randomly generated MQ systems with fixed parameters by analyzing the coefficient space arising from the MQ system. Using the inclusion--exclusion principle, we obtain a lower bound (approximately $0.625$) and an upper bound (approximately $0.667$) on the existence probability, focusing on the case $m=n$. We also derive upper and lower bounds on the probability that the number of solutions is exactly one in the case $m=n$. Finally, we analyze the existence probability of solutions to the MQ problem in the case $m \neq n$.

Block ciphers are versatile cryptographic ingredients that are used in a wide range of applications ranging from secure Internet communications to disk encryption. While post-quantum security of public-key cryptography has received significant attention, the case of symmetric-key cryptography (and block ciphers in particular) remains a largely unexplored topic. In this work, we set the foundations for a theory of post-quantum security for block ciphers and associated constructions. Leveraging our new techniques, we provide the first post-quantum security proofs for the key-length extension scheme FX, the tweakable block ciphers LRW and XEX, and most block cipher encryption and authentication modes. Our techniques can be used for security proofs in both the plain model and the quantum ideal cipher model. Our work takes significant initial steps in establishing a rigorous understanding of the post-quantum security of practical symmetric-key cryptography.

We study efficient non-arithmetic operations in (G)BFV with arbitrary plaintext modulus. We design scheme conversions between (G)BFV and Discrete CKKS, allowing (G)BFV ciphertexts to use radix-based integer computation in the Discrete CKKS setting. This gives asymptotically faster logical operations: for plaintext modulus $p$, homomorphic comparison runs in $O(\log p \log\log p)$ for BFV and $O(\log\log p)$ for GBFV.

The rapid adoption of Transformer-based AI has been driven by accessible models such as ChatGPT, which provide API-based services for developers and businesses. However, as these online inference services increasingly handle sensitive inputs, privacy concerns have emerged as a significant challenge. To address this, secure inference frameworks have been proposed, but their high computational and communication overhead often limit practical deployment. In plaintext settings, token drop is an effective technique for reducing inference cost; however, our analysis reveals that directly applying such methods to ciphertext scenarios is suboptimal due to distinct cost distributions in secure computation. We propose SecDTD, a dynamic token drop scheme tailored for secure Transformer inference. SecDTD advances token drop by shifting the dropping to earlier inference stages, effectively reducing the cost of key components such as Softmax. To support this, we introduce two core techniques. Max-Centric Normalization (MCN): A novel, Softmax-independent scoring method that enables early token drop with minimal overhead and improved normalization, supporting more aggressive dropping without accuracy loss. OMSel: A faster, oblivious median selection protocol that securely identifies the median of importance scores to support token drop. Compared to existing sorting-based methods, OMSel achieves a 16.9 times speedup while maintaining security, obliviousness and randomness. We evaluate SecDTD through 48 experiments across eight GLUE datasets under various network settings using the BOLT and BumbleBee frameworks. SecDTD achieves 4.47 times end-to-end inference acceleration without degradation in accuracy.

Privacy-preserving deep learning addresses privacy concerns in Machine Learning as a Service (MLaaS) using Homomorphic Encryption (HE) for linear computations. Nevertheless, the high computational cost remains a challenge. While prior work has attempted to improve the efficiency, most are built upon models originally designed for plaintext inference. These models are inherently limited by architectural inefficiencies when adapted to HE settings. We argue that substantial efficiency improvements can be achieved by designing networks specifically tailored to the unique computational characteristics of HE, rather than retrofitting existing plaintext models. Our design comprises two main components: the building block and the overall architecture. The first, StriaBlock, targets the most expensive HE operation—Rotation. It integrates ExRot-Free Convolution and a novel Cross Kernel, completely eliminating the need for external Rotation and requiring only 19% of the internal Rotation operations compared to plaintext models. The second component, the architectural principle, includes the Focused Constraint Principle, which limits cost-sensitive factors while preserving flexibility in others, and the Channel Packing-Aware Scaling Principle, which dynamically adapts bottleneck ratios based on ciphertext channel capacity that varies with network depth. These strategies efficiently control the local and overall HE cost, enabling a balanced architecture for HE settings. The resulting network, StriaNet, is comprehensively evaluated. While prior works primarily focus on small-scale datasets such as CIFAR-10, we conduct an extensive evaluation of StriaNet across datasets of varying scales, including large-scale (ImageNet), medium-scale (Tiny ImageNet), and small-scale (CIFAR-10) benchmarks. At comparable accuracy levels, StriaNet achieves speedups of 9.78 times, 6.01 times, and 9.24 times on ImageNet, Tiny ImageNet, and CIFAR-10, respectively.

We propose the first collaborative SNARK based on error-correcting codes that is scalable, i.e., the proof computation overhead is distributed among the $N$ provers. As a starting point, we introduce the notion of $(t,l)$-zero-knowledge collaborative codes that ensure that, when collaboratively computing a codeword over a distributed message, no coalition of up to $t$ corrupted parties learns any additional information about the message, even having queried up to $l$ codeword positions. We show that tensor codes consisting of the composition of two Reed-Solomon codes satisfy our definition, while also being foldable. We then propose a collaborative interactive oracle proof of proximity (coIOPP) for testing codeword closeness in our code, show how it can be made a zero-knowledge IOPP using randomness logarithmic in the size of the message (as opposed to linear with prior approaches), and we use it to construct a coIOPP for multi-linear polynomial evaluation. To compile our coIOPPs into non-interactive arguments, we prove that a natural extension of the compiler of Ben-Sasson-Chiesa-Spooner~(TCC 2016) in the collaborative setting preserves round-by-round (knowledge) soundness against quantum adversaries, which may be of independent interest for future work in collaborative SNARKs. Finally, we use an optimized collaborative version of the Spartan PIOP to build the first transparent and post-quantum secure scalable collaborative SNARK. Our experimental evaluation demonstrates that our scheme consistently outperforms the best existing (non-post-quantum secure) scalable collaborative SNARKs, both in end-to-end prover time and in total communication among provers, for all tested configurations.

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

Discrete Gaussian sampling (DGS) is a fundamental method for generating random noise in various post-quantum cryptographic key generation and signature schemes. However, DGS has been shown to be highly susceptible to side-channel analysis, and several countermeasures have been developed. Masking, a robust countermeasure, is widely employed to secure these schemes against side-channel attacks. Due to the non-linear arithmetic operations involved, DGS has traditionally been considered unsuitable for efficient masked implementations. In this work, we propose $\textsf{MAGNET}$: an efficient masking design for the novel discrete Gaussian sampler based on Boolean circuits introduced by Wei et al. at ACM CCS 2023. With $\textsf{MAGNET}$, we demonstrate that DGS can be implemented in a masking-friendly manner. Previous masked DGS approaches in the literature have relied on computation-intensive floating point operations or table-lookup-based techniques using Cumulative Distribution Tables (CDT). In contrast, we show that DGS can be efficiently masked for moderate orders without relying on heavy computation or precomputed large lookup tables. In addition to delivering good performance at a small standard deviation $\sigma$, the efficiency of $\textsf{MAGNET}$ becomes increasingly significant in large $\sigma$ settings. $\textsf{MAGNET}$ achieves up to $17\times$ speed-up at $\sigma = 256$, and $56\times$ speed-up at $\sigma = 1024$ over the CDT-based sampler of Gérard and Rossi (2019). We provide an arbitrary-order C implementation and a first-order ARM Cortex-M4 implementation of $\textsf{MAGNET}$. We validate the practical security of the first-order implementation through Test Vector Leakage Assessment (TVLA) and systematic hardening of gadgets that exhibit side-channel leakage.

In this paper, we propose a new widely applicable technique for constructing low-depth S-box circuits, which we call SLICE (Segmented Low‑depth Iterative Circuit Exploration). SLICE reduces circuit depth by partitioning circuits into subcircuits and applying bit-level optimizations. To mitigate the optimization cost of subcircuits with large bit-widths or high AND depth, SLICE temporarily reduces their bit-width during the search, making low-depth circuit construction feasible for various S-box sizes. Furthermore, we refine the eBPD algorithm with the aim of minimizing XOR gate count in terms of area, and apply it to the constructed circuits to achieve an additional reduction. Our proposed method is simple yet powerful, especially in practical applications. This work focuses on three practically deployed cases, namely the AES, Ascon S-box circuits and Dillon’s 6-bit APN S-box used in FIDES, and additionally considers the cube $x^3$ S-box. For the AES S-box, we present 14-, 13- and 12-depth circuits, whereas the previous lowest depth was 14. Notably, the 12-depth design sets a new overall depth record for AES S-box circuits, while the 13-depth design records the most hardware-efficient circuit in terms of the area$\times$delay metric (ADP). For the Ascon S-box, we present the first 4-depth circuit. For Dillon's S-box and the cube $x^3$ S-box, we also derive new low-depth circuits that improve upon the best previously known depths. All of our proposed S-box circuits achieve better ADPs than previous designs. We believe that SLICE will be useful for evaluating both existing and novel S-box designs.

Secure multi-party computation (MPC) enables mutually distrustful parties to jointly evaluate a function on their private inputs. Classic MPC protocols, however, assume a static set of participants in which every party must remain online throughout the entire computation. Recent advances have introduced MPC models with dynamic participation, such as Fluid MPC, in which computation steps are delegated to a sequence of committees that change across epochs. This approach improves robustness, enabling parties to go offline once their roles are complete. Yet, this flexibility comes at a cost: the most efficient dynamic-participation MPC protocols still incur communication overheads exceeding traditional MPC by more than an order of magnitude. In this work, we formalize the communication complexity of $(d,n)$-threshold secret-sharing-based Fluid MPC. We prove a tight trade-off between communication cost and the adversary's corruption threshold, showing that linear communication complexity $O(n)$ is impossible when the corruption threshold $t$ exceeds a proportion of $d$. Matching this bound, we construct a protocol with a communication cost of $9.3n$ elements per multiplication gate against a semi-honest adversary and $37.3n$ elements against a malicious adversary. A C++ implementation confirms that our approach brings the cost of fluidity within practical limits.

TFHE is one of the most promising scheme in the literature for an adoption of Fully Homomorphic Encryption (FHE) in practice. The core reason of its good performances is the powerful Programmable Bootstrapping (PBS) operation, that enables to homomorphically evaluate a Look-Up Table (LUT) on a ciphertext while simultaneously reducing its noise. However, the computational cost of running a PBS degrades severely when the size of the plaintext space increases, making it intractable for precision larger than 8 bits. So, evaluating a LUT larger than 2^8 is not considered possible with the "vanilla'' TFHE scheme. In this paper, we propose a technique to accelerate LUT evaluation at high precision, that significantly enhances the state of the art. Our method beats the original PBS for spaces larger than 6 bits, and is competitive with the WoP-PBS (the reference of the state of art) while being conceptually simpler. Moreover, our method relies on the standard PBS of TFHE, and therefore does not require the design of new advanced homomorphic operators, which facilitates its integration into larger homomorphic compilation systems.

In a (non-interactive) multi-signature scheme, parties independently generate keys and produce signatures on a common message, which can be aggregated into a single signature verifiable with respect to the set of public keys. Existing multi-signature constructions, however, suffer from at least one of two limitations: either (1) aggregate signatures cannot be further aggregated, or (2) verification requires auxiliary information beyond the set of public keys, such as the aggregation topology. We argue that these limitations significantly restrict the applicability of multi-signatures in large-scale distributed systems, such as proof-of-stake blockchains. To address this gap, we initiate the formal study of hint-free multi-signatures, which support multi-hop aggregation while allowing verification using only the set of public keys. To the best of our knowledge, the only previously known (folklore) construction that is fully hint-free relies on recursive SNARKs, which introduces unclear heuristics for security (e.g., proving statements about random oracle relations) or inherently limits the depth of the aggregation topology. We show that hint-free multi-signatures can be realized without proof recursion, in the standard model. At a high level, we show how to publicly normalize BLS multi-signatures so that verification depends only on the set of public keys rather than a multi-set. While our scheme is not practical (it uses indistinguishability obfuscation), it establishes the feasibility of the primitive provides a foundation for future work on practical constructions.

The adoption of Distributed Ledger Technology (DLT) for critical financial infrastructures like Central Bank Digital Currencies (CBDCs) is hindered by a significant performance gap. Permissioned blockchains such as Hyperledger Fabric, which are conceptually suitable and have become popular platform used in many production deployments today, are nevertheless limited by architectural bottlenecks. Their monolithic peer design and consensus mechanisms prevent them from achieving the required scale for such demanding applications. This paper presents Fabric-X, a fundamental re-architecture of Hyperledger Fabric that addresses these challenges end-to-end. We have open-sourced Fabric-X as part of the Linux Foundation Decentralized Trust at \url{github.com/hyperledger/fabric-x}. We decompose the monolithic peer into independently scalable microservices for endorsement, validation, and committing. To maximize parallelism, we introduce a transaction dependency graph that enables the safe, concurrent validation of transactions across multiple blocks. Complementing the peer redesign, we introduce Arma, a novel sharded Byzantine Fault Tolerant (BFT) ordering service that dramatically increases throughput by ordering compact transaction digests rather than full transaction payloads. We implemented and benchmarked this framework with a UTXO-based CBDC application. Our evaluation demonstrates a peak throughput exceeding 100,000 transactions per second (TPS)—a multiple-orders-of-magnitude improvement over the standard implementation. This work proves that permissioned DLTs can be engineered for national-scale payment systems, providing a resilient and highly performant foundation for practical CBDC deployments and the integration of advanced, computationally intensive features.