Expansion properties of directed random Schreier graphs of small degree and an application to cryptography

Antoine Joux

CELAR E-mail: joux@ssig.celar.fr

Jacques Stern

École Normale Supérieure E-mail: stern@dmi.ens.fr

Jean-Pierre Tillich

Telecom Paris E-mail: tillich@inf.enst.fr

May 30, 1994

Abstract

We show that random directed Schreier graphs S_{n}/S_{n−k} (where S_{n} is the set of permutations of n elements) are for fixed k, almost always good expanders. These graphs generalize the common probabilistic model of random regular graphs, for which such kind of results were already known. Nevertheless here we are particularly interested in estimating the expansion constant of directed random graphs, whereas all the known result were obtained for undirected graphs. Moreover our result covers the case of graphs with very low degree, which was not really considered by previous work of A. Broder, J. Friedman, and E. Shamir.

What motivated our study was a cryptographic issue : it was thought that some low-cost cryptographic devices could be constructed by using permutation automata. We prove here, that the scheme which was proposed is in general not secure, provided that some random directed Schreier graphs with low degree have good expansion properties. The aforementioned result imply that one could break such schemes by a polynomial time algorithm.

1 Introduction

The aim of this paper is to prove some expansion properties of directed random Schreier graphs where

• the vertex set V is the set of k-tuples (a_{1}, a_{2}, ⋯, a_{k}) where a_{1}, a_{2}, ⋯, a_{k} are all different, and taken in {1, 2, ⋯, n}.

• the edges are chosen at random, by first choosing d random permutations {π_{1}, π_{2}, ⋯, π_{d}} uniformly at random among S_{n}, that is all possible permutations of n elements, the set of edges E is defined by : {(v, π_{j}(v))|j = 1, ⋯, d v ∈ V }. For a vertex v = (a_{1}, a_{2}, ⋯, a_{k}), π_{j}(v) is defined by (π_{j}(a_{1}), π_{j}(a_{2}), ⋯, π_{j}(a_{k}))

We will show that almost surely such graphs are good expanders, and this for every fixed d > 1. Our result follows by using Broder and Shamir approach (see [6]). It should be added here that such an approach has already be applied to the undirected version of these graphs (that is with edges {(v, π_{j}(v)), (v, π_{j}^{−1}(v))|j = 1, ⋯, d v ∈ V }) by Yuval Roichman, for “large” values of d, in [14] . Nevertheless here we focus on expansion results for

• directed graphs,

• and small degree d (we are particularly interested in the case d = 2 which has never been treated before).

In the literature a lot of work has been devoted to the study of expansion properties of the undirected model with k = 1, which is actually a common probabilistic model for 2d-regular graphs. In [6, 8] for instance, and with this probabilistic model, 2d-regular (undirected) graphs were shown to be almost surely very good expanders (for sufficiently large degree d). Nevertheless for practical applications one is often interested in results for fixed (and small) degree d, and even sometimes for directed graphs, and/or k > 1. We will see for example in section 3 an example of application of our result (for the directed model and d = 2, k = 3) to the study of a cryptographic scheme which is currently being considered for memory cards.

2 The main theorem

2.1 The main result and the plan of the proof

We elaborate on the probabilistic model of d-regular directed graphs, constructed in the introduction for some fixed d, k. We will call G_{n,k,d} the d-regular random graph, obtained after choosing π_{1}, ⋯, π_{d}. Hence G_{n,k,d} has n(n − 1) ⋯ (n − k + 1) vertices, and every vertex has indegree and outdegree d. Let us notice that we allow here self-loops and multiple edges, and that a given d-regular graph might be obtained from more than one choice of permutations.

Before stating our main theorem, we need to define what is the expansion constant : Definition 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. c is called here an expansion constant of the graph.

Our main result can be expressed as follows

Theorem 1 For every fixed d ≥ 2,k ≥ 1 and real ϵ > 0, the probability that the graph G_{n,k,d} 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+k}} d^{ϵ})

