International Association
for Cryptologic Research

This work presents a private instant messaging protocol that leverages the public log layer of blockchains as the message transport layer, while the cryptographic state is kept only by client applications. Thanks to the properties of public ledgers, this approach achieves strong censorship resistance, while also revealing the economic and cryptographic limits of on-chain messaging. Notably, given the transparency of public ledgers, and since reading and writing operations are in most cases outsourced to third-party providers that may be curious, a well-known concern is direct metadata leakage. We address this both at first contact and during the conversation: for first contact, we propose two alternative discovery mechanisms, one based on long-term key encapsulation with trial decryption, the other on a private signaling service backed by trusted hardware. For the ongoing conversation, we show that topic rotation, driven by the off-chain cryptographic state, suffices to prevent topic and conversation linkability. As our main contribution, we provide an in-depth analysis of Verbeth's metadata leakage under different adversarial assumptions for both phases.

Category theory is a mathematical theory of composition, widely used in logic, computing, and physics. Here we apply it to give a theory of secure composition. In particular, we provide a categorical treatment of Canetti's Universal Composability (UC) framework for systems with a static number of parties and sessions, often termed UC for static systems, yielding four benefits.

First, we present our results graphically yet retain rigor by applying a standard categorical technique known as string diagrams. In particular, our formulation of the composition theorem can be graphically verified with a short sequence of diagrams, while remaining translatable to equations and amenable to formal verification.

Second, categories let us generalize so that our results extend beyond interactive Turing machines to other forms of computation, such as quantum computation or domain-specific languages.

Third, categories help us drop some unnecessary restrictions of UC (e.g., our adversary can be a computational network rather than a single Turing machine); we prove equivalence between our variant and the usual UC, showing no expressiveness is lost.

Finally, the categorical perspective leads us to identify and correct some minor technical oversights in the standard formulation of simple UC.

Field trace evaluation has emerged as a powerful tool in fully homomorphic encryption, with broad applications ranging from bootstrapping algorithms to privacy-preserving protocols. Recent advances have significantly reduced its noise growth by combining tower-based evaluation strategies with rescaling operations. However, existing analyses rely on uniform noise bounds that fail to capture the actual noise behavior across different coefficients, leading to substantial gaps between theoretical estimates and empirical observations.

In this work, we present a refined algebraic analysis of trace evaluation over power-of-two cyclotomics that uncovers structured cancellation effects among noise coefficients induced by subsequent linear operators, in particular the trace mappings of subextensions. We show that, except for the constant term, the variance of each output noise coefficient depends on the 2-adic valuation of its index, yielding bounds that improve upon prior uniform estimates by a factor of $O(\log n)$ both for non-constant coefficients and after a subsequent plaintext-ciphertext multiplication, where $n$ is the ring degree. We further extend our analysis to two typical algorithmic applications of trace evaluation. For ciphertext packing, we derive a non-recursive formulation that admits a cleaner structure and slightly tighter noise estimates. For coefficient extraction, our coefficient-wise analysis improves upon prior uniform variance bounds by factors ranging from $\Theta(n)$ to $\Theta(n^2)$ for non-constant coefficients and by a factor of $O(n)$ after post-multiplication. Experimental results confirm that the observed noise variances follow the coefficient-wise pattern predicted by our analysis and demonstrate pronounced improvements over existing estimates, providing effective guidance for parameter selection and system configuration in practice.

Designated Verifier Signatures (DVS) are an important variant of digital signatures that ensure only a specified verifier can validate a signature, while preserving non-transferability. With the advent of quantum computing, several quantum DVS schemes have been proposed to achieve quantum security. In this paper, we revisit the quantum DVS protocol of Xin et al. [Quantum Information Processing, 2022] and provide a structural cryptanalysis of its design. We show that the scheme admits an existential forgery under a chosen-message attack: given a valid quantum signature on one message, an adversary can efficiently transform it into a valid signature on another message without knowledge of the signer’s private key. To address this weakness, we propose a minimal countermeasure based on QKD-derived keys and quantum one-time pad encryption.

