% =====================================================================
%  CONJURA CONJECTURE STATEMENT
%  Polynomial Compatibility Conjecture (PCC) of [ACC22], in the
%  inverse-polynomial influence regime, over some finite abelian group.
%  Requires conjura-conjecture.cls in the same directory.
% =====================================================================
\documentclass{conjura-conjecture}

\runninghead{POLYNOMIAL COMPATIBILITY}

\newcommand{\NN}{\mathbb{N}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\cY}{\mathcal{Y}}
\newcommand{\dY}{\widehat{\mathcal{Y}}}
\newcommand{\bF}{\mathbf{F}}
\newcommand{\bG}{\mathbf{G}}

\begin{document}

\cjkicker{CONJURA \textperiodcentered{} OPEN PROBLEM}
\cjtitle{Polynomial Compatibility for Low-Degree, Low-Influence
Distributions}
\cjsubtitle{The inverse-polynomial influence regime, over some finite
abelian group}
\cjstatus{Statement: AI-written from Kai-Min Chung, Yao-Ting Lin,
  Mohammad Mahmoody, \emph{Black-Box Separations for Non-Interactive
  Commitments in a Quantum World}, Cryptology ePrint Archive, Report
  2023/570, 2023, not yet checked by a human. The analogous statement
  with exponentially small influences, $\delta(d) = \exp(-d)$, is proved
  in the work of Austrin et al.\ that introduced the conjecture, while
  the inverse-polynomial regime $\delta(d) = 1/\poly(d)$ recorded here
  is open; since the group is existentially quantified, a proof for any
  one finite abelian group (for instance $\ZZ_2$) settles it
  affirmatively, whereas a refutation must rule out every finite abelian
  group.}
\cjcategory{\emph{Quantum Cryptography}.}

\vspace{0.4em}

\begin{informalconjecture}
Fix a finite abelian group and look at complex-valued functions on
$N$-tuples of its elements, normalized so that the average squared
magnitude is one. Every such function expands uniquely in the characters
of the group; its degree is the largest number of coordinates that any
character with a non-zero coefficient actually depends on, and the
influence of a coordinate is the total Fourier weight sitting on
characters that touch that coordinate. Now take two probability
distributions over such functions, both supported only on normalized
functions of degree at most $d$, and both so spread out that every single
coordinate carries influence at most $\delta$ on average over the
distribution. The conjecture asserts that for some finite abelian group
there is a threshold $\delta$ that is only inverse-polynomially small in
$d$ --- crucially, independent of the number of coordinates $N$ ---
beyond which the two distributions must be compatible: you can pick one
function from the support of each and a single input point at which both
are non-zero. Equivalently, low degree together with low average
influence prevents two distributions of functions from having
systematically interlocking zero sets. The
exponentially-small-influence version of this is known; the
inverse-polynomial version is what is open, and it is exactly what
several black-box impossibility results in quantum cryptography currently
rest on, including the impossibility of building non-interactive
commitments from one-way functions when communication is classical.
\end{informalconjecture}

\section{The setting}\label{sec:setting}

Black-box separations in the quantum setting are proved by exhibiting an
oracle relative to which the assumed primitive survives but the target
primitive is broken by a polynomial-query adversary. In the classical
setting, the separation of non-interactive commitments from one-way
functions~\cite{MP12} plays two oracle distributions against each other:
either a cheating receiver learns enough $\varepsilon$-heavy queries of
the sender to guess the committed bit, or one can fix a partial oracle
consistent with two openings $\mathsf{dec}_0,\mathsf{dec}_1$ of the same
commitment, and partially fixed random oracles are still one-way.

Moving to quantum senders breaks the second step: one cannot record a
superposition query, so ``the set of oracle positions the sender asked''
is no longer a partial function. The route found by Austrin, Chung,
Chung, Fu, Lin and Mahmoody~\cite{ACC22} is to work with the purified
view of the honest party in the quantum random oracle model and to
represent the oracle register in the Fourier basis, following Zhandry's
compressed-oracle technique~\cite{Zha19}. A $d$-query algorithm then has
a sparse Fourier representation, and each branch of the purified sender
turns into a \emph{distribution over degree-$d$, unit-norm,
low-influence functions} on the oracle domain; ``heavy'' queries are
exactly those carrying non-negligible Fourier weight, and after learning
all of them the remaining influences are small. Two openings of the same
commitment are simultaneously realisable precisely when one can find a
function in the support of each branch's distribution together with a
point where both are non-zero. That combinatorial statement is the
Polynomial Compatibility Conjecture, and~\cite{ACC22} isolated it and
proved it in the regime of exponentially small influences.

