Lionel Feugère

Christophe D'

Boris Doval

Performative voice synthesis for edutainment in acoustic phonetics and singing: a case study using the "Cantor Digitalis"

Keywords: edutainment, voice synthesis, performative synthesis, graphic tablet

A real-time and gesture controlled voice synthesis software is applied to edutainment in the field of voice pedagogy. The main goals are teaching how voice works and what makes the differences between voices in an interactive, real-time and audio-visual perspective. The project is based on "Cantor Digitalis", a singing vowel digital instrument, featuring an improved formant synthesizer controlled by a stylus and touch graphic tablet. Demonstrated in various pedagogical situations, this application allows for simple and interactive explanation of difficult and/or abstract voice related phenomena, such as source-filter theory, vocal formants, effect of the vocal tract size, voice categories, voice source parameters, intonation and articulation, etc. This is achieved by systematic and interactive listening and playing with the sound of a virtual voice, related to the hand motions and dynamics on the tablet.

Introduction

Like for any kind of knowledge to be taught, the learning process becomes easier and more entertaining when using various media as teaching materials. Besides, if the students can interact with the media in real-time, success is almost guaranteed. How voice works can be one of this knowledge to be taught.

Splitting a system into several subparts can help for understanding it. Concerning the voice, two observations can be noted. First, a part of the organs of the vocal apparatus is hidden from outside, and it may be dangerous to modify it further than what we can do naturally for understanding its behaviour. Second, despite it is of everyday usage, voice is a complex instrument which involves abstract concepts difficult to understand by the general public.

In this paper, an interactive and real-time application is presented, based on the Cantor Digitalis [START_REF] Feugère | Chorus digitalis: polyphonic gestural singing. 1 st International Workshop on Performative Speech and Singing Synthesis[END_REF], a musical instrument for singing vowels synthesis implemented in Max/MSP [START_REF] Max | [END_REF].

Owing to a signal-type approach and a physically meaningful mapping, it is easy to modify a large number of high level model parameters. The parallel formant 1 synthesis and the source filter model used in this synthesizer allow us to deconstruct the voice model to listen to abstract acoustic phenomena such as individual formants or vocal fold sounds.

A few voice models are available for teaching purposes, such as VocalTract-Lab [START_REF]Vocal Tract Lab[END_REF] or Benoit Project [START_REF]Benoit Project[END_REF]. Their synthesis method can not allow to listen to abstract phenomena, as they are often based on physical models of the vocal apparatus, then reflecting concrete physical phenomena. Also, the original feature of our application is above all the capability to play with the model in real-time and then to listen to the dynamic transformation of the vocal tract 2 and/or the glottal source 3 . The initial goal of the Cantor Digitalis is music, so we can easily use it in an entertaining way for pedagogical purposes by using its control interface while modifying the model parameters and listening to the effects.

After presenting the Cantor Digitalis instrument, we will deal with the decomposition of the source-filter model for a given voice and explain how we use it for pedagogical purposes. Then, still in a real-time interactive perspective, a voice is transformed from one to another through continuous and reactive transformation. We will finally conclude by the main contributions and the perspectives of our work.

Cantor Digitalis: performative singing synthesis

Cantor Digitalis is a digital musical instrument allowing for control of pitch, vowel color, strength and quality of a synthetic voice model. Synthesis is controlled in real-time, like a musical instrument, hence the expression "performative synthesis". A general view of the instrument is given at the figure 1. It is based on an improved formant synthesis model, bi-manually controlled by the position and pressure of a stylus and a finger over a graphic tablet. It has been used in concerts within the Chorus Digitalis ensemble [START_REF] Feugère | Chorus digitalis: polyphonic gestural singing. 1 st International Workshop on Performative Speech and Singing Synthesis[END_REF] [5].

Formant synthesis using the RT-CALM source model

The production model of Cantor Digitalis uses the source-filter theory: the glottal source flow is modeled using the RT-CALM [START_REF] Alessandro | Real-time calm synthesizer: new approaches in hands-controlled voice synthesis[END_REF] and the vocal tract resonances by parallel bandpass filters.

RT-CALM is a real-time version of the CALM model [START_REF] Doval | The voice source as a causal/anticausal linear filter[END_REF]. The spectral properties of the glottal flow model (GFM) are described by the shape of the spectrum derivative: a resonance in low frequencies, and a spectral slope for mid and high frequencies. A white noise modulated by the shape of the GFM represents voice aspiration. Voice strength is realized by an increase in signal intensity, a decrease in the spectral slope of the GFM derivative, and a position shift of the spectrum low frequency maximum toward higher frequencies.

Five bandpass filters model the vocal tract resonances and a bandstop filter the anti-resonance of the piriform sinus [START_REF] Dang | Characteristics of the piriform fossa in models and humans[END_REF]. The bandpass filters represent the formants of the vowels. Thus, a database of formants defines the vowels by a set of amplitude / bandpass / frequency values. A scale factor is applied to the formant central frequencies to model the vocal tract size. Then, the different singer types (bass, tenor, alto, soprano) are only characterized by two parameter shifts in our model: this global scale factor and the pitch range.

Source-filter interactions and automatic source perturbation

For singing, a number of rules has been added to the source-filter model, concerning source-filter interactions and automatic source perturbation.

Source-filter interactions are modeled by specific dependencies between:

-Fundamental frequency F 0 and formant central frequencies F i (i indicates the rank of the formant from the lowest to the highest central frequency). The literature on acoustics shows that singers modify the frequencies of their formants to adapt them with F 0 , in particular F 1 and F 2 are increased with F 0 in the upper part of their range so that they remain greater than F 0 [START_REF] Henrich | Vocal tract resonances in singing: Strategies used by sopranos, altos, tenors, and baritones[END_REF]. Indeed, formants are the key of the voice sound level. -Voice effort and the first formant central frequency F 1

It has been demonstrated [START_REF] Liénard | Effect of vocal effort on spectral properties of vowels[END_REF] that F 1 increases by 3.5 Hz/dB between soft and loud voice, or approximately 50 Hz over 15 dB range. For F 1 = 600 Hz, a scaling factor proportional to vocal effort can be applied to F 1 , in order to get a 10% increase of F 1 from soft vocal effort to maximum vocal effort (voice effort parameter approximately evolves linearly with sound level).

Automatic source perturbation are divided into deterministic and non deterministic perturbations. We implemented the deterministic heart pulse perturbation on amplitude and frequency of the glottal source vibration, as demonstrated by Orlikoff [START_REF] Orlikoff | Heartbeat-related Fundamental Frequency And Amplitude Variation In Healthy Young And Elderly Male[END_REF]. They showed that vocal sound pressure and fundamental frequency across a heart cycle has a deterministic perturbation component and that its deviation depends on vocal effort: 14% (soft), 8% (moderate), 3% (loud) for the amplitude variation; 1.4% (soft, moderate), 0.8% (loud) for frequency variation. Along a heart cycle, the perturbation looks like very coarsely a damped sinusoid around the average value and then was modeled as such. The sound result is a small perturbation of pitch and sound level giving more naturalness to the synthetic voice.

Among the non deterministic perturbation are jitter and shimmer which are modeled by a white noise perturbation over the amplitude and frequency of the GFM fundamental pattern.

Chorus Digitalis: choral performative synthesis

Cantor Digitalis is controlled by one or two graphic tablets. A pen is used to control the pitch very accurately along the X-dimension with the preferred hand, taking advantage of our writing skills. The stylus pressure over the tablet is mapped to voice effort. The tablet is visually augmented with a continuous pitch keyboard to help playing accurately.

The vowel color has been mapped in several ways. By using a second or a part of the main tablet, we can control the vowels in a 2D space with the second hand (figure 2), where four vowel formants are interpolated to get a continuous vocalic space. An alternative to bi-manuality is to control the vowel color along the Y-axis of the single tablet with the preferred hand.

