Andrea Carletto

Andrés F Cardozo

Raffaella Suriano

Eric Manoury

Stefano Turri

Rinaldo Poli
email: poli@lcc-toulouse.fr

Core cross-linked amphiphilic star-block copolymers with (meth)acrylic acid shells prepared by atom transfer radical polymerization

Keywords: ATRP, amphiphilic polymers, core-shell polymers, polymerization, polymers, starblock copolymers

Core cross-linked amphiphilic star-block copolymers were prepared by hydrolysis of the outer shell of star-block copolymers prepared using copper mediated atom transfer radical polymerization (ATRP). In an arm-first approach, linear poly(tert-butyl methacrylate) macroinitiators (PtBMA-Cl) were extended with styrene to yield PtBMA-b-PS-Cl and then cross-linked with divinylbenzene (DVB) in order to yield (PtBMA-b-PS)arms-PDVBcore star-block copolymers. Then, PMAA-b-PS block and (PMAA-PS)arms-PDVBcore star-block copolymers were obtained by hydrolysis of the PtBMA blocks in both linear and cross-linked copolymers, as confirmed by 1 H NMR analyses. The amphiphilic character of these copolymers was confirmed by solubilisation in water. Several factors affecting the polymer aggregation and solubility such as the length, the composition of the arms and the catalyst used were studied. An acrylate analogue i.e. (PAA-b-PS)arms-PDVBcore was also prepared for comparison purposes. Atomic Force Microscopy (AFM) and Differential Scanning Calorimetry (DSC) were used to elucidate the morphology and the thermal behaviour of the star-block copolymers.

Introduction

Using controlled radical polymerization techniques, it is now possible to engineer highly sophisticated polymer architectures. [1] For instance, block copolymers are readily assembled by sequential addition of the desired monomers in two or more separate polymerization steps, where the polymer resulting from the n th step serves as macroinitiator for the assembly of the (n+1) th block.

Among various block copolymers, those having amphiphilic character are particularly interesting for applications that entail compatibilization with an aqueous environment, especially for biomedical applications such as vectors for drug delivery. [2][3] The self assembly of amphiphilic block copolymers into micelles allows transporting a hydrophobic cargo through blood and across membranes in the body. [4] A problem of self-assembled micelles, however, is their equilibrium with the free linear polymers, under the thermodynamic constraint of the critical micellar concentration. It is of potential interest, and not only for biomedical applications, to covalently link the linear chains at the core and create a star-like structure, with each arm being the amphiphilic block copolymer, in order to create a "unimolecular" micelle, for which equilibrium is no longer possible with the free arms.

Multiple arm stars have been assembled by either the core-first [5] or the arm-first [6] method, with the initiating (in the former approach) or terminating (in the latter one) reagent being either a well defined multifunctional molecule (when stars having a controlled number of arms is desired) or a divalent monomer, resulting in the formation of a nanogel. The latter method yields stars with a distribution for the number of arms. Among various controlling techniques, atom transfer radical polymerization (ATRP) has emerged as a preferred method, expecially when using Cu complexes as catalysts since these are inexpensive and easy to assemble by combination of a simple Cu I halide salt and a suitable additive from a wide library of available ligands. [7] In this contribution, we are exploring an arm-first approach for the assembly of star polymers where the inner core is a nanogel generated by the polymerization of a divalent monomer (divinyl benzene) and the arms are amphiphilic blocks, the hydrophilic block being placed on the outer shell. Our strategy consists in assembling I-PtBMA-b-PS-X and I-PtBA-b-PS-X linear arms from an I-X initiator by standard ATRP in an organic medium, followed by cross-linking with DVB and final hydrolysis of the outer shell to create the final amphiphilic object with PMAA or PAA hydrophilic shells. The strategy is summarized in Scheme 1. The hydrolyzed linear arms have also been generated for comparison.

Relative to the state of the art, which usually explores amphiphilic core-shell particles with relatively short arms, our investigation includes polymers with relatively long arm. In addition, we introduce the shell hydrophilicity through PMAA or PAA chains, instead of the more ubiquitous PEO chains which are characterized by a low LCST in water and therefore become compatible with the organic phase at high temperatures. One of our objectives for future applications is to confine the amphiphilic polymer in the water phase even at relatively high temperatures.

Scheme 1. General strategy for the construction of core cross-linked amphiphilic star-block copolymers.

Results

(a) Ts-PtBMA-Cl macroinitiator synthesis