The present paper~\cite{CLM23} uses the conjecture to rule out quantum
black-box constructions of non-interactive commitments from post-quantum
one-way functions in the quantum-computation classical-communication
model, and in fact in the stronger classical-commitment
quantum-decommitment model, for perfectly complete schemes and for a very
weak notion of binding. Boosting a single compatible oracle to a large
\emph{set} of compatible oracles is done with the Donoho--Stark
support-size uncertainty principle~\cite{DS89} in place of
Schwartz--Zippel, and the resulting set is shown one-way against
quantum-advice adversaries by adapting the multi-instance time--space
tradeoff machinery of~\cite{CGLQ20}. The consequences are sharp: since
injective one-way functions imply non-interactive commitments in a
black-box way~\cite{GL89}, the result yields a separation of injective
one-way functions from one-way functions with fully quantum
constructions, improving~\cite{CX21} which allowed only the security
reduction to be quantum, and it complements the positive result
of~\cite{BB21} that a \emph{quantum} commitment with a classical
decommitment does follow from post-quantum one-way functions. All of this
is conditional. The conjecture stated here is the condition, and its
inverse-polynomial regime remains unproved; the paper notes its kinship
with the Aaronson--Ambainis conjecture~\cite{AA09}, which is also known
only for exponentially small influences, and quantum black-box
separations of this shape go back to~\cite{HY20}.

\textbf{Progress to date.} The originating work proves the conjecture
when the average-influence bound is exponentially small in the degree,
$\delta(d) = \exp(-d)$, and the present paper reports this as the
evidence for the conjecture's validity. The paper also records that the
conjecture is close in spirit to the Aaronson--Ambainis conjecture on
low-degree low-influence polynomials, which is likewise only known for
exponentially small influences. The present paper makes no attempt on the
conjecture itself; it consumes it (via an equivalent formulation in terms
of $(\cY,\delta,d,N)$-quantum states and a conversion lemma) and
independently proves the unconditional half of its argument, namely that
oracles sampled from sufficiently large sets of functions are one-way
against polynomial-query quantum adversaries holding polynomial-size
quantum advice.

\textbf{Why it matters.} This single Fourier-analytic statement is the
only thing standing between a family of quantum black-box separations and
unconditional status. If it is true: there is no quantum black-box
construction of non-interactive commitments from post-quantum one-way
functions when the commitment message is classical (even allowing a
quantum decommitment), hence no black-box construction of injective
one-way functions from general one-way functions even with fully quantum
constructions, hence a separation between non-interactive commitments and
pseudorandom states in the classical-commitment/quantum-decommitment
model; and, from the originating work, no perfectly complete key
agreement in the quantum-computation classical-communication model from
one-way functions. If it is false, all of those attacks lose their
combinatorial engine, and the pressing question becomes whether the QCCC
constructions the separations rule out actually exist. Either resolution
changes what is known, and the statement itself is a clean question about
discrete Fourier analysis that is refutable by an explicit pair of
distributions.

\section{Notation and parameters}\label{sec:notation}

\begin{itemize}
  \item $\cY$ is a finite abelian group, and $\dY$ is its dual group,
  whose elements are the characters $\chi\colon\cY\to\CC^{\times}$; the
  trivial character is written $\hat{0}$.
  \item $N\in\NN$ is the number of coordinates, $[N]=\{1,\dots,N\}$, and
  an input is $x=(x_1,\dots,x_N)\in\cY^N$.
  \item For $\chi=(\chi_1,\dots,\chi_N)\in\dY^N$ we write
  $\chi(x):=\prod_{i=1}^{N}\chi_i(x_i)$. These $|\cY|^N$ functions form
  an orthonormal basis for the space of functions $\cY^N\to\CC$ under the
  inner product
  $\langle f,g\rangle:=\mathbb{E}_{x\sample\cY^N}[f(x)\overline{g(x)}]$,
  so every $f\colon\cY^N\to\CC$ has a unique Fourier expansion
  $f=\sum_{\chi\in\dY^N}\hat{f}(\chi)\,\chi$ with coefficients
  $\hat{f}(\chi)\in\CC$.
  \item $\lVert f\rVert_2 :=
  \bigl(\mathbb{E}_{x\sample\cY^N}\lvert f(x)\rvert^2\bigr)^{1/2}$, the
  $\ell_2$-norm with respect to the uniform distribution on $\cY^N$.
  \item $d\in\NN$ is a degree bound and $\delta\in(0,1]$ an influence
  bound; $\deg(\cdot)$ and $\operatorname{Inf}_i(\cdot)$ are as in
  Definition~\ref{def:deginf} below.
  \item $\bF,\bG$ denote probability distributions over functions
  $\cY^N\to\CC$, and $\operatorname{supp}(\bF)$ denotes the support of
  $\bF$, i.e.\ the set of functions to which $\bF$ assigns non-zero
  probability. Expectations $\mathbb{E}_{f\sample\bF}[\cdot]$ are over
  $f$ drawn from $\bF$.
