The Action of a Few Permutations on r-tuples is Quickly Transitive

Joel Friedman ^{1}  Antoine Joux ^{2}  Yuval Roichman ^{3}
Jacques Stern ^{4}  Jean-Pierre Tillich ^{5}

January 23, 1998

1Dept. of Mathematics, Univ. of British Columbia, Vancouver V6T 1Z2, Canada, e-mail jf@math.ubc.ca

2CELAR, France, e-mail joux@ssig.celar.fr 3Dept. of Applied Mathematics, Massachussetts Instit. of Tech., Cambridge MA 02138,

USA, e-mail yuval@math.mit.edu, partially supported by Univ. of British Columbia 4Ecole Normale Supérieure, 45 rue d’ULM, 75005 Paris, France, e-mail stern@dmi.ens.fr 5GREYC, Université de Caen, France, e-mail tillich@info.unicaen.fr, part of this work was

done while the author was visiting the University of British Columbia, BC, Canada

Abstract

We prove that for every r and d ≥ 2 there is a C such that for most choices of d permutations π_{1}, π_{2}, …, π_{d} of S_{n}, the following holds: for any two r-tuples of distinct elements in {1, …, n}, there is a product of less than C log n of the π_{i}’s which map the first r-tuple to the second. Although we came across this problem while studying a rather unrelated cryptographic problem, it belongs to a general context of which random Cayley graph quotients of S_{n} are good expanders.

1 Introduction

Choose d ≥ 2 permutations π_{1}, …, π_{d} at random in the symmetric group S_{n}. Consider now two r-tuples (u_{1}, u_{2}, …, u_{r}) and (v_{1}, v_{2}, …, v_{r}) of distinct elements of {1, 2, …, n}. Is there always a short product of these π_{i}’s which maps the first r-tuple to the second one ? We prove in what follows that for almost all choices of these permutations we only need products of length at most C log n, C being a constant depending on d and r. When such a condition is met by d permutations π_{1}, π_{2}, …, π_{d}, we say that the action of these permutations is C-quickly r-transitive.

This issue has been raised by the study of the security of some low cost cryptographic devices constructed from permutation automata (see section 3). We will exhibit a probabilistic algorithm which reconstructs the secrete device, and which can be shown to run in polynomial time by using the aforementioned result. This shows that such schemes are highly insecure.

Actually the results obtained here are more general than that, and should be put in the broader context of whether or not Cayley graphs over S_{n} are good expanders for a fixed number of random generators, and/or have a small diameter and mixing time. This is quite an important open problem, for a survey see [B&al90, Lub1, Lub2]. A solution of this problem is of great theoretical importance, while a positive solution would be useful for instance for generating random permutations quickly.

Here we take a first step towards a solution of the above open problem. We show that for bounded r the random Schreier graphs S_{n}/S_{n−r} (i.e. the quotients S_{n}/S_{n−r} of Cayley graphs over S_{n}) are good expanders, have a small diameter and mixing time.

More precisely we study the following random model: we choose independently d permutations of the numbers from 1 to n, π_{1}, π_{2}, ⋯, π_{d}, each permutation equally likely. We construct a directed graph, G = (V, E) with vertex set the set of r-tuples of distinct elements of {1, …, n} and there is a directed edge from (u_{1}, u_{2}, ⋯, u_{r}) to (v_{1}, v_{2}, ⋯, v_{r}) iff (v_{1}, v_{2}, ⋯, v_{r}) = (π_{i}(u_{1}), π_{i}(u_{2}), ⋯, π_{i}(u_{r})) for one of those π_{i}’s. We denote this probability space of random directed graphs G_{n,d,r}. Such graphs are dregular (and may have multiple edges or self-loops). We will consider the associated space of undirected graphs G_{n,d,r}^{∗} too. This space is simply obtained from the first one by changing each directed graph into an undirected one, just by replacing each directed edge of the former graph by an undirected edge. The latter space is therefore formed by undirected 2d-regular graphs.

It should be noted that r = 1 corresponds to the common probabilistic model of 2d-regular graphs, G_{n,2d} (as studied in [BS87, Fri91] for example), and that r = n is just the common probabilistic model of random 2d-regular Cayley graphs over S_{n}.

We will show that for every fixed r and for all d ≥ 2 almost all graphs in G_{n,d,r}^{∗} have a small second eigenvalue when the number of vertices becomes large, and that this implies that almost all graphs of G_{n,d,r}^{∗} and of G_{n,d,r} are good expanders, and also have a small diameter and mixing time.

The counting methods used by Bollobas for example to prove this kind of results for random regular graphs (see [Bol85, Bol88, BV82]) seem to fail in our case. In fact we prove our results by generalizing Broder-Shamir [BS87] and Friedman [Fri91] spectral approach.

Moreover we are interested here in obtaining results about the expansion properties of directed graphs too.

Besides being a step towards the study of random Cayley graphs over S_{n}:

• Those results cover the case of graphs of very small degree, which was not really settled by previous works of A. Broder, J. Friedman, and E. Shamir (especially the case d = 2 which is worth studying!). For instance our results show that as soon as d ≥ 2, random 2d-regular graphs have almost always a small second largest eigenvalue, and are therefore good certifiable expanders.

