International Association
for Cryptologic Research

The Signal protocol is used by billions of users daily and recognized as the gold standard for end-to-end encrypted messaging. Its initial handshake protocol X3DH uses XEdDSA to sign its semi-static key and allows parties to derive a session key asynchronously. The protocol is implemented over Curve25519, relying on the assumed 128-bit hardness for solving Discrete Logarithms (DL). Previous non-tight reductions incur a large loss in the number of sessions, and the resulting concrete security guarantees fall far below the intended 128-bit security level. This motivates the development of tight security bounds for these protocols.

In this paper, we improve the security analysis of X3DH and its recent enhancement XHMQV (Fiedler et al., CRYPTO'25) by providing tight security reductions under multi-user Diffie–Hellman (DH) assumptions (Kiltz et al., CT-RSA'23) in the Random Oracle Model. Unlike prior work, our proofs are in the more realistic multi-Test setting. The variant of X3DH that we analyze hashes additional context into the session key. Although this modification is minor, it yields tight security bounds and provides a stronger justification for the use of Curve25519. In light of our results, the Signal developers plan to adopt the same modification.

The Signal protocol is a prominent messaging protocol that se- cures communication for billions of users. It powers WhatsApp, the most widely used messaging application worldwide, and the Signal app, popular among privacy-conscious users. Extensive re- search in the computational and Dolev-Yao settings provides strong formal security guarantees for the protocol itself. However, a gap remains between the guarantees of the protocol specification and the implementation’s actual behavior at runtime.

In this work, we bridge this gap by applying SpecMon, a recently proposed runtime monitor, to check whether observed executions conform to formal protocol models. To this end, we instrument two applications (WhatsApp Web and Signal Desktop) to capture their interactions with the network and the cryptographic components. Using this instrumentation, we develop two multiset-rewrite models that are compatible with Tamarin, thus enabling verification. We derive the first model of WhatsApp Web’s implementation of the Signal protocol and the most detailed model to date of Signal’s original protocol. Monitoring establishes that observed executions conform to these models, relative to the trusted event extraction and the symbolic abstraction. For the core components of the Signal protocol, we verify authentication and secrecy properties. Finally, monitoring reveals previously undocumented differences between the original libsignal library and WhatsApp’s fork.

We evaluate our methodology and demonstrate its reproducibil- ity. Developing the WhatsApp Web model, instrumenting the app, adding fuzzing, and running the experiments took three person- weeks. We also demonstrate efficient monitoring of real-world applications and detection of deliberately injected security faults, with low overhead in our measured setting.

We introduce new two-party threshold signature schemes with strong efficiency and security. The application of our methodology to the two most popular signatures, Schnorr and ECDSA, yields two-round, two-party, stateless and deterministic signing with 4-12 ms of computation on one core of a standard laptop, extremely low communication -- 96 B for Schnorr, and 128 B for ECDSA -- and full concurrent simulatable security. At the heart of our approach is a new pseudorandom correlation function (PCF) for vector-OLE that admits an efficient key generation protocol; we design an end-to-end maliciously-secure and highly parallelizable DKG for this PCF and, using this DKG, we obtain an estimated runtime of 44 s for the (one-time) distributed setup of Schnorr and ECDSA on one core of a standard laptop.

We present a lattice-based construction of secret-key functional encryption (FE) for low-norm polynomials of any constant degree $d$, hence also for $\mathsf{NC}^{0}$ circuits. We rely on two core ingredients: 1. New trapdoor and preimage sampling algorithms for certain degree-$d$ tensor-structured matrices, used to generate functional secret keys. 2. A new $k$-LWE-style assumption where short preimages of non-zero images with respect to the above tensor-structured matrix are given as hints, under which we prove that our secret-key FE scheme is selectively secure (under unbounded collusion). To gain confidence in the new assumption, we prove that the standard LWE assumption implies the degree-$1$ case and cryptanalyse the $d > 1$ case.

As a corollary, we obtain a new pathway to post-quantum secure indistinguishability obfuscation (iO), conditioned on the above new assumption, standard LWE, and the existence of polynomial-stretch pseudorandom generators in $\mathsf{NC}^{0}$. Along the way, we give a new, simple (public-key) FE scheme for linear functions with selective security under the standard LWE assumption.

