Marie Delaplace
email: marie.delaplace@u-pem.fr

Francesca Pagliara

Anne Aguiléra

High-speed Rail Station, Service Innovations And Temporary Office Space For Mobile Workers A Comparison France/Italy

Keywords: High-Speed Rail station, temporary office spaces, service innovation theories, mobile workers

Major investments on High Speed Rail (HSR) systems have been carried out all over the world. The existing and planned lines generate many expectations in served cities in terms of economic growth. In particular, HSR is intended to increase the number of business travellers and to foster economic activity by encouraging the development of offices in and around the railway stations. Using innovation service theories, we show that HSR service can be analysed as service innovations. Based on the case study of France and Italy, we sustain that these innovations can be of interest of both public and private actors in terms of urban renewal. We show that, in these two countries, there is the same kind of "behaviour" with respect to these innovations in terms of producing temporary office spaces in and around rail stations. The result is that HSR stations become working spaces and therefore important "places".

Résumé

Il existe de nombreux projets de desserte ferroviaire à grande vitesse dans le monde, qui suscitent une multitude d'attentes dans les villes desservies en termes de croissance économique. La grande vitesse ferroviaire pourrait accroître le nombre de travailleurs mobiles et booster l'activité économique en encourageant le développement de bureaux dans et autour des gares. A partir des théories de l'innovation dans les services, nous montrons qu'une desserte ferroviaire à grande vitesse peut être analysée comme un ensemble d'innovations de services. A partir du cas de la France et de l'Italie, nous mettons en lumière que ces innovations peuvent être appropriées par des acteurs privés et publics en termes de renouvellement urbain. Nous montrons que, dans ces deux pays, ces acteurs vont développer le même type d'appropriation de ces innovations en proposant une offre de bureaux temporaires en location dans et autour des gares à accueillant la grande vitesse. Cette appropriation fait des gares des espaces de travail et les conforte en tant que lieux.

Mots-clé: Gare TGV ; location temporaire de bureau ; théories de l'innovation dans les services; travailleurs mobiles.

Introduction

