Quantum Security of a Compact Multi-Signature

Abstract

With the rapid advances in quantum computing, quantum security is now an indispensable property for any cryptographic system. In this paper, we study how to prove the security of a complex cryptographic system in the quantum random oracle model. We first give a variant of Zhandry’s compressed random oracle (CStO), called a compressed quantum random oracle with adaptive special points (CStO_s). Then, we extend the on-line extraction technique of Don et al. (EUROCRYPT’22) from CStO to ${\mathbf{CStO}}_s$. We also extend the random experiment technique of Liu and Zhandry (CRYPTO’19) for extracting the $\mathbf{CStO}$ query that witnesses the future adversarial output. With these preparations, a systematic security proof in the quantum random oracle model can start with a random CStO experiment (that extracts the witness for the future adversarial output) and then converts this game to one involving ${\mathbf{CStO}}_s$. Next, the online extraction technique for ${\mathbf{CStO}}_s$ can be applied to extract the witness for any online commitment. With this strategy, we give a security proof of our recent compact multi-signature framework that is converted from any weakly secure linear ID scheme. We also prove the quantum security of our recent lattice realization of this linear ID scheme by iteratively applying the weakly collapsing protocol technique of Liu and Zhandry (CRYPTO 2019). Combining these two results, we obtain the first quantum security proof for a compact multi-signature.

1. Introduction

A multi-signature scheme allows a group of signers to jointly generate a signature while any subset of them cannot represent the group. This mechanism was introduced by Itakura and Nakamura [1] with the motivation to reduce the signature size. In the blockchain application [2], it is also demanded that the aggregated public key that represents the group should also have a small size, as it will be part of the transaction and the network storage. The blockchain has no control over a user, and hence, one should be able to freely decide his public keys. Accordingly, we must make sure that it is secure against a rogue key attack: the attacker might choose his public key after seeing other signers’ public keys. In a poorly designed scheme, an attacker could manage to decide the secret key of the aggregated public-key. In addition, with the advances of quantum computing, the quantum attack places a major threat to any cryptographic system. Especially, the RSA based multi-signature (such as [3]) is no longer secure [4]. In this paper, we investigate the multi-signature security in the quantum random oracle model, where the attacker has an internal quantum computer and also can access to the quantum random oracle. We aim to develop quantum random oracle techniques that enable a security proof of a complex cryptographic system. We then apply it to prove the security of our recent compact multi-signature.

1.1. Related Works

A multi-signature scheme [1] is a special case of aggregate signature [5], where each signer of the latter can sign a possibly different message. Since it was introduced by Itakura and Nakamura [1], it has been intensively studied in the literature [3,6,7,8,9,10,11,12,13,14]. However, most of schemes are based on some variants of a discrete logarithm assumption, which does not hold under a quantum attack [4]. There are multi-signatures that are based on quantum mechanics only (i.e., without a computational hardness assumption) [15,16]. However, their schemes are certainly not what is understood in the crypto community: (1) signers need to share a private key with a trusted party; (2) the verification is completely done by the trusted party; and (3) the signer has no public key.

Constructions from lattice assumptions such as (ring-)LWE are potentially the solutions for the quantum-secure multi-signature problem. However, there are currently only very few schemes [17,18,19,20,21,22] from this. In addition, some schemes [19,20] are known to be insecure [21,23]. Schemes [17,18,22,23,24,25,26] did not consider a quantum attacker. Fukumitsu and Hasegawa [27] is the only previous scheme that considered the quantum security. Their construction is based on Dilithium signature [28]. However, their scheme only allows a constant number of signers, and the verification requires all signers’ public keys. Their proof technique (also that of Dilithium [28]) seems to rely on the statistical lossy property of the underlying ID scheme, and it is unclear if it can be generally usable in other security analysis. In this paper, we investigate general quantum random oracle techniques that are useful in proving a wide class of random oracle-based systems. With this, we prove the quantum security of our recent multi-signature framework [23].

The random oracle basically models a hash function as a completely random function. It was first proposed by Bellare and Rogaway [29]. This methodology has a heuristic assumption: when the random oracle is replaced by a cryptographic hash function, the security will be preserved. This generally is not true [30]. However, the counter example does not seem realistic. So, the crypto community still widely believes that this methodology is practically meaningful. Furthermore, it greatly simplifies the construction of many cryptographic systems and the proof in the classical random oracle model is usually amazingly simple. However, it is not true in the quantum world. The great advantage of a classical random oracle is that the simulator can easily record the attacker’s query history. In the quantum setting, this is difficult as an attacker can query a superposition. If the simulator makes a measurement on the query, it will destroy the quantum state. Zhandry [31] proposed new techniques to record the oracle query, which is called a compressed random oracle ($CStO$). Essentially, if the oracle is only queried q times, then the oracle can be compactly represented as a superposition of a database, with the basis record only containing at most q non-trivial values. Don et al. [32] showed a simulation that can extract an oracle query of a (classic) commitment on the fly. The impact of this feature is that if an adversary outputs a commitment value, we can immediately extract his query input that matches this commitment. This will not destroy the quantum state essentially because when an attacker outputs his classical commitment, he must have already made the measurement. Hence, this gives us a very useful tool, especially when a simulator needs to know the query in order to continue the simulation. However, this is not enough in some proofs. For example, in our multi-signature scheme, the adversary will receive a honest user’s public key $p{k}_1$ and then generate two public keys $p{k}_2,p{k}_2$. At the end, he will try to forge a signature with respect to a combined public key $F(p{k}_1,p{k}_2,p{k}_3)$ that is computed from $H\left(p{k}_i\right|p{k}_1\left|p{k}_2\right|p{k}_3)$ for $i=1,2,3$, and H is the random oracle. The problem is that $p{k}_2,p{k}_3$ will be revealed only at the end of the game. If the simulator wishes to know it in advance, it is impossible using the techniques in [32]. Liu and Zhandry [33] presented a measurement technique to extract $p{k}_2,p{k}_3$ during the game involving $CStO$. Essentially, it chooses a random query and measures it. Then, the outcome is $p{k}_i|p{k}_1\left|p{k}_2\right|p{k}_3$ for some i with a good probability. Furthermore, the adversary success probability for the forgery will be degraded only by a polynomial fraction. For technique reasons, it is desired that the simulator can set the random oracle value of the measure outcome $p{k}_i|p{k}_1\left|p{k}_2\right|p{k}_3$ (called a special point) to a value of his favorite. To take the advantage of both extraction techniques, one might consider the simulation of [32] with the measurement techniques in [33]. However, there are two issues. First, some verification measurements in [33] will be done on the random oracle database, and hence, the extraction theorems in [32] will no longer hold. Second, the special input measurement [33] is operated only once. This sometimes is insufficient to produce a witness for the final adversary output. Our work in this paper is to propose an improved $CStO$ that addresses the two issues and then apply the improved random oracle techniques to prove the security of our recent compact multi-signature scheme [23].

1.2. Contribution

In this paper, we study how to improve $CStO$ so that it still has a simulator (similar to [32]) that allows us to extract a query input of any given commitment on the fly but additionally also allows us to adaptively specify a small number of special points and set their random oracle values according to our own choices. The improved random oracle is called a compressed random oracle with adaptive special points (${\mathbf{CStO}}_s$). We generalize the simulator and extraction theorem in [32] to the ${\mathbf{CStO}}_s$ setting. We also generalize the experiment sampling technique in [33] to allow samplings for several times. This allows us to extract the witness of the final adversary output, where this witness might depend on several random oracle queries (that are measured during the game). This random experiment can be easily converted to an interaction with CStO_s oracle, and hence, the foregoing online extraction technique can be applied. With this improved random oracle technique, we show that our recent multi-signature framework (which is converted from any weakly secure linear identification scheme) is provably secure in the quantum random oracle model. The proof strategy is to use the sequence of the game technique. It starts the adversary with a standard quantum random oracle and then continues with the compressed quantum random oracle (CStO) while preserving the same adversary success probability. It next applies the random experiment sampling techniques, which degrades the adversary success only by a polynomial fraction, but it can extract the witness for the final adversary output. Then, we convert the random experiment (with $\mathbf{CStO}$) to one involving ${\mathbf{CStO}}_s$. Finally, the online extraction technique is used to simulate the interaction without the knowledge of the secret of an ID scheme. This allows us to reduce the adversary success to the security of the ID scheme. We also prove the quantum security of the JAK ID scheme in [23]. The main tool to achieve this is to use the collapsing sigma protocol technique in [33] that was originally proposed by Unruh [34]. Essentially, our security proof is to formulate the JAK ID security game into two public-coin protocols, each of which uses the collapsing property to guarantee the non-negligibility of the adversary success probability. This two-step analysis allows us to reduce the adversary success probability in attacking the JAK ID scheme to break the underlying ring-SIS assumption.

This paper is organized as follows. In Section 2, we present some essential notations and definitions that will be used in the paper. In Section 3, we present some basic properties in quantum computing that are useful in this work. In Section 4, we present CStO and our extension to ${\mathbf{CStO}}_s$. In Section 5, we show how to measure the record in ${\mathbf{CStO}}_s$ to see if a given relation R is satisfied or not. In Section 6, we show how to extract a query x in ${\mathbf{CStO}}_s$ that satisfies a given commitment $t=f(x,RO(x\left)\right)$. In Section 7, we extend the query extraction technique of Liu and Zhandry [33] that witnesses the future adversarial output. In Section 8, we prove the quantum security of our previous multi-signature framework using the techniques in Section 6 and Section 7. In Section 9, we prove the quantum security of the JAK ID scheme, which together with the multi-signature theorem, gives the first quantum security of a compact multi-signature scheme. The last section is the conclusion.

2. Preliminaries

Notations. 

We will use the following notations:

• $x\leftarrow S$ samples x uniformly random from a set S.
• For a randomized algorithm A, $u=A(x;r)$ denotes the output of A with input x and randomness r, while $u\leftarrow A\left(x\right)$ denotes the random output (with unspecified randomness).
• Min-entropy $H_{\infty }\left(X\right)=-log({max}_{x}log{P}_X\left(x\right))$. This is widely known as the worst uncertainty of X, while the well-known Shannon entropy $H\left(X\right)$ is its average uncertainty.
• A concatenating with B is denoted by $A|B$ and also by $(A,B)$ (if the context is clear).
• A non-negative function negl$\left(\lambda \right)$ is negligible if it vanishes faster than any polynomial fraction. That is, for any polynomial $poly\left(\lambda \right)$, there exists $N>0$ so that when $\lambda >N$, it holds that $\mathsf{negl}\left(\lambda \right)<1/poly\left(\lambda \right)$.
• $\left[\nu \right]$ denotes set $\{1,\cdots ,\nu \}.$
• ${\mathcal{Y}}^{\mathcal{X}}$ denotes the set of vector $\mathbf{y}:={\left\{y_x\right\}}_{x\in \mathcal{X}}$. That is, each entry in $\mathbf{y}$ is indexed by $x\in \mathcal{X}.$ We use $\mathbf{y}\left(x\right)$ to denote the entry $y_x.$

2.1. Ring and Module

In this section, we review math concepts: the commutative ring and module (see [35] for details). We start from the integer set $\mathbb{Z}$. It is clear that it has a multiplicative identity of 1 (so $1·z=z$ for any $z\in \mathbb{Z}$) and an additive identity of 0 (so $0+z=z$ for any $z\in \mathbb{Z}$). It forms a group under operator +. But, it is not a group under multiplication as any integer other than −1, as 1 has no inverse in $\mathbb{Z}.$ But, it is associative: $\left(ab\right)c=a\left(bc\right)$. It satisfies the distributive law: $a(b+c)=ab+ac$ and $(b+c)a=ba+ca$. Actually, $\mathbb{Z}$ is a special case of a general concept ring. In this work, we are only concerned with a commutative ring.

A commutative ring A is a set associated with multiplication and addition operators that is respectively written as a product and a sum, satisfying the following conditions for any $a,b,c\in A$:

• R-0. It has a unit 1 and is commutative under multiplication: $ab=ba$ and $\mathbf{1}a=a.$
• R-1. A is a commutative group under addition operator + with identity element 0.
• R-2. A is associative under multiplication operator: $\left(ab\right)c=a\left(bc\right).$
• R-3. It satisfies the distributive law: $a(b+c)=ab+ac$ and $(b+c)a=ba+ca.$

For simplicity, we use the term ring to represent a commutative ring in this paper. If A is a ring with $\mathbf{0}\ne \mathbf{1}$, and every non-zero element in A has an inverse, then A is a field. The rational number set $\mathbb{Q}$, the real number set $\mathbb{R}$, and the complex number set $\mathbb{C}$ are all examples of a field.

Another concept of our interest is the module. A module is actually a simple generalization of a vector space. Recall that a vector space is an additive group V that is associated with a coefficient field $F.$ We can take $V={\mathbb{R}}^n$ and $F=\mathbb{R}$ as an example. In this example, it is distributive: (1) for ${\mathbf{v}}_1,{\mathbf{v}}_2\in V,r\in F,$ it has $r({\mathbf{v}}_1+{\mathbf{v}}_2)=r{\mathbf{v}}_1+r{\mathbf{v}}_2$; (2) for $r_1,r_2\in F,\mathbf{v}\in V,$ it has $(r_1+r_2)\mathbf{v}=r_1\mathbf{v}+r_2\mathbf{v}.$ It is also associative: for $r,s\in F$ and $\mathbf{v}\in V$, it has $\left(rs\right)\mathbf{v}=r\left(s\mathbf{v}\right).$ Also, trivially, $1\mathbf{v}=\mathbf{v}.$ This notation can be generalized so that the coefficient set F is a ring (not just a field). In fact, $F=\mathbb{Z}$ is a good example for this. Also, the addition in V and the addition in F do not need to be the same; similarly, the multiplication between F and V and the multiplication in F do not need to be the same. With these changes in mind, the formal definition of a module can be given as follows.

Definition 1.

Let R be a ring. An additive group M (with group operator ⊞) is a R-module if (1) it has defined a multiplication operator • between R and M: for any $r\in R,m\in M$, $r•m\in M$; and (2) the following conditions are satisfied: for any $r,s\in R$ and $x,y\in M$:

1. 

$r•(x⊞y)=(r•x)⊞(r•y)$;

2. 

$(r+s)•x=(r•x)⊞(s•x)$

3. 

$\left(rs\right)•x=r•(s•x)$

4. 

$1_R•x=x$, where $1_R$ is the multiplicative identity of R.

2.2. Elements of Quantum Computing

We give a brief introduction to quantum computing through a list of notations and some facts, with interpretations if necessary; see [36,37] for details:

• A quantum system is a finite-dimensional complex vector space (called Hilbert space) $\mathcal{H}$ with an inner product $\langle ·|·\rangle$.
• The state of a quantum system in $\mathcal{H}$ is a unit vector $|\psi \rangle$. Its conjugate transpose is denoted by $\langle \psi |.$
• Let $\mathcal{Y}$ be a finite Abelian group. We use ${\left\{\right|y\rangle \}}_{y\in \mathcal{Y}}$ to represent an orthonormal basis for $\mathcal{H}={\mathbb{C}}^{\left|\mathcal{Y}\right|}$. We denote $\mathcal{H}$ by $\mathbb{C}\left[\mathcal{Y}\right]$ to emphasize that $\mathcal{H}$ is expanded by ${\left\{\right|y\rangle \}}_{y\in \mathcal{Y}}$.
• For two quantum systems ${\mathcal{H}}_1$ and ${\mathcal{H}}_2$, the joint system is a tensor product ${\mathcal{H}}_1\otimes {\mathcal{H}}_2$.
• For $|{\psi }_1\rangle \in {\mathcal{H}}_1$ and $|{\psi }_2\rangle \in {\mathcal{H}}_2$, their product state in ${\mathcal{H}}_1\otimes {\mathcal{H}}_2$ is $|{\psi }_1\rangle \otimes |{\psi }_2\rangle$. We write it as $|{\psi }_1\rangle |{\psi }_2\rangle$ for simplicity.
• A quantum register is a system holding the quantum state. It is the quantum analogue of the classical processor register. We use ${|\psi \rangle }_A$ to represent the register A containing quantum state $|\psi \rangle .$
• For an ordered set $\mathcal{X}=\{x_1,\cdots ,x_n\}$, $\mathbb{C}{\left[\mathcal{Y}\right]}^{\otimes \mathcal{X}}$ represents the tensor product of $\left|\mathcal{X}\right|$ copies of $\mathbb{C}\left[\mathcal{Y}\right]$ with the ith copy labeled by $x_i.$
• Assume that quantum system $\mathcal{H}$ has an orthonormal basis $\left\{\right|{\psi }_1\rangle ,\cdots ,|{\psi }_n\rangle \}$. With this, a quantum state $|\psi \rangle \in \mathcal{H}$ can be represented as $|\psi \rangle ={\sum }_{i=1}^n{\lambda }_i|{\psi }_i\rangle$, with ${\sum }_i{\left|{\lambda }_i\right|}^2=1.$
• Let $\mathcal{L}\left(\mathcal{H}\right)$ denote the set of linear operators from $\mathcal{H}$ to $\mathcal{H}$. For $A,B\in \mathcal{L}\left(\mathcal{H}\right)$, their commutator is defined as $[A,B]=AB-BA.$
• Physically realizable quantum operations on $\mathcal{H}$ are unitaries and measurements.
• A unitary U on $\mathcal{H}$ is an operator from $\mathcal{H}$ to $\mathcal{H}$ with $U{U}^{†}=I$, where $U^{†}$ is the conjugate transpose of U.
• Measurement $M={\left\{M_i\right\}}_i$ on a quantum state $|\psi \rangle \in \mathcal{H}$ is the operator for extracting the classical information from $|\psi \rangle$, where each $M_i$ must be Hermitian (i.e., $M_i^{†}=M_i$) and satisfies the completeness condition ${\sum }_i{M}_i^{†}{M}_i=I.$ When M is applied, it will result in a post-measurement state $M_i|\psi \rangle /\left|\right|M_i|\psi \rangle ||$ with probability $\left|\right|M_i{|\psi \rangle ||}^2$.
• A quantum algorithm A is represented by a sequence of unitaries/measurements. Due to deferred measurement principle ([36], p. 186), the measurement can be deferred to the end of operations of A. Hence, whenever applicable, we assume that A before the final measurement is represented by a list of unitaries $U_1,\cdots ,U_{\ell }.$
• If $|1\rangle ,\cdots ,|n\rangle$ is an orthonormal basis of $\mathcal{H}$, then $P={\sum }_{k\in A}|k\rangle \langle k|$ for $A\subset \left[n\right]$ is a projector from $\mathcal{H}$ onto the subspace expaned by ${\left\{\right|k\rangle \}}_{k\in A}$.
• The norm of linear operator A on $\mathcal{H}$ is defined as $\left|\right|A\left|\right|={max}_v\left|\right|A|v\rangle ||$, where $|v\rangle$ goes over all the possible unit vectors in $\mathcal{H}.$ According the singular value decomposition theorem, we can write $A={\sum }_i{\lambda }_i|v_i\rangle \langle y_i|$, where $\left\{\right|v_i\rangle {\}}_i$ and $\left\{\right|y_i\rangle {\}}_i$ are, respectively, a set of orthonormal vectors in $\mathcal{H}$ and ${\left\{{\lambda }_i\right\}}_i$ is the set of positive singular values of A. Hence, $\left|\right|A\left|\right|={max}_i{\lambda }_i$.
• For states $|{\psi }_i\rangle$ and $0\le {\lambda }_i\le 1,i=1,\cdots ,n$ with ${\sum }_{i=1}^n{\lambda }_i=1,$$\rho ={\sum }_{i=1}^n{\lambda }_i|{\psi }_i\rangle \langle {\psi }_i|$ is called a mixed state or simply state when the context is clear. When $\left\{\right|{\psi }_i\rangle {\}}_i$ are orthonormal, $\rho$ can be explained as $|{\psi }_i\rangle$ is sampled with probability ${\lambda }_i.$
• The trace distance between two mixed states $\rho ,\sigma$ is defined as $D_t(\rho ,\sigma )={\displaystyle \frac{1}{2}}\mathsf{tr}\left(\right|\rho -\sigma \left|\right),$ where $\left|A\right|:=\sqrt{A^{†}A}$. If $\rho ={\sum }_{i=1}^n{p}_i|{\psi }_i\rangle \langle {\psi }_i|$ and $\sigma ={\sum }_{i=1}^n{q}_i|{\psi }_i\rangle \langle {\psi }_i|$ for orthonormal basis $\left\{\right|{\psi }_i\rangle {\}}_i$; then, $D_t(\rho ,\sigma )={\displaystyle \frac{1}{2}}{\sum }_{i=1}^n|p_i-q_i|$, which coincides with the statistical distance of distributions $P=(p_1,\cdots ,q_n)$ and $Q=(q_1,\cdots ,q_n).$

2.3. Multi-Signature

In this section, we introduce the multi-signature and its security model.

2.3.1. Syntax

A multi-signature scheme is a protocol that allows a group of signers to jointly generate a signature. The signers can generate their public/private keys independently without a trusted party. The signers have a joint public key (called an aggregated public key) that is derived from all signers’ public keys. The signature should be valid against their aggregated public key. The multi-signature is motivated by the blockchain application, where one can pay to the signers through the aggregated public key, and the signers can spend the received money by jointly generating a multi-signature as an authorization of their pay. This system must be able to prevent an attacker (possibly an insider) from forging a signature under the aggregated public key.

A straightforward multi-signature is to let all signers generate individual signatures and concatenate them together. But in this case, the signature size is linear in the number of signers. A good multi-signature should be much shorter, and the aggregated public key is desired to be as short as possible too. This is because the both signature and the aggregated public key will be part of the transaction in the blockchain application.

Definition 2.

A multi-signature scheme is a quadruple of algorithms (Setup, KeyGen, Sign, and Verify) described as follows.

• Setup. Given $1^{\lambda }$, it generates a system parameter param. Note: param should be part of the input for KeyGen, Sign, and Verify. But, we usually omit it for brevity.
• KeyGen. It takes param as input and generates a private key $sk$ and a public key $pk$. In applications, this will be executed by a user himself.
• Sign. Given public keys $(p{k}_1,\cdots ,p{k}_n)$ and a message M user i has the private key $s{k}_i$ with respect to $p{k}_i$. Then, they interact with each other and finally output a signature σ with respect to an aggregated public key $\overline{pk}:=F(p{k}_1,\cdots ,p{k}_n)$, where F is called an aggregation function.
• Verify. Upon $(\sigma ,M)$ and an aggregated public key $\overline{pk}=F(p{k}_1,\cdots ,p{k}_n)$, the verifier outputs either 1 (for accept) or 0 (for reject).