Following a literature protocol, [8] a Cl-terminated PtBMA block was prepared using tosyl chloride as initiator, CuCl/PMDETA as catalyst (PMDETA = N,N,N',N',N"-pentamethyldiethylenetriamine), and toluene as solvent at 80°C (tBMA/TsCl/CuCl/PMDETA = 30:1:1:1).

The polymerization was quite fast (ca. 89% conversion in 2.5 h and well controlled, yielding an isolated polymer with Mn = 6730 g/mol and a dispersity (Đ) of 1.10 (equation 1). The greater degree of polymerization (46) relative to the initial monomer/initiator ratio, as revealed by SEC, indicates low initiator efficiency.

(1) Additional samples of the PtBMA macroinitiator, with number average degree of polymerizations of 30 and 53, were also prepared using CuBr as catalyst, again with TsCl as initiator. As known in the literature, [9] the relative affinity of the two halides for copper(I) and carbon is such that Br should remain on the metal and Cl on the polymer chain. The obtained Clterminated PtBMA macromolecules are summarized in Table 1. Note that, although the polymerization was well controlled in all cases, use of the CuBr catalyst yielded a narrower molecular weight distribution. After purification, all polymers were white indicating complete removal of the Cu salt. The 1 H NMR spectra allowed an independent verification of the degree of polymerization by chain-end analysis (integration of the methyl group resonance of the tosyl fragment relative to the tert-butyl protons). For instance, the Ts-(tBMA)46-Cl sample, shown in

(b) Synthesis of Ts-PtBMA-b-PS-Cl diblock macroinitiators

The above Cl-functionalized PtBMA products were used as macroinitiators for the polymerization of styrene under the conditions indicated in the literature, [10] namely using CuCl/PMDETA as catalyst and toluene as solvent, at a temperature of 100°C. In order to limit halogen loss at the chain ends by disproportional coupling, [11] these polymerizations were stopped at low to moderate conversion (no more than 70% monomer conversion as monitored by gas chromatography), and the products were isolated and characterized by SEC and 1 H NMR.

Different polymers with different sizes were prepared depending on the initial monomer to macroinitiator ratio. These products are also summarized in Table 1. All the diblock copolymers had a slightly greater dispersity then the precursor Ts-PtBMA-Cl macroinitiator (up to 1.45).

Nevertheless, the molecular weight distributions remained monomodal as shown by SEC (vide infra) and in total agreement with the results obtained by Loos et al. [10] The 1 H NMR spectra of the diblock copolymers allowed a verification of the relative lengths of the two blocks. The shape in the high field region for the diblock is essentially identical to that of the macroinitiator, because the methylene and methine protons from the PS backbone resonate at similar chemical shifts as the tert-buyl and methylene protons of the PtBMA block, whereas the signals of the polystyrene aromatic rings arise as two broad bands around δ 7 (see the example in Figure 1, bottom). Unfortunately, the signal of the methine proton geminal to chlorine atom could not be detected. Previous work has shown the identification of this resonance only for PS blocks of relatively low Mn. [12][13] (c) Synthesis of the PtBMA-b-PSarms-PDVBcore star-block copolymers Starting from the diblock macroinitiators described above, the star-block polymers listed in Table 2 were prepared by ATRP (arm-first approach) with divynylbenzene as cross-linking agent, still with use of CuCl/PMDETA in toluene, at 80°C. The SEC analyses revealed that in each case the reaction was not complete, with a certain amount of linear diblock copolymer remaining present. Selected results are shown in Figure 2, in which the different evolution as followed by SEC is presented. The arm-to-star conversion, was evaluated by deconvolution of the SEC signal (see Table 2). In principle, the RI data should provide a more reliable estimation of the relative weight fractions since the MALLS response becomes smaller for lower molecular weight solutes. It is well known that an incomplete crosslinking from arm macroinitiators and difunctional monomers is obtained under typical ATRP conditions. [1,[14][15][16] The dispersity of the resulting cross-linked polymers were in some cases rather poor, as shown in Table 2, but the dispersity of the cross-linked fraction as estimated after deconvolution of the SEC trace was always similar to that of the precursor linear polymer.

Improved results in terms of cross-linking were obtained when the amount of catalyst was doubled relative to that of macroinitiator and when the reaction time was prolonged to 36 h, as was the case for CCS-4 and CCS-5. The shift of the molecular weigth distributions revealed the inclusion of an average number of arms per star-block copolymer as indicated in Table 2, as estimated from the ration between MnSEC(star-block) and MnSEC(arms). This number is between 7 and 16 for all polymers except for CCS-3 and CCS-6, for which the star-block product contained a smaller number of arms on average. The same crosslinker (DVB) / macromonomer ratio was used in all cases. The lower degree of crosslinking for these polymer may be related to the longer arm length and consequent diffusional problems, which privilege the reaction of the active radical with the smaller crosslinker molecules. However, note that CCS-2, also derived from relatively long arms, leads to a greater degree of crosslinking. The proton NMR analysis of the star-block products was not very informative, because once again the Cl-bonded methine resonance was not detectable and the vinyl groups remaining pendant in the core of the polymer were also invisible. The signals generated by the PtBMA segments remained well defined, as it can be seen in Figure 3. In spite of the similar resonances of both species (star-block and linear arms) on the 1 H-NMR spectrum, their different size and molecular weight result in different diffusional behavior in solution and this can be verified by Diffusion Ordered SpectroscopY (DOSY). DOSY can discriminate and analyze separately the different species in solution since it provides a direct path to the diffusion coefficient and therefore to the hydrodynamic radius through the Debye-Einstein theory. [17] The general case of a spherical particle yields equation 2, where DAB is the diffusion coefficient of the A specie through a viscous medium B, T the absolute temperature, kB the Boltzmann constant, η is the medium viscosity and rH the hydrodynamic radius. The bigger the particle, the slower its movement and hence its diffusion coefficient will be smaller.

(2)

In our case, a single sample of CCS-3 was tested by adding tetramethylsilane (TMS) as an inert internal reference, to eliminate the need to know the medium viscosity (equation 3). [18] The resulting 2-D spectrum is shown in Figure 4. The 1 H NMR data were processed using NMR notebook software with a DOSY module from NMRTEC® that implements the Maximum Entropy / Laplace Inversion Transform algorithm. [19] This complement is well adapted for the treatment of polydisperse samples. [20] As expected, the analysis yielded two major species other than TMS, i.e. the star-block cross-linked polymer and the residual diblock macroinitiator. The DOSY method should provide a better analysis of the relative fractions and yield of the cross-linking reaction than the SEC since the response of the latter depends on the quality of the separation. This is true if the species have a relatively narrow molecular weight distribution and no perturbations to the Brownian movement are present such as convection or settling. Their relative proportions as integrated from the signal intensity in the DOSY differed from those resulting from the deconvolution of the SEC data (see Table 3). Note that the analyzed sample yields a crosslinking yield from the DOSY data that agrees better with the MALLS signal deconvolution than with that of the RI signal. The size of the star-block particle as estimated by the hydrodynamic radius is also in good agreement with the gyration radius determined from the analysis of three-angle light scattering data at the maximum of the SEC peak (Table 2).

(d) Acrylate system

Following the same strategy described previously in (a)-(c), an acrylate analogue, (PtBAb-PS)arms-PDVBcore, was also synthesized. Only one star-block copolymer was prepared with the purpose of comparing the solubility behavior as a function of the outer shell structure. First, a

PtBA-Br macroinitiator was prepared using methyl-2-bromopropionate (MBP) as initiator and CuBr/PMDETA as catalyst, which is more suitable for acrylate monomers using conditions found in the literature. [21][22][23] The same kind of diblock copolymers have also been previously obtained under slightly different conditions. [24] The SEC and according to the SEC and 1 H NMR analyses. Similar block copolymers have also been previously prepared by the reverse order monomer addition (first styrene, then tBA), yielding diblock macroinitiators with the halogen attached to the PtBA end and with a similar level of control. [25] The final (PtBA-b-PS)arms-PDVBcore star-block polymer obtained by cross-linking the CH3CH(COOMe)-PtBMA40-b-PS31-Br macroinitiator had MnSEC = 213100 and Đ = 1.42, from which an average of 24 arms can be calculated.

(e) Hydrolysis. Generation of amphiphilic star-block copolymers.

The amphiphilic character of final polymers is conferred by the final hydrolysis step.

Single PAA and PMAA polymers prepared by ATRP, as well as block copolymers containing these segments, have already been prepared by tert-butyl ester segment hydrolysis. [21,24,26] Both linear and star-like copolymers were hydrolyzed under moderate acid conditions in order to achieve an effective water solubilisation (see Scheme 2).

Both PAA and PMAA homopolymers are intrinsically water soluble, but their copolymers with styrene are not, although they can be solubilised in micellar form depending on the relative size of the two blocks. [24,[26][27][28][29] A good solvent for both blocks is DMSO and this has indeed been used, in the deuterated version, for the 1 H NMR study of the hydrolyzed copolymers. The linear copolymers and the star-block copolymers obtained were not directly soluble in water in the acidic form, most certainly because of the unfavorable contribution of hydrophobic polystyrenic chains. However, they could be dissolved at basic pH with K2CO3 upon heating under vigorous stirring in order to obtain homogeneous polyelectrolyte solutions (see Scheme

3). 22 The potassium salt form of the linear block copolymers will be named as PMAAKn-b-PSm or PAAKn-b-PSm , with n and m corresponding respectively to the number of methacrylic/acrylic units and styrene units.

Scheme 3. General procedure of units' neutralization, for a methacrylate system.

The results of the solubilization tests are shown in Table 4. Both PMAA46-Cl and PAA40-Br homopolymers were water-soluble. Clear and colorless solutions were obtained when using the linear and star-block copolymers containing the acrylic block. For polymers containing both methacrylate and styrene segments, a milky-white dispersion was observed, as already reported in previous contributions. [30] Since the size of these linear diblock and start-block copolymers should not exceed a few tens of nanometers (e.g. 28 nm diameters for CCS-3, see above), the light scattering observed for these polymer solutions must be due to aggregation, probably caused by an incomplete ionization and the consequent establishment of inter-macromolecule Hbonds. Indeed, it is known that the pKa of PMAA is ca. 6.5 for the first acid dissociation but increases rapidly for the subsequent dissociations up to > 9. [31] The first pKa of PAA, on the other hand, is < 4 and increases for subsequent dissociations up to ca. 7. The establishment of intermicellar interactions, affecting the light scattering of aqueous solutions of PS-b-PMAA micelles, has previously been investigated in detail. [32] Table 4. Water solubility features of polymers and corresponding white solutions. display the characteristic periodic pattern typical of a block copolymer, [33] well seen with both topographic and demodulation imaging. However, the size of the "bright" objects is in our case around 500 x 800 nm, much larger than for segregated phases seen by AFM with classical styrene-rubber block copolymers. [34] Also the optical contrast in demodulation images is softer, but this can be due to the fact that in our case the two polymeric blocks, although phase- Figure 8 shows the topographical images for the CCS-2 and CCS-3 samples cast from acetone solutions, performed in tapping mode on a scanning area of 1.35x1.35 µm. From the corresponding topographical data it is possible to recognize ellipsoidal objects with widths in the range of 250-500 nm and heights of 10-15 nm. The lateral size of these structures is significantly larger than hydrodynamic radii of nanogels as measured by NMR data (see Table 3). Such a discrepancy can be due to a partial coalescence of nanogels during the coating and drying process, so that only aggregates are seen by AFM analysis.

A B

Figure 8. Three-dimensional topographical for the CCS-2 (A) and CCS-3 (B) samples dispersed in acetone and spin-coated (scanning area 10 x 10 µm 2 ).

Figure 9 highlights the effect of the solvent on the apparent particle size: in comparison to the morphology obtained from acetone casting (Figure 8B), CCS-3 sample cast from dichloromethane or toluene solutions shows much smaller structures, about 100-150 nm and 50-100 nm wide, respectively. These dimensions are still large but in better agreement with the NMR data. Such an effect may be related to the different features of the solvents used. Table 5 reports the solubility parameter components [START_REF] Barton | CRC Handbook of Solubility Parameters and other Cohesion Parameters[END_REF] of the three solvents in comparison to polystyrene, which is the predominant species of the block copolymers described in the present work. From the examination of Table 5 data it seems that both dichloromethane and toluene show higher dispersive d and smaller polar p components, with values closer to those of polystyrene.

Smaller differences between polymer-solvent solubility parameter components involve a better thermodynamic quality of the solutions, and a more efficient solubilization of the nanogels in our case. On the other hand acetone is expected to be a poorer solvent, and formation of larger size colloidal aggregates is likely. In the light of the above the smaller objects seen after dichloromethane or toluene casting seems a more realistic evaluation of the size of the single particle nanogels.

Table 5. Three-component solubility parameters (dispersion, δd, polar, δp, and hydrogen bonding components, for polystyrene and solvents. [START_REF] Barton | CRC Handbook of Solubility Parameters and other Cohesion Parameters[END_REF] δd (MPa

Conclusions

Using the precision of the ATRP technique, core-crosslinked core-shell nanosized polymers with flexible PS-b-PtBMA or PS-b-PtBA arms were prepared in three steps. The outer poly(tert-butyl (meth)acrylate) shell was then hydrolyzed to PMAA or PAA to afford amphilic core-shell structures that could be dissolved in water in the deprotonated form. The star-block polymer containing an outer PAA shell is more easily soluble in water, without aggregation, to yield clear solutions. The synthesis suffers from incomplete crosslinking, leaving a significant fraction of arms, which is a frequently encountered limitation for these convergent methods of synthesis. [1,6] However, methods allowing improved crosslinking efficiency exist. [14][15][START_REF] Oh | [END_REF] Future synthetic efforts in our group will be devoted to the construction of this type of polymer architecture with a PAA outer shell, with a functionalized hydrophobic core, for specialized applications. As mentioned in the introduction, the PAA shell should insure confinement of the polymer in the water phase for a variety of water/organic biphasic systems, for instance water/toluene, even at relatively high temperatures. The investigation of the phase distribution as a function of temperature and relative size of the core and shell parts is one of the objectives of our future studies.

Experimental Part

Chemicals. All monomers (styrene, 99%; tert-butyl methacrylate, 98%; tert-butyl acrylate, 98%; divinylbenzene, tech. 80%) were purchased from Aldrich, distilled under reduced pressure from CaH2 and stored under argon at -20°C before use. Toluene (99.7%, Aldrich) was dryed and distilled under argon. CuBr (99.999%, Aldrich), CuCl (99.999%, Aldrich), CuBr2 (99.0%, Fluka), p-tosyl chloride (99.0%, Fluka), methyl 2-bromopropionate (99.0%, Fluka) PMDETA (99%, Aldrich), methanol (99.8%, Aldrich) and THF (99.9%, Aldrich) were used without further purification.

Instrumentation. The 1 H NMR spectra were recorded on Bruker ARX250 or Avance 300 spectrometers in CDCl3 for all the hydrophobic precursor polymers and in DMSO-d6 for the hydrolyzed amphiphilic polymers. The NMR DOSY analysis of CCS-3 was carried out at 298 K on a Bruker 500 MHz spectrometer in CDCl3 solutions. The experiments were performed using a stimulated echo bipolar gradiant for diffusion sequence. For each experiment, fine-shaped pulsed-field gradients with a duration of 1.4 ms followed by a recovery delay of 150 μs were used. The diffusion space was recorded by 32 linearly spaced gradients with a diffusion time of During the reaction, several samples (1 mL of solution) were withdrawn and dissolved in 3 mL of toluene, followed by filtration through a small alumina column in order to remove the catalyst.

One part of the colorless samples was analyzed by gas chromatography to determine the monomer conversion and the remaining part was used for the SEC analysis. After 4 hours, the Schlenk flask was rapidly cooled down and the mixture was diluted with toluene and filtered through an alumina column. The resulting solution was concentrated by evaporation under reduced pressure and the polymer was precipitated by addition of MeOH, filtered off and dried overnight under vacuum to yield a white powder. Yield 16 g (76%). MnSEC = 6730 g/mol; Đ = Results and Discussion section), two Gaussian distributions were fitted in order to calculate the fractions of both linear and star polymer. The arm to star yield is reported in Table 2. The procedure used for the synthesis of CCS-4 and CCS-5 differed: a double amount of CuBr, CuBr2

and PMDETA equivalents relative to the macroinitiator was used and the heating was prolonged to 36h. The data for all isolated samples are reported in Table 2. Polymer Hydrolyses. The hydrolyses of the tert-butyl ester groups on the methacrylate and acrylate copolymers were carried out as follows. To a round-bottom flask were added 6 mL of dichloromethane (CH2Cl2) and 300 mg of polymer (PtBMA-X, PtBA-X, diblock copolymer or star polymer). After cooling to 0°C, 0.9 mL (11.7 mmol) of CF3COOH (trifluoroacetic acid)

Polymerizations

were slowly added from a dropping funnel to the vigorously stirred solution. The reaction mixture was kept at 0°C for 3 h, then overnight at room temperature, a precipitate was observed and residual solvent was removed under reduced pressure. The final product was obtained by washing this residue with dichloromethane followed by drying under vacuum.

Ionization. Preparation of the polymer solutions. For each experiment, 30 mg of linear diblock or star-block copolymer was added to 100 mL of a 0.4 M aqueous solutions of K2CO3.

The pH of all solutions was above 7 (complete neutralization of the methacrylic and acrylic acid units). The samples were heated for 45 min at 70°C under vigorous stirring to complete the solubilization. At this stage, the acrylic acid units are in the potassium salt form. [28] Atomic force microscopic studies. AFM images were obtained in tapping mode with a NSCRIPTON DPN Writer (Nanoink, USA) at ambient temperature and humidity. AppNano silicon probes (Applied NanoStructures, Inc. Santa Clara, CA, USA) with a nominal spring constant of 40 N/m and a nominal resonance frequency of 300 kHz were used. These cantilevers are 125 μm long and a tip radius of 5-10 nm. The lateral scan frequency was 0.2 Hz. The images were digitalized by using Nano-R AFM software supplied by Pacific Nanotechnology (USA).

For AFM analysis polymers were dispersed in acetone or in tetrahydrofuran (THF) (2 mg of polymer in 2 mL of solvent), then polymer films were cast by spin coating on silicon substrates, with initial acceleration of 70 rpm/s 2 and speed of 1500 rpm. [37] Silicon substrates were previously cleaned in a distilled water ultrasound bath. The root-mean-square roughness (Rrms), which is the standard deviation of measured data on the analyzed surface, was calculated according to the following equation:

  2 1 N n n rms zz R N    
where z is the average mean of measurements heights and N is the number of points included in the analyzed surface.

Table-of-Content Graphics

Synopsis

Amphiphilic core-shell polymers containing a PDVB crosslinked core PS-b-PMAA or PS-b-PAA linear arms have been obtained by hydrolysis of the tert-butyl esters of related architectures, assembled in three steps by ATRP.

Figure 1 (

 1 Figure 1 (top), gave a number average degree of polymerization of 48.5 from the NMR integration.

Figure 1 . 1 H

 11 Figure 1. 1 H NMR spectra of Ts-PtBMA46-Cl (top) and Ts-PtBMA46-b-PS186-Cl (bottom) in CDCl3. The asterisks (*) indicate residual solvent signals.

a

  Conditions (except for CCS-4 and CCS-5): [Cu] = [PMDETA] = [MI], [DVB]:[toluene] = 1:10, reaction time = 24 h. b Estimated after deconvolution of the SEC RI trace (values from the SEC MALLS trace in parentheses). c [Cu] = [PMDETA] = 2*[MI], reaction time = 36 h. A ratio of [DVB]/ [MI]= 20 was used for all the reactions.

Figure 2 .

 2 Figure 2. Size exclusion chromatograms (left: MALLS detector; right: RI detector) for selected polymers. In each frame are reported the SEC of the synthesized star-block (PtBMA-b-PS)arms-PDVBcore copolymer (plain line) in comparison with the corresponding linear diblock (dashed line) and Ts-PtBMA-Cl macroinitiator (dotted line).

Figure 3 . 1 H

 31 Figure 3. 1 H NMR spectra of CCS-3 in CDCl3. Residual solvent signals are represented by an asterisk (*).

Figure 4 .

 4 Figure 4. NMR DOSY spectrum for CCS-3 at 298 K in CDCl3.

( 3 ) 3 .a

 33 Table Average diffusion coefficients of the species contained in sample CCS-3 in CDCl3 at 298 K.Species DA (m 2 .s -1 ) rH (nm) Relative amount a (%From the intensity integral. b Calculated assuming a tetrahedral geometry and bond lengths for (C-H)=109 pm and (Si-C)= 185 pm. c Residual Ts-PtBMA46-b-PS186-Cl.

  1 H NMR analyses yielded an average formulation of CH3CH(COOMe)-PtBMA40-Br (MnSEC = 5310; Đ = 1.15). This macroinitiator was subsequently chain extended with styrene and cross-linked under the same conditions described above for the Ts-PtBMA-Cl macroinitiator. The intermediate diblock macroinitiator corresponds to CH3CH(COOMe)-PtBMA40-b-PS31-Br (MnSEC = 8620; Đ = 1.30)

Scheme 2 .

 2 Scheme 2. Hydrolysis sequence on tert-butyl groups and synthesis of the poly(acid) external segments.

Figure 5 . 1 H

 51 Figure 5. 1 H NMR spectra of Ts-PtBMA46-b-PS186-Cl in CDCl3 (top) and Ts-PMAA46-b-PS186-Cl in (CD3)2SO (bottom). The starred resonance is the DMSO solvent peak.

  Atomic Force Microscopy (AFM) characterizationAFM analyses were performed in tapping mode on some of the synthesized linear diblock and star-block copolymers. Figure6shows an example of AFM topographical and phase demodulation images for the star polymer CCS-2 (C and D, respectively), and for its linear A B C D diblock copolymer precursor Ts-PtBMA46-b-PS135-Cl (A and B, respectively). Images A and B

Figure 6 .

 6 Figure 6. Topographical -C) and phase demodulation (B -D) images, respectively for Ts-PtBMA46-b-PS135-Cl and CCS-2 samples dispersed in acetone and spin-coated (scanning area 5 x 5 µm 2 ).

Figure 7 .

 7 Figure 7. DSC traces of TsPtBMA46-b-PS135-Cl sample obtained in the first heating run (black line) and in the third heating run (gray line). The arrows indicate the inflection points of curves, corresponding to the glass transition temperatures.

Figure 9 .

 9 Figure 9. AFM topographical images for CCS-3 samples dispersed in (A) dichloromethane and in (B) toluene and spin-coated on silicon (scanning area 1.35 x 1.35 µm 2 ).

Polymerizations. 1 .

 1 220 ms. Diffusion coefficients were obtained by treatment of the NMR data with NMR notebook software which included the Maximum Entropy/Inverse Laplace Transformation algorithm developed by NMRTEC®. The size exclusion chromatographic analyses (SEC) were carried out in filtered THF as eluent on PL gel (5m particles, 50 x 7.5 mm) guard column and a PL-gel 5 m mixed-D (300 x 7.5 mm) column (Polymer Laboratories), equipped with a multiangle lightscattering detector (minidawn Tristar, Wyatt Technology Corporation) coupled with a refractive index detector (RI2000, Sopares) at 35 °C. Molecular weight values for the copolymers and nanogels were determined using the multiangle laser light scattering detector. For the block copolymers, the molecular weight analyses were carried out using the total mass recovery protocol, which also yields the dn/dc value, whereas literature values of dn/dc were used for the homopolymers (0.075 for PtBMA; 0.059 for PtBA). Gas chromatography analyses were performed on a Hewlett Packard 5980 Series II gas chromatograph equipped with a Beta DEXTM 225 capillary column and a flame ionization detector using helium as carrier gas. Differential scanning calorimetry (DSC) was performed on a Mettler-Toledo TA 823 e instrument under nitrogen flux in cooling/heating runs at first from 20 °C to 200 °C, then from 200°C to 20 °C, finally from 20 °C to 200 °C at a rate of 20 °C min -1 . The glass transition temperature (Tg) was measured at the inflection point of the first and the third heating run. Methacrylate systems.(a) Synthesis of the Ts-PtBMA46-Cl macroinitiator. By operating under an atmosphere of argon, in a dry round bottom Schlenk flask equipped with a stirrer bar were introduced CuCl (471.3 mg, 4.6 mmol) PMDETA (960 L, 4.6 mmol), dry toluene (10 mL) and dodecane (as GC internal standard). The mixture was stirred for 20 min at room temperature before the addition of tBMA (23 mL, 138 mmol). Finally, a separately prepared solution of the initiator (TsCl, 907.9 mg, 4.6 mmol in 10 mL of toluene) was transferred into the reaction mixture. After three freezepump-thaw cycles, the flask was placed in a preheated and thermally regulated oil bath at 80°C.

1. 10 .

 10 (b) Synthesis of the other Ts-PtBMAn-Cl macroinitiators. The procedure was identical to that described in the previous section, except for the use of CuBr and different monomer quantities, as follows: Ts-PtBMA30-Cl: CuBr (197.6 mg, 1.35 mmol), CuBr2 (33.5 mg, 0.15 mmol), PMDETA (323 L, 1.5 mmol), TsCl (292 mg, 1.5 mmol), tBMA (25 mL, 150 mmol), toluene (25 mL). MnSEC = 4380 g/mol; Đ = 1.05. Ts-PtBMA53-Cl: CuBr (197.6 mg, 1.35 mmol), CuBr2 (33.5 mg, 0.15 mmol), PMDETA (323 L, 1.5 mmol), TsCl (292 mg, 1.5 mmol), tBMA (45 mL, 270 mmol), toluene (45 mL). MnSEC = 7730 g/mol; Đ = 1.03.(c) Synthesis of Ts-PtBMA-b-PS-Cl. The procedure was similar to that discussed in the previous section. Only the synthesis of Ts-tBMA46-b-S135-Cl will be described in detail. To the solution of copper catalyst (CuCl, 71.5 mg, 0.7 mmol) and PMDETA (150 L, 0.7 mmol) in toluene (6 mL), the monomer (styrene, 5 mL, 42 mmol) and a solution of Ts-PtBMA46-Cl (4.7 g, 0.7 mmol in 6 mL of dry toluene) were added. After three freeze-pump-thaw cycles, the Schlenk flask was immersed in a preheated thermostated oil bath at 100°C. After 7 hours, the flask was rapidly cooled down to room temperature and the reaction mixture was diluted in 30 mL of toluene and passed several times through an alumina column to remove the residual catalyst. It was then concentrated and the polymer was precipitated by adding cold methanol. The recovered white solid powder was dried overnight under vacuum at room temperature. Yield: 7.4 g (60 %). Mn = 20780 g/mol (dn/dc = 0.141); Đ = 1.16. Data for the other isolated samples: Ts-PtBMA30-b-PS19-Cl. Mn = 6360 g/mol (dn/dc = 0.106); Đ = 1.22. Ts-PtBMA46-b-PS186-Cl. Mn = 26140 g/mol (dn/dc = 0.113); Đ = 1.10. Ts-PtBMA53-b-PS13-Cl. Mn = 9120 g/mol (dn/dc = 0.100); Đ = 1.45. Ts-PtBMA53-b-PS16-Cl. Mn = 9340 g/mol (dn/dc = 0.104); Đ = 1.42. Ts-PtBMA53-b-PS97-Cl. Mn = 17850 g/mol (dn/dc = 0.131); Đ = 1.25.(d) Synthesis of (Ts-PtBMA-b-PS)arms-PDVBcore star-block copolymers. The procedure was similar to those used for the preparation of the first block and diblock macroinitiators. Only the synthesis of the star-block copolymer generated from Ts-PtBMA30-b-PS19-Cl (CCS-1) will be described in detail. In a dry round bottom Schlenk flask equipped with a stirrer bar were introduced CuBr (89.9 mg, 0.61 mmol), CuBr2 (15.3 mg, 0.07 mmol), PMDETA (150 L, 0.68 mmol) and dry toluene (10 mL). After 20 minutes of stirring at room temperature, a separately prepared solution of Ts-PtBMA30-b-PS19-Cl (4.3 g, 0.68 mmol) and DVB (2 mL, 13.6 mmoles) in 10 mL of dry toluene was added. After three freeze-pump-thaw cycles, the Schlenk flask was immersed in a preheated thermostated oil bath at 80°C for 36 h. The flask was then removed from the oil bath and rapidly cooled down to room temperature and the reaction mixture was successively diluted and filtered on alumina columns. The star polymer was recovered as described in the previous sections. Mn = 106200 g/mol (dn/dc = 0.182); Đ = 1.65. After deconvolution of the SEC dectector traces (both MALLS and RI traces were analyzed, see

. 2 .

 2 Acrylate systems. (a) Synthesis of the CH3CH(COOMe)-PtBA40-Br macroinitiator. In a dry round bottom Schlenk flask equipped with a stirrer bar were introduced CuBr (146.4 mg, 1 mmol), CuBr2 (22.4 mg, 0.1 mmol), PMDETA (215 L, 1 mmol), dry toluene (15 mL) and dodecane. After 20 minutes of stirring at room temperature, tBA (10.5 mL, 70 mmol) and the initiator methyl-2bromopropionate (250 L, 1 mmol) were injected using argon purged syringes. After three freeze-pump-thaw cycles, the Schlenk flask was placed in a preheated and thermally regulated oil bath at 80°C. The polymer was recovered as described in the previous sections. Yield: 7 g (60 %). MnSEC = 5310 g/mol; Đ = 1.15. (b) Synthesis of the CH3CH(COOMe)-PtBA40-b-PS31-Br macroinitiator. This procedure is similar to those described in the methacrylate section. From 5.3 g (1 mmol) of CH3CH(COOMe)-PtBA40-Br and 4.7 mL (40 mmol) of styrene in 18 mL of toluene, CH3CH(COOMe)-PtBA40-b-PS31-Br Mn = 8620; Đ = 1.30) was synthesized in the presence of CuBr (292.8 mg, 2 mmol) and PMDETA (215 L, 1 mmol). (b) Synthesis of the (PtBA-b-PS)arms-PDVBcore star-block copolymer. This was prepared from 4 g (0.46 mmol) of CH3CH(COOMe)-PtBA40-b-PS31-Br as macroinitiator using 2 mL (13.6 mmol) of DVB in 30 mL of toluene. It was recovered after 72 h of reaction in the presence of CuBr (135 mg, 0.92 mmol), and PMDETA (198 L , 0.92 mmol). MnSEC = 213100 g/mol (dn/dc = 0.099); Đ = 1.42.

Table 1 .

 1 ATRP of tBMA polymers and chain extension with styrene.

Table 2 .

 2 Core cross-linked nanogels synthesized in this work. a

	Diblock macroinitiator	MnSEC (Đ)	Star-Block Copolymer	MnSEC (Đ)	(Đ) b star	Star yield b /%	Rg/nm dn/dcstar Narms SEC
	Ts-PtBMA30-b-PS19-Cl	6360 (1.22)	CCS-1	106200 (1.65)	1.10	21 (64)	8.6	0.182	16.7
	Ts-PtBMA46-b-PS135-Cl 20780 (1.16)	CCS-2	280400 (1.46)	1.11	22 (50)	20.6	0.142	13.5
	Ts-PtBMA46-b-PS186-Cl 26140 (1.10)	CCS-3	95020 (2.57)	1.13	23 (69)	15.7	0.106	3.6
	Ts-PtBMA53-b-PS13-Cl	9120 (1.45)	CCS-4 c	68940 (2.16)	1.21	40 (85)	9.1	0.122	7.6
	Ts-PtBMA53-b-PS16-Cl	9340 (1.42)	CCS-5 c	102900 (1.60)	1.29	66 (71)	15.0	0.125	11.0
	Ts-PtBMA53-b-PS97-Cl	17850 (1.25)	CCS-6	37980 (1.59)	1.06	12 (65)	11.5	0.129	2.1

Acknowledgement

We are grateful to the CNRS (Centre National de la Recherche Scientifique), the ANR (Agence Nationale de la Recherche, Program BIPHASNANOCAT), Yannick Coppel and Christian Bijani for the NMR-DOSY data treatment and the IUF (Institut Universitaire de France) for financial support. A. Carletto thanks the Politecnico Milano for an Erasmus fellowship and A. F. Cardozo thanks the PRES Toulouse for a Ph.D. fellowship.


Yoann Marquer
email: yoann.marquer@inria.fr

Tania Richmond
email: tania.richmond@inria.fr

Pascal Véron
email: pascal.veron@univ-tln.fr

A Hole in the Ladder: Interleaved Variables in Iterative Conditional Branching (Extended Version)

Keywords: Security and Privacy Protection, Public key cryptosystems, Computer arithmetic, Fault injection

The iterative conditional branchings appear in various sensitive algorithms, like the modular exponentiation in the RSA cryptosystem or the scalar multiplication in ellipticcurve cryptography. In this paper, we abstract away the desirable security properties achieved by the Montgomery ladder, and formalize systems of equations necessary to obtain what we call the semi-interleaved and fully-interleaved ladder properties. This fruitful approach allows us to design novel fault-injection attacks, able to obtain some/all bits of the secret against different ladders, including the common Montgomery ladder. We also demonstrate the generality of our approach by applying the ladder equations to the modular exponentiation and the scalar multiplication, both in the semi-and fully-interleaved cases, thus proposing novel and more secure algorithms.

I. INTRODUCTION

We present common algorithms used to compute the modular exponentiation, based on an iterative conditional branching, where a conditional branching depending on the secret updates the value of a variable x on every iteration of one/several loop(s). Amongst these algorithms the Montgomery ladder, that uses a fresh variable y, satisfies desirable properties against side-channel or fault-injection attacks.

A. Contribution

In this paper, we formalize these properties with equations corresponding to two families of cases: the semi-interleaved ladders where the value of x or y may (depending on the secret) depend only on its previous value, and the fullyinterleaved ladders where the value of x and y both depend on both previous values.

We propose 1) an attacker model using fault-injection able to obtain some bits of the secret in the semi-interleaved cases (including the Montgomery ladder) but none in the fullyinterleaved cases, and 2) a stronger attacker model able to obtain all bits of the secret in the semi-interleaved cases, and even in the fully-interleaved cases if the fault can be injected in the key register.

This work was supported by the EU Horizon 2020 project TeamPlay (https://www.teamplay-h2020.eu), grant number 779882.

We also use our formalization to design novel algorithms for the modular exponentiation, including a semi-interleaved ladder with a mask updated at every iteration, and a fullyinterleaved ladder. We demonstrate the generality of the approach by also applying the ladder equations to the scalar multiplication used in elliptic-curve cryptography (ECC), obtaining a semi-interleaved ladder suitable for practical applications, and a fully-interleaved ladder.

The ladder equations, the first two attacks and the algorithms for the modular exponentiation have been published at ARITH 2020 [START_REF] Marquer | A Hole in the Ladder: Interleaved Variables in Iterative Conditional Branching[END_REF]. This paper is an extended version, including novelties like:

• the third attack (for the second attacker model) against all (including fully-interleaved) ladders (Subsection IV-B), • in the case of the modular exponentiation a proof that the probability to obtain randomly a suitable ladder constant for our fully-interleaved ladder candidate is almost 1 when used in concrete applications like RSA or DSA cryptosystems (Subsections V-D and V-E), • and original semi-and fully-interleaved ladder candidates for the scalar multiplication over elliptic curves (Section VI).

B. Organization of the Paper

As introduction, we present in Section II some related works on the modular exponentiation and the Montgomery ladder. In Section III we formalize the iterative conditional branching to deduce the equations satisfied by the semi-interleaved and fully-interleaved ladders, and thus the requirements for ladderizable algorithms. In Section IV we introduce two attacker models using fault injection techniques, and compare the vulnerability of the non-, semi-and fully-interleaved ladders. Finally, we detail how to produce examples of the semiand fully-interleaved ladders in Section V for the modular exponentiation and in Section VI for the scalar multiplication.

II. RELATED WORKS

In this section, we introduce known algorithms for the modular exponentiation, their relevance regarding security, and the desirable properties of the usual Montgomery ladder.

input public a, n; secret k 1: x ← 1 2: for i = d to 0 do 3:

x ← x2 mod n 4:

if k[i] = 1 then 5:

x ← ax mod n 6: end if 7: end for 8: return x output x = a k mod n TABLE I SQUARE AND MULTIPLY input public a, n; secret k 1: x ← 1 2: for i = d to 0 do 3:

x ← x 2 mod n 4:

if k[i] = 1 then 5:

x ← ax mod n 6: else 7:

y ← ax mod n 8:

end if 9: end for 10: return x output x = a k mod n

TABLE II SQUARE AND MULTIPLY ALWAYS

A. Modular Exponentiation

Let k be a secret key, and k = 0≤i≤d k[i] 2 i be its binary expansion of size d + 1, i.e. k[i] is the bit i of k. The square-and-multiply algorithm described in Table I computes the (left-to-right) modular exponentiation a k mod n, by using a 0≤i≤d k[i]2 i = 0≤i≤d (a 2 i ) k [i] . This exponentiation is commonly used in cryptosystems like RSA [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF].

For every iteration, the multiplication ax is computed only if k[i] = 1, which can be detected by observing execution time1 [START_REF] Kocher | Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems[END_REF] or power profiles 2 by means of e.g. SPA (Simple Power Analysis3 ) [START_REF] Kocher | Differential Power Analysis[END_REF], and thus leads to information leakage from both time and power side-channel attacks.

To prevent SPA, regularity of the modular exponentiation algorithms is required, which means that both branches of the sensitive conditional branching perform the same operations, independently from the value of the exponent. Thus, an else branch is added with a dummy instruction [START_REF] Coron | Resistance Against Differential Power Analysis For Elliptic Curve Cryptosystems[END_REF] in the squareand-multiply-always algorithm described in Table II.

But countermeasures developed against a given attack may benefit another one [START_REF] Sung-Ming | A Countermeasure against One Physical Cryptanalysis May Benefit Another Attack[END_REF]. Because the multiplication in the else branch of this algorithm is a dummy operation, a fault injected [START_REF] Ziade | A survey on fault injection techniques[END_REF] in the register containing ax will eventually propagate through successive iterations and alter the final result only if k[i] = 1, thus leaking some information. Therefore, an attacker (see the attacker models in Section IV) able to inject a fault in a given register at a given iteration can obtain the digits of the secret key by comparing the final output with or without fault (technique known as safe-error attack).

B. Montgomery Ladder

This is not the case in the algorithm proposed by Montgomery [START_REF] Montgomery | Speeding the Pollard and Elliptic Curve Methods of Factorization[END_REF] and described in Table III, where a fault injected in a register will eventually propagate to the other one, and thus will alter the final result in any case, preventing the attacker to obtain information. But, as described in Section IV, some information on the last digits may still leak, weakening the protection obtained from the ladder.

input public a, n; secret k 1: x ← 1 2: y ← a mod n 3: for i = d to 0 do 4: if k[i] = 1 then 5:
x ← xy mod n 6:

y ← y 2 mod n 7: else 8:

y ← xy mod n 9:

x ← x 2 mod n 10:

end if 11: end for 12:

return x output x = a k mod n TABLE III MONTGOMERY LADDER 1: x ← init 2: for i = 1 to n do 3:
. . .

4:

if secret then 5:

x ← θ (x) 6: else 7:

x ← ε (x) The Montgomery ladder is algorithmically equivalent [START_REF] Marquer | Algorithmic Completeness of Imperative Programming Languages[END_REF] to the square-and-multiply(-always) algorithm(s), in the sense that x has the same value for every iteration. Actually, some variants [START_REF] Boscher | CRT RSA Algorithm Protected Against Fault Attacks[END_REF] of the square-and-multiply-always algorithm4 may be as resistant as the Montgomery ladder [START_REF] Joye | The Montgomery Powering Ladder[END_REF], both by checking invariants [START_REF] Kiss | Algorithmic Countermeasures Against Fault Attacks and Power Analysis for RSA-CRT[END_REF] violated if a fault is injected. In the case of the Montgomery ladder, the invariant y = ax is satisfied for every iteration. These invariants are important for the self-secure exponentiation countermeasures [START_REF] Giraud | An RSA Implementation Resistant to Fault Attacks and to Simple Power Analysis[END_REF].

Note that the else branch in Table III is identical to the then branch, except that x and y are swapped, which provides also (partial 5 ) protection against timing and power leakage. Moreover, the variable dependency makes these variables interleaved, so this exponentiation is algorithmically (but partially, as we will demonstrate) protected against safe-error attacks. Finally, as opposed to square-and-multiply-always in Table II, the code in the else branch in Table III is not dead, so will not be removed by compiler optimizations.

III. LADDER EQUATIONS

In this section, we formalize the iterative conditional branching occuring in algorithms like the Montgomery ladder, and deduce the requirements to optimize them with semi-or fully-interleaved ladders.

A. Iterative Conditional Branching

In this paper, we focus on algorithms as in Table IV called iterative conditional branching. It appears in algorithms like square-and-multiply for the modular exponentiation, its counterpart double-and-add for elliptic curve point multiplication [START_REF] Miller | Use of Elliptic Curves in Cryptography[END_REF], [START_REF] Koblitz | Elliptic Curve Cryptosystems[END_REF], or the secure bit permutation in the McEliece cryptosystem [START_REF] Strenzke | Side Channels in the McEliece PKC[END_REF] attacked in [START_REF] Petrvalsky | Differential power analysis attack on the secure bit permutation in the McEliece cryptosystem[END_REF]. It also appears naturally (Table V) when trying to turn a loop on the secret into a conditional branching depending on the secret, that can itself be balanced to remove or reduce the dependency on the secret.

But our approach does not depend on the number/depth of the considered loops, hence the dots in Table IV. We assume only that the conditional branching uses only one variable x, the multivariate case being future work (see Section VII). . . . 5:

if secret then 6:

x ← f (x, y) 7:

y ← ε (y) 8: else 9:

y ← f (y, x) 10:

x ← ε (x) 11:

end if 12:

. . . 13: end for . . . 5:

if secret then 6:

x ← f (x, y) 7:

y ← g (x, y) 8: else 9:

y ← f (y, x) 10:

x ← g (y, x) 11:

end if 12:

. . . 13: end for

B. Semi-Interleaved Ladders

To prevent information leakage from side-channel analysis or fault injections, we use another variable y in the algorithm described in Table VI. As in the Montgomery ladder (see Table III), we need to find two functions and f such that for every iteration:

• y = (x), and • x has the same value for every iteration as in Table IV. y = (x) is satisfied at the initialization. By induction, let's assume y = (x) at the beginning of an iteration. In the then branch 6 we have x ← f (x, y) then y ← ε (y), thus in order to have y = (x) satisfied at the end of an iteration the following equation must hold:

∀x, ε ( (x)) = (f (x, (x)))
and to have x updated to θ (x) during the iteration the following equation must hold:

∀x, f (x, (x)) = θ (x)
In the else branch we have y ← f (y, x) then x ← ε (x), thus in order to have y = (x) satisfied at the end of an iteration the following equation must hold:

∀x, f ( (x), x) = (ε (x))
and x is already updated to ε (x) during the iteration.

Definition 2 (Semi-Ladderizable). Let A be an algorithm with a univariate iterative conditional branching with two unary functions denoted θ and ε. A is semi-ladderizable if there exists a unary function and a binary function f such that, for every considered value x:

     ε ( (x)) = (θ (x)) f (x, (x)) = θ (x) f ( (x), x) = (ε (x)) (1) (2) (3)
For the square-and-multiply algorithm we have θ (x) = ax 2 and ε (x) = x 2 , and we know that it can be semi-ladderized by using the Montgomery ladder with (x) = ax and f (x, y) = xy, but we demonstrate in Section V that there are other solutions. Note that to respect the form of the semiinterleaved ladder, we should have written y ← yx and not y ← xy in the else branch 7 of the Montgomery ladder.

C. Fully-Interleaved Ladders

Unfortunately, the semi-interleaved ladder is vulnerable to fault injection techniques, because in every branch at least one variable depends only on its previous value and not the previous value of both variables (see Section IV). Moreover, an attacker able to determine whether the output of one operation is used as the input to another one can [START_REF] Hanley | Exploiting Collisions in Addition Chain-Based Exponentiation Algorithms Using a Single Trace[END_REF] apply collision attacks 8 to deduce whether two following bits are the same. To solve these issues, we propose in Table VII a fully-interleaved ladder using three functions , f and g.

As for the semi-interleaved ladders, y = (x) is satisfied at the initialization. We assume again by induction that y = (x) at the beginning of an iteration. In the then branch we have x ← f (x, y) then y ← g (x, y), thus in order to have y = (x) satisfied at the end of an iteration the following equation must hold:

∀x, g (f (x, (x)), (x)) = (f (x, (x)))

and to have x updated to θ (x) during the iteration the following equation must hold:

∀x, f (x, (x)) = θ (x)
In the else branch we have y ← f (y, x) then x ← g (y, x), thus, in order to have y = (x) satisfied at the end of an iteration, the following equation must hold:

∀x, f ( (x), x) = (g (f ( (x), x), x))
and to have x updated to ε (x) during the iteration the following equation must hold:

∀x, g (f ( (x), x), x) = ε (x)
Definition 3 (Fully-Ladderizable). Let A be an algorithm with a univariate iterative conditional branching with two unary functions denoted θ and ε. A is fully-ladderizable if there exists a unary function and two binary functions f and g such that, for every considered input value x:

         g (θ (x), (x)) = (θ (x)) f (x, (x)) = θ (x) f ( (x), x) = (ε (x)) g (f ( (x), x), x) = ε (x) (4) (5) (6) (7)
Note that Equation ( 2) is Equation ( 5) and Equation ( 3) is Equation [START_REF] Brier | Correlation power analysis with a leakage model[END_REF]. Without surprise, if g is chosen such that g (x, y) = ε (y) then Equation ( 1) is a special case of Equation (4), and Equation ( 7) is satisfied. Thus, semi-interleaved ladders are subcases of fully-interleaved ladders.

D. Ladderizable Algorithms

Theorem 1. Let A be an algorithm with an iterative conditional branching with two unary functions denoted θ and ε. If A is semi-ladderizable with and f , or fully-ladderizable with , f and g, then for every iteration of the ladder variant:

• y = (x) • x is updated as in A: x ← θ (x) if secret ε (x) otherwise
Thus, for every algorithm with an iterative conditional branching, if there exists and f satisfying the equations in Definition 2 then the conditional branching can be rewritten as a semi-interleaved ladder. Even better, if there exists , f and g satisfying the equations in Definition 3 then it can be rewritten as a fully-interleaved ladder.

Because in a semi-or fully-interleaved ladder the operations performed are the same for both the then and the else branches, this transformation is an algorithmic countermeasure against side-channel attacks [START_REF] Kocher | Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems[END_REF], [START_REF] Kocher | Differential Power Analysis[END_REF]. We detail in Section IV the impact of the semi-and fully-interleaved ladderization against fault injection techniques. Then, to demonstrate the concept, we construct examples of semi-and fully-interleaved ladders in Sections V and VI.

IV. FAULT INJECTION

In this section, we introduce two attacker models using fault injection techniques, and compare the vulnerability of the non-, semi-and fully-interleaved ladders.

According to [START_REF] Ziade | A survey on fault injection techniques[END_REF] a fault is a physical defect, imperfection or flaw that occurs within some hardware or software component, while an error is a deviation from accuracy or correctness, and is the manifestation of a fault. Hardware/physical faults can be permanent, transient or intermittent, while software faults are the consequence of incorrect design, at specification or at coding time. Fault injection is defined [START_REF] Arlat | Validation de la sûreté de fonctionnement par injection de fautes : méthode, mise en oeuvre, application[END_REF] as the validation technique of the dependability of fault tolerant systems, which consists in performing controlled experiments where the observation of the system's behavior in presence of faults is induced explicitly by the writing introduction (called injection) of faults in the system.

A. First Attacker Model

For the iterative conditional branching (Table IV) and the semi-and fully-interleaved ladders (Tables VI andVII), we assume as in the Montgomery ladder (Table III) that "secret" is the condition k

[i] = 1, where k[i] is the i-th bit of the secret key k.
Definition 4 (First Attacker Model). We assume that:

• The attacker wants to obtain the secret key stored in the chip and copied in the register k. • The attacker can run the program any number of times:

inputting x init and y init , the initial values in the register x and y, obtaining x final and/or y final , the final value(s) returned by the program.

• A run consists of iterations i over 9 1, . . . , n, where:

k[i] is the i-th bit of k, x i (resp. y i ) denotes the value in the register x (resp. y) between the iterations i -1 and i.

• The attacker can x i (resp. y i ) inject a random fault 10(the affected variable is set to a random value) in the register of x (resp. y) between the iterations i -1 and i.

The attacker might be unlucky and obtain the same value as before, but this is unlikely and can be fixed by several tries, so we will assume for simplicity that the new value is different.

The attacker can run a program for the square-andmultiply(-always) (Tables I andII) algorithm(s) for a given input x init , obtain a value x final , then run the program again with the same input while injecting a fault y i in the register y = ax between the iterations i -1 and i, and obtain a value

x fault . If x fault = x final then k[i] = 0, otherwise k[i] = 1.
This can be done for every iteration (in any order), thus the attacker can obtain that way all the bits of the secret key.

In this algorithm, because the current value in x determines the next value in x, a faulted value x i for an iteration i always propagates to the next iteration x i+1 , which we denote by x i ⇒ x i+1 . To obtain the bit k[i], the attacker has exploited the fact that a fault in y = ax propagates to x, denoted by

y i ⇒ x i+1 , only if k[i] = 1.
As opposed to this nonladderized variant, in Tables VI and VII the values of x and y are interleaved, and the fault propagation patterns are the following:

1) For the semi-interleaved ladder:

x i ⇒ x i+1 and ( y i+1 only if k[i] = 0) y i ⇒ y i+1 and ( x i+1 only if k[i] = 1)
which means that a fault always propagates to the same register, but propagates to the other depending on the current bit of the secret key.

2) For the fully-interleaved ladder:

x i or y i ⇒ x i+1 and y i+1 which means that any fault in one register propagates in every case to both. The fully-interleaved ladder has a lower fault tolerance, i.e. it is easier to disrupt the computation. This is not convenient for properties like functionality, availability or redundancy, but prevents an attacker from obtaining the secret key, thus increases security. Thus, we reduced the information leakage from fault injection by reducing also the fault tolerance. The semi-interleaved ladder is more robust, but this comes at the price of a fault propagation pattern depending on the secret key, which can be exploited.

Indeed, the attacker can y n as in Figure 1 and compare the x output. We assume, as in the exponentiation examples, that changing a read intermediate value would lead to a different output, because if this was not the case then the attacker should have used better x init and y init inputs. So, if If the obtained bit was 0 as in the left part of Figure 2, the attacker can y n-1 . In that case if

x fault = x final then k[n] = 0, otherwise k[n] = 1.
x fault = x final then k[n -1] = 0, otherwise k[n -1] = 1.
This process can be repeated until a 1 is found. If the obtained bit was 1 as in the right part of Figure 2, the attacker can x n-1 . In that case if

y fault = y final then k[n -1] = 1, otherwise k[n -1] = 0. This process can be repeated until a 0 is found. k x y . . . k[n -1] 0 x n x final y n-1 y n y final 1? k x y . . . k[n -1] 1 x n-1 x n x final y n y final 0? Fig. 2

. Attack the Penultimate Bit

One may think that these processes can be alternated in order to recover all the bits of the secret key, but if there is a bit alternation, i.e. (k[i] , k[i + 1]) = (0, 1) or (1, 0), then the bits before i cannot be obtained, as illustrated in Figures 3 and4. So, the attacker can obtain the final bits 10 . . . 0 if x final can be read, and the final bits 01 . . . 1 if y final can be read.

The vulnerability to fault injection is summarized in Table X. Against the first attacker model described in Definition 4, fully-interleaved ladders are more secure than semiinterleaved ladders, which are more secure than without interleaving at all. But we show in the next subsection that a stronger attacker is able to obtain all the bits of the key from both the semi-and fully-interleaved ladders.

B. Second Model

Definition 5 (Second Attacker Model). We assume that:

• The second attacker has the same goal and means that the attacker in Definition 4. • The second attacker can also k >i = 0 (resp. k >i = 1) stuck-at [START_REF] Ziade | A survey on fault injection techniques[END_REF] 0 (resp. 1) all the bits of the register k between iterations i and i + 1.

This stronger attacker is able to break the semi-interleaved ladders by using the attack protocol described in Table VIII in order to recover all the bits of the secret key 11 . EXE(x init , y init , k >i = 1) at Line 4 means that the studied program is executed with inputs x init , y init and a stuck-at k >i = 1, and EXE(x init , y init , k >i = 1, x i ) at Line 5 is the same but with a fault x i . In particular, if both x final and y final can be read, then the Montgomery Ladder (Table III) can be broken (by iterating over 0 to d). This attack does not work against fully-interleaved ladders, but a fully-interleaved ladder is more difficult to obtain (when possible), as discussed in Subsections V-C and VI-C.

Actually, being able to write deterministically in the key register is enough to obtain with a third attack all the bits of the key, even against fully-interleaved ladders. Indeed, let's assume that the second attacker knows the first i bits k

[1] . . . k[i]
, where i = 0 for the initialization. By k >i = 0 (resp. k >i = 1) and k >i+1 = 0 (resp. k >i+1 = 1) the second attacker can compare x fault0 and x final0 (resp. x fault1 and x final1 ) obtained respectively for k [START_REF] Marquer | A Hole in the Ladder: Interleaved Variables in Iterative Conditional Branching[END_REF]

. . . k[i] 0 0 . . . 0 and k[1] . . . k[i] k[i + 1]
0 . . . 0 (resp. with 1 instead of 0 at the end), and the same for y. Thus, the second attacker can (almost) determine whether k[i + 1] = 1 (resp. 0):

• if x fault0 = x final0 or y fault0 = y final0 then k[i + 1] = 1, • if x fault1 = x final1 or y fault1 = y final1 then k[i + 1] = 0. If x fault0 = x final0 , x fault1 = x final1
, y fault0 = y final0 and y fault1 = y final1 then another inputs x init , y init should be chosen in the protocol described in Table IX.

That way all the bits of the key k can be obtained, except the ones such that for every possible x init , x fault0 = x final0 and x fault1 = x final1 . But this case is unlikely, it does not prevent 1: FIx ← 0 2: for i = n to 1 do 3:

if FIx = 1 then 4:

(x final , y final ) ← EXE(x init , y init , k >i = 1) 5:

(x fault , y fault ) ← EXE(x init , y init , k >i = 1, x i ) 6:

if y fault = y final then 7: the attacker from discovering the other bits, and these bits make no difference in the result, thus probably the attacker does not care. Therefore, the second attacker can obtain all the (relevant) bits of the key, even against semi-and fullyinterleaved ladders. The vulnerabilities against these attacks are summarized in Table X.

k[i] ←

V. EXTENDING THE MONTGOMERY LADDER

The purpose of this section is to provide concrete examples of the ladder equations for cryptography, and to generalize the idea behind the Montgomery ladder to improve its protection against side-channel and fault injection attacks.

We demonstrate by using the modular exponentiation. In the following for any n we consider Z/nZ, i.e. integers modulo n, and denote (Z/nZ) the integers invertible modulo n. We assume that θ (x), ε (x), f (x, y), g (x, y) and (x) are quadratic polynomials with the following coefficients: More general quadratic polynomials, e.g. 2 = 0 or more complex θ (x) and ε (x), can be investigated but the general systems of equations tend to be complicated, and in this section we want to focus on the exponentiation algorithms. To ensure that θ (x) = ax 2 and (x) = 1 x + 0 depends on x, we will assume that a = 0 and 1 = 0. Moreover, in the following we focus on solutions without constraint on a to preserve the generality of the original algorithm.

θ (x) = ax 2 ε (x) = x 2 f (x, y) = f 20 x 2 + f 11 xy + f 02 y 2 + f 10 x + f 01 y + f 00 g (x, y) = g 20 x 2 + g 11 xy + g 02 y 2 + g 10 x + g 01 y + g 00 (x) = 1 x + 0 Obtained Bits
Finally, note that Z/nZ may not be an integral domain i.e. there exists x, y ∈ Z/nZ\{0} such that xy = 0 mod n, which is the case for RSA (see Subsection V-D) with p and q such that n = pq. Because n cannot be easily factorized into p and q, and because we are looking for general solutions for any n, if x = 0 and xy = 0 we will look for solutions y = 0, thus loosing some generality but simplifying the analysis.

A. Both Semi-and Fully-Interleaved Ladders

Equation (2) (resp. Equation ( 5)) f (x, (x)) = θ (x) for the semi-(resp. fully-) interleaved cases is equivalent to: 6)) f ( (x), x) = (ε (x)) for the semi-(resp. fully-) interleaved cases is equivalent to:

     f 20 + f 11 1 + f 02 2 1 = a f 11 0 + 2f 02 1 0 + f 10 + f 01 1 = 0 f 02 2 0 + f 01 0 + f 00 = 0 Equation (3) (resp. Equation (
     f 20 2 1 + f 11 1 + f 02 = 1 2f 20 1 0 + f 11 0 + f 10 1 + f 01 = 0 f 20 2 0 + f 10 0 + f 00 = 0 B. Semi-Interleaved Ladder
The remaining Equation (1) ε ( (x)) = (θ (x)) for the semi-interleaved cases is equivalent to:

     2 1 = 1 a 2 1 0 = 0 2 0 = 0 So, because 1 = 0, we assume 1 = a and 0 = 0. Therefore Equation (2) is equivalent to:      f 20 + f 11 a + f 02 a 2 = a f 10 + f 01 a = 0 f 00 = 0
and Equation ( 3) is equivalent to:

     f 20 a 2 + f 11 a + f 02 = a f 10 a + f 01 = 0 f 00 = 0 input public a, n; secret k 1: x ← 1 2: y ← a mod n 3: c ← a 2 + 1 mod n 4: for i = d to 0 do 5: m ← random([0, n -1]) 6: if k[i] = 1 then 7:
z ← y 2 mod n 8:

x ← ma(x 2 + z) + (1 -mc)xy mod n 9:

y ← z 10: else 11:

z ← x 2 mod n 12:

y ← ma(y 2 + z) + (1 -mc)yx mod n 13:

x ← z 14:

end if 15: end for 16:

return x output x = a k mod n TABLE XI SEMI-INTERLEAVED LADDER FOR THE EXPONENTIATION
From f 10 + f 01 a = f 10 a + f 01 we deduce f 10 (a -1) = f 01 (a -1), which is always true without constraint on a if f 10 = f 01 . Moreover, from f 10 + f 01 a = 0 we obtain f 10 = -f 01 a, thus from f 10 a + f 01 = 0 we obtain f 01 (a 2 -1) = 0, which is always true without constraint on a if f 01 = 0. Therefore we assume f 10 = 0 = f 01 .

From

f 20 + f 11 a + f 02 a 2 = f 20 a 2 + f 11 a + f 02 we deduce f 20 (a 2 -1) = f 02 (a 2 -1), which is always true without constraint on a if f 20 = f 02 . The remaining constraint is f 20 (a 2 + 1) + f 11 a = a, which is equivalent to f 20 = a a 2 +1 (1 -f 11 )
. By assuming that the coefficients are integers there exists m such that 1f 11 = m(a 2 + 1). Thus, we have f 20 = ma and f 11 = 1m(a 2 + 1).

Theorem 2. The square-and-multiply algorithm in Table II for the modular exponentiation with θ (x) = ax 2 and ε (x) = x 2 is semi-ladderizable with:

(x) = ax f (x, y) = ma(x 2 + y 2 ) + (1 -m(a 2 + 1))xy
producing the algorithm in Table XI.

Note that if m = 0 then f (x, y) = xy so this solution is the common Montgomery ladder. Note also that m can be chosen randomly for every iteration, providing a mask for the intermediate values and thus reducing the opportunity of information leakage.

C. Fully-Interleaved Ladder (General Case)

Equation ( 4) g (θ (x), (x)) = (θ (x)) for the fullyinterleaved cases is equivalent to:

               g 20 a 2 = 0 g 11 1 a = 0 g 11 0 a + g 02 2 1 + g 10 a = 1 a 2g 02 1 0 + g 01 1 = 0 g 02 2 0 + g 01 0 + g 00 = 0
So, because a = 0 and 1 = 0, we assume g 20 = 0 from the first equation, g 11 = 0 from the second, and the remaining constraints are:

     g 02 2 1 + g 10 a = 1 a 2g 02 1 0 + g 01 1 = 0 g 02 2 0 + g 01 0 + g 00 = 0
According to Equation ( 6) f ( (x), x) = (ε (x)) = 1 x 2 + 0 , so by using g 20 = g 11 = 0 we have: g (f ( (x), x), x) = (g 02 + g 10 1 )x 2 + (g 01 )x + (g 10 0 + g 00 ) Thus, Equation ( 7) g (f ( (x), x), x) = ε (x) for the fullyinterleaved cases is equivalent to:

     g 02 + g 10 1 = 1 g 01 = 0 g 10 0 + g 00 = 0
Because g 20 = g 11 = g 01 = 0 and we require g (x, y) = g 02 y 2 + g 10 x + g 00 to depend on both x and y, we have to assume g 02 = 0 and g 10 = 0. By using g 01 = 0 the remaining constraints from Equation ( 4) are:

     g 02 2 1 + g 10 a = 1 a g 02 1 0 = 0 g 02 2 0 + g 00 = 0
Because g 02 = 0 and 1 = 0, the second equation implies that 0 = 0. Thus, the remaining constraints from Equation (4) and Equation ( 7) are:

     g 02 2 1 + g 10 a = 1 a g 02 + g 10 1 = 1 g 20 = g 11 = g 01 = g 00 = 0
By using the second equation g 02 = 1g 10 1 , the first one is equivalent to:

g 10 (a -3 1 ) = 1 (a -1 )
Because g 10 = 0 and 1 = 0, note that a = 3 1 ⇔ a = 1 , in which case 3 1 = 1 , thus a = 1 = ±1. To remove the constraint on a, we assume that a = 3 1 , and thus g 10 and g 02 depends only on a and 1 :

g 10 = 1 a -1 a -3 1 g 02 = 1 -g 10 1 = a 1 -2 1 a -3 1 g (x, y) = g 02 y 2 + g 10 x = 1 a -3 1 a(1 -2 1 )y 2 + 1 (a -1 )x
Note that because 1 = 0 and g 10 = 0 we have to assume that, as opposed to the semi-interleaved cases, 1 = a.

Moreover, because 0 = 0, the constraints from the common Equations ( 5) and ( 6) can be simplified:

               f 20 + f 11 1 + f 02 2 1 = a f 20 2 1 + f 11 1 + f 02 = 1 f 10 + f 01 1 = 0 f 10 1 + f 01 = 0 f 00 = 0 (L 1 ) (L 2 ) (L 3 ) (L 4 )
In order to have a non-trivial ladder (x) = 1 x, we will assume that 1 = ±1. With (L 4 ) -(L 3 ) we obtain (f 10f 01 )( 1 -1) = 0 thus f 10 = f 01 , and with (L 3 ) we have

f 10 ( 1 + 1) = 0, so f 10 = f 01 = 0. With (L 1 ) -(L 2 ) we obtain (f 02 -f 20 )( 2 1 -1) = a -1 , so f 02 = f 20 + a-1 2
1 -1 . Therefore, remain the following constraints:

                     f 20 ( 2 1 + 1) + f 11 1 = a -2 1 a -1 2 1 -1 = 1 - a -1 2 1 -1 f 02 = f 20 + a -1 2 1 -1 f 10 = f 01 = f 00 = 0
The first line being obtained from (L 1 ) and the second from

(L 2 ). Note that a -2 1 a-1 2 1 -1 = 1 -a-1 2
1 -1 is satisfied and thus is not a constraint. Moreover, because 1 = 0, by using the second line, f 11 can be written as:

f 11 = 1 1 1 - a -1 2 1 -1 -f 20 ( 2 1 + 1) = 1 1 3 1 -a 2 1 -1 -f 20 ( 2 1 + 1)
Thus, we have:

f (x, y) = f 20 x 2 + f 11 xy + f 02 y 2 = f 20 x 2 + 1 1 3 1 -a 2 1 -1 -f 20 ( 2 1 + 1) xy + f 20 + a -1 2 1 -1 y 2 = f 20 x 2 - 2 1 + 1 1 xy + y 2 + 1 2 1 -1 3 1 -a 1 xy + (a -1 )y 2
Finally, f 20 has no constraint. It could have been used as a mask for f as in Theorem 2, but unfortunately not for g. So, for sake of simplicity, we assume f 20 = 0 and obtain the following functions:

Theorem 3. The square-and-multiply algorithm in Table II for the modular exponentiation with θ (x) = ax 2 and ε (x) = x 2 is fully-ladderizable with:

(x) = 1 x f (x, y) = 1 2 1 -1 3 1 -a 1 xy -( 1 -a)y 2 g (x, y) = 1 3 1 -a a( 2 1 -1)y 2 + 1 ( 1 -a)x input public a, n; secret k 1: do 2: ← random([2, n -2] \ {a}) 3: v 0 ← -a mod n 4: (d 1 , u 1 ) ← EEA( , n) 5: v 2 ← 2 -1 mod n 6: (d 2 , u 2 ) ← EEA(v 2 , n) 7: v 3 ← 3 -a mod n 8: (d 3 , u 3 ) ← EEA(v 3 , n) 9: while v 0 mod n = 0 ∨ d 1 = 1 ∨ d 2 = 1 ∨ d 3 = 1 10: c 0 ← u 1 u 2 v 3 mod n 11: c 1 ← -v 0 u 2 mod n 12: c 2 ← av 2 u 3 mod n 13: c 3 ← v 0 u 3 mod n 14: x ← 1 15: y ← 16: for i = d to 0 do 17: if k[i] = 1 then 18:
x ← c 0 xy + c 1 y 2 mod n 19:

y ← c 2 y 2 + c 3 x mod n 20: else 21:

y ← c 0 yx + c 1 x 2 mod n 22:

x ← c 2 x 2 + c 3 y mod n 23:

end if 24: end for 25:

return x output x = a k mod n TABLE XII FULLY-INTERLEAVED LADDER FOR THE MODULAR EXPONENTIATION (GENERAL CASE)
where

1 1 = a mod n, 2 1 ∈ (Z/nZ) , 3 2 1 -1 ∈ (Z/nZ) and 4 3 1 -a ∈ (Z/nZ) , producing the algorithm in Table XII.
The first constraint on the ladder constant (denoted in the following) can be satisfied by checking whether (a) mod n = 0. The other constraints can be satisfied by using the Extended Euclidean Algorithm (d, u) ← EEA(v, n), where uv = d mod n, such that if d = 1 then v is invertible modulo n and v -1 = u mod n. Because = a mod n, 0 ∈ (Z/nZ) , and if = ±1 then 2 1 -1 ∈ (Z/nZ) , we can assume that ∈ Z/nZ can be chosen in L a,n = [2, n-2]\{a}, then check whether satisfies the constraints of Theorem 3 (Lines 1-9). Actually, we prove in the RSA case (Subsection V-D) and the DSA case (Subsection V-E) that a ladder constant verifying these constraints is almost always obtained after one iteration.

Note that after a suitable is chosen, the coefficients of f and g are constant during the iterations, thus can be precomputed (Lines 10-13). These computations to find suitable constants may cause a significant overhead (Lines 1-15) but that does not depend on the secret, thus trading execution time and energy consumption for more security.

We provide in Table XIII a comparison of complexities for the Montgomery, semi-and fully-interleaved ladders. The complexities are given in terms of cost per key bit, where M stands for multiplication, S for squaring and A for addition/subtraction, all modulo n. These costs are given after memoization, for instance the squarings in Line 18 and Line 19 in Table XII are the same, so could have been memorized by using z ← y 2 and then z used instead of the squares. Because the costs are given per key bit, we did not include the cost of the pre-computations, which is far from negligible for the fully-interleaved ladder in Table XII. D. Fully-Interleaved Ladder (RSA Case)

In the context of RSA [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF], we assume that n = pq, where p, q are distinct primes. The modular exponentiation aims at computing a k mod n, so we assume that the input a is already given modulo n, i.e. 0 ≤ a ≤ n-1. Because 0 k and (±1) k are fairly trivial to compute, to simplify the following reasoning we assume that

2 ≤ a ≤ n -2, so card(L a,n ) = n -4, where L a,n = [2, n -2] \ {a}.
To satisfy constraints 1 and 2 of Theorem 3, i.e. = a and ∈ (Z/nZ) , has to be chosen in L a,n such that gcd( , n) = 1. Thus, in the following we will assume that is chosen randomly in L a,n and determine the probability that satisfies the ladder constraints. Within this range, the only integers such that gcd( , n) > 1 are jp for j ∈ [1, q -1] or jq for j ∈ [1, p -1], so the probability to pick randomly a ladder constant not verifying 2 is:

P r(not 2 ) ≤ (p -1) + (q -1) n -4 ≈ 1 p + 1 q
In RSA context, it means that a random ∈ L a,n is invertible modulo n with probability almost equal to 1. Indeed, according to the National Institute of Standards and Technology (NIST) recommendations [START_REF] Barker | Recommendation for Pair-Wise Key Establishment Using Integer Factorization Cryptography[END_REF], if nBits = log 2 n + 1 denotes the number of bits of n = pq, then p and q should verify:

2 nBits-1 2 < p < 2 nBits 2 2 nBits-1 2 < q < 2 nBits 2
Note that if one can compute such that gcd( , n) > 1 then gcd( , n) = p or q, and is able to factorize The same problem occurs in RSA cryptosystem: if Alice can generate a message m such that gcd(m, n) > 1, where n is Bob's public key, then Alice can factorize n and find Bob's secret key. Such an event could occur with a probability nearly equal to 0.

To satisfy constraint 3 of Theorem 3, i.e. 2 -1 ∈ (Z/nZ) , note that according to the chinese remainder theorem the integers such that 2 -1 is not invertible modulo n verify 2 = 1 mod p and 2 = 1 mod q. There are at most four such integers: 1, n -1, γ, nγ, where γ = 1 mod p and γ = -1 mod q. So, the probability to pick randomly a ladder constant in L a,n not verifying 3 is:

P r(not 3 ) ≤ 2 n -4
Finally, to satisfy the last constraint 4 of Theorem 3, i.e.

3a ∈ (Z/nZ) , we use the following lemma from Gauss:

Definition 6 (r th Residues). Let n and r ≥ 2 be two integers. An integer a ∈ (Z/nZ) is a r th residue modulo n if there exists an integer ∈ Z/nZ such that r = a mod n, otherwise it is a non-residue modulo n.

Lemma 1 (Gauss [START_REF] Gauss | Disquisitiones Arithmeticae[END_REF]). Let p be a prime and r ≥ 2 be an integer. We denote b = gcd(p -1, r). We have: 1) For every integer a ∈ (Z/pZ) , a is a r th residue modulo p if and only if a p-1 b = 1 mod p, 2) there exists exactly p-1 b r th residues in (Z/pZ) , 3) if a ∈ (Z/pZ) is a r th residue modulo p then there exists exactly b integers ∈ Z/pZ such that r = a mod p.

