






















In the Element Distinctness problem, one is given an array $a_1,\dots, a_n$ of integers from $[poly(n)]$ and is tasked to decide if $\{a_i\}$ are mutually distinct. Beame, Clifford and Machmouchi (FOCS 2013) gave a low-space algorithm for this problem running in space $S(n)$ and time $T(n)$ where $T(n) \le \widetilde{O}(n^{3/2}/S(n)^{1/2})$, assuming a random oracle (i.e., random access to polynomially many random bits). A recent breakthrough by Chen, Jin, Williams and Wu (SODA 2022) showed how to remove the random oracle assumption in the regime $S(n) = polylog(n)$ and $T(n) = \widetilde{O}(n^{3/2})$. They designed the first truly $polylog(n)$-space, $\widetilde{O}(n^{3/2})$-time algorithm by constructing a small family of hash functions $\mathcal{H} \subseteq \{h | h:[poly(n)]\to [n]\}$ with a certain pseudorandom property. In this paper, we give a significantly simplified analysis of the pseudorandom hash family by Chen et al. Our analysis clearly identifies the key pseudorandom property required to fool the BCM algorithm, allowing us to explore the full potential of this construction. As our main result, we show a time-space tradeoff for Element Distinctness without random oracle. Namely, for every $S(n),T(n)$ such that $T\approx \widetilde{O}(n^{3/2}/S(n)^{1/2})$, our algorithm can solve the problem in space $S(n)$ and time $T(n)$. Our algorithm also works for a related problem Set Intersection, for which this tradeoff is tight due to a matching lower bound by Dinur (Eurocrypt 2020). As two additional contributions, we show a more general pseudorandom property of the hash family, and slightly improve the seed length to sample the pseudorandom hash function.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。