Remark 1.

The aggregated key $\overline{pk}$ carries the information of the signers’ public keys. It is desired that it has a size independent of n. But, this is not enforced in the definition.

2.3.2. Security Model

In the following, we define the existential unforgeability of a multi-signature in the quantum random oracle model. Essentially, it says that no quantum adversary can forge a valid signature on a new message as long as the signing group contains an honest member. Toward this, the attacker can access to a signing oracle and quantum random oracle and create fake public keys at will. In the blockchain setting, this captures the security concern: an attacker can create many fake accounts, but he cannot represent a group containing a honest user to enable a transaction without this honest user’s participating, even if the attacker has seen many transactions involving this user. We consider the security in the quantum setting, where the attacker could have an internal quantum computer, and its quantum state will be updated after each interaction with an external challenger. This captures the concern that the attacker makes use of an internal quantum computer to help break the multi-signature system that is used externally. Formally, the multi-signature security is defined through a game between a challenger $\mathsf{CHAL}$ and a quantum attacker $\mathcal{A}$ that has oracle access to the quantum random oracle and signing oracle from CHAL.

Initially, CHAL generates param and a challenge public key $p{k}^{\ast }$ with a private key $s{k}^{\ast }$. It then provides $p{k}^{\ast }|\mathsf{param}$ to $\mathcal{A}$, who has an initial state $|\psi \rangle ={\sum }_{xyw}{\lambda }_{xyw}{|x\rangle }_X{|y\rangle }_Y{|w\rangle }_W$, where $X,Y,W$ represent the query register, response register, and working register, respectively. Next, $\mathcal{A}$ interacts with CHAL through the signing oracle and random oracle $RO$ and finally generates a forgery.

• Sign$(PK,M)$. Here, $PK$ is a set of distinct public keys with $p{k}^{\ast }\in PK$. Upon this query, CHAL represents the signer of $p{k}^{\ast }$, and $\mathcal{A}$ represents signer of $PK-\left\{p{k}^{\ast }\right\}$ to run the signing protocol on message M. Finally, it outputs the multi-signature $\sigma$ (if it succeeds) or ⊥ (if it fails).
• RO. $\mathcal{A}$ can query the random oracle $RO$ by providing his $XY$ registers to $\mathsf{CHAL}$, who applies $RO$ on $XYD$ so that ${RO|x\rangle }_X{|y\rangle }_Y{|H\rangle }_D=|x\rangle |y+H\left(x\right)\rangle |H\rangle ,$ where H is the random function, and D is the random oracle register maintained by a challenger. Finally, it returns registers $XY$ back to $\mathcal{A}$. See the first paragraph of Section 4.1 for details.
• Forgery. Finally, $\mathcal{A}$ outputs a signature ${\sigma }^{\ast }$ for a message $M^{\ast }$ with respect to a set of distinct public keys $(p{k}_1^{\ast },\cdots ,p{k}_N^{\ast })$ such that $p{k}^{\ast }=p{k}_i^{\ast }$ for some i. $\mathcal{A}$ succeeds if (a) $\mathsf{Verify}(\overline{p{k}^{\ast }},{\sigma }^{\ast },M^{\ast })=1$ and (b) $((p{k}_1^{\ast },\cdots ,p{k}_N^{\ast }),M^{\ast })$ were not issued to $\mathbf{Sign}$ oracle. We denote a successful forgery event by $\mathbf{succ}$.

Definition 3.

A multi-signature scheme (Setup, KeyGen, Sign, and Verify) is existentially unforgeable against a chosen message attack (or EU-CMA for short) in the quantum random oracle model if the following holds:

• Correctness. For $(s{k}_1,p{k}_1),\cdots ,(s{k}_n,p{k}_n)$ generated by KeyGen, the signature generated by signing an algorithm on a message M will pass the verification, except for a negligible probability.
• Existential Unforgeability. For any quantum polynomial time adversary $\mathcal{A}$ in the above forgery game, $Pr\left(\mathbf{succ}\right(\mathcal{A}\left)\right)$ is negligible.

2.4. Canonical Linear Identification

An identification system is a protocol that allows a user who has a public key and a private key to prove that he is the owner of the public key. Here, the public key is known to the verifier, while the private key is known only to the prover. A canonical identification system is a three-round public coin protocol where the first round message is from the prover, while the second message is a random number from the verifier. In addition, the first message has a super logarithmic entropy, which guarantees that correctly guessing it is difficult. The formal definition is presented as follows (also see Figure 1).

Definition 4.

A canonical identification scheme with parameter $\tau \in \mathbb{N}$ is a quadruple of algorithms $\mathcal{ID}=(\mathbf{Setup},\mathbf{KeyGen},P,V_{\tau })$, where Setup takes security parameter λ as input and generates a system parameter param; KeyGen is a key generation algorithm that takes param as input and outputs a public key $pk$ and a private key $sk$; P is an algorithm executed by Prover; and $V_{\tau }$ is an algorithm parameterized by τ and executed by Verifier. $\mathcal{ID}$ is a three-round protocol, where Prover starts with a committing message $\mathrm{CMT}$ with $H_{\infty }\left(\mathrm{CMT}\right)=\omega (log\lambda )$, then Verifier replies with a challenge $\mathrm{CH}\leftarrow \mathsf{\Theta }$, and finally Prover finishes with a response $\mathrm{Rsp}$, which will be either rejected or accepted by $V_{\tau }$.

The domains of $sk$, $pk$, CMT, and Rsp are respectively denoted by $\mathcal{SK},\mathcal{PK},\mathcal{CMT},\mathcal{RSP}.$ We are interested in a canonical ID scheme with linearity [23] and simulability in the following sense.

The motivation for the linearity is that if we linearly combine the transcripts of two protocol executions (with probably different provers), they become the identification transcript of the linearly combined public keys. This property will be used to combine the several ID transcripts into a compact multi-signature.

• Linearity: A canonical ID scheme $\mathcal{ID}=(\mathbf{Setup},\mathbf{KeyGen},P,V_{\tau })$ is linear if it satisfies the following conditions:

  1.

  $\mathcal{SK},\mathcal{PK},\mathcal{CMT},\mathcal{RSP}$ are $\mathcal{R}$-modules for some ring $\mathcal{R}$ with $\mathsf{\Theta }\subseteq \mathcal{R}$ (as a set);

  2.

  For any ${\lambda }_1,\cdots ,{\lambda }_t\in \mathsf{\Theta }$ and public/private pairs $(s{k}_i,p{k}_i)$ ($i=1,\cdots ,t$), we have that $\overline{sk}={\sum }_{i=1}^t{\lambda }_i•s{k}_i$ is a private key of $\overline{pk}={\sum }_{i=1}^t{\lambda }_i•p{k}_i$.

  Note: The operator • between $\mathcal{R}$ and $\mathcal{SK}$ (respectively defined as $\mathcal{PK},\mathcal{CMT},\mathcal{RSP}$) might be different. But, we will use the same symbol • as long as it is clear from the context.

  3.

  Let ${\lambda }_i\leftarrow \mathsf{\Theta }$ and $(p{k}_i,s{k}_i)\leftarrow \mathbf{KeyGen}\left(1^{\lambda }\right),$ for $i=1,\cdots ,t.$ If ${\mathrm{CMT}}_i\left|\mathrm{CH}\right|{\mathrm{Rsp}}_i$ is a faithfully generated transcript of the ID scheme with respect to $p{k}_i$, then

  $$V_{\tau }(\overline{pk},\overline{\mathrm{CMT}}\left|\mathrm{CH}\right|\overline{\mathrm{Rsp}})=1,$$

  (1)

  where $\overline{pk}={\sum }_{i=1}^t{\lambda }_i•p{k}_i,\overline{\mathrm{CMT}}={\sum }_{i=1}^t{\lambda }_i•{\mathrm{CMT}}_i$ and $\overline{\mathrm{Rsp}}={\sum }_{i=1}^t{\lambda }_i•{\mathrm{Rsp}}_i$.

  Note: we require Equation (1) to hold only if the keys and transcripts are faithfully generated. If some are contributed by an attacker, this equality might fail.

• Simulability. $\mathcal{ID}$ is simulatable if there exists a polynomial time algorithm SIM such that for $(sk,pk)\leftarrow \mathbf{KeyGen}\left(1^{\lambda }\right)$, $\mathrm{CH}\leftarrow \mathsf{\Theta }$, and $(\mathrm{CMT},\mathrm{Rsp})\leftarrow \mathbf{SIM}(\mathrm{CH},pk,\mathsf{param})$, it holds that $\mathrm{CMT}\left|\mathrm{CH}\right|\mathrm{Rsp}$ is indistinguishable from a real transcript, even if the quantum distinguisher is given $pk|\mathsf{param}$ and has access to oracle ${\mathcal{O}}_{id}(sk,pk)$, where ${\mathcal{O}}_{id}(sk,pk)$ acts as follows: $(st,\mathrm{CMT})\leftarrow P\left(\mathsf{param}\right)$; $\mathrm{CH}\leftarrow \mathsf{\Theta }$; $\mathrm{Rsp}\leftarrow P\left(st\right|sk|pk,\mathrm{CH})$; output $\mathrm{CMT}\left|\mathrm{CH}\right|\mathrm{Rsp}.$

Now, we define the security for a linear ID scheme. Essentially, it is desired that an attacker is unable to impersonate a prover with respect to an aggregated public key, where at least one of the participating public keys is not generated by an attacker. Here, we use the aggregated public key as the challenge key, because we will later convert an ID scheme into a multi-signature scheme. while the unforgeability security of a multi-signature is against the aggregated public key. In addition, we consider the security in the quantum setting: although the protocol itself does not involve a quantum message, an attacker could have a quantum computer internally and use this computer to help attack the classical protocol. Toward this, we allow the attacker to have an internal quantum state and will update it after receiving each message externally.

Definition 5.

A canonical identification scheme $\mathcal{ID}=(\mathbf{Setup},\mathbf{KeyGen},P,V_{\tau },\mathsf{\Theta })$ with linearity and $\tau \in \mathbb{N}$ is secure if it satisfies correctness and security below.

• Correctness. When no attack presents, Prover will convince Verifier.
• Soundness. For any quantum polynomial time algorithm $\mathcal{A}$, $Pr(EX{P}_{\mathcal{ID},\mathcal{A}}=1)$ is negligible, where $EX{P}_{\mathcal{ID},\mathcal{A}}$ is defined below with $p{k}_i\in \mathcal{PK}$ for $i\in \left[t\right]$ and $\overline{pk}={\sum }_{i=1}^t{\lambda }_i•p{k}_i$.
• Experiment $Ex{p}_{\mathcal{ID},\mathcal{A}}\left(\lambda \right)$
    param $\leftarrow \mathbf{Setup}\left(1^{\lambda }\right)$;
    $(p{k}_1,s{k}_1)\leftarrow \mathbf{KeyGen}\left(\mathsf{param}\right)$;
    $\left(\right|s{t}_0\rangle ,p{k}_2,\cdots ,p{k}_t)\leftarrow \mathcal{A}(\mathsf{param},p{k}_1)$
    ${\lambda }_1,\cdots ,{\lambda }_t\leftarrow \mathsf{\Theta }$
    $\left(\right|s{t}_1\rangle ,CMT)\leftarrow \mathcal{A}\left(\right|s{t}_0\rangle ,{\lambda }_1,\cdots ,{\lambda }_t)$;
    $CH\leftarrow \mathsf{\Theta }$; $Rsp\leftarrow \mathcal{A}\left(\right|s{t}_1\rangle ,CH)$;
    $b\leftarrow V_t(\overline{pk},CMT\left|CH\right|Rsp)$;
    output $b.$

3. Basic Properties in Quantum Computing

In this section, we give some fundamental properties in quantum computing.

3.1. Properties of Commutators

Recall that a commutator between operators A and B is $[A,B]=AB-BA.$ The commutator property is very useful in analyzing the quantum state that goes through a sequence of operators. For example, if $A,B$ commute, then $AB|\psi \rangle =BA|\psi \rangle$. So, instead of analyzing $AB|\psi \rangle$, we can study $AB|\psi \rangle .$ Further, if $\left|\right|[A,B]\left|\right|$ is small, then $AB|\psi \rangle$ and $BA|\psi \rangle$ will be very close in Euclidean distance. So, we can still reduce analyzing $AB|\psi \rangle$ to the analysis of $BA|\psi \rangle$ without losing much accuracy. The following are some identities on commutators.

Lemma 1.

Let $A,B,C\in \mathcal{L}\left(\mathcal{H}\right).$ Then, the following holds:

1. 

$[AB,C]=A[B,C]+[A,C]B$;

2. 

$[ABC,D]=AB[C,D]+A[B,D]C+[A,D]BC;$

3. 

$[A^n,B]={\sum }_{i=0}^{n-1}{A}^i[A,B]A^{n-i-1}.$

The proof can be done by simple calculations. For example, $[AB,C]=ABC-CAB=ABC-ACB+ACB-CAB=A[B,C]+[A,C]B.$ The other two can be proved using item 1 by noticing that $ABC=AB·C$ and $A^n=A^{n-1}·A.$ The details are omitted.

The following notation of control register with respect to a basis will be useful to determine if two operators commute sometimes.

Definition 6.

Register D is a control register in the orthonormal basis ${\left\{\right|y\rangle \}}_y$ for operator B that operates on registers $WD$, if B can be written as $B={\sum }_y{B}_y\otimes {|y\rangle \langle y|}_D$, where $B_y$ operates on W.

Remark 2.

Intuitively, if register D has y, then W will be applied by operator $B_y$, while register D is not changed. The requirement for a control register is very loose. Indeed, if B does not operate on D, then by default, it is understood as $B\otimes I_D={\sum }_{x}B\otimes {|x\rangle \langle x|}_D$ for a basis ${\left\{\right|x\rangle \}}_x$, and so D is a control register for B.

It is clear that if two operators operate on completely disjoint registers, then they commute. The following lemma states that this commutative property still holds even if they further share a common control register in the same basis.

Lemma 2.

Let $XYD$ be three quantum registers. The following properties hold:

1. 

If A operates on $XD$, while B operates on $YD$ with D being a control register in the same basis ${\left\{\right|y\rangle \}}_{y\in D}$ for both A and B, then $[A,B]=0.$

2. 

If A is a projector on D in basis ${\left\{\right|y\rangle \}}_y$, and B operates on $YD$ with D being a control register in the same basis, then $[A,B]=0.$

Proof. 

1. Since A does not operate on Y, and B does not operate on X, we can write $A={\sum }_y{A}_y\otimes I_Y\otimes {|y\rangle \langle y|}_D$ and $B=I_X\otimes B_y\otimes {|y\rangle \langle y|}_D$, with ${\left\{\right|y\rangle \}}_y$ being an ortonormal basis, where $A_y$ operates on register X, and $B_y$ operates on register $Y.$ Thus, both $AB$ and $BA$ equal ${\sum }_y{A}_y\otimes B_y\otimes |y\rangle \langle y|.$ The conclusion follows.

2. If $A={\sum }_{y\in T}{|y\rangle \langle y|}_D$, and $B={\sum }_y{B}_y\otimes {|y\rangle \langle y|}_D$, then $AB$ and $BA$ both equal to ${\sum }_{y\in T}{B}_y\otimes {|y\rangle \langle y|}_D.$ Thus, $[A,B]=0.$ □

3.2. Properties of Norm

This section gives some simple properties of the operator or state norm. The following was stated in [32] without a proof. We give a proof for completeness.

Lemma 3.

Let $A,B,A_1,A_2\in \mathcal{L}\left(\mathcal{H}\right).$ Then, the following holds.

1. 

If $A_1,A_2\in \mathcal{L}\left(\mathcal{H}\right)$, then $\left|\right|A_1\otimes A_2\left|\right|=\left|\right|A_1\left|\right|·\left|\right|A_2\left|\right|.$

2. 

If $A^{†}B=0$ and $A{B}^{†}=0$, then $\left|\right|A+B\left|\right|\le max\left(\right|\left|A\right||,|\left|B\right|\left|\right).$ Especially, if $A={\sum }_x|x\rangle \langle x|\otimes A^x$, then $\left|\right|A\left|\right|\le {max}_x\left|\right|A^x\left|\right|.$

Proof. 

1. By singular value decomposition, we can write $A_1=U_1{D}_1{V}_1$ and $A_2=U_2{D}_2{V}_2$ for $D_i=\mathtt{diag}({\mu }_{i1},\cdots ,{\mu }_{i{t}_i})$, with ${\mu }_{ij}\ge 0$ and unitary $U_1,U_2,V_1,V_2$. Then, $A_1\otimes A_2=(U_1\otimes U_2)(D_1\otimes D_2)(V_1\otimes V_2).$ Hence, $\left|\right|A_1\otimes A_2\left|\right|=\left({max}_t{\mu }_{1t}\right)\left({max}_j{\mu }_{2j}\right)=\left|\right|A_1\left|\right|·\left|\right|A_2\left|\right|$, as $U_1\otimes U_2$ and $V_1\otimes V_2$ are unitary.

2. By the singular value decomposition theorem, we can write $A={\sum }_{i=1}^s{\lambda }_i|x_i\rangle \langle y_i|$ and $B={\sum }_{i=1}^t{\beta }_i|u_i\rangle \langle v_i|$, where $\left\{\right|x_i\rangle {\}}_i,\left\{\right|y_i\rangle {\}}_i,\left\{\right|u_i\rangle {{\}}_i,\left\{\right|v_i\rangle \}}_i$ are, respectively, orthonormal sets of vectors in $\mathcal{H}$ and ${\lambda }_j,{\beta }_i>0$. Then, from $A^{†}B=0$, we have ${\sum }_{i,j}{\lambda }_i^{\ast }{\beta }_j\langle x_i|u_j\rangle ·|y_i\rangle \langle v_j|=0.$ As $\langle y_i\left|A^{†}B\right|v_j\rangle =0$, we know that $\langle x_i|u_j\rangle =0$ for $i=1,\cdots ,s$, and $j=1,\cdots ,t.$ Similarly, from $A{B}^{†}=0$, we have $\langle y_i|v_j\rangle =0.$ Hence, $\left\{\right|y_i\rangle {{\}}_{i=1}^s,\left\{\right|v_i\rangle \}}_{i=1}^t$ are disjoint and together orthonormal states. Together, they can be extended to an orthonormal basis. Let $|x\rangle$ be any normalized state represented under this basis with coordinate vector $(w_1,\cdots ,w_n).$ Then, $(A+B)|x\rangle ={\sum }_{i=1}^s{\lambda }_i{w}_i|x_i\rangle +{\sum }_{j=1}^t{\beta }_j{w}_{s+j}|u_j\rangle .$ Its norm is upper bounded by ${max}_{ij}\left(\right|{\lambda }_i|,|{\beta }_j\left|\right)=max\left(\right|\left|A\right||,|\left|B\right|\left|\right),$ which is desired! This result implies the second claim as $\left(\right|x\rangle {\langle x|\otimes A^x)}^{†}\left(\right|y\rangle \langle y|\otimes A^y)=0$ for any $x\ne y.$ □

The following lemma (from Equation (9.100) [36]) builds the connection between Euclidean distance of pure states and their trace distance. We give a proof here for clarity.

Lemma 4.

Let $|u\rangle ,|v\rangle$ be two states for a quantum system. $D_t\left(\right|u\rangle \langle u|,|v\rangle \langle v\left|\right)\le \left|\right||u\rangle -|v\rangle ||.$

Proof. 

Let $|0\rangle =|u\rangle$ and take $|1\rangle$ as a unit orthogonal state of $|0\rangle$ so that $|v\rangle =\omega (cos\left(\theta \right)|0\rangle +sin(\theta \left)\right|1\rangle )$ with $\theta \in [0,\pi /2]$, by absorbing the complex unit factor (if any) into $|1\rangle ,$ where $\omega$ is a complex unit factor. By calculation, $D_t\left(\right|u\rangle \langle u|,|v\rangle \langle v\left|\right)=|sin\left(\theta \right)|.$ On the other hand, $\left|\right||u\rangle -|v\rangle ||=\sqrt{{|1-\omega cos\left(\theta \right)|}^2+{sin}^2\left(\theta \right)}\ge \sqrt{{(1-cos\left(\theta \right))}^2+{sin}^2\left(\theta \right)}=2|sin(\theta /2)|.$ Since $|sin(\theta \left)\right|=2|sin(\theta /2)·cos(\theta /2\left)\right|\le 2|sin(\theta /2\left)\right|,$ the result follows. □

3.3. Impact of Intermediate Measurement on the Final Output

In the quantum security analysis, it is very common that some intermediate measurements are performed during a quantum algorithm. It is useful to ask if these intermediate measurements affect the final algorithm output or not. The following lemma states that if an intermediate measurement is a projective measurement on a control register in the same basis as for the control register, then the final algorithm output will not be affected.

Lemma 5.

Let $|\psi \rangle ={\sum }_y{t}_y|{\psi }_y{\rangle }_X{|y\rangle }_Y$ be a joint state for register $XY$, with ${\left\{\right|y\rangle \}}_{y\in \mathcal{Y}}$ as the orthonormal basis of register Y. Let $P=\left\{\right|y\rangle {\langle y\left|\right\}}_y$ be the projective measurement on register Y. Let $Q={\left\{Q_x\right\}}_x$ be the measurement on register X. Let $U_y$ be a unitary on register X, which is labeled with $y\in \mathcal{Y}$. Consider procedure A: apply ${\sum }_{y\in \mathcal{Y}}{U}_y\otimes |y\rangle \langle y|$ to $|\psi \rangle$, and then apply measurement Q on X to output x. Also, consider procedure $A^{\prime }$, which starts with measurement P on Y and continues with procedure A, with the final output denoted by $x^{\prime }$. Then, the distributions of x and $x^{\prime }$ are identical.

Proof. 

Procedure A outputs x with probability $\left|\right|{\sum }_y{t}_y{Q}_x{U}_y|{\psi }_y{\rangle |y\rangle ||}^2.$ The procedure $A^{\prime }$ outputs y, resulting in the collapsed state $U_y|{\psi }_y\rangle |y\rangle$ with probability $\left|\right|t_y{\left|\right|}^2$. Following the measurement Q, it outputs x with probability $\left|\right|t_y{Q}_x{U}_y|{\psi }_y{\rangle |y\rangle ||}^2$. So, the overall probability to output x with probability ${\sum }_y\left|\right|t_y{Q}_x{U}_y|{\psi }_y{\rangle |y\rangle ||}^2=\left|\right|{\sum }_y{t}_y{Q}_x{U}_y|{\psi }_y{\rangle |y\rangle ||}^2,$ as ${\left\{\right|y\rangle \}}_y$ is orthogonal, is desired. □