Before giving a sketch of the proof, let us note that this result is far from being optimal, especially for k = 1, where the standard counting argument as used for example in [5, 8] 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, and shows that c > 0.16, whereas the bound of the theorem 1 gives only c > 0.034 (we will give details about that in the final paper). Unfortunately, this counting trick seems to fail for k > 1. Nevertheless, for most practical applications, this theorem is actually sufficient (see for example the section 3).

The proof of theorem 1 follows from the following results

1. First we prove a result on the second largest eigenvalue in absolute value, λ, of the adjacency matrix corresponding to the “undirected” version of G_{n,k,d}, that we call from now on G_{n,k,d}^{∗}, that is the undirected 2d-regular graph with the same set of vertices, and with set of edges {(v, π_{j}(v)), (v, π_{j}^{−1}(v))|j = 1, ⋯, d v ∈ V }. Let us note that this definition allows loops and multiple edges, and that G_{n,k,d}^{∗} is a 2d-regular multigraph. We will state in theorem 2 that almost surely λ is well-separated from 2d.

2. ¿From an argument which relates expansion properties of G_{n,k,d}^{∗} to expansion properties of G_{n,k,d}, we complete the proof of theorem 1.

2.2 The eigenvalue bound on G_{n,k,d}^{∗}

As explained in the introduction, we use Broder and Shamir approach to bound the eigenvalues of the adjacency matrix of G_{n,k,d}^{∗}. More precisely our aim in this section is to prove the result

Theorem 2 For every fixed d ≥ 2, k ≥ 1, and real δ > 0, the probability that the graph G_{n,k,d}^{∗} has its second largest eigenvalue in absolute value larger than 2dα is

O (\frac{1}{n^{e}} )

where β = (\frac{\sqrt{2d−1}}{d})^{\frac{1−δ}{1+k−δ}} and e = _{\frac{1+k−δ}{ln \frac{d}{\sqrt{2d−1}}}} ln \frac{α}{β}.

By choosing α = (\frac{\sqrt{2d−1}}{d})^{\frac{1}{1+k}} d^{ϵ}, and δ such that β < α (which implies e > 0), we get

Corollary 1 For every fixed d ≥ 2,k ≥ 1, and real δ > 0 the probability that the graph G_{n,k,d}^{∗}

has its second largest eigenvalue in absolute value larger than 2\sqrt{2d − 1}^{\frac{1}{1+k}} d^{\frac{k}{k+1} +ϵ} tends to 0 as n tends to infinity.

Let us first define P = \frac{1}{2d}A, where A is the adjacency matrix of G_{n,k,d}^{∗}, and let λ_{1} = 2d ≥ λ_{2} ≥ ⋯ ≥ λ_{n(n−1)···(n−k+1)} be the eigenvalues of A. Then λ = max(λ_{2}, |λ_{n(n−1)···(n−k+1)}|), and it is easy to check that:

tr(P^{2l}) = \frac{1}{(2d)^{2l}} ∑_{i=1}^{n(n−1)···(n−k+1)} λ_{i}^{2l}

The point is that all the eigenvalues of P are real (since P is symmetric), therefore

\frac{1}{(2d)^{2l}} λ^{2l} ≤ tr(P^{2l}) − 1  (1)

All what we have to do now, is to bound the trace of |P_{ij}^{(2l)}| = P^{2l}, and this is achieved by considering P as the transition probability matrix of the Markov chain corresponding to the usual random walk on the graph G_{n,k,d}^{∗}, that is when we are at a given vertex, we take one of 2d edges starting from this vertex with equal probability 1/2d. Hence we can see P_{ii}^{(2l)} as the probability that a particle starting at vertex i and moving according to P is again at vertex i after 2l steps.

This will be obtained by a probabilistic argument, by first bounding E(P_{ii}^{(2l)}), and since this quantity does not depend on i, we have

E(tr(P^{2l})) = n(n − 1) ⋯ (n − k + 1)E(P_{ii}^{(2l)})  (2)

From now on, we will estimate E(P_{ii}^{2l}) for a fixed i, say i = 1 = (1, 2, ⋯, k) . Please note that in what follows, k will be some constant integer≥ 1.