The Chorus Digitalis musical ensemble has performed several times, using 1 to 6 Cantor Digitalis, each controlled by a musician and with a customized voice. The figure 3 represents the Chorus Digitalis publicly performing in May 2012.

Edutainment: the source-filter model of vocal production

After having designed an application for gestural control of voice synthesis for some years, we realized that in order to teach how the voice works, a good way was to deconstruct what we have done. We implemented a software interface to easily listen to certain parts of the voice model. The figure 4 is a screen capture of the software interface. It is separated into a clickable area and a visualization area. The clickable area allows one to build or deconstruct a voice using the source-filter approach. The visualization area displays a real-time spectrum of the output, i.e. what is heard. Below are detailed possible uses of the software for teaching purposes.

Playing with the glottal source

Pitched voice source is an acoustic effect of the vibration of the vocal folds. However, this intrinsic sound is never heard separately, as the voice sound is the convolution of the source and the vocal tract. Besides, it is impossible to remove the vocal tract, whereas by analogy it would be possible to do it with a saxophone for example, where the mouthpiece can be removed from the instrument body. With a voice model using the source-filter theory, it is possible to listen to the source, as if the vocal tract had been removed. Then, by using the same interface as with the Cantor Digitalis, the player can listen to how the glottal source sounds. The glottal control is limited to pitch and vocal effort. Then changing vocal tract configuration (vowels) does not affect the sound.

The software interface allows for choosing the mapping between the stylus pressure and the voice intensity, and then to test it while listening to the different mapping: an on/off mapping depending on stylus contact with the tablet; a volume mapping, by linearly controlling the signal amplitude with the stylus pressure; a more natural control, vocal effort mapping, which acts on amplitude and spectral slope in high frequencies.

Finally, the source noise, due to turbulent flow around the vocal fold, can be added to the harmonic source sound or can be listened independently, an effect hardly achieved with a real voice.

Listening to individual formant motions along articulatory trajectories

Using the glottal source sound, the interface allows for continuously moving each formant to listen to its filtering effect. Formant is a common term in language science, but it can be difficult to understand, above all for students who are not familiar with signal processing. Moreover, an isolated formant never occurs in speech, as the global formants pattern results of the global shape of the vocal tract. Then it is difficult to identify each formant in the sound of a real voice.

While listening to one of the 5 formants, the vocal tract can be modified by exploring the vowel space and then the contribution of this formant to the chosen vowel can be identified. The real-time control of the center frequency of the formant allows to roughly identify articulatory movements: jaw aperture to formant 1, tongue position to formant 2, lip aperture to formant 3.

Combining formants to make vowel identification emerging

After having listened to each formant independently from each other, the formants can be added one by one from the one with the lowest to the highest central frequency. Each additional formant is continuously controlled owing to a slider to highlight the sound effect. The addition of the 2 nd formant to the 1 st one allows for identification of almost all vowels. The addition of the 3 rd formant mainly resolves ambiguities between a few high vowels. The 4 th and 5 th formant improve voice quality, but without changing the vowel quality.

It is very interesting to listen to the emergences of human voice and vowels, while looking at the spectrum evolution. It really enables to understand the link between sound and spectrum, through concept of resonances/formants.

The harmonic contribution of the glottal source sound can be removed, allowing to listen to the effects of the formants on the turbulent noise of the source, while moving into the vowel space.

Synchronizing the voice source and vocal tract motions

This software has been used several times with general public (science festival, science & music day, ...) and in classes with scientific students.

Besides the above presented applications, it was sometimes used to illustrate the coordination task of the glottal source and the vocal tract to produce small words with a given expression. A person was asked to control the glottal source (pitch and vocal effort) while an other had to control the vocal tract (vowel color). They were asked to reproduce short expressive words like Oh yeah or Oui-oui (Yes-yes in French): first by analysing the evolutions of the pitch and the vowel color; second by trying to reproduce the appropriate gesture; last by synchronizing their gestures to produce the targeted expressive word. This allows people to understand how their own voice is produced by controlling a synthesized voice. The enthusiasm was clear and the users understand fast how to improve their first trial and to generalize the method to produce other short words and different expressions.

The source-filter interaction presented in the section 2.2 can be switched on or off, in order to appreciate its effect.

Edutainment: voice settings and individualization

In the preceding section, we presented the way of building / deconstructing a given voice to teach how the vocal apparatus works. Now, we are talking about how to use voice individualization for teaching purposes.

For this sake, we use the voice individualization window, a part of the Cantor Digitalis application. The window interface, as shown in figure 5 is divided into presets and manual settings. The upper part concerns voice types and the bottom part concerns formant values of the vowels. All these settings apply immediately to the voice sound. Each bandpass filter, representing a formant, can be manually adjusted through its central frequency, bandwidth, and amplitude. Then 3 values for the 5 formant filters can be set independently at the bottom left of the interface window, and the effective values (after the source filter interaction) are given at bottom right. The modification is realized in real-time but it is not possible for the user to play this new vowel with the tablet (pitch and vocal effort are controlled via a slider). This can be used to demonstrate that different vowel colors (i.e. different formant configurations) can be perceived as a same vowel, an effect demonstrating the categorical perception of vowels.

Vocal tract size

The smaller the vocal tract, the greater the frequency resonances, and then the greater the central frequency of the vocal tract formants. Then the central frequency of its formants will be larger. Thus, we can change the apparent vocal tract size of our synthesized voice by a common multiplier applied to the central frequencies of the formant filters. In real-time, we can pass from a baby voice (small vocal tract) to an adult voice (large vocal tract). This is even more effective if the pitch range consistently decreases with an increase of the vocal tract size.

Voice quality parameters

Several voice qualities parameters are available for controlling the glottal source model, such as aspiration noise rate, voice tension (inversely proportional to the frequency of the glottal flow spectrum maximum) or aperiodicity (jitter/shimmer of the vocal fold vibration).

Beyond human voice

By modifying all these parameters in real-time, it is easy to individualize the synthetic voice by trial and error. It is possible to demonstrate the vocal apparatus similarities between humans and some animals, by changing the vocal tract size, aspiration noise and vocal fold tension. An impressive example is obtained by the transformation of human voice into a beast roar by increasing a lot the vocal tract size, adding aspiration and vocal tension.

Conclusion

We presented an application derived from the Cantor Digitalis instrument and intended for acoustic phonetics teaching. It allows to use gestural control to interact with a real-time building and individualization of a voice model.

Two main paths can be explored: 1. How does the voice basically work using source-filter model approach? 2. What are the differences and similarities between human voices (or even some animal voices)?

Abstract phenomena like formants, vowel identification, voice decomposition into source and filter can be understood with the help of audio and gestural real-time interaction.

This application has already been demonstrated in several edutainment contexts like general public science festivals or during university classes. But no proper objective or subjective evaluation has been done yet.

Perspectives

Being first of all intended for voice teachers and in order to help as many teachers/students in voice education as possible, the next step would be to make the application available as free or open-source software. Now, the software is not yet available New features could be added to the present prototype, according to the needs expressed by users like voice or music teachers.

Finally, this type of performative synthesis is ideally suited to the creation and design of new voices ("human" or "monster-like") in a fast way, because of the real-time response of the system to any parameter modification. A specific and powerful feature of performative synthesis is its ability to play with vocal dynamics and vocal motion, that are often the key for natural sounding voice synthesis.

Fig. 1 .

 1 Fig. 1. Functional diagram of Cantor Digitalis

Fig. 2 .Fig. 3 .

 23 Fig. 2. The bi-manual controller

Fig. 4 .

 4 Fig. 4. Screen capture of the "voice factory" interface

Fig. 5 .

 5 Fig. 5. Screen capture of the individualization voice interface


The present work investigates the capacity and motivation of young children to grasp other people's communicative intention and use it to draw pragmatic inferences.

