In this paper, we study the problem of sampling random supersingular elliptic curves with unknown endomorphism rings. This problem has recently gained considerable attention as many isogeny-based cryptographic protocols require such ``secure'' curves for instantation, while existing methods achieve this only in a trusted-setup setting. We present the first provable quantum polynomial-time algorithms for sampling such curves with high probability, one of which is based on an algorithm of Booher et. al. One variant runs heuristically in $\tilde{O}(\log^{6.5} p)$ quantum gate complexity, and in $\tilde{O}(\log^{20} p)$ under the Generalized Riemann Hypothesis, and outputs a curve that is provably secure assuming quantum average-case hardness of the endomorphism ring problem. Another variant samples uniform $\mathcal O$-oriented curves with unknown endomorphism rings, for any imaginary quadratic order $\mathcal O$, with security based on the quantum average-hardness of Vectorization problem. When accompanied by an interactive quantum computation verification protocol, our algorithms provide a secure instantiation of the CGL hash function and related primitives and show quantum advantage over classical algorithms. Our analysis relies on a new spectral delocalization result for supersingular $\ell$-isogeny graphs: we prove the Quantum Unique Ergodicity conjecture and provide numerical evidence for complete eigenvector delocalization. We also prove a stronger $\varepsilon$-separation property for eigenvalues of isogeny graphs than that predicted in the quantum money protocol of Kane, Sharif, and Silverberg, thereby removing a key heuristic assumption in their construction.

This paper analyzes differential probabilities in one Feistel round with binary-encoded modular-linear maps or rounded linear maps as internal components. For any fixed round key and any nonzero input difference chosen independently of the matrix instance, the output-difference distribution is uniform after averaging over the instance distribution. For a fixed instance, the 2-adic valuations of the relevant matrix entries deterministically fix certain output-difference bits. We consider an adversary that selects a low-weight input difference maximizing the number of fixed bits and derive lower bounds on the restricted maximum differential probability and its average over instances. The matrix-averaged lower bound is expressed in terms of the exponential moment of the maximum fixed-bit count and is compared with the generic lower bound induced by differential-pair symmetry.

Fully homomorphic encryption (FHE) is an appealing and promising solution for privacy-preserving transformer inference to protect users' privacy. However, the huge computational overhead makes it unrealistic to apply FHE in real-world transformers for large language models (LLM). Current FHE-based approaches to secure transformer inference face significant performance challenges, with total latency exceeding 5 hours for 32-input batches. The feedforward block, comprising a large-scale matrix multiplication followed by a GELU evaluation, is widely recognized as one of the most computationally intensive components in privacy-preserving transformer inference. In the state-of-the-art system NEXUS, evaluating the feedforward block incurs a total latency of 5,378 seconds, processing up to 32 inputs per batch. We aim to reduce the latency and propose LEAF, a low-latency evaluation architecture for the feedforward block. LEAF introduces a novel combination of fast matrix multiplication and an asymptotically efficient algorithm for computing non-polynomial activations. When evaluated on the BERT-base model, LEAF reduces total latency to 53.4 seconds, offering a $100\times$ speedup over the state-of-the-art method in the same environment. Our implementations are available.

Pairing-based multilinear polynomial commitments offer succinct verification for sum-check-based proof systems, but existing schemes trade prover group work against proof size and verifier cost. Building on Mercury's representation of a multilinear evaluation as the constant coefficient of a Laurent polynomial, we construct two schemes with different performance trade-offs. Vela uses inversion symmetry to derive a half-length auxiliary polynomial and opens two polynomials at $z$ and $z^{-1}$ with one univariate KZG proof; the fourth evaluation is not transmitted but recovered from the Laurent evaluation identity. It has a $2\mathbb{G}_1+3\mathbb{F}$ proof, a two-term pairing check, and approximately $2N$ opening MSM scalars, at the cost of $O(N\log N)$ field operations. Carina applies the same constant-term reduction once in each coordinate and jointly proves evaluation claims for the committed bivariate polynomial and two auxiliary polynomials with one grid opening. For $N=2^{\mu}$ and $b=\sqrt{N}$, it has a $4\mathbb{G}_1+8\mathbb{F}$ proof, a three-term pairing check, $O(N)$ field operations, and exactly $N+2b-6$ opening MSM scalars. We prove perfect evaluation completeness, computational commitment binding, and knowledge soundness in the AGM and ROM, with explicit random-oracle error bounds under a falsifiable bilinear $q$-type DLOG assumption. Our curve-generic Rust implementation also provides common implementations of six pairing-based baselines. On BLS12-381 at $\mu=20$, Vela gives the smallest measured proof (200 bytes, 1.88x smaller than the next smallest) and a 2.16 ms verifier within single-run noise of the lowest measured. Carina's opening performance is in the same leading tier as the prover-oriented mKZG and CHOPIN implementations, while its 452-byte proof and 2.81 ms verifier improve on both. Compared with the verifier-oriented Mercury, Carina roughly halves opening time at the cost of a modest verifier slowdown.

Proof-carrying data (PCD) is a powerful cryptographic primitive for ensuring computational integrity in distributed settings. State-of-the-art PCD constructions based on accumulation schemes achieve practical prover efficiency and support a wide range of applications. However, realizing zero-knowledge for accumulation-based PCD remains challenging, particularly for high-degree relations. Existing solutions often incur substantial overhead due to the need for zero-knowledge in both the underlying non-interactive arguments of knowledge (NARKs) and accumulation schemes. In this work, we present new theoretical and practical improvements for zero-knowledge PCD. First, we propose a novel construction that eliminates the need for zero-knowledge NARKs by separating the compliance predicate and accumulation verification, thereby reducing proof size and improving efficiency. Second, we design an efficient zero-knowledge accumulation scheme for special sound protocols, introducing techniques such as masking vectors and zero-knowledge sum-check protocols to ensure privacy with minimal overhead. The theoretical analysis demonstrates that our construction achieves logarithmic proof size and verification time for d-degree NP relations, and outperforms existing solutions in both asymptotic and concrete complexity.

Succinct non-interactive arguments of knowledge (SNARKs) enable a prover to produce a short and efficiently verifiable proof of the validity of an arbitrary NP statement. Recent constructions of efficient SNARKs have led to interest in using them for a wide range of applications, but unfortunately, deployment of SNARKs in these applications faces a key bottleneck: SNARK provers require a prohibitive amount of time and memory to generate proofs for even moderately large statements. While there has been progress in reducing prover time, prover memory remains an issue. In this work, we describe Scribe, a new low-memory SNARK that can efficiently prove large statements even on cheap consumer devices such as smartphones by leveraging a plentiful, but heretofore unutilized, resource: disk storage. Instead of storing its (large) intermediate state in RAM, Scribe's prover instead stores it on disk. To ensure that accesses to state are efficient, we design Scribe's prover in a read-write streaming model of computation that allows the prover to read and modify its state only in a streaming manner. We implement and evaluate Scribe's prover, and show that, on commodity hardware, it can easily scale to circuits of size $2^{28}$ gates while using less than 750 MB of memory and incurring only $10$% proving latency overhead compared to a state-of-the-art memory-intensive baseline (HyperPlonk [EUROCRYPT 2023]) that requires much more memory.

Randomly permuting secret data vectors is a core building block in many privacy-preserving protocols, including those for analytics, advertising, and communication. Existing approaches either rely on computation-heavy public key cryptography and zero-knowledge proofs or scale poorly for large vectors due to use of a quasilinear-sized permutation network. This work presents a preprocessing approach to enable fast linear-time online shuffles in the malicious-secure two-party computation (2PC) setting. We propose FLOSS, a 2PC protocol for securely computing any interactive arithmetic permutation circuit, a notion we introduce to capture how higher level protocols are built on secret-shared field arithmetic and permutations. We show how secret-shared sorting (a subprotocol in data analytics) can be described as an arithmetic permutation circuit, and can thus be compiled to an efficient online 2PC protocol using FLOSS. Our implementation and evaluation confirm FLOSS performs online shuffles fast: shuffling $2^{20}$ elements in under 500ms, greater than $800\times$ faster than state-of-the-art alternatives.

Device identifiers like the International Mobile Equipment Identity (IMEI) are crucial for ensuring device integrity and meeting regulations in 4G and 5G networks. However, sharing these identifiers with Mobile Network Operators (MNOs) brings significant privacy risks by enabling long-term tracking and linking of user activities across sessions. In this work, we propose a privacy-preserving identifier checking method in 5G. This paper introduces a protocol for verifying device identifiers without exposing them to the network while maintaining the same functions as the 3GPP-defined Equipment Identity Register (EIR) process. The proposed solution modifies the PEPSI protocol [USENIX, 2024] for a Private Set Membership (PSM) setting using the BFV homomorphic encryption scheme. This lets User Equipment (UE) prove that its identifier is not on an operator’s blacklist or greylist while ensuring that the MNO only learns the outcome of the verification. The protocol allows controlled deanonymization through an authorized Law Enforcement (LE) hook, striking a balance between privacy and accountability. Implementation results show that the system can perform online verification within five seconds and requires about 15 to 16 MB of communication per session. This confirms its practical use under post-quantum security standards. The findings highlight the promise of homomorphic encryption for managing identifiers while preserving privacy in 5G, laying the groundwork for scalable and compliant verification systems in future 6G networks.

Error-correcting codes play a central role in modern cryptography, enabling efficient constructions of primitives such as zero knowledge proofs and secure multiparty computations. Among them, repeat-accumulate-accumulate (RAA) codes have recently attracted significant attention due to their linear-time encoding and good distance properties. However, prior work only established provable distance guarantees over the binary field or over finite fields whose size is smaller than the message length. The underlying techniques do not extend to larger fields. This restriction is significant, as many cryptographic constructions based on error-correcting codes operate over large finite fields. In this paper, we prove that RAA codes achieve constant relative distance $0<\delta\le \frac{1}{2}$ with high probability over large finite fields. Moreover, we resolve an open conjecture by showing for the first time that the distance of RAA codes improves over large fields. We provide both theoretical analysis and empirical evidence demonstrating that, compared to the binary case, large fields yield strictly better distance guarantees with much smaller failure probabilities. Our empirical evaluation shows that for message length $n=2^{20}$ and repetition factor $r=4$, the RAA code over a 31-bit prime field achieves relative distance $1/2$, except with failure probability $2^{-20}$. This is better than the best provable distance of $\delta = 0.2$ with failure probability $2^{-10}$ over the binary field. Leveraging our improved distance bounds, we obtain a 2.6$\times$ reduction in the proof size of a polynomial commitment scheme based on RAA codes compared to using the binary-field bound, and a 5.4$\times$ reduction compared to a prior construction based on expand-accumulate codes.

Anonymity guarantees of privacy-oriented cryptocurrencies are garnering negative attention from lawmakers who view them as antinomic to accountability. Having recognized their potential for innovation, however, regulators may not want to outright ban privacy coins but instead seek a middle ground where financial oversight is effective, and still some privacy is maintained. Mature designs, such as Zcash, Monero, or Firo, facilitate this through so-called viewing keys that can be disclosed to third parties for the purpose of supervision. This paper studies which privacy guarantees continue to hold once they have been. In doing so, it fills the gap in provable anonymity guarantees for Zcash and Firo under incoming viewing key disclosure, while, at the same time, exposing problems with Monero. Finally, the paper shows that malicious parties may happily surrender all viewing keys in each of Zcash, Monero, and Firo and still find very efficient ways of evading financial monitoring.

UOV and its variants have been submitted to NIST's PQC Standardization Project. And security analysis against UOV families (i.e., UOV and its variants) are typically categorized into key-recovery attacks and forgery attacks, with the XL algorithm serving as one of the most significant methods for mounting key-recovery attacks. Recently, Lars Ran introduced a novel key-recovery attack against UOV families that could be seen as an XL attack using exterior algebra; nevertheless, this new XL attack is applicable only when the underlying (finite) field of UOV instances is of characteristic $2$. In this work, we address this limitation by generalizing Lars Ran's approach, and our contributions are three-fold. First, we generalize the notion of exterior algebra and propose the notion of reduced symmetric algebra over any field, which is essentially symmetric algebra when the characteristic $p$ of the underlying field is $0$ and is exterior algebra when $p=2$. Moreover, based upon the reduced symmetric algebra, we propose a new XL attack against all UOV families: as a generalization of Lars Ran's attack, our XL attack also works for those UOV instances with odd characteristic; for instance, it works for those $12$ recommended QR-UOV instances submitted to NIST's PQC Standardization Project, although its performance does not outperform those of the existing key-recovery attacks. Finally, analysis on our XL attack reveals the connection between the characteristic $p$ and the concrete hardness of UOV instances.

P vs NP problem is the most important unresolved problem in the field of computational complexity. Its impact has penetrated into all aspects of algorithm design, especially in the field of cryptography. The security of cryptographic algorithms based on short keys depends on whether P is equal to NP. In fact, the security requirements for cryptographic keys are much stricter than those for P$\neq$NP, the security of the key must ensure not only a sufficiently high computational complexity to crack it, but also consider the security of each bit of the key, while fully avoiding the effectiveness of various attack methods. In this paper, we innovatively propose a new encoding mechanism and develop a novel block symmetric encryption algorithm, which be named Eagle, whose encryption and decryption can be completed in linear time. The key consists of 6 variables，for the attacker, in the case when only the plaintext-ciphertext correspondence is known, the problem of cracking the key is equivalent to solving a system of equations about six unknown variables. The computational complexity of verifying two variables should not be lower than the computational complexity of enumerating any intermediate unknown variable whose number of possible values is exponentially to the length of the key, thus proving that the computational complexity of verifying two variables is exponential. Due to the computational complexity satisfying the condition of ``complexity of cracking the key = complexity of solving the six variables $\geq$ complexity of solving the two variables $\geq$ complexity of verifying the two variables", thus the computational complexity of cracking the key is at least exponential, So the decryption is a one-way function, and according to ``the existence of one-way function means P$\neq$NP", thus solving the unsolved problem of P vs NP. In addition, this paper delves into the underlying mathematical laws of this new encoding mechanism, and develops a right multiplication operation to binary. Based on this right multiplication operation, we further constructed a nonlinear operation and designed another block symmetric encryption algorithm, which be named $Eagle^{*}$. The key of $Eagle^{*}$ is composed of three independent variables. Given any plaintext ciphertext correspondences, the problem of verifying any two variables in the key is equivalent to solving a system of quintic equations. Based on the conclusion that there are no algebraic solutions to quintic equations, we assert that there is no fast algorithm to verify any two variables, and thus the computational complexity of cracking the key is equal to the computational complexity of completely exhausting the three variables. In addition, we conducted an in-depth analysis that without cracking the key, it is not possible to directly decrypt new ciphertext by simply collecting a large number of ciphertext plaintext correspondences. Due to the fact that ciphertext consists of two parts, one part is a completely randomly generated random number, while the other small part is calculated using plaintext, algorithms, and random numbers, and its distribution is also completely random, thus $Eagle^{*}$ is resistant to all forms of linear and differential attacks.

