International Association
for Cryptologic Research

Polynomial multiplication is fundamental in lattice-based cryptography. While the Number Theoretic Transform (NTT) enables fast multiplication, it imposes constraints on the modulus of the coefficient field. Hafiz et al.\ (2025) addressed this limitation by analyzing the incomplete NTT, which combines a truncated NTT with conventional multiplication methods.

In this work, we revisit Toom-4 multiplication in the context of incomplete NTT. Although Toom-4 is asymptotically faster than Karatsuba, its precise cost has not been expressed in a form compatible with the incomplete NTT framework.

We present a concrete Toom-4 implementation and derive explicit operation counts that separate additions/subtractions and multiplications over the coefficient field. Our analysis based on addition chains yields a simple cost model for incomplete NTT.

Using this model, we analyze hybrid strategies combining Toom-4, Karatsuba, and incomplete NTT. We identify parameter ranges where Toom-4 is advantageous and validate the predicted behavior experimentally.

Du et al. (Security and Communication Networks, 2022) proposed a public-key authenticated searchable encryption scheme that employs Bloom filters and blockchain. In their scheme, Bloom filters are used to search encrypted keywords, while blockchain is used to ensure the integrity of search results that guarantees the search result is correct. In this paper, we demonstrate that Du et al.'s scheme leaks keyword information from ciphertexts. Our analysis focuses on the fact that the Bloom filter is uniquely determined by the keyword to be encrypted and is directly embedded in each ciphertext. We show that the proposed attack succeeds with the probability that no false positives occur in the Bloom filter, and we evaluate the false-positive probability to confirm that the attack achieves a sufficiently high success rate. Furthermore, we examine Du et al.'s security model and their assumed usage scenarios, and we discuss the validity of our attack under those conditions. We also consider a simple modification intended to prevent our attack and demonstrate that our attack, with a slight adaptation, remains effective against the modified scheme. In addition, we show that even when the search results differ, previously generated ciphertexts can still pass verification, indicating that the integrity verification mechanism based on blockchain is insufficient.

Unbiased and unpredictable randomness is a cornerstone of Web3 security, underpinning everything from consensus protocols to DeFi logic. Although Distributed Verifiable Random Functions (DVRFs) eliminate central points of failure, current designs often have to compromise performance. Most existing protocols are hindered by one of three limitations: proofs that scale linearly with the number of participants, high computational cost of bilinear pairings, or latency introduced by mandatory interactive steps during generation. In this work, we present Icy-DVRF, a protocol that improves DVRFwCP by employing a preprocessing scheme similar to FROST to reduce the number of interaction rounds among participants, by lowering the additional communication cost from $O(n^2 t)$ to $O(t)$ while maintaining constant-size proofs. The downside of our construction is that, relative to DDH-DVRF and GLOW-DVRF, this approach incurs an additional off-chain communication round due to the threshold structure of our non-interactive zero-knowledge proof. This architecture ensures that verification costs remain low, regardless of the set of participants. We evaluate Icy-DVRF against established standards and demonstrate that our protocol achieves a substantial efficiency gain over pairing-based alternatives. While theoretical estimates suggest verification costs of approximately one quarter of those of standard designs, our empirical benchmarks on the Sepolia testnet, utilizing the EIP-2537: Precompile for BLS12-381 curve operations, confirm that Icy-DVRF requires only 88,803 gas for full execution. This represents a significant 43.02\% reduction in total gas consumption compared to existing pairing-based constructions, saving 67,035 gas per on-chain verification.

We present Frobenius-UOV, a multivariate public-key signature scheme in the Unbalanced Oil and Vinegar (UOV) family. The scheme replaces generic quadratic polynomials with a structured subclass based on Frobenius-type quadratic forms, yielding a compressed public-key representation while retaining the efficient UOV signing procedure. We describe the key-generation, signing, and verification algorithms, and we detail the derivation of the public system from a compact secret description. We discuss security in the standard multivariate setting, including direct algebraic attacks and key-recovery approaches, and we formalize the underlying computational problems induced by the proposed structure. Finally, we report implementation results quantifying the costs of key generation, signing, and verification, as well as the resulting public-key and signature sizes.

