International Association
for Cryptologic Research

Proof-carrying data (PCD) is a powerful cryptographic primitive for ensuring computational integrity in distributed settings. State-of-the-art PCD constructions based on accumulation schemes achieve practical prover efficiency and support a wide range of applications. However, realizing zero-knowledge for accumulation-based PCD remains challenging, particularly for high-degree relations. Existing solutions often incur substantial overhead due to the need for zero-knowledge in both the underlying non-interactive arguments of knowledge (NARKs) and accumulation schemes. In this work, we present new theoretical and practical improvements for zero-knowledge PCD. First, we propose a novel construction that eliminates the need for zero-knowledge NARKs by separating the compliance predicate and accumulation verification, thereby reducing proof size and improving efficiency. Second, we design an efficient zero-knowledge accumulation scheme for special sound protocols, introducing techniques such as masking vectors and zero-knowledge sum-check protocols to ensure privacy with minimal overhead. The theoretical analysis demonstrates that our construction achieves logarithmic proof size and verification time for d-degree NP relations, and outperforms existing solutions in both asymptotic and concrete complexity.

Masking, i.e., computing over secret-shared data, is one of the main counter-measures against side-channel analysis, provably secure in the standard noisy-leakage model. However, all the state-of-the-art security proofs rely on a reduction to a more abstract model called random probing (Eurocrypt’14). As a result, the noise requirements of such proofs must scale with the field size of the circuit which, beyond not reflecting real-world physics of target devices, is often prohibitive, especially in the post-quantum era. That is why it is critical to find alternative strategies to the reduction to the random-probing model. In this paper, we establish for the first time a masking security proof bypassing this reduction, answering positively to the above question. Contrary to the common belief that directly working in the noisy-leakage model is not convenient, we show how to reach this goal by leveraging an extension of the Xor lemma. We also show how to leverage the IOS framework (CHES’21) in order to derive composable security directly in the noisy-leakage model. As a result, our bound relies on relaxed noise requirements characterized in a weaker metric than the so far state of the art (Crypto’24, ’19). Moreover, our new proof strategy allows us to derive a security bound for circuits masked with the first-order ISW compiler, for which the optimal noise requirement scales as \(\Theta\left(\left|\mathbb{F}\right|^{1/2}\right)\), whereas proofs using the random-probing model work in a regime of \(\mathcal{O}\left(\left|\mathbb{F}\right|\right)\). The latter contribution illustrates how some current design choices for masked implementations could be concretely affected: we exhibit two exemplary masked implementations such that the former one is more secure in the (more abstract) random-probing model, whereas the latter one is more secure in the (more realistic) noisy-leakage model.

The Multidimensional Approximate Agreement problem ($D$-AA) considers a setting with $n$ parties with inputs in $\mathbb{R}^D$. Out of the $n$ parties, up to $t$ may be byzantine (malicious). The goal is for the honest parties to obtain $\varepsilon$-close outputs that lie in the honest inputs' convex hull. While tight bounds on the resilience of $D$-AA have been found for the purely synchronous and asynchronous models, this is still an open question for the network-agnostic model. Here, the type of network is not known a priori: it may be synchronous, and then the number of byzantine parties is up to $t_s$, or asynchronous, and then the number of byzantine parties is up to $t_a \leq t_s$. In this model, it is known that $n > (D + 1) \cdot t_s + t_a$ is sufficient for deterministic protocols [GLW, SPAA'23], tight for $D = 1$ [GLW, PODC'22], while $n > \max\{(D + 1) \cdot t_s, t_s + (D + 1) \cdot t_a\}$ is tight for randomized protocols concerned with exact agreement [CGWW, DISC'24].

In this work, we establish that, for $D > 1$ the condition $n > \max\{(D + 1) \cdot t_s, t_s + (D + 1) \cdot t_a\}$ is tight for deterministic protocols as well. We identify that the gap in prior deterministic protocols is not geometric, but stems from an asymmetry in the communication primitive that produces parties' "views". The core technical contribution of our work is hence a strengthened network-agnostic Gather primitive that enforces a global structural property on the number of values received by honest parties, eliminating the problematic asymmetry - so that standard safe-area geometric convergence arguments apply under the optimal thresholds.

