Anh Thu

Phan Ho

Bao An

Hoang Mai

Wadih Sawaya

Patrick Bas

Document Authentication Using Graphical Codes: Reliable Performance Analysis and Channel Optimization

Patrick Bas and Dr. Wadih Sawaya, who have accepted to read my manuscript and will give me invaluable comment and advice, from which I believe that I would have not only a nice thesis but also progress in my future research.

Especially, I would like to use this opportunity to express my thanks to my PhD advisors, Dr. Patrick Bas and Dr. Wadih Sawaya, for supporting me during these past three years in my PhD life. I am thankful for their helpful guidance, endlessly constructive criticism and friendly advice. Without their help, I cannot imagine where I would be in my research. Pedagogically, carefully and patiently, they shared their experiences and illuminating views with me, put me in the right direction and taught me how to write a good scientic paper. Working with them was a great chance for learning and professional development.

I am sincerely grateful to my family who always give me unconditional love, constant encouragement and continuous support. If I didn't have them in my life, I would be sure that I cannot have chance to sit here and write these words of gratitude. Therefore, I would like to dedicate this thesis to my beloved family.

Last but not least, I also express my warm thanks to my colleagues Thi Le Thu Nguyen, Quoc Thong Nguyen and Anh Thu Phan Ho and all of my friends in France for every wonderful and unforgettable time that we have spent together. I especially thank to all nice people in Telecom Lille and Ecole Centrale de Lille whose appearance in my life made me feel happier and more joyful.

Bao An Mai Hoang

Liste des symboles

The list of notations and their interpretation: See below Books aren't written, they're rewritten. Including your own. It is one of the hardest things to accept, especially after the seventh rewrite hasn't quite done it...

Michael Crichton

1.1 Motivations.

Authentication of genuine goods is a problem which is nowadays more and more concerning in our Society. According to the news channel CNN [START_REF]Counterfeit goods becoming more dangerous[END_REF]: The global trade in counterfeit goods is booming, and it's shifting from relatively innocuous items like shoes and handbags to things like medicine and pesticides that can carry serious health and safety implications.

The economic impact of counterfeiting industry is also signicant. A report of The Organization for Economic Co-operation and Development (OECD) written in 2009 states that the prot from counterfeit goods was responsible for more than $250 billion in total prot of the world trade [START_REF]Counterfeiting and piracy endangers global economic recovery, say global congress leaders[END_REF][START_REF]Counterfeiting statistics[END_REF]. This amount can be compared with the prot of international trade in illegal drugs such as heroin, cocaine, methamphetamine or ecstasy,...and is even more important than other underworld economies such as weapons smuggling, money laundering and human tracking [START_REF]Counterfeit goods becoming more dangerous[END_REF].

According to other sources, the gures are dierent but still impressive: for example the Commercial Crime Services (CCS), a specialized division of the world business organization International Chamber of Commerce (ICC) declares that the prots of counterfeiting could reach an estimated $600 billion a year [1] on average and accounts for between 5 -7% of international trade around the world. For example, in 2008 CCS approximated counterfeit goods were worth up to $650 billion.

From the assessment of CCS, specialists of ICC state that the revenue of counterfeit goods across the world market could surpass $1.7 trillion and contribute over 2% of the world's total output by 2015 [START_REF]Counterfeit goods becoming more dangerous[END_REF]. It gives a huge prot for those who produce and distribute counterfeit goods but it's also a disaster for both the consumers and the current economy.

Several examples are presented below to show the aftermath of counterfeiting industry to the global consumers and world economy.

According to CNBC [START_REF]Counterfeit economy's impact on u.s rms and government[END_REF], among all counterfeit items imported to the United States in 2009, there was $260 million coming from clothing and accessories. Especially, in New York the counterfeit market beneted approximately $34 billion for imitations, robbing $1.6 billion in tax revenue. Disappointingly in the anti-counterfeiting ght, the results have been poor so far despite many eorts done by the governments and security companies. For example in 2002 the U.S Federal ocials only conscated $138 million knockos in which counterfeit clothing is the most popular product. This accounts 18% of all counterfeit items (see Fig. 1.1). As a matter of fact, this amount of money was much smaller than the revenue of counterfeit goods.

Figure 1.1: Growth in seizures of counterfeit goods by U.S. Taken from [START_REF]Counterfeit consumer goods[END_REF].

The problem of counterfeiting is even more worrying within the pharmaceutical industry: with $206.2 billion pharmaceutical sales in Europe per year the prots based on counterfeit products account for 16%, while in Asia this rate reaches 39% [START_REF]Counterfeit economy's impact on u.s rms and government[END_REF]. In 2005, the World Health Organization (WHO) reported that among the medicines produced in developing countries, there was nearly 25% of forgery [START_REF]Global congress addresses international counterfeits threat immediate action required to combat threat to[END_REF]. Interpol [START_REF]Pharmaceutical crime[END_REF] warned that such products nowadays are threatening public health at an international alert level and day by day the consumption of fake drugs, medicines and medical devices endangers the health and life of patients across the world, especially across developing countries.

Why?

According to Interpol [START_REF]Pharmaceutical crime[END_REF]: Illicit drugs can contain the wrong dose of active ingredient, or none at all, or a dierent ingredient. They are associated with a number of dangers and, at worst, can result in heart attack, coma or death . Also declared in [START_REF]Pharmaceutical crime[END_REF],

due to the growing of number of Internet users as well as untrusted sale-online web pages, patients can buy medicines easily, cheaply without prescription of the doctor and this fact makes the ght against counterfeit medicines even more dicult.

The Nato Oce on Drugs and Crime stated in a recent report titled Transnational Organized Crime in East Asia and the Pacic, in which there was nearly 70% of all counterfeits conscated coming from China in the period 2008-2010, while in U.S, according to the Customs, this percentage was 87% for the same period [START_REF]A mind-blowing number of counterfeit goods come from china[END_REF]. We can see in the chart 1.2 the ten countries with the most important seizure values of products violating the Intellectual Property Rights (IPR):

Figure 1.2: Ten largest contributors of value of IPR seizures, taken from [START_REF]Counterfeiting[END_REF].

In another report [START_REF]China piracy costs almost million jobs: Us study[END_REF], the U.S International Trade Commission investigated U.S businesses and they observed that there was approximately $48 billion lost by the infringement of IPR by China in 2009 (see Fig. 1.3).

We can see that the problem of counterfeit prevention and authentication of physical products such as documents, goods, drugs, jewels, ... becomes a major concern in a world of global exchanges, and one important task is to protect the legal manufacturers and consumers. This is the main motivation of the ANR Estampille project which is presented in the next section and with which this thesis is related. imported goods suspected of infringing intellectual property rights [START_REF]China piracy costs almost million jobs: Us study[END_REF].

The Estampille project

The general framework of the Estampille project is to ght against forged printed documents and counterfeited products by protecting their packages [START_REF]Secure printings using graphical codes[END_REF]. In order to do so, the project proposes to insert Graphical Codes (GC) on the document or the package of the commercial product (see an example of such a code in Figure 1.4). The use of GC in security framework enables both to perform integrity check of the printed document (detecting that a document has not been tempered) and to perform authentication (detecting which document is a counterfeit). In fact, CG have already been used by dierent companies, among which the company Advanced Track and Trace belongs to, on millions of commercial products in the pharmaceutical industry, cosmetics, wines and spirits, valuable documents and parts LGP2 (Laboratoire Génie des Procédés Papetiers) is a laboratory in university of Grenoble working on intelligent processes, materials chemistry, solid mechanics, mechanics of materials and printing processes.

LGP2 provides expertise about description and analysis of printing processes at the microscopic level.

LATA is an industrial company working on printing technologies. LATA provides expertise and Data from various printing processes. CERDI provides legal basis for the use of graphical code.

The authentication setup in Estampille

The general framework of Estampille project can be depicted in the Figure (1.5). We recall here the main step of the authentication process:

In step (1), we generate a simulated GC from a random source and model the legitimate printing channel to print this GC out, called printed original GC, then we insert it into the legal product in step [START_REF]Counterfeiting statistics[END_REF].

The opponent observes the printed original GC, and tries to process it in order to be able to print it by his printing channel in step (3) creating a reprinted forged GC.

He then inserts it into his illegal product in step [START_REF]Global congress addresses international counterfeits threat immediate action required to combat threat to[END_REF].

Both printed original and reprinted forged GC are observed by the receiver, and in order to detect the fake product, rstly the receiver has to process these GCs in step [START_REF]Counterfeiting and piracy endangers global economic recovery, say global congress leaders[END_REF] and then to perform the authentication test in step [START_REF]Fingerprinting blank paper using commodity scanners[END_REF]. Analysis and modeling of the printing processes from a physical and signal processing approaches.

Achieving global security of the authentication system.

Design of ecient GC for authentication.

The company ATT has developed the technology for making 2D GC in order to maximize the quantity of information lost by the forgers. This design is based on the fact that the printing process in the real environment comes from complex phenomena.

For example, it can be governed by the intrinsic features of the printers, the physical properties of the ink drop, the randomness of the paper's ber, etc... Viewed under a microscope, we can see in Figure (1.6), the surface of a sheet of paper is not perfectly at but is tangled. In fact, it is like a mixture of wood bers which is highly random and dicult to reproduce [START_REF] Clarkson | Fingerprinting blank paper using commodity scanners[END_REF]. Because of this randomness, a scanner will produce a dierent image depending on the orientation of the page and the printer will cause a stochastic non-invertible noise when conducting a printing process in the paper to print a GC out.

Randomness aects the authentic process and may degrade the accuracy of authentication performance. Consequently, the opponent can try to take advantage of this objective factor to entrap the detector (the receiver). It is consequently important Figure 1.6: An ordinary piece of paper viewed under a microscope [START_REF]Fingerprinting blank paper using commodity scanners[END_REF][START_REF] Clarkson | Fingerprinting blank paper using commodity scanners[END_REF].

to evaluate both the security and authentication performances of this complex system more accurately.

Our team in LAGIS proposes two directions of development to Estampille project:

1) the modeling of the printing processes as well as the characterization of the parameters for the printer and 2) the analysis of the authentication performances for dierent possible types of attacks that the opponent develop to forge the graphical codes and the impact of coding theory in authentication.

The rst direction is carried out by my colleague Quoc Thong Nguyen and his advisors Prof. Yves Delignon and Lionel Chagas. Their works mainly consist in characterizing the intrinsic features of the printer. Motivated from the microscopic analysis of paper printing, in [START_REF] Nguyen | Printer technology authentication from micrometric scan of a single printed dot[END_REF][START_REF] Thong | Printer identication from micro-metric scale printing[END_REF] Furthermore, they illustrate the benet of a such model and estimation algorithm in the case of authentication of printer from micro-tag made of one dot in [START_REF] Nguyen | Printer technology authentication from micrometric scan of a single printed dot[END_REF] and multiple dots in [START_REF] Thong | Printer identication from micro-metric scale printing[END_REF].

The second direction is mostly taken into account by my colleague Anh Thu Phan

Ho and me with our advisors Dr. Wadih Sawaya and Dr. Patrick Bas. While the work of Anh Thu is to consider the benet of information theory, channel coding and coding schemes for authentication, my researches focus on the use of signal processing, statistical estimation and hypothesis testing to improve authentication performance while guaranteeing security.

Sketch of the thesis

This thesis is a part of my researches that aims to answer the second direction of the Estampille project. We study an authentication system on a 2D GC, which will be presented in details within the next chapter, based on the fact that a printing process at very high resolution can be seen as a stochastic process. This is due to the nature of dierent elements such as the paper bers, the ink heterogeneity, or the dot addressability of the printer as mentioned above. Our solution to perform authentication is to use the hypothesis testing on the observed memoryless sequences of a printed GC, by considering the assumption that we are able to perfectly model the printing process [START_REF] Thu | Document authentication using graphical codes: impacts of the channel model[END_REF][START_REF] Thu | Document authentication using graphical codes: Reliable performance analysis and channel optimization[END_REF] and by deriving an optimal test for which the probabilities of error can be accurately approximated. Moreover, when looking for a more practical scenario, we take into account the estimation of the printing process used to generate the GC of the opponent and we see how it impacts the performance of authentication [START_REF] An | Image model and printed document authentication: A theoretical analysis[END_REF].

We also try to optimize the printing channel controlled by the legitimate manufacturers in order to maximize the ability of detecting a forged GC [START_REF] Thu | Document authentication using graphical codes: Reliable performance analysis and channel optimization[END_REF][START_REF] Thu | Authentication using graphical codes: Optimisation of the print and scan channels[END_REF].

The main context of the thesis begins with Chapter 2 in order to present the necessary theoretical backgrounds and state of the art for the thesis.

In Chapter 3, the theoretical analysis of the authentication test and associated error probabilities, together with numerical implementations are proposed.

In Chapter 4, security constraints are taken into account by the fact that the receiver tries to optimize of the parameters of the original printing channel while the adversary tries to optimize his own channel. This is modeled as a min-max game which is solved by using optimization tools.

The thesis is ended in Chapter 5 with the overall conclusions, the existing drawbacks and perspectives as well as the indication for the directions of future researches.

Publications related to the thesis

A part of works presented in this thesis has been published in one journal paper and three conferences papers: We can only see a short distance ahead, but we can see plenty there that needs to be done.

Alan Turing

In this chapter we presents two important aspects in mathematical statistics which are used in the entire thesis: Parameter estimation and hypothesis testing. They are essential and very useful in a vast area of research eld in signal processing. From the practical point of view, we have to use estimation theory in order to extract information about the printing channel and hypothesis testing to derive a test to perform authentication.

We also introduce some aspects of authentication, especially the authentication of printed objects, and we remind several advances in this eld and in modeling the printing-scanning process.

2.1 Fundamental backgrounds

Hypothesis testing for known parameters

In the entire thesis we dene Authentication as the problem of classifying between two groups: one contains authentic objects and the other contains inauthentic objects.

To solve it, it is common to use machine learning or hypothesis testing.

Hypothesis testing problem arises in many context (statistical signal processing, communication, life sciences, social sciences....) and is an active topic in statistics.

The primary task of hypothesis testing is to use observed data to take decisions by distinguishing the true hypothesis among the set of M surveyed hypotheses.

Classical binary hypothesis testing

We can consider two dierent testing approaches: classical and Bayesian hypothesis testing. The Bayesian approach considers that the prior distributions of the hypothesis are concerned while for other approach the prior distributions are assumed to be equiprobable.

