\documentclass{conjura-conjecture}

\newcommand{\NN}{[N]}

\runninghead{3-WAY COLLISIONS, BOUNDED MEMORY}

\begin{document}

\cjkicker{CONJURA \textperiodcentered{} OPEN PROBLEM}
\cjtitle{Finding a Three-Way Collision with Bounded Memory}
\cjsubtitle{The Oblivious Sequential Time--Memory Curve}
\cjstatus{Statement: AI-written, not yet formalized.}
\cjcategory{Symmetric-Key Cryptography.}
\cjkeywords{$3$-collisions; multi-collision finding; branching programs; time--space
  tradeoffs; oblivious algorithms; streaming switching lemma; bounded-memory cryptanalysis.}

\vspace{0.4em}

\begin{informalconjecture}
Fix a schedule of queries to a random function in advance -- an \emph{oblivious} algorithm
-- and allow it $S$ bits of working memory. Finding three inputs with a common output should
cost about $N/\sqrt S$ queries once $S$ exceeds polylogarithmic size, until this curve meets
the unconditional threshold of $N^{2/3}$ queries at $S \approx N^{2/3}$, beyond which memory
buys nothing further. Both endpoints are already known -- a proved theorem at
polylogarithmic $S$, and the query threshold at any memory -- and a matching algorithm
(build a table of two-way collisions, then hunt a third match to one of them) achieves the
curve throughout. The conjecture is that no oblivious algorithm can beat it.
\end{informalconjecture}

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

Multi-collision search asks how many queries to a random function are needed to name $k$
points with a common image; this note takes up the case $k = 3$ under a bound on the
algorithm's working memory, in the model where the query schedule is fixed in advance.
Section~\ref{sec:conjecture} formalizes the statement above.

\smallskip
\noindent\textbf{Notation.}
Throughout, $N \geq 2$ and $f \colon \NN \to \NN$ is a uniformly random function, available only
through an oracle answering $x \mapsto f(x)$.  A \emph{$k$-collision} is a set of $k$ distinct
points of $\NN$ with a common image under $f$; a \emph{$3$-collision} is the case $k = 3$.
Asymptotic notation $\tilde O, \tilde\Omega, \tilde\Theta$ suppresses factors polylogarithmic in
$N$.  Success probabilities are over the choice of $f$ and any coins of the algorithm;
randomisation need not be allowed for separately, since the input is already random.

\smallskip
\noindent\textbf{The model.}
A \emph{branching program} -- the model of Borodin and Cook~\cite{BC82}, specialised to a
random-function oracle -- queries one point of $\NN$ at a time, with its state between queries
capped at $S$ bits; the state may encode anything, so one cannot say what a program \emph{knows}.
It is \emph{oblivious} if its query schedule is fixed in advance, independent of the answers seen
so far, and \emph{repetition-free} if no point is queried twice.  Definition~\ref{def:bp}
formalizes the model.

\smallskip
\noindent\textbf{What is known.}
Four facts fix the landscape.

\begin{enumerate}[label=(F\arabic*),ref=F\arabic*,leftmargin=*,itemsep=1pt,topsep=2pt]
\item\label{F1} \emph{The query threshold is $N^{2/3}$.}  Among $q$ queried points the expected
  number of $3$-collisions is $\binom{q}{3}N^{-2}$, so $q = \Theta(N^{2/3})$ queries are necessary
  and sufficient for constant success probability~\cite{STKT06}.  Quantitatively, an algorithm
  making $T$ queries and then naming three points succeeds with probability
  $O\bigl((T^{3}+1)N^{-2}\bigr)$.  This holds for \emph{any} algorithm, at any memory bound, and
  the conjecture below does not contradict it.
\item\label{F2} \emph{Without a table, $\Theta(N)$ queries suffice.}  Find a $2$-collision
  $\{u,v\}$ by cycle-finding, retain $u$, $v$ and $y = f(u)$, then sample fresh points until one
  maps to $y$.  This uses $O(\log N)$ bits of memory.
\item\label{F3} \emph{The oblivious base case is proved.}  Every repetition-free oblivious
  branching program succeeding with probability at least $\tfrac12$ satisfies
  $T \cdot \bigl(S + \lceil \log_{2} N \rceil\bigr) = \tilde\Omega(N)$; in particular
  $T = \tilde\Omega(N)$ at width $N^{O(1)}$.  The only lower bound known at $k=3$, it is tight
  exactly at $S = \mathrm{polylog}$, matching~\ref{F2}, via the multi-pass streaming switching
  lemma of Dinur~\cite{Din20} applied to the answer stream.  For \emph{adaptive} programs nothing
  memory-sensitive is known at $k=3$: the only available lower bound is the query
  bound~\ref{F1}, which mentions no memory at all.
