Toward the Impossibility of Perfect Complete Quantum PKE from OWFs

In this work, we show that Question 1 is closely related to a fundamental conjecture about the roots of low-degree polynomials on the Boolean hypercube. More specifically, we propose the following conjecture, and show that it implies a full impossibility result of perfect complete QPKE in the QROM.

A partial assignment is denoted by $\rho \in {\{-1,1,\star \}}^n$ and $|\rho |$ is defined as the number of non-$\star$ entries. $x^{\rho }$ is defined as an input string whose $i$-th bit will be equal to $x_i$ if ${\rho }_i=\star$, and otherwise equal to ${\rho }_i$. In other words, the conjecture asserts that for every degree $d$ nonconstant $f$, there is a universal (randomized) way to modify $\mathrm{poly}(d)$ bits such that, every input string $x$ has an inverse-polynomial probability of evaluating to non-zero under this randomized modification.

With the conjecture, we now present our main theorem.

1 is closely related to notions like certificate complexity, sensitivity in the literature of boolean function analysis (BFA), and also to the celebrated Combinatorial Nullstellensatz of Alon [2], making it a considerably natural conjecture. With the tools in BFA and the Combinatorial Nullstellensatz, we can provide many pieces of evidence and prove special cases. We mention some of the most important results below while leaving others in the main body.

Here, we give a brief overview of why 1 implies a full impossibility result of QPKE in the QROM and the main differences between [18] and this work.

We will be mostly focusing on key agreement protocols in the QROM. In the QROM, all parties can quantumly query a random oracle. A key agreement protocol is an interactive protocol between two query-efficient quantum algorithms Alice and Bob, exchanging classical messages. Their goal is to agree on a key, whereas any query-efficient adversary can not learn the key, even observing all the communication on this channel. It is easy to see that QPKE implies a two-round key agreement protocol:

• $\mathrm{■}$

  Alice sends a single message $m_0$ to Bob; in this case, $m_0$ will be the public key.

• $\mathrm{■}$

  Bob sends a message $m_1$ to Alice; in this case, $m_1$ will be the encryption of a random key (which will be the agreed key in the two-round key agreement protocol).

• $\mathrm{■}$

  Finally, they both output their own keys $k_A,k_B$; in this case, Alice decrypts the ciphertext using her secret key, whereas Bob simply outputs the random key.

Thus, to rule out QPKE in the QROM, it is sufficient to rule out the two-round key agreement in the QROM.

Li, Li, Li and Liu [18] proposed the following framework that rules out QPKE with classical-query key generation in the QROM. Let ${\mathrm{𝖵𝗂𝖾𝗐}}_A,{\mathrm{𝖵𝗂𝖾𝗐}}_B$ denote the view of Alice and Bob, right after $m_1$ is received by Alice. They showed that, based on a novel approach called approximate quantum Markov chain, a quantum-query Eve can reconstruct Alice’s view ${\mathrm{𝖵𝗂𝖾𝗐}}_A^{\prime }$ such that

More precisely, Eve can reconstruct Alice’s register such that the margin of the fake Alice and the real Bob is arbitrarily close to the real Alice and the real Bob. However, this is not sufficient; since to compute the key $k_A$, Alice potentially needs to perform computation depending on its current state, the random oracle and all the messages $m_0,m_1$. As the marginal is defined by tracing out the random oracle, we do not know what oracle to work with. For example, a direct attempt is to run fake Alice under the real random oracle $H$; but it is possible that under real $H$, conditioned on the messages being $m_0,m_1$, the view of Alice and Bob will never equal to ${\mathrm{𝖵𝗂𝖾𝗐}}_A^{\prime }{\mathrm{𝖵𝗂𝖾𝗐}}_B$, making the attempt meaningless.

Li et al. solved this by adapting Bob; while perfectly preserving the functionality of the key agreement protocol, the new Bob has one additional nice property (let us call it “stability”):

• $\mathrm{■}$

  if under a random oracle $H$, input message $m_0$, Bob outputs certain $m_1$ with non-zero probability