Multi-key fully homomorphic encryption (MKFHE) enables computation over encrypted data under multiple different keys. Constructing MKFHE without any trusted or interactive setup remains an open problem. In the context of MKFHE, a trusted setup is often assumed to mean the use of a common random string (CRS). In this paper, we present the first MKFHE scheme in the plain model (i.e., without any trusted or interactive setup) based on the RLWE assumption. Specifically, we construct a multi-key somewhat homomorphic encryption based on the RLWE assumption and extend it to a multi-key variant of the Gentry-Sahai-Waters (GSW) scheme with a circular security assumption. Our design yields a 2-round multi-party computation (MPC) in the plain model against semi-honest adversaries. Moreover, it can be applied to transform existing FHE schemes that rely on RGSW in their construction into a multi-key variant. We also provide concrete conversions for widely-used FHE schemes, including BGV, BFV, CKKS, FHEW, TFHE, and Carousel. Finally, we implement our scheme and present experimental results for the expansion algorithm from a single-key ciphertext to a multi-key ciphertext and the multi-key homomorphic multiplication algorithm.

Threshold fully homomorphic encryption (ThFHE) enables decryption by collecting decryption shares from any T-out-of-N parties. A major drawback of previous ThFHE schemes is that they require a super-polynomial modulus (or are subject to other limitations), resulting in long ciphertexts, keys, and decryption shares. Passel`egue and Stehl´e (Asiacrypt 2024) proposed a ThFHE scheme in which a semi-trusted server rounds the input ciphertexts to produce polynomially short ciphertexts and sends them to the parties, thereby making the rest of the decryption process efficient. Although the input ciphertexts are still super-polynomially large, the communication cost of sending them from the parties to the server can be reduced to polynomial size via the transciphering technique; as a result, an entirely low-communication ThFHE is achieved. However, if even a single party colludes with the server (contrary to the assumption), the secret key can be efficiently recovered. Such a risky scenario would be unsuitable for practical deployment. In this paper, we tackle this issue. We propose two serverless ThFHE schemes with polynomially short decryption shares. The core idea is to let the parties directly round the decryption shares, rather than rely on the semi-trusted server to round the ciphertexts. We can also achieve low-communication ThFHE by reducing the communication required to send input ciphertexts to the parties to polynomial size via transciphering. Our first scheme, based on binary coefficient linear secret sharing ({0,1}-LSS), strictly improves upon Boneh et al. (CRYPTO 2018), achieving short decryption shares without any trade-offs. Our second scheme, based on Shamir secret sharing, adapts the technique of Okada and Takagi (Asiacrypt 2025) to eliminate the $O(N^{4.3})$ overhead in share size of our first scheme, further reducing communication costs.

Cloud-based Large Language Model (LLM) inference processes sensitive user inputs, yet current deployments offer limited confidentiality guarantees. Fully Homomorphic Encryption (FHE) can provide strong privacy, but it clashes with transformer architectures, where rigid ciphertext packing demands expensive rotations, and deep polynomial circuits for nonlinearities necessitate costly bootstrapping. Although recent work has reported promising speed-ups, maintaining model accuracy is a challenge. We address these issues with ELLMo, a packing- and depth-aware encrypted transformer design. ELLMo introduces a novel matrix multiplication algorithm to reduce the ciphertext rotations. Further, head-split and merge steps are fused into this new algorithm at no additional cost. To reduce the depth of nonlinear layers, our contributions, Statistical-max Softmax and DelayNorm, help bypass deep comparison trees and homomorphic divisions to reduce bootstrapping by up to 46%. On encrypted BERT-Tiny, ELLMo achieves a $1.4\times$ speedup over state-of-the-art baselines with 0-1.5% accuracy loss across SST-2, MRPC, and RTE downstream tasks.

Searchable Symmetric Encryption (SSE) enables data owners to securely store encrypted data on untrusted cloud servers while retaining the ability to perform secure searches and retrieve relevant documents. However, standard SSE schemes expose search patterns (whether two queries are identical), and result patterns (which documents are returned), making them susceptible to leakage-abuse attacks that can infer sensitive information such as the queried keywords and/or document contents. While Oblivious RAM (ORAM) and Private Information Retrieval (PIR) can hide these patterns, their high computation and communication overhead often render them impractical for real-world search workloads. A more efficient alternative is to obfuscate search and result patterns using Differential Privacy (DP). Unfortunately, existing DP-based SSE schemes either provide insufficient query privacy protection, or still incur substantial performance overhead. In this paper, we propose FROST, a novel differentially private SSE scheme that efficiently obfuscates both search and result patterns, while providing strong resilience against all known statistical leakage-abuse attacks. The core component of FROST is our new rerandomized PIR (RePIR) scheme designed for private databases, which allows server-side rerandomization of encrypted PIR query responses. In FROST, we also introduce a novel method for applying DP noises to SSE for search result obfuscation using only simple arithmetic operations. An important property of FROST is that it requires only a single round of communication, with small user-side storage as an additional benefit. We fully implemented FROST and conducted extensive experiments over real-world datasets to rigorously assess its practical performance and resilience. Our experiments showed that FROST not only effectively mitigates pattern-leakage attacks while maintaining reasonable utility, but also achieves up to four orders of magnitude faster keyword search and three orders of magnitude lower bandwidth overhead than prior DP-based SSE schemes.

Quantum cryptography is a rapidly-developing area which leverages quantum information to accomplish classically-impossible tasks. In many of these protocols, quantum states are used as long-term cryptographic keys. Typically, this is to ensure the keys cannot be copied by an adversary, owing to the quantum no-cloning theorem. Unfortunately, due to quantum state's tendency to decohere, persistent quantum memory will likely be one of the most challenging resources for quantum computers. As such, it will be important to minimize persistent memory in quantum protocols. In this work, we consider the case of one-shot signatures (OSS), and more general quantum signing tokens. These are important unclonable primitives, where quantum signing keys allow for signing a single message but not two. Naturally, these quantum signing keys would require storage in long-term quantum memory. Very recently, the first OSS was constructed in a classical oracle model and also in the standard model, but we observe that the quantum memory required for these protocols is quite large. In this work, we significantly decrease the quantum secret key size, in some cases achieving asymptotically optimal size. To do so, we develop novel techniques for proving the security of cryptosystems using coset states, which are one of the main tools used in unclonable cryptography.

We focus on refined Humbert invariants of principally polarized superspecial abelian surfaces, introduced by Kani in 1994. The main contributions are to enumerate principal polarizations on a superspecial surface, and for each polarization, to compute the refined Humbert invariant of a principally polarized superspecial abelian surface. Then, we present several applications of computing this invariant for isogeny-based cryptography. First, we provide a decision algorithm to check if two given polarizations are isomorphic. Second, we present an efficient algorithm to determine the geometric type of a principally polarized superspecial surface. Third, we prove an upper bound on the largest minimal isogeny degree among pairs of supersingular elliptic curves, independent of their endomorphism-ring structures, and our experimental evidence verifies this claim up to $p=659$, $p\equiv 11\pmod{12}$. Fourth, we present experimental evidence for a minimum isogeny frequency within the proven upper bounds. Lastly, we provide a different perspective on the fixed isogeny degree problem using refined Humbert invariants and analyze it without explicit endomorphism rings.

Signature-based witness encryption (SWE) schemes recently emerged as a viable alternative to instantiate timed-release cryptography in the honest majority setting. In particular, assuming threshold trust in a set of parties that release signatures at a specified time, one can ``encrypt to the future'' using an SWE scheme. It offers stateless decryption, where parties producing the signatures do not need to know the ciphertexts in advance to perform decryption. This statelessness makes SWE vastly superior to regular threshold encryption for decentralized blockchain applications such as sealed-bid auctions and voting. However, the lack of homomorphism in existing SWE schemes severely bottlenecks their throughput and limits their deployment. In this work, we formally introduce Homomorphic SWE (HSWE) to resolve these limitations. We present a systematic suite of HSWE constructions designed to scale across varying message spaces without sacrificing statelessness. We first establish foundational HSWE schemes for binary messages using Cocks IBE and standard Learning With Errors (LWE). To support polynomially-sized message spaces, we construct a pairing-based scheme that features an efficient multi-pairing optimization for cross-tag aggregation. For exponentially large message spaces, we transition to a Ring-LWE construction that achieves high-throughput polynomial packing with post-quantum security. Moreover, we address the inherent privacy limitation of public stateless aggregation by proposing a framework that perfectly hides individual plaintexts and only reveals the final aggregated result. We also present an empirical performance evaluation in Rust to highlight the impact of homomorphism in practical deployments.

We present a new framework for constructing practically efficient publicly verifiable secret sharing(PVSS) with non-interactive dealers, in that the dealer may go offline after sending a single message, and is not involved in the share verification process. We use identity-based encryption (IBE) and commitments as the main ingredients and avoid expensive zero-knowledge proofs. Instantiating them with post-quantum secure schemes, a lattice-based IBE and a hash-based commitment, we obtain our first construction - a post-quantum secure PVSS with non-interactive dealers that outperform the prior lattice-based practical construction, Gentry et al. [Eurocrypt 2022] by two orders of magnitude. However, to enable the aggregation of PVSS transcripts (which facilitates many additional applications such as secure voting), we propose our second construction by replacing hash-based commitments with Pedersen's homomorphic commitments. While this does not achieve full-fledged post-quantum security (as Pedersen's scheme is not quantum safe), it still provides privacy against a post-quantum adversary. We prove the security of this construction in a new model, which we call long-lasting security. This model guarantees that the protocol is secure in the present (pre-quantum era) while maintaining privacy in the long term (post-quantum era). This new model is of independent interest for constructing efficient schemes that are resilient to harvest-now-decrypt-later line of attacks. In this model, we propose a blockchain-compatible secure voting scheme using our PVSS scheme. Our PVSS schemes demonstrate practical efficiency: our post-quantum PVSS shares a secret among $1024$ receivers in $692$~ms and verifies the dealing in $128$ ms, and communicates $4$MB, overall yielding a two orders of magnitude improvement over the state of the art [Gentry et al., Eurocrypt 2022].

In this short note, we show that two identity-based encryption schemes, introduced by Joye and Zhao et al., which appear different, are essentially the same scheme. The only difference between them is that one prioritizes speed (Zhao et al.), while the other prioritizes bandwidth (Joye). We also show how to speed-up Joye's scheme at the cost of adding at most one integer to the public key, thereby achieving a better encryption complexity, while having the same bandwidth requirements.

We show how to translate some of the more advanced techniques used in LWE-based cryptography to the setting of lattice-isomorphism-based cryptography, which was recently introduced by Ducas and van Woerden [Eurocrypt, 2022]. In particular, we show constructions of two powerful cryptographic primitives, identity-based encryption (IBE) and leveled fully homomorphic encryption (FHE). We then prove their security under the assumption that a suitable version of the Lattice Isomorphism Problem is hard. Our constructions use quite general and modular techniques, and we expect them to have other applications. Specifically, we show that the now-ubiquitous techniques introduced by Gentry, Peikert, and Vaikuntanathan [STOC, 2008] to build IBE and Gentry, Sahai, and Waters [Crypto, 2013] to build FHE can be made to work in our setting using any sufficiently ``nice'' lattice.

Overbroad computer crime, intellectual property, and other laws are well known to create legal risks that can discourage essential research. Notable examples include the US Computer Fraud and Abuse Act and the UK Computer Misuse Act. Because such laws fail to distinguish malicious hacking from good-faith testing and research, researchers face serious legal risks for public-interest research activity like identifying software or hardware vulnerabilities or scraping data. Despite the research community's broad awareness of these risks, our understanding of their practical impacts is limited, as most of the community's knowledge comes from anecdotal evidence rather than systematic study. We conduct the first qualitative study focused on researchers' lived experiences, to empirically document the *impacts of legal risks and threats* on research and researchers*, and *how researchers navigate legal risk situations*. Our study engages two participant groups: researchers with legal-risk experiences in the UK or the US ($N_R=36$), who discuss 130 projects and incidents spanning over three decades, and professionals that offer support to researchers navigating legal risks ($N_S=8$), who have collectively supported thousands of researchers. We thus provide an unprecedented big-picture view of researchers' experiences with legal risks. We synthesise actionable strategies for researchers, and our findings provide evidence to support policy reform.

In this paper, we analyze the clash between privacy-oriented cryptocurrencies and emerging legal frameworks for combating financial crime, focusing in particular on the recent European Union regulations. We analyze Monero, a leading "privacy coin" and a major point of concern for law enforcement, and study the scope of due diligence that must be exercised under the new law with regard to Monero trading platforms and how it translates to the technical capabilities of the Monero protocol. We both recognize flaws in the legislation and identify technical pitfalls threatening either the effective compliance of, say, Monero exchanges or the anonymity endeavour of Monero itself. Of independent interest is that we turn to anamorphic cryptography (marking one of the first practical applications of the concept) and leverage it to build a hidden transaction layer embedded in the Monero blockchain that obfuscates illegal money flow and circumvents transaction-level attempts at enforcing the EU law.

This paper proposes a systematic approach to compute cryptanalytic properties of arbitrary Mealy machines or S-functions. Based on the geometric approach to cryptanalysis, we provide a uniform formula for any cryptanalytic property of such a function, as long as the property is compatible with the way its input and output are split into chunks. Examples include linear, (quasi) differential, (ultrametric) integral, differential-linear, and boomerang properties. To illustrate our results, we compute these properties for several important examples, including modular additions, the Chi- and ChiChi-functions, and the SHA-1 step function. As proof-of-concept applications, we construct a boomerang distinguisher for the Subterranean permutation, and show how to compute the correlations of conditional linear approximations in partitioning-based differential-linear attacks more accurately. Our results also lead to a new approach to compute the algebraic normal form of the inverse of the Chi-function.

Threshold signatures are a fundamental primitive in applied cryptography, primarily used to mitigate the custodial risk involved in managing keys. However, existing constructions rely on synchronous communication assumptions and fixed participant sets, limiting their applicability to real-world networks. In addition, as the committees managing those keys serve an ever-growing number of clients and assets, they become lucrative targets for attacks. This issue is often called the Honeypot Problem. A recent work proposed the 2PC-MPC paradigm, in which a client and a decentralized network jointly generate signatures, aiming to mitigate this issue. In this work, we present the first asynchronous 2PC-MPC protocol for ECDSA signatures, designed to operate over reliable broadcast channels as implemented in modern blockchains. Our protocol tolerates dynamic, post-determined quorums whose participants may change between rounds. This allows the protocol to align with asynchronous consensus layers while providing identifiable abort, public verifiability, guaranteed output delivery (assuming completeness of the broadcast channel) and censorship resistance for the client. We introduce global presigns, which are generated autonomously by the network and remain client-agnostic until signing. This enables effective background preprocessing, and results in sub-second online signing network-side latency for dozens of concurrent clients. From a technical perspective, our asynchronous design eliminates commitment rounds, yielding one-round client interaction for both key generation and signing. We also remove the need for zero-knowledge proofs toward the client. This results in a client complexity independent of network size, without proof aggregation (which is particularly challenging over asynchronous channels). Our constructions are proven UC-secure in the asynchronous setting. To achieve concrete security over 256-bit elliptic curves, we introduce the Slightly-Enhanced ECDSA Unforgeability assumption and provide a tight reduction in the EC-GGM model. Beyond theoretical analysis, we implement our protocols and evaluate them in both a local benchmark and a live permissionless deployment with dozens of validators, demonstrating practical performance and robustness under heterogeneous execution speeds.

Byzantine Agreement (BA) protocols must ensure not only agreement and termination, but also validity: the value agreed upon should meaningfully reflect the honest parties' inputs. The choice of validity condition can change the exact resilience threshold at which BA is solvable. Tight characterizations for BA with general validity conditions are known in the partially synchronous model (PODC'23), in the synchronous model (PODC'24), and in the network-agnostic model (DISC'25). We focus on general validity for synchronous BA with responsive termination. Such protocols remain secure against up to $t_s$ byzantine corruptions, but incur a running time that depends on the actual network delay $\delta$, rather than the conservative delay bound $\Delta \gg \delta$, whenever at most $t_r \leq t_s$ parties are corrupted. We present a tight characterization of the validity properties solvable in this setting. We prove that every non-trivial validity property requires $n>2 t_r+t_s$ in authenticated settings, where a public-key infrastructure and digital signatures are available, and $n>3 t_s$ in unauthenticated settings. These threshold conditions are accompanied by a validity-dependent requirement, the responsive similarity condition: roughly, for any concrete configuration of honest inputs, there is a value that is valid for any view that a protocol could obtain from this initial configuration. We then present matching protocols in both settings, showing that these conditions are sufficient. The main technical contribution is an authenticated responsive Core-Set Agreement protocol requiring $n>2 t_r+t_s$. This threshold may place the protocol in an honest-minority regime, where prior constructions for general validity do not apply and where standard Synchronous Broadcast is not responsive. Finally, we instantiate the characterization for several standard validity notions -- weak validity, strong unanimity, convex validity, and honest-input validity.

Elliptic Curve Cryptography (ECC) underpins modern public-key infrastructure, relying on the computational hardness of the Elliptic Curve Discrete Logarithm Problem (ECDLP). While monolithic quantum computers running Shor's algorithm present a long-term threat to ECC, their physical realization is bottlenecked by the massive logical qubit demands of modular arithmetic—specifically modular inversion. Distributed Quantum Computing (DQC) offers a compelling alternative by linking smaller, cooperative quantum processing units (QPUs). In this paper, we adapt two distributed quantum algorithms to the elliptic curve setting and perform a rigorous resource estimation of their architectures. Integrating the compact, register-sharing Extended Euclidean Algorithm (EEA) formulation by Luo et al., we demonstrate distinct resource footprints for each approach on a cryptographically secure 256-bit elliptic curve. Specifically, Xu et al.'s zero-quantum-communication variant requires between 1094 and 1154 logical qubits per node (depending on the search window configuration), while Li et al.'s sequential quantum-communication-based variant can be realized with as few as 856 to 1098 logical qubits per node (depending on the number of participating network nodes). Furthermore, by tuning the window size to $\omega = 16$ across a network of $k = 65$ nodes, we reduce the per-node Toffoli gate count to $2^{26.30}$, achieving approximately a $20\times$ gate count reduction compared to the baseline monolithic scheme by Luo et al. Our comparative analysis maps out the critical trade-offs between quantum communication overhead, classical coordination, and single-node hardware constraints, establishing a clear design space for fault-tolerant distributed quantum cryptanalysis.

We introduce Lether, the first practical account-based private block-chain payment protocol based on post-quantum lattice assumptions, following the paradigm of Anonymous Zether (FC '19, IEEE S&P '21). The main challenge in building such a protocol from lattices lies in the absence of core building blocks: unbounded-level additively-homomorphic multi-message multi-recipient public key encryption (mmPKE), and event-oriented linkable ring signatures with support for multiple tags (events). To address these issues, we propose a verifiable refreshable additively-homomorphic mmPKE scheme and a plug-and-play event-oriented linkable tag scheme from lattices. We believe both to be of independent interest To achieve unbounded-level homomorphic evaluation in the lattice-based setting without relying on heavy techniques such as bootstrapping or large moduli (e.g., over 60 bits) in fully homomorphic encryption (FHE), we introduce a simple yet blockchain-friendly mechanism called refresh. Namely, each user is required to verifiably refresh their account after a certain number of transactions. With our tailored parameter settings, the amortized per-refresh costs of communication and computation are only about 1.3% and 1.5%, respectively, of the cost of a transaction. We also optimize the implementations of LNP22 lattice-based zero-knowledge proof system (Crypto '22) in the LaZer library (CCS ’24), to support efficient batching of various proof components.Overall, for a typical transaction, the total communication cost becomes about 68 KB, with the associated zero-knowledge proof accounting for about 51 KB of this total. Each of proof generation and verification take a fraction of a second on a standard PC. As an additional contribution, we formalize new definitions for Anonymous Zether-like protocols that more accurately capture real-world blockchain settings. These definitions are generic and are expected to benefit the broader development of account-based private blockchain payment protocols, beyond just lattice settings.

Succinct non-interactive arguments of knowledge (SNARKs) based on lattice assumptions offer a promising post-quantum alternative to pairing-based systems, but have until now suffered from inherently quadratic proof sizes in the security parameter. We introduce RoK and Roll, the first lattice-based SNARK that breaks the quadratic barrier, achieving communication complexity of $\tilde{O}(\lambda)$ together with a succinct verification time. The protocol significantly improves upon the state of the art of fully-succinct argument systems established by ``RoK, Paper, SISsors'' (RPS) [ASIACRYPT'24] and hinges on two key innovations, presented as reductions of knowledge (RoKs): - Structured random projections: We introduce a new technique for structured random projections that allows us to reduce the witness dimensions while approximately preserving its $\ell_2$ norm and maintaining the desired tensor structure. In order to maintain succinct communication and verification, the projected image is further committed and adjoined to the original relation. This procedure is recursively repeated until dimension of the intermediate witness becomes $\mathsf{poly}(\lambda)$, i.e. independent of the original witness length. - Unstructured random projection: When the witness is sufficiently small, we let the unstructured projection (over coefficients $\mathbb{Z}_q$) be sent in plain, as in LaBRADOR [CRYPTO'23]. We observe, however, that the strategy from prior works to immediately lift the projection claim to $\mathcal{R}_q$, and into our relation, would impose a quadratic communication cost. Instead, we gradually batch-and-lift the projection a the tower of intermediate ring extensions. This reduces the communication cost to $\tilde{O}(\lambda)$ while maintaining a succinct verification time. These two techniques, combined with existing RoKs from RPS, yield a succinct argument system with communication complexity $\tilde{O}(\lambda)$ and succinct verification for structured linear relations.

PRISM (PKC25) is a hash-and-sign signature scheme whose security relies on the hardness of computing large-prime-degree isogenies originating from a curve of unknown endomorphism ring. In PRISM, the degree of such isogenies is obtained by hashing messages onto a set of large odd integers that pass a primality test. In this work, we investigate the impact of the choice of primality test on the security of PRISM. We first show that when a weak primality test is used, the assumption underlying the security proof in the standard model does not hold. We then extend our analysis to the assumption used in the security proof in the (quantum) random oracle model. In this setting, we argue that the Miller-Rabin test suffices and estimate the minimal number of iterations required for PRISM to achieve the desired security level, thus minimising signing costs.

The problem of computing an isogeny of large prime degree from a supersingular elliptic curve of unknown endomorphism ring is assumed to be hard both for classical as well as quantum computers. In this work, we first build a two-round identification protocol whose security reduces to this problem. The challenge consists of a random large prime $q$ and the prover simply replies with an efficient representation of an isogeny of degree $q$ from its public key. Using the hash-and-sign paradigm, we then derive a signature scheme with a very simple and flexible signing procedure and prove its security in the standard model. The most efficient variant of our signature schemes features a signing which is $1.4\times$ to $1.6\times$ faster than the most recent implementaion of SQIsign, whereas verification ranges from $1.2\times$ slower to $1.01\times$ faster depending on the security level. The sizes of public key and signature are comparable to existing schemes.

Private constrained PRFs are constrained PRFs where the constrained key hides information about the predicate circuit. Although there are many constructions and applications of PCPRF, its relationship to basic cryptographic primitives, such as one-way functions and public-key encryptions, has been unclear. For example, we don't know whether one-way functions imply PCPRFs for general predicates, nor do we know whether 1-key secure PCPRF for all polynomial-sized predicates imply public-key primitives such as public-key encryption and secret-key agreement. In this work, we prove the black-box separation between a 1-key secure PCPRF for any predicate and a secret-key agreement, which is the first black-box separation result about PCPRF. Specifically, we prove that there exists an oracle relative to which 1-key secure PCPRFs exist while secret-key agreement does not. Our proof is based on the simulation-based technique proposed by Impagliazzo and Rudich (STOC 89). The main technical challenge in generalizing the simulation-based technique to PCPRF is the issue of \textit{unfaithfulness} of Eve's simulation to the real world because our oracle is more complicated than a random oracle. We introduce a new technique which we call the ``weighting" technique and show how to leverage it to circumvent the issue of unfaithfulness in the proof framework of Impagliazzo and Rudich.

Sleepy consensus allows parties to join and leave execution arbitrarily, which is a fundamental requirement for large-scale distributed systems. Classic longest-chain protocols, such as Bitcoin and its variants, achieve consensus under this model but suffer from inherent long latency. In contrast, recent protocols that build upon the classic view-based BFT paradigm can achieve constant expected latency and short best-case latency under optimal resilience, but they often incur high communication cost. We observe that the high communication overhead stems from the time-shifted quorums, a technique that makes quorum certificates transferable under dynamic participation. The technique relies on extensive message forwarding to reconcile parties' inconsistent local views, and thus incurs a cubic communication cost unavoidably. In this work, we tackle the problem by proposing a novel way to transfer certificates. Building on this, we construct a Byzantine Agreement (BA) protocol secure against the state-of-the-art growing adversary model. Our BA protocol achieves optimal resilience, constant expected round complexity, and an expected communication complexity of $O(nNL+nN\kappa+nN\log N)$, where $n$ is the maximum number of awake parties throughout the execution, $N$ is the total number of eligible parties, $L$ is the input length, and $\kappa$ is the security parameter. We also present an efficient recovery mechanism for our BA, incurring only $O(N\kappa+nL)$ bits per recovering party. Then we extend our BA to an Atomic Broadcast (ABC) protocol that achieves optimal resilience, constant expected latency, and an expected amortized communication complexity of $O(nNL+nN\kappa+nN\log N)$ per input value. The recovery mechanism for our ABC incurs $O(N\kappa+n\ell L+n\ell \kappa)$ bits per recovering party, where $\ell$ is the number of views that the party has slept for. Last but not least, we establish communication lower bounds of $\Omega(N^2L)$ for sleepy BA and ABC. The result shows that our BA and ABC are communication-optimal when $L$ is sufficiently large (i.e., when $L=\Omega(\kappa+\log N)$), and highlights a fundamental limitation of communication efficiency in the sleepy model.

At ASIACRYPT 2021, Baksi et al. introduced DEFAULT, a block cipher designed to algorithmically resist Differential Fault Attack (DFA), claiming 64-bit DFA security regardless of the number of injected faults. At EUROCRYPT 2022, Nageler et al. demonstrated that DEFAULT's claimed DFA resistance can be broken by applying an information-combining technique. More recently, at ASIACRYPT 2024, Jana et al. improved DFA by searching for differential trails with a single solution. They showed that, for DEFAULT with a simple key schedule, injecting five faults at the fifth-to-last round reduces the key space to one, and for BAKSHEESH, injecting twelve faults at the third-to-last round achieves the same result. In this paper, we propose a new DFA framework that utilizes a Mixed-Integer Linear Programming (MILP) solver. This framework makes it possible to attack deeper rounds than previously achieved, reducing the number of fault injections required for key recovery. Furthermore, we present a method to determine the most efficient fault injection bit positions by systematically analyzing the input differences from all possible single bit-flip faults, thereby further reducing the required number of faults. This systematic analysis has the significant advantage of allowing us to theoretically calculate the required number of faults. Applying our framework, for DEFAULT, injecting three faults at the sixth-to-last round and two faults at the seventh- and eighth-to-last rounds reduces the key space to one.

The current gold standard of cryptographic software is to write efficient libraries with systematic protections against timing attacks. In order to meet this goal, cryptographic engineers increasingly use high-assurance cryptography tools. These tools guide programmers and provide rigorous guarantees that can be verified independently by library users. However, high-assurance tools reason about overly simple execution models that elide micro-architectural leakage. Thus, implementations validated by high-assurance cryptography tools remain potentially vulnerable to micro-architectural attacks such as Spectre or Meltdown. Moreover, proposed countermeasures are not used in practice due to performance overhead. We propose, analyze, implement and evaluate an approach for writing efficient cryptographic implementations that are protected against Spectre v1 attacks. Our approach ensures speculative constant-time, an information flow property which guarantees that programs are protected against Spectre v1. Speculative constant-time is enforced by means of a (value-dependent) information flow type system. The type system tracks security levels depending on whether execution is misspeculating. We implement our approach in the Jasmin framework for high assurance cryptography, and use it for protecting all implementations of an experimental cryptographic library that includes highly optimized implementations of symmetric primitives, of elliptic-curve cryptography, and of Kyber, a lattice-based KEM recently selected by NIST for standardization. The performance impact of our protections is very low; for example, less than 1% for Kyber and essentially zero for X25519.

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

A blind signature scheme is an interactive protocol that enables a user to obtain a signature on a message without revealing any information about the message–signature pair to the signer. Despite more than 40 years of research, all existing constructions suffer from at least two of the following limitations. 1. The protocol is not round-optimal, requiring more than two messages to be exchanged during the signature phase. 2. There is only game-based security and/or lack of composability with global and observable setup (i.e., there is a need for trusted parameters or to program random oracles). 3. Security (unlike regular signatures) is based on demanding hardness assumptions, especially when considering quantum attacks. In this work, we show how to blindly sign a message, simultaneously overcoming all of the above three limitations. Specifically, we construct a Universally Composable (UC), two-round (optimal) blind signature protocol that relies only on one-way functions (optimal), without trusted parameters. The only deviation from the plain model is the need for a global non-programmable random oracle (NPRO). Nicely, our scheme can be instantiated from a variety of assumptions believed to be post-quantum secure (e.g., AES). A central technical component of our scheme is the construction of a novel commitment scheme that enjoys a special (mild) form of composability, which may be of independent interest. We also discuss a concrete instantiation of our scheme that is suitable for practical applications.

Public blockchains expose all state and computation by default, which is incompatible with financial applications that require confidentiality. Solana achieves high throughput and sub-second confirmation, making it an attractive settlement layer, yet it offers no general mechanism for computing over encrypted state: fully homomorphic encryption (FHE) remains orders of magnitude too slow for interactive use, secure multi-party computation (MPC) incurs heavy communication, and Solana’s native confidential-transfer extension hides only token amounts and supports no programmable logic. We present Encifher, a confidentiality coprocessor for Solana that brings general, programmable computation over encrypted state to a high-throughput chain. Encifher adopts the ciphertext-handle and symbolic-execution interface of confidential-computing coprocessors (e.g., Zama’s fhEVM), but resolves it inside a Trusted Execution Environment (TEE) rather than with a fully homomorphic evaluator: on-chain Solana programs manipulate only 128-bit handles to ciphertexts, while an off-chain coprocessor running inside a hardware enclave fetches the corresponding ciphertexts from a public data availability layer, decrypts and computes on plaintext within the enclave, re-encrypts, and commits attested, Merkle-anchored results back on chain. A key observation is that Solana’s account model and parallel (Sealevel) scheduler turn the transaction’s declared read/write set into the dependency graph of the confidential computation, yielding parallel, correctly-ordered execution of encrypted operations without a bespoke scheduler. To avoid the single-point-of-failure of an enclave holding a master decryption key, Encifher distributes trust across a threshold-decryption committee and verifies enclave attestation on chain. Encifher is deployed in production, powering confidential payments, swaps, and a cross-chain bridge. In production, a confidential swap settles in a single Solana transaction costing 157,000 compute units; the AES-256-GCM symmetric-encryption layer runs at over a million operations per second and threshold decryption completes in single-digit to tens of milliseconds (near-plaintext speed, against the many-orders-of-magnitude overhead of FHE), and Encifher has served over 5,000 users and 50,000 confidential operations. We are explicit about the cost of this design point: Encifher reduces the trust base to TEE integrity, honest threshold key management, and the cloud attestation root, rather than to cryptographic hardness alone.

Post-quantum assumptions may not rely on the difficulty of finding secret subgroups as many classical schemes did. Instead, several assumptions make use of more general group actions, with the hope that quantum algorithms are not helpful in this less structured setting. Group action-based constructions were first presented in the context of isogenies in which an ideal class group acts on elliptic curves, but equivalence problems in error-correcting codes and lattices also exhibit such structures. Previous works presented anonymity-preserving constructions in a generic group action framework; however, they were not general enough to encompass the group action underlying the Lattice Isomorphism Problem (LIP), for which the acting group is countably infinite and non-commutative. We bridge this gap by, from zero-knowledge proofs of OR statements, building generic blind signatures and strong designated-verifier signatures with non-delegability from standard assumptions corresponding to a generalised group action inverse problem.

In this work, we construct a new and highly efficient blind polynomial commitment scheme (PCS) over non-binary fields. Our scheme is specifically designed to handle encrypted coefficients without requiring expensive bootstrapping operations, achieving a breakthrough in the "complexity-depth" trade-off. The proposed scheme features an extremely efficient prover both asymptotically and concretely. The commitment and evaluation phases are dominated by a strictly linear $O(n)$ number of field operations. Furthermore, the construction maintains a constant multiplicative depth, which is a critical requirement for efficiency in homomorphic encryption settings. Concretely, for large-scale circuit sizes, our prover is significantly faster than prior state-of-the-art schemes such as phalanx and laminate. Our underlying technique is the Generalized RAA code, an extremely efficient error-correcting code that extends the binary RAA code structure to arbitrary non-binary prime fields $\mathbb{F}_{p}$. We analyze the bounds over non-binary fields, which demonstrate that this code maintains a linear minimum distance property with high probability. By combining Ligero’s IOPP framework, we obtain the first asymptotically and concretely good blind PCS that achieves strictly linear $O(n)$ encoding complexity for the prover while avoiding the expensive bootstrapping operations.

In the information-theoretic model, parties communicate over sender-authenticated point-to-point channels, but use no digital signatures or other transferable cryptographic certificates; the adversary is otherwise computationally unbounded. We present \name, an information-theoretic Byzantine agreement protocol for partial synchrony with a good-case latency of two rounds that achieves the optimal resilience bound of $n = 5f - 1$ in this setting. When the actual network delay after GST is at most $\delta \le \Delta$, our protocol achieves a \emph{robust} good-case latency of $2\delta$. The protocol proceeds in views and guarantees a worst-case view latency of at most $2\Delta + 2\delta$. Moreover, each party requires only $O(1)$ words of persistent storage, and each view incurs $O(n^2)$ messages of $O(1)$ words each.

We give, to our knowledge, the first plain-model, one-time information-theoretically secure, efficient unclonable encryption scheme for one classical bit. Previous work by Bhattacharyya and Culf (Nature Physics, 2026) and Bhattacharyya, Broadbent, and Culf (arXiv:2603.08916) either only showed $1/\mathsf{poly}(\lambda)$ security loss or required inefficient encryption/decryption operations. We avoid both of these caveats; in doing so, we obtain (to our knowledge) the first plain-model construction of many-time secure $1 \to 2$ unclonable encryption for arbitrary polynomial-length messages, assuming the existence of pseudorandom function-like states (Bartusek and Goldin, arXiv:2605.27647). The key is a uniformly random non-identity phase-free Pauli on $n$ qubits, and bit $a$ is encrypted as a random $(-1)^a$ eigenstate of that Pauli. Encryption and decryption use $O(n)$ single-qubit operations and $O(n)$ time classical computation; key generation uses only $O(n)$ time classical computation. The scheme is exponentially secure; we prove that the probability that both receivers recover the bit is at most $\frac{1}{2}+\frac{1}{2}\sqrt{{2^n}/({4^n-1})} = \frac{1}{2} + O\left(2^{-n/2}\right).$ By a lower bound due to Broadbent, Culf, and Rochette, this is the best probability bound achievable with $n$-qubit ciphertexts (up to the constant hidden in the $O(\cdot)$). The main conceptual idea is to leverage, in a precise spectral sense, the balanced commutation-anticommutation structure of the Pauli group. The proof is intricate but completely elementary and makes use of standard spectral bound techniques. The main technical workhorse is a standalone linear-algebraic lemma which we present in its own section: informally, it relates the positivity of two different operators, each capturing the intuition that if the two receivers can individually decrypt unusually often then they must also disagree often. GPT-5.6 Sol Ultra found this proof in an extended conversation with the author and drafted a preliminary version of this paper. The author is fully accountable for the correctness of this paper.

We observe that there exists a single-server quantum private information retrieval with polylogarithmic communication assuming post-quantum one-way functions. Our observation follows immediately from the compilation technique of [Kerenidis-Wolf STOC'03] when combined with distributed point functions by [Gilboa-Ishai EUROCRYPT'14].

A $t$-out-of-$n$ threshold decryption scheme distributes decryption key shares among $n$ parties so that any $t$ of them can jointly decrypt a ciphertext, while fewer than $t$ learn nothing about the plaintext. Traditional threshold schemes provide no accountability: a coalition of $t$ or more parties can combine their key shares and construct a pirate decoder that decrypts arbitrary well-formed ciphertexts, without any risk of being traced. To address this, Boneh, Partap, and Rotem [CRYPTO '24] introduced the notion of threshold traitor tracing (TTT), where a tracing algorithm that is given black-box access to the pirate decoder can identify at least one of the colluding parties. Many subsequent threshold traitor tracing schemes similarly find only a single traitor, even though the decoder must have been constructed using at least $t$ keys. While some constructions can find multiple traitors, they do so at the cost of large ciphertexts or only achieving a weak form of correctness. In this work, we make the following contributions: - Lower bounds: We show that for all existing traitor tracing techniques, the ciphertext must be large to allow tracing close to $t$ traitors. In particular, to trace $t-O(1)$ traitors, the ciphertext size must be at least $\Omega(t)$. To trace $a \leq t- \omega(1)$ traitors, the ciphertext size must scale with $\Omega(\frac{a-1}{t-a+1})$. For schemes that rely on fingerprinting codes, we show an even stronger lower bound. - Upper bounds: We present two generic compilers that construct traitor tracing for general access structures (beyond threshold) from two building blocks: attribute based encryption for general access structures and sufficiently-expressive policies and mixed functional-encryption. We also present two concrete instantiations. Under exponential security assumptions, we construct a pairings-based threshold traitor tracing scheme that can trace $t$ traitors with ciphertext size $O(t^2)$. We also construct an LWE-based traitor tracing scheme for a DNF access structure, that can trace an authorized subset of traitors with ciphertext size $O(\hat{t}^2)$, where $\hat{t}$ denotes the size of the largest unauthorized subset in the access structure. - A Candidate Theoretical Instantiation: We present a new tracing mechanism that can trace $t(1-1/\lambda^c)$ traitors with $\mathsf{poly}(\lambda)$ size ciphertext, public key, and secret keys. We prove security assuming ideal (black box) obfuscation. Our work raises several open questions in the context of tracing multiple parties in a threshold traitor tracing scheme.

Signature schemes based on the MPC-in-the-Head (MPCitH) paradigm play an important role in enabling cryptosystems founded on a wide diversity of hardness assumptions. While the design of such schemes is currently stabilizing, providing efficient implementations on embedded devices remains a critical challenge, as MPCitH frameworks are known to manipulate large data structures and to rely heavily on symmetric primitives. In this work, we present a highly optimized implementation of the NIST candidate MQOM (version 2) targeting embedded microcontrollers. Our implementation significantly outperforms existing MPCitH implementations on such platforms, both in terms of memory footprint and execution time. In particular, for the L1 parameter set, we can achieve an SRAM usage below 10 KB, including the key and signature buffers, while preserving practical signing and verification performance (on the order of a few hundred megacycles). We further explore time-memory trade-offs, achieving execution times below 100 Mc for certain variants at the cost of an additional 5-10 KB of memory. We also provide the first memory-friendly implementation of the one-tree technique, which is used to reduce signature sizes in several MPCitH-based schemes. This enables a comparative analysis of the implementation costs of correlated trees (used in MQOM) versus the one-tree technique (used in other candidates). We then demonstrate how streaming and precomputation techniques can further mitigate the impact of the running time and the signature size. For instance, these approaches enable overlapping computation with data reception, for example by starting computations before all inputs are available, thereby reducing overall latency.

The computation of optimal Ate pairings on elliptic curves with embedding degree $k=27$ (BLS27) is highly relevant for achieving the 256-bit security level, especially in the context of recent advances in the Number Field Sieve (NFS) and its variants (exTNFS, SexTNFS). Traditional binary approaches fail to fully exploit the degree-3 extension tower of $\Fpk{27}$. In this work, we propose an efficient ternary version of the Miller loop, restricting the seed representation to sparse ternary digits $\{0, 1\}$ to streamline point operations and eliminate costly inversions. Furthermore, we generate two new parameter seeds tailored for exTNFS and SexTNFS security levels. These seeds feature sparse ternary representations that simultaneously guarantee the efficiency of the Miller loop and allow the full exploitation of cyclotomic cubing in $\mathbb{F}_{p^{27}}$ during the hard part of the final exponentiation. Compared to the state of the art binary approach by Fouotsa et al. (2020), our exTNFS seed yields a $22\%$ improvement in the overall optimal Ate pairing computation cost. Concurrently, our proposed SexTNFS seed ensures a higher level of security against the most advanced NFS variants.

Despite decades of research in electromagnetic (EM) side-channel analysis (SCA), practical attacks still require manual effort and domain expertise to identify informative probe locations on target devices. Existing approaches rely heavily on exhaustive grid scanning or handcrafted alignment, limiting attack scalability and realism. In this work, we present the first automated and adaptive EM SCA framework that uses particle swarm optimization (PSO) to navigate the probe. Particles are guided by mutual information (MI) leakage maps, enabling efficient recovery of secret-dependent emissions. We introduce a novel application of the Nyström approximation to accelerate MI estimation across EM trace windows, allowing real-time swarm guidance without full kernel computations. Unlike prior work, our method requires no leakage templates, manual tuning, or alignment assistance, enabling automated attacks with minimal assumptions. We validate our framework on both microcontroller and FPGA platforms running AES-128. PSO-guided scanning identifies high-leakage points faster than grid search and reduces the number of traces required for successful CPA-based key recovery by up to a factor of 16, i.e., saving tens of thousands of traces.

The impossible boomerang (IB) attack is one of the most powerful cryptanalytic techniques for block ciphers, with notable successes against AES. However, constructing IB distinguishers—the core component of IB attack—remains a fundamental challenge: existing methods are restricted to specific cipher structures, cannot detect contradictions spanning more than two rounds, and lack a unified framework across attack settings. To solve these issues, this paper introduces three hierarchically complementary methods for constructing IB distinguishers: (1) a GEBCT-based method breaking the 2-round contradiction barrier; (2) a state-based method proven exactly equivalent to the definition of IB distinguishers (the most precise available); and (3) a structural method for fast security evaluation. We prove their inclusion relations, unify all prior methods, and connect the state-based method to the Quasidifferential Framework within IB distinguishers. Furthermore, we develop a unified SAT/SMT-based framework that automatically searches distinguishers under single-key, two-related-key, and four-related-key settings. We evaluate on seven representative block ciphers covering almost major design paradigms: We present the first IB distinguishers for ARX cipher SPECK (ISO/IEC standard) and CHAM, bit-permutation cipher GIFT-64 (CHES'17, an example with 5-round contradictions), and key-dependent Sbox cipher PRINTcipher48 (CHES'20). We obtain the first 5-round related-key IB distinguishers for AES-128 (NIST's standard with nonlinear key schedule, first automatically searched), and 1-round improvements over prior IB distinguishers for tweakable cipher SKINNY-64/192 (CRYPTO'16) and SKINNYee (CRYPTO'22). All IB distinguishers outperform the best impossible differentials by 1--4 rounds, including a PRINTcipher48 result that disproves the long-standing claim about single-key IB distinguisher limitations. Finally, we present a 31-round related-key IB attack on SKINNYee, the best result to date.

Maintaining a decentralized system requires a collective governance mechanism that allows participants to agree on changes to the system. In particular, the governance mechanism should offer a voting functionality for casting, collecting, and tallying votes in a confidential yet verifiable manner. Scaling this functionality for millions of participants in a cost-effective manner is a critical requirement for permissionless blockchains that remains unmet. We put forward a "layer-2" approach to meet this requirement in a setting where a permissionless blockchain acts as the fallback "layer-1" mechanism. Specifically, our approach to scalability realizes the protocol in a layer-2 fashion: the bulk of the protocol is executed off-chain, but secured on the blockchain with a minimal footprint. We prove our protocol secure in the Universal Composability (UC) framework. First, we formalize a governance ideal functionality $\mathcal{F}_{\mathsf{L2Gov}}$. Our definition offers high levels of confidentiality and verifiability. Moreover, in the case of misbehavior, it allows faults to be attributed so that appropriate action (such as the slashing of on-chain funds) can be taken. Second, we demonstrate that our protocol UC-realizes the $\mathcal{F}_{\mathsf{L2Gov}}$ functionality based on a blockchain, an off-chain bulletin board, a distributed homomorphic encryption functionality ($\mathcal{F}_{\mathsf{DHE}}$), and other standard hybrids. To the best of our knowledge, this work presents the first layer-2 blockchain voting protocol with a rigorous security analysis. We also point out some challenges that arise when applying the UC framework to layer-2 protocols.

We present, Quintus, information-theoretic BFT protocols for tolerating $f < n/5$ Byzantine faults among $n$ parties. We present two protocols: (1) The first protocol, Quintus-Fixed, is in a fixed view regime where views advance at a cadence $3\Delta$ time. This protocol incurs a good-case latency of $2\delta$ time where $\delta$ indicates actual network delay and message complexity of $O(n^3)$ in a view. % In optimistic cases with good leaders, it incurs $O(n^2)$ message complexity. (2) The second protocol, Quintus-Responsive, is an optimistically responsive protocol with good-case latency of $2\delta$ time, $O(n^2)$ message complexity, and $2\Delta + 2\delta$ worst-case view latency where $\Delta$ denotes a pessimistic network delay parameter under synchrony.

The Generalized Feistel Network (GFN) underpins widely standardized block ciphers, yet its resistance to full plaintext recovery remains largely unexplored. This paper extends the full-plaintext attack framework for standard Feistel ciphers to multi-branch scenarios, mainly makes the following $3$ research contributions: (1) Developed classic full plaintext recovery attacks on $d$-round Type-I GFN ($d\ge 3$) under CPA with $d+1$ encryption queries and $2d$-round Type-I GFN under CCA with $d$ decryption queries. Query complexity depends on d, increasing branches can enhance anti-interference capability. (2) Developed classic full plaintext recovery attack on 2-round Type-II GFN ($d\ge 4$) under CPA with $3$ encryption queries and 3-round Type-II GFN under CCA with $1$ encryption plus $2$ decryption queries. Query complexity is independent of $d$, increasing branches does not improve resistance. (3) Finded that all attacks treat round functions as black boxes, confirming that the weakness resides in the GFN topology rather than specific round-function designs. Strengthening S-boxes or diffusion matrices cannot mitigate it, only increasing rounds beyond the security threshold provides effective defense.

This short note discusses in detail a folklore but little-known hybrid hash function grounded on both the discrete logarithm and short integer solution problems. In particular, specific satisfactory parameters are provided to ensure the standard $128$-bit security level for the lattice problem with $256$-bit module, which may be useful in its own right. The hash function is a natural generalization of the classical Pedersen and Ajtai ones. Nevertheless, to the authors' knowledge, no one has previously explicitly analysed their hybrid version. Besides, the obtained result is probably prone to significant further optimizations by applying many tricks from elliptic curve and lattice cryptographies. Hashing is known to be a basic operation for constructing more complex and important cryptographic schemes. The authors intend to explore such hybrid ones in future articles. However, the hash function under consideration may be precious by itself due to its double provable security. Thus, this introductory work represents a kind of reincarnation of curve-based cryptography whose development has been severely and unfairly undermined by the potential but still vague quantum threat.

GRAFHEN is a group-based homomorphic-encryption proposal whose public key is a rewriting system and whose secret key is a permutation representation. We present Maverick, an equivalent-key recovery attack. Maverick breaks every released GRAFHEN challenge, including the recommended two-copy $S_{11}$ instance: it reconstructs an equivalent key from public rules and correctly decrypts all $20{,}000$ supplied labelled ciphertexts. On $12$ independently generated recommended-parameter keys, the median end-to-end time is $552$ s and the median peak memory use is $11.28$ GB on an Apple M3 Pro. The attack converts selected public rewrite rules into group relators, reconstructs a regular action by Todd-Coxeter enumeration, recognizes the resulting permutation representations, and aligns the two sides through the public mixed relations. Public labelled encryptions then calibrate an equivalent decryptor. We prove a proof-carrying version of this procedure: a target-order table with a replayable trace certifies the recovered regular action. The reported $S_{11}$ experiments use target-order closure checks, complete-corpus verification, and decryptor validation. We also give an output-sensitive analysis and state the hypotheses needed to extrapolate beyond the measured instances. Following an independent key-recovery attack, GRAFHEN proposed in July 2026 to replace $S_{11}$ by $\mathrm{PSL}_2(343)$. We adapt Maverick to this setting and demonstrate complete public-rule recovery, alignment, certification, and calibration on generated $\mathrm{PSL}_2(169)$ instances. The two-side $q=169$ run decrypts all $5{,}000$ held-out ciphertexts in a $103$~s critical path using $0.93$ GiB peak memory; a $k=2$ admissibility-filtered corpus also succeeds. Under GRAFHEN's stated worst-case estimate for Dumezy's degree-based search, this degree $170$, $d=5$ setting already has cost $O(2^{850})$, well beyond the intended reach of that attack. At the target group, the post-enumeration recovery path from a generated regular action takes $35.0$ s and $1.92$ GiB peak memory. These results suggest that the proposed platform-group change is insufficient to rule out Maverick; recovery from an admissibility-filtered corpus at $q=343$ remains to be measured because the pre-filter KeyGen enumeration exceeded $32$ GiB of memory before it could produce a corpus.

We propose a framework for cryptanalysis of lattice-based schemes, when side information---in the form of ``hints''--- about the secret and/or error is available. Our framework generalizes the so-called primal lattice reduction attack, and allows the progressive integration of hints before running a final lattice reduction step. Our techniques for integrating hints include sparsifying the lattice, projecting onto and intersecting with hyperplanes, and/or altering the distribution of the secret vector. Our main contribution is to propose a toolbox and a methodology to integrate such hints into lattice reduction attacks and to predict the performance of those lattice attacks with side information. While initially designed for side-channel information, our framework can also be used in other cases: exploiting decryption failures, or simply exploiting constraints imposed by certain schemes (LAC, Round5, NTRU). We implement a Sage 9.0 toolkit to actually mount such attacks with hints when computationally feasible, and to predict their performances on larger instances. We provide several end-to-end application examples, such as an improvement of a single trace attack on Frodo by Bos et al (SAC 2018). In particular, our work can estimates security loss even given very little side information, leading to a smooth measurement/computation trade-off for side-channel attacks.

This work presents ConvertInput-Free Vector Homomorphic Secret Sharing (Vector-HSS), a novel HSS primitive based on the Decisional Composite Residuosity (DCR) assumption. Our construction enables efficient high-dimensional vector computations while avoiding the costly $\texttt{ConvertInput}$ operation. As a unified framework, Vector-HSS can be used as a building block for Private Information Retrieval (PIR), Secure Multi-Party Computation (MPC), Privacy-Preserving Machine Learning (PPML), etc. The key idea behind Vector-HSS is to introduce a vector-centric computation paradigm. Unlike traditional approaches, this design allows the server to perform natural and efficient vector computations without the $\texttt{ConvertInput}$ operation while keeping client-side overhead comparable to that of state-of-the-art solutions. To further improve efficiency, we develop a batching mechanism based on the Chinese Remainder Theorem (CRT) that enables parallel computation across multiple vectors. Building on these techniques, we further design a suite of protocol modules to securely support Euclidean/cosine distance computation, comparison, and matrix-vector multiplication in practical applications. Experiments show that our scheme achieves $280\times$ and $70\times$ speedups over prior HSS schemes (EUROCRYPT 2021 and S&P 2026, respectively) for batched inner product evaluation. When applied to privacy-preserving image retrieval, our method achieves sub-second retrieval time, outperforming state-of-the-art solutions under similar security requirements.

We propose a complementary stopping strategy based on complex multiplication (CM) for the subfield-search stage of supersingular isogeny path-finding, a bottleneck in the Delfs-Galbraith/SuperSolver algorithm. The original search performs a non-backtracking walk in the supersingular \(2\)-isogeny graph until it reaches the subfield terminal set \(S_p\). Our idea is to enlarge the set of recognizable terminals, by adding a precomputed set of CM supersingular vertices. For a discriminant bound \(M\), we construct \(S_{\mathrm{CM}}(M)\) from roots of Hilbert class polynomials \(H_D(X)\) over \(\mathbb F_{p^2}\), where \(D\) ranges over inert negative fundamental discriminants with \(|D|<M\). The walk then stops upon reaching \(S_p\cup S_{\mathrm{CM}}(M)\). The only additional per-visit cost is an expected \(O(1)\) hash-table membership query in the precomputed CM terminal table. We estimate the size and preprocessing cost of \(S_{\mathrm{CM}}(M)\), obtaining the heuristic growth \(|S_{\mathrm{CM}}(M)|=\Theta(M^{3/2})\), and show that the overlap \(S_{\mathrm{CM}}(M)\cap S_p\) is lower order. We also give terminal-connection procedures showing how searches that stop at CM vertices can be converted into full isogeny paths under the standard quaternionic and KLPT heuristics. The method does not change the asymptotic exponent of the underlying Delfs-Galbraith search; instead, it provides a complementary technique for existing subfield-search methods by adding efficiently recognizable CM terminals. Experiments on small parameters show that enlarging the terminal union reduces both visited vertices and field multiplications, while lookup benchmarks at SQIsign parameters confirm that the additional table membership test has stable and moderate per-visit overhead.

(Receiver) anamorphic encryption introduced by Persiano et al. (Eurocrypt'22) enables covert communication through innocent-looking ciphertexts, even under strong censorship where a dictator has the power to compel citizens to surrender their private decryption keys. In this work, we study the asymmetric form of anamorphic encryption proposed by Catalano et al. (Eurocrypt'24), where the covert channel operates in a manner analogous to PKE. However, the commonly considered notion, fully asymmetric anamorphic encryption, fails to address collusion, where the dictator can corrupt a sender to additionally obtain the sender double key for encrypting covert messages. In addition, we work with the notion of anamorphic extension proposed by Banfi et al. (Eurocrypt'24), where covert communication can be enabled directly from (already deployed) public keys. Via deniability, this formulation provides stronger security guarantees that are not captured by existing models for the collusion setting. Motivated by these observations, we develop the first general framework for collusion-resistant asymmetric anamorphic extensions. At the heart of our approach is a new cryptographic abstraction, witness PRF for PKE, which can be used to realize secure covert channels under our framework. This reduces the construction of asymmetric anamorphic encryption schemes to the realization of a single primitive, thereby providing a unified and conceptually clean methodology. Theoretically, we further show that any asymmetric anamorphic extension for a PKE scheme gives rise to a witness PRF for this PKE, indicating that our cryptographic abstraction is precise and well suited to the task. Building on this framework, we obtain a generic construction of asymmetric anamorphic encryption for any PKE scheme with high min-entropy ciphertexts. In contrast to prior generic approaches proposed by Catalano et al. (Eurocrypt'25) which rely on indistinguishability obfuscation, our construction achieves stronger security in the collusion setting under assumptions believed to be weaker, thereby improving both theoretical foundations and feasibility. Beyond generic viability, we give direct and practical instantiations of our framework for widely deployed schemes, including ElGamal, Regev, and Paillier, without relying on heavy cryptographic mechanisms. These results demonstrate that collusion-resistant asymmetric anamorphism is not only achievable in general, but also practical in standard encryption systems.

We show that under a plausible number-theoretic conjecture, for any constant $s$ there exists an $s$-server private information retrieval (PIR) protocol that on an $n$-bit database requires communication $\exp(O((\log n)^{1/s} (\log \log n)^{1-1/s}))$. Previous constructions attaining the same communication required $2^{O(s)}$ servers. Our number-theoretic conjecture is implied by existing conjectures, namely the generalized repunit conjecture and Schinzel's hypothesis H (either one of these conjectures would suffice alone). Our result builds on the ``matching vector family + $S$-decoding polynomials'' framework pioneered by Efremenko (STOC 2009) and recently refined by Ghasemi, Kopparty, and Sudan (STOC 2025). The main ingredient is a framework for constructing $S$-decoding polynomials with only $k+1$ nonzero coefficients modulo special products of $k$ primes, resolving an open problem posed by Ghasemi and Kopparty (ITCS 2026). By the lower bound shown by Ghasemi and Kopparty, this is the minimum achievable sparsity. We also empirically validate our construction and make our result unconditional for all $s \leq 15$. We also apply our techniques to regimes where $s$ grows with $n$, showing under a stronger variant of our number-theoretic conjecture that the communication complexity of $s$-server matching-vector PIR can be superpolynomially reduced from the previous state of the art for any $s \leq \exp(o(\sqrt{\log \log n/\log \log \log n}))$. The main result for $s = O(1)$ and its proof were discovered in a GPT-5.5 Pro conversation prompted by the authors.

Vector commitment (VC) schemes enable a prover to commit to a vector and later open any position with a short proof. However, existing VC schemes are designed for centralized settings, and cannot work in decentralized systems, where the input vector is distributed across multiple machines. Similarly, traditional VC schemes cannot leverage distributed parallel computation across multiple machines for acceleration. To tackle this issue, we introduce a new notion—distributed VC (DVC), which allows multiple machines, each holding only a subvector of the input vector, to collectively commit to the entire vector and generate position proofs in a distributed manner. To the best of our knowledge, there is no prior work on DVCs and no existing work can trivially derive an efficient DVC scheme. The key challenge is that both commitments and proofs depend on the entire vector, while no single machine holds the complete vector in distributed settings. We propose the first DVC scheme, HLE-DVC, which leverages $M$ machines to process the distributed vector $\mathbf{v}$ of length $N$ in parallel, with each machine holding a subvector of length $\frac{N}{M}$. HLE-DVC achieves compact proof size-$\text{O}(\log M)$ and allows each machine to generate all its position proofs in a single communication round, with communication cost $\text{O}(\log M)$ and computation cost $\text{O}(\frac{N \log N}{M})$. Moreover, HLE-DVC supports batch proving, proof aggregation, and efficient updates. We conduct the experiments and open-source the code. Using 256 machines to generate all proofs for a committed vector of length $2^{30}$ takes 17,515 seconds. This achieves a $256\times$ parallel speedup over HLE-DVC on a single machine, and is $142\times$ faster than Hyperproofs (a famous single machine VC scheme). The communication cost per machine is 0.768 KB.

The Signal Protocol’s Double Ratchet and X3DH/PQXDH handshakes give in-transit messages forward secrecy and post-compromise security: compromising a session key does not expose past traffic, and the protocol self-heals after a fresh Diffie–Hellman step. Encrypted backups, by contrast, are commonly protected by a single static secret, a “Backup Recovery Key” generated once and held constant until manually rotated. We show, with an explicit attack, that this baseline design provably fails even a minimal forward-secrecy-style security notion: disclosure of the key at any time exposes the entire backup history, with no self-healing. This is not a hypothetical concern: a June 26, 2026 joint FBI/CISA advisory attributes exactly this exploitation pattern to two Russian intelligence-linked clusters, tracked as UNC5792 and UNC4221, who obtained victims’ Backup Recovery Keys through impersonation-based social engineering rather than cryptanalysis. We propose STEBR (Secure Timed-Erasure Backup Ratchet), a backup-key architecture built from three composable layers: (1) a self-erasing hashchain key ratchet so that compromise of the current backup key exposes only a bounded, recent window of history rather than the full archive; (2) (t, n) threshold secret sharing of the current epoch key across independently held devices/guardians so that no single credential extracted in one social engineering interaction is sufficient; and (3) an interactive, rate-limited, out-of-band confirmation gate on any restore request so that possession of valid recovery material is necessary but not sufficient to complete a restore. We give formal security definitions for each property and prove them via standard reductions (PRF security of the key-derivation function, IND-CPA security of the backup AEAD scheme, the information-theoretic secrecy of Shamir sharing, and the authenticity of the existing ratchet-protected control channel). All three layers are composed on top of existing Signal Protocol primitives; none require modifying the Double Ratchet, X3DH/PQXDH, or the wire format of message envelopes. This is a proposal for hardening the backup-key management layer specifically; we make no claim that the Signal Protocol’s transport-layer cryptography is broken or requires replacement the cited advisory itself states plainly that it is not.

Almost fifty years after its introduction, the McEliece cryptosystem occupies an unusual place in the post-quantum landscape. Its public keys are far larger than those of most competing schemes, its original parameters no longer provide adequate security, and several compact variants proposed to reduce key size have subsequently been broken. Nevertheless, the binary Goppa-code foundation retained in Classic McEliece continues to resist known practical attacks for the selected Classic McEliece parameter sets. This survey asks why McEliece has remained relevant despite these limitations. We trace its development from the original 1978 encryption scheme to the modern Classic McEliece key-encapsulation mechanism and organize nearly five decades of cryptanalysis into generic decoding, structural recovery, attacks on compact variants, protocol-level attacks, implementation leakage, and quantum speedups. We emphasize several distinctions that are often blurred in discussions of the scheme: breaking an obsolete parameter set is not the same as recovering the hidden Goppa structure; distinguishing a public code does not necessarily lead to practical key recovery; and compromising a modified or structured variant does not automatically compromise Classic McEliece. This history does not support either of two simple narratives: that McEliece has remained unchanged or that it has simply been broken. Its longevity reflects a conservative mathematical foundation that has survived repeated reassessment, together with parameters, security models, and implementations that have evolved in response to new attacks. We close by outlining the main questions that will shape its future: whether public-key and key-distribution costs can be reduced without exposing exploitable structure, how far modern algebraic cryptanalysis can be extended, how classical and quantum security estimates should be refined, and how secure implementations can be integrated into practical systems.

We give an unconditional construction of information-theoretically secure one-time private-key unclonable encryption scheme for one-bit messages, with efficient encryption and decryption and exponentially small unclonable-indistinguishability advantage.

A central challenge in quantum algorithm analysis and cryptography is reasoning about algorithms with oracle access to a random group element (e.g. a random function, a random permutation, a random unitary). Can we efficiently simulate such algorithms? Can we determine what they know after $t$ queries? Classically, an important tool for this is lazy sampling, where the oracle does not commit to the full group element at the beginning, but rather samples partial information about it on the fly. We study a quantum analog of lazy sampling: compressed oracles (or recording oracles), which are quantum data structures that allow such on-the-fly simulation for quantum queries. Compressed oracles were originally introduced by Zhandry (CRYPTO '19) for random functions, were generalized to random unitaries by Ma-Huang (STOC '25) and to permutations by Carolan (STOC '26), and have been employed to great effect in security proofs and query complexity lower bounds due to their interpretability. In this work, we define and analyze a general-purpose and interpretable path-recording oracle, derived from first principles, that perfectly simulates random elements of any closed subgroup of $U(N)$. Our path-recording oracle stores superpositions of $t$ input-output pairs $|(x_1, y_1), \dots, (x_t, y_t)\rangle$, which encode a Feynman path explored by the algorithm and thus transparently records the information that the algorithm may have learned from its queries. Our compressed oracle builds on a recent work of Grinko and Yoshida (QIP '26), who proposed a different kind of general-purpose compressed oracle without clear interpretability. Crucially for applications, we derive an operationally useful mathematical description of our update procedure in terms of the commutant of the group's tensor power representation. One powerful feature of our path-recording oracle is that it enables direct comparisons between compressed oracles for different groups, which gives a new technique for proving pseudorandomness results. For our main application, we formally relate the $S_N$ and $U(N)$ compressed oracles, yielding what is arguably the simplest construction to date of pseudorandom unitaries: the product $PC$ of a pseudorandom permutation and a random Clifford. This improves on the prior $PFC$ construction of (Metger-Poremba-Sinha-Yuen, FOCS '24; Ma-Huang, STOC '25).

Fully Homomorphic Encryption (FHE) enables arbitrary computation directly on encrypted data. The TFHE scheme supports encryption of bits or small integers, evaluating any univariate function via programmable bootstrapping (PBS), which also refreshes ciphertext noise. Since both linear and nonlinear functions can be expressed with PBS, arbitrary circuits of unlimited depth can be computed without accuracy loss, aside from a negligible failure probability. However, a key limitation of TFHE is that it processes only single encrypted messages of small size; for larger messages, PBS becomes prohibitively expensive, as its cost grows rapidly with message bit-length. To address this, Without-Padding PBS (WoPBS) allows evaluation of larger lookup tables, and is practical up to 28 bits, offering significantly reduced latency compared to pure PBS. Recent advances in the WoPBS workflow have further optimized Circuit Bootstrapping (CBS) operations, narrowing the latency gap to PBS. Still, minimizing the underlying number of PBS operations remains crucial, as PBS dominates the cost. In this work, we introduce novel switching algorithms to efficiently convert ciphertexts between the PBS and WoPBS contexts, carefully managing noise growth while minimizing PBS invocations. This includes a modified batched Circuit Bootstrapping that converts an entire digit with a single Blind Rotation using our novel balanced and monomial selector bases, and a novel batched AES evaluation that halves the per-round Blind Rotations. We further integrate a state-of-the-art noise reduction method into the WoPBS workflow by adopting the centered mean noise reduction for both the PBSmanyLUT and the multi-bit Blind Rotation modulus switching, enabling more efficient parameter sets. All of our parameter sets meet the $\texttt{IND-CPA}^D$ failure budget of $2^{-128}$; under it, our workflows evaluate large lookup tables up to $1.9\times$ faster and AES-128 transciphering up to $1.6\times$ faster than the state of the art on the same machine, with our batched AES evaluation running $1.15\times$ faster than our binary workflow. Our CUDA implementation further evaluates one AES-128 block in 331\,ms on a single RTX 4090, $43\times$ faster than our single-threaded binary CPU workflow and $1.18\times$ faster than the recent Maverick GPU accelerator, whose parameters admit a failure probability of only about $2^{-40}$.

Recent advances in quantum hardware, including Google's Willow processor, have substantially narrowed the timeline to cryptographically relevant quantum computers. In the blockchain setting, where addresses and key derivation standards such as BIP32, BIP44, and SLIP-10 are the dominant infrastructure for wallet management, a quantum computer running Shor's algorithm can recover any elliptic-curve private key from the corresponding public key, threatening every wallet in production today. Migrating to post-quantum signature schemes requires changing the public key format and forcing address migration across all participating networks, a significant problem for blockchain communities. We present an orthogonal approach: keep the existing address format entirely unchanged and instead replace the classical signing step with a NIZK proof of knowledge of the seed underlying the existing address, where security against quantum adversaries reduces to the conjectured quantum hardness of the underlying hash functions and the soundness of the NIZK against quantum adversaries, requiring no address migration or key registration. We build on the observation of Baldimtsi et al. that EdDSA's deterministic seed-to-key mapping makes the seed a valid zero-knowledge witness for the public key, and extend their single-level result to the full hierarchical deterministic wallet setting. Starting from BIP32-Ed25519, we replace the classical signing step with a NIZK proof certifying knowledge of the root seed and the full derivation chain, and prove EUF-CMA security for the resulting scheme; post-quantum security is conjectured to hold since all underlying primitives depend only on the hardness of hash functions and the soundness of the NIZK against quantum adversaries. The existing schemes each derive their quantum-safe witness as an incidental artifact of a curve-specific key format, and none provides a single derivation standard that works uniformly across curves. We therefore introduce QBIP32, a new key derivation scheme based on a keyed function HASH768 (instantiated with KMAC256) that produces the signing scalar, an explicit quantum-safe witness, and the chain code in a single call. QBIP32 is defined for any elliptic curve group of prime order with a fixed generator, requiring no structural change to the derivation or proof system across curves: the same construction covers secp256k1, Ed25519, and any future curve used in blockchain infrastructure. This universality stands in contrast to the BIP32-Ed25519 approach, which relies on the Ed25519 extended key format and has no analogue for other curves. We then address the efficiency problem: a monolithic proof of the full derivation chain has cost growing linearly with derivation depth. Our main contribution is ZKPoSP (Zero-Knowledge Proof of Seed Provenance), a signature scheme conjectured secure against quantum adversaries that splits the proof into a derivation proof generated once per key pair and a signing proof generated once per message, reducing per-message proving cost to a constant independent of derivation depth. We further characterise exactly when the derivation proof itself can be shortened to cover only the last step of the derivation rather than the full chain from the root seed, and identify the existence of a private value that is bound to the seed by a one-way function and not recoverable from the public key as the precise criterion. This criterion is met by hardened keys but not by non-hardened keys, a structural distinction common to all schemes: BIP32 secp256k1, SLIP-10/Ed25519, BIP32-Ed25519, and QBIP32 all admit a last-step derivation proof for hardened keys, while non-hardened keys require a proof reaching back to the last hardened ancestor. We exploit this for BIP44 paths to prove only one hardened step plus the non-hardened suffix in a single proof, enabling secure deletion of the root seed. Before Q-day, separating the derivation and signing proofs already reduces per-transaction cost to a constant independent of derivation depth. After Q-day, once networks reject all non-post-quantum signatures, the leaf scalar can be moved to the public statement, removing all elliptic-curve scalar multiplications from the proof circuit and reducing derivation proving time substantially. We implement all constructions in Rust using RISC Zero as the NIZK backend, instantiate HASH768 with KMAC256, and report benchmarks for monolithic proofs, ZKPoSP across full BIP44 paths, and the post-Q-day variant. Signing proving time is constant at approximately 12-13 seconds and verification time is constant at approximately 9-10 ms across all variants and depths.

We observe that the existing norms within cryptography do not expect protocol analysts to document the sociotechnical properties that a deployed system should have. To help close this potential gap, we develop a framework that allows bringing sociotechnical dimensions into analyses of cryptographic systems, and in particular facilitates "in-context" analysis of proposed cryptographic deployments on top of widely-accepted cryptographic modeling techniques. To explore the utility of our framework, we use Apple's 2021 CSAM scanning proposal as a case study. We show how our framework naturally surfaces many of the criticisms of Apple's proposal and helps us identify a previously undocumented property of the proposal.

The Sumcheck protocol is a cornerstone of modern proof systems, yet its prover remains a performance bottleneck. Even in the multilinear case, the repeated construction of round polynomials leads to significant overhead, limiting scalability in practice. We take a different approach: instead of modifying the protocol, we rethink the representation of multilinear polynomials. We show that any multilinear polynomial admits a simple and structured binary-tree circuit representation, where each node follows a clean recursive rule. This perspective is not merely conceptual; it directly translates into faster algorithms. Our circuit view unifies three core operations: evaluation, summation over the Boolean hypercube, and Sumcheck round generation within a single framework. Construction from the coefficient vector costs exactly nN field operations, and evaluation via bottom-up folding requires exactly N − 1 multiplications — optimal for this class of algorithms. A key structural property of the circuit is its regularity: fixed depth, local recurrences, and no data-dependent branching. This is not incidental — it is a direct consequence of the recursive decomposition, and it is precisely what makes the representation amenable to parallel execution and hardware acceleration. We implement our approach in Rust on the BN254 scalar field and benchmark it against ark-poly with parallelism enabled on both sides. At n = 20, our parallel evaluation kernel achieves a 3.4× speedup over ark-poly (14 ms vs 48 ms). The verifier completes in under 1 μs across all tested dimensions, yielding a prover-to-verifier ratio exceeding 105 at n = 20. Our results suggest that revisiting polynomial representations is a promising direction for accelerating fundamental primitives in proof systems.

FAEST is a family of post-quantum signature schemes based on VOLE-in-the-Head, and is one of the nine candidates advanced to the third round of the NIST Additional Digital Signature process. FAEST relies only on symmetric cryptographic primitives, including block ciphers and hash functions, and does not require structured number-theoretic assumptions. We propose two families of signature schemes, SM4th and uBlockith, targeting 128-bit and 256-bit classical security, respectively. SM4th and uBlockith follow the FAEST framework but instantiate it with Chinese-designed block ciphers, including SM4, uBlock, and Ballet. We further design constraint systems tailored to these block ciphers and provide instruction-set-aware optimized implementations. Our evaluation on two Intel platforms and a Hygon platform shows that the end-to-end performance of the proposed schemes is strongly platform dependent. On an Intel platform with native SM4 support, the SM4th variants achieve performance comparable to the corresponding FAEST-128 variants, with a gap of less than $1\times$. On the Hygon platform with native CIS-SM4 support, the SM4th variants are within approximately $3\times$ of FAEST-128. The SM4th-EM-s (short) variant has a combined public-key and signature size of $3\,850$ bytes, compared with $3\,938$ bytes for FAEST-EM-128s. The uBlockith variants remain approximately $3$--$4\times$ slower than FAEST-256. These results demonstrate the feasibility and costs of instantiating VOLE-based signatures with the selected Chinese block ciphers.

Standard Tseitin encodings of the SHA-256 nonlinear functions Ch and Maj can hide conditioned differential projections from Boolean Constraint Propagation (BCP). We materialize them as short, semantically redundant CNF clauses. A cofactor theorem characterizes all controlled differential linear forms; its implemented unit-vector specialization returns exactly all minimum-control projections, yielding four Ch and twelve Maj clauses per bit. The clauses preserve models, introduce no variables, and strictly strengthen BCP on an explicit gate fragment. We claim neither propagation completeness nor a general affine compiler. We evaluate mechanism separately from performance and distinguish the production bundle from the proposed layer. Frozen studies show a fixed-formula bundle benefit, but the matched clause isolation fails its effect gate and an unrestricted control is inconclusive. We therefore show neither a solver-independent speedup nor a new cryptanalytic attack. The restricted weight-15 C15 census passes the CaDiCaL rule but not the Kissat rule. In the stratified C16 extension, the frozen decisions are too censored for CaDiCaL and too censored for Kissat; these solver-stratified labels are not pooled. A pinned three-solver replay validates larger-bundle execution but cannot attribute performance to the clauses. A variable-preserving probe exposes all 32 tested implications only after augmentation.

Sender untraceability hides the account spent by a cryptocurrency transfer among a set of candidates, its masking set. What a transfer does to that set separates two designs: classical schemes retain the whole set and append a nullifier marking the spent account, so the ledger grows with every transfer; constant-state schemes instead consume and replace the entire set. We ask how this choice affects synchronization. We formalize the two designs as the linear and constant untraceable asset transfer objects (LUAT and CUAT) and locate them in the consensus hierarchy. In LUAT, transfers from distinct accounts commute. Its consensus number is 2, compared with 1 for standard asset transfer, independently of the masking-set size and of the untraceability notion, and LUAT is starvation-free. Partitioning the accounts into fixed masking sets lets exhausted sets be garbage-collected without increasing that number. In CUAT, a transfer consumes and replaces every account of its masking set, so two transfers whose sets intersect cannot both take effect. We formalize this with the conflict graph on masking sets, whose edges join sets sharing an account. Under weak untraceability, which protects a transaction in isolation, the consensus number is unbounded already for one-round protocols. Under strong untraceability, which protects against an observer of the complete history, untraceability holds on a history exactly when any two accounts sharing a masking set occur in the same number of the masking sets in it. This uniform incidence bounds the conflict graph, and matching constructions attain it, so the consensus number is determined exactly and grows quadratically in the masking-set size. Finally, CUAT is not starvation-free. The two objects therefore pay for the same privacy differently: LUAT in storage, CUAT in synchronization and fairness.

Recent advances in fully homomorphic encryption (FHE) have enabled privacy-preserving machine learning directly over encrypted data. As a representative recurrent architecture, the long short-term memory (LSTM) network is widely used for modeling sequential dependencies, yet existing FHE-based LSTM inference schemes still suffer from high latency and limited scalability. In this paper, we present an efficient privacy-preserving LSTM inference protocol on encrypted sequential data based on FHE. We insert a lightweight normalization module before nonlinear activations to bound the hidden states, thereby enabling accurate low-degree polynomial approximations of the Sigmoid, Tanh, and inverse square-root functions via a hybrid Remez and least-squares strategy. We implement the proposed protocol using the Lattigo library, incorporating ciphertext packing optimization, rotation minimization, and SIMD-based parallelization. Experiments show that on standard text classification benchmarks, our encrypted LSTM achieves competitive accuracy compared with plaintext models and consistently outperforms the state-of-the-art FHE-based method, achieving up to a 4.7x speedup.

We present \(\mathsf{Pancake}\), a linear-time SNARK with a circuit-specific setup that eliminates the explicit representation and separate verification of addition gates in Plonkish constraint systems. Specifically, we consolidate wiring constraints and addition-gate constraints into a single family of general linear constraints, which can be enforced efficiently via a single sumcheck protocol. As a result, \(\mathsf{Pancake}\) achieves ``almost-free'' addition gates, which significantly reduces the witness size and directly improves prover efficiency while preserving full support for high-degree custom gates. Our implementation shows that \(\mathsf{Pancake}\) outperforms the state-of-the-art Plonkish SNARK \(\mathsf{HyperPlonk}\) (Chen et al., EUROCRYPT 2023) in terms of prover efficiency. For a circuit size of $2^{24}$ where half the gates are additions, \(\mathsf{Pancake}\) achieves prover speedups of $1.67\times$ (single-threaded) and $2.43\times$ (32-threaded), while also generating smaller proofs and maintaining comparable verification time.

Training machine learning models in untrusted clouds requires strong guarantees of confidentiality, integrity, and correctness, while remaining scalable and resilient to node churn. These challenges are further amplified in emerging agentic AI systems, where autonomous and distributed learning components require trustworthy coordination and secure state management across heterogeneous cloud environments. Existing Trusted Execution Environments (TEEs) lack scalability and remain vulnerable to side-channel attacks for large workloads, while pure secure multi-party computation (MPC) approaches incur prohibitive overhead in practice. SENTRA (Secure ENclave-based TRaining Architecture) addresses these challenges through a hybrid architecture that combines TEEs, secret sharing, and communication-efficient MPC with system level mechanisms that secure the entire training lifecycle. SENTRA introduces a scalable collective attestation protocol that verifies all participating enclaves and enforces hardware exclusivity before any node may store or process secret shares. Training data and model parameters are stored as secret shares in a versioned enclave-backed key–value store (KVS), providing rollback protection and consistent state under adversarial conditions. SENTRA further supports dynamic, fault tolerant membership through Dynamic Proactive Secret Sharing (DPSS)-based resharing, safe packed-MPC computation under degree bounds, and adaptive handling of node failures. Evaluation of a prototype implementation shows that SENTRA achieves up to 8.89 samples/s throughput and 1.29× faster training than the CrypTen baseline in software-only mode. In hardware-enclave mode, SENTRA incurs only an 8.3% performance overhead while providing memory-isolated confidentiality, fault-tolerant membership management, rollback protection, and recovery from node failures in approximately 8 seconds.

Free Hosting Platforms (FHPs) let users publish websites with minimal cost and configuration, but the same provider-managed infrastructure can also be used to host phishing websites. We study how this setting affects Certificate Transparency (CT)-based phishing detection by analyzing X.509, CT, and URL features across FHP phishing, FHP benign, non-FHP phishing, and popular benign websites. Reflecting the shared and wildcard certificate practices common in this setting, we analyze the certificate-level and domain-level data separately. Our measurement study shows that many apparent phishing indicators instead reflect hosting-provider characteristics: in our domain-level correlation analysis, hosting-platform status is more strongly associated with the extracted X.509, CT, and URL features than phishing status is, with the strongest FHP-associated feature (subdomain levels, $\eta=0.54$) exceeding the strongest phishing-associated feature (certificate validity period, $\eta=0.31$). We further evaluate two representative CT-based phishing detection frameworks on FHP-only data and discover that provider-managed infrastructure creates challenges for applying them directly. These findings show the need for future work on CT-based phishing detection methods that account for this deployment setting, especially as AI tools lower the effort required to create convincing phishing websites at scale.

Zero knowledge is formalized via a simulator — i.e., an efficient computation which simulates the view of a (malicious) verifier. The foundational results in constant-round zero knowledge [GMW86,FS90,GK96] all use expected polynomial-time (EPT) simulators, and there is evidence that strict poly-time simulators do not exist for these protocols [BL02]. In the post-quantum setting, we must upgrade the simulator to at least quantum polynomial time (QPT) in order to properly simulate quantum verifiers. Chia et al. [CCLY22] proved a surprising negative result which precludes non-trivial ZK for constant-round protocols with both (strict) QPT and a natural notion of expected quantum polynomial-time (EQPT) black-box simulation. In light of this, Lombardi, Spooner, and Ma [LMS22] introduced a novel EQPT notion, coherent-runtime EQPT or EQPT$_c$, and showed that the [GMW86,FS90,GK96] protocols all allow for EQPT$_c$ simulation. In this work, we identify a fundamental issue with the definition of EQPT$_c$ simulation, and propose a resolution. In particular, we demonstrate that EQPT$_c$ computation is not necessarily efficient and can, in fact, decide any classical decision problem. This is possible through a freedom of choice in selecting a unitary dilation for an efficient quantum channel. We propose an revised definition which carefully restricts this choice, and prove that the definition preserves the zero knowledge of the [GMW86,FS90,GK96] protocols. Additionally, by upgrading the [GK96] framework to the fully quantum setting, we demonstrate for the first time a constant-round (malicious verifier) zero knowledge proof system for QMA (with EQPT$_c$ simulation).

Password-based authentication remains widespread, and large-scale sets of leaked hashes enable practical offline brute-force attacks. Multi-target attacks, which check candidates against large sets of hashes simultaneously, are particularly effective. Understanding the capabilities of low-cost platforms for such attacks is important to assess real-world password security risks. Therefore, we present BF², a modular and scalable FPGA–CPU framework that accelerates multi-target password recovery. BF² combines a password-candidate generator, a fully-pipelined NT hash core, a Bloom filter stage to filter non-matching candidates, and a multi-threaded host-side component that performs exact membership check using a perfect hash function. We implement BF² on the low-cost, \$199 NiteFury II board. With 16 parallel pipelines running at a 100 MHz clock frequency, our FPGA implementation generates $1.6\times10^9$ hashes/s. In our experiments, BF² demonstrates up to $7.5\times$ higher throughput than John the Ripper, and reduces power consumption by as much as $90\%$ compared to Hashcat on an RTX 5000.

A basic property of lattice-based homomorphic encryption schemes is that ciphertexts carry an inherent noise that accumulates as computation advances. The key-switching procedure of these schemes allows the homomorphic re-encryption of a ciphertext under a new secret key, but it is a major source of noise growth. Several strategies have been proposed to reduce the amount of noise introduced by key-switching in the CKKS scheme. In this work, we generalize the RNS-based decomposition technique to an arbitrary number of input polynomials and secret keys. Performing multiple relinearizations and rotations in batch enables one to hoist the modulus lowering and decomposition steps of key-switching, respectively, which restricts noise growth and avoids redundant computation. We prove the security and correctness of all the proposed algorithms, and derive explicit noise bounds for them. Practical examples illustrate the impact of these optimizations on applications like private deep neural network inference. In addition, we provide—to the best of our knowledge—the first noise analysis of the double-hoisted BSGS matrix-vector multiplication algorithm of Bossuat et al. 2021, which is a building block of state-of-the-art CKKS bootstrapping circuits. Our analysis additionally reveals an optimization concerning the automorphism applications during its giant steps.

We propose a novel mechanism for garbling wires and gates of a logical circuit in a privacy-free environment, focusing on the authenticity of the protocol. It is based on one-hot encodings, tensor products and elliptic curve arithmetic. This scheme is designed to work with arithmetic gates, but we also show gadgets to implement transitions from binary inputs to arithmetic outputs and vice versa. For our scheme, each arithmetic gate takes at most one cyphertext of material to execute its functionality (assuming knowledge of the garbled inputs and their cleartexts). We show an application to blockchain transactions. The security of the scheme is proved in the UC setting.

Privacy-preserving technologies are a well-established area of research for modern digital systems, driven by regulatory mandates, such as the GDPR, and growing demand for the user privacy. A notable example of such technologies is blind signatures: a primitive that supports a creation of privacy-sensitive applications, ranging from secure e-voting and anonymous digital cash to privacy-preserving credentials and identity management systems. In this work, we introduce Coppercloud, a blind server-supported RSA signature scheme designed to enhance privacy in digital identity systems. Coppercloud enables a user to obtain a signature on a message, without revealing its content to the supporting server, while distributing the signing key between the user's device and the supporting server. We formalize the security requirements for blind server-supported signing by defining an ideal functionality ${\mathcal{F}^{\textsf{BlindSpl}}}$, and prove that Coppercloud securely realizes this functionality in the Universal Composability (UC) model.

For cryptosystems whose security relies on the hardness of decoding in the sublinear regime, the best known attacks are based on Information Set Decoding (ISD). In this regime, which is particularly relevant to HQC and Pseudorandom Correlation Generators (PCG), the cost of Gaussian elimination is no longer negligible and significantly affects the overall attack complexity. In this work, we revisit the Reduce-and-Prange technique of Kim and Lee, which reduces the cost of Gaussian elimination by reusing partial pivots. We refine its complexity analysis using branching-process techniques, thereby obtaining a more accurate assessment of its performance. We then extend partial pivot reuse to Stern's algorithm and introduce MAGE-Stern, a multilevel amortized Gaussian elimination variant of Stern's algorithm. Under a consistent logic-gate cost model, MAGE-Stern improves upon the best previously known attack against HQC by approximately 3 bits in time complexity, while reducing the memory complexity by about 12 bits. In particular, we estimate the security of the standardized HQC Category I parameter set at approximately 140 bits, about 3 bits below its NIST security target. We further combine multilevel amortized Gaussian elimination with the projective decoding framework of Carrier, Hatey, and Tillich, and investigate its application to regular decoding. Applied to the reference Pseudorandom Correlation Generator (PCG) parameter sets of Boyle, Couteau, Gilboa, and Ishai, the resulting algorithms improve upon the best previously known attacks by up to 6 bits across a broad range of practical parameters.

We present GRAFHEN, a new cryptographic scheme which offers Fully Homomorphic Encryption without the need for bootstrapping (or in other words, without noise). Building on the work of Nuida and others, we achieve this using encodings in groups. The groups are represented on a machine using rewriting systems. In this way the subgroup membership problem, which an attacker would have to solve in order to break the scheme, becomes maximally hard, while performance is preserved. In fact we include a simple benchmark demonstrating that our implementation runs several orders of magnitude faster than existing standards. We review many possible attacks against our protocol and explain how to protect the scheme in each case. Important note: this version was updated to take into account the attack proposed by Jules Dumezy (which is the first documented, successful attack on our scheme.) The recommended parameters have been altered. The new values seem to protect GRAFHEN against the attack; this is currently under investigation.

Private set union~(PSU) allows two parties to compute the union of their private sets without revealing their intersection. In many real-world applications, parties' datasets undergo frequent updates as elements are added or removed over time. Existing PSU protocols, however, must recompute the entire union from scratch whenever either party's set changes. This becomes highly inefficient when updates are small or frequent relative to the original set sizes. In this paper, we introduce the first updatable PSU~(uPSU) protocol for the standard two-party setting, which supports efficient incremental updates. We present a systematic classification of all possible update scenarios, which shows that only a small subset of updated elements actually modify the union, and establish the leakage baseline for uPSU. Based on these classification and leakage baseline, we provide a generic construction for uPSU that uses existing PSI and a tagged variant of PSU as building blocks. We prove security against semi-honest adversaries in the simulation-based model, and guarantee that incremental updates reveal no more information than a fresh execution of a standard PSU protocol on the updated sets. We instantiate and implement our generic construction using Kim et al.'s PSU protocol~(ACM SAC 2026) and Raghuraman and Rindal's PSI protocol~(ACM CCS 2022), demonstrating significant performance improvements over full recomputation of the union, even though its cost still depends on the original set size rather than purely on the update size. For set size $n = 2^{20}$ and update size $t = 2^{12}$, our protocol achieves a 14.1--45.4$\times$ speedup with a 4.8--59.1$\times$ communication reduction over full recomputation using baseline PSU protocols.

The Plonky3 Merkle tree implementation has become one of the most widely deployed Merkle tree constructions due to its high efficiency, and—through its integration into numerous succinct-argument systems—it currently helps secure an estimated \$4 billion in assets. Somewhat paradoxically, however, the underlying 2-to-1 compression function is not collision-resistant, nor even one-way, which at first glance appears to undermine the security of the entire Merkle tree. The prevailing ad-hoc countermeasure is to pre-hash data before using them as leaves in this otherwise insecure Merkle tree. In this work, we provide the first rigorous security analysis of this Merkle tree design and show that the Plonky3 approach is, in fact, sound. Concretely, we show (strong) position-binding and extractability.

The arithmetic crosscorrelation of pseudorandom sequences is a key measure of their suitability for cryptographic and communication applications. While prior work has addressed this quantity for binary sequences, the non-binary setting has remained largely unexplored. This paper initiates a systematic study of the arithmetic crosscorrelation of non-binary pseudorandom sequences constructed from higher-order multiplicative characters over finite fields. For two sequences of coprime periods $P$ and $Q$, defined via $r$-th order characters of polynomials of degree $d$, we show that the joint local patterns of the sequences are asymptotically uniformly distributed, and use this to derive an explicit bound on the arithmetic crosscorrelation $C^A_{S,T}(\tau)$. Specifically, we establish $$ \mathcal{N}\big(C^A_{S,T}(\tau)\big) \ = \ O\Big(\big(\varphi(r)d P^{1/2} Q (\log P)^2\big)^{\varphi(r)}\Big) $$ for all shifts $\tau$, for $r$-th order character sequences, where $\varphi(\cdot)$ is the Euler totient function and $\mathcal{N}(\cdot)$ denotes the norm function. To the best of our knowledge, this work establishes the first nontrivial upper bounds on the arithmetic crosscorrelation of non-binary pseudorandom sequences, thereby extending the results of Chen et al. [IEEE IT'22] and Yan and Ke [ePrint: 2026/616], which were obtained exclusively for the Legendre sequence.

Batched threshold encryption allows any $t$-out-of-$N$ parties in a committee to decrypt a batch of $B$ ciphertexts using sub-linear $o(NB)$ communication, while ensuring that any subset of $<t$ colluding parties learns no information about the underlying plaintext. Our first result is a simple batched threshold encryption scheme that is censorship resistant, avoids epoch restrictions, and achieves quasi-linear $O(B\log B)$ decryption complexity in the batch size $B$. Our scheme has the shortest ciphertext among all known constructions: $|\mathbb{G}_1| + |\mathbb{G}_T|$ for CPA security, with CCA security adding only $2|\mathbb{F}|$ via a simulation-extractable NIZK. However, our scheme requires an interactive setup phase (involving secure multiplications) and secret keys held by the committee grow linearly with the batch size. We prove security under the Decisional Bilinear $B$-Power Diffie-Hellman assumption in asymmetric pairing groups and provide an implementation in Rust to show that our scheme outperforms prior work. We also construct a variant of simple BTE, which allows for a tradeoff between secret-key size and censorship resistance. For any $\delta \leq B$, this variant reduces the size of the secret key held by each party from $O(B) \to O(\delta)$, and the decryption key from $O(BN) \to O(B + \delta N)$, but this comes at the cost of restricting a ciphertext encrypted with index $\mathsf{idx}$ to batch positions $i\in[B]$ satisfying $|i-\mathsf{idx}|<\delta$. Our second result is a new approach for verifying decryption in batched threshold encryption which enables a helper party (that carries out decryption) to provide hints that allow a verifier to check that decryption was carried out correctly using only MSMs and hashes. Concretely, we observe a $114.1\times$ speedup when verifying decryption of 2048 ciphertexts when compared against local decryption. Our approach is quite general and can be applied to other pairing-based advanced encryption schemes such as Timelock Encryption and Silent Threshold Encryption that can be cast as witness encryption schemes.

Outsourcing computations to cloud providers raises significant data privacy concerns, making Privacy-Preserving Computation via Fully Homomorphic Encryption (FHE) increasingly vital. However, adapting data sorting routines to the FHE domain introduces severe performance bottlenecks. This survey systematizes the state-of-the-art in FHE-based sorting algorithms. A novel complexity metric, FHE-Effort, is introduced to accurately evaluate homomorphic circuit efficiency. Eighteen algorithms are benchmarked across three major FHE schemes using a unified codebase. The analysis concludes that TFHE is currently the most efficient scheme for sorting applications, and sorting networks like Odd-Even Merge and Bitonic Sort offer the optimal algorithmic architectures.

Blind signatures play a central role in cryptographic protocols for privacy-preserving authentication and have attracted substantial attention in both theory and practice. A major line of research, dating back to the 1990s, has focused on constructing blind signatures from pairing-free groups. However, all known constructions in this setting require at least three moves of interaction between the signer and the user. These schemes treat the underlying group as a black box and rely on the random oracle in their security proofs. While computationally efficient, they suffer from the drawback that the signer must maintain state during a signing session. In contrast, round-optimal solutions are known under other assumptions and structures (e.g., RSA, lattices, and pairings), or via generic transformations such as Fischlin’s method (CRYPTO~'06), which employ non-black-box techniques. This paper investigates whether the three-round barrier for pairing-free groups is inherent. We provide the first negative evidence by proving that, in a model combining the Random Oracle Model (ROM) with Maurer’s Generic Group Model, no blind signature scheme can be secure if it signs sufficiently long messages while making at most a logarithmic number of random oracle queries. Our lower-bound techniques are novel in that they address the interaction of both models (generic groups and random oracles) simultaneously.

Efficient polynomial multiplication and matrix-vector operations are fundamental to computational algebra and modern cryptography. In lattice-based post-quantum cryptography (PQC), schemes utilizing Number Theoretic Transform (NTT)-unfriendly rings require highly optimized subquadratic multiplication algorithms. In this paper, we establish a rigorous mathematical framework for generalized $k$-way split polynomial multiplication and Toeplitz Matrix-Vector Product (TMVP) algorithms over arbitrary fields. First, we construct generalized $k$-way Schoolbook and Karatsuba multiplication algorithms, deriving exact closed-form recurrence relations and arithmetic complexities for any integer $k$. Second, we introduce a novel $k$-way TMVP algorithm utilizing optimal evaluation points and matrix row-reversal techniques. We mathematically prove that this generalized formulation strictly achieves the theoretical interpolation lower bound, requiring exactly $2k-1$ subproblems and yielding a subquadratic asymptotic complexity of $O(n^{\log_k(2k-1)})$. Furthermore, we determine the optimal consecutive application sequence of $k$-way Karatsuba and Schoolbook algorithms for any input size $n$, proving that the peak efficiency is driven entirely by the prime factorization of $n$. Finally, we establish exact algebraic crossover thresholds, demonstrating that our generalized TMVP formulas and optimal algorithmic sequences significantly outperform state-of-the-art unequal $k$-way splits and classical combinations in the literature, providing minimum arithmetic operation counts for $k \in \{5, 6, 8, 12\}$ and inputs of power-of-two and power-of-three dimensions.

Over the last decades, symbolic (Dolev-Yao) methods for the analysis of security protocols have proven to be effective to analyze and establish strong guarantees for widely deployed protocols and systems, such as TLS 1.3, E-voting protocols, EMV, and MLS. On the one hand, analysis methods like Tamarin and ProVerif provide automation and support for user-defined equational theories. On the other hand, methods like DY* offer more flexible and modular reasoning, but hardcode threat models and do not support custom equational theories. We present DyLean, a framework for the symbolic analysis of cryptographic protocols in the Lean theorem prover. Our framework comprises both a flexible general-purpose symbolic semantics, as well as a concrete proof methodology. DyLean allows defining protocols and expected security properties; its semantics and equational theories can be customized by the user. Furthermore, the semantics are agnostic of the specific proof methodology: our goal is to provide a generic framework that can be used by the community as a foundation to develop various proof methodologies. Moreover, we provide a concrete proof methodology inspired by DY*, based on trace invariants. Thus, DyLean inherits from the qualities of DY*: it is able to analyze protocols involving unbounded loops or datastructures, and is able to compose security proofs in a variety of scenarios. Our proof methodology improves on DY* by allowing for user-defined equational theories and threat models. We exercise DyLean on several focused case studies, which include protocols using merkle trees, ratcheting protocols, post-quantum protocols, and protocols analyzed under different equational theories, which demonstrates that DyLean can effectively analyze protocols with each of these features.

Proof-of-useful-work (PoUW) certifies computational hardness, not utility: a certified computation need not be anyone's demanded job. We separate three properties of a work receipt — work soundness ($\mathsf{W}$), job binding ($\mathsf{B}$), and demand exogeneity ($\mathsf{E}$) — and locate the gap at $\mathsf{E}$. Two results are unconditional. First, payments between coalition-controlled requesters and workers are recoverable transfers that contribute no Sybil-resistant cost, so no security lower bound may count them (Lemma 1). Second, under free pseudonyms and endogenous observation a coalition can simulate the receipts of economically independent requesters, so endogenous receipts cannot certify $\mathsf{E}$ (Theorem 1); we lower-bound the cost of evading a stated class of provenance estimators. Building on these, a robustness bound: because a permissionless mechanism must remain live on the zero-demand path, its leader-election floor cannot depend on the demand component of service receipts (Theorem 2), and any admissible receipt boost is quantitatively capped. Fork-independent salvage value of useful outputs can leave security neutral, negative, or positive depending on salvage asymmetry and demand, which we characterize in a stylized free-entry model. Constructively, an irrecoverable tax on every settled payment makes the burn — not proof of independence — the security resource. Deployed evidence comprises one reported audit (Pearl cuPOW) and a reward-program farming analogue; the election-side failure is, at present, a model prediction. Useful-computation receipts are appropriate instruments for payment, collateral, and loss allocation — and a bounded, priced election boost — but not the leader-election floor.

Secure key leasing allows a cryptographic key to be leased as a quantum state in such a way that the key can later be revoked in a verifiable manner. In this work, we propose a modular framework for constructing secure key leasing with a classical-lessor, where the lessor is entirely classical and, in particular, the quantum secret key can be both leased and revoked using only classical communication. Based on this framework, we obtain classical-lessor secure key leasing schemes for public-key encryption (PKE), pseudorandom function (PRF), and digital signature. We adopt the strong security notion known as security against verification key revealing attacks (VRA security) proposed by Kitagawa et al. (Eurocrypt 2025) into the classical-lessor setting, and we prove that all three of our schemes satisfy this notion under the learning with errors assumption. Our PKE scheme improves upon the previous construction by Goyal et al. (Eurocrypt 2025), and our PRF and digital signature schemes are respectively the first PRF and digital signature with classical-lessor secure key leasing property.

Lookup arguments are designed to prove that all elements in a query vector appear in a lookup table. These arguments are critical for efficiently proving ZK-unfriendly statements, such as range checks and the evaluation of complex functions. Most existing lookup arguments are optimized for scenarios where the query size is smaller than the table size. However, in many real-world applications, the query size $m$ is often much larger than $n$, the table size. This disparity leads to inefficiencies in such schemes. To overcome this limitation, we propose Celer, a novel lookup argument in which the prover's runtime increases slowly with $m$, thereby providing improved scalability. The efficiency of our lookup PIOP stems from reducing the number of commitments to be sublinear in the query size $m$, while maintaining field operations linear in $m$. Experimental results demonstrate that our lookup scheme significantly outperforms state-of-the-art lookup schemes. For the workload of query size $m=2^{28}$ and table size $n=2^{16}$ (a real world case in proving Llama language model inference), our scheme achieves a 25.9$\times$ prover-time speedup over plookup and is 9.4$\times$ faster than LogUp.

Hamming Quasi-Cyclic (HQC) is a code-based key encapsulation mechanism selected by NIST for standardization, making its resistance to implementation attacks critically important. We present a side-channel attack that exploits load/store leakage in the manipulation of HQC's sparse secret vectors. Analysing Cortex-M4 assembly generated from the reference implementation, we identify a leakage surface in which the low and high 32-bit halves of each 64-bit word leak with different strengths, due to compiler-generated register spilling. We exploit this leakage to construct a simple zero-word distinguisher classifying machine words of the secret vector as zero or nonzero from electromagnetic measurements. The recovered zero positions are then translated into decoding hints, reducing HQC key recovery to a shortened syndrome-decoding problem. We analyse the resulting decoding complexity for all HQC parameter sets: at 32-bit granularity an expected $88.7\%$ of the machine words of~$y$ are zero for HQC-1, cutting the decoding to ${\approx}\,2^{46}$ bit operations. Experiments on a Cortex-M4 validate the predicted low/high-half asymmetry---approximately $500$ traces for the stronger low-half channel and $5{,}000$ for the weaker high-half channel---and recover the zero words of an HQC-1 key at 32-bit granularity. Finally, we discuss practical countermeasures that eliminate the sparsity exploited by the attack.

We formalize the notion of polynomial commitment schemes (PCSs) in the proof assistant Isabelle/HOL and formally verify the security proofs of two variants of the widely popular Kate, Zaverucha, and Goldberg (KZG) construction. Moreover, we formalize the Algebraic Group Model (AGM) by Fuchsbauer, Kiltz, and Loss using a novel constraint-programming-inspired approach. We formalize a reusable abstract definition of polynomial commitment schemes and define games for correctness, binding, hiding, and knowledge soundness/extractability. Based on this, we verify all applicable security proofs for two concrete PCS constructions: the standard (DL-)KZG and a batched KZG, using our AGM formalization in the knowledge-soundness proofs. Our proofs follow Shoup’s sequence-of-games approach, with machine-checked transitions, and are carried out in the CryptHOL framework for formal verification of cryptography in Isabelle. To our knowledge, this work is the first formalization of polynomial commitment schemes, the first formalization of the AGM, and the first formal verification of the security proofs for any concrete polynomial commitment scheme. This work lays the foundation for the formal verification of advanced cryptographic constructions, such as pairing-based zero-knowledge proofs (ZKPs) and succinct arguments.

We study large-scale, field-agnostic, hash-based polynomial commitment schemes (PCSs) with the goal of minimizing prover time while preserving polylogarithmic proof size and verifier time. This setting is motivated by advanced applications of zero-knowledge succinct non-interactive arguments of knowledge (zkSNARKs) such as zero-knowledge machine learning (zkML), where committed polynomials may encode billions of parameters and large prime fields are desirable for avoiding wraparound in fixed-point arithmetic. We introduce SwitchFold, a generic construction of a hash-based multilinear PCS from any sequence of linear codes with geometrically increasing block lengths. The polylogarithmic proof size and verifier time do not rely on any specific algebraic structure of the codes, while the linear prover time follows solely from the linear encoding time. At its core, SwitchFold recursively applies the code-switching technique (Ron-Zewi and Rothblum, JACM ’24), reducing each multilinear extension (MLE) claim under one code to a simpler MLE claim under a shorter code. The generator-matrix MLE claims produced by code switching are accumulated across repeated PCS openings using an accumulation scheme (Bünz et al., TCC ’20), and are then proved through a final recursion. We instantiate SwitchFold with the Brakedown code sequence (Golovnev et al., CRYPTO ’23), whose recursive code structure aligns naturally with our framework; we call the resulting scheme BrakeFold. In contrast to prior code-switching PCSs such as Blaze (Brehm et al., EUROCRYPT ’25) and BrakingBase (Nair et al., ASIACRYPT ’25), SwitchFold does not require an auxiliary foldable code. At the scale of one billion coefficients and 100-bit security, the marginal cost of each additional PCS opening in BrakeFold yields 3.5× smaller proof size and 20.6× faster verification than Brakedown, with only a 1.3× increase in prover time. Its succinctness matches that of BaseFold (Zeilberger et al., CRYPTO ’24), while reducing prover time by 17.0×.

Masking is a principal countermeasure against side-channel attacks, yet its practical deployment is often constrained by the high cost of randomness. Existing approaches for reducing randomness overhead generally follow two directions. The first focuses on designing low-randomness gadgets, which often introduces considerable area and latency overheads for complex boolean functions. The second relies on architecture-level randomness reuse, but securely managing the resulting algebraic dependencies typically still requires additional fresh randomness or extra initial randomness. In this work, we introduce a dependency-tracking abstraction, termed unique randomness guard (URG), for reasoning about randomness reuse in masked hardware circuits. We develop a randomness recycling methodology that eliminates historical randomness dependencies before safely reusing the historical randomness to subsequent computations. This enables secure randomness reuse without requiring additional fresh randomness. To demonstrate the practicality of the proposed methodology, we apply it to first-order masked AES hardware implementations in both parallel and serial architectures. The security of these architectures is proven under the robust probing model and practically validated via TVLA on an FPGA platform. Furthermore, hardware synthesis results demonstrate that our implementations achieve highly competitive area and latency performance compared to state-of-the-art low-randomness designs, while using randomness solely for input encoding.

As the usage of Artificial Intelligence (AI) for sensitive purposes increases, there is a growing need for privacy-aware explainable AI (XAI) tools. In this paper, we present a privacy-preserving counterfactual explanation algorithm. Our starting point is a decision-support model that is able to operate on vertically partitioned datasets, meaning that each party holds a different subset of datapoint attributes. The goal of a counterfactual algorithm is to find, given an observation, a datapoint from the (virtual) dataset that is closest to the observation but has a different label. Our algorithm fully preserves the privacy of the n datapoints belonging to the different parties by combining the strengths of homomorphic encryption and secret sharing. Through a number of experiments, we demonstrate the added value of combining multiple datasets in a realistic scenario and show that the privacy-preserving solution does not affect the accuracy. We fully implement our solution and demonstrate that it scales as to thousands of datapoints.

Recently, Shark (S\&P'25) considered the problem of actively two-party secure machine learning inference using an authenticated distributed comparison function (DCF). This is the state-of-the-art work in this setting. On the other hand, Grotto (CCS'23) built a variant DCF with the key size half that of classic DCF. Unfortunately, as Shark states, \textit{it is not known how to extend Grotto to the malicious setting}. In this paper, we present the first actively secure Grotto-style DCF scheme. Our authenticated DCF is deliberately designed on the correlated GGM tree and maintains the key-size advantage of semi-honest Grotto. We further implement an actively secure ML inference framework, named LightShark, which supports efficient primitives (e.g., ReLU, spline, and truncation) and ML models (e.g., VGG-16, GPT, BERT). Compared with Shark, our LightShark outperforms by $1.49 \times \sim 2.69\times$ and reduces communication costs by $66.7\%$ for Bert-base inference. Surprisingly, for larger LLM models, the experimental evaluation demonstrates that our framework works vastly well.

We prove that under a plausible heuristic assumption (on the smoothness of certain random integers), the supersingular isogeny problem can be solved in time and memory $p^{1/3 + o(1)}$. This improves upon the previous best complexity of $p^{1/2} \cdot(\log p)^{O(1)}$. This problem is arguably the central hard problem underlying isogeny-based cryptography, and the cost of its resolution is a major (and often the only) factor in the choice of secure parameters. The impact on concrete parameter sets remains to be clarified, as the asymptotic advantage of the new algorithm is mitigated by a superpolynomial overhead hiding in the $o(1)$ exponent, and by its high memory requirement.