What a lovely hat

Soft Analytical Side-Channel Attacks (SASCA) combine leakage-derived priors from multiple intermediate variables with their functional dependencies through belief propagation (BP).However, when applying SASCA to large-scale cryptographic computations where algorithms are abstracted into extensive factor graphs with large candidate sets per variable node, the memory and computational complexity of SASCA become prohibitive. A natural first choice for large-domain variables is to fragment them...

Blind rotation is the dominant computational bottleneck in bootstrapping for bitwise FHE schemes such as TFHE. Existing constructions typically evaluate $O(n)$ sequential external products for an LWE secret of dimension $n$, incurring substantial latency and a large number of NTT/iNTT operations. In this work, we present a new framework for NTRU-based bootstrapping that reduces the sequential complexity of blind rotation for sparse binary LWE secrets. Inspired by Jain et al. (CRYPTO 2026),...

We present $\textsf{Sluice}$, a read-write streaming Groth16 prover that reduces $\textit{prove-phase}$ random-access working memory from $\mathcal{O}(N)$ to $\mathcal{O}(\log N)$ once the CRS, QAP, and witness are materialized as private streams. It preserves the standard Groth16 interface: a proof of 3 group elements, 3-pairing verification, and unchanged verifier contracts. Our key technical contribution is $\textit{Split-Butterfly-Merge}$ ($\mathsf{SBM}$), an NTT algorithm in the...

Copy-protection is one of the main applications of quantum information in cryptography. In copy-protection, we encode a functionality in a reusable quantum state so that it cannot be split into two states (called freeloader adversaries) that remain simultaneously useful. Despite a long line of research, previous works have only been able to show security with respect to independently sampled challenges in the plain-model. However, arguably a more natural security notion considers the two...

Ring signatures provide signer anonymity for ad hoc sets of public keys. Generic Abe-Ohkubo-Suzuki (AOS) transforms are well understood for plain Fiat--Shamir and hash-and-sign signatures, but not for their rejection-sampling variants: Fiat--Shamir with aborts (FSwA) and hash-and-sign with retry (HSwR). We formalize AOS ring transforms for FSwA and HSwR and analyze their security in the quantum random-oracle model. For unforgeability, we reduce security under adaptive ring-signing queries to...

The main barrier to practical fully homomorphic encryption remains the latency and cost of bootstrapping, the ciphertext refresh step that enables unbounded computation. We design new methods that reduce both the latency and the circuit depth of bootstrapping in the FHEW/TFHE framework, which represents the state-of-the-art for lightweight bootstrapping and for computing deep and unstructured Boolean functions over encrypted data. Our first contribution leverages LWE with a sparse...

This paper studies the post-quantum multi-key security of Galois/Counter Mode (GCM) in the Quantum Ideal Cipher Model (QICM). GCM is one of the most widely deployed AEAD schemes. In practice, widely deployed cryptosystems are often instantiated under many independent keys, making the multi-key setting practically relevant. A trivial extension of a single-key security bound to the multi-key setting incurs a security loss proportional to the number of keys. In particular, in the...

The main message of this paper is that several seemingly different circular-style primitives are existentially equivalent. In particular, somewhat surprisingly, we show that hinting PRGs (Koppula and Waters, CRYPTO 2019) are equivalent to secret-key encryption (SKE) schemes satisfying key-dependent-message (KDM) security. As a conceptual centerpiece, we introduce key-dependent-shift (KDS) security for weak pseudorandom functions (PRFs), and show that they serve as a convenient hub connecting...

In this work, we revisit multi-round public-coin proof systems by enabling the use of their simulators and extractors within other cryptographic protocols. Although research on multi-round public-coin proofs has rapidly progressed, their simulators and extractors typically differ from the 3-move (e.g., Sigma protocols) setting in interface and behavior, and are rarely studied from this viewpoint. Prior work [Abe et al., Eurocrypt ’26] introduced the notion of critical-round...

We revisit the notion of PViO [Jain-Jin, FOCS’22] – an indistinguishability obfuscation (iO) scheme for Turing machines with unbounded input length that guarantees security for pairs of machines whose equivalence can be proven in Cook’s Theory PV. Known constructions of PViO require subexponentially-hard iO for circuits. We give the first construction based on polynomially-hard iO and other standard assumptions. We further show how to replace iO with EFiO – an efficiently falsifiable...

We present a formally verified implementation of the ML-KEM Number-Theoretic Transform (NTT) based on Plantard arithmetic, produced via a code generator that targets ML-KEM, ML-DSA, and FN-DSA from a single parameter triple. The generator embeds a static bound analyzer that places modular reductions at code-generation time without runtime branching, eliminating per-scheme manual tuning while preserving constant-time guarantees. Each generation produces structurally identical implementations...

The Unbalanced Oil and Vinegar (UOV) scheme was proposed by Kipnis et al. in 1999 as a multivariate signature scheme. Owing to its small signature size and its resistance to various attacks over more than two decades, UOV has become one of the leading candidates in multivariate public key cryptography. In 2025, Ran proposed a novel algebraic key recovery attack exploiting the algebraic structure of UOV, which reduced the security of several parameter sets of UOV and its variants submitted...