Because it is dicult to gather information on the prior distribution, we focus our work on the classical binary hypothesis testing (see Fig. A type I error is equivalent to rejecting the null hypothesis H 0 while H 0 is true. In hypothesis testing, the probability of type I error α is often referred as the signicance level of the test or the probability of false alarm (P F A ). On the other hand, accepting H 0 when H 1 is true will cause a type II error whose probability β is often called the probability of type II error or probability of non-detection (P N D ). We dene the power of a test P D = 1 -β as the probability of rejecting H 0 while H 1 is indeed true. In hypothesis testing, it is desired to make α and β as small as possible. Nevertheless, there is an interplay between α and β and both cannot be negligible at the same time. It means that when α is increased, β decreases and vice versa. Hence we have to accept a trade-o between α and β, for example by using Receiver Operating Characteristic (ROC) curves which show the evolution of β (or power P D ) w.r.t α. A ROC curve has several important properties:

1. (α, β) moves continuously along the ROC curve.

2. All points on a ROC curve satisfy P D ≥ α.

An example of the ROC curves is shown in Fig. 2.3, in which we consider the null hypothesis H 0 : P (X| H 0 ) ≡ BSC(p) and alternative hypothesis H 1 : P (X| H 1 ) ≡ BSC(2p(1-p)) (BSC means the Binary Symmetric Channel with transition probability p), and we use Monte Carlo simulation to compute α and β.

In classical binary testing, the Neyman-Pearson theorem plays an essential role for getting an optimum decision rule. This theorem states that the optimum decision rule that minimizes β for a given α (see in [START_REF] Erich | Testing statistical hypotheses[END_REF]) is given by comparing the likelihood ratio between the two hypothesis with a threshold. We recall it below:

Neyman-Pearson theorem : Suppose we have random variables x N distributed by an unknown probability density in a sample space in X ⊆ R N . Among all the procedures applied to x N to test if the distribution of x N comes from the hypothesis H 0 : θ = θ 0 or H 1 θ = θ 1 , the likelihood-ratio test between H 0 and H 1 with a threshold λ satisfying:

Λ(x) = L(θ 1 | x N , H 1 ) L(θ 0 | x N , H 0 ) H 1 ≷ H 0 λ
is the most powerful test of a signicance level α given by P r [Λ(x) > λ | H 0 ]. Thus, β or the probability of non-detection

P N D is dened as P r [Λ(x) < λ | H 1 ]. Herein, L(θ i | x N , H i )
is likelihood function based on hypothesis H i (i = 0, 1) and the most powerful test means the test with the largest power (1-β) for a given signicant level α.

If the logarithm of the likelihood ratio is used, the test is known as a log-likelihood ratio test (LLR test).

The optimum solution coming from the Neyman-Pearson problem requires to select the threshold λ to obtain the smallest possible β while keeping α ≤ α * , α * is xed. The ROC curve is then used to analyse the performances of the test for dierent thresholds and the area under the curve (AUC):

ˆ1 0 βdα, can be used to measure its average performance.

If now we want to apply hypothesis testing using the LLR test for authentication, we assume that the receiver observes an unknown i.i.d sequence v N = (v 1 , v 2 , ..., v N ) of length N in the observation space V N . In order to perform authentication he assumes that H 0 is the hypothesis that v N comes from the legitimate source with probability distribution Q 0 while H 1 is the hypothesis that v N is sent by the opponent with probability distribution Q 1 , then the receiver can use the LLR test between H 0 and H 1 to map the N dimensional problem into a one dimensional problem (see also Fig. 2.4):

L R = log Q 1 v N H 1 Q 0 (v N | H 0 ) H 1 ≷ H 0 λ. (2.1)
If two densities Q 0 and Q 1 are known, the probability of type I and type II error are given by:

α = ´+∞ λ P L R |H 0 (l)dl β = ´λ -∞ P L R |H 1 (l)dl. (2.2)
Here, in Fig. 2.4, we dene:

H 0 = v N ∈ V ⊆ R N : L R (v N ) < λ (2.3) and H 0 = {L R ∈ R : L R < λ} .
(2.4) Figure 2.4: Classical (non-Bayesian) binary hypothesis testing using LLR test.

For example, a signal sequence v = (v 1 , v 2 , . . . , v n ) with {v i } n 1 is n i.i.d random variables is sent to the receiver. We assume that the receiver knows that v i is only distributed by Q 0 ∼ N (µ 1 , σ 2 ) or Q 1 ∼ N (µ 2 , σ 2 ), and he has to determine where x comes from by considering a test:

H 0 : v i ∼ N (µ 1 , σ 2 ), H 1 : v i ∼ N (µ 2 , σ 2 ),
where µ 1 , µ 2 > 0. The receiver can use an LLR test given in this case by:

L R (v) = log Q 1 (v n | H 1 ) Q 0 (v n | H 0 ) = 1 (2πσ 2 ) n/2 e -1 2σ 2 n i=1 (v i -µ 2 ) 2 1 (2πσ 2 ) n/2 e -1 2σ 2 n i=1 (v i -µ 1 ) 2 H 1 ≷ H 0 λ. (2.5) It leads to n i=1 v i H 1 ≷ H 0 σ 2 µ 2 -µ 1 log(λ) + n 2 (µ 2 + µ 1 ) ≡ ζ.
(2.6)

The probability of type I error is given by:

α = P r n i=1 v i > ζ | H 0 = Q ζ -nµ 1 σ √ n . (2.7)
and probability of type II error is given by:

β = P r n i=1 v i < ζ | H 1 = 1 -Q ζ -nµ 2 σ √ n .
(2.8)

where Q(x) is error function. In this particular case, we can rewrite β as the function of α as follow:

β = 1 -Q Q -1 (α) + √ n µ 1 -µ 2 σ .
(2.9)

However, generally it is dicult to compute α and β because the densities of P L R |H 1 (l) and P L R |H 0 (l) are unknown and both the probability of error and the likelihoods have to be approximated numerically. In this case, because of the approximations and the numerical computation, the test is not optimal anymore.

Asymptotic properties of LLR test

In order to derive asymptotic properties for the LLR, if we set

q k = log Q 1 ( v k |H 1 ) Q 0 ( v k |H 0 )
and

S N = 1 N Σ N k=1 q k .
From strong law of large number, when N → +∞, we consequently have:

H 0 : S N a.s → E [q k | H 0 ] = ´log Q 1 ( x|H 1 ) Q 0 ( x|H 0 ) Q 0 (x| H 0 ) dx, H 1 : S N a.s → E [q k | H 1 ] = ´log Q 1 ( x|H 1 ) Q 0 ( x|H 0 ) Q 1 (x| H 1 ) dx.
(2.10)

It is equivalent to write, using D KL (P Q) = ´P (x) log P (x) Q(x) dx the Kullback -Leibler divergence between two densities P (x) and Q(x), that:

H 0 : S N a.s → -D KL (Q 0 Q 1 ) , H 1 : S N a.s → D KL (Q 1 Q 0 ) . (2.11)
Therefore as long as we can collect an arbitrarily large number of i.i.d observations, we can separate perfectly H 0 and H 1 (Q 0 and Q 1 are completely dierent).

If one of the probabilities of error goes to zero arbitrarily slowly, the Stein's lemma [START_REF] Thomas | Elements of information theory 2nd edition[END_REF] provides the best exponent bound to minimize the other probability of error. It means that when α is very close to zero then

1 N lim N →∞ log β = -D KL (Q 0 Q 1 ) , (2.12)
or similarly when β tends to zero, it gives

1 N lim N →∞ log α = -D KL (Q 1 Q 0 ) . (2.13)
However, in a realistic manner, the Stein's lemma cannot be considered as an approximation of the probabilities of error due to the fact that N is limited and every practical detector has to cope with a value of α or β that may be small but not very close to zero.

Uniformly Most Powerful Test

In statistics, the classical binary hypothesis testing (or NP-test) based on likelihood ratio test statistic can be seen as a specic case of a more general testing problem called the uniformly most powerful test (UMP test) which can be used to test between simple hypothesis H 0 : θ ∈ Θ 0 and

H 1 : θ ∈ Θ 1 with Θ 0 ∪ Θ 1 = Θ and Θ 0 ∩ Θ 1 = ∅.
sup θ∈Θ 0 E θ [T * (X)] = α * , (2.14)
if for any other test statistic T (x) of size α such that:

sup θ∈Θ 0 E θ [T (X)] = α ≤ α * , (2.15)
we always suer a loss in power, i.e.,

E θ [T (X)] ≤ E θ [T * (X)] ∀θ ∈ Θ 1 .
(2.16)

An UMP test in general does not always exist. For example, we can let X ∼ Binom(n, θ) and suppose we want to test:

H 0 : θ = θ 0 v.s H 1 : θ = θ 0 (2.17)
at some level α. There is no UMP test in this case [START_REF] Erich | Testing statistical hypotheses[END_REF].

However when the test exists, it can be found by two methods. The rst one comes from Neyman-Pearson theorem as we have stated above. The second method, used in case of scalar parameter and based on the concept of monotone likelihood ratio, can be understood as an extension of Neyman-Pearson theorem and it is called Karlin-Rubin theorem [START_REF] Karlin | The theory of decision procedures for distributions with monotone likelihood ratio[END_REF].

Another diculty with the optimality in NP-test or UMP test (if it exists) is that the density of the population must be assumed to be known, except for a nite number of parameters. This assumption makes the testing problem easier to solve, but in the real scenario it will rarely be true.

Hypothesis testing for unknown parameters

As we know from the previous subsection, the main requirement for a NP-test of an

observed sequence v N H 0 : v N i.i.d ∼ f 0 (x| θ 0 ) θ 0 ∈ Θ 0 H 1 : v N i.i.d ∼ f 1 (x| θ 1 ) θ 1 ∈ Θ 1 (2.18)
is the knowledge of the underlying distributions f 0 (x| θ 0 ) and f 1 (x| θ 1 ) as well as the specic parameters θ 0 and θ 1 , where

Θ 0 ∪ Θ 1 = Θ Θ 0 ∩ Θ 1 = ∅ (2.19)
However, in a realistic situation we do not know exactly the densities of f 0 and f 1 as well as the true parameters θ 0 and θ 1 . In this case, we can use a generalized likelihood ratio test (GLRT).

The GLRT is a general procedure for composite testing problems. The fundamental idea is to compare the maximum likelihood of the model in class H 1 to the maximum likelihood of the model in class H 0 . The test statistic based on the observation v N is

Λ(v N ) = sup θ 1 ∈Θ 1 L(θ 1 | v N , H 1 ) sup θ 0 ∈Θ 0 L(θ 0 | v N , H 0 ) H 1 ≷ H 0 λ, (2.20) or equivalently log Λ(v N ) H 1 ≷ H 0 λ. (2.21)
It can be supposed in practice that the null hypothesis H 0 is completely known, i.e. θ 0 is xed, the expression can be written as

Λ(v N ) = sup θ 1 ∈Θ 1 L(θ 1 | v N , H 1 ) L(θ 0 | v N , H 0 ) H 1 ≷ H 0 λ. (2.22)
If we want to perform a GLRT, we have to solve rst with a maximum likelihood estimation (MLE) problem (which will be discussed more clearly in the next subsection) because the test statistics log Λ(v N ) cannot be expressed explicitly unless we estimate θ i (i = 1, 2). Instead, if we nd θi which maximizes the corresponding likelihood

L(θ i | v N , H i ), i.e.,

θi = argmax

θ i ∈Θ i L(θ i | v N , H i ), (2.23)
then we may write

Λ(v N ) = L( θ1 | v N , H 1 ) L( θ0 | v N , H 0 ) H 1 ≷ H 0 λ. (2.24)
The quantity θi is called the restricted maximum likelihood estimate of θ i under H i .

Although the law of Λ(v N ) is unknown, the following theorem hopefully unveils the method to approximate the threshold given a signicance level α.

Wilks's theorem : [START_REF] Samuel | The large-sample distribution of the likelihood ratio for testing composite hypotheses[END_REF] Let θ 0 = (θ 0,1 , θ 0,2 , ..., θ 0,m ) ∈ Θ 0 ⊂ R m be a vector of parameters of a density family p(x | θ 0 ) in which θ 0,1 , ..., θ 0,l ∈ R are free parameters that need to be estimated using MLE, and θ 0,l+1 = t l+1 , ..., θ 0,m = t m are xed at the real values t l+1 , ..., t m . Assume that p(x | θ 1 ) is a density family parametrized by θ 1 ∈ Θ 1 ⊂ R m with θ 1 includes all free parameters. Consider a composite testing problem

H 0 : v N i.i.d ∼ p (x| θ 0 ) H 1 : v N i.i.d ∼ p (x| θ 1 ) (2.25)
where the parametric density has the same form in each hypothesis. If the 1 st and 2 nd order derivatives of p(x | θ i ) w.r.t θ i exist, then the test statistic

Ŵ (v N ) = sup θ 1 ∈Θ 1 p v N θ 1 sup θ 0 ∈Θ 0 p (v N | θ 0 ) H 1 ≷ H 0 λ, (2.26)
has the following asymptotic distribution when H 0 is true and the sample size N → ∞

2 log Ŵ (v N ) d → χ 2 m-l .
(2.27)

Thus, for large N α = Pr χ 2 m-l (x) ≥ 2 log(λ) H 0 .

(2.28)

Sometimes it is easy to compute only one of the true parameters θ0 or θ1 but dicult or impossible to compute the other one. This motivates the birth of two other tests that are asymptotically equivalent to the Wilks test. The rst one is the Rao test [START_REF] De | Coincidence of the rao test, wald test, and glrt in partially homogeneous environment[END_REF] with test statistic:

R(v N ) = ∇L( θ0 | v N , H 0 ) T J -1 N ( θ0 ) ∇L( θ0 | v N , H 0 ) , (2.29)
where

J N (θ) = -∇ 2 L(θ | v N , H 0 ), (2.30)
is the observed Fisher information matrix for sample size N . The Rao test statistic is asymptotically equivalent to the Wilks test statistic in the order o p (1) under the same conditions for Wilks's theorem, i.e.,

R(v

N ) = Ŵ (v N ) + o p (1).
(2.31)

The most important property of Rao test is that the test statistic depends only on the MLE for the null hypothesis H 0 .

The second one is Wald test [START_REF] De | Coincidence of the rao test, wald test, and glrt in partially homogeneous environment[END_REF][START_REF] David | Notes and comments wald criteria for jointly testing equality and inequality[END_REF] with test statistic is

Û (v N ) = g( θ1 ) T ∇g( θ1 )J -1 N ( θ1 ) ∇g( θ1 ) T -1 g( θ1 ), (2.32)
where g : R N → R N is a constrain function on the set of θ 0 such that g(θ 0 ) = 0. Firstly, most of GLRT fails in obtaining optimality [START_REF] Fan | Generalized likelihood ratio statistics and wilks phenomenon[END_REF][START_REF] Zeitouni | When is the generalized likelihood ratio test optimal? Information Theory[END_REF].

The second important point is that even if we accept a arbitrarily large sample size, when α is very small, i.e. when the threshold is far from the means (it can happen for a highly accurate detector), the calculation of the tail probability of chi-squared distribution may be incorrect [START_REF] Dembo | Large deviations techniques and applications[END_REF].

The asymptotic property of the test statistic only occurs in case when the parametric density has the same form in each hypothesis.

Moreover we need also to compute the asymptotic distribution of the test statistic when the alternative hypothesis happens in order to approximate the probability of type II error β.

This is why another approach proposed to overcome these drawbacks is discussed in the main content of Chapter 3 and Chapter 4.

Parameter estimation

When the receiver observes two GCs how could he certies that a GC is original or is forged? A proposed solution is to use statistical decision to perform authentication.

In our scenario, we assume that the physical process that generate the original GC is known while the other one used by the opponent is dierent and unknown. From the previous subsection, we know that one way for the receiver to perform authentication is rstly to estimate the generating process of the GC and secondly to use hypothesis testing.

This section presents consequently the theoretical background related to parameter estimation.

Parameter estimation is a branch of statistics in which the parameters, describing the whole underlying physical setting of a population, are supposed to be unknown and need to be estimated based on empirical measured data that are supposed to be outcomes of random variables. Although our proposed analysis does not depend on the estimation method, we consider mostly in this thesis Maximum Likelihood Estimation in order to achieve optimal estimation.

Maximum likelihood estimation

Given a statistical model, Maximum Likelihood Estimation (MLE) relates to a popular class of methods in statistical estimation that use sample of empirical data to estimate the model's parameters [START_REF] Fw Scholz | Maximum likelihood estimation[END_REF]. The aim of MLE is to nd an estimated parameter θ, given the sample x, that maximizes the likelihood function L(θ | x).

We consider a n-length sample x = (x 1 , x 2 , ..., x n ) of n i.i.d observations coming from a distribution in which its density function f (x| θ) is supposed to belong to a certain parametric family indexed by the unknown parameters θ ∈ Θ ⊂ R m , called the parametric model. The likelihood of the whole sample is dened as the product of the individual likelihoods: Let us denote H m (θ) the Hessian matrix of the log-likelihood with respect to the parameters:

L(θ | x) = n i=1 L(θ | x i ), = n i=1 f (x i | θ).
H m (θ) = ∂ 2 L(θ) ∂θ i ∂θ j i,j=1,..,m , (2.36)
and let I m (θ) be the Fisher information matrix [START_REF] Efron | Assessing the accuracy of the maximum likelihood estimator: Observed versus expected sher information[END_REF] dened as:

I m (θ) = E ∂L(θ) ∂θ 2 θ = -E f (x|θ) [H m (θ)] , (2.37)
where E f (x|θ) or simply E θ is the expectation taken w.r.t f (x | θ).

From the Cramer-Rao theorem [START_REF] Louis | Statistical signal processing[END_REF] for a large sample size, it can be stated that the covariance matrix of any unbiased ML estimator θ of a parameter θ 0 satises:

Cov( θ) I -1 m (θ 0 ). (2.38)
Since θML is an unbiased estimator, we have:

Cov( θML ) I -1 m (θ 0 ), (2.39)
i.e., the covariance of a unbiased ML estimator can be approximated by the inverse of the Fisher information matrix at the true parameters θ 0 , and θML is an estimator yielding the smallest variance. The asymptotic distribution of θML is then given by: θML asym ∼ N (θ, I -1 m (θ 0 )).

(2.40)

The normality of θML helps us to provide a measure of how the estimated parameters spread w.r.t the true value. The quadratic form of the error (the variation of the estimation) is chi-squared distributed:

ρ( θML ) = θML -θ 0 T Cov -1 ( θML ) θML -θ 0 asym ∼ χ 2 κ , (2.41)
or equivalently

ρ( θML ) = θML -θ 0 T I m (θ) θML -θ 0 asym ∼ χ 2 κ , (2.42)
where χ 2 κ is the chi-squared distribution with κ degree of freedom. Here, κ is the number of free parameters that govern the proposed model. One may observe that ρ( θML ) = cte is an ellipsoid in the κ-dimensional space. In practice, the true parameters are always unknown, hence the Fisher information need to be estimated, for example by the observed Fisher information matrix [START_REF] Efron | Assessing the accuracy of the maximum likelihood estimator: Observed versus expected sher information[END_REF][START_REF] Thomas | Finding the observed information matrix when using the em algorithm[END_REF] at θ = θML

J m ( θML ) = -H m ( θML ) = -∂ 2 L(θ)
∂θ i ∂θ j θ= θML .

(2.43)

Another important property of MLE is the invariant property, i.e. if g is a continuous function w.r.t θ, then η M L = g( θML ) is a ML estimator of η = g(θ). Thenceforth, rather than estimating directly a parameter θ, we can rst estimate some function g(θ) using MLE and then recover an estimate of θ from g(θ).

Expectation Maximization

The Expectation Maximization (EM) algorithm [START_REF] Arthur P Dempster | Maximum likelihood from incomplete data via the em algorithm[END_REF][START_REF] Mclachlan | The EM algorithm and extensions[END_REF][START_REF] Je | A gentle tutorial of the em algorithm and its application to parameter estimation for gaussian mixture and hidden markov models[END_REF] is an iterative method for nding maximum likelihood in cases where the equations in a MLE problem cannot be solved directly. Suppose that we have a given statistical model with a set of observation

x N , a set of unobserved latent or missing data u N , and a vector of unknown parameters θ. The EM algorithm is used to nd a ML estimator for θ by iteratively applying two steps:

1. The Expectation step (E step) computes the expected value of the log likelihood function w.r.t the conditional distribution of U N given X N and the estimate θ (t) of the parameters θ at iteration (t):

Q(θ| θ (t) ) = E U N |X N ,θ (t) L θ| x N , u N . (2.44)
2. The Maximization steps (M step) nds the estimated parameters at iteration (t + 1) that maximizes this quantity:

θ (t+1) = argmax θ Q(θ| θ (t) ).
(2.45)

The algorithm repeats these two steps and assigns, at each iteration T , the estimated θ = θ (T ) of θ until convergence.

In some certain cases, it is more convenient to express EM algorithm under an alternative form. Let us denote

F (q, θ) = E g L θ| x N , u N + H(q), = -D KL q p U N |X N u N x N , θ + L θ| x N , (2.46)
where p U N |X N u N x N , θ is the conditional distribution of the unobserved or missing data u N given the observation x N ; q is an arbitrary probability density over u N and H is the entropy function of q. Then the EM algorithm can be reformulated by the two following steps:

1. Expectation step: select q satisfying q (t) = argmax q F (q, θ (t) ).

(2.47) 2. Maximization step: choose θ satisfying θ (t+1) = argmax θ F (q (t) , θ).

(2.48)

It should be noted that an EM algorithm only yields to a local solution for the estimation, so that it requires an initialization value that is close enough to the true model's parameters to run the algorithm and to insure the convergence of the algorithm.

The EM algorithm has very large applications in many research directions. It can be used for data clustering in data mining [START_REF] Celeux | A classication em algorithm for clustering and two stochastic versions[END_REF][START_REF] Anil K Jain | Data clustering: a review[END_REF][START_REF] Georey | Mixture models. inference and applications to clustering[END_REF][START_REF] Nigam | Text classication from labeled and unlabeled documents using em[END_REF], in signal processing [START_REF] Feder | Parameter estimation of superimposed signals using the em algorithm[END_REF], in computer vision [START_REF] Thomas | A survey of computer vision-based human motion capture[END_REF] or even psychology and social researches [START_REF] Paul D Allison | Missing data: Quantitative applications in the social sciences[END_REF][START_REF] Bock | Marginal maximum likelihood estimation of item parameters: Application of an em algorithm[END_REF], etc. One of the most important application of EM algorithm is to t the mixtures of distributions by using what we might call pseudo missing data [START_REF] Ghahramani | The em algorithm for mixtures of factor analyzers[END_REF][START_REF] Mclachlan | Finite mixture models[END_REF][START_REF] Muthén | Finite mixture modeling with mixture outcomes using the em algorithm[END_REF], i.e. the data that we never obtain but they can be considered as missing in order to facilitate the computation of ML estimators.

In chapter 4, we propose a modication of the EM algorithm for a mixture of truncated Gaussian distributions. This algorithm is used to estimated the parameters of the opponent channel.

Previous works related to authentication of GC

In this section, we present the connections between this thesis and previous works that: have the same general goals of authenticating items, use directly Graphical Codes to perform authentication, use the same methodology, i.e. hypothesis testing, for security related applications, are related with modeling the print and scan channel.

Overview of authentication processes

Authentication processes are used in a lot of dierent elds, often related to computer sciences, such as: Access control on a network/intelligent systems to check the authority of the right users [START_REF] Ravi | Access control: principle and practice[END_REF][START_REF] David | Role-based access controls[END_REF]. Password protection based on RSA system [START_REF] Denning | Digital signatures with rsa and other public-key cryptosystems[END_REF][START_REF] Elgamal | A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF], considered as a digital signature. It is used, for example, to access to bank accounts.

Authentication between objects based on the interaction between all objects which are belongs to the same user [START_REF] Eberhard | Method for authentication between two electronic devices[END_REF][START_REF] Frincke | Developing secure objects[END_REF].

Digital image authentication based on watermarking. Note that image authentication in this case is related to the problem of integrity check and not to authentication per se since a digital plain copy is always authentic. One examples for this approach can be found, for instance in Ho et al [START_REF] Anthony Ts Ho | Image content authentication using pinned sine transform[END_REF].

Authentication of physical materials where the goal is to distinguish genuine products from forged ones. This approach is extremely active nowadays due to the explosion of counterfeiting industry.

The following section proposes more examples of this last application.

Authentication of physical products

As introduced briey in Chapter 1, the authentication of physical products can generally be obtained by using the stochastic structure of either the materials that compose the product or the stochasticity of a physical process that is associated to the generation of the product.

Authentication of physical objects can be for example performed by recording the random patterns of the ber of a paper: in [START_REF] Haist | Optical detection of random features for high security applications[END_REF], the authors combine the optical detection method with recorded digital signatures based on public key codes in order to protect not only banknotes but also credit-and chip-cards, checks, contracts, etc., against counterfeiting. The general idea, depicted in Fig. 2.5, is separated into two parts:

1. Protection: the image is detected then compressed and a digital signature is attached. The result is encoded.

2. Verication: the ber structure of the banknote to be veried is extracted and then compared with the ber structure of the original object stored in a available database. The authors claim that they can obtain a high security without using any expensive production techniques due to the fact that the complicated features, used for verication, are already included in the object. Instead of using random features of objects, they can also detect, code and store the characteristics such as ngerprints, speech, faces... of those who are authorized to access the objects. However, such a system is practically heavy to deploy since each product needs to be linked to its high denition capture stored in a database.

Another solution is to rely on the degradation induced by the interaction between the product and a physical process such as printing, marking, embossing, carving ... Because of both the defaults of the physical process and the stochastic nature of the matter, this interaction can be considered as a Physically Unclonable Function (PUF) [START_REF] Suh | Physical unclonable functions for device authentication and secret key generation[END_REF] that cannot be reproduced by the forger and can consequently be used to perform authentication. According to [START_REF] Suh | Physical unclonable functions for device authentication and secret key generation[END_REF], rigorously a PUF is dened as a random assignment that maps a set of challenges to a set of responses based on an intractably complex physical system. The authors indicate that PUF can be originally described as a innovative circuit primitives that enable signicantly higher physical security with low-cost authentication of individual integrated circuits (ICs) by deriving secrets from complex physical characteristics of ICs rather than storing them in non-volatile digital memory.

According to Fig. 2.6, an authentic device A includes the pairs Challenges-Response stored in the database of A for future authentication operations. To check the authenticity of an unknown device, rstly a challenge that had been recorded but has never been used is selected, and the corresponding response is obtained by PUF. This response is then compared with the one already stored in the database of A for authentication.

Connections with authentication using GC

It is important to note that the Integrated Circuits presented above act in a similar way than the features characterizing the physical printing process in this thesis. The particularity of our system is the fact that this mapping may be understood as a one time PUF or a physical unclonable process because it can be called only once for each object. There are no challenge-response processes in this case but the authentication still relies on a physical unclonable process.

A similar example to our problem can be found in [START_REF] Shariati | Random proles of laser marks[END_REF]. The authors propose another marking technique, called Laser-written PUF or simply LPUF, in order to characterize the random proles of laser marks on materials such as metals. From a technological achievement of TOMO3D project [15], LPUF is generated based on 3-D prole of laser marks using a diameter of 60µm and carved on the surface of a physical object.

They also provide an anti-counterfeiting system based on LPUF and use them for authentication. This scheme is split in two parts:

1. The registration is executed once on the object before it is released to the market.

2. The verication can be executed whenever someone wants to check whether the product is a genuine one or not.

Their approach can be used to protect small objects or to be linked with other authentication methods.

The unclonable process can also be represented solely by the interaction between paper and ink. In [START_REF] Matthew D Gaubatz | Distortion metrics for predicting authentication functionality of printed security deterrents[END_REF], the authors measure the degradation of the inks within printed color-tiles, and use the discrepancy between the statistics of the authentic and printand-scan tiles to perform authentication. They try to estimate whether a printed impediment will authenticate without imploring the actual authentication process. Several algorithms are also proposed to predict the result of the authentication process. The used AOC (area over the curve) statistic shows that there are two metrics, called noreference metric and full-reference metric respectively, which are particularly useful for estimating authentication performance in the existence of distortions caused via dierent choices of print-and-scan systems. Surprisingly, by using AOC, they show that a no-reference metric gives the best performance for authentication. Another eective authentication system has been proposed by Picard et al. [START_REF] Picard | Towards fraud-proof id documents using multiple data hiding technologies and biometrics[END_REF][START_REF] Picard | Improved techniques for detecting, analyzing, and using visible authentication patterns, july 28 2005[END_REF] and uses 2D pseudo random binary codes that are printed at the native resolution of the printer (2400 dpi on a standard oset printer or 812 dpi on a digital HP Indigo printer). It is important to notice that this system is very similar to the one that will be studied in the next chapter.

At the authentication step, in order to perform authentication the receiver computes a test on the observed scanned code, being either the scanned version of the original printed code or the scanned version of the reprinted forged code.

One advantage of this system over previously cited ones is that it is easy to deploy since the authentication process needs only a scan of the graphical code under scrutiny and the seed used to generate the original one: no ngerprint database is required in this case.

Security analyses

The security of this system relies on the fact that the opponent is not able to accurately estimate the original binary code due to solely relying on the use of a PUF. Dierent security analysis have already been performed w.r.t. this authentication system, or to very similar ones.

The authors have studied in [START_REF] Baras | 2d bar-codes for authentication: A security approach[END_REF] the impact of multiple printed observations of the same graphical codes and the authors have shown that the inuence of the noise due to the printing process can be reduced in this particular setup, but not completely removed. Here, the authors consider a batch attack where the product manufacturer (Bob) generates a batch of printed GCs coming from the same original code. Eve can access a number N c of printed versions of a genuine 2D-GC and tries to estimate the original one. The goal of Eve is to convince the receiver that her reproduced GC is a genuine one. This paper shows also that the original code cannot be totally removed even with a large number of observations, which leaves room for secure authentication even under batch attacks.

In [START_REF] Emir | Copy detection pattern-based document protection for variable media[END_REF], a print and scan model is proposed to be adapted to graphical code and a smart attack based on the model is analyzed to show that it can be used to corrupt the eectiveness of authentication (precisely authentication using GC). To handle this type of attack, the authors propose four new detection metrics which are sensitive to print-scan distortions. Through experimental analysis, they show that their proposed features can be employed to improve signicantly the authentication accuracy.

In [START_REF] Mouhamadou L Diong | Document authentication using 2D codes: Maximizing the decoding performance using statistical inference[END_REF], the authors propose to study the security of authentication considering GCs by using machine learning techniques in order to extract the original code from an observation of the printed code. Their results show that the estimation accuracy can be improved without recovering perfectly the original code. A black box strategy is employed to analyze the security. They propose to use a set of observations and try to invert the printing system by inferring a linear classier based on these observations. In [START_REF] Beekhof | Content authentication and identication under informed attacks[END_REF], the considered security analysis is quite similar to the setup of passive ngerprinting using binary ngerprints, which is similar to binary GCs, under informed attacks (the channel between the original code and the copied code is assumed to be a BSC). In this case, the security is shown to increase w.r.t the code length and the authors propose a practical threshold when type I error (original detected as a forgery) and type II error (forgery detected as an original) are equal. A information-theoretic analysis is also derived based on the assumption of the code length.

Hypothesis testing in authentication and forensics

A lot of research papers related to hypothesis testing and information security have been written over last several decades. In this thesis, we deal with authentication considering hypothesis testing technique for detecting the genuineness of products.

Although hypothesis testing is a classical methodology, it is still very eective in many application researches of authentication and forensic. For instance, in [START_REF] Thai | Camera model identication based on the heteroscedastic noise model[END_REF], the fundamental idea is also the use of hypothesis testing, albeit the authors deal with the identication of camera models. They are successful to design a camera model considering only two camera parameters (a, b). They then develop an estimation of these parameters based on the weighted least squares estimation. A binary statistical test based on GLRT is developed to analyze the performance of identication problem using heteroscedastic noise which is stated to describe more precisely the acquisition noise of a natural raw image. Numerical experiments are carried out based on both simulated and real images taken from Nikon D70 and Nikon D200 show that The performance of proposed tests depends on the discriminability of camera parameters (a, b).

Only a small number of pixels is required to achieve a perfect detection performance which proves the sharpness of the tests.

The authors claim that their proposed method is the only one which employs raw images to identify camera model. However, because the main limitation is that raw images may not be available in practice, they consider to extend their approach to other image formats that are related to the post-acquisition and compression processes.

Hypothesis testing is also used in steganalysis, a branch in computer sciences used to detect hidden information in the cover media such as image, audio, video, etc,.. using steganography. In [START_REF] Zitzmann | Statistical decision methods in hidden information detection[END_REF], the authors propose to use the classical binary hypothesis testing and show how it is useful for detecting hidden information. Both simple and composite hypothesis testing schemes based on likelihood ratio tests are used to analyze the performance of hidden information detection. Their approach is strictly based on the parametric statistical model of the media object. Both theoretical and numerical results show not only the impact of observation quantization on the probabilities of type I and type II error but also the benets of using statistical decision on hidden information detection.

In [START_REF] Ueli | Authentication theory and hypothesis testing. Information Theory[END_REF], the authors propose to interpret message authentication as a hypothesis testing problem coming from an information-theoretic point of view based on the concept of discrimination whose expression is related to mutual information in channel coding theory [START_REF] Blahut | Hypothesis testing and information theory. Information Theory[END_REF]. They provide a generalized scheme to evaluate the information-theoretic lower bounds on an opponent's probability of fooling the receiver by forging one of the messages in the sequence shared between sender and receiver. Two types of cheating, impersonation and substitution attacks, are analyzed and lower bounds on cheating probability are also obtained for any authentication system.

Printing-scanning models

Because the principle of our authentication system relies on the degradation induced by the print and scan process, we draw here an overview of the dierent works in this domain.

We recall rst a list of the most important printing techniques (see Fig. 2

.7 for examples of each type)

Oset printing in which the inked image is spread on a metal plate then transferred to a surface of rubber blanket and nally pressed to the paper (see in [START_REF] Kipphan | Handbook of print media: technologies and production methods[END_REF]).

Laser printing [START_REF] Kipphan | Handbook of print media: technologies and production methods[END_REF] in which the printer uses a laser beam to carve an image on a charged drum. The drum is then rolled through a reservoir of ink. The ink is then transferred to the paper using a combination of heat and pressure.

Inkjet printing in which the printer spray droplets of ionized ink on a paper. A inkjet printer can print at a moderately high resolution (300 dots per inch or more). Because of both its outstanding properties and low cost, inkjet printing nowadays is used widely as a printing tool [START_REF] Singh | Inkjet printing process and its applications[END_REF]. As a matter of fact, the printed images are always degraded by the sequence of printing, scanning, copying,... Even if the humans eyes cannot distinguish the dierence between the printed images and the digital, the quality of printed images can be evaluated using text recognition systems [START_REF] Henry | The state of the art of document image degradation modelling[END_REF] because the microscopic view contains more details that can be used to measure the quality of the printed image. Many methods are consequently based on observations from a microscope to estimate the parameters of the printer.

From the aspect of modeling, in [START_REF] Norris | Printer modeling for document imaging[END_REF] the authors propose to use a probabilistic model to generate the images having the toner location (the toner is a special ink used in laser printing technology) that is similar with the one of actual printed images. Using a so called geometric probability described by measuring the area lled by toner and its complementary area, they can develop a deterministic model to describe the average amount of paper to be covered by toner. Simulations show that the results of their model t well with the average coverage of printed images.