Universal hash functions (UHFs) are basic building blocks in cryptography, making the topic of designing secure, fast UHFs of longstanding interest. This paper presents an exploration of the design space for multivariate UHFs, that is UHFs that involve the evaluation of a multivariate polynomial over a finite field. We focus on two-level designs, wherein a lower-level hash function produces intermediate values that are consumed by a higher-level one, and where both hash functions are based on either univariate or multivariate polynomials. This approach allows designs to benefit from the desirable features of both components and thereby strike new trade-offs between key size, security level, and amenability to optimization techniques. We extend the recent UHF code generation and benchmarking framework of Degabriele et al. (IEEE S&P 2024) to accommodate our multivariate designs (and also to support binary field arithmetic). We then use the framework to study the performance of a large collection of new two-level designs. This is done by first conducting a statistical factor analysis to determine which design features (and combinations of those features) most influence performance, and then using it to identify particular combinations of lower-level and higher-level hash functions offering particularly good performance/security trade-offs. We present new designs for both binary and prime fields, at two different security levels (corresponding to roughly 128 and 256 bits of security). Our best designs have performance that significantly outperforms state-of-the-art UHFs in the research literature and as deployed in mainstream cryptography libraries by up to 25%, resulting in 0.3 cycles/byte for 128-bit binary fields. We expect further gains from optimizations such as vectorization, as our benchmarks rely purely on auto-generated code from the extended framework, while state-of-the-art implementations typically use hand-optimized implementation strategies. We conclude with a brief inquiry into the performance implications of employing our best UHF design in the AEAD and Accordion mode designs currently under consideration for standardization by NIST.

We present the first passive side-channel distinguisher on LESSv2.0, a second-round candidate in NIST’s call for additional post-quantum digital signature schemes. We target the Gaussian elimination at the core of LESS and and present a method to exploit algorithmic leakage arising from the manipulation of sparse versus dense columns.

We show that this leakage, while trivially available in non-constant-time implementations, also persists in constant-time implementations and can be exploited using a distinguisher. Concretely, the proposed attack relies only on distinguishing zero-valued computations from random ones that are repeatedly evaluated during the computation, leading to a large attack surface and making the attack robust to noise. Through simulation, we experimentally show that the required number of observed signatures lies between 300 and 2357 depending on the parameter set. This relatively large number is due to the targeted information being inherently noisy, leading to a correlation-based key recovery attack, even with noiseless leakage. Furthermore, we discuss three common countermeasures: first-order masking, shuffling and blinding.

Finally, we validate our approach on implementations with and without masking by showing the presence of leakage on a physical target.

Private histogram computation is a fundamental building block for many data analytics tasks, enabling frequency analysis without revealing individual inputs. Existing protocols achieving robustness against malicious clients and servers typically require three servers with limited adversarial tolerance, restricting practicality.

In this work, we present Paras, the first two-server protocol for private histogram computation that achieves robustness against collusion between a malicious server and arbitrarily many malicious clients. Paras builds upon distributed point function-based approaches and introduces novel consistency checks leveraging vector oblivious linear evaluation (VOLE) to enforce both input correctness and output integrity. To realize these checks, we design two new cryptographic primitives: (1) aBV, an authenticated bit verification protocol that ensures VOLE committed shares correspond to valid bits, and (2) adIPA, an authenticated double inner product argument that enables secure consistency checks across two different VOLE sessions. These primitives may be of independent interest for other secure computation tasks.

We show that Paras is highly efficient and scalable: clients incur minimal cost independent of domain size, while servers achieve low per-client runtime, communication, and storage even at scale. For example, with 8192 clients over a domain of 128 inputs, each server requires only 14 ms runtime and 24 KB communication per client.