According to the chinese remainder theorem, 3a is invertible modulo n = pq if and only if 3a is invertible modulo p and 3a is invertible modulo q. Moreover, because p is prime, 3a is invertible mod p if and only if 3 a = 0 mod p, i.e. a is a 3 rd non-residue modulo p. Therefore, the constraint 4 is not satisfied only if a is a 3 rd residue modulo p or q.

For a fixed, because b p = gcd(p -1, 3) = 1 or 3 and b q = gcd(q -1, 3) = 1 or 3, according to Lemma 1 there are at most 9 non invertible 3a integers modulo n, so the probability to pick randomly a ladder constant in L a,n not verifying 4 is:

P r(not 4 ) ≤ 9 n -4
In the worst case, the unfavorable cases are distinct, thus the probability to pick randomly a suitable ladder constant is:

P r( 1 2 3 4 ) ≥ 1 - p + q -2 n -4 + 2 n -4 + 9 n -4 = 1 - p + q + 9 n -4 ≈ 1 - 1 p - 1 q - 1 n
which is almost equal to 1 in a cryptographic context. Thus, in the RSA case n = pq finding a suitable ladder constant (Lines 1-9) in Table XII costs only one iteration with probability almost equal to 1.

E. Fully-Interleaved Ladder (DSA Case)