Many studies have given evidence that the capacity to attribute intentions to others is acquired early on in life. For example, when playing a hiding and finding game with an adult, infants as young as 14 months infer the communicative intent behind cues such as pointing and gazing and are able to find hidden objects as a consequence (Behne et al, 2005). To what extent do young children use this ability for language comprehension? If a speaker says something in an infelicitous (unexpected) way, will a child look for a reason for this infelicity? We focus here on infelicity in terms of quantity of information given by the speaker.

We consider utterances whose relevance is not obvious (i.e. utterances that require a listener to seek out non-readily accessible information in order to understand a speaker's intended meaning). Building on research showing that children are sensitive to the contrastive function of adjectival modification (Huang & Snedeker, 2008;Davies & Katsos, 2010;Bannard, Klinger & Tomasello, in press), we ask whether children are disturbed by modified referring expressions that are markedly over-or under-informative for the task at hand, and whether they seek out further information from the environment or the speaker.

In the over-informative case, would hearing "Pick the cat with a tail" in a context where there is only one, normal-looking cat lead a child to question why the speaker used such modification (and to consider that there might be a cat without a tail nearby)? Given previous studies of rational imitation in the non-linguistic domain (e.g., Gergely et al., 2002), and of social cognitive and linguistic development (e.g., understanding modified noun phrases), we predict that they would from the age of three.

In the under-informative case, we test how children resolve instructions such as "Pick up the apple" when there is more than one apple in view. Previous research suggests that 4-year-olds are aware of message ambiguity (Nilsen et al, 2008), but rarely go so far as to verbally request clarification (Matthews et al., 2007). Do children seek to resolve ambiguities even at 3 years of age? Do they do so non-verbally, for example, by checking their interlocutor's line of regard?

In this ongoing study, 3-and 5-year-old comprehenders moved toys around a 3-dimensional grid in order to match a target configuration. In a 2 x 2 design, children responded to instructions with or without prepositional phrase modification ('the horse (with the tail)') in cases where there were one or two objects corresponding to the head noun (one or two horses in the grid). The resulting four cells were: optimal (no modification, 1 object); underinformative; optimal (modification, 2 objects); over-informative. Reaction time to grasp the target object after the offset of the utterance was measured for 16 experimental items (4 overinformative, 4 under-informative and 8 matched controls) in a within-subjects design. Mixed effect regression models were fitted to log--transformed data for each age group separately (as the grid was set nearer for the younger children).

For instructions with modification, five-year olds were significantly slower to respond to over-informative instructions compared to optimal ones (B =0.171, S.E. = 0.053, t = 3.217, p = .002). Among the 3-year-olds, we observed no such significant difference.

For instructions without modification, the 3-year olds were significantly more likely to gaze check their partner on under-informative (47 gaze checks) compared to optimal trials (12 gaze checks). X-squared = 20.76, df = 1, p-value = <.0001). The same held for the 5-year-olds (70 gaze checks on under-informative trials and none on control trials: X-squared = 70, df = 1, pvalue < .0001). The 3-year-olds verbally asked for clarification on under-informative trials 23 times and the 5-year-olds did so 52 times. On trials where children's did not verbally request clarification, we calculated reaction times and observed that 5-year-olds were slower to respond to under-informative utterances than optimal ones (B =0.185, S.E. = 0.040, t = 4.651, p = .0002). Among the 3-year-olds, we observed no such significant difference.

In summary, the results suggest that sensitivity to informativeness can be captured developmentally. 5-year-olds showed sensitivity to the infelicity of both under-and overinformative sentences. 3-year-olds only showed some sensitivity to the infelicity of underinformative utterances in terms of their gaze-checking responses. This builds on evidence from 4-year-olds that even young children are implicitly sensitive to ambiguity (Nilsen et al., 2008). However, when instructions were over-informative 3-year-olds showed no sign of finding this infelicitous. This may be because children this age simply do not generate inferences in response to over-informativity. However, future studies with lower task demands are required to be certain of this. For example, the arrays in this study were quite complex for 3-year-olds. Furthermore, children may have been more sensitive to the modified stimuli if the modification came before the head noun rather than after it (by which point the target had already been uniquely identified). These task demands make it all the more striking that the 5-year-olds did show evidence of seeking to understand why the speaker was more informative than they would have expected.

Example of experimental item

« Take the car with wheels »

Results

Log-transformed reaction times as .

a function of age and condition

  Children's Comprehension of Over-and Under-informative UtterancesAuthors: Tiffany Morisseau, Catherine Davies and Danielle Matthews


H Abdoul-Carime

F Berthias

B Farizon

M Farizon

Correlated detection of neutral and charged fragments in collision induced fragmentation of molecular clusters

Keywords: Irradiation, nanosystems, biomolecules, clusters, collision induced dissociation, excitation and relaxation, multiparametric event by event detection

We report on collision induced fragmentation of isolated molecular nanosystems studied with an event by event detection technique including the correlated detection of both neutral and charged fragments. This work focuses on the dissociation induced by collisional excitation without ionisation and electron-capture. Two molecular cluster cations are investigated: the collision of protonated hydrogen clusters at 60keV/amu with helium targets and that of protonated water clusters at 8keV with an argon gas. In addition to the molecular evaporation process the dissociation channel leading to the production of the H 3 + or H 3 O + molecular cations (loss of all the molecules) is observed with an unexpected abundance. The cross section for the production of these cations is observed to increase with the number of molecules in the cluster. Such an increase cannot be associated with the direct collisional excitation of the cation core of the cluster.

Introduction

The effect of the ionizing radiation in molecular nanosystems is emerging as a major and open area of research, both on a fundamental level and as a source for experimental and technical innovations. From the experimental standpoint, it has great potential for new applications in analytical sciences and for the development of new synthesis techniques.

Concurrent theoretical progress can provide new descriptions of the radiative energy transfer in terms of molecular processes, opening new perspectives in several research areas such as the elucidation of the radiation dose at the molecular scale in living systems [START_REF] Schlathölter | Radiation damage in biomolecular system[END_REF] , the investigation of molecules which inhibit or counter the effects of irradiation but also in the context of astrochemistry and astrobiology the chemical evolution of interstellar molecular clouds [START_REF] Oka | [END_REF] .

Pioneering works have demonstrated the possibility of irradiating molecular nanosystems in the gas phase 3,4,5 . During the last decade ion-induced excitation up to ionization and fragmentation has been studied for isolated biomolecules. This opens a novel field of experimental investigation giving access to the initial radiation-induced interactions between molecules and providing key information for the description of the radiation effects at the nanoscopic scale. Although so far limited to the detection and the identification of the produced ion fragments in recent studies it has been extended to the analysis of ions and neutral formed in single events 6,[START_REF] Teyssier | COrrelated Ion and Neutral Time Of Flight" Method: event-by-event detection of neutral and charged fragments in Collision Induced Dissociation (CID) of mass selected ions[END_REF] or to the detection of neutrals species 8 . Nevertheless directly monitoring all ionized and neutral fragments produced and their correlations within a single fragmentation eventas will be described in the followingis a major step towards the complete description of the physics and chemistry of the reaction. In this paper we present results on the fragmentation of isolated nanosystems in gas phase induced by collision onto atom targets and where neutral and charged fragments are detected in an event by event frame. In the first part of this contribution, we report on fragment production spectra issued from the dissociation of protonated hydrogen clusters at 60keV/amu. The second part will focus on the fragment production spectra issued from the dissociation of protonated water clusters at 8keV.

I Collision Induced Dissociation of protonated hydrogen clusters at 60keV/amu

The hydrogen cluster ions are the simplest ionized molecular complexes that for decades have attracted experimental efforts to clarify their structure and properties 9 . Quantum Monte Carlo simulation 10 and quantum chemical calculations 11 have investigated the effect of the protonation of pure hydrogen clusters (H 2 ) m at low temperature. It has been shown that the added proton is trapped as a localized H 3 + core surrounded by stable shells of solvating H 2 molecules. In the present experiment the measurement of all the ionized and neutral fragments produced and their correlations within a single fragmentation event allows the detailed investigation of the processes involved in the subsequent fragmentation from excitation up to ionization.