• We address here the issue of the expansion properties of directed graphs too. We provide here tools to achieve such results, provided that the directed graphs we are interested in have the same indegree and outdegree for each vertex. Although most of the theory on expanders has been developed for undirected graphs— we wish to lay emphasis on the fact that for some applications, expansion properties of directed graphs have to be estimated, this is the case for example in [TZ93, Zem94]— and in this article (see section 3).

Finally we mention that G_{n,d,r}^{∗} arises naturally from G_{n,d}^{∗} = G_{n,d,1}^{∗}, as does G_{n,d,r} from G_{n,d} = G_{n,d,1}, in the following way. Given maps of graphs, G → B and H → B, there is a fiber product (see [Fri93]) G ×_{B} H with a natural map to B. We can similarly form G^{r} = G ×_{B} ⋯ ×_{B} G. If G → B is a covering map, then G^{r} naturally breaks into certain components, such as the diagonal component and the component G^{∧r} whose vertices are those r-tuples of G vertices which are all distinct. In our case a G ∈ G_{n,d}^{∗} comes with a natural map to B = W_{d}, the bouquet of d self-loops (the map given via the d permutations); G^{∧r} would just be a random element in G_{n,d,r}^{∗}. Similarly a random G ∈ G_{n,d} gives rise to G^{∧r}, which is the same as a random element of G_{n,d,r}.

2 The main theorem

2.1 The main theorem and its consequences

Before describing our main theorem, let us introduce some notations. Let us recall that the adjacency matrix A = (a_{ij}) of a graph with n vertices is the n × n matrix indexed by the vertices of the graph, such that entry a_{ij} is the number of edges between i and j. In our case the adjacency matrix A = (a_{IJ}) of the graph G^{∗} of G_{n,d,r}^{∗} obtained by choosing the permutations π_{1}, π_{2}, ⋯, π_{d}, is defined by:

a_{IJ} = #{l | π_{l}(I) = J} + #{l | π_{l}(J) = I};

here we understand that I and J are r-tuples of distinct numbers, and each π_{i} operates on r-tuples in the obvious way. Let us note that each self-loop counts twice for the corresponding (diagonal) entry of the adjacency matrix. G^{∗} is a 2d-regular graph, therefore its adjacency matrix has real eigenvalues 2d = λ_{1} ≥ λ_{2} ≥ … ≥ λ_{N} with N = n(n − 1) ⋯ (n − r + 1); let ρ = max_{i≥2} |λ_{i}| = max(λ_{2}, −λ_{N}). Our main result asserts that ρ is almost always well separated from 2d.

Theorem 2.1 For fixed d, r we have:

E \{ρ^{k}\} ≤ [2d (\frac{\sqrt{2d − 1}}{d})^{1/(r+1)} (1 + O(log log n/ log n))]^{k} if k ≤ 2⌊(r + 1) log_{\frac{d^{2}}{2d−1}} n⌋

Prob \{ρ ≤ (1 + ϵ)2d (\frac{\sqrt{2d − 1}}{d})^{1/(r+1)}\} = 1 − o_{ϵ}(1) for every ϵ > 0

As corollaries we obtain that almost all graphs of G_{n,d,r}^{∗} are good expanders, and the same property holds for almost all graphs of G_{n,d,r}. The result for directed graphs follows from an argument relating the (edge-)expansion properties of a directed graphs to the (edge-)expansion properties of its associated undirected graph, obtained by replacing each directed edge by an undirected edge, and then relating the (edge-)expansion properties of the undirected graph to its second largest eigenvalue in absolute value.

More precisely:

Theorem 2.2 For every fixed d ≥ 2,r ≥ 1 and real ϵ, the probability that the graph

G_{n,d,r} is a c-expander tends to 1, as n tends to infinity, for c = \frac{1−ϵ}{2} (1 − (\frac{\sqrt{2d−1}}{d})^{\frac{1}{1+r}} )

A c-expander is defined as follows:

Definition 2.3 A directed graph G(V, E) with n vertices is a c-expander if, for any subset X of vertices with size ≤ n/2 the following inequalities hold

|N^{+}(X)| ≥ c|X| and |N^{−}(X)| ≥ c|X|

where N^{+}(X) (respectively N^{−}(X)) denotes the set of vertices not in X which are endpoints (respectively initial points) of an edge with initial point (respectively endpoint) in X.

Note that theorem 2.2 is far from being optimal, especially for r = 1, where the standard counting argument as used for example in [Bol88, Fri91] for undirected graphs gives us sharper estimates on the expansion constant. It must be noted here that this argument applies to the case d = 2 to the directed graph model with r = 1, and shows that c > 0.16, whereas the bound of the theorem 2.2 gives only c > 0.034 (see [JST93]). Unfortunately, this counting argument seems to fail for r > 1. Nevertheless, for most practical applications, this theorem is actually sufficient (see for example section 3).

Remark 2.4 It should be pointed out that by using Theorem 2.1 and classical results on Markov chains (see section 2 of [Vaz91]) imply that for every fixed d ≥ 2 and r ≥ 1, random walks on graphs of G_{n,d,r}^{∗} are rapidly mixing for almost all choices of such graphs, and that the mixing time of such random walks is not more than O(log n) almost surely. The same result holds for the directed graph model. This is a consequence of a result obtained by Mihail in [Mih89] (this result is recalled in Theorem 1 in [Vaz91] too) and of Theorem 2.2.

2.2 Proof of the main theorem

In this section we prove theorem 2.1. Throughout this section we view r as fixed. We also use the following notation.