In Digital Signature Algorithm (DSA) [START_REF]Digital signature standard (DSS)[END_REF] context (or for Diffie-Hellman key exchange mechanism [START_REF] Rescorla | RFC2631: Diffie-Hellman key agreement method[END_REF]), the exponentiation is computed modulo n = p, where p is prime.

As in the RSA case we prove that finding a suitable ladder constant costs only one iteration with probability almost equal to 1. The argument is similar to the previous one but even simpler. If ∈ L a,n = [2, n-2]\{a} then 1 = a. Moreover = 0 mod n so 2 is invertible modulo n. Finally, = ±1 so 3 2 -1 = 0 mod n thus 2 -1 is invertible modulo n.

Remains the last constraint 4 3a is invertible modulo n. In the following we denote R 3 n (a) that a is a cubic residue modulo n, and let b = pgcd(n -1, 3).

According to Lemma 1, there exists n-1 b cubic residue in (Z/nZ) . -1 and 1 are cubic residue modulo n, as opposed to 0. Thus, the probability that an integer a ∈ [2, n -2] is a cubic residue is:

P r R 3 n (a) = n-1 b -2 n -3 = 1 b - 2 1 -1 b
n -3 According to Lemma 1, if a is a cubic residue then there exists b cubic roots of a in (Z/nZ) . If = 0, ±1 then a = 3 = 0, ±1, which is excluded. If = a then a = a 3 i.e. a(a + 1)(a -1) = 0 mod p, thus a = 0, ±1 which is excluded. So the cubic roots of a are automatically in L a,n = [2, n -2] \ {a}. Thus the probability that an integer ∈ L a,n is a cubic root of a is b n-4 . Therefore, if a is a cubic residue then the probability that ∈ L a,n satisfies the last constraint is:

P r 4 R 3 n (a) = 1 - b n -4
Finally, if a is not a cubic residue then every ∈ L a,n satisfies 4 . Therefore, the probability to pick randomly a suitable ladder constant is:

P r( 1 2 3 4 ) = P r( 4 ) = P r 4 R 3 n (a) × P r R 3 n (a) + P r 4 not R 3 n (a) × P r not R 3 n (a) = 1 - b n -4 1 b - 2 1 -1 b n -3 + 1 1 - 1 b + 2 1 -1 b n -3 = 1 - 1 n -4 + 2(b -1) (n -3)(n -4)
which is almost equal to 1 in a cryptographic context.

VI. SCALAR MULTIPLICATION IN ECC

As in Section V we demonstrate concrete examples of the ladder equations, this time for the scalar multiplication used in elliptic curve cryptography (ECC).

ECC was independently introduced in 1985 by Neal Koblitz [START_REF] Koblitz | Elliptic Curve Cryptosystems[END_REF] and Victor Miller [START_REF] Miller | Use of Elliptic Curves in Cryptography[END_REF]. It is nowadays considered as an excellent choice for key exchange or digital signatures, especially when these mechanisms run on resource-constrained devices. The security of most cryptocurrencies is based on ECC, which has been standardized by the NIST [START_REF]Digital signature standard (DSS)[END_REF], [START_REF] Barker | Recommendation for Pair-Wise Key Establishment Using Dicrete Logarithm Cryptography[END_REF].