Remark 3.

In Lemma 5, it is important that projective measurement $P=\left\{\right|y\rangle {\langle y\left|\right\}}_y$ uses the same basis as ${\left\{\right|y\rangle \}}_y$ as in ${\sum }_y{U}_y\otimes |y\rangle \langle y|$. That is, the unitary needs to use register Y as a control register on the basis of the projective measurement P. Otherwise, the result will be incorrect. For example, let $|\psi \rangle =|0\rangle |+\rangle ,$ where $|+\rangle ={\displaystyle \frac{|0\rangle +|1\rangle }{\sqrt{2}}}$, and $|-\rangle ={\displaystyle \frac{|0\rangle -|1\rangle }{\sqrt{2}}}.$ Define $U_{+}=|1\rangle \langle 0|+|0\rangle \langle 1|$ and $U_{-}=I.$ Let $Q=\left\{\right|0\rangle \langle 0|,|1\rangle \langle 1\left|\right\}$ on register X and $P=Q$ but on register Y. Let $U=U_{+}\otimes |+\rangle \langle +|+U_{-}\otimes |-\rangle \langle -|$. Then, for procedure A, the state before measurement Q is $|1\rangle |+\rangle$, and hence, the outcome of Q is 1 with probability 1. But for procedure $A^{\prime }$, after measurement P, the state is $|0\rangle |1\rangle$ or $|0\rangle |0\rangle$, each with probability 1/2. Since $|1\rangle ={\displaystyle \frac{|+\rangle -|-\rangle }{\sqrt{2}}}$ and $|0\rangle ={\displaystyle \frac{|+\rangle +|-\rangle }{\sqrt{2}}}$, after applying U, the result is ${\displaystyle \frac{1}{\sqrt{2}}}\left(\right|1\rangle |+\rangle \pm |0\rangle |-\rangle )$ (± depending 1 or 0 on Y register), and next, the measurement Q on register X gives the outcome 1 with probability $1/2·1/2+1/2·1/2=1/2.$ This is different from the procedure A.

The above example shows that an intermediate measurement could change the final output distribution. But, the following result states that the probabilities on the final output without such an intermediate measurement are actually related. This result was given by Boneh and Zhandry [38] (but the intermediate measurement M seemingly needs to be projective). For clarity, we give a proof here.

Lemma 6.

Let A be a quantum algorithm and $Pr\left[x\right]$ be the probability that A outputs x. Let $A^{\prime }$ be the algorithm that runs A until some stage and then performs a projective measurement M, which gives an outcome m (out of k possible choices) and next continues the execution of A with the post-measurement state. Let ${Pr}^{\prime }\left[x\right]$ be the probability that $A^{\prime }$ outputs x. Then, ${Pr}^{\prime }\left[x\right]\ge Pr\left[x\right]/k.$

Proof. 

Let $M={\left\{M_i\right\}}_{i=1}^k$ be the measurement. Let $|\varphi \rangle$ be the state right before this measurement. Then, the probability of M giving outcome m occurs with probability $p_m=\langle \varphi |M_m^{\ast }{M}_m|\varphi \rangle$, and the post-measurement state is $|{\varphi }_m\rangle =M_m|\varphi \rangle /\sqrt{p_m}.$ According to the deferred measurement principle, we can assume that A after this consists of a unitary U and a final projective measurement ${\left\{P_i\right\}}_i$. Then,

$$\begin{array}{cc}\hfill {Pr}^{\prime }\left[x\right]=& \sum _m{p}_m\langle {\varphi }_m|U^{†}{P}_x^{†}{P}_{x}U|{\varphi }_m\rangle =\sum _m\langle \varphi |M_m^{†}{U}^{†}{P}_x^{†}{P}_{x}U{M}_m|\varphi \rangle \hfill \end{array}$$

(2)

$$\begin{array}{cc}\hfill =& \sum _m\left|\right|P_{x}U{M}_m{|\varphi \rangle ||}^2\ge \left|\right|\sum _m{P}_{x}U{M}_m{|\varphi \rangle ||}^2/k\hfill \end{array}$$

(3)

$$\begin{array}{cc}\hfill =& \left|\right|P_x{U|\varphi \rangle ||}^2/k=Pr\left[x\right]/k.\hfill \end{array}$$

(4)

where the inequality follows from Cauchy–Schwarz inequality, and Equation (4) uses the fact that M is the projective measurement, so ${\sum }_m{M}_m={\sum }_m{M}_m^{†}{M}_m=I$. □

3.4. Making Intermediate Measurement Unitaries

It is very common that a quantum algorithm will make intermediate measurements. A deferred measurement principle [36] states that we can move these measurements to the end of the algorithm (without affecting the output). From this principle, we only need to consider an algorithm that consists of a sequence of unitaries except for the final measurement. The following lemma and its corollary are essentially to capture this. We give a proof here, as it demonstrates how this can be made and it will be useful for us later to understand other results later. We start with a simpler version where the algorithm only has one intermediate measurement.

Lemma 7.

Let $|\varphi \rangle$ be a quantum state. We apply the following operators on register A: first a unitary U, then a measurement $M={\left\{M_y\right\}}_y$ that results in y, next a unitary $V_y$, and finally a measurement $N_y={\left\{N_{yx}\right\}}_x$ that results in x. Then, there exist a unitary W on A and additional registers $BC$ and a projective measurement P on C that results in x with the same probability.

Proof. 

It is clear that procedure A outputs x with probability $Pr\left(x\right)={\sum }_y\left|\right|N_{yx}{V}_y{M}_y{U|\varphi \rangle ||}^2.$ Then, define a unitary operator $U_M$ so that $U_M{|\varphi \rangle }_A{|0\rangle }_B={\sum }_y{M}_y{|\varphi \rangle }_A{|y\rangle }_B$ ([36], pp. 95). Also, define unitary V on $AB$ with $V={\sum }_y{V}_y\otimes {|y\rangle \langle y|}_B.$ Also, define unitary $U_N$ so that $U_N{|u\rangle }_A{|y\rangle }_B{|0\rangle }_C={\sum }_x{\sum }_r(N_{rx}\otimes |r\rangle \langle r\left|\right){|u\rangle }_A{|y\rangle }_B{|x\rangle }_C.$ Finally, define P to be the projective measurement $P=\left\{\right|x\rangle {\langle x\left|\right\}}_x.$ Then, consider $U_{N}V{U}_M{U|\varphi \rangle }_A{|0\rangle }_B{|0\rangle }_C$, followed by P on C. Then, the probability of outcome x, by first applying $W=U_{N}V{U}_M$, followed by measurement P on C, is

$$\begin{array}{cc}\hfill & \left|\right|\sum _r(N_{rx}\otimes |r\rangle \langle r{|}_B)·\sum _{y^{\prime }}{V}_{y^{\prime }}\otimes |y^{\prime }\rangle \langle y^{\prime }{|}_B·\sum _y{M}_y{|\varphi \rangle }_A{|y\rangle }_B{|x\rangle }_C{\left|\right|}^2\hfill \\ \hfill =& \left|\right|\sum _y{N}_{yx}{V}_y{M}_y{U|\varphi \rangle |y\rangle \left|\right|}^2\hfill \\ \hfill =& \sum _y\left|\right|N_{yx}{V}_y{M}_y{U|\varphi \rangle ||}^2=Pr\left(x\right),\mathrm{desired}!\hfill \end{array}$$

□

Remark 4.

In this lemma, register B is a control register in the basis ${\left\{\right|y\rangle }_B{\}}_y$ for other operators; register C is a control register in the basis ${\left\{\right|x\rangle }_C{\}}_x$ for other operators. Hence, the projective measurement $\left\{\right|x\rangle {\langle x\left|\right\}}_x$ on B commutes with other operators and so can be moved to the end of the operations (especially after measurement P on C) and hence does not affect the distribution of outcome x of P; thus, it can be removed. This justifies the proof idea of the above lemma. With this in mind, the following generalization corollary of the lemma is straightforward.

Corollary 1.

Let $|\varphi \rangle$ be a quantum state of register A. For $\ell =1,\cdots ,N$, run a unitary $U_{\ell },$ measurement $M_{y^{\ell -1}}={\left\{M_{y^{\ell }}\right\}}_{y_{\ell }}$ that results in $y_{\ell }$, followed by unitary $V_{y^{\ell }}$, where $y^i$ represents the sequence $y_1\cdots y_i$. Finally, it applies measurement $N_{y^N}={\left\{N_{y^{N}x}\right\}}_x$ that results in x. Then, there is unitary W and projective measurement P that apply to the initial state ${|\varphi \rangle |0\rangle }_1{\cdots |0\rangle }_N|0\rangle$, which results in x with the same probability.

4. Quantum Random Oracles

In this section, we will introduce the quantum random oracles. As a convention in this paper, we use bold font to represent the random oracle (e.g., $\mathbf{RO}$) and the italic font (e.g., $RO$) to represent the operator for the random oracle query. We distinguish an oracle and its operator, because some oracle could offer more operators.

We introduce the standard random oracle in Section 4.1. That is, this is the classical random oracle extended to the quantum setting. Then, we introduce Zhandry’s compressed random oracle [31] (CStO) in Section 4.2, which allows a simulator to detect if an input x has been queried to the oracle or not. Next, we present in Section 4.3 our extension of $\mathbf{CStO}$, called the compressed random oracle with adaptive special points (CStO_s), and its connection to $\mathbf{CStO}$. Finally, we address in Section 4.4 how CStO_s and $\mathbf{CStO}$ can be efficiently implemented.

4.1. Standard Random Oracle

In the random oracle model, a cryptographic hash function $H:\mathcal{X}\to {\{0,1\}}^n$ is treated as an external oracle so that whenever one needs to compute $H\left(x\right)$, he queries x to this oracle and receives $H\left(x\right)$. We assume that $\mathcal{X}$ has a finite bit length. The oracle uses a random function from $\mathcal{X}$ to $\mathcal{Y}$ to answer the queries. Let $\mathcal{X}=\{x_1,\cdots ,x_N\}$ be an ordered set with $x_1<x_2<\cdots <x_N.$ Function H can be represented by its truth table $H\left(x_1\right),H\left(x_2\right),\cdots ,H\left(x_N\right)$. In the quantum random oracle model, H is represented by state $|H\rangle$ (using its truth table). An algorithm $\mathcal{A}$ can query a superposition to random oracle $\mathbf{RO}$. For query $|x\rangle |y\rangle$, $RO$ maps $|x\rangle |y\rangle |H\rangle$ to $|x\rangle |y\oplus H\left(x\right)\rangle |H\rangle$.

The standard random oracle $\mathbf{StO}$ has an initial state in a uniform superposition ${\displaystyle \frac{1}{\sqrt{2^{n\left|\mathcal{X}\right|}}}}{\sum }_H|H\rangle .$ For query $|x\rangle |y\rangle$, $StO$ maps ${\displaystyle \frac{1}{\sqrt{2^{n\left|\mathcal{X}\right|}}}}{\sum }_H|x\rangle |y\rangle |H\rangle$ to ${\displaystyle \frac{1}{\sqrt{2^{n\left|\mathcal{X}\right|}}}}{\sum }_H|x\rangle |y\oplus H\left(x\right)\rangle |H\rangle$. Notice that $\mathbf{RO}$ can be obtained from $\mathbf{StO}$ by starting with a projective measurement on an oracle register (resulting in $|H\rangle$). Even though $\mathbf{RO}$ and $\mathbf{StO}$ are different, no adversary can distinguish them. This can be seen from Lemma 2(2) by observing that oracle register is a control register in the computational basis for adversarial operators (which do not operate on oracle register) and $StO$. Hence, the projective measurement on the oracle register can be moved to after $\mathcal{A}$ makes the final measurement.

Fact 1.

Let $\mathcal{A}$ be a quantum algorithm with oracle access to the quantum random oracle. Then, $Pr({\mathcal{A}}^{\mathbf{RO}}()=1)=Pr({\mathcal{A}}^{\mathbf{StO}}()=1)$.

4.2. Compressed Random Oracle

The compressed random oracle $\mathbf{CStO}$ was introduced in [31], and our exposition mainly follows [32]. It is a powerful tool for security proof in the quantum random oracle model (QROM). Let $\mathcal{Y}={\{0,1\}}^n$ and $\overline{\mathcal{Y}}=\mathcal{Y}\cup \{\perp \}$. Let H be the quantum Walsh–Hadamard transform over $\mathbb{C}\left[\mathcal{Y}\right]$. Define ${\varphi }_y=H|y\rangle$ for $y\in {\{0,1\}}^n$. Since ${\left\{\right|y\rangle \}}_{y\in {\{0,1\}}^n}$ is orthonormal, and $H^2=I$, $\left\{\right|{\varphi }_y\rangle {\}}_{y\in {\{0,1\}}^n}$ is orthonormal as well. Then, we define an unitary operator F over $\mathbb{C}\left[\overline{\mathcal{Y}}\right]$ such that

$$\begin{array}{c}\hfill F|\perp \rangle =|{\varphi }_0\rangle ,F|{\varphi }_0\rangle =|\perp \rangle ,F|{\varphi }_y\rangle =|{\varphi }_y\rangle ,\forall y\in \mathcal{Y}-\left\{\mathbf{0}\right\}.\end{array}$$

(5)

It is Hermitian (i.e., $F^{†}=F$) because $F=|{\varphi }_0\rangle \langle \perp |+|\perp \rangle \langle {\varphi }_0|+{\sum }_{y\ne 0}|{\varphi }_y\rangle \langle {\varphi }_y|.$ Furthermore, notice that $|y\rangle =2^{-n/2}{\sum }_{\eta \in {\{0,1\}}^n}{(-1)}^{y·\eta }|{\varphi }_{\eta }\rangle .$ This implies $F|y\rangle =|y\rangle +2^{-n/2}\left(\right|\perp \rangle -|{\varphi }_0\rangle ).$

We consider the multi-register $D={\left\{D_x\right\}}_{x\in \mathcal{X}}$ for the random oracle, where $D_x$ has a state space $\mathbb{C}\left[\overline{\mathcal{Y}}\right]$ spanned by the computational basis ${\left\{\right|y\rangle \}}_{y\in \mathcal{Y}}\cup \left\{\right|\perp \rangle \}.$ The initial state of D is ${\otimes }_x{|\perp \rangle }_{D_x}$. We assume that the adversary has a query register X, a response register Y, and a work register $W.$ To query the oracle, adversary provides $XY$ registers to oracle, who then applies unitary

$$\begin{array}{cc}\hfill CSt{O}_{XYD}& =\sum _{x\in \mathcal{X}}{|x\rangle \langle x|}_X\otimes CSt{O}_{Y{D}_x}\hfill \end{array}$$

(6)

on $XYD$, where $CSt{O}_{Y{D}_x}=F_{D_x}·{\mathrm{CNOT}}_{Y{D}_x}·F_{D_x}$, and ${\mathrm{CNOT}|y\rangle }_Y{|u\rangle }_{D_x}={|y+u\rangle }_Y{|u\rangle }_{D_x}.$ This oracle has the property that if $|x\rangle$ has not been queried before, then $D_x$ will remain as ${|\perp \rangle }_{D_x}$. Also, as shown in the following lemma by Zhandry [31], an (unbounded) attacker can not distanguish $\mathbf{StO}$ and $\mathbf{CStO}$. We stress that this indistinguishability holds only if no operator other than $CStO$ (respectively, $StO$) is applied on D; otherwise, it might fail.

Lemma 8.

[31] Let $\mathcal{A}$ be a quantum algorithm with oracle access to the quantum random oracle. Then, $Pr({\mathcal{A}}^{\mathbf{StO}}()=1)=Pr({\mathcal{A}}^{\mathbf{CStO}}()=1).$

4.3. Compressed Random Oracle with Adaptive Special Points

CStO has the advantage that it can record oracle queries. But, it can not allow a simulator (as in a classical random oracle) to set the random oracle values for some special points. Liu and Zhandry [33] introduced CStO with non-adaptive special points to resolve this issue. However, it seems the Fiat–Shamir-based signature proof in their work seems to require adaptive special points, as the adversary’s signing query cannot be guessed or predicted before the query. In this section, we formalize the compressed random oracle with adaptive special points (denoted by ${\mathbf{CStO}}_s$) as a natural generalization of $\mathbf{CStO}$. It allows a simulator to set special points on the fly. But, this needs some considerations. We need to make it connected to $\mathbf{CStO}$. For example, if an adversary, interacting with a challenger in the $\mathbf{CStO}$ model, has a success probability $ϵ,$ we probably want it to have a success probability at $ϵ/poly\left(\lambda \right)$ when interacting with the challenger in the ${\mathbf{CStO}}_s$ model. We need this, as in applications, we will have a game with $\mathbf{CStO}$, and then we want to transit to a game with ${\mathbf{CStO}}_s$ with the adversary success probability degraded only by at most a polynomial fraction. Liu and Zhandry [33] introduced a random experiment (to be detailed in Section 7) to make the connection. In the adaptive case, it needs some care (in order to be compatible with the random experiment). In the following, we first describe our CStO_s and then outline this subtlety.

The CStO_s oracle initially has state ${\otimes }_x{|\perp \rangle }_{D_x}.$ We maintain two initially empty sets ${\mathsf{\Xi }}_0$ and ${\mathsf{\Xi }}_1$ to record the special points at different stages. We also allow the oracle to abort after certain measurements, and the motivation will be discussed later. The oracle can be accessed through three types of queries below.