I-A Experimental set-up

Mass selected hydrogen cluster ions with an energy of 60 keV/amu were prepared in a high-energy cluster ion beam facility 12 consisting of a cryogenic cluster jet expansion source combined with a high performance electron ionizer and a two-step ion accelerator. After the momentum analysis by a magnetic sector field, the mass selected high energy projectile consisting in the present study of H 3 + (H 2 ) 1≤m≤16 cluster ions is crossed perpendicularly by a helium target beam effusing from a cylindrical capillary tube 13 . Prior to this the ion beam is collimated by two apertures ensuring an angular dispersion of about  0.8 mrad. One meter after this collision region the high-energy hydrogen collision products (neutral and ionised) are passing a magnetic sector field analyser. The undissociated primary H 3 + (H 2 ) 1≤m≤16 cluster projectile ion or the neutral and charged fragments resulting from reactive collisions are then detected approximately 0.3 s after the collision event with a multi-detector device consisting of an array of passivated implanted planar silicon surface barrier detectors located at different positions at the exit of the magnetic analyser. For 60 keV/amu ions and neutral fragments, detection efficiency is 100% 14 .

This instrument allows simultaneous recording for each collision event of the number of each mass-identified fragment ion resulting from the interaction 12,15,16 . In addition, for each fragmentation event we can also monitor in coincidence with the detected ions the sum of the masses of all the neutral fragments. Moreover, by probing the angular distribution of these neutrals in front of the detector by using a movable aperture (0.5 mm of diameter) it has been demonstrated that the neutral products only consist of hydrogen atoms and hydrogen molecules 17,18 with no larger neutral clusters present.

Thus thanks to the event-by-event analysis method we are able to identify all correlated fragments produced in a single collision event between the H

with a-f = 0,1,… and p<m.

The validity of single collision conditions has been ascertained by measurements at different He target pressures which allows also to derive absolute cross sections for the occurrence of specific reaction channels (partial cross sections) 19 . This complete analysis allows us to go beyond the straightforward determination of the total charged fragment size distributions as reported previously 20 but also it provides partial fragment size distributions for selected decay reactions or classes of decay reactions.

I-B Results and discussion

In Figure 1(a) the variety in the fragmentation channels is shown via the histogram of fragmentation events sorted with respect to the value of the sum of the mass (amu) of all the neutral fragments resulting from H 3 + (H 2 ) 11 cluster fragmentation. The sum of the mass (S neutral ) of all the neutral fragments resulting from a fragmented cluster ion H 3 + (H 2 ) 11 is directly resulting from the detection technique and we observe 25 separate peaks as described in references [13] and [20]. All the neutral fragments coming from one incident cluster are detected simultaneously. Thus, in the histogram, each event corresponds to the fragmentation of one incident cluster. The number S neutral associated with each event (S neutral = 1,2,3,4,..., 25) corresponds to the value of the sum of the mass numbers of all the neutral fragments resulting from the fragmentation of a given cluster. In the following a S neutral event is defined as a cluster fragmentation event for which the sum of the mass numbers of all the neutral fragments is equal to S neutral .

The histogram built with 10 4 fragmentation events (10 4 dissociated cluster among more than 2 10 5 incident clusters) sorted with respect to their S neutral value is presented in Figure 1(a). The histogram can be roughly divided into three S neutral value ranges corresponding mainly to evaporation process (2amu≤ S neutral ≤10amu, even), electron capture (S neutral =25amu) and ionisation (11amu≤ S neutral ≤24 amu). The ionisation process which corresponds to both odd and even values of S neutral appears to be involved in about 83% of the dissociation events observed 21 . These results show importance of ionisation of the incident cluster at 60keV/amu incident energy.

In Figure 1(a), all the fragmentation events are included in the histogram. In contrast the histogram in Figure 1(b) is built by selecting events with a single charged fragment. That corresponds to select only the excitation processes of the precursor, i.e. to exclude collisions leading to electronic capture or ionisation. This histogram demonstrates that only events with even value of S neutral are resulting from cluster excitation, with the exception for S neutral = 23amu which is associated with the dissociation of the H 3 + ion core after excitation:

H 3 + (H 2 ) 11 + He  H 2 + + H + 11H 2 (2)
Indeed, protonated hydrogen cluster structures are usually represented as an ion core H 3 + surrounded by H 2 neutral subunits 11 . The events with S neutral = 24amu are also associated with the core dissociation:

H 3 + (H 2 ) 11 + He  H + + 12H 2 (3)
In Figure 1(b), the selected events with even S neutral values ranging from 2 to 22 are associated with the loss of H 2 molecules. The corresponding production yield decreases with increasing number of molecules lost. These fragmentation channels are associated with the unimolecular evaporation process 22 . Nevertheless, a relatively high production yield is observed for the events with the value S neutral = 22amu. This dissociation channel corresponds to the loss of all the molecules:

H 3 + (H 2 ) 11 + He  H 3 + + 11(H 2 ) (4)
The abundance of this dissociation channel (S neutral =22) is similar to the one leading to the evaporation process of only one hydrogen molecule (S neutral =2).

From these production yields and additional measurements, several partial crosssections have been deduced. Several partial cross sections are reported in Figure 2 versus m, the number of molecules, from m=1 to 16 at a given velocity (60keV/amu, v ≈3.38 10 6 m.s -1 ).

For the evaporation of one molecule (eq. 5), the cross-section increases with increasing number of molecules in the cluster.

H 3 + (H 2 ) m + He  H 3 + (H 2 ) m-1 + H 2 with 1≤m≤16 (5)
An increase of the cross section for the loss of a single molecule is expected since the binding energy of the molecule lost decreases with increasing number of molecules in the cluster. Size effects are observed and are related to relative stability of the clusters for different number of molecules. More surprising is the observation of a similar behaviour for the cluster dissociation in all its constituents.

H 3 + (H 2 ) m + He  H 3 + + m(H 2 ) with 1≤m≤16 (6)
The cross-section associated with this process increases with increasing number of molecule in the cluster. The cross-section increases from m=1 up to m=5 then it is nearly constant up to m=13 and then it increases up to 16. Such dissociation process might be related to a collisional excitation of the H 3 + core inducing the complete dissociation of the cluster.

But cross-sections for dissociation processes associated with the core excitation show a different behaviour with the increase of the number of molecules in the cluster. Indeed, in Figure 2 are also reported the cross-sections for the two following dissociation channels:

H 3 + (H 2 ) m + He  H + + H 2 + m(H 2 ) with 0≤m≤16 (7) H 3 + (H 2 ) m + He  H 2 + + H + m(H 2 ) with 0≤m≤16 (8)
The cross-section for these two processes are observed to be constant in the cluster range studied. Such results are in agreement with the results on electron-capture cross section of protonated hydrogen clusters. Indeed, the electron capture cross section is independent of the cluster size and nearly equal to the capture cross section of the H 3 + core 23 . Therefore, the excitation of the H 3 + core cannot explain the increasing with the cluster size of the cross sections associated with the cluster dissociation in all its constituents.

II Collision Induced Dissociation of protonated water clusters on argon gas target at 8 keV