Definition 7 (Elliptic Curve). Let p be a prime. An elliptic curve in short Weierstrass form over a finite field F p is defined by the set E(F p ) = (x, y) ∈ F p × F p y 2 x 3 + ax + b ∪ O, with a, b ∈ F p satisfying 4a 3 +27b 2 = 0 and O being called the point at infinity.

The set E(F p ) is an additive abelian group with an efficiently computable group law. Point addition P + Q or point doubling 2P involves additions and multiplications over F p . The point O is the identity element of the group law. Depending on the parameters a and b of the curve, there exists many formulas to optimize these two operations. A large and updated survey can be found on the elliptic curves explicit formulas database web site: https://www.hyperelliptic.org/EFD/ The main operation in ECC is scalar multiplication kA = A + • • • + A, where A is a point on a curve and k is an integer. It can be performed by using the double-and-add algorithm, similar to the square-and-multiply algorithm in Table II p.2. The initialization x ← 1 is replaced by P ← O, the squaring x ← x 2 is replaced by a doubling P ← 2P and the multiplication x ← ax is replaced by an addition P ← A + P , producing the output P = kA.

Thus, for a fixed point A we consider in this section the following known functions:

θ (P ) = 2P + A ε (P ) = 2P
And we consider ladder functions of the following form:

f (P, Q) = f P P + f Q Q + f A A g (P, Q) = g P P + g Q Q + g A A (P ) = P P + A A
with f P , f Q , P = 0 for both cases, and g P , g Q = 0 for the fully-interleaved ladders case, allowing in principle nonsecure scalar multiplications as intermediate computations for the secure one. The efficiency of the obtained solutions are discussed in Subsection VI-D.