• $\mathrm{■}$

  then for every $H^{\prime }$ that has a small Hamming distance to $H$²²2We ignore a detail here: $H^{\prime }$ should be consistent with $H$ on a small set of inputs, whereas on other inputs, their Hamming distance is small. This does not change the reasoning, thus we make the simplification in the introduction., Bob on $H^{\prime }$ and $m_0$ still has non-zero probability to output $m_1$.

With this property, they show that the two-round key agreement can not exist, when $m_0$ together with ${\mathrm{𝖵𝗂𝖾𝗐}}_A$ can be computed by a classical decision tree (or $\mathrm{𝖦𝖾𝗇}$ only makes classical queries). For any fake Alice view ${\mathrm{𝖵𝗂𝖾𝗐}}_A^{\prime }$, it depends on at most $d$ locations of a random oracle; here $d$ is the number of queries made by the classical decision tree. Thus, for any oracle $H_0$, as long as it is consistent on these $d$ locations, Alice on $H_0$ can output ${\mathrm{𝖵𝗂𝖾𝗐}}_A^{\prime }$ and $m_0$ with non-zero probability. They construct an oracle $H^{\prime }$ such that: (i) it is almost $H$, except (ii) on those $d$ locations, $H^{\prime }$ is reprogrammed to be consistent with these $d$ locations.

It is clear that Alice on $H^{\prime }$ still outputs $m_0,{\mathrm{𝖵𝗂𝖾𝗐}}_A^{\prime }$ with a non-zero probability (consistency of these $d$ locations). Moreover, the “stability” ensures that the adapted Bob on $H^{\prime }$ and $m_0$ outputs ${\mathrm{𝖵𝗂𝖾𝗐}}_B$ also with a non-zero probability. Thus, there is a non-zero probability, under the oracle $H^{\prime }$, Alice and Bob will end up with ${\mathrm{𝖵𝗂𝖾𝗐}}_A^{\prime },{\mathrm{𝖵𝗂𝖾𝗐}}_B$ and transcripts $(m_0,m_1)$. Since we assume the QPKE is perfect, after the whole execution, Alice and Bob should agree on a key. As for Eve, it simply runs Alice with ${\mathrm{𝖵𝗂𝖾𝗐}}_A^{\prime },m_1$ on $H^{\prime }$ and will recover the key.

The above reasoning in [18] does not work even if Alice only makes a single quantum query, and thus they can only rule out QPKE when $\mathrm{𝖦𝖾𝗇}$ makes classical queries. Since a single quantum query can “store” information about exponentially many inputs, it seems that fixing a smaller number of input-output behaviors does not fix Alice’s behavior.

We realize that, we do not need to keep Alice’s behavior the same; we are only required to keep these probabilities non-zero. More precisely, our solution is to directly look at the polynomial $f$ describing the probability that a quantum Alice on some oracle, outputs $(m_0,{\mathrm{𝖵𝗂𝖾𝗐}}_A^{\prime })$,

where we treat $x$ as the random oracle fed into $A$. As the random oracle will be the input to a polynomial, to be consistent with the literature of BFA, we will denote a random oracle by $x$. Since $A$ only makes $d$ quantum queries, such a polynomial $f$ has degree at most $2d$. The real random oracle is some $x$ of which we have no knowledge about; the goal is to find another $x^{\prime }$ such that

• $\mathrm{■}$

  $f(x^{\prime })>0$, meaning Alice on the random oracle $x^{\prime }$ outputs ${\mathrm{𝖵𝗂𝖾𝗐}}_A^{\prime },m_0$ with a non-zero probability, just like the classical case; and,

• $\mathrm{■}$

  $x^{\prime }$ and $x$ have a small Hamming distance, so that Bob still has non-zero probability to output ${\mathrm{𝖵𝗂𝖾𝗐}}_B,m_1$.