Poseidon2 and Neptune use sparse S-box activation in internal partial rounds to reduce arithmetization cost. This structure makes linear subspace trails relevant to algebraic attacks. If the initial state is restricted to a suitable linear subspace, then subsequent internal states may remain in prescribed linear subspaces for a number of rounds. The corresponding partial rounds therefore do not increase the degree of the resulting polynomial system. Existing analyses use this property to estimate the complexity of reduced round preimage attacks. It is therefore important to understand how long such linear subspace trails can persist.

We revisit infinite and finite linear subspace trails in Poseidon-like designs. First, we study the invariant subspace conditions that give rise to infinitely long trails. We relate these conditions to the characteristic polynomials of the Cauchy MDS matrices used in these permutations, and we discuss qualitatively why they are unlikely over fields of large characteristic. Second, we analyze finite linear trails for internal partial rounds in a state of width $t$, where each round activates $s$ S-box coordinates. Under the rank growth condition stated in this paper, when no such invariant subspace exists, a finite trail has length at most $\lceil t/s\rceil-1$. For Poseidon2 and Neptune, $s=1$, this gives at most $t-1$ consecutive linearized internal partial rounds. Considering preimage attacks in sponge mode with rate $r$, capacity $c$, and digest size $d$, the available extra constraint budget is $Ec=r-\min\{c,d\}$. Together, the finite trail bound and this constraint budget determine how many internal partial rounds can be linearized in the corresponding attack model.

Multiscalar multiplication (MSM) is a core operation in modern cryptographic systems, commonly used in various applications such as Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge (ZK-SNARKs) and Homomorphic Encryption. In elliptic curve–based ZK-SNARK constructions, MSM accounts for up to 80–90\% of the total proof generation time, making its optimization critical to improving overall protocol performance. Despite significant progress in accelerating MSM through algorithmic techniques such as Pippenger’s method, existing implementations remain vulnerable to timing attacks due to irregular scalar representations and conditional operations on zero digits.\\

In this paper, we revisit the original Pippenger’s MSM algorithm, proposing novel modifications that achieve resistance to timing attacks while at the same time increasing its performance by almost 25\%. Our main contribution is a new scalar recoding algorithm that transforms conventional $q$-ary representations containing zero digits into equivalent non-zero representations. This ensures that all scalar digits are processed uniformly, eliminating timing-based side-channel leaks. Building on this recoding technique, we introduce a secure variant of Pippenger’s bucket method, that avoids zero digits. Finally, we demonstrate that employing an endomorphism-based splitting yields shorter digit expansions and further efficiency gains. To the best of our knowledge, this is the first MSM algorithm explicitly designed to mitigate timing attacks within the Pippenger bucket method framework.

Digital identity systems are currently build around the globe, aiming to enable secure, usable, but also privacy-preserving user authentication. Concretely, the EUDI Wallet developed in Europe requires to ensure selective attribute disclosure and unlinkable authentication. This essentially mandates the use of anonymous credentials, that have been developed for this exact purpose over the last 20 years. However, they are not integrated in the current solutions as they lack an essential feature: device binding. That is, binding credentials stored on the users' phones to a secure hardware element therein, in order to prevent credential cloning or sharing. Device binding is typically done through encoding a device public key into the user's credential and requiring a fresh signature under the corresponding and hardware-protected secret key - the proof-of-possession (PoP) - when presenting the credential. While academic solutions exist that realize efficient device binding for anonymous credentials, they are not compatible with the secure hardware currently available in consumer phones. The main challenge lies in the underlying curves: all efficient anonymous credentials, (and their native device binding protocols) require the use of pairing-friendly curves, whereas existing phones are essentially restricted to ECDSA signatures and classic P256 curves.

In this work, we show how to bridge these two systems, enabling device-binding for pairing-based credentials on legacy phones, i.e., relying solely on standard ECDSA signatures for the PoP. We present three different constructions with different trade-offs in efficiency and in protocol complexity. Our most efficient solution generates unlinkable bridging proofs of size ~1.5KB in less than ~500ms by relying on a (very simple) arithmetic circuit, whereas the most conservative approach (without circuits) takes as well ~500ms and comes with proof size of ~175KB. All our solutions share a common blueprint, and we express them in the reductions of knowledge framework (Crypto 2023) to reflect this is in our protocols' design. This framework allows to modularly construct complex zero-knowledge proofs in an elegant and intuitive manner, greatly facilitating the security analysis and the implementation. This framework has previously been mainly used in a theoretical context, and our work demonstrates that it is a powerful tool to design, analyze and implement complex real-world systems.