Another feature which needs to be modeled is the ink spreading, a phenomenon of dot gain that produces high color deviations in ink jet printing. In [START_REF] Emmel | Modeling ink spreading for color prediction[END_REF], the authors propose a new model of ink spreading by extending the drop impact w.r.t the shape of its neighbors and the condition of the surface to improve the prediction of the reection spectra of halftoned samples printed on various inkjet printers. By using Pólya's counting theory in combinatorics, they can reduce the number of all possible ink drop congurations to a signicantly small number of cases. For instance, in a three-inkcolor printing, they show that only 30 important cases must be considered instead of

3 × 4 6 = 12288 cases.
Printer modeling can be also carried out using purely the techniques from signal processing [START_REF] Vongkunghae | A printer model using signal processing techniques[END_REF] in which a signal processing model is proposed to model multi-level halftoning and resolution enhancement, as well as traditional halftoning.

Recently, in [START_REF] Nguyen | Printer technology authentication from micrometric scan of a single printed dot[END_REF][START_REF] Thong | Printer identication from micro-metric scale printing[END_REF], using statistical signal processing techniques, the authors provide a model for the scanning and printing process through a binary response scheme based on the shape and the location of the ink dots. They also develop an algorithm called maximum likelihood unsupervised identication to show the accuracy of printing process at the microscopic scale. The algorithm's performance is evaluated through simulation using the true data collected by microscope of various types of papers and printing modes.

Conclusions of Chapter 2

This chapter has presented elements of the theoretical background needed in order to conduct this thesis. Hypothesis testing will be used in the next chapter to derive authentication test, and its combination with parameter estimation in chapter 4 to evaluate the impact of estimation on authentication.

The related works also show that this thesis is connected to multiple domains: authentication schemes, physical unclonable functions, forensics and printing modeling.

The dierent security analyses presented here are also connected to the one presented in chapter 5. Essentially, all models are wrong, but some are useful.

George E. P. Box

The goal of this chapter is rst to present an authentication system for GC that relies on hypothesis testing, and then to provide accurate computations of the error probabilities of this system. The authentication system is dened in the rst section of this chapter, then the print and scan model is presented. We afterwards present two possible strategies for the receivers, which consist in thresholding or not the observed code before applying the hypothesis test and we show that the authentication is more performant without thresholding. Finally we end this chapter by presenting reliable computations of the errors probabilities for this setup. These computations are based on an asymptotic expression and they will be further extended in the next chapter to take into account the estimation of the opponent channel.

The authentication system

As stated in Chapter 1 with the general framework described in Figure 1.5, we focus here on the authentication aspect of the GC , so that the principle of the studied system in this thesis can be depicted more accurately by The opponent's goal is then to reproduce a printed and scanned code similar to the original printed one using a printer that will also generate a non-invertible noise.

In the whole of thesis the authentication model involves two channels X → (Y, Z), we dene the main channel as the channel between the original source and the receiver, while the opponent channel as the channel between the original source and the receiver but passing through the counterfeiter (or opponent) channel (see in Fig. 3.1). The authentication system works as follow: A binary graphical code can be considered as an authentication sequence x N chosen randomly from the message set X N (X N mostly is {0, 1} N ) by the legitimate sender and shared secretly with the legitimate receiver. In our authentication model, x N is published as a noisy version y N , taking values in the set of points V N , modeling the original printed and scanned graphical code (see Fig. 3.2 on the left). An opponent may observe y N and, naturally, tries to retrieve the original authentication sequence using his skills in data estimation. After his processing, he obtains an estimated sequence xN which is supposed practically to be dierent from the original x N (see [START_REF]Counterfeiting statistics[END_REF] in Fig. 3.1). He then prints it using his printing process to create a forged observable noisy image z N taking values in the same set of points V N . He publishes z N hoping that it will be accepted by the receiver as coming from the original source (see Fig. 3.2 on the right). The observed images y N and z N are 8 bits grey level images. In practice, this attack will be used to create false documents or fake packages that could be considered as authentic.

The whole physical process, precisely printing and scanning devices used by the legitimate parts (see (1) in Fig. 3.1) and by the counterfeiter (see [START_REF]Pharmaceutical crime[END_REF] in Fig. 3.1), are respectively modeled by probability distributions conditioned to the original data P Y |X,θ and P Z|X, θ in which θ and θ are set of parameters, taken in Θ, specifying the devices in each case.

When observing a sequence v N , which may be one of the two possible sequences y N or z N , the detector has to determine whether this observed sequence comes from the legitimate source or not (see [START_REF]Counterfeiting and piracy endangers global economic recovery, say global congress leaders[END_REF] in Fig. 3.1) supposed that the models P Y |X,θ is known.

The print and scan process in this particular setup for example can be modeled by an AWGN channel or an additive i.i.d. lognormal noise as in [START_REF] Baras | Towards a realistic channel model for security analysis of authentication using graphical codes[END_REF].

As mentioned before, our authentication is based on NP-test in which the receiver considers two hypothesis H 0 and H 1 . The former hypothesis attests authenticity, i.e. that the received sequence is generated by P Y |X,θ and the latter one unveils a fake code, i.e. that the observed sequence is driven from P Z|X, θ. Performances are evaluated via computing accurately the probability of type I error and the probability of type II error.

Proposed models for print and scan

The two channels X → (Y, Z) are considered being discrete and memoryless with conditional probability distribution P Y Z|X,θ, θ( y z| x, θ, θ). The marginal main and opponent channels P Y |X,θ (y| x, θ) and P Z|X, θ( z| x, θ) are dened by the transition probability matrices of the main channel and the opponent channel, respectively.

Let T V |X,θ be the generic transition matrix modeling the printing and scanning devices. The entries of this matrix are conditional probabilities T V |X,θ (v| x, θ) or simply T V |X (v| x) relating an input alphabet X and the output alphabet V. In practice, X is a digital value, i.e., a binary alphabet standing for black bit (0) and white bit (1), and the channel output set V stands for the set of grey level values in the set {0, 1, ..., 255}.

The marginal distribution of the main channel P Y |X,θ is equivalent to one print and scan process, represents a grey level distribution of the authentic image conditioned to the knowledge of both the authentication dots and the parameters governing the legitimate print and scan process. On the other hand, P Z|X, θ depends on the opponent processing while he tries to recover the original sequence X N by the estimated sequence XN before reprinting it, hoping that Pr( XN = X N ) = ε with ε > 0 is arbitrarily small. Practically, when performing a detection to obtain an estimated sequence XN , the opponent always undergoes errors coming from the realistic fact that he is not able to infer the original code. It is important to note that the opponent will have to print a binary version of its observation because an industrial printer at this very high resolution can only print binary images. These errors yield to the probability P e,W for the confusion between an original white dot with a black one and to the probabilityP e,B for the confusion between an original black dot with a white one. This distinction is due to the fact that the distribution T V |X,θ of the physical devices is arbitrary and not necessarily symmetric. Let D W be the optimal decision region for guessed white dots using thresholding:

D W = v ∈ V : P Y |X,θ (v| x = 1, θ) > P Y |X,θ (v| x = 0, θ) , (3.1)
and D c W is the complementary region in the set V. Error probabilities P e,B and P e,W are then equal to

P e,B = v∈D W P Y |X,θ (v| x = 0, θ), (3.2)
and

P e,W = v∈D c W P Y |X,θ (v| x = 1, θ). (3.3)
The channel X N → XN can be modeled as a binary input binary output (BIBO) channel with transition probability matrix P X|X :

P X|X ( x = 0| x = 0) P X|X ( x = 1| x = 0) P X|X ( x = 0| x = 1) P X|X ( x = 1| x = 1) = 1 -P e,B P e,B P e,W 1 -P e,W (3.4)
As depicted in Fig. 3.1, because the opponent channel X N → Z N is a physically degraded version of the main channel, X N → XN → Z N forms a Markov chain with the relation P X Z|X ( x z| x) = P X|X ( x| x)T Z| X (z| x) where T Z| X ≡ T Z| X, θ is the transition matrix of the counterfeiter physical device. Therefore, given P Z|X, θ a grey level distribution of the forged image conditioned to the knowledge of both the authentication dots and the parameters governing opponent print and scan process, we have:

P Z|X, θ( Z = v| X = 0, θ)
= (1 -P e,B )P Z| X, θ( v| X = 0, θ) + P e,B P Z| X, θ( v| X = 1, θ),

and

P Z|X, θ( Z = v| X = 1, θ) = (1 -P e,W )P Z| X, θ( v| X = 1, θ) + P e,W P Z| X, θ( v| X = 0, θ). (3.6)
Without loss of generality, a generalized symmetric exponential family (or generalized Gaussian distributions) can be used to model the physical device in our analysis, i.e., the association of a printer with a scanner, used by the legitimate source T Y |X (v| x) and by the opponent T Z| X (v| x) which may be expressed as follow:

p(v| x) = b 2aΓ(1/b) e -( |v-µ(x)| a ) b (3.7)
where µ(x) is the mean and the parameter a can be derived from the variance σ 2 = Var(V ) by using below formula

a = σΓ(1/b)Γ(3/b). (3.8)
The parameter b is used to control the sparsity of the distribution, for example, when b = 1 the distribution is Laplacian, b = 2 the distribution is Gaussian, and b → +∞ the distribution is uniform. The resulting distributions P Y |X,θ and P Z|X, θ are rst discretized then truncated to provide values within the nite set [0, 1, ..., 255] to model a reasonable scanning process. Each channel is dened by four parameters, two per each type of dots, µ b = µ(0) and σ b for black dots and µ w = µ(1) and σ w for white dots. Another choice to model the print and scan channel, mentioned in [START_REF] Baras | Towards a realistic channel model for security analysis of authentication using graphical codes[END_REF], is the use of Lognormal distribution:

p(v | x) = 1 vs(x) √ 2π e - (log v-µ(x)) 2 2s 2 (x) (3.9)
with the mode of the distribution is dened as M = e µ(x)-s 2 (x) , and the variance is given by σ 2 = e s 2 (x) -1 e 2µ(x)+s 2 (x) . In our case, the Lognormal distribution can be parametrized by the standard deviations σ b , σ w and the modes M b , M w respectively for black and white dots. Note that other print and scan models that deal with the gamma transfer function or additive noise with input dependent variance can be found in [START_REF] Lin | Distortion modeling and invariant extraction for digital image print-and-scan process[END_REF], but the general methodology considered in this thesis is not dependent on the model and can still be applied.

Receiver strategies

In this subsection we introduce the testing strategies to check whether, for a given

xed codeword (x 1 , ..., x N ) in {0, 1} N , an observed i.i.d sequence (o 1 , ..., o N | x 1 , ..., x N ) (with (o i | x i ) belonging to a discrete nite set V) is generated from a given distribution P Y |X,
θ of the main channel or if it comes from an alternative hypothesis associated to distribution P Z|X, θ of the opponent channel. Generally, we are interested in performing authentication after observing a sequence of N samples (o i | x i ) checking whether this sequence comes from a original source or from a counterfeiter. Similar to the example presented in subsection (2.1.1), the strategy of receiver is to establish a decision based on binary testing problems between two hypothesis H 0 and H 1 corresponding respectively to each of the former cases. As a matter of fact, the sample space V N will be partitioned into two regions H 0 and H 1 and it leads to two kinds of errors as being introduced from the previous chapter: type I error with occurred probability α and type II error with occurred probability β. According to Neyman-Pearson theorem, under the constraint α ≤ α * , β is minimized if and only if the following log-likelihood test deduces the choice of H 1 :

L = log P Z N |X N , θ o N x N , H 1 P Y N |X N ,θ (o N | x N , H 0 ) ≥ λ (3.10)
where λ is a threshold verifying the constraint α ≤ α * .

However, the test statistic (3.10) is just a general expression while in practice, the receiver does not know exactly the true parameters θ related to the print and scan process of the opponent or even the distribution P Z|X, θ of this process. Therefore, the receiver who want to perform authentication can use two possible strategies:

Firstly, it is assumed that he does not know anything about P Z|X, θ, in this case the receiver can use a threshold to count the number of errors between y N and x N or z N andx N respectively. He can after build a test based on the distributions of the number of errors in y N and z N to perform authentication. We call this strategy authentication via binary thresholding.

Secondly, if the underlying distribution P Z|X, θ is known or may be guessed, the receiver can use the knowledge of the true parameters θ to establish a test statistic (see subsection 2.1.2) . This strategy is called authentication via grey level observations (see section 3.3.2).

The last scenario is indeed similar with the second strategy but in the case where the receiver has to rst estimate the opponent channel parameters before designing the authentication test. The impact of the estimation of these parameters on the performance of the authentication system is detailed in the next chapter.

Authentication via binary thresholding

The legitimate receiver rst observes sequence o N and uses a threshold based on the main channel marginal distribution P Y |X,θ to restore a binary version xN , called the decoded sequence of the original message x N using the same decision region as dened by (3.1), which naturally generates errors.

In the main channel, i.e., when O N = Y N , error probabilities are equivalent to Pe,W = (1 -P e,W )P e,W + P e,W (1 -P e,B )

(3.13)
For this rst strategy, the opponent channel may be viewed as the cascade of two binary input/binary output channels:

1 -Pe,B Pe,B Pe,W 1 -Pe,W = 1 -P e
x N . Let N B = {i : x i = 0} and N W = {i : x i = 1} with N B = |N B |, N W = |N W | and N = N B + N W .
From the property of i.i.d sequences we have:

P xN x N , H j = N i=1 P ( xi | x i , H j ) = i∈N B P ( xi | 0, H j ) × i∈N W P ( xi | 1, H j ) (3.15)
Particularly,

Under hypothesis H 0 , the channel X → X has distribution given by (3.2) and

(3.3) and we have:

P xN x N , H 0 = (P e,B ) n e,B (1 -P e,B ) N B -n e,B × (P e,W ) n e,W (1 -P e,W ) N W -n e,W , (3.16)
where n e,B and n e,W are the number of error (x i = x i ) when black is decoded into white and when white is decoded into black respectively.

Under hypothesis H 1 , the channel X → X has distribution given by (3.12) and (3.13) and we have:

P xN x N , H 1 = Pe,B n e,B 1 -Pe,B N B -n e,B × Pe,W n e,W 1 -Pe,W N W -n e,W , (3.17)
Applying now the Neyman-Pearson decision (3.10) the test is expressed as:

L 1 = log P ( xN |x N ,H 1) P ( xN |x N ,H 0 ) H 1 ≷ H 0 λ (3.18)
or

L 1 = n e,B log ( Pe,B( 1-P e,B )) (Pe,B(1-Pe,B)) + n e,W log ( Pe,W (1-Pe,W )) (Pe,W (1-Pe,W )) H 1 ≷ H 0 λ 1 , (3.19)
where

λ 1 = λ -N B log (1-Pe,B) (1-Pe,B) -N W log (1-Pe,W ) (1-Pe,W )
. This expression has the practical advantage to only count the number of errors in order to perform the authentication task but at a cost of a loss of optimality.

Authentication via grey level observations

In the second strategy, the receiver performs his test directly on the received sequence o N without using any given threshold or decoding. We will see in the next subsection (3.4) that this strategy is better than the previous one. Here again, the conditional

distribution of each random component (O i | x i ) of the random i.i.d sequence (O N | x N )
is the same for each type of data of X. The Neyman-Pearson test is expressed as:

L 2 = log P (o N |x N ,H 1) P ( o N |x N ,H 0 ) H 1 ≷ H 0 λ 2 , (3.20)
which can be developed as

L 2 = i∈N B log P Z|X, θ (o i |0) P Y |X,θ (o i |0) + i∈N W log P Z|X, θ (o i |1) P Y |X,θ (o i |1) H 1 ≷ H 0 λ 2 , (3.21)
or more specically,

L 2 = i∈N B log (1 -P e,W ) T Z| X, θ (o i |0) T Y |X,θ (o i |0) + P e,W T Z| X, θ (o i |1) T Y |X,θ (o i |0) + i∈N W log (1 -P e,B ) T Z| X, θ (o i |1) T Y |X,θ (o i |1) + P e,B T Z| X, θ (o i |0) T Y |X,θ (o i |1) H 1 ≷ H 0 λ 2 . (3.22)
Note that the expressions of the transition matrix modeling the physical processes T Y |X,θ and T Z| X, θ are required in order to perform the optimal test, i.e., the receiver needs to know or to estimate the print and scan processes of the opponent.

Comparison between the two strategies

For this comparison and without loss of generality, we consider only the Gaussian model with variance σ 2 for the physical devices T Y |X,θ and T Z| X, θ. and we compare the receiver operating characteristic (ROC) curves associated with the two dierent strategies. Note that the error probabilities are computed using the results given in the next subsection (see 3.4). We can notice that the gap between the two strategies is signicant in the variation of magnitude. This is not surprising since the binary thresholding removes information from the gray-level observation, yet this has a practical impact because one practitioner can be tempted to count the number of errors as given in (3.19) as an authentication score for its easy implementation or in case when he cannot estimate the opponent channel. The information theoretical analysis presented in [START_REF] Thu | Document authentication using graphical codes: Reliable performance analysis and channel optimization[END_REF] conrms also that authentication is more accurate without thresholding.

Reliable computation for error probabilities

In the previous subsection we have expressed explicitly the Neyman-Pearson test for the two proposed receiver's strategies summarized by (3.19) and (3.20). These tests may then be practically performed on the observed sequence of size N coming from an observed GC in order to decide about its authenticity. We aim now at expressing the error probabilities of types I and II and comparing the authentication performance of two possible strategies described previously. It should be reminded that throughout the thesis we deal with discrete case for the main and the opponent densities although the results can be extended to the continuous case. So if we let m = 1, 2 be the index denoting the strategy, a straightforward calculation gives exactly

α m = l>λm P Lm (l | H 0 ) (3.23) β m = l<λm P Lm (l | H 1 ) (3.24)
where P Lm (l | H j ) is the density of the log-likelihood ratio L m under hypothesis H j .

Gaussian approximation

As the length N of the sequence is generally large enough, we commonly use the central limit theorem (CLT) to approximate the distributions P Lm , m = 1, 2 (a similar strategy was considered in [START_REF] Picard | Digital authentication with copy-detection patterns[END_REF]).

For

L 2 = i∈N B l(o i | 0) + i∈N W l(o i | 1) H 1 ≷ H 0 λ 2 , (3.26)
where l(v | t) is a function l : V | X → R having a distribution with mean and variance respectively equal to:

µ x = E [l(V | x) | H j ] = v∈V l(v | x)P (v | x, H j ), (3.27)
and

σ 2 x = Var [l(V | x) | H j ] = v∈V (l(v | x) -µ x ) 2 P (v | x, H j ), (3.28)
with P = P Y |X (respectively P = P Z|X ) for j = 0 (respectively 1). The CLT can then be used again to approximate the distribution of L 2 and compute type I and type II error probabilities.

Asymptotic expression

In this part, for the shake of simplicity we drop the subscript m denoting the strategy as all the subsequent analysis is common for both of them.

One important problem is the fact that the Gaussian approximation proposed previously provides inaccurate error probability values when the threshold λ in (3.23) and (3.24) is far from the mean of the log-likelihood random variable L. Instead Cherno bound and large deviation theory [START_REF] Dembo | Large deviations techniques and applications[END_REF] can be employed in this context as very small error probabilities of types I and II may be desired [START_REF] Robert | Information theory and reliable communication[END_REF]. Given a real number s, the Cherno bound on type I and type II errors may be expressed as:

α = Pr (L ≥ λ | H 0 ) ≤ e -sλ g L (s | H 0 ) for any s > 0, (3.29)
β = Pr (L ≤ λ | H 1 ) ≤ e -sλ g L (s | H 1 ) for any s < 0, (3.30)
where the function g L (s | H j ), j = 0, 1 is the moment generating function of L dened as:

g L (s | H j ) = E P L (L|H j ) e sL , (3.31)
and the expectation is calculated w.r.

t distribution P L (L | H j ).
Because L is a sum of N independent random variables, asymptotic analysis in probability theory (when N is large enough) shows that bounds similar to (3.29) and (3.30) are much more appropriate for estimating α and β than the Gaussian approximation especially when λ is far from E[L], namely when bounding the tails of a distribution [START_REF] Dembo | Large deviations techniques and applications[END_REF][START_REF] Robert | Information theory and reliable communication[END_REF]. The tightest bound is obtained by nding the value of s that provides the minimum of the right hand side (RHS) of (3.29) and (3.30), i.e. for the minimum of e -sλ g L (s | H j ) for each j = 0, 1. Taking the derivative, the value s that provides the tightest bound under each hypothesis is such that

1 : λ = dg L (s|H j ) ds g L (s|H j ) s=s j = d ds log g L (s | H j ) s=s j = d ds µ L (s | H j ) s=s j (3.32)
where

1 one can show that e -sλ g L (s | H j ) is a convex function of s µ L (s | H j ) = log g L (s | H j ), (3.33)
is the semi-invariant moment generating function or cumulant generating function. This function has many interesting properties that ease the extraction of an asymptotic expression for (3.29) and (3.30) [START_REF] Robert | Information theory and reliable communication[END_REF]. For instance, this function is additive for the sum of independent random variables, and we have

µ L (s | H j ) = i∈N B µ i|0 (s | H j ) + i∈N W µ i|1 (s | H j ) (3.34)
where µ i|x (s | H j ) is the cumulant generating function of the random variable l(O i | x) when the observed sequence comes from the distribution associated to hypothesis H j .

Additionally, the relation (3.32) may be interpreted as the sum of the derivatives at the value s j optimizing the bounds of α and β as:

λ = i∈N B µ i|0 (s j | H j ) + i∈N W µ i|1 (s j | H j ). (3.35)
The Cherno bounds on α and β in (3.29) and (3.30) may thus be expressed as:

α = Pr (L ≥ λ | H 0 ) ≤ exp i∈N B µ i|0 (s 0 | H 0 ) -s 0 µ i|0 (s 0 | H 0 ) + i∈N W µ i|1 (s 0 | H 0 ) -s 0 µ i|1 (s 0 | H 0 ) . (3.36)
and

β = Pr (L ≤ λ | H 1 ) ≤ exp i∈N B µ i|0 (s 1 | H 1 ) -s 1 µ i|0 (s 1 | H 1 ) + i∈N W µ i|1 (s 1 | H 1 ) -s 1 µ i|1 (s 1 | H 1 ) . (3.37)
From our assumption, the distribution of each random component

(O i | x i ) in the i.i.d sequence (O N | x N )
exp [N B (µ 0 (s j | H j ) -s j µ 0 (s j | H j )) + N W (µ 1 (s j | H j ) -s j µ 1 (s j | H j ))] . (3.38)
Roughly speaking, Cramér's theorem [START_REF] Dembo | Large deviations techniques and applications[END_REF] states that for suciently large N , the upper bounds expressed for j = 0, 1 in (3.38) are also lower bounds for α and β respectively. Thus without loss of generality, one can suppose that N B = N W = N/2; we have then:

lim N →∞ 2 N log α = [µ(s 0 | H 0 ) -s 0 µ (s 0 | H 0 )] , (3.39) lim N →∞ 2 N log β = [µ(s 1 | H 1 ) -s 1 µ (s 1 | H 1 )] , (3.40)
where s 0 > 0,

s 1 < 0, µ(s j | H j ) = µ 0 (s j | H j ) + µ 1 (s j | H j ) and µ (s j | H j ) = µ 0 (s j | H j )+µ 1 (s j | H j ).
One can show also that s 1 = s 0 -1. A modied asymptotic expression including a correction factor is evaluated for the sum of an i.i.d random sequence (see [START_REF] Robert | Information theory and reliable communication[END_REF], Appendix 5A), and for large N we have:

α = Pr(L ≥ λ | H 0 ) → N →∞ 1 |s 0 | √ N πµ (s 0 |H 0 ) exp N 2 [µ(s 0 | H 0 ) -s 0 µ (s 0 | H 0 )] , (3.41)
and

β = Pr(L ≤ λ | H 1 ) → N →∞ 1 |s 1 | √ N πµ (s 1 |H 1 ) exp N 2 [µ(s 1 | H 1 ) -s 1 µ (s 1 | H 1 )] . (3.42) where µ (s j | H j ) = µ 0 (s j | H j ) + µ 1 (s j | H j ) is the second derivative of cumulant generating function l(V | x) dened by: l(v | 0) = log (1 -P e,B ) T Z| X, θ(v | 0) T Y |X,θ (v | 0) + P e,B T Z| X, θ(v | 1) T Y |X,θ (v | 0) , (3.43) l(v | 1) = log (1 -P e,W ) T Z| X, θ(v | 1) T Y |X,θ (v | 1) + P e,W T Z| X, θ(v | 0) T Y |X,θ (v | 1) . (3.44)
We give below the numerical results for the dierence between Gaussian approximation and Asymptotic Expression and for the comparison with Monte-Carlo simulation in order to see which is the best choice for authentication performance.