Notation: Let N = n(n − 1) ⋯ (n − r + 1) be the number of vertices of the graphs G_{n,d,r}^{∗} or G_{n,d,r} we consider here. We note Π the alphabet {π_{1}, π_{1}^{−1}, π_{2}, π_{2}^{−1}, ⋯, π_{d}, π_{d}^{−1}}, where the π_{i}’s are permutations in S_{n}.

We begin by describing the general approach, which follows essentially the approach initiated by Broder and Shamir in [BS87].

The idea of the proof is to get a rather tight upper bound on E {ρ^{2k}} for rather large values of k. This is obtained by upper bounding this quantity by the expectation of the number of closed walks of length 2k minus (2d)^{2k}, when we choose a random graph from G_{n,d,r}^{∗}.

This is justified by what follows: if we call A = (a_{ij}) the adjacency matrix of a random graph of G_{n,d,r}^{∗}, then an entry b_{ij} of A^{2k} represents the number of walks on the graph of length 2k from i to j. Therefore

Number of closed walks of length 2k = Tr(A^{2k}) = ∑_{i=1}^{N} λ_{i}^{2k} ≥ (2d)^{2k} + ρ^{2k}

Let us note that the expectation E {i →^{2k} i} of the number of walks starting from a vertex i and ending at the same vertex, can be seen as the probability of the following event. We first choose a random word w = w_{1}w_{2} ⋯ w_{2k} in Π^{2k} (all the (2d)^{2k} possible words are chosen with the same probability \frac{1}{(2d)^{2k}}), and then we assign the

letters π_{i} a permutation of S_{n} chosen uniformly at random. We have E {i →^{2k} i} = (2d)^{2k}Prob {w_{1}w_{2} ⋯ w_{2k}(i) = i}.

So for each word w of length 2k over the alphabet Π, and for each vertex v of the graph G_{n,d,r}^{∗}, let P (w, v) denote the probability that when π_{1}, …, π_{d} are assigned permutations at random, the walk determined by w starting in v ends in v. Clearly P (w, v) = P (w) is independent of v. Hence we have

E {ρ^{2k}} ≤ (∑_{i}^{N} E {i →^{2k} i}) − (2d)^{2k}
≤ (  ∑_{w∈Π^{2k},1≤i≤N} P (w, i)) − (2d)^{2k}

≤ N( ∑_{w∈Π^{2k}} P (w)) − (2d)^{2k}
≤ N ∑_{w∈Π^{2k}}(P (w) − 1/N)  (1)

Our task is reduced now to estimate the quantity P (w) − \frac{1}{N}. First we will classify the words w which give us the same probability to close the walk.

We say that a word, w ∈ Π^{∗} is irreducible if w contains no consecutive occurrence of π and π^{−1} for any π ∈ Π. For each word, w ∈ Π^{2k}, we obtain a unique irreducible word, w′, by cancelling all consecutive occurrences of π and π^{−1} in w; we say that w reduces to w′. In this case we clearly have P (w) = P (w′). So to estimate P (w) it suffices to do so when w is irreducible.

Similarly, if w = w_{1} … w_{2k} with w_{i} ∈ Π, then if w_{1} = w_{2k}^{−1} we have that P (w) = P (w′) with w′ = w_{2} … w_{2k−1}. So we say that w = w_{1} … w_{2k} is strongly irreducible if w is irreducible and w_{1} ≠ w_{2k}^{−1}. Again, repeatedly cancelling first and last letters of w if they are inverses (and of consecutive π and π^{−1} occurrences) gives us a unique strongly irreducible word, w′, for which P (w) = P (w′). We say that w strongly reduces to w′, and it suffices to estimate P (w) when w is strongly irreducible.

We say that w ∈ Π^{∗} is periodic if it is of the form u^{m} for some u ∈ Π^{∗} and m ≥ 2. Our main lemma used to estimate P (w) is the following:

Lemma 2.5 Let w be a strongly irreducible word of length 2s with s > 1 such that w is not periodic. Then

P (w) = \frac{1}{n^{r}} + O (\frac{s^{2r+2}}{n^{r+1}} ) .

This lemma will be proved in appendix A. We finish the proof of the theorem assuming this lemma.

Let k be fixed. Let R be the set of words in Π^{2k} which strongly reduce to a word which is empty or periodic, and let

p_{2k} = |R|/|Π^{2k}| = |R|/(2d)^{2k}

be the probability that a random word in Π^{2k} belongs to R. Clearly we have

∑_{w∈Π^{2k}}(P (w) − 1/N)/(2d)^{2k} ≤ p_{2k} max_{w∈R}(P (w) − 1/N) + (1 − p_{2k}) max_{w∉R}(P (w) − 1/N)

≤ p_{2k} + max_{w∉R}(P (w) − 1/N).  (2)

In lemma 2.5 we estimated the right-hand-side of the above expression; the left-hand-side can be estimated by the following lemma.

Lemma 2.6 We have

p_{2k} ≤ (k + 1) (\frac{2d − 1}{d^{2}})^{k}

The proof of this statement is in appendix B.

Applying lemmas 2.5 and 2.6 to equation 2 we get

∑_{w∈Π^{2k}}(P (w) − 1/N)/(2d)^{2k} ≤ (k + 1) (\frac{2d − 1}{d^{2}})^{k} + O(k^{2r+2}/n^{r+1}).

Combining this with equation 1, and using N ≤ n^{r}, yields

