arXiv CSopen access

Verifiable Random Sampling

Verifiable Random Sampling Yeoh Wei Zhu Global Technology Applied Research, JPMorganChase

Soorya Rethinasamy Global Technology Applied Research, JPMorganChase

Anthony Alexiades Armenakas Global Technology Applied Research, JPMorganChase

Yash Satsangi Global Technology Applied Research, JPMorganChase

Shaltiel Eloul Global Technology Applied Research, JPMorganChase

Ruslan Shaydulin Global Technology Applied Research, JPMorganChase

arXiv:2607.26734v1 [cs.CR] 29 Jul 2026

Abstract Verifiable random functions (VRF) underpin a wide range of applications that require publicly verifiable evaluations of a pseudorandom function on a given input. However, once the public key is published, the induced function is fixed and is a deterministic function of the input. This determinism can enable collusion and grinding-style attacks in which adversaries precompute and selectively exploit favorable input-output pairs. To address these limitations, we introduce the formal notion of verifiable random sampling (VRS). We propose a concrete VRS construction based on random quantum circuit sampling (RCS) executable on today’s quantum computing devices. VRS supports multiparty protocols in which the verifier’s final output is a sample that is statistically close to a specified target distribution, while remaining publicly verifiable. We model the construction and prove its security within the constructive cryptography (CC) framework, thereby ensuring composability with other cryptographic protocols. Overall, our results provide a mechanism for verifiable random sampling that simultaneously guarantees sample freshness and public verifiability, enabling applications that require unpredictable, fresh randomness while preserving fairness through public verifiability.

1

Introduction

Many deployed applications rely on randomness to function correctly. Traditionally, random numbers are generated by extracting entropy from physical sources such as thermal noise [59], clock jitter [23], and others [50]. For example, the Linux kernel aggregates entropy from keyboard interrupts, disk I/O, mouse movement, and device-driver interrupts [28] to seed the randomness exposed through /dev/random. However, many modern applications operating in a cloud or distributed setting, such as smart contracts, have no access to a trusted local entropy source and must obtain randomness from a remote party over the Internet. In this setting, a client receiving a purported random sample has no way to verify two properties: (i) that the sample was actually drawn from the claimed physical source rather than fabricated by an adversarial provider, and (ii) that the sample is genuinely fresh, i.e., not precomputed. We address the problem of designing a primitive that provides both guarantees in a publicly verifiable manner. A commonly used solution to this problem is the verifiable random function (VRF) [45], which extends pseudorandom functions to the public-key setting, enabling anyone to verify that an output is computed correctly. VRFs have been adopted in a variety of applications, including e-lotteries [49], leader election in proof-of-stake protocols [33, 22], and many others.

2

Verifiable Random Sampling

However, VRFs face fundamental limitations due to their deterministic structure: once the public key is fixed, the input-to-output mapping is fully deterministic. Consequently, the pseudorandomness guarantee depends on both the secrecy of the VRF provider’s key and on non-collusion between the provider and the party choosing the input. If either condition fails, the output becomes predictable to the colluding parties and the guarantee is lost. Furthermore, even with an honest provider, the determinism enables grinding attacks in which a party who can influence the input precomputes many candidate evaluations and selectively submits the most favorable one. Since these limitations are structural, a suitable replacement must produce fresh outputs that are publicly verifiable, compose securely with other protocols, and support multiple use cases. This motivates the following fundamental question: Can we construct a protocol that: outputs a sample from a target distribution D, produces a publicly verifiable transcript, is composable, and is generic enough to support multiple use cases? We answer this question in the affirmative by constructing a verifiable random sampling (VRS) protocol that builds on the RCS-based certified randomness primitive proposed in [3, 7] and demonstrated experimentally in [36, 37]. In that primitive, a classical client samples ⃗ := (C1 , · · · , CM ) for some positive integer M and sends them to random quantum circuits C a quantum provider, who evaluates Ci |0 · · · 0⟩ for all i ∈ [M ], measures in the computational basis, and returns the outcomes ⃗z := (z1 , · · · , zM ). Passing the XEB score test certifies that ⃗z carries genuine quantum entropy. In prior works, this primitive is an interactive two-party protocol whose guarantees rely on a private freshly sampled challenge and a tight response deadline measured on the verifier’s local clock, neither of which is available to a third party observer of the transcript. To turn this into a publicly verifiable sampling primitive, we replace the client’s private circuit sampling with a public generation of the challenge circuits from the hash of the latest blockchain block, which is unpredictable to the provider before publication and recomputable by any third party afterwards. We replace the local timing deadline with the on-chain block interval T enforced by the consensus layer, and we require the response to be committed on-chain so that any third party can later reconstruct and verify the transcript. To make the protocol work in the blockchain setting, we rule out post-selection and stale-circuit reuse across clients through on-chain checks and domain separation. In addition, we split the classical client of [36] into a challenge generator T and a verifier V that consumes the randomness, and we analyze the resulting three-party protocol in the constructive cryptography model. We provide a technical overview in Section 2 and summarize the contributions below. Contributions To the best of our knowledge, this is the first verifiable random sampling (VRS) formalB3 ization and construction VRSD T,E . Unlike VRFs, which yield a pseudorandom output, B3T,E VRSD outputs a fresh random sample from a desired distribution D. B3 We construct VRSU T,E based on random circuit sampling (RCS) that is implementable on quantum computing devices available today. Our model and framework support replacing the RCS-based entropy source with more efficient entropy sources in the future as fault-tolerant quantum computing devices become available. B3 Given our VRS protocol construction VRSU T,E for sampling from the uniform distribution U, we show how to perform VRS for an arbitrary distribution D using new results on

Y. Wei Zhu et al.

rejection sampling with error source distribution when considering information theoretic randomness. Our analysis is in the constructive cryptography (CC) model, which is composable. Our construction can therefore be arbitrary composed with other protocols.

1.1

Related Works and Comparison to Prior Art

We start by reviewing various related works in the domain of random number generation and then compare them against VRS. Randomness Beacon (RB). Randomness beacons, introduced by [55], provide a public source of randomness that is intended to be unpredictable prior to release in periodic intervals. Works such as [16] propose a more efficient MPC protocol to derive an efficient randomness beacon assuming an honest majority while [57] provide a randomness beacon in the (t,n) threshold model albeit with a non-negligible failure probability against a Byzantine adversary. Recently, beacons based on randomness generated by quantum processes have been demonstrated [1, 31]. However, such beacons lack general provability guarantees, i.e., how a randomness consumer can be guaranteed that the published randomness is indeed a fresh value assuming the beacon committee is fully corrupted. Verifiable Random Function (VRF). VRF [45] offers a strong notion of provability: given a public key and an input, anyone can verify that an output was correctly computed under the corresponding secret key, without learning the secret key itself through the use of zero-knowledge proof. Recently, [27] studies an unbiasable VRF under skewed output distribution induced by malicious key setting. Despite solving the provability issue, VRF suffers from the non-collusion assumption and from a deterministic output on a given input. Physically Unclonable Function (PUF). PUF [25] leverages manufacturing variability to derive device-specific responses to challenges and is often proposed as a hardware-based primitive for identification [18] and entropy extraction [48]. The PUF typically assumes specific hardware properties and that the function is unlearnable; however, as shown in [56], machine-learning-based modeling attacks can break this assumption. Moreover, PUF suffers from the key enrollment problem [53], where we have to trust both the provisioning and the enrollment process. Certified Randomness (CR). Certified randomness focuses on proving that a sequence of bits originated from a truly random process. Several approaches to certified randomness from quantum devices have been proposed. Random Circuit Sampling (RCS) based protocols [3, 36, 7] leverage the classical intractability of sampling from random quantum circuits where scoring high on cross-entropy benchmarking (XEB) score serves as a proof of quantum-ness and passing the XEB score test provably implies entropy generation under certain complexity assumptions (e.g., LLHA [3]). RCS-based protocols have been demonstrated experimentally [36, 37] on today’s noisy quantum devices. However, these protocols suffer from expensive verification. On the other hand, [62] introduced a protocol based on an NP-search problem from error-correcting codes, proven hard classically but solvable by polynomial-time quantum computer. While this approach offers a more efficient verification process, this approach is not experimentally realizable today because it demands quantum decoding capabilities that are out of reach of today’s noisy quantum computers. Therefore, we construct our verifiable random sampling protocol on top of an existing certified randomness protocol that works on current-scale quantum computers, while the efficiency of our construction can be further improved in the future by switching to a certified randomness protocol designed for fault-tolerant quantum computers. Verifiable Random Sampling VRS (This work). VRS solves the provability issue of

3

4

Verifiable Random Sampling

Client (T) Sample

Verifier (V)

Blockchain (B3)

Provider (P)

B3

Figure 1 Simplified VRSU T,E overview. Steps I, II, III are executed inside Steps 1, 2, 3 respectively. Step 0 is optional. Steps inside the box indicate online phase where timing is important. The syntax of T, P, V is modified to include additional inputs for clarity.

randomness beacon while simultaneously guaranteeing fresh randomness, unlike the stale pseudorandom function of a VRF. Compared to PUF, VRS relies on the principles of quantum mechanics, requiring neither a trust assumption nor a hardware assumption. Notably, VRS differs from certified randomness, as it samples from any desired distribution in a publicly verifiable manner. The comparisons are summarized in Table 1. B3

Collusion Resistance Publicly Verifiable Non-deterministic Output Information-theoretic Randomness Specified Distribution

VRSU T,E (This work) ✓ ✓ ✓ ✓ ✓

VRF

PUF

RB

CR - RCS

✗ ✓ ✗ ✗ ✗

✗ ✓ ✓ ✗ ✗

✗ ✗ ✓ ✓* ✗

✓ ✗ ✓ ✓ ✗

Table 1 Comparison of VRS against various random number generation related primitives. * The scheme may exhibit the required property depending on the construction.

2

Technical Overview

In this section, we present the high-level technical overview of our paper. We consider the use case of requiring (unpredictable) verifiable randomness for a generic party V in this B3 paper. The high level overview of the construction VRSU T,E is given in Figure 1. We first state the parties in the VRS protocol from Section 5.1: ⃗ using input x and latest block data. Client T : Generates challenge circuit C Provider P : Provides the response ⃗z with some intrinsic entropy, and posts it to the blockchain. Verifier V : Verifies the response with respect to the circuit and outputs a sample u.

Y. Wei Zhu et al.

2.1

5

(Provable) Random Number Generation: Transitioning from Deterministic Function to Non-Deterministic Sampling

Verifiable Random Function (VRF). VRF remains the most common way to inject verifiable randomness into the execution of smart contracts. VRFs work by provably transforming the smart contract’s input into an output that looks random enough for use cases such as blockchain-based fair matchmaking, fair ordering, lucky draws, and many others [17]. However, this model of supplying randomness critically relies on the non-collusion of the VRF provider and the party selecting the VRF input. Since the random function used in VRF is determined in advance (by publishing the public key), the colluding parties can indeed essentially “predict” the random function evaluation and gain advantage in Web3 on-chain games, lotteries and other applications. Verifiable Randomness Source. The deterministic nature of a fixed random function evaluation can be overcome by introducing a source that is probabilistic in nature. However, proving that a sample returned over the Internet was freshly drawn from some distribution is a non-trivial problem. To that end, Aaronson and Hung [3] showed that we can provably lower bound the min-entropy of the output string given by a potentially adversarial party’s algorithm over the Internet. The protocol goes as follows. Let M be the number of circuits used in the protocol. The protocol starts with a classical verifier generating n-qubit challenge ⃗ = C1 , C2 , . . . , CM pseudorandomly, which are then sent to the provider. The circuits C provider’s server then evaluates each circuit on the initial state |0n ⟩ and measures the final state in the computational basis. The output string ⃗z = z1 , . . . , zM is sent back to the verifier as the response. In [36], the verifier then computes the XEB test score XEBscore =

N X |⟨zi |Ci |0n ⟩|2 − 1, |V| i∈V

