Zero-knowledge succinct arguments of knowledge (zkSNARK) provide short privacy-preserving proofs for general NP problems. Public verifiability of zkSNARK protocols is a desirable property, where the proof can be verified by anyone once generated. Designated-verifier zero-knowledge is useful when it is necessary that only one or a few individuals should have access to the verification result. All zkSNARK schemes are either fully publicly verifiable or can be verified by a designated verifier with a secret verification key. In this work, we propose a new notion of a hybrid verification mechanism. Here, the prover generates a proof that can be verified by a designated verifier. For this proof, the designated verifier can generate auxiliary information with its secret key. The combination of this proof and the auxiliary information allows any public verifier to verify the proof without any other information. We also introduce necessary security notions and mechanisms to identify a cheating designated verifier or the prover. Our hybrid verification zkSNARK construction is based on module lattices and adapts the zkSNARK construction by Ishai et al. (CCS 2021). In this construction, the designated verifier is required only once after proof generation to create the publicly verifiable proof. Our construction achieves a small constant-size proof and fast verification time, which is linear in the statement size.

LESS is a digital signature scheme that is currently in the second round of the National Institute of Standards and Technology’s (NIST’s) ongoing call for standardization of additional post-quantum signature schemes. Recently, the ZKfault attack by Mondal et al. (Asiacrypt 2024) showed several attack surfaces on the first version of LESS (LESS-v1) that can be exploited using different fault attacks. However, the designers of LESS have updated the scheme in the second round to improve efficiency and signature size. The fault attacks in ZKfault are not directly applicable to this new version of LESS (LESS-v2). The physical security of LESS-v2 is still unexplored. In this work, we analyze the new structure of the LESS-v2 signature scheme and propose a method for universal forgery. One crucial observation is that, for LESS-v2, an adversary does not require the full signing key, but some other secret-related information, namely, a permutation of secret monomial matrices. We assume an adversary can use execution interruption techniques, such as fault attacks, to recover this extra information. We have analyzed multiple such attack surfaces in the design of LESS-v2, and using fault injection, we can recover secret-related information. We showed the average number of required faults for two particular fault models to recover the secret equivalent component and observed that, for most parameters, we need only 1 faulted signature, and at most 1088. Our attacks rely on simple and standard fault models. We demonstrated these using both simulation and a simple experimental setup.

With the rapid advances in quantum computer architectures and the emerging prospect of large-scale quantum memory, it is becoming essential to classically verify that remote devices genuinely allocate the promised quantum memory with specified number of qubits and coherence time. In this paper, we introduce a new concept, proofs of quantum memory (PoQM). A PoQM is an interactive protocol between a classical probabilistic polynomial-time (PPT) verifier and a quantum polynomial-time (QPT) prover over a classical channel where the verifier can verify that the prover has possessed a quantum memory with a certain number of qubits during a specified period of time. PoQM generalize the notion of proofs of quantumness (PoQ) [Brakerski, Christiano, Mahadev, Vazirani, and Vidick, JACM 2021]. Our main contributions are a formal definition of PoQM and its constructions based on hardness of LWE. Specifically, we give two constructions of PoQM. The first is of a four-round and has negligible soundness error under subexponential-hardness of LWE. The second is of a polynomial-round and has inverse-polynomial soundness error under polynomial-hardness of LWE. As a lowerbound of PoQM, we also show that PoQM imply one-way puzzles. Moreover, a certain restricted version of PoQM implies quantum computation classical communication (QCCC) key exchange.

LOL (League of Legends) is a general framework for designing blockwise stream ciphers to achieve higher software performance in 5G/6G. Following this framework, stream ciphers LOL-MINI and LOL-DOUBLE are proposed, each with a 256-bit key. This paper focuses on analyzing their security against correlation attacks. Additionally, we propose an observation on constructing linear approximation trails. The repeated linear approximations in trails may not only increase the number of active S-boxes but also make the correlations of corresponding approximations zero. We propose a new rule to address this situation and develop multiple correlation attacks. Furthermore, we use theoretical cryptanalysis to lower the time complexity of aggregation and construct multiple linear approximations efficiently. For LOL-MINI, we construct approximately $2^{32.17}$ linear approximations with absolute correlations ranging from $2^{-118.38}$ to $2^{-127}$. We launch the developed multiple correlation attack on LOL-MINI with a time complexity of $2^{250.56}$, a data complexity of $2^{250}$, a memory complexity of $2^{250}$ and a success probability of 99.4$\%$. For LOL-DOUBLE, there similarly exist approximately ${{2}^{22.86}}$ linear approximations with absolute correlations ranging from $2^{-147.23}$ to $2^{-156}$. It is worth noting that our results do not violate the declaration of LOL-MINI since the maximum length of keystreams for a single pair of key and IV is less than $2^{64}$.

Computer-aided cryptography, with particular emphasis on formal verification, promises an interesting avenue to establish strong guarantees about cryptographic primitives. The appeal of formal verification is to replace the error-prone pen-and-paper proofs with a proof that was checked by a computer and, therefore, does not need to be checked by a human. In this paper, we ask the question of how reliable are these machine-checked proofs by analyzing a formally verified implementation of the Line-Point Zero-Knowledge (LPZK) protocol (Dittmer, Eldefrawy, Graham-Lengrand, Lu, Ostrovsky and Pereira, CCS 2023). The implementation was developed in EasyCrypt and compiled into OCaml code that was claimed to be high-assurance, i.e., that offers the formal guarantees of guarantees of completeness, soundness, and zero knowledge. We show that despite these formal claims, the EasyCrypt model was flawed, and the implementation (supposed to be high-assurance) had critical security vulnerabilities. Concretely, we demonstrate that: 1) the EasyCrypt soundness proof was incorrectly done, allowing an attack on the scheme that leads honest verifiers into accepting false statements; and 2) the EasyCrypt formalization inherited a deficient model of zero knowledge for a class of non-interactive zero knowledge protocols that also allows the verifier to recover the witness. In addition, we demonstrate 3) a gap in the proof of the perfect zero knowledge property of the LPZK variant of Dittmer, Ishai, Lu and Ostrovsky (CCS 2022) that the EasyCrypt proof is based, which, depending on the interpretation of the protocol and security claim, could allow a malicious verifier to learn the witness. Our findings highlight the importance of scrutinizing machine-checked proofs, including their models and assumptions. We offer lessons learned for both users and reviewers of tools like EasyCrypt, aimed at improving the transparency, rigor, and accessibility of machine-checked proofs. By sharing our methodology and challenges, we hope to foster a culture of deeper engagement with formal verification in the cryptographic community.

Threshold fully homomorphic encryption (ThFHE) enables multiple parties to perform arbitrary computation over encrypted data, while the secret key is distributed across the parties. The main task of designing ThFHE is to construct threshold key-generation and decryption protocols for FHE schemes. Among existing FHE schemes, FHEW-like cryptosystems enjoy the advantage of fast bootstrapping and small parameters. However, known ThFHE solutions use the ``noise-flooding'' technique to realize threshold decryption, which requires either large parameters or switching to a scheme with large parameters via bootstrapping, leading to a slow decryption process. Besides, for key generation, existing ThFHE schemes either assume a generic MPC or a trusted setup, or incur noise growth that is linear in the number $n$ of parties. In this paper, we propose a fast ThFHE scheme Ajax, by designing threshold key-generation and decryption protocols for FHEW-like cryptosystems. In particular, for threshold decryption, we eliminate the need for noise flooding, and instead present a new technique called ``mask-then-open'' based on random double sharings over different rings, while keeping the advantage of small parameters. For threshold key generation, we show a simple approach to reduce the noise growth from $n$ times to $max(0.038n,2)$ times in the honest-majority setting, where at most $t=\floor{(n-1)/2}$ parties are corrupted. Our end-to-end implementation reports the running time 17.6 $s$ and 0.9 $ms$ (resp., 91.9 $s$ and 4.4 $ms$) of generating a set of keys and decrypting a single ciphertext respectively, for $n=3$ (resp., $n=21$) parties under the network of 1 Gbps bandwidth and 1 $ms$ ping time. Compared to the state-of-the-art implementation, our protocol improves the end-to-end performance of the threshold decryption protocol by a factor of at least $5.7\times$ $\sim$ $283.6\times$ across different network latencies from $t=1$ to $t=13$. Our approaches can also be applied in other types of FHE schemes like BGV, BFV, and CKKS.

We construct a public-key encryption scheme from the hardness of the (planted) MinRank problem over uniformly random instances. This corresponds to the hardness of decoding random linear rank-metric codes. Existing constructions of public-key encryption from such problems require hardness for structured instances arising from the masking of efficiently decodable codes. Central to our construction is the development of a new notion of duality for rank-metric codes.

The ZUC stream cipher is integral to modern mobile communication standards, including 4G and 5G, providing secure data transmission across global networks. Recently, Dutta et al. (Indocrypt, 2024) presented the first quantum resource estimation of ZUC under Grover's search, Although preliminary, this work marks the beginning of quantum security analysis for ZUC. In this paper, we present an improved quantum resource estimation for ZUC, offering tighter bounds for Grover-based exhaustive key search. Beyond traditional quantum resource estimations, we also provide a concrete timescale required to execute such attacks using the specified quantum resources. Our findings show that a full-round, low depth implementation of ZUC-128 can be realized with a maximum of $375$ ancilla qubits, a T-count of $106536$, and a T-depth of $15816$. Furthermore, the Grover-based key search can be performed most efficiently using $1201$ logical qubits, $170681$ T gates, and a T-depth of $78189$, resulting in a runtime of $1.78\times10^{11}$ years, an improvement of 93.43% over the estimated $2.71 \times 10^{12}$ years by the implementation given by Dutta et al., we also provide akin analysis for ZUC-256 with an 99.23% decrease in time. These estimations are done assuming state-of-the-art superconducting qubit error-correcting technology.

Authenticated garbling, introduced by Wang et al., CCS'17, is a leading paradigm for achieving constant-round maliciously-secure 2PC. In this work, we upgrade authenticated garbling to efficiently support tensor gates (introduced in the context of semi-honest garbling by Heath et al., CCS'21) using the one-hot garbling technique. Our maliciously-secure garbled tensor gate computes $\boldsymbol {x}\otimes \boldsymbol{y}$ for $\boldsymbol{x}\in \{0,1\}^n,\boldsymbol{y} \in \{0,1\}^m$ with $O(n+m)\kappa + O(nm)$ bits of communication, where $\kappa$ is the computational security parameter and $n,m$ are logarithmic in $\kappa$. This improves the best prior constant-round maliciously secure approach, which incurs $O(nm)\kappa$ communication. Our protocol is concretely efficient and improves over state-of-the-art for applications including integer multiplication, matrix multiplication, and more. We benchmark the online phase of our protocol and observe a $5.41\times$ improvement in communication and $3.35\times$ improvement in wall clock time when computing a $128\times 128$ bit tensor product.

ChaCha and Salsa are two ARX based stream ciphers which are widely used in data encryption including TLS v1.3 standard, VPN software etc. Exploiting Probabilistic Neutral Bits (PNB) is one of the most significant cryptanalysis strategies for reduced-round versions of these ciphers. The seminal work using PNB by Aumasson et al. (FSE 2008) claims that the PNB set mostly depends on the output bit difference occurring in the intermediate round. The subsequent works mainly relied on the differential or differential-linear cryptanalysis, or multiple distinct input-output differentials for which the bias is higher than a threshold in the intermediate round. In this paper, we propose a new PNB set construction based on multiple output bit differences with respect to a single input bit difference only. We exploit the differentials to mount key recovery attacks using a multi-step procedure depending on our new PNB set. Our attack achieves a time complexity of $2^{167.90}$ for ChaCha20/7 and $2^{183.54}$ for Salsa20/8 in 256-bit versions, beating all the existing PNB-based attacks on ChaCha20/7 and Salsa20/8 by a significant margin. Further, both our time and data complexities for ChaCha20/7.5 are better than the latest published works by Flórez-Gutiérrez and Todo (Eurocrypt 2025 and Asiacrypt 2025). For 128-bit versions, our attack procedure results in a time complexity of $2^{115.24}$ for ChaCha20/6.5 and $2^{98.40}$ for Salsa20/7.5 respectively. We have also verified our attack experimentally on a published toy version of ChaCha (FSE 2023).