Consider a cryptocurrency exchange that secures the bulk of its reserves under a small set of keys, each of which is only used to transfer cryptocurrency once a year; or the backup codes for an account login or a password manager, which are again rarely used but provide access to crucial systems or information. Securing such infrequently-used high-value secrets is crucial, but existing solutions, such as threshold wallets and 'cold' (offline) wallets, are unsatisfactory. In this work, we...

We develop (mostly) the radix-2 number-theoretic transform (NTT) and its butterflies, the twisting trick and why it never changes the transform, the freedom to use Cooley--Tukey butterflies in both directions, incomplete NTTs, Good's trick, and the ways all of these combine---closing with the coefficient-bound bookkeeping that motivates the whole toolkit. This note is intended to help implementers of postquantum cryptography, and is compressed from the author's lecture...

We present a fast implementation of Falcon (FN-DSA) signature verification with AVX-512. On a modern AMD Zen5 core, it completes a Falcon-512 verification in 3.6 microseconds, 2.6 times faster than an already optimized baseline, with comparable gains on Zen4, and consistent results across clang 21 and gcc 15. The speedup comes from rewriting the Number-Theoretic Transform (NTT) and from vectorising all other stages of the verification algorithm. The novelty is to use a 32-bit...

Efficient polynomial multiplication and matrix-vector operations are fundamental to computational algebra and modern cryptography. In lattice-based post-quantum cryptography (PQC), schemes utilizing Number Theoretic Transform (NTT)-unfriendly rings require highly optimized subquadratic multiplication algorithms. In this paper, we establish a rigorous mathematical framework for generalized $k$-way split polynomial multiplication and Toeplitz Matrix-Vector Product (TMVP) algorithms over...

Recently, Boyle, Jain, Servan-Schreiber, and Srinivasan (EUROCRYPT 2025) introduced the notion of simultaneous-message and succinct (SMS) secure computation. In an SMS protocol, after an initial sampling of a common reference string (CRS), two parties—Alice (with a large input) and Bob (with a small input)—can simultaneously exchange encodings of their private inputs and obtain additive shares of the output of a function evaluated over their inputs. The key requirement is succinctness:...

The rise of quantum computing threatens widely deployed public-key cryptosystems, driving the adoption of post-quantum cryptography (PQC) algorithms that rely heavily on modular arithmetic. Existing hardware accelerators of the PQC algorithms for resource-constrained Internet-of-Things (IoT) devices remain limited and lack integrated fault detection mechanisms. In this work, we present CMALU, a Compact, fault-tolerant Modular Arithmetic Logic Unit supporting six operations on a single...

This paper presents a native Rust implementation of the Korean post-quantum cryptography algorithms (i.e., NTRU+, SMAUG-T, HAETAE, AIMer). We optimize the implementation in Rust for speed and memory usage, and compare our implementation with the C reference code (KpqClean) and unoptimized Rust implementation (baseline). For speed, we use AVX2 and PCLMULQDQ to accelerate NTT- and Toom–Cook-based polynomial multiplication, 4-way SHAKE, and carry-less GF(2^λ) multiplication. Compared to the...

This paper presents a memory-efficient and high-speed implementation of NTRU+, one of the key encapsulation mechanisms (KEMs) selected by Korea’s post-quantum cryptography project (KpqC), on the ARM Cortex-M4. NTRU+ is small enough to run on its own on a Cortex-M4 class microcontroller, yet in real embedded environments, the peak stack occupied by polynomial buffers and the running time dominated by the NTT become key constraints. To address this, in the proposed technique, we reduce memory...

FrodoKEM, a key encapsulation mechanism based on the standard (unstructured) LWE assumption, is recommended as a conservative choice for post-quantum key exchange by agencies like BSI and ANSSI. As such, it has garnered substantial attention from an implementation security standpoint. In particular, several papers have looked into masking FrodoKEM, and, like for various other lattice-based cryptosystems, identified the Gaussian sampling operation as a major bottleneck. In FrodoKEM, it is...

We improve the performance of the lattice-based cryptosystem Dilithium on AVX2 and NEON by deeply exploiting its algorithmic properties, such as small coefficient bounds and high sparsity, with the distinct instruction-level profiles of the underlying architectures. On AVX2, we deploy a single-modulus 16-bit NTT for $c \cdot \mathbf{s}_i$ and a multi-moduli 16-bit NTT coupled with a vectorized CRT reconstruction for $c \cdot \mathbf{t}_0$. These instruction-level optimizations accelerate the...

We initiate the study of multi-authority traitor tracing (MA-TT), a decentralized variant of traitor tracing in which tracing capabilities are distributed across multiple independent authorities rather than concentrated in a single trusted entity. Ciphertexts are associated with tracing policies over a collection of authorities, specifying which subsets of authorities are authorized to jointly accuse a user of contributing to a pirate decoder. This enables fine-grained control over tracing...

This document provides a machine-checked Isabelle/HOL formalisation of the modular-arithmetic core of the Neon NTT paper of Becker, Hwang, Kannwischer, Yang, and Yang. We develop parametric theories of Barrett and Montgomery reduction and multiplication; the equivalence of Barrett and Montgomery arithmetic; the doubling- and rounding-Montgomery variants; and correctness and bounds theorems for Neon assembly kernels, against a hand-written model of the word arithmetic underlying the relevant...