\item\label{F4} \emph{At $k=2$ memory is free.}  Pollard's rho method~\cite{Pol75} with Brent's
  cycle detection~\cite{Bre80} finds a $2$-collision in $\Theta(\sqrt N)$ queries using
  $O(\log N)$ bits, and that count is optimal even with unbounded memory.  Consequently the
  conjecture below is \emph{false} at $k = 2$, and no proof of it can be indifferent to the
  collision order.
\end{enumerate}

\smallskip
\noindent\textbf{The gap.}
Above $S = \mathrm{polylog}$, fact~\ref{F3} stops being tight: an oblivious program can
accumulate $P \leq S$ collision pairs at cost $\tilde\Theta(PN/S)$ and then hunt a third preimage
of one of the $P$ recorded values in $\tilde\Theta(N/P)$ further queries, both phases
non-adaptively; balancing at $P = \sqrt S$ gives $T = \tilde\Theta(N/\sqrt S)$.  A factor
$\sqrt S$ thus separates~\ref{F3} from this algorithm, and closing it is the question taken up
below.

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

Notation as in Section~\ref{sec:setting}.  Definition~\ref{def:bp} restates the branching-program
model formally, for self-containment; the conjecture quantifies over all repetition-free
oblivious branching programs.

\begin{definition}[branching program {\cite{BC82}}]\label{def:bp}
A \emph{branching program} of length $T$ and width $W$ is a DAG on levels $0,\dots,T$ with at
most $W$ nodes per level, in which every node below level $T$ carries a label $x \in \NN$ and has
one outgoing edge for each $y \in \NN$, and every node at level $T$ carries a label in $\NN^{3}$.
It is run by starting at the source, querying the label of the current node, following the edge
labelled by the answer, and reading the label of the sink reached; it \emph{succeeds} if that
label is a $3$-collision.  Its \emph{space} is $S = \log_{2} W$, counted in bits.  It is
\emph{oblivious} if all nodes at a level carry the same label, so that the query schedule
$w_{1},\dots,w_{T}$ is fixed in advance, and \emph{repetition-free} if no point labels two
levels.
\end{definition}

\begin{conjecture}[BS0$^{+}$: the oblivious sequential curve at $k=3$]\label{conj:main}
Every repetition-free oblivious branching program succeeding with probability at least $\tfrac12$
satisfies
\[
  T \;=\; \tilde\Omega\bigl(\max\{\, N^{2/3},\; N/\sqrt{S} \,\}\bigr),
\]
\[
  \text{equivalently} \qquad
  T \cdot S^{1/2} \;=\; \tilde\Omega(N) \ \text{ for } S \leq N^{2/3}.
\]
\end{conjecture}

\begin{remark}[why this is the right curve]\label{rem:tightness}
The first clause is~\ref{F1} and carries no content; all of it is in $T \cdot S^{1/2}$.  The
bound is exactly tight against the algorithm of the gap paragraph above: balancing at
$P = \sqrt S$ gives $T = \tilde\Theta(N/\sqrt S)$, so a factor $\sqrt S$ separates~\ref{F3} from
the conjecture inside its own class.  The two clauses cross at $S = N^{2/3}$, where the curve
meets the query threshold and the problem closes.
\end{remark}

\section{Bibliography}

\begin{conjurabibliography}{STKT06}

\bibitem[BC82]{BC82}
Allan Borodin and Stephen Cook.
\emph{A time-space tradeoff for sorting on a general sequential model of computation}.
SIAM Journal on Computing, 11(2):287--297, 1982.

\bibitem[Bre80]{Bre80}
Richard P. Brent.
\emph{An improved Monte Carlo factorization algorithm}.
BIT Numerical Mathematics, 20(2):176--184, 1980.

\bibitem[Din20]{Din20}
Itai Dinur.
\emph{Tight time-space lower bounds for finding multiple collision pairs and their
applications}.
In EUROCRYPT 2020, volume 12105 of LNCS, pages 405--434. Springer, 2020.
Also: Cryptology ePrint Archive, Paper 2020/229.

\bibitem[Pol75]{Pol75}
John M. Pollard.
\emph{A Monte Carlo method for factorization}.
BIT Numerical Mathematics, 15(3):331--334, 1975.

\bibitem[STKT06]{STKT06}
Kazuhiro Suzuki, Dongvu Tonien, Kaoru Kurosawa and Koji Toyota.
\emph{Birthday paradox for multi-collisions}.
In ICISC 2006, volume 4296 of LNCS, pages 29--40. Springer, 2006.

\end{conjurabibliography}

\end{document}