As explained in [6] (in section 4), E(P11^{(2l)}) can be viewed as the probability that a random walk of length 2l starting from vertex 1 returns to vertex 1, where the random walk is chosen as follows. First we choose uniformly at random a sequence S = σ_{1}σ_{2} ⋯ σ_{2l} where the σ_{i}’s are chosen independently and uniformly at random in the alphabet {π_{1}, π_{1}^{−1}, π_{2}, π_{2}^{−1}, ⋯, π_{d}, π_{d}^{−1}}. Second we assign to each π_{i} a permutation chosen uniformly at random among the n! permutations on n elements. The sequence S determines now the random walk of length 2l as the trajectory :

T = (t_{0} = 1 → t_{1} = σ_{1}(t_{0}) → t_{2} = σ_{2}(t_{1}) → ⋯ → t_{2l} = σ_{2l}(t_{2l−1}))

Therefore we need to estimate the probability that t_{2l} = 1. For this purpose we classify in three categories the walks of length 2l starting from 1 and returning to 1, according to the graph induced by the trajectory (the set of vertices is {t_{0}, t_{1}, ⋯, t_{2l}}, and the set of edges is given by T. For this purpose we need to define precisely what we mean by the associated graph : Definition To each trajectory T we associate the following graph (which will be actually a multigraph, with possible self-loops and multiple edges), defined recursively by :

- the vertices of the graph are t_{0}, t_{1}, ⋯, t_{2l} (we identify identical k-tuples).

- the construction of the graph starts by drawing an edge between t_{0} and t_{1}, after that we carry out the following recursion, starting from i = 1

we add an edge between t_{i} and t_{i+1}, unless there exists j < i, such that either

(.) σ_{j} = σ_{i} and t_{j} = t_{i}, t_{j+1} = t_{i+1} (..) σ_{j} = σ_{i}^{−1} and t_{j} = t_{i+1}, t_{j+1} = t_{i}

we add 1 to the value of i, and start the same procedure again, until i becomes equal to 2l.

¿From now on, we will distinguish between the trajectories for which :

Case 1 The graph has no loop.

Case 2 The graph has just one loop.

Case 3 The graph has more than one loop.

For the second case, we will need to classify the sequences themselves. For this purpose we will distinguish between sequences S which are (we view here a sequence S as an element of the free group generated by {π_{1}, π_{2}, ⋯, π_{d}}):

- irreducible, this means that we can not simplify the sequence by canceling consecutive terms of the sequence of the form π_{i}π_{i}^{−1}.

- strongly irreducible this means that the sequence S^{2} is irreducible too. This is equivalent to say that S can not be put in the form S_{a}S_{b}S_{a}^{−1} (where S_{a} is a non void subsequence of S)

- prime this means that the sequence S can not be put in the form S_{a}S_{b}^{t}S_{a}^{−1} (with t > 1, and S_{b} is not void).

First let us bound the probability that case 1 happens. It is readily seen that a trajectory starts from 1, and returns to 1 without making any loop, if and only if the defining sequence S is equal to the identity in the free group generated by {π_{1}, π_{2}, ⋯, π_{d}}.

lemma 1 The probability that a random sequence S of length 2l is equal to the identity in the free group generated by {π_{1}, π_{2}, ⋯, π_{d}} is

O(\frac{1}{\sqrt{l}} (\frac{2d − 1}{d^{2}})^{l})

proof This is a straightforward consequence of lemma 3.1 of [10]. □

Now let us turn to case 2. When the defining sequence S of the trajectory is irreducible and prime we can state that

lemma 2 Given any irreducible prime sequence of length s = O(log n), the probability that its trajectory is such that its associated graph has only one loop is

\frac{1}{n^{k}} + O(\frac{1}{n^{k+1−δ}})

This formula holds for every constant δ > 0.

(for the proof see the appendix).

For irreducible sequences which are not prime, we have the weaker result lemma 3 Given any irreducible prime sequence of length s = O(log n), the probability that its trajectory is such that its associated graph has only one loop is

O(\frac{1}{n^{k−δ}})

This formula holds for every constant δ > 0.

Intuitively, trajectories which return to 1 and which are produced by a rather long irreducible sequence of the form S_{a}S_{b}^{t}S_{a}^{−1} (where S_{b} is not void and t > 1) are not so common. This is expressed by :

lemma 4 Let S be ann irreducible sequence of length 2s > 0 (with s = O(log n)) chosen uniformly at random. The probability that S simultaneously satisfies the conditions

1. The graph associated to the trajectory of S has exactly one loop, and this trajectory starts at 1 and returns to 1.

2. The sequence S is not prime. is less than

\frac{3}{2}(2d − 1)^{−s}O(\frac{1}{n^{k−δ}})

This formula holds for every constant δ > 0.

Proof This is a rather straightforward consequence of lemma 6 of [6] which bounds the probability that a sequence S chosen uniformly at random has the form S_{a}S_{b}^{t}S_{a}^{−1}, along with our lemma 3. More details will be given in the full paper. □

What happens now if we do not choose an irreducible sequence S? The crux to settle entirely this case, even for d = 2, is to obtain a rather sharp estimation of p_{l,s}, that is the probability that a sequence S of length l chosen uniformly at random, reduces to an irreducible sequence of length s (by repeatedly canceling all consecutive occurrences of ππ^{−1} in the sequence) :

lemma 5 Let us define f_{l}(z) = ∑_{s=0}^{l} p_{l,s}z^{s}. Then for 0 < z < 1

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

(for a proof of this statement, see the appendix)

Now we are ready to bound the probability that case 2 occurs, with a trajectory with only one loop, and which was provided by a sequence S which was not prime

lemma 6 The probability p that a trajectory of length 2l = O(log n), is made up by just one loop, starts from 1 and returns to 1, and is induced by a sequence S which is not prime is

O ((\frac{2d − 1}{d^{2}})^{l} \frac{l}{n^{k−δ}} )

This inequality holds for every constant δ > 0.

Proof The trajectory originates from a sequence S which reduces to some irreducible sequence S′ of length 2s > 0. Therefore by using lemma 4 and we obtain that the probability p is less than

∑_{s} p_{2l,2s} \frac{3}{2}(2d − 1)^{−s}O(\frac{1}{n^{k−δ}})

By using lemma 5 we obtain

p = O ((\frac{2d − 1}{d^{2}})^{l} \frac{1}{n^{k−δ}} )

□ The probability of the last case remains to be bounded. This is obtained by

lemma 7 The probability that a trajectory of length s = O(log n) starting from 1 describes at least two distinct loops is

O (\frac{1}{n^{k+1−δ}} )

(and that for every δ > 0)

(the proof of this theorem uses mainly tools which are developed in the proof of lemma 3 in [6], along with some ideas which are used in the proof of lemma 2 and 3 in our article. More details will be given in the final paper)

Now by using the results of lemma 1, 2, 6, 7 we are ready to estimate the probability that a trajectory T of length 2l starting from 1, returns to 1 :

lemma 8 The probability E(P_{ii}^{(2l)}) that a trajectory T of length 2l = O(log n) which starts from 1 returns to 1 is less than :

\frac{1}{n^{k}} + O (\frac{1}{n^{k+1−δ}} + \frac{1}{n^{k−δ}} (\frac{2d − 1}{d^{2}})^{l} + (\frac{2d − 1}{d^{2}})^{l})

This inequality holds for every constant δ > 0.

Theorem 2 is just a corollary of this last lemma, since if we use equations (1) and (2), together with this lemma 8, by choosing l = ⌊(1 + k − δ)\frac{log n}{log \frac{d^{2}}{2d−1}} ⌋ we get

\frac{1}{(2d)^{2l}} E(λ^{2l}) ≤ E(tr(P^{2l})) − 1 ≤ O(β^{2l})

for β = (\frac{\sqrt{2d−1}}{d})^{\frac{1−δ}{1+k−δ}}. Therefore by using the classical moment inequality

Prob (λ > 2dα) ≤ \frac{E(λ^{2l})}{(2dα)^{2l}}
≤ O ((\frac{β}{α})^{2l})

It is straightforward to check that this last inequality implies theorem 2.

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

To obtain this link, we will not compar directly the expansion constant of a directed graph and its associated undirected graph (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. Let us recall that the isoperimetric number is Definition The isoperimetric number i of a directed graph G(V, E) with n vertices is the largest number 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 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 the following lemma can be obtained

lemma 9 Assume that G is 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)|. When we consider the associated undirected graph, we obtain |∂(X)| = |∂^{+}(X)| + |∂^{−}(X)|. Therefore |∂(X)| = 2|∂^{+}(X)| = 2|∂^{−}(X)| and these equalities imply the lemma. □

Now we can bring in the connection between 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 [11] (see theorem 4.1), and is essentially due to N. Alon and V.D. Milman (see [3]).

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 can deduce that such a graph is a \frac{i}{d}-expander.

¿From these considerations we can deduce the lemma : lemma 10 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 verifies i = \frac{i^{∗}}{2} ≥ \frac{2d−λ}{4} (i^{∗} is the isoperimetric number of G^{∗}). Consequently G is at least a (\frac{1}{2} − \frac{λ}{4d})- expander. □.

The theorem 1 appears therefore as a consequence of lemma 10 and corollary 1.

3 An application to cryptography

With the development of memory card technology, and in particular the developpement of prepaid 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 now recall some definitions and describe an identification protocol which, albeit never published, has been circulated in the smart-card community. Definition A 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} is a member of Q, the initial state.