Progress in the molecular-scale understanding of cellular processes and the development of molecular analysis techniques have triggered key questions related to the effects of ionizing radiation upon living material 24,25,26,27,28 . For instance, technical advances have opened possibilities for the study of biological molecules seeded in clusters of water molecules, and hence an entirely new perspective 29 . This intermediate step between the isolated molecule and the condensed phase has great potential as a target medium for research into the effects of ionizing radiation. Indeed the possibility to form a cluster with a welldefined composition, for instance a small "biomolecule" solvated by a given number of water molecules, offers a unique opportunity to quantify the impact of environment on the irradiation process. Moreover, this well-controlled (and possibly small) size provides exceptional opportunities to obtain direct and complete microscopic descriptions of the irradiation process and, to some extent, the subsequent relaxation pathways. Among the experimental set-ups designed for the investigation of irradiation of nanosystems in the gas phase, the DIAM 30 device (Dispositif d'Irradiation d'Agrégats Moléculaires) produces high intensity beams of mass-and-energy selected molecular and cluster ions. Moreover a mass spectrometric MS-MS method based on Time Of Flight measurements performed on an event-by-event detection technique has been also developed to explore CID fragmentation processes by directly identifying not only all ions and neutral fragments produced but also their arrival time correlations within each single fragmentation event from a dissociating molecular ion [START_REF] Teyssier | COrrelated Ion and Neutral Time Of Flight" Method: event-by-event detection of neutral and charged fragments in Collision Induced Dissociation (CID) of mass selected ions[END_REF] .

II-A Experimental set-up

Here we focused on the exploration of the fragmentation processes involved in the collision induced dissociation of 8 keV -H + (H 2 O) 2≤m≤7 by an argon atom. Briefly, protonated water clusters are produced by electron impact in a supersonic nozzle expansion of water vapour. They are accelerated to energy of 8 keV and mass selected by a double focusing sector field mass spectrometer 30 the correlation between the arrival times of the charged and neutral fragments from the dissociation of one single parent ion can be recorded. For each dissociated parent ion, the difference ΔT between the arrival time of the charged and neutral fragment is characteristic of the mass over charge ratio(s) of the charged species produced. The charged fragments mass spectrum is deduced from successive measurement of the arrival time difference ΔT for a large number of cluster ion dissociation events. The event by event analysis is performed by using ROOT© software.

II-B Results and discussion

In Figure 3 are reported the difference of arrival time between the accelerated fragment ion and water molecules (ΔT) issued from the dissociation of H + (H 2 O) 5 ions which gives a typical example of the measurements. Thus, the difference of arrival time characterizes the dissociation channel and allows the identification of each peak to a given dissociation channel. Thus the COINTOF method allows to select the dissociation processes versus the arrival times of the fragments in an event by event frame. In the present experiment, we select the dissociation induced by excitation processes excluding the electron capture process 31 . After the interaction with the argon gas target H + (H 2 O) 5 parent ions dissociate in five various dissociation channels, each one corresponding to the loss of a given number of water molecules. At the incident energy of 8 keV, dissociation following electronic excitation is the dominant process induced by the collision [START_REF] Mark | Experimental Studies on Cluster Ions[END_REF] .

The insert in figure 3 shows an example of the detection signal for a single dissociation event recorded by the fast ADC electronics. It corresponds to the following channel:

H + (H 2 O) 5 + Ar  H + (H 2 O) 3 + 2(H 2 O) (9)
The detection signal exhibits three peaks: the first one corresponding to the fragment ion is followed by two peaks at higher arrival times associated with the two neutral water molecules. A large number of events are recorded. The histogram built by sorting the dissociation events versus the arrival time difference between the charged fragments and the neutral ones gives the charged fragment mass spectrum. In Figure 3, the various dissociation channels can be identified by their specific product ion

H + (H 2 O) 4 , H + (H 2 O) 3 , H + (H 2 O) 2 , H + (H 2 O) 1 and H + .
Three main dissociation channels observed in the spectrum plotted in Figure 3 can be mainly attributed to the following molecular evaporation processes:

H + (H 2 O) 5 + Ar  H + (H 2 O) 4 + H 2 O (10) H + (H 2 O) 5 + Ar  H + (H 2 O) 3 + 2H 2 O (11) H + (H 2 O) 5 + Ar  H + (H 2 O) 2 + 3H 2 O (12)
As discussed previously in the case of protonated hydrogen clusters the molecular evaporation process should lead to a decrease of the relative production yield with increasing the number of molecules lost.

A weak production of H + ions representing at most 0.5 % of the total dissociation of the precursor ions is also observed in Figure 3 suggesting that sufficient energy has been deposited [START_REF] Mark | Experimental Studies on Cluster Ions[END_REF] . However the most probable dissociation channel clearly leads to a proton binding to at least a water molecule. From the COINTOF data, the branching ratio for each fragmentation channel can be measured : 0. The structure of protonated water clusters has been extensively studied and it is admitted that they are built from two possible protonated cores: the Eigen and the Zundel structures 34 .

The Eigen type consists of a proton strongly bound to a single water forming H 3 O + , the hydronium ion, while in the Zundel type the proton is shared between two water units forming H 2 O … H +… OH 2 . These limiting structures are called the Eigen and Zundel models for the proton in water 34 . For protonated clusters with a small number of molecules (2-7 molecules) various structures have been optimized by ab-initio calculations and for all the cluster sizes Eigen and Zundel type structures are found to be very closed to each other from an energetic point of view 35 .

The cross-section for the production of the H 3 O + ion from collision induced dissociation of protonated water cluster have been measured versus the number of molecules in the cluster.

H + (H 2 O) m + Ar  H 3 O + + (m-1)(H 2 O) (13)
The H 3 O + production cross sections in CID of 8keV-H + (H 2 O) m=2-7 on an argon gas target are plotted in Figure 4. From m=2 up to 5 the cross section is nearly constant and then increases for n=6 and 7. As discussed in the case of hydrogen clusters, the increase of the cross section for the complete dissociation process with the cluster size cannot be understood via a collisional excitation of a positively charged core followed by the loss of all the molecules.

Conclusion

By the selective observation of the processes in a multiparametric event by event detection technique, the results have shown how different excitation mechanisms compete and various relaxation phenomena occur in collision induced dissociation experiment. The relaxation of molecular cluster after excitation induced by collision is observed in the case of the two investigated cluster cations. In both cases, the unimolecular evaporation process is observed. But a high proportion of complete dissociation of the cluster appears. Such behavior was observed in collision induced dissociation of protonated water clusters and associated with a multifragmentation process 36 . Differently in the case of collision induced dissociation of mixed cluster anions, the cluster dissociation in all its constituents has been interpreted in the framework of statistical unimolecular evaporation model 37 . In contrast the present results could also suggest that the observed effect is related to the charge localisation in the cluster cations. According to ab initio calculations on protonated hydrogen clusters, the localisation of the positive charge becomes less restricted with increasing cluster size and/or temperature 38,39 . Thus, the loss of molecules requires a relaxation of the core which could induce the complete dissociation of the cluster. Concerning the protonated water clusters, the charge localisation is strongly different for the Eigen and the Zundel type structures.

Therefore for the latter the relaxation of the molecular system after excitation by collision could favor the dissociation channel producing the H 3 O + ion, rather than the stabilization of the Zundel structure. Thus, the increase of the production of the H 3 O + cation cross-section observed here for protonated water clusters with size of 6 and 7 could be associated with the contribution of Zundel type structure in the protonated cluster beam for the H + (H 2 O) 6 and H + (H 2 O) 7 clusters ions. Signature for the occurrence of Zundel type structures for protonated cluster ions with six and seven molecules has already been observed in infrared spectroscopy 40 .