\end{itemize}

\textbf{Parameters.}
\begin{itemize}
  \item $\cY$ --- the finite abelian group over which the functions are
  defined. Existentially quantified: a single group suffices. The paper's
  own application is presented for $\cY=\ZZ_2$ but goes through for
  whichever group witnesses the conjecture.
  \item $N$ --- the number of coordinates (the ambient dimension).
  Universally quantified, and the influence threshold must not depend on
  it --- this is the crux of the difficulty.
  \item $d$ --- the degree bound on every function in the support of both
  distributions. In the intended application $d$ is governed by the
  number of quantum oracle queries made by the honest party, hence
  polynomial in the security parameter.
  \item $\delta(d)$ --- the threshold on the average influence of each
  coordinate. The open regime is $\delta(d)=1/\poly(d)$; the case
  $\delta(d)=\exp(-d)$ is already proved in the prior work that
  introduced the conjecture.
  \item $\bF,\bG$ --- the two distributions over functions. In the
  application they arise as state polynomial distributions of the two
  branches (committing to $0$ and to $1$) of a purified honest sender in
  the quantum random oracle model.
\end{itemize}

\section{The conjecture}\label{sec:conjectures}

\begin{definition}[degree and influence over a finite abelian group]
\label{def:deginf}
Let $\cY$ be a finite abelian group and let $f\colon\cY^N\to\CC$ have
Fourier expansion $f=\sum_{\chi\in\dY^N}\hat{f}(\chi)\,\chi$.
\begin{itemize}
  \item The \emph{degree} of a character
  $\chi=(\chi_1,\dots,\chi_N)\in\dY^N$ is
  $\deg(\chi):=\bigl\lvert\{i\in[N]\ :\ \chi_i\ne\hat{0}\}\bigr\rvert$,
  and the \emph{degree} of $f$ is
  \[ \deg(f):=\max\bigl\{\deg(\chi)\ :\ \hat{f}(\chi)\ne 0\bigr\}, \]
  with $\deg(f):=0$ when $f$ is identically zero.
  \item The \emph{influence} of coordinate $i\in[N]$ on $f$ is
  \[ \operatorname{Inf}_i(f):=
     \sum_{\substack{\chi\in\dY^N\\ \chi_i\ne\hat{0}}}
     \bigl\lvert\hat{f}(\chi)\bigr\rvert^{2}. \]
\end{itemize}
For $\cY=\ZZ_2$ these specialise to the usual notions for multilinear
polynomials $f=\sum_{S\subseteq[N]}\alpha_S\prod_{i\in S}x_i$ over
variables $x_i\in\{\pm 1\}$, namely
$\deg(f)=\max_{\alpha_S\ne 0}\lvert S\rvert$ and
$\operatorname{Inf}_i(f)=\sum_{S\ni i}\alpha_S^{2}$.
\end{definition}

\begin{conjecture}[polynomial compatibility]\label{conj:main}
There exist a finite abelian group $\cY$, constants $c_1\in(0,1]$ and
$c_2>0$, and a function $\delta\colon\NN\to(0,1]$ satisfying
$\delta(d)\ge c_1\,d^{-c_2}$ for all $d\ge 1$ --- equivalently,
$\delta(d)\ge 1/p(d)$ for some polynomial $p$ --- such that for every
$d\in\NN$ and every $N\in\NN$ the following holds.