• PointReg0 Query. One can send a new point $x\in \mathcal{X}$ to the oracle. If $x\in {\mathsf{\Xi }}_0\cup {\mathsf{\Xi }}_1$, it does nothing; otherwise, the oracle updates ${\mathsf{\Xi }}_0={\mathsf{\Xi }}_0\cup \left\{x\right\}.$
• Random Oracle Query. One can issue a random oracle query by providing a query register X and a response register Y to the oracle. If this is the ith random oracle query, the oracle applies a projective measurement ${\mathsf{\Lambda }}_i=({\mathsf{\Lambda }}_{i0},{\mathsf{\Lambda }}_{i1})$ in the computational basis to oracle register $D_{{\mathsf{\Xi }}_0}$ (${\mathsf{\Lambda }}_i$ can be determined by i and some parameters that are determined before the oracle starts). If the outcome is 1, it aborts; otherwise, it applies $CSt{O}_s={\sum }_{x\in \mathcal{X}}|x\rangle \langle x|\otimes CSt{O}_{sY{D}_x}$ to the $XYD$ registers, where

  $$CSt{O}_{sY{D}_x}=\left\{\begin{array}{cc}CSt{O}_{Y{D}_x},\hfill & x\notin {\mathsf{\Xi }}_1\hfill \\ {\mathrm{CNOT}}_{Y{D}_x},\hfill & \mathrm{otherwise}.\hfill \end{array}\right.$$
  Finally, it returns register $XY$.
• PointReg1 Query. One can send $x\in {\mathsf{\Xi }}_0$ to the oracle. If $x\notin {\mathsf{\Xi }}_0$, it does nothing. Otherwise, it measures $D_x$ with $\mathsf{\Pi }=({\mathsf{\Pi }}_0,{\mathsf{\Pi }}_1)$, where ${\mathsf{\Pi }}_0=|\perp \rangle \langle \perp |,{\mathsf{\Pi }}_1=I-{\mathsf{\Pi }}_0$. If the outcome is 1, it aborts; otherwise, it updates ${|\perp \rangle }_{D_x}$ with $|r\rangle$ for a random $r\in \mathcal{Y}$ (this can be done, as ${|\perp \rangle }_{D_x}$ is now classic; or, we can apply unitary $|\perp \rangle \langle r|+|r\rangle \langle \perp |+{\sum }_{v\in \mathcal{Y}-\left\{r\right\}}|v\rangle \langle v|$). Finally, it updates ${\mathsf{\Xi }}_1={\mathsf{\Xi }}_1\cup \left\{x\right\}$ and ${\mathsf{\Xi }}_0={\mathsf{\Xi }}_0-\left\{x\right\}.$

Remark 5.

It is time to justify this strange random oracle. It is in fact motivated by the requirements in the security proof. The main motivation is to find a modified random oracle so that the random experiment (with $\mathbf{CStO}$) in Section 7 can be easily converted into a game with this modified random oracle. We want to define this modified oracle with respect to this random experiment because adversary success in this experiment, in comparison with the original security game, is degraded only by a polynomial fraction. So, this compatible random oracle is denoted by ${\mathbf{CStO}}_s$. Here the compatibility means that, given the random experiment with $\mathbf{CStO}$, we can easily transit to a game with ${\mathbf{CStO}}_s$ that preserves the adversary success probability. Further remarks on the definition of ${\mathbf{CStO}}_s$ are as follows:

• In the classical random oracle, a simulator can set the random oracle values of special queries to his own choices. In the CStO_s, a special point will be first recorded in ${\mathsf{\Xi }}_0$ and later set to a planned value (when a PointReg1 query on this point is issued). We handle special points in two stages for technical reasons (See the remark after Theorem 5) only. Essentially, if we define the random oracle value of a special point early (e.g., at the time of adding into ${\mathsf{\Xi }}_0$), it could make the previously selected experiment change to a different one.
• CStO_s is to formulate the random experiment in Section 7 as a well-defined random oracle model. Especially, measurement ${\mathsf{\Lambda }}_i$ in a random oracle query is to make sure the interaction with oracle follows the restriction of the selected experiment. If the measurement outcome is 1, it indicates that the game is not consistent with the selected experiment and hence can stop now; otherwise, it continues. This randomly selected but consistent experiment can guarantee the adversary to have a good success probability compared to the original game.
• In the classical random oracle, a simulator can pay attention to each query to make sure that each special point is not queried before it is set to the designated value. In the quantum setting, recording each query is difficult, as one can query ${\displaystyle \frac{1}{\left|\mathcal{X}\right|}}{\sum }_x{|x\rangle }_X{|0\rangle }_Y$, which indicates that every x is actually queried. To overcome this, we need to confirm that $RO\left(x\right)$ is not defined by measurement Π on $D_x$. If the measurement is successful, then $D_x$ will have ${|\perp \rangle }_{D_x}$ now, the non-⊥ components in the superposition are pruned, and we can define the random oracle value for this x; if the measurement fails, we have no way to set the random oracle value for x and so abort. This is why we abort in PointReg1 when the measurement outcome is 1.

One might hope that an attacker cannot distinguish $\mathbf{CStO}$ and ${\mathbf{CStO}}_s$. However, this is not true, as the latter simply has different interfaces. However, we can define a variant of $\mathbf{CStO}$ to achieve this indistinguishability as long as the abortion event does not occur.

Precisely, we define ${\mathbf{CStO}}^{\prime }$ to be a variant of ${\mathbf{CStO}}_s$ so that $CSt{O}_s$ in the random oracle query is replaced by $CStO$ and also in PointReg1 query in case of the measurement outcome 0, where it leaves ${|\perp \rangle }_{D_x}$ as it is (instead of replacing it by $|r\rangle$). Essentially, ${\mathbf{CStO}}^{\prime }$ has three interfaces as in ${\mathbf{CStO}}_s$, but the random oracle query uses $\mathbf{CStO}$ (after the measurement ${\mathsf{\Lambda }}_i$ with outcome 0), and the PointReg1 query only makes $\mathsf{\Pi }$ measurements on D.

The following lemma shows that ${\mathbf{CStO}}_s$ is perfectly indistinguishable from ${\mathbf{CStO}}^{\prime }$, which is conditional on that the abort event in the oracle does not occur.

Lemma 9.

Let $\mathcal{A}$ be a quantum algorithm with access to a quantum random oracle and $\mathsf{abort}$ be the oracle abortion event. Then,

$$\begin{array}{c}\hfill Pr({\mathcal{A}}^{{\mathbf{CStO}}^{\prime }}()=1\wedge \neg \mathsf{abort})=Pr({\mathcal{A}}^{{\mathbf{CStO}}_s}()=1\wedge \neg \mathsf{abort}).\end{array}$$

(7)

Proof. 

We use the hybrid argument with a variant ${\mathbf{CStO}}_s^{\prime }$ of ${\mathbf{CStO}}_s$ to bridge ${\mathbf{CStO}}_s$ and ${\mathbf{CStO}}^{\prime }$.

• Oracle ${\mathbf{CStO}}_s^{\prime }$. We modify ${\mathbf{CStO}}_s$ to ${\mathbf{CStO}}_s^{\prime }$ so that upon PointReg1 query x with $D_x$ measured with outcome 0 (i.e., $|\perp \rangle$), it updates ${|\mathbf{y}\rangle }_D$ to ${\displaystyle \frac{1}{2^{n/2}}}{\sum }_r{|\mathbf{y}\cup {\left(r\right)}_x\rangle }_D$ (instead of ${|\mathbf{y}\cup \left(r\right)}_x{\rangle }_D$ for a random r), where $\mathbf{y}\cup {\left(r\right)}_x$ (which is well defined as $y_x=\perp$) is the vector with $y_{x^{\prime }}$ at index $x^{\prime }\ne x$ and r at index x. Notice that right after this, $x\in {\mathsf{\Xi }}_1$. Furthermore, $D_x$ for this x is a control register (Definition 6) in the computational basis for adversary operations, ${\mathsf{\Pi }}_0,{\mathsf{\Pi }}_1,{\mathsf{\Lambda }}_{i0},{\mathsf{\Lambda }}_{i1}$ and $CSt{O}_{sY{D}_u}$. To see this, it suffices to check $CSt{O}_{sY{D}_x}$ only, as the other cases are clear (e.g., $CSt{O}_{sY{D}_u}$ for $u\ne x$ does not operate on $D_x$ at all). Since $x\in {\mathsf{\Xi }}_1$, we know that $CSt{O}_{Y{D}_x}={\mathrm{CNOT}}_{Y{D}_x}$, which obviously can be written as a format of ${\sum }_{y\in \overline{\mathcal{Y}}}{B}_y\otimes {|y\rangle \langle y|}_{D_x}$. Furthermore, ${\mathbf{CStO}}_s$ is obtained from ${\mathbf{CStO}}_s^{\prime }$ by projective measurement on $D_x$ in the computational basis for every $x\in {\mathsf{\Xi }}_1$ (right after x is put in ${\mathsf{\Xi }}_1$). By Lemma 2 (2), the projective measurement on $D_x$ can be moved to the end of the interaction (after $\mathcal{A}$ outputs). Thus, the output of $\mathcal{A}$ with access to ${\mathbf{CStO}}_s^{\prime }$ is the same as with access to ${\mathbf{CStO}}_s$.
• Oracle ${\mathbf{CStO}}^{\prime }$. We show that under the event $\neg \mathsf{abort}$, if the final (unnormalized) state after interacting with ${\mathbf{CStO}}_s^{\prime }$ is $|\psi \rangle$, then the final state (unnormalized) after interacting with ${\mathbf{CStO}}^{\prime }$ will be $F_{D_{{\mathsf{\Xi }}_1}}|\psi \rangle .$ This can be shown by induction on the query. It is correct initially, as ${\mathsf{\Xi }}_1=\varnothing$ initially, and hence $F_{D_{{\mathsf{\Xi }}_1}}$ is its identity. Then, if it is correct after query $i-1$, consider query $i.$ Before query i, $\mathcal{A}$ will operate on $XYW$ registers (for simplicity, assume it is a unitary). But, since the adversary does not operate on D, the induction assumption on query $i-1$ implies the following: if the state right before query i (when interacting with ${\mathbf{CStO}}_s^{\prime }$) is $|\psi \rangle$, then the state right before query i (when interacting with ${\mathbf{CStO}}^{\prime }$) will be $F_{D_{{\mathsf{\Xi }}_1}}|\psi \rangle$. Let us consider their relation after query i, which has three cases.

If query i is a PointReg0 query, then the claim still holds after the query, as no operation on the quantum state is executed.

If query i is a PointReg1 query x, then it suffices to consider $x\in {\mathsf{\Xi }}_0$. Since $x\notin {\mathsf{\Xi }}_1$ and the outcome of $\mathsf{\Pi }$ is 0 (otherwise, $\mathsf{abort}$ occurs in contradiction to the probability condition), so x will be added to ${\mathsf{\Xi }}_1$, and the conclusion holds after the query as $F|\perp \rangle =|{\varphi }_0\rangle$ (while, after the query, $D_x$ in case of ${\mathbf{CStO}}_s^{\prime }$ will have $|\perp \rangle$ and $D_x$ in the case that ${\mathbf{CStO}}^{\prime }$ will yield $|{\varphi }_0\rangle$).

If query i is a random oracle query, we show that the induction still holds. First, $[F_{D_{{\mathsf{\Xi }}_1}},{\mathsf{\Lambda }}_{ib}]=0$ for both $b=0,1$, as ${\mathsf{\Lambda }}_i$ only operates on register $D_{{\mathsf{\Xi }}_0}$. Thus, after the measurement (with the same outcome), the relation still holds. Second, the relation still holds after operator $CSt{O}_s$ (in the case of ${\mathbf{CStO}}_s^{\prime }$) and operator $CStO$ (in the case of ${\mathbf{CStO}}^{\prime }$): for query ${|x\rangle }_X{|y\rangle }_Y$ with $x\notin {\mathsf{\Xi }}_1$, both oracles use $CSt{O}_{Y{D}_x}$ to respond, and hence, their states after the query maintain the same relation (as $D_{{\mathsf{\Xi }}_1}$ is untouched); for query ${|x\rangle }_X{|y\rangle }_Y$ with $x\in {\mathsf{\Xi }}_1$, ${\mathbf{CStO}}^{\prime }$ uses $CSt{O}_{Y{D}_x}$, and ${\mathbf{CStO}}_s^{\prime }$ uses ${\mathrm{CNOT}}_{Y{D}_x}$, but the two applications of $F_{D_x}$ in ${CStO}_{Y{D}_x}$ will cancel out. So, after the query, the relation still holds. The induction holds too.

Let $|\psi \rangle$ be the final unnormalized state under $\neg \mathsf{abort}$ and the final measurement of $\mathcal{A}$ be $(P_0,P_1)$, with $P_1$ corresponding to outcome 1. Then, $Pr({\mathcal{A}}^{{\mathbf{CStO}}_s^{\prime }}\left(\right)=1\wedge \neg \mathsf{abort})$ is $\left|\right|P_1{|\psi \rangle ||}^2$, while $Pr({\mathcal{A}}^{{\mathbf{CStO}}^{\prime }}\left(\right)=1\wedge \neg \mathsf{abort})$ is $\left|\right|P_1·{\mathsf{F}}_{D_{{\mathsf{\Xi }}_1}}{|\psi \rangle ||}^2$. However, $\left|\right|P_1·{\mathsf{F}}_{D_{{\mathsf{\Xi }}_1}}{|\psi \rangle ||}^2=\left|\right|P_1{|\psi \rangle ||}^2$, as $F_{D_{{\mathsf{\Xi }}_1}}$ commutes with $P_1$ (since they operate on disjoint registers) and $F^2=I$. □

The following lemma essentially states that if $x^{\ast }$ has large min-entropy and we measure $D_{x^{\ast }}$ of the adversary–oracle joint state, then, with high probability, the post-measurement state with outcome ⊥ is close to the original state.

Lemma 10.

Let the current adversary–oracle joint state be $|\psi \rangle ={\sum }_{z\mathbf{y}}{\lambda }_{z\mathbf{y}}{|z\rangle |\mathbf{y}\rangle }_D$ after q queries to ${\mathbf{CStO}}_s$ (or CStO). Let $|{\psi }_x\rangle ={\sum }_{z\mathbf{y}:y_x=\perp }{\lambda }_{z\mathbf{y}}{|z\rangle |\mathbf{y}\rangle }_D$, and $x^{\ast }$ is a random variable over $\mathcal{X}$ with a min-entropy of at least μ. Then, with probability $1-2^{-\mu /2}$ (over $x^{\ast }$), $\left|\right||\psi \rangle -|{\psi }_{x^{\ast }}\rangle \left|\right|\le q^{1/2}{2}^{-\mu /4}$.

Proof. 

Let $|{\psi }_x^{\prime }\rangle ={\sum }_{z\mathbf{y}:y_x\ne \perp }{\lambda }_{z\mathbf{y}}{|z\rangle |\mathbf{y}\rangle }_D.$ Then, $|\psi \rangle =|{\psi }_x^{\prime }\rangle +|{\psi }_x\rangle .$ Consider $L:={\sum }_x\left|\right||{\psi }_x^{\prime }{\rangle \left|\right|}^2$. Let $N_{\mathbf{y}}$ be the number of x so that $y_x\ne \perp$ in $\mathbf{y}$. Then, given $\mathbf{y}$, $|\mathbf{y}\rangle$ appears in $|{\psi }_x^{\prime }\rangle$ for exactly $N_{\mathbf{y}}$ possible xs. Thus, $L={\sum }_{z\mathbf{y}}{\left|{\lambda }_{z\mathbf{y}}\right|}^2{N}_{\mathbf{y}}.$ Since each $\mathbf{y}$ in $|\psi \rangle$ has at most q possible non-⊥ entries, it follows that $N_{\mathbf{y}}\le q$, and hence, $L\le q.$ Hence, there are at most $2^{\mu /2}$ choices for x so that $\left|\right||{\psi }_x^{\prime }\rangle \left|\right|\ge q^{1/2}{2}^{-\mu /4}.$ Since $x^{\ast }$ has min-entropy $\mu$, we have that $\left|\right||{\psi }_{x^{\ast }}^{\prime }\rangle \left|\right|<q^{1/2}{2}^{-\mu /4}$ with a probability of at least $1-2^{-\mu /2}$. The lemma follows. □

4.4. Efficient Encoding of $\mathbf{CStO}$ and ${\mathbf{CStO}}_s$

Notice that, so far, the oracle state is represented via basis states ${|\mathbf{y}\rangle }_D\in {\overline{\mathcal{Y}}}^{\mathcal{X}}$ with at most q non-⊥ entries. However, we need to show how the operators used so far can be efficiently implemented. Zhandry [31] showed how to efficiently encode and compute $O_{XYD}$. In our work, more operators on D are introduced. It is necessary to show that Zhandry’s encoding can be extended. In Appendix B, we detail how these operators can be efficiently executed on the encoded oracle state.

5. Relation Measurement in  CStO_s

In this section, we want to measure if the record in register D of CStO_s satisfies some relation R. In applications, this R could be some properties of a simulator’s interest. Thus, a successful measurement implies a detection of satisfaction of such a property. In Section 5.1, we introduce a unitary operator $U_R$ that writes the smallest input $x_i$ satisfying property R into a new register P and show that the commutator norm $\left|\right|[CSt{O}_s,U_R]\left|\right|$ is small. With this, we can later reduce the analysis of $CSt{O}_s·U_R|\psi \rangle$ to that of $U_R·CSt{O}_s|\psi \rangle$, without worrying about the difference. In Section 5.2, we give an upper bound on the probability that relation R is satisfied in the record of ${\mathbf{CStO}}_s$ after q random oracle queries.

5.1. Relation Measurement

Given a record ${|\mathbf{y}\rangle }_D$, we sometimes are interested in checking if there exists $y_x$ in $\mathbf{y}$ so that $(x,y)$ satisfies a certain property. In this section, we show how to measure such a property, where the property will be represented by a relation. Don et al. [32] has studied this in the CStO setting. Our exposition is to present it in alternative and seemingly simpler way and looks at the norm of its commutator with CStO_s.

Let $R\subset \mathcal{X}\times \mathcal{Y}$ be a fixed and efficiently verifiable relation with $R(x,y)=1$ if and only if $(x,y)\in R$. Especially, $R(x,y)=0$ for any $(x,y)\notin \mathcal{X}\times \mathcal{Y}$. We assume that $0\notin \mathcal{X}$, and so $R(0,y)=0$. Furthermore, $R(x,\perp )=0$ as $\perp \notin \mathcal{Y}$. Let $\overline{\mathcal{X}}=\mathcal{X}\cup \left\{0\right\}.$ We define function $f_R:{\overline{\mathcal{Y}}}^{\left|\mathcal{X}\right|}\to \overline{\mathcal{X}}$ so that

$$f_R(y_1,\cdots ,y_N)=\left\{\begin{array}{cc}{x}_i,\hfill & (x_j,y_j)\notin R \mathrm{for} j<i \mathrm{but} (x_i,y_i)\in R\hfill \\ 0,\hfill & i \text{does not exist}.\hfill \end{array}\right.$$

where $\mathcal{X}=\{x_1,\cdots ,x_N\}$ is an ordered set with $x_1<x_2<\cdots <x_N.$ In other words, $f_R(y_1,\cdots ,y_N)$ is the smallest $x_i$ so that $(x_i,y_i)\in R.$ It is easy to verify that

$$\begin{array}{c}\hfill f_R(y_1,\cdots ,y_{\left|\mathcal{X}\right|})=\sum _{i=1}^{\left|\mathcal{X}\right|}{x}_i·\overline{R}(x_1,y_1)·\dots ·\overline{R}(x_{i-1},y_{i-1})·R(x_i,y_i).\end{array}$$

(8)

Here, we emphasize that we do not require $\overline{\mathcal{X}}$ itself to be a group, but we implicitly assume that it can be regarded as a subset of an Abelian group $\tilde{\mathcal{X}}$ (e.g., $\overline{\mathcal{X}}=\{0,1,2,4\}$ can be regarded as a subset of ${\mathbb{Z}}_5$). Next, we define $U_R$ to be a unitary on $\mathbb{C}{\left[\overline{\mathcal{Y}}\right]}^{\otimes \mathcal{X}}\otimes \mathbb{C}\left[\tilde{\mathcal{X}}\right]$ for register $DP$ so that

$$\begin{array}{c}\hfill U_R{|\mathbf{y}\rangle }_D{|w\rangle }_P={|\mathbf{y}\rangle }_D{|w+f_R(y_1,\cdots ,y_{\left|\mathcal{X}\right|})\rangle }_P,\end{array}$$

(9)

where ${|\mathbf{y}\rangle }_D:=|y_1{\rangle }_{D_{x_1}}\cdots {|y_{\left|\mathcal{X}\right|}\rangle }_{D_{x_{\left|\mathcal{X}\right|}}}$. Let

$${\mathsf{\Gamma }}_R=\underset{x}{max}\left|\{y\mid (x,y)\in R\}\right| \mathrm{and} {\mathsf{\Gamma }}_x=\left|\{y\mid (x,y)\in R\}\right|.$$

(10)

Notice that our $U_R$ is an alternative specification, but it is identical to $U_R$ in [32]. The following lemma was proved in [32] (we can obtain the same bound by a proof for our specification).

Lemma 11.

For any $x\in \mathcal{X}$, $\left|\right|[F_{D_x},U_R]\left|\right|\le 4\sqrt{2{\mathsf{\Gamma }}_R/2^n}.$

Lemma 12.

$[{\mathrm{CNOT}}_{XYD},U_R]=0.$

Proof. 

It can be seen that ${\mathrm{CNOT}}_{XYD}={\sum }_{\mathbf{y}}\left({\sum }_{x,y}\right|x,y_x+y\rangle \langle x,y\left|\right)\otimes {|\mathbf{y}\rangle \langle \mathbf{y}|}_D$ and also that $U_R={\sum }_{\mathbf{y}}\left({\sum }_w\right|w+f_R\left(\mathbf{y}\right)\rangle \langle w{|}_P)\otimes {|\mathbf{y}\rangle \langle \mathbf{y}|}_D$. Therefore, D is a control register for $U_R$ and ${\mathrm{CNOT}}_{XYD}$ in the computational basis. According to Lemma 2(1), they commute. □

Theorem 1.

$\left|\right|[CSt{O}_s,U_R]\left|\right|\le 8·2^{-n/2}\sqrt{2{\mathsf{\Gamma }}_R}.$

Proof. 

Notice that $CSt{O}_s={\sum }_{x\in \mathcal{X}}|x\rangle \langle x|\otimes CSt{O}_{sY{D}_x}$ and for $x\in {\mathsf{\Xi }}_1$, $CSt{O}_{sY{D}_x}={\mathrm{CNOT}}_{Y{D}_x}$. Hence, according to Lemma 12, $[CSt{O}_s,U_R]={\sum }_{x\notin {\mathsf{\Xi }}_1}{|x\rangle \langle x|}_X\otimes [F_{D_x}\otimes {\mathrm{CNOT}}_{Y{D}_x}\otimes F_{D_x},U_R],$ where we also use $\left[\right|x\rangle \langle x{|}_X,U_R]=0.$ By Lemmas 1 (3) and 3 (2),

$$\left|\right|[CSt{O}_s,U_R]\left|\right|\le 2\underset{i}{max}\left|\right|[F_{D_{x_i}},U_R]\left|\right|+\left|\right|[\mathrm{CNOT},U_R]\left|\right|.$$

By Lemmas 11 and 12, the result follows. □

5.2. Bounding the Probability for Relation Search Through Oracle Queries

We are interested in checking whether a relation R is satisfied (i.e., $R(x,y_x)=1$ for some x) in the oracle register D after oracle queries. The following lemma upper bounds this probability. The proof idea is that $R(x,y_x)=1$ can be detected by applying $U_R$ and measuring the P register with outcome $\widehat{x}\ne 0.$ If we apply $U_R$ and measure P at the beginning of the interaction, then $\widehat{x}=0$, because the initial oracle state is a dummy. Hence, the success probability at the end of interaction is obtained by sequentially switching the order of $U_R$ and the operators during the interactions, as well as by looking at the norm of the commutator of these operators with $U_R$.

Lemma 13.

Let $\mathcal{A}$ be a quantum algorithm with access to ${\mathbf{CStO}}_s$, incurring $L_0$ random oracle queries and $q-L_0$ PointReg1 queries. The final state goes through $U_R$ of relation R and a projective measurement on register P in the computational basis with outcome $\widehat{x}\in \overline{\mathcal{X}}$. Then,

$$\begin{array}{c}\hfill Pr(\widehat{x}\ne 0\wedge \neg \mathsf{abort})\le 128q^2{\mathsf{\Gamma }}_R/2^n.\end{array}$$

(11)

Proof. 

Let $|\psi \rangle$ be the initial state of $\mathcal{A}$ with registers $XYZ$. The joint initial state with oracle is then $|{\omega }_0{\rangle =|\psi \rangle }_{XYZ}\otimes {\left({\otimes }_x\right|\perp \rangle }_{D_x}{)\otimes |0\rangle }_P$ (after register P is added). Then, $\mathcal{A}$ has access to ${\mathbf{CStO}}_s$, incurring $L_0$ random oracle queries with intermediate operator $V_{XYZ}$, where, for simplicity, we assume that $V_{XYZ}$ remains unchanged throughout the game. Finally, oracle applies $U_R$ on $DP$ and projective measurement $\mathbf{P}$ on P, outputting the outcome $\widehat{x}$. The final state before measurement $\mathbf{P}$ is $|\omega \rangle =U_R{(V·{\mathbf{CStO}}_s)}^L|{\omega }_0\rangle$ for some L, where ${\mathbf{CStO}}_s$ is the PointReg0 query or PointReg1 query or random oracle query. If the query is PointReg0, it does not operate on the state and so commutes with $U_R$; if it is PointReg1, then we only consider the case $x\in {\mathsf{\Xi }}_0$. Under $\neg \mathsf{abort}$, it consists of projector ${\mathsf{\Pi }}_0$ and $U_{\perp ,r}=|r\rangle \langle \perp |+|\perp \rangle \langle r|+{\sum }_{v\ne r}|v\rangle \langle v|$ for uniformly random r over $\mathcal{Y}$. We notice that $[{\mathsf{\Pi }}_0,U_R]=0$ by Lemma 2(2). Furthermore, it is not hard to verify that $U_{\perp ,r}{\mathsf{\Pi }}_0$ in PointReg1 commutes with $U_R$ if $(x,r)\notin R$ (as $(x,\perp )\notin R$). If it is a random oracle query, we notice that $[{\mathsf{\Lambda }}_i,U_R]=0$, as D is the control register for both ${\mathsf{\Lambda }}_i$ and $U_R$ in the computational basis. Therefore,

$$\begin{array}{cc}\hfill & Pr(\widehat{x}\ne 0\wedge \neg \mathsf{abort})\hfill \\ \hfill & \le {\mathbf{E}}_{\mathbf{r}}\left(\right||(I-|0\rangle \langle 0{|}_P){|\omega \rangle ||}^2)/\ast r^{\prime }\text{s from PointReg1};\text{state}|\omega \rangle \text{is consistent with}\neg \mathsf{abort}\ast /\hfill \\ \hfill & ={\mathbf{E}}_{\mathbf{r}}\left(\right||(I-|0\rangle \langle 0{|}_P)[U_R,{(V·{\mathbf{CStO}}_s)}^L]|{\omega }_0\rangle +(I-|0\rangle \langle 0{|}_P){(V·{\mathbf{CStO}}_s)}^L{U}_R|{\omega }_0{\rangle \left|\right|}^2)\hfill \\ \hfill & /\ast {\mathbf{CStO}}_s\text{requires the operator for measurement outcome}(\text{e.g.,} {\mathsf{\Pi }}_0, {\mathsf{\Lambda }}_{i0})\text{is consistent with}\neg \mathsf{abort}\ast /\hfill \\ \hfill & ={\mathbf{E}}_{\mathbf{r}}\left(\right||(I-|0\rangle \langle 0{|}_P)[U_R,{(V·{\mathbf{CStO}}_s)}^L]|{\omega }_0{\rangle \left|\right|}^2)\hfill \\ \hfill & /\ast \mathrm{as} V \mathrm{and}{\mathbf{CStO}}_s{\text{do not operate on} P,\text{and so part 2 has} |0\rangle }_P \text{before applying} I-|0\rangle \langle 0|\ast /\hfill \\ \hfill & \le {\mathbf{E}}_{\mathbf{r}}\left(\right||[U_R,{(V·\mathbf{CStO})}^L]{\left|\right|}^2)\le {\mathbf{E}}_{\mathbf{r}}\left\{\right(L_0\left|\right|[U_R,CSt{O}_s]\left|\right|+\sum _i\left|\right|[U_R,U_{\perp ,r_i}]{\left|\right|)}^2\}\hfill \\ \hfill & /\ast \mathrm{Lemma} 1\left(3\right),[{\mathsf{\Lambda }}_i,U_R]=[{\mathsf{\Pi }}_0,U_R]=[V,U_R]=0 \mathrm{and} L_0 \mathrm{are} ♯ \mathrm{of} CSt{O}_s\mathrm{queries},\hfill \\ \hfill & \mathrm{and} r_i \text{corresponds to} r \text{in the} i\mathrm{th} \text{PointReg1 query}.\ast /\hfill \\ \hfill & \le {\mathbf{E}}_{\mathbf{r}}\left\{{(8L_0·2^{-n/2}\sqrt{2{\mathsf{\Gamma }}_R}+2N_{\mathbf{r}})}^2\right\}./\ast \text{using Theorem 1} \ast /\hfill \\ \hfill & /\ast N_{\mathbf{r}} \text{is the number of} r_i \mathrm{in} i\mathrm{th} \text{PointReg1}\left(x_i\right)\text{so that}(x_i,r_i)\in R\ast /\hfill \\ \hfill & /\ast [U_R,U_{\perp ,r}]=0 \mathrm{for} (x,r)\notin R;\left|\right|[U_R,U_{\perp ,r}]\left|\right|\le 2 \mathrm{as} \left|\right|U_R\left|\right|=\left|\right|U_{\perp ,r}\left|\right|=1\ast /\hfill \\ \hfill & \le 128q^2{\mathsf{\Gamma }}_R/2^n,\hfill \end{array}$$

where the last inequality follows from the calculation with the observation: $N_{\mathbf{r}}$ is the result of a Bernouli trial with probability ${\mathsf{\Gamma }}_R/2^n$ for $q-L_0$ times; $\mathbf{E}{(a+N_{\mathbf{r}})}^2=Var\left(N_{\mathbf{r}}\right)+{[a+\mathbf{E}\left(N_{\mathbf{r}}\right)]}^2$; $Var\left(N_{\mathbf{r}}\right)=(q-L_0){\mathsf{\Gamma }}_R/2^n(1-{\mathsf{\Gamma }}_R/2^n)$ and $\mathbf{E}\left(N_{\mathbf{r}}\right)=(q-L_0){\mathsf{\Gamma }}_R/2^n$. The lemma follows. □

6. Query Extraction for ${\mathbf{CStO}}_s$

In a classical random oracle model, given $t=f(x,RO(x\left)\right)$ for a fixed function f, a simulator can easily extract x by searching through the adversary’s oracle query history. In the quantum setting, this strategy is not useful, as an attacker could query to an oracle in a superposition that includes x as one component. So generally, it is not clear how we can extract x without destroying the quantum state. In this section, we will show that this extraction is possible, and also, we make the extraction on the fly (i.e., right after t is given). This is an extension of Don et al. [32] from the CStO setting to the CStO_s setting.

This section is organized as follows. In Section 6.1, we present the simulation of ${\mathbf{CStO}}_s$ with an extraction interface. In Section 6.2, we show that if the extraction is conducted at the end of game, then the extraction is correct. In Section 6.3, we show that if we extract on the fly, then the extraction is still correct and the output is not disturbed. This last property is obtained from the extraction at the end of the game by observing that ${\mathbf{CStO}}_s$ almost commutes with the unitary measurement $U_R$ (with high probability), and so we can move $U_R$ gradually to the location where the attacker outputs the commitment t (to be extracted) without significantly disturbing the quantum state.

6.1. Simulating CStO_s with Extraction

In this section, we adapt the simulation of $\mathbf{CStO}$ with the extraction capability in [32] to the ${\mathbf{CStO}}_s$ setting. Essentially, the simulator simulates the oracle and also provides an interface for extracting the attacker’s oracle query x that, together with y in $D_x$, is a witness of a target “commitment”. Let $\theta (x,y)$ be an arbitrary but fixed function from $\mathcal{X}\times \mathcal{Y}$ to $\mathcal{T}.$ For $t\in \mathcal{T}$, define relation $R_t=\{(x,y)\mid \theta (x,y)=t\}$, and $U_t$ denotes unitary $U_{R_t}$. Then, the simulator is described in Figure 2.

In the following two subsections, we prove that if $\mathcal{A}$ uses x and $y=RO\left(x\right)$ to generate t, then the extracted $\widehat{x}$ from $\mathcal{S}.E\left(t\right)$ will equal to x. This is useful in a security proof where an attacker generates an output and we need to find out the witness of this output. We first prove a weaker version of this: if $\widehat{x}$ is extracted at the end of game, the claim is true. Then, we extend to the case that $\widehat{x}$ is extracted on the fly (i.e., right after $\mathcal{A}$ outputs t).

6.2. Extraction at the End of Game

We begin with a collision event in a computational basis ${|\mathbf{y}\rangle }_D$ in the oracle state with respect to function f in the sense that $f(x,y_x)=f(x^{\prime },y_{x^{\prime }})$ for some $x^{\prime }\ne x$. We give a result that says that after q oracle queries, the probability of collision in the oracle is small. This is extended from [31] Theorem 2 in the setting of $\mathbf{CStO}$ to ${\mathbf{CStO}}_s$; see Appendix C for a proof.

Lemma 14.

Let $f:\mathcal{X}\times \mathcal{Y}\to \mathcal{T}$. Then, for any quantum algorithm $\mathcal{A}$ with access to CStO _s, incurring q oracle queries of either PointReg1 or random oracle,

$$Pr(\mathsf{col}\wedge \neg \mathsf{abort})\le 16q^3{\mathsf{\Gamma }}_f/2^n,$$

(12)

where $\mathsf{col}$ is the collision event in the final state ${\rho }_q$, and ${\mathsf{\Gamma }}_f={max}_{x^{\prime }\ne x,y^{\prime }}\left|\{y\mid f(x,y)=f(x^{\prime },y^{\prime })\}\right|$.

Now, we give an extraction theorem, where $\widehat{x}$ is extracted at the end of oracle access. It states that if attacker computes t from x so that $t=f(x,RO(x\left)\right)$, then $\mathcal{S}.E\left(t\right)$ at the end of game will most likely have $\widehat{x}=x$. The idea is as follows. Assume $\widehat{x}\ne x$. After an attacker’s oracle access to ${\mathbf{CStO}}_s$, we apply a classical oracle query on x with the result $y_x$. Assume that this state (right before $\mathcal{S}.E\left(t\right)$) is ${\sum }_{\mathbf{y}:y_{x}fixed}{\lambda }_{\mathbf{y}}|{\omega }_{\mathbf{y}}{\rangle |\mathbf{y}\rangle }_{D_{\mathcal{X}-\left\{x\right\}}}F|y_x{\rangle }_{D_x}{|0\rangle }_P$. Furthermore, notice that $F|y_x\rangle =|y_x\rangle +|\delta \rangle$. If $\mathbf{y}$ in the sum leads to a measurement outcome $\widehat{x}$ on register P (i.e., after $\mathcal{S}.E\left(t\right)$), then it has a collision (since $f(\widehat{x},y_{\widehat{x}})=t=f(x,y_x)$). This probability is small (by Lemma 14), and we can ignore it. If ${|\mathbf{y}\rangle }_{D_{\mathcal{X}-\left\{x\right\}}}|y_x^{\prime }\rangle$ for $y_x^{\prime }\ne y_x$ under $\mathcal{S}.E\left(t\right)$ gives $\widehat{x}$, then $y_x^{\prime }$ must come from $\delta$. However, $\left|\right|\delta \left|\right|$ is very small. So, this is unlikely too. This idea is from [32] Prop 4.5 in the $CStO$ case and can be generalized to prove the case of a vector $(\mathbf{t},\mathbf{x})$.

Theorem 2.

Consider a quantum algorithm $\mathcal{A}$ with access to $\mathcal{S}$ (via interfaces other than $\mathcal{S}.E$), including q random oracle queries or PointReg1 queries and outputting $\mathbf{t}\in {\mathcal{T}}^{\ell }$ and $\mathbf{x}\in {\mathcal{X}}^{\ell }.$ Let $h_i$ be the output for an additional classical query $x_i$ to $\mathcal{S}.RO$ and ${\widehat{x}}_i=\mathcal{S}.E\left(t_i\right)$. Then,

$$\begin{array}{c}\hfill Pr(\exists i:x_i\ne {\widehat{x}}_i,f(x_i,h_i)=t_i\wedge \neg \mathsf{abort})\le 2^{-n+1}\ell +16{(q+\ell )}^3{\mathsf{\Gamma }}_f/2^n.\end{array}$$

(13)

Proof. 

Let the adversary–oracle joint state be $|{\psi }_0\rangle$ after queries to $\mathcal{S}$ (including q random oracle queries or PointReg1 queries). In the following, we always assume that random the oracle query does not abort. Then, $\mathcal{A}$ measures and outputs $\mathbf{t},\mathbf{x}$. Each $x_i$ is then classically queried to $\mathcal{S}.RO$ and results in a joint state $|{\psi }_1\rangle$. We assume that $\mathbf{x}\cap {\mathsf{\Xi }}_1=\varnothing$ (the other case is similar). Hence, $|{\psi }_1\rangle$ can be written as $|{\psi }_1{\rangle =|\mathbf{r}\rangle }_{D_{{\mathsf{\Xi }}_1}}\otimes F_{D_{\mathbf{x}}}{|\mathbf{h}\rangle }_{D_{\mathbf{x}}}\otimes {\sum }_{\omega \mathbf{u}:\mathbf{u}\in {\overline{\mathcal{Y}}}^A}{\lambda }_{\omega \mathbf{u}}{|\omega \rangle }_{XYZ}{|\mathbf{u}\rangle }_{D_A},$ where ${\mathsf{\Xi }}_1\cup \mathbf{x}\cup A$ is a decomposition of $\mathcal{X}.$

Finally, it applies the projective measurement ${\mathsf{\Pi }}_D=\left\{\right|\mathbf{y}\rangle {\langle \mathbf{y}\left|\right\}}_{\mathbf{y}\in {\overline{\mathcal{Y}}}^{\mathcal{X}}}$ in the computational basis on D and applies $U_{t_i},i=1,\cdots ,\ell$ followed by (projective) measurement on register P, as well as measurement $({\mathsf{\Pi }}_{col},I-{\mathsf{\Pi }}_{col})$ to the resulting state (assuming the collision measurement writes the result in a new register C), where ${\mathsf{\Pi }}_{col}$ is a projection into a space spanned by ${|\mathbf{y}\rangle }_D$, with $\mathbf{y}\in {\overline{\mathcal{Y}}}^{\mathcal{X}}$ satisfying $f(x,y_x)=f(x^{\prime },y_{x^{\prime }})$ for some $x^{\prime }\ne x$ and $y_x,y_{x^{\prime }}\in \mathcal{Y}.$ Notice that D is a control register in the computational basis for ${\mathsf{\Pi }}_D,\mathbf{P}{U}_{t_i}$, and collision measurement, where $\mathbf{P}$ is the projective measurement on P. Hence, by Lemma 2, they all commute. Hence, both the collision probability and $Pr(\exists i:x_i\ne {\widehat{x}}_i,f(x_i,h_i)=t_i)$ obtained after our ending measurements will remain the same as the original game (where ${\mathsf{\Pi }}_D$ and collision measurement are not applied). For the collision probability, it is the same as we move $\mathbf{P}{U}_{t_i}$ and ${\mathsf{\Pi }}_D$ to after collision measurement; for $Pr(\exists i:x_i\ne {\widehat{x}}_i,f(x_i,h_i)=t_i)$, it is similar by keeping $\mathbf{P}{U}_{t_i}$ while moving other two operators to the end of game. Let $col$ be the output 0 of measurement $({\mathsf{\Pi }}_{col},I-{\mathsf{\Pi }}_{col})$. Notice that

$$\begin{array}{cc}\hfill & Pr(\exists i:x_i\ne {\widehat{x}}_i,f(x_i,h_i)=t_i||{\psi }_1\rangle )\hfill \end{array}$$

(14)

$$\begin{array}{cc}\hfill \le & Pr(\exists i:x_i\ne {\widehat{x}}_i\wedge f(x_i,h_i)=t_i\wedge \neg col\left|\right|{\psi }_1\rangle )+Pr\left(col\right||{\psi }_1\rangle )\hfill \end{array}$$

(15)

Notice that register $D_{x_i}$ in $|{\psi }_1\rangle$ is $|h_i\rangle +2^{-n/2}\left(\right|\perp \rangle -|{\varphi }_0\rangle ).$ Since $f(x_i,h_i)=t_i$, it follows that under $\neg col$ condition, $x_i\ne {\widehat{x}}_i$ implies that after measurement on P (that results in ${\widehat{x}}_i$ in the ith component on register P), the post-measurement joint state $|{\psi }^{\prime }{\rangle }_{XYZD}{|\widehat{\mathbf{x}}\rangle }_P$ must have $D_{x_i}$ content different from $h_i$ (that is, $\langle h_i|{\psi }^{\prime }\rangle =0$). Since $|{\psi }_1\rangle$ has $F|h_i\rangle$ in $D_{x_i}$, this has a probability $1-|\langle h_i|\left(\right|h_i\rangle +2^{-n/2}|{\varphi }_0{\rangle \left)\right|}^2=1-{(1-2^{-n})}^2\le 2^{-n+1}.$ There are at most ℓ possible is. So, the first item in Equation (15) is at most $2^{-n+1}\ell$. On the other hand, $|{\psi }_1\rangle$ is obtained by measurements and unitaries. Averaging over the choices of $|{\psi }_1\rangle$ satisfying $\neg \mathsf{abort}$ (due to intermediate measurements) gives $Pr(\exists i:x_i\ne {\widehat{x}}_i\wedge f(x_i,h_i)=t_i\wedge \neg col\neg \mathsf{abort})\le 2^{-n+1}\ell$. By Lemma 14, $Pr(col\wedge \neg \mathsf{abort})\le 16{(q+\ell )}^3{\mathsf{\Gamma }}_f/2^n$. Thus, $Pr(\exists i:x_i\ne {\widehat{x}}_i,f(x_i,h_i)=t_i\wedge \neg \mathsf{abort})\le 2^{-n+1}\ell +16{(q+\ell )}^3{\mathsf{\Gamma }}_f/2^n.$ □

6.3. Extraction on the Fly

We have shown the extraction result where the extractions occur only at the end of the game. To be useful, it is expected that we can extract them “on the fly” (i.e., right after each commitment is given during the game). In the following, we consider this. The result is extended from [32] from the $\mathbf{CStO}$ setting to the ${\mathbf{CStO}}_s$ setting.

Let us consider a function $f:\mathcal{X}\to \mathcal{T}\cup \{\varnothing \}$ with some special set $\mathsf{\Xi }\subset \mathcal{X}$ so that $f(\mathsf{\Xi },\mathcal{Y})=\varnothing$ and $f(\mathcal{X}\setminus \mathsf{\Xi },\mathcal{Y})\subseteq \mathcal{T}$. Consider the following games, where $\mathcal{S}.{\mathbf{CStO}}_s$ is $\mathcal{S}.RO$ or $\mathcal{S}.P{R}_0$ or $\mathcal{S}.P{R}_1$.

• Game ${\mathsf{\Gamma }}_0.$ $\mathcal{A}$, with $q_1^{\prime }$ queries to ${\mathbf{CStO}}_s$, outputs $t\in \mathcal{T}$, and then with $q_2^{\prime }$ queries to ${\mathbf{CStO}}_s$, outputs $x\in \mathcal{X}$, and auxiliary output $W.$ Finally, x is classically issued to ${\mathbf{CStO}}_s$ with response h.
• Game ${\mathsf{\Gamma }}_1$. $\mathcal{A}$, with $q_1^{\prime }$ queries to $\mathcal{S}.{\mathbf{CStO}}_s$, outputs $t\in \mathcal{T}$, and $\mathcal{S}.E\left(t\right)$ is executed to output $\widehat{x}$. Then, $\mathcal{A}$ continues $q_2^{\prime }$ queries to $\mathcal{S}.{\mathbf{CStO}}_s$ and finally outputs $x\in \mathcal{X}$ and auxiliary output W. Finally, x is classically issued to $\mathcal{S}.{\mathbf{CStO}}_s$ with response h.

Let $q_1$ be the number of random oracle queries or PointReg1 queries in the first $q_1^{\prime }$ queries to $\mathcal{S}.{\mathbf{CStO}}_s$. Similarly, we can define $q_2.$ The pair ${(X,Y)}_{\mathsf{\Gamma }}$ denotes $(X,Y)$ in game $\mathsf{\Gamma }$. Define $\Delta ({(X,Y=y)}_{{\mathsf{\Gamma }}_0},{(X,Y=y)}_{{\mathsf{\Gamma }}_1})\stackrel{def}{=}{\displaystyle \frac{1}{2}}{\sum }_x|P_{XY}(x,y)-Q_{XY}(x,y)|$ (a partial sum in the statistical distance), where $P_{XY}$ (respectively, $Q_{XY}$) is the joint distribution of $XY$ in ${\mathsf{\Gamma }}_0$ (respectively, ${\mathsf{\Gamma }}_1$).

In the following, we show that the adversarial outputs from ${\mathsf{\Gamma }}_0$ and ${\mathsf{\Gamma }}_1$ are close. Also, the extraction $\widehat{x}$ from $\mathcal{S}.E\left(t\right)$ in ${\mathsf{\Gamma }}_1$ will be mostly identical to x. The idea is that ${\mathsf{\Gamma }}_0$ can be regarded as the simulated game with extraction occurring at the end, because the extraction at the end does not affect the adversarial output. Then, we try to shift $\mathcal{S}.E\left(t\right)$ step by step toward right after the output of t and find out that the change of the quantum state throughout this shift process is small. The second claim $x=\widehat{x}$ follows from the foregoing argument and Theorem 2.

Theorem 3.

Let ${\left(\alpha \right)}_{\mathsf{\Gamma }}$ be the random variable α with respect to game $\mathsf{\Gamma }.$ Let $\mathcal{A}$ be a quantum algorithm with access to ${\mathbf{CStO}}_s$ such that ${\mathsf{\Xi }}_1\subseteq \mathsf{\Xi }$. Let $q=q_1+q_2.$ Then,

$$\begin{array}{cc}\hfill & \Delta ({(t,x,h,W,\mathsf{abort}=0)}_{{\mathsf{\Gamma }}_0},{(t,x,h,W,\mathsf{abort}=0)}_{{\mathsf{\Gamma }}_1})\le 8(q_2+1)\sqrt{2{\mathsf{\Gamma }}_f/2^n},\hfill \end{array}$$

(16)

$$\begin{array}{cc}\hfill & Pr(x\ne \widehat{x}\wedge f(x,h)=t\wedge \mathsf{abort}=0)\le 8(q_2+1)\sqrt{2{\mathsf{\Gamma }}_f/2^n}+2^{-n+1}+{\displaystyle \frac{16{(q+1)}^3{\mathsf{\Gamma }}_f}{2^n}}.\hfill \end{array}$$

(17)

Proof. 

Let $U_t$ be the unitary measurement on $DP$, following which the projective measurement ${\left\{P_x\right\}}_{x\in \overline{\mathcal{X}}}$ on register P is applied, resulting in $\widehat{x}$. Assume that ${\left\{T_t\right\}}_t$ is the measurement for t. Let $V_{XYW}$ be the unitary operator of $\mathcal{A}$ between queries and ${\left\{M_{xw}\right\}}_{x,w}$ be the measurement for $(x,w).$ The initial state is $|{\gamma }_0{\rangle =|\omega \rangle }_{XYW}\otimes {\left({\otimes }_x\right|\perp \rangle }_{D_x}{)\otimes |0\rangle }_P.$ Then, the final unormalized state in ${\mathsf{\Gamma }}_1$ is

$$\begin{array}{cc}\hfill |{\gamma }_1\rangle =& P_h·\mathcal{S}.RO·M_{xw}·{(\mathcal{S}.{\mathbf{CStO}}_s·V)}^{q_2}·\mathcal{S}.E\left(t\right)·T_t·{(\mathcal{S}.{\mathbf{CStO}}_s·V)}^{q_1}|{\gamma }_0\rangle \hfill \end{array}$$

(18)

$$\begin{array}{cc}\hfill =& P_h·{\mathbf{CStO}}_s·M_{xw}·{({\mathbf{CStO}}_s·V)}^{q_2}·P_{\widehat{x}}·U_t·T_t·{({\mathbf{CStO}}_s·V)}^{q_1}|{\gamma }_0\rangle ,\hfill \end{array}$$

(19)

where the last ${\mathbf{CStO}}_s$ in Equation (19) is a random oracle query and $P_{\widehat{x}}=|\widehat{x}\rangle \langle \widehat{x}{|}_P$. Furthermore, if $\mathcal{A}$ makes a random oracle query, then under $\mathsf{abort}=0$, $\mathcal{S}.{\mathbf{CStO}}_s$ is $CSt{O}_s·{\mathsf{\Lambda }}_{i0}$; if $\mathcal{A}$ makes PointReg1 query x and $\mathsf{abort}=0$, then oracle applies ${\mathsf{\Pi }}_0$, and then $U_{\perp ,r}$ to $D_x$. A PointReg0 query does not impact on the quantum state and hence does not occur in the above equation, but it is implicit to maintain ${\mathsf{\Xi }}_0$. We assume that the operators other than the measurements mentioned are unitary (which can be made up with some auxiliary registers). Then, we have the probability of $xhw\widehat{x}t{\mathsf{\Xi }}_1$ with $\mathsf{abort}=0$ in ${\mathsf{\Gamma }}_1$ (denoted by $p_{xhw\widehat{x}t{\mathsf{\Xi }}_1}$) is $\left|\right|{\gamma }_1{\left|\right|}^2$. Furthermore, $P_{\widehat{x}}$ can be moved to the end of game (as variable $\widehat{x}$ and register P are not related to operators currently on the left to $P_{\widehat{x}}$), $p_{xhw\widehat{x}t{\mathsf{\Xi }}_1}=\left|\right|{\gamma }_2{\left|\right|}^2$, where

$$\begin{array}{c}\hfill |{\gamma }_2\rangle =P_{\widehat{x}}{P}_h·{\mathbf{CStO}}_s·M_{xw}·{({\mathbf{CStO}}_s·V)}^{q_2}·U_t·T_t·{({\mathbf{CStO}}_s·V)}^{q_1}|{\gamma }_0\rangle .\end{array}$$

(20)

If we remove $P_{\widehat{x}}{U}_t$ from Equation (19), then $|{\gamma }_1\rangle$ becomes the final state of ${\mathsf{\Gamma }}_0$. Then, the probability of $xhw\widehat{x}t{\mathsf{\Xi }}_1$ in ${\mathsf{\Gamma }}_0$ with $\mathsf{abort}=0$ (denoted by $q_{xhw\widehat{x}t{\mathsf{\Xi }}_1}$) is $\left|\right|{\gamma }_2^{\prime }{\left|\right|}^2$ (if further applying $U_t$ and projective measurement ${\left\{P_{\widehat{x}}\right\}}_{\widehat{x}}$ at the end of ${\mathsf{\Gamma }}_0$), where

$$\begin{array}{c}\hfill |{\gamma }_2^{\prime }\rangle =P_{\widehat{x}}{U}_t{P}_h·{\mathbf{CStO}}_s·M_{xw}·{({\mathbf{CStO}}_s·V)}^{q_2}·T_t·{({\mathbf{CStO}}_s·V)}^{q_1}|{\gamma }_0\rangle .\end{array}$$

(21)

By the triangle inequality, Equation (16) is bounded by

$$\begin{array}{c}\hfill {\displaystyle \frac{1}{2}}\sum _{xhw\widehat{x}t{\mathsf{\Xi }}_1}\left|\right|\left|\right|{\gamma }_2{\rangle \left|\right|}^2-\left|\right||{\gamma }_2^{\prime }{\rangle \left|\right|}^2|\le {\displaystyle \frac{1}{2}}\sum _{i=0}^{q_2}\sum _{xhw\widehat{x}t{\mathsf{\Xi }}_1}\left|\right|\left|\right|{\gamma }_{2(i+1)}{\rangle \left|\right|}^2-\left|\right||{\gamma }_{2i}{\rangle \left|\right|}^2|,\end{array}$$

(22)

where $|{\gamma }_{2i}\rangle$ is the variant of $|{\gamma }_2\rangle$ with $U_t$ relocated (starting from the leftmost) to right after the ith ${\mathbf{CStO}}_s$ operator in $|{\gamma }_2\rangle$ (that is either random oracle query or PointReg1 query), and thus ${\gamma }_2^{\prime }=|{\gamma }_{20}\rangle$ and $|{\gamma }_2\rangle =|{\gamma }_{2(q_2+1)}\rangle$.

We consider the inner summation at Equation (22) for a fixed i. We can separate $xhw\widehat{x}t{\mathsf{\Xi }}_1$ as $AB$, where A is the subset of variables obtained by measurements in $|{\gamma }_{2i}\rangle$ after $U_t$ and B are the remaining variables. Let $|{\psi }_B\rangle$ be the state right before $U_t$ and $M_A^{\prime }$ be the product of operators after $U_t$ and the ith ${\mathbf{CStO}}_s$ in $|{\gamma }_{2i}\rangle$. Then, $|{\gamma }_{2i}\rangle =M_A^{\prime }·U_t·{\mathbf{CStO}}_s|{\psi }_B\rangle$, and $|{\gamma }_{2(i+1)}\rangle =M_A^{\prime }·{\mathbf{CStO}}_s·U_t|{\psi }_B\rangle$, as $[U_t,V]=0$. It is well known that the measurement can be made at the end of operation without changing the measurement outcome distribution. Hence, we can assume that $M_A^{\prime }=M_{A}S$ for the projection $M_A$ of A and unitary S. That is, we can assume that $|{\gamma }_{2i}\rangle =M_A·S·U_t·{\mathbf{CStO}}_s|{\psi }_B\rangle$ and $|{\gamma }_{2(i+1)}\rangle =M_A·S·{\mathbf{CStO}}_s·U_t|{\psi }_B\rangle$. Let $|{\psi }_B^{\prime }\rangle$ be the normalized $|{\psi }_B\rangle$. Then,

$$\begin{array}{cc}\hfill & {\displaystyle \frac{1}{2}}\sum _{xhwt\mathbf{b}\mathsf{\Xi }}\left|\right|\left|\right|{\gamma }_{2(i+1)}{\rangle \left|\right|}^2-\left|\right||{\gamma }_{2i}{\rangle \left|\right|}^2|\hfill \end{array}$$

(23)

$$\begin{array}{cc}\hfill =& \sum _B\left|\right||{\psi }_B{\rangle \left|\right|}^2·{\displaystyle \frac{1}{2}}\sum _A\left|\right||M_A·S·U_t·{\mathbf{CStO}}_s|{\psi }_B^{\prime }{\rangle \left|\right|}^2-\left|\right|M_A·S·{\mathbf{CStO}}_s·U_t|{\psi }_B^{\prime }{\rangle \left|\right|}^2|\hfill \end{array}$$

(24)

If ${\mathbf{CStO}}_s$ is a random oracle query, then the inner sum is the statistical distance between measurement outcomes from $S·U_t·CSt{O}_s·\mathsf{\Lambda }|{\psi }_B^{\prime }\rangle$ and $S·CSt{O}_s·U_t·\mathsf{\Lambda }|{\psi }_B^{\prime }\rangle$ (Note: Here, $\mathsf{\Lambda }$ is some ${\mathsf{\Lambda }}_{i0}$, and $[U_t,\mathsf{\Lambda }]=0$). By Theorem 9.1 [36], it is no more than their trace distance. Further, by Lemma 4, the trace distances of two states are no more than their Euclidean distances, which are further bounded by $\left|\right|[CSt{O}_s,U_t]\left|\right|$ (by the form of Equation (24)). Hence, by Theorem 1,

$$\begin{array}{c}\hfill Equation\left(24\right)\le \sum _B\left|\right||{\psi }_B{\rangle \left|\right|}^2·\left|\right|U_t,{\mathbf{CStO}}_s\left|\right|=\left|\right|U_t,{\mathbf{CStO}}_s\left|\right|\le 8·2^{-n/2}\sqrt{2{\mathsf{\Gamma }}_f}.\end{array}$$

(25)

If ${\mathbf{CStO}}_s$ is PointReg1 query $x\in {\mathsf{\Xi }}_0$ with $\mathsf{abort}=0$, this will apply ${\mathsf{\Pi }}_0$ and $U_{\perp ,r}=|r\rangle \langle \perp |+|\perp \rangle \langle r|+{\sum }_{s\ne r}|s\rangle \langle s|$ to register $D_x$. Note that $U_t$ commutes with $U_{\perp ,r}$ if $f(x,r)\ne t$ (because $R_t(x,r)=R_t(x,\perp )=0$ and so ${|\perp \rangle }_{D_x}$ replaced by ${|r\rangle }_{D_x}$ will not change $\widehat{x}$). By Lemma 2(2), $[{\mathsf{\Pi }}_0,U_t]=0.$ Thus, ${\mathbf{CStO}}_s$ (i.e., PointReg1) commutes with $U_t$ if $f(x,r)\ne t$. By our assumption, $\mathcal{A}$ satisfies ${\mathsf{\Xi }}_1\subseteq \mathsf{\Xi }$. Hence, $f(x,r)=\varnothing$, and so $f(x,r)=t$ will never hold. Hence, PointReg1 commutes with $U_t.$ Hence, Equation (24) is 0 for this query.

Finally, since there are at most $q_2+1$ random oracle queries after t is measured, Equation (22) is bounded by $8(q_2+1)\sqrt{2{\mathsf{\Gamma }}_f/2^n}.$

Now, we consider the second claim. Notice that Z is defined as a Boolean variable $(x\ne \widehat{x}\wedge f(x,h)=t\wedge \mathsf{abort}=0)$ of $(x,h,\widehat{x},t)$. We still use $p_Z$ to denote the distribution in ${\mathsf{\Gamma }}_1$ and $q_Z$ to denote the distribution of Z in ${\mathsf{\Gamma }}_0$. Then, by the forgoing argument, $p_Z\left(1\right)\le q_Z\left(1\right)+8(q_2+1)\sqrt{2{\mathsf{\Gamma }}_f/2^n}.$ Then, by Theorem 2, $q_Z\left(1\right)\le 2^{-n+1}+16{(q+1)}^3{\mathsf{\Gamma }}_f/2^n.$ The result follows. □

The above theorem can be extended to the vector case, where $M_{xw},U_t$ are replaced with several $M_{x_i{w}_i},U_{t_i}$ at location $i.$ Then, we switch $U_{t_i}$ with each ${\mathbf{CStO}}_s$ after $t_i$ is measured, as in the above theorem. Denote the number of this kind of ${\mathbf{CStO}}_s$ (that is either a random oracle query or PointReg1 query) by $q_{2i}$. Then, $q_{2i}<q$. For each i, we obtain the similar bound as the above theorem. Summarizing the argument for $i=1,\cdots ,\ell$, the extension of the first claim can be obtained. The extension of the second claim is very similar to the second claim of the above theorem.

Corollary 2.

Let q be the total number of random oracle queries or PointReg1 queries and ${\mathsf{\Xi }}_1\subseteq \mathsf{\Xi }$. If $(\mathbf{x},\mathbf{t},\mathbf{h},\widehat{\mathbf{x}})$ with vector length ℓ is the vector corresponding to $(x,t,h,\widehat{x})$ in Theorem 3, then

$$\begin{array}{cc}\hfill & \Delta ({(\mathbf{t},\mathbf{x},\mathbf{h},W,\mathsf{abort}=0)}_{{\mathsf{\Gamma }}_0},{(\mathbf{t},\mathbf{x},\mathbf{h},W,\mathsf{abort}=0)}_{{\mathsf{\Gamma }}_1})\le 8(q+\ell )\ell \sqrt{2{\mathsf{\Gamma }}_f/2^n}\hfill \\ \hfill & Pr(\exists i:x_i\ne {\widehat{x}}_i\wedge f(x_i,h_i)=t_i\wedge \mathsf{abort}=0)\le 8(q+\ell )\ell \sqrt{{\displaystyle \frac{2{\mathsf{\Gamma }}_f}{2^n}}}+{\displaystyle \frac{2\ell }{2^n}}+{\displaystyle \frac{16{(q+\ell )}^3{\mathsf{\Gamma }}_f}{2^n}}.\hfill \end{array}$$

(26)

Remark 6.

Theorem 3 requires ${\mathsf{\Xi }}_1\subset \mathsf{\Xi }$. If this is not satisfied, then the proof cannot get through. However, this condition is only used in the PointReg1 query to guarantee that $f(x,r)\ne t$. Since r is taken uniformly and randomly after x is fixed, this condition holds for $2^n-{\mathsf{\Gamma }}_t$ choices of $r.$ If there are at most $q_s$ PointReg1 queries, this holds for every PointReg1 query with a probability of at least $1-q_s{\mathsf{\Gamma }}_t/2^n.$ When this holds, the proof of Theorem 3 remains valid. Furthermore, this argument extends to the vector case in Corollary 2 with further observation that Equation (26) holds with q replaced by $q-q_s$, as that is the bound from the number of the random oracle queries. Notice that ${\mathsf{\Gamma }}_t/2^n<8\ell \sqrt{2{\mathsf{\Gamma }}_t/2^n}.$ Hence, with this tighter analysis, we have the following corollary that preserves the same bound.

Corollary 3.

Let q be the number of random oracle queries or PointReg1 queries. $(\mathbf{x},\mathbf{t},\mathbf{h},\widehat{\mathbf{x}})$ with vector length ℓ is the vector corresponding to $(x,t,h,\widehat{x})$ in Theorem 3. Let $\mathcal{A}$ be a quantum algorithm with access to ${\mathbf{CStO}}_s$ with at most $q_s$ PointReg1 queries. Then,

$$\begin{array}{cc}\hfill & \Delta ({(\mathbf{t},\mathbf{x},\mathbf{h},W,\mathsf{abort}=0)}_{{\mathsf{\Gamma }}_0},{(\mathbf{t},\mathbf{x},\mathbf{h},W,\mathsf{abort}=0)}_{{\mathsf{\Gamma }}_1})\le 8(q+\ell )\ell \sqrt{2{\mathsf{\Gamma }}_f/2^n},\hfill \\ \hfill & Pr(\exists i:x_i\ne {\widehat{x}}_i\wedge f(x_i,h_i)=t_i\wedge \mathsf{abort}=0)\le 8(q+\ell )\ell \sqrt{{\displaystyle \frac{2{\mathsf{\Gamma }}_f}{2^n}}}+{\displaystyle \frac{\ell }{2^{n-1}}}+{\displaystyle \frac{16{(q+\ell )}^3{\mathsf{\Gamma }}_f}{2^n}}.\hfill \end{array}$$

7. Extracting Queries to $\mathbf{CStO}$ That Witness the Future Adversarial Output

7.1. Motivation

In the last section, we have learned how to extract a query for a given commitment on the fly. However, how can we achieve an early extraction for the future output (i.e., no commitment is given at the time of extraction)? For example, in the multi-signature security model, an adversary will finally make a forgery with respect to a set of public keys. However, this set of public keys (say, $PK$) will be revealed only at the end of the game when the attacker shows its forgery. We can not guess attackers’ public keys, as they are completely created by himself. In this case, if the attacker has queried $PK$ to a random oracle, then in the classical setting, we can guess which query is $PK$ while in the quantum setting, this is not clear how to guess because the query might be in a superposition. Liu and Zhandry [33] developed a random experiment by measuring a random query to give $PK$ as a special point and showed that it matches the final output with good probability. In the following, we will extend their technique to the setting of multiple special points.

7.2. Random Experiment

In the above motivation, we consider the extraction of $PK$ for a multi-signature forgery. In general, we want to extract an adversarial query that matches the adversary’s final output which is unknown at the time of the extraction. This extraction technique is very useful in a security proof when the final adversary output is the final solution of the attack, while the query input to be extracted is a certain witness of this solution. In the following, we extend their technique to the setting of multiple extractions (but still interacting with $\mathbf{CStO}$). This modified game can be used to extract multiple queries that are collectively used to derive a witness for the final adversary output. This game can be easily converted to one where the random oracle is ${\mathbf{CStO}}_s$, and so our extraction theorems in the previous sections can be used.

Assume that adversary $\mathcal{A}$ makes at most q oracle queries to $\mathbf{CStO}$ oracle. In the end, we measure the adversary–oracle joint state and obtain $(w,\mathbf{y})$ so that D has the collapsed state $F_D{|\mathbf{y}\rangle }_D$ (i.e., measuring the final state on D using ${\left\{F_D\right|\mathbf{y}\rangle }_{\mathbf{D}}{\}}_{\mathbf{y}}$ basis). Let ${\lambda }_{w,\mathbf{y}}$ denote the probability of outcome $(w,\mathbf{y}).$ We define game ${\mathsf{Exp}}_{i,j,k}$ (with either $i=j=k$ or $i<j<k$ for $i,j,k\in \left[q\right]$). Before this, we define $\underline{x}$ as an equivalence class (which is a subset of $\mathcal{X}$, including x and also determined by x) in the sense that $\underline{x}=\underline{u}$ for any $u\in \underline{x}.$ We assume that the cardinality of $\underline{x}$ is polynomially bounded. For $\mathbf{y}\in {\mathcal{Y}}^{\mathcal{X}}$, $\mathbf{y}\left(\underline{x}\right)=\overrightarrow{\perp }$ means that $y_u=\perp$ for $\forall u\in \underline{x}.$

${\mathsf{Exp}}_{i,i,i}$: In this game, it proceeds normally until the ith oracle query. Assume the attacker–oracle state is ${\sum }_{xuz\mathbf{y}}{\alpha }_{xuz\mathbf{y}}|x,{\varphi }_u,z,\mathbf{y}\rangle ,$ where we recall that Y register is represented using Fourier basis ${\left\{{\varphi }_u\right\}}_{u\in \mathcal{Y}}$. Then, we measure the query input with outcome ${\underline{x}}^{\ast }$, which can be done we follows: let $\mathsf{rep}\left(\underline{x}\right)\in \mathcal{X}$ be the representative of $\underline{x}$, and assume that it can be efficiently computed from any $u\in \underline{x}$; let $U_C$ be a unitary with ${|x\rangle }_X{|0\rangle }_C\mapsto |x\rangle |\mathsf{rep}\left(\underline{x}\right)\rangle$; measuring register C in the computational basis gives $\mathsf{rep}\left(\underline{x}\right)$.

We further measure to test (by two measurements) whether it holds: $D\left({\underline{x}}^{\ast }\right)=\overrightarrow{\perp }$ before the oracle query (which can be done as follows: $D\left({\underline{x}}^{\ast }\right)=\overrightarrow{\perp }$ can be tested by a projective measurement ${\mathsf{\Pi }}_{\perp }=({\mathsf{\Pi }}_{\perp }^0,I-{\mathsf{\Pi }}_{\perp }^0)$ with ${\mathsf{\Pi }}_{\perp }^0={\sum }_{\mathbf{y}:\mathbf{y}\left({\underline{x}}^{\ast }\right)=\overrightarrow{\perp }}|\mathbf{y}\rangle \langle \mathbf{y}|$, which can be implemented by writing bit $\mathbf{y}\left({\underline{x}}^{\ast }\right)==\overrightarrow{\perp }$ onto a new register and measuring it) but $D\left({\underline{x}}^{\ast }\right)\ne \overrightarrow{\perp }$ after the oracle query (which can be done as follows: if $D\left(x^{\prime }\right)=\perp$ before the oracle query, then it remains $D\left(x^{\prime }\right)=\perp$ after the oracle query (i.e., after applying $CStO$) if and only if Y register is currently $|{\varphi }_0\rangle$. Thus, to test if $D\left(x^{\prime }\right)=\perp$ after the oracle query, we can simply apply the unitary $|{\varphi }_y{\rangle }_Y{|0\rangle }_Q\mapsto |{\varphi }_y{\rangle }_Y{|y\rangle }_Q$ and measure if Q register has 0. That is, we can make the test without applying the $CStO$ operation). If both test measurements succeed, then the resulting state before applying $CStO$ oracle will be

$$\begin{array}{c}\hfill \sum _{x^{\prime }uz\mathbf{y}:y_{x^{\prime }}=\perp ,u\ne 0,x^{\prime }\in {\underline{x}}^{\ast }}{\alpha }_{x^{\prime }uz\mathbf{y}}|x^{\prime },{\varphi }_u,z,\mathbf{y}\rangle ,\end{array}$$

(27)

where the case $u=0$ is removed because these components will still have $D\left({\underline{x}}^{\ast }\right)=\perp$ after the $CStO$ query. In this case, the state after the $CStO$ query will become

$$\begin{array}{c}\hfill \sum _{x^{\prime }uz\mathbf{y}:y_{x^{\prime }}=\perp ,u\ne 0,x^{\prime }\in {\underline{x}}^{\ast }}{\alpha }_{x^{\prime }uz\mathbf{y}}|x^{\prime },{\varphi }_u,z\rangle {\displaystyle \frac{1}{\sqrt{2^n}}}\sum _{y\in \mathcal{Y}}{(-1)}^{u·y}|\mathbf{y}\cup {\left(y\right)}_{x^{\prime }}\rangle .\end{array}$$

(28)

Then, the game proceeds normally. If one or both measurements fails, the game aborts.

${\mathsf{Exp}}_{i,j,k}$ with $i<j<k$: In this game, it proceeds normally until the ith oracle query. Let the attacker–oracle state be ${\sum }_{xuz\mathbf{y}}{\alpha }_{xuz\mathbf{y}}|x,{\varphi }_u,z,\mathbf{y}\rangle .$ Then, we measure the query input to output ${\underline{x}}^{\ast }$ and then measure (similar to that in ${\mathsf{Exp}}_{i,i,i}$) to test whether the followings are satisfied throughout the ith oracle query to the kth oracle query (using the methods mentioned above):

• Right before the ith query, $D\left({\underline{x}}^{\ast }\right)=\overrightarrow{\perp }$; but after it, $D\left({\underline{x}}^{\ast }\right)\ne \overrightarrow{\perp }$.
• After ith query and before the jth query, it remains that $D\left({\underline{x}}^{\ast }\right)\ne \overrightarrow{\perp }$.
• After jth query and before the kth query, $D\left({\underline{x}}^{\ast }\right)=\overrightarrow{\perp }.$
• Right after the kth query, $D\left({\underline{x}}^{\ast }\right)\ne \overrightarrow{\perp }.$

If the test measurement fails, the game aborts; otherwise, it proceeds normally. It should be emphasized that we do not care if $D\left({\underline{x}}^{\ast }\right)=\overrightarrow{\perp }$ after any other query than those listed above.

We remark that ${\mathsf{Exp}}_{i,i,i}$ in fact is a special case of ${\mathsf{Exp}}_{i,j,k}$, with $i=j=k$ as “after ith query and before the j query“ and “after jth query and before the k query” in ${\mathsf{Exp}}_{i,j,k}$ are both null statements in this setting.

Further, although ${\mathsf{Exp}}_{i,j,k}$ is defined in the game between adversary and $\mathbf{CStO}$, by inspecting its definition, we can see that ${\mathsf{Exp}}_{i^{\prime },j^{\prime },k^{\prime }}$ in ${\mathsf{Exp}}_{i,j,k}$ is also well defined (as the conducted measurements are well defined). It is not hard to see that the game ${\mathsf{Exp}}_{i,j,k}$ in ${\mathsf{Exp}}_{i^{\prime },j^{\prime },k^{\prime }}$ and the game ${\mathsf{Exp}}_{i^{\prime },j^{\prime },k^{\prime }}$ in ${\mathsf{Exp}}_{i,j,k}$ are the same. By iteration, we can define ${\mathsf{Exp}}_{i^t,j^t,k^t}$ as game ${\mathsf{Exp}}_{i_t,j_t,k_t}$ in ${\mathsf{Exp}}_{i^{t-1},j^{t-1},k^{t-1}}$, where $v^t$ is the sequence $v_1,\cdots ,v_t.$ Let ${\mathcal{U}}_{IJK}$ be the distribution of $(i,j,k)$ that is uniformly random in $\left\{\right(i,i,i)\mid i\in [q\left]\right\}\cup \left\{\right(i,j,k)\mid 1\le i<j<k\le q\}.$ Furthermore, ${\mathcal{U}}_{IJK}^c$ is the product distribution of ${\mathcal{U}}_{IJK}$ of c copies.

7.3. Extraction Theorem

The following is the main result in this section. This is an extension of Corollary 6 [33] with the proof mainly extending Theorem 9 [33]. It essentially states that if the adversary has a successful probability in the original game, then in the random experiment ${\mathsf{Exp}}_{i^c,j^c,k^c}$ for $\left(i^c,j^c,k^c\right)\leftarrow {\mathcal{U}}_{IJK}^c$, it will have a successful probability that is degraded only by a polynomial fraction. With this result, we can reduce our security analysis to this random experiment. The advantage of this result is that we can set the special points of ${\underline{x}}_{i_j}$ to any value of our choices during the $k_j$ the query because $D({\underline{x}}_{i_j})=\overrightarrow{\perp },$ where $j=1,\cdots ,c$. This is a similar capability in a classical random oracle model. The detailed proof of this theorem can be found in Appendix D.

Theorem 4.

Let $c>0$ be a constant. Take $(i^c,j^c,k^c)\leftarrow {\mathcal{U}}_{IJK}^c$. Let S be a subset of the possible output $(w,\mathbf{y})$ in the game with $CStO$ oracle. Define the measurement $(P_0,P_1)$ with $P_0={\sum }_{(w,\mathbf{y})\in S}|w,\tilde{\mathbf{y}}\rangle \langle w,\tilde{\mathbf{y}}|$ (where we use the basis $F_D|\mathbf{y}\rangle =|\tilde{\mathbf{y}}\rangle$ for the consistency with the measurement at the beginning of this section) and $P_1=I-P_0.$ Let $x_{w,\mathbf{y},t}\in \mathcal{X}$ for $t=1,\cdots ,c$ be representatives for c (possibly repeating) classes, being determined by $(w,\mathbf{y})$ with $\mathbf{y}\left({\underline{x}}_{w,\mathbf{y},t}\right)\ne \perp$. Let λ be the probability in the random game ${\mathsf{Exp}}_{i^c,j^c,k^c}$ that gives ${\underline{x}}_{w,\mathbf{y},t}$ for some $(w,\mathbf{y})\in S$ from the measurement on the $i_t$th oracle query for $t=1,\cdots ,c$, and the final measurement $(P_0,P_1)$ gives outcome 0. Let γ be the probability that the final measurement in the normal game gives outcome 0. Then, $\lambda \ge {\displaystyle \frac{\gamma }{{(q+\left(\genfrac{}{}{0pt}{}{q}{3}\right))}^{3c}}}.$

8. Quantum Security of the JAK Multi-Signature Framework

Jiang et al. [23] proposed a framework that converts a linear ID scheme into a compact multi-sinagure scheme. In this framework, each signer i with public key $p{k}_i$ starts with a commitment $r_i=H_0\left({\mathrm{CMT}}_i\right|p{k}_i)$ to his first ID message ${\mathrm{CMT}}_i$. The aggregated public key is $\overline{pk}={\sum }_i{\lambda }_i•p{k}_i,$ where ${\lambda }_i=H_0(p{k}_i,{\left\{p{k}_j\right\}}_{j=1}^n).$ They proved its security in the classical random oracle model. In that proof, a simulator can extract ${\mathrm{CMT}}_i$ of signer i (played by attacker) by searching through the oracle query history that matches $r_i.$ This strategy cannot be used in the quantum setting, as an attacker might query ${\mathrm{CMT}}_i|p{k}_i$ in a superposition. To resolve this difficulty, we use the extraction technique in Section 6.3 to handle it. Similarly, the proof in the classical random oracle model can detect early, which public key set ${\left\{p{k}_j\right\}}_{j=1}^n$ will be used for the forgery by randomly guessing from all possible queries toward some ${\lambda }_i.$ Again, this guessing cannot be directly used in the quantum setting. To resolve this, we use the technique in Section 7 to handle. This gives an outline of the main technical differences from a classical proof.

This section is planned as follows. We review the multi-signature framework [23] in Section 8.1. Then, we prove its security in the quantum random oracle model in Section 8.2 using the techniques outlined above.

8.1. Review of JAK Mutli-Signature Framework

In this section, we review the multi-signature framework in [23]. Essentially, to generate a multi-signature on message M, each signer signs M by converting a canonical ID scheme but with the same challenge CH (from Fiat–Shamir) and then linearly combines these linear signatures in a compact signature.

Let

$$\mathcal{ID}=({\mathbf{Setup}}_{id},{\mathbf{KeyGen}}_{id},P,V_{\tau },\mathsf{\Theta })$$

be a canonical linear ID with parameter $\tau \in \mathbb{N}$. Let $H_0,H_1$ be two random oracles from ${\{0,1\}}^{\ast }$ to $\mathsf{\Theta }$ with $\mathsf{\Theta }\subseteq \mathcal{R}$, where $\mathcal{R}$ is the ring defined for the linearity property of $\mathcal{ID}$. The JAK multi-signature scheme $\left(\mathbf{Setup},\mathbf{KeyGen},\mathbf{Sign},\mathbf{Verify}\right)$ is as follows.

• Setup. Sample and output $\mathsf{param}\leftarrow {\mathbf{Setup}}_{id}\left(1^{\lambda }\right)$.
• KeyGen. Sample $(pk,sk)\leftarrow {\mathbf{KeyGen}}_{id}\left(\mathsf{param}\right)$; output public key $pk$ and private key $sk$.
• Sign. Assume that signers with public keys ${\left\{p{k}_i\right\}}_{i=1}^t$ want to jointly sign message M. Let ${\lambda }_i=H_0(p{k}_i,PK)$ and $\overline{pk}={\sum }_{i=1}^t{\lambda }_i•p{k}_i$, where $PK=(p{k}_1,\cdots ,p{k}_t).$ They execute the following:
  • R-1. Signer i takes $(s{t}_i,{\mathrm{CMT}}_i)\leftarrow P\left(\mathsf{param}\right)$ and sends $r_i:=H_0\left({\mathrm{CMT}}_i\right|p{k}_i)$ to all signers.
  • R-2. Upon $r_j$ for all j (we do not restrict $j\ne i$ for brevity), signer i sends ${\mathrm{CMT}}_i$ to all signers.
  • R-3. Upon ${\mathrm{CMT}}_j,j=1,\cdots ,t$, signer i checks if $r_j=H_0\left({\mathrm{CMT}}_j\right|p{k}_j)$ for all j. If no, it rejects; otherwise, it computes $\overline{\mathrm{CMT}}={\sum }_{j=1}^t{\lambda }_j•{\mathrm{CMT}}_j$, $\mathrm{CH}=H_1(\overline{pk}|\overline{\mathrm{CMT}}\left|M\right)$ and ${\mathrm{Rsp}}_i=P(s{t}_i|s{k}_i|p{k}_i,\mathrm{CH})$. Finally, it sends ${\mathrm{Rsp}}_i$ to all signers.
  • Output. Upon ${\mathrm{Rsp}}_j,j=1,\cdots ,t$, signer i computes $\overline{\mathrm{Rsp}}={\sum }_{j=1}^t{\lambda }_j•{\mathrm{Rsp}}_j$ and outputs the aggregated public key $\overline{pk}|t$ and multi-signature $\overline{\mathrm{CMT}}|\overline{\mathrm{Rsp}}$.
• Verify. Upon signature $(\overline{\mathrm{CMT}},\overline{\mathrm{Rsp}})$ on message M with the aggregated public key $\overline{pk}|t$, it outputs $V_t(\overline{pk},\overline{\mathrm{CMT}}\left|\mathrm{CH}\right|\overline{\mathrm{Rsp}})$, where $\mathrm{CH}=H_1(\overline{pk}|\overline{\mathrm{CMT}}\left|M\right).$

8.2. Security Theorem

In this section, we prove the security of the JAK framework in the quantum random oracle model. Our proof strategy is to use the sequence of game techniques. We first replace two random oracles $|H_0\rangle$ and $|H_1\rangle$ with a single oracle $|H\rangle$ so that $H\left(0\right|x)=H_0\left(x\right)$ and $H\left(1\right|x)=H_1\left(x\right).$ Since the distributions of $H\left(b\right|x)$ and $H_b\left(x\right)$ are identical, the adversary success does not decrease. Then, we replace $|H\rangle$ by $\mathbf{CStO}$, and this will not change the adversary success by Fact 1 and Lemma 8. Next, we sample experiment ${\mathbf{Exp}}_{i^2,j^2,k^2}$ so that the $i_1$th query has measurement outcome ${\underline{x}}_1^{\ast }$ with $x_1^{\ast }=0\left|p{k}_1^{\prime }\right|P{K}^{\prime }$, where $P{K}^{\prime }$ is the signature group in the attacker’s forgery, and the measurement outcome for the $i_2$th query is ${\underline{x}}_2^{\ast }$, with $x_2^{\ast }=1\overline{p{k}^{\prime }}|\overline{{\mathrm{CMT}}^{\prime }}|M$ being the attacker’s input to compute ${\mathrm{CH}}^{\prime }$ in its forgery. By Theorem 4, the adversary success in this experiment is degraded only by a polynomial fraction. Then, we consider the signing oracle in ${\mathbf{Exp}}_{i^2,j^2,k^2}$. We will try to confirm (by measurement) that the query input $x=1|\overline{pk}\left|\overline{\mathrm{CMT}}\right|M$ to compute $\mathrm{CH}$ is not recorded in $\mathbf{CStO}$ (so that we can set this $\mathrm{CH}$ by ourselves). Since $\overline{\mathrm{CMT}}$ contains the challenger’s committing message (that has super-logarithmic min-entropy), this confirmation measurement will succeed with high probability (Lemma 10). Then, we reformulate ${\mathbf{Exp}}_{i^2,j^2,k^2}$ as the game with ${\mathbf{CStO}}^{\prime }$. The format of ${\mathbf{Exp}}_{i^2,j^2,k^2}$ is very compatible with ${\mathbf{CStO}}^{\prime }$, and so this switch is just a simple formatting problem. Then, we further change to a game with ${\mathbf{CStO}}_s$, and by Lemma 9, the adversary success probability will not change. Now, under the game with ${\mathbf{CStO}}_s$, we can use the extraction technique to extract the committing messages from adversary in a signing oracle and treat $x=1|\overline{pk}\left|\overline{\mathrm{CMT}}\right|M$ as a special point. We also treat ${\underline{x}}_1^{\ast },{\underline{x}}_2^{\ast }$ as special points. We can set the random oracle value of these special points by ourselves. With this benefit, we use the ID simulator to simulate the honest signer’s messages in a signing oracle without its secret. Finally, we can reduce the adversary success to break the ID scheme by setting the CH in the attacker’s forgery as the challenge from the ID challenger. So, the attacker’s forgery will help us to break the ID security.

Theorem 5.

Assume that $h\leftarrow \mathsf{\Theta }$ is invertible in $\mathcal{R}$ with probability $1-\mathsf{negl}\left(\lambda \right)$. Let $\mathcal{ID}=({\mathbf{Setup}}_{id},{\mathbf{KeyGen}}_{id},P,V_{\tau })$ be a secure ID scheme with linearity and simulability. Then, the JAK multi-signature scheme is EU-CMA-secure in the quantum random oracle model.

Proof. 

Our proof follows the sequence of game strategy. The game consists of quantum polynomial time adversary $\mathcal{D}$ and a challenger $\mathcal{C}$ who maintains the quantum random oracle and the signing oracle that jointly signs a message M with $\mathcal{D}.$ We use $\mathsf{Succ}\left(\mathbf{G}\right)$ to denote the adversary success probability in game $\mathbf{G}.$

• Game ${\mathbf{G}}_0.$ This is the real forgery game. The challenger runs Setup $\left(1^{\lambda }\right)$ to generate $\mathsf{param}$ and executes $\mathbf{KeyGen}\left(\mathsf{param}\right)$ to generate a challenge key pair $(p{k}^{\ast },s{k}^{\ast })$. Then, it provides $(p{k}^{\ast },\mathsf{param})$ to $\mathcal{D}$ and maintains two quantum random oracles $|H_0\rangle ,|H_1\rangle$ and signing oracle ${\mathcal{O}}_s$ to interact with $\mathcal{D}$. Finally, $\mathcal{D}$ outputs a forgery $({\sigma }^{\ast },M^{\ast })$ with a set of public keys $(p{k}_1^{\ast },\cdots ,p{k}_N^{\ast })$, where $p{k}^{\ast }=p{k}_1^{\ast }.$ He succeeds if $\mathsf{Verify}(\overline{p{k}^{\ast }},{\sigma }^{\ast },M^{\ast })=1$ and no query $(p{k}_1^{\ast },\cdots ,p{k}_N^{\ast },M^{\ast })$ was issued to ${\mathcal{O}}_s.$
• Game ${\mathbf{G}}_1.$ We modify ${\mathbf{G}}_0$ to ${\mathbf{G}}_1$ so that $H_0\left(x\right)=H\left(0\right|x)$ and $H_1\left(x\right)=H\left(1\right|x)$ for a random oracle $H.$ This does not reduce the adversary success probability, as the tables for $H\left(0\right|·),H(1|·)$ and the tables for $H_0(·),H_1(·)$ are jointly identically distributed (i.e., purely random in both cases). Any query $|\psi \rangle$ to $H_b(·)$ is a special case of query $|b\rangle |\psi \rangle$ to $|H\rangle$. Thus, $Pr(\mathbf{Succ}\left({\mathbf{G}}_1\right)\ge Pr\left(\mathbf{Succ}\left({\mathbf{G}}_0\right)\right)$.
• Game ${\mathbf{G}}_2.$ We modify ${\mathbf{G}}_1$ to ${\mathbf{G}}_2$ so that the random oracle is implemented using $\mathbf{CStO}.$ By Fact 1 and Lemma 8, the success probabilities of $\mathcal{D}$ in ${\mathbf{G}}_1$ and ${\mathbf{G}}_2$ are identical.
• Game ${\mathbf{G}}_3.$ We modify ${\mathbf{G}}_2$ to ${\mathbf{G}}_3$ so that it selects the game (involving $\mathcal{D}$) ${\mathbf{Exp}}_{i^2,j^2,k^2}$ for $(i^2,j^2,k^2)\leftarrow {\mathcal{U}}_{IJK}^2$. Let the measurement at the $i_t$th oracle query be ${\underline{x}}_t^{\ast }$ for some $x_t^{\ast }$ for $t=1,2.$ At the end of the game, let $(w,\mathbf{y})$ be the measurement output, where w is the forgery $(\alpha ,\beta ,P{K}^{\prime },M)$ measured by $\mathcal{D}$ on register $XYW$, and $\mathbf{y}$ is the measurement outcome on D (which represents the quantum state $F_D{|\mathbf{y}\rangle }_D$, and hence, $\mathbf{y}$ satisfies $y_x=RO\left(x\right)$). Define $x_{w,\mathbf{y},1}=0\left|p{k}_1^{\prime }\right|P{K}^{\prime }$ for $P{K}^{\prime }=(p{k}_1^{\prime },\cdots ,p{k}_n^{\prime })$. Furthermore, define ${\underline{x}}_{w,\mathbf{y},1}=\left\{0\right|p{k}_v^{\prime }|P{K}^{\prime }:v=1,\cdots ,n\}$ and $\underline{x}=\left\{x\right\}$ (for any x that cannot be written in $0|p{k}_v|PK$ with $p{k}_v\in PK$). Hence, the equivalence class is well defined. In addition, define $x_{w,\mathbf{y},2}=1|\overline{p{k}^{\prime }}\left|\alpha \right|M$. We consider the case $x_t^{\ast }=x_{w,\mathbf{y},t}$ for $t=1,2$. Define S in Theorem 4 as the set of all pairs $(w,\mathbf{y})$ so that w is a valid forgery under random oracle assignments $y_x=RO\left(x\right)$. Since the probability $(w,\mathbf{y})\in S$ is the success probability of $\mathcal{D}$ in ${\mathbf{G}}_2$, by Theorem 4, the success probability of $\mathcal{D}$ in ${\mathbf{G}}_3$ will be at least ${\displaystyle \frac{ϵ}{{(q+\left(\genfrac{}{}{0pt}{}{q}{3}\right))}^6}}.$
• Game ${\mathbf{G}}_4.$ We modify ${\mathbf{G}}_3$ to ${\mathbf{G}}_4$ so that in the signing oracle, right before the classical oracle query $x=1|\overline{pk}\left|\overline{\mathrm{CMT}}\right|M$ to generate $\mathrm{CH},$ it does a measurement $\left(\right|\perp \rangle \langle \perp |,I-|\perp \rangle \langle \perp \left|\right)$ to the register $D_x$ of the oracle. If it gives the outcome 1, it aborts with $\mathsf{Fail}$ (indicating the failure of the simulation); otherwise, it continues normally. By Lemma 10, this Fail occurs only with a negligible probability (recall that $H_{\infty }\left(\mathrm{CMT}\right)$ is super-logarithmic for randomly generated $\mathrm{CMT}$), and hence, the success probability $\mathcal{D}$ in G₄ is at least ${\displaystyle \frac{ϵ}{{(q+\left(\genfrac{}{}{0pt}{}{q}{3}\right))}^6}}-\mathbf{negl}\left(\kappa \right)$
• Game ${\mathbf{G}}_5.$ We reformat ${\mathbf{G}}_4$ as a game between an adversary $\mathcal{D}$ and challenger ${\mathcal{C}}^{\prime }$ that has oracle access to ${\mathbf{CStO}}^{\prime }$ (ref. Section 4.3) so that $\mathcal{D}$ in ${\mathbf{G}}_5$ has the success probability exactly identical to that of $\mathcal{D}$ in ${\mathbf{G}}_4.$ The code of ${\mathcal{C}}^{\prime }$ as follows. It follows $\mathcal{C}$ to set up ${\mathbf{G}}_4$ to invoke $\mathcal{D}$ with the public parameters and then interacts with $\mathcal{D}$. ${\mathcal{C}}^{\prime }$ also follows $\mathcal{C}$ to choose the random game ${\mathbf{Exp}}_{i^2,j^2,k^2}$:
  • Whenever a random oracle query is issued, ${\mathcal{C}}^{\prime }$ does as follows. Assume that this is the ℓth random oracle query. If $\ell =i_1$ or $i_2$, then ${\mathcal{C}}^{\prime }$ (like challenger $\mathcal{C}$ in ${\mathbf{G}}_4$) will apply a projective measurement on X register in the computational basis and results in ${\underline{x}}_1^{\ast }$ or ${\underline{x}}_2^{\ast }$, and then it issues a PointReg0 query with each $x\in {\underline{x}}_1^{\ast }$ or ${\underline{x}}_2^{\ast }$ to ${\mathbf{CStO}}^{\prime }$. If $\ell =k_t$ (for $t=1$ or 2), it issues a $PointReg1$ query with $x^{\prime }\in {\underline{x}}_t^{\ast }$ (which does measurement $\mathsf{\Pi }$ on $D_{x^{\prime }}$ like challenger in ${\mathsf{\Gamma }}_4$). Then (no matter what is ℓ), recall that, in ${\mathbf{G}}_4$, the challenger will conduct a projective measurement ${\mathsf{\Lambda }}^{\prime }$ (determined by ℓ and $i_1,j_1,k_1$) on D and another projective measurement ${\mathsf{\Lambda }}^{″}$ (still determined by $\ell ,i_2,j_2,k_2)$ on D. These measurements are described in ${\mathbf{Exp}}_{i^2,j^2,k^2}$, and it can be seen that they are only applied on $D_{{\mathsf{\Xi }}_0}$ as desired by ${\mathbf{CStO}}^{\prime }$. These two measurements can be combined into one projective measurement ${\mathsf{\Lambda }}_{\ell }=({\mathsf{\Lambda }}_{\ell 0},I-{\mathsf{\Lambda }}_{\ell 0})$ in the computational basis on $D_{{\mathsf{\Xi }}_0}$. Then, to be consistent with ${\mathbf{G}}_4$, ${\mathcal{D}}^{\prime }$ in ${\mathbf{G}}_5$ issues the random oracle query with its register $XY$ to ${\mathbf{CStO}}^{\prime }$, which will handle it first with measurement ${\mathsf{\Lambda }}_{\ell }$ and then with $CStO$ (if it does not abort). Under this reformatting, the action on the joint state is the same as in ${\mathbf{G}}_4$.
  • When $\mathcal{D}$ issues a signing query $(PK,M)$ so that $PK$ contains $p{k}_1^{\ast }$, ${\mathcal{C}}^{\prime }$ in G₅ computes $\overline{pk}$, $\overline{\mathrm{CMT}}$, and $x=1|\overline{pk}\left|\overline{\mathrm{CMT}}\right|M$ normally as in ${\mathbf{G}}_4$, with possibly random oracle access to ${\mathbf{CStO}}^{\prime }$ as in the previous item. Next, it issues $PointReg0$ query, then $PointReg1$ query both with x to ${\mathbf{CStO}}^{\prime }$, and finally a classical random oracle query with x (if it does not abort), where the random oracle queries are handled as the above reformatting. In turn, if ${\mathbf{CStO}}^{\prime }$ does not abort, ${\mathcal{C}}^{\prime }$ receives the reply $y=RO\left(x\right)$, and it continues normally as in ${\mathbf{G}}_4$ to generate the signature. Note that ${\mathcal{C}}^{\prime }$, together with ${\mathbf{CStO}}^{\prime }$, acts the same as $\mathcal{C}$ together with $\mathbf{CStO}$ in ${\mathbf{G}}_4$. Thus, this does not change the view of $\mathcal{D}$ and the joint quantum state.
  From our description, we can see that $\mathcal{D}$ in ${\mathbf{G}}_4$ and ${\mathbf{G}}_5$ have the same view, as this is just a reformatting of ${\mathbf{G}}_4$. Hence, $\mathcal{D}$ in ${\mathbf{G}}_5$ has the same success probability as in ${\mathbf{G}}_4.$
• Game ${\mathbf{G}}_6.$ We modify ${\mathbf{G}}_5$ to ${\mathbf{G}}_6$ s.t. ${\mathbf{CStO}}^{\prime }$ is replaced by ${\mathbf{CStO}}_s$. By Lemma 9, the success probability of $\mathcal{D}$ in ${\mathbf{G}}_6$ is the same as in ${\mathbf{G}}_5$ by checking the output of ${\mathcal{C}}^{\prime }$, which is defined as 1 if and only if $\mathcal{D}$ succeeds ($\neg \mathbf{abort}$ can be removed in the lemma, as ${\mathcal{C}}^{\prime }$ outputting 1 indicates $\neg \mathbf{abort}=1$).
• Game ${\mathbf{G}}_7.$ We modify ${\mathbf{G}}_6$ to ${\mathbf{G}}_7$ so that ${\mathbf{CStO}}_s$ is now simulated by $\mathcal{S}$. Since $\mathcal{S}.E$ is not used, the adversary success probability is identical to ${\mathbf{G}}_6.$
• Game ${\mathbf{G}}_8.$ We modify ${\mathbf{G}}_7$ to ${\mathbf{G}}_8$ so that in the signing query $O_s(p{k}_1,\cdots ,p{k}_n,M)$, after receiving $r_i$, challenger extracts ${\mathrm{CMT}}_i^{\prime }=\mathcal{S}.E\left(r_i\right)$ and later in round R-3, when it receives ${\mathrm{CMT}}_i$; if ${\mathrm{CMT}}_i\ne {\mathrm{CMT}}_i^{\prime }$ but $\mathcal{S}.RO\left({\mathrm{CMT}}_i\right)=r_i$, it terminates with Fail. By Corollary 2, this occurs negligibly. Thus, the success probability of $\mathcal{D}$ in ${\mathbf{G}}_8$ is negligibly close to that in ${\mathbf{G}}_7.$
• Game ${\mathbf{G}}_9.$ We modify ${\mathbf{G}}_8$ to ${\mathbf{G}}_9$ so that in $O_s(p{k}_1,\cdots ,p{k}_n,M)$ with $p{k}_t=p{k}^{\ast }$ for some t, it generates $({\mathrm{CMT}}_t,{\mathrm{Rsp}}_t)\leftarrow \mathbf{SIM}(\mathrm{CH},p{k}^{\ast },\mathsf{param})$, where $\mathrm{CH}\leftarrow \mathsf{\Theta }$. It does the same as ${\mathbf{G}}_8$: measures $\left(\right|\perp \rangle \langle \perp |,I-|\perp \rangle \langle \perp \left|\right)$ on $D_x$ (specified since ${\mathbf{G}}_4$), issues a $PointReg0$ query, and then $PointReg1$ queries with $x=1|\overline{pk}\left|\overline{\mathrm{CMT}}\right|M$ to CStO_s, where $PointReg1$ will define r in ${\mathbf{CStO}}_s$ for $D_x$ (if it does not abort) as the random oracle value for x. In ${\mathbf{G}}_9$, it defines this r as $\mathrm{CH}$. By the simulability of ID, this has the same distribution as ${\mathbf{G}}_8$. So, the adversary success probability remains the same as in ${\mathbf{G}}_8$ (specifically, any non-negligible difference in this success probability can be straightforwardly reduced through hybrid argument on $({\mathrm{CMT}}_t,{\mathrm{Rsp}}_t,{\mathrm{CH}}_t)$ in the signing queries to break the ID simulability; the details are omitted). We recall that the secret key $sk$ is no longer used in ${\mathbf{G}}_9$.
• Game ${\mathbf{G}}_{10}.$ We modify ${\mathbf{G}}_9$ to ${\mathbf{G}}_{10}$ so that it will embed the ID challenge into the attack. Specially, ${\mathcal{C}}^{\prime }$ sets up the game so that $p{k}_1^{\ast }$ is the ID challenge key. In addition, after obtaining ${\underline{x}}_1^{\ast }$ (by measuring the $i_1$th random oracle query) with $x_1^{\ast }=1\left|p{k}_1^{\ast }\right|\{p{k}_1^{\ast },\cdots ,p{k}_n^{\ast }\}$, it sends $p{k}_2^{\ast },\cdots ,p{k}_n^{\ast }$ as its response of group keys to its own ID challenger and in turn will receive ${\lambda }_1,\cdots ,{\lambda }_n$. Upon $PointReg1$ queries $x_u\in {\underline{x}}_1^{\ast }$ (from ${\mathcal{C}}^{\prime }$), ${\mathbf{CStO}}_s$ sets its random oracle value (recall that in ${\mathbf{G}}_5$–${\mathbf{G}}_9$, the PointReg1 query for $x\in {\underline{x}}_1^{\ast }$ occurs when $\mathcal{D}$ issues the $k_1$th random oracle query, where the test measurement $\mathsf{\Pi }$ has the outcome ${|\perp \rangle }_{D_x}$ as it does not abort, and hence $D\left(x\right)=\perp$) $\mathcal{S}.RO\left(x_u\right)$ as ${\lambda }_u$ ($u=1,\cdots ,n$), which is provided by the ID challenger. In addition, later for $x_2^{\ast }=1|\overline{p{k}^{\prime }}\left|\alpha \right|M$, in $PointReg1$ query $x_2^{\ast }$, it sets the hash value $r=\mathrm{CH}$, which is provided by the ID challenger. This will not change the distribution of the game, because ${\lambda }_u$ for any u, and these $\mathrm{CH}$ are all uniformly random, remaining as the same distribution as in ${\mathbf{G}}_9$. When $\mathcal{D}$ outputs its forgery, if the output $(\mathbf{w},\mathbf{y})\in S$, then it sends the response $\mathrm{Rsp}$ in w to the ID challenger as its response. Obviously, ${\mathcal{C}}^{\prime }$ succeeds in its ID challenge session if and only if $\mathcal{D}$ succeeds with $(w,\mathbf{y})\in S$ (that is, the forgery is valid). Thus, the adversary success probability is the same as in ${\mathbf{G}}_9$, and hence, ${\mathcal{C}}^{\prime }$ has a success probability negligibly close to ${\displaystyle \frac{ϵ}{{(q+\left(\genfrac{}{}{0pt}{}{q}{3}\right))}^6}}$. This contradicts the security of the ID scheme. □

Remark 7.

In ${\mathbf{G}}_5$, we convert the game with $\mathbf{CStO}$ to the game with ${\mathbf{CStO}}^{\prime }$, where we register ${\underline{x}}_t^{\ast }$ to ${\mathsf{\Xi }}_0$ at the $i_t$th oracle random oracle query, while it registers to ${\mathsf{\Xi }}_1$ only at the $k_t$th random oracle query. This generally is the routine to convert ${\mathbf{Exp}}_{i^c,j^c,k^c}$ to a game with ${\mathbf{CStO}}^{\prime }$. One might wonder why we register ${\underline{x}}_t^{\ast }$ twice. The issue in fact comes from the switch from ${\mathbf{CStO}}^{\prime }$ to ${\mathbf{CStO}}_s$ in ${\mathbf{G}}_6$. CStO_s requires that after registration in ${\mathsf{\Xi }}_1$, no measurement for testing $D\left(x\right)=\perp$ will be performed. If we register it once, this should happen at the $i_t$th query for ${\underline{x}}_t^{\ast }$. But in this case, we cannot guarantee that ${\mathbf{G}}_5$ (with ${\mathbf{CStO}}^{\prime }$) will be indistinguishably switched to ${\mathbf{G}}_6$ with ${\mathbf{CStO}}_s$: after the $i_t$th query, we still need to measure if $D\left({\underline{x}}_t^{\ast }\right)=\perp$. But in ${\mathbf{G}}_6$, this will never be true, as $|\perp \rangle$ is replaced by $|r\rangle$, while in ${\mathbf{G}}_5$ (with ${\mathbf{CStO}}^{\prime }$), it is still possible. This distinguishing event does not violate Lemma 9, because this test is no longer performed in  CStO_s after updating $|\perp \rangle$ by $|r\rangle .$

9. Quantum Security of the JAK ID Scheme

In this section, we prove the quantum security of the lattice-based ID scheme in [23] (which we call the JAK ID scheme). Together with Theorem 5, it gives a secure lattice-based multi-signature in the quantum random oracle model. We will use the following notations:

• As a convention for lattice over ring, the security parameter is denoted by n (a power of 2);
• q is a prime with $q\equiv 3$ mod 8;
• $R=\mathbb{Z}\left[x\right]/(x^n+1)$; $R_q={\mathbb{Z}}_q\left[x\right]/(x^n+1)$; $R_q^{\ast }$ is the set of invertible elements in $R_q$;
• A vector $\mathbf{w}$ is implicitly a column vector, and the ith component is $w_i$ or $\mathbf{w}\left[i\right]$;
• for a matrix or vector X, $X^T$ is its transpose;
• $\mathbf{1}$ denotes the all one-vector ${(1,\cdots ,1)}^T$ value of a clear dimension only in the specific context;
• For $u={\sum }_{i=0}^{n-1}{u}_i{x}^i\in R$, ${\left|\right|u\left|\right|}_{\infty }={max}_i\left|u_i\right|;$
• $\alpha \in {\mathbb{Z}}_q$ always uses the default representative with $-(q-1)/2\le \alpha \le (q-1)/2$, and similarly, for $u\in R_q$, each coefficient of u by default belongs to this range;
• $e=2.71828\cdots$ is the Euler’s number;
• $\mathcal{C}=\{c\in R\mid |\left|c\right|{|}_{\infty }\le logn,deg\left(c\right)<n/2\}$;
• $\mathcal{Y}=\{y\in R\mid |\left|y\right|{|}_{\infty }\le n^{1.5}\sigma {log}^{3}n\}$;
• $\mathcal{Z}=\{z\in R\mid |\left|z\right|{|}_{\infty }\le (n-1)n^{1/2}\sigma {log}^{3}n\}$.

9.1. Ring-LWE and Ring-SIS

In the following, we introduce the ring-LWE and ring-SIS assumptions (see [39,40,41] for details). For $\sigma >0$, distribution $D_{{\mathbb{Z}}^n,\sigma }$ assigns the probability proportional to $e^{-{\pi \left|\right|\mathbf{y}\left|\right|}^2/{\sigma }^2}$ for any $\mathbf{y}\in {\mathbb{Z}}^n$ and 0 for other cases. As in [42], $y\leftarrow D_{R,\sigma }$ samples $y={\sum }_{i=0}^{n-1}{y}_i{x}^i$ from R by taking $y_i\leftarrow D_{\mathbb{Z},\sigma }.$

The Ring Learning With Error (${\mathrm{Ring-LWE}}_{q,\sigma ,2n}$) problem over R with standard deviation $\sigma$ is defined as follows. Initially, it takes $s\leftarrow D_{R,\sigma }$ as secret. It then takes $a\leftarrow R_q,e\leftarrow D_{R,\sigma }$ and outputs $(a,as+e)$. The problem is to distinguish $(a,as+e)$ from a tuple $(a,b)$ for $a,b\leftarrow R_q.$ The ${\mathsf{Ring}-\mathsf{LWE}}_{q,\sigma ,2n}$ assumption [43,44] is to say that no quantum polynomial time algorithm can solve ${\mathrm{Ring-LWE}}_{q,\sigma ,2n}$ problem with a non-negligible advantage.

The Small Integer Solution problem with parameters $q,m,\beta$ over ring R (${\mathrm{Ring-SIS}}_{q,m,\beta }$) is as follows: given m uniformly random elements $a_1,\cdots ,a_m$ over $R_q$, find $(t_1,\cdots ,t_m)$ so that $\left|\right|t_i{\left|\right|}_{\infty }\le \beta$ and $a_1{t}_1+\cdots +a_m{t}_m=0$. We consider the case $m=3$. We assume that $q=3$ mod 8, in which case, by Theorem 1 [45], $x^n+1={\mathsf{\Phi }}_1\left(x\right){\mathsf{\Phi }}_2\left(x\right)$ for irreducible polynomials ${\mathsf{\Phi }}_1\left(x\right),{\mathsf{\Phi }}_2\left(x\right)$ of degree $n/2$. So by the Chinese remainder theorem, $a_i$ is invertible, except for probability $2q^{-n/2}$. Hence, ring-SIS is equivalent to the case of invertible $a_2$, which is further equivalent to problem $a_1{t}_1+t_2+a_3{t}_3=0$, as we can multiply it by $a_2^{-1}$. The quantum hardness of ring-SIS can be found in [39,46].

9.2. The JAK ID Scheme

We now review the JAK ID scheme [23]. Initially, take $s_1,s_2\leftarrow D_{R,\sigma },a_1,a_2\leftarrow R_q$ and compute $u=a_1{s}_1+a_2{s}_2$. The system parameter is $(a_1,a_2)$; the public key is u and the private key is $(s_1,s_2).$ The ID scheme is as follows (also see Figure 3):

1.

Prover generates ${\mathbf{y}}_1,{\mathbf{y}}_2\leftarrow {\mathcal{Y}}^{\mu }$ and computes $\mathbf{v}=a_1{\mathbf{y}}_1+a_2{\mathbf{y}}_2$; it sends $\mathbf{v}$ to Verifier, where $\mu \ge {log}^{2}n.$

2.

Receiver samples $c\leftarrow \mathcal{C}$ and sends it to Prover.

3.

Upon c, Prover computes $z_1=s_{1}c+{\sum }_j{y}_{1j},z_2=s_{2}c+{\sum }_j{y}_{2j}.$

4.

Upon $z_1,z_2$, Verifier checks if ${\sum }_{i=1}^{\mu }{v}_i\stackrel{?}{=}{a}_1{z}_1+a_2{z}_2-uc$ and $\left|\right|z_b{\left|\right|}_{\infty }\stackrel{?}{\le }{\eta }_t$ for $b=1,2,$ where ${\eta }_t=5\sigma n^2\sqrt{t\mu }{log}^{6}n$, and t is a positive integer (that represents the number of signers when converted to a signature scheme); recall that (as a convention) $v_i$ is the ith component of $\mathbf{v}$. If all are valid, it accepts; otherwise, it rejects.

The above specification uses the public-key $u=a_1{s}_1+a_2{s}_2$, while the original protocol uses $u=a{s}_1+s_2.$ This change is only for convenience for our proof for Lemmas A3 (that is needed for the ID security). It will not affect other properties—correctness, simulatability, linearity, and classical security—as if we define $a=a_1{a}_2^{-1}$ (ignore the negligible probability $2q^{-n/2}$ that $a_2$ is not invertible: recall that $x^n+1={\mathsf{\Phi }}_1\left(x\right){\mathsf{\Phi }}_2\left(x\right)$ and $a_2$ are invertible if and only if they are non-zero modular ${\mathsf{\Phi }}_1,{\mathsf{\Phi }}_2$ both); the current version is different from the original one only by a scaling factor $a_2$ (in $\mathbf{v}$ and u), and all the proofs go through. Furthermore, Step 3 in the above specification is a simplified but equivalent version of the original protocol (see the remark after the scheme description in [23]). The proofs of the correctness and linearity do not involve the adversary and hence remain unchanged, as in [23]. The simulability given in [23] holds statistically. It hence holds against a quantum attacker, where the model is the same except that the attacker can internally run a quantum computer (which can be simulated by unbounded adversary).

It remains to prove the quantum security of this ID scheme under Definition 5. The idea is to implement the classical rewinding technique in the quantum world. We start with the security game below with $u_1$ being the honest signer’s public key. We first make the change that ${\lambda }_2,\cdots ,{\lambda }_t$ are provided by attacker (which will increase the attacker A’s success probability only):

1.

$a_1,a_2\leftarrow \mathbf{Setup}\left(1^{\lambda }\right)$;

2.

$\left(\right|s{t}_0\rangle ,{\lambda }_2,u_2,\cdots ,{\lambda }_t,u_t)\leftarrow A(a_1,a_2,u_1)$;

3.

${\lambda }_1\leftarrow \mathcal{C}$;

4.

$\left(\right|s{t}_1\rangle ,\mathbf{v})\leftarrow A\left(\right|s{t}_0\rangle ,{\lambda }_1)$;

5.

$c\leftarrow \mathcal{C}$; $z_1|z_2\leftarrow A\left(\right|s{t}_1\rangle ,c)$;

6.

Check: ${\sum }_{j=1}^{\mu }{v}_j\stackrel{?}{=}{a}_1{z}_1+a_2{z}_2-\overline{u}c,\left|\right|z_1{\left|\right|}_{\infty }<{\eta }_t,\left|\right|z_2{\left|\right|}_{\infty }<{\eta }_t$?

In the proof in the classical model, we first obtain a transcript $({\left\{{\lambda }_i\right|u_i\}}_{i=2}^t,{\lambda }_1,\mathbf{v},c,z_1|z_2)$ and then rewind A to line 5 and produce another valid transcript $({\left\{{\lambda }_i\right|u_i\}}_{i=2}^t,{\lambda }_1,\mathbf{v},c^{\prime },z_1^{\prime }|z_2^{\prime })$. This allows us to derive a short solution $(o_1,o_2,o_3)=(z_1-z_1^{\prime },z_2-z_2^{\prime },c-c^{\prime })$ for equation $a_1{o}_1+a_2{o}_2-\overline{u}{o}_3=0.$ In the quantum world, this rewinding strategy is not quite working, because when A produces $z_1,z_2$, it might do a measurement that is not reversible. If it only uses unitary (e.g., U), then the rewinding can be done by applying $U^{†}.$ Unruh [34] introduced the notion of the collapsing property for a protocol: even with the measurement, the rewinding still can produce a successful new transcript with a good probability. In our quantum security proof, we will guarantee that this property is satisfied. Next, we rewind A to step 3 with a new challenge ${\lambda }_1^{\prime }$ and repeat the above procedure to obtain a new solution $(o_1^{\prime },o_2^{\prime },o_3^{\prime })$ satisfying $a_1{o}_1^{\prime }+a_2{o}_2^{\prime }-\overline{u^{\prime }}{o}_3^{\prime }=0$, where $\overline{u^{\prime }}$ is updated as $u_1{\lambda }_1^{\prime }+{\sum }_{i=2}^t{\lambda }_i{u}_i.$ Combining these two solutions allows us to derive a short solution $(x_1,x_2,x_3)$ for $a_1{x}_1+a_2{x}_2+u_1{x}_3=0.$ If $u_1$ is uniformly random in $R_q$, this is the solution for Ring-SIS. However, even though $u_1$ is sampled as $a_1{s}_1+a_2{s}_2$, it is indistinguishable from the uniformly random $u_1$ by Ring-LWE assumption. Since the secret $(s_1,s_2)$ is never used in the above game, if we use the uniformly random $u_1$ in the game, we can obtain the solution $(x_1,x_2,x_3)$ with the similar probability. This contradicts the Ring-SIS assumption. The detailed implementation of this strategy is given Appendix A.

Theorem 6.

Under ${\mathit{ring-LWE}}_{q,\sigma ,2n}$ and ${\mathit{ring-SIS}}_{3,q,\beta }$ assumptions, the JAK ID scheme is secure (under Definition 5), where $\beta \ge 16{\eta }_t\sqrt{n}{log}^{2}n$.

Applying the compiler theorem to the JAK ID scheme, it gives a quantum-secure multi-signature scheme (denoted by RLWE-Multisig scheme). For a complete description of this scheme, see [23]. The following is a summary of its security.

Corollary 4.

Under ${\mathit{Ring-LWE}}_{q,\sigma ,2n}$ and ${\mathit{Ring-SIS}}_{3,q,\beta }$ assumptions, RLWE-MultiSig is EU-CMA secure in the quantum random oracle model, where $\beta \ge 16{\eta }_t\sqrt{n}{log}^{2}n$.

10. Conclusions

In this paper, we investigated the security analysis techniques in the quantum random oracle model. We extended Zhandry’s compressed random oracle CStO to a compressed random oracle with adaptive special points (CStO_s). In CStO_s, we can set the random oracle value at the special point to whatever we want, which is well known to be a powerful property in a classical random oracle model. We extended the sampling experiment of Liu and Zhandry that identifies special points in CStO, witnessing the future adversarial output that can be easily converted to a game with CStO_s. We also extended the online query extraction technique of Don et al. [32] from CStO to the CStO_s setting, which allows us to extract the input to any adversarial commitment on the fly, just as we can do in a classical random oracle model. We applied this new random oracle and its extraction techniques to prove the security of our recent compact multi-signature scheme. This gives the first compact multi-signature provable secure in the quantum random oracle model. We believe that this random oracle technique will be useful to prove the post-quantum security of many cryptographic systems. To realize the quantum secure multi-signature framework, we proved the quantum security of the ID scheme in [23]. Our strategy is to derive two public coin protocols from that ID scheme and prove that they are weakly collapsing (in the sense of [33]), as well as iteratively apply Unruh’s quantum rewinding lemma [34] to reduce the security of the ring-SIS problem.

There are several questions deserving further investigations. First, our conversion from the StO and $\mathbf{CStO}$ model to the ${\mathbf{CStO}}_s$ model was through the sampling experiment in the $\mathbf{CStO}$ model. It degrades the adversarial success probability by a factor of order $O\left(q^{-6c}\right)$ (Theorem 4), where q is the number of oracle queries, and c is the number of witness for the final adversarial output. This factor will carry to the overall reduction advantage in a security proof. It is interesting to know if one can find a new method that bridges CStO and ${\mathbf{CStO}}_s$ with a much better factor. It is even more interesting to know if one can find a new random oracle model so that it is much simpler than ${\mathbf{CStO}}_s$, and the transition from $\mathbf{CStO}$ to this model has much less security loss. Second, the proof of JAK ID security has applied Unruh’s lemma twice and results in a successful probability of order $O\left({ϵ}^6\right)$ if the adversary has a success probability $ϵ$ in breaking the original ID scheme. In general, if it applies this lemma k times, then the resulting success probability will reduce to the order of $O\left({ϵ}^{3k}\right).$ An interesting open question is to find a polynomial strategy with a significantly better success probability. Third, the JAK ID scheme needs to combine $\mu =\omega (logn)$ copies of element ID executions. It will be interesting if this $\mu$ can be dramatically reduced.