Hélène Le Bouder

Thierno Barry

Damien Couroussé

Jean-Louis Lanet

Ronan Lashermes

A template attack against VERIFY PIN algorithms

Keywords: Template attack, Side Channel Analysis, Electromagnetic Emission, VERIFY PIN Algorithm, Embedded Systems' Security

This paper presents the first side channel analysis from electromagnetic emissions on VERIFY PIN algorithms. To enter a PIN code, a user has a limited number of trials. Therefore the main difficulty of the attack is to succeed with very few traces. More precisely, this work implements a template attack and experimentally verifies its success rate. It becomes a new real threat, and it is feasible on a low cost and portable platform. Moreover, this paper shows that some protections for VERIFY PIN algorithms against fault attacks introduce new vulnerabilities with respect to side channel analysis.

INTRODUCTION

In many smart cards, a Personal Identification Number (PIN or PIN code) is used to authenticate the user. These PIN codes are used, for example, in payment cards or SIM cards. Hence, they are targets of choice for malicious adversaries. When discussing about the security of embedded devices, a critical aspect is: the interaction of the computing unit with its physical environment. This interaction is used by physical attacks.

State of the art.

The physical attacks are mainly divided in two families: the Side Channel Analysis (SCA) and the Fault Injection Attacks (FIA).

FIA consist in disrupting the circuit behavior (with EM pulse, laser, clock glitch...). VERIFY PIN algorithms are designed to resist FIA such as (Moro et al., ; Riviere et al., ).

