Pseudo-mixing Time of Random Walks

Abstract

We introduce the notion of pseudo-mixing time of a graph, defined as the number of steps in a random walk that suffices for generating a vertex that looks random to any polynomial-time observer. Here, in addition to the tested vertex, the observer is also provided with oracle access to the incidence function of the graph.

Assuming the existence of one-way functions, we show that the pseudo-mixing time of a graph can be much smaller than its mixing time. Specifically, we present bounded-degree N-vertex Cayley graphs that have pseudo-mixing time t for any $t(N)=\omega (\log \log N)$. Furthermore, the vertices of these graphs can be represented by string of length $2\log _2N$, and the incidence function of these graphs can be computed by Boolean circuits of size $\mathrm{poly}(\log N)$.

An early version of this work appeared as TR19-078 of ECCC. The presentation was somewhat elaborated in the current revision.

1 Introduction

A popular way to sample a huge set that is endowed with a group structure is to start at a fixed element of the set, which is typically easy to find, and take a random walk on the corresponding Cayley graph. If the length of the random walk exceeds the graph’s mixing time, then the end-point of the walk is almost uniformly distributed in the corresponding set.

A couple of comments are in place. First, the aforementioned sampling procedure is beneficial only when the original set S is non-trivial in the sense that its elements can be represented by bit-strings of a certain length, denoted $\ell$, but S may occupy only a negligible fraction of ${\{0,1\}}^\ell$ (i.e., $|S|<\mu (\ell )\cdot 2^\ell$, where $\mu :{\mathbb {N}}\rightarrow [0,1]$ is a negligible function (e.g., tends to zero faster than the reciprocal of any polynomial)). In such cases, it is infeasible to sample S (almost) uniformly by selecting uniformly few $\ell$-bit long strings and taking the first string that falls in S, and so one needs an alternative.

Second, the set S should be endowed with a feasible group operation, and the group should be generated be a small number of generators that are easy to find (along with their inverses). If this is that case, then we can sample S almost uniformly by taking a sufficiently long random walk on the corresponding Cayley graph, starting at the vertex that corresponds to the identity element (which we assume, without loss of generalization, to be represented by $0^\ell$).¹ Of course, the length of the random walk should slightly exceed the graph’s mixing time (i.e., the minimum t such that the total variation distance between the end-vertex of a t-step random walk and a uniformly distributed vertex is negligible).

The requirement that the random walk be longer than the mixing time of the graph is aimed at obtaining a distribution that is statistically close to the uniform distribution over the set of vertices. However, for actual applications, which may be modeled as efficient procedures that run in time that is polynomial in the length of the description of a vertex in the graph, it suffices to require that it is infeasible to distinguish the distribution of the end-point of the walk from a uniformly distributed vertex. Indeed, here we adopt the notion of computational indistinguishability, which underlies much of modern cryptography and the computational notion of pseudorandomness (cf. [3, Apdx. C] and [3, Chap. 8], resp.), and consider the following notion of “pseudo-mixing time” (which is formulated, as usual in the theory of computation, using asymptotic terms).

Definition 1

(pseudo-mixing time, a naive definition): For a constant d, let $\{G_\ell =(V_\ell ,E_\ell )\}_{\ell \in {\mathbb {N}}}$ be a sequence of d-regular graphs such that $0^\ell \in V_\ell \subseteq {\{0,1\}}^\ell$. For a function $t:{\mathbb {N}}\rightarrow {\mathbb {N}}$, the graphs $\{G_\ell \}_{\ell \in {\mathbb {N}}}$ have pseudo-mixing time at most t if for every probabilistic polynomial-time algorithm A it holds that

$$|\mathrm{Pr}[A(W_t(G_\ell ))\!=\!1]-\mathrm{Pr}[A(U(G_\ell ))\!=\!1]|=\mathtt{negl}(\ell ),$$

where $W_t(G_\ell )$ denotes the distribution of the end-point of a $t(|V_\ell |)$-long random walk on $G_\ell$ starting at $0^\ell$, and $U(G_\ell )$ denotes the uniform distribution over $V_\ell$. Indeed, $\mathtt{negl}$ denotes a negligible function (i.e., one that vanishes faster than 1/p, for any positive polynomial p).