E \{ρ^{2k}\} ≤ (O(k^{2r+2}/n) + n^{r}(k + 1) (\frac{2d − 1}{d^{2}})^{k})(2d)^{2k}.

Taking k to be the greatest integer K less than (r + 1) log_{\frac{d^{2}}{2d−1}} n yields:

(E \{ρ^{2K}\})^{1/(2K)} ≤ 2d 2^{1/(2K)} max ([O(K^{2r+2}/n)]^{1/(2K)} , [n^{r}(K + 1) (\frac{2d − 1}{d^{2}})^{K} ]^{1/(2K)})

≤ 2d (\frac{\sqrt{2d − 1}}{d})^{1/(r+1)} (1 + O(log log n/ log n)).

Finally, Hölder’s inequality implies that for any k ≤ 2K

E \{ρ\} ≤ (E \{ρ^{k}\})^{1/k} ≤ (E \{ρ^{2K}\})^{1/(2K)} ≤ 2d (\frac{\sqrt{2d − 1}}{d})^{1/(r+1)} (1+O(log log n/ log n))

(3)

which completes the proof of the first statement of the main theorem. The second claim is just a consequence of Markov’s inequality:

Prob \{ρ > α\} ≤ \frac{E \{ρ^{2l}\}}{α^{2l}},

by putting l = K and α = (1 + ϵ)2d (\frac{\sqrt{2d−1}}{d})^{1/(r+1)}, and using inequality 3.

□

2.3 The link between expansion properties of G_{n,d,r} and G_{n,d,r}^{∗}

To obtain this link, we will not compare directly the expansion constant of a directed graph G and its associated undirected graph G^{∗} (which is the graph obtained from the directed one by replacing each directed edge by an undirected edge), but we will compar their isoperimetric number first. This number is defined as follows:

Definition 2.7 The isoperimetric number i of a directed graph G(V, E) with n vertices is the largest number, i, such that for any subset X of vertices with size ≤ n/2 the following inequalities hold

|∂^{+}(X)| ≥ i|X|

|∂^{−}(X)| ≥ i|X|

where ∂^{+}(X) (respectively ∂^{−}(X)) denotes the set of edges with initial point (respectively endpoint) in X and endpoint (respectively initial point) in V \ X. The isoperimetric number i^{∗} of an undirected graph G^{∗}(V, E) with n vertices is the largest number, i^{∗}, such that for any subset X of vertices with size ≤ n/2 one has

|∂(X)| ≥ i^{∗}|X|

where ∂(X) denotes the set of edges between X and V \ X.

For a regular directed graph G we have:

Lemma 2.8 Let G be a regular directed graph, and G^{∗} its associated undirected graph. Let i and i^{∗} be the isoperimetric numbers of G and G^{∗} respectively. Then

i = \frac{i^{∗}}{2}

Proof For a directed regular graph, it is readily seen that for any subset, X, of vertices of the graph |∂^{+}(X)| = |∂^{−}(X)|. With the associated undirected graph, we have |∂(X)| = |∂^{+}(X)| + |∂^{−}(X)|. Therefore |∂(X)| = 2|∂^{+}(X)| = 2|∂^{−}(X)| and these equalities imply the lemma. □

Now we can bring in the connection between the isoperimetric number i^{∗} of an undirected regular graph G^{∗}(V, E) and the second smallest eigenvalue of the Laplacian of the graph λ(G^{∗}) (recall here that the Laplacian is the matrix diag_{v∈V} (deg(v)) − A, where A is the adjacency matrix of the graph G^{∗}(V, E))

i^{∗} ≥ \frac{λ(G^{∗})}{2}

This inequality can be found in [Moh89] (see theorem 4.1), and is essentially due to N. Alon and V.D. Milman (see [AM85]).

Now, it just remains to give a connection between this parameter and the isoperimetric number i. Since for every subset of vertices X of a directed regular graph G(V, E) of degree d, one has

|N^{+}(X)| ≥ \frac{1}{d}|∂^{+}(X)| and |N^{−}(X)| ≥ \frac{1}{d}|∂^{−}(X)|,

one deduces that such a graph is a \frac{i}{d}-expander.

From these considerations we can deduce the lemma:

Lemma 2.9 Let G be a regular directed graph of degree d, G^{∗} its associated undirected graph. Let λ be the second largest eigenvalue in absolute value of the adjacency matrix of G^{∗}. Then G is a c-expander, where c = \frac{1}{2} − \frac{λ}{4d}.

Proof It is readily seen that G^{∗} is a 2d-regular graph. Therefore the second smallest eigenvalue of the Laplacian of this graph is greater (or equal) than 2d−λ. The preceding discussion gives that the isoperimetric number i of G satisfies i = \frac{i^{∗}}{2} ≥ \frac{2d−λ}{4} (where i^{∗} is the isoperimetric number of G^{∗}). Consequently G is at least a (\frac{1}{2} − \frac{λ}{4d})-expander. □

The corollary 2.2 appears therefore as a consequence of lemma 2.9 and theorem 2.1.

3 An application to cryptography

With the development of memory card technology, and in particular the developpement of pre-paid cards, that give access to some service, the protection of the service issuer against fraud is becoming a crucial issue. However, for low-cost applications, the service provider might not afford to replace his memory cards by smart cards containing classical cryptographic protocols for identification of genuine cards. Still, it might be possible to devise (classical) identification protocols to improve the security offered by memory cards, while keeping their cost within reasonable bounds. In particular, permutation automata have been considered as offering a general design methodology for such purposes. We recall here some definitions and describe an identification protocol which, albeit never published, has been circulating in the smart-card community.

