Monica Billio

Cal Ès

Dominique Gu Égan

Portfolio Symmetry and Momentum $,$$

Keywords: (P) Finance, Graph Theory, Momentum, Quantum Probability, Spectral Analysis JEL Classification: C14, C44

This paper presents a novel theoretical framework to model the evolution of a dynamic portfolio (i.e., a portfolio whose weights vary over time), considering a given investment policy. The framework is based on graph theory and quantum probability. Embedding the dynamics of a portfolio into a graph, each node of the graph representing a plausible portfolio, we provide the probabilities for a dynamic portfolio to lie on different nodes of the graph, characterizing its optimality in terms of returns. The framework embeds cross-sectional phenomena, such as the momentum effect, in stochastic processes, using portfolios instead of individual stocks. We apply our methodology to an investment policy similar to the momentum strategy of Jeegadeesh and Titman (1993). We find that the strategy symmetry is a source of momentum.

Introduction

In a seminal paper, [START_REF] Jeegadeesh | Returns to buying winners and selling losers: Implications for stock market efficiency[END_REF] introduce the momemtum strategy. Considering a given market, their strategy consists of $ An earlier version of this paper has been presented at a University Paris-1 seminar, in February 2009 and at the European Conference on Operational Research -EURO XXIII in July 2009. We thank participants for their comments and feedback.

$$ The authors are very grateful to Rodney Wolff and an anonymous referee for their numerous comments which greatly helped to improve the paper.

* Corresponding author.

Email addresses: billio@unive.it (Monica BILLIO), ludovic.cales@unive.it (Ludovic CAL ÈS), dguegan@univ-paris1.fr (Dominique GU ÉGAN) buying stocks which performed well in the past and selling those which performed poorly. They showed that this strategy generates significant positive returns. This persistent arbitrage opportunity has raised a lot of interest, as it contradicts market efficiency.

The momentum strategy of [START_REF] Jeegadeesh | Returns to buying winners and selling losers: Implications for stock market efficiency[END_REF] is a zero-dollar long/short equally-weighted strategy being long the best stock decile of a given market and being short the worse stock decile. In order to determine the best and worse stock deciles, they rank the stocks according to their past performance. Typically, a stock past performance is its return over the last six months. The strategy being zero-dollar, the value of the sold stocks is the value of the bought stocks. The strategy being equally-weighted, the value invested in each stock is the same, in absolute value. [START_REF] Jeegadeesh | Returns to buying winners and selling losers: Implications for stock market efficiency[END_REF] used their momentum strategy in a market composed of all available stocks from the CRSP1 database. This strategy has been used in many other markets. It has been shown to generate significant positive returns in most international stock markets [START_REF] Rouwenhorst | International Momentum Strategies[END_REF], [START_REF] Chan | Profitability of momentum strategies in the international equity markets[END_REF]), in commodities markets [START_REF] Kazemi | Momentum in asset returns: are commodity returns a special case ?[END_REF]) and in currency markets [START_REF] Okunev | Do momentum-based strategies still work in foreign currency markets ?[END_REF]). For an extensive review of the research about momentum, we refer to [START_REF] Kazemi | Momentum in asset returns: are commodity returns a special case ?[END_REF]. Currently, it seems that momentum is a behavioral feature of finance. Indeed, according to [START_REF] Barberis | A model of investor sentiment[END_REF] and [START_REF] Daniel | Investor Psychology and security under-and over-reactions[END_REF], momentum is due to investors' under-reaction to news.

In this paper, we present a novel framework embedding cross-sectional phenomena, such as the momentum effect, in stochastic processes through the study of market dynamics using portfolios, and not individual stocks. Considering a given investment policy, we model the evolution of a dynamic portfolio as a path on a graph generated by an investment strategy. This framework takes into account the symmetries of the given strategy. These properties allows us to compute the probabilities for the occurences of given changes in a portfolio. Considering a momentum strategy, we find that the symmetry of this strategy is a source of the momentum effect. Finally, this new approach can improve asset management through the use of dynamic portfolios.

The paper is composed by four sections. Section 2 specifies the framework, based on graph theory and quantum probability, used to model the dynamics of a portfolio. In Section 3, we introduce the dynamics of a portfolio and its associated spectral distribution. Section 4 gives the probabilistic properties of the momentum effect and provides an application. Section 5 concludes.

The Framework

In this section, we introduce a framework which associates a graph with a given investment strategy.

Jeegadeesg & Titman's Momentum Strategy

An investment policy defines the set of all investable portfolios through the specification of constraints on the portfolios' weights. For instance, the momentum strategy of [START_REF] Jeegadeesh | Returns to buying winners and selling losers: Implications for stock market efficiency[END_REF] is defined as follows:

• 20% of stocks have non-zero weights (C1)

• the long and the short positions have equal weights, ω 0 , in absolute value (C2)

• the weights imply a 2:1 leverage 2 (C3)

• the number of long and short positions is the same (C4)

We can specify these four properties in a more formal way. Let us consider a market of N assets and note γ(i) the given weight associated with asset i in a portfolio. Respecting the momentum strategy of [START_REF] Jeegadeesh | Returns to buying winners and selling losers: Implications for stock market efficiency[END_REF], then we have:

• ∃J ⊂ {1, . . . , N } such that γ(j) = 0, ∀j ∈ J and |J| N ≈ 0.8 (C1) • |γ(i)| = ω 0 , ∀i ∈ {1, . . . , N } \J, ω 0 > 0. (C2) • N i=1 |γ(i)| = 2 (C3) • N i=1 γ(i) = 0 (C2+C4)
2 The notation 2:1 means that the amount of capital backing the portfolio represents 50% of the portfolio value. It is the minimum amount required under the U.S. Regulation T. As a consequence, the sum of the absolute values of the weights of the portfolio equals 2.

The Full Market Momentum Strategy

Here we consider a momentum strategy slightly different from that of [START_REF] Jeegadeesh | Returns to buying winners and selling losers: Implications for stock market efficiency[END_REF] presented in Section 2.1, based on a zerodollar long/short strategy with a leverage of 2:1. Instead of having positions in two deciles of the market stocks, the strategy we consider has positions in each of the market stocks. The constraint (C1) in Section 2.1 becomes:

• 100% of the stocks have non-zero weights (C1) So, any portfolio generated by this strategy is either long a position, with weight 2 N , or short the same position, with weight -2 N . In the following, we denote by Γ the set of portfolios generated by this specific strategy. We denote by γ a portfolio of Γ represented by the vector of its weights: γ = (γ(1), . . . , γ(N )) , where A stands for the transpose of A, and γ(i) corresponds to the weight of the portfolio γ in the i'th asset, ∀i = 1, . . . , N .

We call this strategy the "full market momentum strategy with leverage 2:1".

Definition 1: Having a market of N assets, N even, we define Γ to be the set of portfolios generated by the full-market momentum strategy with leverage 2:1, namely

Γ = γ ∈ - 2 N , 2 N N | N i=1 γ(i) = 0 .

Strategy representation

In order to obtain the distribution of the distance between a dynamic portfolio and its original portfolio -given a strategy and the portfolio dynamics -we use graph theory to obtain an elegant representation of the strategy. First of all, we specify the distance between two portfolios, then we introduce the notion of a graph associated with a strategy. Finally we illustrate our approach with an example.

Let γ 1 , γ 2 ∈ Γ. The turn-over between the two portfolios, noted T O(γ 1 , γ 2 ), defines a distance between γ 1 and γ 2 and we express it as the 1-norm distance:

T O(γ 1 , γ 2 ) = N i=1 |γ 1 (i) -γ 2 (i)|.
In the case of the full market momentum strategy, this distance is important for the construction of the graph characterizing the strategy and for portfolio management. Indeed,

• the turn-over distance corresponds to the minimum number of permutations between long and short positions in order to pass from one portfolio to another. It is also known as the Damerau-Levenshtein distance, as in [START_REF] Damerau | A technique for computer detection and correction of spelling errors[END_REF] and [START_REF] Levenshtein | Binary codes capable of correcting deletions, insertions, and reversals[END_REF]. Moreover, the previous distance describes the turn-over, and a distance of 1 can be interpreted as the minimum effort for an investor to pass from between portfolios. The minimization of the turn-over is of great interest for any investor because it reduces the transaction costs.

• it allows one to define a stratification of Γ, as presented in [START_REF] Hora | Quantum Probability and Spectral Analysis of Graphs[END_REF]. Associated with three matrices (the quantum components), it leads to the quantum decomposition which is the main notion of quantum stochastic calculus. This aspect is beyond the scope of this paper but leads to the theorem 1 used in Section 3. For more details, we refer to [START_REF] Hora | Quantum Probability and Spectral Analysis of Graphs[END_REF], Chapter 2. A presentation of the stratification is provided in Section 2.4. Now, we denote by E the set of edges such that each edge binds two portfolios whose turnover is minimal, i.e.,

E = {{γ 1 , γ 2 } |T O(γ 1 , γ 2 ) = 1 , γ 1 , γ 2 ∈ Γ} .
Then, we denote by G = (Γ, E) the undirected graph which characterizes the investment strategy. We provide an example for the full market momentum strategy, as follows. In a market of four assets (A, B, C and D), the portfolios generated by this strategy are given in Table 1 and the corresponding graph is given in Figure 1. The portfolios linked by an edge differ by one permutation between their long and short positions.

Minimization of the turn-over mentioned earlier corresponds to the search for the shortest path, which is a typical graph theory problem.

Asset A Asset B Asset C Asset D γ 1 2/N 2/N -2/N -2/N γ 2 -2/N 2/N -2/N 2/N γ 3 2/N -2/N -2/N 2/N γ 4 -2/N 2/N 2/N -2/N γ 5 2/N -2/N -2/N 2/N γ 6 -2/N -2/N 2/N 2/N
= ∞ n=0 Γ n , Γ n = {γ ∈ Γ|T O(γ, γ * ) = n}
is the stratification of Γ associated with the portfolio γ * , given by the minimum number of permutations which separate γ * from the portfolios of each stratum.

Considering the previous example, the stratification of Γ associated with γ 1 is illustrated in Figure 2, with Now, we introduce the optimal portfolio of Γ over a given period. Given the returns of N assets over a given period, we define the optimal portfolio for these assets as the portfolio, among those in Γ, which provides the highest return. In the case of the full market momentum strategy, the optimal portfolio buys the N 2 assets which performed the best and sells the N 2 assets which performed the worst.

Γ 0 = {γ 1 } , Γ 1 = {γ 2 , γ 3 , γ 4 , γ 5 } , Γ 2 = {γ 6 } 6
An important stratification for the study of the momentum effect is the one associated with the optimal portfolio in the case of the full market momentum strategy. The returns of the portfolios generated by this strategy, relative to the return of the optimal portfolio and according to the portfolios' strata, have the distribution given in Figure 3. The return of the portfolios is defined relative to the optimal portfolio return, so it is normalized over the different periods.