We present the first general upper bound on permutation-based pseudorandom functions in the information-theoretic setting. We show that any non-compressing PRF, with input and output domain at least \([N]\), making \(t\) black-box calls to any \(t\) public permutations on \([N]\), can be distinguished from a random function over the output domain with at most \(\widetilde{O}\big(N^{t/(t+1)}\big)\) total queries to the PRF and the permutations. Our results suggest that the designs of Chen et al. (Crypto~2019) are optimal, among all possible constructions, in terms of information-theoretic security.

In particular, we propose the generalized key alternating construction, which captures permutation-based PRFs. We then prove that, for any such construction, there exists an explicit distinguisher achieving the tradeoff $Q_fQ_p^{t}=\widetilde{O}\big((2t^2)^{t+1}N^{t}\big) $ with constant advantage, where \(Q_f\) counts PRF queries and \(Q_p\) counts queries to each public permutation. We further extend our bound to blockcipher-based PRFs and to an adaptive setting in which each round may adaptively choose a permutation from a public family of permutations \(\mathcal P\). In this case, the general upper bound becomes \(\widetilde{O}\big(|\mathcal P|\,N^{t/(t+1)}\big)\).

In this paper, we study the IND-CPA-D security of FHE schemes when combined through scheme switching. We introduce a formal framework that captures security in this setting and provide a rigorous analysis of different constructions. Within this framework, we identify sufficient conditions for the switching algorithm under which the combined schemes achieve IND-CPA-D security, assuming the individual schemes are IND-CPA-D-secure.

We then focus on the specific case of scheme switching from CKKS to TFHE. We analyze how existing switching algorithms designed for vanilla CKKS can be modified to preserve IND-CPA-D security. We demonstrate an attack against the IND-CPA-D security of the PEGASUS construction [LHHMQ21] and we implement a proof-of-concept of this attack against the CKKS-to-FHEW switching mechanism in the OpenFHE library. Finally, we present a generic transformation that converts a vanilla CKKS-based switch into an IND-CPA-D-secure one.

The Algebraic Group Model (AGM) has become a standard framework for analyzing the knowledge soundness of group-based polynomial commitment schemes. In this work, we formally establish inherent limitations of this methodology. We isolate a structural property satisfied by essentially all practical group-based polynomial commitments, which we term AGM-clarity. We prove that for AGM-clear schemes, evaluation binding implies knowledge soundness in the AGM. This collapse reveals that the AGM definition of knowledge soundness does not capture a distinct security property, but is merely a structural consequence of evaluation binding.

To precisely characterize the guarantees on extractability provided by the AGM, we introduce Weak Interpolation Knowledge Soundness (WIKS) in the standard model, which is an extreme relaxation of extractability. We show that WIKS is implied by standard evaluation binding and prove that, for AGM-clear schemes, knowledge soundness in the AGM is equivalent to WIKS. Ultimately, our results demonstrate that proofs in the AGM for practical polynomial commitment schemes do not certify ``knowledge'' in the sense of immediate extractability, as they yield no guarantees beyond those already implied by standard model evaluation binding.

In this work, we study the concrete efficiency of SPDZ-type MPC protocols in the dishonest majority setting with maximum corruption, where $t=n-1$ out of $n$ parties can be corrupted. In the semi-honest setting, the state-of-the-art SPDZ protocol achieves an amortized communication cost of $4n$ field elements per multiplication gate, assuming a pseudorandom correlation generator (PCG) that prepares random Beaver triples silently in the offline phase. However, achieving security against malicious adversaries typically incurs a substantial overhead. Existing works either require communication of at least $10n$ field elements per gate, or additionally require an additively homomorphic encryption scheme. In this work, we construct a maliciously secure SPDZ-type protocol with the same amortized communication complexity as the semi-honest variant, i.e., $4n$ field elements per multiplication gate, assuming a PCG for tensor-product correlations. We note that the tensor-product correlations come free as by-products from almost all existing constructions of PCGs for random Beaver triples. These by-products allow us to construct an efficient preprocessing phase and a recursive check protocol, which enables an online evaluation of the circuit without authenticating all the wire values. The correctness of the online computation can also be checked efficiently with a sublinear communication cost in the circuit size.