Clearly, if the total variation distance between $W_t(G_\ell )$ and $U(G_\ell )$ is negligible (in terms of $\ell$), then $G_\ell$ has pseudo-mixing time at most t. The point is that this sufficient condition is not necessary; as we shall see, $G_\ell$ may have pseudo-mixing time at most t also in case that the total variation distance between $W_t(G_ell)$ and $U(G_\ell )$ is large (say, larger than 0.99).

Definition 1 is titled “naive” because algorithm A, which represents an observer that examines (or uses) the sampled vertex, does not get (or use) any auxiliary information about the graph $G_\ell$. In contrast, the motivating discussion referred to the case that one can take a random walk on the graph. Hence, it is natural to augment the (efficient) observer by providing it with a device that lists the neighbors of any vertex of its choice. In other words, we provide the observer with oracle access to the incidence function of the graph; this oracle answers the query (v, i) with the $i^\mathrm{th}$ neighbor of vertex v in the graph. Indeed, such a device constitutes a representation of the graph, and we are most interested in the case that this representation is succinct; that is, the incidence function can be computed by an efficient algorithm (given some short auxiliary information) or equivalently by a small Boolean circuit. This leads to the following definition.

Definition 2

(succinct representation of graphs and pseudo-mixing time): For a constant d, let $\{G_\ell =(V_\ell ,E_\ell )\}_{\ell \in {\mathbb {N}}}$ be a sequence of d-regular graphs such that $0^\ell \in V_\ell \subseteq {\{0,1\}}^\ell$. The graph $G_\ell$ is represented by its incidence function $g_\ell :V_\ell \times [d]\rightarrow V_\ell$, where $g_\ell (v,i)$ is the $i^\mathrm{th}$ neighbor of v in $G_\ell$.

• Succinct representation: The graphs $\{G_\ell \}_{\ell \in {\mathbb {N}}}$ have a succinct representation if there exists a family of $\mathrm{poly}(\ell )$-size Boolean circuits that compute their incidence functions.

• Pseudo-mixing time (revised): For a function $t:{\mathbb {N}}\rightarrow {\mathbb {N}}$, the graphs $\{G_\ell \}_{\ell \in {\mathbb {N}}}$ have pseudo-mixing time at most t if for every probabilistic polynomial-time oracle machine M it holds that

  $$|\mathrm{Pr}[M^{g_\ell }(W_t(G_\ell ))\!=\!1] -\mathrm{Pr}[M^{g_\ell }(U(G_\ell ))\!=\!1]|=\mathtt{negl}(\ell ),$$

  where $M^g(x)$ denotes the output of M on input x when making queries to the oracle g, and the other notations (e.g., $W_t(G_\ell )$ and $U(G_\ell )$) are as in Definition 1.

We stress that pseudo-mixing refers to observers that are efficient in terms of the length of the description of vertices in the graph (i.e., they run for $\mathrm{poly}(\ell )$-time). Recall that our focus is on the case that the size of $V_\ell$ is exponential in $\ell$. Hence, a polynomial-time machine cannot possibly explore the entire graph $G_\ell$. On the other hand, if $G_\ell$ is rapidly mixing (i.e., its mixing time is $O(\log |V_\ell |)$), then a polynomial-time machine may obtain many samples of $W_t(G_\ell )$ and $U(G_\ell )$ (or rather many samples that are distributed almost as $U(G_\ell )$).² At this point, we can state our main result.

Theorem 3

(main result): Assuming the existence of one-way functions, there exists a sequence of bounded-degree Cayley graphs $\{G_\ell =(V_\ell ,E_\ell )\}_{\ell \in {\mathbb {N}}}$ such that the following properties hold:

• 1. The graphs $\{G_\ell \}_{\ell \in {\mathbb {N}}}$ have a succinct representation.

• 2. For every $t:{\mathbb {N}}\rightarrow {\mathbb {N}}$ such that $t(N)=\omega (\log \log N)$, the graphs $\{G_\ell \}_{\ell \in {\mathbb {N}}}$ have pseudo-mixing time at most t.

• 3. The vertex set is hard to sample “without walking on the graph”: Any probabilistic polynomial-time algorithm that is given input $1^\ell$, fails to output a vertex of the graph other than $0^\ell$, except with negligible probability.³

Furthermore, the graph $G_\ell$ has $2^{(0.5+o(1))\cdot \ell }$ vertices, and its mixing time is $\varTheta (\ell )=\varTheta (\log |V_\ell |)$.