In order to assess the accuracy of the computations of α and β using either the Gaussian approximation given by (3.23) and (3.24), the Asymptotic Expression given by (3.39) and (3.42) and the Monte-Carlo simulations using importance sampling given in our paper [START_REF] Thu | Document authentication using graphical codes: Reliable performance analysis and channel optimization[END_REF], we respectively derive ROC curves for generalized Gaussian distributions and b = {1, 2, 6}. The ROCs are practically computed by rst setting a threshold λ and then deriving the probabilities associated to this threshold.

Conclusion of Chapter 3

In this chapter, rigorously we have introduced the general model for print and scan channels. We have also proposed the receiver's strategies to perform authentication relying on the classical binary hypothesis testing. We have made the comparisons for all strategies and indicated the best strategy for the receiver. A reliable computation of the authentication performance based on Asymptotic Expression method has been derived and compared with the Monte-Carlo simulation (see also in [START_REF] Thu | Document authentication using graphical codes: impacts of the channel model[END_REF][START_REF] Thu | Document authentication using graphical codes: Reliable performance analysis and channel optimization[END_REF]).

From the practical point of view, the next chapter studies the impact of the estimation on authentication performance. Another expression of Asymptotic Expression, based on a well-known distribution in statistical physic, will be proposed to fulll this study.

Chapter 4

Impact of estimation on authentication performances There is no end to education. It is not that you read a book, pass an examination, and nish with education. The whole of life, from the moment you are born to the moment you die, is a process of learning.

In this chapter we extend our analysis to the case where the receiver does not know the true parameter θ related to the opponent print and scan process, but establishes a test statistic using estimated ones obtained by a maximum likelihood based algorithm.

The estimated parameters are computed from several codes identied previously as fake codes which represent a set of printed and scanned dots driven from P Z|X, θ (see (4) in Fig. 3.1).

Asymptotic expression employing Boltzmann's distribution

As we have mentioned in the setup, practically the receiver have only a partial knowledge about the opponent channel. We assume indeed that the receiver has an a-priori knowledge about the families of distributions that govern the opponent channel. Furthermore we assume that the receiver observes several identied fake GCs, he then uses these observed data to estimate the parameters of the opponent channel. Because every estimation yields noise, the loss in authentication performance is computed by comparing the error probabilities obtained for the true and estimated channel. A rigorous study of this loss is consequently needed due to the natural fact that the receiver in this chapter performs authentication based on the estimated opponent channel instead of the true one that gives the optimal performance.

It is important to compare our study with a direct use of the Generalized Likelihood Ratio Tests (GLRT, see 2.1.2). Or analysis is motived by the following points:

In our setup, the opponent channel parameters are not estimated directly from the received code (as for the GLRT) but they are estimated beforehand from a batch of codes which are known to be fake.

Because we are interested in computing an accurate estimation of the error probabilities, we cannot invoke a variation of the Wilks' theorem (see eq. (2.26)), since it is only accurate for large N or small false alarm probabilities.

Moreover, our setup is dierent from the assumptions of the Wilks's theorem since the parametric denition of densities under H 0 and H 1 can be dierent in our case.

There is one connection however: in the case where the observation used by the GLRT comes from only fake codes, then the test that we use in this chapter and the GLRT are equivalent.

In this section, we develop an essential tool to fulll this study, which is originally related to the more general concepts of f -divergence in information theory and Boltzmann's distribution in statistical physics.

There exists dierent expressions for the asymptotic tail probabilities of sum of i.i.d random variables, for example, in the part Asymptotic expression of section (3.4) or in [START_REF] Thomas | Elements of information theory 2nd edition[END_REF] on Sanov's theorem that uses information theoretical arguments. Here, we present a unied tool employing the Boltzmann's distribution, that allows to derive these expressions and to use them to link the probability errors of the tests obtained for true parameters and for estimated ones. All these expressions or proofs use a twisted distribution (see in [START_REF] Anand | Relations between Kullback-Leibler distance and Fisher information[END_REF][START_REF] James | Large deviation techniques in decision, simulation, and estimation[END_REF]) which is centered on the desired threshold when optimized.

This desired threshold is bounded from above and below by the quantities related to the Kullback-Leibler divergences between the distribution of the main and opponent channels. By the use of Boltzmann's distribution, we can generalize the concept of this twisted distribution. The most important fact is that the generalized tool helps us approximate accurately the losses on β via a very simple expression when the opponent channel is estimated.

The goal of this part is to show the relation between the Boltzmann's distribution and the Cherno bounds mentioned in the previous part and to deduce several interesting properties. We start with generating a property related to the f -divergence. For simplicity, we denote:

p 0 ≡ P V |H 0 , (4.1)
the parametric density of the sequence coming from the null hypothesis H 0 , and

p 1 ≡ P V |H 1 , (4.2)
for the one coming from the alternative hypothesis H 1 .

Generally, we can consider two densities p 0 (v) and p 1 (v) dened on a space Ω. The requirement is that the n-moment of the log-likelihood ratio w.r.t p 0 and p 1 are nite, i.e.,

ˆΩ log p 1 (v) p 0 (v) n p 1 (v)d(v) < ∞, (4.3)
ˆΩ log p 0 (v) p 1 (v) n p 0 (v)d(v) < ∞, (4.4)
which implies that D KL (p 1 ||p 0 ) < ∞ and D KL (p 0 ||p 1 ) < ∞ by taking n = 1.Hence p 0 (v) and p 1 (v) have common support on Ω, i.e., both p 0 and p 1 are absolutely continuous w.r.t a common Lebesgue measure on Ω. So the following parametric density, called a Boltzmann distribution, is well-dened:

p t (v) = [p 0 (v)] 1-t [p 1 (v)] t N t , (4.5)
on

Ω with N t is normalized constant N t = ´Ω [p 0 (v)] 1-t [p 1 (v)] t dv (0 ≤ t ≤ 1).
We are then able to dene the f -divergence between p t and p u as:

D f (p t ||p u ) = ˆΩ f p t (v) p u (v) p u (v)dv, (4.6)
with f is a convex function.

α exp {N r [µ(s) -sµ (s)]} , β exp {N r [µ(s) + (1 -s)µ (s)]} . 0 < s < 1 (4.7)
or equivalently:

log α N r (µ(s) -sµ (s)) = -N r D KL (p s ||p 0 ), (4.8)
and

log β N r (µ(s) + (1 -s)µ (s)) = -N r D KL (p s ||p 1 ). (4.9)
Now we apply this general development in our case in which D KL (p s p 0 ) and D KL (p s p 1 ) (0 < s < 1) are dened as:

D KL (p s p 0 ) = D KL (p s (• | 0) p 0 (• | 0)) + D KL (p s (• | 1) p 0 (• | 1)), (4.10) and D KL (p s p 1 ) = D KL (p s (• | 0) p 1 (• | 0)) + D KL (p s (• | 1) p 1 (• | 1)), (4.11)
where

p 0 (v | x) = P Y |X,θ (v| x, H 0 ) p 1 (v | x) = P Z|X, θ (v| x, H 1 ) x = 0, 1 (4.12)
and

p s (v | x) = [p 0 (v|x)] 1-s [p 1 (v|x)] s v∈V [p 0 (v|x)] 1-s [p 1 (v|x)] s x = 0, 1. (4.13)
As we have mentioned above, we can consider without loss of generality that N B = N W = N/2 (N is the sample size), the formulas (4.8) and (4.9) are then:

log α - N 2 D KL (p s ||p 0 ) (4.14) log β - N 2 D KL (p s ||p 1 ), (4.15)
which gives us an explicit approximation of the error probabilities w.r.t. the Boltzmann's distribution p s .

Approximation of authentication performance up to the second order

In this section we analyze how the set of estimated parameters impacts the performance of the probability of type II error β(α, θ) for a xed value of α. Precisely, we provide a relation between the variation on log β(α, θ) and the variation on θ. To do this, we assume that the proposed estimation scheme is able to provide unbiased estimated parameters θ that are close to the true parameters θ of the opponent channel.

Second order approximation

Here, we suppose that θ is a vector of m unknown parameters, i.e., θ = ( θ1 , ..., θm ).

Without loss of generality, we can take into account our analysis on the codes with the same number of bits 0 (N b ) and bits 1 (N w ), i.e., N b = N w = N According to the Taylor expansion we can write:

β * ( θ) ∼ = β * ( θ) + ∇β * ( θ) θ= θ ( θ -θ) + 1 2 ( θ -θ) T ∇ 2 β * ( θ) θ= θ ( θ -θ) + ... (4.16)
where

β * ( θ) ≡ β * (α, θ) = 2 N log β(α, θ) = µ(s 1 ( θ) | H 1 ) -s 1 ( θ)µ (s 1 ( θ) | H 1 ),
and ∇β * ( θ) and ∇ 2 β * ( θ) are the gradient vector and Hessian matrix of β * ( θ) respectively. For simplicity, we denote D = ∇β * ( θ) and H = ∇ 2 β * ( θ).

Let's denote also:

α * ( θ) ≡ 2 N log α( θ) = µ(s 0 ( θ) | H 0 ) -s 0 ( θ)µ (s 0 ( θ) | H 0 ),
We have for each θi the rst partial derivative of α * ( θ) w.r.t θi as:

∂α * ( θ)

∂ θi = E p 0 s 0 ( θ)l i ( θ)e s 0 ( θ)l( θ)
E p 0 e s 0 ( θ)l( θ)

-s 0 ( θ)

∂λ 0 ( θ) ∂ θi N/2 , (4.17)
where l( θ) = log p 1 (v| θ) p 0 (v| θ)

and l i ( θ) = ∂l( θ) ∂ θi . Because α is xed, ∂α * ( θ) ∂ θi = 0 (i = 1, ..., m),
and hence:

∂λ 0 ( θ) ∂ θi N/2 = E p 0 l i ( θ)e s 0 ( θ)l( θ)
E p 0 e s 0 ( θ)l( θ)

.

(4.18)
Similarly, the rst partial derivative of β * ( θ) w.r.t θi is ∂β * ( θ)

∂ θi = E p 1 s 1 ( θ)l i ( θ)e s 1 ( θ)l( θ) E p 1 e s 1 ( θ)l( θ)
-s 1 ( θ)

∂λ 1 ( θ) ∂ θi N/2 . (4.19)
We always choose the same threshold for the test, so λ 0 ( θ) = λ 1 ( θ) ∀ θ and then ∂β * ( θ)

∂ θi = s 1 ( θ)    E p 1 l i ( θ)e s 1 ( θ)l( θ) E p 1 e s 1 ( θ)l( θ) - E p 0 l i ( θ)e s 0 ( θ)l( θ) E p 0 e s 0 ( θ)l( θ)    . (4.20)
By using two Boltzmann's distributions p s 0 ( θ) ≡ p s 0 (v | θ) and p s 1 ( θ) ≡ p s 1 (v | θ)

dened as follow:

p s 0 ( θ) = e s 0 ( θ)l( θ) p 0 ( θ) Ep 0 e s 0 ( θ)l( θ) , p s 1 ( θ) = e s 1 ( θ)l( θ) p 1 ( θ) Ep 1 e s 1 ( θ)l( θ) .

(4.21)

and with the approximation that p 1 ( θ) ≈ p 1 ( θ), we can simplify Eq. 4.20 with:

∂β * ( θ) ∂ θi ≈ s 1 ( θ) E ps 1 l i ( θ) -E ps 0 l i ( θ) . (4.22)
Note that this approximation does not impair our results since in the following, we compute the expectation of all derivatives for θ = θ. As pointed out previously, at the true parameters θ, we know that :

s 1 ( θ) = s 0 ( θ) -1. (4.23)
This property leads to the following lemma:

Lemma 1. For every integrable function f (θ), whenever the Cherno 's bounds are optimized we have:

E ps 1 f ( θ) = E ps 0 f ( θ) (4.24)
at the true parameters θ.

Proof. The proof is directly obtained when plugging property (4.23) in (4.24). Now we respectively compute the values of D and H at the actual model parameters θ of opponent's printing process.

Value of D at θ:

Applying this lemma we can directly imply the following equality for the gradient of β * at the true parameter θ:

∇β * ( θ) θ= θ = 0, (4.25)
hence D = 0. The equation (4.25) is not surprising since the NP-test is known to reach the optimum when applied on the true parameter.

Value of H at θ:

In order to compute the value of H at θ, we respectively derive the analytical formulas for ∂ 2 β * ( θ)

∂ θ2 i θ= θ and
∂ 2 β * ( θ)
∂ θi ∂ θk θ= θ. Now let us rst denote:

cov(l, l i ) = E ps 0 l( θ)l i ( θ) -E ps 0 l( θ) E ps 0 l i ( θ) cov(l i , l k ) = E ps 0 l i ( θ)l k ( θ) -E ps 0 l i ( θ) E ps 0 l k ( θ) Var(l) = E ps 0 l 2 ( θ) -E 2 ps 0 l( θ) Var(l i ) = E ps 0 l i ( θ) 2 -E 2 ps 0 l i ( θ) .
Then we can prove the two lemmas presented below that give expression of the the second partial derivatives of β * ( θ):

Lemma 2. At θ = θ we have, for each parameter θi :

∂ 2 β * ( θ) ∂ θ2 i θ= θ = s 1 ( θ) cov 2 (l,l i ) Var(l) -Var(l i ) (4.26)
Proof. See A.2 in Appendix.

Similar to the above lemma, we can prove the following result for the second partial derivatives of β * ( θ) w.r.t the parameters θi and θk : Lemma 3. At θ = θ we get, for each couple of parameter ( θi , θk ), the following result:

∂ 2 β * ( θ) ∂ θi ∂ θk θ= θ = s 1 ( θ) cov(l,l i )cov(l,l k ) Var(l) -cov(l i , l k ) (4.27)
Proof. Taking the partial derivative on both sides of (4.22) w.r.t θk and follow the same way as in lemma [START_REF]Counterfeiting statistics[END_REF].

From Taylor expansion, the property (4.23), the lemma (2), (3) and Eq. 4.25, we get the close form formula for the Hessian matrix H (i.e., we do not have to use any sample to compute H) and obtain the important theorem below:

Theorem 4. The expansion for the log of the probability of type II error w.r.t the estimated parameters close to the true parameters θ, can be expressed as a quadratic form:

log β( θ) ∼ = log β( θ) + N 4 ( θ -θ) T H( θ)( θ -θ) (4.28)
where

H i,i ( θ) = s 1 ( θ) cov 2 (l,l i ) Var(l) -Var(l i ) H i,k ( θ) = s 1 ( θ) cov(l,l i )cov(l,l k ) Var(l)
-cov(l i , l k ) . It should be reminded that in order to analyze the authentication performance, we try to analyze the variation of log β( θ) w.r.t the set of estimated parameters θ . It means that we want to approximate the distribution of log β( θ) considering the distribution of θ. Because we consider an unbiased MLE in order to achieve optimal estimation, θ asymptotically tends to a normal distribution and consequently the distribution of log β( θ) can be determined.

Distribution of log β( θ)

Distribution for one estimated parameter

For the sake of simplicity, we can start with the assumption that there is only one parameter θi 0 that needs to be estimated. In this case the formula (4.28) in Theorem (4) becomes:

log β( θ) ∼ = log β( θ) + N 4 ∂ 2 β * ( θ) ∂ θ2 i 0 θ= θ θ 2 , (4.30)
where θ = ( θi 0 -θi 0 ) and

∂ 2 β * ( θ) ∂ θ2 i 0 θ= θ = s 1 ( θ) cov 2 (l, l i 0 ) Var(l) -Var(l i 0 ) . Let γ(α, θ) = N 4 ∂ 2 β * ( θ) ∂ θ2 i 0 θ= θ × Var( θi 0 ), (4.31)
and the normalized module be:

ρ( θi 0 ) = θ 2
Var( θi 0 ) ,

where Var( θi 0 ) is the variance of the estimated parameter θi 0 . is the variation of the estimation . The expression (4.30) is then:

log β( θ) ∼ = log β( θ) + γ(α, θ)ρ( θi 0 ). (4.33)
From the property of NP-test, we always have log β( θ) ≥ log β( θ) for all θ so γ(α, θ) is always nonnegative. By using (2.41), we can see ρ( θi 0 ) has normalized chi-squared distribution with 1 degree of freedom. Therefore, from (4.33) we show that log β( θ) follows a shifted and scaled chi-squared distribution. The mean and variance of log β( θ) for an unbiased estimator θ are then:

E log β( θ) = log β( θ) + γ(α, θ), Var log β( θ) = 2γ 2 (α, θ). (4.34)
Now if we take 100(1 -η)% of an error spread region χ 2

1, η 2 , χ 2 1,1-η 2
for θi 0 satisfying:

Pr ρ( θi 0 ) ≤ χ 2 1, η 2 = η 2 Pr ρ( θi 0 ) ≤ χ 2 1,1-η 2 = 1 -η 2 .
We thus have a corresponding 100(1 -η)% error spread region for log β( θ):

log β( θ) + γ(α, θ)χ 2 1, η 2 , log β( θ)γ(α, θ)χ 2 1,1-η 2 , (4.35)
and derive two critical ROC curves that bound 100(1 -η)% error spread region for the losses in authentication performance.

Distribution for several estimated parameters

The extension of this analysis for vectors of estimated parameters of size m is more practical and needs to be taken into account. Hopefully, in this case if θ is unbiased ML estimator and if we dene:

H * ≡ N 2 H (4.36) then log β( θ) ∼ = log β( θ) + 1 2 ( θ -θ) T H * ( θ)( θ -θ) (4.37)
is called a quadratic form of normal distribution and sometimes its distribution is called generalized chi-squared distribution, say Gχ 2 m , in statistical literature [58, 59, 67, 86, 92]. Generally, its density has no explicit form but it can be approximated numerically in [START_REF] So Rice | Distribution of quadratic forms in normal random variables-evaluation by numerical integration[END_REF][START_REF] Sheil | Algorithm as 106: The distribution of nonnegative quadratic forms in normal variables[END_REF]. For such quadratic models, which are extremely popular in nancial risk calculation [START_REF] Jaschke | Asymptotic behavior of tails and quantiles of quadratic forms of Gaussian vectors[END_REF], the quantiles can be estimated in [START_REF] Jaschke | Asymptotic behavior of tails and quantiles of quadratic forms of Gaussian vectors[END_REF]. Based on these developments, we can deduce the condence regions for log β( θ) which are important to analyze the losses in authentication performance.

We can obtain the explicit formulas for the expectation and variance of the quadratic form (4.37) by using the following proposition: Proposition 5. If θ is unbiased ML estimator with mean θ and covariance matrix Σ θ , H * is a symmetric matrix with constant terms in R, then the expectation and variance of log β( θ) are can be computed numerically in [START_REF] Jaschke | Asymptotic behavior of tails and quantiles of quadratic forms of Gaussian vectors[END_REF]. The approximations for the probabilities of log β( θ) can be provided using the method described in [START_REF] Sheil | Algorithm as 106: The distribution of nonnegative quadratic forms in normal variables[END_REF].

E log β( θ) = log β( θ) + 1 2 tr H * Σ θ , Var log β( θ) = 1 2 tr H * Σ θ 2 .

Approximation of authentication performance up to the third order

Note that for authentication purposes only, our goal is to obtain a good approximation of the distribution of the error probability as we have done in the previous section.

We are also interested here in analyzing the loss of accuracy due to the rest of the Taylor expansion of log β( θ) w.r.t. the estimation error, especially the most important term after the second derivative, i.e. the third order derivative. We show in this section that if we take into account the third derivative, we are able to obtain a better match with the asymptotic expression, however its impact is rather marginal compared with the inuence of the second order derivative. As a perspective we foresee that the use of the third derivative might lead to a better approximation of the distribution of log β( θ).

This development help us obtain such a more accurate behavior of log β( θ) w.r.t to ρ( θ).

For the sake of simplicity, we start this analysis for only one estimated parameter rst and then, as above, we provide an extension for the case of multiple estimated parameters. Precisely, we suppose that there is only unknown parameter θi 0 and the aim is to compute analytically the third partial derivative of log β( θ) w.r.t θi 0 .

From (A.12) we have:

∂ 3 β * ( θ) ∂ θ3 i 0 = s(i 0 ) 1 ( θ)A( θ) + 2 ṡ(i 0 ) 1 ( θ) ∂A( θ) ∂ θi 0 ( θ) + s 1 ( θ) ∂ 2 A( θ) ∂ θ2 i 0 ( θ), with s(i 0 ) j ( θ) = ∂s 2 j ( θ) ∂ θ2 i 0
( θ) (j = 0, 1). By using the the lemma (1), the third partial derivative of β * ( θ) w.r.t θi 0 at the true parameter θ is then

∂ 3 β * ( θ) ∂ θ3 i 0 θ= θ = 2 ṡ(i 0 ) 1 ( θ) ∂A( θ) ∂ θi 0 θ= θ + s 1 ( θ) ∂ 2 A( θ) ∂ θ2 i 0 θ= θ , (4.39)
where

∂ 2 A( θ) ∂ θ2 i 0 = E ps 1 l i ( θ) -E ps 0 l i ( θ) + 2 v∈V l i 0 ( θ) ∂ps 1 ( θ) ∂ θi 0 - ∂ps 0 ( θ) ∂ θi 0 + v∈V l i 0 ( θ) ∂ 2 ps 1 ( θ) ∂ θ2 i 0 - ∂ 2 ps 0 ( θ) ∂ θ2 i 0 . (4.40)
From lemma (1), we also get: Part (v) in Theorem ( 8) especially highlights the importance of the proposed development on expressing Cherno bound by using the concept of Boltzmann's distributions. We will see in the numerical part how these developments can be used to fulll our proposed analysis.

∂ 2 A( θ) ∂ θ2 i 0 θ= θ = 2 v∈V l i 0 ( θ) ∂ps 1 ( θ) ∂ θi 0 - ∂ps 0 ( θ) ∂ θi 0 θ= θ + v∈V l i 0 ( θ) ∂ 2 ps 1 ( θ) ∂ θ2 i 0 - ∂ 2 ps 0 ( θ) ∂ θ2 i 0 θ= θ.
And last but not least, in A.5 of Appendix we discuss about how to approximate log β( θ) in the case of multiple estimated parameters using Taylor expansion up to the third order. To do this, we have to rewrite the Taylor expansion (4.28), plus the appearance of the third order term, as follow:

log β( θ) ∼ = log β( θ) + N
β * ( θ) = 2 N log β( θ),
so we just have to nd to formula for

∂ 3 β * ( θ) ∂ θi ∂ θj ∂ θk θ= θ which is presented in Appendix A.5.
However, it should be emphasized here that until now we cannot derive the probability distribution for the expansion of log β( θ) up to the third order due to the fact that the cube of a normal distribution is indeterminate (see [START_REF] Berg | The cube of a normal distribution is indeterminate[END_REF][START_REF] Targhetta | On a family of indeterminate distributions[END_REF]). It is reminded that the aim of this part is to nd a better estimation of the behavior of log β( θ) w.r.t the variation ρ( θ) of the estimated parameters.

Numerical results

In order to perform our analysis numerically, we have to construct a MLE scheme for parameter estimation. It is known from the subsection (2.1.3) that the Expectation Maximization (EM) algorithm is an iterative method for nding maximum likelihood.

Without loss of generality we assume that T Z| X=0, θ and T Z| X=1, θ are modeled by truncated discrete normal distributions with θ = (μ b , σ2 b , μw , σ2 w ) such that T Z| X, θ is a mixture of two truncated Gaussians (for instance, see (3.7) for b = 2). We then develop an EM algorithm for this particular mixture to estimate the set of unknown parameters.

EM algorithms on truncated data

First, in order to interpret why we have to develop and to adapt the EM algorithm to fulll our analysis, let's see in Fig. 4.1 that if we use the classical EM algorithm for a mixture of two continous Gaussians the results are completely inaccurate even when the number of observation N obs is large. For example, in Fig. 4.1, the estimated values μb of the true mean of black bits μb = 50 are mostly on the range [START_REF] Pérez-Cruz | Kullback-leibler divergence estimation of continuous distributions[END_REF][START_REF] Targhetta | On a family of indeterminate distributions[END_REF] and the estimated values σb of the true standard deviation σb = 42 are mostly on the range [START_REF] Feder | Universal composite hypothesis testing: A competitive minimax approach[END_REF][START_REF] Thu | Authentication using graphical codes: Optimisation of the print and scan channels[END_REF]. Similarly, μw ∈ [157, 172] while the true mean of white bits μw = 150 and σw ∈ [START_REF] Feder | Universal composite hypothesis testing: A competitive minimax approach[END_REF][START_REF] Thu | Authentication using graphical codes: Optimisation of the print and scan channels[END_REF] while the true standard deviation of white bits σw = 42. In our setup, the observations, collected from the identied fake codes of opponent's channel, as supposed, are restricted to be integer (grey level) in the range [0, 255]. As introduced in (3.2), the probability density function of the opponent channel has the form:

P Z|X, θ(Z = v | X = 0, θ) = (1 -P e,B )T Z| X, θ(v | X = 0, θ) + P e,B T Z| X, θ(v | X = 1, θ) or P Z|X, θ(Z = v | X = 1, θ) = (1 -P e,W )T Z| X, θ(v | X = 1, θ) + P e,W T Z| X, θ(v | X = 0, θ).
Let call the mixing weights π 0,B = 1-P e,B , π 1,B = P e,B and π 0,W = P e,W , π 1,W = 1-P e,W . The j-th (j = 0, 1) component truncated density function

T Z| X, θ(v | X = j, θ) = f j (v| θ) 255 u=0 f j (u| θ)
where f j (v | θ) are discrete normal distributions. Recall that z j,n be indicator random variables for the component membership. We can express the log-likelihood functions for complete data of size N = N b + N w as

L T ( θ) = L T ( θ | B) + L T ( θ | W ) (4.43)
where

L T ( θ | B) = N b n=1 j=0,1 z j,n B log π j,B + log T Z| X, θ(v n | X = j, θ) = N b n=1 j=0,1 z j,n B log π j,B + log f j (v n | θ) -log 255 u=0 f j (u | θ) (4.44) and L T ( θ | W ) = Nw n=1 j=0,1 z j,n W log π j,W + log T Z| X, θ(v n | X = j, θ) = Nw n=1 j=0,1 z j,n W log π j,W + log f j (v n | θ) -log 255 u=0 f j (u | θ) (4.45)
After some steps of mathematical computation we can have in E-step:

z j,n B = π j,B T Z| X, θ(v n | X = j, θ) k=0,1 π k,B T Z| X, θ(v n | X = k, θ) (4.46) and z j,n W = π j,B T Z| X, θ(v n | X = j, θ) k=0,1 π k,B T Z| X, θ(v n | X = k, θ) (4.47)
and in M-step the following update rules

μj = N b n=1 z j,n B vn+ Nw n=1 z j,n W vn N b n=1 z j,n B + Nw n=1 z j,n W -M 1 j σ2 j = N b n=1 z j,n B (vn-μ j ) 2 + N b n=1 z j,n W (vn-μ j ) 2 N b n=1 z j,n B + Nw n=1 z j,n W -M 2 j (4.48)
where

M 1 j = 255 u=0 (u-μ j )f j (u| θ) 255 u=0 f j (u| θ) M 2 j = 255 u=0 [(u-μj) 2 -σ 2 j ]fj(u| θ)

Fisher information for mixture of truncated discrete normal distribution

In our analysis, in order to compute the mean of log β(α, θ) and express the error spread region for the authentication performance, it is required to compute the covariance matrix Σ θ associated with the ML estimators θ. Using the Cramer-Rao lower bound, it is known that Σ θ can be approximated by the inverse of the Fisher information I m ( θ) of a sequence of N i.i.d random variables conditioned by the vector of parameter θ of size m (see (2.37)). This matrix, in general, cannot be computed explicitly because θ is unknown but it may be approximated by the observed Fisher information J m ( θ) at the ML estimators θ (2.43) when N is suciently large. However, in order to conduct our analysis, we suppose that we know the true parameters θ of the main channels. Therefore, we can numerically calculate the actual Fisher information matrices I m ( θ) and use it as an approximation for Σ θ.

In our setting, generally we consider θ = (μ b , σ2 b , μw , σ2 w ) hence m = 4 and we need to express the formulas for each I 4 ( θh , θk ) (h, k = 1, ..., 4):

I 4 ( θh , θk ) = I B
4 ( θh , θk ) + I W 4 ( θh , θk ) where I B 4 ( θh , θk ) and I W 4 ( θh , θk ) are respectively the (h, k)-entries of the Fisher information matrix I 4 calculated by using N b observed data from black bits and N w observed data from white bits. Without loss of generality, we show here the formulas for I W 4 ( θh , θk ) and obtain the similar ones for I B 4 ( θh , θk ). If we take gθ ≡ P Z|X=1, θ and we can easily nd (for i ∈ {0, 1}):

∂ log gθ(v) ∂µ i = π i,W B i σ i v-µ i σ i + A i B i f i (v| θ) gθ(v) ∂ log gθ(v) ∂σ 2 i = π i,W B i σ 2 i 1 2 v-µ i σ i 2 + C i B i -1 2 f i (v| θ) gθ(v) (4.50)
where

A i = f i (255 | θ) -f i (0 | θ) B i = 255 u=1 f i (u | θ) C i = 255-µ i 2σ 2 i f i (255 | θ) + µ i 2σ 2 i f (0 | θ). (4.51)
Let's denote M (i,j)

i 1 j 1 = u=255 u=0 u -µ i σ i i 1 u -µ j σ j j 1 f i (u | θ)f j (u | θ) f (u | θ) , i 1 , j 1 ∈ {0, 1, 2},
then we have the following formulas after several steps of calculation:

I W 4 (µ i , µ j ) = π i,W π j,W B i B j σ i σ j M (i,j) 11 + A j π i,W π j,W B i B 2 j σ i σ j M (i,j) 10
+ A i A j π i,W π j,W B 2 i B 2 j σ i σ j M (i,j) 00 + A i π i,W π j,W B 2 i B j σ i σ j M (i,j) 01 (4.52) I W 4 (µ 0 , σ 2 i ) = π 0,W π i,W 2B 0 B i σ 0 σ 2 i M (0,i) 12 -M (0,i) 10 + C i π 0,W π i,W B 0 B 2 i σ 0 σ 2 i M (0,i) 10 + A 0 π 0,W π i,W 2B 2 0 B i σ 0 σ 2 i M (0,i) 02 -M (0,i) 00 + A 0 C i π 0,W π i,W B 2 0 B 2 i σ 0 σ 2 i M (0,i) 00 (4.53) I W 4 (µ 1 , σ 2 i ) = π 1,W π i,W 2B 1 B i σ 1 σ 2 i M (i,1)
21 -M (i,1) 01

+ C i π 1,W π i,W B 1 B 2 i σ 1 σ 2 i M (i,1) 01 + A 1 π 1,W π i,W 2B 2 1 B i σ 1 σ 2 i M (i,1)
20 -M (i,1) 00

+ A 1 C i π 1,W π i,W B 2 1 B 2 i σ 1 σ 2 i M (i,1) 00
(4.54) I W 4 (σ 2 i , σ 2 i ) = π 2 i,W 4B 2 i σ 4 i M (i,i) 22 -2M (i,i) 11 + M (i,i) 00 + C i π 2 i,W B 3 i σ 4 i M (i,i) 11 -M (i,i) 00 + C 2 i π 2 i,W B 4 i σ 4 i M (i,i) 00 (4.55) I W 4 (σ 2 0 , σ 2 1 ) = π 0,W π 1,W 4B 0 B 1 σ 2 0 σ 2 1 M (0,1) 22 -M (0,1) 20 -M (0,1) 02 + M (0,1) 00 + C 1 π 0,W π 1,W 2B 0 B 2 1 σ 2 0 σ 2 1 M (0,1) 20
-M (0,1) 00

+ C 0 C 1 π 0,W π 1,W B 2 0 B 2 1 σ 2 0 σ 2 1 M (0,1) 00 + C 0 π 0,W π 1,W 2B 1 B 2 0 σ 2 1 σ 2 0 M (0,1) 02 -M (0,1) 00 .
(4.56)

The quadratic form of the error ρ( θ) in (2.42) is then:

ρ( θ) = θ -θ T I 4 ( θ) θ -θ asym ∼ χ 2 4 (4.57)
which is bounded by two 4-dimensional ellipsoids:

R = θ : χ 2 4,γ 1 ≤ ρ( θ) ≤ χ 2 4,

Impact of estimation on authentication performance

First, in case of one parameter, we can show the interplay between the error spread region ρ and the probability of type II error log β. Precisely, based on the statistical quantities of ρ, we can derive the corresponding statistical quantities of log β and vice versa.

Figs. (4.3) and (4.4) show that in the case of one estimated parameter, log β(α, σb ) and log β(α, σw ) precisely follow a shifed-scaled chi-squared distributions of 1-degree of freedom (see Eq. 4.33), given that ρ( σb ) and ρ( σw ) are chi-squared distributions of 1-degree. In Fig. 4.5, we suppose that only μw is unknown and we run the EM algorithm N iter times using each time N obs observations and obtain a set of μw . The scatter plot of Figure [4.5] represents the computed values of log β(α, μw ) coming from the Asymptotic Expression and is compared with the analytical expression ((4.33)). Here ρ( μw ) ∼ χ 2 1 , covariance matrix of the estimators becomes the variance Var( μw ), hence Var -1 ( μw ) I 1 (μ w ). The rst derivative of log-likelihood ratio l 3 ( θ) w.r.t μw at μw = μw is then:

∂ log P Z|X=0, θ ∂ μw μw=μw = P e,B P Z|X=0, θ (v -μw ) 2 2σ 4 w S 1 - S 2 S 2 1 e - (v
γ(α, μw ) = N 4   ∂ 2 β * ( θ | X = 0) ∂ μ2 w μw=μw + ∂ 2 β * ( θ | X = 1) ∂ μ2 w μw=μw   × Var( μw ). (4.62)
For additional comparisons, we represent the statistical linear regression estimated from the set of μw and expressed as log β(α, μw ) = 0.1463ρ( μw ) -44.4586 with the goodness of t coecient 0.9994. We see that the slope of statistical linear regression is quite the same with γ(α, μw ) and hence the analytical line and statistical line coincide.

In Fig. 4.6, we analyze the impact of the estimation error on the ROC curves. We select a 95% of error region for μw , i.e., ρ( μw ) is bounded by two critical levels χ 2 1,0.025 and χ 2 1,0.975 such that Pr[ρ( μw ) ≤ χ 2 1,0.025 ] = 0.025 and Pr[ρ( μw ) ≤ χ 2 1,0.975 ] = 0.975, and we thus obtain a corresponding 95% error region for log β(α, μw ). We then derive two critical ROC curves C 0.025 min and C 0.975 max computed analytically from χ 2 1,0.025 and χ 2 1,0.975 and we choose the mean value for ρ( μw ) to nd the mean ROC curve C mean . After that, we compare three analytical ROC curves C 0.025 min , C 0.975 max and C mean with the three ones (Min ROC, Max ROC and Mean ROC) computed from the dataset of ρ( μw ) (see the legend in the Figs. 4.6, 4.8 and 4.13) and we observe that our approximation is accurate.

In Fig. 4.7, we execute the same analysis as in Fig. 4.5 but now when μb is unknown. Similarly, we can nd the rst derivative of log-likelihood ratio l 1 ( θ) w.r.t μb at μb = μb as follow: Moreover, the statistical linear regression can be found from the dataset of μb and expressed as log β(α, μb ) = 0.1987ρ( μb ) -40.10725. We also analyze the impact of the estimation of μb on the ROC curves in Fig. 4.8. Again, in this gure, we can see the accuracy of our analysis.

For the case of multiple estimated parameters, without loss of generality, we suppose that there are four unknown parameters, ie., θ = (μ b , σ2 b , μw , σ2 w ). Here, we want to present the numerical results for the implementation of the CDF and the quantile of log β(α, θ) in order to analyze the losses in authentication performance.

Generally, in the case of multiple parameters, we cannot theoretically relate the impact of variation of error estimation to the probability of type II error as in the case of one parameter estimation, albeit in Fig. 4.9 when the standard deviations of the opponent channels σb , σw are small, we observe that log β(α, θ) are quite linear w.r.t ρ( θ).

To see more clearly the dierence, Fig. 4.10 shows that the log of probability of type II error log β(α, θ) is absolutely nonlinear w.r.t the variation ρ( θ). Hopefully, we can directly derive the condence region for log β(α, θ) without using indirectly the role of the total variation ρ( θ) using [START_REF] Sheil | Algorithm as 106: The distribution of nonnegative quadratic forms in normal variables[END_REF] and [START_REF] Jaschke | Asymptotic behavior of tails and quantiles of quadratic forms of Gaussian vectors[END_REF].

From these results, we can extend our analysis on the ROC curves for one estimated parameter to the analysis of ROC curves in general case of vector of estimated parameters. First, let us show the histogram for log β(α, θ) in Fig. 4.11 to see how the distribution of log β(α, θ) looks like. In Fig. 4.12, it can be shown that the distribution of log β(α, θ) could be accurately approximated by a generalized chi-squared distribution Gχ 2 4 (see Eq. 4.37).

Based on the algorithm proposed in [START_REF] Jaschke | Asymptotic behavior of tails and quantiles of quadratic forms of Gaussian vectors[END_REF], we nd that the quantile for log β(α, θ) in Fig. 4.9 at level 2.5% is x 0.025 = -49.2083 and at 97.5% is x 0.975 = -48.35566. We also obtain the average value x mean = -49.01286 for log β(α, θ) using Proposition 5. Let F β Similarly, in Fig. 4.10 the quantile for log β(α, θ) at level 2.5% is x 0.025 = -19.9603 and at 97.5% is x 0.975 = -18.8928. The average value of log β(α, θ) is x mean = -19.5283.

And based on [START_REF] Sheil | Algorithm as 106: The distribution of nonnegative quadratic forms in normal variables[END_REF], it yields to: As in the case of one estimated parameter, we now analyze the impact of the estimation of four parameters in authentication performance in Fig. 4.13based on the dataset used in Fig. 4.10. We also derive the analytical ROC curves C 0.025 min , C 0.975 max and C mean from using x 0.025 , x 0.975 and x mean based on the quadratic form (4.37) and the computation of the quantile uses a numerical method derived from [START_REF] Jaschke | Asymptotic behavior of tails and quantiles of quadratic forms of Gaussian vectors[END_REF]. We then compare with the true ones attained from N iter data used in Fig. 4.10, and once again we can see that our analysis is accurate. 4.4.4 A more accurate approximation for log β(α, θ) using third order expansion

F β (x 0.025 ) = F β (-19.9603) = 0.02502 ≈ 0.
In this part, we show the numerical results for the expansion of log β(α, θ) up to the third order and see how this development ts with the direct computation based on Asymptotic Expression.

In Fig. (4.14), we assume that there is only μw in the set of parameters θ needs to be estimated and we will show how a worse estimation for μw impacts the authentication performance, and how our development in Theorem ( 8) can be used to approximate accurately the performance of log β(α, μw ). In Fig. 4.14, the blue dots are the values of log β(α, μw ) using directly Asymptotic Expression while the red dots are the ones using Taylor expansion up to third order of log β(α, μw ) around the true value μw . We can see two set of dots are very close to each other and this shows that our development is reliable. A similar analysis is carried out in Fig. 4.15 in the case where σw is unknown.We can notice that the Taylor expansion up to the second order around the true parameter σw (the black line) is not accurate enough to approximate log β(α, σw ) (blue dots), while the one up to third order (red dots), once again, provides a rather accurate match between the Asymptotic expression and the approximation up to the third derivative. Continue analyzing the accuracy of third order expansion of log β(α, θ) in case of multiple estimated parameters, without loss of generality, we consider the case when μb , μw are unknown and need to be estimated in Fig. 4.16. In this case the Taylor expansion has the form:

log β( μb , μw ) = 1 2 ∂ 2 β ∂ μ2 b (a)v 2 b + 2 ∂ 2 β ∂ μb ∂ μw (a)v b v w + ∂ 2 β ∂ μ2 w (a)v 2 w + 1 6 ∂ 3 β ∂ μ3 b (a)v 3 b + 3 ∂ 3 β ∂ μ2 b ∂ μw (a)v 2 b v w + 3 ∂ 3 β ∂ μb ∂ μ2 w (a)v b v 2 w + ∂ 3 β ∂ μ3 w (a)v 3 w (4.66)
where a = (μ b , μw ), v b = ( μb -μb ), v w = ( μw -μw ).

We can obviously see in Fig. 4.16 that the 3 rd order expansion approximates the values of log β( μb , μw ) better than 2 nd order expansion.

Asymptote of authentication performance w.r.t the sample size

Last but not least, we want to show the asymptotic property of authentication performance w.r.t the number of observations. As we've already known that the larger the number of observation, the better the estimation and thus it is obviously to see that the authentication performance will be better as well. Moreover, this consequently makes the condence region of log β(α, θ) more and more smaller. Here, we show this property numerically in Fig. 4.17. Note that Min ROC is denoted for the ROC curve computed at level 2.5%, Max ROC for the one computed at level 97.5% and Mean ROC for the average values computed from using (5) of log β(α, θ).

To do this, rst we run EM algorithm described in (4. We can easily see in Fig. 4.17 when N obs is increased, the authentication performance (here, without loss of generality we use log 10 β(α, θ) instead of log β(α, θ) ) is more and more better. According to this gure, when N obs = 10 4 , the Min Roc is quite the same with the the actual ROC curve and the Max ROC curve is very close to it. While in the case of small N obs (for example, N obs = 2.10 3 ), the condence region of log 10 β(α, θ) is really signicant.

Conclusions of chapter 4

In this chapter we have proposed to analyze the impact of parameter estimation on the authentication performances. This was possible by relying on the asymptotic expression of the error probability presented in the previous chapter, and by computing a Taylor expansion linking the estimation error and the error probability.

The quadratic approximation derived from the expansion enables to compute the distributions of the error probabilities and to derive critical or average Receiver Operating Curves. Moreover, a higher order expansion is considered to approximate better the behavior of the authentication performance w.r.t the estimation error.

We also show practically the asymptotic property of the authentication w.r.t the number of observations used to estimate the opponent parameters. This suggests that if we get a large enough number of observations, the impact of estimation is not important anymore.

The next chapter explain how the accurate expression of the error probabilities can be used in order to optimize the print and scan channel. (Game theory) is essentially a structural theory. It uncovers the logical structure of a great variety of conict situations and describes this structure in mathematical terms. Sometimes the logical structure of a conict situation admits rational decisions; sometimes it does not.

Anatol Rapoport

In this chapter we propose to cast the problem of authentication of printed documents using binary graphical codes into an optimization game (called min-max game) between the legitimate source and the opponent, each player tries to select the best print and scan channel to minimize or maximize his authentication performance. This game is popularly used in many disciplines such as game theory, economics, engineering and technology, etc. This game is possible when considering accurate computations of the type I and type II probability errors and by using stochastic processes to model the print and scan channel.

Moreover, we also propose a mathematical interpretation to fulll the min-max game analytically based on the theory of nonlinear constrained optimization.

Passive and active opponents

We adopt in this chapter a methodology related to security by considering that the legitimate source or/and the adversary may try to modify their print and scan channel in order to maximize/minimize the authentication performances of the system. Practically this means that the channel can be chosen by using a given quality of paper, an ink of appropriate density and/or by adopting a given resolution. For example if the legitimate source wants to decrease the noise variance, he can choose to use oversampling to replicate the dots, on the contrary if the legitimate source wants to increase the noise variance, he can use a paper of lesser quality. It is important to recall that because the opponent will have to print a binary version of its observation, and because a printing device at this very high resolution can only print binary images, the opponent will in any case have to print with decoding errors after estimation XN .

From a mathematical point of view, this game can be considered as an optimization problem where the main goal of the designer of the authentication system (or the sender) is the achievement of the optimal ROC curves, i.e., for a given probability of type I error α, he tries to nd a channel that minimizes the probability of type II error β.

We analyze three practical scenarios that are described below:

The legitimate source and the opponent have identical printing and scanning devices (by devices we mean printer, ink, paper, scanner), practically this means that they use exactly the same setup. Therefore, we can suppose that the set of possible channels used by the opponent is the same than the one used by the legitimate source. In this case the legitimate source will try to look for the channel C p such that for a given probability of type I error α, the legitimate party will have a probability of type II error β * which is the smallest value among all the possible probabilities of type II β involved in the set of channels C, i.e.,

β * ≡ β(C p ) = min C β(α).
(5.1) In this case, opponent is dened to be passive and has no strategy but duplicating the graphical code. We can refer this game as a passive game.

The opponent can modify its printing channel C o , practically it means that he can modify one or several parameters of his printing setup. As a matter of fact, we can assume that he changes the variance of its noise given that it will be the most ecient way for him to confuse the receiver. The opponent thus tries to maximize the probability of type II error by choosing his adequate printing channel, whereas the legitimate source will adopt a printing channel C l which minimizes the probability of type II error. We end up with so-called a min-max game (or minimax game) in game theory, where the optimal β * (obtained by a couple of channels C l a , C o a ) is not only the largest value among all the possible probabilities of type II β involved in the set of channels C 0 , but also the smallest value among all the possible probabilities of type II β involved in the set of channels C l , i.e.,

β * ≡ β(C l a , C o a ) = min C l max Co β(α). (5.2)
Because for this scenario we assume that the receiver has a perfect knowledge of the opponent channel, we will denote it as an active opponent facing an informed receiver since the opponent tries to adapt his strategy by selecting exactly C o a in order to degrade the authentication performance. This game can be seen as a deterministic minimax game.

The last scenario is more general in the sense that we assume here that the receiver will have to estimate the opponent channel. Because of the Kerckhos' principle we assume that the opponent knows also this fact and that he will try to maximize a statistic of the type II probability β, such as for example E[β( θ)], to conduct the game. i.e.,

β * = min C l max Co E β( θ) . (5.3)
Here, the scenario presents an active opponent facing a non-informed receiver, the term non-informed coming from the fact that the receiver needs to estimate the opponent parameters beforehand in oder to compute the hypothesis test. We will use the results obtained from the preposition (5) in the previous chapter in order to conduct this analysis.This game can be seen as a random minimax game.. In order to study the this game rigorously, we would like to develop the problems (5.1) and (5.2) more explicitly in the next section.

Min-max games as optimization problems

If the problems formulated by equations (5.1), (5.2) and (5.3) can be easily intuitively solved when the opponent vector parameter θ is one dimensional, it is necessary to provide a formulation to nd a solution in the N -dimensional case mathematically. We consequently aim to provide the mathematical expressions of the passive game (5.1) and the active deterministic game (5.2). Because the active random game (5.3) is more complicated, we postpone its mathematical analysis for future researches.

We can consider these games as constrained optimization problems. The constraint comes from the fact that in the entire thesis, we suppose that the probability of type I error α is xed. Taking into account this fact, here we let α = α 0 with α 0 is a constant and nd the optimization for the probability of type II error β.

We know that we can solve a constrained optimization problem by means of Lagrange multiplier method (see [START_REF] Bertsekas | Constrained optimization and Lagrange multiplier methods[END_REF], [START_REF] Ito | Lagrange multiplier approach to variational problems and applications[END_REF]) and for any function f (x) > 0, we can look for the optimum using log f (x) instead of f (x). Therefore, our problem turns to nd the optimal log β given xed log α = log α 0 . Remind that log α and log β can be approximated from (4.8) and (4.9) and hence we can rewrite:

For the passive game, minimize C -N c D KL (p s 0 p 1 ) subject to -N c D KL (p s 0 p 0 ) = log α 0 (5.4)
For the active deterministic game, min

C l max Co -N c D KL (p s 0 p 1 ) subject to -N c D KL (p s 0 p 0 ) = log α 0 (5.5)
where N c = N 2 .

First, we start to conduct the constrained optimization problem for the case of passive game. Suppose that θ 0 is such parameter governing the channel C in the problem (5.4), we consider the Lagrange multiplier function of (5.4) as:

F (s 0 , θ 0 , λ) = -N c D KL (p s 0 p 1 ) -λ [-N c D KL (p s 0 p 0 ) -log α 0 ] . (5.6)
If we put

f (s 0 , θ 0 ) = -N c D KL (p s 0 p 0 ) -log α 0 g(s 0 , θ 0 ) = s 0 E(l 0 ) + E ∂ log p 0 ∂θ 0 = s 0 E ∂ log p 1 ∂θ 0 + (1 -s 0 )E ∂ log p 0 ∂θ 0 (5.7)
where l 0 = ∂l(θ 0 ) ∂θ 0 and the expectation is taken w.r.t p s 0 , then in order to solve (5.4), it necessarily leads to solve the system of nonlinear equations below (see detail computation in Appendix A.6):

f (s 0 , θ 0 ) = 0 g(s 0 , θ 0 ) = 0 (5.8)
For the deterministic active game, the scenario is more complicated and we cannot take advantage of the Lagrange multiplier. However, because the legitimate channel C l and the opponent channel C o are independent, we can solve this problem by splitting C l into M discreet setups (C 1 l , C 2 l , ..., C M l ) to perform the minimization and we can use the result of the maximization can be solved by Lagrangian formulation. Therefore, the game (5.5) can be rewritten as:

min (C 1 l ,C 2 l ,...,C M l ) max Co -N c D KL (p s 0 p 1 )
subject to -N c D KL (p s 0 p 0 ) = log α 0 .

(5.9)

and the pseudo algorithm can be written as:

Algorithme 5.1 Optimization algorithm for the deterministic active game.

For each legitimate channel

C i l do:\\ Compute max Co -N c D KL (p s 0 p 1 ) subject to -N c D KL (p s 0 p 0 ) = log α 0 end For
Choose the minimum as the solution If we assume that θ 1 is the parameter governing the opponent channel C o we will use the Lagrange multiplier method for each C i l . This leads to the fact that we need to solve M corresponding systems of nonlinear equations:

-N c D KL (p s 0 p 0 ) -log α 0 = 0 E ∂ log p 1 ∂θ 1 = 0 (5.10)

Numerical methods

Because it is not possible to obtain close form solution of these sets of equations, it is required to use numerical optimizers such as the Newton-Raphson method which is based on the computation of the Jacobian matrix J (see Appendix A.6) and then nd J -1 to approximate the actual solution through an iterative procedure.

However, sometimes it is dicult to compute J -1 because J is close to singular and overows the number range. We can overcome this issue by using quasi Newton algorithm (see [START_REF] John E Dennis | Quasi-Newton methods, motivation and theory[END_REF][START_REF] Thong | Printer identication from micro-metric scale printing[END_REF]) which approximate J -1 through an iterative formula instead of calculating it directly. We can also use function fsolve in Matlab toolbox (see [START_REF] Branch | MATLAB: optimization toolbox: user's guide version 1[END_REF][START_REF] Coleman | Optimization Toolbox for Use with MATLAB: User's Guide, Version 2[END_REF]) to nd the solution for the system of nonlinear equations (5.8) or (5.10).

Another approach for solving passive game is applying a certain class of algorithms which is best known for solving nonlinear constrained optimization problems (see in [START_REF] Potra | Interior-point methods[END_REF][START_REF] Wright | The interior-point revolution in optimization: History, recent developments, and lasting consequences[END_REF][START_REF] Arkadi | Interior-point methods for optimization[END_REF]). Taking into account this advantage, we can practically use fmincon and fminimax functions from Matlab optimization toolbox in order to nd the solution for the games (5.1) and (5.2) (see [START_REF] Branch | MATLAB: optimization toolbox: user's guide version 1[END_REF][START_REF] Coleman | Optimization Toolbox for Use with MATLAB: User's Guide, Version 2[END_REF]).

Numerical results

For the sake of simplicity, in this part, we conduct this analysis for the generalized Gaussian model and Lognormal model, where we assume respectively that the means µ b , µ w and the modes M b , M w (see Eqs. 3.7 and 3.9) are constant for the main and the opponent channels (which implies that the scanning process has the same calibration for the two types of images). We also assume that the main channel and the opponent channel variances σ 2 and σ2 are identical for black and white dots.

Passive game

Here the opponent has to undergo a channel identical to the main channel, the only parameter of the optimization problem 5.1 is consequently σ = σ m . If the generalized Gaussian channels are used, Fig. 5.1 presents the evolution of β(α) w.r.t. σ m for α = 10 -6 and µ b = 50, µ w = 150. For each channel conguration, we can nd an optimal conguration, this conguration oers a smaller probability of error for b = 6 than for b = 2 or b = 1. It is not surprising to notice that in each case, β is important whenever σ m is very small (i.e. when the print and scan noise is very small hence the estimation of the original code is easy) or very large (i.e. when the print and scan noise is so important that the original and forgery become equally noisy).

It is not surprising to notice that in each case β(α) is important whenever σ m is very small, i.e. when the print and scan noise is negligible hence the estimation of the original code by the opponent is easy; or very large; i.e. when the print and scan noise is so important that the original and forgery become equally noisy. The legitimate source will consequently avoid a channel that generates noise of very small or very large variance.

Active deterministic game

First, the opponent is supposed to be able to use the generalized Gaussian channel with dierent variance σ2 = σ 2 o than the main channel σ 2 = σ 2 m and we try to solve the game dened in (5.2). Fig. 5.4 shows the evolutions of β(α) w.r.t σ o for dierent σ m . We can see that in each case it is in the opponent interest to optimize his channel, i.e., he tries to select such channels that maximize the possibility of getting type II error of the receiver.

Note that even if we assume that the opponent print and scan channel is perfect ( XN = Z N ), because the input of the printer has to be binary and because the opponent will make decoding errors by estimating the original code, the copied printed code will be necessarily dierent from the original printed code (see Figure 3.1), which implies a perfect discrimination between the two hypotheses. The active scenario oers a saddle point satisfying (5.2) either for generalized Gaussian or Lognormal distribution. This means that even if the opponent owns ideally perfect print and scan devices (σ 0 → 0, o N = xN ), it is not to his advantage to use it since the authentication is still ecient due to the decoding errors he will create by generating the binary code XN . Another general remark is to notice that the optimal opponent parameters are very close to the optimal parameters of the passive scenario, which means that the opponent has little room to maneuver when choosing his best attack (see Fig. 5.1 and Fig. 5.5, 5.6) and nearly no room when the noise is close to uniform (for example, b = 6). For the generalized Gaussian distribution, it is important to notice that for distributions of same variance, dense distributions yields to better authentication performance than sparse distributions for both scenarios (see Fig. 5.1 and Fig. 5.5). Unsurprisingly, this is due to the fact that a distribution close to uniform tend to create a bigger overlap between the two decision regions than a sparse distribution that will generate codes mainly lying in the original one.

For the Lognormal distribution we can easily see that the authentication performances are almost similar for dierent values of modes, both for a passive and an active opponent (see Fig. 5.2 and Fig. 5.6). However, the larger the dierence, the larger the optimal standard deviation, which means that it is in the designer strategy to force the opponent to generate decoding errors in this case.

We have shown practically that for both the generalized Gaussian and Lognormal distributions the game can be tractable, and that it is in the interest of the legitimate source to adopt a channel which is close to the uniform distribution.

Figs. 5.7 and 5.8 shows the result of the optimization for dierent setups in the case of truncated Gaussian distributions when the variance is optimized. It is interesting to notice that in some cases (the setups considered in Fig. 5.8) the local minimum occurs for the minimal standard deviation of the selected range. This happens particularly for the setup where the parameters µ of the legitimate channel and the opponent channel are dierent, which means that for such setups, this dierence between other characteristics of the channel is enough to enable accurate authentication. In this case the optimal strategy is to adopt the print-and-scan system presenting the best delity for the legitimate printer, because the opponent diers w.r.t to parameters that he cannot control. For the Lognormal distribution, we can notice in Fig. 5.6 that the opponent's probability of type II error stays the same when the distribution is close to uniform.

Active random game

In Fig. 5.9, we see the dierence between the evolutions of the active deterministic game and the active random game for a setup where the standard deviation σ m is tuned. It is not surprising to notice that the larger σ m , the more important the dierence between the deterministic and the random game since it is well known that large variances are more dicult to be estimated than small ones.

The dierence between these two games is however relatively small, and the optimal parameter is only slightly modied (σ m ≈ 36.5 for the random game vs σ m ≈ 37 for the deterministic game). We analyze another numerical result in Fig. 5.10 for the case where there is no saddle point and the means of black and white dots are close to each other. Here, the optimal points of the active deterministic game and the active random game are exactly the same. Similarly to the former example, the dierence between the deterministic and the random game is signicant for only large σ m .

In this case, we can notice that the probabilities of type II error of both games gradually goes to 1 when σ m increases. This fact is not surprising since the means of black and white dots are close to each other, the distributions of black and white dots tend to be very similar for large variances.

Conclusions of Chapter 5

In this chapter, we have modeled the optimization of the print and scan channels as a min-max game between the legitimate receiver and the opponent.

Our rst conclusions are the facts that (i) the authentication performance is better for dense noises than for sparse noises for both scenarios, and (ii) for both families of distribution, the opponent optimal parameters are close to the legitimate source parameters, and (iii) the legitimate source can nd a conguration which maximizes the authentication performance.

Moreover, the results obtained within the two previous chapters lead us to perform optimization in the more general context that includes the problem of parameter estimation and it's impact on this security game.

Chapter 6

Conclusions and perspectives 6.1 Conclusions

Perspectives

In the end, it's not the years in your life that count. It's the life in your years.

Abraham Lincoln

We summarize here all the achievements of this thesis and we provide general conclusions and comments regarding the results we have achieved.

Last but not least, we would like also present our current works, several ideas in preparation and sketch out the directions for the future researches.

Conclusions

This thesis has presented a framework for authentication using graphical codes that is based on statistical hypothesis testing. The main advantages of such a methodology are:

the possibility to rely on the Neyman-Pearson lemma and to derive optimal tests (i.e. test minimizing a type II error for a given type I error) whenever the model of the legitimate printer and the model of the opponent are known. This strategy has the advantage to be very exible since it can be used for various distributions and it helps us to compare the performances of dierent printing models, as proposed in the chapter 5.

the computation of accurate approximations of the error probabilities based on the asymptotic expression that we have derived in chapter 3. Theses approximations are based on the Cherno 's bound and are useful whenever the error probabilities are very small (e.g. < 10 -3 ).

the fact that, using Boltzmann's distributions, it is possible to approximate the distribution of the error probabilities when the opponent channel has to be estimated beforehand. This analysis derived in chapter 4 enables to compute the average performance of the authentication system or the bounds of a condence

interval, but also to analyze the evolution of theses statistics w.r.t. the number of observed codes.

the possible optimization of the channel of a legitimate printing facing a passive or an active adversary. In the case where the opponent can tune his channel and the receiver has to estimate the opponent channel, we deal with a random game with an active adversary that is solvable (at least numerically) by using the results of chapter 3 and chapter 4. This analysis enables to point out the categories of distributions that are compatible with our authentication problem.

Perspectives

In this section, we would like to indicate several objective limitation of our analysis and possible approach that can be used to overcome these drawbacks.

Throughout the thesis, we propose and analyze eectively the classical binary testing for the sequences of i.i.d discrete random variables and its application to the analysis of authentication performance. However, until now we have not come up yet to the case in which graphical codes are composed from such a memory source sequences. One of the possible problem that can be considered is to generate the graphical codes from using a Markov chain. In [START_REF] Natarajan | Large deviations, hypotheses testing, and source coding for nite markov chains. Information Theory[END_REF], an asymptotic approximation for the probabilities of type I and type II error is proposed based on the ideas of large deviation principle. In Fig. 6.1, we can implement to obtain the ROC curve of a test between two transition matrices.

However, the values of log α and log β are still very important in comparison with the i.i.d cases. This may be due to the fact that the congurations for the matrices are realistic. Therefore, the study for this problem will be taken into account in an upcoming research.

Another perspective stems from the fact that, due to the assumption of the print and scan process, we have only dealt with the case of discrete distributions for the main and the opponent channels. In order to extend our analysis in this thesis to a larger class of forensic or signal processing problems, it is required to consider a large family of continuous distributions for H 0 and H 1 . It leads to look for the approximations schemes for the formulas (4.8) and (4.9). In the literature, there are several authors that have worked on this problem, for example [START_REF] John | Approximating the kullback leibler divergence between gaussian mixture models[END_REF][START_REF] Pérez-Cruz | Kullback-leibler divergence estimation of continuous distributions[END_REF]. Based on their works, we believe that we could apply our analysis to many other applications.

In the case when the distributions of the opponent channels are completely unknown by the receiver, our problem somehow is related to the problem of universal hypothesis testing which has already discussed in literature, for example [START_REF] Zeitouni | On universal hypotheses testing via large deviations[END_REF][START_REF] Feder | Universal composite hypothesis testing: A competitive minimax approach[END_REF]. However, these study are still very deep in theory and have not been used for applications. We hope that we could bring these study to applications in the future research.

As a nal remark, a more general perspective is to test the presented methodology on real print-and-scanned graphical codes. This is a complicated problem since in order to derive robust tests, we will need to select more realistic print and scan models (that probably are not i.i.d) and to infer their parameters, but also to test them on real acquisitions that need to be resynchronized and calibrated.

Chapitre 7

Résumé en Français

L = log P Z N |X N o N x N , H 1 P Y N |X N (o N | x N , H 0 ) , ( 7
α = Pr (L ≥ λ | H 0 ) . (7.3)
Classiquement, cette probabilité est calculée en invoquant le théorème central limite qui approxime la distribution de la variable aléatoire L par une distribution Gaussienne. Il Nous avons ici utilisé la borne de Cherno qui propose un encadrement supérieur de α ou de β à partir de la fonction génératrice des moments g L (s | H 0 ) de la variable L, ainsi :

α ≤ e -sλ g L (s | H 0 ) pour tout s > 0, (7.4) avec g L (s | H 0 ) = E P L (L|H 0 ) e sL , la borne la plus précise étant obtenue pour la valeur s 0 minimisant e -sλ g L (s | H 0 ) sous H 0 . En introduisant la fonction génératrice des moments semi-invariante µ(s ; H 0 ) = ln g L (s | H 0 ) et en invoquant le théorème de Cramer [START_REF] Dembo | Large deviations techniques and applications[END_REF][START_REF] Robert | Information theory and reliable communication[END_REF] pour N susamment grand, nous obtenons l'expression asymptotique suivante :

α → N →∞ 1 s 0 √ N πµ (s 0 ) exp N 2 [µ(s 0 ) -s 0 µ (s 0 )] . ( 7
log β( θ) ≈ log β(θ) + N 4 ( θ -θ) T H(θ)( θ -θ) (7.6)
où H(θ) est la matrice Hessienne de la fonction log β(θ) explicitée par : Proof. These equations, (A.2) and (A.1), are very important in our analysis, and they are true also ∀s:

H i,i (θ) = s 1 (θ) cov 2 (l,l i ) Var(l) -Var(l i ) , H i,k (θ) = s 1 (θ) cov(l,l i )cov(l,l k ) Var(l) -cov(l i , l k ) , cov(l, l i ) = E ps 0 l( θ)l i ( θ) -E ps 0 l( θ) E ps 0 l i ( θ) , cov(l i , l k ) = E ps 0 [l i (θ)l k (θ)] -E ps 0 [l i (θ)] E ps 0 [l k (θ)] , Var(l) = E ps 0 [l 2 (θ)] -E 2 ps 0 [l(θ)] , Var(l i ) = E ps 0 l i ( θ) 2 -E 2 ps 0 l i ( θ) .
D KL (p s ||p 0 ) = ˆps (v) log p s (v) p 0 (v) dv, = ˆp1-s 0 (v)p s 1 (v) N s log p 1-s 0 (v)p s 1 (v) Ns p 0 (v) dv, = ´p0 (v) p 1 (v) p 0 (v) s log p 1 (v) p 0 (v) s dv N s -log N s , = sE p 0 [l(V ) exp(sl(V )] E p 0 [exp(sl(V )] -log E p 0 [exp(sl(V )] , = sµ (s) -µ(s).
where l(v) = log p 1 (v) p 0 (v) .

Proposition 7. Let X t be a random variable with density function p t , the mean and variance of X t satisfy E pt (X t ) = µ (t)

(A.3) and Var pt (X t ) = µ (t) (A.4)
Proof. Taking directly the rst and second derivatives of µ(t), and using the denition of mean and variance of X t w.r.t p t .

A.2 Proof of lemma 2

Proof. We choose the same threshold for the LLR test so we can rewrite this condition mathematically as:

E ps 1 l( θ) = E ps 0 l( θ) (A.5)
Taking derivative on both sides of (A.5) yields:

v∈V l i ( θ)p s 1 ( θ) + v∈V l( θ) ∂p s 1 ( θ) ∂ θi = v∈V l i ( θ)p s 0 ( θ) + v∈V l( θ) ∂p s 0 ( θ) ∂ θi . (A.6)
At θ = θ, using lemma (1), Eq. A. = tr H * Σ θ .

Apply theorem 1 in page 55 of the book [START_REF] Shayle R Searle | Linear models[END_REF], we then have:

Var Y T H * Y = 2tr H * Σ θ 2 .
So the proposition is proven.

A. [START_REF]Global congress addresses international counterfeits threat immediate action required to combat threat to[END_REF] The third order expansion of log β(α, θ) -one parameter

Let rst denote generally:

cov(l becomes l i 0 , l i 0 or l i 0 respectively.

(m) i 0 , l (n)
In order to achieve a better approximation for the authentication performance we need to come up the following theorem:

Theorem 8. At the point θ = θ, these below equalities are always true: = s(i 0 ) 1 ( θ) -s(i 0 ) 0 ( θ) cov(l, l i 0 ) + 2 ṡ(i 0 ) 1 ( θ) -ṡ(i 0 ) 0 ( θ) Var(l i 0 ) -cov(l i 0 , l i 0 ) + ṡ(i 0 ) 1 ( θ) 2 -ṡ(i 0 ) 0 ( θ) 2 cov(l i 0 , l 2 ) -2E(l)cov(l, l i 0 ) + 2s 0 ( θ) ṡ(i 0 ) 1 ( θ) -ṡ(i 0 ) 0 ( θ) cov(l, (l i 0 ) 2 ) -2E(l i 0 )cov(l, l i 0 ) -2 ṡ(i 0 ) 1 ( θ) cov(l, (l i 0 ) 2 ) -2E(l i 0 )cov(l, l i 0 ) -s 1 ( θ) + s 0 ( θ) cov(l i 0 , (l i 0 ) 2 ) -2E(l i 0 )Var(l i 0 ) (iii) v∈V l( θ) + 2s 0 ( θ) ṡ(i 0 ) 1 ( θ) -ṡ(i 0 ) 0 ( θ) cov(l i 0 , l 2 ) -2E(l)cov(l, l i 0 ) -2 ṡ(i 0 ) 1 ( θ) cov(l i 0 , l 2 ) -2E(l)cov(l, l i 0 ) -s 1 ( θ) + s 0 ( θ) cov(l, (l i 0 ) 2 ) -2E(l i 0 )cov(l, l i 0 ) (iv)

2 ∂A( θ) Proof. We respectively prove (i) to (vi) as follow (i) We follow the same way as in the proof in lemma 2.

∂ θi 0 θ= θ + v∈V l( θ)
(ii) Remind that: We have denoted:

K(t,
p s 0 ( θ) = e s 0 ( θ)l( θ) p 0 ( θ)

Ep 0 e s 0 ( θ)l( θ)

p s 1 ( θ) = e s 1 ( θ)l( θ) p 1 ( θ) Ep 1 e s 1 ( θ)l( θ) , B 1 ( θ) = s(i 0 ) 1 ( θ) -s(i 0 ) 0 ( θ) E ps 0 l( θ)l i 0 ( θ) -E ps 0 l i 0 ( θ)l i 0 ( θ) + 2 ṡ(i 0 ) 1 ( θ) -ṡ(i 0 ) 0 ( θ) E ps 0 l i 0 ( θ) E ps 0 l( θ) E ps 0 l( θ)l i 0 ( θ) + s 0 ( θ) ṡ(i 0 ) 1 ( θ) -ṡ(i 0 ) 0 ( θ) E ps 0 l( θ) E ps 0 l i 0 ( θ) 2 + s 0 ( θ) ṡ(i 0 ) 1 ( θ) -ṡ(i 0 ) 0 ( θ) E ps 0 l i 0 ( θ) E ps 0 l( θ)l i 0 ( θ)

-s

(i 0 )
1 ( θ) + s (i 0 ) 0 ( θ) E ps 0 l i 0 ( θ) E ps 0 l i 0 ( θ) 2 -ṡ(i 0 ) 1 ( θ) E ps 0 l( θ) E ps 0 l i 0 ( θ)

2 + E ps 0 l i 0 ( θ) E ps 0 l( θ)l i 0 ( θ) (A.29)

We then get B 1 ( θ) -B 3 ( θ) = s(i 0 ) 1 ( θ) -s(i 0 ) 0 ( θ) E ps 0 l( θ)l i 0 ( θ) -E ps 0 l( θ) E ps 0 l i 0 ( θ) + 2 ṡ(i 0 ) 1 ( θ) -ṡ(i 0 ) 0 ( θ) E ps 0 l i 0 ( θ)

2 -E ps 0 l i 0 ( θ)

2 -E ps 0 l i 0 ( θ)l i 0 ( θ) -E ps 0 l i 0 ( θ) E ps 0 l i 0 ( θ) E ps 0 l 2 ( θ)l i 0 ( θ) -E ps 0 l 2 ( θ) E ps 0 l i 0 ( θ) + 2s 0 ( θ) ṡ(i 0 ) 1 ( θ) -ṡ(i 0 ) 0 ( θ) E ps 0 l( θ) l i 0 ( θ)

2 -E ps 0 l i 0 ( θ) E ps 0 l( θ)l i 0 ( θ) -

s (i 0 )
1 ( θ) + s (i 0 ) 0 ( θ) E ps 0 l i 0 ( θ)

3 -E ps 0 l i 0 ( θ) E ps 0 l i 0 ( θ) 2 -2 ṡ(i 0 ) 1 ( θ) E ps 0 l( θ) l i 0 ( θ)

2 -E ps 0 l i 0 ( θ) E ps 0 l( θ)l i 0 ( θ)

(A.31) 2 B 6 ( θ) -B 5 ( θ) = 2 ṡ(i 0 ) 1 ( θ) 2 - ṡ(i 0 ) 0 ( θ) 2
E ps 0 l( θ) E ps 0 l( θ) E ps 0 l i 0 ( θ) -E ps 0 l( θ)l i 0 ( θ) + 2s 0 ( θ) ṡ(i 0 ) 1 ( θ) -ṡ(i 0 ) 0 ( θ) 2E ps 0 l( θ) E ps 0 l i 0 ( θ)

2 -E ps 0 l( θ) E ps 0 l i 0 ( θ)

2 -E ps 0 l i 0 ( θ) E ps 0 l( θ)l i 0 ( θ) -2 s

(i 0 )
1 ( θ) + s (i 0 ) 0 ( θ) E ps 0 l i 0 ( θ)

3 -E ps 0 l i 0 ( θ) E ps 0 l i 0 ( θ) 2 -2 ṡ(i 0 ) 1 ( θ) 2E ps 0 l( θ) E ps 0 l i 0 ( θ)

2 -E ps 0 l( θ) E ps 0 l i 0 ( θ)

2 -E ps 0 l i 0 ( θ) E ps 0 l( θ)l i 0 ( θ) . + 2s 0 ( θ) ṡ(i 0 ) 1 ( θ) -ṡ(i 0 ) 0 ( θ) cov(l, (l i 0 ) 2 ) -2E(l i 0 )cov(l, l i 0 )

-2 ṡ(i 0 ) 1 ( θ) cov(l, (l i 0 ) 2 ) -2E(l i 0 )cov(l, l i 0 )

-s 1 ( θ) + s 0 ( θ) cov(l i 0 , (l i 0 ) 2 ) -2E(l i 0 )Var(l i 0 ) . (iii) Similar to (ii).

(iv) Taking the second derivative from both sides of (A.5) yields: To obtain the explicit formula for (A.48), we need the following equations (for the sake of simplicity, we drop out the index of parameter θ):

v∈V l i ( θ)

Figure 1 . 3 :

 13 Figure 1.3: Chart showing the rising number of complaints lodged in the US against

Figure 1 . 4 :

 14 Figure 1.4: A simulated Graphical Code before being printed.

CERDI(

  Centre d'Etudes et de Recherche en Droit de l'Immatériel) is belongs to university Paris 11 working on the law in intellectual property of new technologies.

Figure 1 . 5 :

 15 Figure 1.5: Description of the works of Estampille project

  they propose to model the micrometric scan of document printing by a binary response model whose the parameters depend on the location and the shape of ink dots. Ink dots viewed under microscope are shown in Figure (1.7). They provide a maximum likelihood identication algorithm, its performance is assessed through simulations and true data.

Figure 1 . 7 :

 17 Figure 1.7: Left: Ink dots in uncoated paper printed in Laser printer (600dpi). Right: Ink dots in coated paper printed in Laser printer (600dpi).

  2.1) to test two kinds of hypotheses: 1) the null hypothesis H 0 and 2) the alternative hypothesis H 1 . A decision d is derived based on the observed data in order to decide if H 0 is true or not. For any decision, there are two types of error called type I and type II error (Fig.2.2).

Figure 2 .

 2 Figure 2.1: Classical (non-Bayesian) binary hypothesis testing.

Figure 2 . 2 :

 22 Figure 2.2: Graphical description of a decision rule for classical binary hypothesis testing.

Figure 2 . 3 :

 23 Figure 2.3: ROC curves of test between two hypothesis: H 0 : P (X| H 0 ) ≡ BSC(p) and H 1 : P (X| H 1 ) ≡ BSC(2p(1 -p)), the length of i.i.d sequence X is 500, p is equal to 0.2, 0.25 and 0.3 respectively. The number of trials is 10 6 .

( 2 . 34 )

 234 Instead of working directly with the likelihood function, we can use the log-likelihood L(θ) = log L(θ | x). Since all individual likelihoods are always positive, the likelihood function and its log version achieve the maxima at the same point θML = argmax θ∈Θ L(θ),

( 2 . 35 )

 235 which is the solution for a MLE and called maximum likelihood estimator (ML estimator) for θ.

Figure 2 . 5 :

 25 Figure 2.5: Protection and Verication of banknote (taken from [51])

Figure 2 . 6 :

 26 Figure 2.6: Description of PUF-based authentication (taken from [94])

Figure 2 . 7 :

 27 Figure 2.7: From left to right: oset, laser and inkjet printing dots on uncoated papers.

Figure 3

 3

Figure 3 . 1 :

 31 Figure 3.1: Principle of authentication using graphical codes.

Figure 3 . 2 :

 32 Figure 3.2: Left: an original printed and scanned GC. Right: a re-printed and scanned (forged) GC.

Fig. 3 .

 3 Fig. 3.3 illustrates the dierent types of GCs using generalized Gaussian distributions on the main and the opponent channels of same mean and variance and with b = 1, b = 2 and b = 6 (a distribution which is close to uniform).

Figure 3 . 3 :

 33 Figure 3.3: Examples of 20 × 20 code which are generated (X N ) and printed (Y N ) by the main channel, then estimated ( XN ) and reprinted (Z N ) by an opponent using generalized Gaussian distributions in case b = 1, b = 2 and b = 6. Main and opponent channels are identical, µ b = 50, µ w = 150, σ b = 42 and σ w = 42.

Fig. 3 .

 3 4 depicts truncated Lognormal distributions having same modes but dierent standard deviations.

Figure 3 . 4 :

 34 Figure 3.4: Representation of the print and scan model for the black dots (on the left) and the white parts of the paper (on the right) for dierent standard deviations σ b = σ w = σ with M b = 70 and M w = 150 for the Lognormal distribution.

( 3 . 2 )

 32 and (3.3). In the opponent channel, i.e., when O N = Z N , we make use of (3.5) and (3.6) to express the corresponding error probabilities: Pe,B = v∈D W P Z|X, θ( v| X = 0, θ) (3.11) hence Pe,B = (1 -P e,B ) v∈D W T Z| X, θ( v| X = 0, θ) +P e,B v∈D W T Z| X, θ( v| X = 1, θ) = (1 -P e,B )P e,B + P e,B (1 -P e,W ) (3.12) where P e,B = v∈D W T Z| X, θ( v| X = 0, θ) and P e,W = v∈D c W T Z| X, θ( v| X = 1, θ). The same development yields:

Figure 3 . 5 :

 35 Figure 3.5: ROC curves for two dierent strategies in case N = 2.10 3 , σ b = σ w = 52

Fig. 3 . 10 - 10 - 6 Figure 3 . 6 :

 31010636 Fig. 3.6 illustrates the gap between the estimation of α and β using the Gaussian approximation and the asymptotic expression or the Monte-Carlo simulations. The Monte-Carlo simulations conrm the fact that the derived Cramér Cherno bounds are tight, and the dierence between the results obtained with the Gaussian approximation are very important especially for close to uniform channels. This sheds light on

Equations (A. 2 )

 2 and (A.1) developed in Appendix A.1 are interesting from the mathematical point of view because each of them merges the cumulant generating function and the Kullback-Leibler divergence in a same formula. Expressions for the tail probabilities α and β of the sum of N r i.i.d random variables expressed in (3.39) and (3.42) may be expressed then by, after pointing that s 1 = s 0 -1:

2 .

 2 Furthermore, for large enough N , the changes of correcting factors 1 |s j | √ N πµ (s j |H j ) (j = 0, 1) in (3.41) and (3.42) are negligible and we drop their analysis.

(4. 29 )

 29 All quantities cov and Var in (4.29) are taken w.r.t the Boltzmann density p s 0 dened in (4.21).

(4. 38 ) 2 m, η 2 , 2 m

 38222 Proof. See in Appendix A.3.In our case, the 100(1-η)% condence region for log β( θ) is Gχ Gχ

(4. 41 )

 41 In order to derive an explicit formula for the third partial derivative of β * ( θ) w.r.t θi 0 at the true parameter θ we need to compute analytically ∂ 2 A( θ) Their expressions are presented in the theorem 8 in Appendix A.4.

∂ 2 ∂ 3

 23 log β( θ) ∂ θi ∂ θj θ= θ ( θiθi )( θjθj ) log β( θ) ∂ θi ∂ θj ∂ θk θ= θ ( θiθi )( θjθj )( θkθk ) (4.42)and this reduces to calculate∂ 3 log β( θ) ∂ θi ∂ θj ∂ θk θ= θ.Remind that we let:

  (a) Histogram of μb (b) Histogram of μw (c) Histogram of σb (d) Histogram of σw

Figure 4 . 1 :

 41 Figure 4.1: Histogram of four estimated parameters μb , σb , μw , σw of true parameters (50, 150, 42, 42) via classical EM algorithm for truncated data. Here, N obs = 10 4 , N iter = 5.10 3 , parameters of the main channel are[START_REF] Anthony Ts Ho | Image content authentication using pinned sine transform[END_REF] 155,[START_REF] Efron | Assessing the accuracy of the maximum likelihood estimator: Observed versus expected sher information[END_REF][START_REF] Efron | Assessing the accuracy of the maximum likelihood estimator: Observed versus expected sher information[END_REF].

. 4 . 2 ,

 42 we can see that the parameter estimations are accurate: the means of estimated parameters are close to the actual parameters and the standard deviations are not important compared with the range of possible values of the model parameters.

  (a) Histogram of μb (b) Histogram of μw (c) Histogram of σb (d) Histogram of σw

Figure 4 . 2 :

 42 Figure 4.2: Histogram of four estimated parameters μb , σb , μw , σw of true parameters (50, 150, 42, 42) via modied EM algorithm for truncated data. Here, N obs = 10 4 , N iter = 5.10 3 , parameters of the main channel are[START_REF] Anthony Ts Ho | Image content authentication using pinned sine transform[END_REF] 155,[START_REF] Efron | Assessing the accuracy of the maximum likelihood estimator: Observed versus expected sher information[END_REF][START_REF] Efron | Assessing the accuracy of the maximum likelihood estimator: Observed versus expected sher information[END_REF].

  (a) Histogram of the second order expansion of log β(α, σb ) via Monte Carlo sampling. (b) Histogram of log β(α, σb ), and the pdf curve via Monte Carlo sampling of the second order expansion.

Figure 4 . 3 :

 43 Figure 4.3: Comparison of histograms of log β(α, σb ) and its second order expansion. Here, θ = (70, 30 2 , 160, 30 2 ), θ = (70, 35 2 , 160, 35 2 ), σb is unknown. N obs = 8.10 3 , N iter = 5.10 3 , N = 2.10 3 , α = 10 -16 .

  (a) Histogram of the second order expansion of log β(α, σw ) via Monte Carlo sampling. (b) Histogram of log β(α, σw ), and the pdf curve via Monte Carlo sampling of the second order expansion.

Figure 4 . 4 :

 44 Figure 4.4: Comparison of histograms of log β(α, σw ) and its second order expansion. Here, θ = (70, 30 2 , 160, 30 2 ), θ = (70, 35 2 , 160, 35 2 ), σw is unknown. N obs = 8.10 3 , N iter = 5.10 3 , N = 2.10 3 , α = 10 -16 .

Figure 4 . 5 :

 45 Figure 4.5: Comparison of the log-form of the probability of type II error β(α, θ) (horizontal line) based on true opponent's parameters θ, the probability of type II error β(α, θ) (dots) based on estimated opponent's parameters θ with their statistical regression (stars) and the analytical line (straight line) for dataset θ = (80, 63 2 , 170, 63 2 ), θ = (85, 65 2 , 160, 65 2 ), supposed that only one parameter μw is unknown by the re- ceiver, i.e, θ = (85, 65 2 , μw , 65 2 ). The vertical straight and dash line show the critical value χ 2 1,0.025 and χ 2 1,0.975 . Here, N obs = 3.10 3 , α = 10 -16 , N iter = 5.10 3 , N = 2.10 3 , ρ = ρ( θ) = ρ( μw ) and γ(α, μw ) = 0.14186.

Figure 4 . 6 :

 46 Figure 4.6: Comparison between three analytical ROC curves C 0.025 min (squares), C 0.975 max (stars) and C mean (circles) with true min ROC curve (dash line), true max ROC curve (red line) and true mean ROC curve (black line) computed directly from N iter = 5000 data of μw .

Figure 4 . 7 :

 47 Figure 4.7: Comparison of the log-form of the probability of type II error β(α, θ) (horizontal line) based on true opponent's parameters θ, the probability of type II error β(α, θ) (dots) based on estimated opponent's parameters θ with their statistical regression (plus) and the analytical line (straight line) for dataset θ = (80, 63 2 , 170, 63 2 ), θ = (85, 65 2 , 160, 65 2 ), supposed that only one parameter μb is unknown by the re- ceiver, i.e, θ = ( μb , 65 2 , 160, 65 2 ). The vertical straight and dash line show the critical value χ 2 1,0.025 and χ 2 1,0.975 . Here, N obs = 2.10 3 , α = 10 -18 , N iter = 5.10 3 , N = 2.10 3 , ρ = ρ( θ) = ρ( μb ) and γ(α, μb ) = 0.20969.

Figure 4 . 10 :

 410 Figure 4.10: Comparison of the log-form of the probability of type II error β(α, θ) (horizontal line) based on true opponent's parameters θ, the probability of type II error β(α, θ) (dots) based on estimated opponent's parameters θ. Here we consider θ = (80, 63 2 , 170, 63 2 ), θ = (80, 60 2 , 170, 60 2 ) and μb , σ2 b , μw , σ2 w are unknown. N obs = 3.10 3 , α = 10 -16 , N iter = 5.10 3 , N = 2.10 3 .

Figure 4 . 8 :

 48 Figure 4.8: Comparison between three analytical ROC curves C 0.025 min (squares), C 0.975 max (stars) and C mean (circles) with true min ROC curve (dash line), true max ROC curve (red line) and true mean ROC curve (black line) computed directly from N iter = 5000 data of μb .

Figure 4 . 9 :Figure 4 . 11 :

 49411 Figure 4.9: Comparison of the log-form of the probability of type II error β(α, θ) (horizontal line) based on true opponent's parameters θ, the probability of type II error β(α, θ) (dots) based on estimated opponent's parameters θ. Here we consider θ = (55, 40 2 , 155, 40 2 ), θ = (50, 42 2 , 150, 42 2 ) and μb , σ2 b , μw , σ2 w are unknown.

  (a) Histogram of the second order expansion of log β(α, θ) via Monte Carlo sampling (see (4.37)). (b) Histogram of log β(α, θ), and the pdf curve via Monte Carlo sampling of the second order expansion.

Figure 4 . 12 :

 412 Figure 4.12: Comparison of histograms of log β(α, θ) and its second order expansion. Here, θ = (55, 40 2 , 155, 40 2 ), θ = (50, 42 2 , 150, 42 2 ), θ is unknown. N obs = 8.10 3 , N iter = 5.10 3 , N = 2.10 3 , α = 10 -16 .

025 andF

 025 β (x 0.975 ) = F β (-18.8928) = 0.975094 ≈ 0.975.

Figure 4 . 13 :

 413 Figure 4.13: Comparison between three analytical ROC curves C 0.025 min (squares), C 0.975 max (stars) and C mean (circles) with true min ROC curve (dash line), true max ROC curve (red line) and true mean ROC curve (black line) computed directly from N iter = 5000 data used in Fig. 4.10 of four estimated parameters μb , σ2 b , μw , σ2 w .

Figure 4 . 14 :

 414 Figure 4.14: Scatter plot of the probability of type II error v.s the Taylor expansion up to the third derivative in case of one estimated parameter μw . The parameters set of the main and opponent channels are dataset θ = (80, 63 2 , 170, 63 2 ) and θ = (85, 65 2 , 160, 65 2 ). Here we use a xed probability of type I error α = 10 -18 and N obs = 2.10 3 , N iter = 5.10 3 , N = 2.10 3 .

Figure 4 . 15 :

 415 Figure 4.15: Scatter plot of the probability of type II error v.s the Taylor expansion up to the third derivative in case of one estimated parameter σw . The parameters set of the main and opponent channels are dataset θ = (80, 63 2 , 170, 63 2 ) and θ = (80, 60 2 , 170, 60 2 ). Here we use a xed probability of type I error α = 10 -16 and N obs = 2.10 3 , N iter = 5.10 3 , N = 2.10 3 .

  (a) log β(α, θ) with estimated μb , μw (b) 3 rd order expansion of log β(α, θ) (c) log β(α, θ) v.s 2 nd order expansion (d) log β(α, θ) v.s 3 rd order expansion

Figure 4 . 16 :

 416 Figure 4.16: Scatter plot of the probability of type II error v.s the Taylor expansion up to the second and the third order in case of two estimated parameters ( μb , μw ). The parameters set of the main and opponent channels are dataset θ = (80, 63 2 , 170, 63 2 ) and θ = (85, 65 2 , 160, 65 2 ). Here we use a xed probability of type I error α = 10 -16 and N obs = 2.10 3 , N iter = 5.10 3 , N = 2.10 3 .

  [START_REF]Global congress addresses international counterfeits threat immediate action required to combat threat to[END_REF].1) for dierent numbers of observations to estimate four unknown parameters of the opponent channel. For each N obs , we use the number of iteration N iter = 5.10 3 . In order to compute the critical points of log β(α, θ) at levels 2.5% and 97.5%, we use the same way as we did in Fig.4.13.

Figure 4 . 17 :

 417 Figure 4.17: The asymptotic property of log 10 β(α, θ) w.r.t the number of observations N obs . Here, θ = (70, 50 2 , 160, 50 2 ) and θ = (70, 52 2 , 160, 52 2 ), α = 10 -16 , N iter = 5.10 3 , N = 2.10 3 .

  β * ≈ 10 -20 b = 2, β * ≈ 10 -32 b = 6, β * ≈ 10 -74

Figure 5 . 1 :

 51 Figure 5.1: Evolution of β(α) w.r.t. σ m (α = 10 -6 ) in case of generalized Gaussian distribution. Main and opponent channels are identical, µ b = 50, µ w = 150.

Fig. 5 .MFigure 5 . 2 :

 552 Fig. 5.3 shows the result of the optimization for dierent setups in the case of truncated Gaussian distributions when the variance is optimized. We can notice the

Figure 5 . 3 :

 53 Figure 5.3: Evolution of β(α) w.r.t. σ m (α = 10 -6 ) in case of Gaussian distributions for dierent setups of main and opponent channels.

Fig. 5 .

 5 Fig. 5.5 shows the evolution of best opponent strategy max σo β(α) w.r.t σ m . This gure reects the purpose of the receiver when he wants to minimize the possibility of getting type II error considering the best setup of the opponent. By comparing it with Fig. 5.1, we can see that the opponent's probability of type II error can be multiplied by one or several orders of magnitude (×10 7 for b = 1, ×10 5 for b = 2 and ×10 for b = 6).

6 Figure 5 . 4 :

 654 Figure 5.4: Evolution of the probability of type II error β(α) w.r.t σ o for dierent σ m in case of generalized Gaussian distribution. The plots arriving from left to right show σ m varying from 20 to 80 with an increment of 10. Here, µ b = 50, µ w = 150, α = 10 -6 .

73 Figure 5 . 5 :

 7355 Figure 5.5: Evolution of best opponent strategy max σo β w.r.t σ m in case of generalized Gaussian distribution. Here, µ b = 50, µ w = 150, α = 10 -6 .

MFigure 5 . 6 :

 56 Figure 5.6: Evolution of best opponent strategy max σo β w.r.t σ m (α = 10 -6 ) in case of

  (a) Evolution β(α) w.r.t σ o for dierent σ m . Here, µ b = μb = 60, µ w = μw = 150. (b) Evolution of best opponent strategy max σo β w.r.t σ m . Here, µ b = μb = 60, µ w = μw = 150.

  (c) Evolution β(α) w.r.t σ o for dierent σ m . Here, µ b = 65, µ w = 170, μb = 70, μw = 160. (d) Evolution of best opponent strategy max σo β w.r.t σ m . Here, µ b = 65, µ w = 170, μb = 70, μw = 160.

Figure 5 . 7 :

 57 Figure 5.7: Left: Evolution β(α) w.r.t σ o for dierent σ m , right: Evolution of the best opponent strategy max σo β. α = 10 -6 .

Figure 5 . 8 :

 58 Figure 5.8: Left: Evolution β(α) w.r.t σ o for dierent σ m , right: Evolution of the best opponent strategy max σo β. α = 10 -6 .

Figure 5 . 9 :

 59 Figure 5.9: Evolution of best opponent strategy max σo β and max σo E(β) w.r.t σ m in case of Gaussian distribution. Here, µ b = μb = 70, µ w = μw = 160, α = 10 -12 . The horizontal line (σ m ≈ 36.5) presents the minimum of max σo E(β). It is very close to the minimum

Figure 5 . 10 :

 510 Figure 5.10: Evolution of best opponent strategy max σo β and max σo E(β) w.r.t σ m in case of Gaussian distribution. Here, µ b = μb = 100, µ w = μw = 140, α = 10 -12 . The minimum of max σo E(β) and the minimum of max σo β are the same.

Figure 6 .

 6 Figure 6.1: ROC curve computed from the test between two nite Markov chains. The size of transition matrices are 500 × 500. Each row of these matrices is generated by uniform distributions in [a, b] (a, b > 0).

Figure 7

 7 Figure 7.1: Eet du processus d'impression acquisition : (a) Code graphique avant impression. (b) Code graphique après impression (les segments autour des coins sont utilisés pour des besoins de synchronisation).

7.1. 3

 3 Liens avec les travaux existants D'autres systèmes d'authentication sont semblables, le plus proche étant celui proposé par Picard et al. [82, 83] . Ce système dière essentiellement par le test d'hypothèse qui est basé dans ce cas ci sur le comptage du nombre d'erreurs des codes acquis puis binarisés. Nous montrons dans la section 3.3 que cette stratégie n'est pas optimale au sens de l'authentication. La sécurité de ce système a été étudiée par Baras et Cayre [18] dans le cadre d'une attaque par lots (attaque où l'adversaire essaye d'estimer le code graphique original à partir d'un lot de code graphiques imprimés). Les auteurs montrent que, même si le système est sensible à ce type d'attaques et que les performances d'authentication sont moindres, la présence d'éléments déterministes mais non inversibles dans le système d'impression permet de garantir la sécurité de ce système. Une autre étude menée par Diong et al. [37] a cherché à inférer la fonction permettant à partir d'éléments du code imprimé de retrouver des éléments du code original. Cette étude a montré qu'il est possible de diminuer l'erreur d'estimation par rapport à l'utilisation d'une binarisation optimale, sans pour autant garantir un taux d'erreur nul. Le caractère non-inversible du procédé d'impression-acquisition n'a donc pas pu être remis en cause. Il existe également d'autres systèmes d'authentication similaires, mais reposant sur des supports diérents. Dans [91] les auteurs proposent un procédé d'authentication utilisant la gravure laser des métaux comme procédé non inversible. Dans [51] le procédé d'authentication repose sur l'enregistrement des structures aléatoires des bres de

Figure 7 . 2 :

 72 Figure 7.2: Description of the works of Estampille project

Figure 7 . 3 :Figure 7 . 4 :

 7374 Figure 7.3: Caractère aléatoire des bres de papier vues sous microscope. [6, 28].

Figure 7 .

 7 Figure 7.4 (b)). Le modèle du contrefacteur pour une valeur de code x donnée est calculé à partir d'un mélange de deux distributions, l'une pour l'impression-acquisition d'un point noir, l'autre pour l'impression-acquisition d'une zone restée blanche et les paramètres de ce mélange sont déterminés à partir de l'erreur commise par le contrefacteur lors de la binarisation du code original. Soit H 0 l'hypothèse traduisant le fait que l'observation du code reçu o N est un code original et soit H 1 l'hypothèse traduisant le fait que l'observation du code reçu o N est un code contrefait. Dans ces conditions, le receveur peut utiliser la stratégie de Neyman-Pearson qui consiste à calculer le rapport de vraisemblance :

Figure 7 . 5 :

 75 Figure 7.5: Comparaison des courbes ROC avec et sans binarisation. Ici l'utilisation directe de codes scannés en niveau de gris permet d'obtenir des performances en authentication bien supérieures. Modèle Gaussien, N = 2.10 3 , σ b = σ w = 52.

10 -80 10 -

 10 67 10 -54 10 -41 10 -28 10 -15 10

Figure 7 . 6 :

 76 Figure 7.6: Comparaison entre l'approximation Gaussienne, l'expression asymptotique et les simulations de Monte-Carlo via échantillonage d'importance dans le cas de distributions Gaussienne généralisées b = 1, b = 2 and b = 6. Les canaux d'impressionacquisition pour l'imprimeur légitime et le contrefacteur sont identiques, µ b = 50, µ w = 150, σ b = 40, σ w = 40.

(7. 7 )

 7 Une étude plus précise de la dérivée troisième montre d'une part que celle-ci est dans la plupart des cas négligeable, d'autre part qu'elle permet d'expliquer en grande partie des diérence entre l'approximation quadratique et les mesures pratiques.7.3.3 Modélisation de la distribution des probabilités de fausse détectionUne fois l'approximation quadratique établie, il est possible de modéliser la distribution des log β en partant du principe qu'un estimateur utilisant une estimation par maximum de vraisemblance ou bien par algorithme EM génère une erreur d'estimation dont les marginales sont Gaussiennes. Après normalisation, il en ressort donc que le terme quadratique de 7.6 se comporte comme une loi χ 2 et donc que log β peut être s'approximer par une loi χ 2 généralisée, comme illustrée sur la Figure7.7.

Figure 7 . 7 :

 77 Figure 7.7: Histogramme et densité de probabilité de log β(α, θ) pour 4 paramètres..

Figure 7 . 8 :

 78 Figure 7.8: Courbes ROC obtenues après l'estimation de quatre paramètres du canal du contrefacteur via l'algorithme EM (modélisation Gaussienne) μb , σ2 b , μw , σ2 w pour dif- férentes statistiques (moyenne, minimum, maximum pour un seuil de conance de 95%) en utilisant les formules litérales en via simulations. Comparaison avec la connaissance des paramètres du canal (courbe True).

Figure 7 . 9 :

 79 Figure 7.9: Evolution de log 10 β(α, θ) en fonction du nombre d'observations N obs , α = 10 -16 .

( 7 . 8 )

 78 Dans le second cas, l'optimisation consiste à résoudre un jeu min max pour deux familles de canaux, l'un appelé C l pour l'imprimeur légitime, l'autre appelé C o pour le contrefacteur. Dans le cas où le receveur connait le canal du contrefacteur, nous cherchons donc la probabilité β * telle que :

( 7 . 9 )

 79 Dans le cas où le receveur doit estimer le canal du contrefacteur, nous utilisons les résultats sur les performances après estimation du canal pour, par exemple, optimiser les performances moyennes E[β(α)], nous cherchons donc la probabilité β * telle que :β * = min C l max Co E[β(α)].

3

 3 Résultats obtenus La gure 7.10 présente un exemple de résultats obtenus dans le scénario qui considère un contrefacteur actif. Nous voyons que pour chacun de ces exemples (ce n'est cependant pas vrai dans tous les cas), la stratégie optimale pour l'imprimeur certiée est d'éviter un procédé d'impression-acquisition peu bruité qui favoriserai une estimation facile du code original par le contrefacteur, mais d'éviter également un procédé trop dégradé pour lequel le bruit important empêcherait la distinction entre code originaux et codes contrefaits. Ces résultats montrent également l'intérêt d'utiliser un canal proche de la loi uniforme, c'est à dire paramètre b grand qui amène un β faible, par rapport à un canal proche d'une loi parcimonieuse, c'est à dire unb faible qui amène un β grand. La gure 7.11 illustre la diérence entre l'optimisation eectuée sans et avec estimation du canal. Nous notons que dans cet exemple la diérence de performance croit en fonction du paramètre σ m mais que le résultat de l'optimisation est peu diérent d'un scénario à l'autre.

73 Figure 7 . 10 :

 73710 Figure 7.10: Evolution de la meilleure stratégie du contrefacteur max σo β en fonction de l'écart type σ m d'une distribution Gaussienne généralisée pour diérents paramètres b de cette distribution. µ b = 50, µ w = 150, α = 10 -6 .

Figure 7 . 11 : 18 P 18 Q

 7111818 Figure 7.11: Comparaisons entre les optimisations max σo β et max σo E(β) en fonction de σ m pour une distribution Gaussienne. Ici, µ b = μb = 70, µ w = μw = 160, α = 10 -12 .

  t ( θ) p t ( θ) where K(t, θ) = t( θ)l( θ)So (A.7) is equivalent to E ps 1 l( θ) ∂K(s 1 , θ) ∂ θ θ= θ -E ps 1 l( θ) E ps 1 ∂K(s 1 , θ) ∂ θ θ= θ = E ps 0 l( θ) ∂K(s 0 , θ) ∂ θ θ= θ -E ps 0 l( θ) E ps 0 ∂K(s 0 , θ) θ)l( θ) + t( θ)l ( θ) (A.9)and using (4.23), it can be shown that (A.8) is equivalent toṡ(i) 1 ( θ) -ṡ(i) 0 ( θ) E ps 0 l 2 ( θ) -E 2 ps 0 l( θ)-E ps 0 l( θ)l i ( θ) -E ps 0 l( θ) E ps 0 l i ( θ

  θ) = E ps 1 l i ( θ) -E ps 0 l i ( θ) , (A.11) from (4.22), we have ∂ 2 β * ( θ) E ps 1 l i ( θ) -E ps 0 l i ( θ) + v∈V l i ( θ) ∂p s 1 ( θ) 1 ( θ) -ṡ(i) 0 ( θ) E ps 0 l( θ)l i ( θ) -E ps 0 l( θ) E ps 0 l i ( θ) -E ps 0 l i ( θ)2 -E 2 ps 0 l i ( θ) .

(A. 13 )

 13 Finally, it is trivial to nish the proof and obtain (4.26).A.3 Proof of proposition 5Below we give the analytical computation stated in preposition 5 for the mean and variance of the quadratic form (4.28):Proof. Let Y = θθ, we have E(Y ) = 0 and E(Y Y T ) = Σ θ . Since Y T H * Y is a scalar,it is equal to its trace, hence:E Y T H * Y = E tr Y T H * Y = E tr H * Y Y T = tr E H * Y Y T

=

  ∂ m l( θ) ∂ θm i θ= θ and if m is equal 1, 2 or 3 then l (m) i 0

  cov(l, l i 0 ) -cov(l i 0 , l i 0 ),

2 [

 2 cov(l, l i 0 ) -cov(l i 0 , l) cov(l, l 2 ) -2E(l)Var(l)]

=θ2 i 0 -B 2 θi 0 2 -θi 0 2 (A. 19 )B 3 ∂ 2 Kθ2 i 0 -∂ 2 KB 4 θi 0 2 -θi 0 2 (A. 21 )B 5 θi 0 2 -θi 0 2 .(A. 23 )

 02221932024222152223 B 1 ( θ) -B 3 ( θ) + B 2 ( θ) -B 4 ( θ) + 2 B 6 ( θ) -B 5 ( θ) (A.17) where B 1 ( θ) = E ps 1 l i 0 ( θ) ∂ 2 K(s 1 ( θ), θ) ∂ E ps 0 l i 0 ( θ) ∂ 2 K(s 0 ( θ), θ) ( θ) = E ps 1 l i 0 ( θ) ∂K(s 1 ( θ), θ) ∂ E ps 0 l i 0 ( θ) ∂K(s 0 ( θ), θ) ∂ ( θ) = E ps 1 l i 0 ( θ) E ps 1 (s 1 ( θ), θ) ∂ E ps 0 l i 0 ( θ) E ps 0 (s 0 ( θ), θ) ( θ) = E ps 1 l i 0 ( θ) E ps 1 ∂K(s 1 ( θ), θ) ∂ E ps 0 l i 0 ( θ) E ps 0 ∂K(s 0 ( θ), θ) ∂ ( θ) = E ps 1 ∂K(s 1 ( θ), θ) ∂ θi 0 E ps 1 l i 0 ( θ) ∂K(s 1 ( θ), θ) ∂ θi 0 -E ps 0 ∂K(s 0 ( θ), θ) ∂ θi 0 E ps 1 l i 0 ( θ) ∂K(s 0 ( θ), θ) ∂ θi 0 (A.22) B 6 ( θ) = E ps 1 l i 0 ( θ) E ps 1 ∂K(s 1 ( θ), θ) ∂ E ps 0 l i 0 ( θ) E ps 0∂K(s 0 ( θ), θ) ∂ At θ = θ, using (4.23) and (A.14) we have:

2 ( 2 E 2 (A. 25 )B 3 2 - 2 E

 22225322 ps 0 l i 0 ( θ)l 2 ( θ)+ 2s 0 ( θ) ṡ(i 0 ) 1 ( θ) -ṡ(i 0 ) 0 ( θ) E ps 0 l( θ) l i 0 ( θ) ) E ps 0 l i 0 ( θ) 3 -2 ṡ(i 0 ) 1 ( θ)E ps 0 l( θ) l i 0 ( θ) ( θ) = E ps 0 l i 0 ( θ) s(i 0 ) 1 ( θ) -s(i 0 ) 0 ( θ) E ps 0 l( θ) -E ps 0 l i 0 ( θ) + 2 ṡ(i 0 ) 1 ( θ) -ṡ(i 0 ) 0 ( θ) E ps 0 l i 0 ( θ) (A.26) B 4 ( θ) = E ps 0 l i 0 ( θ) ṡ(i 0 ) 1 ( θ) ps 0 l 2 ( θ) + 2s 0 ( θ) ṡ(i 0 ) 1 ( θ) -ṡ(i 0 ) 0 ( θ) E ps 0 l( θ)l i 0 ( θ) ) E ps 0 l i 0 ( θ) 2 -2 ṡ(i 0 ) 1 ( θ)E ps 0 l( θ)l i 0 ( θ)

2 E 2 E

 22 ps 0 l( θ) ps 0 l i 0 ( θ)+ 2s 0 ( θ) ṡ(i 0 ) 1 ( θ) -ṡ(i 0 ) 0 ( θ) E ps 0 l( θ) E ps 0 l i 0 ( θ) )E ps 0 l( θ) E ps 0 l i 0 ( θ) 2 .

== 2 cov(l i 0 , l 2 )

 22 B 1 ( θ) -B 3 ( θ) + B 2 ( θ) -B 4 ( θ) + 2 B 6 ( θ) -B 5 ( θ) B 1 ( θ) -B 3 ( θ) + B 2 ( θ) -B 4 ( θ) + 2 B 6 ( θ) -B 5 ( θ) = s(i 0 ) 1 ( θ) -s(i 0 ) 0 ( θ) cov(l, l i 0 ) + 2 ṡ(i 0 ) 1 ( θ) -ṡ(i 0 ) 0 ( θ) Var(l i 0 ) -cov(l i 0 , l i 0 ) -2E(l)cov(l, l i 0 )

(A. 33 )

 33 So, (ii) is proven.

v∈V l i 0 2 v∈V 34 )Fom 2 1

 02342 ( θ)p s 1 ( θ) + At θ = θ, from (A.11), the above equation is equivalent to: (iii) and (iv), we can calculate exactlys(i 0 ) 1 ( θ) -s(i 0 ) 0 ( θ). (v) In our analysis, we suppose that α * ( θ) = 2 N log α( θ) is xed, hence log α * ( θ) is xed and so ∂ log α * ( θ) ∂ θi 0 = 0. (A.36)From using (4.8), we can express: -2s 0 ( θ) .