Language models now routinely produce text that is difficult to distinguish from human writing, raising the need for robust tools to verify content provenance. Watermarking has emerged as a promising countermeasure, with existing work largely focused on model quality preservation and robust detection. However, current schemes provide limited protection against false attribution.

We strengthen the notion of soundness by introducing two novel guarantees: unforgeability and recoverability. Unforgeability prevents adversaries from crafting false positives, texts that are far from any output from the watermarked model but are nonetheless flagged as watermarked. Recoverability provides an additional layer of protection: whenever a watermark is detected, the detector identifies the source text from which the flagged content was derived. Together, these properties strengthen content ownership by linking content exclusively to its generating model, enabling secure attribution and fine-grained traceability.

We construct the first undetectable watermarking scheme that is robust, unforgeable, and recoverable with respect to substitutions (i.e., perturbations in Hamming metric). The key technical ingredient is a new cryptographic primitive called robust (or recoverable) digital signatures, which allow verification of messages that are close to signed ones, while preventing forgery of messages that are far from all previously signed messages. We show that any standard digital signature scheme can be boosted to a robust one using property-preserving hash functions (Boyle, LaVigne, and Vaikuntanathan, ITCS 2019).

A number of recent works propose watermarking the outputs of large language models (LLMs) but fail to describe who is authorized to watermark the text or check for a watermark. To resolve these problems, we propose interactive watermarking schemes. Our technique leverages the fact that, for many of the cases in which detecting synthetic text is useful, the detector is able to control some part of the prompt that is passed to the LLM.

