Cryptography often considers the strongest yet plausible attacks in the real world. Preprocessing (a.k.a. non-uniform attack) plays an important role in both theory and practice: an efficient online attacker can take advantage of advice prepared by a time-consuming preprocessing stage.

Salting is a heuristic strategy to counter preprocessing attacks by feeding a small amount of randomness to the cryptographic primitive.
We present general and tight characterizations of preprocessing against cryptographic salting, with upper bounds matching the advantages of the most intuitive attack.
Our result quantitatively strengthens the previous work by Coretti, Dodis, Guo, and Steinberger (EUROCRYPT'18).
Our proof exploits a novel connection between the non-uniform security of salted games and direct product theorems for memoryless algorithms.

For quantum adversaries, we give similar characterizations for property finding games, resolving an open problem of the quantum non-uniform security of salted collision resistant hash by Chung, Guo, Liu, and Qian (FOCS'20).
Our proof extends the compressed oracle framework of Zhandry (CRYPTO'19) to prove quantum strong direct product theorems for property finding games in the average-case hardness.

§ INTRODUCTION

In modern cryptography, the notion of security serves as the cornerstone for evaluating the robustness of cryptographic objects against various adversarial attacks.
In most constructions, the security boils down to the specific hardness of cryptographic primitives.
For instance, the hardness of hash functions refers to the complexity of finding hash collisions; the security of one-way functions hinges on the intractability of finding pre-images of designated outputs.

Traditionally under the lens of uniform security, the adversary's capability is assumed to be fixed and oblivious to the actual primitive.
However, as cryptographic systems evolve to tackle increasingly sophisticated adversaries, the concept of non-uniform security emerges as a critical consideration <cit.>, which departs from uniform security by allowing the adversary to adaptively choose its attack strategies based on pre-computed knowledge or advice on the specific cryptographic primitive in question.
This departure reflects a more realistic model of real-world attacks, where the adversary performs extensive interactions with the given primitive with significant amount of time and computational power in an offline phase before actually trying to break the protocol in the online phase.
Given this offline preprocessing stage, adversaries can sometimes perform much better than their uniform counterparts. For example, finding collisions in a vanilla hash function becomes trivial if the adversary reads through its truth table and store one pair of collisions offline.

Cryptographic salting is a fundamental and universal technique to address the above issue. By including a random value, known as a salt, from the salt space $[K]$ to the primitive, the output becomes unique even if the input data is the same.
Take collision resistant hash as an example. In the salted version, a random oracle $H\colon[K] \times [M] \to [N]$ is provided.
The goal of the adversary is, given a uniformly random salt $k$, to find a pair of distinct inputs $x,x' \in [M]$ such that $H(k, x) = H(k, x')$.
Intuitively, the randomness of the salt $k$ prevents adversaries from effectively using pre-computed tables unless they store look-up tables for each possible salt value, vastly increasing the computational resources required to mount a successful attack.

The “salting” approach, dating back to a work by Morris and Thompson <cit.>, guarantees heuristic non-uniform security. The provable consequences of salting  were first investigated by De, Trevisan, and Tulsiani <cit.>.
Later, Chung, Lin, Mahmoody, and Pass <cit.> studied salting for collision resistant hash, one of the most important cryptographic applications.
Then Mahmoody and Mohammed <cit.> used salting to obtain non-uniform black-box separation results and Dodis, Guo, and Katz <cit.> established tight bounds for some specific salted cryptographic applications.

More recently, Coretti, Dodis, Guo, and Steinberger <cit.> proved that salting generically defeats preprocessing. Let $G$ be a cryptographic game in the random oracle model (ROM) and $\epsC_G(T)$ be the optimal winning probability that a $T$-query algorithm can obtain. Let $G_K$ be the salted game with the salt space $[K]$ and $\epsC_{G_K}(S, T)$ be the maximum success probability that a non-uniform algorithm with $S$-bit advice and $T$ queries can achieve.
Then they showed that $\epsC_{G_K}(S,T)$ can be bounded by (a multiple of) $\epsC_G(T)$ with an additional non-uniform advantage term decaying as the salt space $[K]$ enlarges.

For any cryptographic games $G$ in the ROM, we have

* Multiplicative version. $\epsC_{G_K}(S, T) \le\widetilde O\left(\epsC_G(T) + S T/K\right)$.

* Additive version. $\epsC_{G_K}(S, T) \le \epsC_G(T) + \widetilde O\left(\sqrt{S T/K}\right)$.

Here we use $\widetilde O$ to hide low order terms for simplicity.

When $K$ is sufficiently large, the above theorem suggests that non-uniform security of any game is about the same as its uniform security.
However quantitatively, their lower bounds does not match the most intuitive algorithm. For instance, when $G$ is the game for collision finding, we have $\epsC_G(T) = T^2/N$ by birthday paradox.[We omit low-order terms in the introduction for conciseness.]
The optimal non-uniform algorithm should be the following: store collisions for $S$ distinct salts; then in the online stage, it either outputs a stored collision for the challenge salt, or executes a birthday-paradox attack. The algorithm achieves advantage $T^2/N+S/K$, but <cit.> only provides an upper bound of $T^2/N + ST/K$.

Furthermore, when a security game with challenges (unlike collision finding) is considered, <Ref> is even looser. Dodis, Guo, and Katz <cit.> showed that for the function / permutation inversion problem, the optimal bound is $T/N + (ST)/(KN)$, whereas <Ref> only offers $T/N + S/K$.

Beyond classical adversaries, the growing power of quantum computing poses significant threats to modern cryptography. Chung, Guo, Liu, and Qian <cit.> and Liu <cit.> studied how salting could prevent quantum non-uniform attacks and provides bounds similar to <Ref>. However, even for the simplest yet most important cryptographic application — collision finding in the quantum random oracle model (QROM) — they were only able to give an upper bound $T^3/N + ST/K$, whereas the best known attack only achieves $T^3/N + S/K$, where $T^3/N$ comes from the quantum collision finding algorithm <cit.> and $S/K$ is the same advantage by storing collisions for $S$ salts.

Therefore, in this  article, we ask:

Can we provide tighter characterizations for preprocessing against salting,
in both the classical and quantum world?

§.§ Our Results

*Classical Results.
Let $G$, $G_K$, $\epsC_G$, and $\epsC_{G_K}$ be defined above. We present our first result.

For any cryptographic game $G$ in any idealized model, we have

* Multiplicative version. $\epsC_{G_K}(S,T)\le2\cdot\epsC_G(T)+2S/K$.

* Additive version. $\epsC_{G_K}(S,T)\le\epsC_G(T)+4\sqrt{S/K}$.

For applications, the multiplicative version of <Ref> is suited for games with small advantages (i.e., when $\epsC_G(T)\ll1$) and the additive version of <Ref> should be used for games with noticeable advantages (e.g., $\epsC_G(T)\ge1/2$ when $G$ is a decision game).
We also remark that while the addend in the additive version of <Ref> incurs a square-root-type loss compared with the multiplicative version, similar term appears and is shown to be tight in related works on non-uniform security of cryptographic primitives (see e.g., <cit.>).

Our <Ref> improves <cit.> (see <Ref>) in all aspects:

* First, our result shaves the extra $T$ factor in front of each $S/K$ in <Ref>.

This improvement leads to a sharp characterization for games without challenges (like collision finding or zero-preimage-finding): with $S$ bits of advice, one can store answers for $\approx S$ salts and use $T$ queries to solve challenges for other salts.

* Second, our result works in any idealized model (ROM, the random permutation model, the ideal cipher model, the generic group model, or any distribution of oracles) with any query type (see <Ref> for detail), while <Ref> only works for ROM.

* Finally, our bound is much cleaner and simpler, providing explicit control of the low order terms.
Our bound is even capable of handling small constant regimes of $S,T,K$ and can be useful in practice.

When games with challenges are considered (e.g., salted function inversion), <Ref> may no longer be tight. Intuitively, different challenges have completely different answers and a piece of $S$-bit advice cannot guarantee correctness on $S$ salts. We develop a general framework (<Ref>) for understanding salting for these kinds of games.
To demonstrate its versatility and strength, we provide two non-exhaustive examples: we reprove the bound for salted function inversion as in <cit.> and provide a tight characterization of salting when the advice is large.

Let ${\sf Inv}$ be the game, where a challenge is a uniformly sampled $y \in [N]$ and the goal is to find $x \in [M]$ in a random function such that $x$ is a pre-image of $y$. Let ${\sf Inv}_K$ be the salted game. Then we have

\begin{align*}
\epsC_{{\sf Inv}_{K}}(S, T) \leq O\left(\frac{T}{N} + \frac{ST}{KN}\right).
\end{align*}

When $S = \Omega(K)$, for any cryptographic game $G$ in any idealized model, it holds that

\begin{align*}
\epsC_{G_K}(S, T) \leq O\left( \max_{\substack{n_1, \ldots, n_K \in \mathbb{Z}^+ \\ n_1 + \cdots + n_K = S}}  \sum_{i=1}^K \frac{\delta_{G}(n_i, T)}{K} \right),
\end{align*}

where $\delta_{G}(n, T)$ is the $n$-th root of the uniform security of the vanilla game $G$ equipped with $n$ independent challenges using $nT$ queries.

It turns out that $\delta_G(n,T)$ is an upper (and usually tight) bound on the non-uniform security of the game $G$ with $n$-bit advice and $T$ queries <cit.>.
In these cases, our <Ref> is also tight and offers an intuitive strategy to achieve the optimality for large $S=n_1+\cdots+n_K$:
reserve $n_k$ bits for each salt $k$ as the best $n_k$-bit advice.
Then the algorithm uses the corresponding advice in the online challenge phase, achieving success probability $(\delta(n_1, T) + \cdots + \delta(n_K, T))/{K}$.

*Quantum Results.
Next, we turn our attention to the quantum case. <cit.> already studied general bounds for non-uniform quantum attacks against salting. They similarly have an extra factor of $T$ in front of $S/K$, making the bound non-tight even for collision resistant hash.

We start by aiming for a general quantum result as <Ref>, which successfully shaves the additional factor $T$. However, in the proof of <Ref>, we require an average-case direct product theorem (DPT) for general games.
While a worst-case quantum DPT is known <cit.>, an average-case quantum DPT is needed to analyze the idealized model, which turns out to be a long-standing open problem in quantum query complexity.

Therefore, we resort to the compressed oracle technique by Zhandry <cit.>, a powerful framework for proving average-case complexity in the quantum random oracle model (QROM). We show optimal quantum bounds for property finding games, which includes function inversion, collision finding, $k$-SUM, and more.

Let ${\sf CRHF}$ be the game, where the goal of a quantum-query algorithm is to find $x \ne x' \in [M]$ such that they have the same image under the random oracle. Its quantum non-uniform security $\epsQ_{{\sf CRHF}_K}$ (with quantum advice) is at most

\begin{align*}
\epsQ_{{\sf CRHF}_K}(S, T) \leq \widetilde{O}\left( \frac{T^3}{N} + \frac{S}{K} \right).
\end{align*}

At the center of our quantum results is an quantum strong DPT (in fact, we prove a threshold direct product theorem that is even stronger than direct product theorems) in Zhandry’s compressed oracle framework (see <Ref>).
To the best of our knowledge, this is the first average-case DPT for quantum query algorithms, which may be of independent interests.

We give an overview of our techniques in <Ref>.
Formal definitions are listed in <Ref>.
Then <Ref> contains the analysis of cryptographic salting in the classical case and <Ref> is for the quantum random oracle case.
Missing proofs can be found in Appendix.

§ TECHNIQUE OVERVIEW

We give a high-level overview of our proof techniques.

§.§ The Classical Setting

Let $\As$ be a classical algorithm with $T$ queries and $S$ bits of advice.
Upon receiving a uniformly random salt $k\sim[K]$, $\As$ aims to solve the $k$-th independent copy of the game $G$ in the salted game $G_K$.
Let $\eps$ be the winning probability of $\As$ and our goal is to give an upper bound on $\eps$.

*Removing Advice.
To eliminate the effect of the non-uniform advice, we consider executing the above procedure multiple times (say, $L$ times).
The key idea here is that, the non-uniform advice is given in advance of the random salt, therefore its power is intuitively diluted across the salt space $[K]$ <cit.>.

Let $k_1,\ldots,k_L$ be the $L$ salts chosen. Let $f_1,\ldots,f_K$ be the oracles of each salt.
For any fixed $f_1,\ldots,f_K$, the advice is also fixed.
Thus by the independence of $k_1,\ldots,k_L$, the probability of $\As$ winning on all these $L$ salts conditioned on $f_1,\ldots,f_K$ is simply

\left(\E_k\left[\eps_k\right]\right)^L,

where $\eps_k$ is the winning probability of $\As$ on salt $k$.
Considering the randomness of $f_1,\ldots,f_K$, we also have

\eps=\E_{f_1,\ldots,f_K}\left[\E_k\left[\eps_k\right]\right].

Hence by convexity, it suffices to bound the probability $\delta$ of $\As$ winning $L$ salts simultaneously and then $\eps\le\delta^{1/L}$.

Intuitively, $\delta$ should be of order $o(1)^L$ since the definition of $\delta$ involves solving $L$ independent trials, where $o(1)$ is the advantage of solving one.
When $L\gg S$, it does not hurt if we replace the non-uniform $S$-bit advice by a random $S$-bit string, since the latter has a probability of $2^{-S}\gg2^{-L}$ to be equal to the former.

Formally, let $\eta$ be the probability of $\As$ winning $L$ salts with a uniformly random $S$-bit string as advice (which can in turn be hardwired oblivious to $f_1,\ldots,f_K$).
Then we have $\delta\le2^S\cdot\eta$ and, more importantly, since the oracle-dependent advice is removed, we only need to analyze uniform algorithms for $\eta$.
This corresponds to <Ref> in the proof of <Ref>.

*Reducing to Direct Product Theorems.
Let $\Bs$ be the $T$-query algorithm corresponding to $\As$ with hardwired advice. Then $\eta$ is equivalent to the success probability of the following procedure:

*  Sample salts $k_1,\ldots,k_L\sim[K]$.

*  Check whether $\Bs$ solves the $k_i$-th independent copy of $G$ for each $i\in[L]$.

Let $U$ be the set of distinct salts in $k_1,\ldots,k_L$.
Then conditioned on <Ref>, $U$ is fixed and the success of <Ref> implies on the success of $\Bs$ solving independent copies of $G$ indexed by $U$.
Though $\Bs$ has access to all $f_1,\ldots,f_K$ even when just solving salt $k$, intuitively only $f_k$ should be relevant. This corresponds to <Ref>.

The above desired phenomenon is exactly characterized by direct product theorems:
assume our best advantage is $\gamma$ for a single instance (i.e., the game $G$ here) with $T$ budget (i.e., total amount of queries here).
Then solving $u$ independent copies (i.e., $u=|U|$ here) of this instance with $uT$ budget should be $\gamma^u$, which is simply applying the optimal strategy for each copy independently.

Since $\gamma^u$ is attainable, such a direct product theorem is the best possible.
In many cases, such a strong result does not hold and the exact decay bound remains elusive for many important applications (see e.g., <cit.>).
The study on direct product theorem is rich on its own with numerous works in circuit complexity (e.g., <cit.>), query complexity (e.g., <cit.>), communication complexity (e.g., <cit.>), property testing and coding theory (e.g., <cit.>), and more.

Our setting (the classical query model) unfortunately prohibits a general strong direct product theorem <cit.>, and the best known bound incurs an inevitable polynomial loss <cit.> dependent on $\gamma$.
Nevertheless, we are able to exploit the memoryless structure of the above procedure to obtain a strong direct product theorem through a similar analysis as presented in <cit.>. We explain it after we complete the analysis of the non-uniform security $\eps$ of $G_K$ against $T$-query algorithms with $S$-bit advice:

* By considering $L$ independent salts, we have $\eps\le\delta^{1/L}$.

* By guessing and removing the advice, we have $\delta\le2^S\cdot\eta$.

* By strong direct product theorems, we have

\eta\le\E_U\left[\gamma^{|U|}\right]\le\left(\gamma+\frac LK\right)^L,

where $\gamma$ is the uniform security of $G$ against $T$-query algorithms and $|U|$ is the number of distinct values in a draw-with-replacement experiment with $L$ draws from the universe $[K]$.
The second inequality follows from standard martingale analysis (see <Ref>).

Rearranging and optimizing the choice of $L$ gives the desired bound (see <Ref> for detail).

*Strong Direct Product Theorems for Memoryless Algorithms.
Before presenting our argument, we remark that our analysis coincides with a much earlier work by Nisan, Rudich, and Saks <cit.> under a different background. While we only became aware of their work after the completion of our paper, we do not consider our analysis for this part as our technical contribution, and we keep our argument within our setting just for completeness.

For simplicity, consider the following scenario and the general treatment can be found in <Ref>: let $x^1,\ldots,x^n$ be $n$ i.i.d. random strings given oracle access to, and we execute a $T$-query algorithm $\Cs$ sequentially for $1,2,\ldots,n$ to predict $h(x^1),\ldots,h(x^n)$.
To compare with the analysis above, $n=|U|$ is the number of distinct salts and $x^1,\ldots,x^n$ are the corresponding oracles, $\Cs$ is essentially $\Bs$, $h$ is the predicate for the game (e.g., $h(x)$ is the pre-image of zero in $x$), and $\gamma$ is the optimal success probability of a $T$-query algorithm in predicting an individual $h(x^i)$.
Our goal is to prove that the above joint prediction succeeds with probability at most $\gamma^n$.

The literature of direct product theorems usually assumes the joint prediction is provided by a much more powerful query algorithm, one single algorithm of $nT$ queries that makes all the predictions in the end <cit.>.
While intuitively it makes no sense for the algorithm to query outside $x^i$ to predict $h(x^i)$, it can actually distribute the total $nT$ queries in a more clever and adaptive way that outperforms the naive strategy to predict $h(x^i)$ individually with $T$ queries on $x^i$.
As a consequence, a strong bound of $\gamma^n$ turns out to be false <cit.> and the best known bound has an inevitable growing loss dependent on $\gamma$ itself <cit.>, making it insufficient for our purposes.

The key belief that drives us towards a bound of $\gamma^n$ in our setting comes from the fact that $\Cs$ is executed separately to predict each $h(x^i)$ and it does not share memory between separate prediction tasks.
In other words, the above scenario has a memoryless structure that the workspace is cleaned repeatedly after each $T$ queries, which intuitively forbids any contrived attacks requiring coordination between predictions of $\Cs$.
Note that while this intuition checks out, in reality $\Cs$ can still query, say $x^j$, outside $x^i$ to predict $h(x^i)$, which makes the predictions $h(x^i),h(x^j)$ correlated and perhaps magically they can be correct simultaneously with higher probability.
In fact, examples in this spirit date back to Feige's famous counterexample for the sharp parallel repetition theorem <cit.>.

To rigorously verify our belief, we start with the work by Shaltiel <cit.>, which proves the tight $\gamma^n$ bound for fair algorithms.
A fair algorithm is allowed to make all predictions in the end, potentially dependent on all the $nT$ queries, however, it is guaranteed that each $x^i$ can only be queried at most $T$ times.
Since the queries can still be intertwined among $x^i$'s, the predictions are, again, correlated.
Nevertheless, since there is an upper bound on the queries for each $x^i$, a simple induction argument can be carried out.
In a bit more detail, one can do induction on the $n$-tuple $(T_1,\ldots,T_n)$ where each $T_i$ is the upper bound of the total number of queries on $x^i$. Then one can show that the optimal strategy for a fair algorithm is spending $T_i$ queries on $x^i$ to predict $h(x^i)$ independently.

Given the sharp bound for fair algorithms (<Ref>), our goal is to reduce our memoryless algorithms to fair algorithms (<Ref>).
Note that while the memory is cleaned after each $T$ queries, the whole execution can make $\gg T$ queries on $x^i$.
On the other hand, since a fair algorithm does not have to be memoryless, these two types of algorithms are incomparable to each other.
To get a fair algorithm from a memoryless algorithm, we further exploit the memoryless structure: if some $h(x^i)$ is already predicted, then we can privately simulate the future queries to $x^i$ without actually querying $x^i$, as $\Cs$ is separately executed for each prediction and these executions commute.

By this observation, we perform the following out-of-order simulation:
let $\Cs_1,\ldots,\Cs_n$ be $\Cs$ executed to predict $h(x^1),\ldots,h(x^n)$ respectively.
We initialize $\Cs_1,\ldots,\Cs_n$ and assume without loss of generality they are deterministic.
While there is some prediction not ready, we use a cycle / path elimination procedure to progress:
for each $i$, if $\Cs_i$ has not terminated and wants to query $x^j$, then we add a directed edge from $i$ to $j$.
In this directed graph,

* Either we have a directed cycle $i_1\to i_2\to\cdots\to i_\ell\to i_1$.

Then we advance $\Cs_{i_1},\cdots,\Cs_{i_\ell}$ by one query to $x^{i_2},\ldots,x^{i_{\ell}},x^{i_1}$ respectively.

* Or we have a directed path $i_1\to i_2\to\cdots\to i_\ell$.

Then we advance $\Cs_{i_1},\ldots,\Cs_{i_{\ell-2}}$ by one query to $x^{i_2},\ldots,x^{i_{\ell-1}}$ respectively.
In addition, we privately simulate the query of $\Cs_{i_{\ell-1}}$ on $x^{i_\ell}$ without actually querying $x^{i_\ell}$.
This is valid since $i_\ell$ is the endpoint of the path, thus $\Cs_{i_\ell}$ is already terminated and the prediction $h(x^{i_\ell})$ is already generated.

By the above procedure, each $x^i$ is queried at most $T$ times, since when $\Cs_i$ queries, either $x^i$ gets a query from the predecessor in the cycle / path, or the query is privately simulated.
Therefore this out-of-order execution is a fair algorithm and we can apply the known strong direct product theorem for fair algorithms.

*A Different Analysis.
Finally we sketch a different analysis (see detail in <Ref>) that improves the previous analysis for games with numerous challenges (e.g., <Ref>) or large advice (<Ref>).
Recall that in the reduction to direct product theorems, we focus on $U$, the set of distinct salts in $L$ independent uniform salts $k_1,\ldots,k_L$.
This is tight if the challenge distribution of $G$ has low entropy.
For example, if the challenge is null (e.g., collision finding requires no challenge description), then winning salts $k_1,\ldots,k_L$ is equivalent to winning salts in $U$.
However if the challenge distribution has high entropy (e.g., the function inversion asks to invert a random challenge point), then winning $U$ can be quite off from winning all the salts, since with high probability we get different challenges even if the salts are the same.

To avoid such a potential loss, we instead look directly into $k_1,\ldots,k_L$. For each salt $k\in[K]$, let $n_k$ be the number of its appearances in $k_1,\ldots,k_L$.
Then $n_1,\ldots,n_K$ are determined by $k_1,\ldots,k_L$.
Now for fixed $k_1,\ldots,k_L$, the algorithm $\Bs$ needs to solve $n_k$ independent challenges of salt $k$ for each $k\in[K]$.
Let $G^{n_k}$ be the multi-challenge version of the game $G$ where $n_k$ i.i.d. challenges are asked simultaneously.
Then the algorithm aims to win all of them in a similar memoryless fashion: it can use $n_kT$ queries to solve $G^{n_k}$ separately for each $k\in[K]$.
Though the games $G^{n_1},\ldots,G^{n_K}$ are not identical, strong direct product theorems for memoryless algorithms can be proved with an almost identical argument.
Therefore, we can relate the non-uniform security of salting to the advantages of the multi-challenge version of $G$ (see <Ref>).

We remark that the multi-challenge version of $G$ is closely related to the non-uniform security of $G$ itself (without salting), and (tight) upper bounds have been established for various games (see e.g., <cit.>).

§.§ The Quantum Random Oracle Setting

We now move to the quantum case. The aforementioned reduction in the classical setting works in the quantum setting as long as the non-uniform quantum algorithm is given classical advice. In the described reduction, we construct a non-uniform algorithm solving multiple instances of a game, by iteratively executing an algorithm with fixed advice many times.
Such a reduction falls short when the advice is quantum, as outputting any answer would destroy the advice in an irreversible way.

*Quantum Bit-Fixing.
To address the quantum non-cloning issue, we resort to the quantum bit-fixing framework, which was first introduced by Guo, Li, Liu, and Zhang <cit.> and later refined by Liu <cit.>.
In their work, they defined the so-called quantum bit-fixing model (QBF) and proved a novel connection between security in the QBF model and non-uniform security in the quantum random oracle model (QROM). Before introducing the QBF model,  let us first grasp the intuition behind it (see <Ref> for more details).

Liu <cit.> considered a quantum-friendly adaptation of direct product games, where the quantum advice can be effectively reused to win “multiple instances” of the original games (formally, the alternating measurement game). This is achieved by a similar idea of the witness preserving amplification of QMA <cit.>, to make sure that the quantum advice is preserved throughout the entire game.
The $S$-fold alternating measurement game has $S$ rounds, with each round allowing the algorithm to make $T$ queries. An algorithm wins if and only if it succeeds all rounds in a sequential order, much like the memoryless algorithms mentioned earlier.
Since it is not the primary focus of this work, we refer interested readers to <cit.> for more details of alternating measurement games.
Eventually, if any uniform quantum-query algorithm (conducting $T$ queries per round) can win the $S$-fold alternating measurement game with probability at most $\eta^S$, the quantum non-uniform security $\epsQ_G(S, T)$ of the original game is at most $\eta$.

Now the goal is to bound the success probability of the $S$-fold game. For each $i\in[S]$, let $\mathbf{W}_i$ be the event that the algorithm wins the $i$-th round.
We aim to show that for some $\eta$, the following holds:

\begin{align*}
\Pr\left[ \mathbf{W}_1 \wedge \mathbf{W}_2 \wedge \cdots \wedge \mathbf{W}_S \right] < \eta^S.
\end{align*}

Define $\mathbf{W}_{<i}$ be the event that the algorithm wins the first $(i-1)$ rounds. Then we have

\begin{align*}
\Pr\left[ \mathbf{W}_1 \wedge \mathbf{W}_2 \wedge \cdots \wedge \mathbf{W}_S \right] = \prod_{i=1}^S \Pr[ \mathbf{W}_i \,|\,  \mathbf{W}_{<i}].
\end{align*}

Since <cit.> also showed that $\Pr[ \mathbf{W}_i \,|\,  \mathbf{W}_{<i}]$ is monotonically non-decreasing in $i$, if we can prove $\Pr[\mathbf{W}_S|\mathbf{W}_{<S}] < \eta$, it will imply  $\Pr[ \mathbf{W}_1 \wedge \cdots \wedge \mathbf{W}_S] < \eta^S$.
Even further, we can assume $\Pr[\mathbf{W}_{<S}]$ is typical, say, $\Pr[\mathbf{W}_{<S}]\ge(1/N)^{S}$.[This lower bound $(1/N)^{S}$ is arbitrarily chosen in this section for clarity in presentation.] Since otherwise $\Pr[ \mathbf{W}_1 \wedge \cdots \wedge \mathbf{W}_S]\le\Pr[\mathbf{W}_{<S}] < (1/N)^{S} \leq \eta^S$ is automatically satisfied as the target $\eta$ is usually $\gg1/N$.

The security in the QBF model is defined as the maximum of $\Pr[\mathbf{W}_S|\mathbf{W}]$ over any $T$-query strategy for the $S$-th game and any event $\mathbf{W}$ that can be achieved by an $(ST)$-quantum-query algorithm with a “non-negligible” probability (e.g., $(1/N)^{S}$ as above).
In the salted case, $\mathbf{W}_S$ itself precisely represents the event that a uniform $T$-quantum-query algorithm wins the game $G$ on a random salt.

Two immediate questions arise. First, even without conditioning on $\mathbf{W}$, bounding the probability of $\mathbf{W}_S$ necessitates tools from average-case quantum query complexity. Moreover, it becomes even more challenging when conditioning is considered.

In this study, we focus solely on the game for which Zhandry's compressed oracle technique <cit.> serves as a potent tool for addressing average-case query complexity. We will first provide an exposition of this technique and then introduce the concepts required to handle conditioning.

*An Exposition of the Compressed Oracle Technique.

In the rest of the overview, we will focus on the collision finding problem. Let us begin with the classical case. A $T$-classical-query algorithm can acquire information on at most $T$ input-output pairs of a random function. By the principle of deferred decision, one can assume that outputs are only sampled for those queried inputs, and every other output remains uniformly random. This is commonly referred to as “lazy sampling”. Thus, we can say a random oracle is initialized as $D = \emptyset$ (an empty database), meaning every output is uniformly random at the beginning. For every query $x \in [M]$, if there is a pair $(x, y) \in D$, it outputs $y$; otherwise it updates $D \gets D \cup \{(x, y)\}$ for a uniformly random $y$ and returns $y$. The database contains all the information a classical algorithm learns so far. Most importantly, the probability of the algorithm finds a collision is roughly the probability that $D$ contains a collision.
Hence, the objective shifts to bounding the probability that, following $T$ queries, $D$ contains a collision.

The seminal work by Zhandry <cit.> invented a quantum analogue of the classical lazy sampling, called “compressed oracle”. Since quantum queries can be made in superposition, one single classical database is no longer feasible to track all the information.
However, the notion of a “database” is still meaningful if the “database” itself is also stored in superposition. A quantum-query algorithm interacting with a quantum-accessible random oracle can be equivalent simulated as follows:

* The database register is initialized as $\ket \emptyset$: the algorithm has not yet queried anything.

* When the algorithm makes a quantum query, the database register gets updated in superposition: for a query $\ket x$ and a database $\ket D$, the simulator looks up $x$ in $D$.
If $x$ is not in $D$, it initializes an equal superposition $\sum \ket y$ (up to normalization), and updates $\ket D$ to $\sum_y \ket {D\cup (x, y)}$.
It then returns $y$ also in superposition.

The above description provides a high-level idea, albeit slightly inaccurate. Since a quantum algorithm can forget  previously acquired information, a formal “compressed oracle” necessitates an additional step to perform these forgetting operations.

The compressed oracle exhibits several favorable properties akin to those enjoyed by classical lazy sampling technique:

* Local change. Every quantum query will only change $\ket D$ locally: the addition of a new entry $(x, y)$, no change, or the removal of an existing entry (corresponding to the ability of forgetting).

* Knowledge upper bound. The probability of a quantum algorithm finding a collision is approximately the same as the probability of measuring the database register and obtaining $D$ with collision.

Hence, for the remainder of the overview, our focus will solely be on detecting collisions within the database register, rather than the output produced by the quantum algorithm.

*Probability as Path Integral.

Before we approach our goal: the security of salted collision finding in the QBF model (i.e., to upper bound $\Pr[\mathbf{W}_S|\mathbf W]$), we first reprove the bound for the vanilla collision finding <cit.> against uniform quantum query algorithms. We reinterpret the analysis as a form of “path integral”. This alternative view gives a new way to understand <cit.> and will help us establish a strong (threshold) direct product theorem to upper bound $\Pr[\mathbf{W}_S|\mathbf W]$.

For any $T$-query quantum algorithm, its interaction with a compressed  oracle can be written as $\compressO \, U_T \cdots \compressO \, U_2 \, \compressO \,  U_1 \ket 0 \otimes \ket \emptyset$, where $\ket 0$ is the algorithm's initial state, $\ket \emptyset$ is the initial database, each $U_i$ is a local unitary only on the algorithm's register, and $\compressO$ is the compressed oracle query. We are interested in the probability of observing a collision in $D$, i.e., the squared norm of the following (sub-normalized) state:

\begin{align*}
\ket \phi := \Lambda \, \compressO \, U_T \, \cdots \compressO \, U_2 \, \compressO \,  U_1 \ket 0 \otimes \ket \emptyset,
\end{align*}

where $\Lambda$ is a projection onto databases with at least one collision.

Feynman's interpretation of quantum mechanics (path integral), on a high level, postulates that the probability of an event (observing a collision) is given by the squared modulus of a complex number (as $\|\ket \phi\|$ above), and this amplitude is given by adding all paths contributing to the complex number.
Since our ultimate goal is to observe a collision within the database, the collision must occur as a result of one of the oracle queries $\compressO$. Therefore, we contemplate all potential pathways leading to a collision. For any $t \in \{1, 2, \ldots, T\}$, we define the following (sub-normalized) state:

\begin{align*}
\ket {\psi_t} := \underbrace{(\Lambda \, \compressO) \, U_T}_\textrm{$T$-th query} \, \underbrace{(\Lambda \, \compressO) \, U_{T-1}}_\textrm{$(T-1)$-th query}  \cdots \underbrace{(\Lambda \, \compressO) \, U_t}_\textrm{$t$-th query} \, \underbrace{(\mathbb{I}-\Lambda) \compressO \, U_{t-1}}_\textrm{$(t-1)$-th query}  \cdots \compressO \, U_2 \, \compressO \,  U_1 \ket 0 \otimes \ket \emptyset.
\end{align*}

The definition of $\ket{\psi_t}$ guarantees that, starting from the $t$-th query, the database register will always be supported on those databases containing collision.
Observe that $\ket \phi=\ket {\psi_1} + \ket {\psi_2} + \cdots + \ket {\psi_T}$.
Thus $\|\ket \phi\| \leq \|\ket {\psi_1}\| + \|\ket {\psi_2}\| + \cdots + \|\ket {\psi_T}\|$.
Then by showing $\|\ket {\psi_t}\| \lesssim \sqrt{t/N}$, one deduces $\|\ket \phi\|^2 \lesssim T^3/N$.

We can also treat the classical lazy sampling as a path integral, where we similarly define $\ket \phi$ (resp., $\ket {\psi_t}$) as the computation at the end (resp., after $t$ queries) projected onto databases with collisions. The only difference is that, all probabilities are summed directly in the classical case: $\|\ket \phi\|^2 = \|\ket {\psi_1}\|^2 + \|\ket {\psi_2}\|^2 + \cdots + \|\ket {\psi_T}\|^2 \lesssim T^2/N$. This is because in this path integral for the classical algorithm, the path decomposition $\ket{\psi_1},\ldots,\ket{\psi_T}$ are mutually orthogonal, for which we can use Pythagorean equation to replace the triangle inequality.

*Establishing the Security in the QBF Model.

Recall that $G_K$ is the salted collision finding problem.
The security of $G_K$ in the QBF model requires us to upper bound $\Pr[\As \text{ wins } G_K \,|\, \mathbf{W}]$, where $\As$ is a $T$-quantum-query algorithm and the event $\mathbf{W}$ can be achieved by an $ST$-quantum-query algorithm with a “non-negligible” probability.
We aim to show that the probability above is upper bounded by $O(T^3/N + S/K)$.

What does this conditioning enforce in the context of the compressed oracle? It implies that the database register does not start with $\ket \emptyset$, but rather as a superposition of databases. Moreover, since $\mathbf{W}$ can be achieved by an $ST$-quantum-query algorithm, according to the “local change” property, the database register will have non-zero support only over databases with at most $ST$ entries.  However, this condition alone is not sufficient to derive the desired bound.  Consider the following scenario: though every $\ket D$ with non-zero support has at most $ST$ entries, it exactly stores collisions for $ST/2$ distinct salts. In such a case, with a random challenge salt, the database with probability $ST/K$ consists of an answer for the salt even if $\As$ makes no further query.
Given this example, we further separate the probability:

\begin{align*}
\Pr[\As \text{ wins } G_K \,|\, \mathbf{W}] \leq \underbrace{\Pr[\As \text{ wins } G_K \,|\, \mathbf{W} \land \mathbf{E}]}_\textrm{(i)} + \underbrace{\Pr[\overline{\mathbf{E}}|\mathbf{W}]}_\textrm{(ii)},
\end{align*}

where $\mathbf{E}$ denotes the event that the database register contains $\ket D$ that stores collisions for at most $\widetilde{S} = 2 S \log N$ distinct salts. This idea of posing $\mathbf{E}$ was first proposed by Akshima, Guo, and Liu <cit.> in the context of classical Merkle-Damgård hash. We adapt it to the quantum setting, combining with the compressed oracle technique.

The term (i) follows closely to the ideas in the lower bound of the vanilla collision finding, with the distinction that the database register commences with databases satisfying the requirements outlined by both $\mathbf{W}$ and $\mathbf{E}$: each database has at most $ST$ entries and collisions for at most $\widetilde{S}$ salts. We show that (i) is $\lesssim T^3/N + \widetilde{S}/K$.

To bound the term (ii), we show that $\Pr[\overline{\mathbf{E}}] < (T^3/N)^{\widetilde{S}} \lesssim(1/N)^{2 S}$. Since we assumed $\Pr[\mathbf W]\ge(1/N)^S$, we now have $\Pr[\overline{\mathbf{E}}|\mathbf{W}] < \Pr[\overline{\mathbf{E}}] / \Pr[{\mathbf{W}}] < 1/N$.  Upon accomplishing this, we establish security in the QBF model, along with the non-uniform security for salted collision finding.  Please refer to <Ref> for more detail.

*Strong (Threshold) Direct Product Theorem in the Compressed Oracle.
Now we give more detail for the term (ii).
This final step involves bounding $\Pr[\overline{\mathbf{E}}]$. The probability corresponds to the following direct-product-type experiment:
there is a random oracle $f:[K] \times [M] \to [N]$ (simulated as a compressed oracle).
An algorithm makes at most $ST$ quantum queries and the objective is to make the database register contain collisions for at least $\widetilde{S}$ salts. We let $\Lambda^{\geq r}$ be a projection onto databases with collisions on at least $r$ salts and $\Lambda^{=r}$ projects onto database with collisions on exact $r$ salts. Then $\Pr[\overline{\mathbf{E}}]$ is the squared norm of the following (un-normalized) state:

\begin{align*}
\ket \phi :=\ & \Lambda^{\geq \widetilde{S}} \, \compressO \, U_{ST} \, \cdots \compressO \, U_2 \, \compressO \,  U_1 \ket 0 \otimes \ket \emptyset\\
=\ & \sum_{r\geq \widetilde{S}}\Lambda^{=r} \, \compressO \, U_{ST} \, \cdots \compressO \, U_2 \, \compressO \,  U_1 \ket 0 \otimes \ket \emptyset.
\end{align*}

We list all possible computation paths that lead to databases in $\Lambda^{=r}$ for some $r\ge \widetilde{S}$.
For every $\ket D \in \Lambda^{=r}$, following its evolution, there exists $\vz = (z_1, z_2, \ldots, z_{r})$ such that before the $z_i$-th query, there are $(i-1)$ salts having a collision that the database will not forget in the future;
right after the $z_i$-th query, there are $i$ salts having a collision that the database will not forget.
We denote the computation path by the state $\ket {\psi_\vz}$. Similar to the vanilla collision finding, for the case of databases in $\Lambda^{=r}$, it holds that

\begin{align*}
\Lambda^{=r}\ket \phi = \sum_\vz \ket {\psi_\vz}.
\end{align*}

Finally, we show that for every possible path $\vz$, the state $\ket {\psi_\vz}$ has a norm $\lesssim(T/N)^{r/2}$. This step necessitates a much more intricate analysis compared to bounding $\|\ket{\psi_{i}}\|$ in the vanilla case. When some salt obtains a collision in the database that will never be forgotten in the future, we must keep track of which salt $i$ it is, as well as how many queries / entries $q_i$ already exist for this particular salt. If we further split $\ket {\psi_\vz}$ into paths with all possible $(k_1, \ldots, k_r)$, $(q_1, \ldots, q_r)$ and still use the triangle inequality, we will not be able to obtain the desired bound. One of our novel and key ideas to finalize the proof in the direct product game is to show that all these paths have some form of orthogonality. We can leverage the orthogonality of all these cases[We only show that these paths are “approximately” orthogonal instead of perfectly orthogonal, and this suffices to conclude the result.], and show that we can use Pythagorean equation instead of triangle inequality to complete the proof, much like the path integral for classical algorithms.

Since the total number of $\vz$'s is $\binom{ST}{r}$, $\|\Lambda^{=r}\ket \phi\|^2 \lesssim \binom{ST}{r}^2 (T/N)^{r} \lesssim (T^3/N)^{r}$. By summing over every $r\ge \widetilde{S}$, we can conclude that $\|\ket \phi\|^2=\sum_{r\ge\widetilde{S}}\|\Lambda^{=r}\ket{\phi}\|^2\lesssim (T^3/N)^{r}$, from the summation of geometric series for the case of $T^3/N<1/2$.
More details on our strong (threshold) direct product theorem can be found in <Ref>.

§ PRELIMINARIES

For each positive integer $n$, we use $[n]$ to denote set $\{1,2,\ldots,n\}$.
We use $\mathbb{Z}$ to denote the set of integers, use $\mathbb{N}$ to denote the set of non-negative integers, and use $\mathbb{Z}_+$ to denote the set of positive integers.

For a distribution $\mu$, we use $x\sim\mu$ to denote a sample $x$ from $\mu$.
For a finite set $S$, we use $x\sim S$ to denote a uniformly random element $x$ from $S$.

For a complex number $x\in\mathbb{C}$, we denote its norm $|x|=(x\overline{x})^{1/2}$, where $\overline{x}$ is the conjugate of the complex number $x$. For a complex vector $\vx\in\mathbb{C}^n$ or a quantum state $\ket{\phi}=\sum_{i\in[n]}\alpha_i\ket{i}$, we denote the $\ell_2$-norm $\|\vx\|=|\vx|_2=(\sum_{i\in[n]}x_i\overline{x_i})^{1/2}$ and $\|\ket{\phi}\|=(\sum_{i\in[n]}\alpha_i\overline{\alpha_i})^{1/2}$.

We use the standard $O(\cdot), \Omega(\cdot), \Theta(\cdot)$ notation, and emphasize that in this paper they only hide universal positive constants that do not depend on any parameter.

We start by defining the game in the general oracle model, then instantiate it in various settings.

A game $G$ is described by an oracle distribution $\mu$ over functions $f\colon[M]\to[N]$,[Throughout the paper, we assume that oracles are functions with domain $[M]$ and range $[N]$ where the actual $M$ and $N$ may change under different contexts. This is without loss of generality due to the flexibility of $\mu$.] a challenge distribution $\pi_f$ specified by each possible oracle $f$ from $\mu$, and an accepting outcome set (aka predicate) $\mc{R}_{f,\ch}$ specified by each possible oracle $f$ from $\mu$ and each possible challenge from $\pi_f$.

We say a query algorithm $\As$ wins the game given oracle access to $f$ and challenge $\ch$ if the output of $\As$ is in $\mc{R}_{f,\ch}$, i.e., $A^f(\ch) \in \mc{R}_{f,\ch}$.
The winning probability of $\As$ is then computed by

\Pr\left[\As^f(\ch)\in \mc{R}_{f,\ch}\right],

where the randomness is over $f\sim\mu$, $\ch\sim\pi_f$, and potentially the internal randomness of $\As$.

Note that in the above definition, $R_f$ is allowed to be empty, in which case the winning probability is simply zero.

During the analysis, we will need the oracle distribution conditioned on challenge. This naturally leads to the notion of plain games: games without any challenge.

A plain game $G$ is described by an oracle distribution $\mu$ and an accepting outcome set $\mc{R}_f$.
The winning probability of a query algorithm is defined similarly as in <Ref>.

Since games with or without challenge can be distinguished by whether there is a challenge distribution, we will address both of them as games for convenience when context is clear.

Given a game $G=(\mu,\{\pi_f\},\{\mathcal{R}_{f,\ch}\})$ and a possible challenge $\ch$, we use $G_\ch=(\mu_\ch,\{\mathcal{R}_{f,\ch}\})$ to denote the plain game of $G$ conditioned on $\ch$, where $\mu_\ch$ is the oracle distribution conditioned on the challenge being $\ch$.

We also have the following easy fact.

$\mu=\E_\ch[\mu_\ch]$, where $\ch$ is sampled from $\pi_f$ for $f\sim\mu$.

*Optimal Winning Probabilities.
We start by defining the optimal winning probabilities for uniform and non-uniform query algorithms.
Let $G$ be a game and $S,T\in\mathbb{N}$.

* Classical Uniform Game.
In this case, $\As$ is a classical query algorithm with at most $T$ queries given challenge $\ch$ (if not plain) and classical oracle access to $f$. A classical oracle query to $f\colon[M]\to[N]$ is specified by a coordinate $x\in[M]$ and gets in return the value $f(x)\in[N]$.

We use $\epsC_G(T)$ to denote the maximal winning probability of such algorithms.

* Classical Non-Uniform Game.
In this case, $\As$ is still limited to at most $T$ classical queries to $f$.
With classical non-uniform power, $\As$ now additionally receives an $S$-bit advice string $\sigma_f$ that can depend arbitrarily on $f$ (but not on the challenge $\ch$).
We use $\As^f(\sigma_f,\ch)$ (or $\As^f(\sigma_f)$ if plain) to explicitly denote that $\As$ takes the non-uniform advice as a separate input.

We use $\epsC_G(S,T)$ to denote the maximal winning probability of such algorithms.

* Quantum Uniform  Game. Here, $\As$ is a $T$-quantum-query algorithm. In this paper, we are only interested in the case when $f$ is a uniformly random oracle. More details are provided in <Ref>.

We use $\epsQ_G(T)$ to denote the maximal winning probability of such quantum algorithms.

* Quantum Non-Uniform Game. Here, $\As$ is a $T$-quantum-query algorithm, with an additional piece of advice $\sigma_f$. In the quantum case, we consider the most general case: the advice $\sigma_f$ has $S$ qubits and can arbitrarily depend on $f$.

We use $\epsQ_G(S,T)$ to denote the maximal winning probability of such non-uniform quantum algorithms.

Since the challenges are explicitly provided to the algorithm, the optimal winning probabilities for uniform algorithms are equivalent for a game and the corresponding challenge-conditioned games.

Let $G=(\mu,\{\pi_f\},\{\mathcal{R}_{f,\ch}\})$ be a game.
Then $\epsC_G(T)=\E_\ch[\epsC_{G_\ch}(T)]$.

*Salted Games.
Salting is a generic way to restrict non-uniform power. The method appends a piece of random data (aka salt) to inputs fed into a hash function (or more generally, an oracle); and the game will be now played under the random data.

Let $G$ be a game (see <Ref>) specified by $(\mu,\{\pi_f\}_f,\{\mc{R}_{f,\ch}\}_{f,\ch})$.

For each $K \in \mathbb{Z}_+$, we define the salted game $G_K$ as follows:

* The oracle distribution $\mu_K$ is over functions $g\colon[KM] \to [N]$. We identify $[KM]$ as $[K]\times[M]$ and $g=(f_1,\ldots,f_K)$ where each $f_i\colon[M]\to[N]$. The distribution $\mu_K$ is generated by independently sampling $g(i,\cdot)=f_i\sim\pi$ for each $i\in[K]$.

* For each possible oracle $g=(f_1,\ldots,f_K)$ from $\mu_K$, the challenge $\ch=(k,\ch_k)\sim\pi_g$ is produced by first picking a uniformly random $k\sim[K]$, then sampling $\ch_k\sim\pi_{f_k}$.

* For each possible oracle $g=(f_1,\ldots,f_K)$ from $\mu_K$ and challenge $\ch=(k,\ch_k)$ from $\pi_g$, the accepting outcome set $\mc{R}_{g,\ch}$ is defined as $\mc{R}_{f_k,\ch_k}$.

Intuitively, the game $G_K$ samples $K$ independent copies $f_1,\ldots,f_K$ from $\mu$ as a joint oracle, then samples a uniformly random one $f_k$ for the challenge, followed by a concrete challenge $\ch_k$ from $\pi_k$ and the corresponding accepting outcome set $\mc{R}_{f_k,\ch_k}$.
In order to win this game, the algorithm $\As$ needs to output a valid answer for $\mc{R}_{f_k,\ch_k}$.

Note that the definition of optimal winning probabilities carries over. In particular, our goal for the classical setting is to relate $\epsC_G(T)$ and $\epsC_{G_K}(S,T)$. We similarly want to relate $\epsQ_G(T)$ and $\epsQ_{G_K}(S,T)$ in the quantum random oracle model.

*Useful Inequalities.
<Ref> is a moment bound for the number of distinct elements in a draw-with-replacement experiment. Its proof can be found in <Ref>.

Let $K,L\in\mathbb{Z}_+$.
Sample $k_1,\ldots,k_L\sim[K]$ independently and let $\ell$ be the number of distinct elements in $k_1,\ldots,k_L$.
Then for any $c\ge0$, we have

\E[c^\ell]\le\left(c+\frac LK\right)^L.

<Ref> is a simple counting argument and the estimate follows directly from Stirling's formula, i.e. $a!>(a/e)^a$ for $a\in\mathbb{Z}_{+}$.

For $K,L\in\mathbb{Z}_+$, we have

\left|\left\{n_1,\ldots,n_K\in\mathbb N\colon n_1+\cdots+n_K=L\right\}\right|
\le\begin{cases}
(2e\cdot K/L)^L & L\le K,\\
(2e\cdot L/K)^K & L\ge K.
\end{cases}

§ NON-UNIFORM SECURITY OF SALTING: THE CLASSICAL SETTING

In this section, we prove the non-uniform security of salting in the classical case: we upper bound the advantage of an adversarial classical algorithm against salted oracles with the help of advice strings.

Let $G$ be a game and let $G_K$ be the salted game for $K\in\mathbb{Z}_+$.
Then for any $S,T\in\mathbb N$, we have

\epsC_{G_K}(S,T)\le\min_{L\in\mathbb{Z}_+}2^{S/L}\cdot\left(\epsC_G(T)+\frac LK\right).

Since we do not assume any structure of $G$ in <Ref> and its bound does not depend on specific range parameters in $G$, this result is general enough to handle any kind of classical query model.

Let $f\colon[N]\to[M]$ be the oracle for $G$.
Let $\mathcal{Q}$ be the set of allowed queries, e.g., bit query (each time queries some $i$-th bit of some $f(x)$), word query (each time queries some $f(x)$, which is the query model we use here), majority query (each time queries the majority of $\{f(x)\colon x\in S\}$ for some $S\subseteq[N]$), and so on.
Let $\mathcal S$ be the range of the possible answers of queries in $\mathcal Q$.

Then we can view each oracle $f$ as a function $f_{\mathcal{Q}}\colon\mathcal{Q}\to\mathcal S$.
In particular, $f_{\mathcal Q}(q)$ returns the query answer on $f$ given a query $q\in\mathcal Q$.
Then the allowed query $\mathcal Q$ on $f$ becomes the word query on $f_{\mathcal Q}$.
Therefore, we can simply treat $f_{\mathcal Q}$ as the oracle in the game $G$, change the accepting outcome set accordingly, and apply <Ref>.[One subtlety here is that $f$ and $f_{\mathcal{Q}}$ may not be a one-to-one correspondence. Though $f$ defines $f_{\mathcal Q}$, it is possible that the answers to the queries does not uniquely identify the oracle. In this case, the distribution of $f_{\mathcal Q}$ is properly induced the distribution of $f$ and the predicate (aka accepting outcome set) will be probabilistic given $f_{\mathcal Q}$ ans algorithm's output. The argument still works out with minor changes and we leave this as an exercise for interested readers.]

Though <Ref> is generally tight (see <Ref>), it can be further strengthened in some setting.
Intuitively, if the game has numerous possible challenges, one cannot store sufficient amount of answers to cover all the challenges, especially given the presence of salts.
In other words, answers in a look-up table need to not only specify the salt, but also specify the exact challenge corresponding to the answer.

Given the above intuition, in <Ref> we modify the proof of <Ref> to get a different estimate, which improves <Ref> when there are many possible challenges. We also explicitly compute some examples to demonstrate the tightness.

The strategy to prove <Ref> is as follows:
let $g$ be the salted oracle sampled from $g\sim\mu_K$.

* We first relate the success probability of winning a single challenge $\ch\sim\pi_g$ to the success probability of winning independent challenges $\ch_1,\ldots,\ch_L\sim\pi_g$.

* Then we show that the $S$-bit advice string does not boost the winning probability much when we have multiple independent challenges in the sense that a random string of $S$-bit can be taken as the advice.

* Now that the advice string is substituted by a random string independent of $g$, we only need to bound the winning probability of a uniform query algorithm against multiple independent challenges. This will be handled by a direct product theorem.

One can view the direct product theorem as a type of concentration results, where one analyze the high order advantages of algorithms.
This reduction from non-uniform security to uniform security with concentration is analogous to earlier works of Impagliazzo and Kabanets <cit.>, and has been revived in recent works <cit.>.

We emphasize that the most general direct product theorems <cit.> incur a necessary loss in parameters and cannot produce sharp bounds that <Ref> needs.
Instead, we exploit the memoryless property of our algorithms and show a strong direct product theorem for this class of algorithms.

Let $G$ be specified by $(\mu,\{\pi_f\}_f,\{\mathcal{R}_{f,\ch}\}_{f,\ch})$.
Recall <Ref> and <Ref>. The game $G_K$ samples $K$ independent copies of $G$ and focuses on a uniformly random one of them.
As such, let $f_1,\ldots,f_K\sim\mu$ and $k\sim[K]$ be independent, then $g=(f_1,\ldots,f_K)$ is the joint oracle sampled from $\mu_K$ for $G_K$.
Let $\ch_k\sim\pi_{f_k}$, then $\ch=(k,\ch_k)$ is the challenge sampled from $\pi_g$ for $G_K$.

Fix an arbitrary $L\in\mathbb{Z}_+$.
Let $\As$ be an arbitrary non-uniform query algorithm for $G_K$ that takes an $S$-bit advice string $\sigma_g$ and makes at most $T$ queries to $g$.
Then the winning probability of $\As$ is $\Pr\left[\As^g(\sigma_g,\ch)\in\mathcal{R}_{g,\ch}\right]$, where $\mathcal{R}_{g,\ch}=\mathcal{R}_{f_k,\ch_k}$.
Since we only make classical queries, oracle access to $g$ is equivalent to oracle access to $f_1,\ldots,f_K$ separately.
Therefore it suffices to prove

\begin{equation}\label{eq:thm:classical_salt_1}
\Pr_{\substack{f_1,\ldots,f_K\\k,\ch_k}}\left[\As^{f_1,\ldots,f_K}(\sigma_g,k,\ch_k)\in\mathcal{R}_{f_k,\ch_k}\right]\le2^{S/L}\cdot\left(\epsC_G(T)+\frac LK\right),
\end{equation}

where we assume that $\As$ is a deterministic query algorithm given $\sigma_g,k,\ch_k$ by fixing the optimal randomness.

To remove the non-uniform advice from the LHS of <Ref>, we use a tensor trick.
Let challenges $(k_1,\ch_{k_1}),\ldots,(k_L,\ch_{k_L})\sim\pi_g$ be independent copies of $(k,\ch_k)$.
Then for any fixed $g$ (i.e., $f_1,\ldots,f_K$), the advice $\sigma_g$ is also fixed and we have

\Pr_{(k_i,\ch_{k_i}),i\in[L]}\left[\As^{f_1,\ldots,f_K}(\sigma_g,k_i,\ch_{k_i})\in\mathcal{R}_{f_{k_i},\ch_{k_i}},\forall i\in[L]\right]

\begin{align*}
\text{LHS of \Cref{eq:thm:classical_salt_1}}
\notag\\
\tag{by convexity}\\
&=\Pr_{\substack{f_1,\ldots,f_K\\(k_i,\ch_{k_i}),i\in[L]}}\left[\As^{f_1,\ldots,f_K}(\sigma_g,k_i,\ch_{k_i})\in\mathcal{R}_{f_{k_i},\ch_{k_i}},\forall i\in[L]\right]^{1/L}.
\end{align*}

Now observe that if $\sigma_g$ is replaced by a uniformly random string $\sigma\sim\{0,1\}^S$, then $\sigma$ still has a probability of $2^{-S}$ to be identical with $\sigma_g$, from which we recover the true non-uniform algorithm.
Putting this into the above calculation, we have

\begin{align}
\text{LHS of \Cref{eq:thm:classical_salt_1}}
&\le\left(2^S\cdot\Pr_{\substack{f_1,\ldots,f_K\\(k_i,\ch_{k_i}),i\in[L]\\\sigma\sim\{0,1\}^S}}\left[\As^{f_1,\ldots,f_K}(\sigma,k_i,\ch_{k_i})\in\mathcal{R}_{f_{k_i},\ch_{k_i}},\forall i\in[L]\right]\right)^{1/L}
\notag\\
&\le2^{S/L}\cdot\Pr_{\substack{f_1,\ldots,f_K\\(k_i,\ch_{k_i}),i\in[L]}}\left[\Bs^{f_1,\ldots,f_K}(k_i,\ch_{k_i})\in\mathcal{R}_{f_{k_i},\ch_{k_i}},\forall i\in[L]\right]^{1/L},
\label{eq:thm:classical_salt_2}
\end{align}

where $\Bs$ is a uniform $T$-query algorithm obtained by fixing the optimal choice of $\sigma$ for $\As$.

For each possible $(k_1,\ldots,k_L)$, we fix an arbitrary[For example, if $(k_1,k_2)=(1,2)$, then $U=\{1,2\}$; if $(k_1,k_2)=(1,1)$, then $U$ can be either $\{1\}$ or $\{2\}$.] $U\subseteq[L]$ such that $U$ contains indices of distinct salts in $k_1,\ldots,k_L$.
Note that $U$ is deterministic given $(k_1,\ldots,k_L)$.
Now we further analyze the RHS of <Ref>:

\begin{align}
&\Pr_{\substack{f_1,\ldots,f_K\\(k_i,\ch_{k_i}),i\in[L]}}\left[\Bs^{f_1,\ldots,f_K}(k_i,\ch_{k_i})\in\mathcal{R}_{f_{k_i},\ch_{k_i}},\forall i\in[L]\right]
\notag\\
\le&\Pr_{\substack{f_1,\ldots,f_K\\(k_i,\ch_{k_i}),i\in[L]}}\left[\Bs^{f_1,\ldots,f_K}(k_i,\ch_{k_i})\in\mathcal{R}_{f_{k_i},\ch_{k_i}},\forall i\in U\right]
\notag\\
=&\E_{\substack{U\\(k_i,\ch_{k_i}),i\in U}}\left[\Pr_{f_1,\ldots,f_K}\left[\Bs^{f_1,\ldots,f_K}(k_i,\ch_{k_i})\in\mathcal{R}_{f_{k_i},\ch_{k_i}},\forall i\in U\middle|U,\{(k_i,\ch_{k_i})\}_{i\in U}\right]\right].
\label{eq:thm:classical_salt_3}
\end{align}

Observe that $(U,\{k_i\}_{i\in U})$ is independent from $(f_1,\ldots,f_K)$ and each $\ch_{k_i}$ only distorts the distribution of $f_{k_i}$ from $\mu$ to $\mu_{\ch_{k_i}}$ (recall <Ref>).
Hence, conditioned on $(U,\{(k_i,\ch_{k_i})\}_i)$, the oracles $f_1,\ldots,f_K$ are still independent; and in particular, $f_{k_i}$ has distribution $\mu_{\ch_{k_i}}$ for $i\in U$ and other oracles have marginal distribution $\mu$.
Therefore, the RHS of <Ref> can be simplified as

\begin{align}\label{eq:thm:classical_salt_4}
\E_{\substack{U\\(k_i,\ch_{k_i}),i\in U\\f_j\sim\mu,j\notin\{k_i\colon i\in U\}}}\left[\Pr_{f_{k_i}\sim\mu_{\ch_{k_i}},i\in U}\left[\Bs^{f_1,\ldots,f_K}(k_i,\ch_{k_i})\in\mathcal{R}_{f_{k_i},\ch_{k_i}},\forall i\in U\right]\right].
\end{align}

We will prove the following claim by a strong direct product theorem in <Ref>.

For any fixed $(U,\{(k_i,\ch_{k_i})\}_i,\{f_j\}_j)$, we have

\Pr_{f_{k_i}\sim\mu_{\ch_{k_i}},i\in U}\left[\Bs^{f_1,\ldots,f_K}(k_i,\ch_{k_i})\in\mathcal{R}_{f_{k_i},\ch_{k_i}},\forall i\in U\right]
\le\prod_{i\in U}\epsC_{G_{\ch_{k_i}}}(T).

Assuming <Ref>, we can upper bound <Ref>:

\begin{align*}
\E_{\substack{U\\(k_i,\ch_{k_i}),i\in U\\f_j\sim\mu,j\notin\{k_i\colon i\in U\}}}\left[\prod_{i\in U}\epsC_{G_{\ch_{k_i}}}(T)\right]
&=\E_{\substack{U\\k_i,i\in U}}\left[\E_{\ch_{k_i},i\in U}\left[\prod_{i\in U}\epsC_{G_{\ch_{k_i}}}(T)\right]\right]\\
&=\E_{\substack{U\\k_i,i\in U}}\left[\prod_{i\in U}\E_{\ch_{k_i}}\left[\epsC_{G_{\ch_{k_i}}}(T)\right]\right]
\tag{by independence}\\
&=\E_{\substack{U\\k_i,i\in U}}\left[\prod_{i\in U}\epsC_G(T)\right]=\E_U\left[\epsC_G(T)^{|U|}\right]
\tag{by \Cref{fct:opt_game_cond}}\\
&\le\left(\epsC_G(T)+\frac LK\right)^L.
\tag{by \Cref{lem:draw_with_repl}}
\end{align*}

Combining with <Ref> and <Ref>, this establishes <Ref> and thus concludes the proof of <Ref>.

§.§ Strong Direct Product Theorems for Memoryless Algorithms

In this section, we will present the strong direct product theorem we use in <Ref>. This theorem was proved within the context of classical complexity theory in a much earlier work by Nisan, Rudich, and Saks <cit.>.
While we only became aware of their work after the completion of our paper, we do not consider our analysis in <Ref> as our technical contribution, and we prove the theorem here within our model for completeness.

We start by defining the direct product of games.

Let $G_1,\ldots, G_k$ be $k$ plain games specified by $\mu_1,\ldots, \mu_k$ and collections of predicates $\mc{R}_{1,f_1}, \ldots, \mc{R}_{k,f_k}$.
The direct product of these games is denoted by $G^\times = G_1 \times G_2 \times \cdots \times G_k$ with $\mu^\times = \mu_1 \times \mu_2 \times \cdots \times \mu_k$ and predicate $\mc{R}^\times_{f_1, \ldots, f_k} = \mc{R}_{1, f_1} \times \cdots \times \mc{R}_{k, f_k}$.

The probability that a query algorithm $\As$ wins $G^\times$ is $\Pr\left[ \As^{f_1, \ldots, f_k} \in \mc{R}_{1, f_1} \times \cdots \times \mc{R}_{k, f_k} \right]$, where $\As$ can make queries to any $f_1,\ldots,f_k$.
The direct product theorem intuitively says that the winning probability of $kT$-query algorithms for $G^\times$ should be roughly the product of the winning probabilities of $T$-query algorithms for each $G_i$.

To capture the algorithms in <Ref>, we focus on memoryless algorithms for direct product of games. In these algorithms, the workspace is repeatedly refreshed, which forbids long-range computation.

Let $G^\times = G_1\times \cdots \times G_k$ be a direct product of games.
A query algorithm $\As$ for $G^\times$ is memoryless if it is deterministic[The assumption about being deterministic is not necessary as one can fix the randomness of the algorithm. However assuming so is easier for our analysis.] and there exist query algorithms $\As_1, \ldots, \As_k$ such that $\As^{f_1, \ldots, f_k} \equiv \As_1^{f_1, \ldots, f_k}, \ldots, \As_k^{f_1, \ldots, f_k}$.
That is, $\As$ runs $\As_1, \ldots, \As_k$ sequentially for $\mathcal{R}_{1,f_1},\ldots,\mathcal{R}_{k,f_k}$ and does not share memory between two executions.
Moreover, we say $\As$ is $(T_1,\ldots, T_k)$-memoryless if each $\As_i$ makes at most $T_i$ queries.

Note that, while $(T_1,\ldots,T_k)$-memoryless algorithms are guaranteed to make at most $T_i$ queries for each predicate $\mathcal{R}_{i,f_i}$, the queries can be interlaced and highly dependent on the query history.
Therefore, it is generally not the case that a $(T_1,\ldots,T_k)$-memoryless algorithm would simply execute a $T_1$-query algorithm on $f_1$, followed by a $T_2$-query algorithm on $f_2$, and so on.
However, as shown in <Ref>, this special strategy turns out to be optimal.

Let $G^\times = G_1\times \cdots \times G_k$ be a direct product of games.
If $\As$ is a $(T_1,\ldots,T_k)$-memoryless algorithm for $G^\times$, then its winning probability is at most $\prod_{i=1}^k \epsC_{G_i}(T_i)$.

Given <Ref>, we can easily deduce <Ref>.

With $(U,\{(k_i,\ch_{k_i})\}_i,\{f_j\}_j)$ fixed, each $\Bs^{f_1,\ldots,f_K}(k_i,\ch_{k_i})$ is a deterministic $T$-query algorithm on $\{f_{k_i}\}_i$.
Overall, they form a $(T,\ldots,T)$-query algorithm to solve challenge-conditioned games $\{G_{\ch_{k_i}}\}_i$ in a memoryless way.
Hence the desired bound follows from <Ref>.

To prove <Ref>, we will convert memoryless algorithms to another special type of algorithms for which strong direct product theorems are easier to establish.

Let $G^\times = G_1\times \cdots \times G_k$ be a direct product of games. We say a query algorithm $\As$ for $G^\times$ is $(T_1, \ldots, T_k)$-fair if it is deterministic[The assumption about being deterministic is not necessary as one can fix the randomness of the algorithm. However assuming so is easier for our analysis.] and makes at most $T_i$ queries to each $f_i$ in any execution.

We emphasize that a $(T_1,\ldots,T_k)$-fair algorithm does not need to be memoryless.
Moreover, the queries to different oracles can be mixed up as well.
Therefore, fair algorithms and memoryless algorithms are incomparable.
By an induction on the total number of queries, one can prove a sharp direct product theorem for fair algorithms <cit.>.

Let $G^\times = G_1\times \cdots \times G_k$ be a direct product of games.
If $\As$ is a $(T_1, \dots, T_k)$-fair algorithm for $G^\times$, then its winning probability is at most $\prod_{i=1}^k \epsC_{G_i}(T_i)$.

We remark that <cit.> proves for the case where $T_1=\cdots=T_k$ and each $G_i$ is a decision game (i.e., each $\mathcal{R}_{i,f_i}$ is a singleton set of a binary bit). However the proof can be extended to our setting with minimal changes.
We also note that Drucker <cit.> gives an alternative proof using martingale analysis, which generalizes beyond fair algorithms with a necessary loss on the bounds.

In light of <Ref> and to prove <Ref>, it suffices to present a reduction from memoryless algorithms to fair algorithms which we present below. Note that <Ref> follows immediately by the combination of <Ref> and <Ref>.

Let $G^\times = G_1\times \cdots \times G_k$ be a direct product of games.
Let $\As$ be any $(T_1, \ldots, T_k)$-memoryless algorithm for $G^\times$. Then there exists a $(T_1, \ldots, T_k)$-fair algorithm $\Bs$ with winning probability at least the winning probability of $\As$.

To prove <Ref>, we will frequently use the notion of partial assignments.

Any string $u \in ([M] \cup \{*\})^N$ is a partial assignment for functions of range $[M]$ and domain $[M]$.
For a function $f\colon[M] \to [N]$, we say it is consistent with $u$ (or $f \lhd u$) if $f(x) = u_x$ holds for any $x$ that $u_x\neq*$.

Now we present the reduction and prove <Ref>.

Assume without loss of generality that the oracle of each game $G_i$ is a function from $[M]$ to $[N]$.
Recall <Ref>. There exists $k$ algorithms $\As_1, \ldots, \As_k$, each making at most $T_1,\ldots,T_k$ queries respectively and $\As$ executes as follows:

Algorithm: The memoryless algorithm $\As$

* $\As$ executes the algorithm one by one:

* It runs $\As_1$ and obtains an output $e_1$;

* It runs $\As_2$ and obtains an output $e_2$;

k. It runs $\As_k$ and obtains an output $e_k$.

* Eventually, $\As$ outputs $e_1,\ldots, e_k$.

Since all the algorithms $\As_1, \ldots, \As_k$ commute with each other, $\As$ can run an “out-of-order execution” of them, so long as the query order within the same algorithm $\As_i$ does not change.
More precisely, the following algorithm $\widetilde{\As}$ has the same output distribution as $\As$:

Algorithm: The “out-of-order execution” algorithm $\widetilde{\As}$

* $\widetilde{\As}$ initializes $\As_1, \ldots, \As_k$, each $\As_i$ makes no query yet.

* As long as there exists $j \in [k]$ such that $\As_j$ has not terminated yet.

* $\widetilde{\As}$ picks a subset $\mc{J} \subseteq [k]$, where $\As_j$ has not terminated for every $j \in \mc{J}$.

* For each $j\in\mc J$, it runs $\As_j$ by one query further.

* $\widetilde{\As}$ outputs the results $e_1,\ldots,e_k$ of $\As_1, \ldots, \As_k$.

The subset $\mc J$ constructed by $\widetilde{\As}$ at Step 1 can be arbitrary and adaptive. Before presenting its construction, we note the following important observation.

Assume $\As_j$ terminates at some stage of $\widetilde{\As}$. Let $u$ be the partial assignment of $f_j$ that $\widetilde{\As}$ learned so far. Consider the following two cases:

* The real execution. $\widetilde{\As}$ finishes the rest of its execution with the real $f_j$. Let the winning probability in the case be $p$.

* The simulated execution. Given $u$, $\widetilde{\As}$ picks some function $f'_j$ consistent with $u$ and finishes the rest of its execution with the fake $f'_j$. Let the winning probability in the case be $p'$.

Then there always exists a choice of $f'_j$ such that $p' \geq p$.

Without loss of generality assume $j = 1$. Since $\As_1$ already terminates, its outcome $e_1$ is fixed. We have

\begin{align*}
p = \sum_{f_1 \lhd u} [e_1 \in \mathcal{R}_{1, f_1}] \cdot \Pr_{f \sim \mu_1^{(u)}}[f = f_1] \cdot \Pr_{f_2, \ldots, f_k}\left[ \As_2, \ldots, \As_k \text{ win} \middle| f_1 \right],
\end{align*}

where $[e_1 \in \mathcal{R}_{1, f_1}]$ is the binary indicator.
On the other hand, we have

\begin{align*}
p' = \sum_{f_1 \lhd u} [e_1 \in \mathcal{R}_{1, f_1}] \cdot \Pr_{f \sim \mu_1^{(u)}}[f = f_1]  \cdot \Pr_{f_2, \ldots, f_k}\left[ \As_2, \ldots, \As_k \text{ win} \,|\, f'_1 \right].
\end{align*}

Therefore, we can pick $f'_1 := {\sf argmax}_{f_1 \lhd u} \Pr_{f_2, \ldots, f_k}\left[ \As_2, \ldots, \As_k \text{ win} \,|\, f_1 \right]$ and then $p' \geq p$.

With the above observation, we now consider the following algorithm $\Bs$ that is almost identical to $\widetilde{\As}$ except that whenever some $\As_j$ terminates, it picks a function $f_j'$ consistent with the partial assignement learned so far and runs the rest of the protocol using $f'_j$.
By <Ref>, $\Bs$ wins with probability at least that of $\widetilde{\As}$.

Algorithm: The algorithm $\Bs$

* $\Bs$ initializes $\As_1, \ldots, \As_k$, each $\As_i$ makes no query yet.

* As long as there exists $j \in [k]$ such that $\As_j$ has not terminated yet.

* $\Bs$ picks a subset $\mc{J} \subseteq [k]$, where $\As_j$ has not terminated for every $j \in \mc{J}$.

* For every $j \in \mc{J}$, it runs $\As_j$ by one query further.

If $\As_j$ terminates, $\Bs$ picks $f'_j$ (as in <Ref>). In the rest of the execution, whenever $f_j$ is queried, $\Bs$ uses $f'_j$.

* $\Bs$ outputs the results of $\As_1, \ldots, \As_k$.

Finally, we show that there exists a way of picking $\mc{J}$ such that at every stage and for each $i\in[k]$, the number of queries to $f_i$ is at most the number of queries made by $\As_i$.
This is in general not true, for instance $\As_1$ and $\As_2$ can make all their $T_1+T_2$ queries to $f_1$.
However by the reduction above and the memoryless property, we can now rearrange queries by carefully designing $\mc J$ to avoid these cases.

There exists a strategy of picking $\mc{J}$ such that at any stage and for each $i\in[k]$, we have $t_i\le q_i$, where $q_i$ is the number of queries made by $\As_i$ and $t_i$ be the number of queries made to (the real) $f_i$.

A direct consequence of the above lemma is that, when we use the strategy to pick $\mc{J}$ for $\Bs$, it becomes a fair algorithm since $t_i \leq q_i \leq T_i$.

We prove the statement by induction. It is obviously true at the initialization stage where $t_i = q_i = 0$ for every $i \in [k]$.

For inductive hypothesis, assume that each $\As_i$ already makes $q_i$ queries and each $f_i$ gets queried $t_i$ times with $t_i \leq q_i$.
For the next stage, we define a directed graph $(V, E)$ as follows:

* Let $V\subseteq[k]$ be the set of $\As_i$'s that has not terminated yet.

* For every $r \in V$,

* if $A_r$ makes the next query to $f_v$ and $v \in V$, then a direct edge $\langle r, v \rangle \in E$;

* otherwise $A_r$ makes the next query to $f_v$ and $v \not\in V$, then no edge will be added.

Since $v \not\in V$ means $\As_v$ already terminates and thus every query to $f_v$ will be directed to the simulated oracle $f'_v$ constructed by <Ref>.

Observe that every node in the graph has out-degree at most one and $V\neq\emptyset$.
We complete the proof of <Ref> by the following case analysis.

*There exists as a directed cycle.
If $r_1\to r_2\to\cdots\to r_\ell\to r_1$ forms a directed cycle, then we define $\mc{J} = \{r_1,\ldots, r_\ell\}$. Therefore each $\As_{r_i}$ will make a query and each function $f_{r_i}$ gets one more query. The induction hypothesis holds.

*There is no directed cycle.
Then there exists a direct path $r_1\to r_2\to\cdots\to r_\ell$ where $\ell\ge1$.
Assume $A_{r_\ell}$ makes the next query to $f_{v_\ell}$.
Since $r_\ell$ is the endpoint of the path, we know that $\As_{v_\ell}$ already terminates and we have replaced $f_{v_\ell}$ with the simulated oracle $f_{v_\ell}'$ by <Ref>.

Now let $\mc{J} = \{r_1, \ldots, r_\ell\}$. Each $\As_{r_i}$ makes a new query, and functions $f_{r_2}, \ldots, f_{r_\ell}$ get one more query respectively.
Note that $f_1$ is not queried and the query of $\As_{r_\ell}$ is simulated by $f_{v_\ell}'$ without querying the actual oracles. Thus, the induction hypothesis holds.

By <Ref>, the algorithm $\Bs$ is indeed $(T_1,\ldots,T_k)$-fair.
Then <Ref> guarantees that $\Bs$ has at least the winning probability as that of $\As$, which completes the proof of <Ref>.

§.§ Improved Estimates for Games with Numerous Challenges

In this section, we provide an alternative way of analyzing the RHS of <Ref>, which implies improved bounds for games with numerous challenges.

For a game with challenge, we define the multi-challenge version of it by asking the algorithm to solve multiple independent challenges.
Note that the repetition here is on challenges instead of salts.

Let $G$ be a game specified by $(\mu,\{\pi_f\}_f,\{\mathcal{R}_{f,\ch}\}_{f,\ch})$.
For each $n\in\mathbb N$, we define the multi-challenge game $G^n$ as follows:

* The oracle distribution is the same $\mu$.

* For each possible oracle $f$ from $\mu$, the challenge $\ch=(\ch^1,\ldots,\ch^n)$ is produced by sampling independent $\ch^1,\ldots,\ch^n\sim\pi_f$.

* For each possible oracle $f$ and challenge $\ch=(\ch^1,\ldots,\ch^n)$, the accepting outcome set $\mathcal{R}_{f,\ch}=\mathcal{R}_{f,\ch^1}\times\cdots\times\mathcal{R}_{f,\ch^n}$.

In other words, the algorithm needs to output accepting configuration for each challenge.

We remark that if $n=0$, then the multi-challenge game $G^0$ is a trivial game.

Note that the definition of optimal winning probabilities carries over.
In particular, $\epsC_{G^n}(nT)$ refers to the optimal winning probability of a $nT$-query classical algorithm for the multi-challenge game $G^n$.
Oftentimes, $\epsC_{G^n}(nT)^{1/n}$ is a good upper bound for the non-uniform security of $G$ against algorithms with $n$-bit advice and $T$ queries (see e.g., <cit.>).

Using this notion, we provide the following variant of <Ref> and then instantiate it on the function / permutation inversion problem (see e.g., the survey by Corrigan-Gibbs and Kogan <cit.>).

Let $G$ be a game and let $G_K$ be the salted game for $K\in\mathbb{Z}_+$.
Then for any $S,T\in\mathbb N$, we have

\epsC_{G_K}(S,T)\le\min_{L\in\mathbb{Z}_+}2^{S/L}\cdot\left(\frac{L!}{K^L}\sum_{\substack{n_1,\ldots,n_K\in\mathbb N\\n_1+\cdots+n_K=L}}\prod_{k=1}^K\frac{\epsC_{G^{n_k}}(n_kT)}{n_k!}\right)^{1/L}.

The argument deviates from the proof of <Ref> on the analysis of the RHS of <Ref>.
We will prove the following alternative bound which completes the proof of <Ref>:

\begin{equation}\label{eq:thm:classical_salt_mult_1}
\Pr_{\substack{f_1,\ldots,f_K\\(k_i,\ch_{k_i}),i\in[L]}}\left[\Bs^{f_1,\ldots,f_K}(k_i,\ch_{k_i})\in\mathcal{R}_{f_{k_i},\ch_{k_i}},\forall i\in[L]\right]
\le
\frac{L!}{K^L}\sum_{\substack{n_1,\ldots,n_K\in\mathbb N\\n_1+\cdots+n_K=L}}\prod_{k=1}^K\frac{\epsC_{G^{n_k}}(n_kT)}{n_k!}
\end{equation}

To establish <Ref>, for each $k\in[K]$ we define $n_k=|\left\{i\in[L]\colon k_i=k\right\}|$ to be the number of salt $k$'s appearances in $k_1,\ldots,k_L$.
Note that $n_1,\ldots,n_K$ depend only on $k_1,\ldots,k_L$.
Then the following procedure is equivalent to the LHS of <Ref>:

First sample $n_1,\ldots,n_K$ and $k_1,\ldots,k_L$.

For each $k\in[K]$, let $S_k\subseteq[L]$ of size $n_k$ be the appearances of salt $k$ in $k_1,\ldots,k_L$.

*  For each $k\in[K]$, we sample $f_k$ and execute the following subroutine:
for each $i\in S_k$, sample $\ch_{k_i}$ and execute $\Bs^{f_1,\ldots,f_K}(k,\ch_{k_i})$ to check if the outcome is in $\mathcal{R}_{f_k,\ch_{k_i}}$.

Recall that $\Bs$ is a $T$-query algorithm.
Therefore, conditioned on <Ref>, each subroutine in <Ref> is an $n_kT$-query algorithm aiming to solve the multi-challenge game $G^{n_k}=|S_k|$.
In particular, their combination is a memoryless algorithm.
Therefore we have the following result analogous to <Ref>.

Conditioned on <Ref>, <Ref> succeeds with probability at most $\prod_{k=1}^K\epsC_{G^{n_k}}(n_kT)$.

The reduction to <Ref> is similar to the proof of <Ref>.
We only remark that while <Ref> is proved for plain games (i.e., games without challenge), the same result naturally extends to games with challenge by conditioning on the challenge as in the proof of <Ref>.

Given <Ref>, we now verify <Ref>:

\begin{align*}
\text{LHS of \Cref{eq:thm:classical_salt_mult_1}}
\tag{by \Cref{clm:thm:classical_salt_mult}}\\
&=\sum_{\substack{n_1,\ldots,n_K\in\mathbb N\\n_1+\cdots+n_K=L}}\binom L{n_1,\ldots,n_K}\cdot\frac1{K^L}\cdot\prod_{k=1}^K\epsC_{G^{n_k}}(n_kT)\\
&=\sum_{\substack{n_1,\ldots,n_K\in\mathbb N\\n_1+\cdots+n_K=L}}\frac{L!}{K^L}\cdot\prod_{k=1}^K\frac{\epsC_{G^{n_k}}(n_kT)}{n_k!}
=\text{RHS of \Cref{eq:thm:classical_salt_mult_1}}
\tag*{\qedhere}
\end{align*}

Now we present a variant of <Ref> that is potentially easier to use and is in fact tight for the large advice regime (see <Ref>) and some specific important games (see <Ref>).

Let $G$ be a game and let $G_K$ be the salted game for $K\in\mathbb{Z}_+$.
Then for any $S,T\in\mathbb N$, we have

\epsC_{G_K}(S,T)\le 2e^2\cdot\min_{L\in\mathbb{Z}_+}2^{S/L}\max_{\substack{n_1,\ldots,n_K\in\mathbb N\\n_1+\cdots+n_K=L}}\sum_{k=1}^K\frac{\epsC_{G^{n_k}}(n_kT)^{1/n_k}}{\min\{K,L\}}.

For any fixed $n_1,\ldots,n_K$ with $n_1+\cdots+n_K=L$, we have

\begin{align}
\left(\prod_{k=1}^K\frac{\epsC_{G^{n_k}}(n_kT)}{n_k^{n_k}}\right)^{1/L}
\notag\\
\tag{by the weighted AM-GM inequality}\\
\label{eq:thm:classical_salt_mult_2}
\end{align}

where we note that $\epsC_{G^{n_k}}(n_kT)=1$ (and thus $\epsC_{G^{n_k}}(n_kT)^{1/n_k}=1$) if $n_k=0$.
Therefore for any fixed $L\in\mathbb{Z}_+$, we have

\begin{align*}
\epsC_{G_K}(S,T)
&\le2^{S/L}\cdot\left(\frac{L!}{K^L}\sum_{\substack{n_1,\ldots,n_K\in\mathbb N\\n_1+\cdots+n_K=L}}\prod_{k=1}^K\frac{\epsC_{G^{n_k}}(n_kT)}{n_k!}\right)^{1/L}
\tag{by \Cref{thm:classical_salt_mult}}\\
&\le2^{S/L}\cdot\left(\frac{L^L}{K^L}\sum_{\substack{n_1,\ldots,n_K\in\mathbb N\\n_1+\cdots+n_K=L}}\prod_{k=1}^K\frac{e^{n_k}\cdot \epsC_{G^{n_k}}(n_kT)}{n_k^{n_k}}\right)^{1/L}
\tag{since $a!\ge(a/e)^a$}\\
&\le e\cdot 2^{S/L}\cdot \frac LK\cdot\binom{L+K-1}{K-1}^{1/L}\cdot\max_{\substack{n_1,\ldots,n_K\in\mathbb N\\n_1+\cdots+n_K=L}}\left(\prod_{k=1}^K\frac{\epsC_{G^{n_k}}(n_kT)}{n_k^{n_k}}\right)^{1/L}\\
&\le e\cdot 2^{S/L}\cdot \frac LK\cdot\binom{L+K-1}{K-1}^{1/L}\cdot\max_{\substack{n_1,\ldots,n_K\in\mathbb N\\n_1+\cdots+n_K=L}}\sum_{k=1}^K\frac{\epsC_{G^{n_k}}(n_kT)^{1/n_k}}L.
\tag{by \Cref{eq:thm:classical_salt_mult_2}}
\end{align*}

By <Ref>, we know that if $L\le K$, then $\binom{L+K-1}{K-1}^{1/L}\le 2e\cdot \frac KL$ and

\epsC_{G_K}(S,T)\le 2e^2\cdot2^{S/L}\max_{\substack{n_1,\ldots,n_K\in\mathbb N\\n_1+\cdots+n_K=L}}\sum_{k=1}^K\frac{\epsC_{G^{n_k}}(n_kT)^{1/n_k}}L

and otherwise $L\ge K$, then $\binom{L+K-1}{K-1}^{1/L}\le (2e\cdot \frac LK)^{K/L} \le 2e$ and

\epsC_{G_K}(S,T)\le 2e^2\cdot2^{S/L}\max_{\substack{n_1,\ldots,n_K\in\mathbb N\\n_1+\cdots+n_K=L}}\sum_{k=1}^K\frac{\epsC_{G^{n_k}}(n_kT)^{1/n_k}}K

as desired.

To demonstrate the tightness of <Ref> and <Ref>, we consider the function / permutation inversion game $G$, for which an upper bound of $\epsC_{G^n}(nT)$ is known.

The function inversion game $\mathsf{Inv}$ is the following game:

* The oracle is a uniformly random function $f\colon[N]\to[N]$.

* The challenge $\ch$ is a uniformly random element in $[N]$.

* An answer $a\in[N]$ is an accepting configuration if $f(a)=\ch$.

The permutation inversion game can be similarly defined where the oracle is then a uniformly random permutation.[Since <Ref> holds for both function inversion game and permutation inversion game, we do not distinguish them here with extra notation. However we remark that <Ref> is known to be tight for permutation inversion, but conjectured not tight for function inversion. Strengthening the latter will establish the non-uniform security of function inversion, which is a long-standing open problem in cryptography with deep connections to circuit lower bounds and data structure lower bounds <cit.>.]

That is, an adversary wins $\mathsf{Inv}$ iff it successfully inverts a random point in a random function / permutation.
For our purpose, we quote a known upper bound on the multi-challenge version of $\mathsf{Inv}$ from <cit.>.

$\epsC_{\mathsf{Inv}^n}(nT)\le O\left(\frac{nT}N\right)^n$.

Plugging <Ref> into <Ref> and choosing $L=S$, we get the following immediate corollary, which gives another proof of the results in <cit.>.

For any $S,T\in\mathbb N$, we have

\epsC_{\mathsf{Inv}_K}(S,T)\le O\left(\frac{ST}{N\cdot\min\{S,K\}}\right)=O\left(\frac{T}{N} + \frac{ST}{KN}\right).

We remark that using <Ref>, we can only get a weaker bound of

O\left(\frac TN+\frac SK\right).

Indeed, the message from <Ref> is much stronger: salting can eliminate the additional advantages of non-uniform advice once the number of salts exceeds the length of the advice string.

§ NON-UNIFORM SECURITY OF SALTING IN THE QROM

In this section, we prove the non-uniform security of salting in the quantum random oracle model (QROM) for property finding problems.

§.§ Preliminaries: Database and Property on Databases

We consider a random oracle $f : [M] \to [N]$. For convenience, let $\X = [M]$ be the domain of the random oracle. Let $\Y = [N]$ be the range of the random oracle.
For $0 \leq \nu \leq M$, let $\binom{\X}{\nu}$ be the set of all subsets of $\X$ with size $\nu$. We use $\vx \in \binom{\X}{\nu}$ to denote a vector $\vx$ of length $\nu$ such that $1 \leq x_1 < x_2 < \cdots < x_\nu \leq M$.

A database $D = \{(x_i, y_i)\}_{i \in [\nu]}$ is defined by $\vx \in \binom{\X}{\nu}$, $\vy \in \Y^\nu$ of the same length.  $|D|=\nu$ is the length/size of the database. An empty database is denoted by $\emptyset$.

Loosely speaking, a database $D$ defines knowledge about a random oracle: namely, the random oracle $f$ will output $y_i$ on $x_i$ for $1 \leq i \leq \nu$; its behavior on other inputs is undefined.

Although a database $D$ is similar to a partial assignment, we will use the word “database” only in the quantum setting. $D$ is used in the compressed oracle technique by Zhandry <cit.>; even if it intuitively describes a partial assignment that an algorithm learns about a function, databases are “stored” in superposition and can also be unlearned by a quantum algorithm. Due to the differences between classical and quantum algorithms, we will adopt the notation “database” in Zhandry's work for consistency in our analysis.

For a pair $(x, y) \in \X \times \Y$, $(x, y) \in D$ denotes that $D$ contains this pair; for an input $x \in \X$, $x \in_\X D$ denotes that there exists $y \in \Y$ such that $(x, y) \in D$. We similarly define $(x, y) \not\in D$, $x \not\in_\X D$, $y \in_\Y D$, and $y \not\in_\Y D$. For $(x, y) \in D$, we define $D(x) := y$; otherwise $x \not\in_\X D$, $D(x)$ is set as a special symbol $\bot$.

We say a database $D \subseteq D'$ if every $(x_i, y_i) \in D$ is also contained in $D'$. For $x \not\in_{\X} D$ and $y \in \Y$, define $D \cup \{(x, y)\}$ as the database with $(x, y)$ added into $D$.

Define $\Ds_{\X, \Y}$ as the set of all databases of a random oracle:

\begin{align*}
\Ds_{\X, \Y} = \left\{ D = \{(x_i, y_i)\}_{i \in [\nu]} \,:\,\vx \in \binom{\X}{\nu}, \vy \in \Y^\nu, \,\forall \nu \in [M] \right\}
\end{align*}

We will ignore the subscripts when $\X$ and $\Y$ are clear from the context and simply write $\Ds$.

A property $P$ of databases $\Ds$ is a subset of $\Ds$. For a property $P$, let $P^{(\nu)}$ denote all databases with property $P$ of size $\nu$ and $P^{(\leq \nu)}$ denote all databases with property $P$ of size at most $\nu$.

We say a property $P$ is monotone if for any $D \in P$ and $D \subseteq D'$, we have $D' \in P$.

§.§ Preliminaries: Quantum Random Oracle and Compressed Oracle

§.§ Classical and Quantum Property Finding Problem

*Classical Property Finding.
The optimal winning probability of many important games can be captured by the following property finding problem.

Let $P$ be a monotone property.[We are only interested in the case of $P$ being monotone, i.e., learning more information is always better.]
We say a query algorithm wins if $D \in P$, where $D$ is the database corresponding to the partial assignment a classical algorithm learns by querying a random oracle.

Some Examples. In the pre-image search problem, the goal is to find an input $x$ such that $f(x) = 0$. The property is defined as $P = \{D: 0\in_\Y D\}$. For the collision finding problem, we want to find a pair of distinct inputs that map to the same output. In this case, $P = \{ D:  D(x) = D(x')\text{ for some distinct } x,x' \in_\X D\}$.

For a monotone property $P$, we define $\overline{P}$ to be the complement of $P$, and the probability $p_\nu$ as

\begin{align*}
p_\nu = \max_{\substack{D \in \overline{P}^{(\leq \nu)} \\ x \not\in_\X D }} \Pr_{y \gets \Y}[D \cup \{(x, y)\} \in P],
\end{align*}

where we recall that $\overline{P}^{(\leq \nu)}$ denotes all databases in $\overline{P}$ of size at most $\nu$.
By the monotonicity of $P$, $p_\nu$ is non-decreasing on $\nu$.

Let $P$ be a monotone property with transition probability $p_t$.
For any classical $T$-query algorithm, the probability of winning the property finding problem of $P$ is at most $p_0 + p_1 + \cdots+ p_{T-1} \leq T\cdot p_T$.

Since we are not interested in the above classical lemma for the purpose of this work, we just offer an illustrative example to compare with the quantum analog of it.

The probability of an algorithm reaching $D \in P$ is upper bounded by the summation of its probability of reaching $D$ at the $i$-th step for every $i \in  \{1, 2, \ldots, T\}$. Thus, the probability is at most $p_0 + \cdots + p_{T-1} \leq T\cdot p_T$.

*Quantum Property Finding Problem.
In the quantum case, we work in the compressed oracle framework. At any stage of an algorithm, the joint system of the algorithm and the random oracle is described by a state over the algorithm register and the database register.

let $\Lambda_P$ be a projection that in superposition checks whether the database is in $P$:

\Lambda_P = \sum_{D \in P} \ket D \bra D.

We can similarly define the quantum version of property finding problem in the quantum random oracle model.

The quantum property finding problem for property $P$ is defined as follows: a quantum algorithm interacts with a compressed oracle; when the algorithm stops, a binary-valued measurement $\{\Lambda_P, \I - \Lambda_P\}$ is applied to the compressed oracle register and the algorithm wins if the measurement outcome is $0$ (corresponding to $\Lambda_P$, it “finds” the property).

Let $P$ be a monotone property with transition probability $p_t$.
For any quantum $T$-query algorithm, the probability of its winning the quantum property finding problem for property $P$ is at most $\gamma_T = O(\sqrt{p_0} + \sqrt{p_{1}} + \cdots + \sqrt{p_{T-1}})^2 = O(T^2\cdot p_T)$.

§.§ Main Quantum Theorem

Let $R$ be a collection of tuples in $X^c \times Y^c$.
Define $P_R$ to be the property on $\mathcal{D}$ such that $D \in P_R$ if and only if $D$ consists of a tuple in $R$:

\begin{align*}
D \in P_R  \quad \iff \quad
\exists (x_1, \ldots, x_c, y_1, \ldots, y_c) \in R \text{ such that } D(x_i) = y_i, \forall i \in \{1, 2, \ldots, c\}.
\end{align*}

It is easy to see that $P_R$ is monotone for any $R$.

The game we consider in the QROM is the following.

Let $R$ be a collection of tuples. $G_R$ askes a quantum-query algorithm to output $(x_1, \ldots, x_c, y_1, \ldots, y_c) \in R$.

Here we are interested in the case when $c$ is small.
Some examples of $G_R$ include: finding pre-images of zero, collision finding,  $k$-SUM.
Problems like computing the parity of the function has large $c$ and therefore are not covered in our main theorem.
We now present our main theorem in the quantum case.

Let $R$ be a collection of tuples and $R \subseteq \X^c \times \Y^c$. Let $G_R$ be the game defined above. Let $p_T$ be the transition probability, and $\gamma_T$ be an upper bound on the winning probability of any $T$-quantum-query algorithm, derived from Zhandry's compressed oracle technique (<Ref>); $\gamma_T=\Theta(T^2\cdot p_T)$. If the transition probability $p_t$ is polynomial in $t$, i.e., $p_t=\Theta(t^{c_1}/N^{c_2})$ for some constants $c_1,c_2\ge 0$, then for every $T \geq c$,

\begin{align*}
\epsQ_{G_{R,K}}(S, T) \leq \widetilde{O}\left( \gamma_T + \frac{S}{K} + \frac{c}{N}\right),
\end{align*}

where $\widetilde{O}$ hides low order terms in $\log N$.

Since an algorithm needs to output a $c$-tuple of input-output pairs that are consistent with a random oracle, we can without loss of generality only consider the case when $T \geq c$.
For $G_R$ that we are interested in the work, the compressed oracle technique shows that $\epsQ_{G_R}(T) \leq O(\gamma_T + \frac{c}{N})$.
When the technique is tight, our theorem is also tight.
Zhandry <cit.> demonstrated the tightness of <Ref> for some special cases. Thus, we  get the following consequences.

For ${\sf CRHF}$ whose goal is to find two distinct inputs whose images are identical, we have

\begin{align*}
\epsQ_{{\sf CRHF}_K}(S, T) \leq \widetilde{O}\left(\frac{T^3}{N} + \frac{S}{K} \right).
\end{align*}

For ${\sf Inv_0}$ whose goal is to find a pre-image of zero, we have

\begin{align*}
\epsQ_{{\sf Inv}_{0,K}}(S, T) \leq \widetilde{O}\left(\frac{T^2}{N} + \frac{S}{K} \right).
\end{align*}

For ${\sf kSUM}$  whose goal is to find $k$ distinct inputs whose images sum up to zero, we have

\begin{align*}
\epsQ_{{\sf kSUM}_K}(S, T) \leq \widetilde{O}\left(\frac{T^{k+1}}{N} + \frac{S}{K} \right).
\end{align*}

§.§ Quantum Direct Product Theorems for Property Finding Problem

To prove our main theorem <Ref>, one crucial step is to give a (threshold) strong direct product theorem for the property finding problem. In this part, we introduce the notion of quantum direct product of property finding problems, and present the strong direct product theorems (SDPT) in this case.

*Quantum Direct Product of Property Finding Problem. Now a random oracle $f$ is treated as $[K] \times \X \to \Y$. For convenience, $\KX := [K] \times \X$. The random oracle can be viewed as a concatenation of $K$ independent random oracles; namely,  for each $k \in [K]$, $f_k = f(k,\cdot)$ is a random oracle $\X \to \Y$.

An input is denoted by $(k, x) \in \KX$ for $k \in [K]$ and $x \in \X$. A database $D$ is similarly defined by $\vx \in \binom{\KX}{\nu}$ and $\vy \in \Y^\nu$ of the same length $\nu$. It is also nature to define $((k, x), y) \in D, (k, x) \in_{\KX} D, y \in_\Y D$ and $D \subseteq D'$.

For a database $D \in \Ds_{\KX, \Y}$ and an index $k \in [K]$, we define the restriction of $D$ to $k$ as $D|_k \in \Ds_{\X, \Y}$:

\begin{align*}
D|_k = \{(x, y) \,:\, ((k, x), y) \in D\}.
\end{align*}

In other words, $D|_k$ is a subset of $D$ with prefix $k$ removed.

Let $P$ be a property on $\Ds_{\X, \Y}$.
Let $\kappa \in \mathbb{Z}_+$ and $\KX = [\kappa] \times \X$.
Define the direct product property on $\Ds_{\KX, \Y}$ as $P^{\times \kappa}$:

\begin{align*}
D \in P^{\times \kappa} \quad \Longleftrightarrow \quad D|_{k} \in P, \forall k \in [\kappa].
\end{align*}

In the quantum setting, when the database register is a superposition state of databases, $D|_k\in P$ corresponds to the projected state where every superposition satisfies $D|_k\in P$.

Let $P$ be a property on $\Ds_{\X, \Y}$.
If $D|_k\in P$, we say that the database $D$ succeeds on salt $k$. If $\mathcal{K}$ is the set of $k$ such that $D|_k\in P$, we say that the database $D$ succeeds on $|\mathcal{K}|$ salts.

*Quantum Direct Product Theorems.
We have the following direct product theorem for quantum property finding problem:

Let $P$ be a monotone property with transition probability $p_t$.
Let $\gamma_T$ be an upper bound on the winning probability of any $T$-quantum-query algorithm, derived from Zhandry's compressed oracle technique (<Ref>).

Let $\kappa \in \mathbb{Z}_+$ and $P^{\times \kappa}$ be the direct product. If $p_T$ is polynomial in $T$, i.e., $p_T=\Theta(T^{c_1}/N^{c_2})$ for some constants $c_1,c_2\ge 0$, then with $\gamma_T=\Theta(T^2\cdot p_T)$, the maximum winning probability of any $\kappa T$-query quantum algorithm for the quantum property finding problem for $P^{\times \kappa}$ is at most $O(1)^\kappa\cdot \gamma_T^\kappa$.

Actually we can have a threshold version of <Ref>.

Let $P$ be a monotone property with transition probability $p_t$.
Let $\gamma_T$ be an upper bound on the winning probability of any $T$-quantum-query algorithm, derived from Zhandry's compressed oracle technique (<Ref>).

For salt space $[K]$ and threshold $\kappa\le K$, if $p_T$ is polynomial in $T$, i.e., $p_T=\Theta(T^{c_1}/N^{c_2})$ for some constants $c_1,c_2\ge 0$, the maximum winning probability for any $B$-query quantum algorithm ($B\in\mathbb{Z}_{+}$) to succeed on at least $\kappa$ salts in this quantum property finding problem is at most $O(1)^\kappa\cdot (\gamma_{B/\kappa})^\kappa$.

For <Ref>, we can rewrite $p_T$ as the polynomial $p(T)=\Theta(T^{c_1}/N^{c_2})$, and in this way we define $p_{B/\kappa}:=p(B/\kappa)$ when $B/\kappa$ is not an integer.
Similarly we define $\gamma_{B/\kappa}=t^2\cdot p_{t}=t^2\cdot p(t)$ for $t=B/\kappa$.

The proof of <Ref> and <Ref> can be found in <Ref>, where we prove the strong direct product theorem for quantum property finding, and the threshold version as a corollary.

§.§ Proof of SDPT in the QROM

In this section, we consider the following two-stage quantum algorithms $(\Bs, \As)$.

* Let $\Bs$ be a $2 S T$-quantum-query algorithm. First, $\Bs$ executes and outputs a binary predicate $b$, together with a quantum state.

* The quantum state is then given to $\As$. The goal of $\As$ is to win $G_{R, K}$ within $T$ quantum queries and with the state received from $\Bs$.

We denote the event of $b = 0$ by $\mathbf{W}$.
To prove <Ref>, we only need to prove the following theorem.

Let $G_{R,K}$ be a game and $c \in \mathbb{Z}^+$ as defined in <Ref>.
Assume there exists $\delta > \frac{1}{N}$ such that for every two-stage quantum algorithms $(\Bs, \As)$ with $2 S T$ and $T$ queries each, we have $\Pr[\mathbf{W}] > 1/N^S$ and

\begin{align*}
\Pr_{\substack{f\sim\mu\\ k\sim[K]}}\left[\cA^f(k)\text{ wins } \middle| \bW\right] \leq \delta.
\end{align*}

Then $\epsQ_{G_{R,K}}(S, T) \leq \delta$.

The proof is intuitively explained in the technical overview (Quantum Bit-Fixing section) and a formal proof is deferred to <Ref>.

Thus, our goal becomes to give an upper bound for $\Pr[\cA^f(k)\text{ wins } | \bW]$ when $\Pr[\bW]$ is not “too small”.
We define $\bE$ to be the event that the database registers succeed on at most $2S\log N$ salts.
With $\bE$, we can give the following bound
of $\Pr[\cA^f(k)\text{ wins } | \bW]$.

Define $\bE$ to be the event that when the algorithm $\Bs$ finishes, the database registers succeed on at most $2S\log N$ salts. Define $\overline{\bE}$ to be the complement of $\bE$ where the database registers can succeed on more than $2S\log N$ salts. Then,

\begin{align}\label{ineq:upbound-W-E}
\Pr_{\substack{f\sim\mu\\ k\sim[K]}}[\cA^f(k)\text{ wins } | \bW]
&\le\Pr_{\substack{f\sim\mu\\ k\sim[K]}}[\cA^f(k)\text{ wins } | \bW\land \bE]+\frac{\Pr_{f\sim\mu}[\overline{\bE}]}{\Pr_{f\sim\mu}[\bW]}.
\end{align}

From <Ref>, we can give an upper bound for the two terms in RHS of <Ref> respectively. This leads us to the proof of <Ref>.
The main idea of the proof is as follows:

* For the first term $\Pr[\cA^{f}(k)\text{ wins }|\bW\land \bE]$,

* We apply <Ref> and reduce it to giving an upper bound for the quantum property finding problem, as in <Ref>.

* Then we upper bound that quantum property finding problem, as in <Ref>.

* For the second term $\Pr[\overline{\bE}]/\Pr[\bW]$, since $\Pr[\bW]\ge 1/N^S$, we only need to give an upper bound for $\Pr[\overline{\bE}]$. This corresponds to a threshold strong direct product theorem for the quantum property finding problem, as in <Ref>.

For $\cA^f$ that outputs answers as a tuple $(x_1,\ldots,x_c,y_1,\ldots,y_c)$, we have the following relation between the original game and its corresponding property finding problem:

\begin{align}\label{ineq:conditioned_lem5}
\Pr_{\substack{f\sim\mu\\ k\sim[K]}}[\cA^f(k)\text{ wins } | \bW\land \bE]
\le 2\cdot\Pr_{\substack{f\sim\mu\\ k\sim[K]}}[(D|_k\in P)| \bW\land \bE]+\frac{2c}{N}.
\end{align}

Here $D$ corresponds to the database registers, and $D|_k\in P$ corresponds to the projected state that $D|_k\in P$ for every superposition; it means that $\cA^f$ succeeds on salt $k$ for the quantum property finding problem of $P$.

Conditioned on $\bW\land\bE$, we have the following upper bound of the maximum winning probability for the property finding problem on a random salt $k\sim [K]$:

\begin{align}\label{ineq:conditioned_propertyfinding}
\Pr_{\substack{f\sim\mu\\ k\sim[K]}}[(D|_k \in P)| \bW\land \bE] \le O(\gamma_{2T})+\widetilde{O}\left(\frac{S}{K}\right).
\end{align}

In the theorem statement, $\gamma_t$ is assumed  to be a polynomial in $t$.
Thus, $\gamma_{2T} = O(\gamma_{T})$.

For $\overline{\bE}$ as defined in <Ref>,

\begin{align}\label{ineq:threshold-qsdpt-E}
\Pr_{f\sim\mu}[\overline{\bE}]\le \Pr_{f\sim\mu}[\bW]\cdot\frac{1}{N}.
\end{align}

With <Ref>, <Ref>, <Ref>, and <Ref>, we can conclude an upper bound for $\Pr[\cA^f(k)\text{ wins } | \bW]$. Together with <Ref>, this gives us an upper bound for the non-uniform security as in <Ref>.

Proofs of all the claims and <Ref> can be found in <Ref>.

§ ACKNOWLEDGEMENT

KW wants to thank Guangxu Yang and Penghui Yao for references in direct product theorems.

Missing 'biblatex' package
The bibliography requires the 'biblatex' package.

booktitleAnnual International Cryptology Conference
titleTime-space tradeoffs and short collisions in merkle-damgård hash functions

booktitleAnnual International Cryptology Conference
titleTime-space lower bounds for finding collisions in Merkle-Damgård hash functions

journaltitlearXiv preprint quant-ph/9705002
titleQuantum algorithm for the collision problem

booktitleAdvances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part I
seriesLecture Notes in Computer Science
titleRandom Oracles and Non-uniformity

booktitleAnnual International Conference on the Theory and Applications of Cryptographic Techniques
titleOn the compressed-oracle technique, and post-quantum security of proofs of sequential work

booktitle2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)
titleTight quantum time-space tradeoffs for function inversion

booktitleTheory of Cryptography Conference
titleThe function-inversion problem: Barriers and opportunities

booktitleProceedings of the 4th conference on Innovations in Theoretical Computer Science
titleOn the power of nonuniformity in proofs of security

booktitleProceedings of the 2015 Conference on innovations in theoretical computer science
titleDirect sum testing

booktitleAdvances in Cryptology - EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 - May 4, 2017, Proceedings, Part II
seriesLecture Notes in Computer Science
titleFixing Cracks in the Concrete: Random Oracles with Auxiliary Input, Revisited

journaltitlecomputational complexity
titleImproved direct product theorems for randomized query complexity

booktitle2014 IEEE 29th Conference on Computational Complexity (CCC)
titleDirect product testing

booktitleAnnual Cryptology Conference
titleTime space tradeoffs for attacks against one-way functions and PRGs

IEEE Computer Society

booktitle1991 Proceedings of the Sixth Annual Structure in Complexity Theory Conference
titleOn the success probability of the two provers in one-round proof systems

booktitleProceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)
titleConcentration bounds for almost k-wise independence with applications to non-uniform security

booktitleAnnual International Cryptology Conference
titleOn time-space tradeoffs for bounded-length collisions in Merkle-Damgård hashing

booktitleTheory of Cryptography Conference
titleUnifying Presampling via Concentration Bounds

booktitleProceedings of the Fortieth Annual ACM Symposium on Theory of Computing
titleUniform direct product theorems: simplified, optimized, and derandomized

booktitleInternational Workshop on Randomization and Approximation Techniques in Computer Science
titleConstructive proofs of concentration bounds

booktitle2011 IEEE 26th Annual Conference on Computational Complexity
titleRelativized separations of worst-case and average-case complexities for NP

booktitle36th Computational Complexity Conference
titleA Direct Product Theorem for One-Way Quantum Communication

booktitle2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)
titleA direct product theorem for quantum communication complexity with applications to device-independent QKD