We study error correction in a computationally bounded world, where errors are introduced by an arbitrary polynomial-time adversarial channel. Recent works construct seeded codes in this model, where the encoding and decoding procedure share a public random seed. They achieve significantly better tradeoffs between rate and error tolerance than what is possible information theoretically for unique decoding, essentially matching the parameters of the best known efficiently list-decodable...

Quantum cryptography is a rapidly developing area which leverages quantum information to accomplish classically impossible tasks. In many of these protocols, quantum states are used as long-term cryptographic keys, relying on the quantum no-cloning theorem to ensure that the keys cannot be copied by an adversary. Unfortunately, quantum state tend to decohere, and hence, persistent quantum memory is and will remain one of the most valuable and challenging resources for quantum computers. As...

In KEM-based TLS 1.3 key establishment, the client generates a fresh KEM key pair for each connection, placing key generation on the handshake critical path. For NTRU+, a KEM based on the NTRU problem selected in the Korean Post-Quantum Cryptography (KpqC) competition, the dominant cost in this path is the polynomial inversion needed to compute the public key. Although NTRU+ uses an NTT-friendly ring and performs this inversion in the NTT domain, the routine still decomposes into many base...

NIST standardised a lattice-based key-encapsulation mechanism (ML-KEM) and a lattice-based digital signature scheme (ML-DSA) in 2024 as post-quantum replacements for classical key establishment and digital signatures. Both compute a forward number-theoretic transform (NTT) over secret-bearing polynomials; the NTT's twiddle constants are a documented fault-attack surface. Published attacks zero every twiddle with a single glitch on ML-KEM key generation, or zero individual twiddles on ML-DSA...

Modern cryptography relies on the intractability of computational problems. We present an approach to building cryptography from a new source of hardness: \emph{proving mathematical theorems}. Our main result is a construction of succinct non-interactive arguments (SNARGs) for NP under a new, but natural, assumption on the hardness of proving lower bounds in proof complexity. Specifically, our assumption states that it is impossible to prove, within a weak bounded arithmetic theory, the...

We study generic committing attacks—where ciphertexts decrypt under more than one context, i.e., key, nonce, associated data—for sponge-based authenticated encryption. As our main contribution, we give three new committing attacks which outperform existing attacks. One of our attacks provides a counterexample showing that the previous proof for the committing security of Ascon-like schemes with zero-padding does not extend to all parameter choices: in case of 128-bit tags and 256-bit...

Side-channel attacks are a relevant threat to many modern cryptographic schemes and often have fatal consequences such as revealing partial information about secret keys. While leakage-resilient cryptography aims to solve this problem, existing works focus exclusively on showing security against classical leakage. Moreover, recent public key encryption (PKE) schemes utilizing quantum secret keys achieve security against unbounded classical leakage, but offer no guarantees on any amount of...

Correlation-robust (CR) hashing and its variants are central components in efficient secure-computation protocols, including OT extension, garbled-circuit optimizations such as Free-XOR and half-gates, and GGM-style tree constructions. In practice, these hashes are typically instantiated from block ciphers, such as AES. The most commonly analyzed constructions are the Matyas-Meyer-Oseas (MMO) construction and its variants, such as \(\widehat{\mathsf{MMO}}\). Existing analyses of such...

Registered attribute-based encryption (ABE) is a generalization of ABE that replaces the central trusted key-issuer with an untrusted key curator. In registered (ciphertext-policy) ABE, users generate their own public keys and there is a transparent aggregation process that takes the public keys of the users together with their attributes and aggregates them into a short master public key that functions as the public key for a standard ABE scheme. A sequence of works has focused on...

Multivariate quadratic (MQ) signature schemes are an important class of post-quantum digital signatures. These schemes rely on the hardness of solving underdetermined MQ systems, where the number of variables \(n\) exceeds the number of equations \(m\). Therefore, analyzing the efficiency of algorithms for underdetermined MQ systems is essential for evaluating the security of MQ-based signature schemes. Several algorithms have been proposed to solve underdetermined MQ systems efficiently....

Implementing post-quantum signatures correctly in production cryptographic libraries remains challenging even after standardization. ML-DSA implementations rely on NTT-based polynomial arithmetic with lazy Montgomery reductions, and omitting a reduction may be either a valid optimization or a latent arithmetic defect. In practice, reduction calls are often removed for performance, memory, or embedded-deployment reasons, but the required correctness condition is inter-procedural: a site that...

Topology-hiding computation (THC) enables a set of parties, communicating over an incomplete network, to execute a secure multiparty computation (MPC) protocol for securely computing a function, while also hiding the network topology from within a given class of graphs. Semi-honest THC can be achieved over arbitrary graph classes, facing an arbitrary number of corruptions, from various assumptions implying oblivious transfer (OT). These assumptions are justified by strong lower bounds,...

Discrete Gaussian sampling is an important operation at the core of many lattice-based cryptosystems, which presents significant challenges from an implementation standpoint. In particular, it is difficult to protect against side-channel attacks. Extensive research has gone into the problem of addressing timing side-channel attacks, and as result, constant-time discrete Gaussian sampling is now well-understood. However, few papers so far have attempted to achieve protection against...

