The random oracle model [BR93] has proven to be a powerful tool for heuristically proving the security of schemes that otherwise lacked a security proof. In the random oracle model (ROM), a hash function H is modeled as a truly random function that can only be evaluated by querying an oracle for H. A scheme is secure in the ROM if it can be proven secure in this setting. Of course, random oracles cannot be efficiently realized; in practice, the random oracle is replaced with a concrete efficient hash function. The hope is that the ROM proof will indicate security in the real world, provided there are no structural weaknesses in the concrete hash function.
Meanwhile, given the looming threat of quantum computers [IBM17], there has been considerable interest in analyzing schemes for so called "post-quantum" security [NIS17, Son14, ATTU16, CBH + 17, YAJ + 17, CDG + 17, CDG + 15]. Many of the proposed schemes are random oracle schemes; Boneh et al. [BDF + 11] argue that the right way of modeling the random oracle in the quantum setting is to use the quantum random oracle model, or QROM. Such a model allows a quantum attacker to query the random oracle on a quantum superposition of inputs. The idea is that a real-world quantum attacker, who knows the code for the concrete hash function, can evaluate the hash function in superposition in order to perform tasks such as Grover search [Gro96] or collision finding [BHT98]. In order to accurately capture such real-world attacks, it is crucial to model the random oracle to allow for such superposition queries. The quantum random oracle model has been used in a variety of subsequent works to prove the post-quantum security of cryptosystems [BDF + 11, Zha12b, Zha15, TU16, Eat17].
The Recording Barrier. Unfortunately, proving security in the quantum random oracle model can be extremely difficult. Indeed, in the classical random oracle model, one can copy down the adversary's queries as a means to learning what points the adversary is interested in. Many classical security proofs crucially use this information in order to construct a new adversary which solves some hard underlying problem, reaching a contradiction. In the quantum setting, such copying is impossible by no-cloning. One can try to record some information about the query, but this amounts to a measurement of the adversary's query state which can be detected by the adversary. A mischievous adversary may refuse to continue if it detects such a measurement, rendering the adversary useless for solving the underlying problem. Because of the difficulty in reading an adversary's query, it also becomes hard to adaptively program the random oracle, another common classical proof technique.
This difficulty has led authors to develop new quantum-sound proof techniques to replace classical techniques, such as Zhandry's small-range distributions [Zha12a] or Targhi and Unruh's extraction technique [TU16]. These proof techniques choose the oracle from a careful distribution that allows for proofs to go through. However, every such proof technique always chooses a classical oracle at the beginning of the experiment, and leave the oracle essentially unchanged through the entire execution. The inability to change the oracle seems inherent, since if the proof gives the adversary different oracles during different queries, this is potentially easily detectable (even by classical adversaries) 1Constraining the oracles to be fixed functions seems to limit what can be proved using such non-recording techniques. For example, Dagdelen, Fischlin, and Gagliardoni [DFG13] show that such natural proof techniques are likely incapable of proving the security of Fiat-Shamir 2 . This leads to a natural question: Is it possible to record information about an adversary's quantum query without the adversary detecting Enter Indifferentiability. The random oracle model (quantum or otherwise) assumes the adversary treats the hash function as a monolithic object. Unfortunately, hash functions in practice are usually built from smaller building blocks, called compression functions. If one is not careful, hash functions built in this way are vulnerable to attacks such as length-extension attacks. Coron et al. [CDMP05] show that a hash function built from a compression function can be as good as a monolithic oracle in many settings if it satisfies a notion of indifferentiability, due to Maurer, Renner, and Holenstein [MRH04]. Roughly, in indifferentiability, an adversary A has oracle access to both h and H, and the adversary is trying to distinguish two possible worlds. In the "real world", h is a random function, and H is built from h according to the hash function construction. In the "ideal world", H is a random function, and h is simulated so as to be consistent with H. A hash function is indifferentiable from a random oracle if no efficient adversary can distinguish the two worlds.
Coron et al.'s proof of indifferentiability for Merkle-Damgard requires the simulator to remember the queries that the adversary has made. This is actually inherent for any domain extender, by a simple counting argument discussed below. In the quantum setting, such recording presents a serious issue, as recording a query is equivalent (from the adversary's point of view) to measuring the query. As any measurement will disturb the quantum system, such measurement may be detectable to the adversary. Note that in the case where A is interacting with a truly random h, there is no measurement happening. Therefore, if such a measurement can be detected, the adversary can distinguish the two cases, breaking indifferentiability.
To illustrate what might go wrong, we will use the simple example from Coron et al. [CDMP05]. Here, we will actually assume access to two independent compression functions h 0 , h 1 : {0, 1} 2n → {0, 1} n . We will define H : {0, 1} 3n → {0, 1} n as H(x, y) = h 1 (h 0 (x), y), where x ∈ {0, 1} 2n , y ∈ {0, 1} n .
To argue that H is indifferentiable from a random oracle, Coron et al. use the following simulator S, which has access to H, and tries to implement the oracles h 0 , h 1 . S works as follows:
-S keeps databases D 0 , D 1 , which will contain tuples (x, y). D b containing (x, y) means that S has set h b (x) = y. -h 0 is implemented on the fly: every query on x looks up (x, y) ∈ D 0 , and returns y if it is found; if no such pair is found, a random y is chosen and returned, and (x, y) is added to D 0 . -By default, h 1 is answered randomly on the fly as in h 0 . However, it needs to make sure that h 1 (h 0 (x), y) always evaluates to H(x, y), else it is trivial to distinguish the two worlds. Therefore, on a query (z, y), h 1 will check if there is a pair (x, z) in D 0 for some x. If so, it will reasonably guess that the adversary is trying to evaluate H(x, y), and respond by making a query to H(x, y). Otherwise it will resort to the default simulation.
Note that by defining the simulator in this way, if the adversary ever tries to evaluate H on (x, z) by first making a query x to h 0 to get y, and then making a query (y, z) to h 1 , the simulator will correctly set the output of h 1 to H(x, z), so that the adversary will get a result that is consistent with H. However, note that it is crucial that S wrote down the queries made to h 0 , or else it will not know which point to query H when simulating h 1 . Now consider a quantum adversary. A quantum query to, say, h 0 will be the following operation:
Now, imagine our simulator trying to answer queries to h 0 in superposition. For simplicity, suppose this is the first query to h 0 , so D 0 is empty. The natural approach is to just have S store its database D 0 in superposition, performing a map that may look like |x, u → |x, u ⊕ y ⊗ |x, y , where y is chosen randomly, and everything to the right of the ⊗ is the simulators state.
But now consider the following query by an adversary. It sets up the uniform superposition x,u |x, u and queries. In the case where h 0 is a classical function, then this state becomes
Namely, the state is unaffected by making the query. In contrast, the simulated query would result in
Here, the adversary's state is now entangled with the simulator's. It is straightforward to detect this entanglement by applying the Quantum Fourier Transform (QFT) to the adversary's x registers, and then measuring the result. In the case where the adversary is interacting with a random h 0 , the QFT will result in a 0. In the simulated case, the QFT will result in a random string. These two cases are therefore easily distinguishable.
To remedy this issue, prior works in the quantum regime have abandoned on-the-fly simulation, instead opting for stateless simulation. Here, the simulator commits to a function to implement the oracle in the very beginning, and then sticks with this implementation throughout the entire experiment. Moreover, the simulator never records any information about the adversary's query, lest the adversary detect the entanglement with the simulator. This will certainly fix the issue above, and by carefully choosing the right implementations prior works have shown how to translate many classical results into the quantum setting.
However, for indifferentiability, choosing a single fixed function for h 0 introduces new problems. Now when the adversary makes a query to h 1 , the simulator needs to decide if the query represents an attempt at evaluating H, and if so, it must program the output of h 1 accordingly. However, without knowing what inputs the adversary has queried to h 0 , it seems impossible for the simulator to determine which point the adversary is interested in. For example, if the adversary queries h 1 on (y, z), there will be roughly 2 n possible x that gave rise to this y (since h 0 is compressing). Therefore, the simulator must choose from one of 2 n inputs of the form (x, z) on which to query H.
To make matters even more complicated, an adversary can submit the uniform superposition x |x, 0 , resulting in the state x |x, h 0 (x) , which causes it to "learn" y = h 0 (x). At this point, the simulator should be ready to respond to an h 1 query on (y, z) by using x, meaning the simulator must be entangled with x. Then, at some later time, the adversary can query again on the state x |x, h 0 (x) , resulting in the original state x |x, 0 again. The adversary can test that it received the correct state using the quantum Fourier transform. Therefore, after this later query, the simulator must be un-entangled with x. Even more complex strategies are possible, where the adversary can compute and un-compute h 0 in stages, so as to try to hide what it is doing from any potential simulator.
These issues are much more general than just the simple domain extender above. Indeed, even classically domain extension with a stateless simulator is impossible, by the following simple argument. Suppose there is a hash function
Then L, represent the logarithm of the size of the truth tables for H, h. Since we are domain extending, we are interested in the case where L . Suppose even L ≥ + 0.001.
Suppose toward contradiction that h can be simulated statelessly, which we will represent as Sim H (since the function can make H queries). Then h has a truth table of size 2 . In the real world, H agrees with C h on all inputs; therefore in order for indifferentiability to hold, in the simulated world a uniformly random H must agree with C h = C Sim H on an overwhelming fraction of inputs. But this is clearly impossible, as it would allow us to compress the random truth table of H: simply output the truth table for Sim H , along with the fraction of of input/output pairs where H and C Sim H disagree. The total length of this compressed truth table is 2 + ( 2 M )(M N ) = 2 + N 2 L . As is negligible (and therefore much smaller than 1/N ) the compressed truth table will be smaller than 2 L , the size of the truth table for H. But since H is a random function its truth table cannot be compressed, reaching a contradiction.
Therefore, any simulator for indifferentiability, regardless of the scheme, must inherently store information about the adversary. But the existing QROM techniques are utterly incapable of such recording. We therefore ask: Is indifferentiable domain extension even possible?
In this work, perhaps surprisingly, we answer the question above in the affirmative. Namely, we give a new compressed oracle technique, which allows for recording the adversary's queries in a way that the adversary can never detect. The intuition is surprisingly simple: an adversary interacting with a random oracle can be thought of as being entangled with a uniform superposition of oracles. As entanglement is symmetric, if the adversary ever has any information about the oracle, the oracle must also have information about the adversary. Therefore a simulator can always record some information about the adversary, if done carefully.
We then use the technique to prove the indifferentiability of the Merkle-Damgård construction. We believe our new technique will be of independent interest; for example our technique can be used to prove the security of the Fujisaki-Okamoto transformation [FO99], and also gives very short proofs of several quantum query lower bounds.
The Compressed Oracle Technique. In order to prove indifferentiability, we devise a new way of analyzing quantum query algorithms Consider an adversary interacting with an oracle h : {0, 1} m → {0, 1} n . It is well established that the usual quantum oracle mapping |x, y → |x, y ⊕ h(x) is equivalent to the "phase" oracle, which maps |x, u → (-1) u•h(x) |x, u (we discuss this equivalence in Section 3). For simplicity, in this introduction we will focus on the phase oracle, which is without loss of generality.
Next, we note that the oracle h being chosen at random is equivalent (from the adversary's point of view) to h being in uniform superposition h |h . Indeed, the superposition can be reduced to a random h by measuring, and measuring the h registers (which is outside of A's view) is undetectable to A. To put another way, the superposition over h is a purification of the adversary's mixed state.
Therefore, we will imagine the h oracle as containing h |h . When A makes a query on x,u α x,u |x, u , the joint system of the adversary and oracle are
The query introduces a phase term (-1) u•h(x) , so the joint system becomes
We normally think of the phase as being returned to the adversary, but the phase really affects the entire system, so it is equivalent to think of the phase as being added to the oracle's state. Now, we will think of h as a vector of length 2 m × n by simply writing down h's truth table. We will think of each x, u pair as a point function P x,u which outputs u on x and 0 elsewhere. Using our encoding of functions as vectors, we can write u • h(x) as P x,u • h. We can therefore write the post-query state as
In general, the state after making q queries can be written as
Next, notice that by applying the Quantum Fourier transform to h, the h registers will now contain (P x1,u1 + • • • + P xq,uq ) mod 2. Working in the Fourier domain, we see that each query simply adds P x,u (modulo 2) to the result. In the Fourier domain, the initial state is 0.
Therefore, from A's point of view, it is indistinguishable whether the oracle for h is a random oracle, or it is implemented as follows:
-The oracle keeps as state a vector D ∈ {0, 1} n×2 m , initially set to 0.
-On any oracle query, the oracle performs the map |x, u ⊗ |D → |x, u ⊗ |D ⊕ P (x, u) Thus, with this remarkably simple change in perspective, the oracle can actually be implemented by recording and updating phase information about the queries being in made.
We can now take this a couple steps further. Notice that after q queries, D is non-zero on at most q inputs (since it is the sum of q point functions). Therefore, we can store the database in an extremely compact form, namely the list of (x, y) pairs where y = D(x) and y = 0. Notice that this allows us to efficiently simulate a random oracle, without an a priori bound on the number of queries. Previously, simulating an unbounded number of queries efficiently required computational assumptions, and simulation was only computationally secure. In contrast, simulating random oracles exactly required 2q-wise independent functions [Zha12b] and hence required knowing q up front. We therefore believe this simulation will have independent applications for the efficient simulation of quantum oracles. We will call this the compressed Fourier oracle.
We can then take our compressed Fourier oracle, and convert it back into a primal-domain oracle. Namely, for each (x, y) pair, we perform the QFT on the y registers. The result is a superposition of databases of (x, w) pairs, where w roughly represents h(x). For any pair not in the database, h(x) is implicitly a uniform superposition of inputs independent of the adversary's view. We call this the compressed standard oracle. It intuitively represents what the adversary knows about the function h: if (x, y) is in the database then the adversary "knows" h(x) = y, and otherwise, the adversary "knows" nothing about h(x). In Section 3, we show how to directly obtain the compressed standard oracle.
Applying Compressed Oracles to Indifferentiability. The compressed standard oracle offers a simple way to keep track of the queries the adversary has made. In particular, it tracks exactly the kind of information needed in the classical indifferentiability proof above, namely whether or not a particular value has been queried by the adversary, and what the value of the oracle at that point is. We use this to give a quantum indifferentiability proof for Merkle-Damgård construction using prefix-free encodings [CDMP05].
To illustrate our ideas, consider our simple example above with h 0 , h 1 and H. Our simulator will simulate h 0 as in the compressed standard oracle, keeping a (superposition over) lists D 0 of (x, y) pairs. Next, our simulator must handle h 1 queries. When given a phase query |y, z , the simulator does the following. If first looks for a pair (x, y ) in D 0 with y = y. If one is found, it reasonably guesses that the adversary is interested in computing H(x, z), and so it makes a query on (x, z) to H. Otherwise, it is reasonable to guess that the adversary is not trying to compute H on any input, since the adversary does not "know" any inputs to h 0 that would result in a query to h 1 on (y, z).
While the above appears to work, we need to make sure the simulator does not disturb the compressed oracle. Unfortunately, some disturbance is necessary. Indeed, determining the value of h 0 (x) is a measurement in the primal domain. On the other hand, the update procedure for the compressed oracles needs to decide whether or not x belongs in the database, and this corresponds to a measurement in the Fourier domain (since in the Fourier domain, h 0 (x) must be non-zero). These two measurements do not commute, so by the uncertainty principle it is impossible to perform both measurements perfectly.
Nonetheless, we show that the errors are small. Intuitively, we observe that the simulator does not actually need to know the entire value of h 0 (x), just whether or not it is equal to y. We call such information a "test". Similarly, the compressed oracle implementation just needs to know whether or not h 0 (x) is equal to 0, but in the Fourier domain.
Now, these primal and Fourier tests still do not commute. Fortunately, they "almost" commute, which we formalize in the full version [Zha18]. The intuition is that, if a primal test of the form "is h 0 (x) = y" has a non-negligible chance of succeeding, h 0 (x) must be very "far" from the uniform superposition. This is because a uniform superposition puts an exponentially small weight on every outcome. Recall that the uniform superposition maps to h 0 (x) = 0 in the Fourier domain. Thus by being "far" from uniform, the Fourier domain test has a negligibly-small chance of succeeding. Therefore, one of the two tests is always "almost" determined, meaning the measurement negligibly affects the state. This means that, no matter what initial state is, the two tests "almost" commute.
Thus, the simulator can perform these tests without perturbing the state significantly. This shows that h 0 queries are correctly simulated; we also need to show that h 1 queries are correctly simulated and consistent with H. The intuition above suggests that h 1 should be consistent with H, and indeed in Section 5 we show this using a careful sequence of hybrids. Then in the full version [Zha18], we use the same ideas to prove the indifferentiability of Merkle-Damgård.
The Power of Forgetting. Surprisingly, our simulator ends up strongly resembling the classical simulator. It is natural to ask, therefore, how the simulator gets around the difficulties outlined above.
First, notice that if we translate the query x,u |x, u in our example to a phase query, it becomes x |x, 0 . This query has no effect on the oracle's state. This means the oracle remains un-entangled with the adversary, as desired.
Second, a query x |x, 0 becomes x,u |x, u for a phase query. Consider applying the query to the compressed Fourier oracle. The joint quantum system of the adversary and simulator becomes
A similar expression holds for the compressed standard oracle. Note that the simulator can clearly tell (whp) that the adversary has queried on x. Later, when the adversary queries on the same state a second time, (x, u) will get mapped to (x, 0), and will hence be removed from the database. Thus, after this later query, the database contains no information about x. Hence, the adversary is un-entangled with x, and so it's tests will output the correct value.
Ultimately then, the key difference between our simulator and the natural quantum analog of the classical simulator is that our simulator must be ready to forget some of the oracle points it simulated previously. By implementing h 0 as a compressed oracle, it will forget exactly when it needs to so that the adversary can never detect that it is interacting with a simulated oracle.
We expect our compressed oracle technique will have applications beyond indifferentiability. Here, we list two additional sets of results we are able to obtain using our technique:
Post-quantum security of Fujisaki-Okamoto. The Fujisaki-Okamoto transformation [FO99] transforms a weak public key encryption scheme into a public key encryption scheme that is secure against chosen ciphertext attacks, in the random oracle model. Unfortunately, the classical proof does not work in quantum random oracle model, owing to similar issues with indifferentiability proofs. Namely, in one step of the proof, the reduction looks at the queries made by the adversary in order to decrypt chosen ciphertext queries. This is crucial to allow the reduction to simulate the view of the adversary without requiring the secret decryption key. But in the quantum setting, it is no longer straightforward to read the adversary's queries without disrupting its state.
Targhi and Unruh [TU16] previously modified the transformation by including an additional random oracle hash in the ciphertext. In the proof, the hash function is set to be injective, and the reduction can invert the hash in order to decrypt.
In the full version [Zha18], we show how to adapt our compressed oracle technique to prove the security of the original transform without the extra hash. In addition, we show security against even quantum chosen ciphertext queries, thus proving security in the stronger model of Boneh and Zhandry [BZ13]. We note that recently, Jiang et al. [JZC + 18] proved the security of the FO transformation when used as a key encapsulation mechanism. Their proof is tight, whereas ours is somewhat loose. On the other hand, we note that their proof does not apply if FO is used directly as an encryption scheme, and does not apply in the case of quantum chosen ciphertext queries.
Simple Quantum Query Complexity Lower Bounds. We also show that our compressed oracles can be used to give very simple and optimal quantum query complexity lower bounds for problems for random functions, such as pre-image search, collision finding, and more generally k-SUM.
Our proof strategy is roughly as follows. First, since intuitively the adversary has no knowledge of values of h outside of D, except with very small probability any successful algorithm will output points in D. Therefore it suffices to bound the number of queries required to get D to contain a pre-image/collision/k-sum.
For pre-image search, we re-prove the optimal lower bound of Ω(2 n/2 ) queries of [BBBV97], but for random functions; note that pre-image search for random functions and worst-case functions is equivalent using simple reductions. The proof appears superficially similar to [BBBV97]: we show that each query can increase the "amplitude" on "good" databases by a small O(2 -n/2 ) amount. After q queries, this amplitude becomes O(q/2 n/2 ), which we then square to get the probability of a "good" database. The proof is only slightly over a page once the compressed oracle formalism has been given.
We then re-prove the optimal collision lower bound of Ω(2 n/foot_2 ) queries for random functions, matching the worst case bound [AS04] and the more recent average case bound [Zha15]. Remarkably, our proof involves only a few lines of modification to the pre-image lower bound. We show that the amplitude on "good" databases increases by O( √ q × 2 n/2 ) for each query, where the extra √ q intuitively comes from the fact that the database has size at most q, giving q opportunities for a collision every time a new entry is added to the database 3 . In contrast to our very simple extension, the prior collision bounds involved very different techniques and were much more complicated. Also note that prior works could not prove directly that finding collisions were hard. Instead, they show that distinguishing a function with many collisions from an injective function was hard. This then only works directly for expanding functions, which are of little interest to cryptographers. Zhandry [Zha15] shows for random functions a reduction from expanding functions to compressing functions, giving the desired lower bound for compressing functions. Our proof, in contrast, works directly with functions of arbitrary domain and range. These features suggests that our proof technique is fundamentally different than those of prior works.
By generalizing our collision bound slightly, we can obtain an Ω(2 n/(k+1) ) lower bound for finding a set of distinct points x 1 , . . . , x k such that i H(x i ) = 0. This bound is tight as long as n ≤ km by adapting the collision-finding algorithm of [BHT98] to this problem. Again, our proof is obtained by modifying just a few lines of the pre-image search proof.
Ristenpart, Shacham, and Shrimpton [RSS11] shows that indifferentiability is insufficient for replacing a concrete hash function with a random oracle in the setting of multi-stage games. Nonetheless, Mittelbach [Mit14] shows that indifferentiability can still be useful in these settings. Exploring the quantum analogs of these results is an interesting direction for future research.
Distinguishing quantum states. The density matrix captures all statistical information about a mixed state. That is, if two states have the same density matrix, then they are perfectly indistinguishable.
For density matrices ρ, ρ that are not identical, we define the trace distance as T (ρ, ρ ) = 1 2 i |λ i |, where λ i are the eigenvalues of ρ-ρ . The trace distance captures the maximum distinguishing advantage amongst all possible measurements of the state.
We will need the following Theorem of Bennett et al. (which we have slightly improved, see full version [Zha18] for the improved proof):
We will also need the following relaxation of commuting operations:
Definition 1. Let U 0 , U 1 be unitaries over the same quantum system. We say that U 0 , U 1 -almost commute if, for any initial state ρ, the images of ρ under U 0 U 1 and U 1 U 0 are at most -far in trace distance.
Here, we describe several oracle variations. The oracles will all be equivalent; the only difference is that the oracle registers and/or the query registers are encoded in different ways between queries. We start with the usual quantum random oracle, which comes in two flavors that we call the standard oracle and phase oracle. Then we will give our compressed standard and phase oracles.
Standard Oracle. Here, the oracle H : {0, 1} m → {0, 1} n is represented as its truth table: a vector of size 2 m where each component is an n-bit string.
The oracle takes as input a state consisting of three sets of registers: mqubit x registers representing inputs to the function, n-qubit y registers for writing the response, and n2 m -qubit H registers containing the truth table of the actual function. The x, y registers come from the adversary, and the H registers are the oracle's state, which is hidden from the adversary accept by making queries. On basis states |x, y ⊗ |H , the oracle performs the map
For initialization, the oracle H will be initialized to the uniform superposition over all H:
H |H . We will call this oracle StO. The only difference between StO and the usual quantum random oracle model is that, in the usual model, H starts out as a uniformly chosen random function rather than a superposition (that is, the H registers are the completely mixed state). We will call the oracle with this different initialization StO . Proof. This can be seen by tracing out the oracle registers. The mixed state of the adversary in both cases will be identical. Thus, our initialization is equivalent to H being a uniformly random oracle.
Phase Oracle. We will also consider the well-known phase model of oracle queries. This model technically offers a different interface to the adversary, but can be mapped to the original oracle by simple Hadamard operations.
The oracle takes as input a state consisting of three sets of registers: x registers representing inputs to the function, z phase registers, and H registers containing the truth table of the actual function. On basis states |x, y ⊗ |H , it performs the map |x, z
For initialization, H is the uniform superposition as before. We will call this oracle PhO. Analogous to the above, this is equivalent to the case where H is uniformly random. The following Lemma is implicit in much of the literature on quantum-accessible oracles: Lemma 3. For any adversary A making queries to StO, let B be the adversary that is identical to A, except it performs the Hadamard transformation H ⊗n to the response registers before and after each query. Then
Compressed Standard Oracles. We now define our compressed standard oracles. The intuition for our compressed standard oracle is the following. Let |τ be the uniform superposition. In the standard (uncompressed) oracle, suppose for each of the 2 m output registers, we perform the computation mapping |τ → |τ |1 and |φ → |φ |0 for any |φ orthogonal to |τ . In other words, this computation tests whether or not the state of the output registers is 0 in the Fourier basis. We will write the output of the computation in some auxiliary space. Now the state of the oracle is a superposition over truth tables, and a superposition over vectors in {0, 1} 2 m containing the output of the tests. A straightforward exercise (and a consequence of our analysis below) shows that if we perform these tests after q queries, all vectors in the test vector superposition have at most q positions containing a 0. The reason is, roughly, if we do the tests before any queries the vector will be identically 1 since we had a uniform superposition (which is 0 in the Fourier basis). Then, each query affects only one position of the superposition, increasing the number of 0's by at most 1.
Also notice that anywhere the vector contains a 1, the corresponding truth table component contains exactly the uniform superposition |τ . Anywhere the vector contains a 0, the corresponding truth table component contains a state that is guaranteed to be orthogonal to |τ .
What we can do then is compress this overall state. We will simply write down all the positions where the test vector contained a 0, and keep track of the truth table component for that position. Everywhere else we can simply ignore since we know what the truth table contains. The result is a (superposition over) database consisting of at most q input/output pairs. In more detail, a database D will be a collection of (x, y) pairs, where (x, y) ∈ D means the function has been specified to have value y on input x. We will write D(x) = y in this case. If, for an input x there is no pair (x, y) ∈ D, then we will write D(x) = ⊥, indicating that the function has not been specified. We will maintain that a database D only contains at most one pair for a given x.
Concretely, if we have an upper bound t on the number of specified points, a database D will be represented an element of the set S t , where S = ({0, 1} m ∪ {⊥})×{0, 1} n . Each value in S is an (x, y) pair; if x = ⊥ the pair means D(x) = y, and x = ⊥ means the pair is unused. For x 1 < x 2 < • • • < x and y 1 , . . . , y , the database representing that input x i has been set to y i for i ∈ [ ], with all other points unspecified, will be represented as:
where the number of (⊥, 0 n ) pairs is equal to t -.
After query q, the state of the oracle will be a superposition of databases in this form, using the upper bound t = q. So initially the state is empty. We will maintain several invariants:
-For any database in the support of the superposition, for any (x, y) pair where x = ⊥, we have that y = 0 n . All (⊥, 0 n ) pairs are at the end of the list. -For any database in the support of the superposition, if (x, y) occurs before (x , y ), it must be that x < x . -For any of the positions that have been specified, the y registers are in a state that is orthogonal to the uniform superposition |τ (indicating that in the Fourier domain, the registers do not contain 0).
We also need to describe several procedures on databases. Let |D| be the number of pairs (x, y) ∈ D for x = ⊥. For a database D with |D| < t and D(x) = ⊥, write D ∪ (x, y) to be the new database obtained by adding the pair (x, y) to D, inserting in the appropriate spot to maintain the ordering of the x values. Since |D| was originally less than t, there will be at least one (⊥, 0 n ) pair, which is deleted. Therefore, the overall number of pairs (including ⊥s) in D and D ∪ {(x, y)} are the same.
Before describing how to process a query, we need to describe a local decompression procedure StdDecomp x which acts on databases. This is a unitary operation. It suffices to describe its action on a set of orthonormal states. Let t be the current upper bound on the number of set points.
-For D such that D(x) = ⊥ and |D| < t,
In other words, if D already is specified on x, and moreover if the corresponding y registers are in a state orthogonal to |τ (meaning they do not contain 0 in the Fourier domain), then there is no need to decompress and StdDecomp x is the identity. On the other hand, if D is specified at x and the corresponding y registers are in the state |τ , StdDecomp x will remove x and the y register superposition from D.
Note that the left-hand sides of last two cases form an orthonormal basis for the span of |D such that D(x) = ⊥. The left-hand sides of the first two cases form an orthonormal basis for the remaining D. Thus, StdDecomp x is defined on an orthonormal basis, which by linearity defines it on all states. The right-hand sides are the same basis states just in a different order. As such, this operation maps orthogonal states to orthogonal states, and is therefore unitary. Note that StdDecomp x is actually an involution, as applying it twice results in the identity. Let StdDecomp be the related unitary operating on a quantum system over x, y, D states, defined by it's action on the computational basis states as:
In other words, in superposition it applies StdDecomp x to |D , where x is taken from the x registers.
For some additional notation, we will take y ⊕ ⊥ = y and y • ⊥ = 0. Let Increase be theprocedure which initializes a new register |(⊥, 0 n ) and appends it to the end. In other words, Increase|x, y ⊗ |D = |x, y ⊗ |D |(⊥, 0 n ) , where |D |(⊥, 0 n ) is interpreted as a database computing the same partial function as D, but with the upper bound on number of points increased by 1.
Let CStO , CPhsO be unitaries defined on the computational basis states as
Finally, we describe the CStO and CPhsO oracles:
In other words, increase the bound on the number of specified points, then uncompress at x (which is ensured to have enough space since we increased the bound), apply the query (which is ensured to be specified since we decompressed), and then re-compress. Proof. We prove the case for CStO and StO, the other case being almost identical. We prove security through a sequence of hybrids.
Hybrid 0. In this case, the adversary interacts with StO. That is, the oracle's database is initialized to the uniform superposition over all H, and each query performs the unitary mapping |x, y ⊗ |H → |x, y ⊕ H(x) ⊗ |H .
Hybrid 1. In this hybrid, we use a slightly different way of representing the function H. Instead of writing H as a truth table, we represent it as a complete database D = ((0, H(0)), (1, H(1)), . . . , (2 m -1, H(2 m -1))). Here, the upper bound on the number of determined points is exactly 2 m . The oracle's state starts out as
The update procedure for each query is simply CStO , meaning that each query maps |x, y ⊗ |((0, H(0)), (1, H(1)), . . . , (2 m -1, H(2 m -1))) to |x, y ⊕ H(x) ⊗ |((0, H(0)), (1, H(1)), . . . , (2 m -1, H(2 m -1))) . Hybrid 1 is identical to Hybrid 0, except that we have inserted the input points 1, . . . , 2 m -1 into the oracle's state, which has no effect on the adversary. Hybrid 2. Next, introduce a global decompression procedure StdDecomp , which applies StdDecomp x for all x in the domain, one at a time from 0 up to 2 m -1.
We observe that when the upper bound on determined points is 2 m , then StdDecomp x commutes with StdDecomp x for any x, x . This readily follows from the fact that when the upper bound is t = 2 m , D(x) = ⊥ implies |D| < t.
In Hybrid 2, the oracle starts out as the empty database with upper bound 2 m . Then, each query is implemented as
Notice that StdDecomp only affects the oracle's registers and therefore commutes with the any computation on the adversary's side. Also notice that between each two queries, StdDecomp is applied twice and that it is an involution. Therefore the two applications cancel out. At the beginning, StdDecomp is applied to an empty database, which maps it to the uniform superposition
before the first application of CStO . Therefore, this hybrid is perfectly indistinguishable from Hybrid 1.
Hybrid 3. This hybrid applies StdDecomp • CStO • StdDecomp for each query.
To prove indistinguishability from Hybrid 2, consider a database D with upper bound 2 m but where |D| = for some ≤ 2 m . Notice that for any D in the support of StdDecomp x |D , D (x) = D(x) for all x = x . This means
In other words, when the query register contains x = x , StdDecomp x and CStO commute. Therefore,
This shows that Hybrid 2 and Hybrid 3 are identical.
Hybrid 4. Finally, this hybrid is the compressed standard oracle: the oracle's state starts out empty, and CStO is applied for each query.
To prove equivalence, first notice that for any x, y, D,
Indeed, all D are defined on the same inputs except for possibly the input x.
This means that after q queries in Hybrid 3, the oracle's registers only have support on D containing at most q defined points; the remaining ≥ 2 mq points are all (⊥, 0 n ). Therefore, we can discard all but the first q pairs in D, without affecting the adversary's state. The result is identical to Hybrid 4.
In the full version [Zha18], we give several more oracle variations; while not used in this work, they may be useful in other settings. These variations also provide an alternative way to arrive at the compressed standard oracles.
Here, we provide a lemma which relates the adversary's knowledge of an oracle output to the probability that point appears in the compressed oracle database. This lemma is proved in the full version [Zha18], and follows from a straightforward (albeit delicate) analysis off the action of CStO.
Lemma 5. Consider a quantum algorithm A making queries to a random oracle H and outputting tuples (x 1 , . . . , x k , y 1 , . . . , y k , z). Let R be a collection of such tuples. Suppose with probability p, A outputs a tuple such that (1) the tuple is in R and (2) H(x i ) = y i for all i. Now consider running A with the oracle CStO, and suppose the database D is measured after A produces its output. Let p be the probability that (1) the tuple is in R, and (2) D(x i ) = y i for all i (and in particular D(
In this section, we re-prove several known query complexity lower bounds, as well as provide some new bounds. All these bounds follow from simple applications of our compressed oracles.
Here, we re-prove that the quadratic speed-up of Grover search is optimal. Specifically, we prove that for a random function H : {0, 1} m → {0, 1} n , any q query algorithm has a success probability of at most O(q 2 /2 n ) for finding a pre-image of 0 n (or any fixed value).
Theorem 1. For any adversary making q queries to CStO or CPhsO and an arbitrary number of database read queries, if the database D is measured after the q queries, the probability it contains a pair of the form
Proof. Let 0 n ∈ D mean that D contains a pair of the form (x, 0 n ). The compressed oracle's database starts out empty, so the probability 0 n ∈ D is zero. We will show that the probability cannot rise too much with each query. We consider compressed phase queries, CPhsO. Compressed standard queries are handled analogously. Consider the joint state of the adversary and oracle just before the qth CPhsO query:
Where D represents the compressed phase oracle, x, y as the query registers, and z as the adversary's private storage. Define P as the projection onto the span of basis states |x, y, z ⊗ |D such that 0 n ∈ D. Our goal will be to relate the norms of P |ψ (the magnitude before the query) to P • CPhsO|ψ (the magnitude after the query).
Define projections Q onto states such that (1) 0 n / ∈ D (meaning the database does not yet contain 0 n ), ( 2
Finally, P • CPhsO • P |ψ ≤ P |ψ and CPhsO • S|ψ = S|ψ . Putting it all together, we have that
Therefore, after q queries, we have that the projection onto D containing a zero has norm at most q/ √ 2 n . Now, the probability the database in |ψ contains a 0 n is just the square of this norm, which is at most q 2 2 n . The following is obtained by combining Theorem 1 with Lemma 5: Corollary 1. After making q quantum queries to a random oracle, the probability of finding a pre-image of 0 n is at most O(q 2 /2 n ).
Proof. We will assume the adversary always makes a final query on it's output x, and outputs (x, H(x)). This comes at the cost of at most 1 query, so it does not affect the asymptotic result. Then we can use the relation R(x, y) which accepts if and only if y = 0 n . In the second experiment of Lemma 5, the only way for the adversary to win is to have the database contain a pre-image of 0 n . As such, Theorem 1 shows p = O(q 2 /2 n ). Then Lemma 5 shows that p = O(q 2 /2 n ), which is exactly the probability the adversary outputs a pre-image of 0 n when interacting with the real random oracle.
Theorem 2. For any adversary making q queries to CStO or CPhsO and an arbitrary number of database read queries, if the database D is measured after the q queries, the resulting database will contain a collision with probability at most O(q 3 /2 n ) Proof. The proof involves changing just a few lines of the proof of Theorem 1. We define P to project onto databases D containing a collision, and re-define Q, R, S accordingly. Write Q|ψ = x,y,z,D α x,y,z,D |x, y, z ⊗ |D . Then
We can write this as the 1 √ 2 n i |φ i , where |φ i is the partial sum which sets w to be the ith element in D (provided it exists). The |φ i are orthogonal, and satisfy |φ i ≤ Q|ψ . Moreover, after q queries D has size at most q, and so there are at most q of the |φ i . Therefore, P • CPhsO • Q|ψ ≤ q/2 n Q|ψ .
By a similar argument, P •CPhsO•R|ψ ≤ q/2 n R|ψ . Putting everything together, this shows that the norm of P |ψ increases by at most q/2 n with each query. Therefore, after q queries, the total norm is at most q 3 /2 n , giving a probability of q 3 /2 n . Corollary 2. After making q quantum queries to a random oracle, the probability of finding a collision is at most O(q 3 /2 n ).
We can easily generalize even further. Let R be a relation on -tuples over {0, 1} n . Say that R is satisfied on a database D if D contains distinct pairs (x i , y i ) such that R(y 1 , . . . , y ) = 1. Let k(q) be the maximum number of y that can be added to an unsatisfied database of size at most q -1 to make it satisfied.
Theorem 3. For any adversary making q queries to CStO or CPhsO and an arbitrary number of database read queries, if the database D is measured after the q queries, the resulting database will be satisfied with probability at most O(q 2 k(q)/2 n ).
For the k-sum problem, there are at most q k-1 incomplete tuples that can be completed by adding a new point. As such, k(q) ≤ q k-1 ≤ q k-1 . This gives:
Corollary 3. After making q quantum queries to a random oracle, the probability of finding k distinct inputs x i such that i H(x i ) = 0 n is at most O(q k+1 /2 n ).
Let h : {0, 1} m → {0, 1} n be a random oracle, and let C h : {0, 1} M → {0, 1} N be a polynomial-sized stateless classical circuit that makes oracle queries to h. Intuitively, in the "real" world, h is a random function and H is set to be C h . C h is indifferentiable if this real world is indistinguishable from an "ideal" world, where H is a random function, and h is set to be Sim h for some efficient simulator Sim.
In order to help us prove indifferentiability of a simulator Sim, we introduce two weaker requirements. The first is indistinguishability, a weakened version of indifferentiability where the distinguisher is not allowed any queries to H:
Next, we introduce the notion of consistency. Here, we set h to be simulated by Sim H , and we ask the adversary to distinguish honest evaluations of H from evaluations of C h (where again h is still simulated by Sim H ).
Lemma 6. Any consistent and indistinguishable simulator is indifferentiable.
The proof of Lemma 6 is straightforward, and proved in the full version [Zha18]. Finally, it is straightforward to adapt the definitions and Lemma 6 to handle the case of many random compression functions h 1 , . . . , h . In this case, C makes queries to h 1 , . . . , h , D has quantum oracle access to h 1 , . . . , h and H, while S makes quantum queries to H and simulates h 1 , . . . , h .
We now consider a simple domain extender. Let h 1 : {0, 1} m → {0, 1} n , h 2 : {0, 1} n × {0, 1} → {0, 1} n be two functions. Let C h1,h2 (x 1 , x 2 ) = h 2 (h 1 (x 1 ), x 2 ) Theorem 4. If h 1 , h 2 are random oracles, the simple domain extender C is indifferentiable from a random oracle.
Coron et al. [CDMP05] show that the indifferentiability of C is sufficient to prove the indifferentiability of Merkle-Damgård for a particular choice of prefixfree encoding (see paper for details). That part of the paper translates immediately to the quantum setting, so Theorem 4 then shows quantum indifferentiability for the same prefix free encoding. In the full version [Zha18], we show more generally that Merkle-Damgård is indifferentiable for any choice of prefix-free encoding. All the main ideas for the full proof are already contained in the proof of Theorem 4 below, just the details get a bit more complicated in the more general setting.
Before describing our simulator, we need some terminology. For a database D of input/output pairs, a collision is two pairs (x 1 , y 1 ), (x 2 , y 2 ) ∈ D, x 1 = x 2 such that y 1 = y 2 . For an input (y, x 2 ) ∈ {0, 1} n × {0, 1} , a completion in D is a pair (x 1 , y) ∈ D. For such a completion, we will call w = (x 1 , x 2 ) the associated input.
We define a classical procedure FindInput. FindInput takes as input x ∈ {0, 1} n × {0, 1} , and a database D. It parses x as (y, x 2 ) ∈ {0, 1} n × {0, 1} . Then, it looks for a completion (x 1 , y) ∈ D. If found, it will take, say, the completion with the smallest x 1 value, and output (b = 1, w = (x 1 , x 2 )). If no completion is found, it will output (b = 0, w = 0 m+ ). Note that for the output values in D, FindInput only needs to apply an equality check on those values, testing if they contain y. By applying such an equality check to each output register, it can compute b and w. Looking forward, when we implement FindInput in superposition, this means FindInput only touches the output registers of D by making a computational basis test.
We are now ready to describe our simulator. Sim will keep a (superposition over) database D a , which represents the simulation of the random oracle h a that it will update according to the CStO update procedure. D a is originally empty. It will also have a private random oracle h b . For concreteness, h b will be implemented using another instance of CStO, but it will be notationally convenient to treat h b as being a uniformly random function.
On h 1 queries, Sim makes a query to h a , performing the appropriate CStO update procedure to D a . On h 2 queries, Sim performs a unitary operation with the following action on basis states:
This unitary is straightforward to implement with a single query to each of h b and H, and is detailed in the full version [Zha18].
In the next three subsections, we prove that our simulator is indifferentiable. In Section 5.4, we prove a useful commutativity lemma. Then in Sections 5.5 and 5.6, we prove the indistinguishability and consistency, respectively, of Sim. By Lemma 6, this proves that Sim is indifferentiable, proving Theorem 4.
Lemma 7. Consider a quantum system over x, D, x , z. The following two unitaries O(1/ √ 2 n )-almost commute:
-StdDecomp, acting on the x, D registers.
-FindInput, taking as input the D, x registers and XORing the output into z.
The intuition is that, for StdDecomp to have any effect, either (1) D(x) = ⊥ or (2) D(x) is in uniform superposition; StdDecomp will simply toggle between the two cases. Now, a uniform superposition puts a weight of 1/ √ 2 n on each possible y value. Since there is only a single possible y value for D(x) that matches x , it is exponentially unlikely that FindInput will find a match at input x in Case (2). On the other hand, it will never find a match at input x in Case (1). Hence, there is an exponentially small error between the action of FindInput on these two cases. We prove the lemma formally in the full version [Zha18].
Lemma 8. Sim is indistinguishable. In particular, for any distinguisher D making at most q queries to h 1 , h 2 , We define a classical encoding procedure Encode for pairs D a , D b of databases. Intuitively, Encode will scan the values ((z, x 2 ), y) in D b , seeing if any of the (z, x 2 ) values correspond to a completion in D a . If so, such a completion will have an associated input w. Encode will reasonably guess that such a completion corresponds to an evaluation of H(w) = C h1,h2 (w). Therefore, Encode will remove the value ((z, x 2 ), y) in D b , and add the pair (w, y) to a new database E, intuitively representing the oracle H. In more detail, Encode does the following:
-For each pair ((z, x 2 ), y) ∈ D b , run FindInput((z, x 2 ), D a ) = (b, w). If b = 1, re-label the pair to (w, y) -Remove all re-labeled pairs D b (which are easily identifiable since the input will be larger) and place them in a new database E.
We define the following Decode procedure, which operates on triples D a , D b , E:
-Merge the databases D b , E -For each pair (w, y) that was previously in E, where w = (x 1 , x 2 ), evaluate z = D a (x 1 ). Re-label (w, y) to ((z, x 2 ), y). If z = ⊥ or if the input (z, x 2 ) was already in the database, output ⊥ and abort.
Note that Encode, Decode are independent of the order elements are processed. It also follows from the descriptions above that Decode(Encode(D a , D b )) = (D a , D b ). Therefore, Encode can be implemented in superposition, giving the unitary that maps |D a , D b to |Encode(D a , D b ) . Also note that Encode(∅, ∅) = (∅, ∅, ∅).
With this notation in hand, we are now ready to prove security: consider a potential distinguisher D. We prove security through a sequence of hybrids.
Hybrid 0. This is the real world, where h 1 , h 2 are random oracles. Let p 0 be the probability D outputs 1 in this case.
Hybrid 1. This is still the real world, but we add an abort condition. Namely, after any query to h 1 , we measure if the database h a contains a collision; if so, we immediately abort and stop the simulation. Let p 1 be the probability D outputs 1 in Hybrid 1.
Proof. First, suppose that before the ith query to h 1 , the superposition over h a has support only on databases containing no collisions. Let |ψ be the joint state of the adversary and simulator just after the query to h 1 . Then write |ψ = |ψ 0 + |ψ 1 where |ψ 0 is the projection onto states where h a has no collisions, and |ψ 1 is the projection onto states where h a contains at least one collision. Following the proof of Theorem 2, we know that |ψ 1 ≤ i/2 n .
Therefore, if we let |ψ q be the joint state after the qth query in Hybrid 0 and |φ q the joint state in Hybrid 2, we would have that |ψ Proof. We start with Hybrid 1. First, by Lemma 4, we can implement D a , D b in Hybrid 1 as independent instances of CStO. Now, between all the queries insert Encode followed by Decode. Also insert the two procedures before the first query. Now each query is preceded by a Decode and followed by a collision check and an Encode. Note that Encode, Decode do not affect the database D a , and so commute with the collision check. Therefore, we can swap the order of the collision check and Encode that follow each query.
By merging the Decode, query, Encode and collision check operations together, we get exactly the update procedure of Hybrid 2. All that's left is an initial Encode procedure at the very beginning, which produces |∅, ∅, ∅ as the database state, just as in Hybrid 2.
Hybrid 3. This hybrid is the ideal world, where h 1 , h 2 queries are answered by Sim, except that we will have the abort condition if a collision in h a is ever found. In other words, instead of decoding, applying the query, and then encoding, in Hybrid 3 we act directly on the encoded state using the algorithms specified by Sim. For h 1 queries, the difference from Hybrid 2 is just that the queries are made directly to h a , instead of Decode, then h a query, then Encode. For h 2 queries, the differences appear more substantial. h 2 queries, on superpositions over x, y, D a , D b , E, can be summarized as follows:
Proof. We start with the very last query, and gradually change the queries one-by-one from how they were answered in Hybrid 2 to Hybrid 3. For h 1 queries, we observe that it suffices to swap the order of Encode and CStO. Indeed, suppose we move the final Encode to come before CStO. The previous query ended with an Encode, and now the current query begins with Decode then Encode. Since Decode • Encode is the identity, all thee of these operations collapse into a single Encode, which we keep at the end of the previous query. The result is that the current query is just a direct call to CStO, as in Hybrid 3. Then it remains to show that we can swap the order of Encode and CStO. For this, notice that Encode only interacts with D a through FindInput. As such, all steps in Encode, CStO commute except for the two StdDecomp operations in CStO and the FindInput operation in Encode for each entry in D b (plus another FindInput operation when un-computing the scratch-space of Encode in order to implement in superposition). By Lemma 7, these ≤ 4q operations each O(1/ √ 2 n )-almost commute, meaning Encode and CStO O(q/ √ 2 n )-almost commute. For h 2 queries, fix an x, D a and suppose D a contains no collisions as guaranteed. There are two cases: 3. Finally, make another h 1 query to un-compute the value of z. This is accomplished in the following steps: Let D be a potential distinguisher. We consider the following hybrids:
Hybrid 0. In this hybrid, H queries are answered using C h1,h2 , as worked out above. Let p 0 be the probability D outputs 1.
Hybrid 1. This hybrid is identical to Hybrid 0, except that Steps 1c and 3a are removed. Let p 1 be the probability D outputs 1 in this hybrid. Proof. In either hybrid, since we do not apply the Steps 1c and 3a, D a is guaranteed to contain the pair (x 1 , z), where z is the same as in Step 2. Therefore, in Hybrid 2, FindInput((z, x 2 ), D a ) is guaranteed to find a completion. Moreover, for D a that contain no collisions, FindInput((z, x 2 ), D a ) will find exactly the completion (x 1 , z). In this case, w = (x 1 , x 2 ), and Hybrid 2 will make a query to H on (x 1 , x 2 ). The end result is that for D a containing no collisions, Step 2 is identical in both Hybrids. Since the collision check guarantees no collisions in D a , this shows that the two hybrids are identical.
Hybrid 4. In this hybrid, H queries are made directly to H, but we still have the abort condition. Let p 4 be the probability D outputs 1 in this hybrid. Overall then |p 0p 5 | < O( q 3 /2 n ), finishing the proof of Lemma 13.
Here, we summarize our results on the Fujisaki-Okamoto transformation [FO99].
The transformation starts with a symmetric key encryption scheme (Enc S , Dec S ) and a public key encryption scheme (Gen P , Enc P , Dec P ). Assuming only mild security properties of these two schemes (which are much easier to obtain than strong CCA security), the conversion produces a new public key scheme (Gen, Enc, Dec) which is secure against chosen ciphertext attacks. Let G, H are two random oracles, where G outputs keys for Enc S and H outputs the random coins used by Enc P . The scheme is as follows:
-Gen = Gen The main difficulty in the classical proof of security is allowing the reduction to answer decryption queries. The key idea is that, in order for the adversary to generate a valid ciphertext, it must have queried the oracles on δ. The reduction will simulate G, H on the fly by keeping track of tables of input/output pairs. When a chosen ciphertext query comes in, it will scan the tables looking for a δ that "explains" the ciphertext.
In the quantum setting, we run into a similar recording barrier as in the indifferentiability setting. Our key observation is that the output values of the G, H tables are only used for set membership tests. Just like equality tests used in our indifferentiability simulator, set membership tests in the primal and Fourier domain very nearly commute. As such, we can use our compressed oracles to mimic the classical proof following our techniques. Our reduction can even handle chosen ciphertext queries on quantum superpositions of ciphertexts. In the full version [Zha18], we prove the following theorem:
The one exception we are aware of is Unruh's adaptive programming[Unr15]. This proof does change the oracle adaptively, but only inputs for which adversary's queries have only negligible "weight". Thus, the change is not detectable. The following discussion also applies to Unruh's technique.
We note that if the underlying building blocks are strengthened, Fiat-Shamir was proven secure by Unruh[Unr16]
and the square root comes from the fact that the norm of the sum of q unit vectors of disjoint support is √ q