In Figure 3, we consider the monthly returns of the ten world sectorial indices of Datastream from 01/1973 to 09/2009 (439 observations per index). In the abscissa, we indicate the ratio of the portfolios' returns with respect to the optimal portfolio return. We observe that, on average, the return of a portfolio of a stratum n is greater than the one of a portfolio of a stratum m when m > n. Consequently, we expect a portfolio which is at a distance n from the optimal portfolio to provide a return greater than the return of a portfolio which is at a distance m from the optimal portfolio, when m > n. This fact is the basis of the study of the momentum effect.

We also observe that the distributions of the returns of the portfolios corresponding to the strata Γ n and ΓN 2 -n are symmetric with respect to 0. This property is due to the symmetry of Γ : indeed, if γ ∈ Γ n , then -γ ∈ Γ N 2 -n .

Figure 3: Distribution of the portfolios returns according to the portfolios' strata and relatively to the return of the optimal portfolio 2.5. Dynamic Portfolio A dynamic portfolio is a "portfolio" whose weights change over time. We represent it as a sequence of portfolios. For instance, in a market of four assets, a dynamic portfolio over the periods {T 1 , . . . , T 5 } can be represnted by (γ T 1 , γ T 2 , γ T 3 , γ T 4 , γ T 5 ), where

γ T 1 = 2/N 2/N -2/N -2/N ; γ T 2 = 2/N -2/N -2/N 2/N ; γ T 3 = 2/N -2/N 2/N -2/N . γ T 4 = -2/N -2/N 2/N 2/N ; γ T 5 = -2/N 2/N 2/N -2/N
We call γ T 1 the origin portfolio for the dynamic portfolio (γ T 1 , γ T 2 , γ T 3 , γ T 4 , γ T 5 ). The periods {T 1 , . . . , T 5 } can overlap, such as being periods corresponding to a rolling window. An example of dynamic portfolio is the sequence of optimal portfolios over a rolling window. Another one is the sequence of portfolios of Γ with the lowest volatility over a rolling window.

The Spectral Distribution

Given a graph associated with a strategy, we consider a dynamic portoflio whose dynamics is characterized by a random walk and we compute the distribution associated with the distance between this portfolio and its origin. This distribution is called the "spectral distribution".

Portfolio dynamics: a random walk

First, we suppose that the dynamic portfolio follows a walk on the graph G = (Γ, E). Thus, we have the following assumption:

A 0 : Considering a rolling window (T 1 , . . . , T n ) where each T i has the same length T , then we say that the dynamic portfolio (γ T 1 , . . . , γ Tn ) follows a walk on the graph

G = (Γ, E) if T O γ T i , γ T i+1 ≤ 1, ∀i ∈ {1, . . . , n}.
In the case of the full market momentum strategy, this means that two consecutive portfolios differ by at most one permutation. Figure 4 illustrates such a walk. This hypothesis is relevant for a dynamic portfolio based on returns whenever we expect that two consecutive portfolios with overlapping periods are very close. By choosing a long period and a short frequency, it appears possible to make this difference very small.

As an example, let us consider the market constituted by the ten Datastream world indices3 over 439 months from 01/1973 to 09/2009. In this market, we consider the optimal dynamic portfolio of the full market momentum strategy over a 22-day rolling window (period: 22 days; frequency: daily), and we count the differences between two consecutive optimal portfolios. The results are given in Table 2. We observe that the assumption A 0 is violated 3% of the time, and only by a distance of 2. We can fairly suppose that, in the case of a rolling window with an higher frequency (for instance hourly data), an intermediate portfolio appears. Then, instead of having two portfolios (γ a , γ b ) such that T O(γ a , γ b ) = 2, we shall have three portfolios (γ a , γ c , γ b ) such that T O(γ a , γ c ) = T O(γ c , γ b ) = 1. Thus, the 3% of violations will diminish. Moreover, we are only interested in the moves of a dynamic portfolio, thus, when two successive portfolios are equal we drop the second one.

We suppose now that the dynamics of the portfolio is characterized by a random walk with an equal probability of moving in any direction, thus we introduce the following assumption:

A 1 : The dynamic portfolio γ follows a random walk with an equal probability of moving in any direction.

In the case of the full market momentum strategy, this means that we give the same probability for the occurence of any permutation.

The Spectral Distribution of a Dynamic Portfolio

We give now an expression for the spectral distribution associated with this dynamic portfolio. The spectral distribution presented below corresponds to the probability of finding a dynamic portfolio at a given distance from an origin portfolio: it provides the probabilities for the dynamic portfolio to be in different strata of Γ.

General expression for the spectral distribution

Consider a graph G = (Γ, E) generated by a given strategy. We know that if the graph G is 2-antipodal distance-regular4 , then it can be characterized by the eigenvalues of its adjacency matrix, and their multiplicities, [START_REF] Fiol | Locally pseudo-distance-regular graphs[END_REF] . It means that the properties of an investment strategy represented by such a graph can also be resumed by its eigevalues. Consider now a dynamic portfolio γ p which verifies the hypothesis A 1 , on a distance-regular graph, then the following theorem provides the expression of the spectral distribution characterizing this dynamic portfolio. The proof of this theorem is postponed in Section 6.3.

Theorem 1. If G is a finite distance-regular graph with diameter d and intersection table

  c 0 c 1 c 2 . . . c d a 0 a 1 a 2 . . . a d b 0 b 1 b 2 . . . b d  
then the spectral distribution of G is a probability measure such that the probability for dynamic portfolio γ p verifying A 1 to be at a distance n from the original portfolio γ o after p random moves on G is :

P (T O(γ p , γ o ) = n) = |Γ k | d 2p P k |Γ| d i=0 m i λ p i P k (λ i )
where λ i are the eigenvalues of the adjacency matrix of the graph G, with their multiplicities m i , and {P n (x)} d n=0 are the Gram-Schmidt polynomials, defined as below in the three-term recurrence relation : [START_REF] Salimi | Continuous-time quantum walks on semi-regular spidernet graphs via quantum probability theory[END_REF]. The first use of the distance-regular property to characterize a walk is provided in Jafarizadeh and Salimi (2007) for a continuous-time quantum walk. This continuous-time quantum version can also be found as theorem 14.2.1 (and corollary 14.2.2) in the lecture given by Obata in Wroclaw in 20085 .

P 0 (x) = 1 P 1 (x) = x -a 0 xP n (x) = P n+1 (x) + a n P n (x) + b n-1 c n P n-1 (x) , n = 1, 2, . . .

This theorem is the discrete classical version of a continuous-time theorem presented in

The spectral distribution of a dynamic portfolio in the case of a fullmarket momentum strategy

We compute now the spectral distribution provided by the previous theorem for a full-market momentum strategy. Consider G = (Γ, E) the graph generated by the full-market momentum strategy on a market of N assets. In order to apply Theorem 1, we need to verify that G is a distance-regular graph and we also need to compute the eigenvalues of its adjacency matrix, with their multiplicities. This last computation uses the 2-antipodal property of G. These properties are obtained in the following lemma whose proof is relegated to Section 6, with the computations of the eigenvalues of the adjacent matrix of G.

Lemma 1. Given a graph generated by the full market momentum strategy, then we have the following properties: (i) It is a distance-regular graph, (ii) It is a 2-antipodal graph.

Thanks to this lemma, we are able to compute the spectral distribution associated with a full market momentum strategy. We illustrate this result in the following example. We consider a market of ten assets (N = 10) and we assume that a dynamic portfolio follows a random walk on G = (Γ, E). We provide in Figure 5 the probabilities that it will be at distance n from its origin after p = 1, 3, 5, 10 moves. They correspond to the probabilities of the dynamic portfolio to be in the stratum Γ n after p = 1, 3, 5, 10 moves. After one move, the dynamic portfolio can only be at a distance 1 from its origin, i.e., in stratum Γ 1 . After three moves, the dynamic portfolio can only be observed at distance 0, 1, 2 or 3 from its origin. Its distribution is then clearly skewed toward 0. The larger the number of moves, the more the spectral distribution tends to be symmetric, and thus less skewed toward zero. After ten moves, the distribution is already quite symmetric. Intuitively, when the number of moves increases, the probability of finding the dynamic portfolio in a node tends to be the same for any node. So, P (T O(γ p , γ o ) = n) tends to |Γn| |Γ| when p tends to infinity.

The Full Market Momentum strategy and the Momentum effect

In this section, we propose linking the momentum effect with the evolution of the optimal dynamic portfolio. Then, we illustrate this result through the market of the ten Datastream world indices discussed above.

The Momentum Effect

The momentum effect characterizes the persistance of the returns of a given portfolio. [START_REF] Jeegadeesh | Returns to buying winners and selling losers: Implications for stock market efficiency[END_REF] showed empirically that the optimal dynamic portfolio of their investment strategy (outlined in Section 2.1) presents some momentum effect. With our approach, considering that the assets selected in their strategy constitute the market, we observe the same momentum effect as them. Thus, as soon as we are in presence of the momentum effect, the optimal portfolio of our strategy should provide a positive return over the next period.

In Section 2.4, we have seen that we can characterize the momentum effect in terms of distance instead of returns. Thus, the new optimal portfolio should be close rather than far from the previous optimal portfolio. In other words, the spectral distribution of the optimal dynamic portfolio should be skewed toward 0. So, knowing the distance of a given portfolio from the origin portfolio is important because it permits one to measure how far the previous optimal portfolio (used as the investment portfolio) is from the current optimal portfolio. The shorter this distance, the greater are the returns of the investment portfolio, and the greater is the momentum effect.

Empirical verification with a ten-assets market

Consider the market constituted by the ten Datastream world indices over 439 months from 01/1973 to 09/2009. In this market, applying the full market momentum strategy, i.e., buying the half best performers and selling the half worse performers of the last month, and holding them the next month, leads to a monthly price return of 0.39% with a t-statistic of 3.47. So, this market exhibits momentum.

To describe the evolution of the optimal portfolio of the full-market momentum strategy, month by month, we use the spectral distribution given in Theorem 1. Indeed, we assume that the dynamic portfolio satisfies assumption A 1 . The probabilities for the dynamic portfolio to be at a distance n from its origin after p = 1, 3, 5, 10 moves are illustrated in Figure 5.

In Figure 6, we report the number of single steps that this optimal dynamic portfolio has executed every month. We observe that the number of moves is not always large enough to lead to a symmetric spectral distribution. Indeed, 8.9% of the number of moves are less than or equal to 5, and 17.8% of the moves are less than or equal to 6. They correspond to probabilities 60% and 56% of being at a distance less than or equal to 2 from the origin portfolio. So, the spectral distribution is clearly skewed. On average, it leads to a positive return for the dynamic portfolio, as we have shown in Section 2.4. So, according to our modeling, we observe momentum for about 15% of the observations. For the rest of the time, the number of moves leads to a symmetric distribution which corresponds to equal probabilities for the final portfolio to provide positive or negative returns. As a consequence and overall, we consider the strategy to be profitable. In Section 3.2.2, we have seen that the symmetry of the full market momentum strategy, through its graph, implies that the spectral distribution of a dynamic portfolio following a random walk is skewed towards its origin and that only for large numbers of moves it tends to be symmetric. Moreover, from our previous illustration, the number of moves observed in the market is not always large enough to imply a symmetric spectral distribution. So, in this case, the symmetry of the full market momentum strategy implies at least a part of the momentum effect observed on the market.