Definition 3.1 An automaton is a tuple (Q, B, δ, q_{0}) where:

• Q is a finite nonempty set of states,

• B is a finite nonempty set of input symbols or basic actions,

• δ is the next-state function which maps Q × B into Q,

• q_{0} ∈ Q is the initial state.

Definition 3.2 A permutation automaton is such that, for every action b, the function δ(., b) is a permutation of Q.

We let A = B^{∗} be the set of finite sequences of basic actions, and we extend the domain of the function δ to A in the usual way.

We now consider the special case B = {0, 1}, Q = [1..n] and q_{0} = 1. Moreover, we fix a parameter L and we let B^{L} be the subset of all words of length L in A.

The basic idea of the identification protocol is to install a secret permutation automaton in each memory card. All these automata are generated from a master key, and the card reader can reconstruct it before starting the identification. During the identification itself, the card reader sends a random query w from B^{L} to the memory card, which computes the image of q_{0} by w, and outputs this result. The card reader checks this result, accepts the card and issues the service if it is correct, and rejects otherwise.

What is important in the above, is the fact that the length of the queries is fixed. In the designer’s mind, this was presumably enough to prevent a statistical analysis of the outputs. This was even expected to remain true if the user was allowed to make repeated experiments with the automaton. Thus our cryptographic problem can be interpreted as a problem of learning theory for automata, (see, for example, [Ang78, AS83, F&al93, Gol78, RS87, RS89]). However, for all the attacks based on learning theory that we are aware of, the number of experiments needed to construct an automata which simulates the identification grows with the length of the query. Thus, these attacks can be defeated by limiting the number of identifications that a single card can perform. Yet, we show that even in this context, the above identification algorithm is insecure by describing an algorithm that allows to reconstruct the given automaton after a few queries (the number of queries does not depend on their size). The algorithm is straightforward but the main achievement of the paper is an actual proof that, with high probability, the algorithm succeeds with only a polynomial number of queries, when the permutation automaton is chosen at random. This is by no means obvious, and relies on Theorem 2.2. We first describe the algorithm. k and l are parameters to be specified later.

Initialization step: Fix a set U = {u_{1}, ⋯, u_{t}} of elements of A, all of the same length k < L. And given any state q in Q, let E_{q} be the equivalence relation on U defined by

δ(q, u_{i}) = δ(q, u_{j}).

Sampling step: Pick at random (without repetitions) elements a_{i} of A of (small) length ≤ l (s.t. k + l < L); set q_{i} := δ(q_{0}, a_{i}). Repeat until the set of equivalence relations E_{q_{i}} has n distinct members. Renumber the chosen elements so that E_{q_{1}}, ⋯ E_{q_{n}} are distinct and discard the other values. Comment: Computing E_{q_{i}} can be done by comparing the answers given by the automaton to the concatenation a_{i}^{⌢}u_{j}^{⌢}w_{i} where w_{i} is a word independent of j such that a_{i}^{⌢}u_{j}^{⌢}w_{i} has length L and j ranges over {1, ⋯, t}.

Computing step: For i := 1 to n and for each b in B compute E_{δ(q_{i},b)}. Comment: this can be done by comparing the answers given by the automaton to the concatenation a_{i}^{⌢}b^{⌢}u_{j}^{⌢}w where w is any fixed word of appropriate length and j ranges over {1, ⋯, t}.

Identification step: Choose random words W_{i} of length L. Compute E_{δ(q_{0},W_{i})} using the table built in the computing step and identify this equivalence relation with the output of the automaton under W_{i}. Repeat until all output states have been identified.

The sampling step of this algorithm is the most crucial one, if it can construct n elements a_{i} such that all E_{q_{i}} are distinct then the whole algorithm will succeed, otherwise it won’t. In order to prove this fact, let us remark that E_{q_{i}} ≠ E_{q_{j}} implies q_{i} ≠ q_{j}, thus if we construct n different values E_{q_{i}}, then the q_{i}’s range over all possible values in Q. Moreover, the equivalence classes E_{q} induced by U uniquely identify each state q, and the rest of the algorithm will succeed.

We can easily characterize the properties that are needed for the sampling step to succeed; they are the following:

1. Any state can be reached from q_{0} by applying a sequence of actions of length ≤ l.

2. There exists U that discriminates the given automaton, i.e. such that two different states q ≠ q′ have different equivalence relations E_{q} ≠ E_{q′}.

We now claim that the two above properties are the consequence of expansion properties of directed random graphs G_{1} and G_{3} of G_{n,2,1} and G_{n,2,3} respectively, both defined by the two (random) permutations π_{1} = δ(., 0) and π_{2} = δ(., 1). From corollary 2.2 we know that G_{1} is almost always an α_{1}-expander and G_{3} an α_{3}-expander (the corresponding values of α_{i} are given by the corollary). We need the following theorem, that states that expanders have small diameters:

Theorem 3.3 If G is an α-expander with v vertices, then the diameter of G is smaller than

2(1 + log_{1+α}(v)).