Aggarwal, Dadush, Regev, and Stephens-Davidowitz (ADRS; STOC 2015) sample $2^{n/2}$ discrete Gaussians at an arbitrary parameter in $2^{n+o(n)}$ time, and above smoothing in $2^{n/2+o(n)}$ time. They ask whether the latter bound suffices for one sample at an arbitrary parameter. We answer this question affirmatively: for every rank-$n$ lattice $L\subseteq\R^n$ specified by a rational basis and every rational $s^2>0$, we produce one sample from $D_{L,s}$ within statistical distance $\exp(-\Omega(n^3))$ in expected $2^{n/2+o(n)}$ time and $2^{n/2+o(n)}$ space on every execution. The algorithm samples from random superlattices that are smooth at the required scale with constant probability and outputs the first point in $L$; a Gaussian-mass comparison shows that the $2^{n/2}$ samples produced by one ADRS call contain a point of $L$ with inverse-polynomial probability. The factor $2^{n/2}$ is tight in this Gaussian-mass comparison. For every fixed rational $\alpha<1.4697$, the same comparison gives a sub-$2^n$ algorithm for exact CVP on targets satisfying $\dist(y,L)\le\alpha\lambda_1(L)$, without a uniqueness assumption, and an exact-SVP algorithm in $2^{0.7315n+o(n)}$ time.

Video provenance is an important problem on the modern internet. In response, the Coalition for Content Provenance and Authenticity (C2PA) has developed a standard for verifying video and image provenance where cameras sign captured videos with an on-device secret key. Since videos are generally edited and resized before be- ing posted, the C2PA signature from a camera cannot be used as is to verify provenance of published videos. Prior work has developed zero-knowledge techniques for verifying provenance of edited im- ages and videos. In this work, we develop new efficient techniques for producing such zero-knowledge proofs. First, we show how to represent common video edits as matrix multiplications in a form that is particularly friendly for zero-knowledge provers and enables a number of optimizations. Second, we develop a SNARK-friendly video representation, which we call sfvr, that reduces prover work for video editing. Third, we design new efficient methods for incor- porating signed data into a SNARK proof. To evaluate our designs, we built an end-to-end system for proving edits to a signed video. In our end-to-end system, we optimize the NeutronNova folding scheme for high-arity folding. To scale the size of our Neutron- Nova proofs, we implement a “Read-Write Streaming” version of NeutronNova to take advantage of high-performance storage and parallel computing resources. Our system achieves competitive performance and scale relative to prior work.