Conclusion

In this paper, we propose a novel framework to model the walk of dynamic portfolios on graphs corresponding to determined strategies. The nodes consist of the investable portfolios generated by a given strategy and the edges bind the portfolios which are at the minimal turn-over distance from one to the other. Under the assumption that a dynamic portfolio evolves passing from a portfolio of the graph to an adjacent one, we can use recent developments in graph theory and quantum probability to get the spectral distribution of the dynamic portfolio to be at a certain distance from a previous location. These probabilities depend on the graph's eigenvalues which represents the symmetries of the graph, i.e., the symmetries of the investment strategy.

As an illustration, we have seen that the symmetry of the momentum strategy induces a part of the momentum effect. Indeed a random walk on the graph generated by such a strategy produces probabilities (for the dynamic portfolio to be at a certain distance from a previous location) skewed enough to be at the origin of the momentum effect. Moreover, part of the momentum effect observed in the momentum strategy of [START_REF] Jeegadeesh | Returns to buying winners and selling losers: Implications for stock market efficiency[END_REF] can also be explained by this property of symmetry which characterizes the momentum strategy. Indeed, considering as the entire market the one composed of the assets selected in the strategy of [START_REF] Jeegadeesh | Returns to buying winners and selling losers: Implications for stock market efficiency[END_REF], the conclusions obtained for the full-market momentum strategy stand.

As the momentum effect is a short-term property of the markets, it would also be interesting, as future work, to model trends as long run walks, considering random walks as the noise surrounding this long run walk. Eventually, one might even think about modeling a business cycle as a cycle in terms of walk on a graph.

APPENDIX

6.1. Proof of Lemma 1 (i) Let denote G the graph generated by the Full Market Momentum Strategy in a market of N assets. We suppose N even. Let i, j, k be non-negative integers. We know that a graph G = (V, E) is distance-regular if for any choice of x, y ∈ V with d(x, y) = k the number of vertices z ∈ V such that d(x, z) = i and d(y, z) = j is independent of the choice of x, y. Thus, taking x, y ∈ V with d(x, y) = k the number p k ij = |{z ∈ V ; d(x, z) = i, d(y, z) = j}| is defined only depending on i, j, k.

Let F N 2 be the binary vector space of dimension N. As we are interested in a two-weight strategy, there exists an isomorphism between Γ and a subset of F N 2 . We consider that a vector φ of F N 2 represents a portfolio γ with

γ(i) = -2 N if φ(i) = 0 and γ(i) = 2 N if φ(i) = 1, i ∈ {1, . . . , N }.
Let consider γ, γ 1 , γ 2 ∈ Γ, three portfolios such that d (γ, γ 1 ) = i, d (γ, γ 2 ) = j and d (γ 1 , γ 2 ) = k. We note φ, φ 1 and φ 2 the respective representions of γ, γ 1 and γ 2 in F N 2 . Let note Γ i (γ 1 ) and Γ j (γ 2 ) the sets of the portfolios which are, respectively, at a distance i from γ 1 and at a distance j from γ 2 .

Γ i (γ 1 ) = {γ ∈ Γ|d (γ 1 , γ) = i} Γ j (γ 2 ) = {γ ∈ Γ|d (γ 2 , γ) = j} .
We divide Γ i (γ 1 ) ∩ Γ j (γ 2 ) in 4 parts:

P 1 = {i ∈ {1, . . . , N } |φ 1 (i) = 0 and φ 2 (i) = 1} P 2 = {i ∈ {1, . . . , N } |φ 1 (i) = 1 and φ 2 (i) = 0} P 3 = {i ∈ {1, . . . , N } |φ 1 (i) = 0 and φ 2 (i) = 0} P 4 = {i ∈ {1, . . . , N } |φ 1 (i) = 1 and φ 2 (i) = 1} . As d (γ 1 , γ 2 ) = k, we have: |P 1 | = k, |P 2 | = k, |P 3 | = N 2 -k and |P 4 | = N 2 -k.
Now, we study the allocation of, let say, the long positions of γ among these 4 parts. The strategy is two-weighted so, once the long positions are allocated, the short positions also are. With these notations, we have:

|Γ i (γ 1 ) ∩ Γ j (γ 2 )| = |A|,|B|,|C|,|D| k |A| k |B| N 2 -k |C| N 2 -k |D| .
(1) The strategy is a full-market momentum strategy, so φ has N 2 long positions and N 2 short positions, so:

|A| + |B| + |C| + |D| = N 2 . ( 2
)
Moreover d (γ, γ 1 ) = i, so we have:

|A| + |C| = i. (3)
As d (γ, γ 2 ) = j, we also have:

|B| + |C| = j. (4)
From ( 3) and (4), we get:

|B| = |A| + j -i (5) |C| = i -|A|. (6)
From ( 2), ( 5) and ( 6), we get:

|D| = N 2 -j -|A|. (7)
Noting |A| and inserting ( 5), ( 6) and ( 7) in (1), we finally get:

|Γ i (γ 1 ) ∩ Γ j (γ 2 )| = n k n k n + j -i N 2 -k i -n N 2 -k N 2 -j -n = k-j+i n=0 k n k k + i -j -n N 2 -k i -n N 2 -k n + j -k (8).
From (8), we have that |Γ i (γ 1 ) ∩ Γ j (γ 2 )| only depends on i, j and k, thus G is a distance-regular graph.

(ii) A graph G is k-antipodal when each of its vertex is diametrically opposed to k-1 others which are themselves diametrically opposed.

Considering the graph defined by a Full-Market Momentum strategy, the distance considered (half the Hamming distance) consists in permutations between long and short positions. Then, the maximum number of permutations that can be applied to a given portfolio is obtained by permuting all its long position with all its short positions, as there are N 2 long positions and N 2 short positions. So the maximum distance between any two portfolios is N 2 . It corresponds to the diameter of the graph. Moreover, only one portfolio corresponds to the one got by permuting all the long positions with all the short positions of a given portfolio. Thus, the graph is 2-antipodal.

6.2. Computation of the spectrum of the graph generated by the 2-Weight Full Market Momentum Strategy Let consider the graph G defined by a Full-Market Momentum strategy. Its diameter is noted d. From Lemma 1 (i), we know that it is a distanceregular graph. Let note its intersection table as following

  c 0 c 1 c 2 . . . c d a 0 a 1 a 2 . . . a d b 0 b 1 b 2 . . . b d   .
We know that the eigenvalues of the adjacency matrix of the distance-regular graph G are the eigenvalues of the following matrix T:

T =          a 0 b 1 c 1 a 2 b 2 c 2 a 3 . . . . . . . . . . . . a d-1 b d-1 c d-1 a d         
.

The matrix T is a (d + 1) × (d + 1) matrix. From Lemma 1 (ii), we have d = N 2 . So, for markets with a reasonable number of assets, we are able to

m k = d i=1 |λ 0 -λ i | d i=0,i =k |λ k -λ i |
, ∀k ∈ {1, . . . , d}

Proof of Theorem 1

In the following, we use the bracket notation of quantum probability. Let consider a graph G = (V, E) and its adjacency matrix A. Let x, y ∈ V and p ∈ Z. From proposition 2.9 in [START_REF] Hora | Quantum Probability and Spectral Analysis of Graphs[END_REF], we have that < δ x |A p |δ y > is the number of p-steps walks connecting the vertices y and x.

So, the number of p-walks from the origin to the elements of Γ k is Let note µ the spectral distribution of adjacency matrix A. We have

µ = 1 |Γ| d i=0 m i δ λ i
where λ i and m i are the eigenvalues, with multiplicities, of A.

As seen in section 6.1, G is a distance regular graph with diameter d. In this case, from the expression (4.16) in Jafarizadeh and Salimi (2007), we have:

< Φ k |A p |Φ o >= 1 P k R x p P k (x) µ(dx)
where {P k (x)} d i=0 are the orthogonal polynomials defined by the three-term relation.

By integrating the last expression using the spectral distribution as defined above, we have

< Φ k |A p |Φ o >= 1 P k |Γ| d i=0 m i λ p i P k (λ i )
So, the number of p-walks from the origin to the elements of Γ k is

|Γ k | P k |Γ| d i=0 m i λ p i P k (λ i )
Moreover, in our case, as G is a d 2 -regular graph, the total number of p-steps walks is d 2p . In addition, according to assumption A 1 , the walk is random. So, each of these p-steps walks have the same probability. Consequently, the probability, for a dynamic portfolio γ p which follows a random walk on G, to be at a distance n from the original portfolio γ o after p random moves, is :

P (T O(γ p , γ o ) = n) = |Γ k | d 2p P k |Γ|

Figure 1 :

 1 Figure 1: Graph associated with the Full Market Momentum Strategy

  Document de Travail du Centre d'Economie de la Sorbonne -2009.03 (Version révisée)

Figure 2 :

 2 Figure 2: Stratification of Γ associated with portfolio γ 1

Figure 4 :

 4 Figure 4: Illustration of a walk in a graph Distance 0 1 2 3+ Percentage of occurence 56% 41% 3% 0%

Figure 5 :

 5 Figure5: Spectral distribution for a dynamic portfolio to be at a distance n from its origin after 1, 3, 5, 10 moves

Figure 6 :

 6 Figure 6: Number of single moves of the optimal portfolios over a month

  du Centre d'Economie de la Sorbonne -2009.03 (Version révisée)A = {i ∈ {1, . . . , N } |φ(i) = 1 and φ 1 (i) = 0 and φ 2 (i) = 1} B = {i ∈ {1, . . . , N } |φ(i) = 1 and φ 1 (i) = 1 and φ 2 (i) = 0} C = {i ∈ {1, . . . , N } |φ(i) = 1 and φ 1 (i) = 0 and φ 2 (i) = 0} D = {i ∈ {1, . . . , N } |φ(i) = 1 and φ 1 (i) = 1 and φ 2 (i) = 1} .

20

  Document de Travail du Centre d'Economie de la Sorbonne -2009.03 (Version révisée) compute the graph eigenvalues.From Lemma 1 (ii), we also know that G is 2-antipodal. And fromDalfo et al. (2009), we know that a distance-regular graph G of diameter d with spectrumSpec(G) = λ 0 λ 1 . . . λ d m 0 m 1 . . . m d is r-antipodal (r ≥ 2)if and only if its eigenvalues satisfy:m k = π 0 π k (k even) m k = (r -1) π 0 π k (k odd) where π k = d i=0,i =k |λ k -λ i |.So we can compute the multiplicities of the eigenvalues as follows:

  x∈Γ k < δ x |A p |δ o >Using the usual notation, we noteΦ k = 1 |Γ k | x∈Γ k δ x and observing that Φ 0 = δ o as |Γ 0 | = 1the number of p-walks from the origin to the elements of Γ k is|Γ k | < Φ k |A p |Φ 0 >21Document de Travail du Centre d'Economie de la Sorbonne -2009.03 (Version révisée)

  du Centre d'Economie de la Sorbonne -2009.03 (Version révisée)