The M operation was introduced by Yura as an alternative to the max operation appearing in the box-ball system (BBS) to construct a BBS over finite fields. The Me operation is a version of the M operation for an elliptic curve $E$ over a finite field ${\mathbb F}_p$. As with the M operation, the Me operation satisfies the idempotent law and does not satisfy the associative law. Nevertheless, for $P,Z \in E({\mathbb F}_p)$ and $n \in {\mathbb N}$, the 1st Me-scalar multiplication $P_{n,Z}^{\,I}$ with auxiliary element $Z$ can be defined. Moreover, for $P,Z \in E({\mathbb F}_p)$ and $n \in {\mathbb Q}_+$, the 2nd Me-scalar multiplication $P_{n,Z}^{II}$ with auxiliary element $Z$ can be defined. This paper shows the following properties that may be useful to construct cryptographic protocols: $(P_{n_0,Z}^{\,I})_{n_1,Z}^{\,I}=(P_{n_1,Z}^{\,I})_{n_0,Z}^{\,I}$, $(P_{n_0,Z}^{II})_{n_1,Z}^{II}=(P_{n_1,Z}^{II})_{n_0,Z}^{II}=P_{n_0n_1,Z}^{II}$; the 1st MeDLP and the 2nd MeDLP, which are Me versions of the ECDLP, are difficult to solve on classical computers under certain conditions; the 1st MeCDH and the 2nd MeCDH, which are Me versions of the ECCDH, are NOT difficult to solve; and the sequence $\{ P_{n,Z}^{II}:n=1,2,3,\ldots \}$ is nonperiodic unless it is constant.