We stress that these bounded-degree graphs have size $N=\exp (\varTheta (\ell ))$, and so their pseudo-mixing time (i.e., $t(N)=\omega (\log \log N)=\omega (\log \ell )$) is only slightly larger than logarithmic in their (standard) mixing time (i.e., $\varTheta (\ell )=\varTheta (\log N)$). Indeed, the pseudo-mixing time of these graphs is only slightly larger than double-logarithmic in their size (i.e., $|V_\ell |$). In contrast, the pseudo-mixing time of bounded-degree graphs cannot be (strictly) double-logarithmic in $|V_\ell |$, since an observer can explore the $O(\log \log |V_\ell |)$-neighborhood of $0^\ell$ in $\mathrm{poly}(\ell )$-time (and so distinguish vertices in this $\mathrm{poly}(\ell )$-sized set from all other $\exp (\varTheta (\ell ))$ vertices of the graph).

We comment that, as shown in Theorem 7, the existence of one-way functions is essential for the conclusion of Theorem 3. Essentially, the existence of one-way function, which implies the existence of pseudorandom generators, allows to construct Cayley graphs $G_\ell$ with succinct representation in which all vertices (except for $0^\ell$) look random. Of course, once we reach a vertex in $G_\ell$ by following a walk from the vertex $0^\ell$, we learn the label of this vertex, but the labels of vertices that we did not visit in such walks look random to us. Hence, for $t(N)=\omega (\log \log |V_\ell |)$, both the random variable $W_t(G_\ell )$ and $U(G_\ell )$ are unlikely to hit vertices that were visited by such $\mathrm{poly}(\ell )$-many explorations; that is, $W_t(G_\ell )$ and $U(G_\ell )$ hit explored vertices with negligible probability, and otherwise they look random.

A Stronger Notion of the Pseudo-mixing Time. Given that our focus is on Cayley graphs, one may wonder whether our upper bound on the pseudo-mixing time holds also when the observer is given access to the group operation (as well as to the corresponding inverse operation).⁴ A necessary condition for such a stronger notion of pseudo-mixing time is that, for every ($\mathrm{poly}(\ell )$-time computable)⁵ word $w=w[X]$ over the set of generators and a variable X, if w equals the identity when X is in the support of $W_t(G_\ell )$, then it is trivial (i.e., it equals the identity over the entire group). Hence, for starters, we suggest the following problem (where $r(\ell )$ replaces $t(\exp (\ell ))$, which was used above).

Open Problem 4

(vanishing over a large ball implies vanishing in the group): For some $r:{\mathbb {N}}\rightarrow {\mathbb {N}}$ such that $r(\ell )\in [\omega (\log \ell ),o(\ell )]$, is it possible to construct an $\exp (\ell )$-sized group having succinct representation that satisfies the following condition: For every word over the group’s generators and a variable X that vanishes over a ball of radius $r(\ell )$ centered at the group’s identity, it holds that the word vanishes over the entire group.

As hinted above (see also footnote 5), we are actually interested in words that are computable by arithmetic circuits of size $\mathrm{poly}(\ell )$.

2 The Main Result and Its Proof

Theorem 3 is proved by combining the following facts:

• 1. Arbitrarily relabelling the elements of any finite group yields a group that is isomorphic to the original group (Proposition 5).

• 2. Assuming the existence of one-way functions, the foregoing relabeling can be pseudorandom and succinct (in the sense of Property 1 of Theorem 3).

• 3. There are explicit Cayley graphs with $2^{(1+o(1))\cdot \ell /2}$ vertices such that the $o(\ell )$-neighborhood of each vertex is a tree.⁶

Indeed, the graphs asserted in Theorem 3 are obtained by starting with a Cayley graph as in Fact 3, and relabeling its vertices as suggested by Facts 1–2. Hence, the pivot of our proof is performing such relabeling, and so we first prove Fact 1.

Proposition 5

(relabeling a group): Let $(S,*)$ be a group such that $S\subset {\{0,1\}}^\ell$ and $0^\ell$ is the identity element, and let $\pi$ be a permutation over ${\{0,1\}}^\ell$ such that $\pi (0^\pi )=0^\pi$. Then, the set $S_\pi =\{\pi (e):e\in S\}$ combined with the operation ${\diamond }_\pi :S_\pi \times S_\pi \rightarrow S_\pi$ such that ${\diamond }_\pi (\alpha ,\beta )=\pi (\pi ^{-1}(\alpha )*\pi ^{-1}(\beta ))$ forms a group that is isomorphic to $(S,*)$.