A. Both Semi-and Fully-Interleaved Ladders Equation (2) (resp. Equation ( 5)) f (x, (x)) = θ (x) and Equation (3) (resp. Equation ( 6)) f ( (x), x) = (ε (x)) for the semi-(resp. fully-) interleaved cases imply that:

f P + f Q P = 2 f Q = (2 -f P ) P So (2 -f P )( 2 P -1) = 0. If f P = 2 then f Q = 0, thus we assume f P = 2.
To make no assumption about the finite field, we assume for the following P = ±1. They also imply that:

f Q A + f A = 1 f A = (2 -f P ) A -A So (2 -f P )( P + 1) A = 1 + A . • If P = -1 then A = -1, f Q = f P -2 and f A =
(f P -2) + 1, thus the candidate ladder functions are:

f (P, Q) = f P (P + Q + A) -(2Q + A) (P ) = -(P + A)
• If P = 1 then by assuming that 3 -2f P is invertible we obtain A = 1 3-2f P , f Q = 2f P and f A = 1 -2-f P 3-2f P , thus the candidate ladder functions are:

f (P, Q) = f P (P -Q) + 2Q + 1 -f P 3 -2f P A (P ) = P + 1 3 -2f P A B. Semi-Interleaved Ladder
The remaining Equation (1) ε ( (x)) = (θ (x)) for the semi-interleaved ladders is already satisfied for the P = -1 case. For the P = 1 case, it implies that ( 1 3-2f P -1)A = 0, thus to avoid constraint on A we assume f P = 1.