FIGURES

  . The energy and mass-selected H + (H 2 O) 5 beam is crossed with an effusive argon gas jet which density is controlled in order to insure single collision conditions in the CID region. The time of flight apparatus involving the COINTOF technique[START_REF] Teyssier | COrrelated Ion and Neutral Time Of Flight" Method: event-by-event detection of neutral and charged fragments in Collision Induced Dissociation (CID) of mass selected ions[END_REF] is mounted right after the CID region along the direction of the incident beam. Any single dissociative collision of a H + (H 2 O) 5 parent ion with an Ar atom produces a daughter ion and one or more neutral fragments. The charged species are then accelerated at 1.8kV before reaching a field free zone, while the neutral fragments almost keep the initial velocity of the parent ion. All the fragments are then detected by the same Micro Channel Plate detector (MCP, Hamamatsu) with the charged fragment arriving significantly earlier than the neutral species. The MCP signal is sampled by a fast analog to digital converter (8 Gsample/s ADC, Acqiris®, Agilent) and recorded without dead time during a given arrival time window. The intensity of the initial parent ion beam is controlled in order to ensure that only the fragments of one single parent ion can reach the detector during the detection time window. Therefore,

Figure 1 :

 1 Figure 1: The variety in the fragmentation channels is shown via the histogram built with 10 4 fragmentation events sorted with respect to the value of the sum of the mass (amu) of all the neutral fragments resulting from the H 3 + (H 2 ) 11 cluster fragmentation. (a) all the fragmentation events. (b) fragmentation events induced by collisional excitation without ionization and electroncapture.

Figure 2 :

 2 Figure 2: Cross section of the H 3 + fragment production without collision induced ionisation versus m, the number of molecules in the cluster.

Figure 3 :Figure 4 :

 34 Figure 3: Collision induced dissociation of 8keV-H + (H 2 O) 5 on an argon atom: fragmentation channels observed via the COINTOF mass spectrometry technique. Insert: typical example of the signal recorded for the dissociation of a single cluster ion in the channel H + (H 2 O) 5 + Ar → H + (H 2 O) 3 + 2H 2 O

  4, 0.229, 0.158, 0.211, and 0.0024, for the production of H + (H 2 O) 4 , H + (H 2 O) 3, H + (H 2 O) 2, H + (H 2 O) and H + , respectively[START_REF] Berthias | Collision-induced dissociation cross section of protonated water clusters[END_REF] . The branching ratio values decreases with the increase of the number of evaporated water units, excepted for

	the production of the H + (H 2 O) ion. This result is similar to that observed for H 3	+ fragment
	produced in the dissociation after excitation induced by collision of H + (H 2 ) 11 shown in Fig 1b.

  60 keV/amu-H + (H 2 ) m + He → H 3 + + mH 2 60 keV/amu-H + (H 2 ) m + He → H 2 + + H + mH 2 60 keV/amu-H + (H 2 ) m + He → H + + H 2 (or 2H) + mH 2 60 keV/amu-H + (H 2 ) m + He → H + (H 2 ) m-1 + H 2


Youssou Faye
email: yfaye@femto-st.fr

Herve Guyennet
email: hguyenne@femto-st.fr

Ibrahima Niang
email: iniang@ucad.sn

Yanbo Shou
email: yshou@femto-st.fr

Fast Scalar Multiplication on Elliptic Curve Cryptography in Selected Intervals Suitable For Wireless Sensor Networks

Keywords: Elliptic Curve Cryptography, Fast Scalar Multiplication, Wireless Sensor Networks

In Wireless Sensor Networks (WSNs), providing a robust security mechanism with limited energy resources is very challenging because of sensor node's limited resources (computation, bandwidth, memory). Asymmetric-key can fulfill the requirement, but if the number of nodes is large, symmetric-key cryptography is the best natural method because of its scalability. Asymmetric-key cryptography is power-hungry; nevertheless, Elliptic Curve Cryptosystems (ECC) are feasible and more flexible for sensor nodes. Scalar multiplication is the most widely used operation on ECC. Various methods for fast scalar multiplication exist, but they are based on the binary/ternary representation of the scalar. In this paper, we present a novel technique to make fast scalar multiplication on Elliptic Curve Cryptosystems over prime field for light-weight embedded devices like sensor nodes. Our method significantly reduces the computation of scalar multiplication by an equivalent representation of points based on point order in a given interval. Since our technique can act as a support for most existing methods, after an analytical and efficiency analysis, we implement and evaluate its performance in different scenari.

Introduction

Security in Wireless Sensor Networks has attracted more and more attention in recent years. Symmetric cryptography is the most suitable application in constrained platforms such as sensor devices. For a large number of devices, the natural method employed is the asymmetric key cryptography algorithm because of its scalability. Compared to other asymmetric cryptosystems like RSA, Elliptic Curve Cryptography is an emerging favorite due to its shorter key length requirements for the same level of security strength [START_REF] Robshaw | Elliptic Curve Cryptosystems, An RSA hbomtories Technical Note[END_REF]. The mathematical hierarchy of elliptic curve involves three arithmetic levels: scalar arithmetic, point arithmetic and field arithmetic [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF]. Point operations involve points addition and doubling, tripling or quadrupling (or similar operations). Scalar multiplication denoted by kP where P represents a point on the ellipic curve and k represents a scalar. The scalar multiplication is the central and most time-consuming operation in ECC because it is used for key generation, encryption/decryption of data and signing/verification of digital signatures. To perform fast computation of scalar multiplication, which is the major computation involved in ECC, much research has been devoted to the point arithmetic level and the scalar arithmetic [START_REF] Gordon | A Survey of Fast Exponentiation Methods[END_REF][START_REF] Dimitrov | Efficient and secure elliptic curve point multiplication using double-base chains[END_REF][START_REF] Ciet | Trading inversions for multiplications in elliptic curve cryptography[END_REF][START_REF] Meloni | Elliptic curve scalar multiplication combining Yaos algorithm and double bases[END_REF][START_REF] Tian | An Efficient Elliptic Curves Scalar Multiplication Algorithm Suitable for Wireles Network[END_REF][START_REF] Imai | Faster Multi-Scalar Multiplication Based on Optimal Double-Base Chains[END_REF]. On the scalar arithmetic level, the double-and-add technique is the traditional binary algorithm which is based on points operations, namely doubling of a point and addition of points. Also, well-known algorithms, such as Non-Adjacent Form (NAF), window NAF, and sliding window [START_REF] Gordon | A Survey of Fast Exponentiation Methods[END_REF], can effectively reduce the number of point operations. Again, some other algorithms, such as double-base chains, have been developed to compute faster scalar multiplication by using binary and ternary representation [START_REF] Dimitrov | Efficient and secure elliptic curve point multiplication using double-base chains[END_REF], [START_REF] Ciet | Trading inversions for multiplications in elliptic curve cryptography[END_REF], [START_REF] Meloni | Elliptic curve scalar multiplication combining Yaos algorithm and double bases[END_REF]. Thus, algorithms, based on the aforementioned algorithms, optimize faster scalar multiplication [START_REF] Tian | An Efficient Elliptic Curves Scalar Multiplication Algorithm Suitable for Wireles Network[END_REF], [START_REF] Imai | Faster Multi-Scalar Multiplication Based on Optimal Double-Base Chains[END_REF]. In addition, on point arithmetic, some schemes use algebraic substitutions of the multiplication operations with squaring operations and other cheaper field operations such as addition, subtraction and multiplication or division by a small constant [START_REF] Longaanda | Fast and Flexible Elliptic Curve Point Arithmetic over Prime Fields[END_REF]. Recently, a new concept of using multiprocessor architectures to process several operations of scalar multiplication simultaneously has been developed. At the point arithmetic level, some algorithms parallelize ECC formulas to reduce the time complexity of scalar multiplication [START_REF] Longaanda | Fast and Flexible Elliptic Curve Point Arithmetic over Prime Fields[END_REF]. At the scalar arithmetic level, the algorithm in [START_REF] Ansari | Parallel Scalar Multiplication for Elliptic Curve Cryptosystems[END_REF] parallelizes the series of doubling and addition operations of a point on the binary algorithm with two processor architectures. For other solutions, parallelization is done by partitioning the scalar into n equal-length bit substrings on multiprocessor architectures [START_REF] Wu | Partitioned Computation to Accelerate Scalar Multiplication for Elliptic Curve Cryptosystems[END_REF], [START_REF] Lim | More flexible exponentiation with precomputation[END_REF]. In very recent research, this partitioning technique is used on the sensor nodes in [START_REF] Shou | Parallel Scalar Multiplication on Elliptic Curves in Wireless Sensor Networks[END_REF]. In this paper, we propose a method to accelerate scalar multiplication. For a given scalar multiplication k P, we replace it with an equivalent representation d P where the scalar d <k . Our technique is based on point order and the negative of point. Current research shows this is the first method based on this technique. All the above mentioned algorithms can basically use our technique to perform faster computation on scalar multiplication. The rest of this paper is organized as follows: Section 2 describes some preliminaries about ECC over prime fields; in Section 3, we present our new scalar reduction. After outlining the context of our first contribution (Section 3.1), we describe the new scalar reduction (Section 3.2), and make respectively, an analytical evaluation and efficiency analysis (Section 3.3) and (Section 3.4). In order to verify our claims we implemented a simulator in Java and analyze its performance (Section 3.5). Finally, Section 4 is related to our conclusions and perspectives.