where N = 2n , V is the verification set, and the probability of observing a string zi is pi (zi ) = |⟨zi |Ci |0n ⟩|2 . Assuming the hardness of spoofing the XEB test score, if the test score is sufficiently large XEBscore ≥ χ, then there must be some genuine entropy in the response string (See Theorem 4 for the formal statement). We provide an overview of the hardness justification in Section C. We briefly explain the intuition behind the hardness of spoofing the XEB score. For random circuits sampled from the Haar distribution, Ci ∼ Haar(N ) (See Section 3 for the definition of the Haar measure), the probability distribution {pi (zi )}zi 1 is highly non-uniform, that is a large fraction of output strings have probability p < 1/N , and the probability density is concentrated on a relatively smaller fraction of the output strings. A genuine quantum device sampling from pi will therefore output strings that are biased toward these higherprobability outcomes, while classical spoofing strategies, assuming the unstructured nature of RCS circuits from Assumption 1, will not be able to output enough of such higher probability output strings. The XEBscore measures this bias by averaging the ideal probabilities pi (zi ) of the returned samples and rescaling by N . For classical spoofing attempts, it satisfies E[N pi (zi )] ≈ 1 and hence XEBscore ≈ 0. Meanwhile, ideal sampling satisfies E[N pi (zi )] ≈ 2 and XEBscore ≈ 1. Thus, a larger XEB score indicates stronger correlation with the intended circuit distribution. Note here that a straightforward classical spoofing strategy is to simulate the entire RCS circuit, find the output distribution, and sample from it. This would lead to a high

1

The probability distribution approximates the Porter-Thomas distribution

6

Verifiable Random Sampling

XEBscore score. However, this type of simulation is computationally expensive even using state-of-the-art classical simulation methods. Thus, requiring that the response is submitted within a certain time-bound rules out such potential spoofing attacks [3], and is essential to the protocol. We will make use of this verifiable randomness source in the next section to build Verifiable Random Sampling (VRS).

2.2

Constructing VRSU : From Certified Randomness to Verifiable Random Sampling (VRS).

Extracting Uniform Sample from Randomness Source. The output of the verifiable randomness source Z is an output string ⃗z with a verifiable (smooth) min-entropy guarantee, ϵh such that Hmin (Z) ≥ B for some bound B. To extract uniform randomness, we assume a second source of (private) randomness. We can now apply the randomness extractor theorem (formally stated in Definition 5). We specifically consider a quantum-proof strong extractor because the string z is given by a (potentially malicious) quantum algorithm who may possess quantum side-information on it. The output distribution of the randomness extractor is then statistically close to the uniform distribution as stated in Definition 5, even if one of the inputs is publicly known. Public Verifiability. The above output is not publicly verifiable, however. When a third party is given the transcript of the above interaction, they cannot be sure whether the interaction was completed on-time or whether the challenge circuits were honestly generated. We solve both of these issues by using a blockchain resource, which provides both an alternate entropy source to create the challenge circuits and a method to timestamp the interaction. Specifically, the latest blockchain hash data is used to generate the challenge circuits, which ensures that the interaction is linked to on-chain activity, serving as a thirdparty timestamp. The blockchain hash data contains enough computational entropy [12] (though it is potentially biasable, see also A.7), which ensures that the challenge circuits are freshly generated. Furthermore, posting the responses to the chain is useful for enforcing timing constraints. Assuming that there exists a certain time bound T between each block publication such that B[id + 1].τ − B[id].τ < T, where B denotes the blocks, and τ denotes the timestamp, we can be sure that the challengeresponse protocol is completed within some time bound and can subsequently rule out the time-consuming spoofing or simulation attacks [3]. We note here that our protocol works with any bulletin-board-like scheme other than blockchain, as modeled by the ideal blockchain B3T,E defined formally in Section 5.3, as long as it provides a time-stamping feature at the granularity specified by T, and broadcasts pseudorandom numbers at a regular interval that contains at least E-bits of entropy. In addition to ensuring the timing constraint, we also enforce that no post-selection can be done by the client. A client might decide to launch several VRS protocols in parallel, post all the transcripts, and “choose” the best transcript. This would bias the output distribution. To prevent this type of manipulation, we as the third party itself must pick the transcript. For example, if the third-party supplied input x (like V in our protocol), it can either pick the earliest transcript, or pick among the available transcripts uniformly at random. Our verifier’s algorithm will pick the first available transcript after a verifier specified time to ensure both that no pre-sampling is done before the verifier specified time and that no post-selection is done. To further ensure public verifiability of the output sample u by V as a third-party observer

Y. Wei Zhu et al.

outside the protocol against potentially malicious parties T , P , and V , the verifier further performs one of the following, depending on the context: Non-colluding Verifier with Provider and One-time Use: The verifier attaches the second input to the randomness extractor alongside the sample u together with the transcript. Non-colluding Verifier with Provider and Multiple Use: The verifier simply generates a NIZK proof of correct generation of a sample u against a seed committed before the protocol execution. Corrupted Verifier: The verifier, instead of using private input, samples from the blockchain hash data of the block in which the response is published. Then, the verifier uses the sampled blockchain hash data to derive the final sample u. Note that for all three cases above, the extractor’s second input remains secret until the moment the provider P publishes its response. Now, the third party simply executes the same evaluation/verification algorithm πV executed by an honest verifier V . We discuss these instantiations further in Section A.2. Ensuring Independent Inputs. Randomness extractor theorems (see Definition 5) require the independence of the primary and secondary inputs. For the randomness extractor used in the final sample generation, the other input is assumed to be private and is modeled as such in Figure 4, which means the extractor input string from the provider does not depend on this unknown second input. Domain Separation: Avoiding Challenge Circuit Staleness across Multiple Clients. Multiple different clients might try to reuse the same input x to derive their randomness. However, it can be seen that given the same input x and the same blockchain hash, the same output string can be reused while passing the TestXEB verification test, since the challenge circuit is the same. Note that it does not contradict the entropy guarantee from Theorem 4, which requires the circuit to be (pseudo-)randomly generated on each invocation. This issue can be solved by requiring the client (and verifier) to perform (and verify) domain separation in the input space for the hash function used to pseudorandomly derive the challenge circuit. Domain separation or salting in the hash function input space is a common security practice [10, 9, 20, 35]. Note that we model this case using a generic domain separator CTX, since the solution to this problem can be context or domain-specific as discussed above, and we discuss the domain separation in detail in Section A.4. We assume that different contexts will be represented as different values in CTX. For example, CTX can be a session ID. Protocol Summary. We give a VRS protocol high-level summary in Section 5.6.

2.3

Use Cases and Extensions

2.3.1

Lifting VRSU to VRSD .

We constructed a protocol VRSU , given in Section 5, that allows one to sample from the uniform distribution. To sample from an arbitrary distribution D, we can make use of the rejection sampling technique [60]. The technique is built on the premise that perfect sampling from U is possible. However, it may be the case that we are only able to sample from Ũ that is ϵ−close to U in statistical distance. To alleviate this, we further derive a result on the rejection sampling with error stated as Lemma 10 in Section 6.1. The rejection sampling with error works by sampling from the imperfect distribution Ũ and then rejects with probability as if we are sampling from the intended source distribution U. With the rejection sampling with error, we are able to bound the statistical distance of the sample obtained from D̃ with the intended output distribution D, where D̃ is the output distribution of the rejection sampling with error algorithm.

7

8

Verifiable Random Sampling

2.3.2

Use Cases for VRS

To demonstrate the effectiveness of the VRS formal model across various use cases with different trust assumptions, we showcase its applicability in the following scenarios: 1. Publicly Verifiable Randomness Derivation. In a publicly verifiable randomness derivation use case, a verifier who may lack a local qualified randomness source would like to derive a random value by observing the transcript obtained from the interaction between a client T and a provider P . Therefore, we have the setting where P and T are potentially malicious while V is honest. This is the exact setting analyzed in Section 5. 2. Smart Contract Random Value Derivation. Similarly, smart contract use cases typically fall into the above setting but with an honest T , since a smart contract usually lacks local randomness and behaves honestly. The setting in which both the client and verifier are honest (where the verifier also serves as the challenge-generating client) while the provider is potentially malicious is also addressed by the protocol defined in Section 5, since the capabilities of a malicious client are a strict superset of those of an honest one (a malicious party can always adopt the honest strategy). By substituting the second input (seed) in the construction with a future blockchain hash value that is unpredictable, the smart contract can likewise derive a statistically close sample. 3. e-Lottery: Verifiable Fairness for All. In an e-Lottery setting, a set of mutually distrusting clients T and a lottery operator LO wish to jointly compute a function V that determines the winner. The winning criterion is that the party who draws the smallest sample from a uniform distribution wins. For simplicity, the seed can be defined as a P shared secret seed = si , jointly computed by each party Ti and LO over pre-published commitments Commit(si ), where si ∈ Zq . A similar construction can be realized using threshold distributed key generation, as described in [26]. In this setting, T and P are malicious, while V is honest (enforced by the MPC protocol computing the function V ), matching the construction given in Section 5.

3

Preliminaries

We use a ∼ D to denote that a is a random sample drawn from a distribution D and use b ←$ D to denote that b is a random sample from a set D. Let C be an n-qubit quantum circuit and let N = 2n be the dimension of the Hilbert space H. We define P(H) to denote the set of positive semi-definite operators on H. The trace of an operator ρ is given by P Tr(ρ) := i ⟨i|ρ|i⟩ for any orthonormal basis {|i⟩}. We can then define the normalized quantum states and sub-normalized quantum states as S(H) := {ρ ∈ P(H) : Tr(ρ) = 1} and S≤ (H) := {ρ ∈ P(H) : Tr(ρ) ≤ 1}. In the interest of notational convenience, we ⃗ := C1 ⊗ · · · ⊗ CM to denote the composite circuit and use the tensor product notation C ⃗ |0n·M ⟩ in the consequently ⃗z to denote the output string obtained from measuring the state C computational basis rather than addressing them separately via index notation. In practice, the circuit is represented using the individual factor Ci rather than the full tensor product. For RCS experiments, the relevant distribution is the distribution of bitstrings given a particular circuit C, denoted by pC (z) := |⟨z|C|0n ⟩|2 . An alternate notation used in this work is using the Measure operation, i.e., Measure(|ϕ⟩) is the random variable obtained by measuring the state |ϕ⟩ in the computational basis. We denote the hash function as Hash(·) and use the overloaded symbol HashD (·) to mean hashing into the specific distribution D. Let X, Y be two random variables with support P SX , SY respectively, the statistical distance is defined as SD(X, Y) := 21 u∈SX ∪SY | Pr[X = u] − Pr[Y = u]|.

Y. Wei Zhu et al.

Haar-random Circuit. Let Haar(N ) denote the unique bi-invariant probability measure on the unitary group U (N ) so that for any fixed unit vector |ϕ⟩ ∈ CN and C ∼ Haar(N ), C |ϕ⟩ is uniformly distributed over the unit sphere in CN . For deriving a Haar-random circuit, it is known that with a uniform seed, we can sample from a distribution that approximates Haar(N ) in a pseudorandom manner [44, 13]. We denote such an algorithm DeriveHaar(N )M : {0, 1}s → (C1 , · · · , CM ) where Ci is an n-qubit quantum circuit. Entropy. For a quantum state ρ, H denotes the von Neumann entropy H(ρ) := −Tr(ρ log ρ), which reduces to the Shannon entropy in the classical setting H(X) := P − i Pr(xi ) log Pr(xi ) for some random variable X, when ρ is diagonal. H ϵ denotes the smooth version of the entropy measure [58]. Given a classical-quantum state ρXA classical on X, the conditional min-entropy is defined as Hmin (X|A)ρ := − log pguess (X|A)ρ where pguess (X|A)ρ is the optimal probability of guessing. The smooth version is defined using ϵ-ball of states around ρ ∈ S(H) defined as B ϵ (ρ) where p:= {σ ∈ S≤ (H) : P (ρ, σ) ≤ ϵ}, √ √ the purified distance metric is given by P (ρ, σ) := 1 − F 2 (ρ, σ), and F (ρ, σ) := ρ σ 1 √ and ∥A∥1 = Tr( A† A). Given a smoothing parameter ϵ, the smooth min-entropy can then ϵ be defined as Hmin (X|A)ρ := supσXA ∈B ϵ (ρ) Hmin (X|A)σ . In the classical setting, we use Hmin (X) to denote the min-entropy for a random variable X such that Hmin (X) = H∞ (X) = − log(maxx Pr[X = x]).