SCA are based on observations of the circuit behavior during the computation. They exploit the fact that some physical values of a circuit depend on intermediary values of the computation. This is the socalled information leakage of the device. The most classic leakages are timing [START_REF] Kocher | Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems[END_REF], power consumption (Mangard et al., 2008a;[START_REF] Mangard | A simple power-analysis (SPA) attack on implementations of the AES key expansion[END_REF] and electromagnetic emissions (EM) [START_REF] Quisquater | Electromagnetic analysis (EMA): Measures and counter-measures for smart cards[END_REF]. VERIFY PIN algorithms are designed to resist timing attacks [START_REF] Foo Kune | Timing attacks on pin input devices[END_REF]. To the best of our knowledge, there is no published work on EM analysis against VERIFY PIN algorithms.

In this paper we are interested in statistical categorizations more precisely template attacks. Templates were introduced as the strongest side channel attack possible from an information theoretic point of view [START_REF] Chari | Template attacks[END_REF]. They have been used in many attacks, such as [START_REF] Archambeau | Template attacks in principal subspaces[END_REF][START_REF] Elaabid | Template Attacks with a Power Model[END_REF][START_REF] Oswald | Template attacks on masking-resistance is futile[END_REF][START_REF] Rechberger | Practical template attacks[END_REF] since.

Motivation.

The most classical SCA are Correlation Power Analysis (CPA) [START_REF] Brier | Correlation Power Analysis with a Leakage Model[END_REF]. In these attacks many traces are required to break the secret. But in a PIN code, a user has a limited number of trials, so an attacker can exploit only a few EM traces. This is a major difficulty, which explains why there are no known CPA attacks on PIN codes. The ultimate goal of our work is to test the resistance of a VERIFY PIN against a SCA with only few traces. That is why we are interesting by Template attacks.

Contribution.

This paper presents what is, to the best of our knowledge, the first EM SCA attack on VERIFY PIN algorithms. We have chosen to study template attacks because they can be effective with only one trace.

Template analyzes are statistical categorizations divided in two steps: a profiling phase and an attack phase. Because of this, the attacker can perform the first phase ahead of time. And then the attack phase becomes extremely fast because only few traces are used. The experimental bench can be purchased at a very low cost and can be portable.

Additionally this paper shows that some countermeasures against FIA can introduce new vulnerabilities in SCA.

Organization.

This paper is organized as follows. The section 2 describes the target implementation. The attack is detailed in section 3. The experimental set-up and the results are presented in section 4. Finally the conclusion is drawn in section 5.

IMPLEMENTATION OF THE TARGET: VERIFY PIN ALGORITHM

In our settings, a PIN code is an array of 4 bytes indexed by b (b ∈ [[0, 3]]), where each byte can take up to 10 values. The set of these values is noted K = [[0, 9]]. So, there are 10 4 different PIN codes.

A PIN code is used to authenticate a user. A particular PIN, called true PIN, noted U is embedded in the smart card, and only its rightful owner knows this true PIN value. The protocol to authenticate a user is as follows. A user proposes a PIN called candidate PIN, noted V , to the device (smart-card). A VERIFY PIN algorithm compares the candidate PIN and the true PIN. A candidate PIN is valid if and only if it is equal to the true PIN (U = V ). In that case, the user is authenticated. end for 17:

Algorithm 1 Simplified VERIFY PIN 1: procedure VERIFY PIN(candidate PIN V ) 2: counter = counter -1 3: if counter > 0 then 4: status = COMPARISON(U,V ) 5: status 2 = COMPARISON(U,V ) 6: if status =
return status 18: end procedure In theory, the correct user should always propose a valid candidate PIN, but a human error is still possible. That is why in practice, in a VERIFY PIN algorithm, the user has several trials, number noted C. Usually it is 3 in a SIM card or a payment card, but it is possible that more tries are authorized, for example in an electronic lock. In the device, there is a ratification counter which decreases when a failed candidate PIN is tested. This counter is reset to the original value when a valid candidate PIN is proposed. If it is equal to zero, the device is blocked; nobody can use it again. We emphasize the fact that an attacker has to keep a trial to be authenticated. It is of no interest to retrieve a PIN code if the device is blocked.

In our attack, the implementation of VERIFY PIN proposed by [START_REF] Riviere | Sécurité des implémentations logicielles face aux attaques par injection de faute sur systemes embarqués[END_REF] is chosen. This implementation respects the verifications of [START_REF] Folkman | The use of a power analysis for influencing PIN verification on cryptographic smart card[END_REF]. But, to clarify our description only a very simplified version is described in Algorithm 1.

A classic countermeasure against FIA is to compare the candidate PIN with the true PIN twice, as in Algorithm 1 at line 4 and line 5. This countermeasure doubles the opportunities of leakage on COM-PARISON, as shown in the Table 1.

In our case, the attacker focuses on leakages from the COMPARISON algorithm. The algorithm used in this paper is described in COMPARISON Algoritm 2.

To resist the timing attack [START_REF] Foo Kune | Timing attacks on pin input devices[END_REF][START_REF] Kocher | Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems[END_REF], the comparison between the true PIN U and the candidate PIN V has to be in a constant time. All bytes have to be compared even if the previous bytes are false. The computation time for a valid candidate PIN or a false candidate PIN has to be the same.

Implementation C = 2 C = 3 1 COMPARISON 1 trace 2 traces 2 COMPARISON 2 traces 4 traces

DESCRIPTION OF THE ATTACK

Preliminaries

Generally template attacks are used against cryptosystems, but to the best of our knowledge, it is the first time they are tested with a VERIFY PIN algorithm.

To implement a template attack, a pair of identical devices is needed. One is called the profiling device, the attacker has full control of it; and the other is the targeted device.

The first step, called profiling phase, is to build a physical model of the EM traces for all possible secret values with the profiling device. A model for one value is called a template. After that, the attack phase starts by obtaining traces on the targeted device. These traces are confronted to the different templates.

In our attack, it is assumed that the attacker has the same device as the targeted device, where true PIN is known. She can obtain all the desired measurements on the profiling device, only a valid candidate PIN is proposed after every other candidate PIN. Namely she can:

• obtain one trace on the targeted device;

• change the true PIN in her profiling device;

• obtain many traces on her profiling device.

In this way, it is possible to build a template attack on VERIFY PIN algorithms.

The attack is divided in two parts and six steps. The profiling phase is split in:

1. Campaign on the profiling device, 2. Detection of the points of interest, 3. Building templates.

The attack phase is split in: 4. Campaign on the targeted device, 5. Confrontation between measurements, 6. Discrimination of one guess.

In this template attack, 3 PIN codes are considered. The true PIN in the targeted device is noted U and the true PIN in the profiled device is noted U . The goal of the attack is to learn U. The candidate PIN is the same in the profiling phase and in the attack phase and it is noted V .

In SCA a divide and conquer approach is generally chosen; so in this case only one secret byte is retrieved at a time. So the target is a byte

U b . A guess on a byte U b (b ∈ [[0, 3]]) is noted k ∈ K; and v denotes the value of V b .

The profiling phase

Step 1: Campaign on the profiling device. The profiling phase consists in collecting many traces on the profiling device, for the purpose of building templates. A campaign is for one given byte b.

• The byte U b of the true PIN takes all values k in K and the other PIN bytes stay to zero.

• The candidate PIN byte V b is always fixed to a chosen value v.

For each guess k, the attacker acquires a campaign of n curves with a true PIN byte U b fixed to k and candidate PIN byte fixed to v,

(U b = k and V b = v).
Step 2: Detection of points of interest.

A window of points of interest, denoted PoI, is a set of points of a trace such as information on the secret can be retrieved from them. They are the moment of information leakage. The first step of the traces treatment is to detect the PoI. In our case, it is first to detect in the VERIFY PIN, when the COMPARISON (Algorithm 2) is computed.

To respect a divide and conquer approach, the second step is to find where each comparison for each byte occurs in a trace of COMPARISON.

A time window is selected for each byte to perform the template attack byte per byte. If this step is not performed, in the best case, the attacker can retrieve the values of all the bytes but she cannot put them in the right order, so the attack fails. Generally it is possible to detect the PoI where the difference between the means of the template traces are the most significant or using variance analysis as in (Linge et al., ). In our implementation the bytes of a candidate PIN V are tested one after another. So, in practice a trigger signal is put around the COMPARISON and the traces are split in 4.

Step 3: Building templates. In this paragraph, the attacker has selected a good PoI window on traces for each byte, to respect a divide and conquer approach.

The attacker obtains a matrix M v,k = xk (i, j) , with i ∈ [[0, n]] and j ∈ [[0, p]]; n is the number of traces and p the number of points in a trace. The column vector j of M v,k is noted xk j and xk j is the mean of this vector. The mean vector is noted xk = xk j .

xk j = 1 n n ∑ i=1 xk i, j .
Template attacks apply advanced statistical methods. However, in this paper the optimizations presented in [START_REF] Choudary | Efficient template attacks[END_REF], are used.

The first step is to compute the covariance matrix S v,k , a square matrix of size p • p. The elements of S v,k = sk ( j, j ) are computed with equation (1) 1 .

sk ( j, j ) = 1 n -1 • xk j -xk j t xk j -xk j .
(1)

Attack phase

Step 4: Campaign on the targeted device.

During this step the attacker obtains one trace such that:

• the value of the true PIN byte U b is unknown, it is the target;

• the candidate PIN byte V b is equal to v.
The trace is a vector T v = {xt j } j∈[[0,p]] of p points. Of course T v corresponds at a good windows of PoI.

Step 5: Confrontation between measurements.

The goal of the attack is to confront the trace T v to the template matrix S v,k .

In SCA, it is classic to suppose that the electronic noise at each point of a power trace is normally distributed as described in [START_REF] Mangard | Power analysis attacks: Revealing the secrets of smart cards[END_REF]. So the probability density function f v , given S v,k and xk is computed with (2) 2 .

f v T v |S v,k , xk = 1 √ 2π p •|S v,k | • exp -1 2 • T v -xk • S -1 v,k • T v -xk t .
(2) As explained in [START_REF] Choudary | Efficient template attacks[END_REF], several problems appear when implementing the template attack, so our attack follows their given advices. The logarithm is used for the multivariate normal distribution in (3),

1 M t means transposed of M. 2 |M| is the determinant of M F v (T v , k) = ln f v T v |S v,k , xk = -1 2 • ln (|S v,k |) + T v -xk • S -1 v,k • T v -xk t + c .
(3) where c is a constant, c = -p • ln (2π) .

(4)

Moreover, the logarithm of the determinant is computed with the equation ( 5),

ln (|S v,k |) = 2 * ∑ d ii∈diag(D) ln(d ii ) ; ( 5
)
where D is the Cholesky decomposition of S v,k :

S v,k = D t • D .
One has to remark than D can be pre-computed in the profiling phase. In this paper, this way is used to compute F v .

Step 6: Discriminating guesses.

The attack returns the guess k v for which F v is maximal for a given T v . This guess maximizes F v as in equations ( 6). Let max -1 be the function that returns the fiber of the maximum.

max k∈K (F v (T v , k)) = F v (T v , k v ) max -1 k∈K (F v (T v , k)) = k v . (6)
The attack succeeds if the guess, noted k v defined in ( 6) is equal to the real value of U b . It is possible to rank the guesses k according to the value of F v (T v , k). If the attack fails, it shows how well the correct value U b is ranked.

EXPERIMENTAL RESULTS

Acquisition protocol of EM traces

Once the theoretical framework has been setup, an experimental benchmark was performed. The VER-IFY PIN algorithm is implemented on an ARMbased STM32-F100RB micro-controller embedding a Cortex-M3 core and running in our case at 24MHz. The board used is the STM32VLDICOVERY. This chip does not embed any countermeasures against side channels but it is a popular choice for Internet Of Things (IoT) applications.

The experimental bench is composed of a control computer, a 3405A Picoscope and an EM probe. The experimental bench is described in Fig. 1.

1. The STM32 sends (via an USB/UART FTTDI232) that it is ready to test a PIN code, to the computer.

2. Still via the UART, the computer sends the PIN candidate to the STM32. The EM probe from Langer (RF-R0,3-3) is used to measure the signal. This last one is amplified by a Preamplifier from Langer (PA 303), before the measurements by the Picoscope 3405A (USB oscilloscope). The bandwidth of the measurement setup is limited by the Picoscope with an upper frequency of 100MHz. The traces obtained are composed of p = 3700 points, with a 1GS/s sampling rate. We remind that 100MHz is a cutoff frequency marking an attenuation of the relevant signal, not its total removal.

One has to remark that the required equipment comes at a very low cost, under 2000 excluding the computer.

The computation heavy step is the profiling phase. The program is written with the language (Bezanzon et al., ), which is particularly efficient for computing-intensive tasks. Considering the large size of the covariance matrices, the computation requires a lot of memory. To create 10 templates (for guesses in K = [[0, 9]], of size n = 400000 traces, we have used a server with 16 cores and 128GB of RAM, where the computation lasted 4 hours (64 core-hours). It is however possible to manage the computation of the covariance matrix computation in smaller tasks in order to reduce memory consumption, at the expense of an increased computation time.

Results

Intermediate results

To start this section, results on only one trace of VERIFY PIN, so 1 or 2 trace(s) on COMPARISON Algorithm 2, are studied.

For each value v ∈ K, and each value of k, we have built a template S v,k with matrix M v,k of size n = 100000 traces and p = 3700 points. Results for 10000 attacks, on a byte U b , are in Tables 3 and2. These preliminaries results on only one trace are important for the three following points. In the case where U b = V b , the success is less pertinent, but the attacker can eliminate the guess k = v. The figure Fig. 3 shows this result for a successful attack, where U b = 3 and v = 0. The results are normalized to the same scale to compare with the first case Fig. 2.

1 trace of COMPARAISON v U b ∈ K U b = v U b = v 0 27
Moreover we have focused on results of templates v = 0 and v = 1. For v = 1, some values taken by U b have a very high probability to be retrieved and others a very small one. At the opposite, for v = 0, all values U b = 0 have a probability of around 20% to be retrieved. We conclude that v = 0 is more useful. A consequence of using templates with a zero candidate PIN byte (v = 0), is that the attacker does not need to know the COMPARISON function at the hardware level.

F 0 (T 0 , k 0 ) = 0 8: k = max -1 k∈K (F 0 (T 0 , k)) see equation (6). 9: v = k v 10:
end whilereturn k 11: end procedure

The attacker uses a first template S 0 , k. If k 0 = 0, the template used for the next trace is for v = k 0 (the value returned by the result of the analysis of the first trace). There are two possibilities: the new template confirms the result and the attack on this byte succeeds; or it does not confirm it. If the second template S k 0 ,k does not confirm k 0 , the attacker uses the tem-plate where 0 is the preimage of the second maximum of F 0 (T 0 ) after k 0 . In other words, the attacker can test all values of v according to the rank of the guesses in the first template attack with v = 0.

Final results

The rank of the correct guess k = U b for one trace on VERIFY PIN is given in Table 4 For example, with a template of size n = 400000, the correct guess is the first in 32.91% and second in 16.28% of the analyses. So if the attacker has only two traces the attack has a success rate of 32.91 + 16.28 = 48.38%.

Final results of our attack are in Table 5. One has to remark that if the implementation of VERIFY PIN has two calls to COMPARISON, the success rate increases.

The results are given for one byte, to have the success rate for the whole PIN, the results have to be put to the power of the number of bytes. success for PIN = success for 1 byte number of bytes .

For example, with a template of size n = 400000, 4 trials (C = 4) so 3 traces, and a VERIFY But whatever the number of bytes in the PIN code, the attack always succeed in at most 8 traces.

CONCLUSION

In this paper, we have presented the first SCA attack with EM traces on VERIFY PIN algorithms. It is an application of template attacks to a situation where very few traces are available.

Indeed, we have shown that we can always retrieve a PIN code with 8 traces (9 trials), whatever the number of bytes in the PIN code.

For a classical PIN code with 4 bytes in a VER-IFY PIN with 3 trials, our attack has a success rate of 48.38% per byte, so finally 5.48% for the whole PIN. For a classical PIN code with 4 bytes in a VER-IFY PIN with 4 trials, our attack has a success rate of 60.88% per byte, so finally 13.74% for the whole PIN. These results are not optimal, but the experimental set-up used is very low cost; moreover the biggest template managed had a size of n = 400000 traces. With a better measurement setup and bigger templates, results should be drastically improved. So we can imagine that an attacker with a better equipment (a high bandwidth oscilloscope and a better computation power to manage more than 400000 traces) can have better results.

Furthermore, an attacker can combine this attack with other information. For example in [START_REF] Andriotis | A pilot study on the security of pattern screenlock methods and soft side channel attacks[END_REF], the authors detect the print touch on a phone.

Another important remark is that the double Comparison of the PIN code to protect against FIA introduces new vulnerabilities for SCA.

By using templates, the attack is made portable. The attacker can perform the profiling phase ahead of time. Then on the target location, the measures and the analysis are fast as only a few traces are required. Moreover, she can easily perform batch attacks where multiple targets are attacked with the same templates.

For all these points, our attack is a real threat.

A countermeasure against our attack could be to compare the different bytes in a random order. The attacker can retrieve the PIN but not in the right order; so for example, for a PIN code with 4 bytes, with 4 different values, there is 4! = 24 possibilities. In most cases, this number of possibilities is too big to be authenticated before the device gets blocked. In future works, we plan to test the practical application of this countermeasure.

  3. A trigger signal measured by the Picoscope meansthat the STM32 tests the PIN candidates.4. The probe and the Picoscope measure the EM leakage and store the traces.5. The Picoscope sends the traces to the computer.

Figure 1 :

 1 Figure 1: Experimental bench

Figure 2 :

 2 Figure 2: Results for a targeted true PIN byte U b = 0, a candidate PIN byte v = 0

Figure 3 :

 3 Figure 3: Results for a targeted true PIN byte U b = 3, a candidate PIN byte v = 0. The second picture is a zoom of the first without the result for guess 0.

  status 2 then

		Algorithm 2 Comparison of two PIN codes
		1: procedure COMPARISON(candidate PIN V , true
		PIN U)
	7:	ERROR, device is blocked
	8:	else
	9:	if status = TRUE then
	10:	counter initialized at original
		value: C
	11:	end if
	12:	end if
	13:	else
	14:	device is blocked
	15:	end if
	16:	return status
	17: end procedure

Table 1 :

 1 Number of traces corresponding to COMPARISON, obtained by the attacker according to the implementation of VERIFY PIN, C is the number of trials.

Table 2 :

 2

		.7	17.7	100
	1	34.33	24.33	100
	2	22.49	12.49	100
	3	20.52	10.52	100
	4	21.12	11.12	100
	5	21.75	11.75	100
	6	21.5	11.5	100
	7	25.23	15.23	100
	8	20.61	10.61	100
	9	24.38	14.38	100
	0	31.71	21.71	100
	1	34.13	24.13	100
	2	21.28	11.28	100
	3	20.94	10.94	100
	4	20.68	10.68	100
	5	22.00	12.00	100
	6	21.71	11.71	100
	7	27.12	17.12	100
	8	21.35	11.35	100
	9	26.37	16.37	100

Success rate (in percents) according to different values of V b and U b , for template size n = 100000, results computed for 10 • 1000 attacks. 2 traces of COMPARAISON v U b ∈ K U b = v U b = v

Table 3 :

 3 Success rate (in percents) according to different values of V b and U

b , for template size n = 100000, results computed for 10 • 1000 attacks.

Table 4 :

 4 Percentage of the rank of the correct guess k = U b for the different sizes of template, statistics are for 10000 attacks.

			.
		1 trace of COMPARAISON
	rank of k \ n 100000 20000 40000
	1	27.70	29.28 29.56
	2	13.77	14.99 14.55
	3	12.37	12.52 11.89
	4	10.15	10.62 10.88
	5	9.08	9.25	9.08
	6	8.26	7.25	8.08
	7	7.18	6.77	6.54
	8	6.28	5.33	5.51
	9	5.21	3.99	3.91
	10	0.0	0.0	0.0
		2 traces of COMPARAISON
	rank of k \ n 100000 20000 40000
	1	31.71	32.72 32.91
	2	14.85	16.8	16.28
	3	11.26	12.44 13.25
	4	9.94	10.09 10.38
	5	8.87	8.44	8.35
	6	7.73	7.04	6.64
	7	6.32	5.7	5.63
	8	5.44	4.18	3.96
	9	3.88	2.59	2.60
	10	0.0	0.0	0.0

Table 5 :

 5 Success rate to retrieve a byte U b according to the size n of the templates and the number and the choice of traces PIN with two COMPARISON, the success rate is 0.6088 4 ≈ 0.1374 thus 13.74%.

Acknowledgment This work was partially funded by the French National Research Agency (ANR) as part of the program Digital Engineering and Security (INS-2013), under grant agreement ANR-13-INSE-0006-01. The authors would like to thank Thibault Cattelani and Gaël Thomas for their helpful comments and discussions.


Amine Mrabet

Nadia El-Mrabet

Ronan Lashermes

Jean-Baptiste Rigaud

Belgacem Bouallegue

Sihem Mesnager

Mohsen Machhout

High-performance Elliptic Curve Cryptography by Using the CIOS Method for Modular Multiplication

Keywords: Hardware Implementation, ECC, Modular Multiplication, Montgomery Algorithm, CIOS method, Systolic Architecture, DSP48, FPGA

Elliptic Curve Cryptography (ECC) is becoming unavoidable, and should be used for public key protocols. It has gained increasing acceptance in practice due to the significantly smaller bit size of the operands compared to RSA for the same security level. Most protocols based on ECC imply the computation of a scalar multiplication. ECC can be performed in affine, projective, Jacobian or others models of coordinates. The arithmetic in a finite field constitutes the core of ECC Public Key Cryptography. This paper discusses an efficient hardware implementation of scalar multiplication in Jacobian coordinates by using the Coarsely Integrated Operand Scanning method (CIOS) of Montgomery Modular Multiplication (MMM) combined with an effective systolic architecture designed with a two-dimensional array of Processing Elements (PE). As far as we know this is the first implementation of such a design for large prime fields. The proposed architectures are designed for Field Programmable Gate Array (FPGA) platforms. The objective is to reduce the number of clock cycles of the modular multiplication, which implies a good performance for ECC. The presented implementation results focuses on various security levels useful for cryptography. This architecture have been designed in order to use the flexible DSP48 on Xilinx FPGAs. Our architecture for MMM is scalable and depends only on the number and size of words.

Introduction

The search for the most optimised architecture for arithmetic has always fascinated the embedded system world. In recent years this has been especially the case in finite fields for cyber security due to the invention of asymmetric encryption systems based on modular arithmetic operations. Throughout the history of cryptography for embedded systems, there has been a need for efficient architectures for these operations. The implementations must be cost-effective, both in terms of area and latency. Finite field arithmetic is the most important primitive of ECC, pairing and RSA. Since 1976, many Public Key Cryptosystems (PKC) have been proposed and all these cryptosystems base their security on the difficulty of some mathematical problem. The hardness of this underlying mathematical problem is essential for security. Elliptic Curve Cryptosystems which were proposed by Koblitz [9] and Miller [START_REF] Miller | Use of elliptic curves in cryptography[END_REF], RSA [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF] and the Pairing-Based Cryptography [START_REF] Joux | A one round protocol for tripartite diffie-hellman[END_REF] are examples of PKCs. All these systems require an efficient finite field multiplication. As a consequence, the development of efficient architecture for modular multiplication has been a very popular subject of research. In 1985, Montgomery has presented a new method for modular multiplication [START_REF] Montgomery | Modular multiplication without trial division[END_REF]. It's one of the most suitable algorithm for performing modular multiplications in hardware and software implementations. The efficient implementation of the Montgomery Modular Multiplication (MMM) in hardware was considered by many authors [START_REF] Hariri | Bit-serial and bit-parallel montgomery multiplication and squaring over gf[END_REF][START_REF] Huang | An optimized hardware architecture for the montgomery multiplication algorithm[END_REF][START_REF] Iwamura | Systolic-arrays for modular exponentiation using montgomery method[END_REF][START_REF] Ors | Hardware implementation of a montgomery modular multiplier in a systolic array[END_REF][START_REF] Perin | Montgomery modular multiplication on reconfigurable hardware: Systolic versus multiplexed implementation[END_REF][START_REF] Tenca | A scalable architecture for montgomery multiplication[END_REF]. There is a variety of ways to perform the MMM, considering if multiplication and reduction are separated or integrated. A systolic array architecture [START_REF] Kung | Why systolic architectures?[END_REF][START_REF] Vucha | Design and fpga implementation of systolic array architecture for matrix multiplication[END_REF] is one possibility for the implementation of the Montgomery algorithm in hardware, with a design both parallel and pipelined [START_REF] Hariri | Bit-serial and bit-parallel montgomery multiplication and squaring over gf[END_REF][START_REF] Ors | Hardware implementation of a montgomery modular multiplier in a systolic array[END_REF][START_REF] Perin | Montgomery modular multiplication on reconfigurable hardware: Systolic versus multiplexed implementation[END_REF][START_REF] Reymond | A hardware pipelined architecture of a scalable montgomery modular multiplier over gf(2m)[END_REF][START_REF] Tenca | A scalable architecture for montgomery multiplication[END_REF]. A similar work [START_REF] Reymond | A hardware pipelined architecture of a scalable montgomery modular multiplier over gf(2m)[END_REF] has been done for binary fields (field characteristic is a power of 2) without having to deal with carry propagation as a consequence. These architectures use a Processing Elements (PE) array where each Processing Element performs arithmetic additions and multiplications. In accordance with the number of words used, the architecture can employ a variable number of PEs. The systolic architecture uses very simple Processing Elements (as in a pipeline). As a consequence, the systolic architecture decreases the needs for logic elements in hardware implementations. Our contribution is to combine a systolic architecture, which is assumed to be the best choice for hardware implementations, with the CIOS method of Montgomery modular multiplication. We optimize the number of clock cycles required to compute a n-bit MMM and we reduce the utilization of FPGA resources. We have implemented the modular multiplication in a fixed number of clock cycles. To the best of our knowledge, this is the first time that a hardware or a software multiplier of modular Montgomery multiplication, suitable for various security level, is performed in just 33 clock cycles. Furthermore, as far as we know, our work is the first one dealing with systolic architecture and CIOS method over large prime characteristic finite fields. Using our efficient MMM hardware implementation, we propose an efficient design for ECC operations: point addition and doubling. This paper is organized as follows: Section 2 discusses related state-of-the-art works. Section 3 presents the CIOS method of Montgomery Modular Multiplication algorithm. The proposed architectures and results are presented in Section 4 and Section 5. Finally, the conclusion is drawn in Section 6.

State of the art

Elliptic Curve Cryptography

The use of elliptic curves in cryptography has been independently introduced by Victor S. Miller [START_REF] Miller | Use of elliptic curves in cryptography[END_REF] and N. Koblitz [START_REF] Koblitz | Elliptic curve cryptosystems[END_REF] during the 80s. The main advantage of ECC is that the bit sizes of the key are reduced for the same security level when comparing with a classical RSA algorithm [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF]. For instance, at the AES 128-bit security level the key for ECC is 256 bits, while RSA requires a 3072-bit key. The main operation in ECC is the scalar multiplication over the elliptic curve. This scalar multiplication consists in computing α × P , for α an integer and P a point of an elliptic curve. When such an operation is implemented on an embedded system such as a FPGA, it is subject to constraints of area and speed. Efficient scalar multiplication arithmetic is hence a central issue for cryptography. The interested reader is referred to [START_REF] Hankerson | Guide to elliptic curve cryptography[END_REF] for a good overview of the question.

ECC preliminaries Let E be an elliptic curve defined over F p with p > 3 according to the following short Weierstrass equation:

E : y 2 = x 3 + ax + b (1)
where a, b ∈ F p such that 4a 3 + 27b 2 = 0. The elliptic curve E(F p ) is the set of points (x, y) ∈ F 2 p whose coordinates satisfy Equation 1. The rational points of E, augmented with a neutral element O called point at infinity, have an abelian group structure. The associated addition law computes the sum of two points in affine coordinates P = (x 1 , y 1 ) and Q = (x 2 , y 2 ) as P + Q = (x 3 , y 3 ) where:

x 3 = λ 2 -x 1 -x 2 and y 3 = λ(x 1 -x 3 ) -y 1 with λ =      y 2 -y 1 x 2 -x 1 if P = Q, 3x 2 1 + a 2y 1 if P = Q. (2)
The scalar multiplication of a point P by a natural integer α is denoted αP . The discrete logarithm problem is finding the value of α, given P and αP . The security of ECC is based on the hardness of the discrete logarithm problem. Point addition formulae such as in Equation 2 are based on several operations over F p (e.g. multiplication, inversion, addition, and subtraction) which have different computational costs.

ECC in Jacobian coordinates

In Jacobian coordinates, we use (x : y : z) to represent the affine point (x/z 2 ; y/z 3 ). The elliptic curve equation becomes:

Y 2 = X 3 + aXZ 4 + bZ 6 .
Doubling step: we represent the point

Q ∈ E(F p ) in Jacobian coordinates as Q = (X Q , Y Q , Z Q ).
The formulae for doubling T = 2Q = (X T , Y T , Z T ) can be computed as:

X T = 9X 4 Q -8X Q Y 2 Q . Y T = 3X 2 Q (4X Q Y Q -X T ) -8Y 4 Q . Z T = 2Y Q Z Q . Adding step: let Q = (X Q , Y Q , Z Q ) and T = (X T , Y T , Z T ) ∈ E(F p ). Then the point R = T + Q = (X R , Y R , Z R ), can be computed as: X R = (2Y Q Z 3 T -2Y T ) 2 -4(X Q Z 2 T -X T ) 3 -8(X Q Z 2 T -X T ) 2 X T . Y R = (2Y Q Z 3 T -2Y T )(4(X Q Z 2 T -X T ) 2 X T -X R ) -8Y T (X Q Z 2 T -XT ) 3 . Z R = 2Z T (X Q Z 2 T -X T ).
Algorithm 1: Scalar Multiplication

Input: α = (αnαn-1 . . . α1α0)2 radix 2 decomposition ∈ Fp, P ∈ E(Fp) Output: αP 1 T ← P 2 for i = n -1 to 0 do 3 T ← 2T 4 if αi = 1 then 5 T ← T + P 6 return T 3 Our architecture for MMM (CIOS Method)
The Coarsely Integrated Operand Scanning (CIOS) method presented in Algorithm 2, improves the Montgomery Algorithm by integrating the multiplication and reduction. More specifically, instead of computing the product a • b, then reducing the result, this method allows an alternation between iterations of the outer loops for multiplication and reduction. The integers (p, a and b) are seen as lists of s words of size w. This algorithm requires an array T of size only s + 2 to store the intermediate state. The final result of the CIOS algorithm is composed by the s + 1 least significant words of this array at the end.

Algorithm 2: CIOS algorithm for Montgomery multiplication [START_REF] Koç | Analyzing and comparing montgomery multiplication algorithms[END_REF]

Input: p < 2 K , p = -p -1 mod 2 w , w, s , K = s • w :bit length, R = 2 K , a, b < p Output: a • b • R -1 mod p 1 T ← 0; 2 for i ← 0 to s -1 do 3 C ← 0; 4 for j ← 0 to s -1 do 5 (C, S) ← T [j] + a[i] • b[j] + C α cell 6 T [j] ← S 7 (C, S) ← T [s] + C 8 T [s] ← S    α f cell 9 T [s + 1] ← C 10 m ← T [0] • p mod 2 w β cell 11 (C, S) ← T [0] + m • p[0] 12 for j ← 1 to s -1 do 13 (C, S) ← T [j] + m • p[j] + C γ cell 14 T [j -1] ← S 15 (C, S) ← T [s] + C 16 T [s -1] ← S    γ f cell 17 T [s] ← T [s + 1] + C
The alternation between multiplications and reductions is possible since the value of m (in line 11 of the Algorithm 2) in the i th iteration of the outer loop for reduction depends only on the value T [0], which is computed by the first iteration of the corresponding inner loop. In order to perform the multiplication, we have modified the CIOS algorithm of [START_REF] Koç | Analyzing and comparing montgomery multiplication algorithms[END_REF] and designed this method with a systolic architecture. Indeed, instead of using an array to store the intermediate result, we replace T by input and output signals for each Processing Element. As a consequence, our design uses fewer multiplexers decreasing as a consequence the number of slices taken by our design.

Hardware Implementation

Block DSP in Xilinx FPGAs

Modern FPGA devices like Xilinx Virtex-4, Virtex-5 and Artix-7 as well as Altera Stratix FPGAs have been equipped with arithmetic hardcore extensions to accelerate digital signal processing applications. These DSP blocks can be used to build a more efficient implementation in terms of performance and reduce at the same time the demand for area. DSP blocks can be programmed to perform basic arithmetic functions, multiplication, addition and subtraction of unsigned integers. Figure 1 shows the generic DSP structure in advanced FPGAs. DSP can operate on external input A,B and C as well as on feedback values from P or result PCIN.

Proposed Architecture

The idea of our design is to combine the CIOS method for the MMM presented in [START_REF] Koç | Analyzing and comparing montgomery multiplication algorithms[END_REF] with a two-dimensional systolic architecture in the model of [START_REF] Lee | Algorithm and VLSI architecture design for H.264/AVC Inter Frame Coding[END_REF][START_REF] Reymond | A hardware pipelined architecture of a scalable montgomery modular multiplier over gf(2m)[END_REF][START_REF] Vucha | Design and fpga implementation of systolic array architecture for matrix multiplication[END_REF]. As seen in section 3, the CIOS method is an alternation between iterations of the loops for multiplication and reduction. The concept of the two-dimensional systolic architecture presented in Section 2 combines Processing Elements with local connections, which take external inputs and handle them with a predetermined manner in a pipelined fashion. This new architecture is directly based on the arithmetic operations of the CIOS method Figure 2: data dependency in general systolic architecture. of Montgomery Algorithm. The arithmetic is performed in a radix-w base (2 w ). The input operands are processed in s words of w bits. We present many versions of this method. We illustrate our design for s = 16 architecture, denoted NW-16 (for Number of Words). We describe it in detail as well as the various Processing Element behaviours. In order to have less states in our Final State Machine (FSM), we divided our Algorithm 2 of Montgomery in five kinds of PEs (α, β, γ, α f , γ f ). Our efficient architecture comes from the fact that the data dependency in the CIOS algorithm allows to perform several operations in parallel. Figure 2 presents the dependency of the different cells. Below we describe precisely each cell. The letters MSW stand for the Most Significant Word and LSW for the Least Significant Word. In our notation the letter C denote the MSW of the result and the letter S the LSW.

α cell The α cell corresponds to lines 5 and 6 of Algorithm 2. Its operations are described in Algorithm 3. Notice how registers are embedded into the cell, avoiding in this manner

Algorithm 3: α cell Input: a[i], b[j], CIn(= C), SIn(= T [j]) Output: COut, SOut 1 t1 ← SIn + CIn 2 t2 ← a[i] • b[j] 3 t3 ← t2 + t1 4 COut ←MSW(t3) 5 SOut ←LSW(t3) 6 return COut, SOut
the usage of an external memory. This cell corresponds to one iteration of the first inner loop. As such it must be used several times in a row (the number of iterations in the inner loop). This chain of α cells is terminated by an α f cell (alpha final) corresponding to lines 7, 8 and 9 of Algorithm 2. Once the first α cell (for each outer loop) is computed, data is available for the β cell (it requires T [0]). It is preferable to consume this data as soon as it is available as to minimize memory usage.

Input: SIn(= T [0]), p , p[0] Output: COut, SOut 1 t1 ← SIn • p 2 m ←LSW(t1) 3 t2 ← p[0] • m 4 t3 ← SIn + t2 5 COut ←MSW(t3) 6 return COut, m
second inner loop with γ cells.

γ cell The γ cell corresponds to one iteration of the second inner loop. As such these cells must be chained so as to complete the whole second inner loop. For each cell in this chain,the same m value is required. Value that is changed for each outer loop iteration (m is computed by the β cell). Since a new m value may be computed before the end of the γ chain, the value must be propagated along the cells in the same chain. Its operations are described in Algorithm 6.

Algorithm 6: γ cell

Input: CIn(= C), SIn(= T [j]), m, p[j] Output: COut, SOut 1 t1 ← SIn + CIn 2 t2 ← m • p[j] 3 t3 ← t1 + t2 4 COut ←MSW(t3) 5 SOut ←LSW(t3) 6 return COut, SOut, m
γ f cell Finally, the γ f cell terminate each γ cell chain. It consists in two additions as shown in Algorithm 7. The difference with the α f cell is that in this case both output Algorithm 7: γ f cell

Input: CIn(= C), S1In(= T [s]), S2In(= T [s + 1]) Output: COut(= T [s]), SOut(= T [s -1]) 1 t1 ← S1In + CIn 2 t2 ←MSW(t1) 3 SOut ←LSW(t1) 4 COut ←LSW(S2In + t2) 5 return COut(= T [s]), SOut(= T [s -1])
values S and C are used in the rest of the computation. C is used by the α f cell and S by an α cell.

Our architectures

Firstly, we will start with the NW-16 architecture which contains 6 PEs of type alpha and 6 of type gamma. An MMM can be performed with this architecture in 66 clock cycles. Similarly, in order to implement the NW-32 architecture and the NW-64 architecture it is required to double the number of cells each time. We provide a comparison of our architectures at the end of this section.

NW-16 Architecture

In this architecture, the operands and the modulo are divided in 16 words. The NW-16 architecture is designed in the same way as the NW-32 an NW-64. This example illustrates the scalability of our design. The NW-16 architecture is composed of 15 Processing Elements distributed in a two-dimensional array, where every Processing Elements are responsible for the calculus involving w-bit words of the input operands.

The 15 Processing Elements are divided like this: 6 α cells, 1 α f cell, 1 β cell, 6 γ cells et 1 γ f cell. As said previously, the number of other PE type (α f , β, γ f ) remains unchanged whatever the number of words in the design. In order to evaluate the number of clock cycles of the NW-16 architecture, the first parameter is 6 = max{number of α cells, number of γ cells}, implying that our algorithm requires to loop s + 6 times. We can perform the multiplication with our design in 66 clock cycles since our design requires three states (66 = 3 × (s + 6)). The different results of this architecture for bit-length 256 are given in Table 1.

Architectures comparison

The Table 2 shows a comparison between the different architectures. The number of clock cycles for every architecture is equal to 3 × (s + nb), such that nb = max{number of α cells, number of γ cells}, implying that our algorithm ECC algorithms when implemented in a sequential way have the advantage that the number of finite field arithmetic modules can be reduced to a minimum. For example, only one adder, one multiplier and one subtraction unit (can be an adder) are needed for point addition and doubling. Parallelization between multiplication, addition and subtraction was achieved. We proposed in Figure ?? and Figure ?? the dataflow graphs for point addition and doubling. In this design we use our efficient systolic architecture of MMM to perform squaring or multiplication. The Table 4 summarizes the implementation results of the scalar multiplication. We present a results with both NW-8 and NW-16 architectures. To check the correctness of the hardware results, we compare the results given by the FPGA with sage software implementation.

Experimental Results

The Table 3 summarizes the FPGA post-implementation results for the proposed versions of MMM architectures. We present results for NW-16 architecture. The designs were described in a hardware description languages (VHDL) and synthesized for Artix-7 and Virtex-5 Xilinx FPGAs. We present the different results after implementation of bitlength k which are given in Table 3. As it is shown in Table 3, an interesting property of our design is the fact that the clock cycles are independent from the bit length. This property gives to our design the advantage of suitability to different security level. In order to implement the modular Montgomery multiplication for fixed security level, we must choose the most suitable architecture. The results presented in this work are compared with the previous work [START_REF] Harris | An improved unified scalable radix-2 montgomery multiplier[END_REF][START_REF] Huang | New hardware architectures for montgomery modular multiplication algorithm[END_REF][START_REF] Ors | Hardware implementation of a montgomery modular multiplier in a systolic array[END_REF][START_REF] Perin | Montgomery modular multiplication on reconfigurable hardware: Systolic versus multiplexed implementation[END_REF] in the Table 3. We can notice that our results are better than [START_REF] Perin | Montgomery modular multiplication on reconfigurable hardware: Systolic versus multiplexed implementation[END_REF] considering every point of comparison i.e. the number of slice and the number of clock cycles. Considering the number of slices, we recall that [START_REF] Perin | Montgomery modular multiplication on reconfigurable hardware: Systolic versus multiplexed implementation[END_REF] used an external memory to optimize the number of slices used by their algorithms. Considering the comparison with [START_REF] Ors | Hardware implementation of a montgomery modular multiplier in a systolic array[END_REF], our design requires less slices and can ran at a better frequency, without considering the huge progress in the number of clock cycles. Our design performed the MMM in 66 clock cycles for the 512 and 1024 bit length corresponding to AES-256 and AES-512 security level, while [START_REF] Ors | Hardware implementation of a montgomery modular multiplier in a systolic array[END_REF] performed the multiplication in 1540 clock cycles for the AES-256 security level and 3076 for the AES-512 security level.

Conclusion

In this paper we have presented an efficient hardware implementation of the CIOS method of MMM over large prime characteristic finite fields F p . We give the results of our design after routing and placement using a Artix-7 and Virtex-5 Xilinx FPGAs. Our systolic implementations is suitable for every implementation implying a modular multiplication, for example RSA, ECC and pairing-based cryptography. Our architectures and the designs were matched with features of the FPGAs. The NW-16 design presented a good performance considering latency × area efficiency. This architecture can run for all the bit length corresponding to classical security levels (128, 256, 512 or 1024 bits) in just 66 clock cycles. Our systolic design using this method CIOS is scalable for any other number of words. Then we showed that using this multiplier, it is possible to achieve an efficient scalar multiplication.

Figure 1 :

 1 Figure 1: Structure of DSP block in modern FPGA device.

α

  f cell The α f cell corresponds to the end of the first inner loop. It is just an addition as shown in Algorithm 4.Algorithm 4: α f cell Input: CIn(= C), SIn(= T [s]) Output: COut(= T [s + 1]), SOut(= T [s]) 1 t1 ← SIn + CIn 2 COut ←MSW(t1) 3 SOut ←LSW(t1) 4 return COut, SOutβ cell The β cell is used to compute the m value for each outer loop as well as the first special iteration of the second inner loop. Its operations are described in Algorithm 5. Once the β cell computation has been done, it now becomes possible to compute the Algorithm 5: β cell

Figure 3 :

 3 Figure 3: Proposed Montgomery modular multiplication architecture of NW-16.

Figure 4 :

 4 Figure 4: DFG for the point addition algorithm.

Figure 5 :

 5 Figure 5: DFG for the point doubling algorithm.

Table 1 :

 1 Implementations of cells and MMM (NW-16). require to loop s + nb times. It is interesting to notice that all our architectures are scalable and can target the different security levels useful in cryptography.

	Artix-7	DSP Frequency Clock cycles
	MMM (s=16/K=256)	29	146	66
	α	2	379	1
	γ	2	379	1
	β	2	453	1
	α f	1	460	1
	γ f	2	443	1
	CIOS	s=8	s=16	s=32	s=64
	K=256	32	16	8	4
	K=512	64	32	16	8
	K=1024	128	64	32	16
	K=2048	256	128	64	32
	Clock cycles= 3 × (s + nb) 33	66	132	264
	Number of cells	6 +3 12 +3 24 +3 48 +3

Table 2 :

 2 Comparison of our architectures

	4.4 ECC implementation

Table 3 :

 3 Comparaison of our work with state-of-art implementations.

					Xilinx FPGAs
		Our works A7 Our works V5 [19] V5	[18] VE [5] VII [4] VII [14] V [1] K7 and V5
		512	1024	512	1024	512 1024 512 1024 1024 1024 512 1024 512 K7 512 V5
	Freq	106	65	97	65	95 130 95.2 95.6 116.4 72.1 79.2 176	123
	Cycles	66	66	66	66	96 384 1540 3076 1088 1167 -	-	66	66
	Speed µs 0.622 1.013 0.680 1.015 1.010 2.953 16.031 32.021 9.34 9.80 -	-0.374 0.536
	Slice Reg 2164	4208 3046	6072 3876 6642 -	-	-	-	-	-5076 4960
	Slice LUTs 1789 5242 1781 5824	-	-2972 5706 9319 9271 3125 6243 8757 10877
	BRAM	0	0	0	0	128 256	-	-	-	-	-	-	0	0
				Slice	DSPs		BRAM	Freq		Slice FF		Slice LUT
		NW-8 (256)	3745	33		12	98		8281		9722
		NW-16 (256)	3770	34		12	130		8313		9255
		NW-8 (512)	7066	92		23	59		16500		20394
		NW-16 (512)	7116	60		23	74		16501		19199

Table 4 :

 4 Implementations of ECC (Jacobian) in Xilinx FPGA.


Xavier Descombes
email: xavier.descombes@inria.fr

Multiple objects detection in biological images using a Marked Point Process Framework

Keywords: Marked Point Process, object detection, biological imagery

The marked point process framework has been successfully developed in the field of image analysis to detect a configuration of predefined objects. The goal of this paper is to show how it can be particularly applied to biological imagery. We present a simple model that shows how some of the challenges specific to biological data are well addressed by the methodology. We further describe an extension to this first model to address other challenges due, for example, to the shape variability in biological material. We finally show results that illustrate the MPP framework using the "simcep" algorithm for simulating populations of cells.

Introduction

Detecting multiple instances of a given object from images is a major issue in computer vision as it often represents the first step towards image understanding and interpretation. For example, in remote sensing, the description of land cover (especially when dealing with high resolution images) relies on a previous detection of objects in the scene such as buildings, trees or roads. In computational biology this problem also appears frequently in order to evaluate, characterize or classify a population of biological objects such as cells, vesicles within cells or RNA/protein complexes [START_REF] Forero | Image Processing Methods for Automatic Cell Counting In Vivo or In Situ Using 3D Confocal Microscopy[END_REF][START_REF] Smal | Quantitative comparison of spot detection methods in fluorescence microscopy[END_REF]. A particular case can be the initialization of a tracking algorithm to study, for example, vesicles trajectories [START_REF] Chenouard | Objective comparison of particle tracking methods[END_REF]. In addressing biological applications some specific issues have to be considered due to the variability of biological material within and between different classes of objects. For example, objects representing other biological material may be mixed with the actually targeted ones, thus the image cannot be simply modeled as a collection of objects of interest in a background. Besides, the size of these targeted objects is sometimes close to the voxel size, making the differentiation between objects and noise particularly complicated. In this paper, we present a methodological framework that provides tools to solve the different issues raised by multiple biological objects detection from microscopic images. We will particularly develop the following: Issue 1: How to address the intensity heterogeneity that prevents from considering a global threshold on the intensity in order to separate to objects from background ?

Issue 2: How to deal with nuisance objects that do not belong to the targeted class of objects but cannot be considered as background neither ?

Issue 3: How to deal with a high density of objects that generates clusters of possibly overlapping objects ?

Issue 4: How to handle the shape variability between objects ?

Issue 5: How to detect objects that consist of a few pixels ?

Issue 6: How to deal with both 2D and 3D datasets ?

Throughout the literature that addresses this problem, we distinguish both global as well as local methods. Global methods usually consider a threshold to separate the background from pixels belonging to objects. Each n-connected group of pixels tagged as object is then analyzed. A watershed segmentation is then performed on the distance map inside each component to split it into individual objects. Each individual object is finally selected or rejected depending on its size and shape, considering for example a circularity parameter. This classical approach is usually the one proposed by common image analysis software such as Matlab, the particle analyzer of Fiji or Cell Profiler [START_REF] Schindelin | Fiji: an open-source platform for biological-image analysis[END_REF][START_REF] Carpenter | CellProfiler: image analysis software for identifying and quantifying cell phenotypes[END_REF]. Nevertheless, issue 1 is not addressed within this approach. In consequence, in order to remove background variation, a high pass filter has to be previously applied. Issues 2,3 and 4 are partially solved if the objects of interest have more or less a circular shape and can be bounded by particular minimum and maximum sizes that discriminate them from nuisance objects. The shape of the detected object is arbitrarily defined by the watershed algorithm, so issue 4 is not addressed. Finally, issue 5 is not addressed in case of noisy data. In local approaches, a first step usually consists of seeds detection.

A growing process then extends each seed to define an object using, for example an active contour or marker controlled watershed. This process allows the object shape recovery only if they are initially properly localized by the seeds. Therefore, the seeds detection is crucial. Some strategies to obtain these seeds include local maxima after a global threshold or a template matching process [START_REF] Miroslaw | Correlation-based Method for Automatic Mitotic Cell Detection in Phase Contrast Microscopy Computer Recognition Systems[END_REF]. Issue 1 can be partially solved by considering a low threshold when seeds are defined by local maxima. Issue 2 is not addressed whereas clusters are split arbitrarily when two growing objects intersect.

In this paper we present the marked point process modeling (MPP) as a framework to solve the different issues described above. These models derived from the application of point processes to spatial statistics. They have proven their efficiency and robustness in various fields of computer vision in order to evaluate populations of, for example, trees, buildings, roads, people in a crowd or flamingos. A survey of marked point processes applied to image analysis can be found in [START_REF]Stochastic geometry for image analysis[END_REF]. Herein we focus on biological images and show how to derive specific models to accurately address the different issues mentioned above.

Method

Marked Point Process

Let us consider an object space O ⊂ IR m that contains the geometrical description of the object of interest. For example if we consider the set of disks with radius bounded by r min and r max , then O = [r min , r max ] ⊂ IR.

We consider the configuration set Ω as the union of all the possible finite sets of objects lying in a subspace S of IR n defined by the support of the image :

Ω = ∞ i=0 Ω i , (1)
where

Ω i = {ω 1 , . . . , ω i } ∈ (S × O) i (2)
is the set of configurations containing exactly i objects, ω i = (p i , m i ), p i ∈ S is the center of the object and m i ∈ O are the marks. We define a marked point process [START_REF] Lieshout | Markov point processes and their applications Imperial[END_REF] by athe Gibbs density as follows:

∀ω ∈ Ω, dπ(ω) = 1 Z exp [-U (ω)] dπ 0 (ω), (3)
where π 0 is the measure of the Poisson process and U (ω) is the energy function that evaluates each configuration of objects. The lower the energy function value the more probable is the particular object configuration. In the context of image analysis, the energy function embeds a data term, U D (Ω|I), that evaluates the consistency of any object with respect to the data I as well as a prior, U P (Ω), that reflects constraints on the objects geometry and repartition in the image plane.

Let us consider a first example, shown in figure 1, where the image {I(s), s ∈ L } on the lattice L consists of circular cells on a dark background. We first define a data term that measures the contrast between a candidate object and its neighborhood as follows:

P (I|Ω = {ω 1 , . . . , ω i , . . . , ω n }) = exp -U D (Ω|I) with (4)
U D (Ω|I) = n i=1 u d (ω i ),
where u d (ω i ) is a contrast term we defined as:

u d (ω i ) = 1 -d(ω i ) d 0 if d(ω i ) < d 0 exp d 0 -d(ω i ) 3d 0 -1 otherwise. (5)
In equation [START_REF] Carpenter | CellProfiler: image analysis software for identifying and quantifying cell phenotypes[END_REF], d(ω i ) is a distance between pixels in the object ω i and pixels in the external boundary ∂ω i (see figure 2). For example the Bhattacharrya distance is defined by:

d(ω) = 1 4 (µ o -µ b ) 2 σ 2 o + σ 2 b + 1 2 log σ 2 o + σ 2 b 2σ o σ b , (6)
where µ o (resp. µ b ) and σ 2 o (resp. σ 2 b ) are the mean and variance of pixels in ω (resp. ∂ω. In order to prevent object overlap as much as possible, we add the following prior:

U P (Ω) = i,j:ω i ∩ω j =∅ f (ω i , ω j ) with (7) f (ω i , ω j ) = ∞ if |ω i ∩ω j | min(|ω i |,|ω j |) > o 0 otherwise
where |ω i | refers to the size of object i and o is the maximum overlap ratio permitted.

The solution is then defined as the minimizer of the global energy:

U (Ω) = U P (Ω) + U D (Ω|I). ( 8
)

Optimization

Two practical issues arise when analyzing this problem. On the first place, the energy U (Ω) we want to minimize is not convex. Secondly, the normalizing constant (or partition function) Z defined in equation 3 is analytically and numerically intractable. Therefore, the optimization is classically performed using a simulated annealing coupled with a sampling algorithm. This last that can be, for example, jump and diffusion processes or MCMC approaches, particularly Reversible Jump MCMC (RJMCMC), as the number of objects is unknown. More recently, the multiple births and deaths (MBD) algorithm based on a discretization scheme of a stochastic differential equation has been proposed [START_REF] Descombes | Object Extraction Using a Stochastic Birth-and-Death Dynamics in Continuum[END_REF]. As an advantage, this algorithm permits to address a whole set of objects in the same iteration. Besides, there is no rejection in the birth step that allows any new objects introduction at every stage of the simulated annealing. Some faster suboptimal algorithms have also been proposed such as the multiple births and cut (MBC). In this paper we consider the MBD algorithm as the MBC algorithm is restricted to particular energy functions.

The MBC algorithm alternates births and deaths steps consisting in adding new objects and removing some of them with a certain probability that depends on the specific value of the energy function: i by descending order of the data energy (from the "worst" to the "best").

Death step : For each object {ω j ∈ Ω b i } taken sequentially in the ordered list, remove

ω j from Ω b i with probability p = δa(ω j ,Ω b i ) 1+δa(ω j ,Ω b i ) such that a(ω j , Ω b i ) = exp - 1 T U (Ω b i /{ω j }) -U (Ω b i )
If not converged decrease T (resp. δ) by a factor α T (resp. α δ ) and go back to step 2.

The convergence has been theoretically proved in [START_REF] Zhizhina | Double Annealing Regimes in the Multiple Birth-and-Death Stochastic Algorithms[END_REF], and is empirically obtained either after a fix number of iterations or when the configuration does not change during a couple of iterations.

Results

We validate this model on several synthetic images of cells simulated with the "Simcep" algorithm [START_REF] Lehmussola | Computational Framework for Simulating Fluorescence Microscope Images With Cell Populations[END_REF]. To do so, we compare the performance of the proposed MPP approach with the classical approach proposed by software such as Fiji or Matlab. This last one consists in binarizing the image and splitting the clusters using the watershed algorithm on the distance map. Resulting connected components are selected as objects depending on their size and a circularity coefficient. We first consider a noise free image of cells given on figure 3, and then we add noise on figure 4. Finally we increase the background heterogeneity due to the light source (see figures 5 and 6). With this first model we partially address the different challenges (issues 1, 2 and 3). The main advantage of this approach is that the data is taken into account at the object level. In the data term, statistics of pixels contained in the whole object are considered providing a high robustness with respect to noise (see figure 4). Besides, we consider a local contrast term between the object and the surrounding pixels that gives robustness with respect to the background heterogeneity (see figures 5 and6) compared to the classic approach. Finally, the shape model facilitates the discrimination between objects of interest and nuisance objects. Notice however that in the case of disk shaped objects the watershed algorithm (classic approach) performs quite well on the task of splitting clusters (see figure 3). However, this performance decreases rapidly with noise or background heterogeneity while the MPP approach remains robust. Finally, with this simple model, only circular cells are addressed. Several extensions have to be considered Figure 5: A first exemple of an heterogeneous background (top left), results with the MPP approach (top right) and with two parameter settings for the fiji particle analyser (bottom left and right) Figure 6: A stongly heterogeneous background (left), results obtained the fiji particle analyser (midlle) and with the MPP approach (right). in order to generalize the approach.

Discussion

We have shown in section 2.3 that the MPP approach gives an answer to issues 1, 2 and, partially, 3. By considering objects instead of pixels as unknown variables we obtain a robust detection with respect to noise and to non homogeneous background. However, at this stage issues 4, 5 and 6 have not been yet addressed. In this section we discuss several extensions to the previous model that take into consideration the shape and size variability of the objects within the same MPP framework.

More general shapes

In section 2, we have considered an object space consisting of disks. However, it is straightforward to take into account more complex parametric spaces in order to define other geometries. For example, if we consider the image given on figure 7, it is clear that a model based on disks would fail to detect the cells. The particle analyzer based on the distance transform (Fiji) is also inadequate as shown on figure 7 (middle). This problem can be solved within the marked point process framework by considering ellipses as objects, such that the object space is defined by O

= [a min , a max ] × [b min , b max ] × [0, π].
We can see on the MPP result on figure 7 (right) that the objects have been correctly detected and delineated, contrary to the particle analyzer approach, that cannot correctly split clusters of ellipses. Several parametric shapes have been proposed in the literature including rectangles, segments or superquadrics. The mix of two shape spaces such as disks and ellipses is also possible. However, the parametric space that defines the shapes should have a low dimension, typically lower than 5, to avoid computational burden. This can be limiting in case of complex shapes such as the cells on figure 8, or when the objects are composed of a few pixels, causing the discretization to lead to a poor approximation of the parametric shapes. To overcome this limit, it has been proposed to define the object space as a dictionary of precomputed shapes. Such a dictionary can be obtained from previous segmentation maps as in [START_REF] Poulain | Cells Detection Using Segmentation Competition[END_REF] (see the result on figure 8) or by constructing an exhaustive description of shapes included in a small bounding box. On figure 8 we can see that the use of a dictionary combining shapes obtained by the particle analyzer algorithm and by an active contour approach allows to select the most relevant ones from each method and for different parameters, thus improving the global result. On figure 9, the dictionary is defined by the whole set of convex shapes bounded by 5 × 5 pixels square [START_REF] Cedilnik | SPADE: Small PArticle DEtection[END_REF]. This last approach has been proven to overcome state of the art detection techniques, such as the one included in Icy which is based on wavelets (see figure 9 middle and right).

Energy function

The energy function is composed of a data term that fits the objects onto the image and a prior that favors or imposes properties on the whole configuration. In section 2 Figure 7: Example of elliptic cells (left), results obtained by the Fiji particle analyser (middle) and the MPP approach (right) Figure 8: Spheroid containing cells of various shapes (left), results obtained with the Fiji particle analyser (middle) and the MPP approach based on a dictionary (right). Figure 9: An example of small particles within cells (top left), ground truth (top right), results obtained by the wavelet approach proposed by Icy (bottom left) and by the MPP approach (bottom right)-Green : true positive -Blue : false negative -Red : false positve we have considered a contrast term based on the Bhattacharrya distance between the pixel intensity inside the object and in a crown surrounding it. Several formulations to define the data term can be found that compare the mean, the median or the maximum value between the object and its neighborhood. These terms are based on the contrast norm of the object with respect to the surrounding pixels that are supposed to belong to the background. Another class of data terms is based on the scalar product of the normalized intensity gradient on the object frontier and the normal of the shape along this frontier. This notably leads to models that are invariant with respect to the image contrast [START_REF] Soubies | Graph Cut Based Segmentation of Predefined Shapes: Applications to Biological Imaging[END_REF]. In this setting the data term is entirely based on the object geometry (in the data) independently on the contrast. This is therefore fully adapted to cases when the contrast is not constant within the image due to heterogeneous illumination in the background or variability in the object intensity. The second part of the energy function consists of prior information. In this paper we have considered a repulsive term that prevents objects overlap. Some attractive properties can also be defined, for example, to favor clusters of objects or to align them by sharing similar angles.

Computational considerations

The Multiple Birth and Death algorithm has been proposed in [START_REF] Descombes | Object Extraction Using a Stochastic Birth-and-Death Dynamics in Continuum[END_REF] as an alternative to the classical RJMCMC scheme. As for the RJMCMC, the convergence to the configuration that minimizes the energy has been proven in a simulated annealing context [START_REF] Zhizhina | Double Annealing Regimes in the Multiple Birth-and-Death Stochastic Algorithms[END_REF]. Regarding the MBD algorithm, its main advantage lies in the birth step, where several objects are added simultaneously to the configuration independently of the temperature. Therefore, even at a low temperature, the system can investigate new objects that locally increase the energy. To improve the convergence speed, one can introduce a birth map to favor introducing new objects with a higher probability in relevant locations within the image. For example this birth map can be based on a precomputation of the data terms for each possible location of the objects. A tradeoff needs then to be found between the complexity of the birth map computation and the gain in terms of number of iterations before convergence. Some suboptimal algorithms have been proposed in order to speed up the convergence. For these algorithms there is no guarantee to reach the global optimizer, but they have proven to be efficient in practice. As for Markov Random Fields, the graph cut algorithm has been employed by replacing the death step in the MBD by a graph cut to select the most relevant objects. This has lead to the Multiple Birth and Cut (MBC) algorithm [START_REF] Gamal Eldin | Multiple Birth and Cut Algorithm for Multiple Object Detection[END_REF]. The main advantage of the MBC over RJMCMC and MBD schemes is that it prevents from embedding the algorithm into a simulating annealing scheme thus avoiding the calibration of the cooling parameters (initial value and decreasing coefficient of the temperature). To speed up the convergence speed one can consider a deterministic version of the MBC algorithm that can be compared to the ICM for Markov Random Fields. It simply consists of the removal of an object -during the death step -in the case that this change in the configuration induces an energy decreasing. A quantitative comparison between stochastic samplers, in terms of accuracy and computational time, is given in [START_REF] Verdié | Detecting parametric objects in large scenes by Monte Carlo sampling[END_REF] on a particular application. However, the efficiency of these algorithms highly depends on their design (kernel choice in case of RJMCMC, birth map in case of MBD), thus each case needs to be specially studied.

Further MPP applications to biology imagery

In this paper we focus on object detection. However, other problems can be addressed within the marked point process framework as it has been proposed for remote sensing applications. In this particular context, a hierarchical model has been proposed by [START_REF] Börcs | Extraction of Vehicle Groups in Airborne Lidar Point Clouds with Two-Level Point Processes[END_REF] to model groups of vehicles (i.e.: each vehicle is a first order object and a group of them is a second object order). Such a multi-level model can be applied to study populations of vesicles within cells. An extra dimension representing time can be added to MPP models in order to obtain an object tracking algorithm [START_REF] Craciun | Joint detection and tracking of moving objects using spatio-temporal marked point processes[END_REF]. MPP can thus be employed to study vesicles trajectories. Finally, the transition between two states of a given object, for example a cell from alive to dead, can be addressed through change detection models [START_REF] Benedek | Building Development Monitoring in Multitemporal Remotely Sensed Image Pairs with Stochastic Birth-Death Dynamics[END_REF].

Conclusion

The MPP approach, originally developed in the domain of spatial statistics for the modeling of populations, has been more recently successfully applied to solve image analysis problems and, more particularly, multiple object detection from images. In this paper we have shown that this framework is well suited to perform object detection in biological imagery. The different issues raised by these applications can be satisfactorily addressed with MPP modeling. This includes noise, shape variability and background heterogeneity. The non convexity of the functional to be minimized may lead to heavy computational time, especially when treating 3D datasets. However, some sub-optimal algorithms have been proposed that make the approach usable in practice. Some issues remain unsolved concerning MPP. Shapes are currently defined in a low dimensional parametric space or in a predefined dictionary. To consider general shapes defined in a shape space, as for example in [START_REF] Srivastava | Statistical Shape Anlaysis: Clustering, Learning and Testing[END_REF], is a very challenging issue. Apart modeling issues we can also mention improvement in the optimization to speed up the convergence or to define parallel implementation [START_REF] Verdié | Detecting parametric objects in large scenes by Monte Carlo sampling[END_REF]. Finally, estimating the parameters is still a largely open issue [START_REF] Chatelain | Parameter estimation for marked point processes. Application to object extraction from remote sensing images[END_REF].

Figure 1 :

 1 Figure 1: Example of an image containing a collection of objects on a background.

Figure 2 :

 2 Figure 2: Discretization of a disk ω and its neighborhood ∂ω

Algorithm 1

 1 Multiple Births and Deaths Intialize the objects configuration with the empty set Ω 0 = ∅, set T = T 0 , i = 0 and δ = δ 0 Births step : Set i = i + 1, Generate randomly a set of objects B i = {b j i } and compute the data term for each object u d (ω j i ). The location and the marks of objects are drawn from a uniform distribution and the number of objects is drawn from a Poisson law of parameter δ × |L|, |L| being the number of pixels. Set Ω b i = Ω i-1 B i . Sorting step : Sort the objects in Ω b

Figure 3 :

 3 Figure 3: A noise free example of image cells (left) and the detection obtained using the fiji particle analyser (middle) and the MPP approach (right).

Figure 4 :

 4 Figure 4: A noisy example of image cells (left) and the detection obtained using the fiji particle analyser (middle) and the MPP approach (right).

Acknowledgment:

The author would like to thank A. Razetti for careful proof reading.


Eric Sanchez
email: eric.sanchez@unifr.ch

Claudine Piau-Toffolon
email: claudine.piau-toffolon@univ-lemans.fr

Lahcen Oubahssi
email: lahcen.oubahssi@univ-lemans.fr

Audrey Serna
email: audrey.serna@insa-lyon.fr

Iza Marfisi-Schottman

Guillaume Loup
email: guillaume.loup@univ-lemans.fr

Sébastien George
email: sebastien.george@univ-lemans.fr

Toward a Play Management System for Play-Based Learning

Keywords: Game-Based Learning, Play Management System, Classroom Orchestration, Design-Based Research, Teachers' Requirement Analysis

come   L'archive ouverte pluridisciplinaire

Introduction

Within a context marked by the development of alternative pedagogies, this position paper aims to describe a model of an integrated system, called Play Management System (PMS), dedicated to support players and teachers to deliver, use, manage and track play situations. The purpose of this article is to propose an innovative approach for implementing a play-based learning approach by [START_REF] Sanchez | Learning, Serious Games, and Gamification[END_REF] focusing on the learners and taking into consideration the situation that emerges when they play rather than the artifact dedicated to play (play vs game) and (2) focusing on the teachers who want to implement and manage a play-based learning situation in their classroom (play management vs game design). Thus, we address the issue of teachers' requirements for the orchestration of a play situation within an educational context. In the first section of this paper, we advocate for a player-centered approach for game-based learning. The second section presents a game developed during the project and the design-based research methodology adopted for designing this game. The third section describes

Switching from Game to Play

Digital Epistemic Games (referend to as JENs1 in this paper) are playful and authentic learning situations that lead the learners to solve complex, interdisciplinary and nondeterminist problems. JENs allow students to develop their own ways of thinking and acting by designing and trying out their own solutions [START_REF] Shaffer | Epistemic Frames for Epistemic Games[END_REF][START_REF] Ohlsson | Learning to Do and Learning to Understand: A Lesson and a Challenge for Cognitive Modeling[END_REF]. JENs also rely on mixed reality technologies [START_REF] Milgram | A Taxonomy of Mixed Reality Visual Displays[END_REF] to create contextual and situated activities and to support knowledge co-construction among learners. "Learning situation" are key words of this definition and Henriot emphasized the importance of distinguishing the game, as an artifact, and play, its usage [START_REF] Henriot | Le jeu[END_REF]. For Henriot, play emerges from the interactions between a player and a game. In other words, play depends on the lusory attitude [START_REF] Suits | Grasshopper: Games, Life and Utopia[END_REF] of the players, i.e. their willingness to take on the rules of the game and to participate. Usually, studies on game-based learning are focused on the characteristics of a given game. We consider that it is the learning situation in which the game is used that is paramount, and that a shift from a game-based to a play-based perspective is needed. Implementing a game-based pedagogy implies that the teachers have to manage the classroom orchestration [START_REF] Dillenbourg | Design for Classroom Orchestration[END_REF]. Their role entails the introduction of the game to the students. A teacher may also act as a game master and be involved in the assignment of rewards, if it is not automatic. Following a gamification trend, for some Learning Management Systems such as Moodle2 , badge functionalities enable students to represent their achievements and skills. Such an approach has been implemented for the game Classcraft3 , designed for classroom management. The success of the game, in terms of its adoption by teachers, demonstrates its relevance [START_REF] Sanchez | Classcraft: from Gamification to Ludicization of Classroom Management[END_REF]. Another teachers' roles relates to the animation of debriefing sessions, dedicated to foster reflection and metacognition after the game, or in-between game sessions [START_REF] Garris | Games, Motivation, and Learning: A Research and Practice Model[END_REF]. Regarding the importance and the complexity of the teachers' role for game-based learning, it becomes apparent that they need to be taken into account when designing a technical solution to implement their game and that such a solution should include support for dynamic classroom orchestration.

Play Management System Requirement Analysis

The methodology of this research work is based on the collaboration of practitioners (teachers) and researchers. Thereafter, the objectives are both pragmatic (producing innovative digital applications adapted to the teachers' expectations) and theoretical (developing new models for instruction and learning). As a result, the methodology applied is influenced by the Design-Based Research (DBR) approach [START_REF]Design-based research: An Emerging Paradigm for Educational Inquiry[END_REF]. This de-sign process is combined with the analysis of these educational practices, carried out collaboratively by researchers and practitioners. In the field of Technology Enhanced Learning, DBR has close relationships with software design methodologies that aim to integrate end-users in the early stages of the design process, such as Agile or usercentered methodologies [START_REF] Highsmith | Agile Software Development Ecosystems[END_REF] and participatory design [START_REF]Participatory Design: Principles and Practices[END_REF] from the Human Computer Interaction field. Considering our needs for play orchestration of JENs, we therefore choose to apply DBR for the analysis of the teachers' requirement. In order to provide an example of the JENs designed with this method, let us present Insectophagia, one of the three games we designed with teachers.

Insectophagia is a game that convers the principles of sustainable development. This game was designed for five classes (86 students) from 15 to 17 years old. The global objective, for each team (composed of 3 or 4 learners) is to create a start-up company, specialized in insect-based food production. First, the team needs to choose the type of insect they want to farm, based on ecological and dietary properties. Then, they have to find a proper location to build their factory and make the right investments in terms of sustainable energy sources. Finally, they need to come up with an innovative and appealing product for customers. The players use digital technologies and real-world settings depending on the performed mission. The game lasts approximatively 7 weeks (approx. 18 hours) depending on the school. Rewards and points depend on how the players manage to deal with environmental, social and economic issues. The teacher is responsible for introducing the different missions, rewarding the students, time keeping and also for chairing the debriefing session. We also designed two other very different JENs: Rearth, a science-fiction game dedicated to science and programming and Generalisima, an exploration game, used by a company to train their employees.

Six design sessions, involving researchers and teachers, were dedicated to define the learning objectives, the game universe and the gameplay of the JENs. Several students also participated and provided ideas. After the design phase, we developed prototypes that were partial paper-based and partial digital. The main structure of the game was paper-based (e.g. paper cards, tokens representing points, game booklet) while punctual activities were completed on computers (e.g. documentary research, smartphone game for exploring the potential locations for the farm). The prototype was experimented in naturalistic conditions by the teachers involved in the design phase. After the experimentation, two sessions were organized to discuss the lessons learned from the experimentation of the JENs. From the teachers' point of view, the game was valuable for students since they were immerged in a complex situation for which they had to collaborate and use various resources. However, the pedagogical situation emerging from this game was not easy to manage in real-time in the classroom. The teachers expressed the need for a tool dedicated to manage class orchestration (assigning specific goals to players, organizing teams) and play management (rewarding successful players with points and badges). These fruitful discussions helped us to define a preliminary generic model of PMS for JENs.

Towards a Play Management System

The first user studies described previously support the need for a generic system, dedicated to play management. We describe the global architecture of the system and the functionalities that we identified.

A System Dedicated to Play Management

We called this platform Play Management System (PMS) in reference to Learning Management Systems (LMS). Indeed, there are several analogies between PMS and LMS: the shift from game to play is an analogy of the shift from teaching to learning, in line with a learner-centered approach for education; the shift from a resourcecentered to an activity-centered approach, in line with the Educational Modelling Language community approach [START_REF] Giesbers | Towards a Methodology for Educational Modelling: a Case in Educational Assessment[END_REF]; and finally, management system refers to the complexity of the game master's roles: designing and implementing the learning/gaming situation, real-time tutoring and assessing/rewarding, and debriefing. Figure 1 summarizes the main ideas behind the PMS as discussed during debriefing session. A PMS is an integrated system that supports players and teachers to carry out play-based learning. This system, separated from the game itself (JEN units), supports the different dimensions of an educational play situation (learning context, game documents, game characteristics, social interactions, and technological aspects). As a result, the PMS may be used to plan, implement, and assess specific learning processes based on play activities.

. Fig. 1. A global scheme of the PMS emerging from debriefing sessions Within a JEN, both individual play and collaborative play must be encouraged. Therefore, a PMS must offer the means for developing individual and collaborative activities that foster production, communication and coordination [START_REF] Ellis | Groupware: some Issues and Experiences[END_REF].

There is also a need, for the teacher to track play activities in order to get information about players' achievements. Indeed, the teacher's expressed the need for PMS to take into consideration data collection (traces) for the asynchronous analysis of players' interactions. As a result, learning analytics [START_REF] Long | Penetrating the Fog: Analytics in Learning and Education[END_REF] services might be offered.

Since traditional Learning Management Systems (LMS) have been developed to manage learning situations such as online or hybrid courses, they do not offer all the functionalities and dedicated interactions needed to manage play situation and they are not well suited to the specific needs of JENs. We therefore propose a new architecture.

Toward a Play Management System Architecture

The ideas expressed by the teachers and researchers during the debriefing sessions, show that the PMS architecture should be composed of 4 modules with a set of functionalities. [START_REF] Sanchez | Learning, Serious Games, and Gamification[END_REF] The Administrator Module offers the functionalities to customize the PMS, manage user accounts, the resources needed to play (documents for students) and the technical aspects of the game. (2) The Player/Learner Module offers all the functionalities for each individual player to perform the missions of the game and also to customize her/his personal data and avatar. (3) The Game Master Module is dedicated to dynamic orchestration. Teachers have the possibility to define (or redefine) specific goals, to organize teams of learners and to reward the players with points and badges. The PMS also offers different tools to support interactions between players and between players and the teacher (as a game master). ( 4) The Service Module provides teachers and learners with generic functionalities that can be used at any time during the JEN. These functionalities offer numerous ways of enhancing the play experience with specific reward tools (leader board, points, badges…), supporting collaborative work (collaborative production tools, task management tools…) and communication (chat, forum, mail...), and also tracking actions performed by the players (learning analytics).

Conclusion

The goal of this study was to propose an innovative approach for implementing playbased learning into secondary education. Since we decided to implement a playercentered approach for game-based learning and to offer support for dynamic classroom orchestration, a new perspective emerged. A PMS is an integrated system that supports players and teachers to deliver, use, manage, and track play situations dedicated to educational objectives. This system may be used to plan, implement, and assess Digital Epistemic Games. The PMS model proposed in this paper is composed of four modules: Administration Module, Player/Learner Module, Game-Master Module and Service Module.

The contributive, collaborative and iterative methodology based on experimentation in real school settings enabled linking pragmatic issues (implementing a game in a classroom) and theoretical issues (designing a model of a system adapted to play management). The main results consist of the identification of the functionalities needed for play orchestration (i.e. teachers' requirements). New experimentations are now conducted. The preliminary results underline that the persistence of the game has been recognized to be important. Thus, the prototype now offers the players the opportunity to consult their logbook, refreshed in real time. It is expected that PMS, by taking on the issue of persistence, will sustain the players' motivation and enhance decision making. In sum, the lessons learned from the ongoing experimentations, lead us to better take into consideration players' requirements.

  Eric Sanchez, Claudine Piau-Toffolon, Lahcen Oubahssi, Audrey Serna, Iza Marfisi-Schottman, Guillaume Loup, Sébastien George, « Toward a Play Management System for Play-Based Learning », Proceedings of the European Conference on Technology Enhanced Learning, EC-TEL, 14-15 September 2016, Lyon, France, pp. 484-489.

	the model of a Play Management System, based on the results that emerged imple-
	menting and testing a game in real school contexts

JEN stands for Jeu Epistémique Numérique in French

https://moodle.com/, visited on March 2016

http://www.classcraft.com/fr/, visited on March 2016

Acknowledgments. The JEN.lab project is a multi-disciplinary project funded by the French Research Agency (ANR-13-APPR-0001). The authors want to thank the students and teachers for their full support and key contributions.