A proof of this statement can be found, for example, in [Zem94]. The idea of the proof is to look at two distinct vertices x and y, and to consider the ball of radius r centered at x (the vertices attained by a directed path of length ≤ r starting from x) and the “inverse” ball of radius r centered at y ( the vertices from which we can attain y by a directed path of length ≤ r). The crux is that the size is exponential in r (the exponent is at least 1+α) therefore the two balls must intersect for a radius which is logarithmic in v- and this gives a directed path traversing the point of intersection and going from x to y, of length at most twice the radius of the balls.

In particular, G_{1} has diameter smaller than 2(1+log_{1+α_{1}}(n)), thus the first property needed for the algorithm to succeed holds as soon as l > 2(1 + log_{1+α_{1}}(n)). Moreover, the number of elements of length smaller than l is polynomial in n if we choose l = 2(2+log_{1+α_{1}}(n)). Thus the sampling step will take polynomial time, once U is correctly chosen.

We now want to prove that the small diameter of G_{3} implies the second property. Let us remark that in order to prove this property it suffices for any pair of states (x, y) to produce a pair of words of the same length (smaller than k) w_{1} and w_{2} such that δ(x, w_{1}) = δ(x, w_{2}) and δ(y, w_{1}) ≠ δ(y, w_{2}). w_{1} and w_{2} can be completed to length k by appending any fixed word of appropriate length at their ends. We construct U as the union of all words w_{1}(x, y) and w_{2}(x, y).

Let d_{3} denote the diameter of G_{3}, and given a pair (x, y), choose (z, r, s) such that x, y, z, r, s are all distinct (we suppose that n ≥ 5). Since G_{3} has diameter d_{3}, there exists a word m_{1} of length ≤ d_{3} that goes from edge (x, y, z) to edge (y, z, r) and likewise a word m_{2} of length ≤ d_{3} that goes from edge (x, y, z) to edge (y, z, s). Let w_{1} = m_{1}^{⌢}m_{2} and w_{2} = m_{2}^{⌢}m_{1}, then clearly, w_{1} and w_{2} have the same length and:

δ(x, w_{1}) = z = δ(x, w_{2}) and δ(y, w_{1}) = s ≠ r = δ(y, w_{2}).

Thus the second property holds, if k ≥ 2d_{3} = 4(1 + log_{1+α_{3}}(n)). Moreover, it suffices to choose U = B^{k}, the set of all words of length k, whose size is polynomial in n if we choose k = 4(1 + log_{1+α_{3}}(n)).

Thus, we have constructed a polynomial time algorithm that reconstructs the secret automaton of a given card as soon as n is large enough for the expansion properties of G_{1} and G_{3} to hold. Moreover, we have implemented this algorithm for a small value n = 8 and even in this case it succeeds with a good probability, and with less than 30 queries.

A Proof of the Main Lemma

In this section we complete the proof of theorem 2.1 by proving the main lemma 2.5.

Here we review the Broder-Shamir-Friedman (of [BS87] and [Fri91]) approach to understanding P (w). So fix an irreducible word, w, of length 2s over Π, and consider the trajectory of (1, 2, …, r) under w. To estimate P (w) we will consider only the part of π_{1}, …, π_{d} determined by this trajectory.

Specifically, let w = w_{1} ⋯ w_{2s} with w_{i} ∈ Π, and consider the random variables

t_{1} = w_{1}(1),  t_{2} = w_{1}(2),  … t_{r} = w_{1}(r),
t_{r+1} = w_{1}w_{2}(1),  t_{r+2} = w_{1}w_{2}(2), … t_{2r} = w_{1}w_{2}(r),
… … . . . . . .
t_{(2r−1)s+1} = w_{1}w_{2} ⋯ w_{2s}(1),  … t_{2rs} = w_{1}w_{2} ⋯ w_{2s}(r),

in this order. For example, t_{1} takes on each of values {1, …, n} with probability 1/n; t_{2} takes on each of the values {1, …, n} − {t_{1}} with probability 1/(n − 1). As another example consider t_{r+1} with t_{1}, …, t_{r} being determined; then there are a number of possibilities: if w_{2} = w_{1}, then t_{r+1} may already be determined; if w_{2} ≠ w_{1} then since w_{2} ≠ w_{1}^{−1} we have that t_{r+1} takes on each of values {1, …, n} with probability 1/n. When t_{j}’s value is determined by the previous values of t_{1}, …, t_{j−1}, we say that t_{j} is a forced choice; otherwise we say that t_{j} is a free choice. If t_{j} is a free choice, then clearly t_{j} takes on one of n − m values each with probability 1/(n − m) for some m ≤ 2rs − 1. If a free choice happens to be a previously occurring vertex, i.e. 1, …, r or t_{1}, …, t_{j−1}, we say that t_{j} is a coincidence; this will occur with probability ≤ (r +j −1)/(n−j +1). Notice that at least r coincidences must occur if we have that (1, 2, …, r) returns to (1, 2, …, r) under w, i.e. that t_{(2s−1)r+j} = j for j = 1, …, r.

The first estimate we need is that the probability that ≥ r+1 coincidences occurring is small. Namely, this probability is less than

\binom{2rs}{r + 1}[(r + 2rs − 1)/(n − 2rs + 1)]^{r+1} = O(s^{2r+2}/n^{r+1}).

The second estimate we need involves the more complicated analysis of how r coincidences may occur; the analysis is greatly simplified by requiring w to be a strongly irreducible word not of the form u^{m} for any m ≥ 2. So consider the graph, G, determined by the choice of the t_{j}’s, i.e. consisting of all vertices 1, …, r and t_{1}, …, t_{2rs}, and all edges (j, t_{j}) for 1 ≤ j ≤ r and edges (t_{j}, t_{j+r}) for which t_{j+r} is a free choice, for 1 ≤ j ≤ (2s − 1)r. This graph may have self-loops and multiple edges. Our main claim is:

Lemma A.1 Let r coincidences occur and assume w is not of the form u^{m} for any m ≥ 2. If (1, …, r) returns to (1, …, r) under w, then the graph determined by the t_{j}’s must consist of r distinct loops of length 2s originating and terminating at each of 1, …, r. In particular, in this case we have that t_{1}, …, t_{2rs−r} are free choices without coincidence, and the last r t_{j}’s are free choices with coincidence.

Proof Consider the degrees of the vertices of the graph, G = (V, E), determined by the t_{j}’s. It is easy to see that the number of coincidences is precisely:

|E| − |V | + r = r + (1/2) ∑_{v∈V}(deg(v) − 2).

Furthermore, given that (1, …, r) returns to (1, …, r) under w, and that the first and last letter of w are not inverses of each other, then the degree of each of 1, …, r is at least two. Furthermore, since w is reduced it follows that the degree of each other vertex is at least two (for the time it is first entered and first left). Finally, each coincidence raises the degree of a vertex by one (not counting the r coincidences corresponding to the last letter of w at the vertices 1, …, r. It follows from the above formula that there are no other coincidences, and that the degree of each vertex in G is 2. So if G does not consist of r loops, one for each vertex 1, …, r, then there must exist a path from one of these vertices to another, say from 1 to 2. If this path is of length q, then since all paths are non-backtracking walks (since w is irreducible) in an everywhere degree two graph, w must equal w′ where w′ is cyclic shift of w by q. But then w = u^{m} with m = |w|/GCD(|w|, q), implying that m ≥ 2 since q < |w|, and therefore contradicting the assumption of the theorem.

□

At this point we can bound P (w) for w not periodic by the probability of the last r free choices being coincidences. After t_{2rs−r} have been determined, at most 2rs − r values of each permutation π_{i} have been determined. So the probability that the last r t_{j}’s are precisely 1, …, r (in that order) is no more than

(\frac{1}{n − 2rs + r} ) (\frac{1}{n − 2rs + r − 1}) ⋯ (\frac{1}{n − 2rs + 1}) ≤ \frac{1}{(n − 2rs)^{r}}

Adding this to the probability of having ≥ r + 1 coincidences yields the main lemma.

B Proof of lemma 2.6

First of all let us bound the probability that a random word in Π^{2k} reduces to the empty word. Let us note q_{k,s} the probability that a random word in Π^{k} reduces to an irreducible word of length s.

Sublemma B.1

q_{2k,0} ≤ (\frac{2d − 1}{d^{2}})^{k}

This lemma follows from the inequality given in section 2 of [Del89]. The same result can be obtained (asymptotically) by using lemma 3.1 of [McK81].

Let us now estimate the probability that a random word in Π^{2k} strongly reduces to a periodic word. As in [BS87] we will first consider the case of an irreducible word. More precisely:

Sublemma B.2 The probability that an irreducible word of length 2s chosen uniformly at random strongly reduces to a periodic word is less than

\frac{4s}{3(2d − 1)^{s}}

Proof We proceed as in [BS87]. The number of irreducible words which have the form w_{a}w_{b}^{i}w_{a}^{−1} (where the word w_{a} is of fixed length t, and w_{b} of fixed length l) is less than: 2d(2d − 1)^{t+l−1} (this is because the word w_{a}w_{b} must be irreducible). Therefore the probability we want to estimate is less than (for d > 1)

\frac{1}{2d(2d − 1)^{2s−1}} ∑_{0≤t≤s−1} ∑_{1≤l≤s−t} 2d(2d − 1)^{t+l−1}  (4)
≤ \frac{1}{2d(2d − 1)^{2s−1}} ∑_{0≤t≤s−1}(2d)^{2}(2d − 1)^{s−2}  (5)
= \frac{1}{2d(2d − 1)^{2s−1}} s(2d)^{2}(2d − 1)^{s−2}  (6)
≤ \frac{4s}{3(2d − 1)^{s}}  (7)

□

Let us consider the set of words w of length in Π^{2k} which reduce to a word w′ of fixed length 2s. If we choose such a word uniformly at random, the word w′ is uniformly distributed over the irreducible words of length 2s. From this remark and sublemmas B.1 and B.2 we deduce that:

p_{2k} ≤ (\frac{2d − 1}{d^{2}})^{k} + ∑_{s=1}^{k} q_{2k,2s} \frac{4s}{3(2d − 1)^{s}}  (8)

This leads us to consider the following generating function: f_{l}(z) = ∑_{s=0}^{l} q_{l,s}z^{s}.

Sublemma B.3 For 0 < z < 1

f_{l}(z) ≤ z (\frac{(2d − 1)z^{2} + 1}{2dz})^{l−1}

Proof It is readily seen that

q_{2l,2s} = \frac{1}{2d}q_{2l−1,2s+1} + \frac{2d − 1}{2d}q_{2l−1,2s−1}  (9)
q_{2l+1,2s+1} = \frac{1}{2d}q_{2l,2s+2} + \frac{2d − 1}{2d}q_{2l,2s}for s ≥ 1  (10)
q_{2l+1,1} = q_{2l,0} + \frac{1}{2d}q_{2l,2}  (11)
q_{2l+1,2s} = q_{2l,2s+1} = 0  (12)

From (12) it follows f_{2l}(z) = ∑_{s=0}^{l} q_{2l,2s}z^{2s} and f_{2l+1}(z) = ∑_{s=0}^{l} q_{2l+1,2s+1}z^{2s+1}

From (9) we obtain

f_{2l}(z) = \frac{(2d − 1)z^{2} + 1}{2dz}f_{2l−1}(z)  (13)

From (10) and (11) we obtain

f_{2l+1}(z) = \frac{(2d − 1)z^{2} + 1}{2dz}f_{2l}(z) − \frac{1 − z^{2}}{2dz} q_{2l,0}  (14)

From f_{1}(z) = z, relations (13) and (14) we deduce our sublemma. □

We are ready now to prove lemma 2.6. By using inequality (8) and sublemma B.3, we obtain for d > 1:

p_{2k} ≤ (\frac{2d − 1}{d^{2}})^{k} + ∑_{s=1}^{k} q_{2k,2s} \frac{4s}{3(2d − 1)^{s}}

≤ (\frac{2d − 1}{d^{2}})^{k} + \frac{4dk}{3(2d − 1)} (\frac{2d − 1}{d^{2}})^{k}

≤ (k + 1) (\frac{2d − 1}{d^{2}})^{k}

References

[Ang78] D. Angluin. “On the complexity of minimum inference of regular sets”, Information and Control 39 (1978), 302–320.

[AS83] D. Angluin and C.H. Smith. “Inductive inference, theory and methods”, Computing Surveys 15(3) (1983), 237–269.

[AM85] N. Alon and V.D. Milman. “λ_{1}, isoperimetric inequalities for graphs and superconcentrators”, J. Comb. Theory, Ser. B, 38, (1985), 73–88.

[Bab94] L. Babai. “Transparent proofs and limits to approximation”, preprint, (1994).

[B&al90] L. Babai, G. Hetyei, W.M. Kantor, A. Lubotzky, A. Seres. “On the diameter of finite groups”, 31st annual Symposium on Foundations of Computer Science, (1990), 857–865.

[Bol85] B. Bollobas. Random Graphs, Academic Press, London (1985).

[Bol88] B. Bollobas. “The isoperimetric number of random regular graphs”, Europ. J. Combinatorics 9 (1988), 241–244.

[BV82] B. Bollobas and W. F. de la Vega. “The diameter of random-regular graphs”, Combinatorica, 2, (1982), 125–134.

[BS87] A. Broder, E. Shamir. “On the second eigenvalue of random regular graphs”, 28th annual Symposium on Foundations of Computer Science, (1987), 286– 294.

[Del89] C. Delorme. “Counting closed paths in trees”, Technical Report n.516, University of Paris-Sud, Laboratoire de recherche en informatique Orsay, September 1989 (in French).

[F&al93] Y. Freund, M. Kearns, D. Ron, R. Rubinfeld, R.E. Schapire and L. Sellie. “Efficient learning of typical finite automata from random walks”, 25th ACM Symposium on the Theory of Computing (1993), 315–324.

[Fri91] J. Friedman. “On the second eigenvalue and random walks in random dregular graphs”, Combinatorica 11 (4) (1991), 331–362.

[Fri93] J. Friedman. “Some geometric aspects of graphs and their eigenfunctions.” Duke Mathematical Journal, 69 (1993), 487–525.

[Gol78] E.M. Gold. “Complexity of automaton identification from given data”, Information and Control 37 (1978), 302–320.

[JST93] A. Joux, J. Stern, J.P. Tillich. “Inferring finite automata by queries of fixed length”, Technical report of the Ecole Normale Supérieure.

[Lub1] A. Lubotzky. Discrete groups, expanding graphs and invariant measures, Progress in Mathematics, Vol. 125, Birkhäuser 1994.

[Lub2] A. Lubotzky. “Cayley graphs: eigenvalues, expanders and random walks”, to appear in Survey in Combinatorics, 1995.

[McK81] B. McKay. “The expected eigenvalue distribution of a large regular graph”, Linear Algebra and its Applications, 40, (1981), 203–216.

[Mih89] M. Mihail. “Conductance and convergence of Markov chains—a combinatorial treatment of expanders”, Proceedings of the 30th Annual Symposium on Foundations of Computer Science, 1989.

[Moh89] B. Mohar. “Isoperimetric number of graphs”, Journal of Comb. Theory (B) (1989), 274–291.

[RS87] R.L. Rivest and R.E. Schapire. “Diversity based inference of finite automata” Proceedings of the 28th Annual Symposium on the Foundations of Computer Science (1987), 78–87.

[RS89] R.L. Rivest and R.E. Schapire. “Inference of finite automata using homing sequences” Proceedings of the 21st ACM Symposium on the Theory of Computing (1989), 411–420.

[TZ93] J.P. Tillich, G. Zémor. “Group-theoretic hash functions”, Proceedings of the 1st French-Israeli Workshop in algebraic coding 1993, Springer Verlag, Lecture Notes 781, 90–110.

[Vaz91] U. Vazirani. “Rapidly mixing markov chains”, Proceedings of Symposia in Applied Mathematics, Volume 44, (1991), 99–121.

[Zem94] G. Zémor. “Hash Functions and Cayley graphs”, to appear in Design, Codes and Cryptography, of October 1994.