Table 1 :

 1 Portfolios of the Full Market Momentum strategy in a market of four assets

Table 2 :

 2 Distance between two consecutive portfolios in the optimal dynamic portfolio

Center for Reseach in Security Prices

Document de Travail du Centre d'Economie de la Sorbonne -2009.03 (Version révisée)

Document de Travail du Centre d'Economie de la Sorbonne -2009.03 (Version révisée)

WORLD-DS Oil & Gas, Basic Mats, Industrials, Consumer Gds, Health Care, Consumer Svs, Telecom, Utilities, Financials, Technology

These notions are recalled in Section 6 11 Document de Travail du Centre d'Economie de la Sorbonne -2009.03 (Version révisée)

The notes of this lecture are available at http://www.math.uni.wroc.pl/analiza/obata/index.html 12 Document de Travail du Centre d'Economie de la Sorbonne -2009.03 (Version révisée)


domain: math info

text:
Olivier Batard

David Lubicz

Embedded evaluation of the statistical parameters of the thermal noise for online test of TRNG

Keywords: Hardware random number generators, free-running oscillators, stochastic models, entropy, dedicated statistical tests

 can have dramatic effects on its precision and reliability. In this paper, we propose a recipe for choosing good parameters and present some algorithmic tweaks to improve its robustness. We have extensively tested the new method with simulations and implemented it in hardware to verify its efficiency and practicality.

Introduction

Random numbers generators are essential security component used in every cryptographic hardware implementation for the production of confidential keys, initialization vectors, padding values, challenge for authentication protocols and also as random masks in side-channel attack countermeasures. They are usually composed of two stages: a non deterministic stage, called True Random Number Generator (TRNG) and a deterministic one, called Deterministic Random Number Generator (DRNG). The TRNG serves as an entropy source to guarantee unpredictability of generated numbers against an adversary with an unlimited computational power. The DRNG, which uses TRNG output as a seed, ensures that the output of the random number generator is unpredictable for an attacker with a bounded computational power even if the TRNG partially or temporarily fails according a security model such as the one of [].

1 This paper deals with the TRNG stage of a random number generator. It is still a challenging task to design such a device with a high level of certainty on its security which is measured for cryptographic application by its entropy rate. In order to do so, according to [], it is necessary to go thought a several steps process, the main points of which being:

1. identifying a unpredictable physical phenomenon that can be exploited in the operation of the electronic device and have a statistical model for this phenomenon;

2. design a TRNG using this phenomenon and have a stochastic model of the TRNG depending on parameters and giving the distribution of the output bits of the TRNG;

3. measure the parameters of the random phenomenons and using the stochastic model of the TRNG compute its entropy rate.

As far as we know, there is not much choice for a technological platform for which a simple and reliable implementation of all the steps of the preceding process in known. One known possibility uses the instability of the propagation time of the electric signal across logic gates called time jitter. It can be amplified in a so called ring oscillators which is composed of a sequence of inverters and delay elements connected in ring. A ring oscillator produces, when enabled, a clock signal the phase of which randomly fluctuate causing the so called phase jitter. The phase jitter can be exploited to produce random numbers. An example of simple well known design to do so, called Elementary Ring Oscillator based TRNG (ERO-TRNG) [START_REF] Fischer | Entropy computation for oscillator based trng[END_REF] is composed of two ring oscillators O 1 and O 2 , the signal of O 2 sampling that of O 1 with a type-D flipflop. More complex designs such as MRO-TRNG are described in [START_REF] Fischer | Entropy computation for oscillator based trng[END_REF].

The phase jitter is the result of several physical phenomenons or noises with different statistical properties. The paper [START_REF] Baudet | On the Security of Oscillator-Based Random Number Generators[END_REF] describes a statistical model to compute contribution of the thermal noise to the entropy rate of the TRNG. Since the thermal noise is statistically independent of the other sources of noises, this model, based on a unidimensional Weiner process, is sufficient to compute a lower bound on the entropy rate of a oscillator based TRNG. The statistical parameters of this model are given by the drift λ and volatility σ of a Weiner process [START_REF] Baudet | On the Security of Oscillator-Based Random Number Generators[END_REF]. Measuring the physical quantity related to these parameters is one of the most challenging part of the design of an oscillator based TRNG with a good level of certainty on its security. One difficulty lies in the fact that it is necessary to distinguish the different components of the phase jitter (see [START_REF] Baudet | On the Security of Oscillator-Based Random Number Generators[END_REF] for a more in depth discussion on this subject). A way to distinguish the thermal noise component of the phase jitter is to measure it at high frequency where it is predominant over other noise sources.

The phase jitter can be measured externally, the clock signal being analyzed by an oscilloscope or with the internal method described in [START_REF] Fischer | Embedded Evaluation of Randomness in Oscillator Based Elementary TRNG[END_REF], the measure on the analog signal is done inside the chip and only numerical data are processed after this measure. The problem with the external method is that the acquisition chain add a lot of perturbation on the analog signals which make the measure less precise. It is also not practical because one can not use an oscilloscope on the assembly line of the chip. The second method is in theory far more accurate and practical. Still, in most cases, in practise, it does not achieve the goals displayed in [START_REF] Fischer | Embedded Evaluation of Randomness in Oscillator Based Elementary TRNG[END_REF] to have a reliable and precise measure, simple enough to be embedded inside a chip (including the computational steps necessary to recover the parameters λ and σ). Actually, the good operation of the method depends on the choice of parameters and good configuration of the oscillators which is non trivial, not always possible and not explained. With a random choice of parameters and configurations in most cases the internal measure will lead to poor estimation of the statistical parameters of the thermal noise component of the phase jitter. This can lead to an overestimation of the entropy rate of the TRNG and thus a security vulnerability. The aim of this paper is to point to and explain the shortcomings of the method [START_REF] Fischer | Embedded Evaluation of Randomness in Oscillator Based Elementary TRNG[END_REF] and explain how to tweak it to overcome these problems.

The paper in organized as follows. In Section 2, we briefly recall the method of [START_REF] Fischer | Embedded Evaluation of Randomness in Oscillator Based Elementary TRNG[END_REF] in order to set the notations for the rest of the paper and explain in Section 3 the shortcomings of the method. In Section 4, we introduction improvements based an new algorithm to overcome the problems previously described. In Section 5, we present the outcome of our hardware implementation and extensive experiment of the new method to show its reliability. Then, we build upon the previous results to explain how to embed the internal measure method.

2 The internal measure method : summary and shortcomings

In this section, we briefly recall the method of [START_REF] Fischer | Embedded Evaluation of Randomness in Oscillator Based Elementary TRNG[END_REF] in order to fix the notations, explain its shortcomings and hint at our improvements. In [START_REF] Fischer | Embedded Evaluation of Randomness in Oscillator Based Elementary TRNG[END_REF], the authors show that what they call an elementary oscillator-based TRNG can be seen at the same time, for a different mode of operation, as an efficient measurement device for the phase jitter.

In order to simplify the presentation, we only describe the elementary oscillator-based TRNG in its configuration for measuring the phase jitter and call it an oscillator-based jitter measurement device (OJMD). An OJMD is composed of two oscillators, O i for i = 1, 2. The output clock signal of O 2 is used to determine the sampling times of O 1 . The sampling unit can be a synchronous D flip-flop (see Figure 1). In this case, the sample times correspond to the rising edges of the signal of O 2 .

For i = 1, 2, the output signal of O i is given by a quasi-periodic function s i (t) of time t that takes the form

s i (t) = f αi (ω i (t + ξ i (t))), (1)
where for α ∈ [0, 1), we define f α as the real valued 1-periodic function such that f α (x) = 1 for all 0 < x < α and f α (x) = 0 for α < x < 1, and f α (0) = f α (α) = 1/2. The parameter α i accounts for the duty cycle of s i (t). Up to replacing f αi by 1 -f αi , we will always suppose in the following that α i ∈ [0, 0.5). For i = 1, 2, ω i is the mean frequency of the signal s i (t), ϕ i (t) = ω i (t + ξ i (t)) is its phase and the function ξ i (t) represents its absolute phase drift caused by the time jitter that we call phase jitter. Similarly, T i = 1/ω i is the mean period of s i (t). Following [START_REF] Baudet | On the Security of Oscillator-Based Random Number Generators[END_REF], for i = 1, 2, we model the evolution of the total phase ϕ i (t) = ω i (t+ξ i (t)) from Eq. ( 1), i.e. the phase of a ring oscillator O i subject to the thermal noise, using a stationary Wiener stochastic process Φ i (t) with drift µ i > 0 and volatility σ 2 i > 0. In other words, for any time t ≥ t 0 , the phase Φ i (t) conditioned by the value Φ i (t 0 ) = ϕ(t 0 ) follows a Gaussian distribution of expected value ϕ i (t 0 )+µ i (t-t 0 ) and variance σ 2 i (t-t 0 ). In [3, Appendix C], it is shown that, under general hypothesis always fulfilled in practise, the output of oscillator O 1 with duty cycle α 1 drift T 1 and volatility σ 2 1 , sampled at time intervals determined by oscillator O 2 with drift T 2 and volatility σ 2 2 produces the same distribution of output bits as that of a stable clock signal (a jitter-free signal) with period duty cycle 0.5 and period T 2 /T 1 sampling an oscillator O ′ 1 with duty cycle α 1 , drift 0 and volatility σ where σ = T2 T1 2 σ 2 2 + σ 2 1 . We call the triple:

(α = α 1 , µ = T 2 /T 1 mod 1, σ 2 = T 2 T 1 2 σ 2 2 + σ 2 1 ) (2)
the statistical parameters of the OJMD composed of the oscillators O 1 and O 2 . The knowledge of these parameters are enough to reproduce the distribution of the output bits b = (b j ) j=1,...,n at sampling times (t j ) j=1,...,n of the OJMD. Actually, the internal state of a OJMD with parameters (α, µ, σ 2 ) can be represented by a phase ϕ(t) depending on t. The output at time t of the OJMD knowing the phase according to (1) is f α (ϕ(t)).

As said before, the evolution of ϕ(t) is given by a Wiener process Φ(t) over the interval [0, 1] with drift µ and volatility σ 2 . So, from the knowledge of ϕ(t 0 ) at time t 0 , at time t > t 0 , the phase at t is drawn at random following the Gaussian distribution with expected value µ and standard deviation σ. The Algorithm 1 uses this in order to produce a series of bits following the distribution of a OJMD with given parameters (α, µ, σ 2 ).