Proof:

One can readily verify that the group axioms hold.

• For every $\alpha ,\beta ,\gamma \in S_\pi$ it holds that

  $$\begin{aligned} {\diamond }_\pi ({\diamond }_\pi (\alpha ,\beta ),\gamma )= & {} \pi (\pi ^{-1}({\diamond }_\pi (\alpha ,\beta ))*\pi ^{-1}(\gamma )) \\= & {} \pi (\pi ^{-1}(\pi (\pi ^{-1}(\alpha )*\pi ^{-1}(\beta ))) *\pi ^{-1}(\gamma )) \\= & {} \pi ((\pi ^{-1}(\alpha )*\pi ^{-1}(\beta ))*\pi ^{-1}(\gamma )) \\= & {} \pi (\pi ^{-1}(\alpha )*(\pi ^{-1}(\beta )*\pi ^{-1}(\gamma ))) \\= & {} {\diamond }_\pi (\alpha ,{\diamond }_\pi (\beta ,\gamma )) \end{aligned}$$

  where the last equality is established analogously to the first three equalities.

• For every $\alpha \in S_\pi$ it holds that ${\diamond }_\pi (\alpha ,0^\ell )=\pi (\pi ^{-1}(\alpha )*0^\ell )=\alpha$ and ${\diamond }_\pi (0^\ell ,\alpha )=\pi (0^\ell *\pi ^{-1}(\alpha ))=\alpha$. Indeed, $0^n$ is the identity element of the new group.

• Denoting by $\mathtt{inv}(a)$ the inverse of $a\in S$ in the original group, we can verify that $\pi (\mathtt{inv}(\pi ^{-1}(\alpha )))$ is the inverse of $\alpha \in S_\pi$ in the new group. Specifically,

  $$\begin{aligned} {\diamond }_\pi (\alpha ,\pi (\mathtt{inv}(\pi ^{-1}(\alpha ))))= & {} \pi (\pi ^{-1}(\alpha )*\pi ^{-1}(\pi (\mathtt{inv}(\pi ^{-1}(\alpha ))))) \\= & {} \pi (\pi ^{-1}(\alpha )*\mathtt{inv}(\pi ^{-1}(\alpha ))) \\= & {} 0^\ell \end{aligned}$$

  and similarly ${\diamond }_\pi (\pi (\mathtt{inv}(\pi ^{-1}(\alpha ))),\alpha )=0^\ell$.

Lastly, note that $\pi$ is an isomoprphism of $(S,*)$ to $(S_\pi ,{\diamond }_\pi )$, since $\pi (a*b) = {\diamond }_\pi (\pi (a),\pi (b))$.    $\blacksquare$

Restating Theorem 3. For sake of clarity, we restated Theorem 3, while strengthening a few of its aspects. First, the succinct representation of an $\exp (\varTheta (\ell ))$-vertex graph $G_\ell$ is provided by an $\ell$-bit string (called a seed) coupled with a uniform (polynomial-time) algorithm. Second, we will consider a distribution $\mathcal{D}_\ell$ over such graphs rather than a single graph per each value of $\ell$; actually, the distribution $\mathcal{D}_\ell$ will correspond to a uniformly selected $\ell$-bit long seed. Lastly, the difficulty-of-sampling condition is stated with respect to oracle machines that have access to the incidence function of the graph, and it discards vertices obtained as answers to incidence queries. As before, we use $\mathtt{negl}$ to denote a generic negligible function; that is, a function that tends to zero faster than the reciprocal than any positive polynomial.

Theorem 6

(main result, restated): Assuming the existence of one-way functions, there exists a distribution ensemble of bounded-degree Caley Graphs, denoted $\{\mathcal{D}_\ell \}_{\ell \in {\mathbb {N}}}$, such that the following properties hold:

• 1. Succinct representation: For some $d\in {\mathbb {N}}$ and every sufficiently large $\ell \in {\mathbb {N}}$, each graph in the support of $\mathcal{D}_\ell$ is a d-regular graph with $2^{(0.5+o(1))\cdot \ell }$ vertices. Furthermore, the vertex set is a subset of ${\{0,1\}}^\ell$ and contains $0^\ell$. These graphs are strongly explicit in the sense that each of these graphs is represented by an $\ell$-bit long string, called its seed, and there exists a polynomial-time algorithm that on input a seed s, a vertex v in the graph represented by s, and an index $i\in [d]$, returns the $i^\mathrm{th}$ neighbor of v in the graph.

• 2. Pseudo-mixing time: For every $t:{\mathbb {N}}\rightarrow {\mathbb {N}}$ such that $t(N)=\omega (\log \log N)$, any probabilistic polynomial-time oracle machine M that is given oracle access to the incidence function of a graph $G=(V,E)$ selected according to $\mathcal{D}_\ell$ cannot distinguish the uniform distribution over G’s vertices from the distribution of the end-vertex in a t(|V|)-step random walk on G that starts in $0^\ell$. Furthermore, with probability $1-\mathtt{negl}(\ell )$ over the choice of G in $\mathcal{D}_\ell$, it holds that

  $$|\mathrm{Pr}[M^G(W_t(G))\!=\!1]-\mathrm{Pr}[M^G(U(G))\!=\!1]|=\mathtt{negl}(\ell ),$$

  where U(G) denotes the uniform distribution on G’s vertices, and $W_t(G)$ denotes the distribution of the end-vertex of a t(|V|)-step random walk on G that starts at $0^\ell$.

• 3. Difficulty of sampling “without walking on the graph”: Any probabilistic polynomial-time oracle machine M that is given oracle access to the incidence function of a graph G selected according to $\mathcal{D}_\ell$ produces, with probability $1-\mathtt{negl}(\ell )$, an output that is either not a vertex or is a vertex obtained as answers to one of its queries or $0^\ell$. Furthermore, with probability $1-\mathtt{negl}(\ell )$ over the choice of $G=(V,E)$ in $\mathcal{D}_n$, it holds that

  $$\mathrm{Pr}[M^G(1^\ell )\in V\setminus (0^\ell \cup A_M^G)]=\mathtt{negl}(\ell ),$$

  where $A_M^G$ is the set of answers provided to M’s queries during the execution of $M^G(1^\ell )$.

Moreover, these graphs are expanders.

Theorem 3 follows by fixing an arbitrary typical graph in each distribution $\mathcal{D}_\ell$. Recall that Property 2, which asserts the non-triviality of the notion of pseudo-mixing time (i.e., $t(|V|)=o(\log |V|)$), is the focus of this work, whereas Property 1 asserts that this fact may hold also for succinctly represented graphs. Property 3 asserts that we are in a case of interest in the sense that taking walks on G is the only feasible way to obtain vertices of G (other than $0^\ell$).

Proof:

Our starting point is a family of explicit d-regular Cayley Graphs $\{G_\ell =(V_\ell ,E_\ell )\}_{\ell \in {\mathbb {N}}}$ such that $0^\ell \in V_\ell \subset {\{0,1\}}^\ell$ and $|V_\ell |=2^{(0.5+o(1))\cdot \ell }$. Furthermore, we assume that $W_t(G_\ell )$ has min-entropy $\omega (\log \ell )$, where the min-entropy of a random variable X equals $\min _{x}\{\log _2(1/\mathrm{Pr}[X\!=\!x])\}$. This certainly holds if $G_\ell$ is an expander graph, which is the choice made to satisfy the “moreover clause”.

Next, we consider the distribution $\mathcal{D}_\ell$ obtained by selecting a permutation $\pi$ over ${\{0,1\}}^\ell$ that is pseudorandom subject to $\pi (0^\ell )=0^\ell$. It is instructive to view $\pi$ as selected as follows: First, we select a pseudorandom permutation $\phi$ of ${\{0,1\}}^\ell$, and then we let $\pi (x)=\phi (x)\,{\oplus }\,\phi (0^\ell )$, where ${\oplus }$ denotes the bit-by-bit exclusive-or of bit strings. Recall that pseudorandom permutations can be constructed based on any one-way function (cf. [4,5,6]). These permutations of ${\{0,1\}}^\ell$ are represented by $\ell$-bit long strings, and are coupled with efficient algorithms for evaluating the permutation and its inverse.