We study pseudorandomness arising from quartic Dirichlet characters and obtain results that connect analytic and cryptographic perspectives. From an analytic perspective, and following the framework of Mauduit and Sárközy, we define a Boolean function $\psi_\pi$ from the quartic character $\chi_\pi$ modulo a Gaussian prime $\pi$ and analyze sequence $E_{p-1}=(\psi_\pi(1),\ldots,\psi_\pi(p-1))$ for $p=\pi\bar\pi \equiv 1 \bmod{4}$. Using classical character-sum bounds (Pólya-Vinogradov and refinements of Mauduit-Sárközy and Oon), we show that $E_{p-1}$ satisfies $W(E_{p-1}) =O(\sqrt{p}\log p)$ and $C_{\mu}(E_{p-1}) \leq 2^{\frac{\mu}{2}+1} \mu \sqrt{p}\log p,$ which imply strong pseudorandomness for small $\mu$. From the cryptographic side, we resolve an open question posed by Damgård by proving that quartic characters yield the secure pseudorandom generators and weak pseudorandom functions (wPRFs). Adapting similar techniques of Corrigan-Gibbs and Wu, we have shown that distinguishing quartic wPRF implies solving quadratic residuosity, via a chain of polynomial-time reductions. Our results show that under the Quadratic Residuosity Assumption, the quartic character also yields cryptographically secure wPRFs whose one-wayness was assumed in the construction of $\mathsf{Quartapus}$ signature scheme by Brier et al. and the post-quantum secure signature scheme $\mathsf{PorcRoast}_{4}$ by Beullens et al. that are more efficient and secure than legacy schemes based on the Legendre character.

To address the expanding attack surface caused by increasing digitization and interconnection, operators of Industrial Automation and Control Systems (IACS) adopt security measures already established in information technology, such as Public Key Infrastructure (PKI), to Operational Technology (OT). However, operating a PKI proves to be challenging in complex and heterogeneous IACS landscapes. Hence, operators might rely on external PKI service providers, resulting in new trust dependencies and a loss of direct control over critical security components.

In the WebPKI, Certificate Transparency (CT) is leveraged to monitor the certificate issuance of publicly trusted certificate authorities. Since CT's original WebPKI-centric design and trust assumptions do not align with the isolated and constrained nature of IACS environments, we investigate the adaptation of CT to a private IACS-specific PKI infrastructure operated by a service provider.

We propose amendments to CT processes and roles, an IACS operator-controlled CT infrastructure, and a layered approach to align with ISA/IEC 62443. Despite the lack of CT support by crypto libraries intended for OT devices, we demonstrate the feasibility of our approach by a proof-of-concept implementation.

Byzantine fault-tolerant (BFT) protocol from delegated committee is an approach in improving the performance and scalability of blockchains. Notable industrial examples include Delegated Proof-of-Stake (DPoS) by Tron, Polkadot, and Solana, and Proof-of-Staked-Authority (PoSA) by Binance. In these protocols, a subset of nodes is first selected to form a committee, then the committee members reach an agreement and disseminate the results to all nodes. Although these approaches allow the committee members to be rotated periodically, the security of the system is built upon a strong assumption that no committee can have more than certain fraction of faulty nodes (e.g., one-third in a partially synchronous network).

In this paper, we provide a revamped two-stage design to model BFT from delegated committee without making the strong assumption. Namely, the only assumption is that in a partially synchronous network, the entire system does not have more than one-third faulty nodes. We propose rBFT, a practical BFT protocol that has a fast path where only committee members participate and a slow path where all nodes in the system are involved. We show that, not surprisingly, the fast path is extremely fast, and under reasonable assumptions such as alive-but-corrupt nodes and rational nodes, only fast path can be triggered. Meanwhile, even under conventional Byzantine failures where the slow path is triggered, our protocol is still practical enough.