We present randomized algorithms for the shortest vector problem (SVP). For the $n$-dimensional lattice $\mathcal L$, our algorithms solve SVP in time $2^{0.6039n+o(n)}$ classically and $2^{0.5411n+o(n)}$ quantumly and space $2^{0.5n+o(n)}$, improving the previous best algorithm running in $2^{n+o(n)}$ time and space of Aggarwal, Dadush, Regev, and Stephens-Davidowitz [STOC'15].

Our algorithms heavily use the property of the Hessian of the periodic Gaussian function at the half shortest vector: For a shortest vector $v \in \mathcal L$, the Hessian at $v/2$ has the eigenvector close to $v$, which can be used to recover $v$ using the (preprocessing) bounded distance decoding algorithm. Given the periodicity modulo $\mathcal L$, the candidate midpoints are indexed by the parity classes in $\mathcal L/2\mathcal L$. Our algorithm searches for the class of a shortest vector by estimating the corresponding Hessians using discrete Gaussian samples.

We optimize the algorithm using random sublattice cosets and various sampling technique, achieving the final complexity. The optimization techniques may be of independent interest.

Payment Channel Hub (PCH) improves blockchain scalability by enabling off-chain transactions via an untrusted intermediary known as the tumbler. However, existing PCHs either fail to guarantee the unlinkability privacy or rely on inefficient non-interactive zero-knowledge (NIZK) proofs. Recently, Ge et al. proposed Accio, a privacy-preserving PCH that eliminates the need for NIZK proofs. Nevertheless, Accio only supports unidirectional channels which results in high on-chain costs and routing inefficiencies. In this paper, we present Baker, the first bidirectional payment channel hub that operates without NIZK proofs and guarantees unlinkability. Unlike prior PCH solutions that maintain channel balance using a single state, Baker introduces a novel design in which each non-tumbler user maintains two separate pockets to record the channel balance. To ensure payment atomicity, Baker further designs a novel cryptographic primitive named Aggregatable Adaptor Signature (AAS) to enable atomic signature exchanges and signature aggregation. We implement Baker and empirically demonstrate its advantages over state-of-the-art protocols. Compared to BlindHub, which relies on NIZK proofs for privacy, Baker reduces off-chain communication overhead to 0.0036%. Moreover, the off-chain computation overhead of Baker is 7% of that of BlindHub and 40% of TBPChannel. Relative to Accio, Baker incurs only 80% of its on-chain cost and enjoys a 25% higher average transaction success rate.

Neural differential distinguishers are usually compared at a fixed number of labeled samples. However, different input representations may require different numbers of ciphertexts per sample, making fixed-sample comparisons potentially misleading from a cryptanalytic data-complexity perspective. In this paper, we study neural differential distinguishers under a fixed ciphertext budget. We ask whether the available encryption queries should be spent on more independent plaintext bases, or on richer samples containing more ciphertext-difference rows.

We introduce a shared-base multi-difference representation in which several input differences are applied around the same plaintext base, and compare it with the standard single-difference baseline and an independent-pair control representation. Experiments on GIFT-64, PRESENT-64, RECTANGLE-64, and SPECK-64/128 show that the single-difference baseline is rarely the best fixed-budget allocation. Adding more difference rows often improves the distinguisher even though it reduces the number of independent training samples. At the same time, the optimal number of rows is not universal: logistic regression often benefits from larger representations, while a multilayer perceptron frequently prefers intermediate values due to sample-starvation and overfitting.

We further test several non-adaptive difference sets and observe that the main trend is not tied to a single hand-picked set. The results suggest that the number of differences per sample should be treated as an explicit design parameter in neural differential cryptanalysis, and that fixed-budget evaluation is necessary for comparing richer neural distinguisher inputs fairly.

Witness encryption (WE) allows one party to encrypt a message under an arbitrary satisfiable circuit, so that anyone holding a satisfying input can decrypt. Efficient WE enables numerous modern applications, such as identity-based and attribute-based encryption.

Recent candidates for efficient WE base their security on rank properties of structured ciphertext matrices, which encode the validity of a given witness. This shrinks ciphertext sizes considerably compared to previous constructions, but rests on heuristic arguments rather than security reductions.

We describe two attacks against two such constructions, namely the affine determinant program (ADP) construction from 2020 and its arithmetic extension, the AADP, from 2026. The first attack observes that for sparse circuits, the natural regime for both schemes, commutators formed from the public ciphertext matrices have unexpectedly low rank. Elementary linear algebra on these matrices then recovers the encrypted message directly from the public ciphertext, without knowledge of any witness, and hence breaks the security of both schemes. The second attack linearizes the nearly-skew-symmetric (NSS) variant of the ADP construction, recovering the encryption randomness and the message. To our knowledge, ours are the first attacks against these WE candidates, and we verify both in practice.

HAWK is a lattice signature scheme that is currently a third-round candidate in NIST's post-quantum signature competition. We give an unconditional, deterministic polynomial-time reduction from HAWK-$n$ key recovery over $K_n=\mathbb{Q}(\zeta_{2^\ell})$ to $\mathrm{poly}(n)$ calls to an exact Shortest Vector Problem (SVP) oracle in dimension $n/2+1$, where $n=2^{\ell-1}$ is the ring degree. The reduction uses a nontrivial automorphism of the key lattice, supplied by the Galois involution $\tau:\zeta\mapsto-\zeta$ and recoverable as a shortest vector of a public rank-$n$ lattice isometric, up to scaling, to $\mathbb{Z}^{n/2+1}\oplus\sqrt{2}\,\mathbb{Z}^{n/2-1}$. Ducas's block reduction on this near-hypercubic class finds the automorphism, and the descent of van Gent and Pulles recovers the key from it. In the gate-count model, the attack lowers the key-recovery cost of HAWK-512 from $2^{150}$ to $2^{108}$ and of HAWK-1024 from $2^{288}$ to $2^{182}$. We demonstrate this with a practical implementation that recovers a HAWK-256 secret key end-to-end in a few hours on a single server. The construction does not transfer to Falcon. Conductors $m\in\{p^k,2p^k\}$ ($p$ an odd prime), i.e.\ the $m>4$ with cyclic $(\mathbb{Z}/m)^\times$, evade the attack.

This paper analyzes the bilinear embedding of matrix algebras into commutative cyclotomic rings. We apply the Cohn-Umans method. This establishes that single-multiplication bilinear monomial embeddings require a ring degree of $\widetilde{\Omega}(N^3)$. We circumvent this bound by routing Strassen tensor rank decompositions through orthogonal Chinese Remainder Theorem ideals. This reduces the asymptotic complexity to $\widetilde{\Omega}(N^{\log_2 7})$. We optimize the coprime tensor decomposition. Embedding the inner tensor into the maximal real subfield satisfies the Lempel-Weinberger parity constraint. This guarantees the existence of a Self-Dual Normal Basis, reducing the required basis generators to a single element and mathematically halving the homomorphic trace depth. Canonical integer polynomial lifts ensure uniform norm bounds. Type I Optimal Normal Bases bound the trace dual expansions to an $O(1)$ constant. By invoking Kronecker's theorem, we prove that the polynomial power basis minimizes the canonical expansion for the non-evaluated tensor components. A towered evaluation over composite degrees controls noise propagation. This decouples key-switching errors into a logarithmic bound. We generalize the embedding to Galois rings via Hensel's and Nakayama's lemmas to support high-precision integer arithmetic. Furthermore, we extend the architecture to boundless matrices exceeding the fixed ring capacity via a multi-ciphertext block-Strassen decomposition. By deferring the homomorphic trace operator to post-Strassen recombination, we completely eliminate homomorphic basis-switching, achieving an asymptotic complexity of $O(N^{\log_2 7 - 1/\rho})$ multiplications and $\widetilde{O}(N^{2 - 2/(\rho \log_2 7)})$ automorphisms for matrices of arbitrary dimension. Empirical benchmarks over the BGV scheme validate the approach. A multi-threaded towered trace evaluates $32 \times 32$ matrices in $141.3$ milliseconds at a security level of $\lambda=148$ using one ciphertext-ciphertext multiplication. We achieve a speedup factor of $2.49$ over multi-threaded baselines.

We present a polynomial-time quantum algorithm for the Dihedral Coset Problem (DCP). The algorithm is based on Regev's polynomial-time reduction of the Dihedral Subgroup Problem (DSP) to the modular subset sum problem, but uses a different technique to erase sample bits without use of a subset sum oracle. The algorithm can thus combine with Regev's reduction of lattice problems to DCP, improved by Brakerski, Kirshanova, Stehl{\'e} and Wen, to yield polynomial-time quantum algorithms for various lattice problems, such as finding a polynomial-factor approximation to the shortest vector in an $n$-dimensional lattice (SVP), and the ``learning with errors'' problem (LWE). The algorithm can tolerate a faulty sample rate as high as $1/O(\log{n})$, allowing the algorithm-reduction combination to efficiently solve, for example, SVP with a $\sqrt{n}$ polylog($n$) approximation factor, or LWE instances with $\alpha=\sqrt{n}$ polylog($n$).

Oblivious Key-Value Stores (OKVS) (Garimella et al., CRYPTO 2021), once encoded, provide indistinguishability over keys and random values. This is an important property in many secure computation applications, such as private set intersection and multi-key searchable encryption. We introduce an Updatable Oblivious Key-Value Store with access control (UOKVS), a dynamic extension of OKVS that supports insertions over time. We provide meaningful security in the presence of updates by equipping UOKVS with fine-grained access control. As a building block in UOKVS, we provide the first analysis of oblivious insertions for Cuckoo hashing, which may be of independent interest.

We show the application of UOKVS to multi-key searchable encryption where a data owner wishes to share parts of a multimap with multiple clients. We construct an oblivious multimap with insertions from UOKVS and private information retrieval (PIR). Unlike prior multi-key searchable encryption schemes, our construction supports sharing without replicating data across authorized users, substantially reducing storage costs in addition to stronger privacy guarantees.

We implement our multi-key searchable encryption construction on a dataset containing up to 24 million entries using the Enron email dataset. For keywords matching 100 documents on a WAN, query processing completes in $0.6$ seconds using FrodoPIR as the underlying PIR protocol. By comparison, the scheme of Wang and Papadopoulos (Cloud Computing 2023) achieves a query time of $0.6$ seconds and also incurs data replication and leaks access patterns. Our construction reduces leakage, maintains performance, and only requires a $3.1$x storage overhead.

We investigate a multi-prime multi-power generalization of the RSA cryptosystem for arbitrary moduli $n>1$, which under reasonable cryptographic assumptions works correctly for almost all messages $m

Boolean polynomial multiplication is the primary computational bottleneck of the Hamming Quasi-Cyclic (HQC) key encapsulation mechanism. In this paper, we reframe the Frobenius Additive FFT (FAFFT) in ring-theoretic terms, via quotient-ring homomorphisms and the Chinese Remainder Theorem. This perspective shows that a complete decomposition into evaluation points is unnecessary for multiplication, and naturally yields the Strided FAFFT (SFAFFT), which operates over smaller finite fields with fewer butterfly stages and admits a much sparser CRT modulus for the non-power-of-two degrees in HQC. Our SFAFFT implementations outperform all previous FAFFT-based multiplications on every tested platform (x86 AVX2, GFNI, Apple M1, ARM Cortex-A72, and Cortex-M4), and set new overall speed records for HQC in nearly all settings except plain AVX2, where Toom-Cook-Karatsuba remains faster for the two smaller parameter sets.

We give a classical randomized algorithm for the exact Euclidean Shortest Vector Problem (SVP) on arbitrary full-rank lattices. It runs in $2^{0.7314n+o(n)}$ time and$2^{n/2+o(n)}$ space. More precisely, it returns a shortest vector with high probability and runs in $$ 2^{E_0n+o(n)} \quad\text{time and}\quad 2^{n/2+o(n)} \quad\text{space}, \qquad E_0=0.73133754\ldots . $$ This improves the $2^{n+o(n)}$ classical bound of Aggarwal, Dadush, Regev, and Stephens-Davidowitz (ADRS, STOC 2015). It also beats the previous best known worst-case quantum bounds of Aggarwal, Chen, Kumar, and Shen (ACKS, SIAM J.Comp. 2025), namely $2^{0.9497n+o(n)}$ without QRAM and $2^{0.8345n+o(n)}$ with QRAM.

The algorithm constructs a random prime-index superlattice $\Gamma\supset L$ and applies the above-smoothing honest discrete Gaussian sampler of ADRS to $\Gamma$. Then it simply scans the resulting samples and retains the shortest nonzero one that lies in $L$.

The analysis passes to the dual lattice $M=\Gamma^*$. The random codimension-one constraint reduces the expected contribution of vectors outside $pL^*$ by a factor smaller than $1/p$, while the forced Gaussian mass on $pL^*$ is controlled geometrically using the Kabatiansky--Levenshtein sphere-packing bound. Consequently, $\Gamma$ is smooth at the sampling scale and a fixed shortest vector of $L$ is hit with probability at least $2^{-E_0n-o(n)}$ per ideal sample.