As we do not know $x$, the only way we can obtain $x^{\prime }$ is by locally modifying some locations of $x$. For example, reprogramming some locations of the real oracle, and running the rest of Alice under the reprogrammed oracle – this is where the partial assignment takes place. If we can find a partial assignment $\rho$ with $|\rho |$ is small, such that for every $x$, $f(x^{\rho })>0$, then the problem is resolved! This is the high-level intuition why our conjecture (1) implies a full impossibility result of QPKE in the QROM.

Towards Conjecture 1, we remark that the Combinatorial Nullstellensatz [2] directly implies the existence of such $\rho$. More specifically, the Combinatorial Nullstellensatz claims that: given any maximal monomial $x_S$ of $f$, for any $x\in {\{-1,1\}}^n$, there exists a $\rho$ with $\mathrm{𝗌𝗎𝗉𝗉}(\rho )=S$ such that $f(x^{\rho })\ne 0$. Therefore, Conjecture 1 holds if we swap the order of quantifiers of $\rho$ and $x$. Consequently, by letting $𝒟$ be the uniform distribution on the set of partial assignments $\rho$ with $\mathrm{𝗌𝗎𝗉𝗉}(\rho )=S$, we have ${\mathrm{Pr}}_{\rho \sim 𝒟}[f(x^{\rho })\ne 0]\ge 1/2^d$ for any $x$, as claimed by Lemma 7. In particular, when $\mathrm{𝖦𝖾𝗇}$ makes only $O(\log n)$ queries and then $\mathrm{deg}(f)=O(\log n)$, we have ${\mathrm{Pr}}_{\rho \sim 𝒟}[f(x^{\rho })\ne 0]\ge 1/\mathrm{poly}(n)$, which implies Lemma 10.

In Conjecture 1, we characterize $d$-query quantum algorithms as degree-$2d$ polynomials [8]. This characterization was further strengthened by Aaronson and Ambainis [1] in terms of bounded degree-$2d$ block-multilinear polynomials. Later, Arunachalam, Briet, and Palazuelos [4] provided an exact characterization of quantum query algorithms in terms of the so-called completely bounded norm.

Every function $f:{\{-1,1\}}^n\to ℝ$ on the hypercube can be uniquely expressed as a multilinear polynomial

where $x_S:={\mathrm{\Pi }}_{i\in S}{x}_i$. Indeed, this expression is called the Fourier expansion of $f$, where $a_S=2^{-n}{\sum }_{x}f(x)\cdot x_S$. The degree of $f$, denoted $\mathrm{deg}(f)$, is defined as the degree of its multilinear polynomial expression, i.e., $\max \{|S|\mid a_S\ne 0\}$. A monomial $x_S$ is called maximal if it has degree $\mathrm{deg}(f)$, i.e., $|S|=\mathrm{deg}(f)$ and $a_S\ne 0$. The rank of $f$, denoted $\mathrm{rank}(f)$, is the maximum number of disjoint maximal monomials.

A partial assignment is a function $\rho :[n]\to \{-1,1,\star \}$. We define the support of $\rho$ as $\mathrm{𝗌𝗎𝗉𝗉}(\rho ):=\{i|{\rho }_i\ne \star \}$, and the size as $|\rho |:=|\mathrm{𝗌𝗎𝗉𝗉}(\rho )|$. For $x\in {\{-1,1\}}^n$, we define the modification of $x$ with $\rho$, denoted $x^{\rho }$, as the string $x^{\prime }\in {\{-1,1\}}^n$ where $x_i^{\prime }={\rho }_i$ for $i\in \mathrm{𝗌𝗎𝗉𝗉}(\rho )$ and $x_i^{\prime }=x_i$ for any other $i$.

We use $\mathrm{𝖵𝖺𝗋}(f):={𝔼}_x[f{(x)}^2]-{\left({𝔼}_{x}f(x)\right)}^2$ to denote $f$’s variance, and define ${\Vert f\Vert }_{\mathrm{\infty }}:={\max }_x|f(x)|$. A real polynomial $p$ $ϵ$-approximates $f$ if $|f(x)-p(x)|\le ϵ$ for every $x\in {\{-1,1\}}^n$. The approximate degree of $f$, denoted by $\widetilde{\mathrm{deg}}(f)$, is defined to be the minimum degree needed to $1/3$-approximate $f$.