Applying Proposition 5 to the group $(V_\ell ,*)$ that underlies the Cayley graph $G_\ell$, using the foregoing permutation $\pi$, we obtain a group $(S_\pi ,{\diamond }_\pi )$ that is isomorphic to $(V_\ell ,*)$, and it follows that $\pi (G_\ell )=(S_\pi ,E_\pi )$, where $E_\pi =\{\{\pi (u),\pi (v)\}:\{u,v\}\in E_\ell \}$, is a Cayley Graph of the group $(S_\pi ,{\diamond }_\pi )$. Specifically, letting $g:V_\ell \times [d]\rightarrow V_\ell$ denote the incidence function of $G_\ell$, the incidence function of $\pi (G_\ell )$, denoted $g_\pi$, satisfies $g_\pi (\alpha ,i)={\diamond }_\pi (\alpha ,\pi ({\gamma }_i))$ (which equals $\pi (\pi ^{-1}(\alpha )*{\gamma }_i)$), where ${\gamma }_i$ is the $i^\mathrm{th}$ generator of the set underlying the definition of $G_\ell$. (Here and below, we include both the generator and its inverse in the set of generators, so to avoid inverse notations.) This establishes Property 1.

To prove Properties 2 and 3, we analyze an ideal construction in which $\pi :{\{0,1\}}^\ell \rightarrow {\{0,1\}}^\ell$ is a uniformly distributed permutation that satisfies $\pi (0^\ell )=0^\ell$; equivalently, $\phi$ is a totally random permutation. By the pseudorandomness of the permutations used in the actual construction, if Property 2 (resp., Property 3) holds for the ideal construction, then it holds also for the actual construction, since otherwise we obtain a $\mathrm{poly}(\ell )$-time oracle machine that distinguishes the truly random permutations from the pseudorandom ones. Hence, we focus on the analysis of the ideal construction.

Starting with Property 3, observe that, by making oracle calls to $G'=\pi (G_\ell )$, a machine that runs in $\mathrm{poly}(\ell )$-time may encounter $\mathrm{poly}(\ell )$ many vertices of $G'$ by taking walks (of various lengths) from the vertex $0^\ell$. As far as such a machine is concerned, the name of each other vertex is uniformly distributed among the remaining $2^\ell -\mathrm{poly}(\ell )$ strings of length $\ell$. Hence, if such a machine outputs a string that is neither $0^\ell$ nor any of the vertices encountered by it, then this string is a vertex of $G'$ with probability at most $\frac{|V_\ell |}{2^\ell }=\exp (-\varOmega (\ell ))=\mathtt{negl}(\ell )$.

