% =====================================================================
%  CONJURA CONJECTURE STATEMENT
%  Post-quantum minimality of one-way functions under non-black-box
%  security reductions.
%  Requires conjura-conjecture.cls in the same directory.
% =====================================================================
\documentclass{conjura-conjecture}

\runninghead{POST-QUANTUM MINIMALITY OF OWFS, NON-BLACK-BOX}

\newcommand{\bits}{\{0,1\}}
\newcommand{\Pc}{\mathcal{P}}
\newcommand{\Qc}{\mathcal{Q}}
\newcommand{\Fc}{\mathcal{F}}
\newcommand{\Rc}{\mathcal{R}}
\newcommand{\Es}{\mathsf{E}}
\newcommand{\PPT}{\mathrm{PPT}}
\newcommand{\QPT}{\mathrm{QPT}}
\newcommand{\QPTpoly}{\mathrm{QPT}/\mathrm{poly}}
\newcommand{\ket}[1]{|#1\rangle}

\begin{document}

\cjkicker{CONJURA \textperiodcentered{} OPEN PROBLEM}
\cjtitle{Post-Quantum Minimality of One-Way Functions Under Non-Black-Box
  Security Reductions}
\cjsubtitle{The classical implication is proved without a black-box
  reduction between the security games}
\cjstatus{Statement: AI-written from Sam Buxbaum and Mohammad Mahmoody,
  \emph{A Note on the Minimality of One-Way Functions in Post-Quantum
  Cryptography}, IACR Communications in Cryptology, Vol.~1, No.~4, 2024
  (received 2024-10-09, accepted 2024-12-03; also Cryptology ePrint
  Archive, Report 2024/2095, 2024), not yet checked by a human. Settled
  affirmatively whenever the classical implication from $\Qc$ to one-way
  functions is witnessed by a black-box reduction between the two
  security games, with the implementation reduction arbitrary, for both
  uniform and non-uniform quantum adversaries and also for reductions
  that assume a deterministic adversary; open when that security
  implication is not witnessed by such a black-box reduction, and the
  paper takes no position on which way it goes.}
\cjcategory{\emph{Foundations}.}

\vspace{0.4em}

\begin{informalconjecture}
In classical cryptography, one-way functions are the minimal assumption:
almost every basic primitive implies them. Post-quantum cryptography
keeps the protocols classical but lets the attacker be quantum, and it is
not obvious that the classical implications survive, because a classical
proof that a primitive implies one-way functions typically works by
taking an attacker on the one-way function and running it, repeatedly and
from rewound states, to attack the primitive. Rewinding a quantum
attacker is not generally possible. This paper shows the implications do
survive whenever the classical proof is a black-box reduction between the
two security games and the target primitive's security is defined by a
two-message challenge-response game, which is the case for one-way
functions; the argument replaces the quantum attacker by an equivalent
stateful one that answers repeated questions consistently, so that
rewinding it gains the reduction nothing and it becomes indistinguishable
from an inefficient classical attacker the reduction was designed for.
What the paper does not settle is the case where the classical
implication is not proved by such a black-box reduction: the reduction
may inspect the code of the attacker, and while a uniform quantum
attacker is still generated by classical code, its state --- and, in the
non-uniform case, its quantum advice --- has no classical description.
The paper does not say why this case resists; it simply records it as
unresolved. The question is whether the classical implication still
lifts, so that one-way functions are minimal for post-quantum
cryptography with no restriction on how the classical proof was carried
out.
\end{informalconjecture}

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

One-way functions are the minimal assumption of classical cryptography:
Impagliazzo and Luby showed that identification protocols, symmetric-key
encryption, commitments and coin flipping all imply them~\cite{IL89}, and
the standard way such implications are established is a black-box
reduction, which uses the primitive and the adversary as oracles and
therefore relativizes~\cite{RTV04}. Non-black-box security reductions,
which exploit the code of the adversary, exist but are comparatively
rare~\cite{Bar01}.

Quantum cryptography appears to have a different assumption hierarchy:
there are oracles relative to which pseudorandom quantum states exist
while $\mathbf{BQP} = \mathbf{QMA}$~\cite{Kre21}, and a classical oracle
relative to which single-copy pseudorandom states exist while
$\mathbf{P} = \mathbf{NP}$~\cite{KQST23}, so quantum analogues of one-way
functions may not sit at the base. \emph{Post-quantum} cryptography is
the intermediate regime: protocols and challengers stay classical, but
adversaries are quantum. Whether the classical hierarchy survives there
is not automatic, because a classical security reduction may rewind its
adversary, and rewinding destroys the internal state of a quantum one.
This is the difficulty that work on constructive post-quantum
reductions~\cite{BBK22} and on universal reductions relative to stateful
oracles~\cite{CFP22} addresses, in both cases under restrictions on the
reduction (single-copy adversaries, non-adaptivity, or straight-line
behaviour).

The present paper removes those restrictions on the \emph{reduction} and
instead restricts the \emph{game}. Its main theorem: if a classical
black-box game-based security reduction proves that $\Qc$ implies a
primitive $\Pc$ whose security game has only two messages, then any
efficient quantum adversary breaking $\Pc$ can be turned into an
efficient quantum adversary breaking $\Qc$, so the implication lifts. The
technique replaces the quantum adversary by a lazily-evaluated,
memoizing version, which answers repeated queries identically and is
therefore statistically indistinguishable, even under rewinding and
resetting, from an inefficient classical adversary of the same advantage;
a two-message game asks the adversary only one question, so this
modification costs nothing in advantage. Since one-way functions have a
two-message falsifiable game, every primitive that classically implies
one-way functions by a black-box game-based reduction implies
post-quantum one-way functions post-quantumly, for uniform and
non-uniform quantum adversaries alike, and even when the reduction
assumes its adversary is deterministic.

The hypothesis that the security reduction is black-box is what makes the
whole argument possible: the proof works by substituting a doctored
adversary into $\Rc$ as an oracle. When the classical implication from
$\Qc$ to one-way functions is proved some other way, the paper's
machinery has nothing to substitute into, and the paper records this case
as unresolved. Note that the paper's results are already insensitive to
how the \emph{implementation} is built from $\Qc$: that may be
arbitrarily non-black-box. Only the security direction is constrained.

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

\begin{itemize}
\item $n \in \mathbb{N}$ is the security parameter. A function is
  \emph{negligible} if it is eventually smaller than $1/p(n)$ for every
  polynomial $p$; a probability is \emph{non-negligible} otherwise.
\item $\PPT$ denotes a classical probabilistic polynomial-time
  algorithm.
\item $\QPT$ denotes a uniform efficient quantum algorithm with
  classical inputs and outputs: a family $\{Q_n\}_{n \in \mathbb{N}}$ of
  quantum circuits of size $\poly(n)$ whose descriptions are produced by
  a $\PPT$ machine on input $1^n$, with work registers initialized to
  $\ket{0}$ and the output register measured in the computational basis.
\item $\QPTpoly$ denotes the non-uniform variant: the same, except the
  work registers of $Q_n$ are initialized with a quantum advice state
  $\ket{\phi_n}$ on $\poly(n)$ qubits, depending only on $n$.
\item $\Es$ ranges over $\{\QPT, \QPTpoly\}$ and denotes the class of
  efficient quantum adversaries fixed in the statement.
\item $\Pc = (F_{\Pc}, R_{\Pc})$ denotes a classical primitive, with
  $F_{\Pc}$ its set of correct implementations and $R_{\Pc}$ its
  breaking relation; $C_{\Pc,f}$ is its challenger on implementation $f$
  and $t_{\Pc}$ its success threshold. $\Pc'$ denotes the post-quantum
  variant of $\Pc$.
\item $\Qc$ and $\Qc'$ denote the primitive in the hypothesis and its
  post-quantum variant; $\Fc$ and $\Fc'$ denote the one-way function
  primitive and its post-quantum variant.
\item $f$ denotes an implementation of $\Qc$ and $g_f$ the implementation
  of $\Fc$ obtained from it; $A$, $A_{\Pc}$, $A_{\Qc}$, $A_{\Fc}$ denote
  adversaries, and $\Rc$ a black-box reduction.
\end{itemize}

The parameters are:
\begin{itemize}
\item $n$, the security parameter; all efficiency and negligibility are
  asymptotic in it.
\item $\Es$, the fixed class of efficient quantum adversaries, either
  uniform ($\QPT$) or non-uniform with polynomial-size quantum advice
  ($\QPTpoly$). The conjecture is asserted for each choice separately.
\item $\Qc$, an arbitrary classical primitive with a game-based security
  definition, quantified universally.
\item $t_{\Qc}$, the success threshold of $\Qc$'s security game;
  unrestricted (it may be $0$, $1/2$, or anything else).
\item $f, g_f$: a $\PPT$ implementation of $\Qc$, and the $\PPT$
  implementation of one-way functions built from it by the
  implementation clause of the reduction.
\end{itemize}

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

\begin{definition}[Game-based classical primitive]\label{def:prim}
A \emph{classical primitive} is a pair $\Pc = (F_{\Pc}, R_{\Pc})$, where
$F_{\Pc}$ is a set of (possibly inefficient) randomized algorithms,
called the correct implementations of $\Pc$, and $R_{\Pc}$ is a relation
on pairs $(f, A)$ of algorithms; $(f,A) \in R_{\Pc}$ is read ``$A$
$\Pc$-breaks $f$''.

The primitive is \emph{game-based} if $R_{\Pc}$ is given by a security
game: an interactive protocol, over classical communication, between a
challenger $C_{\Pc,f}$ (which may depend on the implementation $f$) and
an adversary $A$, on common input the security parameter $1^n$, at the
end of which $C_{\Pc,f}$ outputs $1$ (``$A$ wins'') or $0$; together
with a \emph{success threshold} $t_{\Pc} : \mathbb{N} \to [0,1]$. Then
$(f,A) \in R_{\Pc}$ iff there is a polynomial $p$ such that
\begin{align*}
  \Pr\big[\,C_{\Pc,f}(1^n)&\text{ outputs } 1
    \text{ against } A\,\big]\\
  &\ \ge\ t_{\Pc}(n) + \tfrac{1}{p(n)}
\end{align*}
for infinitely many $n \in \mathbb{N}$.
\end{definition}

\begin{definition}[Classical and post-quantum
existence]\label{def:exist}
Let $\Pc = (F_{\Pc}, R_{\Pc})$ be a game-based classical primitive.

$\Pc$ \emph{exists classically} if there is a $\PPT$ implementation
$f \in F_{\Pc}$ such that no $\PPT$ algorithm $A$ satisfies
$(f,A) \in R_{\Pc}$.

The \emph{post-quantum variant} $\Pc'$ of $\Pc$ against a class $\Es$ of
efficient quantum adversaries is the same primitive with the same
implementations and the same challenger $C_{\Pc,f}$, with the adversary
now ranging over $\Es$; the communication with the challenger remains
classical. Thus $\Pc'$ \emph{exists} if there is a $\PPT$ implementation
$f \in F_{\Pc}$ such that no $A \in \Es$ wins $C_{\Pc,f}(1^n)$ with
probability at least $t_{\Pc}(n) + 1/p(n)$ for any polynomial $p$ and
infinitely many $n$.
\end{definition}

\begin{definition}[One-way functions as a game-based
primitive]\label{def:owf}
The primitive $\Fc = (F_{\Fc}, R_{\Fc})$ of one-way functions has
$F_{\Fc}$ equal to the set of all functions
$f : \bits^* \to \bits^*$, viewed as deterministic algorithms; a $\PPT$
implementation is one computable in deterministic polynomial time.

Its security game is the $2$-message game with threshold $t_{\Fc} = 0$:
on security parameter $1^n$ the challenger samples $x \sample \bits^n$
and sends $f(x)$; the adversary replies with a single message $x'$; the
challenger outputs $1$ iff $f(x') = f(x)$.

Hence $\Fc$ exists classically iff classical one-way functions exist,
and $\Fc'$ exists against $\Es$ iff there is a deterministic
polynomial-time computable $f$ with
\[
  \Pr_{\substack{x \sample \bits^n,\\ x' \sample A(f(x),1^n)}}
  \big[f(x') = f(x)\big]
\]
negligible in $n$ for every $A \in \Es$.
\end{definition}

\begin{definition}[Potentially non-constructive
reduction]\label{def:red}
A \emph{potentially non-constructive reduction} from a classical
primitive $\Pc = (F_{\Pc}, R_{\Pc})$ to a classical primitive
$\Qc = (F_{\Qc}, R_{\Qc})$ exists if both of the following hold.
\begin{enumerate}
\item \emph{Implementation.} For every $\PPT$ implementation
  $f \in F_{\Qc}$ there is a $\PPT$ implementation $g_f \in F_{\Pc}$.
\item \emph{Security.} For every $\PPT$ implementation $f \in F_{\Qc}$:
  if there is a $\PPT$ adversary $A_{\Pc}$ that $\Pc$-breaks $g_f$, then
  there is a $\PPT$ adversary $A_{\Qc}$ that $\Qc$-breaks $f$.
\end{enumerate}
Neither clause carries any black-box requirement; clause 2 is a bare
existential statement, and clauses 1 and 2 together entail that the
classical existence of $\Qc$ implies the classical existence of $\Pc$.

A reduction is additionally \emph{game-based black-box} if $\Pc$ and
$\Qc$ are game-based and the existence of $A_{\Qc}$ in clause 2 is
established by a black-box reduction: a $\PPT$ oracle algorithm $\Rc$
that is additionally given $1^{1/\varepsilon}$ as an input parameter,
such that for every (possibly inefficient) adversary $A$ winning in
$C_{\Pc,g_f}$ with advantage
$\varepsilon(n_1) \ge 1/\poly(n_1)$ at every security parameter $n_1$,
the algorithm $\Rc^{A}$ wins in $C_{\Qc,f}$ with advantage
$\delta_{\varepsilon} \ge 1/\poly(n_2)$ above $t_{\Qc}$, where $\Rc$ may
query $A$ on inputs of its choice, on several security parameters, and
may rewind $A$ or reset its randomness.
\end{definition}

\begin{conjecture}[post-quantum minimality of one-way functions without a
black-box security reduction]\label{conj:main}
Fix a class of efficient quantum adversaries
$\Es \in \{\QPT, \QPTpoly\}$, and keep it fixed throughout.

Let $\Qc = (F_{\Qc}, R_{\Qc})$ be any classical primitive with a
game-based security definition (Definition~\ref{def:prim}), with
challenger $C_{\Qc,f}$ and success threshold $t_{\Qc}$, and let $\Fc$ be
the one-way function primitive (Definition~\ref{def:owf}).

Suppose that a potentially non-constructive reduction from $\Fc$ to
$\Qc$ exists in the sense of Definition~\ref{def:red}; this is the
paper's formalization of the classical existence of $\Qc$ implying the
classical existence of one-way functions, and in particular it entails
that implication. No assumption is made about how the security clause of
Definition~\ref{def:red} is established: in particular, the passage from
a $\PPT$ adversary $A_{\Fc}$ breaking $g_f$ to a $\PPT$ adversary
$A_{\Qc}$ breaking $f$ need \emph{not} be witnessed by a black-box
reduction from winning in $C_{\Qc,f}$ to winning in $C_{\Fc,g_f}$, and
may depend arbitrarily on the code of $A_{\Fc}$.

Then: if the post-quantum variant $\Qc'$ of $\Qc$ against $\Es$ exists
(Definition~\ref{def:exist}), one-way functions secure against $\Es$
exist, i.e.\ the post-quantum variant $\Fc'$ of $\Fc$ against $\Es$
exists.
\end{conjecture}

\begin{remark}[openness]\label{rem:open}
The paper poses the question and records the non-black-box case as
unresolved: ``Our work leaves open answering our main question when Q
implies OWFs through a non-black-box security reduction, or when P uses a
more complicated security game than a two-message one'' (p.~1). The
question itself is stated there as ``If a classically secure
cryptographic primitive Q implies one-way functions, does the
post-quantum-secure variant of P imply (post-quantum) one-way functions
as well?'' (p.~3). The paper conjectures no direction, so the affirmative
phrasing of Conjecture~\ref{conj:main} is a site convention rather than
the authors' claim, and a solver should treat both directions as live.
\end{remark}

\begin{remark}[what is proved]\label{rem:progress}
Theorem~1 lifts any classical black-box reduction from a game $\Qc$ to a
$2$-message game $\Pc$ to the post-quantum setting, uniformly and
non-uniformly. Theorem~3 turns this into a statement about primitives,
and Corollary~1 specialises it to $\Pc = {}$ one-way functions, with no
restriction on how the reduction calls its adversary, because the one-way
function game is falsifiable: ``To derive Corollary 1 from Theorem 3 we
merely observe that one-way functions have a 2-message security game and
that their security game is falsifiable'' (p.~22). Theorem~2 extends the
lifting to reductions that assume their oracle adversary is
deterministic, under any one of three side conditions ($\Qc$
threshold-zero with single-security-parameter calls; $\Pc$ falsifiable;
$\Qc$ falsifiable with single-security-parameter calls). In the other
direction, the paper observes that the $2$-message restriction on $\Pc$
cannot simply be dropped: a contrived primitive built from the
$4$-message qubit certification test of Brakerski et al.\ is implied by
LWE classically through a black-box reduction but, the paper argues, not
post-quantumly unless LWE is quantumly broken.
\end{remark}

\begin{remark}[the scope of the black-box hypothesis]\label{rem:scope}
Only the security direction is constrained in the settled case: ``This
means that our results do not depend on how the implementation reduction
is performed, as formalized in [RTV04], meaning that we can handle
non-black-box constructions, so long as the security reduction is a
black-box reduction between games'' (p.~11). The post-quantum variant is
the same primitive with a quantum adversary: ``Then, we define the
post-quantum variant of P to be the same primitive, but now the security
definition allows efficient quantum adversaries to participate in the
same security game (using classical communication)'' (p.~11).
\end{remark}

\begin{remark}[caveats for a reviewer]\label{rem:caveats}
Four things a reviewer should press on. First, whether this is a problem
or a programme: the paper gives no account of what makes the
non-black-box case hard and offers no partial result towards it.
``Non-black-box security reduction'' is not a structured class the way
black-box reductions are; the hypothesis of
Conjecture~\ref{conj:main}, as Definition~\ref{def:red} makes explicit,
is little more than the bare implication ``$\Qc$ classically exists
$\Rightarrow$ one-way functions classically exist'', so a positive proof
would have to be a general lifting theorem with no reduction structure to
grip. The honest reading may be that the affirmative direction is not
attackable, and that only the refuting direction --- a contrived
primitive, in the style of the paper's own $4$-message counterexample ---
has a visible line of attack. Second, the paper leaves the question open
without conjecturing a direction (Remark~\ref{rem:open}). Third, the
literature after December~2024 has not been checked for a resolution, and
the paper is short and recent enough that a follow-up could exist.
Fourth, the third ``Furthermore'' clause of Corollary~1
(deterministic-adversary reductions) is asserted for one-way functions on
the strength of the falsifiability of the one-way function game; the
conjecture above is deliberately kept free of any deterministic-adversary
hypothesis, matching the black-box statement the paper proves.
\end{remark}

\section{Bibliography}

\begin{conjurabibliography}{99}

\bibitem[Bar01]{Bar01}
Boaz Barak.
\emph{How to go beyond the black-box simulation barrier}.
42nd IEEE Symposium on Foundations of Computer Science, pages 106--115,
2001.

\bibitem[BBK22]{BBK22}
Nir Bitansky, Zvika Brakerski, and Yael Tauman Kalai.
\emph{Constructive post-quantum reductions}.
Advances in Cryptology --- CRYPTO 2022, pages 654--683, Springer, 2022.

\bibitem[CFP22]{CFP22}
Benjamin Chan, Cody Freitag, and Rafael Pass.
\emph{Universal reductions: Reductions relative to stateful oracles}.
Theory of Cryptography (TCC), pages 151--180, Springer, 2022.

\bibitem[IL89]{IL89}
Russell Impagliazzo and Michael Luby.
\emph{One-way functions are essential for complexity based
cryptography}.
30th Annual Symposium on Foundations of Computer Science, pages
230--235, 1989.

\bibitem[KQST23]{KQST23}
William Kretschmer, Luowen Qian, Makrand Sinha, and Avishay Tal.
\emph{Quantum cryptography in algorithmica}.
55th Annual ACM Symposium on Theory of Computing (STOC), pages
1589--1602, 2023.

\bibitem[Kre21]{Kre21}
William Kretschmer.
\emph{Quantum Pseudorandomness and Classical Complexity}.
16th Conference on the Theory of Quantum Computation, Communication and
Cryptography (TQC 2021), LIPIcs vol.~197, pages 2:1--2:20, 2021.

\bibitem[RTV04]{RTV04}
Omer Reingold, Luca Trevisan, and Salil Vadhan.
\emph{Notions of reducibility between cryptographic primitives}.
Theory of Cryptography (TCC), pages 1--20, Springer, 2004.

\end{conjurabibliography}

\end{document}