Definition 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 bears some resemblance with the setting of learning automata, despite the fact that the fixed-length query model does not seem to have been considered in the vast literature on inferring automata (see for example [1, 2, 7, 9, 12, 13]).We show that the above identification protocol is insecure by describing an algorithm that allows to reconstruct the given automaton after a few queries. The algorithm is quite direct 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 the expansion properties of Schreier graphs. We first describe the algorithm.

initialization step Fix a set U = {u_{1}, ⋯, u_{r}} 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 a_{i}^{⌢}u_{j}^{⌢}w_{i} where w_{i} is a word independent of j such that the concatenation a_{i}^{⌢}u_{j}^{⌢}w_{i} has length L and j ranges over {1, ⋯, r}.

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 a_{i}^{⌢}b^{⌢}u_{j}^{⌢}w where w is any fixed word of appropriate length and j ranges over {1, ⋯, r}.

identification step Choose random words W_{i} of length N. 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 exist 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 two well chosen Schreier graphs, G_{1} and G_{3} that are defined as G_{N,1,2} and G_{N,3,2} using the two permutations π_{1} = δ(., 0) and π_{2} = δ(., 1). In the sequel, we suppose that G_{1} is an α_{1}-expander and G_{3} an α_{3}-expander. We need the following theorem, that states that expander graphs have small diameters:

Theorem 3 If G is an α-expander graph with n vertices then the diameter of G is smaller than

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

( a proof of this statement can be found for example in [16] , section 7.2)

In particular, G_{1} has diameter smaller than 2(1 + log_{1+α_{1}}(N)), thus the first property needed for the algorithm to succeed hold 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} denotes 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 exist 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 succeed with a good probability, and with less than 30 queries. Acknoledgments We wish to thank Joel Friedman for interesting and very helpful conversations.

APPENDIX

A Proof of lemmas 2 and 3

A.1 Proof of lemma 2

We assume first that S = σ_{1}σ_{2} ⋯ σ_{s} is strongly irreducible (that is S is not of the form S_{a}S_{b}S_{a}^{−1}, where S_{a} and S_{b} are non void subsequences). In that case, the trajectory T = (1, t_{1}, t_{2}, ⋯, t_{s−1}, t_{s} = 1) starting at 1 and associated to S is such that t_{1}, t_{2}, ⋯, t_{s} are all different. The probability we want to estimate, is the probability that σ_{s}(t_{s−1}) is equal to 1. Let us note t_{s−1} = (a_{1}, a_{2}, ⋯, a_{k}) (where the a_{i}’s are in {1, 2, ⋯, n}). Since the a_{i}’s may belong to another t_{i}, some values of σ_{s}(a_{i}) may be fixed. Let us note A_{j} the event that exactly j values σ_{s}(a_{i}) are fixed, and that for these values, we have σ_{s}(a_{i}) = i. Therefore