3.1

Cryptographic Assumption

We first recall the entropy guarantee that arises from complexity assumptions. We only state the theorem here without definition, see Section C for more details. ▶ Theorem 1 (Passing MLXEB test with low entropy solves LLQSV(Theorem 8, [36])). There exists a quantum-classical Arthur-Merlin protocol which on input of an O(n)-bit advice string solves LLQSVB (D) ,which means LLQSVB (D) ∈ QCAMTIME(2B nO(1) )/O(n), if there exists a device A which runs in polynomial time and satisfies the following: hP i k bk A solves MLXEB with probability q = PrC∼D k ,⃗ ⃗ ⃗ i=1 pCi (zi ) ≥ N , z ∼A(C)   ⃗ A < B bq−1−ϵ where ϵ = n−O(1) . H(Z|C) 2 b−1 LLQSV is a conjectured hard problem in [3] and it is proved that LLQSV(D) ∈ / QCAMTIME( B O(1) 2 n )/q(2 n ) in the random oracle model. Despite the above, it is currently hard to instantiate an experimentally viable protocol based on complexity-theoretic arguments. We instead rely on the following min-entropy bound obtained by using the assumption given below, which is supported by the complexity argument given in Section C as otherwise we could exploit the presumed structure to solve LLQSV with the gap required: B O(1)

▶ Assumption 1 (Unstructuredness of Random Circuit Sampling and Hardness of XEBscore ). Output distribution of sufficiently deep RCS circuits is “unstructured”. That is the classical description of the circuit does not leak any information about which output are heavy or light. Consequently, the best strategy for optimizing XEBscore is the frugal rejection sampling strategy described in [36] which approximately simulates the circuit classically and returns the output as it is. ▶ Remark 2. The above assumption is used in the Google quantum supremacy experiment [4]. A similar assumption is used in [3, 37, 7] and the assumption is analyzed in [2, 11]. For convenient we define the XEB test as follow.

9

10

Verifiable Random Sampling