Integral attacks pose a significant threat to block cipher security, yet providing guarantees against such attacks for a target block cipher is difficult. At ASIACRYPT 2021, Hebborn, Lambin, Leander, and Todo proposed the integral resistance property, which offers strong security guarantees for certain SPN and AND-RX block ciphers, assuming independent round keys. However, limitations remain: they proved a security bound for 13-round Present, while the longest known integral distinguisher covers only 9 rounds. Further, their method cannot tackle complex Feistel structures such as Twine and Lblock. A major challenge in their method is the difficulty of finding key monomials that lead to odd-number monomial trails. We observe that in the first and last parts of the target cipher, many interfering monomials exist that always produce interfering trails, which is a critical reason that makes it difficult to find odd-number monomial trails. Fortunately, we find that these interfering monomials are avoidable by a careful selection of the key monomials. Using this insight, we successfully prove the security of 11-round Present, improving the previous result by 2 rounds, and provide a partial analysis for 10-round Present. We also extend their integral-resistance property to general-Feistel-network (GFN) ciphers Twine and Lblock by proposing an equivalent key transformation method. Through acceleration strategies for identifying key monomials, we confirm, for the first time, that 20-round Twine (out of 36 rounds) and Lblock (out of 32 rounds) are resistant to integral distinguishers. We believe our observations and strategies provide gains to Hebborn et al.’s security guarantees for block ciphers.

Sleepy consensus allows parties to join and leave execution arbitrarily, which is a fundamental requirement for large-scale distributed systems. Classic longest-chain protocols, such as Bitcoin and its variants, achieve consensus under this model but suffer from inherent long latency. In contrast, recent protocols that build upon the classic view-based BFT paradigm can achieve constant expected latency and short best-case latency under optimal resilience, but they often incur high communication cost. We observe that the high communication overhead stems from the time-shifted quorums, a technique that makes quorum certificates transferable under dynamic participation. However, the technique relies on extensive message forwarding to reconcile parties' inconsistent local views, and thus incurs a cubic communication cost unavoidably.

In this work, we tackle the problem by proposing a novel way to transfer certificates. Building on this, we construct a Byzantine Agreement (BA) protocol secure against the state-of-the-art growing adversary model. Our BA protocol achieves optimal resilience, constant expected round complexity, and an expected communication complexity of $O(nNL+nN\kappa+nN\log N)$, where $n$ is the maximum number of awake parties throughout the execution, $N$ is the total number of eligible parties, $L$ is the input length, and $\kappa$ is the security parameter. We also present an efficient recovery mechanism for our BA, incurring only $O(N\kappa+nL)$ bits per recovering party. Then we extend our BA to an Atomic Broadcast (ABC) protocol that achieves optimal resilience, constant expected latency, and an expected amortized communication complexity of $O(nNL+nN\kappa+nN\log N)$ per input value. The recovery mechanism for our ABC incurs $O(N\kappa+n\ell L+n\ell \kappa)$ bits per recovering party, where $\ell$ is the number of views that the party has slept for. Last but not least, we establish communication lower bounds of $\Omega(N^2L)$ for sleepy BA and ABC. The result shows that our BA and ABC are communication-optimal when $L$ is sufficiently large (i.e., when $L=\Omega(\kappa+\log N)$), and highlights a fundamental limitation of communication efficiency in the sleepy model.

Organisations are upgrading their cryptographic infrastructure to become quantum‑safe before large‑scale quantum computers materialise. Post‑quantum cryptography (PQC) standards now exist for key‑exchange and digital signatures, but the urgent question for adopters is how to operationalise PQC in complex environments with confidence. In banking, Transport Layer Security (TLS), for example, protects data‑in‑transit across public‑facing channels and internal services, and is terminated at many heterogeneous endpoints (web servers, API gateways, load balancers, reverse proxies), each a potential quantum‑vulnerable component and migration target.

We argue that the bottleneck is operational rather than algorithmic: hybrid key exchanges such as X25519‑ML‑KEM‑768 are already available in mainstream libraries, but security teams lack precise visibility into TLS configurations and repeatable methods for enabling PQC‑compatible settings across a heterogeneous estate. This paper presents a configuration‑parsing methodology that automatically extracts and normalises TLS cryptographic posture across dominant enterprise web‑server stacks, producing a unified, provenance‑traced cryptographic inventory as a foundation for migration and compliance. We demonstrate the approach on 8,443 real‑world Nginx configurations from public repositories and in a proof‑of‑concept deployment at a financial institution, where ML‑KEM‑512 and X25519‑ML‑KEM‑768 are onboarded at TLS termination points (web server and API gateway) securing an internal application, with zero application‑layer changes and manageable performance overhead.