Let $\bF$ and $\bG$ be any two probability distributions over functions
$\cY^N\to\CC$ such that:
\begin{itemize}
  \item \emph{unit $\ell_2$ norm:} $\lVert f\rVert_2 = 1$ for every
  $f\in\operatorname{supp}(\bF)$ and $\lVert g\rVert_2 = 1$ for every
  $g\in\operatorname{supp}(\bG)$;
  \item \emph{degree at most $d$:} $\deg(f)\le d$ for every
  $f\in\operatorname{supp}(\bF)$ and $\deg(g)\le d$ for every
  $g\in\operatorname{supp}(\bG)$;
  \item \emph{$\delta$-influences on average:} for every $i\in[N]$,
  \[
    \begin{aligned}
      \mathop{\mathbb{E}}_{f\sample\bF}
        \bigl[\operatorname{Inf}_i(f)\bigr]
        &\ \le\ \delta(d) \quad\text{and} \\
      \mathop{\mathbb{E}}_{g\sample\bG}
        \bigl[\operatorname{Inf}_i(g)\bigr]
        &\ \le\ \delta(d).
    \end{aligned}
  \]
\end{itemize}
Then there exist $f\in\operatorname{supp}(\bF)$,
$g\in\operatorname{supp}(\bG)$, and $x\in\cY^N$ such that
\[ f(x)\cdot g(x)\ \ne\ 0. \]
\end{conjecture}

\begin{remark}[what the quantifiers do and do not allow]
\label{rem:quant}
Note that $\delta$ is allowed to depend on $d$ but not on $N$, and that
the group $\cY$ is existentially quantified: exhibiting a single finite
abelian group for which the above holds settles the conjecture
affirmatively.
\end{remark}

\section{Bibliography}

\begin{conjurabibliography}{99}

\bibitem[AA09]{AA09}
S. Aaronson, A. Ambainis.
\emph{The need for structure in quantum speedups}.
arXiv preprint arXiv:0911.0996, 2009.

\bibitem[ACC22]{ACC22}
P. Austrin, H. Chung, K.-M. Chung, S. Fu, Y.-T. Lin, M. Mahmoody.
\emph{On the impossibility of key agreements from quantum random
oracles}.
Annual International Cryptology Conference (CRYPTO), 2022.

\bibitem[BB21]{BB21}
N. Bitansky, Z. Brakerski.
\emph{Classical binding for quantum commitments}.
Theory of Cryptography Conference, pages 273--298, Springer, 2021.

\bibitem[CGLQ20]{CGLQ20}
K.-M. Chung, S. Guo, Q. Liu, L. Qian.
\emph{Tight quantum time-space tradeoffs for function inversion}.
61st Annual Symposium on Foundations of Computer Science (FOCS), pages
673--684, IEEE Computer Society Press, 2020.

\bibitem[CLM23]{CLM23}
K.-M. Chung, Y.-T. Lin, M. Mahmoody.
\emph{Black-Box Separations for Non-Interactive Commitments in a Quantum
World}.
Cryptology ePrint Archive, Report 2023/570, 2023 (report number and year
taken from the harvested filename, not printed on the page). [UNVERIFIED]

\bibitem[CX21]{CX21}
S. Cao, R. Xue.
\emph{Being a permutation is also orthogonal to one-wayness in quantum
world: Impossibilities of quantum one-way permutations from one-wayness
primitives}.
Theoretical Computer Science, 855:16--42, 2021.

\bibitem[DS89]{DS89}
D. L. Donoho, P. B. Stark.
\emph{Uncertainty principles and signal recovery}.
SIAM Journal on Applied Mathematics, 49(3):906--931, 1989.

\bibitem[GL89]{GL89}
O. Goldreich, L. A. Levin.
\emph{A hard-core predicate for all one-way functions}.
21st Annual ACM Symposium on Theory of Computing (STOC), pages 25--32,
ACM Press, 1989.

\bibitem[HY20]{HY20}
A. Hosoyamada, T. Yamakawa.
\emph{Finding collisions in a quantum world: Quantum black-box
separation of collision-resistance and one-wayness}.
Advances in Cryptology --- ASIACRYPT 2020, Part I, volume 12491 of LNCS,
pages 3--32, Springer, 2020.

\bibitem[MP12]{MP12}
M. Mahmoody, R. Pass.
\emph{The curious case of non-interactive commitments --- on the power of
black-box vs.\ non-black-box use of primitives}.
Advances in Cryptology --- CRYPTO 2012, volume 7417 of LNCS, pages
701--718, Springer, 2012.

\bibitem[Zha19]{Zha19}
M. Zhandry.
\emph{How to record quantum queries, and applications to quantum
indifferentiability}.
Advances in Cryptology --- CRYPTO 2019, Part II, volume 11693 of LNCS,
pages 239--268, Springer, 2019.

\end{conjurabibliography}

\end{document}