Theorem 4. The double-and-add algorithm with θ (P ) = 2P + A and ε (P ) = 2P is semi-ladderizable with two solutions:

1)

f (P, Q) = f P (P + Q + A) -(2Q + A) (P ) = -(P + A)
where f P = 0, 2, and:

2)

f (P, Q) = P + Q (P ) = P + A
The second solution is actually the common Montgomery ladder for the scalar multiplication. The first one for f P = 1 corresponds to the ladder function f (P, Q) = P -Q which is similar to the common Montgomery ladder except that the point Q has an opposite sign.

C. Fully-Interleaved Ladder

In the case P = -1, Equation ( 4) g (θ (x), (x)) = (θ (x)) for the fully-interleaved ladders is equivalent to:

2g P -g Q = -2 g P -g Q + g A = -2
So g Q = 2(1 + g P ) and g A = g P . Thus Equation ( 7) g (f ( (x), x), x) = ε (x) for the fully-interleaved ladders implies that f P g P = 0. Because we assumed f P , g P = 0 and we are looking for a solution independent from the chosen field for the coefficients, we have no solution for this case.

In the case P = 1, Equation ( 4) g (θ (x), (x)) = (θ (x)) for the fully-interleaved ladders is equivalent to:

   2g P + g Q = 2 g P + g Q 3 -2f P + g A = 1 + 1 3 -2f P So g Q = 2(1 -g P ) and g A = 1 + (2f P -1)g P -1
3-2f P . Thus Equation (7) g (f ( (x), x), x) = ε (x) for the fully-interleaved ladders implies that 2(f P (g P -1)+1)

3-2f P

A = 0. To avoid constraint on A we assume f P (g P -1) + 1 = 0, i.e. g P = 1 -1 f P . Theorem 5. The double-and-add algorithm with θ (P ) = 2P + A and ε (P ) = 2P is fully-ladderizable with:

f (P, Q) = f P P -Q - 1 3 -2f P A + 2Q + 1 3 -2f P A g (P, Q) = P + 1 f P -P + 2Q + 1 3 -2f P A - 1 3 -2f P A (P ) = P + 1 3 -2f P A
where f P = 0, 1, 2, and where f P and 3 -2f P are invertible.

The ladder functions of this solution for f P = 1 are f (P, Q) = P + Q, g (P, Q) = 2Q and (P ) = P + A, i.e. the common Montgomery ladder for the scalar multiplication, but is no longer a fully-interleaved ladder.

D. Application to ECC

The novel candidates are the first semi-interleaved ladder in Theorem 4 requiring a scalar multiplication by f P , and the fully-interleaved ladder in Theorem 5 requiring a scalar multiplication by 1 3-2f P then f P and 1 f P . Scalar multiplications cA for various coefficients c can be precomputed if A was a fixed point, as in the DSA signing step or the first step of Diffie-Hellman protocol. But both candidates involve scalar multiplications for non-fixed points R, linear combination of A, P , and Q.

A scalar multiplication cR for a specific coefficient c can be efficiently computed (i.e. with very few field operations) by using an elliptic curve endowed with an efficient endomorphism. On such curves, there exists a constant λ, depending on the modulus p and the parameters of the curve (see Definition 7), such that λR can be computed with very few multiplications (only one in most cases). This is detailed in [START_REF] Gallant | Faster point multiplication on elliptic curves with efficient endomorphisms[END_REF], where the authors describe the GLV method used in various standards, like the Bitcoin protocol specification or TLS [START_REF] Nir | RFC8422: Elliptic curve cryptography (ECC) cipher suites for transport layer security (TLS) versions 1.2 and earlier[END_REF].

Another way to optimize the cost of cR is to use a short addition chain [START_REF] Knuth | The Art of Computer Programming: Fundamental Algorithms[END_REF], so that the number of point operations to compute cR is equal to the length of the chain. The problem of computing the shortest addition chain for a given integer is hard [START_REF] Bahig | Improved generation of minimal addition chains[END_REF] but for "small" integers there exists tables giving the corresponding chain, like https://bo.blackowl.org/random/ln.

Therefore, for the first semi-interleaved ladder in Theorem 4, one can use an elliptic curve endowed with an efficient endomorphism λ and assign f P = λ. Or, for a non-specific curve, one can choose f P amongst the integers corresponding to "very short" addition chains. In that case, because as in Theorem 2 f P does not occur in (P ), f P can be chosen randomly for every iteration, thus increasing security compared to the common Montgomery ladder. However, this comes at the price of drastically increasing the computational cost of the scalar multiplication.

For the fully-interleaved ladder candidate, neither an efficient endomorphism nor an addition chain can be used. Indeed, that f P R can be efficiently computed does not imply that 1 f P R can also be efficiently computed, because both coefficients are dependent. Therefore, the fully-interleaved ladder candidate might not be applicable in practice to ECC.

VII. CONCLUSION AND FUTURE WORK

We abstracted away the algorithmic strength of the Montgomery ladder against side-channel and fault-injection attacks, by defining semi-and fully-ladderizable algorithms. We designed also fault-injection attacks able to obtain some/all bits of the secret key from the semi-interleaved ladders like the Montgomery ladder, and even from the fully-interleaved ladders if the attacker is able to stuck-at the key register.

As examples, we provided for the modular exponentiation a better semi-interleaved ladder using a random mask updated at every iteration, and a fully-interleaved ladder depending on an appropriate ladder constant. We investigated the properties required by the ladder constant, and discovered that they are almost always satisfied in a cryptographic context.

To demonstrate that generality of our approach, we provided new algorithms for the scalar multiplication in elliptic curves: a novel and effective semi-interleaved ladder, and a fullyinterleaved ladder. The applicability of the last candidate depends on the efficient computations of several dependent coefficients for the scalar multiplications, which is an open and interesting problem.

Finally, we only investigated the univariate case for conditional branching, but the multivariate case may be of interest. For instance, a multi-variable polynomial 0≤n≤d n1+•••+n k =n c n1,...,n k 1≤i≤k x ni i can be represented by a multidimensional array of coefficients, thus the manipulation of ladder equations could be handled by using matrix operations.

Fig. 1 .

 1 Fig. 1. Attack the Last Bit

Fig. 3 .Fig. 4 .

 34 Fig. 3. x or y 01

  final , y final ) ← EXE(x init , y init , k >i = 0) 14:(x fault , y fault ) ← EXE(x init , y init , k >i = 0, y i ) final , y final ) ← EXE(x init , y init , k >i = 0) 3:(x fault , y fault ) ← EXE(x init , y init , k >i+1 = 0) 4:if x fault = x final or y fault = y final then

			1
	8:		else
	9:		k[i] ← 0
	10:		FIx ← 0
	11:		end if
	12:	else
	13: (x 15: if x fault = x final then
	16:		k[i] ← 0
	17:		else
	18:		k[i] ← 1
	19:		FIx ← 1
	20:		end if
	21:	end if
	22: end for
	23: return k
			TABLE VIII
		PROTOCOL TO ATTACK THE SEMI-INTERLEAVED LADDERS
	1: for i = 0 to n -1 do
	2: (x 5:	k[i + 1] ← 1
	6:	else
	7: (x 10:	k[i + 1] ← 0
	11:		end if
	12:	end if
	13: end for
	14: return k
			TABLE IX
	PROTOCOL TO ATTACK BOTH SEMI-AND FULLY-INTERLEAVED LADDERS

final , y final ) ← EXE(x init , y init , k >i = 1) 8:

(x fault , y fault ) ← EXE(x init , y init , k >i+1 = 1) 9:

if x fault = x final or y fault = y final then

TABLE XIII COST

 XIII PER BIT OF THE MONTGOMERY, SEMI-AND FULLY-INTERLEAVED LADDERS (AFTER MEMOIZATION)

Even observing the duration of the whole execution can leak the Hamming weight of the secret key, and thus can narrow down the exploration space.

A multiplication can be distinguished from a squaring, hence variants with squaring only have been proposed in[START_REF] Clavier | Square Always Exponentiation[END_REF] and improved in[START_REF] Ha | Power Analysis Attacks on the Right-to-Left Square-Always Exponentiation Algorithm[END_REF].

The power profile depends also on the values in the considered registers, so computing a multiplication in every case is better against SPA but not against CPA (Correlation Power Analysis)[START_REF] Brier | Correlation power analysis with a leakage model[END_REF], even if standard blinding techniques can prevent differential attacks[START_REF] Coron | Resistance Against Differential Power Analysis For Elliptic Curve Cryptosystems[END_REF],[START_REF] Messerges | Power Analysis Attacks of Modular Exponentiation in Smartcards[END_REF].

See[START_REF] Joye | Highly Regular Right-to-Left Algorithms for Scalar Multiplication[END_REF] for highly regular right-to-left variants,[START_REF]Highly Regular m-Ary Powering Ladders[END_REF] for a generalization to any basis and left-to-right/right-to-left variants, and[START_REF] Walter | The Montgomery and Joye Powering Ladders are Dual[END_REF] for their duality.

The variables x and y may have different access time, which hinders protection against cache-timing leakage.

Because the condition depends on the secret, we will not assume that in the then branch the condition is satisifed but not in the else branch, to prevent data dependencies that could be attacked.

The former is actually better regarding vulnerability to the M safe-error[START_REF] Joye | The Montgomery Powering Ladder[END_REF] or collision[START_REF] Kim | Practical Second-Order Correlation Power Analysis on the Message Blinding Method and Its Novel Countermeasure for RSA[END_REF] attacks, showing that our methodology is good practice.

A countermeasure proposed in[START_REF] Le | Randomizing the Montgomery Powering Ladder[END_REF] is to randomly blend variants of the ladder, or compute the exponentiation by taking a random (bounded) walk.

To simplify the notations, we assume in this section that the counter is incremented (from 1 to n with a step 1), but the argument is similar for other initial or final values, a decremented counter, and/or other step values.

In the Montgomery ladder (TableIII) the invariant y = ax is satisfied for every iteration. So, if a random fault is injected in x or y, the violation of the invariant allows the algorithm to detect the fault[START_REF] Giraud | An RSA Implementation Resistant to Fault Attacks and to Simple Power Analysis[END_REF] and thus to enhance the appropriate fault policy, as stopping the program or switching to a random key for the rest of the computation. The same argument holds for our semiand fully-interleaved ladders with the invariant y = (x).

Note that the iterations are reversed in this attack protocol.

ACKNOWLEDGMENTS

The authors want to thank the reviewers of ARITH 2020 for their relevant and very useful comments.