(A. 46 )A. 5 +∂ 2 ∂ 2

 46522 Finally, using (i)-(vi) in the above theorem, we can easily obtain the explicit formula for∂ 3 β * ( θ)The third order expansion of log β(α, θ) -multiple parametersIn order to compute∂ 3 β * ( θ) ∂ θi ∂ θj ∂ θk θ= θ,we follow the same steps as in the case of computing∂ 3 β * ( θ) ∂ θ3 i 0θ= θ with some modication. First, generally we have:∂ 3 β * ( θ) ∂ θi ∂ θj ∂ θk = ṡ(j) 1 ( θ) E ps 1 l ik ( θ) -E ps 0 l ik ( θ) + v∈V l i ( θ) 1 ( θ) E ps 1 l ij ( θ) -E ps 0 l ij ( θ) + v∈V l i ( θ) s 1 ( θ) E ps 1 l ijk ( θ) -E ps 0 l ijk ( θ) + v∈V l ij ( θ) ps 1 ( θ) ∂ θj ∂ θk -ps 0 ( θ) ∂ θj ∂ θk + s(ij) 1 ( θ) E ps 1 l i ( θ) -E ps 0 l i ( θ) .

(A. 47 )∂ 2 ∂ 2

 4722 Thus at θ = θ, using lemma 1 we similarly get:∂ 3 β * ( θ) ∂ θi ∂ θj ∂ θk θ= ps 1 ( θ) ∂ θj ∂ θk -ps 0 ( θ) ∂ θj ∂ θk θ= θ (A.48)where for x = 0, 1∂p sx ( θ) x , θ) ∂ θu p sx ( θ) p sx ( θ) u = j, k and ∂ 2 ps x ( θ) ∂ θj ∂ θk = p sx ( θ) ∂ 2 K(sx, θ) ∂ θj ∂ θk -v∈V ∂ 2 K(sx, θ) ∂ θj ∂ θk p sx ( θ) + ∂K(sx, θ) , θ) ∂ θk p sx ( θ) ∂K(sx, θ) ∂ θj -v∈V ∂K(sx, θ)∂ θj p sx ( θ) .