In other words, we propose poisoning the prompt, through which the examining user establishes a steganographic channel with the LLM provider. This lets the user and the LLM provider agree on a shared key, which is then used to embed a a symmetric watermark and permits the end-user examiner to learn if the entity they are conversing with is a bot. Because the steganographic prompt and the LLM response are indistinguishable from their natural distributions, this approach simultaneously sidesteps prior impossibility results from Zhang et al. [ICML'24] and resolves the authorization questions unanswered by previous work.

Our primary construction is based on elliptic curve Diffie-Hellman; we sketch a more sophisticated version using broadcast encryption. Our secondary construction uses a symmetric key protocol with a pre-shared key. To improve efficiency, we introduce steganographic synchronization codes. We experimentally validate our theoretical findings and outline directions for future work.

Solving the Discrete Logarithm problem on the group of points of an elliptic curve is one of the major cryptographic applications of Shor's algorithm. However, current estimates for the number of qubits required remain relatively high, and notably, higher than the best recent estimates for factoring of RSA moduli. For example, recent work by Gidney (arXiv 2025) estimates 2043 logical qubits for breaking 3072-bit RSA, while previous work by Häner et al. (PQCrypto 2020) estimates a requirement of 2124 logical qubits for solving discrete logarithm instances on 256-bit elliptic curves over prime fields. Indeed, for an $n$-bit elliptic curve, the most space-optimized optimized implementation by Proos and Zalka (Quant. Inf. Comput. 2003) gives $5n + o(n)$ qubits, as more additional space is required to store the coordinates of points and compute the addition law.

In this paper, we propose an alternative approach to the computation of point multiplication in Shor's algorithm (on input $k$, computing $k P$ where $P$ is a fixed point). Instead of computing the point multiplication explicitly, we use a Residue Number System to compute directly the projective coordinates of $k P$ with low space usage. Then, to avoid performing any modular inversion, we compress the result to a single bit using a Legendre symbol.

This strategy allows us to obtain the most space-efficient polynomial-time algorithm for the ECDLP to date, with only $3.12n + o(n)$ qubits, at the expense of an increase in gate count, from $\mathcal{O}(n^3)$ to $\widetilde{\mathcal{O}}(n^3)$. For $n = 256$ we estimate that 1098 qubits would be necessary, with 22 independent runs, using $2^{38.10}$ Toffoli gates each. This represents a much higher gate count than the previous estimate by Häner et al. (roughly $2^{30}$), but half of the corresponding number of qubits (2124).

Concrete security estimates for Module-LWE (MLWE) over an appropriate ring are often obtained by translating to an "equivalent" unstructured LWE instance, which implicitly treats algebraic structure as a pure efficiency gain with no impact on security. We show that this heuristic fails for realistic parameters. In common MLWE/RLWE instantiations, an attacker can exploit symmetries to obtain hybrid attacks that are strictly stronger than the best corresponding attack on LWE, translating to a concrete hardness gap between MLWE and LWE.

Our starting point is the observation that many cryptographically relevant rings admit coefficient isometries: ring elements whose multiplication acts as a signed permutation on coefficient vectors and preserves the secret and error distributions of interest. Multiplying an MLWE instance by such an isometry creates many derived instances that share the same public matrix and are therefore compatible with the same expensive offline preprocessing in hybrid attacks. We formalise this mechanism and incorporate it into both primal and dual hybrid frameworks.

We instantiate coefficient isometries for power-of-two cyclotomic rings, and quantify the resulting advantage in two regimes. For sparse-secret RLWE (popular in homomorphic encryption), isometry-enabled hybrids yield gaps of up to 15 bits over LWE-based estimates. For the standardised Kyber/ML-KEM parameters, we obtain a consistent 2--3 bit gap under standard cost models. Our results demonstrate that the widely assumed equivalence between LWE and MLWE in power-of-two cyclotomics does not hold, with real world consequences for deployed schemes.

Many modern systems parse PDF files to extract semantic information, including multimodal large language models and academic submission platforms. We show that this practice is extremely vulnerable in real-world use cases. By exploiting standard-compliant features of the PDF page description language, an adversary can craft PDFs whose parsed content differs arbitrarily from what is visually rendered to human readers and whose metadata can be manipulated to mislead automated systems.

We demonstrate two concrete vulnerabilities. First, we build adversarial PDFs using font-level glyph remapping that cause several widely deployed multimodal language models to extract incorrect text, while remaining visually indistinguishable from benign documents. Across six platforms, most systems that rely on PDF text extraction are vulnerable, whereas OCR-based pipelines are robust. Second, we analyze arXiv's TeX-detection mechanism and show that it relies on brittle metadata and font heuristics, which can be fully bypassed without changing the visual output.

Our findings reveal a potential risk arising from discrepancies between automated PDF parsing and human-visible semantics. We argue that rendering-based interpretation, followed by computer vision, is one better approach for security-sensitive PDF interpretation.

Transport Layer Security (TLS) attestation protocols are a key building block for decentralized applications that require authenticated off-chain data. However, existing Designed Commitment TLS (DCTLS) constructions rely on designated verifiers, which prevents public verifiability and enables prover–verifier collusion in on-chain settings. To address these limitations, we propose a collusion-minimized TLS attestation framework $\Pi_{\textsf{coll-min}}$ that enables jointly verifiable attestations with distributed verifiers. The framework combines two complementary components: a modified and exportable variant of DCTLS, denoted as dx-DCTLS, which enables third-party verification by replacing non-verifiable components with verifiable counterparts, and a decentralized validation layer based on distributed verifiable random functions (DVRF) and a threshold signature scheme (TSS). Together, these two components allow multiple verifiers to jointly validate TLS attestations while minimizing prover–verifier collusion. In this study, we formalize a threshold attestation unforgeability notion capturing adversarial behaviors in multi-verifier environments and prove security under standard assumptions. Specifically, by transitioning from independent multi-session validations, as commonly employed in decentralized oracle networks (DONs), to a unified and exportable attestation framework, we achieve a reduction in the prover complexity from $O(n)$ to $O(1)$. To evaluate practicality, we provide a prototype implementation of the DVRF–TSS component and a performance analysis of dx-DCTLS. The results show that the proposed framework remains efficient at high threshold sizes and introduces only modest additional overhead, demonstrating the feasibility of collusion-minimized and jointly verifiable TLS attestations for smart contract environments.

We expand the well developed toolbox between quaternionic ideals and supersingular elliptic curves into its higher dimensional version, namely (Hermitian) modules and maximal supersingular principally polarised abelian varieties. One of our main result is an efficient algorithm to compute an unpolarised isomorphism $A \simeq E_0^g$ given the abstract module representation of $A$. This algorithm relies on a subroutine that solves the Principal Ideal Problem in matrix rings over quaternion orders, combined with a higher dimensional generalisation of the Clapotis algorithm. To illustrate the flexibility of our framework, we also use it to reduce the degree of the output of the KLPT$^2$ algorithm, from $O(p^{25})$ to $O(p^{15.5})$.

Traditional deniable encryption primarily focuses on denying the $content$ of secret communications, allowing plausible alternative plaintexts to be presented in the event of coercion. However, even the recognizable use of deniable encryption may already defeat its purpose, making any revealed plaintext suspicious to a coercer. Hence, for practical deniability, not only does the content need to be deniable, but also the entire use of deniable encryption must be considered. We call this $second~order~deniability$. This notion aims to hide the whole use of deniable encryption, where covert communication is indistinguishable from innocuous data, and enhanced content deniability, enabling multiple, cryptographically plausible decryptions that are computationally indistinguishable from the true message. To show its practicality, we present PhantomCrypt, which combines conventional deniable encryption (DE) with steganographic methods to hide the use of DE itself, while retaining the ability to decrypt a ciphertext into several distinct plaintexts, even if not under pressure. We prove the security of PhantomCrypt using a formalization of second-order deniability in standard cryptographic terms.

Non profiled side-channel attacks aim at exploiting leakage traces from a targeted embedded system to extract secret information, without a priori knowledge on the true leakage model of the device. To automate and simplify attacks, deep learning techniques have thus been introduced in the side-channel community. Most of the works published have mainly explored the use of discriminative models in the profiled or non profiled context. However, the lack of interpretability and explainability of these models constitutes a major limitation for security laboratory. Indeed, the lack of theoretical results regarding the choice of neural network architectures or the selection of appropriate loss functions poses significant challenges for evaluators seeking to construct a relevant and suitable model for the targeted leakage traces. To address the aforementioned limitations, we propose in this work a novel conditional generative model, specifically designed to carry out non profiled attacks, which is fully interpretable and explainable. To do so, we develop a novel model that fits to the non profiled context. To guarantee the interpretability and explainability of our model, we provide theoretical results to justify both its architecture, and a new loss function for its optimization process. We further propose a key recovery strategy based on our model that requires no leakage model assumptions. As a consequence, our work represents thus the first interpretable and generic (i.e. no a priori knowledge on the leakage model is required) non profiled deep learning-based side-channel attacks. Moreover, to emphasise the benefits of our new model in comparison with conventional linear regression based attack (LRA), we also provide a theoretical comparative analysis on the deterministic part estimation for different Gaussian noise configurations. Finally, we experimentally validate and compare the attack performances of our model with LRA and state-of-the-art discriminative-models-based non profiled attacks using simulations and various publicly available datasets.

Cryptographic primitives involving multiple participants, such as secure multiparty computation (MPC), threshold signatures, and threshold encryption, are typically designed under the assumption that at least a threshold number of participants remain honest and non-colluding. However, many real-world applications require more expressive access structures beyond simple thresholds. A prominent example is the weighted threshold access structure, where each party is assigned a weight and security holds as long as the total weight of corrupted parties does not exceed a specified threshold.

Despite the practical relevance of such access structures, our understanding of efficient constructions supporting them remains limited. For instance, existing approaches for weighted MPC and weighted threshold encryption incur costs that scale with the total assigned weights to all parties or rely on non-black-box use of cryptography.

In this work, we present the first black-box constructions of the following weighted cryptosystems with weight-independent complexity in the trusted setup model: (i) a weighted MPC protocol with guaranteed output delivery, (ii) a semi-honest weighted threshold encryption scheme and (iii) a semi-honest weighted threshold Schnorr signature scheme.

At the heart of our constructions is a new succinct computational secret sharing scheme with linear homomorphism for weighted threshold access structures. We provide two concrete instantiations of this primitive, based on the Decisional Composite Residuosity (DCR) assumption and the Learning With Errors (LWE) assumption, respectively. Furthermore, our constructions extend to any general access structure that can be represented efficiently as a monotone Boolean circuit.

We study the minimal hardness assumptions required for constructing succinct interactive arguments for NP—the total number of bits sent by the prover is smaller than the witness size. Known constructions of such arguments rely on collision-resistant hash functions (Kilian, STOC 92), indistinguishability obfuscation (Sahai and Waters, STOC 14), discrete logarithm (Bootle et al., Eurocrypt 16), and lattice-based assumptions (Baum et al., Crypto 18). This may suggest that succinct interactive arguments require (at least) the existence of one-way functions (OWFs). Somewhat surprisingly, we prove that the existence of a fully black-box reduction from OWFs to interactive arguments, succinct or not, is unlikely; the existence of such a reduction implies (unconditionally) the existence of OWFs. More generally, we consider fully black-box reductions from OWFs to interactive arguments combined with an additional hardness assumption G (e.g., NP ̸⊆P/poly). Such reductions would demonstrate that any algorithm breaking the candidate one-way function can be transformed into an algorithm that either breaks the soundness of the interactive argument or violates the assumption G. We prove that the existence of such a reduction implies a black-box reduction from OWFs to G alone. Moreover, this remains true even if the reduction only needs to work when the interactive argument oracle is perfect zero knowledge (the reduction, however, does not get oracle access to the zero-knowledge simulator). In conclusion, we show that the existence of succinct interactive arguments has no black-box implications on the existence of OWFs, and this holds also when combined with an additional hardness assumption.

The classical EUF-CMA notion for the security of message authentication codes (MACs) is based on "freshness": messages chosen by the adversary are authenticated, and then the adversary has to authenticate a fresh message on its own. In a quantum setting, where classical messages are authenticated but adversaries can make queries in superposition, "freshness" is undefinable. Instead of requiring the adversary to be unable to forge a fresh message, one can require "stability" (the adversary cannot authenticate more messages than queried before), or "exclusiveness" (the adversary cannot authenticate a message from a subset of messages it did not query before). The "plus-one" security definition, proposed by Boneh and Zhandry at Eurocrypt 2013, maintains stability, but fails at exclusiveness. The "blind unforgeability" notion from Alagic et al. (Eurocrypt 2020) maintains exclusiveness, but it is unknown if it maintains stability.

This paper proposes a new security definition: "splitting unforgeability" (SU). A MAC is SU-secure, if it maintains both stability and exclusiveness. Against classical adversaries, SU is equivalent to EUF-CMA. Against quantum adversaries, SU implies both plus-one security and blind unforgeability. With respect to $q$-query adversaries, $(2q-1)$-wise independent functions do not suffice for SU, but $(3q+1)$-wise independent functions do, as does a qPRF. Boneh and Zhandry's "Quantum Carter-Wegman MAC" (BZq-MAC), which combines a qPRF and an $\epsilon$-AXU hash function, is SU-secure up to the quantum birthday bound.

We additionally analyse the security of different instantiations of the Hash-then-MAC composition of a SU-secure MAC $F$ and a hash function $H$ which is either collapsing or Bernoulli-preserving.

In this work, we study the pseudorandomness of the bounded Knapsack function family defined over a number ring ${R}$. We establish that if the Knapsack function family is one-way and certain related folded Knapsack function families are pseudorandom, then the original Knapsack is pseudorandom. This can be seen as a generalisation of the work of Micciancio and Mol presented at the CRYPTO-2011, for the case of Knapsack function families defined over arbitrary number ring.