International Association
for Cryptologic Research

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.

Blind rotation is the computational core of GINX, AP, and AP+ bootstrappings, yet its error behavior has not been precisely characterized. Prior analyses rely on heuristic independence assumptions that fail to capture the distinct error accumulation patterns of different algorithmic variants. We prove that no additional assumptions are needed: the (M)LWE assumption guaranteeing ciphertext indistinguishability also implies the independence properties required for an exact second-moment characterization of blind rotation error. We derive the first closed-form formulas covering all four combinations of decomposition type (full vs. approximated) and algorithmic variant (vanilla vs. unrolled). Our analysis reveals three structural phenomena previously overlooked: (i) a message-dependent residual term that halves the effective decomposition variance, (ii) a doubling coefficient inherent to unrolled implementations, and (iii) bounded cross-term correlations whose contribution remains constant in the security parameter. Our formulas match experimental measurements within 1%, whereas prior estimators deviate by up to 50% for unrolled blind rotation. Our results show that the (M)LWE assumption—already required for security— is sufficient to determine the exact error behavior of GINX, AP, and AP+ bootstrapping.

Two linear codes $\mathcal{C},\mathcal{C}’$ over $\mathbb{F}_q$ are linearly equivalent if one can be mapped to the other via a monomial transformation. Recovering this monomial from $\mathcal{C}$ and $\mathcal{C}’$ is known as the Linear Code Equivalence (LCE) problem.

The most efficient algorithms to solve the LCE problem follow a common framework based on finding low-weight codewords. This framework admits a natural lower bound obtained by assuming that among the found low-weight codewords, a single equivalent codeword pair can be identified and used to reconstruct the monomial without overhead. Whether this lower bound can be achieved by a constructive instantiation has remained an open problem. Existing algorithms all require multiple equivalent pairs for monomial reconstruction, resulting in both concrete and asymptotic gaps to the lower bound.

In this work, we answer the question of whether there exists such an optimal framework instantiation in the affirmative. We introduce a canonical labeling technique, as a generalization of canonical forms, that allows for monomial reconstruction from a single pair of equivalent codewords. Crucially, this labeling procedure, even if not necessarily polynomial-time, can be embedded into the codeword-search framework to identify equivalent codewords and perform final monomial recovery without overhead. This gives rise to the first framework instantiation that meets its lower bound both asymptotically and concretely up to negligible tolerance.

For the parameter sets proposed for the LESS signature scheme, an active second-round contender in the NIST PQC standardization process, our analysis reduces the estimated bit security by up to 15 bits.

Evolving secret sharing allows a dealer to share a secret message between a growing number of $n$ parties. Crucially, the dealer does not know an upper bound on $n$, neither it knows the access structure before party $n$ arrives; furthermore, the dealer is not allowed to update the shares of old parties. We construct new secret sharing schemes for so-called evolving (weighted) threshold access, in which the arrival of party $n$ determines the number of parties $t_n \le n$ that are required in order to reconstruct the secret. We also consider the more general case in which party $n$ has associated a weight $w_n$ with logarithmic size, and the authorized subsets of parties are those for which the sum of the corresponding weights exceeds the current threshold $t_n$. In particular, we obtain: - A secret sharing scheme for evolving threshold access structures with adaptive privacy in the plain model, and with share size $\mathsf{poly}(\lambda,\log n)$. This construction requires one-way functions (OWFs) and indistinguishability obfuscation (iO) for Turing machines. - A secret sharing scheme for evolving weighted threshold access structures with adaptive privacy in the plain model, and with share size $\mathsf{poly}(\lambda,\log W_n)$ where $W_n$ is the sum of the weights up to party $n$. This construction requires OWFs and iO for Turing machines, and additionally assumes that the weights are fixed (i.e., cannot change over time). - A secret sharing scheme for evolving weighted threshold access structures with static privacy in the plain model, and with share size $\mathsf{poly}(\lambda,\log W_n)$. This construction allows the weight of old parties to change over time, but it requires somewhere statistically binding hash functions and achieves only static privacy. Previous constructions of secret sharing schemes for evolving (weighted) threshold access structures achieved (much worse) share sizes linear in $W_n$ (and in the security parameter) and, when considering adaptive privacy, they require the random oracle model.

Transparent, code-based polynomial commitment schemes (PCSs) such as BaseFold (CRYPTO’24) are a compelling building block for large-scale zero-knowledge proofs (ZKPs): they avoid trusted setup, rely on standard hash assumptions, offer post-quantum security, and achieve high performance. As ZKP workloads grow, the polynomials that PCSs must commit to and open increasingly exceed the memory and throughput of a single machine, motivating a scalable distributed version of BaseFold. However, existing distribution attempts either only support polynomials of specific structures, or their proof size grows with the number of workers, or they do not scale to arbitrarily many workers. In this paper, we present UltraFold, the first distributed BaseFold PCS that works with general polynomials, scales to any number of workers, and maintains succinct proofs whose size does not depend on the worker count. To enable efficient distributed commitment and opening, UltraFold introduces an interleaved Merkle leaf layout that is realized via a single all-to-all exchange of partially encoded values, and each worker’s computation becomes local after this exchange. To mitigate hashing overhead, UltraFold further uses packed Merkle trees, reducing both prover time in practice and the resulting proof size. We implement UltraFold and evaluate it in a distributed setting: using 256 single-core workers, we commit to and open a 134M-coefficient polynomial in under 2 seconds, with a proof size of 216 KB.