In side-channel analysis of ML-KEM (a NIST-standard PQC algorithm), SASCA is a powerful profiling attack. However, obtaining a profiling device strictly matching the target is challenging in practice. To address this, we propose the first profiling-device-free SASCA framework for ML-KEM. The framework first controls the NTT input by choosing ciphertexts and trains a leakage model. Subsequently, leveraging the similarity between NTT and INTT, it uses adversarial unsupervised domain adaptation...

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...

In 2020, Ravi et al. [23] published three shuffling variants with each offering a different performance-security trade-off for protecting the Numeric theoretic Transform (NTT). Among them, the fine-shuffling was proposed as the lightweight variant. The idea is to randomise the order of loading and storing the operands of the butterfly computation using conditional swapping based on random control bit. However, as noted by the authors themselves, basic fine-shuffling implementation suffered...

A non-interactive secure computation (NISC) protocol allows a client with input $x$ and a server with input $y$ to compute $f(x,y)$ using a single message from the client and a single response from the server. The protocol is called succinct if the size of the server’s message depends only on the output length and is independent of the size of $y$ and the complexity of $f$. In the semi-honest setting, succinct NISC is known from fully homomorphic encryption (FHE). In contrast, malicious...

Communication locality of an $n$-party protocol measures the maximum degree of the communication graph induced by the protocol execution. While secure multi-party computation (MPC) with small, sublinear locality exists in the static-corruption setting, this goal seems nearly paradoxical in the adaptive-corruption setting: Even against fail-stop adversaries, small neighbour sets of honest parties lie vulnerable to identification and corruption. Surprisingly, Chandran et al. [ITCS '15]...

Dwork and Naor (FOCS 2000) showed a generic transformation to construct a ZAP (a two-round public-coin witness-indistinguishable proof) from any non-interactive zero-knowledge (NIZK) proof with statistical soundness in the common random string model. In recent years, a number of works have shown how to construct NIZK arguments in the common random string model from a broad range of assumptions including decisional Diffie-Hellman (DDH), learning with errors (LWE), or combinations of multiple...

Succinct non-interactive arguments (SNARGs) for NP allow an efficient prover to convince a verifier that an NP statement is true with a proof that is much shorter than the original NP witness. Gentry and Wichs (STOC ’11) showed that adaptive soundness of such SNARGs cannot be proven via a black-box reduction from any falsifiable assumption. However, recent works by Waters, Wu and Zhandry (STOC ’24, CRYPTO ’24, CRYPTO ’25) circumvent this negative result by relying on subexponential hardness...

The *random oracle model* (ROM) allows us to optimistically reason about security properties of cryptographic hash functions, and has been hugely influential in designing practical cryptosystems. But it is overly optimistic against non-uniform adversaries, and often suggests security properties and security levels unachievable by any real hash function. To reconcile with this discrepancy, Unruh [CRYPTO ’07] proposed the *auxiliary-input random oracle model* (AI-ROM), where a non-uniform...

Isogeny-based cryptography is a kind of cryptography whose security relies on the computational hardness of the isogeny problem. This field is gaining attention as a promising candidate for post-quantum cryptography. Among the notable schemes within this category is SQIsign, a signature schemes that has been submitted to the NIST Post-Quantum Cryptography Standardization competition. In this paper, we introduce a new isogeny-based signature scheme, ∆-SQIsign, which represents a significant...

Zero-knowledge execution of high-level programs proceeds by repeatedly evaluating CPU steps. Each such step privately selects and evaluates an instruction (possibly involving memory access) from a rich instruction set. Building on this paradigm, ZEE (Heath et al., S&P'21) realized a full toolchain supporting arbitrary $\texttt{ANSI C}$ programs, demonstrating this capability by proving SIR- and CVE-reported bugs in off-the-shelf Linux programs $\texttt{sed}$ and $\texttt{gzip}$. We revamp...

Tosun and Savas (IEEE TIFS'23) proposed a non-profiling power analysis attack on masked ML-KEM, or CRYSTALS-Kyber. Their attack can recover a full secret key of Kyber with 7,000 power traces. Later, Tosun et al. (IEEE Access'24) claimed an improvement over the previous attack with only 550 traces, but the result is not convincing. In particular, their attack does not seem to recover a full secret key of masked Kyber; instead, it recovers only the absolute values for every coefficient of a...

Garbled circuits are a fundamental primitive in cryptography. While the size of garbled circuits in Yao's original scheme grows linearly with the circuit size, a recent line of work on stacked garbling (SGC) [Heath-Kolesnikov, CRYPTO'20] has achieved near-sublinear size for branching computations, based only on one-way functions. Specifically, these schemes achieve garbled size growing only with the size of a single branch and the total input length to all the branches. Due to the latter...

Fully homomorphic encryption (FHE) enables computation directly on encrypted data and is increasingly researched for privacy-preserving machine-learning inference. Such workloads are dominated by matrix multiplication, which is not represented natively by conventional vector-oriented FHE schemes. CKKS is widely used for approximate encrypted inference because it supports packed real and complex arithmetic; however, matrix multiplication generally requires specific packing formats that are...

We present the first lattice-based, partially non-interactive threshold signature scheme that tolerates the adaptive corruption of up to $T-1$ signers, where $T$ is the signing threshold. Our construction relies on the MSIS and MLWE assumptions, and has two rounds, of which only the second is message-dependent. We substantially improve upon prior adaptively secure lattice-based schemes (CRYPTO '24 and EUROCRYPT '26), which require at least two message-dependent rounds. Compared to prior...

We consider (almost) $k$-wise independent hash functions, whose evaluations on any $k$ inputs are (almost) uniformly random, for very large values of $k$. Such hash functions need to have a large key that grows linearly with $k$. However, it may be possible to evaluate them in sub-linear time by only reading a small subset of $t \ll k$ locations during each evaluation; we call such hash functions $t$-local. Local hash functions were previously studied in several works starting with Siegel ...

We present a Number Theoretic Transform (NTT) hardware architecture based on the Prouhet-Thue-Morse (PTM) code, enabling NTT implementations relying only on single-port RAMs (SPRAMs), rather than using dual-port RAMs (DPRAMs) as usually done in the literature. We show that the PTM code supports a conflict-free, transactional, and streamlined pipeline across all NTT computation stages, as well as scalable parallelism through multiple butterfly units. Using this approach, we design single- and...

Cold boot attacks, first introduced by Halderman et al. (USENIX'08), are a class of attacks that aim at recovering cryptographic secrets stored in volatile memory after a computer is powered off, using the fact that DRAM modules retain their contents to a large extent for some time, especially at low temperatures. Cold boot attackers can recover the original contents of memory with some flipped bits, with bit flip probabilities of <10% for one-to-zero and much lower (<0.1%) for zero-to-one...

At EUROCRYPT 2024, Flórez-Gutiérrez and Todo introduced the puncturing technique for linear key recovery attacks. Puncturing works by modifying the map which evaluates the linear approximation as a function of the plaintext, ciphertext and key by setting carefully chosen coordinates of its Fourier transform to zero. These modifications are intended to reduce the time complexity of the attack at the cost of an increase in data complexity. In this note, we revisit the model which is used to...

Fully Homomorphic Encryption (FHE) enables arbitrary computation on encrypted data without decryption, providing strong privacy guarantees for secure cloud computing, encrypted analytics, and privacy-preserving machine learning. However, practical deployment of FHE remains limited by the high computational cost of polynomial arithmetic over large modular rings. In particular, Number Theoretic Transform (NTT)–based polynomial multiplication dominates the execution time of modern lattice-based...

QR-UOV is a multivariate signature scheme derived from UOV that achieves compact public keys by exploiting quotient-ring structure, making it a promising candidate for post-quantum digital signatures. In QR-UOV, most parts of the public map are derived from the public key seed using a PRG. This public key expansion for QR-UOV includes rejection sampling to generate coefficients uniformly over $\mathbb{F}_q$, since QR-UOV uses a small odd-prime base field. However, this rejection sampling...

Large-size Number Theoretic Transforms (NTTs) are key operations in modern Zero-Knowledge Proofs (ZKPs), where the NTT size often reaches millions of points and the arithmetic is over wide prime fields. To handle such NTTs on hardware, prior designs commonly rely on the decomposition algorithm, which makes large-size NTTs feasible by streaming sub-NTTs through limited on-chip buffers. However, in practical implementations, decomposition alone is insufficient to ensure high efficiency. Since...

This paper presents the first round-optimal threshold blind signature without random oracles. Our construction achieves security in the algebraic group model (AGM) for asymmetric pairing groups, and tolerates adaptive corruption of up to $t-1$ signers, where $t$ is the threshold. We improve upon the recent threshold blind signatures of Lehmann, Nazarian and Özbay (EUROCRYPT 2025) and Jarecki and Nazarian (ASIACRYPT 2025) in two ways: we eliminate both the reliance on random oracles and the...

The processing of ML-KEM (formerly CRYSTALS-Kyber), a key encapsulation mechanism with post-quantum security, is performed by multiplication, addition, and subtraction of polynomials whose coefficients lie in the finite field ${\mathbb F}_{3329}$. To reduce the number of such operations, it is common to use the Number Theoretic Transform (NTT). This paper focuses on arithmetic over ${\mathbb F}_{3329}$ and proposes the use of a logarithmic representation with respect to a primitive element...

This paper gives the first lattice-based two-round threshold signature scheme that tolerates the adaptive corruption of up to $T -1$ out of $N$ signers. Our construction is based on the MLWE and MSIS assumptions. We substantially improve upon the only existing adaptively secure lattice-based construction, recently given by Katsumata, Reichle, and Takemure (CRYPTO '24), which requires five rounds.

Mahadev [SIAM J. Comput. 2022] introduced the first protocol for classical verification of quantum computation based on the Learning-with-Errors (LWE) assumption, achieving a 4-message interactive scheme. This breakthrough naturally raised the question of whether fewer messages are possible in the plain model. Despite its importance, this question has remained unresolved. In this work, we prove that there is no quantum black-box reduction of non-interactive classical verification of...

Registered attribute-based encryption (Reg-ABE) is a new variant of attribute-based encryption (ABE) that was introduced to resolve the notorious key escrow problem. In a Reg-ABE system, there is no authority that generates secret keys, and each user joins the system by generating its own public/secret key pair. Because of its public-key infrastructure-like model and versatile access control functionality, Reg-ABE is a promising alternative of ABE. In this work, we present a highly space...

One-time programs (OTPs) aim to let a user evaluate a program on a single input while revealing nothing else. Classical OTPs require hardware assumptions, and even with quantum information, deterministic functionalities remain impossible due to gentle-measurement attacks (Broadbent, Gutoski and Stebila, 2013). While recent works achieve positive results for randomized functionalities with high-entropy outputs, the fundamental limits and the strongest achievable security notions remain poorly...

\emph{Modular Polynomial Commitment Schemes (Mod-PCS)} extend standard PCSs by enabling provable evaluation of integer polynomials modulo a random modulus, providing a natural foundation for SNARKs that operate directly over large integers without emulating arithmetic in finite fields. Only two Mod-PCS constructions are known. The first (Campanelli and Hall-Andersen, IACR ePrint 2024) serves primarily as a feasibility result and is impractical and not post-quantum secure due to its reliance...

A recent breakthrough [Hirahara and Nanashima, STOC’2024] established that if $\mathsf{NP} \not \subseteq \mathsf{ioP/poly}$, the existence of zero-knowledge (ZK) with negligible errors for $\mathsf{NP}$ implies the existence of one-way functions (OWFs). This work obtains a characterization of one-way functions from the worst-case complexity of zero-knowledge in the high-error regime. Assuming $\mathsf{NP} \not \subseteq \mathsf{ioP/poly}$, we show that any non-trivial, constant-round...

The unbalanced oil and vinegar signature scheme (UOV) was proposed by Kipnis et al. in 1999 as a multivariate-based scheme. UOV is regarded as one of the most promising candidates for post-quantum cryptography owing to its short signatures and fast performance. Recently, Ran proposed a new key recovery attack on UOV over a field of even characteristic, reducing the security of its proposed parameters. Furthermore, Jin et al. generalized Ran’s attack to schemes over a field of arbitrary...

We revisit the question of minimizing the overhead of security against malicious parties in dishonest-majority secure computation. A leading approach, pioneered by the SPDZ line of protocols, uses homomorphic MACs to authenticate computation: Parties effectively compute a MAC on the computation output using authenticated multiplication triples (AMT). However, securely generating these AMTs presently sits as the cost bottleneck. In this work, we introduce a new technique for enabling...

Quantum computing threatens widely deployed public-key cryptosystems, driving the urgent adoption of post-quantum cryptography (PQC) in cloud and hardware-accelerated security infrastructures. This paper presents Adams Bridge, an industry-grade hardware accelerator for lattice-based PQC that integrates ML-KEM and ML-DSA within a unified architecture to maximize hardware reuse and silicon efficiency. The design features a staged, pipelined datapath that exploits multi-level parallelism to...

This paper presents improved attacks and proofs for the key committing security of EtE-HCTR2, a robust authenticated encryption scheme constructed from HCTR2 and the Encode-then-Encipher (EtE) framework, in light of the ongoing standardization effort of cryptographic accordions by NIST. We improve attacks on the instantiations with two common encodings, where zeros are either appended or prepended to the message, namely EtE_A-HCTR2 and EtE_P-HCTR2. Compared with the state-of-the-art attack...

Most PQC schemes remain too resource-intensive for ultra-constrained 8-bit AVR wireless sensor nodes. In this work, we present a comprehensive approach to practical lightweight PQC for such devices, covering scheme design, implementation optimization, and protocol integration. Our contributions are threefold: (i) We propose CTRU-Light, a lattice-based KEM specifically tailored for IoT sensor nodes. It combines small moduli, low-degree polynomials, and NTT-friendly arithmetic for high...

We construct the first folding scheme that simultaneously achieves six desirable properties: plausible post-quantum security, pay-per-bit commitment costs, field-native arithmetic (the sum-check and norm checks run purely over a small field), support for general (non-SIMD) constraint systems, small-field support (e.g., Goldilocks), and low recursion overheads. No existing scheme satisfies all six: group-based schemes (e.g., HyperNova) lack post-quantum security and are tied to large...

Post-Quantum cryptography (PQC) typically requires more memory and computational power than conventional public-key cryptography. Until now, most active research in PQC optimization for embedded devices has focused on 32-bit and 64-bit ARM architectures, specifically Cortex-M0/M3/M4 and ARMv8. To enable a smooth migration of PQC algorithms in Internet of Things environments, optimization research is also required for devices with lower computational capabilities. To address this gap, we...

Existing protocols for classical verification of quantum computation (CVQC) consume the prover's witness state, requiring a new witness state for each invocation. Because QMA witnesses are not generally clonable, destroying the input witness means that amplifying soundness and completeness via repetition requires many copies of the witness. Building CVQC with low soundness error that uses only *one* copy of the witness has remained an open problem so far. We resolve this problem by...

Every formally verified system embeds a verification boundary: the interface between code with machine-checked proofs and code that is trusted without them. We study what happens when this boundary is not communicated clearly. Through a case study of CE Labs's libcrux and hpke-rs cryptographic libraries, we present thirteen vulnerabilities that escaped formal verification. Nine reside in unverified code, including a cross-backend endianness bug that caused real decryption failures in...

We study succinct non-interactive arguments of proximity (SNAP), which allow a prover to convince a verifier that a statement is true through a short message. Moreover, the verifier reads only a sublinear number of bits of the statement, and soundness is required to hold against polynomial-time adversaries when the statement is $\epsilon$-far from any true statements. SNAPs can be seen as the natural analog of property testing in the context of succinct non-interactive arguments...

Homomorphic Encryption (HE) provides strong data privacy for cloud services but at the cost of prohibitive computational overhead. While GPUs have emerged as a practical platform for accelerating HE, there remains an order-of-magnitude energy-efficiency gap compared to specialized (but expensive) HE ASICs. This paper explores an alternate direction: leveraging existing AI accelerators, like Google's TPUs with coarse-grained compute and memory architectures, to offer a path toward ASIC-level...

The Merkle-Damgård construction (in its strengthened form as used in SHA-256 and SHA-512, the untruncated members of SHA-2) is not classically indifferentiable from a Variable-Input-Length (VIL) random oracle because of the length-extension attack. Nevertheless, Dodis, Ristenpart, and Shrimpton showed that Merkle-Damgård is publicly indifferentiable, a weaker notion that still justifies replacing a VIL random oracle by Merkle-Damgård in many security proofs when all inputs to a random...

To enhance the diversity of basic hard problems underlying post-quantum cryptography (PQC) schemes, NIST launched an additional call for PQC signatures in 2023. Among numerous candidate schemes, several code-based ones, which have successfully advanced to the second round, are constructed by applying the Fiat--Shamir transform to the parallel repetition of a (relatively low soundness) commit-and-prove sigma protocol similar to the Stern identification scheme. In Fiat--Shamir-based...

Falcon is a lattice-based signature scheme that has been selected as a standard in NIST post-quantum cryptography standardization project. The trapdoor generation process of Falcon amounts to generating two polynomials, $f$ and $g$, that satisfy certain conditions to achieve a quality parameter $\alpha$ as small as possible, because smaller $\alpha$ usually leads to higher security levels and shorter signatures. The original approach to generate NTRU trapdoors, proposed by Ducas,...

The ongoing transition to Post-Quantum Cryptography (PQC) has highlighted the need for cryptographic schemes that offer high security, strong performance, and fine-grained parameter selection. In lattice-based cryptography, particularly for the popular module variants of learning with errors (Module-LWE) and learning with rounding (Module-LWR) schemes based on power-of-two cyclotomics, existing constructions often force parameter choices that either overshoot or undershoot desired security...

As quantum computing continues to advance, traditional public-key cryptosystems face increasing vulnerability, necessitating a global transition toward post-quantum cryptography (PQC). A primary challenge for both cryptographers and system architects is the efficient integration of PQC into high-performance computing platforms. ARM, a dominant processor architecture, has recently introduced ARMv9-A to accelerate modern workloads such as artificial intelligence and cloud computing. Leveraging...

The block cipher (BC) mode for realizing a variable-input-length strong tweakable pseudorandom permutation (VIL-STPRP), also known as the accordion mode, is a rapidly growing research field driven by NIST's standardization project, which considers AES as a primitive. Widely used VIL-STPRP modes, such as HCTR2, have birthday-bound security and provide only 64-bit security with AES. To provide higher security, NIST is considering two directions: to develop new modes with beyond-birthday-bound...

A classical obfuscator for quantum circuits is a classical program that, given the classical description of a quantum circuit $Q$, outputs the classical description of a functionally equivalent quantum circuit $\widetilde{Q}$ that hides as much as possible about $Q$. Previously, the only known feasibility result for classical obfuscation of quantum circuits (Bartusek and Malavolta, ITCS 2022) was limited to "null" security, which is only meaningful for circuits that always reject. On the...

This paper presents the first construction of adaptively secure non-interactive key exchange (NIKE) for an unbounded number of parties. Prior unbounded protocols were restricted to static security, with no adaptively secure constructions known even in the random oracle model. Our main contribution is a NIKE scheme in the standard model, that supports an unbounded number of honest and malicious users, as well as unbounded party sizes, while tolerating a bounded number of dynamic user...

We revisit the question of whether it is possible to build succinct non-interactive arguments ($\mathsf{SNARG}$s) for all of $\mathsf{NP}$ under standard assumptions using non-signaling probabilistically checkable proofs [Kalai-Raz-Rothblum, STOC' 14]. In particular, we observe that using exponential-length PCPs appears to circumvent all of the existing barriers. For our main result, we give a candidate non-adaptive $\mathsf{SNARG}$ for $\mathsf{NP}$ and prove its soundness under: -...

We show that a simple eavesdropper listening in on classical communication between potentially entangled quantum parties will eventually be able to impersonate any of the parties. Furthermore, the attack is efficient if one-way puzzles do not exist. As a direct consequence, one-way puzzles are implied by reusable authentication schemes over classical channels with quantum pre-shared secrets that are potentially evolving. As an additional application, we show that any quantum money scheme...

The construction of building beyond-birthday-bound secure pseudorandom functions (PRFs) from the Xor-sum of 2 pseudorandom permutations (PRPs) has been known since EUROCRYPT 1998. However, the first concrete instance was only published recently at FSE 2022: the low-latency PRF Orthros. Subsequently, at ASIACRYPT 2024, Flórez-Gutiérrez et al. proposed the general framework of ZIP ciphers, where a block cipher $E_{1} \circ E_{0}$ is used to construct the PRF $E_{0} \oplus E_{1}^{-1}$. They...

Along with the National Institute of Standards and Technology (NIST) post-quantum cryptography (PQC) stan- dardization process, efficient hardware acceleration for PQC has become a priority. Among the NIST-selected PQC digital signature schemes, FALCON shows great promise due to its compact key sizes and efficient Signature Verification procedure. However, FALCON is regarded as highly computationally com- plex, and as a result, few works for hardware acceleration of FALCON can be...

Learning problems have become a foundational element for constructing quantum-resistant cryptographic schemes, finding broad application even beyond, such as in Fully Homomorphic Encryption. The increasing complexity of this field, marked by the rise of physical learning problems due to research into side-channel leakage and secure hardware implementations, underscores the urgent need for a more comprehensive analytical framework capable of encompassing these diverse variants. In...

Watermarks are an essential tool for identifying AI-generated content. Recently, Christ and Gunn (CRYPTO '24) introduced pseudorandom error-correcting codes (PRCs), which are equivalent to watermarks with strong robustness and quality guarantees. A PRC is a pseudorandom encryption scheme whose decryption algorithm tolerates a high rate of errors. Pseudorandomness ensures quality preservation of the watermark, and error tolerance of decryption translates to the watermark's ability to...

The last decade has seen remarkable success in designing and uncovering new applications of indistinguishability obfuscation (i$\mathcal{O}$). The main pressing question in this area is whether post-quantum i$\mathcal{O}$ exists. All current lattice-based candidates rely on new, non-standard assumptions, many of which are known to be broken. To make systematic progress on this front, we investigate the following question: can general-purpose i$\mathcal{O}$ be reduced, assuming...

Recent advances in quantum computing pose a threat to the security of digital communications, as large-scale quantum machines can break commonly used cryptographic algorithms, such as RSA and ECC. To mitigate this risk, post-quantum cryptography (PQC) schemes are being standardized, with recent NIST recommendations selecting two lattice-based algorithms: ML-KEM for key encapsulation and ML-DSA for digital signatures. Two computationally intensive kernels dominate the execution of these...

We construct a publicly-verifiable non-interactive zero-knowledge argument system for QMA with the following properties of interest. 1. Transparent setup. Our protocol only requires a uniformly random string (URS) setup. The only prior publicly-verifiable NIZK for QMA (Bartusek and Malavolta, ITCS 2022) requires an entire obfuscated program as the common reference string. 2. Extractability. Valid QMA witnesses can be extracted directly from our accepting proofs. That is, we...

Threshold encryption distributes decryption capability across $n$ parties such that any $t$ of them can jointly decrypt a ciphertext, while smaller coalitions learn nothing. However, once $t$ or more parties collude, traditional threshold schemes provide no accountability: a coalition of $t$ or more parties can pool its keys into a pirate decoder that enables unrestricted decryption, all without any risk of being exposed. To address this, Boneh, Partap, and Rotem [CRYPTO '24] introduced...

We present SALSAA, a more efficient and more versatile extension of the state-of-the-art lattice-based fully-succinct argument frameworks, ``RoK, paper, SISsors (RPS)'' and ``RoK and Roll (RnR)'' [Klooß, Lai, Nguyen, and Osadnik; ASIACRYPT'24, '25], integrating the sumcheck technique as a main component. This integration enables us to design an efficient norm-check protocol (controlling the norm during witness extraction) with a strictly linear-time prover while reducing proof sizes by...

In a batched identity-based encryption (IBE) scheme, ciphertexts are associated with a batch label $\mathsf{tg}^\ast$ and an identity $\mathsf{id}^\ast$ while secret keys are associated with a batch label $\mathsf{tg}$ and a set of identities $S$. Decryption is possible whenever $\mathsf{tg} = \mathsf{tg}^\ast$ and $\mathsf{id}^\ast \in S$. The primary efficiency property in a batched IBE scheme is that the size of the decryption key for a set $S$ should be independent of the size of $S$....

Quantum cryptography is a rapidly-developing area which leverages quantum information to accomplish classically-impossible tasks. In many of these protocols, quantum states are used as long-term cryptographic keys. Typically, this is to ensure the keys cannot be copied by an adversary, owing to the quantum no-cloning theorem. Unfortunately, due to quantum state's tendency to decohere, persistent quantum memory will likely be one of the most challenging resources for quantum computers. As...

The MPC-in-the-Head paradigm is a promising approach for constructing post-quantum signature schemes. Its significance is underscored by NIST's selection of six signatures based on this paradigm and its variants, TC-in-the-Head and VOLE-in-the-Head, among the fourteen round-2 candidates in its additional post-quantum cryptography standardization process. Recent works by Aguilar-Melchor et al. (ASIACRYPT 2023), Hülsing et al. (CRYPTO 2024), and Baum et al. (CRYPTO 2025) have established...

Key-dependent attacks are effective only for specific weak-key classes, limiting their practical impact. We present a generic statistical framework that combines multiple key-dependent distinguishers into universal attacks covering the full key space. Using log-likelihood ratio statistics, our framework tests the secret key against multiple weak-key distinguishers, aggregates their evidence to determine whether the key is weak or strong for each distinguisher, and exploits this...