Proof-of-stake blockchains require consensus protocols that support Dynamic Availability and Reconfiguration (which we call the DAR model). Here, Dynamic Availability means that the consensus protocol should remain live even if a large number of nodes temporarily crash, and Reconfiguration means it should be possible to change the set of operating nodes over time. State-of-the-art protocols inspired by the DAR model, such as Ethereum, Cardano's Ouroboros, or Snow White, require additional model features comprising external mechanisms or node capabilities that are difficult to justify, such as social consensus or the requirement that key evolution be performed even when nodes have crashed. The key result of this paper is the necessary and sufficient adversarial condition under which consensus can be achieved in the plain DAR model, without any extra features. We then introduce an additional feature to the model that is justified by proof-of-stake blockchain designs: honest nodes complete a sign-off procedure the moment they express intent to exit from the set of operating nodes. This additional feature reduces the power of the adversary relative to the plain DAR model and helps us obtain a bootstrapping gadget that is particularly simple and efficient in the common optimistic case of few reconfigurations and no double spending.

Linear error-correcting codes with fast encoding and high minimum distance are a central primitive across modern cryptography. They appear prominently in at least two domains: (1) pseudorandom correlation generators (PCGs), which enable sublinear-communication generation of correlations such as oblivious transfer and vector oblivious linear evaluation, and (2) zero-knowledge proof systems, where linear-time encoders underpin proof soundness and scalability. In both settings, the prover or sender must multiply by a large generator matrix $\mathbf{G}$, often with dimensions in the millions, making computational efficiency the dominant bottleneck. We propose a generalized paradigm for building crypto-friendly binary codes with provable minimum distance. Roughly speaking, these codes are based on randomized turbo codes such as repeat-accumulate codes. We prove linear asymptotic minimum distance and compute the exact expected weight spectrum for concrete sizes. We observe that our codes approach the Gilbert-Varshamov distance bound and outperform prior constructions. We construct several novel codes, the most promising of which we call Block-Accumulate codes. Among codes with provable distance, our code is $8\times$ faster than the state of the art on a CPU and $50\times$ faster on a GPU; even against aggressive parameters with conjectured distance, it is $3\times$ and $20\times$ faster, respectively. Under these parameters, this yields overall PCG speedups of $2.5\times$ on the CPU and $15\times$ on the GPU, achieving a projected 200$+$ million OTs per second, or about 100 million binary Beaver triples per second, on the GPU (excluding the one-time 10 ms GGM seed expansion). We also observe a $2\times$ encoding speedup and half the peak memory consumption in the Blaze zero-knowledge (PCS) scheme of Brehm et al. (EUROCRYPT~'25).

Blind signatures have become a cornerstone for privacy-sensitive applications such as digital cash, anonymous credentials, and electronic voting. The elliptic curve variant of the Digital Signature Algorithm (ECDSA) is widely adopted due to its efficiency in resource-constrained environments, such as mobile devices and blockchain systems. Building blind ECDSA is hence a natural goal. One presents the first such construction relying solely on the ECDSA assumption. Despite the inherent complexities in integrating blindness with ECDSA, we design a protocol that ensures both unforgeability and blindness without introducing new computational assumptions and ensuring concurrent security. It involves zero-knowledge proofs based on the MPC-in-the-head paradigm for complex statements combining relations on encrypted elliptic curve points, their coordinates, and discrete logarithms.

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

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

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.

This paper presents a unified information-theoretic framework for steganography that simultaneously addresses reliability, statistical undetectability, computational security, and robustness over noisy channels. Unlike prior work that treated these aspects separately under idealized assumptions, the framework formalizes them within a single model, providing definitions, capacity bounds, and impossibility results based on statistical distances. It also considers computationally bounded adversaries and trade-offs between payload, detectability, and error, offering a rigorous foundation for designing secure, robust, and efficient steganographic systems.

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

Mental Poker enables two players to play card games at a distance without having a physical deck of cards at hand, as long as they have reliable trapdoor permutations or access to Oblivious Transfer (OT). OT itself can be stored and extended using just a one-way function. We examine whether Mental Poker can be extended from initial hands of ordinary physical poker. On the theoretical side, this work establishes OT amplification/extraction as a cryptographic primitive using asymmetrically-viewed fully-randomizing permutations. On the pragmatic, it is naturally related to ``card cryptography'' although in a very restricted sense: 52-card deck protocols using fully scrambling shuffles. While secret-key exchange protocols make strong use of full shuffles, full shuffles are avoided in 2PC/AND/Solitaire card settings because of detrimental over-randomization. Within those domains, this work explains decades-old impossibility conjectures in certain circumstances. More positively, we provide several practical and information-theoretically secure ways to establish base OTs from 5-Card Draw over ordinary decks at rates sufficient to establish a foothold for indefinite Mental Poker extension in just an afternoon of play.

Plaintext-awareness of AEAD schemes is one of the more obscure and easily misunderstood notions. Originally proposed by Andreeva et al., Mennink and Talnikar showed in 2025 that the original definitions are vague and leave too much room for interpretation. They presented new definitions and analyzed the three main AEAD compositions relative to the new definitions. In particular, they showed that MAC-then-Encrypt (MtE) is not plaintext-aware. However, they showed that an SIV-style variant is indeed plaintext-aware. In this work, we first show that their analysis contains a gap, voiding their proof. We show this by showing several attacks; against their choice of extractor, with trivial complexity, and against any extractor, with birthday-bound complexity. Next, we re-establish their results by designing a new extractor that captures their intended goal and prove a tight PA1 security bound. We also show that the result is not dependent on the encryption scheme used, by showing that an extractor can also be designed for sMtE[ΘCB3], a variant where the encryption step is done by an ΘCB3-like scheme. Afterwards, we strengthen their results, by revisiting other compositions. In particular, we show that Encrypt-then-MAC (EtM) is in fact PA2-secure. Furthermore, we show that SIV-style MtE cannot be PA2-secure. Additionally, we show that Encode-then-Encipher is also PA2-secure, but not beyond the first successful forgery. More importantly, we show that up to some necessary assumptions, PA2 and RAE are equivalent. This result, while positive, holds only up to the first successful forgery. This indicates that the PA2 formalization maybe too strong for practical schemes, since we believe RAE sufficient for intuitive security. Last but not least, we investigate the value of the notion of plaintext awareness. We look deeper into the relation between plaintext awareness and confidentiality. We show that the problem of confidentiality in the presence of release of unverified plaintext can be seen as a confidentiality-with-leakage problem in the simulatable leakage framework. In this regard, we start, by showing that PA1 security cannot imply confidentiality with leakage. Similarly, we compare our results to the AERUP notion of TOSC 2019. We show that a scheme can be AERUP secure but not secure against a somewhat straightforward left-or-right attack in the same model. This puts into question the meaning and relevance of the PA1 and AERUP security notions. Results based on these notions can be seen as providing security in a two-phase game, where the adversary does not observe any leakage after the first challenge query, as we argue in the paper. On the positive side, we show that if a scheme achieves IND-CPA, INT-RUP and PA2, then it achieves confidentiality with leakage for the appropriate leakage function. This closes a gap in the literature on the relation between confidentiality with leakage and RUP notions.

Group-action-based Sigma protocols have proven to be truly flexible for the design of advanced cryptosystems. When they are compiled via the Fiat-Shamir transform, the resulting NIZKPs can be efficiently optimized using standard techniques within the fixed-weight framework. Unfortunately, the same techniques are not as effective when they are combined with straight-line extractable NIZKPs (e.g. Fischlin, CRYPTO '05), a key building block in the design of complex protocols. This work introduces the GAO (Group Action Oriented) transform, a new generic compiler that produces straight-line extractable NIZKPs from Sigma protocols while significantly simplifying the analysis of the fixed-weight framework. The GAO transform is then optimized in two different ways. First, by defining a collision predicate that results to be even more effective combined with GAO than with the Fischlin transform, for which was originally introduced (Kondi and shelat, ASIACRYPT '22). Second, adopting a technique, which we call Stretch-and-Compress (SC), that enables trading a smaller number of expensive operations for a larger number of inexpensive ones, which surprisingly leads to a reduction of both the computational complexity and the proof size. Our final transform, obtained from GAO applying the two optimizations, is called SC-Coll-GAO. The practical advantages of the SC-Coll-GAO transform are theoretically motivated and concretely tested on the Sigma protocol underlying the Fiat-Shamir digital signature LESS, a code-based candidate that recently advanced to the second round of the NIST standardization process specifically purposed for post-quantum signatures. Remarkably, when compared to the Fiat-Shamir LESS baseline, SC-Coll-GAO incurs a computational cost increase by 50-60%, while signature sizes grow by only 10-20%.

This work studies the security and constructions of correlation robust (CR) hash functions in secure multi-party computation (MPC). Existing definitions of CR hashing are all game-based (i.e., no simulator to achieve programmability or extractability), but MPC protocols are proven secure in the simulation-based models including both stand-alone and universal composability models. We found that for some MPC protocols, e.g., TinyOT-like authenticated-triple generation protocols and correlated oblivious transfer (COT) extension protocols, such a mismatch could lead to a gap in security proofs, even for the semi-honest adversary and stand-alone model. To bridge the gap, we introduce a simulation-based security notion for CR hash functions to allow secure composition. Instead of building from scratch, we introduce such a simulator to a wide class of existing ideal-cipher-based CR hashing constructions, and derive the security bound from their original game-based CR security. This enables us to obtain an efficient CR hashing construction making just one call to a blockcipher, and is much more efficient than the construction from a random oracle used in previous TinyOT-like protocols. We showcase the utility of the new CR notion in easing security proofs and mitigating the risk of errors on two classes of protocols: (1) authenticated-triple generation protocols in the TinyOT family with a countermeasure; (2) COT extension protocols with bootstrapped iterations.

A random local function defined by a $d$-ary predicate $P$ is one where each output bit is computed by applying $P$ to $d$ randomly chosen bits of its input. These represent natural distributions of instances for constraint satisfaction problems. They were put forward by Goldreich as candidates for low-complexity one-way functions, and have subsequently been widely studied also as potential pseudo-random generators. We present a new search-to-decision reduction for random local functions defined by any predicate of constant arity. Given any efficient algorithm that can distinguish, with advantage $\epsilon$, the output of a random local function with $m$ outputs and $n$ inputs from random, our reduction produces an efficient algorithm that can invert such functions with $\tilde{O}(m(n/\epsilon)^2)$ outputs, succeeding with probability $\Omega(\epsilon)$. This implies that if a family of local functions is one-way, then a related family with shorter output length is family of pseudo-random generators. Prior to our work, all such reductions that were known required the predicate to have additional sensitivity properties, whereas our reduction works for any predicate. Our results also generalise to some super-constant values of the arity $d$, and to noisy predicates.

We propose Pool: a conceptually simple post-quantum (PQ) oblivious pseudorandom function (OPRF) protocol, that is round-optimal (with input-independent preprocessing), practically efficient, and has security based on the well-understood hardness of the learning with rounding (LWR) problem. Specifically, our design permits oblivious computation of the LWR-based pseudorandom function $F_{\mathsf{sk}}(x) = \lceil H(x)^{\top} \cdot \mathsf{sk} \rfloor_{q,p}$, for random oracle $H: \{0,1\}^* \mapsto \mathbb{Z}_q^n$ and uniformly chosen $\mathsf{sk} \in \{0,1\}^n$. For 128-bits of semi-honest security, the Pool OPRF has an online communication cost of 11.9~kB, and a computational runtime of less than 2~ms on a single thread (via an open-source software implementation). This is more efficient (in either online communication cost or runtime) than constructions from well-known PQ PRFs, and is competitive even with constructions that only conjecture PQ security on lesser-known assumptions. As a result, our design gives high-performance, post-quantum variants of established OPRF applications in multi-party computation and private set operation protocols.

A Private Simultaneous Messages (PSM) protocol is a secure multiparty computation protocol with a minimal interaction pattern, which allows input parties sharing common randomness to securely reveal the output of a function by sending messages only once to an external party. Since existing PSM protocols for arbitrary functions have exponentially large communication complexity in the number $n$ of parties, it is important to explore efficient protocols by focusing on special functions of practical use. In this paper, we study the communication efficiency of PSM protocols for symmetric functions, which provide many useful functionalities for real-world applications. We present a new $n$-party PSM protocol for symmetric functions with communication complexity $n^{2d/3+O(1)}$, where $d$ is the size of the input domain of each party. Our protocol improves the currently best known communication complexity of $n^{d+O(1)}$. As applications to other related models, we show that our novel protocol implies improved communication complexity of ad-hoc PSM, where only a subset of parties actually send messages, and also leads to a more communication-efficient robust PSM protocol, which is secure against collusion of the external party and input parties. The extension to ad-hoc PSM is not a straightforward application of the previous transformation but includes an optimization technique based on the symmetry of functions.

Proof-of-work (PoW)-based consensus mechanisms have long been criticized for their high resource (electricity, e-waste) consumption and reliance on hash puzzles, which have no utility beyond cryptocurrencies. Proof-of-Useful Work (PoUW) has emerged as an alternative whose mining objective is expected to provide societal utility. Despite numerous designs, PoUW lacks practical relevance and theoretical scrutiny. In this paper, we provide a systematization of knowledge (SoK) on PoUW, focusing on security-economic trade-offs. We build the taxonomy to discuss core principles (difficulty adjustment, verifiability, etc.), architecture, trade-offs, and economic incentives. We examine more than 50 PoUW constructions where we find recurring shortcomings. We introduce a formal economic model of PoUW for miner incentives, solution reusability, and external market value to the security budget. To validate our hypothesis, we employ a Toulmin-based evaluation of claims on the security and energy efficiency of these constructions. Our findings show that PoUW is actually not as useful as expected, since the economic and societal utility do not contribute to the security budget. Finally, we highlight design recommendations for PoUW that integrate verifiable computation, partial incentive allocation, and utility-aware difficulty adjustment.

In this work, we investigate whether the cost of two-party ECDSA signing can be brought within the realm of plain ECDSA signing. We answer the question in the affirmative for the case of communication complexity, by means of a new signing protocol. Our protocol consumes bandwidth linear in the security parameter, and hence the size of an ECDSA signature. Our scheme makes only blackbox use of generic tools---Oblivious Transfer during key generation, and any Pseudorandom Function when signing. While computation complexity is not asymptotically optimal, benchmarks of our protocol confirm that concrete costs are the lowest known for ECDSA signing. Our protocol is therefore the most concretely efficient in the literature on all fronts: bandwidth, computation, and rounds. On a technical level, our protocol is enabled by a novel Pseudorandom Correlation Function (PCF) for the Vector Oblivious Linear Evaluation correlation over a large ring. The PCF relies on one-way functions alone, and may be of independent interest. Our scheme supports standard extensions, such as pre-signing, and including backup servers for key shares in a $(2,n)$ configuration.

The hardness of finding isogenies of degree $d$ between supersingular elliptic curves is a fundamental assumption in isogeny-based cryptography. Let $E_1$ and $E_2$ be supersingular elliptic curves defined over $\mathbb{F}_{p^2}$, and let $d$ be a smooth integer. %removed > p^{1/2} part. At CRYPTO~2024, Benčina et al.\ proposed an algorithm with time complexity $\widetilde{O}(\max\{p^{1/2}, d/p^{5/8}\})$ in the classical setting and $\widetilde{O}(\max\{p^{1/4}, d^{1/2}/p^{1/4}\})$ in the quantum setting. In this work, we first observe that their analysis omits a sub-exponential factor $\exp(O(\log^{3/4} p))$. We then improve their result to $\widetilde{O}(\max\{p^{1/2}, \exp(O(\log^{4/5} p)) \cdot d/p^{2/3}\})$ classically and $\widetilde{O}(\max\{p^{1/4}, \exp(O(\log^{4/5} p)) \cdot d^{1/2}/p^{1/3}\})$ quantumly. Our approach relies on small-root bounds for Coppersmith’s method applied to a four-variable integer equation. To this end, we adapt the explicit asymptotic formulas for small-root bounds introduced by Feng et al.\ (CRYPTO~2025) in the modular setting to the integer setting. As an additional application, we strengthen the attack of Benčina et al.\ on the SIDH signature scheme by Basso et al. (ACNS~2024). We expect that these refined techniques for Coppersmith’s method will be valuable for further post-quantum cryptanalysis.

We present a simple range-proof mechanism for Pedersen commitments that avoids per- transaction heavy ZK verification and pairings. The idea is to commit once to a Merkleized range table of points {(U, aX·G)}X∈{1,...,2n} for a secret a ∈ Zq and a public anchor U = a·B. At transaction time, a prover shows set membership of the leaf (U, ax · G), proves via a Chaum–Pedersen DLEQ that logB U = logC C′ where C′ = a · C and C is the Pedersen commitment, and finally proves (Schnorr) that C′ − (ax·G) lies in the H-direction. These three checks enforce x to be the in-range value indexed by the Merkle leaf while preserving privacy. Verification costs a single Merkle proof plus a DLEQ and a Schnorr discrete-log proof over an elliptic curve group.

Garbled circuits with one-bit-per-gate communication were recently introduced by Liu et al. (BitGC, Eurocrypt 2025), Meyer et al. (Crypto 2025), and Ishai et al. (Crypto 2025). However, these works focus primarily on the theoretical communication complexity, leaving open questions about practical computational efficiency. In this paper, we present a set of optimizations that substantially improve its practical efficiency. First, we eliminate key barriers to enable SIMD support for BitGC, leading to a substantial speedup in its homomorphic operations. Second, we demonstrate that XOR gates can be garbled without any communication, improving both efficiency and simplicity. Finally, we present a computationally efficient garbling scheme that requires zero communication for XOR gates and only 5 bits per AND gate. When applied to an AES-128 circuit, our fastest garbling scheme generates a garbled circuit of just 4 KB in 2 minutes on a single CPU core.

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

Abstract. Multivariate quadratic problem over a finite field, a NP-hard problem, is also considered as one of the hard problems for cryptanalytic-relevant quantum computers. It is the foundation of multivariate quadratic-based cryptography and several post-quantum digital signature schemes initially proposed in 1990s. Patarin’s unbalanced Oil-and-Vinegar (UOV) scheme is the oldest MQ signature algorithm that remain secure against large-scale cryptanalytic-relevant quantum computers. UOV has compact signature size and succinct verification time. However, it suffers from a very large public key size. Subsequently, UOV-based variants have focused on minimizing the size of central map. MAYO, a candidate advanced to NIST’s round 2 additional post-quantum digital signatures, is based off the UOV algorithm with whipped structure to reduce public key size. In this paper, we present a theoretical framework for fault injection-based attack. It targets the construction of valid signatures during the signing phase. This fault-based analysis allows efficient extraction of secret oil vectors from the public signatures, facilitating the complete recovery of the entire secret oil space O. Finally, we show that this analysis is applicable to parameter sets of all three security level of all versions of MAYO.

Linkable Ring Signatures (LRS) allow anonymous signing on behalf of an ad hoc ring, while making any two signatures by the same signer publicly linkable. Traceable Ring Signatures (TRS), introduced by Fujisaki and Suzuki [PKC'07], strengthen linking to tracing: two signatures on different messages additionally reveal the signer's public key. Since cheating almost always means signing two distinct messages, for example two conflicting transactions, traceability turns detection into accountability and makes misbehavior costly. However, TRS remain far less studied and deployed than LRS. We identify two gaps and address both. First, the security notions inherited from [PKC'07], anonymity, linkability, and exculpability, do not capture attacks specific to tracing. For example, they together do not imply unforgeability, a fundamental requirement for all signature-like primitives. We close this gap by introducing extended linkability and extended exculpability, which reflect the security requirements of TRS more faithfully than their standard counterparts. Second, all existing TRS schemes trace in $O(n)$ time for a ring of size $n$, whereas LRS link in $O(1)$. Over a pool of $\ell$ signatures, pairwise tracing therefore costs $O(\ell^2 n)$ against $O(\ell^2)$ for linking. We design a new TRS framework with $O(1)$ tracing for valid signatures. Instantiated from DDH with Bulletproofs [S&P'18], it yields signatures of $(64\log n+544)$ bytes on Curve25519. To our knowledge this is the shortest TRS for $n \ge 12$, and it is on par with state-of-the-art DLog-based LRS schemes. TRS thus gains traceability at essentially no cost over LRS.

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

Function Secret Sharing (FSS) schemes enable sharing efficiently secret functions. Schemes dedicated to point functions, referred to as Distributed Point Functions (DPFs), are the center of FSS literature thanks to their numerous applications including private information retrieval, anonymous communications, and machine learning. While two-party DPFs benefit from schemes with logarithmic key sizes, multi-party DPFs have seen limited advancements: $O(\sqrt{N})$ key sizes (with $N$, the function domain size) and/or exponential factors in the key size. We propose a DDH-based technique reducing the key size of existing multi-party schemes. In particular, we build an honest-majority DPF with $O(\sqrt[3]{N})$ key size. Our benchmark highlights key sizes up to $10\times$ smaller (on realistic problem sizes) than state-of-the-art schemes. Finally, we extend our technique to schemes supporting comparison functions.

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

Homomorphic secret sharing (HSS) is a powerful cryptographic primitive that enables efficient, low-communication secure computation without the use of fully homomorphic encryption. Public-key HSS is a well-known variant that supports inputs from multiple parties, but all parties must agree on a joint public key before any party can encode their inputs, requiring extra rounds of communication in applications. Recently, Couteau et al. (EUROCRYPT 2025) constructed multi-key HSS (MKHSS)—a new primitive which allows parties to encode their inputs under independent keys—under the DCR assumption. MKHSS assumes only a reusable common reference string, without the need for prior interactions between parties or a public-key infrastructure. In this paper, we construct and implement the first concretely-efficient MKHSS scheme under the same assumptions used by Couteau et al. Using an algorithmic insight that reduces the largest modulus in Couteau et al. from $N^4$ to $N^2$, our optimized implementation can homomorphically multiply inputs in 5.0 milliseconds—while an implementation of Couteau et al. requires 224.6 milliseconds—thereby achieving a $45\times$ speedup. A powerful application of MKHSS is to realize attribute-based non-interactive key exchange (ANIKE), which generalizes password-authenticated key exchange (PAKE) to arbitrary attribute policies. ANIKE is currently only known from MKHSS and in this paper we show the first practical instantiation of ANIKE for two concrete predicate types with applications to geolocation-based key exchange and fuzzy PAKE. We use our implementation to evaluate the first concretely-efficient ANIKE schemes for a range of practically useful policies. Using our implementation, two parties can perform a geolocation-based key exchange in under one second and a fuzzy PAKE on an 8-word passphrase in a few seconds for realistic parameters, on a single core, achieving a roughly $30 \times$ speedup over Couteau et al. for both applications.

We present Zyga, a pairing-based zero-knowledge proof system optimized for privacy-preserving DeFi applications. Our main contribution is an enhancement of existing zkSNARK constructions that enables dynamic public input substitution during verification while maintaining privacy of witness components through one-sided encoding. The one-sided encoding aspect favors practical deployment constraints on Solana and Ethereum where G2 scalar multiplications are computationally expensive. Zyga separates private values (blinded through trusted setup) from public values (instantiated on-chain), enabling ap- plications like private trading against current market rates without reproofing. We further introduce two-sided encoding, an extension that removes circuit structure restrictions by adding a private B com- mitment and a rebase mechanism, enabling arbitrary R1CS circuits with proof reuse across changing base values. We provide rigorous security analysis under discrete logarithm and q-Strong Diffie-Hellman assumptions, demonstrating computational soundness, zero-knowledge, and completeness. Performance analysis shows verification requires only 3–4 pairings with constant proof size, making it practical for blockchain deployment where transaction costs are critical.

In this paper, we propose a quantum circuit implementation of AIM2. We apply optimization to reduce the circuit depth and introduce a method to reuse qubits by performing inverse operations in parallel. For all AIM2 variants (AIM2-I, AIM2-III, AIM2-V), we design quantum circuits for $\mathsf{Mer}^{-1}$, the linear layer, $\mathsf{Mer}$, and feed-forward. We confirm that the $\mathsf{Mer}^{-1}$ operation dominates the overall cost. Compared to the previous version of AIM, AIM2 requires significantly more quantum resources since it introduces $\mathsf{Mer}^{-1}$ before the linear layer. Based on the proposed circuits, we estimate the cost of Grover's algorithm for key search and compare it with the NIST estimates for AES. As a result, AIM2-I, AIM2-III, and AIM2-V achieve the post-quantum security levels of Level-1, Level-3, and Level-5, respectively.

We describe several families of efficiently implementable Boolean functions achieving provable trade-offs between resiliency, nonlinearity, and algebraic immunity. In particular, the following statement holds for each of the function families that we propose. Given integers $m_0\geq 0$, $x_0\geq 1$, and $a_0\geq 1$, it is possible to construct an $n$-variable function which has resiliency at least $m_0$, linear bias (which is an equivalent method of expressing nonlinearity) at most $2^{-x_0}$ and algebraic immunity at least $a_0$; further, $n$ is linear in $\max(m_0,x_0,a_0)$, and the function can be implemented using $O(n)$ 2-input gates, which is essentially optimal.

Secure storage of private keys is a challenge. Seed phrases were introduced in 2013 to allow wallet owners to remember a secret without storing it electronically or writing it down. Still, very few people can remember even 12 random words. This paper proposes an alternative recovery option that utilizes lower-than-standard entropy secrets (such as passwords, biometrics, and object extractors). It can be used on its own (in combination with strong key derivation functions) or provide an additional backup option for the existing mnemonics. In this work, we investigate several aspects of secure key derivation: (1) how much entropy different sources can provide; (2) what is the preferred construction of the fuzzy extractor; (3) our key contributions in the selected approach; (4) the main security assumptions and properties of Unforgettable Fuzzy Extractor; (5) economic rationale for parameters (e.g., fuzzy vault size, additional PoW difficulty, secret length, cost of the attack) achieving the optimal solution from both security and time perspectives.

Blind signatures are a versatile cryptographic primitive with many applications, especially in privacy-preserving technologies. Threshold blind signature schemes (TBS) enhance blind signatures with a signing procedure distributed among up to n signers to reduce the risk attached to the compromise of the secret key. So far, TBS constructions over groups rely on strong assumptions, e.g., the algebraic group model (AGM) or interactive assumptions. In this work, we propose two TBS based on the computational Diffie-Hellman assumption (CDH) in the ROM: – The first TBS over pairing-free groups without the AGM. – The first round-optimal TBS over pairing-based groups that does not rely on interactive assumptions. The starting point for both constructions is the pairing-based signature scheme derived from Boneh-Boyen IBE (Eurocrypt’04), and their recent blind signature variants by Katsumata et al. (Asiacrypt’23) and Klooß et al. (Asiacrypt’24) based on the decisional Diffie-Hellman assumption (DDH). We first remove the reliance on DDH in their schemes, then provide careful adaptations to the threshold setting.

In this paper, we provide details on the proofs of the quantum polynomial time algorithm of Biasse and Song (SODA 16) for computing the $S$-unit group of a number field. This algorithm directly implies polynomial time methods to calculate class groups, $S$-class groups, relative class group and unit group, ray class groups, solve the principal ideal problem, solve certain norm equations, and decompose ideal classes in the ideal class group. Additionally, combined with a result of Cramer, Ducas, Peikert and Regev (Eurocrypt 2016), the resolution of the principal ideal problem allows one to find short generators of a principal ideal. Likewise, methods due to Cramer, Ducas and Wesolowski (Eurocrypt 2017) use the resolution of the principal ideal problem and the decomposition of ideal classes to find so-called ``mildly short vectors'' in ideal lattices of cyclotomic fields.

Fuzzy PSI is a variant of PSI, which on input a set of points from the receiver and sender respectively, allows the receiver to learn which of the sender's points lie within a threshold distance $\delta$ under a specific distance metric. Baarsen and Pu (EUROCRYPT'24) first proposed efficient fuzzy PSI protocols for general $L_{p}$ distances (where $p \in [1, \infty]$) in $d$-dimensional space, achieving communication complexity linear in the input size, $\delta$, and $2^d d$. However, they leave open the question of whether the prefix technique of Chakraborti et al. (USENIX Security'23) can further reduce the communication complexity of their fuzzy PSI protocols in both low and high dimensions. In this work, we thoroughly explore using the prefix technique to reduce the complexity of fuzzy PSI. First, we propose fuzzy matching protocols for $L_{\infty}$ and $L_p$ distances, where the communication complexity is improved from $O(\delta d)$ to $O(\log\delta\, d)$ for $L_\infty$, and from $O(\delta^p)$ to $O((\log \delta)^d p)$ for $L_p$ distance. By applying our fuzzy matching protocol in conjunction with spatial hashing, we propose fuzzy PSI protocols for low-dimensional space. For high-dimensional space, we present the first fuzzy PSI protocols achieving communication and computation complexity that scales logarithmically in $\delta$ and linearly in dimension $d$ and input set sizes. We implement our fuzzy PSI protocols and compare them with state-of-the-art protocols. Experimental results demonstrate that our protocols achieve superior performance for large $\delta$: for input size $N=2^8$, $d=5$, and $\delta=256$, our protocol requires $10$--$36\times$ less running time and $3$--$4.5\times$ lower communication than existing protocols.

In anonymous token protocols, clients obtain access tokens by proving eligibility for the usage of a resource and later get access to the resource by redeeming the token. The server verifying eligibility and providing the resource cannot link the token issuance to its redemption. To prevent ineligible clients from accessing resources, it is crucial to prevent the transfer or sale of tokens. Durak et al. (CCS'24) propose binding tokens to valuable insurance secrets, which must be known to redeem the tokens. The value of the insurance secret deters the vendor from transferring the secret to the token buyer, who cannot redeem the token without the secret. However, the authors do not consider scenarios, where the token vendor assists the buyer during token redemption. Their construction, therefore, falls short to guarantee non-transferability when facing a vendor-aided token redemption. We address this gap by introducing the concept of anonymous tokens with betrayability. Our notion ensures that a token buyer, that is able to redeem a bought token, either knows the insurance secret or is able to betray the vendor in a vendor-aided redemption. The betrayal allows the buyer to steal the insurance secret without being detected. This way, we make the support in the token redemption equivalent to a transfer of the insurance secret and, hence, inherit the transfer deterrence of the insurance secret even when considering a vendor-aided token redemption. We formalize our new security notion, present a protocol for anonymous tokens with betrayability, prove its security, and provide an implementation and experimental evaluation.

Finding shortest paths in graphs is one of the fundamental combinatorial optimization problems with numerous applications. Privacy constraints in these applications have lead to an extensive line of research on the so-called privacy-preserving (length of) shortest path problem. A Secure Multi-Party Computation (SMPC) protocol that solves this problem computes the lengths of shortest paths on a secret graph in a distributed fashion while ensuring that the graph remains secret. While many such protocols have been proposed in the past, they only compute the length of the shortest paths and not the paths themselves. In this paper, we address this shortcoming but also propose a novel adaptable protocol design that chooses between different sub-protocols for the building blocks it uses depending on input size, the network delay and bandwidth, and the security model the protocol operates in. Our protocol thus finds the run-time optimal combination of sub-protocols for a given environment. We compare the resulting adaptive protocol to a less flexible baseline protocol in an extensive evaluation using the MP-SPDZ framework, spanning multiple network and security settings. Compared to the baseline protocol, the adaptivity of our optimized path construction leads to speedups from 4% to 32% in the overall time to find the shortest path. Further, we find and fix a small leakage in two prior (length of) shortest path protocols, and report multiple observations that can be used to improve the practical runtime of other SMPC protocols.

We give a formal analysis of the optimized variant of the $\mathsf{gemini}$ polynomial commitment scheme [BCHO22] used by the $\href{https://github.com/AztecProtocol/aztec-packages}{\text{Aztec Network}}$. Our work is motivated by an attack on a previous implementation [GL25].

The rapid advancement of quantum computing threatens the security of widely deployed public-key cryptosystems, creating an urgent need for practical migration to post-quantum cryptographic (PQC) standards. Although the U.S. National Institute of Standards and Technology (NIST) and Korea’s KpqC initiative have recently standardized PQC algorithms, integrating them into Transport Layer Security (TLS)~1.3 remains operationally challenging. Larger certificates, higher handshake costs, and incompatibility with legacy clients make naive deployment impractical in production environments. While hot reload has long been supported in classical TLS deployments (e.g., Nginx, HAProxy), these mechanisms were designed for RSA/ECC contexts with small keys and certificates, and they do not address PQC-specific challenges. This work presents a systematic demonstration of \emph{hot reload and rollback in a PQC-enabled TLS context}, incorporating a policy-driven state machine for staged migration and rollback under realistic constraints such as increased handshake latency and legacy-client compatibility. We propose a bridge-server-based framework that operates at the TLS library level, enabling zero-downtime migration across classical, hybrid, and PQC deployments. Experimental evaluation shows that PQC handshakes incur a $\approx$5.8--6.4$\times$ increase in latency in compute-bound settings relative to ECC baselines, while the relative overhead is significantly smaller in network-bound scenarios, highlighting the importance of deployment context. These findings provide a feasible path toward secure and incremental PQC integration in TLS infrastructures, contributing to broader strategies for achieving crypto-agility under evolving cryptographic standards.

Polynomial multiplication over $\mathbb{F}_2[x]$ is a fundamental building block in code-based and lattice-based cryptography, particularly on lightweight embedded devices where dedicated carry-less multiply instructions are unavailable. This paper presents a high-speed, constant-time implementation of radix-16 polynomial multiplication on the ARM Cortex-M4, combining zero-padding with recursive Karatsuba layers. Building on the radix-16 decomposition proposed by Chen et al. in TCHES’21, we replace the conventional schoolbook inner multiplier with a multi-level Karatsuba scheme. This optimization reduces cycle counts on the ARM Cortex-M4 while preserving constant-time execution. To further optimize efficiency, the design minimizes packing and unpacking overhead by operating at 128-bit granularity and employs a five-stage pipeline—Decomposition, Padding, Multiplication, Unpadding, and Reassembly—implemented entirely with data-independent shifts, XORs, and masks. Experimental results on the Cortex-M4 show that our optimized $ct\_poly32\_mul\_64\_bit$ implementation achieves up to 31\% improvement over the best existing constant-time baseline, demonstrating the efficiency and scalability of recursive Karatsuba for resource-constrained cryptographic applications.

We propose CA-MCPQ, a context-aware post-quantum-secure extension of the Model Context Protocol (MCP). Unlike standard MCP, which leaves authentication, encryption, and authorization optional or implementation-specific, CA-MCPQ elevates them to mandatory protocol-level mechanisms. The design incorporates post-quantum mutual authentication, KEM-derived session keys, and authenticated sequencing to ensure session integrity and prevent replay. Role-based access control is enforced, while token-based authentication is eliminated entirely. AI dynamically infers the required security tier from contextual information and negotiates compatible PQC algorithms; each response returns a reliability score that quantifies alignment with the requested security level. This architecture addresses critical vulnerabilities of MCP—including token misuse, session hijacking, impersonation, and quantum attack—while preserving interoperability. Notably, our evaluation shows that the cryptographic and transport overheads are negligible compared to model computation, confirming that strong post-quantum assurances can be achieved without degrading system performance. Overall, CA-MCPQ provides a practical path toward secure-by-design AI agent ecosystems and lays the groundwork for future extensions such as agent–agent secure coordination.

We present Olingo, a framework for threshold lattice signatures that is the first to offer all desired properties for real-world implementations of quantum-secure threshold signatures: small keys and signatures, low communication and round complexity, non-interactive online signing, distributed key generation (DKG), and identifiable abort. Our starting point is the framework by Gur, Katz, and Silde (PQCrypto 2024). We change the underlying signature scheme to Raccoon (Katsumata et al, Crypto 2024), remove the trapdoor commitments, extend the scheme from two to three rounds, and then apply numerous improvements and optimizations to achieve all the above properties. We provide detailed proofs of security for our new framework and present concrete parameters and benchmarks. At the $128$-bit security level, for up to $1024$ parties and supporting $2^{60}$ signatures, our scheme has $4.4$ KB public keys and $11.3$ KB signatures; while signing requires communication of $852$ KB per party using the LaBRADOR proof system (Beullens and Seiler, Crypto 2023). An optimistic non-interactive version of our scheme requires only $76$ KB communication per party.

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

We present a 4-round statistical non-malleable zero-knowledge (statistical NMZK) argument for NP in the plain model under standard hardness assumptions. Our construction can be based on any collision-resistant hash function and injective one-way function, and it guarantees simulation extractability in the delayed-input, one-many setting. Before this work, 4-round constructions were known for computational NMZK but not for statistical NMZK.

The CKKS fully homomorphic encryption (FHE) scheme enables computations on vectors of approximate complex numbers. A moderate precision of $\approx 20$ bits often suffices but, in many applications, a higher precision is required for functionality and/or security. Indeed, to obtain IND-CPA-D security [Li-Micciancio; Eurocrypt'21], secure threshold-FHE [Asharov et al; Eurocrypt'12] and circuit privacy [Gentry; STOC'09], all known approaches require a precision that supports noise flooding. This may lead to a precision of $\approx 80$ bits, or more. High-precision CKKS is hard to achieve, notably because of bootstrapping. The main difficulty is modulus consumption: every homomorphic multiplication consumes some, out of an overall modulus budget. Unfortunately, in high precision, most known bootstrapping algorithms consume so much modulus that one needs to increase the parameters to increase the budget. The state-of-the-art approach, Meta-BTS [Bae et al; CCS'22], performs moderate-precision bootstrapping several times to enable high-precision bootstrapping, with similar modulus consumption as the base bootstrapping it builds upon. It however damages latency. We introduce a new approach for high-precision CKKS bootstrapping, whose cost is almost independent of the precision (as opposed to Meta-BTS) and whose modulus consumption increases significantly more slowly than with classical bootstrapping algorithms. Our design relies on the EvalRound bootstrapping [Kim et al; Asiacrypt'22], which we improve in the high-precision context by leveraging and improving recent techniques for handling discrete data with CKKS. We obtain for the first time a non-iterative 80-bit precise bootstrapping algorithm which can be run in ring degree $N=2^{16}$, with 494 bits of remaining modulus for computations. In terms of throughput, and for 80-bit precision, our implementation shows an acceleration of 64\% compared to Meta-BTS.

Pseudorandom unitaries (PRUs), one of the key quantum pseudorandom notions, are efficiently computable unitaries that are computationally indistinguishable from Haar random unitaries. While there is evidence to believe that PRUs are weaker than one-way functions, so far its relationship with other quantum cryptographic primitives (that are plausibly weaker than one-way functions) has not been fully established. In this work, we focus on quantum cryptographic primitives with classical communication, referred to as QCCC primitives. Our main result shows that QCCC bit commitments and QCCC key agreement, cannot be constructed from pseudorandom unitaries in a black-box manner. Our core technical contribution is to show (in a variety of settings) the difficulty of distinguishing identical versus independent Haar unitaries by separable channels. Our result strictly improves upon prior works which studied similar problems in the context of learning theory [Anshu, Landau, Liu, STOC 2022] and cryptography [Ananth, Gulati, Lin, TCC 2024].

The quantum Haar random oracle model is an idealized model where every party has access to a single Haar random unitary and its inverse. We construct strong pseudorandom unitaries in the quantum Haar random oracle model. This strictly improves upon prior works who either only prove the existence of pseudorandom unitaries in the inverseless quantum Haar random oracle model [Ananth, Bostanci, Gulati, Lin, EUROCRYPT 2025] or prove the existence of a weaker notion (implied by strong pseudorandom unitaries) in the quantum Haar random oracle model [Hhan, Yamada, 2024]. Our results also present a viable approach for building quantum pseudorandomness from random quantum circuits and analyzing pseudorandom objects in nature.

Is it possible to efficiently convert any arbitrary source with sufficiently high (min-)entropy into nearly uniformly random bits? Information-theoretically, this is achievable using seeded extractors, provided the source is independent of the seed. However, in the absence of any such independence guarantee, no solution is possible for general computationally unbounded sources. Even for efficiently samplable sources, we cannot extract randomness that is statistically close to uniform, but can at best condense the randomness into an output that is only missing logarithmically many bits of entropy compared to the uniform distribution. Dodis, Ristenpart and Vadhan (TCC '12) constructed such seeded condensers for efficiently samplable sources that can depend arbitrarily on the seed assuming near-optimal security of collision-resistant hash functions. In this work, we investigate whether such condensers can be made seedless. We present several new results: -- We construct seedless condensers for all efficiently samplable sources assuming near-optimal security of keyless multi-collision resistant hash functions. We justify this assumption by showing it holds in the auxiliary-input random oracle model. -- We show that such seedless condensers cannot be proven secure via a black-box reduction from any standard game-based assumption, even if we assume optimal exact security. In fact, we give a general black-box separation that applies to a broad class of seedless primitives, with seedless condensers as a special case. -- We consider the class of efficiently samplable distributed sources where two parties jointly sample randomness $x=(x_0,x_1)$, with one party honestly choosing $x_b$ uniformly at random while the other party adversarially chooses $x_{1-b}$ depending on $x_b$. We show how to construct seedless condensers for such sources assuming near-optimal security of game-based assumptions -- either: (1) adaptive one-way functions, or (2) a certain from of (single-input) correlation-intractable hash functions that can be instantiated from key-dependent-message (KDM) secure encryption.

A verifiable delay function (VDF) [Boneh et al., CRYPTO 2018] is a function $f$ that is slow-to-compute, but is quickly verifiable given a short proof. This is formalised using two security requirements: i) sequentiality, which requires that a parallel adversary is unable to compute $f$ faster; and ii) soundness, which requires that an adversary is unable to generate a proof that verifies wrong outputs. A time-lock puzzle (TLP), on the other hand, is a puzzle that can be quickly generated, but is slow-to-solve. The security requirement here is sequentiality, which requires that a parallel adversary is unable to solve puzzles faster. In this paper, we study the relationship between these two timed primitives. Our main result is a construction of ``one-time'' VDF from TLP using indistinguishability obfuscation (iO) and one-way functions (OWFs), where by ``one-time'' we mean that sequentiality of the VDF holds only against parallel adversaries that do not preprocess public parameters. Our VDF satisfies several desirable properties. For instance, we achieve perfectly sound and short proofs of $O(\lambda)$ bits, where $\lambda$ is the security parameter. Moreover, our construction is a trapdoor (one-time) VDF that can be easily extended to achieve interesting extra properties (defined in our paper) such as trapdoor-homomorphic and trapdoor-constrained evaluation. Finally, when combined with the results of Bitansky et al., [ITCS 2016], this yields one-time VDFs from any worst-case non-parallelizing language, iO and OWF. To the best of our knowledge, this is the first such construction that only relies on polynomial security.

Threshold Fully Homomorphic Encryption (FHE) enables arbitrary computation on encrypted data, while distributing the decryption capability across multiple parties. A primary application of interest is low-communication multi-party computation (MPC), which benefits from a fast and secure threshold FHE decryption protocol. Several works have addressed this problem, but all existing solutions rely on "noise flooding" for security. This incurs significant overhead and necessitates large parameters in practice, making it unsuitable for many real-world deployments. Some constructions have somewhat better efficiency, but at the cost of weaker, non-simulation-based security definitions, which limits their usability and composability. In this work, we propose a novel threshold FHE decryption protocol that avoids "noise flooding" altogether, and provides simulation-based security. Rather than masking the underlying ciphertext noise, our technique securely removes it via an efficient MPC rounding procedure. The cost of this MPC is mitigated by an offline/online design that preprocesses special gates for secure comparisons in the offline phase, and has low communication and computation in the online phase. This approach is of independent interest, and should also benefit other MPC protocols (e.g., secure machine learning) that make heavy use of non-linear comparison operations. We prove our protocol secure in the Universal Composability (UC) framework, and it can be generally instantiated for a variety of adversary models (e.g., security-with-abort against a dishonest majority, or guaranteed output delivery with honest majority). Compared to the state of the art, our protocol offers significant gains both in the adversary model (i.e., dishonest vs. honest majority) and practical performance: empirically, our online phase obtains approximately 20,000$\times$ better throughput, and up to a 37$\times$ improvement in latency.

Let $1$ be the all-one vector and $\odot$ denote the component-wise multiplication of two vectors in $\mathbb F_2^n$. We study the vector space $\Gamma_n$ over $\mathbb F_2$ generated by the functions $\gamma_{2k}:\mathbb F_2^n \to \mathbb F_2^n, k\geq 0$, where $$ \gamma_{2k} = S^{2k}\odot(1+S^{2k-1})\odot(1+S^{2k-3})\odot\ldots\odot(1+S) $$ and $S:\mathbb F_2^n\to\mathbb F_2^n$ is the cyclic left shift function. The functions in $\Gamma_n$ are shift-invariant and the well known $\chi$ function used in several cryptographic primitives is contained in $ \Gamma_n$. For even $n$, we show that the permutations from $\Gamma_n$ with respect to composition form an Abelian group, which is isomorphic to the unit group of the residue ring $\mathbb F_2[X]/(X^n+X^{n/2})$. This isomorphism yields an efficient theoretic and algorithmic method for constructing and studying a rich family of shift-invariant permutations on $\mathbb F_2^n$ which are natural generalizations of $\chi$. To demonstrate it, we apply the obtained results to investigate the function $\gamma_0 +\gamma_2+\gamma_4$ on $\mathbb F_2^n$.

Algebraic Immunity (AI) is a fundamental property in the security analysis of stream ciphers and Boolean functions, measuring the resistance of a function against algebraic attacks. In this work, we focus on the computation of AI and, more specifically, on its generalization to restricted algebraic immunity, which considers annihilators constrained to specific subsets of $\mathbb{F}_2^n$. While the computation of AI has been studied using methods based on Reed-Muller codes and iterative rank-based algorithms, these approaches have not been formally adapted to the restricted setting. We address this gap by establishing the theoretical foundations required for the adaptation of these techniques and providing explicit algorithms for computing restricted algebraic immunity. To assess the efficiency of our algorithms, we conduct practical experiments comparing the computational cost of the Reed-Muller and iterative approaches in terms of time and memory. As a case study, we analyze the algebraic immunity restricted to the slices of $\mathbb{F}_2^n$, i.e. the sets of binary vectors of fixed Hamming weight, denoted $\mathsf{AI}_k$. The slices are of particular interest in areas of cryptography, such as side-channel analysis and stream cipher design, where the input weight may be partially predictable. We further investigate restricted algebraic immunity for Weightwise (Almost) Perfectly Balanced (W(A)PB) functions, which have been extensively studied since $2017$. Our results include an empirical analysis of $\mathsf{AI}_k$ distributions for WPB functions with $4$, $8$, and $16$ variables, as well as an evaluation of $\mathsf{AI}_k$ for various known function families.

This article develops a unified framework for analyzing and enhancing a family of multivariate signature schemes based on UOV. We conduct a comparative study of three recent UOV-like schemes—QR-UOV, MAYO, and SNOVA—and identify a common design principle: employing tensor product constructions to enlarge the dimension of the oil subspace. Building on this perspective, we propose a new multivariate signature scheme called TSUOV that synthesizes these insights to provide improved key and signature sizes without compromising security.

This paper presents an ARMv8/NEON–oriented, constant-time implementation of NCC-Sign and a careful head-to-head evaluation against a clean KPQClean baseline on Apple~M2. We design lane-local SIMD kernels (e.g., a 4-lane Montgomery multiply--reduce, centered modular reduction, fused stage-0 butterfly, and streamlined radix-2/3 pipelines) that minimize cross-lane shuffles and keep memory access streaming. Using a reproducible harness with PMU-based cycle counting and identical toolchains for baseline and optimized builds, we observe consistent end-to-end gains across all parameter sets: geometric-mean speedups of \textbf{1.22$\times$} for key generation, \textbf{1.58$\times$} for signing, and \textbf{1.50$\times$} for verification, yielding an overall \textbf{1.42$\times$} improvement over NCC-Sign-1/3/5. The largest benefits appear in NTT-intensive signing/verification, and absolute savings scale with parameter size.

In 2023, LeGrow, Ti, and Zobernig proposed a cryptographic hash function (we refer to it as the LTZ hash function in this paper) based on a certain (2,2)-isogeny graph between supersingular non-superspecial abelian surfaces over $\mathbb{F}_{p^4}$. The authors estimated that the time and space complexities required to find a collision in the LTZ hash function are both given by $\widetilde{O}(p^3)$. In this paper, we first propose a mathematical conjecture on the number of vertices defined over the smaller field $\mathbb{F}_{p^2}$ in the isogeny graphs used in the LTZ hash function. Based on this conjecture, we then construct a collision-finding algorithm for the LTZ hash function, which preserves the time complexity $\widetilde{O}(p^3)$, while reducing the required memory to $O(\log(p)^2)$. We implemented this algorithm in Rust, and successfully found a collision for parameters claimed to provide 35-37 bits of security, within 26.2MB of memory usage on average in 20.2 hours.

Cloud computing has matured into the default substrate for data processing, yet confidentiality demands of- ten force a hard trade-off between the utility of outsourced computation and the privacy of sensitive inputs. Homomorphic encryption (HE)[1] promises to dissolve that trade-off by enabling computation directly on ciphertexts, returning encrypted results that only the data owner can decrypt. Despite remarkable progress in fully homomorphic encryption (FHE) and leveled variants suitable for bounded-depth circuits, deploying HE at cloud scale remains challenging. The cost of ciphertext arithmetic is orders of magnitude higher than plaintext compute; noise growth and rescaling impose algorithmic discipline; vectorization and rotation keys complicate program layout; and the lack of verifiability in bare HE obliges trust in a correct-but-curious cloud[?]. This paper develops a system perspective on how to apply modern HE in cloud environments without reducing it to a boutique feature. We introduce a reference architecture that marries approximate-arithmetic HE for analytics with exact- arithmetic HE for integrity-critical operations, composes HE with succinct proofs for verifiability, and integrates a cost model into the scheduler so that elastically provisioned serverless workers can meet latency objectives under price constraints. The design begins with a compiler that lowers dataflow graphs to operator sequences parameterized by multiplicative depth L and rotation sets; it then chooses schemes and parameters—CKKS for floating-point style analytics and signal processing, BFV/BGV for integer operations and counters, TFHE-style bootstrapping for comparisons—that minimize the total time-to-result under explicit error and security budgets. A cryptographic key service supports threshold issuance and rotation-key escrow without learning plaintexts, while a storage layer packs columns into ciphertext SIMD lanes to amortize cost across tenants. For verifiability, we attach homomorphic message authentication tags to intermediate ciphertexts and wrap end-to-end executions in succinct non-interactive proofs specialized to the bilinear equations that certify correct key switching, rescaling, and boot- strapping. Analytically, we characterize latency by a linear model in the counts of core homomorphic primitives and show how to saturate GPUs or vector units with batched number-theoretic transforms to bend throughput toward practical regimes. Under realistic traces of analytic queries and encrypted inference, the architecture achieves sub-second P95 for circuits of depth six to eight with one or two bootstraps, while sustaining 128-bit security under RLWE. By treating HE not as an exotic afterthought but as a first-class cloud programming and scheduling primitive, the proposed approach demonstrates a path to confidential-by- default services in which the cloud never sees data in the clear yet remains efficient, elastic, and auditable.

Mutual Transport Layer Security (mTLS) under- pins authenticated, confidential communication across modern service meshes, but its deployment stance in machine-learning platforms is typically static—fixed cipher suites, certificate life- times, and re-authentication schedules chosen for worst-case threats rather than observed risk. Large Language Model (LLM) serving pipelines exacerbate this rigidity: traffic is bursty, topolo- gies reconfigure dynamically under autoscaling, and sensitive artifacts such as prompts, training features, and evaluation data traverse heterogeneous substrates. In this paper we argue that mTLS for LLM systems[1] should be governed by adaptive control rather than static policy. We formalize a feedback loop that ingests multi-modal telemetry—connection error codes, handshake latencies, anomaly scores from request semantics, workload attestation freshness, and service-level objective (SLO) drift—and outputs fine-grained adjustments to transport posture: client-certificate renewal cadence, certificate path length and key type selection, session resumption eligibility, early data gat- ing, proof-of-possession challenges, and revocation propagation thresholds. The controller targets two coupled objectives: maintain cryptographic assurances (mutual authentication, forward secrecy, and replay resistance) while bounding the cost of security on tail latency and throughput during high-load inference.

We study whether Verifiable Delay Functions (VDFs) can be constructed in the (plain) Random Oracle Model (ROM) without any computational assumptions. A first partial answer to this question is due to Mahmoody, Smith, and Wu [ICALP 2020] where they rule out perfectly unique VDFs in the ROM. Building on this result, Guan, Riazanov, and Yuan [CRYPTO 2025] prove that VDFs with computational uniqueness and public-coin setup are impossible in the ROM. These works leave open the possibility of constructing computationally unique VDFs with private-coin setup in the ROM. We resolve this problem and additionally rule out computationally-unique VDFs with computationally expensive private-coin setup in the ROM.

Traditional single-proposer blockchains suffer from miner extractable value (MEV), where validators exploit their serial monopoly on transaction inclusion and ordering to extract rents from users. While there have been many developments at the application layer to reduce the impact of MEV, these approaches largely require auctions as a subcomponent. Running auctions efficiently on chain requires two key properties of the underlying consensus protocol: selective-censorship resistance and hiding. These properties guarantee that an adversary can neither selectively delay transactions nor see their contents before they are confirmed. We propose a multiple concurrent proposer (MCP) protocol offering exactly these properties.

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

The proposed $\mathsf{SL\text{-}DNSSEC}$ protocol (AsiaCCS'25) uses a quantum-safe KEM and a MAC to perform signature-less $\mathsf{(SL)}$ DNSSEC validations in a single UDP query / response style. In this paper, we give a formal analysis of $\mathsf{SL\text{-}DNSSEC}$ in the reductionist model.

Random classical linear codes are widely believed to be hard to decode. While slightly sub-exponential time algorithms exist when the coding rate vanishes sufficiently rapidly, all known algorithms at constant rate require exponential time. By contrast, the complexity of decoding a random quantum stabilizer code has remained an open question for quite some time. This work closes the gap in our understanding of the algorithmic hardness of decoding random quantum versus random classical codes. We prove that decoding a random stabilizer code with even a single logical qubit is at least as hard as decoding a random classical code at constant rate—the maximally hard regime. This result suggests that the easiest random quantum decoding problem is at least as hard as the hardest random classical decoding problem, and shows that any sub-exponential algorithm decoding a typical stabilizer code, at any rate, would immediately imply a breakthrough in cryptography. More generally, we also characterize many other complexity-theoretic properties of stabilizer codes. While classical decoding admits a random self-reduction, we prove significant barriers for the existence of random self-reductions in the quantum case. This result follows from new bounds on Clifford entropies and Pauli mixing times, which may be of independent interest. As a complementary result, we demonstrate various other self-reductions which are in fact achievable, such as between search and decision. We also demonstrate several ways in which quantum phenomena, such as quantum degeneracy, force several reasonable definitions of stabilizer decoding—all of which are classically identical—to have distinct or non-trivially equivalent complexity.

We present DualMatrix, a zkSNARK solution for large-scale matrix multiplication. Classical zkSNARK protocols typically underperform in data analytic contexts, hampered by the large size of datasets and the superlinear nature of matrix multiplication. DualMatrix excels in its scalability. The prover time of DualMatrix scales linearly with respect to the number of non-zero elements in the input matrices. For $n \times n$ matrix multiplication with $N$ non-zero elements across three input matrices, DualMatrix employs a structured reference string (SRS) of size $O(n)$, and achieves RAM usage of $O(N+n)$, transcript size of $O(\log n)$, prover time of $O(N+n)$, and verifier time of $O(\log n)$. The prover time, notably at $O(N+n)$ and surpassing all existing protocols, includes $O(N+n)$ field multiplications and $O(n)$ exponentiations and pairings within bilinear groups. These efficiencies make DualMatrix effective for linear algebra on large matrices common in real-world applications. We evaluated DualMatrix with $2^{15} \times 2^{15}$ input matrices each containing $1G$ non-zero integers, which necessitate $32T$ integer multiplications in naive matrix multiplication. DualMatrix recorded prover and verifier times of $150.84$s and $0.56$s, respectively. When applied to $1M \times 1M$ sparse matrices each containing $1G$ non-zero integers, it demonstrated prover and verifier times of $1,384.45$s and $0.67$s. Our approach outperforms current zkSNARK solutions by successfully handling the large matrix multiplication task in experiment. We extend matrix operations from field matrices to group matrices, formalizing group matrix algebra. This mathematical advancement brings notable symmetries beneficial for high-dimensional elliptic curve cryptography. By leveraging the bilinear properties of our group matrix algebra in the context of the two-tier commitment scheme, DualMatrix achieves efficiency gains over previous matrix multiplication arguments. To accomplish this, we extend and enhance Bulletproofs to construct an inner product argument featuring a transparent setup and logarithmic verifier time.

This paper introduces the first multilinear polynomial commitment scheme (PCS) over Galois rings achieving $\bigO{\log^2 n}$ verification cost. It achieves $\bigO{n\log n}$ committing time and $\bigO{n}$ evaluation opening prover time. This PCS can be used to construct zero-knowledge proofs for arithmetic circuits over Galois rings, facilitating verifiable computation in applications requiring proofs of polynomial ring operations (e.g., verifiable fully homomorphic encryption). First we construct random foldable linear codes over Galois rings with sufficient code distance and present a distance preservation theorem over Galois rings. Second we extend the $\textsf{Basefold}$ commitment (Zeilberger et al., Crypto 2024) to multilinear polynomials over Galois rings. Our approach reduces proof size and verifier time from $\bigO{\sqrt{n}}$ to $\bigO{\log^2 n}$ compared to Wei et al., PKC 2025. Furthermore, we give a batched multipoint openning protocol for evaluation phase that collapses the proof size and verifier time of $N$ polynomials at $M$ points from $\bigO{NM \log^2 n}$ to $\bigO{\log^2 n}$, prover time from $\bigO{NMn}$ to $\bigO{n}$, further enhancing efficiency.

Distributed Point Functions (DPFs) enable sharing secret point functions across multiple parties, supporting privacy-preserving technologies such as Private Information Retrieval, and anonymous communications. While 2-party PRG-based schemes with logarithmic key sizes have been known for a decade, extending these solutions to multi-party settings has proven challenging. In particular, PRG-based multi-party DPFs have historically struggled with practicality due to key sizes growing exponentially with the number of parties and the field size. Our work addresses this efficiency bottleneck by optimizing the PRG-based multi-party DPF scheme of Boyle et al. (EUROCRYPT'15). By leveraging the honest-majority assumption, we eliminate the exponential factor present in this scheme. Our construction is the first PRG-based multi-party DPF scheme with practical key sizes, and provides key up to $3\times$ smaller than the best known multi-party DPF. This work demonstrates that with careful optimization, PRG-based multi-party DPFs can achieve practical performances, and even obtain top performances.

We initiate the study of untelegraphable encryption (UTE), founded on the no-telegraphing principle, which allows an encryptor to encrypt a message such that a binary string representation of the ciphertext cannot be decrypted by a user with the secret key, a task that is classically impossible. This is a natural relaxation of unclonable encryption (UE), inspired by the recent work of Nehoran and Zhandry (ITCS 2024), who showed a computational separation between the no-cloning and no-telegraphing principles. In this work, we define and construct UTE information-theoretically in the plain model. Building off this, we give several applications of UTE and study the interplay of UTE with UE and well-studied tasks in quantum state learning, yielding the following contributions: - A construction of collusion-resistant UTE from standard secret-key encryption (SKE). We additionally show that hyper-efficient shadow tomography (HEST) is impossible assuming collusion-resistant UTE exists. By considering a relaxation of collusion-resistant UTE, we are able to show the impossibility of HEST assuming only pseudorandom state generators (which may not imply one-way functions). This almost unconditionally answers an open inquiry of Aaronson (STOC 2018). - A construction of UTE from a quasi-polynomially secure one-shot message authentication code (OSMAC) in the classical oracle model, such that there is an explicit attack that breaks UE security for an unbounded polynomial number of decryptors. - A construction of everlasting secure collusion-resistant UTE, where the decryptor adversary can run in unbounded time, in the quantum random oracle model (QROM), and formal evidence that a construction in the plain model is a challenging task. We additionally show that HEST with unbounded post-processing time (which we call weakly-efficient shadow tomography) is impossible assuming everlasting secure collusion-resistant UTE exists. - A construction of secret sharing for all polynomial-size policies that is resilient to joint and unbounded classical leakage from collusion-resistant UTE and classical secret sharing for all policies. - A construction (and definition) of collusion-resistant untelegraphable secret-key functional encryption (UTSKFE) from single-decryptor functional encryption and plain secret-key functional encryption, and a construction of collusion-resistant untelegraphable public-key functional encryption from UTSKFE, plain SKE, and plain public-key functional encryption.

Keccak, the hash function at the core of the Ethereum ecosystem, is computationally expensive to reason about in SNARK circuits, creating a critical bottleneck in the ability of the ZK ecosystem to reason about blockchain state. The recent state-of-the-art in proving Keccak permutations relies on proof systems that can perform lookup arguments, which—while exhibiting better performance than directly proving the hash operations in circuit—still typically require tens of thousands of constraints to prove a single keccak-f permutation. This paper introduces a new method, termed keccacheck, which builds upon sum-check with influence from GKR to create circuits that can batch-verify Keccak permutations with fewer than 4000 constraints per instance. Keccacheck achieves this by exploiting the logarithmic scaling of recursive verification of the sum-check protocol, reducing the computational cost of verifying large enough batches to be only slightly higher than evaluating the multilinear extension of the input and output states. Its performance becomes competitive for a batch containing 16 permutations and offers more than a 10x cost reduction for batches of 512 or more permutations. This approach enables new levels of efficiency for the ZK ecosystem, providing the performant storage proofs that are essential to light clients, cross-chain bridges, privacy-focused protocols, and roll-ups.

NIST recently selected Kyber as a standard for key encapsulation and decapsulation. As such, servers will soon need dedicated hardware for these encapsulation protocols. The computationally critical operation of Kyber is its Number Theoretic Transform, which is commonly accelerated by dedicated hardware such as FPGAs. This work presents an extremely high-throughput design for the Kyber NTT. By utilizing the LUT-based modular multiplication technique used by us in CHES 2025, its area delay product is generally between one and two orders of magnitude better than similar designs in literature. For instance, where Yaman et al. with 16 Processing Elements requires 9500 LUTs and 16 DSPs to perform an NTT in 69 clock cycles, our design requires 67210 LUTs and no DSPs to perform an NTT every clock cycle.

A threshold signature allows one to delegate its signing rights to $n$ parties, such that any subset of size $t$ can sign a message on their behalf. In this work, we show how to construct threshold signatures for any $t$ and $n$ from one way functions, thus establishing the latter as a necessary and sufficient computational assumption. Our protocol makes non-black box use of one-way functions, and can be generalized to other access structures, such as monotone policies.

Quadratic functional encryption (QFE for short) is a cryptographic primitive which can output the value of a quadratic function between two vectors, without leaking other information on the plaintext vectors. Since the first breakthrough of Baltico et al. (Crypto 2017), there are already many constructions for QFE from bilinear groups. However, constructing more efficient QFE schemes and proving their security has always been a challenging task. While generic bilinear group model (GBGM for short) can be used to construct highly efficient QFE schemes and proving their security, obtaining a security proof under GBGM is difficult and may contain undiscovered mistakes. In this paper, we solve this problem by presenting new techniques which finally lead to an automated proof tool for QFE schemes, and can also be used to find potential attacks. Our automated proof tool shows that the RPB+19 scheme (Riffel et al, NIPS'19) which is the most efficient QFE scheme in the literature and already used in several works, is in fact insecure, and also gives an attack for the scheme. Finally, we present two new QFE schemes, each shares same efficiency with the RPB+19 scheme from one aspect, and prove their security using our automated proof tool. Our new schemes are more efficient than all existing QFE schemes other than the RPB+19 scheme, which means that they are most efficient among all existing ``secure'' QFE schemes.

The vast majority of work on the efficiency of lattice-based cryptography, including fully homomorphic encryption~(FHE), has relied on *cyclotomic* number fields and rings. This is because cyclotomics offer a wide variety of benefits, including good geometrical properties, fast ring arithmetic, and rich homomorphic operations like vectorized (SIMD) operations on "packed" plaintexts, automorphisms, and ring-switching. However, selecting a suitable cyclotomic that has the desired number and type of plaintext "slots," while also balancing security and efficiency, is a highly constrained problem that often lacks an ideal solution, resulting in wasted SIMD capacity and lost efficiency. This work provides a suite of tools for instantiating ring-based lattice cryptography to work over *subfields* of cyclotomics, which provide more flexibility and better-fitting parameters for applications. A particular focus is on realizing FHE with *optimal plaintext packing* and homomorphic SIMD parallelism for *any* plaintext characteristic, along with efficient *packed bootstrapping* that fully exploits this parallelism. Toward this end, this (two-part) work makes the following main technical contributions, all of which are catalyzed by Galois theory: -- For sampling and decoding errors in encryption and decryption (respectively), we construct geometrically short, structured bases for the number rings of arbitrary subfields of prime-power cyclotomics (and hence their composites as well). -- For fast ring arithmetic, we define and establish analogous structural properties for Chinese Remainder Theorem (CRT) bases in *abelian* number rings, and give specialized fast transforms that map between CRT bases and any similarly structured bases. -- For packed bootstrapping and homomorphic linear algebra, we give a general framework for *homomorphic evaluation of structured linear transforms* in abelian number rings, and show that CRT transforms can be evaluated using relatively few homomorphic operations.

Solving a long-standing open problem, Faonio, Fiore, and Russo proved that the widely used Plonk zk-SNARK is simulation extractable. However, their proof assumes both the random oracle model (ROM) and the algebraic group model. We prove that the same holds in the ROM under falsifiable assumptions. We combine the template of Faust et al., who proved that simulation extractability follows from knowledge soundness, (weak) unique response, and trapdoorless zero-knowledge, with the recent result of Lipmaa, Parisella, and Siim (Crypto 2025), who proved that Plonk has knowledge soundness in the ROM under falsifiable assumptions. For this, we prove that Plonk satisfies new variants of the weak unique response and trapdoorless zero-knowledge properties. We prove that several commonly used gadgets, like the linearization trick, are not trapdoorless zero-knowledge when considered as independent commit-and-prove zk-SNARKs.

WireGuard is a VPN based on the Noise protocol, known for its high performance, small code base, and unique security features. Recently, Hülsing et al. (IEEE S&P'21) presented post-quantum (PQ) WireGuard, replacing the Diffie-Hellman (DH) key exchange underlying the Noise protocol with key-encapsulation mechanisms (KEMs). Since WireGuard requires the handshake message to fit in one UDP packet of size roughly 1200 B, they combined Classic McEliece and a modified variant of Saber. However, as Classic McEliece public keys are notoriously large, this comes at the cost of severely increasing the server's memory requirement. This hinders deployment, especially in environments with constraints on memory (allocation), such as a kernel-level implementations. In this work, we revisit PQ WireGuard and improve it on three fronts: design, (computational) security, and efficiency. As KEMs are semantically, but not syntactically, the same as DH key exchange, there are many (in hindsight) ad-hoc design choices being made, further amplified by the recent finding on the binding issues with PQ KEMs (Cremers et al., CCS'24). We redesign PQ WireGuard addressing these issues, and prove it secure in a new computational model by fixing and capturing new security features that were not modeled by Hülsing et al. We further propose 'reinforced KEM' (RKEM) as a natural building block for key exchange protocols, enabling a PQ WireGuard construction where the server no longer needs to store Classical McEliece keys, reducing public key memory by 190 to 390×. In essence, we construct a RKEM named 'Rebar' to compress two ML-KEM-like ciphertexts which may be of an independent interest.

We suggest post quantum secure protocol based on pseudorandom walk on infinite q-regular forest D(q) where q = 2^m, m > 1. Correspondents share positive integer n, pseudorandom tuple from (Fq) ^n and two pseudorandom input words in the alphabet F_q of length O(1). They use the group of cubic multivariate transformations of the vector space of points of D(q) induced by walks on the forest of even length as the platform for the implementation of modified Twisted Diffie-Hellman protocol of Noncommutative Cryptography based on the complexity of the Conjugacy Power Problem. The output of the protocol is a vector from (F_q)^n. In fact the action of the group on the partition set of the bipartite homomorphic image D(n, q) of the forest is used. Correspondents elaborate the collision vector in time O(n^2) in the case when the length of input words is O(1) and the size of private integer parameters is O(n). If length of the input words is also O(n) then the complexity of protocol will be O(n^3). We suggest also the obfuscation of the scheme with hidden graph of the 1complexity O(n^5) for which the output of the algorithm is a symbolic cubic transformation F of (Fq)^n. It can be used symbiotically with the symmetric encryption via the adding to the ciphertext from (F_q)^n the vector F(b_1, b_2, . . . , b_n) where the tuple (b_1, b_2, . . . , b_n) of pseudorandom nature is known publicly.

When neural networks are trained to classify a dataset, one finds a set of weights from which the network produces a label for each data point. We study the algorithmic complexity of finding a collision in a single-layer neural net, where a collision is defined as two distinct sets of weights that assign the same labels to all data. For binary perceptrons with oscillating activation functions, we establish the emergence of an overlap gap property in the space of collisions. This is a topological property believed to be a barrier to the performance of efficient algorithms. The hardness is supported by numerical experiments using approximate message passing algorithms, for which the algorithms stop working well below the value predicted by our analysis. Neural networks provide a new category of candidate collision resistant functions, which for some parameter setting depart from constructions based on lattices. Beyond relevance to cryptography, our work uncovers new forms of computational hardness emerging in large neural networks which may be of independent interest.

Bandwidth remains a major bottleneck in post-quantum cryptography, particularly for authenticated key exchange (AKE) protocols. In this work, we present DAKE, a bandwidth-efficient AKE framework built from double-KEM constructions. DAKE comes in two main versions achieving, respectively, weak and full perfect forward secrecy, as well as explicit authentication. It further admits two variants: a unilateral version, and another where a signature scheme replaces a KEM. They are proven secure in the standard model under eCKw and eCK-PFS, two strong variants of the extended Canetti–Krawczyk framework. DAKE employs a double-KEM, a primitive that encapsulates a single key under two public keys simultaneously. Such constructions can achieve smaller encapsulation sizes than two independent KEM encapsulations, offering a significant bandwidth advantage. To facilitate the design of double-KEMs compatible with DAKE, we introduce a chosen-key Fujisaki–Okamoto (CK-FO) transform proven in the QROM, which upgrades IND-CPA double-PKEs to IND-CCA double-KEMs while ensuring the one-sided chosen-key security required by DAKE. As a concrete instantiation, we propose Maul, a compact double-KEM derived from ML-KEM under the Hint-MLWE assumption. Maul reuses ciphertext components to cut encapsulation size by up to 42% compared to two parallel ML-KEMs. When instantiated with Maul, DAKE achieves overall communication reductions of about 16% (mutual authentication) and 21% (unilateral), outperforming both the double-KEM AKE of Xue et al. (ASIACRYPT 2018) and standard ML-KEM-based AKEs.

The transition to post-quantum cryptography (PQC) is accelerating due to the potential of quantum computing to compromise classical public-key cryptosystems. While standardized schemes such as CRYSTALS-Kyber, CRYSTALS-Dilithium, and SPHINCS+ offer strong theoretical security, practical deployments remain susceptible to physical-layer vulnerabilities, notably side-channel attacks (SCAs). SCAs exploit unintentional leakages in hardware and software implementations—such as power traces, electromagnetic emissions, and timing variations—to recover secret keys without altering the target system. These attacks are non-invasive, cost-effective, and applicable across diverse platforms, making them a critical threat vector for PQC in embedded and resource-constrained environments. This survey provides a structured, in-depth review of SCAs targeting PQC implementations, encompassing both classical methods—such as Simple Power Analysis, Differential Power Analysis, Correlation Power Analysis, Template Attacks, and Mutual Information Analysis—and emerging machine learning (ML)-driven approaches. Special attention is given to deep learning models, including CNNs, RNNs, and MLPs, which have demonstrated superior performance in profiling attacks by automatically learning leakage patterns from high-dimensional trace data, even in the presence of countermeasures like masking and desynchronization. We categorize and compare recent attack strategies, analyze their effectiveness against various PQC schemes, and examine the limitations of existing countermeasures. Finally, we identify open research challenges and outline hybrid defense strategies that integrate classical protections with adaptive, ML-aware mitigation techniques. This comprehensive synthesis aims to bridge the gap between PQC algorithm design and secure, implementation-level deployment in the quantum era.

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

Group signatures enable users to sign on behalf of a group while preserving anonymity, with accountability provided by a designated opener. The first rigorous model for dynamic groups (Bellare, Shi, Zhang, CT--RSA '05) captured anonymity, non-frameability, and traceability, later extended with trace-soundness (Sakai et al., PKC '12) and non-claimability (introduced as ``opening-soundness'' by Bootle et al., ACNS '16 & JoC '20). In practice, issuer and opener are often distinct entities, often implemented by different organizations and/or hardware modules. We therefore formalize and prove the consequences of a model that enforces their complete separation, allows key reuse across groups, treats issuer and opener as stateless, and makes both joining and opening non-interactive. This separation makes it necessary to reformulate traceability against a corrupt issuer and to introduce three additional unforgeability notions-key-unforgeability, certificate-unforgeability, and opening-unforgeability-for the case of a corrupt opener. Following this line of reasoning, we also develop strengthened formulations of trace-soundness and non-claimability. We prove that in this model the eight resulting properties are fully distinct: even the conjunction of any seven does not imply the eighth. This yields the first comprehensive map of group signature security in a stateless, reusable-key, and non-interactive framework, and formally demonstrates the impact of complete issuer--opener separation.

This paper introduces new, stringent security notions for elliptic curves. We define two new classes of strong elliptic curves, which offer resilience against a broader range of known attacks, including those leveraging the twist. To construct curves satisfying these exceptional criteria, we developed a highly scalable, parallel framework based on the complex multiplication method. Our approach efficiently navigates the vast parameter space defined by safe primes and fundamental discriminants. The core of our method is the efficient scanning algorithm that postpones expensive curve construction until after orders are confirmed to meet our security definitions, enabling significant search efficiency. As a concrete demonstration of our definitions and techniques, we conducted a large-scale computational experiment. This resulted in the first known construction of $91$ very strong 256-bit curves with extreme twist orders (i.e., where the curve order is a safe prime and the twist order is prime) and cofactors $u=1$ along with $4$ such 512-bit curves meeting the extreme twist order criteria. Among these, one 512-bit curve has both its order (a safe prime) and its twist order being prime, while the other three have a small cofactor ($u=7$) but their twist orders are primes. All curves are defined over finite fields whose orders are safe primes. These results not only prove the existence of these cryptographically superior curves but also provide a viable path for their systematic generation, shifting the paradigm from constructing curves faster to constructing curves that are fundamentally stronger.

Emails are one of the main forms of digital communication. They were designed to provide many guarantees that have surprisingly not yet been formalized in cryptography. Yet many of the guarantees emails were designed to provide have not been formalized in cryptography. This paper models an important feature of email applications: the plausible deniability of including Bcc recipients. Concretely, - we define a basic (theoretical) email application capturing these guarantees in Constructive Cryptography (Maurer and Renner, ICS '11) - we introduce Email Encryption: a new cryptographic primitive that is tailor-made to construct our email application - we define game-based notions for Email Encryption schemes, proving that their combination is sufficient to construct our simple email application and - we give a generic (proof-of-concept) construction of an Email Encryption scheme that provides all these guarantees. Our work identifies and formalizes missing theoretical foundations for the security of emails providing the first step towards practical solutions.

We revisit the BUFF transform, which was proposed by Cremers et al. (S&P'21) as a means to achieve security properties beyond standard unforgeability for digital signature schemes. One of these properties, non-resignability (NR), has recently drawn some attention due to a strong impossibility result for the original definition of the property. Recent follow-up work then considered a variant (sNR) of the original definition, and showed that it is satisfied by the BUFF transform when the underlying hash function is modeled as a random oracle - while the original impossibility result still applies for the plain model. This raises the natural question of whether the BUFF transform satisfies sNR in a more fine-grained use of the random oracle model, when we consider a real-life iterative-hash-function design (such as Merkle-Damgaard or Sponge) and instead idealize the round function. Our discoveries in this direction are two-fold: First, contrary to what one might expect, we show that there is a simple attack on the non-resignability property sNR of the BUFF-transform when instantiated with an iterative hash function. The attack relies on leaking an intermediate result of the hash computation to the adversary who is challenged to "resign" the message. This negative result once more shows the subtlety in the non-resignability property. Second, on the positive side, we propose a small modification to the original BUFF transform, which we call Sandwich BUFF (for reasons to become clear), and prove the non-resignability property sNR of Sandwich BUFF both for Merkle-Damgaard-based hash functions in the random oracle model, and for Sponge-based hash functions in the random permutation model.

TLS 1.3 is at the heart of secure modern internet communications. With the rise of quantum attacks, post-quantum TLS 1.3, built on post-quantum key encapsulation mechanisms (KEMs), has naturally become a major research focus. At Eurocrypt 2022, Huguenin-Dumittan and Vaudenay demonstrated that KEMs secure against chosen-plaintext attacks (CPA) are sufficient to construct a secure TLS 1.3 handshake in the random oracle model (ROM), but their security reduction incurs an $\mathcal{O}(q^6)$ loss, where $q$ is the number of random oracle queries. Improving their security bounds was left as an open problem. To address this problem, Zhou et al. took the first step at Asiacrypt 2024, improving the loss factor to $\mathcal{O}(q^2)$ in the ROM and $\mathcal{O}(q^4)$ in the quantum ROM (QROM) for OW-CPA secure KEMs, and to $\mathcal{O}(q)$ (ROM) and $\mathcal{O}(q^2)$ (QROM) for IND-CPA secure KEMs. In this work, we advance the state-of-the-art by providing tighter security reductions for TLS 1.3 handshake based on CPA-secure KEMs. We introduce a new security notion, \textit{IND-1CCA-1MAC}, and show that with a slight ciphertext expansion, the reduction losses can be significantly improved to $\mathcal{O}(q)$ (ROM) and $\mathcal{O}(q^2)$ (QROM) for OW-CPA secure KEMs, and to only $\mathcal{O}(1)$ in both models for IND-CPA secure KEMs. Moreover, we prove that without additional modifications such as ciphertext expansion, the loss of $\mathcal{O}(q)$ (ROM) and $\mathcal{O}(q^2)$ (QROM) is unavoidable. Finally, we analyze the security of TLS 1.3 from CPA-secure KEMs in the hybrid key exchange setting, and provide experimental evidence that ciphertext expansion is a practical trade-off for mitigating reduction losses.

Designing practically secure masked circuits remains a central problem in the field of cryptographic implementation. While most masking schemes have been proven secure in the classical probing model, this model fails to capture more advanced side-channel attacks such as horizontal attacks. In recent years, the community has shifted toward the more realistic random probing model, which offers stronger guarantees. Yet, balancing strong security with practical efficiency continues to be a significant challenge. In this work, we introduce new tools and constructions that significantly improve the design and analysis of random probing secure circuits. First, we formalize new security notions that combine the benefits of cardinal and general Random Probing Composability (RPC), two recently introduced notions enabling more flexible and efficient composition of secure gadgets. We then show how uniformly random permutations can be applied to transform any cardinal or general RPC gadget into a so-called uniformly cardinal RPC gadget, thereby enhancing security at low cost. Using these techniques, we propose the first non-linear multiplication gadget, inspired by the recursive construction from CHES 2016, that achieves concrete cardinal RPC security. We provide a detailed comparison with state-of-the-art multiplication gadgets in terms of both random probing advantage and implementation complexity. Building upon this gadget, we design a tighter random probing compiler that strategically uses permutations to improve security bounds while preserving efficiency. Finally, we apply our compiler to the AES and demonstrate improved performance and security compared to existing methods.

Payment channels are a cornerstone of a scalable blockchain infrastructure that enables transacting parties to lock assets on the blockchain and perform rapid off-chain updates with minimal latency and overhead. These protocols dramatically reduce on-chain interaction and improve throughput, with blockchain consensus only invoked in the event of disputes or final closure. While widely adopted in single-chain settings—such as in the Lightning Network for Bitcoin—existing constructions have several limitations, in particular they suffer from at least one of the following limitations: 1) No cross-chain. They do not enable fast trading of assets that reside on multiple isolated blockchains. 2) Non-optimal round complexity. The off-chain round complexity is not optimal (i.e., parties require more than two rounds to update the channel). 3) No bitcoin compatibility. They require a more advanced scripting language that prevents cross-chain interaction between chains that only have a simple (Bitcoin-like) scripting language. In this work, we introduce a novel payment channel protocol that breaks through all the above limitations. Our construction supports bidirectional, multiasset, and off-chain interaction across an arbitrary set of blockchains, where each update of the channel requires the parties to send only one message each. Our protocol is fully compatible with Bitcoin and can be deployed on chains with only minimal scripting capabilities, making it broadly applicable to real-world blockchain networks. Crucially, our design ensures atomic settlement across blockchains without relying on trusted intermediaries. We formally prove the security of our protocol together with a novel definition of the cross-chain payment channel that we introduce. Finally, we empirically validate our protocol, showing the minimal costs that our payment channel incurs in the setting where two parties make multiple exchanges of assets that reside on three different blockchains.

In this work, we present two fault attacks against MPCitH-based signature schemes: we present a key recovery attack and a signature forgery attack, both of which only need a single successful fault injection to succeed. We analyze all five MPCitH-based schemes which are currently analyzed in round 2 of NIST's additional signature standardization process: Mirath, MQOM, PERK, RYDE, and SDitH. Our analysis shows that all five schemes are vulnerable to at least one of the attacks. We validate the practicality of our attacks using the ChipWhisperer setup and discuss countermeasures to prevent the attacks.

Using stock market data as a source of public randomness has deep historical roots and has seen renewed interest with the development of verifiable delay functions. Prior work has estimated that asset prices contain ample entropy to prevent prediction by a passive observer, but has not considered an active attacker making trades in the marketplace. VDFs can make manipulation more difficult, forcing an attacker to precompute beacon results for some number of potential outcomes and then force the market into one of them by price manipulation. To date, there has been no analysis of the difficulty of such an attack. We propose a framework for evaluating this attack using standard finance models for price movement and the price impact of trades. We then estimate from empirical data that, even under generous assumptions, for a basket of large-cap stocks (the S&P 100) an active adversary would require huge capital reserves (on the order of billions of US dollars) and incur major losses to slippage (millions of US dollars).

We give novel lifting theorems for security games in the quantum random oracle model (QROM) in Noisy Intermediate-Scale Quantum (NISQ) settings such as the hybrid query model, the noisy oracle and the bounded-depth models. We provide, for the first time, a hybrid lifting theorem for hybrid algorithms that can perform both quantum and classical queries, as well as a lifting theorem for quantum algorithms with access to noisy oracles or bounded quantum depth. At the core of our results lies a novel measure-and-reprogram framework, called hybrid coherent measure-and-reprogramming, tailored specifically for hybrid algorithms. Equipped with the lifting theorem, we are able to prove directly NISQ security and complexity results by calculating a single combinatorial quantity, relying solely on classical reasoning. As applications, we derive the first direct product theorems in the average case, in the hybrid setting - i.e., an enabling tool to determine the hybrid hardness of solving multi-instance security games. This allows us to derive in a straightforward manner the NISQ hardness of various security games, such as (i) the non-uniform hardness of salted games, (ii) the hardness of specific cryptographic tasks such as the multiple instance version of one-wayness and collision-resistance, and (iii) uniform or non-uniform hardness of many other games.

We present the first pairing-based ciphertext-policy attribute-based encryption (CP-ABE) scheme for the class of degree $3$ polynomials with compact parameters: the public key, ciphertext and secret keys comprise $O(n)$ group elements, where $n$ is input length for the function. As an immediate corollary, we obtain a pairing-based broadcast encryption scheme for $N$ users with $O(N^{1/3})$-sized parameters, breaking the long-standing $\sqrt{N}$ barrier for pairing-based broadcast encryption. All of our constructions achieve adaptive security against unbounded collusions, and rely on the (bilateral) $k$-Lin assumption in prime-order bilinear groups.

Blockchains preserve public data indefinitely, creating tension between verifiability today and secrecy decades hence. In particular, pairing-based SNARKs (e.g., Groth16, PLONK) rely on discrete-log assumptions that are structurally vulnerable to Shor-type quantum attacks, motivating hash-based alternatives. This work investigates whether a fully on-chain pipeline that verifies both a ZK-STARK and a post-quantum signature can operate within Solana L1's compute and memory constraints. Our prototype adapts Winterfell 0.12 with a dedicated SHA-256 hashv syscall path to reduce hashing overhead, suppresses inlining in FRI hotspots to respect SBF (Solana BPF) stack limits, and uses a custom bump allocator synchronized with requested heap frames. Artifacts are uploaded in ≤900 byte chunks under a rolling hash chain and finalized in two steps: (i) SLH-DSA (SPHINCS+) signature verification over a length-delimited transcript, and (ii) STARK verification bound to SHA256(cipher) via public inputs. The result is an L1 verifier that is CPI-friendly, reproducible from a public repository, and engineered for predictable cost. On devnet, across n=100 runs, we measure mean finalize_sig cost of 5.01×10^5 CU (median 4.999×10^5) and mean verify_stark cost of 1.10×10^6 CU (median 1.11×10^6), with maxima below 1.19×10^6 CU; all runs fit within Solana's 1.4×10^6 CU transaction budget. At representative sizes, the derived intensities are ≈63.8 CU/Sig-byte (7,856 B) and ≈248.9 CU/Proof-byte (4,437 B), and verification scales approximately linearly with proof bytes under a fixed FRI policy. We systematize DoS and fee controls (fixed-offset appends, rolling-hash checks), justify the binding of public inputs to the ciphertext, and outline engineering levers (single-call hashing, stack discipline, phase separation) that make full L1 STARK+PQC verification practical at ≈128-bit settings.

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