We give new algorithms for tree evaluation (S. Cook et al. TOCT 2012) in the catalytic-computing model (Buhrman et al. STOC 2014). Two existing approaches aim to solve tree evaluation (TreeEval) in low space: on the one hand, J. Cook and Mertz (STOC 2024) give an algorithm for TreeEval running in super-logarithmic space $O(\log n\log\log n)$ and super-polynomial time $n^{O(\log\log n)}$. On the other hand, a simple reduction from TreeEval to circuit evaluation, combined with the result of Buhrman et al. (STOC 2014), gives a catalytic algorithm for TreeEval running in logarithmic $O(\log n)$ free space and polynomial time, but with polynomial catalytic space.

We show that the latter result can be improved. We give a catalytic algorithm for TreeEval with logarithmic $O(\log n)$ free space, polynomial runtime, and subpolynomial $2^{\log^\epsilon n}$ catalytic space (for any $\epsilon > 0$). Our result gives the first natural problem known to be solvable with logarithmic free space and even $n^{1-\epsilon}$ catalytic space, that is not known to be in standard logspace even under assumptions. Our result immediately implies an improved simulation of time by catalytic space, by the reduction of Williams (STOC 2025). Our catalytic TreeEval algorithm is inspired by a connection to matching vector families and private information retrieval, and improved constructions of (uniform) matching vector families would imply improvements to our algorithm.

Secure aggregation enables a server to learn the sum of private inputs of clients, while revealing no additional information beyond the final sum. Recent work, Willow (CRYPTO 2025) achieves one--shot secure aggregation in the single-server model with dynamic client participation. To ensure security under these features, Willow relies on an auxiliary committee to verify the correctness of the aggregation. Although this verification requires no private information---broadening the set of parties eligible to participate in the committee---the committee’s total work scales linearly with the number of clients, which poses a challenge for large-scale deployments. This linear committee cost limitation is also shared by other state-of-the-art single-server secure aggregation protocols, including Flamingo (IEEE S&P 2023) and OPA (CRYPTO 2025).

In this paper, we introduce WillowFold, a secure aggregation scheme based on Willow that enables lightweight verification of the aggregation and requires only logarithmic committee cost in the number of clients. Our scheme additionally supports streaming aggregation and reduces per-client server storage to a single ID (4 bytes), rather than storing full contributions as in Willow (1.5 KB), which facilitates distributed execution of the server-side computation. Finally, we close a gap in Willow’s security proof by showing that the zero-knowledge proofs underlying the scheme must be simulation extractable in order to rule out correlated ciphertext attacks.

WillowFold employs proof-carrying data (PCD)---a primitive for incremental verification of distributed computations---to achieve a lightweight verification cost. In particular, we present a concretely efficient instantiation of WillowFold using a variant of Spartan+KZH-Fold (CCS 2025) as the underlying PCD scheme. As independent contributions, we show a zero-knowledge variant of Spartan+KZH, which is the SNARK underlying Spartan+KZH-Fold, that uses logarithmic randomness, and we further prove that this variant satisfies the simulation extractability.

We implement and evaluate WillowFold, showing that it supports $8$ million clients with proof size $<60$~KB and verification time under one second--a $10^{5}$-fold improvement over Willow.

The classical results of Cramer et al. [Crypto’94] showed how to compose $n$ $\Sigma$-protocols with statistical HVZK to obtain an efficient proof of knowledge of their disjunction maintaining statistical HVZK without adding hardness assumptions. The Fiat-Shamir (FS) transform applied to their construction produces a statistical NIZK proof of knowledge in the random oracle (RO) model, but, unfortunately, the proof size in their case is linear in $n$. Recently, there has been increasing interest in solving the major open problem of obtaining statistical NIZK proofs of knowledge for disjunctions starting from $\Sigma$-protocols, with improved communication and minimizing hardness assumptions. The current best results are due 1) to Goel et al. [Eurocrypt '22], which, unfortunately, require Dlog-based assumptions, and 2) to Boudgoust and Simkin [TCC '24] which, unfortunately, obtain computational ZK only. In this work, we solve the above open problem showing, for a large class of $\Sigma$-protocols, how to obtain a non-interactive compact statistical NIZK proof of knowledge without adding hardness assumptions, therefore only relying on random oracles. More precisely, the communication complexity of our construction is $O(\lambda^2\log{n})+\mathsf{CC}(\Sigma)$ where $\lambda$ is the security parameter and $\mathsf{CC}(\Sigma)$ is the communication of a single run of the underlying $\Sigma$-protocol, and this is obtained via calls to a random oracle and to a prover executing a stand-alone instance of the $\Sigma$-protocol.