Prob (σ_{s}(t_{s−1}) = 1) = ∑_{j=0}^{k} Prob (σ_{s}(t_{s−1}) = 1|A_{j}) Prob(A_{j})

It is straightforward to check that all possible values of σ_{s}(t_{s−1}) are equiprobable, and since in case of event A_{j} there are at least (n − ks)^{k−j} possible values of σ_{s}(t_{s−1}) :

Prob (σ_{s}(t_{s−1}) = 1|A_{j}) ≤ \frac{1}{(n − ks)^{k−j}}  (3)

It remains to bound Prob(A_{j}). We will show in what follows that

sublemma A.1 for j ≥ 1

Prob (A_{j}) ≤ \frac{k^{3j+2}s^{2j+2}}{(n − ks)^{j+1}}

To obtain this result we will consider separately the coordinates a_{1}, a_{2}, ⋯, a_{k}. For that, let us define the following trajectories induced by S over {1, 2, ⋯, n}.

T_{1} = (t_{1,0} = 1 → t_{1,1} = σ_{1}(t_{1,0}) → t_{1,2} = σ_{2}(t_{1,1}) → ⋯ → t_{1,s} = σ_{s}(t_{1,s−1}))
T_{2} = (t_{2,0} = 2 → t_{2,1} = σ_{1}(t_{2,0}) → t_{2,2} = σ_{2}(t_{2,1}) → ⋯ → t_{2,s} = σ_{s}(t_{2,s−1}))
⋯
T_{k} = (t_{k,0} = k → t_{k,1} = σ_{1}(t_{k,0}) → t_{k,2} = σ_{2}(t_{k,1}) → ⋯ → t_{k,s} = σ_{s}(t_{k,s−1}))

Whithout loss of generality, we may assume that the a_{i}’s which have already fixed values by σ_{s}, are a_{1}, a_{2}, ⋯, a_{j}. These values are consequently 1, 2, ⋯, j. Let us call this event A′_{j}. It is clear that

Prob(A_{j}) = ( \begin{matrix}k \\ j \end{matrix} ) Prob(A′_{j})  (4)

As in [6], the major point of the proof is the notion of fixed and free choices. More precisely

Definition We say that σ_{l+1}(t_{i,l}) is a fixed choice if and only if there exist l′ < l, 1 ≤ i′ ≤ k, such that either

σ_{l+1} = σ_{l′+1} and t_{i′,l′} = t_{i,l}, t_{i′,l′+1} = t_{i,l+1}

or

σ_{l+1} = σ_{l′+1}^{−1} and t_{i′,l′} = t_{i,l+1}, t_{i′,l′+1} = t_{i,l}

We will also say in that case, that σ_{l+1}(t_{i,l}) is fixed by the trajectory T_{i′}, and that the edge e_{i,l+1} = (t_{i,l}, t_{i,l+1}) is fixed. Otherwise we say that the edge e_{i,l+1} is free We say that a trajectory T_{i} joins a trajectory T_{i′}, if and only if there exists 1 ≤ l′ < l ≤ s, such that t_{i,l} = t_{i′,l′}. T_{i} joins a trajectory T_{j} freely, if there exists 1 ≤ l′ < l ≤ s, such that t_{i,l} = t_{i′,l′}, and σ_{l}(t_{i,l−1}), is a free choice. In that case, we call the edge e_{i,l} a coincidence obtained at step l.

We will need later the straightforward remark

Fact 1 If e_{i,l} is free, and e_{i,l+1} is fixed, then e_{i,l} is a coincidence.

We claim that