In [START_REF] Fischer | Embedded Evaluation of Randomness in Oscillator Based Elementary TRNG[END_REF], the authors describe a method, which we briefly recall, to measure the statistical parameters (α, µ, σ 2 ) of a OJMD from the knowledge of a sample of its output bits. For n ∈ N * , let b = (b j ) j∈{1,...,n} be the output bits sequence corresponding to the sampling of O 1 at times (t j = t 0 + jµ) j∈{1,...,n} given by the rising edges of O 2 as depicted in Fig. 1. For any S ⊂ {1, . . . , n}, we define

P S {b j ̸ = b j+M } = #{j ∈ S|b j ̸ = b j+M } #S .
The method of [START_REF] Fischer | Embedded Evaluation of Randomness in Oscillator Based Elementary TRNG[END_REF] is based on three facts that we state without recalling all the conditions upon which they rely for the sake of simplicity and because in the following we are going to discuss these conditions. Let N ∈ N and for i ∈ {1, . . . , n -N + 1}, we set S i = {i, . . . , i + N -1}.

Algorithm 1: Algorithm to simulate a OJMD subject only to the thermal noise input :

• (α, µ, σ 2 ) the statistical parameters of the OJMD;

• n a number of output bits;

• (t j ) j=1,...,n sampling times.

output: (b j ) j=1,...,n output bits.

1 ϕ = 0.5 /* Comment Initial relative phase */ 2 t 0 ← t 1 -1; 3 for i = 1 to n do 4 Draw a random x following the distribution G(µ(t i -t i-1 ), σ 2 (t i -t i-1 )) ; 5 ϕ ← (ϕ + x) mod 1; 6 if ϕ < α then 7 b i ← 1;
D(M )(x)dx = P{(Φ(t 0 + M µ) ≤ x|Φ(t 0 )) = x 0 ∈ [a, b]} where Φ(t)
is the Wieiner process governing the evolution of the phase ϕ(t) of the OJMD with statistical parameters (α, µ, σ 2 ).

Using Fact 1, one can recover σ 2 by computing the empirical variance V (S N,M ) of S N,M with any variance estimator such as:

V (S N,M ) = 1 K K i=1 c 2 i -( 1 K K i=1 c 2 i ).
We remark that, if we make the hypothesis that O 1 and O 2 are only subject to the thermal noise component of the phase jitter, V (S N,1 ) = σ 2 and that V (S N,M ) = M V (S N,1 ), so that in order to improve the measure of σ 2 , one can compute a sample of V (S N,M ) for different values of M and recover σ 2 = V (S N,1 ) as the slope of the line obtained as the linear regression of the samples. If M is small enough, the thermal noise will be preponderant over other noise sources so that the behaviour of V (S N,M ) as a function of M will be linear that the slope of V (S N,M ) gives σ 2 . Fact 2. [2, Fact 2] Under certain hypothesis, we have for any S ⊂ S

1 2 P S {b i ̸ = b i+1 } = T 2 /T 1 mod 1 if T 2 /T 1 < 0.5 1 -T 2 /T 1 mod 1 otherwise. (3)
Fact 2 immediately gives a way to recover µ = T 2 /T 1 mod 1.

Fact 3. [2, Fact 1] Under certain hypothesis, we can obtain the duty cicle of the oscillator O 1 of the OJMD as:

α = n i=1 b i n . (4)
It is clear that together Fact 1, Fact 2 and Fact 3, in principle, allow to recover the statistical parameters (α, µ, σ 2 ) of the OJMD. Nonetheless, as stated, these facts depend on hypothesis that are not always easy to fullfil and control. We are going to see in the next section that if these conditions are not verified, the precision of the measures may be greatly affected resulting in some cases in absurd outcomes.

Shortcomings of the method

We first treat the case of Fact 3, which is the easiest. Recall that (t j ) j=1,...,n are the sampling times corresponding to the rising edges of the signal produced by O 2 . Then Fact 3 is true as long as (t i mod T 1 ) follows a uniform distribution in [0, T 1 ]. This property is guarantied over a long period of time by the jitter phenomenon even if we suppose it to be very small. By the central limit theorem, the precision of the measure is in the order of 10 log 10 (n)/2 with high probability.

As for Fact 2, it is true as long as (t i mod T 1 ) follows a uniform distribution in [0, T 1 ]. Again, the precision of the measure is, with high probability, in the order of 10 log 10 (n)/2 .

The analysis of Fact 1 is much more delicate than the other facts in part because it depends on the choices of the parameters N and M which may affect its outcome. In order to assess its precision and the conditions upon which it works, we have made simulations using Algorithm 1 to produce series of bits (b j ) j∈{1,...,n} by a simulated OJMD with well chosen statistical parameters (α, µ, σ 2 ) for the thermal noise and used Fact 1 to recover σ 2 with different choices of N, M .

A first observation is that the line obtained as the linear regression of the samples V (S N,M ) does not pass through the origin as it should in theory: its equation is of the form σ 2 x + b = 0 where in general b in non-zero. Using simulation it is easily seen that this is due to the quantization error when approximating ϕ(t 0 + (M + i)µ) -ϕ(t 0 + iµ) by c i . This means in particular that one has to compute V (S N,M ) for at least two values of M to be able to recover σ 2 .

In a first experiment, we have used Algorithm 1 with parameters (α = 0.5, µ = 0.3376, σ 2 = 10 -6 ). We have computed the samples (S 117,M ) for M = (300 + 5j) j=0,...,49 and plotted in Figure 2 the variance of these samples together with the line L σ 2 with slope 10 -6 = σ 2 that we should recover. We see that although most points V (S 117,M ) fit correctly with L σ 2 , there are a lot of outliers. For instance, although V (S 117,540 ) is very close to L σ 2 , V (S 117,545 ) is widely apart. If we look in Figure 3 at the cumulative distribution function of S 117,540 , we see that it is well approximating the cumulative distribution function of a Gaussian distribution as it should be for a Weiner process. This is not the case of the cumulative distribution function of S 117,545 on the right hand of Figure 3 where we note that the left tail of the expected Gaussian distribution is flattened.

How can we explain that ? In fact, if we have a closer look at the statement of [2, Fact 1], we see that the c i are not drawn following the probability density function D(M )(x) but rather that of ψ α (D(M )) where ψ α is the function defined as:

ψ α (x) = 2x if 0 ≤ x ≤ α, ψ α (x) = 2α if α ≤ x ≤ 1 -α, ψ α (x) = 2 -2x if 1 -α ≤ x ≤ 1.
(5) Using this we can explain the shape of the distributions obtained in Figure 3. In the left hand figure, the Gaussian distribution is contained in the interval [0, α] so that it is just stretched by a factor 2 by the function ϕ α . In the right hand figure, the expected value of the Gaussian distribution is in 0 so that it is folded by ψ α . This explains why, in the second case, the computation of the variance of the distribution is far lower than the expected one thus the corresponding abnormal point in the Figure 2. This problem occurs whenever the ϵ-support of the probability density function D(M ) intersects the set {0, α}. By ϵ-support, we mean the smallest interval I centered around the expected value of D(M ) such that I D(M ) ≥ 1 -ϵ for a small ϵ > 0. But the mean value of D(M ) in [0, 1] is given by M T 2 mod T 1 so that it is fixed by the parameter M . Thus we see that whether the empirical distribution of S N,M is a good approximation of D(M ) depends of a choice of M that is not explained in [START_REF] Fischer | Embedded Evaluation of Randomness in Oscillator Based Elementary TRNG[END_REF]. We made a second experiment to illustrate the sensitivity of the method of [START_REF] Fischer | Embedded Evaluation of Randomness in Oscillator Based Elementary TRNG[END_REF] with the N parameter of Fact 1. We have generated a bit sequence using Algorithm 1 with parameters (α = 0.5, µ = 0.332, σ 2 = 10 -6 ). We have computed the samples (S 80,M ) and (S 125,M ) for M = (300 + 5j) j=0,...,49 and plotted in Figure 5 the variance of these samples together with the line L σ 2 with slope 10 -6 = σ 2 that we should recover.

We see that V (S 125,M ) fits correctly with the expected L σ 2 but that V (S 80,M ) does not even looks like an affine law. The problem here is that Fact 1, rely on the hypothesis that the distribution of {iµ mod 1, i = 1, . . . , N } is ϵ-uniform for a small positive ϵ. This means that the number of samples of {iµ mod 1, i = 1, . . . , N } in the interval [a, b] over N is close (up to a small ϵ) to the expected one if the distribution of the {ξµ mod 1, i = 1, . . . , N } was uniform in the interval [0, 1] that is the size of the interval [a, b].

We see in Figure 4 that the distribution of {iµ mod 1, i = 1, . . . , N } is uniform in [0, 1] (represented by a circle in the figure) if N = 80 but this is not the case if N = 40. This time we see that whether the empirical distribution of S N,M is a good approximation of D(M ) also depends in a crucial manner on the choice of N .

Improvements

In the previous section, we have described cases when the distribution of S N,M that we can compute is not a good approximation of that of D(M ) that we want to recover. A first problem affects the choice of M and the second that of N so that if one does not take care when choosing the parameters of the method of [START_REF] Fischer | Embedded Evaluation of Randomness in Oscillator Based Elementary TRNG[END_REF], the outcome may be very far from the result that we look for. In this section, we explain how to tweak the jitter measurement method of [START_REF] Fischer | Embedded Evaluation of Randomness in Oscillator Based Elementary TRNG[END_REF] to overcome these defects and so to improve its precision and reliability.

Outlier detection and mitigation

We have seen that the distribution of the S N,M that we compute does not follow the probability density function D(M ) but rather that of ψ α (D(M )) where ψ α is defined by [START_REF] Lubicz | Towards an Oscillator Based TRNG with a Certified Entropy Rate[END_REF].

In the case that the ϵ-support of the distribution D(M ) intersects {0, α} the distribution of the S N,M will not be, in general, a good approximation of D(M ) up to a linear factor. In order to avoid this, one can filter out bad values of M so that the ϵ-support of S N,M does not meet {0, α}. We suppose that σ is very small compared to 1 which is the case in most of the measures that we have done on a wide range of different technologies.

A first idea to filter out bad values of M is to choose M so that