An anonymous messaging service has to solve a basic routing problem: a server must deliver an encrypted message to its recipient without learning who the recipient is. Broadcasting all ciphertexts hides the destination but forces every recipient to constantly scan for new messages. Oblivious Message Retrieval (OMR; CRYPTO~'22) tackles this by using fully homomorphic encryption (FHE) to let an untrusted server perform message retrieval on a recipient's behalf without learning which messages are pertinent.

We introduce Oblivious Signaling, which shifts this cost from retrieval to sending. The server maintains a fixed-size encrypted inbox for each recipient. When a sender submits a message, the server applies the same homomorphic update to every inbox: the intended inbox absorbs the message, and the rest remain unchanged at the plaintext level. The update is uniform, can be parallelized across inboxes, and ties the delivery cost strictly to the size of the anonymity set rather than global traffic. Recipients retrieve by fetching and decrypting their inbox, so checking for new messages is independent of the global traffic.

We formalize receiver privacy against an untrusted server, even when it colludes with other users, give a concrete construction based on fully homomorphic encryption, and analyze the resulting "digital postage'' trade-off: delivery is expensive, but checking is cheap. Our prototype identifies practical regimes in which this cost-model shift is preferable to scan-based retrieval, even with highly optimized OMR implementations. This cost model is well-suited to settings where recipients check frequently, and messages arrive sporadically, and it naturally discourages high-volume spam.

Arithmetic response existence is a prerequisite for signing, but is not implied by a large number of bounded-degree isogenies. We study how endpoint collisions, exact level-structure constraints, and sampling dependence affect this existence problem for supersingular curves in characteristic $p$. For every binary degree filter independent of the endpoints and every $1 \le D < p$, we prove the mean-square endpoint discrepancy bound $\mathcal{V}_a \ll_\delta p^\delta(D^2 + D^{7/2}/p) + P_a^2/p^2$, where $P_a$ counts the allowed cyclic kernels on each source curve. The proof combines square-divisor inversion with classical Brandt–Hecke and harmonically weighted Petersson estimates. Filters with $P_a \ge cD^2$ for fixed $c>0$ give existence probability $1-o(1)$ for independent uniform endpoints above $p^{1/2+\gamma}$; every filter gives $o(1)$ below $p^{1/2-\gamma}$, for fixed $\gamma>0$. The Weil pairing converts the two cosets of the kernel of the quadratic determinant character into degree filters. Combining this observation with an exact-coset incidence bound yields opposite existence probabilities at the same degree bound: $1-o(1)$ for this subgroup and $o(1)$ for split and nonsplit Cartan normalizers, although all three induce the same additive Hom-lattice condition. These are idealized experiments with different challenge-space sizes. We also give challenge-preserving primitive reduction and explicit joint-distribution transfer conditions.

MDS matrices are a key structure for providing optimal diffusion in symmetric primitives. However, the theoretical analysis of their cost remains limited. This issue is particularly relevant to arithmetization-oriented permutations, where designs often either use costly MDS matrices or sacrifice the MDS property to reduce the number of constraints.

This paper studies the number of fan-in-two additions needed to implement MDS matrices. We represent fan-in-two addition constraints by a directed acyclic graph and derive lower bounds on the number of additions using the established result that any such computation graph implementing an MDS matrix must be a superconcentrator.

Building on size-reduction lemmas for superconcentrators, we present a recursive algorithm that improves both lower and upper bounds for $t\times t$ matrices with $t\leq 8$. As a result, we obtain explicit MDS matrices over large primes for $t=3,4,5,6,7,8$, requiring $5,8,12,16,21,26$ additions, respectively. These bounds are tight for $t\leq 6$. We also use the same superconcentrator graphs as templates for MDS matrices with $k$-bit words. For $t=5,6,7$, our matrices require fewer XORs than the state of the art for most considered parameter choices in this line of work.

It has been known for two decades that performing compression before encryption is dangerous, because it introduces a side channel leaking information about plaintexts through ciphertext lengths: the compressed plaintext length may be visible in the ciphertext length, and the amount of compression obtained is plaintext-dependent; hence an adversary can obtain some leakage about the plaintext via observation of ciphertext lengths. This issue was first pointed out by Kelsey (FSE 2002) and turned into a practical plaintext recovery attack in the form of the CRIME attack on SSL and TLS by Rizzo and Duong in 2012. A long series of variations and attacks against other systems followed. Despite the known dangers, the compress-then-encrypt paradigm is still prevalent in practice today. This may be because the compression-based side channel is susceptible to noise and may require a large number of queries to enable plaintext recovery, and so can be mitigated by either adding noise (e.g. with random padding) or limiting an adversary's interaction with the system.

We demonstrate that this side channel is much more powerful than previously thought. We focus on the widely-used DEFLATE algorithm in our analysis. We present novel techniques that enable strong amplification of small length differences arising during compression. Our telescoping and chaining amplification techniques exploit the way in which DEFLATE replaces common strings by shorter back-references. Our collision-based amplification technique focusses on exploiting hash table collisions in DEFLATE implementations. This involves a deeper examination (and exploitation) of the internals of DEFLATE than in previous works. These insights result in compressed length differences growing linearly with the length of queries. Compared with length differences of a few bits or bytes in prior work, our new amplification techniques thus enable us to defeat existing noise-based countermeasures.

Finally, we introduce the concept of CRIME automata, these being carefully crafted query strings that enable an attacker to exert fine control over the internal behaviour of DEFLATE and produce differences in the output lengths of the compressor according to various criteria (such as whether the DEFLATE sliding window contains a given target string). In turn, our automata are composed in a modular fashion from gadgets having different functions, including matching against target strings, performing logical operations between other gadgets, and, most importantly, amplifying differences in output lengths using the above-mentioned techniques. We provide multiple, concrete automata designs that serve different attack goals. These designs are supported by experiments and a publicly available codebase demonstrating the power, flexibility, and practical impact of our CRIME automata approach.

Jafari and Khazaei (Journal of Cryptology, 2021) introduced a kernel-based lower-bound method for linear secret-sharing schemes by fixing one minimal qualified coalition and comparing its participant components with those arising from auxiliary minimal qualified coalitions. These comparisons form a star. We extend the same mechanism from stars to coalition-labelled trees and obtain new characteristic-two inequalities for the relaxed-line non-Fano port $\widehat N$. For this access structure, the tree method is strictly stronger than the star method, yielding facet inequalities not implied by the star inequalities. We also show that the tree method does not determine the full contribution region.

To complete the analysis of $\widehat N$, we introduce component-dual compression (CDC). CDC replaces each share by the span of the components selected from minimal reconstructions and realizes the duals of these compressed spaces in a common coordinate system indexed by the original minimal coalitions. This yields the remaining lower-bound inequalities. Together with matching constructions, the star, tree, and CDC bounds determine the complete characteristic-two linear contribution region of $\widehat N$, with maximum and average linear information ratios $5/4$.

In this paper, we revisit the design of multi-party distributed point functions (DPFs) and make several new contributions that advance the state of the art. We begin by revisiting security amplification, a fundamental tool underlying many DPF constructions. In particular, the recent landmark work of Goel, Wang, and Wang (CRYPTO'25) critically relies on security amplification and, for a general polynomial number of parties, gives the only known construction based on one-way functions (OWFs) that achieves sublinear dependence on the input domain size. Unfortunately, due to a known gap in the proof of the security amplification theorem of Boyle et al. (CRYPTO'22), we currently still lack a fully established security amplification theorem for DPFs.

We fill this gap by providing a new proof of security amplification for DPFs with tight parameters. Equipped with this security amplification theorem as a key technical tool, we develop several new techniques that asymptotically improve the communication cost of multi-party DPFs in both the honest-majority and corrupt-majority settings. Our main results are summarized below, where $N$ denotes the input domain size, $m$ denotes the number of parties, and $t$ denotes the corruption threshold:

In the all-but-one-corrupt setting, we describe a new scheme based on OWFs with $\widetilde{O}_\lambda\left(N^{\frac12 + \epsilon} \cdot \sqrt{m}\right)$ share size where $\epsilon > 0$ is an arbitrarily small constant. In comparison, the best previously known OWF-based construction due to Goel et al. incurs $\widetilde{O}_\lambda\left(N^{\frac12 + \epsilon}\cdot m^3\right)$ share size.

In the honest-majority setting, assuming $m > (1+\epsilon)D t$ for some integer $D \ge 2$ and arbitrarily small constant $\epsilon > 0$, we construct a new OWF-based scheme with share size $\widetilde{O}_\lambda(N^{\frac{1+\epsilon}{2D}})$, as well as an information-theoretically secure scheme with share size $\widetilde{O}(N^{1/D})$. Both constructions achieve an exponential factor improvement in their dependence on $m$ and $t$ compared to the state-of-the-art schemes of Bunn, Kushilevitz, and Ostrovsky.

Solving multivariate polynomial systems is a fundamental problem in cryptanalysis, with increasing relevance in algebraic attacks on arithmetization-oriented (AO) primitives. Current approaches primarily rely on Gröbner bases or the Sylvester resultant. However, Gröbner basis methods typically rely on FGLM to change the monomial order, which applies only to zero-dimensional ideals, whereas the Sylvester resultant eliminates only one variable at a time, limiting its flexibility in multivariate elimination.

We revisit the Dixon resultant as an efficient and flexible tool for eliminating several variables simultaneously. We derive refined upper bounds on the Dixon matrix size via lattice-path counting and analyze the complexity under several determinant computation models, yielding explicit complexity estimates. For well-determined systems, the Dixon resultant is a viable alternative to Gröbner basis methods; moreover, it is attractive for elimination in underdetermined systems, whereas Gröbner basis methods remain preferable for overdetermined ones.

We present an efficient open-source C implementation, DRSolve, with multiple determinant methods and a degree-aware submatrix selection strategy to mitigate the impact of extraneous factors. Experiments show that our implementation is competitive with the state-of-the-art Gröbner basis solvers Magma and msolve on randomly generated well-determined systems, with significant advantages in the low-variable/high-degree regime, while Magma and msolve remain preferable in the high-variable/low-degree regime.

Finally, we formulate three elimination strategies for polynomial systems arising from AO primitives: direct elimination, iterative elimination, and reduction-based hybrid elimination. We demonstrate these strategies on Poseidon, Vision, and Xhash12, yielding complexity reductions in many cases.

We study rounding error in the Closest-Vector Problem (CVP) over cyclotomic lattices of arbitrary order \(m\), motivated by its role in approximate homomorphic encryption (HE), where lattice-based rounding directly affects the noise and precision of key operations. For the worst-case analysis, we derive a new covering-radius upper bound. For the average-case analysis, we study the efficient approximate solution given by Babai’s nearest-plane algorithm, whose error upper bounds that of exact nearest-point rounding. For an arbitrary lattice and a target sampled uniformly from a fundamental domain, we show that Babai’s error has independent uniform coordinates in the Gram–Schmidt basis. This determines its mean-squared error (MSE); for cyclotomic lattices, we further show that the squared error concentrates around its mean. Using the tensor decomposition of cyclotomics, we express our bounds in terms of the prime-power decomposition of \(m\), revealing provably improved rounding for non-power-of-two cyclotomics over their power-of-two counterparts while retaining efficient arithmetic for broad families of indices. We apply these results to approximate HE, where improved rounding-error bounds inform the choice of encryption parameters. Our concrete evaluation yields parameter choices with simultaneously smaller lattice dimension and ciphertext modulus at fixed output precision and target security level, illustrating the potential of non-power-of-two cyclotomic rings for approximate HE.

Deep neural networks (DNNs) are increasingly used in sensitive applications, where certifying properties such as adversarial robustness and fairness is crucial. Several recent works propose DNN certification systems using zero-knowledge proofs (ZKPs)— cryptographic primitives that allow verifying certificates while maintaining confidentiality of the model. While certification algorithms typically treat the DNN as a function over reals, naively translating these algorithms into finite-precision implementations can result in unsound certification due to rounding errors. In ZKPs, this unsoundness is amplified due to a larger precision loss from fixed-point arithmetic emulated using finite fields. In this work, we highlight an overlooked gap in the soundness of prior protocols. We propose AZKABAN, a system for zero-knowledge abstract interpretation-based analysis with end-to-end soundness. We introduce operators for sound interval analysis over finite-fields, including efficient ZKP-amenable algorithms for inner-products and division, while preventing privacy leaks due to non-linear activations. We implement our system which is comprehensive in terms of supporting both feed-forward and convolutional neural networks. AZKABAN improves over the state-of-the-art ZK individual fairness certification protocol by up to two orders of magnitude in end-to-end proof time. Further, it scales to much larger models than those considered in the state-of-the-art. AZKABAN also provides, to our knowledge, the first solution for ZK robustness certification.

Strong designated-verifier signatures provide authentication while restricting verification to a chosen verifier and protecting the signer from transferable evidence. Designing such signatures in the post-quantum setting is challenging because authentication, signer privacy, simulation, and efficiency must be achieved simultaneously. Recently, Renan proposed CSI-SDVS, a compact post-quantum strong designated-verifier signature scheme built from CSIDH-style commutative isogeny class-group actions. We show that its response design, $z_i=b_i-s_i$, breaks privacy of the signer's identity: because the PSI experiment reveals both candidate signer secret keys, an adversary can reconstruct the signing randomness and identify the actual signer with overwhelming probability. We validate the attack over 30,000 executions, obtaining 100\% signer identification in the main 128-bit experiment and for $\eta\in \{1,2,4,8\}$. In the following, we propose an isogeny-based strong designated verifier signature. We prove correctness, non-transferability, signer privacy, and strong unforgeability under Gap Parallelization in the random-oracle model. For $\eta=1$, the redesigned signature is 113 bytes compared with 49 bytes in CSI-SDVS, while signer key sizes remain unchanged.

Since the introduction of Threshold Traitor Tracing by Boneh, Partap and Rotem at CRYPTO '24, several works have extended the functionalities within the framework or improved the parameters. However, most of the existing solution fall short in providing post quantum security guarantees. The only lattice-based construction, due to Das et al. from EUROCRYPT '26, achieves post-quantum security but is limited to private tracing: a dedicated tracing authority holds a secret tracing key. In a threshold system, where the fundamental goal is to distribute trust, such a single point of failure is undesirable. In this work, we construct the first threshold traitor tracing scheme that simultaneously achieves post-quantum security and public traceability, where anyone can trace a pirate decoder without any secret tracing key. Our core building block is a Q-Partite Threshold Public Key Encryption (QTPKE) scheme, which is known to imply threshold traitor tracing when combined with a robust IPP code: we build QTPKE from plain Learning With Errors (LWE) using a key-shifting mechanism on top of Regev's encryption scheme thresholdised via {0,1}-Linear Secret Sharing. We finally prove the security of our scheme in the standard model under standard lattice assumptions.

Non-malleable zero-knowledge argument(NMZK) is a strong notion of zero-knowledge argument that ensures security against man-in-the-middle(MIM) attacks. While three-round constructions exist for various weak zero-knowledge arguments under standard assumptions, all known (weak) NMZK protocols in the plain model have required at least four rounds.

In this work, we construct the \emph{first three-round weak non-malleable zero-knowledge argument} under standard cryptographic assumptions. Our protocol satisfies weak zero-knowledge and $\epsilon$-non-malleability, where the latter allows an $\epsilon$ probability gap between the MIM experiment and the stand-alone experiment for any polynomial inverse $\epsilon$. Our construction relies only on well-established primitives, such as the existence of two-message oblivious transfer protocols and delayed-input WI arguments, non-interactive commitments, and circuit-privacy fully homomorphic encryptions.

Block ciphers including several variants of the well-known \textsf{AES}, the newly proposed tweakable block cipher \textsf{Deoxys-BC} (standardized by ISO/IEC and renamed Deoxys-TBC), and \textsf{ChiLow} (EUROCRYPT 2025) adopt key sizes larger than their block sizes. These designs offer security higher than the block size. This paper evaluates the security of such ciphers by revisiting the Impossible Polytopic Attack (\ipa{}, proposed by Tyge Tiessen at EUROCRYPT 2016). We show that \ipa{} can build longer-round distinguishers, enabling attacks on more rounds. Moreover, the attack is applicable under the known-plaintext (KP) setting. Towards this end, we first formalize the distinguisher from Tiessen’s original work and establish a generic framework for distinguisher construction. We further propose two novel methods to lower the corresponding construction complexity. Moreover, we develop two dedicated key-recovery techniques, namely the plaintext‑grouping technique and the partition-guess-filter technique. The former allows cryptanalysis on more rounds of target ciphers, while the latter substantially lowers the overall attack complexity. Finally, we build the first framework for \ipa{}. We apply our method to the chosen-plaintext/ciphertext (CP/CC) and KP scenarios under the single-key setting. As a result, we obtain new distinguishers and attacks against \textsf{AES}, \textsf{Deoxys-BC}, \textsf{Joltik-BC}, \textsf{LED-128}, and \textsf{ChiLow-32}. Notably, 10-round attacks are constructed on \textsf{Deoxys-BC-384} and \textsf{Joltik-BC-192}. Compared with impossible differential attacks, which are closely related and extensively studied, the proposed results outperform such attacks by one round. Furthermore, a novel full-round attack on \textsf{ChiLow-32} is constructed under the KP setting, achieving the state-of-the-art attack with optimal data complexity and overall complexity.

Lattice extraction often produces openings normalized by challenge differences, whereas an inconsistency must ultimately yield a short integral SIS relation. Clearing each extracted branch before comparison removes every denominator obstruction carried by that branch, including factors irrelevant to the mismatch that is eventually tested.

We formalize direct integral comparison for generic polynomial block systems. If block \(a\) has width \(r_a\) and the two extraction centers differ on \(J\), the minimum worst-case coefficient degree is \(\max\{\max_a r_a,\sum_{a\in J} r_a\}\). Within a branch-separated polynomial integralize-then-compare architecture, it is \(2\sum_a r_a\). The coordinate case gives \(\max\{1,h\}\) and \(2L\), where \(h=|J|\).

Exact conditional resampling obtains the required partially synchronized successful executions without a reciprocal-success loss. The coordinate schedule uses at most \(2L+1\) additional retry invocations in unconditional expectation.

Two cases illustrate the bounds. For Cyclo-style coordinate folding, one unsynchronized coordinate has the same certified radius as same-root synchronization. For two independently extracted Esgin-style Vandermonde stars, direct comparison has degree \(\binom{k+1}{2}\) in the anchor-universal polynomial-linear model. The degree is \(k^2\) within the stated branch-separated integralize-then-compare architecture.

MACsec Key Agreement (MKA) is the IEEE 802.1X key-management protocol used to establish and maintain Secure Associations for MACsec deployments. Although MKA is widely deployed, machine-checked analyses of its core key-agreement logic remain scarce. This paper presents a formal analysis of a simplified two-party MKA exchange using the Tamarin prover. We model the initial session establishment and a subsequent rekey round, and verify secrecy, authentication, agreement, ordering, and freshness properties. The analysis confirms these guarantees under a Dolev--Yao adversary when the pre-shared Connectivity Association Key (CAK) is not compromised. We also identify a structural weakness: a malicious or compromised Key Server can inject an arbitrary Secure Association Key (SAK) that the Server accepts. This finding clarifies the trust assumptions of MKA and motivates additional verification or binding mechanisms for partially trusted deployments.