In this section, a brief background description about ECC over finite prime fields is given. An elliptic curve E over finite field F (of order n ) denoted by E(F) can be defined by the long Weierstrass equation [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF]:

E : y 2 + a 1 xy+a 3 y=x 3 +a 2 x 2 +a 4 x+a 6 .
(

) 1
where a 1 , a 2 , a 3 ,a 4 and a 6 are elements in F.

The field generally used in cryptography relates to the prime field denoted by F p where p= q m and q a prime number called the characteristic of F p . If q m =p, F p is called a prime field. In this paper, we work with a prime field F p , where p >3.

For prime fields, if the characteristic is more than 3, the Weierstrass equation can transform to:

E : y 2 =x 3 +ax+b . ( 2
)
where a and b ∈ F p .

To be used for cryptography, the necessary condition is the discriminant of polynomial:

f (x) = x 3 + ax + b, = 4a 3 + 27b 2 = 0. (3)
The points (x, y), where integer coordinates x, y satisfy the above equation and the point at infinity denoted by ∞ is also a point on the curve and form an abelian group. The group law mainly consists of two basic operations: point doubling (2P ) and point addition (P+Q) where P and Q are two different points on the curve. Given P=(x p ,y p ) and Q=(x q ,y q ) two points ( = ∞ ) which are on the elliptic curve over F p denoted by E (F p ). The points addition P+Q=(x pq ,y pq ) or point doubling 2P=P+Q=(x pq ,y pq ) if P=Q can be calculated as:

x pq = λ 2 -x p -x q y pq = λ(x p -x p+q ) -y p (4)        λ = y q -y p x q -x p , ifP = Q λ = 3x 2 p + a 2y p , ifP = Q (5)
The negative of a point only involves the change of at most one of its coordinate values in the point representation. For example, the negative of a point P = (x p ,y p ) is its reflection in the x -axis: the point -P is (x p ,-y p ). Notice that for each point P on an elliptic curve, the point -P is also on the curve.

3 New scalar reduction method

Context

In this section, we present a new improvement in the scalar arithmetic level. This improvement is based on specific reduction of the scalar in a selected interval.

Assume that F p has a characteristic greater than 3. Let E (F p ) be an elliptic curve over a prime field. Let #E (F p ) denotes the number of points of the elliptic curve over E (F p ). #E (F p ) is also called the order of group of points. A wellknown theorem of Hasse states that [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF]:

|#E (F p ) -p -1 ≤ 2 √ p |.
Let G be a cyclic group of E (Fp) of order n generated by a base point P (namely generator point). The points in G are expressed as multiples of P : G=P ={∞, P, 2P, ....., (n-2)P, (n-1)P }⊆ E (F p ) with nP =∞. The order of point P (denoted by #P ) is n.

Description of our new scalar reduction method

In our approach, we replace the point, namely kP, in the main scalar multiplication operation by an equivalent representation point dP (k and d two scalars

and k > d) in the interval [n/2+1, n-1],
where n/ 2 denotes the integer-part function of n/ 2. As the negative of a point is obtained freely, we use it to make fast computation. Given the point P=(x p , y p ) in affine coordinates, to compute the negative (inverse) of the point kP=(x kp , y kp ), we can compute kP=(x kp , y kp ) and then change the sign on the y-coordinate (y kp ). Notice that for each point P on an elliptic curve, the point -P is also on the curve. Thus, we can replace the point kP by an equivalent point representation dP utilizing the negative of point. For a secret scalar k (integer number), by the point kP, we get an equivalent points representation dP by following the equations, in a general case: We use an example of the above description in order to better express our reduction method.

                       a. If k > n , kP = dP where d = (k -k/2.n); b. If k ∈ ]n/2, n-1], kP = dP where d = (k -n); c. If k ∈ ]0, n/
Example: We choose the prime number p =23. Note that this process mainly reflects our new protocol. In real cases, the p is much bigger than this. If we consider the elliptic E over F 23 defined by E (F 23 ):

y 2 =x 3 +x+1, then # E (F 23 )=28, E (F 23
) is a cyclic group. Let P (0,1) be a generator point. The points in E (F 23 ) are shown below: general case from Figure 1 that the points -34P, -6P, 22P, 50P have the same coordinates. To process the point -6P (the negative of 6P ), we compute the point 6P and affix the minus sign to the y-coordinate. Thus, computation of -6P is free and almost equal to computing 6P . The scalar multiplication using our method in the the general case would be computed as follows:

to calculate 50P, we compute -6P by applying formula; (6.a) to calculate 22P, we compute -6P by applying formula; (6.b) to calculate -34P, we compute -6P by applying formula. (6.g) On the other hand, for the special case of ECC, we can see from Figure 2 |k|P , see formula [START_REF] Longaanda | Fast and Flexible Elliptic Curve Point Arithmetic over Prime Fields[END_REF].

n-1 k=1 kP = 2 n/2-1 k=1 kP + n 2 P + 2 n/2-1 k=1 kP (8)
By using our method, the equation ( 8) can be replaced by equation ( 9):

n/2-1 k=1 kP + n/2-1 k=1 |k|P + n 2 P. (9)
By scanning all scalars k for computation of kP in the interval [n/2+1, n-1 ],we can see from formulas ( 8)-( 9), that we gain a rate of n/2-1 k=1 2kP . The speed-up for a given scalar kP is 2(k-(n/2)). For example, in Figure 2, computing kP =22P, is equal to computing 6P, the speed-up is 2(22-(14/2))= 16P since 16P + 6P = 22P. In fact, the complexity of scalar multiplication is determined by the length bit of k which is equal tolog 2 (k)+1 or log 2 (k) if k=2 x , where x is an integer. In binary representation, log 2 (k) can be replaced in our method by:

log 2 (k -2(k - n 2 )) = log 2 (k) + log 2 (k + n -2k k ) ( 10
)
Thus, the speed-up in length bit is:

|log 2 (k + n -2k k )| = |log 2 ( |d| k )|, where log 2 (k + n -2k k ) < 0.
Since our reduction method is not possible for n=1, from Figure 3 our method is not used since its design is only for the interval [n/2+1, n-1 ]. Consequently, it is very efficient in Figure 3,in which we only consider scalars in this interval. From formula [START_REF] Wu | Partitioned Computation to Accelerate Scalar Multiplication for Elliptic Curve Cryptosystems[END_REF], we make the average computation of all scalar k in interval[n/2 + 1, n -1], where our technique can be applied

1 n -1 -n/2 ( n-1 k=n/2+1 kP ) = 1 n -n/2 ( n/2-1 k=1 kP ). ( 11
)
The average of scalar k can be found in Figure 4, where we can also apply our technique in the interval[n/2+1, n-1].

Optimization can be done in the interval [n/2+1, n-1] by using only even numbers for order n. If the order n >2 is an even number: If the order n ≥3 is an odd number:

3 n/2-1 k=1 kP > n-1 k=n/2+1 kP ≥ 2 n/2-1 k=1
kP . Figure 5 shows the speed-up between even and odd numbers. We can see that Fig. 5. Speed-up rate between even and odd order if n is even, the speed-up curve is a horizontal line whose equation is y=3. But if n is odd, the line y=3 is a horizontal asymptote for the speed-up curve. If we work with even order, the speed is three times faster. If the order is odd, the enhancement is > 2, and < 3.

Efficiency analysis

The unit of this speed-up can be the length bit or the number of doubling/addition operations. For example, NAF needs log 2 (k) doubling and log 2 (k)/3 addition. In the interval [n/2 + 1, n -1], three cases are possible for the speed-up:

-If log 2 (n)=x, where x is an integer, our method can speed up the scalar multiplication in interval [n/2 + 1, n -1] by reducing the length bit of k. -If log 2 (n)=x, where x is not an integer, our method can speed up the scalar multiplication only in interval [2 log2 n 2

+1

, n -1] -If k= (n-1), we reach the maximum speed-up, the length bit of the scalar k is maximum (equal to log 2 (n -1), where it is equal to one bit for d. In this case, our method does not require computation.

From Table 1 and Table 2, we can see the speed-up in length bit for some values of the scalar k.

Table 1. Speed-up S for some values of k for x integer.

Values of k n/2 + 1 >=(n/2 + 1) (n-1) Speed-up(bits) 1 1 < S < log2(k) log2(k)
Table 2. Speed-up S for some values of k for x not integer.

Values of k 2 log 2 n 2 +1 >= 2 log 2 n 2 +1 (n-1)
Speed-up(bits)

1 1 < S < log2(k) log2(k)

Performance Evaluation

To test the performance of our solution, we have implemented a simulator in Java. The program is then run on an Intel Core i5-2520 processor taking into account the computing power difference between this processor and a MSP 430 MCU. During the test, we choose an elliptic curve over F p using NIST-192 recommended parameters which are given in Table 3. p is the size of prime field F p , and a, b are coefficients of the simplified Weierstrass form of our curve. P (x P , y P ) is chosen as the generator point, and its order equals n.

As indicated in equation (6.b), when we need to perform a scalar multiplication kP for cryptographic purpose, we choose k < n where n is the order of the generator point P , which means nP = ∞. In addition, theoretically our method works only when k ∈] n 2 , n-1]. To prove this property, we have chosen 6 values of 192 bits for k which are distributed uniformly in ]0, n -1] (see table 4).

We have tested our method using both affine and jacobian coordinates, the scalars are represented respectively in binary and NAF form combined with the proposed scalar reduction method. The test results are given in tables 5 and 6, and illustrated graphically in figure 6 and7.

Parameter NIST-192 recommended values p 2 192 -2 64 -1 a -3 b 0x 64210519 e59c80e7 0fa7e9ab 72243049 feb8deec c146b9b1 xP 0x 188da80e b03090f6 7cbf20eb 43a18800 f4ff0afd 82ff1012 yP 0x 07192b95 ffc8da78 631011ed 6b24cdd5 73f977a1 1e794811 n 0x ffffffff ffffffff ffffffff 99def836 146bc9b1 b4d22831 6279 6325 5320 6445 6556 28 Table 5. Running times (ms) using affine coordinates (SR: Scalar reduction) Fig. 6. Running times (ms) using affine coordinates

In both cases, we can notice that, firstly when the scalar is in NAF form, the computation is faster than the one using binary form. Secondly when k ∈]0, n 2 ], we cannot apply the proposed scalar reduction method. However, if k ∈] n 2 , n-1],

we may accelerate slightly the computation by reducing the scalar. Especially when the value of k is close to n-1, the computation can be done instantaneously since (n -1)P = -P . When we use jacobian coordinates, as we don't need to repeat the modular inverse (see equation ( 5)), the computation is obviously faster than the first case. Same as the results obtained using affine coordinates, our scalar reduction method can be used during the computation only when k ∈] n 2 , n -1]. When it's applied, the scalar is reduced, and the computation can run faster.

According to the results of performance evaluation, our scalar reduction method does speed up the computation of scalar multiplication on a standard NIST-192 elliptic curve. The acceleration rate strongly depends on the value of the scalar used. The scalar k can be reduced if k ∈] n 2 , n -1], and once applied, the computation task can be simplified and carried out more quickly.

Conclusion

In this paper, we have proposed a novel method based on point order and the negative of point to speed up the computation of scalar multiplication on elliptic curve cryptosystems. On one hand, the proposed method will significantly reduce the computation time in the interval [n/2+1, n-1 ]. On the other hand, we show that the usage of even order is more efficient than odd order. Our method is a very suitable tool for embedded devices such as WSNs. Also, it can be easily applied to almost all existing fast scalar multiplication methods as shown in NAF. Thus, that's comparisons are nor required regarding some existing schemes. Additionally, a thorough analysis and simulation based on evaluations will show that the proposed solution does speed up the computation of scalar multiplication on a standard NIST-192 elliptic curve. Our future research plans will be oriented towards experimenting our current technique on real sensor nodes with elliptic curves over finite prime fields.

6 )

 6 2], kP = dP where d = k; d. If k=n or 0 or -n, kP = ∞; e. If k ∈ [-(n-1), -n/2[, kP = dP where d = (n + k); f. If k ∈ [-n/2, 0[, kP = dP where d = k; g. If k <-n, k P=dP where d =k +n.|k|/2. (In Elliptic Curve Cryptography k ∈ ]0, (n-1)], we get an equivalent representation for point dP by equations (6.b) and (6.c) following: (b) If k ∈ ]n/2, n-1], kP = dP where d = (kn); (c) If k ∈ ]0, n/2], kP = dP where d = k.

Fig. 1 .

 1 Fig. 1. General elliptic curve case

  that computing the points from [15P,16P,.........26P, 27P ] can be replaced respectively by [-13P, -12P,.........,-2P, -P ]. In this case, computing 27P can be replaced by -P and is almost free.

Fig. 2 .kP

 2 Fig. 2. Elliptic Curve Cryptography case

Fig. 3 .

 3 Fig. 3. Sum of all k values function of order n in [n/2+1, n-1]

Fig. 4 .

 4 Fig. 4. Average of all k values function of order in [n/2+1, n-1]

Fig. 7 .

 7 Fig. 7. Running times (ms) using jacobian coordinates

Table 3 .

 3  recommended elliptic curve parameters

	k Value in hexadecimal
	n/6 0x 2aaaaaaa aaaaaaaa aaaaaaaa 99a5295e 58bca19d 9e2306b2
	n/3 0x 55555555 55555555 55555555 334a52bc b179433b 3c460d65
	n/2 0x 7fffffff ffffffff ffffffff ccef7c1b 0a35e4d8 da691418
	2n/3 0x aaaaaaaa aaaaaaaa aaaaaaaa 6694a579 62f28676 788c1aca
	5n/6 0x d5555555 55555555 55555555 0039ced7 bbaf2814 16af217a
	n -1 0x ffffffff ffffffff ffffffff 99def836 146bc9b1 b4d22830

Table 4 .

 4 Values of k chosen for performance evaluation

	√ √ √ √	6579 6572 7604 6555 6931 7471 6282 6326 5317 6239 6698 5114 6578 6573 7600 6416 6600 27

NAF SR n/6 n/3 n/2 2n/3 5n/6 n -1

Table 6 .

 6 Running times (ms) using jacobian coordinates (SR: Scalar reduction)

	NAF SR n/6 n/3 n/2 2n/3 5n/6 n -1 3066 3102 3621 3072 3202 3520 √ 3053 3074 3592 3071 3189 3541 √ 3070 3100 3622 3030 3107 9 √ √ 3050 3075 3597 3194 3136 9