Proof of Stake (PoS) blockchain systems require weighted threshold signatures where participants’ voting powers reflect their stakes. As stakes change dynamically through deposits and withdrawals, efficient weight and threshold adjustments are essential for maintaining system security and availability without downtime. However, existing approaches face critical limitations: (1) virtualization-based schemes require $O(w)$ operations (signatures) per participant with weight w; (2) dynamic threshold / paricipants schemes do not support weighted participants; (3) schemes with both properties require trusted dealers or $O(n^2)$ re-setup, causing temporary unavailability. This paper introduces Active Weighted Signature (AWS), enabling dynamic adjustments without trusted dealers or re-setup. We propose Generalized Lagrange Interpolation (GLI), encoding weights as polynomial derivatives rather than virtualized participants, and instantiate AWS through ADAPT by applying GLI to the Schnorr-based threshold signature FROST. Our implementation shows that ADAPT achieves comparable efficiency to FROST for key generation, while weight and threshold adjustments complete in 4.1-22.3% of re-setup time. For uneven weight distributions, ADAPT achieves sub-linear scaling: 49× weight difference requires only 3.29× computation versus 49× in virtualization.

Threshold fully homomorphic encryption (ThFHE) enables decryption by collecting decryption shares from any T-out-of-N parties. A major drawback of previous ThFHE schemes is that they require a super-polynomial modulus (or are subject to other limitations), resulting in long ciphertexts, keys, and decryption shares. Passel`egue and Stehl´e (Asiacrypt 2024) proposed a ThFHE scheme in which a semi-trusted server rounds the input ciphertexts to produce polynomially short ciphertexts and sends them to the parties, thereby making the rest of the decryption process efficient. Although the input ciphertexts are still super-polynomially large, the communication cost of sending them from the parties to the server can be reduced to polynomial size via the transciphering technique; as a result, an entirely low-communication ThFHE is achieved. However, if even a single party colludes with the server (contrary to the assumption), the secret key can be efficiently recovered. Such a risky scenario would be unsuitable for practical deployment.

In this paper, we tackle this issue. We propose two serverless ThFHE schemes with polynomially short decryption shares. The core idea is to let the parties directly round the decryption shares, rather than rely on the semi-trusted server to round the ciphertexts. We can also achieve low-communication ThFHE by reducing the communication required to send input ciphertexts to the parties to polynomial size via transciphering. Our first scheme, based on binary coefficient linear secret sharing ({0,1}-LSS), strictly improves upon Boneh et al. (CRYPTO 2018), achieving short decryption shares without any trade-offs. Our second scheme, based on Shamir secret sharing, adapts the technique of Okada and Takagi (Asiacrypt 2025) to eliminate the $O(N^{4.3})$ overhead in share size of our first scheme, further reducing communication costs.

Recently, Gentry and Lee (GL) proposed a fully homomorphic encryption (FHE) scheme optimized for matrix arithmetic. In this paper, we propose an efficient bootstrapping technique for the GL scheme. Our core idea leverages the linearity of the slot--coefficient transformations, namely CtS and StC: we formulate these operations as ciphertext--plaintext matrix multiplications, which are natively supported by the GL scheme. As a result, the proposed method reduces the number of key-switching operations per step to a small constant. To enable this, we first generalize the GL scheme to matrices of non-power-of-two dimensions by introducing a generalized definition of the trace over commutative rings and proving that it commutes with decryption. Our bootstrapping adopts the CKKS paradigm: ModRaise, CtS, EvalMod and StC. Typically, CtS/StC and EvalMod dominate runtime and depth, respectively; our optimization shifts the bottleneck to EvalMod for both. A proof-of-concept implementation shows that linear transformations account for 20.1% of the total bootstrapping time, compared to 54.9-71.7% in prior CKKS bootstrapping, and that, despite lacking low-level optimizations, our amortized CtS runtime is still about 3 times faster than the well-optimized library (Lattigo).

We introduce YsPIR, a single-server private information retrieval (PIR) protocol that improves upon the state-of-the-art KsPIR protocol by Luo, Liu, and Wang (CCS 2024) in server response time and offline communication. YsPIR is built on a new first-dimension folding technique, which reduces online computation time and decreases the public-key material required in the offline phase.

Our approach has three main advantages. First, it enables the most resource-intensive computations to be preprocessed offline, thereby reducing online response time. Second, its offline communication is independent of the database size and remains small. Third, it maintains low communication cost even under high-throughput settings.

We conduct comprehensive experiments to evaluate the concrete performance of YsPIR. The results show that YsPIR achieves approximately 1.64x higher online throughput and reduces offline communication by about 3.09x compared with KsPIR.

Falcon is a lattice-based digital signature scheme offering excellent performance and key sizes, and it has been selected for standardization by the National Institute of Standards and Technology (NIST) as part of their post-quantum standardization project. However, the use of floating-point and/or fixed-point arithmetic in Falcon presents unique challenges. One such challenge is the lack of reproducibility, which can arise due to the inexact representation of fractional numbers. Traditionally, implementations are validated for correctness using Known Answer Tests (KATs), but this approach requires exact reproducibility. We propose a novel alternate procedure for validating the correctness of Falcon’s key generation. Our procedure never rejects correct implementations of Falcon that vary due to the numerical instability of floating and fixed-point arithmetic. It is still strict enough to guarantee that differences in generated keys due to these variations will not create security problems, although like all black-box testing methods, it does not rule out security problems due to other implementation characteristics, such as side channels. Combined with black-box conformance testing on signing and verification, this provides a path for validating the correctness of Falcon implementations on defined platforms. We further study Falcon’s keys by defining and computing perfect keys that are generated using infinite precision. Last, we estimate the total number of valid keys that could be generated from a single seed. Our work is based on extensive experiments for which the code is available.

The study of digital signatures with tight reductions has attracted considerable attention over the past two decades, as such schemes inherit essentially the same quantitative hardness as the underlying computational problem. In the context of lattice-based cryptography, the GPV approach (Gentry, Peikert, and Vaikuntanathan, STOC ’08) admits a simple tight reduction from the SIS problem, but relies on preimage sampling via trapdoors, which often leads to complex and brittle implementations. By contrast, tight proofs for trapdoor-free constructions, following the Fiat–Shamir paradigm, necessarily rely on decisional assumptions, most notably the decisional LWE assumption. From the perspective of concrete security, however, reliance on a search assumption is preferable, as known search-to-decision reductions for LWE provide only weak quantitative guarantees.

This paper presents the first efficient lattice-based signature scheme with a tight reduction to a search assumption (namely, the hardness of the search LWE problem) that does not require any trapdoor in the scheme itself (but merely uses, instead, a trapdoor in the proof). Our construction follows the Fiat-Shamir paradigm and can be viewed as a lattice analogue of Chevallier–Mames signatures (CRYPTO ’05). Establishing security in the lattice setting, however, requires overcoming significant technical obstacles: in particular, our proof develops several new techniques to cope with the inherently weak soundness guarantees of lattice-based interactive proofs.

It is getting widely recognized that quantum computers pose a fundamental threat to blockchain security. The transaction signature transition to Post-quantum cryptography (PQC) is therefore an urgent challenge. However, it remains unclear how much quantum computing power would be sufficient to compromise blockchain security and, consequently, by when the transition should be completed. To address these questions theoretically, we first formalize the signature transition process and the quantum adversary based on the well-known Bitcoin backbone protocol framework. We then establish a threshold for the chain's tolerable quantum adversary capability. Specifically, we prove that a security property migration liveness holds with overwhelming probability if and only if $$ \Delta_{\mathrm{eff}} \;\geq\; \left\lceil \frac{4}{(1 - \epsilon)f} \right\rceil, $$ where $\Delta_{\mathrm{eff}}$ is the number of rounds the quantum adversary needs to produce a forged transaction after the broadcast of a migration transaction, $f$ is the honest mining success probability, and $\epsilon$ is the concentration quality of the underlying random variables. We further generalize the analysis to derive a relationship between the transition process and the tolerable quantum adversary capability, providing a theoretical basis for designing secure signature transition plans.