Turning to Property 2, note that the relevant machine may encounter vertices of $G'=\pi (G_\ell )$ by taking walks (of various lengths) either from $0^\ell$ or from the test vertex (which is distributed either according to $W_t(G')$ or according to $U(G')$). Each newly encountered vertex looks as being uniformly distributed among the unencountered vertices, and so the difference between the two cases (regarding the tested vertex) amount to the difference between pattern of collisions that the machine sees, where all walks are oblivious of the names of the encountered vertices (since these are random). Collisions between walks that start at the same vertex do not matter, since these are determined by the corresponding sequence of steps obliviously of the start vertex.⁷ Hence, the only collisions that may contribute to distinguishing the two cases are collisions between a walk from the tested vertex and a walk from the vertex $0^\ell$ (equiv., a collision between the tested vertex and a walk from vertex $0^\ell$).⁸

The key observation is that both $W_t(G')$ and $U(G')$ have min-entropy $\omega (\log \ell )$; specifically, $\max _{v}\{\mathrm{Pr}[W_t(G')\!=\!v]\}=\exp (-\omega (\log \ell ))$ and $\max _{v}\{\mathrm{Pr}[U(G')\!=\!v]\}=\exp (-\varOmega (\ell ))$. Hence, such a collision (between the tested vertex and a walk from vertex $0^\ell$) occurs with probability at most $\exp (-\omega (\log \ell ))=\mathtt{negl}(\ell )$. It follows that a $\mathrm{poly}(\ell )$-query machine cannot distinguish between $W_t(G')$ or $U(G')$; that is, its “distinguishing gap” is at most $\mathrm{poly}(\ell )\cdot \mathtt{negl}(\ell )=\mathtt{negl}(\ell )$.

The foregoing analysis refers to what happens in expectation over the choice of $G'\sim \mathcal{D}_\ell$, whereas the two furthermore claims refer to what happens on typical graphs drawn from $\mathcal{D}_\ell$. In the case of Property 3, applying Markov inequality will do, since we actually upper-bounded (by $\frac{|V_\ell |}{2^\ell }+\mathtt{negl}(\ell )$) the probability that the machine outputs a vertex in $\pi (V_\ell )\setminus \{0^\ell \}$ that was not encountered in its queries. The case of Property 2 requires a slightly more refined argument, since the gap $\mathrm{Pr}[M^G(W_t(G))\!=\!1]-\mathrm{Pr}[M^G(U(G))\!=\!1]$, for each G, may be either positive or negative.⁹ Using the fact that (for any G in the support of $\mathcal{D}_\ell$)¹⁰ we can approximate both $\mathrm{Pr}[M^G(W_t(G))\!=\!1]$ and $\mathrm{Pr}[M^G(U(G))\!=\!1]\approx \mathrm{Pr}[M^G(W_{O(\ell )}(G))\!=\!1]$, we can translate a gap on a non-negligible measure of $\mathcal{D}_\ell$ to a gap in the expectation, which means that the main claim of Property 3 implies its furthermore claim.   $\blacksquare$

Digest: Why is Theorem 6 true? Essentially, a priori (and with the exception of $0^\ell$), the vertices of the (distribution of) graphs that we construct look like random $\ell$-bit strings. By taking walks from the vertex $0^\ell$, the observer may discover $\mathrm{poly}(\ell )$ vertices of the graph, but (in both cases) these vertices look random and are unlikely to include the tested vertex. The latter assertion relies on the fact that $\max _v\{\mathrm{Pr}[W_t(G)\!=\!v]\}$ is negligible, which requires $t(|V_\ell |)=\omega (\log \ell )$. (Recall that the support of $W_t(G)$ can be found in time $\exp (O(t(|V_\ell |)))$).

3 Additional Comments

We first note that our choice to use graphs with $2^{(0.5+o(1))\cdot \ell }$ vertices is quite immaterial. It is merely a natural intermediate point that balanced between having too many vertices and too little vertices. Likewise, we could have used seeds of length $\ell ^{\varOmega (1)}$ rather than length $\ell$.

3.1 The Pseudorandomness of Multiple Walks

Recall that each graph G in the support of $\mathcal{D}_\ell$ is an expander, and so the statistical difference between U(G) and $W_{O(\ell )}(G)$ is negligible (e.g., $\exp (-\ell )$). Hence, essentially, we can generate samples of both $W_{O(\ell )}(G))$ and $G_t(G)$ in $\mathrm{poly}(\ell )$-time, provided that $t(N)=\mathrm{poly}(\log N)$. It follows that, given oracle access to $G\sim \mathcal{D}_\ell$, a $\mathrm{poly}(\ell )$-time observer cannot distinguish between multiple samples of the t-step random walk (i.e., samples of $W_t(G)$) and multiples samples of the graph’s vertices (i.e., samples of U(G)).

The foregoing result is a special case of a general result that asserts that indistinguishability of a single sample (drawn from one of two distributions) implies indistinguishability of multiple samples (that are all drawn from one of the two distributions). This generic result presupposes that the (single sample) distinguisher can obtain additional samples of each of the two distributions, which holds in our case by the foregoing discussion. The general result can be proved using a “hybrid argument” (see, e.g., [3, Sec. 8.2.3.3]).

3.2 On the Necessity of One-Way Functions

A natural question is whether using one-way function is necessary towards establishing Theorem 6. We show that the answer is affirmative, essentially because the existence of efficiently sampleable distribution ensembles that are far apart but are computationally indistinguishable implies the existence of one-way functions [2]. Next, we present a more direct argument (tailored to the current application).

Theorem 7

(one-way functions are necessary for Theorem 6): The existence of a distribution ensemble of expander graphs that satisfies Conditions 1 and 2 of Theorem 6 implies the existence of one-way functions.