√ σ 2 M < ϵ 0 (6) |E(D(M )) -α/2| < ϵ 0 , (7)
for ϵ 0 > 0 much smaller than α (for instance take ϵ 0 = α/4). Actually, if the variance of D(M ) is small and its expected value is far from {0, α} then the probability that the ϵ-support of D(M ) gets across {0, α} is small. We remark that, as one can evaluate T 2 /T 1 mod 1 and α using respectively Facts 2 and 3, it is possible to recover |E(D(M ))-α/2| as [M T 2 /T 1 mod 1-α/2| and so choosing a M verifying the second condition. Nonetheless, as don't know σ 2 because this is exactly what we want to measure, it is difficult to verify that the first condition is fulfilled. So the method works only if one knows an order of magnitude of σ 2 and take margins. The problem is then that we are going to discard a lot of values of M suitable for the computation of σ 2 . By being to much selective on M we take the risk to eliminate all possible values or diminish drastically the number of points used to compute a linear regression and so lose precision. We would like to be able to asses if the distribution S N,M actually gets across {0, α} without an a priori knowledge of σ 2 .

In order to explain how to do it, we suppose to simplify the explanation that S N,M gets across 0 (the case of α is similar). Let c i = 1 2 P Si {b j ̸ = b j+M } for i ∈ {1, . . . , n-N -M +1} and we recall that S i = {i, . . . , i + N -1}. Let δ(M, t) = ϕ(t + M µ) -ϕ(t). As the phase jitter per period is small, we have:

|δ(M, t 0 + iµ) -δ(M, t 0 + (i -1)µ)| < ϵ 1 , (8)
for a small ϵ 1 (of the order of √ σ 2 T 2 ). Moreover, if the conditions of Fact 1 are fullfiled, there exists a small ϵ 2 (M ) > 0 such that for all i ∈ {1, . . . , n -

N -M }, |x -δ(M, t 0 + iµ)| < ϵ 2 (M ), (9)
for x ∈ {c i , 1 -c i }. When c i is far from 0, c i and 1 -c i are far apart from each other so that it is easy to decide which one is the correct approximation of δ(M, t 0 + iµ) by induction on i: for c 0 we can choose at random any of c 0 and 1 -c 0 , this will act by -1 on the computed distribution of the δ(M, t 0 + iµ) for i = 1, . . . , N without affecting its variance. Then suppose that we have chosen a good approximation y ∈ {c i-1 , 1-c i-1 } of δ(M, t 0 + (i -1)µ) then by equations ( 8) and (9),

x ∈ {c i , 1 -c i } is a good approximation of δ(M, t 0 + iµ) if it verities |x -y| < ϵ 1 + 2ϵ 2 (M ).
But when c i is near to 0, we don't have a criterion to decide which of c i or 1 -c i is the good approximation of δ(M, t 0 + iµ) so we can not use the value of c i to detect if δ(M, t 0 + iµ) crosses 0 for different values of i. In order to improve that, using the fact that, in practise, the jitter by period √ σ 2 T 2 is small, for λ = ±1, we have for all t 0 :

|ϕ(t 0 + M µ) -(ϕ(t 0 + (M -λ)µ) + λµ)| < ϵ 1 for a small ϵ 1 of the order of √ σ 2 T . This means that: |δ(M, t 0 + iµ) -(δ(M -λ, t 0 + iµ) + λµ)| < ϵ 1 . (10)
Based on this remark, keeping the definition for ϵ 1 , ϵ 2 (M ) from above, we have the following fact:

Fact 4. Let λ = ±1 be an integer, let c i = 1 2 P Si {b j ̸ = b j+M } and c ′ i = 1 2 P Si {b j ̸ = b j+M -λ }. Set ϵ = ϵ 1 + 2max(ϵ 2 (M ), ϵ 2 (M ± λ)). If we have |λµ mod 1| > ϵ, |λµ - 1 -2c i 2 mod 1| > ϵ, (11)
there is a unique pair (x, y) where x ∈ {c i , 1 -c i } and y ∈ {c Proof. The existence of the pair (x, y) is an immediate consequence of the triangular inequality and the fact that for a

′ i + λµ, 1 -c ′ i + λµ} such that |x -y| < ϵ.
x ∈ {c ′ i , 1 -c ′ i }, |x -δ(M -λ, t 0 + iµ)| < ϵ 2 , for a y ∈ {c i , 1-c i }, |y-δ(M, t 0 +iµ)| < ϵ 2 and moreover that |δ(M, t 0 +iµ)-δ(M -λ, t 0 +iµ)+λη mod 1| < ϵ 1 .
For the unicity, suppose that

|c ′ i -c i + λµ| < ϵ. If |1 -c ′ i -c i + λµ mod 1| < ϵ then |λµ -1-2ci 2 mod 1| < ϵ. If |1 -c ′ i -1 -c i + λµ| < ϵ, then |λµ -0 mod 1| < ϵ. The case, |c ′ i -1 -c i + λµ| < ϵ is similar.
In order to use the preceding Fact, we remark that we can obtain a good approximation of µ using Fact 2 and then use it to check if the conditions (11) are fulfilled (in practise, one can take safely ϵ = 1/10). Then Fact 4 allows to lift the ambiguity about which of c i and 1 -c i is a good approximation of δ(M, t 0 + iµ) except in the rare cases when conditions (11) are not fulfilled. In this case, one can redo the computations with λ = -1. This gives a way to detect when c i gets across 0.

We can use it either to detect when a c i is likely to be an outlier and discard it as in Algorithm 3. It is also possible to compute c i taking into account of the fact that it has crossed 0 or α as in Algorithm 4. Note that in this last algorithm the distribution of c[i] that we compute can get across 0 or α but the P S (b j ̸ = b j+M ) is always in [0, 1] so that we have to glue them together using the integer offset that is updated by plus or minus 1 when the c[i] goes through 0 or 1.

We have tested the two algorithms with the Wiener process W (α = 0.5, µ = 0.3376, σ = 10 -6 ) and we have computed the samples (S 117,M ) for M = (300 + 5j) j=0,...49 exactly as for Figure 2. We remark in Figure 6 (left) that the new method allows to detect and remove all the outlier. When we use it to glue the distribution of c i together we still have some outlier but far less than with the old method as it is shown in Figure 6 (right). These outlier are due to the fact that it may happen very rarely that δ(M, t 0 + iµ) and δ(M -λ, t 0 + iµ) are far enough so that we are wrong when using it to decide whether to choose c i or 1 -c i .

Continued fractions and ϵ-uniformity

In this section, we consider that the interval [0, 1[ is a circle by identifying 0 and 1. We say that T ⊂ [0, 1[ is an interval if ∪ t∈Z (T + t) is an interval of R. • η = T 1 /T 2 mod 1, λ a small integer;

• M and N integers.

output: Fail or c[i] which have the same distribution as D(M ).

1 i ← 0; 2 for i in range(n -M -N ) do 3 S i ← [i + 1, . . . , i + N ]; 4 c = P Si (b j ̸ = b j+M ); 5 c ′ = P Si (b j ̸ = b j+M -λ ) + ηλ; 6 C = [c, 1 -c]; 7 C ′ = [c ′ , 1 -c ′ ]; 8 Let (k, l) such that |C[k] -C ′ [l]| = min{|x -y|, x ∈ C, y ∈ C ′ }; 9 c[i] = C[k]; 10 end 11 return c[i];
We have seen in Section 2 that the outcome of Fact 1 can be affected by the choice of N . In order to have a better understanding of the relation between N and the precision of the computation of σ 2 by Fact 1, we recall some definitions and statements from [START_REF] Baudet | On the Security of Oscillator-Based Random Number Generators[END_REF].

| ♯K ∩ [a, b] ♯K -(b -a)| ≤ ϵ. (12)
In the following, for any K finite subset of [0, 1[, we denote by ϵ(K) the minimum of the set L = {ϵ > 0|K is ϵ-uniform} (such a minimum exists since L is closed and bounded from below by 0). For any i positive integer, we let

κ(i) = ϕ(t 0 + (i + M )µ) -ϕ(t 0 + iµ) mod 1 ∈ [0, 1[. We set S i = {i, . . . , i + N -1} for i = 1, . . . , n -N + 1 and for i = 1, . . . , n -N -M + 1, let K i = {κ(j), j ∈ S i }, E Si (κ) = 1 N j∈Si κ(j).
If we have a closer look at the statement of [3, Fact 1], we see that:

| 1 2 P Si {b j ̸ = b j+M } -min(E Si (κ), 1 -E Si (κ)| < ϵ(K i ).
In other words, the points that we compute in order to recover the distribution D(M ) are approximation up to ϵ(K i ) of the real points E Si (κ(i)) or 1 -E Si (κ(i)). We would like to choose N in order to obtain the smallest possible ϵ(K i ). A first question is: when K run through the set of finite subsets of cardinality N of [0, 1[, what is the span of ϵ(K) and for what configuration of K ϵ(K) is the smallest possible. This question is answered • η = T 1 /T 2 mod 1, λ a small integer;

• K, M and N integers.

output: c[i] which have the same distribution as D(M ). by the following lemma which explains that ϵ(K) is optimal when the points of K are uniformly distributed in [0, 1[. We state also the basic invariance of ϵ(K) with respect to translations.

1 for i = 0, . . . , K do 2 offset ← 0; 3 S i ← [N i + 1, . . . , N i + N ];
Lemma 1. Let K(N ) by a finite subset of [0, 1[ of cardinality N , we have:

• ϵ(K(N )) = ϵ(K(N ) + t) for any t ∈ R (invariance of ϵ(K(N )) by translation by t), ϵ(K(N )) < 1;

• if there exists ζ > 0 and

I an interval of [0, 1[ such that d(I) = ζ, I ∩ K(N ) = ∅ then ϵ(K(N )) ≥ ζ; • ϵ({i/N mod 1, i = 0, . . . , N -1}) = 1/N . If K(N ) has cardinality N then ϵ(K(N )) ∈ [1/N,
Using Equations ( 13) and ( 14), we obtain that ϵ(K) ≤ 1/N . If K has cardinality N then min({d(x, y), x, y ∈ K} ≥ 1/N so that ϵ(K) ≥ 1/N whence the last claim.

As N is small, considering that the phase jitter is small during N T 2 , we can suppose that ϕ(iη) = iη mod 1. So we have to study the ϵ-uniformity of the set K(N ) = {iη mod 1, i = 0, . . . , N -1}. A basic remark is that if η is a rational, write it as P/N an irreducible fraction then K(N ) = {i/N, i = 0, . . . , N -1} and we have seen in Lemma 1 that ϵ(K(N )) = 1/N and is minimal among all finite subsets of [0, 1[ of cardinality N . However in our application, for typical values, η will be a real number known up to precision say 10 -3 using for instance Fact 2 to compute η with a sample of 10 6 bits. So that η is of the from P/N with N of the order to 10 3 and we would like to choose N of the order to 10 2 so that N is small enough to comply with the hypothesis that the jitter during N T 2 is small. So we can not apply the preceding naive approach. But it seems reasonable to think that ϵ(K(N )) will be the smallest when we choose N so that there exists a good rational approximation P/N of η. These good approximations are given by the theory of continued fractions (first introduced in [START_REF] Lubicz | Towards an Oscillator Based TRNG with a Certified Entropy Rate[END_REF] in the context of jitter measurement of oscillator based TRNG). We briefly recall the classical results and notations that we use in the following and refer the reader to [START_REF] Ya | Continued fractions[END_REF] for a more in-depth introduction to continued fractions.

Let x be a real number, we denote by [a 0 , a 1 , . . .] where a 0 , a 1 , . . . are positive integers, the (possibly infinite) continued fraction representation of x that is:

x = a 0 + 1 a 1 + 1 a2+... . ( 15
)
If s = [a 0 ; a 1 , . . .] is a continued fraction and k a positive integer, we denote by s k = [a 0 ; a 1 , . . . , a k ] its k th segment of by s(p) k s(q) k its k th convergent. In other words, s(p) k s(q) k is the unique irreducible fraction representing [a 0 ; a 1 , . . . , a k ]. Let s ∞ be the real number represented by s. Denote by d(s, k) = s(q) k s ∞ -s(p) k and more generally by d(s, k, λ) = λd(s, k + 1) + d(s, k) for any λ ∈ {0, . . . , a k+2 } positive integer. We say, following [START_REF] Ya | Continued fractions[END_REF], that a/b a fraction with b > 0 is a best approximation of second kind of a real number α if for all λ/µ fraction such that λ/µ ̸ = a/b and 0 < µ < b, we have |bα -a| < |µα -λ|.

We have gathered in the following proposition the main results of the theory of continued fraction that we use:

Proposition 1 ([6]
). We have:

1. [START_REF] Ya | Continued fractions[END_REF][Theorem 4] for all k positive integer, (-1) k d(s, k) > 0 and the sequence

(-1) k (d(s, k)) k∈N is decreasing; 2. [6][Theorem 1]we have the relations s(p) k = a k s(p) k-1 +s(p) k-2 , s(q) k = a k s(q) k-1 + s(q) k-2
for all k ≥ 2;

3. [START_REF] Ya | Continued fractions[END_REF][Theorem 16] an irreducible fraction λ/µ is a best approximation of second kind of s ∞ if and only if λ/µ = s(p) k /s(q) k for a certain k.

It is clear that d(s, k, 0) = d(s, k) and by Proposition 1[2.], we have

d(s, k, a k+2 ) = d(s, k + 2). (16)
We need a slight generalisation of the definition of approxiamtion of second kind:

Definition 1. We say that a fraction a/b, b > 0 is a best positive (resp. negative) approximation of second kind of a real number α if for all λ/µ such that µ > 0, λ/µ ̸ = a/b, 0 < µ < b, we have 0 < bα -a < µα -λ (resp. bα -a > µα -λ > 0).

With this definition, we can state the following lemma which will be useful:

Lemma 2. Let s = [a 0 ; a 1 , . . .] be the continued fraction representation of s ∞ . We have:

• For all k, λ positive integer such that λ ∈ {0, . . . , a k+2 -1}, (-1) k d(s, k, λ) > 0;

• The fraction λ/µ, µ > 0 is a best positive (resp. negative) approxmation of second kind of s ∞ if and only if λ = λ 0 s(p) k+1 + s(p) k and µ = λ 0 s(q) k+1 + s(q) k for λ 0 ∈ {0, . . . , a k+2 } and k even (resp. odd).

Proof. For the first claim, it is true for λ = 0 by Proposition 1 since d(s, k, 0) = d(s, k) by definition. Next, we suppose in order to simplify the notations that k is even and leave the odd case to the reader. Suppose that for a λ ∈ {0, . . . , a k+2 -1}, we have d(s, k, λ) < 0. Let λ 0 be the smalest positive integer realizing this condition. Then 0 ∈]d(s, k, λ 0 + 1), d(s, k, λ 0 )[ and we have d(s, k, λ 0 + 1) -d(s, k, λ 0 ) = d(s, k + 1) < 0 by definition. This means that |d(s, k, λ 0 )| < |d(s, k + 1)| and s(q) k + λ 0 s(q) k+1 < s(q) k+2 . But this contradicts Proposition 1 saying the only the convergeants are best approximation of second kind. We prove the second claim, by induction on k. We suppose it to be true for all k ∈ {0, . . . , k 0 -1}, the case k 0 = 0 being trivial since s(q) 0 = 1. We do the induction in the case that k 0 is even the odd case being similar.

So we have to prove that for λ 0 ∈ {0, . . . , a k0+2 -1}, P (λ 0 )/Q(λ 0 ) for P (λ 0 ) = λ 0 s(p) k0+1 + s(p) k0 and Q(λ 0 ) = λ 0 s(q) k0+1 + s(q) k0 is a best positive approximation of second kind and that any best positive approximation of second kind is of this form.

We do an induction on λ 0 . For λ 0 = 0, the result is an immediate consequence of Proposition 1, because Q(0)s ∞ -P (0) > 0 and P (0)/Q(0) is a best approximaiton of second kind. We make the inductive hypothesis that for λ 0 < a k0+2 -1, P (λ 0 )/Q(λ 0 ) is a best positive approximation of second kind and we want to prove that P (λ 0 +1)/Q(λ 0 +1) is the only next one. We suppose the contrary and let λ/µ, µ > 0 be a rational such that

Q(λ 0 )s ∞ -P (λ 0 ) > µs ∞ -λ > 0, Q(λ 0 ) < µ < Q(λ 0 + 1). ( 17
)
Set λ 1 = λ -P (λ 0 ) and µ 1 = µ -Q(λ 0 ). Then by Equation ( 17) and using the fact that

d(s, k 0 ) > Q(λ 0 )s ∞ -P (λ 0 ) (because d(s, k 0 + 1) < 0), we have: 0 > µ 1 s ∞ - λ 1 > -s(d, k 0 ). Moreover, because of Equation (17), we have µ 1 < s(q) k0+1 so that by Proposition 1, 0 > s(d, k 0 + 1) > µ 1 s ∞ -λ 1 .
We can gather all the provious in the inequalities:

0 > s(d, k 0 + 1) > µ 1 s ∞ -λ 1 > -s(d, k 0 ). (18)
But, by the induction hypothesis for k 0 -1, we know that if λ 2 /µ 2 is a best negative approximation of second kind of s ∞ with µ 2 the biggest such that 0 < µ 2 < s(q) k0+1 , then µ 2 s ∞ -λ 2 = d(s, k 0 -1, a k0+1 -1) = d(s, k 0 + 1) -d(s, k 0 ) because of Equation ( 16). Comparing with Equation (18), we obtain:

0 > µ 1 s ∞ -λ 1 > µ 2 s ∞ -λ 2 . (19)
Recall that µ 1 < s(q) k0+1 , the Inequality (19) contractids the hypothesis that λ 2 /µ 2 is a best negative approximation of second kind of s ∞ with µ 2 the biggest such that µ 2 < s(q) k0+1 . We deduce that λ/µ verifying Equation (17) does not exists and so that P (λ 0 + 1)/Q(λ 0 + 1) is the only next best positive approximation of second kind of s ∞ after P (λ 0 )/Q(λ 0 ). Let η ∈ R and s = [a 0 ; a 1 , . . .] be its continued fraction representation so that s ∞ = η. Let N be a positive integer and i ∈ {0, N -1}. We consider the finite set K(N ) = {iη mod 1, i = 0, . . . , N -1} ⊂ [0, 1[. We suppose that the cardinal of K(N ) is N and we rank the elements of K(N ) by writing K(N ) = {κ j , j = 1, . . . , N -1} such that κ j ≤ κ j+1 for j = 0, . . . , N -2. Let χ be the permutation of {0, . . . , N -1} such that κ j = χ(j)η mod 1. Let s = [a 0 ; a 1 , . . .] be the continued fraction representation of s ∞ = η. Denote by D N the set of all d(s, k, λ), for k a positive integer and λ ∈ {0, . . . , a k -1} such that a k s(q) k-1 + s(q) k-2 ≤ N . It is clear from Proposition 1 that D N is finite. In order to compute ϵ((K(N )), we need to understand what are the quantities d(κ j+1 , κ j ). For this we denote by I = {d(κ j+1 , κ j ), j = 1, . . . , N -1}. We use the following Lemma : Lemma 3. For j ∈ {0, . . . N -1}, let D N j be the set of all d(s, k, λ) ∈ D N such that χ(j) + (-1) k (λs(q) k+1 + s(q) k ) ∈ {0, . . . , N -1}.

(20) Let d(s, k 0 , λ 0 ) be the smallest element of D N j . Then we have χ(j + 1) = χ(j) + (-1) k0 (λ 0 s(q) k0+1 + s(q) k0 ) and d(κ j+1 , κ j ) = (-1) k0 d(s, k 0 , λ 0 ).

Proof. Let µ = χ(j + 1) -χ(j). We remark that µ > 0 (resp. µ < 0) if and only if there exists λ such that λ/|µ| is the best positive (resp. negative) approximation of second kind of η with µ < N -χ(j) (resp. with µ + χ(j + 1) > 0). Actually, if µ > 0, let λ ′ /µ ′ be the best positive approximation of η with µ ′ < N -χ(j). If µ ′ ̸ = µ then 0 < ηµ ′ -λ ′ < ηµ -λ. But this means that χ(j)η mod 1 < (χ(j) + µ ′ )η mod 1 < χ(j + 1)η mod 1 (21) with χ(j) + µ ′ ∈ {0, . . . , N -1}. But this is a contracdiction with the definition of χ.

The negative case can be treated in the same manner.

Corollary 1. We let D N = {d i } with d i < d i+1 and denote by D N ≤i0 the set {d i , i ≤ i 0 } ⊂ D N . Let i 0 be the smallest index such that D N ≤i0 contains d(s, k 1 , λ 1 ), d(s, k 2 , λ 2 ) and such that:

1. (-1) k1 + (-1) k2 = 0; 2. |(λ 1 s(q) k1+1 + s(q) k1 ) + (λ 2 s(q) k2+1 + s(q) k2 )| ≤ N Then we have D N ≤i0 ⊃ I.

Proof. For j ∈ {0, . . . , N -1}, we have to prove that χ(j + 1) -χ(j) = (-1) k (λs(q) k+1 + s(q) k ) for d(s, k, λ) ∈ D N ≤i0 . But the two hypothesis of the Corollary ensure that there is d(s, k, λ) ∈ D N ≤i0 verifying (20) since χ(j) ∈ {0, . . . , N -1}. Thus D N ≤i0 contains the smallest d(s, k, λ) vérifying (20). By applying Lemma 3, we obtain the result.

As the distance between two points of K(N ) are elements of I ⊂ D N ≤i0 verifying the conditions of the previous Corollary, the set K(N ) is especially uniformly distributed in [0, 1[ when there exists such a D N ≤i0 with small cardinality. The following Corollary tells that, it has the smallest possible cardinality which is 2 when N is a convergent not equal to s ∞ (this last case is covered by Lemma 1).

Corollary 2. Suppose that N = s(q) k for k ≥ 2 and s ∞ ̸ = s(p) k /s(q) k . Then, D N ≤i0 = {d(s, k -2, λ), λ = 0, . . . , a k -1} and I = {|d(s, k -2)|, |d(s, k -2) + d(s, k)|}.
Proof. We apply Corollary 1 with d(s, k 1 , λ 1 ) = d(s, k -1, 0) and d(s, k 2 , λ 2 ) = d(s, k -2, a k -1). Using Proposition 1, we have that i=1,2 λ i s(q) ki-1 + s(q) ki-2 = s(q) k = N , by hypothesis and it is clear that (-1) k1 + (-1) k2 = 0.

Under the hpothesis of the Corollary it is easy to see that ϵ(K(s(q) k )) = d(s, k -2) + d(s, k).

Recall that η can be measured easily using the algorithm deduced from Fact 2. Then it is well known that the s = [a 0 ; a 1 , . . .] can be obtained with a sequence of Euclidean divisions as it is explained in Algorithm 4. From the continued fraction representation of η it is trivial to obtain the set of convergent with the recurrence formulas of Proposition 1. In the same way, in our first experiment of Section 3, we have considered an OJMD with paremeters (α = 0.5, µ = 0.3376, σ = 10 -3 ). The convergents of 0.6752 are [START_REF] Schindler | Evaluation Criteria for True (Physical) Random Number Generators Used in Cryptographic Applications[END_REF][START_REF] Schindler | Evaluation Criteria for True (Physical) Random Number Generators Used in Cryptographic Applications[END_REF][START_REF] Baudet | On the Security of Oscillator-Based Random Number Generators[END_REF]37,40,117,507] whence the choice of 117 in our computations. input :

• ζ ∈ R;
• n a positive integer.

output: s = [a 0 ; a 1 , . . . , a M ] the M th remainder of the continued fraction representation of ζ. If we get back to the example presented in Section 2 for the oscillator with parameters (α = 0.5, µ = 0.332, σ = 10 -3 ). If we compute the successive s(q) k for the continued fraction such that s ∞ = 0.664, we obtain [1, 1, 2, 3, 125, . . .] which explains according to the previous Corollary why the distribution of the {iµ mod 1, i = 1, . . . , N } looks more uniformly distributed in Figure 4 for N = 125 than for N = 80 and thus the discrepancy in the result of the measure when we choose N = 80.

5 Embedded implementation of the measure

Implementation

We have implemented and tested the algorithms of this paper on a FPGA XILINX ARTIX-7 (28nm HPL technology of TSMC). We have implemented 32 rings oscillator O i for i = 0, . . . , 31 of different length together with a fixed sampling ring oscillator O ech . A cell is implemented on the FPGA by a LUT. If the number n of cells is pair (resp. odd), the ring oscillator is made of n -1 inverters and one AND (resp. NAND) cell to cycle the electric signal and enable the ring. We obtain 32 OJMD denoted OJMD i for i = 0, . . . , 31, where OJMD i is made of the ring O i of mean period T i sampled by O ech for mean period T ech by the way of a type-D flip flop.

Constraints for positioning each element of the ring as well as bounds on time delay on the rings allow to control the reproducibility of the behaviour of the rings from an implementation to another. Note that we use a AND (or NAND) gate so that the ring is disabled when we set the configuration of the FPGA in order to avoid to have several clock edges per period. A double counter in implemented, one of them counting the edges of a clock the frequency of which is known and stabilized (for instance by a quartz) allows to measure the frequency of the rings.

An acquisition module is implemented on the FPGA. It allows to save 262 144 bits at the output of the each OJMD. These data are uploaded on a computer by the way of a UART link and saved in a file. We get 100 files for each OJMD. The experiments are done at ambient temperature and with the nominal voltage for the FPGA. For a complete characterisation of a oscillator based TRNG furthers experiments would be necessary to test the behavior each OJMD with respect to parameters which are known to have influence on its operation (supply voltage, temperature, electromagnetic environment, aging, technological dispersion).

The algorithms that we have implemented not only output the statistical parameters (α, µ, σ 2 ) of a OJMD but also curves providing information about the quality of the measures. Denote by T i (t) (resp. T ech (t)) the period of O i (resp. O ech ) at time t. Denote by (b i j ) the output bit sequence of OJMD i where the bit b i j is sampled at time t j . One can compute a good approximation of T ech (t j0 )/T i (t j0 ) mod 1 using Fact 2 by computing 1 2 P Sj 0 {b i ̸ = b i+1 } with S j0 = {b i j0 , . . . , b i j0+L } for L big enough so that one can compute the empirical probability P Sj 0 {b i ̸ = b i+1 } is small enough so that period of time between b i j0 and b i j0+L is short.

Transient phenomena

In Figure 7, we see the evolution of T ech (t)/T 0 (t) mod 1 when the acquisition of data begins just when O ech and O 0 are enabled. We note that T ech (t)/T 0 (t) mod 1 gradually slides down to a stable value. Our interpretation of the transient phenomenon is that when enabled the ring produce heat which increase the temperature locally on the silicon and thus modify the signal propagation time. This means that it is important to let some time passes between when we enable the OJMD and the acquisition time to let it stabilize. If one does not take this precaution, the variation of T ech (t)/T 0 (t) mod 1 can distort the measuring result and increase the estimation of the physical noise.

Experiments and results

The method of continued fraction of Section 4.2 is used in order to compute a value of N well suited so that S N,M gives a good approximation of the probability density function D(M ) for each acquisition file (Figure 8 for the OJMD 0 ). We compute V (S are normalized by 2.N so that they are in the interval [0, 0.5]. The Figure 9 shows V (S N,M ) as a function of M for a large span of M (from 0 to 1000). We note the quadratic shape of the curve due to flicker noises when M is big. This quadratic behavior is not visible on the simulated ring with only thermal noise.

In order to compute the slope of thermal component of the curve V (S N,M ), we use a span of accumulation time M where the effect of flicker noise seems to be negligible: with the condition M ≫ N , we can chose M in the interval [500, 700] with our settings. The Figure 10 represents the values of V (S N,M ) for M in the span [500, 700]. Only the squared points correspond to computed values and the lines between these points are interpolations. We remark that in this span the law of V (S N,M ) is nearly affine. The Figure 11 gives the centered distribution of the c i for M = 700. The general aspect of the law is Gaussian as expected and we not see any hint of a folding that we experienced in the simulations (see Section 3). We have furtherly checked this assumption by computing successive moments of the law and comparing them with that of a Gaussian law. The Figure 12 provides with the histogram of the values of σ 2 that is the slope of the affine law V (S N,M ) computed by linear interpolation. We note that the log normal distribution is Gaussian probably because of the flicker noise. We this dataset we obtain a most values of Q are around 2.16 10 -6 .

The Figure 13 gives the histogram of the values of Q the quality factor of a simulated OJMD. With this data set, we obtain a value of Q of 2.36 10 -6 for a Q injected in simulation of 2.39 10 -6 . In Figure 14, we see the values of Q for different OJMD. We find as expected that the value of Q is increasing with the frequency of the sampled oscillator.

The Figure 15 gives the value of T i and T ech for each OJMD. Some OJMD could not be characterized because the continued fraction method could not allow us to obtain a valid value of N .

Conclusion

In this paper, we have shown that the jitter measurement method of [] works at the condition that one choose correctly the two parameters M and N upon which it depends. Using simulations, we have highlighting the fact that bad choices of N and M produces outliers which affect the measure of the σ 2 parameter of the phase jitter. We have presented method that allows to choose correctly M and N which where not explained in [START_REF] Fischer | Embedded Evaluation of Randomness in Oscillator Based Elementary TRNG[END_REF] and tested the resulting algorithms with simulations.

Figure 1 :

 1 Figure 1: Scheme of an elementary OJMD

2 P

 2 12 return (b i ) i=1,...,n . Fact 1. [2, Fact 1] Under certain hypothesis the set: S N,M = {c i = 1 Si {b j ̸ = b j+M }} i∈{1,...,n-N -M +1} is a sample drawn following the probability density function D(M )(x) such that for all a, b ∈ R, b a

Figure 2 :

 2 Figure 2: V (S 117,M ) for M = (300 + 5j) j=0,...,49

Figure 3 :

 3 Figure 3: Distribution of values V (S 117,540 ) (left) and V (S 117,545 ) (right)

Figure 4 :Figure 5 :

 45 Figure 4: Example of distribution of values V (S 80,M ) (left) and V (S 15,M ) (right) for M = (300 + 5j) j=0,...,49

Figure 6 :

 6 Figure 6: V (S 117,M ) for M = (300 + 5j) j=0,...,49 discarding outliers (left) and by gluing distributions (right)

Algorithm 2 :•

 2 Algorithm to compute the probability density function D(M ) input : The output sequence [b 1 , . . . , b n ] of an OJMD;

  For x, y ∈ [0, 1[, let d(x, y) = min(|x -y|, 1 -|x -y|). If I is an interval of [0, 1[, we define the diameter of I denoted by d(I) the quantity max(d(x, y), x, y ∈ I). Let K be a finite subset of the interval [0, 1[, we say that K is ϵ-uniform if for all [a, b] ⊂ [0, 1], we have:

Algorithm 3 :•

 3 Algorithm to compute the probability density function D(M ) input : The output sequence [b 1 , . . . , b n ] of an OJMD;

4 c 5 c 6 ν

 456 = P S (b j ̸ = b j+M ); ′ = P S (b j ̸ = b j+M -λ ) + ηλ; ← {min(x, y) x ∈ {c, 1 -c}, y ∈ {c ′ , 1 -c ′ }}; 7 if ν -c[i -1] > 0.5 then 8 offset ← offset + 1; 9 end 10 if ν -c[i -1] < -0.5 then 11 offset ← offset -1; 12 end 13 c[i] = c + offset; 14 end 15 return c[i];

1 [

 1 and because of the preceding these bounds are optimal. Proof. The first two claims of the Lemma are clear. Let K = {i/N mod 1, i ∈ {0, . . . , N -1}. By applying the second claim to |0, 1/N [∩K = ∅, we have ϵ(K) ≥ 1/N . Let I ⊂ [0, 1[ be an interval, we have ⌊N d(I)⌋/N ≤ ♯(K ∩ I)/N ≤ ⌊(N d(I)⌋ + 1)/N (13) and moreover, ⌊N d(I)⌋/N ≤ d(I) ≤ ⌊N d(I)⌋/N + 1/N.

Algorithm 4 :

 4 Algorithm to compute the continued fraction representation of ζ.

1 x ← ζ; 2 s 4 x 0 ← ⌊x⌋; 5 r ← x -x 0 ; 6 s

 2456 ← []; 3 for i = 0, . . . , M do ← s + [x 0 ];

Figure 7 :

 7 Figure 7: Evolution of T ech (t)/T 0 (t) mod 1 at startup

Figure 8 :

 8 Figure 8: S N,M for OJMD 0 .

Figure 9 :

 9 Figure 9: V (S N,M ) as a function of M for a large span of M .

Figure 10 :

 10 Figure 10: V (S N,M ) as a function of M for M ∈ [500, 700].

Figure 11 :

 11 Figure 11: Distribution of c i for M = 700.

Figure 12 :

 12 Figure 12: Histrogram of values of Q for simulated dataset.

Figure 13 :

 13 Figure 13: Histrogram of values of Q.

Figure 14 :

 14 Figure 14: Values of Q for different OJMD.

Figure 15 :

 15 Figure 15: Values of T i and T ech for each OJMD.