The following lemma will be used.

In this paper, we will consider constructions in the quantum random oracle model. Given security parameter $\lambda$, the oracle $H$ is chosen from the uniformly random distribution over the family of functions ${\mathscr{H}}_{\lambda }:[2^{n_{\lambda }}]\to \{0,1\}$, where $n_{\lambda }$ is a polynomial of $\lambda$. The quantum circuit has access to the oracle unitary $U_H$ that maps $|i,y⟩$ to $|i,y\oplus H(i)⟩$. We can also view the oracle unitary in the phase basis $U_H^{\prime }|i,y⟩\to {(-1)}^{H(i)y}|i,y⟩$.

We will consider quantum public key encryption with classical public key $\mathrm{𝗉𝗄}$ and ciphertext $\mathrm{𝖼𝗍}$ in this paper. Particularly, we will consider the quantum public key encryption (QPKE) scheme in the quantum random oracle model (QROM) defined as follows:

The algorithms should satisfy the following requirements:

Perfect Completeness

$\mathrm{Pr}\left[{\mathrm{𝖣𝖾𝖼}}^H(\mathrm{𝗌𝗄},{\mathrm{𝖤𝗇𝖼}}^H(\mathrm{𝗉𝗄},m))=m:{\mathrm{𝖦𝖾𝗇}}^H(1^{\lambda })\to (\mathrm{𝗉𝗄},\mathrm{𝗌𝗄})\right]=1$.

IND-CPA Security

For any QPT adversary ${ℰ}^H$, for every two plaintexts $m_0\ne m_1$ chosen by ${ℰ}^H(\mathrm{𝗉𝗄})$ we have

$\mathrm{Pr}\left[{ℰ}^H(\mathrm{𝗉𝗄},{\mathrm{𝖤𝗇𝖼}}^H(\mathrm{𝗉𝗄},m_b))=b\right]\le {\displaystyle \frac{1}{2}}+{\displaystyle \frac{ϵ(\lambda )}{2}}.$

where we call $ϵ(\lambda )$ as the advantage of the adversary. The scheme is IND-CPA secure if $ϵ(\lambda )$ is negligible for any adversary ${ℰ}^H$.

The main evidence for 1 comes from the celebrated Combinatorial Nullstellensatz of Alon [2], which implies 1, except with ${\mathrm{Pr}}_{\rho \sim 𝒟}[f(x^{\rho })\ne 0]\ge 1/2^d$ instead of ${\mathrm{Pr}}_{\rho \sim 𝒟}[f(x^{\rho })\ne 0]\ge 1/\mathrm{poly}(d)$. Let us state the special case of the Combinatorial Nullstellensatz for polynomials on the hypercube.

We remark that Lemma 22 was also proven by Midrijanis [21]. Even though Lemma 22 has an exponential rather than polynomial dependence on $1/d$, we observe that it already has a nontrivial implication on the separation between QPKE and OWFs. Precisely, it implies that

The proof of Theorem 23 is the same as Theorem 17 by replacing 1 with Lemma 22.

In this subsection, we present the proof of Lemma 9, which claims that Conjecture 1 is equivalent to a seemingly much weaker conjecture, namely Conjecture 8.

See 8 See 9

We also affirm 1 for some special classes of functions.

Additionally, we provide evidence for the equivalent form 13 (and consequently for 1). The first piece of evidence is from the anti-concentration result for low-degree polynomials by Meka, Nguyen and Vu [20], which implies Conjecture 13 when $X$ is uniform distribution on ${\{-1,1\}}^n$, except that $|\rho |$ is allowed to be as large as $d^{8d+4}$ instead of $|\rho |\le \mathrm{poly}(d)$.