sublemma A.2 In case of event A′_{j}, the set of trajectories T_{1}, T_{2}, ⋯, T_{k} contains at least j + 1 coincidences, obtained before the last step.

This sublemma follows from the facts

Fact 2 The first edge of each trajectory T_{i} is free (and this for every 1 ≤ i ≤ k).

This property implies that we can define for a trajectory the last edge which is free. When we walk along a trajectory T_{i}, we traverse successively e_{i,1}, e_{i,2}, ⋯, and the last free edge e_{i,l} that we encounter, will be noted e(T_{i}). Let us note also l(T_{i}) = l. For 1 ≤ i ≤ j, e(T_{i}) ≠ e_{i,s} (or what is the same l(T_{i}) < s). From this remark, and facts 1, 2 it is readily seen that

Fact 3 In case of event A′_{j}, e(T_{1}), e(T_{2}), ⋯, e(T_{j}), are coincidences.

We suppose now that the sublemma A.2 is false. From facts 1,2,3, it follows that all edges on a trajectory T_{i} (for 1 ≤ i ≤ j) are free, from edge e_{i,1} to e(T_{i}). All the edges of the trajectories T_{i}, with j + 1 ≤ i ≤ k, must be free. Moreover this implies

Fact 4 All the points t_{i,l}, where 1 ≤ i ≤ k and 0 ≤ l < l(T_{i}), are different.

Nevertheless, since the edges e_{i,s} are fixed for 1 ≤ i ≤ j, this implies that these edges must have been traversed before. We say here that a given edge e_{i,l} = (t_{i,l−1}, t_{i,l})) was traversed before by the trajectory T_{i′} at step l′ < l, if and only if,

σ_{l} = σ_{l′} and t_{i′,l′} = t_{i,l}, t_{i′,l′−1} = t_{i,l−1}

or

σ_{l} = σ_{l′}^{−1} and t_{i′,l′} = t_{i,l−1}, t_{i′,l′−1} = t_{i,l}

We call e_{i′,l′} the corresponding edge. Let us consider the first time that an edge e_{i,s} was traversed before. The corresponding edge (which will be noted e_{i}), is clearly free. Since one of the endpoint of such an edge is i, it follows from fact 4 that e_{i} is one of edges e(T_{i′}), with 1 ≤ i′ ≤ j (otherwise e_{i} would be a new coincidence, or the edge e_{i,1}, but this would imply that σ_{1} = σ_{s}^{−1}, which is impossible). Hence Fact 5

{e(T_{i})|1 ≤ i ≤ j} = {e_{i}|1 ≤ i ≤ j} = {(a_{i}, i)|1 ≤ i ≤ j}

Without loss of generality, we may assume that the trajectory T_{i} wich has the smallest “l(T_{i})” is T_{1}. From the facts 4 and 5, we see that the set of edges {e_{i,l}|1 ≤ i ≤ j, 1 ≤ l ≤ l(T_{i})} forms one or several cycles (disjoint from the trajectories T_{i′}, with i′ > j). Hence the only way to fix the edges e_{1,l(T_{1})+1}, e_{1,l(T_{1})+2}, ⋯, is that σ_{1} = σ_{l(T_{1})+1}, σ_{2} = σ_{l(T_{1})+2},... It is rather straightforward to see that this implies that the sequence S can be written as S^{′t}, with t > 1. This clearly contradicts the fact that S is prime.

This proves the sublemma A.2. From this sublemma it is readily deduced that :

sublemma A.3

Prob (A′_{j}) ≤ \frac{(ks)^{2(j+1)}}{(n − ks)^{j+1}}

Proof Let us choose j + 1 edges among {e_{i,l}|1 ≤ i ≤ k, 1 ≤ l ≤ s − 1}. The probability that j + 1 given edges are coincidences is less than

\frac{(ks)^{j+1}}{(n − ks)^{j+1}}

(we use the same argument as for the estimation of Prob (σ_{s}(t_{s−1}) = 1|A_{j}) ). Therefore

Prob(A′_{j}) ≤ ( \begin{matrix}k(s − 1) \\ j + 1 \end{matrix} ) \frac{(ks)^{j+1}}{(n − ks)^{j+1}}