Major investments on High Speed Rail (HSR) systems have been carried out all over the world. According to UIC (UIC, 2013) in July 2013, all over the world, 21365 km are operational, 13964 km are under construction and 16347 are planned by 2025. The existing and planned lines generate many expectations in served cities in terms of economic growth (for a review, cf. [START_REF] Bazin | Grande vitesse ferroviaire et développement économique local : une revue de la littérature[END_REF]. In particular, HSR is intended to increase the number of business travellers and to foster economic activity by encouraging the development of offices in and around the railway stations.

Based on service innovations theories, we analyse HSR as service innovations compared to the classical railway system. Then the focus will be on the comparison between France and Italy in terms of service innovations and appropriation of these innovations by public and private actors through urban renewal in the HSR stations and the surroundings. We show that in these two countries, there is the same kind of appropriation of these innovations for producing business offices and more specifically temporary office spaces.

The paper is divided into four sections. The first section gives a brief overview of the HSR systems in France and in Italy. The second section of the paper analyses the service innovations associated to HSR regarding the transport system. The third section discusses the forms of appropriation of these service innovations in France and in Italy regarding the provision of office spaces and especially temporary office spaces for mobile professionals in and around the stations. Conclusions are finally reported in the last section.

A brief overview of HSR system in France and in Italy

The development of the High Speed/High Capacity network in Italy is embedded in the wider context of the Trans European corridors. In 2000 Italy had 248 km of HSR line, those from Rome to Florence; around half of those of Germany and Spain and even one fifth of those of France. In 2006 there were 562 km due to the opening of the Rome-Naples and of the Turin-Novara sections. In 2013, 923 kms are in operation. Once the whole HSR project is completed in 2014, most major cities will be connected to the network (Figure 1). The key objective for the construction that is currently underway is to raise the Italian rail network to the best European standards and to improve its capacity.

The HSR in Italy consists of two lines connecting most of the country's major cities. The first line connects Milan to Salerno via Bologna, Florence, Rome and Naples, the second runs from Turin to Venice via Milan, and is under construction in parts. Lines are designed for a top speed of over 300 km/h. 25 million passengers travelled on the network in 2011. Service is provided by Trenitalia and since April 2012 by NTV. Several projects are underway to expand the system. Plans include both more domestic connections such as to Genova, and new international connections to France, Austria and Slovenia. After the completion of the HSR system there will be a reduction in travel time between the major cities connected of almost 40-50%.

In France, since the opening of the first line between Paris and Lyon in 1981, HSR and train services have been mainly developed through radial axes from Paris. In 2013, the HSL is 2 036 km long (UIC, 2013). In France, HSR network is connected to the conventional rail network, and HST rolling stock is compatible on both networks, allowing a large and direct accessibility of HSR services in the French territory. In France, there are less than 20 HSR stations but about 200 stations served by HST (Figure 2).

Services innovations associated to HSR in France and in Italy

Using theories of service innovation (3.1), HSRS can be analysed as improvement innovations (3.2) and incremental innovations with regards to a classical railway service [START_REF] Delaplace | TGV, développement local et taille des villes ; Une analyse en termes d'innovation de services[END_REF].

The theories of service innovation, a useful tool to analyse HSRS

Besides their immaterial character, what distinguishes the services is their relational character between the provider and the user [START_REF] Howells | Services and innovation and service innovation: new theoretical directions[END_REF] and this service relation takes place in times and in space. Using the analysis of [START_REF] Gallouj | Innovation in Services[END_REF] improved [START_REF] Vries De | Innovation in services in networks of organizations and in the distribution of Services[END_REF], a service can be represented by vectors of technical characteristics, services characteristics and competences of the client and of the provider(s).

The rail service is characterized by technical characteristics (T 1 , T 2 … T n ) linked to the product "train" (the kind of engine of the train -diesel or electric, the power of the train, the braking system, railway cars stabilization system or size). Some other technical characteristics are linked to the infrastructure (type of lines (specific or not) type of railroad (rail gauge, compatibility of the different railroads) or to train station (architecture, centrality, types of rail connection, of intermodality, etc.). Some others are intangible like for instance, methods and procedures to define a schedule that will allow different trains to circulate on the network. The client can himself use tools allowing him to interact with the technical characteristics of the service provider(s). It is the case for example when a client books his train ticket using the Internet with his personal computer. Consequently we must take into account a vector of technical characteristics for the client must be introduced (T' 1 , T' 2 … T' o ), [START_REF] Vries De | Innovation in services in networks of organizations and in the distribution of Services[END_REF].

The rail service is also characterized by service characteristics (Y 1 , Y 2 …Y m ), called final characteristics which are related to the utilities and how there are perceived by the user (speed, safety or comfort, or in the case of an electric engine, low pollution trains). These final characteristics are also related to additional services such as food, Wifi connection, electrical outlet, etc. and/or in the train station or near it (car parks, car rental, travel agencies, hotels, Newsstands, cash machines, urban and inter-urban transports, etc.). As other services, the rail service is produced in interaction between the provider(s) and the client who both needs some competencies that can be represented as vector of competencies (C 1 , C 2 … C p ), for the provider(s) and (C' 1 , C' 2 … C' q ) for the client(s). Using this framework, we can analyse HST and HSRS as a set of improvement and incremental innovations with regards to the train and to the classic rail service [START_REF] Delaplace | TGV, développement local et taille des villes ; Une analyse en termes d'innovation de services[END_REF].

HSRS, as improvement and incremental innovations

An improvement innovation consists of improving some technical or service characteristics, and/or some competences, without changing the structure of the system. For example, the value of Y i is increased, the competence C k or the technical characteristic T j is improved.

HSRS is an improvement innovation of technical characteristics (for instance motor power, kind of HSL and HST, etc.). This train circulates at high speed (its definition varies according to authors (over 200km/h, 240 or 250 km/h)), sometimes on specific tracks, sometimes on existing lines.

HSRS can also be seen as an improvement innovation of the final characteristics of services † . The commercial speed is improved, reducing journey length. The magnitude of this service innovation will be even stronger as the speed is high. It depends on the technical characteristic of HSTs and/or on infrastructures [START_REF] Campos | Some stylized facts about High-Speed Rail: A review of HSR experiences around the world[END_REF]; for example, is the service handled on specific tracks or on classical ones?

HSRS can also be analysed as incremental innovations. According to Gallouj and Weinstein, an incremental innovation, is an innovation which corresponds to the addition of one or more new service characteristics (Y 4 , for example), that rises the utility of the agents but again without changing the structure of the system. It is the case when, a new High-Speed Transport Service is supplied to the travellers which use it (for instance the possibility to travel at high-speed and to connect with Wifi at the same time). These innovations which need new technical characteristics can increase the number of users.

More basically, the HSRS adds a new characteristic, in term of modernity, to the traditional rail service that can be described as semiotic in the sense that it conveys a sign to numerous stakeholders of either served or not cities. Like a fashion brand has a specific utility which is to distinguish the person who wears it, the HSRS provides a distinctive sign to the cities, a new image (cf. [START_REF] Bazin | Grande vitesse ferroviaire et développement économique local : une revue de la littérature[END_REF], for a review of literature on this subject).

Furthermore, as [START_REF] Bertolini | Cities on rails: The redevelopment of railway station areas[END_REF] have argued a train station as a transport node should ideally also be a significant place in the city. However, this rarely seems to be the case, and the resolution of this disparity, which they refer to as the "node-place" problem, in practice means redesigning what are currently national-to-regionalto-local transport nodes to also function as local pedestrian nodes. This is a complex design task [START_REF] Cascetta | Integrated Railways-based Policies: The Regional Metro System project of Naples and Campania[END_REF]. But HSRS tends to increase the importance of the train station as a place (cf. also [START_REF] De | European high-speed train station area: the renaissance of the railway station[END_REF][START_REF] Mannone | Gares TGV et nouvelles dynamiques urbaines en centre-ville : le cas des villes desservies par le TGV Sud-Est[END_REF], and particularly in our case a place to work.

In this respect, these innovations can be appropriated by private and public actors. They propose to renew the station and its neighbourhoods and, sometimes, some office spaces.

Forms of appropriation of HSRS innovations: the case of temporary offices in and around the station

HSRS gives new opportunities of development for the stations and their surroundings (4.1), particularly in terms of office and corporate real estate programs around the stations (4.2). Classical offices are proposed but also, very recently, temporary office spaces that are provided by different actors like Regus, Buroclub, Multiburo but also smaller ones (for example, RPAD in Reims, France). These temporary offices will meet the growing demand for drop-in workspace from the new breed of flexible worker who is required to embrace a nomadic work style. The providers propose to get a place to work without the costs of a full-time office, to host meetings, sometimes, to use collaborative workspace to bring together mobile workers. And more recently it is in the station that these offices are located. These solutions might allow avoiding unnecessary travel (4.3).

HSR and the renewal of the station and their surroundings

In Italy, HS hubs have become centres for services and urban redevelopment. The HS stations in the major metropolitan hubs of Turin, Milan, Bologna, Florence, Rome and Naples have been renovated or built from scratch to designs by renowned architects who have won international competitions. The first new HS station completed was Roma Tiburtina, inaugurated on 28 November 2011. Stations are considered as protagonists of significant urban redevelopment operations and the expression of a new architectural language, and conceived as spaces not only dedicated to railway activities but also meeting and communication places. The restyling of † It is important to quote that the importance of this innovation also depends on the quality of the previous rail service (cf. infra) and of the type of concerned actor: an innovation can be minor for the rail company and great for the client.

Roma Termini and more recently of Milano Centrale stations are pilot projects of the new way of interpreting stations as city squares. The redevelopment of Milano Centrale, centre of urban mobility and a real gateway to the city, also for future visitors to Expo 2015, marks a milestone in the expansion of regional and metropolitan transport and exploits the role of the station as a junction for the new High Speed/High Capacity lines. In Naples, the new High Speed station, designed by Zaha Hadid, built in the municipality of Afragola, will be integrated with the major roads and regional railway lines, which will have new stops. The four-level building will take up 20.000 m2 Afragola will be a strategic station for domestic and international traffic and it will be a fundamental junction point for the Naples -Bari line (Ferrovie dello Stato, 2012).

In France also, the central stations are renewed on the basis of the existing ones and in some cases new ones are built outside the city ‡ . The magnitude of the renewals depends on the size of the city and on the services. For example, on the South-east axis, for the stations that only benefit from a couple of daily stops, the renewal was minimal whereas some bigger cities with very good services the central station was fully renewed (Dijon, Chambéry) or a new station was built (Lyon Part-Dieu) (Manonne, 1997). Concerning the South West Line, the new Novaxis business center was built near the HSR station [START_REF] Chevalier | Perspectives technopolitaines et développement du centre d'affaires Novaxis[END_REF][START_REF] Bazin | Desserte TGV et localisation des entreprises sur les quartiers d'affaires: nouvelle accessibilité ou nouvelle offre immobilière de bureaux ? Le cas de la gare centre de Reims[END_REF][START_REF] Facchinetti-Mannone | L'implantation des gares TGV en France : tensions interscalaires, jeux d'acteurs et recompositions spatiales[END_REF]. Concerning the North HS Line, a new TGV station and a business centre, EuraLille, were conceived near the existing rail station [START_REF] Menerault | Dynamiques et politiques régionales autour du tunnel sous la Manche et du T.G.V. Nord[END_REF]. More recently, in the case of the East European High-Speed Line, news stations were built near the city (Champagne-Ardenne station) or outside (Meuse TGV, Lorraine TGV), and in bigger cities as Reims, Metz and Strasbourg, the central station was renewed to make it a new place in the city. Around the stations in an urban environment, business park or business centres were built and the district was renewed.

The development of office and corporate real estate programs around HST stations

HSRS can give birth to a development of office and corporate real estate programs around the station. The role of the HSR line in the location choice of firms and consequently its role in the attractiveness of served territories has been studied elsewhere [START_REF] Bazin | Desserte TGV et localisation des entreprises sur les quartiers d'affaires: nouvelle accessibilité ou nouvelle offre immobilière de bureaux ? Le cas de la gare centre de Reims[END_REF][START_REF] Facchinetti-Mannone | Location of high speed rail stations in French medium-size city and their mobility and territorial implications: central, peripheral and bis (both central and peripheral in the same city)[END_REF], 2010[START_REF] Willigers | High-speed rail's impact on the location of office employment within the Dutch Randstad Area[END_REF].

The real-estate investors get into position in different TGV cities in France: in Tours and Le Mans where the tourangeau promotor Art & Bat (groupe EPRIM) has invested, and in Reims with Lazard, Nacarat, Brooks or Montroyal Immobilier. According to [START_REF] Bazin | Desserte TGV et localisation des entreprises sur les quartiers d'affaires: nouvelle accessibilité ou nouvelle offre immobilière de bureaux ? Le cas de la gare centre de Reims[END_REF], the HSR service could reassure investors. In this respect, if the investment decision depends on many elements (expected profitability and so on), some elements are subjective ones, linked to the way the investors understand and analyse the risk of this investment. By producing an image effect in terms of dynamism and modernity, a HSR service can encourage the investors to consider locations that they don't consider before.

Moreover, as we put forward before, the HSR service induces urban renewal around the station. Public actors implement public policies to renew the station district. Therefore these actors give a positive message to the promoters concerning the future use of this district. If the new real-estate supply depends on promoters strategies, they also depend on public strategies (see also [START_REF] Mérenne-Schoumaker | L'émergence d'un marché d'immobilier d'entreprise[END_REF].

In the case of the arrival of a HS train to a city, these actors implement actions in terms of collective infrastructures development, parking creation, and so on. By releasing land due to the reorganization of the station, the HSR service can generate new opportunities in terms of real-estate. And this public policy encourages the promoters to develop a new business real-estate supply, around train station.

It was the case of many promoters which have located business centres around TGV stations in big cities asLyon Lille or in intermediate cities like Le Mans Reims, etc.. These strategies also encounter those of private actors in partnership with rail manager in the station itself. ‡ The outside stations were dedicated to the connexion between French provincial towns whereas central stations are dedicated to the connection with Paris.

Temporary offices spaces in and around the HSR stations: new work spaces of mobile workers

Temporary office spaces that can be analysed as service innovations are offered in and around stations (4.3.1). This supply of new work spaces makes the station a new place to work for the growing number of mobile workers (4.3.2). This is the case in France and in Italy (4.3.3).

The development of temporary offices, an analysis in terms of service innovations

Office rental can be analysed as a service. This service depends on technical characteristics of the office (surface, modularity, equipment, etc.), of the building (location, environmental quality, type of heating, etc.) and of the neighbourhoods (architecture, centrality, design, etc.). This service has also final characteristics related to the office (comfort, connection to the electric network, to the Internet, etc.) and to the building (security, comfort, etc.). Other characteristics depend on the neighbourhood: accessibility by public transport, parking facilities, access to shops and services, etc.). The service is co-produced by a provider (the company which sells the building or the provider itself) and the client itself who participates in the definition of the service and uses it.

If we consider the service innovation analysis then the rental of temporary workplaces (office, meeting room, etc.) can be considered as a set of innovations from the point of view of office & corporate real estate. Indeed it is an incremental innovation because it adds to the rental service new service characteristics that are chosen by the client (secretariat, printer, wifi, catering, etc.). From the customer point of view the service delivery can be considered as a form of externalization of a function of the company which fosters the implementation of innovations in work organization: temporary office rental is indeed characterized by a high flexibility at different levels: modular space and service delivery, simplification of the procedures, technical and administrative supports [START_REF] Aguiléra | Les espaces de travail temporaires dans les gares TGV : Une innovation de service pour la conquête du marché métropolitain des professionnels mobiles[END_REF].

Additionally temporary office rental in railway stations is also a commercial innovation from relational type [START_REF] Delaplace | TGV, développement local et taille des villes ; Une analyse en termes d'innovation de services[END_REF]. Indeed it corresponds to the establishment of particular relations between the stakeholders: clients, providers, public authorities, competitors, etc. and here in addition the station managers and the rail operators.

Hence it is also an incremental innovation from the point of view of the functionalities of the stations and especially HSR stations. Indeed if the station is a space characterized by passenger flows, temporary office rental allows mobile professionals to make profits of the time spent in stations and/or to decrease total travel time because they do not have to make additional trips from the station to meet clients, partners, etc.. The meeting can be organized in the station or in its surroundings. Hence from the point of view of the railway station manager, this service is an incremental innovation which contributes to optimize the waiting time spent between two trains. It increases the utility of the mobile professional, whose number is growing especially among managers and executives, because it contributes to increase their productivity In this respect, HSR stations are very important because the literature shows that executives foster HSR service [START_REF] Klein | Le TGV-Atlantique : entre récession et concurrence[END_REF].

The new market of mobile professionals

Physical mobility is typical of certain modern forms of work, in which there is a reduced adherence to predefined locations (Corso et al., 2006, Vilhelmson and[START_REF] Vilhelmson | Is regular work at fixed places fading away? The development of ICTbased and travel-based modes of work in Sweden[END_REF]. This kind of travel is an essential and probably growing component of work activity for a number of professional categories, including some of the selfemployed, executives and salespeople, as well as many company directors (Aguiléra and Proulhac, 2012;[START_REF] Haynes | Information and communication technology and international business travel: mobility allies?[END_REF]. The reasons behind the increasing demand for mobility are now relatively well identified (Aguiléra, 2008 and[START_REF] Aguilera | Business travel and sustainability[END_REF]: the globalisation of companies and markets, the expansion of multi-facility companies, the introduction of multi-site team working, the growing reliance on outsourcing and partnerships with other companies. These trends have effectively contributed to an overall increase in the need for companies to communicate with geographically remote interlocutors (customers, suppliers, etc.), It is however difficult to estimate the share of mobile workers. In France the survey by [START_REF] Boboc | Travailler, se déplacer et communiquer: premiers résultats d'enquête[END_REF] estimates that 13% of French workers are nomadic workers (no regular workplace) and 21% are partially mobile (regular workplace + irregular workplace= 15% and home + regular workplace + irregular workplace= 6%). In Italy, the phone survey by [START_REF] Corso | What knowledge management for mobile workers?[END_REF] shows that 46% of the firms had mobile employees but that they represented in general less than 5% of the workforce. Additionally the most relevant group of mobile workers are the sales force, the managers and the technicians (for on-site maintenance).

These data highlight the emergence of new and temporary workplaces also called third places [START_REF] Felstead | Rapid change or slow evolution? Changing places of work and their consequences in the UK[END_REF][START_REF] Moriset | Tiers-lieux de travail et nouvelles territorialités de l'économie numérique: Les espaces de coworking[END_REF]. They correspond on the one hand to a wide range of hybrid spaces dedicated both to private and professional practices (Internet cafes, hotel, airport, rail station, etc.) and, on the other hand, to spaces explicitly dedicated to temporary occupation by professionals: telecentres, co-working spaces and temporary offices for rent (an hour, a day, etc.) which offer specific services (meeting rooms, printers, etc.).

New work spaces, and especially temporary offices for rent, are dedicated firstly to workers who try to decrease commuting distance without working at home where they could suffer from social isolation, and secondly to mobile professionals who try to increase the productivity of business travel by working in good conditions while waiting for an appointment or a transport mean (a train, a plane, etc.) and/or by reducing overall distance travelled by organizing meetings in or near airports and rail stations i.e. in a highly accessible (and often central in the case of rail stations) location.

In this respect, there is a development of temporary office spaces in France and in Italy

The development of temporary office spaces in France and in Italy

In March 2007, Regus has signed a partnership with Thalys § . With this agreement, business men who move between Paris, Bruxelles, Amsterdam and Cologne and who are member of Cybelys Gold program from Thalys, can access to the 950 places of Regus in 70 countries all around the world. With this agreement, Regus clients owning a Network Access card and a ticket Thalys can access to the Thalys Lounge located in the Bruxelles-Midi station. These business men, can access to a working place with many services. The business lounges, offices and meeting room have been designed for them.

In France, in 2011, Gares & Connexions -the subsidiary of SNCF-has chosen Regus to develop projects of business centre in TGV station to make waiting rooms connected working spaces [START_REF] Aguiléra | Les espaces de travail temporaires dans les gares TGV : Une innovation de service pour la conquête du marché métropolitain des professionnels mobiles[END_REF]. Six test stations have been selected: Le Mans which will be inaugurated in the second semester 2013, Lille, Bordeaux in Saint Jean station, Nancy, in the SNCF business centre. In these two last cases, the opening is announced ** . The aim is to « develop a network of modern and innovating working spaces inside stations to meet the needs of mobile workers » (CP Gares & Connexions -Regus, 2011) and reduce loss of time: « there is an important demand for these spaces because they polarize flows, but also because they are ideal location for offices, allowing to reduce transport times » † † . For instance, the business centre which will be opened in Le Mans would allow to workers in Paris to « work on place one or two days a week to avoid two hours of transport » ‡ ‡ (ESSEC, 2013, p. 76).

In their services in Italy. People involved in the chemical industries (13%), in finance (11%), in insurance (11%), in tobacco industries (10%) are the main clients (www.assotemporary.it).

In Italy, like in other parts of the world, the Regus Gold Card gives unlimited access to all the facilities of Regus, distributed in 550 cities of 95 countries. It offers business lounge with work areas, free internet access and catering services. Thanks to the partnership between Trenitalia, the Italian State railways company, and Regus, since 2012 holders of Gold and Platinum Cartafreccia can have access to the 11 FrecciaClubs of the main Italian stations (number expected to grow in the coming years), even in the nine Regus centers, all within easy reach and in areas of great prestige. The agreement allows those who frequently travel on Trenitalia High Speed trains "Frecciarossa" and "Frecciargento" to enjoy unlimited access to Regus business lounge, as members of the Businessworld program. The benefits of the program include internet access and complementary refreshments in its 1,200 business lounges. Members also receive the discount on the rental of meeting rooms, one-day offices and videoconferencing services. The business lounge areas are reserved and comfortable, located in the central districts of major cities, where you can work at any time of the day. The products and services available include pc, wi-fi, internet, international newspapers, hot drinks, reception and secretarial services, meeting rooms, videoconferencing, pony express and international courier services, printing, photocopying and fax services.The Director of the Division of National and International Passengers Trenitalia, Gianfranco Battisti, hailed the agreement with these words: "We always want to offer the best to our customers. This new agreement confirms it. Access to Regus business lounge, in Italy and in the world, is a plus because it extends prestigious incentives and benefits to our customers even after they have reached their destination, helping them in their business and in their meetings " (www.fsnews.it). According to Mark Dixon (Regus, May 2012) this new generation of business centres in rail station can be analysed as "an extension of the Regus network to the mobility chain".

According to our analysis it is an incremental service innovation from the point of view of business real estate. This innovation allows to meet the growing demand of mobile workers (cf. supra). The location in the station adds news characteristics to the office rent: flexibility and modularity of the rent, in many locations, furthermore connected to the HSR network. By locating flexible working places in or around HSR station, these promoters contribute to the creation of a specific model that associates third places and mobile workers.

But beyond the individual interest of worker, and due to the development of business centre in the rail station and especially with the supply of meeting rooms, we can analysed the rail station as a destination for the « Professionnals » (Press release Gares & Connexions -Regus, 2011). The rail station gets new functionality: a working space in itself for mobile workers and therefore an important place.

Conclusions and further perspectives

This paper focuses on the innovations brought about by HSRS in terms of reduction of travel times, new image for the served cities, etc. Moreover, as airlines slash flights and cut spending in the wake of rising fuel prices, rail travel across Europe is indeed entering into a period of renewal. A journey on HS train Eurostar between London and Paris generates one-tenth of the carbon dioxide produced by an equivalent flight. Rail's city-centre-to-citycentre service is also becoming an increasingly attractive alternative to flying. Research has shown that business travelers are now willing to travel up to four hours on rail because of the increased productivity versus the airlines. Leisure travelers are prepared to go further, using trains on journeys of up to six hours. These concerns are becoming now very common, but our contribution goes even further. We argue that HSRS also lead to other important innovations in rail stations that reinforce HSR stations as "places", according to the Bertolini and Spit's theory. The revolution brought by Regus and other companies deserve attention. It is indeed something that in the past would not have ever happened. Temporary offices for mobile workers placed within the station can modify the professional trip behaviour and change the door to door professional trip.

Further research will focus on testing these hypotheses, by building up a questionnaire to identify the motivations for which mobile workers find these temporary offices appealing. Therefore it will be possible to identify the differences between these business centres nearby or within an HSR station and other business centres.

Figure 1 :

 1 Figure 1: The HS/HC rail system in Italy Figure 2: High speed lines and high speed rail services in France (Delaplace and al., to be published)

  Italy, the development of Flexible work-places in train station emerges with the partnership between Trenitalia and Regus. Regus started in Italy in 1996. Milan Duomo, Torino Street 2 was opened at that time. Milan Montenapoleone at Monte di Pietà Street 21, was opened in 1998 as well as Rome Popolo, at Popolo Square 18, inside the prestigious Palazzo Valadier; following Milan North Park in 1999, Milan Velasca in 2000, Milan Brera in 2001 together with Rome Barberini and Rome EUR. In 2008 new offices are opened in the thirdItalian city, Turin, as well as their sixth centres in Milan, Carrobbio, a few steps away from the main square where the famous cathedral is placed. In September 2013 the Naples Centre will open, exactly inside the HS Garibaldi Railway Station. Since Regus opened in Italy, centres occupancy has always been above 85 % and the trend is still the same. In its centres there are co-working spaces where different companies can share their space. The services offered for mobility workers are business lounges, videoconferencing services, day office services and meeting rooms. Last year Regus was able to report the statistics of the typology of mobile workers using

§ http://www.topmanagement.net/tm.net/f/shared/Show1Inet.asp?ID=26750629&COUNTRY= ** And Amiens which has no high-speed rail service. † † Interview of Frédéric Bleuze, ESSEC, 2013, P. 76 (our translation) ‡ ‡ Interview of Frédéric Bleuze, ESSEC, 2013, P. 76 (our translation)


domain: info math

text:
J C Bajard

S Duquesne

M Ercegovac

COMBINING LEAK-RESISTANT ARITHMETIC FOR ELLIPTIC CURVES DEFINED OVER F p AND RNS REPRESENTATION by

Keywords: 2010 Mathematics Subject Classification. -14G50. Key words and phrases. -Elliptic curves, Montgomery ladder, leak-resistance, residue number system (RNS), modular multiplication, modular reduction

In this paper we give a survey of a method combining the residue number system (RNS) representation and the leak-resistant arithmetic on elliptic curves. These two techniques are relevant for implementation of elliptic curve cryptography on embedded devices.

It is well known that the RNS multiplication is very efficient whereas the reduction step is costly. Hence, we optimize formulae for basic operations arising in leak-resistant arithmetic on elliptic curves (unified addition, Montgomery ladder) in order to minimize the number of modular reductions. We also improve the complexity of the RNS modular reduction step. As a result, we show how to obtain a competitive secured implementation.

Finally, we show that, contrary to other approaches, this method takes optimally the advantage of a dedicated parallel architecture.

Introduction

Elliptic curve cryptosystems (ECC) have become popular to such a degree that they have been recommended by the NSA in 2005 for public key cryptography. However, as usual in cryptography, the algorithms involved must be protected against side-channel attacks which take advantage of leaks of information during computations ( [START_REF] Kocher | Timing attacks on implementations of DH, RSA, DSS and other systems[END_REF][START_REF] Kocher | Differential power analysis[END_REF][START_REF] Quisquater | ElectroMagnetic Analysis (EMA): Measures and Countermeasures for Smart Cards. e-smart[END_REF]). There are two types of such attacks, the simple power analysis (SPA) and the differential power analysis (DPA). In particular, elliptic curves are especially sensitive to SPA because of the difference in complexity between the addition of two points and the doubling of a point. Two ways have been used in the past 10 years to deal with this: the use of unified addition formulae ( [START_REF] Brier | Weierstrass Elliptic Curves and Side-Channel Attacks. Public Key Cryptography[END_REF][START_REF] Joye | Hessian Elliptic Curves and Side-Channel Attacks[END_REF][START_REF] Liardet | Preventing SPA/DPA in ECC systems using the Jacobi form[END_REF]) and the Montgomery ladder ( [START_REF] Brier | Weierstrass Elliptic Curves and Side-Channel Attacks. Public Key Cryptography[END_REF][START_REF] Fischer | Parallel scalar multiplication on general elliptic curves over F p hedged against Non-Differential Side-Channel Attacks[END_REF][START_REF] Izu | A Fast Parallel Elliptic Curve Multiplication Resistant against Side Channel Attacks. Public Key Cryptography[END_REF][START_REF] Montgomery | Speeding the Pollard and elliptic curve methods of factorization[END_REF]). Unfortunately these protections consequently increase the algorithmic cost of the scalar multiplication (λ times a point of an elliptic curve, λ is an integer) so that it is very important to reduce the cost of the base field arithmetic. In this paper, as common in ECC, the base field is a random prime field F p where the central operation is the modular multiplication. For standard representation of F p the multiplication and the reduction step have similar cost ([8, 36]). On the contrary, the Residue Number System (RNS) introduces a gap of complexity between the multiplication and the reduction steps. Indeed, it allows a very efficient multiplication by distributing the computations on small independent integers whereas the reduction step remains costly. The RNS has other advantages. In particular, it is easily parallelizable and it is not specific to a value of p contrary to Mersenne number based arithmetic. The aim of this paper is to combine SPA-resistant arithmetic on elliptic curve and the RNS. To obtain an interesting and efficient combination, we work on two aspects: -The adaptation of the RNS reduction to the context of ECC (Section 3). It merges ideas from [START_REF] Bajard | Selected RNS Bases for Modular Multiplication[END_REF] and [START_REF] Bajard | Efficient RNS bases for Cryptography[END_REF] and leads to intermediate RNS bases which are less restrictive than [START_REF] Bajard | Selected RNS Bases for Modular Multiplication[END_REF] and more efficient than [START_REF] Bajard | Efficient RNS bases for Cryptography[END_REF]. We give a detailed complexity study of this algorithm and use it to provide comparisons between RNS and standard arithmetic in Section 5. This is made in a context as generic as possible (architecture for which additions and shifts are more efficient than products). -The modifications of the formulae on elliptic curve for minimizing the number of modular reductions (Section 4), in exchange for an increased number of multiplications with respect to the RNS properties (i.e. costly reductions and cheap multiplications). In several cases, we propose new formulae adapted to these RNS features.

Background properties of the different representations and algorithms

2.1. Modular multiplication. -Let us assume that p < β n and that elements of F p are given in radix representation (i.e., X = n-1 i=0 x i β i with 0 ≤ x i < β). The elliptic curve arithmetic over F p mainly involves modular multiplications modulo p. Because of the small size of the numbers used in ECC (192 to 512 bits, i.e., n = 6 to 16 32-bit words), the multiplication is performed by the schoolbook method with a complexity of n 2 word operations. Indeed, for the current ECC key size, Karatsuba or Toom-Cook approaches remain costlier, as discussed in the study made by the GMP group (1) . The reduction step consists of finding the remainder of the Euclidean division by p. It can be substantially speeded up by using the Montgomery reduction or by using a special modulo.

2.1.1. Montgomery general reduction algorithm. -In [START_REF] Montgomery | Modular multiplication without trial division[END_REF], Montgomery proposed to substitute the reduction modulo p by a division by a power of the radix β (i.e., a simple shift). The result is not exactly X mod p but Xβ -n mod p. This can be overcome by using Montgomery representation where X ′ = X × β n mod p.

Algorithm 1: Montgomery p (R)

Data: R = A × B < pβ n , p < β n , the precomputed value -p -1 mod β n ; Result: r such that r = β -n mod p, with r < 2p; q ← -R × p -1 mod β n ; r ← (R + qp)/β n ;
The complexity of this reduction is n 2 + n word operations [START_REF] Bosselaers | Comparison of the three modular reduction functions[END_REF]. As r < 2p, a comparison and a final subtraction could occur, but the output of Algorithm 1 can be used as input by adding a condition on p, specifically 4p < β n . Finally, for A < β n , its Montgomery representation is obtained via Algorithm 1 with R = A × (β n mod p). Similarly, if A ′ is the Montgomery representation of A, we recover A using Algorithm 1 with R = A ′ . However, since all the computations can be done in Montgomery representation, we ignore the cost of the conversion between Montgomery and classic representation.

2.1.2. Reduction using special modulo. -When p has some special form (as generalized Mersenne prime [START_REF] Chung | More generalized Mersenne numbers[END_REF][START_REF] Solinas | Generalized Mersenne numbers[END_REF]), the modular reduction can be performed with only some shifts and additions. This is used in most of the ECC standards but the main drawback is that a dedicated architecture is necessary which cannot be used for other prime fields. Consequently, it is not practical in either software or hardware implementation and many customers prefer flexible products. For this reason we do not consider this restrictive approach in this paper.

2.2.

Leak-resistant arithmetic in elliptic curve cryptography. -As it is the dominant operation in all elliptic curve based schemes (such as encryption/decryption or signature generation/verification), the scalar multiplication of points on the curve must be very efficient. It is usually done by using standard scalar multiplication methods (double and add, sliding window) combined with recoding of the exponent. However, these methods are not leakresistant which means that they are sensitive to side channel attacks like SPA or DPA. We are not interested in this paper in the protection against DPA. Indeed, in elliptic curve cryptography, this problem can be efficiently solved by randomizing the projective coordinates, the base point or the scalar [START_REF] Coron | Resistance against differential power analysis for elliptic curve cryptosystems[END_REF]. In general these protections do not affect the arithmetic algorithms. On the other hand protections against SPA consequently increase the algorithmic cost of the scalar multiplication and, therefore, must be implemented as efficiently as possible.

Currently there are two means to perform SPA-resistant arithmetic on elliptic curves. The first one is to use a representation of the curve for which the addition and the doubling can be done with the same formulae. In this work, we are interested in unified formulae for three representations of the curve: the Hessian form, the Jacobi form and the short Weierstrass form, but this can easily be generalized to other representations (as Edwards curves) with similar results. The second one is to use the Montgomery ladder where both an addition and a doubling are performed at each step of the scalar multiplication. As for unified formulae, this method is more efficient on restrictive models of the curve and we are dealing both with the restrictive and the general model in this work.

2.2.1. Unified addition formulae. -An elliptic curve in Hessian form is given by an equation

X 3 + Y 3 + Z 3 = 3dXY Z
where d ∈ F p is not a third root of unity. In [START_REF] Joye | Hessian Elliptic Curves and Side-Channel Attacks[END_REF], Joye and Quisquater described formulae for the addition of two projective points

(X 1 , Y 1 , Z 1 ) and (X 2 , Y 2 , Z 2 ):    X 3 = Y 2 1 X 2 Z 2 -Y 2 2 X 1 Z 1 , Y 3 = X 2 1 Y 2 Z 2 -X 2 2 Y 1 Z 1 , Z 3 = Z 2 1 X 2 Y 2 -Z 2 2 X 1 Y 1 . (1)
These formulae require 12 field multiplications and can be used both for addition and doubling because 2(X,

Y, Z) = (Z, X, Y ) + (Y, Z, X).
At the same time, the use of the Jacobi model was introduced by Liardet and Smart in [START_REF] Liardet | Preventing SPA/DPA in ECC systems using the Jacobi form[END_REF].

It is improved in [START_REF] Billet | The Jacobi Model of an Elliptic Curve and Side-Channel Analysis[END_REF] and, more recently, in [START_REF] Duquesne | Improving the Arithmetic of Elliptic Curve in Jacobi Model[END_REF]. It is easy to prove that any elliptic curve containing a 2-torsion point is birationally equivalent to a Jacobi quartic given by an equation

Y 2 = εX 4 -2δX 2 Z 2 + Z 4 . (2)
In this case, the formulae for adding two points are also valid for doubling:

   X 3 = X 1 Z 1 Y 2 + Y 1 X 2 Z 2 , Y 3 = (Z 2 1 Z 2 2 +εX 2 1 X 2 2 )(Y1Y2-2δX1X2Z1Z2)+2εX1X2Z1Z2(X 2 1 Z 2 2 +Z 2 1 X 2 2 ), Z 3 = Z 2 1 Z 2 2 -εX 2 1 X 2 2 .
In most cases, ε can be rescaled to a small value so that these formulae also require 12 multiplications [START_REF] Duquesne | Improving the Arithmetic of Elliptic Curve in Jacobi Model[END_REF]. However, these methods can only be used for curves having their cardinality even (Jacobi quartic) or divisible by 3 (Hessian form). To overcome this restriction, Brier and Joye give, in [START_REF] Brier | Weierstrass Elliptic Curves and Side-Channel Attacks. Public Key Cryptography[END_REF], unified formulae for the short Weierstrass form

(3) Y 2 Z = X 3 + aXZ 2 + bZ 3 .
Again, formulae given for the addition are also valid for doubling:

   X 3 = 2λ d λ 2 n -(X 1 Z 2 + X 2 Z 1 )(Y 1 Z 2 + Y 2 Z 1 )λ d , Y 3 = λ n 3(X 1 Z 2 + X 2 Z 1 )(Y 1 Z 2 + Y 2 Z 1 )λ d -2λ 2 n -((Y 1 Z 2 + Y 2 Z 1 )λ d ) 2 , Z 3 = 2λ 3 d , where λ n = (X 1 Z 2 + X 2 Z 1 ) 2 -X 1 X 2 Z 1 Z 2 + aZ 2 1 Z 2 2 and λ d = (Y 1 Z 2 + Y 2 Z 1 )Z 1 Z 2 .
However, these formulae are less efficient since they require 18 multiplications. Note that by using an isomorphism or an isogeny as in [START_REF] Brier | Fast Point Multiplication on Elliptic Curves Trough Isogenies, Applied Algebra, Algorithms and Error-Correcting Codes[END_REF], it is possible in most cases to rescale a to a small value and then to save one multiplication. This is explained and improved in Section 4.3 within Montgomery ladder context.

Publications mathématiques de Besançon -2013 2.2.2. Montgomery scalar multiplication. -Montgomery proposed in [START_REF] Montgomery | Speeding the Pollard and elliptic curve methods of factorization[END_REF] to work only with the x-coordinate. In this case, doubling is still possible but adding two points P and Q is possible only if P -Q is known (this is called pseudo-addition).

Proposition 1. -Let E be an elliptic curve defined over F p in Montgomery form:

BY 2 Z = X 3 + AX 2 Z + XZ 2 .
Let also P = (X P , Y P , Z P ) and

Q = (X Q , Y Q , Z Q ) ∈ E(F p )
given in projective coordinates. Assume that P -Q = (x, y) is known in affine coordinates. Then

X P +Q = ((X P -Z P )(X Q + Z Q ) + (X P + Z P )(X Q -Z Q )) 2 , Z P +Q = x ((X P -Z P )(X Q + Z Q ) -(X P + Z P )(X Q -Z Q )) 2 , X 2P = (X P + Z P ) 2 (X P -Z P ) 2 , Z 2P = 4X P Z P (X P -Z P ) 2 + A+2 4 4X P Z P , with 4X P Z P = (X P + Z P ) 2 -(X P -Z P ) 2 .
In this way, both a pseudo-addition and a doubling requires only 3 multiplications and 2 squarings, which is much faster than usual operations ( [START_REF] Cohen | Handbook of elliptic and hyperelliptic curve cryptography[END_REF]). However, the pseudo-addition is not sufficient for usual scalar multiplication algorithms. Thus, Montgomery introduced a new algorithm for computing kG using pairs of consecutive multiples of G, so that the difference between the two components is always equal to G: Algorithm 2: Montgomery_Scalar()

Data: G ∈ E (F p ) and k ∈ N * , k = t i=0 k i 2 i , k i ∈ {0, 1} Result:
The X and Z-coordinate of kG Initialize T = (O, G) where O is the point at infinity; For i from [log 2 k] to 0 do;

If k i = 0 then T = (2T [1], T [1] + T [2]) else T = (T [1] + T [2], 2T [2]); return T [1];
Both an pseudo-addition and a doubling are done for each bit of the exponent which ensure natural SPA protection. The cost of this algorithm is about 10 [log 2 k] multiplications which is better than other algorithms (even those which are not SPA-resistant). Finally, the xcoordinate of kG is usually sufficient but some cryptosystems, like ECDSA, require the ycoordinate but it can easily be recovered as explained in [START_REF] Okeya | Efficient Elliptic Curve Cryptosystems from a Scalar Multiplication Algorithm with Recovery of the y-Coordinate on a Montgomery-Form Elliptic Curve[END_REF]. Unfortunately, in odd characteristic, all elliptic curves cannot be transformed into Montgomery form (which implies even cardinality). The Montgomery ladder can be generalized to curves in short Weierstrass form but is more time consuming ( [START_REF] Brier | Weierstrass Elliptic Curves and Side-Channel Attacks. Public Key Cryptography[END_REF], [START_REF] Fischer | Parallel scalar multiplication on general elliptic curves over F p hedged against Non-Differential Side-Channel Attacks[END_REF] and [START_REF] Izu | A Fast Parallel Elliptic Curve Multiplication Resistant against Side Channel Attacks. Public Key Cryptography[END_REF]).

Proposition 2. -Let E be an elliptic curve defined over F p by equation [START_REF] Bajard | Residue systems efficiency for modular products summation: Application to Elliptic Curves Cryptography[END_REF]. Let also P = (X P , Y P , Z P ) and

Q = (X Q , Y Q , Z Q ) ∈ E(F p ) given in projective coordinates. Assume that P -Q = (x, y) is known in affine coordinates. Then X P +Q = -4bZ P Z Q (X P Z Q + X Q Z P ) + (X P X Q -aZ P Z Q ) 2 , Z P +Q = x(X P Z Q -X Q Z P ) 2 , X 2P = X 2 P -aZ 2 P 2 -8bX P Z 3 P , Z 2P = 4Z P X 3 P + aX P Z 2 P + bZ 3 P .
Hence, pseudo-addition requires 10 multiplications and doubling only 9. So, the scalar multiplication can be performed in about 19 [log 2 k] multiplications in F p . Note that the ycoordinate can also be recovered in this case ( [START_REF] Brier | Weierstrass Elliptic Curves and Side-Channel Attacks. Public Key Cryptography[END_REF]). In this paper, we use Residue Number Systems for the arithmetic on the base field. As a consequence, the cost of the multiplication becomes negligible compared to the cost of the modular reduction. Thus, it is necessary to rewrite the formulae given above in order to minimize the number of modular reductions.

Residue Number Systems

After a short introduction of these systems of representation (Section 3.1), we explain how the RNS bases used in this paper are selected. This choice is based on results that can be found in [START_REF] Bajard | Efficient RNS bases for Cryptography[END_REF][START_REF] Bajard | Selected RNS Bases for Modular Multiplication[END_REF]. But here, the number of possible RNS bases is much larger than in [START_REF] Bajard | Selected RNS Bases for Modular Multiplication[END_REF] which is very restrictive, and the performances obtained are clearly better than in [START_REF] Bajard | Efficient RNS bases for Cryptography[END_REF]. Then, we recall (Section 3.2) the translation in RNS of the well-known Montgomery algorithm for modular reduction [START_REF] Montgomery | Modular multiplication without trial division[END_REF] (see Section 2), as usually described in the literature [START_REF] Bajard | A RNS Montgomery's Modular Multiplication[END_REF][START_REF] Bajard | Modular multiplication and base extension in residue number systems[END_REF][START_REF] Kawamura | Cox-rower architecture for fast parallel montgomery multiplication[END_REF][START_REF] Posch | Modulo reduction in residue number systems[END_REF]. The main differences between these versions of this RNS Montgomery algorithm rely in the RNS bases conversions. We justify (Section 3.3) our choice of a conversion algorithm with respect to the bases selected in this paper. The complexity study (Section 3.4) supports our approach.

3.1. Representation. -The Residue Number Systems (RNS) are issued in a natural way from the Chinese Remainder Theorem (CRT). They are based on the fact that a number a can be represented by its residues (a 1 , a 2 , . . . , a n ) modulo a set of coprime numbers

(m 1 , m 2 , . . . , m n ), called RNS basis, thus a i = a mod m i = |a| m i . We generally assume that 0 ≤ a < M = n i=1 m i .
The elements a i are called RNS-digits, or simply digits if there is no ambiguity. The strongest advantage of a such system is that the operations on large integers are performed independently on the residues. These systems were introduced and developed in [START_REF] Svoboda | Operational Circuits. Stroje na Zpracovani Informaci, Sbornik III[END_REF][START_REF] Garner | The residue number system[END_REF][START_REF] Szabo | Residue Arithmetic and its Applications to Computer Technology[END_REF]. A good introduction can be found in [START_REF] Knuth | Seminumerical Algorithms[END_REF]. For constructing an arithmetic over F p , we assume that M = n i=1 m i is such that p < M . In this system, two numbers a and b can be represented by their remainders modulo the m

i , i = 1, . . . , n. a = (a 1 , . . . , a n ) and b = (b 1 , . . . , b n ) A multiplication modulo M is reduced to n independent RNS-digit products. (4) r = (|a 1 × b 1 | m 1 , . . . , |a n × b n | mn ) = a × b mod M Publications mathématiques de Besançon -2013
A RNS-digit product is equivalent to a classical digit product followed by a modular reduction modulo m i , which represents few additions (see [START_REF] Bajard | Efficient RNS bases for Cryptography[END_REF][START_REF] Bajard | Selected RNS Bases for Modular Multiplication[END_REF]). The digit modular reduction is frequent, so the choice of the RNS base appears to be fundamental in a such arithmetic. The bases considered in this paper are constructed for obtaining an efficient digit reduction. As in [START_REF] Bajard | Efficient RNS bases for Cryptography[END_REF], we consider RNS base (m 1 , ..., m n ) with elements such that, m i = 2 k -c i , where c i is small, and as in [START_REF] Bajard | Selected RNS Bases for Modular Multiplication[END_REF] we consider c i = 2 t i ± 1, with c i < 2 k/2 . For example, for m i < 2 32 , it is easy to find 16 coprime values with c i = 2 t i ± 1, with t i = 0...16 for c i = 2 t i -1 and t i = 1...15 if c i = 2 t i + 1. This ensures that c i < 2 16 . Then, if we want more co-prime values, we can consider the

c i = 2 t i ± 2 s i ± 1.
The reduction modulo m i is, in this case, obtained with few shifts and adds. For ρ < 2 2k (for example the result of a MAC operation with operands lower than 2 k ), we consider that

ρ = ρ h 2 k + ρ l = c i ρ h + ρ l mod m i
where the product by c i is just a shift and add processing. Hence, if we note

ρ ′ = c i ρ h + ρ l = ρ ′ h 2 k +ρ ′ l , we have ρ ′ < 2 3k/2 when ρ < 2 2k , thus we ensure that ρ ′′ = c i ρ ′ h +ρ ′ l ≤ 2(2 k -2 k/2
) < 2m i . This property confirms that the reduction part on each m i , in the case of a product (or MAC ) operations, represents around 10% of the total cost [START_REF] Bajard | Efficient RNS bases for Cryptography[END_REF][START_REF] Bajard | Selected RNS Bases for Modular Multiplication[END_REF][START_REF] Brent | The Area-Time Complexity of Binary Multiplication[END_REF].Then in the following we consider that an RNS digit-product is equivalent to 1.1 word-product (word = k-bits). We now focus on the multiplication modulo p using the Montgomery algorithm presented in [START_REF] Bajard | A RNS Montgomery's Modular Multiplication[END_REF][START_REF] Bajard | Modular multiplication and base extension in residue number systems[END_REF].

RNS Montgomery reduction.

-This algorithm is a direct transposition of the classical Montgomery method. The main difference is due to the representation system. When the Montgomery method is applied in a classical radix β number system, the value β n occurs in the reduction, division and Montgomery factor. In RNS, this value is replaced by M . Thus an auxiliary RNS base is needed to handle the inverse of M . Hence some operations will be performed on the two bases, it is the case of the initial product which costs 2n RNS-digitproducts. Algorithm 3 presents the RNS Montgomery reduction (c can be considered as the result of an RNS product on the two bases), where all the operations considered are in RNS. We specify on which basis they are done. q ← (c) × (-p -1 ) in B;

[q in B] -→ [q in B ′ ] First base extension; r ← (c + q × p) × M -1 in B ′ ; [r in B ] ←-[r in B ′ ] Second base extension;
Publications mathématiques de Besançon -2013

To summarize, q is computed modulo M , such that (c + q × p) is a multiple of M (thus its RNS representation in B is composed of zeros). Hence, we extend the representation of q in the base B ′ where M -1 exists and where (c + qp) × M -1 can be performed. Instructions 1 and 3 of Algorithm 3 deal with RNS operations as presented in the previous section, which are performed independently for each element of the basis, so they are very efficient. These two instructions represent 3n RNS-digit products (which is equivalent to 3 RNS-digit operations on a n cells parallel architecture). Instructions 2 and 4 are dedicated to RNS base extensions, and remain quadratic (or linear on an n-cells architecture). We can use different full RNS extensions as shown in [START_REF] Bajard | A RNS Montgomery's Modular Multiplication[END_REF][START_REF] Bajard | Modular multiplication and base extension in residue number systems[END_REF][START_REF] Kawamura | Cox-rower architecture for fast parallel montgomery multiplication[END_REF][START_REF] Posch | Modulo reduction in residue number systems[END_REF].

For two numbers a and b given in RNS, we compute c = a × b in RNS, then this algorithm actually evaluates r = abM -1 mod p. To obtain the right result, we need to use it again with r and (M 2 mod p) as operands. To avoid this, we convert the values in a Montgomery representation where a ′ = a×M mod p which is stable for Montgomery product and addition. This conversion is done once at the beginning by performing Montgomery product with a and (M 2 mod p) as operands, and once at the end of the complete cryptographic computing with 1 as second operand. Hence, this transformation will be neglected in the following. Moreover, as the RNS is not redundant, this representation is well suited for cryptography without any conversion [START_REF] Bajard | A full RNS implementation of RSA[END_REF].

3.3. RNS Base extensions. -For the RNS bases extensions, there exist two main approaches coming from the conversion from RNS to standard number systems. One proceeds directly from the CRT (Chinese Remainders Theorem) and looks like a Lagrange interpola-

tion a = n i=1 a i |M i | -1 m i m i M i M
, with M i = M/m i and |.| m the reduction modulo m. The other approach corresponds to a Newton interpolation using an intermediate representation calls Mixed Radix System (MRS), and is depicted later. The drawback of the CRT version can be described in two points: the modulo M operation which means that we must subtract to the summation a multiple of M , and the randomness of the M i which refrains from any improvement of the products by these values. To find the multiple of M , there are two main methods: one exact proposed in [START_REF] Shenoy | Fast base extension using a redundant modulus in RNS[END_REF] using an extra modulo, or one by approximation [START_REF] Posch | Modulo reduction in residue number systems[END_REF][START_REF] Kawamura | Cox-rower architecture for fast parallel montgomery multiplication[END_REF]. In [START_REF] Bajard | Modular multiplication and base extension in residue number systems[END_REF] the authors propose to avoid the calculus of this multiple for the first extension (the one of q). But in all the cases, the evaluation of the summation stays necessary and requests n multiplications-accumulations. As this operation must be done modulo each element of the new base (B ′ or B depending of the extension), the real cost in RNS is, at least, n 2 RNS-digit products. Due to our choice of bases, looking in detail the calculus, we prove that our approach is 30% better. We consider bases of the following form:

m i = 2 k -2 t i ± 1 (or 2 k -2 t i ± 2 s i ± 1 if we need more elements, see Appendices) with 2 t i ± 1 < 2 k/2 (
for ECC, k can be equal to 32, for keys up to 1024 bits and maybe more). Due to properties of such bases, the best alternative for the base extension is, a priori, the MRS approach. The MRS representation (ã 1 , ã2 , • • • , ãn ) of an integer a is such that:

(5)

a = ã1 + ã2 m 1 + ã3 m 1 m 2 • • • + ãn-1 m 1 m 2 ...m n-2 + ãn m 1 m 2 ...m n-1 with 0 ≤ ãi < m i
This MRS representation can be deduced modulo the m i directly from the RNS representation (a 1 , a 2 , • • • , a n ) with a classical radix conversion algorithm (which can be seen also as the

Publications mathématiques de Besançon -2013

Newton interpolation):

(6) ã1 = a 1 ã2 = (a 2 -ã1 )m -1 1,2 m 2 ã3 = ( (x 3 -ã1 )m -1 1,3 m 3 -ã2 )m -1 2,3 m 3 ã4 = ( ( (x 4 -ã1 )m -1 1,4 m 4 -ã2 )m -1 2,4 ) m 4 -ã3 )m -1 3,4 m 4 . . . ãn = (. ( (x n -ã1 )m -1 1,n mn -ã2 )m -1 2,n ) mn -. -ãn-1 )m -1 n-1,n mn
where m -1 i,j is the inverse of m i modulo m j , and (x 1 , x 2 , ..., x n ) is the RNS representation of a. We transpose Equation ( 5) modulo the elements of the new RNS base B ′ with j = n + 1...2n, applying the Horner scheme. ( 7)

a j = ã1 + m 1 |ã 2 + m 2 |ã 3 • • • + m n-2 |ã n-1 + m n-1 ãn | m j • • • | m j | m j m j
Due to the properties of the m i , this last transformation does not need any products, only shift and add operations.

We note that we use this MRS approach for the two base extensions of Algorithm 3. In [START_REF] Bajard | Efficient RNS bases for Cryptography[END_REF] the bases are more general with the form 2 k -c i , this work presents an RNS-MRS conversion using properties of the Montgomery reduction for the multiplication by the m -1 i,j , for that they need very small c i (few bits, 8 or 10), hence they maintain some products in the modular reductions over the bases elements. On the other hand, in [START_REF] Bajard | Selected RNS Bases for Modular Multiplication[END_REF] the goal was to construct optimal bases for all operations with sparse elements and constants, but the number of interesting bases is small and the elements are bigger (at least 64 bits). Here, we had observed that it is not the best choice to try to minimize the cost of the products by the m -1 i,j , it is really better to concentrate on the inner reductions of the RNS.

3.4. Analysis of the complexity. -To easily compare the RNS approach of this paper to classical number systems one, we evaluate the cost of Algorithm 3 by giving the number of word-multiplications needed, as it is commonly done in the literature. As it is written in the introduction we consider an architecture as generic as possible where additions and shifts are more efficient than products (and more however than division).

In step 1 and 3, the evaluations of q and r are made in RNS independently for each modulus. The value q is computed in the base B, which represents n RNS-digit multiplications by a constant value |p| -1 m i . The calculation of r involves 2n RNS-digit multiplications in the base B ′ . Now for the base extension, multiplications occur only in the conversion to Mixed Radix given by Equation 6. The number of RNS-digit multiplications by a constant (the

|m i | -1 m j ) is: (8) T RN S-M RS (n) = n 2 -n 2

RNSdigit-products

Publications mathématiques de Besançon -2013

In the conversion from MRS to RNS, the basic operation |a + m i b| m j is split in two: first we consider a + m i b = a + 2 k b -2 t i b ± b which is performed with two additions (a + 2 k b is just a concatenation), then we deal with the reduction modulo m j which represents 3 additions, as we note in section 3.1. We notice that we are not forced to make a complete reduction, we can move on the calculus with values lower than 2m j . This remark implies that 2 t i ± 1 < 2 k 2 -1 for a direct reuse of the result inside a series of calculus (for example in the Horner process). In fact, the only complete reduction modulo m j is requested at the last step of the construction of the MRS digits. Thus, the evaluation of each a j requests 5(n -1) word-additions. If we refer to Brent and Kung theorem [START_REF] Brent | The Area-Time Complexity of Binary Multiplication[END_REF], the ratio, taking into account the area, between the complexity of a multiplication and an addition is in Θ( √ k), which represents, for 32 or 64 bits words (and greater), a ratio α greater than 10 for a RNSdigit-product compared to an addition. Software algorithms are described in [START_REF] Brent | Modern Computer Arithmetic[END_REF], and hardware ones can be found in [START_REF] Ercegovac | Digital Arithmetic[END_REF]. ( 9)

T M RS-RN S (n) = 5 α (n 2 -n) RNSdigit-products
As we need two extensions in Algorithm 3, the total complexity of this algorithm is :

(10) T Algo3 (n) = n 2 -n + 2 5 α (n 2 -n) + 3n = α + 10 α (n 2 -n) + 3n RNSdigit-products
As α > 10, this approach is asymptotically better than previous results [START_REF] Kawamura | Cox-rower architecture for fast parallel montgomery multiplication[END_REF][START_REF] Guillermin | A high speed coprocessor for elliptic curve scalar multiplications over F p[END_REF] which are, at least, in 2n 2 .

If we operate with an architecture of n basic word-arithmetic cells, Algorithm 3 can be performed in a parallel manner. In this case, due to the independency of the RNS, the evaluation requires, (n -1) steps for the conversion RNS-MRS, and 5 α (n -1) for the RNS-MRS conversion, one step for each RNS product. Hence, a parallel evaluation of Algorithm 3 can be done in 2α+10 α (n -1) + 3 steps.

3.5. Discussion of the advantages of this approach. -Even though the number of operations needed for the reduction is somewhat higher than in a classical representation (n 2 + n) words products for the classical Montgomery reduction), RNS has some important advantages. In general, a modular reduction occurs after a series of operations such as a summation of products. Because in RNS additions and multiplications are very cheap, the gain obtained in the computation of these operations compensate the cost of the reduction. For example, Assuming that for ECC size (192 to 512 bits), the classical multiplication needs n 2 word-products, the RNS approach proposed in this paper is quite interesting, the modular multiplication which represents 2n 2 + n word-products in classical systems, is done in α+10 α (n 2 -n) + 3n × 1.1 word-products in RNS. Furthermore, due to the independence of the RNSdigit operations, computations can be performed in a random order and, consequently, the architecture can be parallelized. With n basic operators (arithmetic units), the time complexity of a modular multiplication can reach 2 modular digit-operations for the multiplication (or multiplication-addition) and 2α+10 α (n -1) + 3 for the modular reduction. These two points are developed in section 4, where by reformulating addition formulae on elliptic curves, we propose solutions up to 30% better than the classical approaches.

Publications mathématiques de Besançon -2013

Another advantage of the RNS is the flexibility of the architecture. With a given structure of n modular digit operators, it is possible to handle any values of p which satisfy : 4 × p < M . Thus, by reinitializing the pre-computed values of Algorithm 3, the system can be adapted for a new value of p. If p is relatively small as compared to M , we can adjust the RNS base by reducing the number of elements. We also note that all the products which occur in the RNS conversions, are with constant factors. Hence, some of them can be reduced to some shift and add operations. For example, in [START_REF] Bajard | Selected RNS Bases for Modular Multiplication[END_REF] the elements of the bases are selected for having low Hamming weight inverses. As, it is shown in [START_REF] Lefèvre | Multiplication by an integer constant: lower bounds on the code length[END_REF], there are many different rewriting ways for minimizing these products. For example, the constant can be decomposed in a product of two low Hamming weight factors. However, the present work is focused on a most general case for having a complexity study suitable to our objectives.

SPA-resistant arithmetic on elliptic curves optimized for RNS representation

The aim of this section is to rewrite or modify the formulae given in section 2.2 in order to minimize the number of modular reductions, since this is the most expensive operation in RNS representation. Thus we have to group together several multiplications before performing only one reduction.

4.1. Unified addition formulae. -This can be well illustrated by elliptic curves in Hessian form. We give here the steps required by the formulae [START_REF] Bajard | A RNS Montgomery's Modular Multiplication[END_REF].

step operations red. mul. computation of A = X 2 Y 1 , B = Y 1 Z 2 , C = X 1 Y 2 3 3 intermediate products D = Y 2 Z 1 , E = X 1 Z 2 , F = X 2 Z 1 3 3 computation of X 3 AB -CD 1 2 computation of Y 3 EC -F A 1 2 computation of Z 3 EB -F D 1 2
Thus the total cost in RNS representation is 9 modular reductions, which has to be compared to the 12 modular multiplications in standard representation. Concerning the Jacobi quartic, the cost in terms of modular reductions is given in [START_REF] Duquesne | Improving the Arithmetic of Elliptic Curve in Jacobi Model[END_REF] and is equal to 10, whereas 12 multiplications are necessary. Finally, we give details of the steps for computing the sum of two points using unified addition formulae for a curve given in short Weierstrass form. step operations red. mul.

λ n A = X 2 Z 1 , B = X 1 Z 2 , C = Z 1 Z 2 , D = aC 4 4 λ n = (A + B) 2 -AB + CD 1 3 λ d E = Y 1 Z 2 + Y 2 Z 1 , λ d = EC 2 3 intermediate F = Eλ d , G = λ 2 n , H = F (A + B) 3 3 X 3 2λ d (G -H) 1 1 Y 3 λ n (3H -2G) -F 2 1 2 Z 3 2λ 3 d 2 2
In this case, the total cost in RNS is 14 modular reductions, whereas 18 multiplications must be performed. Thus, the computation of unified addition requires fewer reductions than multiplications. This means that using the RNS representation can become attractive in terms of performance. A detailed comparison is given in Section 5.

4.2. Montgomery formulae. -We have seen in Section 2.2.2 that, in the restrictive case of curves in Montgomery form, 10 modular multiplications are required at each step of the Montgomery ladder but it is not possible to have less reductions because of the degree of the formulae. The case of curves in short Weierstrass form is more interesting. Following the strategy used for the unified addition formulae (accumulating multiplications before reduction) leads to 16 reductions and 19 multiplications. But it is actually possible to further reduce this complexity by resuming, from the beginning, the Montgomery ladder from a more theoretical standpoint. The Montgomery ladder is based on the fact that the y-coordinate carry only minor information. Indeed, it only allows to distinguish a point and its opposite (or equivalently a point and its image under the hyperelliptic involution). Thus, from a theoretical standpoint, dealing with the x-coordinate only results in working on the quotient of the curve by the hyperelliptic involution, which is called the Kummer variety. Of course, taking such a quotient implies that it is not possible to add two different points since P + Q and P -Q are not equal in the Kummer variety. However, doubling is still possible (it is easy to discern P + P and P -P = O) and if P -Q is known, it is possible to discern P + Q and P -Q. More precisely, it is proved in [START_REF] Flynn | An explicit theory of heights[END_REF] that there are biquadratic forms M x , M z and M xz , such that for any points P = (X P , Z P ) and Q = (X Q , Z Q ) on the Kummer variety, we have

2X P +Q X P -Q = M x , X P +Q Z P -Q + X P -Q Z P +Q = M xz , 2Z P +Q Z P -Q = M z .
These biquadratic forms are explicitely given by

M x = (X P X Q -aZ P Z Q ) 2 -4bZ P Z Q (Z P X Q + X P Z Q ), M xz = X P X Q (Z P X Q + X P Z Q ) + Z P Z Q (a(Z P X Q + X P Z Q ) + 2bZ P Z Q ), M z = (Z P X Q -X P Z Q ) 2 .
If P -Q is known, one can easily deduce formulae to compute X P +Q and Z P +Q from these biquadratic forms. In fact, only two of them are necessary. For instance, formulae obtained (in another way) by Brier and Joye in [START_REF] Brier | Weierstrass Elliptic Curves and Side-Channel Attacks. Public Key Cryptography[END_REF] and given in Proposition 2 can be easily deduced from M x and M z . Here, we use M xz and M z , in order to minimize the number of reductions.

X P +Q = 2(M xz -X P -Q Z P +Q ) Z P +Q = M z
Let us note that the theory of Kummer varieties also provides formulae for doubling but these always lead to the same formulae as in Proposition 2. Therefore, we have the following theorem.

Theorem 1.

-Let E be an elliptic curve defined over F p by [START_REF] Bajard | Residue systems efficiency for modular products summation: Application to Elliptic Curves Cryptography[END_REF]. Let also P = (X P , Y P , Z P ) and

Q = (X Q , Y Q , Z Q ) ∈ E(F p )
given in projective coordinates. Assume that P -Q = (x, y)

Publications mathématiques de Besançon -2013

is known in affine coordinates. Then

X P +Q = 2 (X P X Q (Z P X Q + X P Z Q ) + Z P Z Q (a(Z P X Q + X P Z Q ) + 2bZ P Z Q ) -xZ P +Q ) , Z P +Q = (X P Z Q + X Q Z P ) 2 -4X P X Q Z P Z Q , X 2P = X 2 P -aZ 2 P 2 -8bX P Z 3 P , Z 2P = 4X P Z P X 2 P + aZ 2 P + 4bZ 4 P .
Finally, we detail the steps for computing these expressions step operations red. mul. preliminary

A = Z P X Q + X P Z Q , B = 2X P X Q 2 3 computations C = 2Z P Z Q , D = aA + bC 2 3 Z P +Q A 2 -BC 1 2 X P +Q BA + CD + 2xZ P +Q 1 3 preliminary A = 2X P Z P , B = X 2 P , C = Z 2 P 3 3 computations D = -4bA, E = aA 2 2 X 2P BD + (C -E) 2 1 2 Z 2P 2B(C + E) -AD 1 2
In this case, the total cost for each bit of the exponent in RNS representation is 13 modular reductions and 20 multiplications whereas 19 base field multiplications must be performed in a standard representation. Hence the use of an arithmetic which complexity is concentrated on the reduction step (as the RNS) becomes very attractive with these new formulae. It is interesting to note that, contrary to the case of the standard representation, the extra cost for curves in short Weierstrass form compared to (more specific) curves in Montgomery form is not too large (33% in RNS representation compared to 90% in standard representation). Lastly, if a (or b) is a small number, the cost becomes 12 modular reductions whereas 17 multiplications must be performed in a standard representation. Let us now show that we can almost always assume that either a or b is small.

4.3.

Rescaling the constant to a small value. -This section is not specific to the RNS representation and can be applied in other contexts. It is motivated by the fact that there are 2 multiplications by a in the general formulae for the Montgomery ladder. Thus, the gain will be attractive if a can be rescaled to a small value. The standard way to perform such a rescaling is to find a small k such that a k is a fourth power u 4 in F p and to use the isomorphism (x, y) → x u 2 , y u 3 to send E on the curve E ′ defined by the equation y 2 = x 3 + a u 4 x + b u 6 . However, we can obtain a better result in the context of the Montgomery ladder. Indeed, y is not used in this representation so only u 2 will be used and it is actually sufficient that a k is a square in F p . The isomorphism is now defined over F p , so that it is easier to use a change of variables to describe the rescaling.

Theorem 2. -Let E be an elliptic curve defined over F p by (3) and k be a small integer such that a k is a square v 2 in F p . Let also P = (X P , Y P , Z P ) and

Q = (X Q , Y Q , Z Q ) ∈ E(F p )
given in projective coordinates. Assume that P -Q = (x, y) is known in affine coordinates.

Put Z ′ = vZ. If b ′ = b v 3 and x ′ = x v are precomputed, we have:

X P +Q = -4b ′ Z ′ P Z ′ Q (X P Z ′ Q + X Q Z ′ P ) + (X P X Q -kZ ′ P Z ′ Q ) 2 , Z ′ P +Q = x ′ (X P Z ′ Q -X Q Z ′ P ), X 2P = X 2 P -kZ ′2 P 2 -8b ′ X P Z ′3 P , Z ′ 2P = 4Z ′ P X 3 P + kX P Z ′2 P + b ′ Z ′3 P .
In this case, pseudo-addition can be performed in 9 multiplications and doubling in 8. Of course the same idea can be applied to formulae optimized for the RNS representation given in Section 4.2.

As the constraint on k has been relaxed compared to former results in the literature ( a k must be a square, not necessarily a fourth power), it is easier to rescale a to a small value in the context of Montgomery ladder than in the general context. Using the properties of the Legendre symbol, it is easy to prove that k is either 1 or the smallest non-square in F p and that the proportion of prime fields such that the n first prime numbers are squares is only 1 2 n . Anyway, if k is too large to neglect the multiplication by k, a can be rescaled to a small value thanks to isogenies [START_REF] Brier | Fast Point Multiplication on Elliptic Curves Trough Isogenies, Applied Algebra, Algorithms and Error-Correcting Codes[END_REF]. Finally, the method explained for rescaling a to a small value can also be applied to b if there is a small k such that 4b k is a cube in F p which leads to the same gain (2 multiplications). This method is particularly well suited if p ≡ 2 mod 3 since any element in F p is a third power. Then b can always be rescaled to 1 in this case. In conclusion, the probability that neither a nor b can be rescaled (by using Z ′ or isogenies) to a small value is very low, especially in the Montgomery ladder context.

Performance comparisons

In this section, we compare the complexities of our approach to those using Montgomery modular multiplication. First, we summarize the complexities for base field operations in Table 1. 1. Complexities for performing a multiplication and a modular reduction in RNS and with Montgomery approach for two n-word integers. A RNSdigit-product is equivalent to 1.1 word-product (see section 3.1). α represents the ratio between a RNSdigit-product and an addition (in general α > 10 for words with more than 32 bits).

addition (resp. a doubling and a pseudo-addition) for the different representations of the curve we chose to deal with in this paper.

It is then easy to deduce the global complexity in each case. For instance, one step of the Montgomery exponentiation algorithm using the formulae given in Section 2.2 (for the Montgomery approach) or section 4.2 (for our approach) when a is small requires 17n using RNS. We summarize, in Table 4, the word complexity for each representation of the curve we considered in this paper (i.e., those having SPA-resistance properties). We also give these complexities for usual ECC sizes for a 32-bit architecture. All these complexities are given for one basic step of the scalar multiplication. For Montgomery ladder, such a step always requires both an pseudo-addition and a doubling, so that the complexities are easy to compute. For unified formulae, we assume that this step requires 1.25 unified additions in average using, for example, a sliding window method with window size 3. This is not necessarily the best choice (for example in 512 bits) but this has no effect on our comparisons.

The complexities we obtain in RNS are always asymptotically better than in the classical representation. This is due to the fact that we optimized formulae on elliptic curves in order to minimize the number of reductions. As a consequence, our method becomes more interesting for high level of security. For example, the gain obtained is anecdotal for unified formulas in 192 bits but becomes interesting for higher level of security. The gain is also important for the Montgomery ladder because we discovered new formulae which are well adapted to the RNS representation of numbers. Moreover, all of the advantages of the RNS arithmetic become evident when a parallel architecture is used. Indeed, assuming that we have an architecture equivalent to n word-operators on a single word-bus, Table 5 shows the complexities of the different approaches in number of word operations. Note that we only give these complexities in the case of the Montgomery ladder with a small in order to simplify the paper. The complexities for the other curves representations can be easily deduced from Table 4. The estimation of the cost for the multiplication and for the Montgomery parallel product are based on systolic implementations [START_REF] Orlando | A scalable GF(p) elliptic curve processor architecture for programmable hardware[END_REF] or on parallel implementations [START_REF] Bunimov | Efficient Parallel Multiplication Algorithm for Large Integers Euro-Par 2003[END_REF][START_REF] Sanu | Parallel Montgomery Multipliers[END_REF], where the given architectures are respectively in O(n 2 /log(n) 2 ) and O(n 2 ) for the area and O(log(n)) for the time. As we did not find an explicit complexity for multiplication using a O(n) area architecture, we give two values for the complexity. The first one is minimal but certainly not realistic. The second one, which is not necessarily optimal, takes into account that :

-each product of a number by a digit will produce two numbers (high and low parts), -a carry-save adder will need an extra register for storing the carry and a final adder for absorbing these carries, -32-bit words look-up tables are not reasonable. Then, to get an idea with ECC key size, we compare three different implementations in table 6 for the number of operations required for one step of the Montgomery scalar multiplication on an elliptic curve in Weierstrass form with a small. In this configuration, the RNS becomes very attractive compared to the Montgomery arithmetic in terms of efficiency for a leak-resistant implementation of elliptic curve cryptosystems, even if we use our non-realistic lower bound for the comparison.

Practical implementation

In this paper, we prove that using RNS arithmetic is theoretically interesting for leak-resistant elliptic curve scalar multiplication. This result is based on a fine complexity study which has been made in a context as generic as possible (architecture for which additions and shifts are more efficient than products). In [START_REF] Guillermin | A high speed coprocessor for elliptic curve scalar multiplications over F p[END_REF], Guillermin produced a practical implementation to validate this work. He used the results provided in this paper but had to adapt them to his specific architecture. For example, he used an algorithm for base extension deduced from the CRT method [START_REF] Kawamura | Cox-rower architecture for fast parallel montgomery multiplication[END_REF]. It involves 2 times more products than the MRS method (chosen for our complexity study) and less additions. This is justified by his choice of architecture where products are especially cheap. The FPGA implementation obtained is the fastest one for elliptic curves defined over non-Mersenne prime field. It would be interesting in the future to have implementation on other platforms (like ASIC, smart cards, other FPGA, etc).

Conclusion

By combining Residue Number System and SPA-resistant arithmetic on elliptic curves, we obtained an efficient and secure implementation of elliptic curves cryptosystems, especially suitable for parallel architectures.

Since the expensive operation in RNS is the reduction, we proposed to rewrite formulae for elliptic curve SPA-resistant arithmetic in order to minimize the number of reductions even if the number of multiplications is increased. In the case of the Montgomery ladder on elliptic curves in Weierstrass form, we obtain new formulae which are better suited to RNS representation of numbers and we show why multiplications by one of the coefficients of the curve can be neglected in most cases.

We also give an in-depth analysis of the complexity of the RNS reduction. We thus realized that some improvements could be made to obtain a final complexity of α+10 α (n 2 -n) + 3n for a n-word number. It is clear that, without the results we obtained in these two directions, the combination of RNS arithmetic and elliptic curves will be possible but less convincing. Thus, we theoretically obtain an efficient leak-resistant arithmetic especially for high security levels and in the case of the Montgomery ladder on elliptic curves in Weierstrass form. This has been validated by a successful efficient FPGA implementation [START_REF] Guillermin | A high speed coprocessor for elliptic curve scalar multiplications over F p[END_REF] and generalized to pairing computations in [START_REF] Duquesne | RNS arithmetic in Fpk and application to fast pairing computation[END_REF][START_REF] Cheung | FPGA Implementation of Pairings Using Residue Number System and Lazy Reduction[END_REF]. This means that both on the theoretical and on the practical point of view, our approach is very attractive and promising. Of course, it is particularly interesting from a hardware standpoint since the RNS representation of numbers has many advantages (easy to implement and to parallelize, flexibility).

Algorithm 3 :

 3 MontgR_RNS(c, p) Data: Two RNS bases B = (m 1 , . . . , m n ), and B ′ = (m n+1 , . . . , m 2n ), such that M = n i=1 m i < M ′ = n i=1 m n+i and gcd(M, M ′ ) = 1 ; p a prime number represented in RNS in both bases such that 0 < 4p < M and gcd(p, M ) = 1; A positive integer c represented in RNS in both bases, with c < M p. Result: A positive integer r = cM -1 mod p represented in RNS in both bases, with r < 2p.

[

Table 2 (

 2 resp. 3) shows the number of operations required for a doubling or an Table

	Operation	RNS (in RNSdigit-products) Montgomery (in word-products)
	Multiplication	2n	n 2
	Reduction	α+10 α (n 2 -n) + 3n	n 2 + n

  2 + 14(n 2 + n) operations with Montgomery modular multiplication, and 18(2n) + 12( α+10 α (n 2 -n) + 3n) × 1.1

	Curve representation	RNS representation Standard representation
	Hessian form	9 red. and 12 mul.	12 mul. and 9 red.
	Jacobi form	10 red. and 12 mul.	12 mul. and 10 red.
	Unified Weierstrass form 14 red. and 18 mul.	18 mul. and 14 red.
	Publications mathématiques de Besançon -2013

Table 2 .

 2 Number of operations in RNS and standard representation for a unified addition

	Curve representation	RNS representation Standard representation
	Montgomery ladder	13 red. and 20 mul.	19 mul. and 16 red.
	Montgomery ladder (a small) 12 red. and 18 mul.	17 mul. and 14 red.

Table 3 .

 3 Number of operations in RNS and standard representation for each bit of the exponent of a Montgomery ladder

Table 4 .

 4 Cost in word-products (32-bits) of one scalar multiplication iteration (for α = 15)

	Curve rep.	size in bit		RNS	Montgomery	ratio in %
	Hessian form	32n 192	1.25 15n 2 + 36n × 1.1 1039	1.25(21n 2 + 9n) 1012	-2.6 %
		256		1716		1770	3.1 %
		512		6072		6900	13.6 %
	Jacobi form	32n 192	1.25 16.6n 2 + 37.3n × 1.1 1.25(22n 2 + 10n) 1133 1065	-6 %
		256		1877		1860	-1 %
		512		6688		7240	8.3 %
	Unif. Weierstrass	32n 192	1.25 23.3n 2 + 54.6n × 1.1 1.25(32n 2 + 14n) 1606 1545	-3.8 %
		256		2654		2700	1.7 %
		512		9416	10520	11.7 %
	Montg. ladder	32n 192	21.6n 2 + 57.3n × 1.1 1236	35n 2 + 16n 1356	9.7 %
		256		2029		2368	16.7 %
		512		7110		9216	29.6 %
	M. lad. (a small)	32n 192	20n 2 + 52n × 1.1 1135	31n 2 + 14n 1200	5.7 %
		256		1865		2096	12.3 %
		512		6547		8160	24.6 %
	Operation		RNS		Montgomery
	Multiplication Reduction One iteration of algorithm 2	2 × 1.1 a (n -1) + 3 × 1.1 2a+10 35.2n + 44	n . . . 2n 2n . . . 3n 44n . . . 75n

Table 5 .

 5 Number of cycles with parallel implementations on an n word-operators structure. (α = 15)

Table 6 .

 6 log 2 p] word RNS Montgomery Cost in word-products (32-bits) of one scalar multiplication iteration on a parallel architecture

	ratio inc

Résumé. -Dans cet article, nous donnons un survol d'une méthode qui combine le système de représentation des nombres basé sur les restes chinois (RNS) avec les formules de loi de groupe sur les courbes elliptiques qui sont résistantes aux attaques par fuites. Ces deux techniques sont particulièrement intéressantes pour l'implémentation de cryptosystèmes basés sur les courbes elliptiques dans des systèmes embarqués.Dans le système de représentation RNS, la multiplication de grands entiers est très efficace contrairement à la réduction modulaire. Nous réécrivons donc ici les formules de la loi de groupe pour les modèles de courbes elliptiques résistant aux fuites (loi d'addition unifiée, forme de Montgomery) dans le but de minimiser le nombre de réductions modulaires. Nous améliorons aussi la complexité de l'étape de réduction. Ces deux aspects permettent d'obtenir des implémentations sécurisées compétitives.Finalement, nous montrons que, contrairement aux autres approches, cette méthode peut profiter pleinement d'une architecture parallèle dédiée.

Publications mathématiques de Besançon -2013