▶ Definition 3 (TestXEBα,χ [36]). Let D be a probability distribution over quantum circuits on ⃗ := (C1 , . . . , CM ) drawn from Dk , a sample ⃗z = (z1 , . . . , zM ) ∈ ({0, 1}n )M , n qubits. Given C ⃗ ⃗z) is defined as follow: a threshold score χ and a test set size α, TestXEBα,χ (C, ( P 2n 1, if |V| i∈V pCi (zi ) ≥ χ + 1 where V ←$ {v : v ⊆ [M ] ∧ |v| = α}, ⃗ TestXEBα,χ (C, ⃗z) = 0, otherwise. Unstructuredness of RCS motivates the oracle-access model where the (classical) adversary is given a quantum computer resource as a query oracle that evaluates the quantum circuit honestly and returns the sampled output string. We follow Ref. [36], which specifically studies the case where the adversarial algorithm has just enough classical computing power to spoof M − QC⃗ number of samples and has to honestly return at least QC⃗ samples from the quantum computer within a time bound τres . However, we remark that our analysis can be straightforwardly extended to the more general adversary of Ref. [37], which we leave to future work. We first recall the simplified one-shot protocol without batching from [36] that proceeds as follows: ⃗ := 1. The (challenge) client pseudorandomly generates M -numbered n-qubits circuits C C1 , . . . , CM . 2. For each i ∈ [M ], the provider evaluates the circuits Ci |0n ⟩ and measures in computational basis to obtain zi . The provider then returns ⃗z := z1 , . . . , zM . ⃗ ⃗z) = 0 for some α, χ, otherwise the verifier 3. The (verifier) client aborts if TestXEBα,χ (C, outputs the sample ⃗z. Let ϵs ∈ (0, 1/4). Let I˜ be the classical side information consisting of the seed Kseed ⃗ and some side information S 0 . We now recall the used to generate the challenge circuit C min-entropy bound from [36] but we include the necessary assumptions made by [36] into the theorem statement. ▶ Theorem 4 (Entropy Guarantee, Theorem 1 [36]). Assuming the protocol described above and the adversary making at most QC⃗ queries to the quantum circuits oracle OC⃗ defined ⃗ ∼ Haar(N )M , that on input circuits C, ⃗ outputs Z = (z1 , . . . , zM ) , it holds below, where C that ϵs ˜ ≥ Qmin (n − 1) + log ϵs Hmin (Z|I) conditioned on non-aborting event Ω where Qmin = min{Q : ϵadv (Q, χ)2 ≥ 4ϵs }, Pr[Ω] is upper bounded by ϵadv (Q, χ). OC⃗ (i): //qC⃗ are initialized to 0 if qC⃗ > QC⃗ return ⊥ qC⃗ = qC⃗ + 1 ⃗ |0n ⟩) return Measure(C[i]

Next, from a string with enough smooth min-entropy, we can effectively extract ϵ−uniform randomness out of it using the strong two-source quantum-proof randomness extractor defined in the following:

2

ϵadv (Q, χ) is monotonically non-decreasing.

Y. Wei Zhu et al.

11

▶ Definition 5 (Two-Source Quantum-Proof Strong Extractor (Lemma 74, [37])). Let a function Ext : {0, 1}n1 ×{0, 1}n2 → {0, 1}ℓ be a quantum-proof strong (n1 , κ1 , n2 , κ2 , ℓ, ϵext ) two-source extractor. Then for any independent source ρX1 X2 E classical on Xi with Hmin (X1 |E)ρ ≥ κ1 ϵs and Hmin (X2 |E)ρ ≥ κ2 + log2 (1/ϵ2 ) where ϵ2 ∈ (0, 1) and ϵs ∈ (0, 1], we have ρExt(X1 ,X2 )Xi E − τℓ ⊗ ρXi E 1 ≤ 6ϵs + 2ϵext + 2ϵ2 where τℓ is a maximally mixed state on ℓ bits. We need strong quantum-proof randomness extractor because the weak source (in our case the provider’s output string) is supplied by the (potentially malicious) provider and the adversary may have quantum side-information on it. The second input that is held by the verifier is assumed to be secret and independent from the provider’s source. In this paper, we sometimes refer to the extractor’s second (private) input as seed3 .

3.2

Constructive Cryptography (CC)

In the framework of constructive cryptography (CC) [41, 43] (also known as abstract cryptography (AC) [42]), security is defined as the indistinguishability between two worlds, rather than a game between a challenger and an adversary. The model defines worlds using concepts of resources and converters, analogous to the functionalities and protocols defined in the Universal Composability (UC) model [15]. The CC framework has been used to analyze various cryptographic systems such as DIDComm [5], quantum key distribution (QKD) [52], ratcheting [30], functional encryption [40] and others [32, 51]. Resources expose interface(s) to which converter(s) can attach to. In the CC framework, the real world is composed of resources composed in parallel. Then, the protocol converter(s) are attached to the resources to convert them into other resources. The ideal world resource is made up of an ideal resource, to which a simulator is attached to. The privacy notion and other properties that should be exhibited by the protocol should be captured in the ideal resource. In the CC framework, we prove the following property πR ≈ϵ Sσ, where π represents the protocol executed on top of a real resource R and σ represents a simulator acting on an ideal resource S. It translates what the adversary can do in the real world (left side) into what the adversary needs to do in the ideal world (right side) to achieve the same result. Assuming that REAL := πR and IDEAL := Sσ expose the same interfaces, we now consider a distinguisher that attaches to the resources and tries to tell them apart. If any distinguisher can only succeed with negligible probability, then we achieve the indistinguishable property as required. Then, we say that π constructs S from R denoted π as R − → S. Composability. The construction notion briefly discussed above is proven to be composable in the CC framework [42, 41]. That is, π

π′

π ′ ◦π

R− → S ∧ S −→ T =⇒ R −−−→ T. Syntax. We follow the resource syntax from [5] when defining the interfaces that a resource exposes. The interfaces are defined by first specifying the party that the interface is

3

Note that the strong two-source extractor here allows either one of the sources to be public while the strong seeded extractor only allows the seed to be public.

12

Verifiable Random Sampling

exposed to, followed by the command as the first parameter while the rest of the parameters represent the inputs to the interface. For example, the command Post for the interface accessible to party i taking input m is defined as i(Post, m). We further use the syntax this to address the interface described in the resource itself.

4

Verifiable Random Sampling (VRS)

In this section, we describe the VRS syntax and security properties at a high level. The high-level overview for the use cases of VRS is given in Section 2.3.2. In Section A.1, we will reconcile the analysis and protocol given in the CC model in Section 5 with the high-level overview given below in Section A.1. First, we define Verifiable Random Sampling (VRS) using similar syntax to VRF as follows: ▶ Definition 6. Verifiable random sampling (VRS) is a tuple of algorithms VRSD := (Gen, Chal, Res, Eval) defined as follows: The following algorithms are executed by verifier V : (Seedchl , Seedext ) ← VRS.Gen(1λ ): On input a security parameter 1λ , outputs a challenge seed Seedchl and an extractor seed Seedext . ⃗ ⃗z): On input a challenge seed Seedchl , an ((u, σ)/⊥) ← VRS.Eval(Seedchl , Seedext , x, C, ⃗ and an extractor seed Seedext , an input string x ∈ {0, 1}ℓ , a quantum circuit vector C, n output string ⃗z ∈ {0, 1} , outputs a sample u with a proof σ or aborts with ⊥. The following algorithm is executed by client T : ⃗ ← VRS.Chal(Seedchl , x): On input a challenge seed Seedchl and an input string x ∈ C ⃗ {0, 1}ℓ , outputs a circuit vector C. The following algorithm is executed by provider P : ⃗ ⃗ outputs a classical output ⃗z ← VRS.Res(C): On input a quantum circuit vector C, response string y ∈ {0, 1}n . For the purpose of showing the security property captured by the ideal resource, we state informally the security properties that VRS should satisfies as follows: 1. Correctness: Eval outputs a valid sample u from the distribution D̃ when the protocol is executed honestly. 2. Non-deterministic / Freshness: Given two protocol executions of Chal, Res, Eval with the same inputs, the resulting outputs u, u′ are not the same, u ̸= u′ except with collision probability caused by the independent sampling from the output distribution. 3. Information-theoretic Randomness: The output distribution D̃ for samples u is statistically close to the ideal distribution D. We specifically model and proved the case where party T and party P are corrupted. We further discuss the trust model with different corruption patterns in Section A.2.

5

Verifiable Random Sampling from Quantum Random Circuit B3 Sampling, VRSD T,E

5.1

Overview

We first list the parties involved and their roles. We refer to Section 2 for a high-level overview of our scheme. The symbols used can be found in Figure 2.

Y. Wei Zhu et al.

13

Party. We model and analyze the case where the verifier V is an honest party while the client T and the provider P can be corrupted by the adversary. We further provide the analysis of different corruption patterns in Section A.2. The parties are summarized below: 1. P : Provider with access to the quantum computing resource, 2. E/A: Adversary, 3. T : Client who interacts with the provider to generate a timestamped transcript, 4. V : Verifier who would check the output of provider and finally outputs the final sample.

Symbol Symbol ⃗ C ⃗z n, N = 2n XEBscore aux B BID TXID T E τ CTX U, D

Meaning Certified Randomness Quantum circuit vector Response vector (Classical string) Number of qubits XEB test score Blockchain Block auxiliary information Blockchain block Block ID Transaction ID Block time bound Block entropy bound Timestamp Others Use case specific context Uniform and arbitrary distributions

B3T,E VRS AUT Seed π Hash() H() Hmin () ϵ Hmin () T, P, V E, A H C pub I

Meaning Model Blockchain Verifiable random sampling Communication channel Seed Protocol (Converter) Function Hash function von Neumann entropy Min-entropy Smooth min-entropy Parties Client, Provider, Verifier Adversary Honest party set Corrupted party set All party set Generic party set

Figure 2 Symbol Table.

In the rest of this section, we will first introduce various preliminary resources used for modeling the protocol in the context of CC such as blockchain B3T,E , a read-only storage resource with basic access control called the seed resource Seed, communication channel B3 resource AUT. Then, we introduce verifiable random sampling as an ideal resource VRSD T,E , followed by a protocol (πTVRS , πPVRS ,πVVRS ) that will construct the ideal resource, and finally we prove the security of our construction.

5.2

Messaging Channel, AUT

Authenticated channels are sufficient for our use cases, and our construction would work over insecure communication channels as well. We use the authenticated messaging channel from [40] denoted as resource AUTI→R . The authentication property of the messaging channel means that the adversary can neither modify any message nor impersonate either party. Slightly modifying the definition from [40], the authenticated channel can be defined as follows: ▶ Definition 7 (Adapted from [40]). An authenticated channel from initiator (I) to receiver (R), denoted by AUTI→R , with an eavesdropper (E), is a resource with three interfaces I, R, and E. On input a message m at interface I using the command Send, the same message can be read at interfaces R and E using the receive command Rec.

14

Verifiable Random Sampling

Resource B3T,E Init():

i(Read, id, txid := ∅):

i(Post, m):

M (Mine, τ, aux):

BID := 1

//i ∈ {P, E, T, V }

//i ∈ {P, E, T, V }

//Finalize Block

B∗ := ∅

//Read message

TXID ← Hash(BID||m)

if τ − B[BID − 1].τ ≥ T :

B := [B0 ]

if id = −1 :

//Record message

id := BID − 1

i(Latest): //Latest BlockID return BID − 1

if txid = ∅ :

return ⊥

B∗ [TXID] := m

B[BID] := (B∗ , τ, aux, BID)

return (BID, TXID)

B∗ := ∅

return B[id]

BID := BID + 1 return ok

else: return B[id][txid]

Figure 3 B3T,E - (Ideal) Batched bulletin board resource where BID is the unique sequential block identifier, B∗ is the latest pending block content, and B contains all historic block information. B∗ is appended to B when a new block is mined.

5.3

Bulletin Board in Timed Batched Mode with Auxiliary Information, B3T,E

The proposed scheme requires the existence of a public ledger that can record messages and later provide the recorded messages when queried. Our starting point is the bulletin board abstraction provided in [19, 24] for the UC model. The bulletin board allows the user to post an arbitrary message to the board and later retrieve it using the associated counter (denoted as BID). However, it is insufficient for our scheme, since we additionally require the pinned message to be batched into a time-sensitive sequential ordering where the time interval of each batch of posted messages is upper bounded by some bound T. While the notion of time is investigated in [34, 8, 38], these works are concerned with synchronized clocks for the purpose of synchronous computation in multi-party computation. In particular, the participants in our scheme do not need to have access to a synchronized clock, and it is sufficient for a trustworthy service to timestamp the message in a coarse manner. Combining the aforementioned properties, we give an ideal bulletin board resource with timed batched mode in the context of the CC model. Batched Bulletin Board resource, B3T,E . We assume that BID is a unique increasing block identifier, and we associate each batch with “block”. In practice, the blocks are published periodically within some time bound T with increasing BID. B3T,E provides timing guarantee such that for all valid id, B[id + 1].τ − B[id].τ < T. The timestamp τ is determined by the block miner. It is generally checked by consensus that the timestamp is reasonable and chronologically consistent. The block miner is considered to be honest, and its honest behavior is encouraged through an incentive mechanism (reward fees) as analyzed in [14] and [33], where the honest behavior is a Nash equilibrium [47]. Thus, we assume that the miner in this case will always behave honestly. We further denote the block auxiliary information (including the block header) as aux. In addition, we assume that the block hash contains some (computational) min-entropy lower-bounded by E. That is, comp Hmin (Hash(B, aux)) ≥ E, comp where Hmin is defined to be the HILL computational min-entropy [29, 6]. This assumption

Y. Wei Zhu et al.

15

is shown to hold for Bitcoin in [12], where it is analyzed that the computational min-entropy of the Bitcoin block header that is mined using a proof-of-work mechanism can be lowerbounded. We further discuss biasable block hashes and personalized randomness expansion in Section A.7. The blockchain resource is given formally in Figure 3, where i denotes the interface for blockchain users, and M denotes the interface for a miner. On the instantiation of B3T,E using existing Blockchains. While it is possible to instantiate batched bulletin board resource B3T,E using just a single central trusted party to perform all the computation and bookkeeping, it is often the case that the same functionality instantiated by distributed systems is more desirable due to the decentralization of trust. Blockchain, an append-only ledger that is maintained by ad-hoc communities, is a natural choice for the use case. Proof-of-work blockchains like Bitcoin [46] and proof-of-stake blockchains like Ethereum [61] are two of the most prominent blockchains. The block miners (proposers or validators), who are maintaining the state of the blockchain, are incentivized to produce a consistent state through an inherent reward structure and penalty system for malicious misbehavior. Similar reasoning is used in [19] to instantiate Bitcoin/Ethereum blockchain as the bulletin board.

5.4

B3

Ideal Verifiable Random Sampling Resource VRSD T,E B3

In this section, we describe the ideal VRS resource VRSD T,E and explain why it closely models the real-world setting. The ideal resource is parameterized by an internal blockchain resource B3T,E and the resulting target sample distribution D. The blockchain resource is used to record the response with a timestamp and to provide a string with sufficient min-entropy for the challenge circuit generation as described in Section 5.3. The resource captures the fact that the challenge circuits are derived by combining an input x, a context CTX, and blockchain data rather than by sampling directly from the challenge circuit distribution. This construction guarantees that the challenge circuits can only be known after the hash block header is mined, assuming all other inputs are predetermined, so that provider cannot pre-sample ahead of time. In response, the ideal resource samples from the intended response output distribution4 . Finally, the verifier V interface will only output a sample from u ∼ D if and only if the challenge circuit is correctly derived, the response is given within a reasonable time, and the given provider output string ⃗z passes the TestXEB test. This ensures a valid sample u is returned if and only if we are sure that the provider output string ⃗z contains enough entropy and is derived independently of the sampling extractor’s second input. We also make sure to take the earliest response string to avoid any protocol-level oversampling attempt. Let BIDτ denote the maximum tolerable block interval as specified in Figure 4. To apply Theorem 4, we set BIDτ · T ≤ τres , where τres is the maximum latency considered by Theorem 4. Let T denote the client, P denote the provider, V denote the verifier, and E denote the adversary. We denote pub := {T, P, V, E} to be the public set consisting of all parties, H to be the honest party set H := pub \ C, and C ⊆ pub to be the corrupted party set. A complete specification of the ideal resource VRS is given in Figure 4. In our use case, the verifier responsible for verifying the provider’s output string is assumed to be honest.

4

While it might seem that sampling from any source with sufficient entropy that still passes TestXEB is sufficient for the ideal resource specification for the honest interface P (Res), there might be a distribution where the former holds but it is distinguishable from the intended response output distribution in the real protocol instantiation.

16

Verifiable Random Sampling

B3

Resource VRSD T,E

//Variables representing communication

T (Chal, CTX, x): // T ∈ H b ·, aux, BIDC ) ← B3T,E .T (Read, B3T,E .T (Latest)) (B,

C, R := ∅

⃗ ← DeriveHaar(N )M (Hash(Hash(B, b aux)||CTX||x)) C

Init():

⃗ BIDC , CTX, x) C := (C,

E(Rec):

return ok

return (C, R)

V (Eval, CTX, x): // V ∈ H

T (Send, C′ ):

P (Send, R′ ):

C := C′

R := R′

return ok

return ok

P (Read):

V (Read):

⃗ ← DeriveHaar(N )M (Hash(Hash(B b∗ , aux∗ )||CTX∗ ||x∗ )) C

return C

return R

if ∃(BID′ , TXID′ ) s.t. (CTX∗ , x∗ ) ∈ B3T,E .V (Read, BID′ , TXID′ )

(⃗z, BIDR , TXID) := R ⃗ ∗ , BID∗C , CTX∗ , x∗ , ⃗z∗ ) ← B3T,E .V (Read, BIDR , TXID) (C

b∗ , ·, aux∗ , ·) ← B3T,E .V (Read, BID∗C ) (B

∧ BID′ < BIDR ∧ TXID′ < TXID :

P (Res): // P ∈ H

return ⊥//Abort on earlier reply, detect multi-attempt

⃗ BIDC , ·) := C (C,

u∼D

⃗ |0n·M ⟩ |2 ⃗z ∼ DC⃗ where DC⃗ (x) = |⟨x|C

(·, BIDmin , ·) := CTX

(BIDR , TXID) ← B3T,E .P (Post, (C, ⃗z))

⃗∗ = C ⃗ ∧ TestXEB(C, ⃗ ⃗z∗ , χ) ∧ BIDR − BID∗C ≤ BIDτ if C

R := (⃗z, BIDR , TXID) return ok

∧ CTX∗ = CTX ∧ BID∗C ≥ BIDmin ∧ x∗ = x : return u else : return ⊥

P (Res, R′ ): // P ∈ C R := R′

T (Chal, C′ ): // T ∈ C

return ok

C := C′ return ok

V (Eval, u): // V ∈ C return u

B3 ⃗ = (C1 ⊗ · · · ⊗ CM ). Figure 4 VRSD T,E - (Ideal) Verifiable Random Sampling resource where C H is the honest parties, and C are the corrupted parties. BIDτ is a timing parameter.

Communication. For communication between client T , provider P , and the verifier V , the resource assumes an authenticated communication channel with eavesdropper E, as captured by interface commands Read, Rec for parties (T, P, V ), E respectively. The ideal resource is defined in Section 5.2 and is used in the protocol construction in the next section. Seed. We model the extractor’s second input, the seed, as an ideal resource SeedI (see Figure 5) that stores and supplies a seed to any party in the set I. For example, by setting I := {V }, access to the seed is restricted to party V , making it a private seed. We defer the discussion of context-dependent seed initialization and instantiation to Section A.2. Domain Separator. We model the domain separator as an input CTX to the commands Chal and Eval. This models the requirement that the verifier V runs the verification algorithm and outputs the sample only if both the circuit-generating party T and the verifier V agree on the same context (e.g., session ID, party T ’s unique identifier, etc.) We further encode the verifier-specified challenge block constraint BIDmin within the context CTX, allowing the verifier to specify that the sampling must only occur at or after the block BIDmin .

Y. Wei Zhu et al.

17

Resource SeedℓI i(Read):

Init(): seed ←$ {0, 1}

ℓ

//i ∈ I return seed

Figure 5 SeedℓI Ideal random seed resource

5.5

VRS Verifiable Random Sampling Protocol Converter π{T,P,V }

We now discuss the real resource and the protocol converter. We start with the prominent use case considered during the construction of VRS in this paper. We discuss and showcase multiple different use cases and potential other instantiations in Section 2.3.2. In addition, we discuss different threat models or corruption patterns for VRS in Section A.2. Use Case. In practice, a server or an algorithm that needs a verifiable random value from a client party T will play the role of party V , for example to determine the lottery winner or to perform leader election. However, client T generally cannot prove that it performs random sampling correctly, but the client T still wants to supply its own sample rather than letting the verifier V pick a sample on its behalf. Client T together with provider P will jointly produce a verifiable sample from a specified distribution with some guaranteed min-entropy. Finally, the verifier V can perform the randomness extraction using the extractor from Definition 5. At this point, the sample can be proven to be a legitimate sample from the uniform distribution. Client T can ensure the last step is performed correctly using techniques B3 from Section A.2. We give the construction for VRSU T,E as follows: Client T . From the perspective of party T , it hashes the latest public blockchain data together with an input x and a context CTX to pseudorandomly derive context-specific ⃗ T then submits the challenge circuits to P . The protocol for party T is quantum circuits C. given in Figure 6. Prover P . The protocol for party P is given in Figure 6. The party P protocol is ⃗ |0n·M ⟩ and then measure simple. It just needs to evaluate the given quantum circuit vector C the resulting state. Then, it returns the measured bit-string ⃗z back to the requester. The provider P also needs to record its response on-chain using B3T,E .P (Post, m) so that the response is timestamped for some response message m. Verifier V . The verifier V tests that the on-chain response is consistent with its view ⃗ ⃗z) to ensure the received sample is a valid sample. V further and runs the test TestXEB(C, checks that there does not exist any other earlier response on-chain to prevent post-selection bias. Finally, it runs the randomness extractor on the received sample using a secret seed and outputs the distribution sample given by the randomness extractor. By the randomness extractor theorem, the sample is a sample from an ϵ−close uniform distribution. The concrete protocol is given in Figure 6.

5.6

Protocol Summary

The protocol can be summarized as follows: Step 0: Verifier V and client T optionally agree on the input x and context CTX used in the session. Otherwise, client T picks an input x and a context CTX itself.

18

Verifiable Random Sampling

Converter πTVRS Converter πVVRS

T (Chal, CTX, x): b ·, aux, BIDC ) ← B3T,E .T (Read, (B, B3T,E .T (Latest)) ⃗ ← DeriveHaar(N )M (Hash(Hash(B b C , aux)||CTX||x))

V (Read): R ← AUTP →V .V (Rec) return R

⃗ BIDC ) C := (C, AUTT →P .T (Send, C)

V (Eval, CTX, x): (⃗z, BIDR , TXID) ← this.V (Read)

return ok

⃗ ∗ , BID∗C , CTX∗ , x∗ , ⃗z∗ ) ← B3T,E .V (Read, BIDR , TXID) (C

b∗ , ·, aux∗ , ·) ← B3T,E .V (Read, BID∗C ) (B Converter πPVRS

⃗ ← DeriveHaar(N )M (Hash(Hash(B b∗ , aux∗ )||CTX∗ ||x∗ )) C if ∃(BID′ , TXID′ ) s.t. (CTX∗ , x∗ ) ∈ B3T,E .V (Read, BID′ , TXID′ ) ∧ BID′ < BIDR ∧ TXID′ < TXID :

P (Read): C ← AUT

T →P

return ⊥//Abort on earlier reply, detect multi-attempt

.P (Rec)

seedq ← SeedV .V (Read)

return C

u ← Ext(⃗z, seedq )

P (Res, ⃗z):

(·, BIDmin , ·) := CTX

⃗ BIDC ) ← this.P (Read) (C,

⃗∗ = C ⃗ ∧ TestXEB(C, ⃗ ⃗z∗ ) ∧ BIDR − BID∗C ≤ BIDτ if C ∧ CTX∗ = CTX ∧ BID∗C ≥ BIDmin ∧ x∗ = x :

⃗ |0n·M ⟩} ⃗z ← Measure(C

return u

(BIDR , TXID) ← B3T,E .P (Post, (C, ⃗z)) R := (⃗z, BIDR , TXID)

else : return ⊥

AUTP →V .P (Send, R) return ok

Figure 6 Converter πPVRS for emulating interface of P , converter πTVRS for emulating interface of T , and converter πVVRS for emulating interface of V of VRS

⃗ by deriving it from a combination of the latest block Step 1: Client T generates circuit C hash, input and the context, represented by T (Chal, CTX, x). ⃗ |0n·M ⟩ Step 2: Provider P gets the derived circuit C, samples from it by evaluating C and then measuring in the computational basis to obtain ⃗z. P then posts this output. The steps are represented by P (Res). Step 3: Verifier V verifies four things – no earlier transcript, consistency of circuit derived from block hash, ⃗z passes the TestXEB, and timing constraint. The steps are represented by V (Eval, CTX, x).

5.7

B3

Security Analysis for VRSU T,E

The following correctness theorem states that if all parties are honest, then the ideal resource B3 VRSU T,E where D := U is constructed. ▶ Theorem 8. For the protocols (πT , πP ), πV defined in Figure 6, we have that B3

πT πP πV (B3T,E ||AUTT →P ||AUTP →V ||SeedV ) ≈ VRSU T,E . Proof. The correctness of the proposed construction follows directly from the entropy

Y. Wei Zhu et al.

19

guarantee from Theorem 4 and randomness extractor Definition 5, and the rest by relabeling and inspection. ◀ We set H := {V } and C := {T, P } which is considered the main use case of our scheme. We prove the main security theorem of our scheme stated as the theorem below where the verifier V is honest and the provider P together with the client T are corrupted. We rely on composability theorem of CC framework to replace ideal resource with real resource. ▶ Theorem 9. Consider an ideal resource B3T,E from Figure 3, an ideal resource AUT from B3 Definition 7, an ideal resource Seed from Figure 5, and an ideal resource VRSU T,E from Figure 4, then there exists a negligible function ϵ such that B3

πV (B3T,E ||AUTT →P ||AUTP →V ||SeedV ) ≈ VRSU T,E σ{P,E,T } . Proof. Sketch. The full proof is provided in the Section E. We give the intuition of the proof. From the perspective of the distinguisher, the challenge circuit is generated using the randomness from the latest block hash and there is not enough time to spoof the output to reduce the min-entropy guarantee of the output string while still passing TestXEB. Similarly, the distinguisher also does not know at the time of response submission to the bulletin board, what seed will ultimately be used to derive the sample. Therefore, if the distinguisher does not have access to this “seed” randomness, it cannot distinguish the final random sample from an appropriately defined uniform distribution due to the statistical guarantee of the randomness extractor. ◀ B3

6

Extending VRSU T,E and Discussion

6.1

VRSD : VRS for Arbitrary Distribution

Rejection sampling [60] can be used to sample a target distribution f (x) given a source distribution g(x) that is easier to sample from. For example, it is used in lattice-based signatures [39] to sample from a distribution that is independent of the secret. However, existing works require a known source distribution g(x), whereas in our VRS instantiation, we may only be sampling from a distribution that is only ϵ−close to the intended source distribution because of the property of the randomness extractor (Definition 5). Therefore, we introduce and prove an error-version of the rejection sampling algorithm below. Rejection Sampling with Error. Rejection sampling [60] performs sampling from an arbitrary target distribution with known probability mass function f (x) given a source distribution g(x) by accepting samples drawn from g(x) with probability f (x)/(M · g(x)). Then, the final output distribution is indeed f (x). However, in practice, the available source distribution may differ from the ideal: we may only have access to g̃(x) := g(x) + η(x), where η(x) represents the error. Let the support be defined as supp(g) := {x ∈ X : g(x) ̸= 0}. We give a rejection sampling using the approximate source distribution g̃(x) and prove its properties with respect to a target distribution f˜(x) (with error) as follows: ▶ Lemma 10 (Rejection Sampling with Error). Let the ideal source PMF be g and ideal target PMF be f . Assume that f (x) ≤ M · g(x) for all x and supp(g̃) ⊆ supp(g). Given an actual source PMF g̃ where SD(g, g̃) = ϵ, the following algorithm, in expected steps at most M 2M ϵ ˜ ˜ ( 1−2M ϵ ), outputs a sample from a distribution whose PMF is f (x) where SD(f, f ) ≤ 1−2M ϵ if 2M ϵ < 1: 1. X ∼ g̃.

20

Verifiable Random Sampling

(X) 2. Output X with probability Mf·g(X) . Otherwise, go to step (1).

The proof is given in Section D. We are now ready to lift VRSU ,ϵu to VRSD,ϵd for any D where ϵu and ϵd are the distribution errors. We assume that the uniform samples suffice, which can be achieved by obtaining a longer uniform sample or repeating the protocol. Then, we apply 2M ϵu Lemma 10 to obtain a sample from the distribution D̃ such that SD(D̃, D) = ϵd ≤ 1−2M ϵu . Let acceptance probability be p := Pr[accept]. To ensure a negligible failure probability (1 − p)α ≤ 2−λ , it is sufficient to set the repetition factor α > (1/p)λ ln 2.

6.2

Different Corruption Patterns. B3

Our VRSU T,E is analyzed for when T and P are malicious and V is honest. Assuming the provider is always malicious, we provide analysis for different corruption patterns below: B3

1. (Honest T, V ; Malicious P ): VRSU T,E also captures this setting since the honest strategy is contained within arbitrary malicious strategies. 2. (Honest T ; Malicious P, V ): Since the verifier is dishonest, we consider the case that there exists a third party who is interested in the existence of a sample u given by the verifier V . In this case, T is that third party. First, the verifier uses the future block hash as the extractor’s second input to extract the final sample together with provider’s response string ⃗z. The third party (in this case T ) simply re-runs the verification algorithm but with the second input replaced as mentioned above. 3. (; Malicious T, P, V ): Similar to the above, except the third party is neither T, P, nor V . B3

Captured by VRSU T,E B3 Captured by VRSU T,E Item 2 Above Item 3 Above

Client T . ✓ ✓ .

Provider P . . . .

Verifier V ✓ ✓ . .

Table 2 Corruption Patterns. Provider is always malicious. ✓ is an honest party while . is a corrupted party.

Further Discussion. We defer discussion on the transition to fault-tolerant QC, performance, domain separation, and other topics to the Appendix.

7

Conclusion

In this work, we introduced verifiable random sampling (VRS), a new protocol which allows for publicly verifiable sampling from any target distribution in a composable manner. The protocol outputs information-theoretic randomness and is resistant to collusion. In addition, we prove security in the constructive cryptography (CC) model, ensuring composability. Building on experimentally demonstrated quantum certified randomness protocols, VRS is practical for deployment in today’s blockchain environments. The versatility of VRS is demonstrated through several use cases, including smart contract randomness and e-lotteries, applicable to blockchain. We believe that our protocol addresses a growing need for high quality randomness that is both unbiasable and verifiable. While our model is built on top of RCS, we leave it to future work to adapt our construction by basing the entropy source on preimage sampling in an NP-search problem. This regime is more relevant for fault-tolerant quantum computers of the future, and using them can make our construction more efficient. Additionally, in this work we analyze the security of the

Y. Wei Zhu et al.

model against a restricted class of adversaries. We believe this restriction can be lifted, and we leave this as an important direction for future work.

Acknowledgments We thank Pradeep Niroula for helpful discussions of random quantum circuit sampling and its applications. We thank Rob Otter for the executive support of the work and invaluable feedback on this project. The authors thank their colleagues at the Global Technology Applied Research center of JPMorganChase for their support.

Disclaimer This paper was prepared for informational purposes with contributions from the Global Technology Applied Research center of JPMorgan Chase & Co. This paper is not a product of the Research Department of JPMorgan Chase & Co. or its affiliates. Neither JPMorgan Chase & Co. nor any of its affiliates makes any explicit or implied representation or warranty and none of them accept any liability in connection with this paper, including, without limitation, with respect to the completeness, accuracy, or reliability of the information contained herein and the potential legal, compliance, tax, or accounting effects thereof. This document is not intended as investment research or investment advice, or as a recommendation, offer, or solicitation for the purchase or sale of any security, financial instrument, financial product or service, or to be used in any way for evaluating the merits of participating in any transaction. References 1 2 3

4 5

6 7

8

9

A reference for randomness beacons: Format and protocol version 2. NIST Technical Report, 05 2019. Scott Aaronson and Sam Gunn. On the classical hardness of spoofing linear cross-entropy benchmarking. Theory Comput., 16:1–8, 2020. Scott Aaronson and Shih-Han Hung. Certified randomness from quantum supremacy. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, page 933–944, 2023. Frank Arute et al. Quantum supremacy using a programmable superconducting processor. Nature, 574:505–510, October 2019. Christian Badertscher, Fabio Banfi, and Jesus Diaz. What did come out of it? analysis and improvements of didcomm messaging. In Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security, CCS ’24, page 4732–4746. ACM, December 2024. URL: http://dx.doi.org/10.1145/3658644.3690300, doi:10.1145/3658644.3690300. Boaz Barak, Ronen Shaltiel, and Avi Wigderson. Computational Analogues of Entropy, page 200–215. Springer Berlin Heidelberg, 2003. doi:10.1007/978-3-540-45198-3_18. Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn, and Avishay Tal. On certified randomness from fourier sampling or random circuit sampling. Quantum, 10:2002, February 2026. URL: http://dx.doi.org/10.22331/q-2026-02-10-2002, doi:10.22331/ q-2026-02-10-2002. Carsten Baum, Bernardo David, Rafael Dowsley, Jesper Buus Nielsen, and Sabine Oechsner. Tardis: A foundation of time-lock puzzles in uc. In Advances in Cryptology – EUROCRYPT 2021, page 429–459. Springer International Publishing, 2021. URL: http://dx.doi.org/10. 1007/978-3-030-77883-5_15, doi:10.1007/978-3-030-77883-5_15. Mihir Bellare, Hannah Davis, and Felix Günther. Separate Your Domains: NIST PQC KEMs, Oracle Cloning and Read-Only Indifferentiability, page 3–32. Springer International

21

22

Verifiable Random Sampling

10

11

12

13

14

15

16

17 18 19

20

21

22

23

24

Publishing, 2020. URL: http://dx.doi.org/10.1007/978-3-030-45724-2_1, doi:10.1007/ 978-3-030-45724-2_1. Mihir Bellare and Phillip Rogaway. Random oracles are practical: a paradigm for designing efficient protocols. In Proceedings of the 1st ACM conference on Computer and communications security - CCS ’93, CCS ’93, page 62–73. ACM Press, 1993. URL: http://dx.doi.org/10. 1145/168588.168596, doi:10.1145/168588.168596. Sergio Boixo, Sergei V. Isakov, Vadim N. Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J. Bremner, John M. Martinis, and Hartmut Neven. Characterizing quantum supremacy in near-term devices. Nature Physics, 14(6):595–600, April 2018. doi:10.1038/ s41567-018-0124-x. Joseph Bonneau, Jeremy Clark, and Steven Goldfeder. On bitcoin as a public randomness source. Cryptology ePrint Archive, Paper 2015/1015, 2015. URL: https://eprint.iacr.org/ 2015/1015. Fernando G. S. L. Brandão, Aram W. Harrow, and Michał Horodecki. Local random quantum circuits are approximate polynomial-designs. Communications in Mathematical Physics, 346(2):397–434, August 2016. URL: http://dx.doi.org/10.1007/s00220-016-2706-8, doi: 10.1007/s00220-016-2706-8. Vitalik Buterin, Daniel Reijsbergen, Stefanos Leonardos, and Georgios Piliouras. Incentives in ethereum’s hybrid casper protocol. In 2019 IEEE International Conference on Blockchain and Cryptocurrency (ICBC), page 236–244. IEEE, May 2019. URL: http://dx.doi.org/10. 1109/BLOC.2019.8751241, doi:10.1109/bloc.2019.8751241. Ran Canetti. Universally composable security: A new paradigm for cryptographic protocols. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 136–145. IEEE, 2001. Ignacio Cascudo and Bernardo David. SCRAPE: Scalable Randomness Attested by Public Entities, page 537–556. Springer International Publishing, 2017. doi:10.1007/978-3-319-61204-1_ 27. Chainlink. 35+ blockchain rng use cases enabled by chainlink vrf | chainlink. https://chain.link/education-hub/rng-in-blockchain-use-cases, 2025. Accessed: 2026/05/05. Wenjie Che, Fareena Saqib, and Jim Plusquellic. Puf-based authentication. In 2015 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pages 337–344. IEEE, 2015. Arka Rai Choudhuri, Matthew Green, Abhishek Jain, Gabriel Kaptchuk, and Ian Miers. Fairness in an unfair world: Fair multiparty computation from public bulletin boards. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS ’17, page 719–728. ACM, October 2017. URL: http://dx.doi.org/10.1145/3133956. 3134092, doi:10.1145/3133956.3134092. Hannah Davis, Denis Diemert, Felix Günther, and Tibor Jager. On the Concrete Security of TLS 1.3 PSK Mode, page 876–906. Springer International Publishing, 2022. URL: http: //dx.doi.org/10.1007/978-3-031-07085-3_30, doi:10.1007/978-3-031-07085-3_30. Frédéric Dupuis, Omar Fawzi, and Renato Renner. Entropy accumulation. Communications in Mathematical Physics, 379(3):867–913, 2020. URL: http://dx.doi.org/10.1007/ s00220-020-03839-5, doi:10.1007/s00220-020-03839-5. Muhammed F Esgin, Veronika Kuchta, Amin Sakzad, Ron Steinfeld, Zhenfei Zhang, Shifeng Sun, and Shumo Chu. Practical post-quantum few-time verifiable random function with applications to algorand. In International Conference on Financial Cryptography and Data Security, pages 560–578. Springer, 2021. Viktor Fischer and Miloš Drutarovský. True Random Number Generator Embedded in Reconfigurable Hardware, page 415–430. Springer Berlin Heidelberg, 2003. URL: http: //dx.doi.org/10.1007/3-540-36400-5_30, doi:10.1007/3-540-36400-5_30. Sivanarayana Gaddam, Ranjit Kumaresan, Srinivasan Raghuraman, and Rohit Sinha. Luciditee: Scalable policy-based multiparty computation with fairness. In Cryptology and Network

Y. Wei Zhu et al.

25

26

27 28 29

30

31

32

33

34

35

36 37

Security, page 343–367. Springer Nature Singapore, 2023. URL: http://dx.doi.org/10. 1007/978-981-99-7563-1_16, doi:10.1007/978-981-99-7563-1_16. Blaise Gassend, Dwaine Clarke, Marten van Dijk, and Srinivas Devadas. Silicon physical random functions. In Proceedings of the 9th ACM conference on Computer and communications security, CCS02, page 148–160. ACM, November 2002. doi:10.1145/586110.586132. Rosario Gennaro, Stanislaw Jarecki, Hugo Krawczyk, and Tal Rabin. Secure distributed key generation for discrete-log based cryptosystems. Journal of Cryptology, 20(1):51–83, May 2006. doi:10.1007/s00145-006-0347-3. Emanuele Giunta and Alistair Stewart. Unbiasable Verifiable Random Functions, page 142–167. Springer Nature Switzerland, 2024. doi:10.1007/978-3-031-58737-5_6. Z. Gutterman, B. Pinkas, and T. Reinman. Analysis of the linux random number generator. In 2006 IEEE Symposium on Security and Privacy (S&P’06). IEEE, 2006. Johan HÅstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28(4):1364–1396, January 1999. doi:10.1137/s0097539793244708. Daniel Jost, Ueli Maurer, and Marta Mularczyk. A unified and composable take on ratcheting. In Theory of Cryptography, page 180–210. Springer International Publishing, 2019. URL: http://dx.doi.org/10.1007/978-3-030-36033-7_7, doi:10.1007/978-3-030-36033-7_7. Gautam A. Kavuri, Jasper Palfree, Dileep V. Reddy, Yanbao Zhang, Joshua C. Bienfang, Michael D. Mazurek, Mohammad A. Alhejji, Aliza U. Siddiqui, Joseph M. Cavanagh, Aagam Dalal, Carlos Abellán, Waldimar Amaya, Morgan W. Mitchell, Katherine E. Stange, Paul D. Beale, Luís T. A. N. Brandão, Harold Booth, René Peralta, Sae Woo Nam, Richard P. Mirin, Martin J. Stevens, Emanuel Knill, and Lynden K. Shalm. Traceable random numbers from a non-local quantum advantage. Nature, 642(8069):916–921, 2025. URL: http://dx.doi.org/ 10.1038/s41586-025-09054-3, doi:10.1038/s41586-025-09054-3. Thomas Kerber, Aggelos Kiayias, and Markulf Kohlweiss. Composition with knowledge assumptions. In Advances in Cryptology – CRYPTO 2021, page 364–393. Springer International Publishing, 2021. URL: http://dx.doi.org/10.1007/978-3-030-84259-8_13, doi:10.1007/ 978-3-030-84259-8_13. Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov. Ouroboros: A provably secure proof-of-stake blockchain protocol. In Advances in Cryptology – CRYPTO 2017, page 357–388. Springer International Publishing, 2017. URL: http://dx.doi.org/10. 1007/978-3-319-63688-7_12, doi:10.1007/978-3-319-63688-7_12. Aggelos Kiayias, Hong-Sheng Zhou, and Vassilis Zikas. Fair and robust multi-party computation using a global transaction ledger. In Advances in Cryptology – EUROCRYPT 2016, page 705–734. Springer Berlin Heidelberg, 2016. URL: http://dx.doi.org/10.1007/ 978-3-662-49896-5_25, doi:10.1007/978-3-662-49896-5_25. Hugo Krawczyk. Cryptographic Extraction and Key Derivation: The HKDF Scheme, page 631–648. Springer Berlin Heidelberg, 2010. URL: http://dx.doi.org/10.1007/ 978-3-642-14623-7_34, doi:10.1007/978-3-642-14623-7_34. Minzhao Liu et al. Certified randomness with a trapped-ion quantum processor. Nature, 640:343–348, 2025. Minzhao Liu, Pradeep Niroula, Matthew DeCross, Cameron Foreman, Wen Yu Kon, Ignatius William Primaatmaja, M. S. Allman, J. P. Campora III, Akhil Isanaka, Kartik Singhal, Omar Amer, Shouvanik Chakrabarti, Kaushik Chakraborty, Samuel F. Cooper, Robert D. Delaney, Joan M. Dreiling, Brian Estey, Caroline Figgatt, Cameron Foltz, John P. Gaebler, Alex Hall, Zichang He, Craig A. Holliman, Travis S. Humble, Shih-Han Hung, Ali A. Husain, Yuwei Jin, Fatih Kaleoglu, Colin J. Kennedy, Nikhil Kotibhaskar, Nathan K. Lysne, Ivaylo S. Madjarov, Michael Mills, Alistair R. Milne, Kevin Milner, Louis Narmour, Sivaprasad Omanakuttan, Annie J. Park, Michael A. Perlin, Adam P. Reed, Chris N. Self, Matthew Steinberg, David T. Stephen, Joseph Sullivan, Alex Chernoguzov, Florian J. Curchod, Anthony Ransford, Justin G. Bohnet, Brian Neyenhuis, Michael Foss-Feig, Rob Otter, and Ruslan Shaydulin.

23

24

Verifiable Random Sampling

38

39

40

41

42 43

44

45

46 47

48

49

50

51

52

53

Certified randomness amplification by dynamically probing remote random quantum states, 2025. URL: https://arxiv.org/abs/2511.03686, arXiv:2511.03686. Chen-Da Liu-Zhang and Ueli Maurer. Synchronous constructive cryptography. In Theory of Cryptography, page 439–472. Springer International Publishing, 2020. URL: http://dx.doi. org/10.1007/978-3-030-64378-2_16, doi:10.1007/978-3-030-64378-2_16. Vadim Lyubashevsky. Lattice signatures without trapdoors. In David Pointcheval and Thomas Johansson, editors, Advances in Cryptology – EUROCRYPT 2012, pages 738–755, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. Christian Matt and Ueli Maurer. A definitional framework for functional encryption. In 2015 IEEE 28th Computer Security Foundations Symposium, page 217–231. IEEE, July 2015. URL: http://dx.doi.org/10.1109/CSF.2015.22, doi:10.1109/csf.2015.22. Ueli Maurer. Constructive cryptography – a new paradigm for security definitions and proofs. In Sebastian Mödersheim and Catuscia Palamidessi, editors, Theory of Security and Applications, pages 33–56, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. Ueli Maurer and Renato Renner. Abstract cryptography. In International Conference on Supercomputing, 2011. URL: https://api.semanticscholar.org/CorpusID:15503771. Ueli Maurer and Renato Renner. From indifferentiability to constructive cryptography (and back). In Theory of Cryptography, page 3–24. Springer Berlin Heidelberg, 2016. URL: http://dx.doi.org/10.1007/978-3-662-53641-4_1, doi:10.1007/978-3-662-53641-4_1. Tony Metger, Alexander Poremba, Makrand Sinha, and Henry Yuen. Simple constructions of linear-depth t-designs and pseudorandom unitaries. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), page 485–492. IEEE, October 2024. URL: http: //dx.doi.org/10.1109/FOCS61266.2024.00038, doi:10.1109/focs61266.2024.00038. Silvio Micali, Michael Rabin, and Salil Vadhan. Verifiable random functions. In 40th annual symposium on foundations of computer science (cat. No. 99CB37039), pages 120–130. IEEE, 1999. Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system. 2008. John F. Nash. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences, 36(1):48–49, January 1950. URL: http://dx.doi.org/10.1073/pnas.36.1.48, doi:10.1073/pnas.36.1.48. Charles W O’donnell, G Edward Suh, and Srinivas Devadas. Puf-based random number generation. In MIT CSAIL CSG Technical Memo, volume 481. MIT CSAIL Cambridge, MA, USA, 2004. Yuechen Pan, Yiwen Zhao, Xiaoguang Liu, Gang Wang, and Ming Su. Fplotto: A fair blockchain-based lottery scheme for privacy protection. In 2022 IEEE International Conference on Blockchain (Blockchain), pages 21–28, 2022. doi:10.1109/Blockchain55522.2022.00014. S. Pironio, A. Acín, S. Massar, A. Boyer de la Giroday, D. N. Matsukevich, P. Maunz, S. Olmschenk, D. Hayes, L. Luo, T. A. Manning, and C. Monroe. Random numbers certified by bell’s theorem. Nature, 464(7291):1021–1024, April 2010. URL: http://dx.doi.org/10. 1038/nature09008, doi:10.1038/nature09008. Christopher Portmann. Quantum authentication with key recycling. In Advances in Cryptology – EUROCRYPT 2017, page 339–368. Springer International Publishing, 2017. URL: http: //dx.doi.org/10.1007/978-3-319-56617-7_12, doi:10.1007/978-3-319-56617-7_12. Christopher Portmann and Renato Renner. Security in quantum cryptography. Reviews of Modern Physics, 94(2), June 2022. URL: http://dx.doi.org/10.1103/RevModPhys.94. 025008, doi:10.1103/revmodphys.94.025008. Amir Ali Pour, Vincent Beroulle, Bertrand Cambou, Jean-Luc Danger, Giorgio Di Natale, David Hely, Sylvain Guilley, and Naghmeh Karimi. Puf enrollment and life cycle management: Solutions and perspectives for the test community. In 2020 IEEE European Test Symposium (ETS), page 1–10. IEEE, May 2020. URL: http://dx.doi.org/10.1109/ETS48528.2020. 9131578, doi:10.1109/ets48528.2020.9131578.

Y. Wei Zhu et al.

54 55 56

57

58 59

60 61 62

John Preskill. Quantum computing and the entanglement frontier, 2012. URL: https: //arxiv.org/abs/1203.5813, doi:10.48550/ARXIV.1203.5813. Michael O Rabin. Transaction protection by beacons. Journal of Computer and System Sciences, 27:256–267, 1983. Ulrich Rührmair, Frank Sehnke, Jan Sölter, Gideon Dror, Srinivas Devadas, and Jürgen Schmidhuber. Modeling attacks on physical unclonable functions. In Proceedings of the 17th ACM conference on Computer and communications security, CCS ’10, page 237–249. ACM, October 2010. doi:10.1145/1866307.1866335. Ewa Syta, Philipp Jovanovic, Eleftherios Kokoris Kogias, Nicolas Gailly, Linus Gasser, Ismail Khoffi, Michael J. Fischer, and Bryan Ford. Scalable bias-resistant distributed randomness. In 2017 IEEE Symposium on Security and Privacy (SP), pages 444–460, 2017. doi:10.1109/SP. 2017.45. Marco Tomamichel, Roger Colbeck, and Renato Renner. A fully quantum asymptotic equipartition property. IEEE Transactions on information theory, 55(12):5840–5847, 2009. Meltem Sönmez Turan, Elaine Barker, John Kelsey, Kerry A McKay, Mary L Baish, and Mike Boyle. Recommendation for the entropy sources used for random bit generation. Special Publication (NIST SP). Report No. 800-90B (NIST, 2018). John Von Neumann. 13. various techniques used in connection with random digits. Appl. Math Ser, 12(36-38):3, 1951. Gavin Wood et al. Ethereum: A secure decentralised generalised transaction ledger. Ethereum project yellow paper, 151:1–32, 2014. Takashi Yamakawa and Mark Zhandry. Verifiable quantum advantage without structure. Journal of the ACM, 71(3):1–50, June 2024. URL: http://dx.doi.org/10.1145/3658665, doi:10.1145/3658665.

A

Deferred Discussion

A.1

Reconciliating VRS specified in Section 5 with VRS Overview from Section 4

Security Properties. It can be seen that the correctness property informally stated in Section 4 is captured by Theorem 8. The non-deterministic randomness property is captured by the fact that the V -interface from the ideal resource given in Figure 4 always outputs a “fresh” sample from the intended distribution as output when given x as input. For non-deterministic sample generation within the same block epoch and the same input x, we rely on the domain separation CTX where CTX is the domain separating string as discussed in Section A.4. The information theoretic randomness property is captured by the fact that the V -interface outputs random sample from the intended output distribution. Algorithm Mapping. VRS.Gen is the setup algorithm that generates the necessary challenge seed and extractor seed. We assume the setup is done correctly and model the extractor seed as an ideal resource Seed which specifies the exact parties that have access to the Seed resource. We further discuss different setup instantiations for seed in Section A.2. The challenge seed Seedchl is derived using hash function on a blockchain hash, a context CTX, and an input x. VRS.Chal, VRS.Res, and VRS.Eval are modeled in the ideal resource B3 VRSD T,E given in Figure 4 with some minor modifications.

A.2

Different Instantiation and Setup

‘Private’ Seed Setup. The seed (extractor’s second input) is required to be unknown to the provider at the time of the response submission. We specifically model the seed as a verifier’s private seed to achieve this. For use cases where there does not exist private

25

26

Verifiable Random Sampling

storage for the verifier V , we can make use of the future unpredictable block hash as a second entropy source for the randomness extractor. We use this approach for smart contract use cases as described in Section 2.3.2. If the verifier is composed of distributed entities, then we can make use of common MPC techniques such as distributed key generation (DKG) [26] to derive a reconstructible shared common seed as described in Section 2.3.2.

A.3

Transitioning from Today’s Quantum Computing Devices to Future Fault-Tolerant Quantum Computing Devices B3

Our VRSU T,E is constructed using RCS-based challenge-response as the entropy source. RCSbased challenge-response works over today’s noisy QC device as demonstrated in [36, 37] experimentally with complexity-theoretic foundation from [3]. However, this approach is time-sensitive whereby we have to bound the provider’s response time and we have to set the difficulty of the problem to be not too hard as the verifier needs to compute the TestXEB which is considered computationally expensive. Fortunately, our VRS construction can be made more efficient by basing the entropy source on sampling pre-image in a NP-search problem that is solvable by quantum polynomial-time machines but not by classical probabilistic polynomial-time machines as studied in [62]. However, it requires operations that are not feasible on today’s QC devices. Assuming there will be fault-tolerant quantum computing devices in the future, we can instantiate VRS based on the aforementioned pre-image sampling problem instead. Notably, the framework developed in this work can be modified from being RCS-based challenge-response to the pre-image search challenge-response.

A.4

Domain Separation

Domain separation is encouraged in hash functions where instead of computing Hash(x), we compute Hash(CTX||x) instead for some context string CTX [9]. Similarly, we have that the VRS protocol also takes in as input a context CTX where CTX can represent clientverifier public keys, session ID, and many other use-cases-specific contexts. The CTX can be deterministic and has no entropy but it has to be unique for the context it operates in. For example, we can pass in the smart contract address as context to derive challenge circuits for a specific smart contract V . Context enables different challenge circuits to be derived deterministically for different client contexts CTX in the same block epoch.

A.5

Instantiation Analysis

Experiments on the RCS-based certified randomness protocol are reported in [36, 37]. In particular, [37] derives concrete parameter settings and estimates the expected verification cost in GPU hours where the GPU hours are with respect to Intel Data Center GPU Max with approximately 46 TeraFLOPS theoretical peak performance. In that work, the effective latency is modeled as TM /nparallel , where TM denotes the time between the moment the circuit (or the measurement basis) is revealed and the moment the response is received considering the base unit nparallel = 1, and nparallel is the number of quantum-computing resources available to the prover. In a blockchain setting, TM is likely to remain relatively fixed, but the prover can increase nparallel to handle more challenge circuits simultaneously, thereby reducing the effective latency per unit circuit. If this effective latency becomes sufficiently small, the validation cost could drop below one GPU hour. Since validation is fully parallelizable, validation time on the order of minutes is achievable through straightforward parallelization.

Y. Wei Zhu et al.

A.6

27

Advantage of VRS in the Malicious Client Setting

Let us work in a setting in which the client is rationally malicious, attempting to maximize value for themselves, and the provider is honest. Now consider a transformation of our VRS protocol which replaces the circuit generator and quantum server with a classical VRF. Within an epoch of time T , the output of this transformed protocol is precisely determined by the inputs submitted by the client. If a client submits the same input twice within this epoch of period T , the output is identical. Therefore, a client can perform a grinding attack by submitting a set S of inputs and choosing xmax ∈ S such that Utility (Output(xmax )) = max Utility (Output(y)) , y∈S

where Output is a map defined as the VRF output for a given input, and Utility is a well-defined map on possible client inputs during the epoch quantifying the utility of the output for the client. Note that Output is well-defined for our protocol under replacement of the circuit generator and server with a classical VRF, by the determinism of a classical VRF. In our proposed VRS (with the circuit generator and quantum server as originally proposed), there is no well-defined analogue to Output due to freshness. Freshness ensures a resubmission of the same input yields different outputs with high probability. Therefore, while the client can grind and obtain circuits a priori within an epoch of time T , they cannot effectively grind for optimal output as they can under replacement with a classical VRF.

A.7

Others

When Blockchain Fails. We further provide analysis for when the assumption that blockchain provides entropy fails. We assume the blockchain hash contains enough computational entropy [12] to argue about the pseudorandomness of the circuits generated. For the case that the blockchain entropy is slightly biasable, the block hash entropy is reduced by a few bits. Our scheme will remain secure under this few-bit biasability scenario. Why not just use existing blockchain entropy? Blockchain entropy can be interpreted as a source of randomness from a randomness beacon. The randomness is broadcast at a relatively fixed interval. VRS provides a way to verifiably “expand” the number of samples extractable from a single-source of randomness. Importantly, the samples extracted will be different for different parties CTX even though they rely on the same source of randomness without any extra entropy source from their end. Importantly, the VRS protocol converts any source of pseudo-randomness into information-theoretic randomness. Provider’s Authentication. The provider might be rewarded based on the quality of the response it returns. Note that our scheme implicitly captures the authentication aspect for the response it submits by requiring the provider to submit to the blockchain through signing the response as a transaction. The verification algorithm can simply, in addition, check that the response is submitted by the provider it requested using the provider’s public key.

B

Deferred Preliminaries

▶ Definition 11 (VRF). Verifiable random function (VRF) is a tuple of algorithms VRF := (VRF. Gen(·), VRF. Eval(·), VRF. Vfy(·)) defined as follows: (SK, PK) ← VRF. Gen(1λ ): On input a security parameter 1λ , outputs a secret key SK and public key PK.

28

Verifiable Random Sampling

(y, π) ← VRF. Eval(SK, x): On input a secret key SK and an input string x ∈ {0, 1}ℓ , outputs y ∈ {0, 1}n and a proof π. b ← VRF. Vfy(PK, x, y, π): On input a public key PK, an input string x, an output string y, and a proof π, outputs a bit b ∈ {0, 1}, VRF satisfies the following properties: 1. Correctness - ∀λ ∈ N, ∀(SK, PK) in the image of VRF. Gen(1λ ), ∀x, and ∀(y, π) in the image of VRF. Eval(SK, x), VRF. Vfy(PK, x, y, π) = 1. 2. Unique Provability - ∀ PK (not necessarily generated by VRF. Gen(), ∀x ∈ {0, 1}L , ∀y0 , y1 ∈ S, and all possible proofs π0 , π1 , we have (VRF. Vfy(PK, x, y0 , π0 ) = VRF. Vfy(PK, x, y1 , π1 ) = 1) =⇒ y0 = y1 . In other words, ∀x ∈ {0, 1}L , ∃ a valid proof for at most one y value. 3. Pseudorandomness - ∀ PPT adversaries A = (A1 , A2 ), we have h i 1 vrf Advvrf ≤ negl(λ). A (λ) := Pr ExpA (λ) = 1 − 2 Algorithm 1 The VRF Security Experiment : Expvrf A (λ) 1: b ←$ {0, 1} 2: (pk, sk) ←$ VRF.Gen(1λ ) O

3: (x⋆ , state) ← A1 eval

(·)

(pk) 4: (y0 , π) ← VRF.Eval(sk, x⋆ ) 5: y1 ←R S O (·) 6: b′ ← A2 eval (state, yb ) 7: return b == b′

Algorithm 2 The VRF Evaluation Oracle : Oeval (x) 1: if x = x⋆ then 2:

return ⊥

3: end if 4: (y, π) ← VRF.Eval(sk, x) return (y, π)

C

Complexity of RCS

We first recall the definition for (Mixed) Linear Cross-Entropy Benchmark MLXEBb,k (D) metric from [36] for some distribution D. ▶ Definition 12 (MLXEBb,k (D) [36]). Let D be a probability distribution over quantum circuits ⃗ := (C1 , . . . , Ck ) drawn from Dk , output sample ⃗z = (z1 , . . . , zk ) ∈ on n qubits. Given C n k ({0, 1} ) such that k 1X b pC (zi ) ≥ . k i=1 i N

Y. Wei Zhu et al.

We usually consider the case that D ∼ Haar(N ). We now recall the complexity class needed for the paper. ▶ Definition 13 (Quantum classical Arthur-Merlin (QCAM)). Let x be a statement and L be a language. The complexity class QCAM consist of languages L for which there exists a quantum polynomial-time algorithm V (Arthur) and a polynomial p such that the following hold: If x ∈ L, then there exists a polynomial q and a polynomial-length classical string w ∈ {0, 1}q|x| such that Prr∈{0,1}p|x| [V (x, r, w) accepts] ≥ 2/3. If x ∈ / L, then for every a polynomial q and every polynomial-length classical string w ∈ {0, 1}q|x| such that Prr∈{0,1}p|x| [V (x, r, w) accepts] ≤ 1/3. QCAMTIME(T )/q(A) is the generalization of QCAM whereby the verifier can use running time of T and receives A bits of quantum advice that only depends on n. The following problem that is conjectured to be hard in [3]. The same assumption is used to demonstrate quantum supremacy [54] through random circuit sampling (RCS) in the original Google quantum supremacy experiment [4]. ▶ Definition 14 (Long List Quantum Supremacy Verification (LLQSV)). Given a list of M = O(N 3 ) circuit-string tuples {(Ci , si ) : i ∈ [M ]} such that Ci ∼ D, distinguish the cases: Yes-case: for each i ∈ [M ], si is sampled from Ci . No-case: for each i ∈ [M ], si is sampled uniformly at random and thus is independent of Ci . In addition, it is proved that the following assumption hold in the random oracle model, i.e. LLQSV(D) ∈ / QCAMTIME(2B nO(1) )/q(2B nO(1) ). ▶ Assumption 2 (Long List Hardness Assumption (LLHAB (D) [3] ). There exists no QCAM protocol for which quantum Arthur solves LLQSV in time 2B nO(1) given access to a quantum advice of length 2B nO(1) . / QCAMTIME(cn )/q(cn ) ▶ Theorem 15 ([3] Theorem 5.21 ). Relative to a random oracle, LLQSV ∈ for some constant 1 < c < 2. We now state the result from [36] that says passing MLXEB with low von Neumann entropy means solving LLQSV, in other words, LLQSVB (D) ∈ QCAMTIME(2B nO(1) )/O(n). ▶ Theorem 16 (Passing MLXEB test with low entropy solves LLQSV(Theorem 8, [36])). There exists a quantum-classical Arthur-Merlin protocol which on input an O(n)-bit advice string solves LLQSVB (D) which means LLQSVB (D) ∈ QCAMTIME(2B nO(1) )/O(n), if there exists a device A which runs in polynomial time and satisfies the following: hP i k bk A solves MLXEB with probability q = PrC∼D k ,⃗ ⃗ ⃗ i=1 pCi (zi ) ≥ N , z ∼A(C)   ⃗ A < B bq−1−ϵ where ϵ = n−O(1) . H(Z|C) 2 b−1 As a direct corollary, we have the following theorem that bound the entropy obtained assuming LLHA hardness assumption hold. ▶ Theorem 17 (Entropy Guarantee, Theorem 6 [36]). Assuming that LLHAB (D) for distribution D over quantum circuits acting on n qubits, given any device that on input takes k ⃗ ∼ Dk outputs a classical string Z := (z1 || . . . ||zk ) ∈ {0, 1}nk independently sampled circuits C solving MLXEBb,k with probability q, it holds that   ⃗ ≥ B bq − 1 − n−ω(1) . H(Z|C) 2 b−1

29

30

Verifiable Random Sampling

Therefore, assuming that LLHAB (D) for distribution D over quantum circuits acting on n qubits, we can derive entropy from the output string from the algorithm. We can further derive smooth min-entropy lower bounded by the von Neumann entropy by repetition using Entropy Accumulation Theorem (EAT) [21].

D

Deferred Proofs

Proof. We will now prove Lemma 10. Let g̃(x) = g(x) + η(x) where 12 that SD(g, g + η) = ϵ. We compute probability of acceptance first.

P

x |η(x)| = ϵ such

Pr[accept] = Pr[x = 0] · Pr[accept|x = 0] + · · · X f (x) = (g(x) + η(x)) · M · g(x) x ! X 1 f (x) = 1+ η(x) · M g(x) x 1 (1 + δ) M 1 ≤ (1 + |δ|) M ! X f (x) 1 1+ |η(x)| · ≤ M g(x) x X 1 ≤ (1 + |η(x)|M ) M x =

≤

(LoTP)

(δ =

f (x) x (η(x) · g(x) ))

P

(tri.ineq) (x) ≤ M) ( fg(x)

1 + 2ϵ, M

1 1 1 and Pr[accept] = M (1 + δ) ≥ M (1 − |δ|) ≥ M (1 − 2M ϵ). Note that |δ| ≤ 2M ϵ < 1. Thus,

f˜(x) = Pr[X = x|accept] = Pr[X = x] · Pr[accept|X = x] · 1/ Pr[accept]   1 f (x) · 1/ (1 + δ) = (g(x) + η(x)) · M · g(x) M   f (x) η(x) = · 1+ . 1+δ g(x) Finally, the error is given by   f (x) η(x) f˜(x) − f (x) = 1+ − f (x) 1+δ g(x)   f (x) η(x) = −δ . 1 + δ g(x)

Y. Wei Zhu et al.

31

The statistical difference is then SD(f˜, f ) = =

1X ˜ f (x) − f (x) 2 x  1 X f (x) η(x) 2

x

1+δ

g(x)

 −δ

  η(x) 1 X f (x) g(x) − δ = 2 x |1 + δ|   X η(x) 1 f (x) = −δ 2|1 + δ| x g(x) !   X X 1 η(x) ≤ f (x) + |f (x)δ| 2|1 + δ| g(x) x x !  X 1 f (x) ≤ |η(x)| · + |δ| 2|1 + δ| g(x) x

(tri.ineq)

1 (2M ϵ + 2M ϵ) 2|1 + δ| 1 ≤ (2M ϵ) |1 + δ| 1 ≤ (2M ϵ) |1 − |δ|| 1 ≤ (2M ϵ) 1 − 2M ϵ ≤

(reverse tri.ineq, |δ| < 1)

◀

E

Deferred Security Proof

Proof. We will prove Theorem 9 by providing a simulator σ and a sequence of hybrids H0 , · · · , H4 such that for any (classical5 ) probabilistic polynomial-time distinguisher D: B3

πV (B3T,E ||AUTT →P ||AUTP →V ||SeedV ) ≈ VRSU T,E σ{P,E,T } . We start by specifying the simulator σ{P,E,T } given in Figure 7. The simulator is a straightforward proxy to the internal interface since we do not make use of any secret in the ideal resource. We give the distinguisher D access to OC⃗ that operates exactly like the oracle defined in Theorem 4. Note that the query count QC⃗ is tracked separately for each different ⃗ corresponding to a new session. Then, we proceed to show a sequence of indistinguishable C hybrids. Hybrid H0 . This hybrid is the same as πV (B3T,E ||AUTT →P ||AUTP →V ||SeedV ). Hybrid H1 . This hybrid is the same as previous one except we abort when there is a collision of circuits provided by in DeriveHaar(N )M in any of the previous session. The collision

5

The result should naturally extends to the quantum distinguisher if we use the min-entropy from complexity guarantee stated at Theorem 17.

32

Verifiable Random Sampling

probability is negligible. Hybrid H2 . This hybrid is the same as previous one except we abort when the verification ⃗ ⃗z) passes but the Q ⃗ < Qmin where Qmin is defined as in Theorem 4. This TestXEB(C, C hybrid transition make use of the fact that adversary cannot spoof more than specified or else it fails with overwhelming probability. Since the protocol matches that of Theorem 4, we have that the abort condition is negligible. That is the verification passes with at most negligible probability Pr[Ω] = 4ϵs when QC⃗ < Qmin and ϵs is negligible. Hybrid H3 . This hybrid is the same as H2 except that instead of sampling circuit u using extractor on the response recorded on-chain with the second extractor input provided by SeedV , we sample u b uniformly from U. Since u is the output from randomness extractor ϵ defined in Definition 5 and assume that ⃗z fulfills Hmin and seedq fulfills Hmin requirement, we have that the distinguishing advantage between the state where u is returned and the state where u b is returned is upper bounded by the trace distance 6 21 (6ϵs + 2ϵext + 2ϵ2 ) which is negligible. Since extractor second input trivially satisfies the min-entropy requirement ℓseed > κ1 , we now show that the smooth min-entropy requirement for ⃗z is satisfied. We consider the case that the distinguisher D has the exact computational capacity specified in Section 3.1 and has access to the quantum circuit query oracle OC⃗ . b Assuming B3T,E bulletin board entropy E is sufficiently high, the block hash Hash(B||aux) contains enough entropy and the distinguisher cannot guess it in advance except querying it at the latest block where it is first published. Since the distinguisher do not have enough time to completely spoof the output sample against pseudorandomly but freshly generated challenge circuit, it is forced to returns valid quantum sample in some of the output string Z = ⃗z. Let BIDC⃗ be the block where challenge circuit is derived from and BIDJ be the block where the response can be submitted to just in time for any Q-query bounded algorithm that can only spoof at most M − QC⃗ samples that still passes the TestXEB when rest of QC⃗ samples come from ideal quantum circuit evaluation (response from OC⃗ ). From the block timing guarantee defined in Section 5.3 and the aforementioned conditions, by ensuring B3T,E time bound T ≤ τres , we have that B[BIDJ ].τ − B[BIDC⃗ ].τ ≤ τres . Since there is at least Qmin quantum samples because of the abort condition in the previous hybrid and considering the scenario described matches exactly that of assumption made in Theorem 4, then using Assumption 1 and Theorem 4, it can be concluded that ϵs ˜ ≥ Qmin (n − 1) + log ϵs . Hmin (Z|I)

Assume that Qmin (n − 1) + log ϵs ≥ κ2 + log2 (1/ϵ2 ) , we conclude that the change is indistinguishable. Hybrid H4 . This hybrid is the same as H3 except we re-label the communication channel B3 and the seed to the symbol used in the ideal resource with simulator VRSU T,E σP ∪E . Therefore, H4 ≡ H3 .

6

Trace distance T (ρ, σ) := 12 ∥ρ − σ∥1 quantifies the distinguishing advantage between two quantum states ρ and σ.

Y. Wei Zhu et al.

33

At this point with H4 , conditioned on non-aborting events, it can be seen that the distribution of transcript when interacting with H4 is identically distributed as interacting B3 with VRSU T,E σP ∪E . ◀

Simulator σ{P,E,T } Emulating E(Rec):

Emulating T (Chal, C′ ): // T ∈ C

return call E(Rec)

return call T (Send, C′ )

Emulating P (Read): // P ∈ C

Emulating T (Send, C′ ): // T ∈ C

return call P (Read)

return call T (Send, C′ )

Emulating P (Res, R′ ): // P ∈ C

Emulating P (Send, R′ ): // P ∈ C

return call P (Send, R′ )

return call P (Send, R′ )

Figure 7 Simulator σ{P,E,T } for VRS.