The hypothesis that the graphs in the distribution are expanders is used only in order to infer that computational indistinguishability holds also with respect to multiple samples of the tested distribution (as discussed in Sect. 3.1). This is required in order to assert that a sequence of samples of U(G) has higher entropy than the length of the succinct representation of $G\sim \mathcal{D}_\ell$ (i.e., an m-long sequence of samples of U(G) has entropy at least $m\cdot \ell /2$, whereas each graph in $\mathcal{D}_\ell$ is described using a seed of length $\ell$). Alternatively, if we assume that this succinct representation is shorter than the min-entropy of a single sample of U(G), then the hypothesis that G is an expander is not needed.

Proof:

Using the hypothesis, we present a “false entropy generator” (as defined in [5]), and use the fact that such a generator implies a pseudorandom generator (see [5]), which in turn implies a one-way function. Details follow.

Fixing a function $t:{\mathbb {N}}\rightarrow {\mathbb {N}}$ such $t(N)=o(\log N)$, let $t'(\ell )=t(2^{(0.5+o(1))\cdot \ell })=o(\ell )$. For $m=8$ and every $\ell$, we consider a function $F:{\{0,1\}}^\ell \times ([d]^{t'(\ell )})^m\rightarrow {\{0,1\}}^{m\cdot \ell }$ that takes as input a seed s for a graph in the support of $\mathcal{D}_\ell$ along with the descriptions of m random $t'(\ell )$-step walks, where each description is an $t'(\ell )$-long sequence over [d], and outputs a sequence of m corresponding end-vertices; that is, $F(s,w_1,...,w_{m})=(v_1,v_2,...,v_{m})$ if $v_i$ is the end-vertex of the $i^\mathrm{th}$ random walk, described by $w_i\in [d]^{t'(\ell )}$, on the graph represented by s.

By Condition 1 of Theorem 6, the function F is computable in polynomial-time. On the other hand, by Condition 2 (and the foregoing comment about the pseudorandomness of multiple walks), it follows that the output of the function is indistinguishable (in polynomial-time) from m uniformly and independently distributed vertices of the graph. The point is that the length of the input to F is $\ell '{\mathop {=}\limits ^\mathrm{def}}\ell +m\cdot O(t'(\ell ))=\ell +O(1)\cdot o(\ell )<2\ell$, whereas the output is computationally indistinguishable from an m-long sequence of samples of U(G), which has min-entropy at least $k{\mathop {=}\limits ^\mathrm{def}}m\cdot \ell /2 > 2\ell '$ (i.e., each possible outcome occurs with probability at most $2^{-k}$). Hence, $F:{\{0,1\}}^{\ell '}\rightarrow {\{0,1\}}^{m\cdot \ell }$ is a “false entropy generator” (as defined in [5]).

At this point, applying [5] yields the claimed result. For sake of self-containment we outline the rest of the proof, while assuming basic familiarity with the notions of pseudorandom generators and randomness extractors (see, e.g., [3, Sec. 8.2] and [3, Apdx. D.4], resp.). The direct proof capitalizes on the fact that the output of F has high min-entropy (rather than high entropy only). Specifically, we obtain a pseudorandom generator by using either a randomness extractor of seed length $d=o(\ell )$ or a strong randomness extractor of seed length $\mathrm{poly}(\ell )$ (see, e.g., [3, Def. D.8] for both versions).¹¹ Either way, we extract $0.75\cdot k$ bits (from an input of min-entropy k), while incurring an error of $\exp (-\varOmega (k))=\exp (-\varOmega (\ell ))$. Applying the extractor on the output of F, we obtain a pseudorandom generator, since the output of the extractor is computationally indistinguishable from a distribution that is $\exp (-\varOmega (\ell ))$-close to being uniform on ${\{0,1\}}^{0.75k}$, whereas its input is shorter than its output.

For example, suppose that $E:{\{0,1\}}^{d}\times {\{0,1\}}^{m\cdot \ell }\rightarrow {\{0,1\}}^{0.75k}$ is such an extractor, and consider $G(s',s'')=E(s'',F(s'))$, then $|G(s',s'')|=0.75\cdot |F(s')|\ge 1.5\cdot |s'|$, whereas $|s''|=o(|s'|)$. Alternatively, consider $G(s',s'')=(s'',h_{s''}(F(s'))$, where $h_{s''}:{\{0,1\}}^{O(|s''|)}\rightarrow {\{0,1\}}^{1.5\cdot |s''|}$ is a pairwise-independent hash function (see, e.g., [3, Apdx. D.2]), which constitutes a strong extractor.¹²   $\blacksquare$