□ Therefore from equation (4) we obtain :

Prob(A_{j}) ≤ \frac{k^{3j+2}s^{2j+2}}{(n − ks)^{j+1}}

We deduce our lemma from that and equation (3), when the sequence S is strongly irreducible. If the sequence S is “only” irreducible, this means that S = S_{a}S_{b}S_{a}^{−1} (where S_{b} is strongly irreducible). In that case, the trajectory induced by S_{b}, returns to its starting point by describing a single loop, and we can use the previous discussion to bound the probability of this event, by \frac{1}{n^{k}} + O (\frac{1}{n^{k+1−δ}} ).

A.2 Proof of lemma 3

Here again, we suppose first that the sequence S is strongly irreducible. Here it may happen that we pass through 1, before step 1. Let us consider the subsequence S′ of S, for which we come back at 1 for the first time at the last step. Necessarily S = S^{′t}. We can use the same discussion as above with S′, but this time we obtain a slightly weaker corresponding sublemma A.2 : in case of event A′_{j} we can only prove that the set of trajectories T_{1}, T_{2}, ⋯, T_{k} contain j coincidences obtained before the last step. By making the same reasoning we obtain this time:

Prob(1 →^{S′} 1) = O (\frac{1}{n^{k−δ}} )

By summing over all possible subsequences (there are less than s such subsequences), we obtain our lemma in case of a strongly irreducible sequence S. This gives us our lemma when the sequence is strongly irreducible. When the sequence S is not strongly irreducible, we use the same argument as at end of the proof of lemma 2.

B Proof of lemma 5

Let us notice the relations

p_{2l,2s} = \frac{1}{2d}p_{2l−1,2s+1} + \frac{2d − 1}{2d}p_{2l−1,2s−1}  (5)
p_{2l+1,2s+1} = \frac{1}{2d}p_{2l,2s+2} + \frac{2d − 1}{2d}p_{2,2s}for s ≥ 1  (6)
p_{2l+1,1} = p_{2l,0} + \frac{1}{2d}p_{2l,2}  (7)
p_{2l+1,2s} = 0  (8)
p_{2l,2s+1} = 0  (9)

¿From (9) it follows

f_{2l}(z) = ∑_{s=0}^{l} p_{2l,2s}z^{2s}

¿From (8) it follows

f_{2l+1}(z) = ∑_{s=0}^{l} p_{2l+1,2s+1}z^{2s+1}

¿From (5) we obtain

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

¿From (6) and (7) we obtain

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

¿From f_{1}(z) = z, relations (10) and (11) we deduce our lemma.

References

[1] D. Angluin. On the complexity of minimum inference of regular sets. Information and Control 39 (1978), 302-320.

[2] D. Angluin and C.H. Smith. Inductive inference, theory and methods. Computing Surveys 15(3) 1983, 237-269.

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

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

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

[6] A. Broder, E. Shamir. “On the second eigenvalue of random regular graphs”, 28th annual Symposium on Foundations of Computer Science, 1987, 286-284.

[7] Y. Freund, M. Kearns, D. Ron, R. Rubinfeld, R.E. Schapire and L. Sellie. “Efficient learning of typical finite automata from random walks”, Proc. of the 25-th ACM Symp. on the Theory of Comp. 1993, 315-324.

[8] J. Friedman. “Random d-regular graphs”, Combinatorica 11 (4) 1991, 331-362.

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

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

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

[12] R.L. Rivest and R.E. Schapire. “Diversity based inference of finite automata” Proc. 28th Annual Symp. on the Found. of Comp. Sci (1987), 78-87.

[13] R.L. Rivest and R.E. Schapire. “Inference of finite automata using homing sequences” Proc. of the 21st ACM Symp. on the Theory of Comp. 1989, 411-420.

[14] Y. Roichman. Unpublished manuscript

[15] R.M. Tanner. “Explicit constructions of concentrators from generalized N-gons”, SIAM J. Alg. Disc. Meth., 5, 1984, 287-293.

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