booktitleProceedings of the seventeenth annual ACM symposium on Theory of computing
titleOne-way functions and pseudorandom generators

booktitleAnnual International Conference on the Theory and Applications of Cryptographic Techniques
titleNon-uniformity and Quantum Advice in the Quantum Random Oracle Model

journaltitlecomputational complexity
titleA strong direct product theorem for quantum query complexity

booktitleAdvances in Cryptology–EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II 35
titleOn the power of hierarchical identity-based encryption

ACM New York, NY, USA

journaltitleCommunications of the ACM
titlePassword security: A case history

journaltitlecomputational complexity
titleQuantum arthur–merlin games

journaltitleSIAM Journal on Computing
titleProducts and help bits in decision trees

booktitle2010 IEEE 25th Annual Conference on Computational Complexity
titleParallel repetition of two prover games (invited survey)

journaltitleComputational Complexity
titleTowards proving strong direct product theorems

booktitleProceedings of the forty-third annual ACM symposium on Theory of computing
titleStrong direct product theorems for quantum communication and query complexity

booktitleAdvances in Cryptology - CRYPTO 2007, 27th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2007, Proceedings
seriesLecture Notes in Computer Science
titleRandom Oracles and Auxiliary Input

booktitle23rd Annual Symposium on Foundations of Computer Science (SFCS 1982)
titleTheory and application of trapdoor functions

booktitleProceedings of the twenty-second annual ACM symposium on Theory of computing
titleCoherent functions and program checkers

booktitleAnnual International Cryptology Conference
titleHow to record quantum queries, and applications to quantum indifferentiability

§ MISSING PROOFS FOR THE CLASSICAL CASE

We use standard martingale analysis.
For each $i=0,1,\ldots,L$, let $\ell_i$ be the number of distinct elements in $k_1,\ldots,k_i$.
Then $\ell_0=0$ and $\ell_L=\ell$.
Since each $\ell_i$ is at most $L$, we have

\E\left[c^{\ell_i}\right]
\le\left(c+\frac LK\right)\cdot\E\left[c^{\ell_{i-1}}\right].

The desired bound follows by applying the above inequality $L$ times.