= ∂ log β ∂s 0 -λ ∂ log α ∂s 0 =+ N c E ∂ log p 0 ∂θ 0 = 0 + E ∂ log p 0 ∂θ 0 .= 0 + E ∂ log p 0 ∂θ 0 .=-E ∂ log p 0 ∂θ 0 + -λs 2 0 0 + λE ∂ log p 0 ∂θ 0 .(A. 66 )..(A. 70 )= s 0 l 2 p+ E ∂ 2 log p 0 ∂θ 2 0+ s 0 cov l , ∂ log p 0 ∂θ 0 + Var ∂ log p 0 ∂θ 0 .(A. 78 ).

 00000002006670220078 , l i ) -cov(l i , l j ) , l j ) -cov(l j , l k ) v∈V l k ( θ)∂ps 1 ( θ) , l k ) -cov(l k , l j ) , l ij ) -cov(l k , l ij ) l ik ) -cov(l j , l ik ) l u )Var(l) , u = j, k(A.51) ∂F (s 0 ,θ 0 ,λ) ∂s 0 N c [1 -s 0 + λs 0 ] Var [l(θ 0 )] . 0 )p s 0 (θ 0 ) -s 0 v∈V l(θ 0 ) ∂ps 0 (θ 0 ) ∂θ 0 + v∈V s 0 l (θ 0 )p s 0 (θ 0 ) + v∈V ∂ log p 0 ∂θ 0 p s 0 (θ 0 ) = -s 0 v∈V s 0 l(θ 0 )l (θ 0 )p s 0 (θ 0 ) + v∈V ∂ log p 0 ∂θ 0 p s 0 (θ 0 ) + s 0 v∈V l(θ 0 )p s 0 (θ 0 ) v∈V s 0 l (θ 0 )p s 0 (θ 0 ) -s 0 v∈V l(θ 0 ) ∂ log p 0 ∂θ 0 p s 0 (θ 0 ) + s 0 v∈V l(θ 0 )p s 0 (θ 0 ) v∈V ∂ log p 0 ∂θ 0 p s 0 (θ 0 ) , (A.63)hence (for the sake of simplicity we drop out the index of parameter θ 0 )∂ log α ∂θ 0 = N c s 0 -s 0 E [ll ] + s 0 E [l] E [l ] -E l ∂ log p 0 ∂θ 0 + E [l] E ∂ log p 0 ∂θ 0 N c -s 2 0 cov(l, l ) -s 0 cov l, ∂ log p 0 ∂θ N c E [l ] -(s 0 -1)s 0 cov(l, l ) -(s 0 -1)cov l, ∂ log p 0 ∂θ -N c {-E [l ] + (s 0 -1)s 0 cov(l, l ) + (s 0 -1)cov l, ∂ log p 0 ∂θ 0 cov(l, l ) -λs 0 cov l, ∂ log p 0 ∂θFrom (A.62) we easily get:∂F (s 0 ,θ 0 ,λ) ∂θ 0 = N c E [l ] + 1 s 0 E ∂ log p 0 ∂θ 0 (s 0 ,θ 0 ,λ) ∂λ = N c D KL (p s 0 p 0 ) + log α 0 . (A.68)From (A.61), (A.67), (A.68) and (A.56), it reduces to solve the following system of non-linear equations: c D KL (p s 0 p 0 ) -log α 0 = 0s 0 E [l ] + E ∂ log p 0 solve (A.[START_REF] Mclachlan | The EM algorithm and extensions[END_REF], we rst try to use Newton-Raphson method, hence we need to compute the Jacobian matrix. Let's call:f (s 0 , θ 0 ) = -N c D KL (p s 0 p 0 ) -log α 0 g(s 0 , θ 0 ) = s 0 E [l ] + E ∂ log p 0 ∂θ 0Similar to (A.59), we get:∂f (s 0 , θ 0 ) ∂s 0 = -N c s 0 Var [l(θ 0 )] , (A.71)and we can easily obtain:∂g(s 0 , θ 0 ) ∂s 0 = E [l ] + s 0 cov(l, l ) + cov l, ∂ log p 0 ∂θ 0 . (A.72)Now we have only compute ∂f (s 0 ,θ 0 ) ∂θ 0 and ∂g(s 0 ,θ 0 ) ∂θ 0 . From (A.64), we have:∂f (s 0 , θ 0 ) ∂θ 0 = N c -s 2 0 cov(l, l ) -s 0 cov l, ∂ log p 0 ∂θ 0 + E ∂ log p 0 ∂θ 0 . s 0 -l p s 0 E [s 0 l ] + l ∂ log p 0 ∂θ 0 p s 0 -l p s 0 E ∂ log p 0 ∂θ 0 (A.75) hence v∈V l (θ 0 ) ∂p s 0 (θ 0 ) ∂θ 0 = s 0 Var [l ] + cov l , ∂ log p 0 ∂θ 0 ..74), (A.76) and (A.77), we obtain: ∂g(s 0 ,θ 0 ) ∂θ 0 = s 0 E [l ] + s 0 Var [l ] + cov l , ∂ log p 0 ∂θ 0 From (A.71), (A.73), (A.72) and (A.78) we obtain the explicit formula of the Jacobian matrix of the problem (A.70) as: J = ∂f (s 0 ,θ 0 ) ∂s 0∂f (s 0 ,θ 0 ) ∂θ 0 ∂g(s 0 ,θ 0 ) ∂s 0 ∂g(s 0 ,θ 0 ) ∂θ 0

table Notations

 Notations

	Chapter 1
	Introduction
			Interpretation
	α
	1.1	Motivations.
	1.2	The Estampille pro ject
		1.2.1	Participant organizations
		1.2.2	The authentication setup in Estampille
	1.3	Sketch of the thesis
	1.4	Publications related to the thesis

  is the same for each type of data X, and consequently, µ i|x (s | H j ) = µ x (s | H j ), i.e. µ i|x (s | H j ) is independent from i for each type of data x.

	The
	RHS in (3.36) and (3.37) can be simplied as

  γ 2 ,

		(4.58)
	where χ 2 4,γ 1	and χ 2 4,γ 2

are critical values w.r.t γ 1 and γ 2 , i.e., Pr[ρ( θ) ≤ χ 2 4,γ 1 ] = γ 1 and Pr[ρ( θ) ≤ χ 2 4,γ 2 ] = γ 2 .

  Y N |X N v N x N où X N est le vecteur aléatoire représentant le code original et Y N le vecteur aléatoire représentant le code original imprimé, d'autre part le modèle statistique d'impression-acquisition des codes contrefaits P Z N |X N v N x N où Z N est le vecteur aléatoire représentant le code contrefait. Ces deux hypothèses se traduisent pratiquement par le fait que si les codes sont imprimés dans des conditions constantes (même papier, même encre, même imprimante, ...) à la fois chez l'imprimeur légitime et le contrefacteur, il sera possible d'estimer précisément les modèles d'impression-acquisition. Nous supposons que ces deux modèles d'impression-acquisition sont i.i.d., et notre méthodologie peut s'appliquer pour diérentes distributions comme par exemples des modèles Gaussien ou Lognormaux (voir

	7.2 Authentication et tests d'hypothèses
	7.2.1 Principes du système d'authentication
	Dans un premier temps, nous sommes partis de l'hypothèse que le receveur a en sa
	connaissance :
	d'une part le modèle statistique d'impression-acquisition des codes imprimés origi-
	naux P

  .1) et à décider H 0 ou H 1 en comparant ce rapport à un seuil λ garantissant une probabilité de non détection minimale pour une probabilité de fausse alarme inférieure à un niveau la connaissance du canal d'impression du contrefacteur et qu'elle se traduit par un comptage du nombre d'erreurs entre le code observé et le code original.

	α :
		H 1
	L	≷	λ.
		H 0
	7.2.2 Calcul précis des probabilités d'erreur
	La probabilité de fausse alarme α, c'est à dire la probabilité de détecter un code original
	comme faux, s'exprime comme :

(7.2) Nous avons dans un premier temps comparé deux types d'observations, le premier suppose que le receveur binarise le code observé avant de calculer son test d'hypothèse, alors que le second type suppose que c'est l'image scannée en niveau de gris qui est directement utilisée comme observation o N . Nous avons montré que la stratégie consistant à utiliser un code binaire n'est pas optimale dans le sens où pour une probabilité de fausse alarme donnée, la probabilité de non-détection d'un code contrefait est plus importante qu'avec l'utilisation d'un code scanné en niveau de gris. Par contre, d'un point de vue pratique cette stratégie peut comporter plusieurs avantages puisqu'elle ne nécessite pas

  || θ -θ|| 2 et le logarithme de la probabilité de non-détection log β, nous avons cherché à l'expliquer en analysant le développement limité de log β pour des erreurs d'estimation faibles. Pour cela nous avons calculé la dérivée première, seconde et troisième intervenant dans le développement. De part l'optimalité du test pour une erreur d'estimation nulle, il est facile de montrer que la dérivée première est nulle. Les variations par rapport à l'erreur quadratique et celle du troisième ordre nécessitent l'utilisation de la distribution de Boltzmann p s 0 ( θ) au point s 0 (voir équation (4.21)), et en introduisant le rapport de vraisemblance l( θ) = log p 1 (v | θ)/p 0 (v | θ) nous obtenons la dépendance quadratique suivante :

	tème, ou encore les performances minimales ou maximales pour un taux de conance
	donné.
	7.3.2 Relation entre l'erreur d'estimation et la probabilité de
	fausse détection
	Après avoir constater une relation quasi-linéaire entre le carré de l'erreur d'estimation
	7.3 Impact de l'estimation du canal du contrefacteur
	sur les performances d'authentication
	7.3.1 Cadre et objectifs de l'étude
	Dans la section précédente nous faisions l'hypothèse que les systèmes d'impression-
	acquisition de l'imprimeur légitime et du contrefacteur étaient tous les deux connus.
	Nous prenons maintenant le cas plus réaliste où le modèle de l'imprimeur légitime reste
	connu, mais où celui du contrefacteur reste à estimer. Dans ce scénario, le receveur
	cherche, à partir d'un ensemble de N obs codes contrefaits qu'il a en sa possession, à
	estimer les paramètres du modèle d'impression-acquisition du contrefacteur.
	Puisque les paramètres d'estimation sont entachés d'une erreur, nous cherchons ici

à quantier l'impact de cette erreur d'estimation sur les performances globales du système d'authentication, l'objectif étant pour une probabilité de fausse alarme donnée, de calculer les performances moyennes en terme de probabilité de non-détection du sys-

  = t i 0 ( θ)l( θ) + t( θ)l i 0 ( θ) = t i 0 ( θ)l( θ) + 2t i 0 ( θ)l i 0 ( θ) + t( θ)l i 0 ( θ)

	∂ 2 pt( θ) ∂ θ2 i 0	= p t ( θ) ∂ 2 K(t, θ) ∂ θ2 i 0	-	v∈V	∂ 2 K(t, θ) i 0 ∂ θ2	p t ( θ)
			+ ∂K(t, θ) ∂ θi 0	2	-	v∈V	∂K(t, θ) ∂ θi 0	2	p t ( θ)
			-2	v∈V	∂K(t, θ) ∂ θi 0	p t ( θ) ∂K(t, θ) ∂ θi 0	-	v∈V	∂K(t, θ) ∂ θi 0	p t ( θ) .
			∂ θi 0	=	∂K(t, θ) ∂ θi 0	-
	we then have
	∂K(t, θ)
	∂ θi 0
	∂ 2 K(t, θ) i 0 ∂ θ2								(A.14)
	∂K(t, θ) ∂ θ	2	= t i 0 ( θ)	2	l 2 ( θ) + t 2 ( θ) l i 0 ( θ)	2	+ 2l( θ)l i 0 ( θ)t( θ)t i 0 ( θ)

θ) = t( θ)l( θ)

and ∂p t ( θ) v∈V ∂K(t, θ) ∂ θi 0 p t ( θ) p t ( θ), where t i 0 ( θ) = ∂t( θ) ∂ θi 0 , t i 0 ( θ) = ∂ 2 t( θ) ∂ θ2 i 0 and l i 0 ( θ) = ∂l( θ) ∂ θi 0 , l i 0 ( θ) = ∂ 2 l( θ) ∂ θ2 i 0

. Moreover, we obtain the general formula for the second derivative of p t ( θ) w.r.t θi 0 as:

Jiddu Krishnamurti

Acknowledgments

Firstly, I want to express my sincere gratitude to the everybody in the jury: two reviewers Prof. Lionel Fillatre and Prof. William Puech, the President of the jury Prof. Philippe VanHeeghe, the examiner Dr. François Cayre, and my two advisors Dr.

A. [START_REF]Global congress addresses international counterfeits threat immediate action required to combat threat to[END_REF] The third order expansion of log β(α, θ) -one parameter A. [START_REF]Counterfeiting and piracy endangers global economic recovery, say global congress leaders[END_REF] The third order expansion of log β(α, θ) -multiple parameters A.6 Constrained optimization using Lagrange multiplier method Appendix usually means "small outgrowth from large intestine," but in this case it means "additional information accompanying main text." Or are those really the same things? Think carefully before you insult this book.

Pseudonymous Bosch

A.1 Boltzmann's distributions and probabilities of error Proposition 6. We always have for any s ∈ (0, 1):

Similarly we can obtain :

It is able to see:

We know that at θ = θ, v∈V l( θ)

From (A.36), we have:

Consequently,

and (v) is proven.

(vi) From (A.10), we get:

and so

From (v) and (vi), we can rewrite:

where

0 is computed by using:

The condition (A.53) comes from the fact that we use the same threshold for the hypothesis testing. Note that similar to (A.52), we also have:

All E, Var and cov are taken w.r.t the Boltzmann's distribution p s 0 ( θ).

A.6 Constrained optimization using Lagrange multiplier method

We remind that the Lagrange multiplier function of the passive game (5.4) is dened as:

In order to solve the problem (5.4), we need to solve a system of non-linear equations below:

First we have nd the explicit formulas for the partial derivatives of F (s 0 , θ 0 , λ) w.r.t s 0 , θ 0 and λ respectively. Remember that log α and log β can be performed as (see (4.7)):

Using (A.4), we then have: Nous étudions dans cette thèse l'inuence d'un système d'authentication utilisant des codes graphiques 2D modiés lors de l'impression par un procédé physique non-clônable. Un tel procédé part du principe qu'à très haute résolution le système d'impression acquisition peut être modélisé comme un processus stochastique, de part le caractère aléatoire de la disposition des bres de papiers, de mélange des particules d'encre, de l'adressabilité de l'imprimante ou encore du bruit d'acquisition. Nous considérons un scénario où l'adversaire pourra estimer le code original et essaiera de le reproduire en utilisant son propre système d'impression. La première solution que nous proposons pour arriver à l'authentication est d'utiliser un test d'hypothèse à partir des modèles à priori connus et sans mémoire des canaux d'impression-acquisition de l'imprimeur légitime et du contrefacteur. Dans ce contexte nous proposons une approximation able des probabilités d'erreur via l'utilisation de bornes exponentiels et du principe des grandes déviations. Dans un second temps, nous analysons un scénario plus réaliste qui prends en compte une estimation a priori du canal du contrefacteur et nous mesurons l'impact de cette étape sur les performances du système d'authentication. Nous montrons qu'il est possible de calculer la distribution des probabilité de non-détection et d'en extraire par exemple ses performances moyennes. La dernière partie de cette thèse propose d'optimiser, au travers d'un jeu minmax, le canal de l'imprimeur légitime an de maximiser ses performances d'authentication tout en envisageant une attaque au pire des cas de la part du contrefacteur.

Mots-clefs : authentication, codes graphiques, tests d'hypothèses, probabilités d'erreurs, théorie de l'estimation Performance Analysis of an Authentication Method relying on Graphical Codes Abstract:

We study in this thesis the impact of an authentication system based on 2D graphical codes that are corrupted by a physically unclonable noise such as the one emitted by a printing process. The core of such a system is that a printing process at very high resolution can be seen as a stochastic process and hence produces noise, this is due to the nature of dierent elements such as the randomness of paper bers, the physical properties of the ink drop, the dot addressability of the printer, etc. We consider a scenario where the opponent may estimate the original graphical code and tries to reproduce the forged one using his printing process in order to fool the receiver. Our rst solution to perform authentication is to use hypothesis testing on the observed memoryless sequences of a printed graphical code considering the assumption that we are able to perfectly model the printing process. The proposed approach arises from error exponent using exponential bounds as a direct application of the large deviation principle. Moreover, when looking for a more practical scenario, we take into account the estimation of the printing process used to generate the graphical code of the opponent, and we see how it impacts the performance of the authentication system. We show that it is both possible to compute the distribution of the probability of non-detection and to compute the average performance of the authentication system when the opponent channel has to be estimated. The last part of this thesis addresses the optimization problem of the printing channel controlled by the legitimate manufacturer in order to maximize his ability to detect a forged graphical code within a min-max game.

Key words : authentication, graphical codes, hypothesis testing, error probabilities, estimation theory