Frederic Marias
email: frederic.marias@univ-pau.fr

Stéphanie Vielcazals

Pierre Cézac

François Jacques Mercadier

P Cezac

F Cansell

Theoretical study of the expansion of supercritical water in a capillary device at the output of a hydrothermal oxidation process

Keywords: Supercritical water oxidation, Modelling, Expansion, Salts, Thermodynamic approach

Theoretical study of the expansion of supercritical water

in a capillary device at the output of a hydrothermal oxidation process

Introduction

Organic wastes produced by our societies need to undergo some treatment in order to be destroyed (at least to become inert for the environment) and to recover the potential energy that their constitutive molecules hold. The transformation of these organic species requires the addition of an oxidant in order to transform their carbon into carbon dioxide and their hydrogen into water. To complete this transformation within a short time, the use of activators of reaction is very frequent. Indeed, in the case of biological treatment, the activator is bacteria media, while it is temperature in the case of incineration, pyrolysis or gasification. Hydrothermal oxidation uses both temperature and pressure as activators. The main effect of pressure is to homogenise the reactive media and to enhance transfer inside this homogeneous phase (at high pressure, oxygen can be completely dissolved into water holding organic wastes) while the effect of temperature is to enhance the chemical reaction rate.

One of the main advantages of hydrothermal oxidation is that this mode of operation is compatible with sustainable development. The by products of this process are nontoxic. Carbon and hydrogen are respectively converted into carbon dioxide and water while hetero-atoms (N, Cl, S, . . .) lead to atmospheric nitrogen and mineral acids [START_REF] Dutournié | Modélisation de réacteurs d'oxydation de déchets organiques en milieu aqueux supercritique[END_REF][START_REF] Cansell | Thermodynamic aspect of supercritical fluids processing: applications to polymers and wastes treatment[END_REF][START_REF] Cansell | Hydrothermal oxidation of model molecules and industrial wastes[END_REF][START_REF] Tester | Supercritical water oxidation technology. Process development and fundamental research[END_REF]. Among the different process of hydrothermal oxidation, supercritical water oxidation is the most efficient because it operates at high pressure (25 MPa) but also at higher temperature (above the critical point of pure water 647 K) than other hydrothermal oxidation processes (di-phasic wet oxidation and under critical homogenous oxidation) leading to higher chemical reaction rates, and thus to shorter reactors [START_REF] Smith | Supercritical water oxidation: principles and prospects[END_REF]. It is also very interesting from the environmental point of view because the mineral acids that can be present in the waste itself (NaCl, Na 2 SO 4 , (NH 4 ) 3 PO 4 , . . .), or that can be produced inside the reactor itself (HCl, H 2 SO 4 , . . .) [START_REF] Hodes | Salt precipitation and scale control in supercritical water oxidation[END_REF] are at the solid state Nomenclature b empirical parameter (kg 1/2 mol -1/2 ) C molar concentration of salts inside the capillary (mol l -1 ) d inner diameter of the capillary (m) e esu electronic charge in esu (4.8029 × 10 -10 esu). G • i standard molal Gibbs free energy of formation (J mol -1 ) G • R standard Gibbs free energy of reaction (J mol -1 ) h specific enthalpy of the reactive media (J kg -1 ) H heat transfer coefficient with the surroundings (W m -2 K -1 ) H F NaCl latent heat of fusion of NaCl (J mol above the critical point of pure water because of the low value of its dielectric constant [START_REF] Valyashko | Phase equilibria in water-salt systems: some problems of solubility at elevated temperature and pressure[END_REF]. At present time a lot of research is performed on the particular topic of salts behaviour into supercritical water both on the modelling and on the experimental point of view [START_REF] Hodes | Salt precipitation and scale control in supercritical water oxidation[END_REF][START_REF] Hodes | Salt precipitation and scale control in supercritical water oxidation. Part B. Commercial/full-scale applications[END_REF][START_REF] Ott | Influence of salts on the dehydration of several biomass-derived polyols in sub-and supercritical water[END_REF][START_REF] Bermejo | Bubble points of the systems isopropanol-water, isopropanol-water-sodium acetate and isopropanol-water-sodium oleate at high pressure[END_REF][START_REF] Bermejo | The influence of Na 2 SO 4 on the CO 2 solubility in water at high pressure[END_REF]. This solid state makes the separation between the process stream and the salts easier. Indeed if this separation is performed while mineral acids are kept at solid state, there is no need to use a waster water treatment that would be necessary to recover minerals dissolved in water. Such a supercritical fluid solid separation can be handled into a cyclone and this is what we plan to do. However, in order to limit the cost of such a device, it is necessary to lower both the pressure and the temperature of the fluid to process. Our proposal is to use a capillary device in order to expand the fluid and thus to reduce its pressure and consequently its temperature. The alternative to use such a device is motivated by the fact that regulation systems that are able to control a pressure drop of 250 bar are very complex to handle when the flow is loaded with solid particles.

The first part of this article gives insights into the device we actually study. The specifications (in terms of operating conditions of the incoming fluid) and the geometrical parameters to design are given in this part. Then, in a second part, the mathematical model that has been used to compute this data is presented. This model is divided into two parts. The first one deal with the expansion itself while the second part deals with thermodynamical aspects that allow for the prediction of the distribution of salts between the supercritical, the vapour and the liquid phase that might occur during the expansion of the process stream. Finally, some results of the model are presented. As a preliminary, the influence of the diameter of the capillary on its length is discussed. Then, the next set of results focuses on the expansion at nominal conditions. Evolution, of temperature, pressure as well as distribution of minerals between the phases is presented versus the length of the capillary device. Finally, the influence of the operating conditions on the length of the capillary and on the possible recover of salts at solid state is discussed.

Device under study

The device under study is depicted in Fig. 1. It is composed of a storage tank where mineral acids can are dissolved into pure water. This mixture is fed to a heater by a high pressure pump at 25 MPa. The control loop for the mass flow rate of mixture entering the process is not represented on the figure. The fluid then enters the heater that allows for the control of the temperature of the stream entering the capillary tube. Basically, this heater represents the reactor of the supercritical water oxidation process that would lead to energy release and thus heating up of the process stream. The mixture is then expanded into the capillary device under study before entering the cyclone. The capillary is insulated by a calcite shell. Inside the cyclone the solid/gas separation is performed under the effect of centrifugal force acting at high speed of rotation. The free of solids vapour exhausting the cyclone is then condensed and collected into a tank. The capillary that needs to be designed have to be able to expand the following process stream:

• inlet mass flow rate: ṁin = 20 kg h -1 ;

• inlet pressure: P in = 25 MPa;

• inlet temperature: T in = 873 K;

• inlet salts concentration: C in = 0.5 mol l -1 ;

As it has been quoted into the introduction, and, as it is explained in the literatures [START_REF] Laspidou | Heather effects on cyclone performance for the separation of solids from high temperature and pressure effluents[END_REF][START_REF] Dell'orco | The separation of particulates from supercritical water oxidation processes[END_REF][START_REF] Killilea | Supercritical water oxidation: microgravity solids separation[END_REF], the process stream entering the cyclone must have a pressure of the order of magnitude of the atmospheric pressure. The role of the capillary device is to expanded the fluid under the combined effect of:

• Linear pressure drop inside the tube.

• Decrease of the density of the mixture (under both pressure and temperature effects). • Increase in the velocity of the fluid (by conservation of the total mass flow rate of mixture) which, in turns, increases the linear pressure drop. • Decrease of the temperature of the fluid (by conservation of the total energy of the fluid) which, in turns, decreases the density of the fluid.

In order to compute the length of the capillary device, we impose the value of the pressure at the outlet of the tube to be equal to atmospheric pressure:

P out = P atm = 0.1 MPa (1)

Mathematical modelling

In this section, the governing equations responsible for the expansion of the fluid are presented. We first give insights on the assumptions that have been formulated in order to translate the physical and chemical phenomena into mathematical formalism.

Assumptions

Inside the capillary, the mixture is composed of water and salts. Thus, the prediction of the thermodynamical properties of the mixture (enthalpy and density) should take into account the influence of these salts as well as the influence of temperature and pressure.

However, because of the low concentration of salts inside the mixture, the main part of the total mass flow rate of the fluid flowing inside the reactor is water. This is the reason why we assume that the process stream is pure water. These properties are computed from the IAPWS formulation for pure water [START_REF] Wagner | The industrial standard IAPWS-IF97 for the thermodynamic properties and supplementary equations for other properties[END_REF]. So the first assumption is:

Assumption 1.
Thermodynamical properties (specific enthalpy and density) of the reacting media are assumed to be equal to pure water properties.

The second assumption (which is closed to the first one) is relative to the transport properties of the mixture. Indeed, with the same justification than Assumption 1, we postulate: Assumption 2. Transport properties (thermal conductivity and viscosity) of the reacting media are equal to pure water properties and are computed from the IAPWS formulation for pure water.

Given some general operating conditions (temperature at inlet is above 450 • C and pressure is 25 MPa) and a mass flow rate of 20 kg h -1 , the Reynolds's number at the entrance of the capillary can be evaluated: Re = 58 000. Thus the flow field inside the tube is fully turbulent. That is why we assume the plug flow mode of operation of this capillary. Thus, in stationary mode of operation, the state variables of the system are one-dimensional. This leads to the third assumption: Assumption 3. In stationary mode of operation, the system under study is considered as one-dimensional.

Although the whole apparatus is thermally insulated, it is obvious that thermal losses exist. They have to be taken into account into the energy balance of the device. To compute these losses, we have assumed that at each location of the reactor, a specific heat flux was lost according to Newton's law for heat transfer.

Assumption 4. The specific heat flux by the thermal losses is expressed as:

ϕ lost = H(T -T ext ) (2)
In this expression, H represents the overall heat transfer coefficient with the surroundings, T and T ext stand, respectively for the local temperature of the fluid and the external temperature.

As it has been quoted into the introduction, a lot of mineral acids can be present within the fluid to process. A rigorous study should take into account the specificity of each of these salts. However, in order to simplify the mathematical treatment and to simplify the thermodynamical description of the system we suppose the salts to be composed solely of NaCl. Assumption 5. The salts are supposed to be solely composed of NaCl.

When the pressure and temperature are lowered, we might reach the saturation point during the expansion. This means that water will exist under different phases. The salts present in the mixture have different affinities for each of these phases. In order to compute the distribution of the salts between these phases, we assume that the thermodynamical equilibrium of the salts is reached. This means that we do not take into account the time that would be required to dissolve salts from solid state to liquid for example. This is a way to maximise the estimation of the salts dissolved within the liquid phase when saturation is reached. This leads to the final assumption. Assumption 6. The distribution of salts between the different phases of water is computed assuming thermodynamical equilibrium to be reached at each location of the capillary.

Governing equations

One of the aims of a mathematical model is to provide some information about the physical and chemical phenomena that can occur in an apparatus when either this apparatus does not exist or some data are inaccessible to physical measurement. For example, in our case, we expect the model to be able to describe the evolution of the salt concentration as well as the temperature along the capillary. In order to obtain such information, we need to write some mathematical equations that translate physical and chemical phenomena into mathematical formalism. Basically, these equations postulate that in stationary mode of operation, mass, species, momentum and energy are conserved over a control volume of our choice. Moreover, in order to compute the distribution of the salts between the different phases, we assume that at each location of the capillary, the Gibb's free energy has reached her minimal value.

In the following paragraph we show the governing equations in their "derivative" form inside each of the three reactors.

Total mass conservation

∂ρu ∂x = 0 (3)
where ρ stands for the local density of the mixture and u for its velocity. This equation states that within the reactor mass is neither created nor disappeared.

Momentum conservation

As it has been quoted into Assumption 3, we consider the system as one-dimensional. However, a complete formulation of the momentuum equation should include a two-dimensional formulation of this equation because of the shear stress at the wall of the reactor. Indeed, this shear stress resutls in high radial gradients a this loccation. Thus the momentum balance is written as follows:

∂ρuu ∂x = - ∂P ∂x + ∂τ xj ∂x j ( 4
)
where P stands for the local pressure of the reacting media, and τ xj for the stress tensor, in direction x, linked to a gradient of velocity in the direction j. Moreover, in turbulent mode of operation, the stress tensor should include the Reynolds's stress tensor and an appropriate model to compute it. This would drastically complicate the mathematical description of the process. Thus, the choice that has been made here is to compute the divergence of the stress tensor as the local pressure drop over the control volume under consideration [START_REF] Kodra | Modeling of oxidation of aqueous waste in a deep well reactor[END_REF]. This computation has been done according to Churchill's correlation, valid for any Reynolds's number [START_REF] Idel'cik | Memento des Pertes de Charge[END_REF]. The resulting balance equation is then:

∂ρuu ∂x = - ∂P ∂x - ξ x ( 5
)
where ξ/ x represents the local lineic pressure drop inside the capillary tube. This is a positive data of our model.

Energy conservation

Following the formalism used to derive the divergence of the stress tensor, one is able to compute the disspation (both viscous and turbulent) as [START_REF] Chassaing | [END_REF]:

Θ = u ξ Δx (6)
Then the balance of energy over the control volume is expressed as:

∂ρuh ∂x = u ξ x + u ∂P ∂x + ∂ ∂x λ ∂T ∂x - 4H d (T -T ext ) (7)
where λ stands for the thermal conductivity of pure water and is computed according to Wagner and Kruse [START_REF] Wagner | The industrial standard IAPWS-IF97 for the thermodynamic properties and supplementary equations for other properties[END_REF]. This equation states that the enthalpy of the fluid along the device is

• Increased by the dissipation of mecanical energy by friction (the term ξ/ x is positive). • Decreased by the expansion (the term ∂P/∂x is negative).

• Decreased by conduction and by external losses (the term ∂T/∂x is negative).

Vapour fraction

The vapour fraction needs to be computed when saturation has been reached. If both temperature and pressure are above the critical point of pure water, or, if the operating pressure is lower than the saturation pressure we postulate:

ω = 1 ( 8
)
If the saturation curve has been reached, then the vapour fraction is computed replacing Eq. ( 8) by the following:

P = P sat (T ) (9)
This leads to an ordinary differential and algebraic system of seven unknowns (u, P, T, ρ, h, μ, ω) with seven Eqs. ( 3), ( 5), ( 7), ( 9)-( 12).

Models for density, enthalpy to weight and viscosity

Finally, to close the problem, one needs to write equations for the computation of density and the computation of enthalpy. These equations are issued from the IAPWS formulation for pure water Eq. ( 8) (see Assumption 1) and they are written as:

ρ = ρ m (P, T, ω) (10) h = h m (P, T, ω) (11) μ = μ m (P, T, ω) (12)

Salts accountability

As long as the rate of vapourization is equal to 1, salt is supposed to be distributed between a vapour phase and a solid phase. The model of Shin et al. [START_REF] Shin | Development of a solution model to correlate solubilities of inorganic compounds in water vapor under high temperatures and pressures[END_REF] was used to predict the solubility, in terms of mass fraction of salt in the vapour phase (y NaCl ):

ln(y NaCl ) = H F NaCl RT T T F NaCl -1 - v NaCl RT (δ water -δ NaCl ) 2 -1 + v NaCl v water -ln v NaCl v water ( 13
)
where H F NaCl and T F NaCl stand, respectively for the heat of fusion (J mol -1 ) and the melting point of NaCl (K), while v k and δ k represent the molar volume (m 3 mol -1 ) and the solubility parameter of the species k ((J m -3 ) 1/2 ).

The solubility parameter for water is calculated using the expression proposed by Sagara et al. [START_REF] Sagara | Calculation of Henry's constant of gases in hydrocarbon solvent by regular solution theory[END_REF]:

δ water = (6v solid water εN 0 ) 0.5
v water [START_REF] Dell'orco | The separation of particulates from supercritical water oxidation processes[END_REF] where v solid water stands for the solid molar volume of water. The value proposed by Wagner and Kruse [START_REF] Wagner | Properties of Water and Steam[END_REF] was used in this study. N 0 is Avogadro's number (mol -1 ) and ε is the pair potential energy (J). These values are computed according to Higashi et al. [START_REF] Higashi | Measurement and correlation for solubilities of alkali metal chlorides in water vapor at high temperature and pressure[END_REF]. Finally, the molar volume of water vapour, v water , is computed following the relations established in IAPWS-IF97 [START_REF] Wagner | The industrial standard IAPWS-IF97 for the thermodynamic properties and supplementary equations for other properties[END_REF]:

The solubility parameter of NaCl is given by [START_REF] Barton | Handbook of Solubility Parameters and Other Cohesion Parameters[END_REF]:

δ NaCl = u NaCl v NaCl 0.5 (15)
where u NaCl is the cohesive energy of NaCl. The dependence upon the temperature of this energy is computed according to Higashi et al. [START_REF] Higashi | Measurement and correlation for solubilities of alkali metal chlorides in water vapor at high temperature and pressure[END_REF]:

u NaCl = 0.16491T + 14.23 (16)
v NaCl is the molar volume of NaCl. It is calculated following the work proposed by Iwai et al. [START_REF] Iwai | Correlation of solubilities of highboiling components in supercritical carbon dioxide using a solution model[END_REF]:

ln(v NaCl ) = α v NaCl ln(ρ water ) + β v NaCl ( 17
)
The parameters α v NaCl and β v NaCl are dimensionless parameters estimated by Shin et al. [START_REF] Shin | Development of a solution model to correlate solubilities of inorganic compounds in water vapor under high temperatures and pressures[END_REF].

All the parameters used for calculate the solubility of NaCl in the vapour phase are accessible Table 1.

During the expansion, some liquid water might be formed in the capillary. Because of the higher solubility of NaCl in this phase than in the vapour one, specific attention must be paid to this phase. Indeed the following equilibrium has to be taken into account:

NaCl sol ↔ Na acq + + Cl acq - (18)
To describe pure salt solubility in the aqueous phase, we use the mathematical form of the liquid solid equilibrium:

i m i m 0 γ i ν i -K(T ) = 0 ( 19
)
where m i is the molality of species i and m 0 is the unit molality.

In the preceding expression, γ i stands for the activity coefficient of the species under inspection while ν i represents its stoichiometric coefficient in the equilibrium relation. Finally, the equilibrium constant K is computed from the definition of the standard Gibbs free energy:

ln(K) = - G • R RT ( 20
)
This energy was computed using the standard molal Gibbs' free energy taken from the SUPCRT92 computer program data file [START_REF] Johnson | SUPCRT92: a software package for calculating the standard molal thermodynamic properties of minerals, gases, aqueous species reactions from 1 to 5000 bar and 0-1000 • C[END_REF].

Pitzer's model [START_REF] Pitzer | Activity Coefficients in Electrolyte Solutions[END_REF] was used in order to evaluate the activity coefficients. There are numerous articles, which give complete details of the Pitzer equations. For an electrolyte CA with ν C cation of charge z C and ν A anion of charge z A , the mean activity coefficient is given by

ln(γ ± CA ) = -|z C z A |A φ I 1/2 1 + bI 1/2 + 2 b ln(1 + bI 1/2 ) + m 2ν C ν A ν C + ν A B γ CA + m 2 2(ν C ν A ) 3/2 ν C + ν A C γ CA ( 21
)
where b is an empirical parameter fixed at 1.2, m the mean molality the electrolyte CA, I the ionic strength and A φ is the Debye-Hückel parameter expressed in specific units [START_REF] Zemaitis | Handbook of Aqueous Electrolyte Thermodynamics[END_REF]:

A φ = 1 3 2πN 0 ρ A φ w 1000 1/2 (e esu ) 2 ψk erg B T 3/2 (22)
In Eq. ( 22), ρ A φ w is the density of aqueous solution (g cm -3 ), k erg B the Boltzmann's constant in erg (1.38045 × 10 -16 erg), T the absolute temperature (K), ψ the water dielectric constant and e esu is the electronic charge in esu (4.8029 × 10 -10 esu).

In Eq. ( 21), C γ CA and B γ CA are parameters of the model and they are computed according to:

C γ CA = 3 2 C φ CA , ( 23
)
B γ CA = B CA + B φ CA ( 24
)
where

B φ CA = β (0) CA + β (1) CA exp(-α 1 I 1/2 ) + β (2) CA exp(-α 2 I 1/2 ) ( 25
)
and

B CA = β (0) CA + β (1) CA g(α 1 I 1/2 ) + β (2) CA g(α 2 I 1/2 ) (26)
where the function g is defined as:

g(x) = 2 x 2 [1 -(1 + x) exp(-x)] ( 27
)
For a salt with at least one univalent cation or anion like NaCl, α 1 = 2 and β

(2) CA = 0 [START_REF] Zemaitis | Handbook of Aqueous Electrolyte Thermodynamics[END_REF][START_REF] Carrier | Salt solubility under high pressure and high temperature[END_REF].

β (0) CA , β (1)
CA and C φ CA are electrolyte specific parameters functions of the temperature and the pressure. We use the function proposed by Pitzer et al. [START_REF] Pitzer | Thermodynamic properties of aqueous sodium chloride solutions[END_REF]: f (T, P) = q 1 T + q 2 + q 3 P + q 4 P 2 + q 5 P 3 + q 6 ln(T ) + (q 7 + q 8 P + q 9 P 2 + q 10 P 3 )T + (q 11 + q 12 P + q 13 P 2 )T 2 + (q 14 + q 15 P + q 16 P 2 + q 17 P 3 ) T -227 + (q 18 + q 19 P + q 20 P 2 + q 21 P 3 ) 680 -T

The parameters necessary for NaCl/H 2 O system are given in Table 2.

The preceding equations yield the respective solubility of NaCl in the vapour and the liquid phases. The model is completed using mass balances that compute the distribution of the salt between each phase.

Results

Diameter of the capillary

As it has been quoted in the introduction, the model is firstly used to check the influence of the diameter of the capillary on its length and also on the distribution of NaCl at the output. Table 3 sums us these results. It can be observed that the higher the diameter is, the longer the capillary device must be. Indeed, for small diameter devices, friction forces are much more important leading to a smaller length. For example the length of the 6.4 mm capillary device is approximately 17 km whereas it is only 0.624 m for a 0.8 mm device. Thus one could conclude that the smallest internal diameter is the better. However, the percentage of NaCl dissolved in the liquid phase decreases when the internal diameter increases. Fig. 2 gives an explanation about this phenomenon. This figure illustrates the two expansions in the (P-T) diagram. What can be seen in that diagram is that for lower diameters the expansion pathway is such that the saturation curve is reached quicker than for higher diameters. The reason for this quicker appearance of liquid state is that the shorter the diameter is, the higher the speed of the fluid is. These higher speeds lead to higher pressure drop and because of mechanical energy conservation, to a more important decrease in the temperature of the stream at a given pressure. This leads to value of the vapour fraction of ω = 0.988 and 0.997 for the respective diameters of 0.8 and 1.6 mm. This lower value of the vapour fraction means that more liquid water has been formed at the end of the device. Because the solubility of NaCl is higher in the liquid phase than in the vapour one, the final amount of salt in the liquid phase is higher. Thus two opposite conclusions might be drawn regarding the length of the device or the distribution of salt at the output. Because of its lower size, we have finally chosen to focus our studies on the 1.6 mm diameter device. coupling between the variables P, T, ρ and U. Indeed, the pressure drop firstly leads to a decrease in the density of the fluid. For total mass conservation this density decrease leads to an increase in the velocity of the fluid, what in turns (because of total energy conservation) induces a lowering of the temperature. By the end of the capillary, the density becomes so small that the velocity becomes very high and creates very high temperature gradient at this position. These phenomena have to be taken into account for future design of the device. Fig. 5 represents the distribution of NaCl in the different phases as a function of position in the device. The curve representing the liquid fraction has voluntary be translated to the right in order see both the stiff decrease in the solid phase and increase in the liquid phase. This stiff behaviour is linked to the occurrence of liquid water at this position: once liquid water appears, out equilibrium calculation saturates the liquid fraction into NaCl up to its solubility at this point.

Expansion at nominal conditions

Influence of the operating conditions

Table 4 summarises the influence of the inlet temperature on the properties of the expanded flow. The main influence of this parameter is relative to the inlet velocity of the fluid. If the temperature is rose, the inlet density is also decreased what increases the inlet velocity of the fluid. Finally, this leads to a decrease in the total length of the capillary. However, one can notice that the temperature does not exercise a great influence on the salt distribution at the output.

Table 5 shows the influence of the initial mass flow rate of incoming water on the properties of the output of the device. Once again, the impact of the total mass flow rate is linked to the initial velocity of the fluid. For a given set of inlet pressure and temperature, an increase in the total mass flow rate leads to an increase in the inlet velocity. Finally, one can observe that the higher the mass flow rate is, the shorter the length is. As it was explained in the paragraph devoted to the description of the diameter, longer expansion leads however to a smaller amount of salt in the liquid phase, the occurrence of the liquid phase being translated towards the output of the device.

Table 6 shows the influence of the external heat transfer coefficient. From adiabatic to free convection with the surroundings (H ≈ 30 W m -2 K -1 ), there is no significant evolution of the output data. This means that the heat losses to the surroundings do not contribute significantly to Eq. ( 7). This also means that there is no need to perfectly insulate the device.

To conclude with the influence of the operating parameters, Fig. 6 gives the influence of the initial salt composition on its final distribution between the liquid phase and the vapour phase. Because the computation of solubilities is post processed from the results of the expansion calculation, the initial concentration of salt does not have any influence on the evolution of these solubilities inside the tube. It is just that for very low inlet con- centration, the final solubility of salt in the liquid phase is higher than its initial concentration in the mixture. The whole amount of the incoming salt is dissolved in liquid water at the exhaust of the device. Intermediate results can be observed for the whole range of incoming salt concentrations.

Conclusion

This paper deals with theoretical expansion of supercritical water, loaded with salts, into a capillary device. A mathematical model for the flow field has been developed. Basically, it is based on the mass balance equation, the momentum equation and the energy conservation equation. It is completed with the assumption of pure water behaviour for the computation of the density of the media as well as for its enthalpy to weight. From the prediction of salt distribution point of view, a thermodynamic approach has been used. It allows for the computation of the solubilities of NaCl within the liquid and the vapour phase, leading in turns (with the aim of a mass balance) to the amount of salt present in each phase.

Using this model it has been possible to enhance our knowledge of how such an expansion is processed within a capillary device. Details have been given on how the pressure drop, linked to the friction of the flow with the capillary material, exercises modifications of the value of the fluid density and in turns on its temperature. It has also shown the importance of the thermal gradients and velocities near the output of the tube. Such considerations have to be carefully taken into account for future design of the apparatus. However, the model has also helped us to make our choice for the diameter of the device. A value of 1.6 mm seems to correspond to our specifications (in terms of total length of the device and amount of dissolved salt). Moreover the model enhances our confidence in terms of possibility of separation of the salts from the flow. Our computations have shown that a maximum value of 5.17% of the incoming salt (if sufficiently concentrated) might be dissolved into liquid water. We would like to point out that this is a thermodynamical computation, what means that this represents the maximal value that might be observed. However, because of the high value speed of the flow near the output of the device, we expect that the residence time of the fluid inside the tube once liquid has appeared will not be sufficient for dissolution to effectively occur. This would mean that qt the output of the device it is possible to separate the solid from the exhausting fluid at atmospheric condition.

Fig. 1 .

 1 Fig. 1. Presentation of the device under study.

Fig. 2 .

 2 Fig. 2. P-T diagram of the expansion for capillary diameters of 0.8 and 1.6 mm.

Figs. 3

 3 Figs.3-5show the evolution of the state variables of the system a s a function of the distance from the inlet of the device for an adiabatic expansion operated at nominal conditions ( ṁin = 20 kg h -1 , P in = 25 MPa, T in = 873 K, C in = 0.5 mol l -1 ). Figs.3 and 4should be studied together because there is a high

Fig. 3 .

 3 Fig. 3. Evolution of temperature and pressure as a function of position inside the capillary device for nominal expansion.

Fig. 4 .

 4 Fig. 4. Evolution of density and velocity as a function of position inside the capillary device for nominal expansion.

Fig. 5 .

 5 Fig. 5. Evolution of ratio of NaCl held in the solid phase, the liquid phase and the vapour phase as a function of position inside the capillary device for nominal expansion.

Fig. 6 .

 6 Fig. 6. Influence of the initial concentration of NaCl on the ratio of NaCl held in the solid phase, the liquid phase and the vapour phase at the output of the capillary device.

Table 1

 1 Parameters used to compute the solubility of NaCl in the vapour phase according to Shin et al.[START_REF] Killilea | Supercritical water oxidation: microgravity solids separation[END_REF]

	Parameter	Value	Reference
	H F NaCl (J mol -1 )	28200	[26]
	T F NaCl (K)	1074	[26]
	v solid water (m 3 mol -1 )	1.963 × 10 -5	[17]
	ε	9.3926 × 10 -21	[18]
	α v NaCl β v NaCl	-1 -2.62	[15] [15]

Table 2 β

 2

	(0) CA , β	(1) CA , C CA parameters for the H 2 O/NaCl system (-273 < T < 573 K and -1 < P < 1000 bar) φ
	Parameters	β	(0) CA	β	(1) CA	φ CA C
	Q 1		-656.81518	119.31966	-6.1084589
	Q 2		24.8691295	-0.48309327	4.0217793 × 10 -1
	Q 3		5.381275267 × 10 -5	0.0	2.2902837 × 10 -5
	Q 4		-5.58874699 × 10 -8	0.0	0.0
	Q 5		6.58932633 × 10 -12	0.0	0.0
	Q 6		-4.4640952	0.0	-0.075354649
	Q 7		0.01110991383	1.4068095 × 10 -3	1.531767295 × 10 -4
	Q 8		-2.657339906 × 10 -7	0.0	-9.0550901 × 10 -8
	Q 9		1.746006963 × 10 -10	0.0	0.0
	Q 10		1.0462619 × 10 -14	0.0	0.0
	Q 11		-5.307012889 × 10 -6	0.0	-1.53860082 × 10 -8
	Q 12		8.634023325 × 10 -10	0.0	8.6926600 × 10 -11
	Q 13		-4.1785962 × 10 -13	0.0	0.0
	Q 14		-1.579365943	-4.2345814	0.3531041306
	Q 15		2.202282079 × 10 -3	0.0	-4.33144252 × 10 -4
	Q 16		-1.310550324 × 10 -7	0.0	0.0
	Q 17		-6.3813688333 × 10 -11	0.0	0.0
	Q 18		9.706578079	0.0	-0.09187145529
	Q 19		-0.02686039622	0.0	5.1904777 × 10 -4
	Q 20		1.534474401 × 10 -5	0.0	0.0
	Q 21		-3.215398267 × 10 -9	0.0	0.0

Table 3

 3 Influence of the capillary diameter on the total length of the device and on the salt distribution at the exhaust

	Diameter of the	Total length of the	Occurrence of the	Percentage of NaCl in	Percentage of NaCl in	Percentage of NaCl in
	capillary, d	capillary, L (m)	liquid phase, L sat (m)	the solid phase, %Sol	the vapour phase, %Vap	the liquid phase, %Liq
	(×10 -3 m)
	0.8	0.624	0.610	85.28	0.00	14.72
	1.6	21.515	21.486	96.58	0.00	3.42
	3.2	608.330	608.241	99.23	0.00	0.77
	6.4	16670.618	No occurence	100.00	0.00	0.00

Table 4

 4 Influence of the inlet temperature on the total length of the device and on the salt distribution at the exhaust

	Inlet temperature,	Total length of the	Occurrence of the	Percentage of NaCl in	Percentage of NaCl in	Percentage of NaCl in
	T in ( • C)	capillary, L (m)	liquid phase, L sat (m)	the solid phase, %Sol	the vapour phase, %Vap	the liquid phase, %Liq
	700	17.782	17.760	96.88	0.00	3.12
	650	19.434	19.409	96.76	0.00	3.24
	600	21.515	21.486	96.58	0.00	3.42
	550	24.278	24.245	96.29	0.00	3.71
	500	28.382	28.240	95.96	0.00	4.04
	400	35.164	35.092	95.24	0.00	4.76

Table 5

 5 Influence of the inlet mass flow rate on the total length of the device and on the salt distribution at the exhaust

	Inlet mass flow rate,	Total length of the	Occurrence of the	Percentage of NaCl in	Percentage of NaCl in	Percentage of NaCl in
	ṁin (kg h -1 )	capillary, L (m)	liquid phase, L sat (m)	the solid phase, %Sol	the vapour phase, %Vap	the liquid phase, %Liq
	30	10.123	10.095	94.83	0.00	5.17
	25	14.241	14.213	95.62	0.00	4.38
	20	21.515	21.486	96.58	0.00	3.42
	15	36.390	36.360	97.45	0.00	2.55
	10	75.656	75.624	98.70	0.00	1.30
	5	259.985	259.947	99.33	0.00	0.67

Table 6

 6 Influence of the heat transfer coefficient on the total length of the device and on the salt distribution at the exhaust

	Heat transfer	Total length of the	Occurrence of the	Percentage of NaCl in	Percentage of NaCl in	Percentage of NaCl in
	coefficient, H	capillary, L (m)	liquid phase, L sat (m)	the solid phase, %Sol	the vapour phase, %Vap	the liquid phase, %Liq
	(W m -2 K -1 )
	0	21.515	21.486	96.58	0.00	3.42
	5	21.183	21.152	96.63	0.00	3.37
	10	20.851	20.824	96.66	0.00	3.34
	15	20.537	20.501	96.74	0.00	3.26
	20	20.215	20.190	96.75	0.00	3.25
	25	19.916	19.895	96.82	0.00	3.18
	30	19.614	19.590	96.82	0.00	3.18

Acknowledgments

We wish to thank the French minister of economy and the European Union (Interreg IIIb, Atlantic area) for their financial support to this work in the Frame of the SUPERMAT network.


Nigel P Smart

Emmanuel Thomé

Joppe W Bos

Martijn Stam

History of Cryptographic Key Sizes

Introduction

Picking a cryptographic algorithm to use is often the simplest part in designing a system which uses cryptography. The difficult part comes in how one combines different algorithms together to meet some security objective and how the related parameters to the underlying cryptographic algorithms are selected. Probably the most important parameter is the key size, and one needs to select this for each algorithm separately, so that the combined system meets the desired security level.

Different algorithms have different metrics for measuring key strength; thus breaking a 128-bit key length for AES is not the same difficulty as breaking a 128-bit key length for RSA (the former is infeasible even with a quantum computer, whilst the latter is an undergraduate student project). To ease this issue Lenstra and Verheul published in 2000 an influential paper entitled Selecting Cryptographic Key Sizes [START_REF] Lenstra | Selecting Cryptographic Key Sizes[END_REF], with a longer version in [START_REF] Lenstra | Selecting Cryptographic Key Sizes[END_REF]. This was the first systematic attempt to measure the relative difficulty of different problems and provide some form of scientific guidance.

Determining key sizes is not an exact science, but it is an combination of four related factors:

1. A stable understanding of the best algorithm(s) to solve the computational problem. 2. Good asymptotic estimates of running time and storage requirements of such algorithm(s). 3. Some data points from large-scale computations, eg of cryptographic challenges. 4. The 'tightness' of any security proof which the cryptographic scheme relies upon.

In this chapter we will ignore the later point as in practice often security proofs are used to validate designs rather than used to set key sizes. Thus 'tightness' in security proofs, i.e. the gap between the difficulty of breaking the scheme versus the difficulty of breaking the underlying hard mathematical problem is often ignored in practice.

At the time of publication the default key size for many symmetric algorithms was 80 bits of security, although no standardized algorithm had this level of security or higher (AES did not become a standard until 2002), whereas RSA keys were suggested to be around 1024 bits in length, with ECC keys of 160 bits in length. Although in practice 512-bit RSA keys were widespread, despite a 512-bit RSA modulus being factored in the previous year [START_REF] Cavallar | Factorization of a 512-Bit RSA Modulus[END_REF]. Following Lenstra's paper a number of official and community recommendations followed. The most important of the official recommendations being those of NIST [72], ANSSI [START_REF] Anssi | Référentiel Général de Sécurité, Annexe B1 Mécanismes cryptographiques : Régles et recommandations concernant le choix et le dimensionnement des mécanismes cryptographiques[END_REF], and BSI [START_REF]Kryptographische Verfahren: Empfehlungen und Schlüssellängen[END_REF]. The most influential of the community led recommendations being the series of reports published by the ECRYPT projects in various years spanning from 2004 to 2018, with ENISA sponsoring the reports in 2013 and 2014 3 . The ECRYPT reports not only covered key size, but also other aspects of how a cryptographic primitive should be used, such as recommendations for modes of operation etc.

To derive recommendations for cryptographic key size one needs to take into account all the possible algorithms, and ways of implementing them, that can be used to recover keys. In doing so, one needs to also take into account that ones attacker might not be just some 'script kiddy' working in their bedroom, but could be a well funded nation state actor with access to large software and hardware resources.

Attacking Symmetric Algorithms with Software and Hardware

Attacking symmetric algorithms (block ciphers and hash functions) using hardware (and in some cases software) has a long history. Some of this work has been motivated by the desire to show that existing algorithms are insecure and need replacing (such as in the case of DES and MD5), some has been motivated to show just how inefficient such approaches will be (such as in the case of AES), whilst some has been to enable new applications (such as in the case of bitcoin mining of SHA-256).

Attacking DES

The most famous, and impactful, of the research in this area has been the long history of breaking the DES algorithm. Recall that DES is one of the oldest cryptographic primitives to be standardized for public use, and when proposed the key length was set to be 56 bits. Even at the time Martin Hellman and Whit Diffie estimated that DES would be insecure against a determined attacker, by estimating that one could build a parallel computer to evaluate one million DES operations per second at a cost of $20 million [START_REF] Diffie | Special Feature Exhaustive Cryptanalysis of the NBS Data Encryption Standard[END_REF]. Accounting for inflation this would amount to $86 million in todays money.

This idea was left, in the open community at least, as an intellectual curiosity for twenty years until in 1998 the Electronic Frontier Foundation (EFF) built the Deep Crack machine [START_REF] Gilmore | Cracking DES: Secrets of Encryption Research, Wiretap Politics and Chip Design[END_REF]. Deep Crack could find a single DES key in 22 hours, with a cost of building the machine of $200, 000. The reduction in cost, and the time needed to perform the attack, coming from the relentless march of improvements in computer hardware.

With the advent of FPGAs the design and build costs for such machines came within the range of University researchers. Fast forward another decade to 2006, and the CO-PACOBANA FPGA based cracker [START_REF] Kumar | Breaking Ciphers with COPACOBANA -A Cost-Optimized Parallel Code Breaker[END_REF] was built, which cost about $10, 000 and could break a single DES key in 6.4 days. At roughly the same time it was estimated [START_REF] Quisquater | Exhaustive key search of the DES: Updates and refinements[END_REF] that, after a pre-computation of a week on a $12, 000 device, one could break any DES keys in half an hour using just a $12 FPGA.

Whilst with special purpose hardware one has a high upfront cost and then the cost of attacking each key is minimal, and only really costs in terms of time, pure software attacks on DES keys are possible using standard computers. In [START_REF] Kleinjung | Using the Cloud to Determine Key Strengths[END_REF] Lenstra and his coauthors estimated that the dollar cost of finding a key in as short a time as possible on the Amazon EC2 cloud service was $14, 700 in 2012. This reduced to $4, 500 by 2018, purely due to the reduction in prices by Amazon for its cloud service. This hardness measure, in terms of dollar cost per key, is a more telling cost for weak algorithms such as DES. For a secure algorithm one expects the dollar cost per key to be so high, that it dwarfs the size of the world economy.

Attacking AES

The attacks mentioned above on the venerable DES cipher led NIST to look for a replacement. In 1997 a competition was announced to find a replacement, and in 2000 the winner, a cipher called Rijndael from Belgium, was selected. The Rijndael algorithm, was then selected as the Advanced Encryption Standard (AES). AES comes in three variants, each with block size 128-bits, the variants are a cipher with key size 128-bits, one with 192-bits and one with 256-bits. Whilst in theory the same approaches that were applied to DES can also be applied to AES, the effects are noticeably different. For example [START_REF] Kleinjung | Using the Cloud to Determine Key Strengths[END_REF] estimates that in 2018 it would cost around $10 19 million to break AES-128 using Amazon's EC2 cloud service.

Attacking Hash Functions

Not all breaking of mainstream symmetric algorithms has been done via raw computer power, some have been broken by advances in cryptanalysis, combined with raw computing power. A class example of this is the MD5 hash algorithm. This was proposed in 1991 by Ron Rivest and it saw widespread deployment in many applications. Soon after deployment (in 1996) Dobbertin found a collision in the compression function used within the algorithm, and cryptographers began recommending that MD5 not be used. However, this did not stop the widespread deployment of MD5 in the subsequent decades.

However in 2004 a collision for the full MD5 was announced by a group of cryptographers from China led by Wang, effectively breaking the hash function at the CRYPTO Rump Session (see [START_REF] Hawkes | Musings on the Wang et al. MD5 Collision[END_REF] for a contempory discussion and [START_REF] Wang | How to Break MD5 and Other Hash Functions[END_REF] for the paper). However, this was a random collision and thus was not a direct threat to computer systems. Soon after Lenstra and co-authors constructed two X.509 certificates with the same hash value [START_REF] Stevens | Chosen-Prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities[END_REF].

Rapid progress followed, using off-the-shelf computers one can now find collisions in specific situations in a matter of hours. That MD5 was broken led to other attacks on computer systems; for example the Flame malware from 2012 attacked Microsoft operating systems by exploiting problems with MD5.

When flaws in MD5 were discovered the recommendation was to switch to the SHA-1 algorithm. This was a very similar algorithm, but cryptographers thought it would provide longer term security compared to MD5. However, whilst stronger it was not that much stronger. A year after finding a collision in MD5, Wang's team gave another announcement at the CRYPTO Rump Session, this time giving a theoretical attack against SHA-1. Further improvements to this theoretical attack were announced over the coming decade. Then in 2015 using GPU time on Amazon's EC2 Cloud Service Stevens et al announced the first collision in SHA-1 requiring $2000 cost per new collision on EC2 4 . In 2020 Leurent and Peyrin announced the first practical chosen prefix collision on SHA-1. This method requires an expenditure of less than $100, 000 per collision, and builds upon the work in [START_REF] Leurent | From Collisions to Chosen-Prefix Collisions Application to Full SHA-1[END_REF].

The flaws in SHA-1 announced in 2005 led NIST to release a modified, more secure version, called SHA-2 (which comes in various output size, the most popular being SHA-256). In addition NIST announced a competition for a new hash algorithm, to be called SHA-3. The competition was started in 2006, and in 2012 was won by a Belgium team with their Keccak algorithm. Lenstra et al's estimates of the cost of breaking SHA-256 via running EC2 instances but the cost at $10 58 million dollars. Currently, no estimates exist for the cost of finding a collision in SHA-3.

SHA-256 is used in the Bitcoin system as the hard problem on which miners operate to authenticate a block. Each miner needs to evaluate two evalations of SHA-256 and then see if the resulting output has a special form before they can claim their reward. The profitability of this mining operation led to first FPGA and then ASIC mining hardware. The total Bitcoin system (as of 2020) is hashing at a rate of roughly 2 66 hashes per second. To find a collision in SHA-256 is expected to take 2 128 such hashes, thus even with the entire Bitcoin network we can only expect to find a hash in 2 36 years!

Software Attacks on Factoring and Discrete Logarithms

The integer factorization problem and the discrete logarithm problem in finite fields were the two hard problems underpinning the security of most of public-key cryptography in its first decades of existence. While a variety of primitives appeared since that rely on the assumed hardness of other mathematical problems, the prevalence of the primitives that rely on integer factorization and discrete logarithm, such as RSA and the Diffie-Hellman key exchange using multiplicative groups of finite fields, is clear.

One may encounter at times the argument that the hardness of factoring is a wellstudied problem because it has been actively studied for a long time (decades, centuries, or millenia for the most bodacious statements of this kind). In fact, the first important algorithmic improvements over naive methods date back to the early 1970s, with work by Shanks [START_REF] Shanks | Class number, a theory of factorization, and genera[END_REF], Pollard [START_REF] Pollard | Theorems on factorization and primality testing[END_REF], and Morrison and Brillhart [START_REF] Morrison | A method of factoring and the factorization of F 7[END_REF]. The motivations for these early endeavours towards smarter and smarter factoring methods were, for example, the factorization of discriminants of number fields, or the factorization of numbers of the form b n ± 1, which are potentially useful in a variety of settings ranging from combinatorics to group theory.

The advent of the RSA cryptosystem in the late 1970s, and its dependence on the hardness of factoring, led to a considerable surge in academic interest (and certainly non-academic interest as well). A good measure of the perceived (in)feasibility limit by 1978 is given in the RSA paper itself [START_REF] Rivest | A Method for Obtaining Digital Signatures and Public-Key Cryptosystems[END_REF]: factoring a 100-decimal digit integer was estimated to require about a century of computation time. We will see shortly that this key size withstood factoring attempts for hardly a decade. This provides two immediate lessons. First, in hindsight, four decades of algorithmic progress have evidently gone a long way. Second, estimating hardness is a tricky matter.

The Morrison-Brillhart CFRAC algorithm can be regarded as the ancestor of a series of algorithms that includes in particular the quadratic sieve and the number field sieve, both of which have numerous variants. For four decades, it has been a cryptographically important task to regularly provide good estimates of how hard factoring actually is in practice, using either commodity hardware or various kinds of more special-purpose equipment, ranging from academic supercomputers to specially designed hardware accelerators. Such estimates include the development of algorithmic ideas that are very effective in improving the computation time, often based on the constraints of the chosen computation platform.

Factoring by Email

The early 1980s saw several improvements of the state of the art of integer factorization. In their 1988 paper Factoring by electronic mail [START_REF] Lenstra | Factoring by Electronic Mail[END_REF], Lentra and Manasse adressed the variety of existing factoring records at the time, and provided a pragmatic answer to the question: how big are the integers we can factor within one month of elapsed time, if we only want to use computing time that we can get for free? This article was influential in the definition of the line of work of academic records for the following decades. It firmly installs, however, a distinction between academic records, done with this strategy, and what can be done by governements or possibly criminal organizations, who are ready to spend money to meet their goals.

Lenstra and Manasse used the MPQS algorithm, which is the multiple polynomial variant of the quadratic sieve. This algorithm is described in [START_REF] Silverman | The multiple polynomial quadratic sieve[END_REF]. In MPQS (and also in CFRAC, which MPQS superseded), one can separate the computation in two main steps. First, the relation collection step searches for multiplicative relations involving integers modulo N. In a later matrix step, these relations are combined to form an congruence of squares. Finding this combination is equivalent to finding an element in the nullspace of a sparse matrix over the binary field GF [START_REF] Adleman | The function field sieve[END_REF]. As a matter of fact, these two steps have also been the two main steps of all large factoring and discrete logarithm computations since.

The relation collection step in MPQS can be distributed massively. By 1988, standard hardware that was capable to contribute significantly to the relation collection towards the factorization of numbers of, say, 100 decimal digits, was relatively common in universities and research labs. Furthermore, the amount of output that was produced by each machine participating in the computation was relatively low. This made it possible to gather the results using any commodity means, and electronic mail was a perfect fit for that goal, usefully leveraging existing infrastructure.

The largest computation done with MPQS, following this approach of gathering contributions from hundreds of enthusiasts, was the factorization of RSA-129. This computation solves a challenge that was concocted by the RSA authors and presented in Martin Gardner's column in the August 1977 issue of Scientifc American. Atkins, Graff, Lenstra and Leyland factored the public modulus in 1994 and were able to unveil the secret RSA-encrypted message that was "The Magic Words are Squeamish Ossifrage" [START_REF] Atkins | The Magic Words are Squeamish Ossifrage[END_REF]. A striking fact about this computation is the number of contributors (more than 600) and the variety of machines used, ranging from 16MB 80386sx PCs to Cray C90s (the code was even ported to . . . fax machines).

The RSA-129 challenge was the most famous of a number of challenge factorization problems. The RSA company itself published a list of factorization challenges at various key lengths to encourage people to look into the security of cryptography based on factoring. This became known as the RSA Challenge list.

The development of the number field sieve

The RSA-129 paper concluded, quite naturally, with extrapolations on the hardness of reaching "most wanted" targets such as the factorization of 512-bit RSA moduli. Such keys were in widespread use at the time. With MPQS, it was estimated this this goal was almost feasible using massive power, but also qualified as "the last gasp of an elderly workhorse". The more recent Number Field Sieve, with better asymptotical behaviour, appeared probably more fit for that goal.

The Number Field Sieve originated in an astute way, designed by Pollard in 1988, to factor the seventh Fermat number 2 128 +1. Pollard used cubic integers. More mathematics were entering the scene. Pollard's method was understood by many as a curiosity. Its reliance an almost coincidental match between cubic integers and the special form of 2 128 + 1 raised doubts as to the possibility of extending the approach to other numbers.

Generalizations did come. By the end of 1989, Lenstra, Lenstra, Manasse and Pollard had extended Pollard's original approach to further numbers, and were able in 1990 to factor the 9-th Fermat number 2 512 + 1, which was a bit of a holy grail to factoring enthusiasts. Several challenges were still to overcome in order to factor general numbers. Not the least of which was the fact that the matrix step, it seemed, had to be solved with coefficient ring Z -it later appeared that solving over Z/2Z was enough. Several people contributed to loosening the constraints. The 1993 book The Development of the Number Field Sieve [START_REF]The development of the number field sieve[END_REF] includes further work by Bernstein, Buhler, Couveignes, Pomerance, leading to a General Number Field Sieve (GNFS) algorithm which was convincingly able to factor large numbers with good performance.

While early successes with GNFS were obtained while the algorithm was still being developed, the RSA-129 MPQS mark was improved in 1996, with the factorization of RSA-130 by GNFS. Because the Number Field Sieve had the peculiarity of being able to take advantage of the special form of integers to be factored in some cases, a good benchmark could no longer be the good old way of picking challenge numbers from the Cunningham tables, or otherwise defined numbers that had "some mathematical interest". This good benchmark was defined in 1991 by the RSA challenge list, formed of good RSA moduli, with two secretly chosen prime factors of similar size.

Following RSA-130, several records followed, most often picked from the RSA challenge list. All were factored with GNFS. This provided a nice view of the progress of computational power on the one hand, and also progress on implementation and algorithmic refinements. The landmark factorization of a 512-bit RSA modulus was reached in 1999, the culmination of a significant effort from many contributors, coordinated by CWI in Amsterdam. As of today the list of factored RSA-challenge numbers is given in Table 1

Discrete Logarithms in Finite Fields

The development of algorithms to solve discrete logarithms in large prime characteristic finite fields F p follows roughly the same development of the case of factoring 6 . The basic algorithm is to perform a sieving stage, followed by a large matrix step. The key difference is in the matrix step. For factoring the matrix equation one is trying to solve is modulo 2, whereas for discrete logarithms it is modulo q, where q is the large prime factor of p -1.

The methods to collect relations are also almost identical. Indeed in 2000 Schirokauer [START_REF] Schirokauer | Using number fields to compute logarithms in finite fields[END_REF] showed how to use the Number Field Sieve to solve discrete logarithms in the field F p , and that is now the method of choice. Just as with factoring there is the basic Number Field Sieve, and a more efficient variant called the Special Number Field Sieve which can utilize special properties of the representation of the number p if they exist.

At the time of writing (Autumn 2019) a record for discrete logarithms has just been announced for a general 240-decimal digit, 795-bit prime field [START_REF] Boudot | Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment[END_REF]. The record for primes of special form are slightly larger, with a discrete logarithm computation in 2016 for a a 308-decimal digit, or 1024-bit, prime [START_REF] Fried | A Kilobit Hidden SNFS Discrete Logarithm Computation[END_REF]. Note that discrete logarithms are slightly harder than factoring, judging by the publication time of records for general 768-bit factoring or prime discrete logarithms (2009 and 2016, respectively) or the of records for special 1024-bit factoring or prime discrete logarithms (2007 [START_REF] Aoki | A Kilobit Special Number Field Sieve Factorization[END_REF] and 2016). However, the largest known records were done at the same time, and indicate that the difference gap between the two problems is not as large as usually considered [START_REF] Boudot | Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment[END_REF].

Hardware for Factoring

At the heart of modern factoring algorithms, and to some extent almost all algorithms for solving discrete logarithms, is the so-called sieving step. This sieving step is essentially trying to solve a more complex version of the classical problem of finding simulataneous solutions to modular diophantine equations x = a i (mod m i ) for i = 1, . . . , t.

Classically 'machines' to solve this problem date back to as far back as 1896, when Lawrence presented a mechanical design for such a machine. In 1912 the first actual design was implemented by four French mathematicians Gérardi, Kraitchik, and Pierre and Eugène Carissan. The most famous of the mechanical devices where those built by the Lehmers in the 1930's some of which can now be found in the Computer History Museum in Silicon Valley. For a discussion of the history of such early machines see [START_REF] Shallit | Discovery of a lost factoring machine[END_REF] and [START_REF] Lehmer | The mechanical combination of linear forms[END_REF][START_REF] Lehmer | Hunting big game in the theory of numbers[END_REF][START_REF] Lehmer | A photo-electric number sieve[END_REF].

The advent of modern factoring algorithms led to a renewed interest in such 'sieving machines'. In the early 1980s a special purpose computer was designed to implement the CFRAC factoring algorithm by Smith and Wagstaff [START_REF] Pomerance | New Ideas for Factoring Large Integers[END_REF], called the 'Georgia Cracker'. This was accompanied by another design by Rudd, Buell and Chiarull who designed a machine in 1984 which could factor numbers ten times faster than existing general purpose computers [START_REF] Rudd | A High Performance Factoring Machine[END_REF].

In the early 2000's there was renewed interest in special purpose hardware for the sieving step. This was initiated by a EuroCrypt 1999 Rump Session talk in which Adi Shamir introduced his idea for the TWINKLE machine. In classical sieving we sieve a region by assigning each region some space in a computer memory, then we use time to go through all the primes in the factorbase so as to encode the contribution of each prime to each location in the space. TWINKLE switches this around, and uses light based computation (much like one of Lehmer's devices [START_REF] Lehmer | A photo-electric number sieve[END_REF]). The idea now is that space is used up by lights which flash according to a timing signal dependent on the prime, thus each light corresponds to a prime; whilst we use time to represent the sieving region. At a time signal corresponding to when more lights flash we have an element in the sieving region which needs to be investigated further. The initial TWINKLE design was presented in [START_REF] Shamir | Factoring Large Numbers with the Twinkle Device (Extended Abstract)[END_REF] and then analysed in [START_REF] Lenstra | Analysis and Optimization of the TWINKLE Factoring Device[END_REF] by Lenstra and Shamir. It was deemed too costly to build in order to factor numbers of interest.

TWINKLE was soon followed up in 2003 by another idea of Shamir and Tromer called TWIRL [START_REF] Shamir | Factoring Large Number with the TWIRL Device[END_REF]. This dispensed with the optical computing methodology, but kept the time/space reversal, of TWINKLE. The design was based on novel routing networks to represent the sieving operation. The design was never built, but was considered feasible for factoring 1024-bit integers in a paper by Lenstra and co-authors [START_REF] Lenstra | Factoring Estimates for a 1024-Bit RSA Modulus[END_REF]; one estimate gives a cost of $1.1 million dollars to factor a 1024-bit integer in one year. A related design, based on idea of Bernstein (see below), was presented by Geiselmann and Steinwandt in [START_REF] Geiselmann | A Dedicated Sieving Hardware[END_REF][START_REF] Geiselmann | Yet Another Sieving Device[END_REF]. It too was considered practical for 1024-bit moduli, but slightly more expensive to build than TWIRL.

Related to TWIRL is a design from 2005 by Franke and others called SHARK [START_REF] Franke | SHARK: A Realizable Special Hardware Sieving Device for Factoring 1024-Bit Integers[END_REF]. This used a different form of routing network, but could utilize more off-the-shelf components. The authors estimated that one could factor 1024-bit numbers in a year at a cost of $200 million dollars. This is higher than TWIRL, but was considered easier to build with current technology; thus the design risk was less.

It is not only the sieving step which has been the subject of hardware design proposals. Modern factoring also involves a large matrix step. In 2001 Bernstein presented a proposal for the matrix step, which in fact influenced the methods of Geiselmann and Steinwandt mentioned above. Bernstein's idea was to reduce the amount of idle storage in the standard matrix algorithm by using a form of mesh sorting. The design was analysed, again by Lenstra and co-authors, in [START_REF] Lenstra | Analysis of Bernstein's Factorization Circuit[END_REF], where they concluded that the method was not cost-effective in factoring 1024-bit integers.

Special purpose, but commodity hardware, has also been used to factor integers. The Graphical Processing Units (GPUs) in modern gaming consoles provide a cheap form of computing. Often the hardware is sold at a discount as the manufacturer aims to get their investment back in sales of games. Combined with the amazing parallel processing capability of modern GPUs, games consoles form an attractive way of obtaining supercomputer performance at a fraction of the price. In 2011 it was shown how to utilize such hardware to factor integers, using a variant of the Elliptic Curve Factoring Method (ECM) [START_REF] Bos | Efficient SIMD Arithmetic Modulo a Mersenne Number[END_REF][START_REF] Bos | ECM at Work[END_REF].

Attacking Cryptosystems Based on Elliptic Curves

For an elliptic curve E(F q ) over the finite field F q to be used in cryptography, one usually selects a curve which has a subgroup of prime order p, with p ≈ q. By Hasse's Theorem we cannot have p q, and for efficiency we want to keep q as small as possible, but the complexity of the best algorithm for attacking an elliptic curve has complexity O( √ p).

Thus to obtain 80-bit security, one selects a 160-bit curve, to obtain 128-bit security one selects a 256-bit curve and so on.

Inspired by the RSA Challenges, Certicom (a Canadian company which specialised in ECC based cryptography) in 1997 launched the Certicom ECC Challenge. This comprised a set of toy challenges (for 79-bit, 89-bit and 97-bit curves), Level I challenges (for 109-bit and 131-bit), plus Level II challenges (for 163-bit, 191-bit, 239-bit and 359bit). The challenges were also sub-divided into those over finite fields of characteristic two and those over large prime fields.

By the end of 1999 all of the toy challenges had been solved in both categories of fields. These attacks were performed via the method of van Oorschot and Wiener [START_REF] Van Oorschot | Parallel Collision Search with Cryptanalytic Applications[END_REF], which are themselves extensions of the ideas of Pollard [START_REF] Pollard | Monte Carlo algorithms for index computation (mod p)[END_REF][START_REF] Pollard | Kangaroos, Monopoly and Discrete Logarithms[END_REF]. Clients were distributed across the internet on peoples idle machines, with communication back to the central control point being performed either by e-mail or via socket connections. The 109-bit challenges were then all solved by 2004. Some teams have attempted to solve the 131-bit challenge, but so far no reports of success are available.

The application of gaming consoles mentioned earlier has also been applied to attacking elliptic curve based systems. For example [START_REF] Bos | Solving a 112-bit prime elliptic curve discrete logarithm problem on game consoles using sloppy reduction[END_REF] discusses breaking a 112-bit elliptic curve instance using gaming consoles.

In [START_REF] Kleinjung | Using the Cloud to Determine Key Strengths[END_REF] Lenstra and his co-authors consider the cost of breaking ECC keys using Amazon EC2 instances alone. Their estimates give that determining a 256-bit ECC key will require one to spend $10 20 million on EC2. With the estimated costs for the Level II Certicom challenges being $10 6 , $10 11 , $10 18 , $10 36 million respectively. Current key sizes are recommended to be 256-bits for ECC, to correspond to the 128-bit security of AES-128, or 512-bits, to correspond to the 256-bit security of AES-256. Thus, baring the advent of a quantum computer, current recommended key sizes for ECC can be considered secure.

However, one needs to avoid 'special curves' which have attacks which perform better than O( √ p). One such class of curves are those defined over finite fields with q = n . An example of such attacks is the Weil descent attack when q = 2 n and n is composite, as explained in [START_REF] Gaudry | Constructive and Destructive Facets of Weil Descent on Elliptic Curves[END_REF], the so-called GHS-attack. This attack exploits special properties of elliptic curves over such fields for composite n. The attack works much like factoring methods; in the first stage one collects relations and then in the second one uses linear algebra to find specific discrete logarithms. Thus whilst this attack has no effect on key sizes it does have an effect on the choice of specific key types.

In recent years the method of Weil descent has been extended to elliptic curves over general fields of the form F n . This study was initiated by Semaev [START_REF] Semaev | Summation polynomials and the discrete logarithm problem on elliptic curves[END_REF], who introduced the Semaev summation polynomials into the Weil restriction methodology. This idea was then developed by Gaudry [START_REF] Gaudry | Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem[END_REF] and Diem [START_REF] Diem | On the discrete logarithm problem in elliptic curves[END_REF]. A nice succinct statement of these results is that if is a prime power and n is such that

a • log( ) ≤ n ≤ b • log( )
for some fixed positive real numbers a < b then asymptotically one can solve the discrete logarithm problem on an elliptic curve E(F n ) in time e O(log( n ) 2/3 ) . Another class of weak curves are the so-called anomalous curves, which are the curves for which p = q. These were shown to be very weak in three papers which appeared at roughly the same time [START_REF] Satoh | Fermat quotients and the polynomial time discrete log algorithm for anomalouselliptic curves[END_REF][START_REF] Semaev | Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curve in characteristic p[END_REF][START_REF] Smart | The Discrete Logarithm Problem on Elliptic Curves of Trace One[END_REF].

Pairing Based Cryptography

The most interesting class of curves for which there is a possible weakness are those which possess a pairing to a finite field. In particular there are classes of elliptic curves E(F q ) for which there are numbers k ≤ n for which there is an efficiently computable map t :

E(F q ) × E(F q k ) -→ F q n .
In fact such pairs (k, n) exist for all elliptic curves, but curves for which (k, n) are small are very rare indeed.

In the early days of ECC it was common to select curves, for efficiency reasons, which had k = 1 and n ≤ 6. However, this means one can map the discrete logarithm problem in E(F q ) into the discrete logarithm problem in F q n [START_REF] Menezes | Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field[END_REF]. Suppose E(F q ) is chosen to have 80-bit symmetric security, i.e. 160-bit ECC security, then this means the finite field F q n is of size less than 960. In the early 1990's this killed off such curves in the case when n 6.

When n = 6 one seemed to have a nice balance in the security, as in those days 1000 bit finite field discrete logarithms were considered as secure as 160-bit elliptic curve discrete logarithms. This 'magic' property of the number six, i.e. 6 • 160 ≈ 1000, was utilized by Lenstra and Verheul to construct the XTR cryptosystem in [START_REF] Lenstra | The XTR Public Key System[END_REF] in 2000.

However, the move to 128-bit symmetric security, and the equivalent 256-bit elliptic curve security and the supposed equivalence of 3072 bit finite field discrete logarithm security, led to the number six loosing its magic properties and being replaced by the magic number 12, since 12 • 256 = 3072. We shall return to the number 12 below. Thus the existence of such pairings seemed to imply that such curves should be avoided at all costs in cryptographic applications.

However, the interest in pairings on elliptic curves was ignited when Joux [START_REF] Joux | A One Round Protocol for Tripartite Diffie-Hellman[END_REF] found a constructive application of such mappings. This was quickly followed by other applications, such as Identity Based Encryption [START_REF] Boneh | Identity-Based Encryption from the Weil Pairing[END_REF][START_REF] Sakai | Cryptosystems based on Pairing[END_REF]. Soon a whole zoo of applications of pairings was created. But such a zoo needed secure curves to work on.

The main security requirement of pairing based systems is that the curve E(F q ) needs a large subgroup of prime order p with log 2 p being twice the desired symmetric security level, so p = 2 256 say. We also would like q to be small to enable good efficiency. But we need a pairing to exist for which n is such that the finite field F q n gives hard discrete logarithms.

There turned out to be three popular choices.

1. Pick q n = m , for = 2 or = 3. The advantage here is one obtains very good implementation efficiency. The problem is the discrete logarithm in low characteristic fields turned out to be not as hard as originally thought (see below).

2. Pick p ≈ q and select n to make the discrete logarithm hard. Thus we return to picking n to be (say) the magic number 12. Such curves are usually called "pairingfriendly". A typical choice here was the so-called Barreto-Naehrig curves [START_REF] Barreto | Pairing-Friendly Elliptic Curves of Prime Order[END_REF], called BN curves. The problem here is that such curves are subject to a potential 'medium prime' attack (again see below). 3. Pick n = 2, and make q huge, e.g. q ≈ 2 1500 but keep p of size 2 256 (say). Here one loses efficiency, but we are pretty certain of security.

We now discuss these last three cases in turn:

When q n = m for small : Algorithms to solve discrete logarithms in small characteristic field have had a very interesting history. In the case of = 2, the first algorithms can be dated back to 1982 [START_REF] Hellman | Fast Computation of Discrete Logarithms in GF(q)[END_REF]. But the real advance came in 1984 when Coppersmith [START_REF] Coppersmith | Fast evaluation of logarithms in fields of characteristic two[END_REF], building upon earlier ideas of Blake et al [START_REF] Blake | Computing Logarithms in GF(2 n )[END_REF], gave an algorithm with heuristic complexity L q n (1/3, c + o( 1)). This was the first algorithm to have such a complexity, and this was a decade before the NFS algorithm was known for the factoring problem with a similar complexity. The idea behind Coppersmith's algorithm was shown, after the invention of the Number Field Sieve, to be closely related to another algorithm called the Function Field Sieve which was invented by Adleman in 1994 [START_REF] Adleman | The function field sieve[END_REF]. This algorithm was improved slightly by Joux and Lercier in 2002 [START_REF] Joux | The Function Field Sieve Is Quite Special[END_REF], but there seemed to be little further improvements that could be made.

Then in 2013 a series of papers and email announcements started coming out. In looking at fields of the form q = 2 m , an announcement by Joux in Febrary of 2013 gave a L q n (1/4, c + o(1)) complexity algorithm and a new record of m = 1778, which was way above existing records [START_REF] Joux | A New Index Calculus Algorithm with Complexity L(1/4 + o(1)) in Small Characteristic[END_REF]. Then in the same month Granger et al solved discrete logarithms in a field with m = 1971, using a variant of the Function Field Sieve [START_REF] Göloglu | On the Function Field Sieve and the Impact of Higher Splitting Probabilities -Application to Discrete Logarithms in F 2 1971 and F 2 3164[END_REF]. In March Joux responded with another record of m = 4080, with Granger et al responding with m = 6120 in April. The back-and-forth continued, with Joux posting a record of m = 6168 in May. In June 2013 Barbulescu et al presented a quasi-polynomial time algorithm for fields of the form q n = 2 m [START_REF] Barbulescu | A Heuristic Quasi-Polynomial Algorithm for Discrete Logarithm in Finite Fields of Small Characteristic[END_REF]. Finally in January 2014 Granger et al posted the solution to a problem with m = 9234. Thus in one year the entire area of pairing based cryptography over finite fields of characteristic two had been destroyed. The current record is a huge value of m = 30750 set by Granger et al in 2019 [START_REF] Granger | On the discrete logarithm problem in finite fields of fixed characteristic[END_REF].

The case of characteristic three finite fields, which held a lot of promise for pairing based cryptography, faired not much better. In the period from 2010 to 2016 the record advanced from a 676-bit field, up to 4841 [START_REF] Adj | Computing discrete logarithms in cryptographically-interesting characteristic-three finite fields[END_REF].

Medium Prime Finite Field Discrete Logarithms The 'medium prime' case of the finite field discrete logarithm problem is for the case q n = m , where is not small and m is not one. It was not really until the advent of pairing based cryptography and XTR in the early 2000's that this problem became of interest to cryptographers. The first major work on this case of the problem was by Granger and Vercauteren [START_REF] Granger | On the Discrete Logarithm Problem on Algebraic Tori[END_REF], and Joux and Lercier [START_REF] Joux | The Function Field Sieve in the Medium Prime Case[END_REF], which showed that a variant of the Function Field Sieve could be applied in this case to obtain a complexity of L q n (1/3, c + o(1)). In [START_REF] Joux | The Number Field Sieve in the Medium Prime Case[END_REF] the analysis was then carried out for the Number Field Sieve algorithm as well. This enabled a L q n (1/3, c + o(1)) algorithm to be applied in all finite fields; with the precise algorithm to be used depending on the sizes of and m.

In 2015 Barbulescu et al [START_REF] Barbulescu | The Tower Number Field Sieve[END_REF] initiated the renewed study of an earlier algorithm of Schirokauer called the Tower Number Field Sieve (TNFS), which had appeared in [START_REF] Schirokauer | Using number fields to compute logarithms in finite fields[END_REF]. There followed a rapid sequence of papers looking again at the TNFS as a means to attack the third type of pairing parameters mentioned above, e.g. [START_REF] Barbulescu | Improving NFS for the Discrete Logarithm Problem in Non-prime Finite Fields[END_REF][START_REF] Kim | Extended Tower Number Field Sieve: A New Complexity for the Medium Prime Case[END_REF][START_REF] Kim | Extended Tower Number Field Sieve with Application to Finite Fields of Arbitrary Composite Extension Degree[END_REF][START_REF] Sarkar | A General Polynomial Selection Method and New Asymptotic Complexities for the Tower Number Field Sieve Algorithm[END_REF].

No efficient implementation of the TNFS algorithm exists as of 2019. Yet, hardness estimates can be done using rough extrapolations. This was done for example by Barbulescu and Duquesne in [START_REF] Barbulescu | Updating Key Size Estimations for Pairings[END_REF] or Guillevic in [START_REF] Guillevic | A Short-List of Pairing-Friendly Curves Resistant to Special TNFS at the 128-Bit Security Level[END_REF], who provided comprehensive analyses of key sizes for such pairing based systems. In particular their recommendation is that for 128-bits of symmetric security a BN curve needs to be selected with at least q ≈ 2 446 , which makes the implementation advantages of BN curves disappear, since q is no longer of the order of 2 256 . Thus curves would need to be selected, to obtain the same balance between security and performance, with a higher embedding degree n. This is a particular problem as such BN curves have recently been standardized for use in systems such a the Trusted Computing Module.

When n = 2: In this case the theoretical algorithm of choice is that of Joux et al [START_REF] Joux | The Number Field Sieve in the Medium Prime Case[END_REF]. Using an adaption of this method, Barbulescu in 2014 announced a discrete logarithm record in a finite field of the form F q 2 , for a prime q of 264-bits, where the interesting subgroup had order p ≈ 2 261 . To date this is the largest problem solved, and hence it appears that picking q of approximately 512 to 1500 bits should result still result in a secure pairing system. At the 128-bit security level their estimates correspond to using an embedding degree of n = 16 or n = 18, whereas at the 256-bit security level an embedding degree of m = 24 is to be preferred, and even that is not optimal.

Post Quantum Cryptography

The problem with the above analysis of the difficulty of the factoring and discrete logarithm problems, is that it becomes totally redundant if a quantum computer is ever built. In 1994 Shor [START_REF] Shor | Algorithms for Quantum Computation: Discrete Logarithms and Factoring[END_REF] came up with a polynomial time algorithm for both the factoring problem, and the discrete logarithm problem in any finite abelian group. The only problem with Shor's algorithm is that one requires a quantum computer to run it.

A quantum computer uses quantum bits (so called qubits) as opposed to classical bits. Currently very small numbers of quantum bits can be processed for a short period of time without falling prey to noise. Thus, the issue is whether one can build a quantum computer, with enough qubits, which can run noise-free for long enough to factor an interesting number, or break an interesting discrete logarithm.

The current quantum factoring records are much less than that which can be done with classical computers. In 2001 a team from IBM factored the number 15 (into 3 × 5 surprisingly enough) using a quantum computer with seven qubits [START_REF] Vandersypen | Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance[END_REF]. At the time of writing (Autumn 2019) the current record is to factor 4088459 = 2017 × 2027, which was done on a 5 qubit processor [START_REF] Dash | Exact search algorithm to factorize large biprimes and a triprime on IBM quantum computer[END_REF]. However, despite these numbers being small the threat of a quantum computer means that people have turned to examining so called post-quantum systems.

These post-quantum public key cryptographic systems are necessarily based on different hard problems (lattice based problems, coding theory based problems, problems in isogeny theory and so on). However, these problems need to go through the same analysis of difficulty to determine key sizes as has previously happened for the prequantum algorithms. At the time of writing NIST is running a 'competition' to determine what type of post-quantum will be most suitable in the coming decades.

Lattice Based PQC: One of the most promising areas of post-quantum cryptography is those systems based on lattices. The most basic lattice problem is the shortest-vector problem, which is the problem of determining the smallest non-zero vector in the set

{ x = A • k : k ∈ Z n }
when A is a random square integer matrix of dimension n. The most famous classical algorithm to solve this problem is the LLL algorithm [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF], and its modern improvements such as the BKZ algorithm, which was introduced in [START_REF] Schnorr | A Hierarchy of Polynomial Time Lattice Basis Reduction Algorithms[END_REF] and then improved in other works such as [START_REF] Chen | BKZ 2.0: Better Lattice Security Estimates[END_REF]. However, none of the classical algorithms to solve this problem can be significantly improved using a quantum computer. Thus, the closest vector problem seems a very good candidate to use to build post-quantum cryptographic systems.

Just like with factoring and elliptic curve based systems before them, lattice based cryptanalysis has been spurred on by a series of challenge problems. The most famous of these are the Darmstadt Lattice Challenge https://www.latticechallenge.org/. This presents a number of challenges for different dimensions n, and for different variants of lattice problems.

The most important variant of the challenges is that given by the Learning-With-Errors (LWE) problem. This is the problem to recover the vector s ∈ Z n given only a random matrix A and the vector b which satisfies b = A • s + e (mod q) for some vector e of small euclidean norm. The LWE problem is related to the classical closest vector problem in lattices, but it can be used to more easily construct cryptographic systems.

The problem with lattices problems, and LWE problems in particular, is that the potential attack algorithms have many different parameters which can be tweaked, and many different sub-procedures may have (small) potential quantum speed-ups. Thus determining a precise 'key size' estimate is hard. To help this with the LWE problem there is software which performs this calculation for one called the lwe-estimator: https://bitbucket.org/malb/lwe-estimator/src/master/.

Coding Based PQC: Basing public key cryptography on the difficult problem of decoding random linear codes is a long standing construction. The earliest designs go back to McEliece [START_REF] Mceliece | A Public-Key Cryptosystem Based On Algebraic Coding Theory[END_REF] in 1978. What is quite remarkable about code based cryptography is that the state-of-the-art in terms of cryptanalysis has remained relatively constant over the last forty years. This is in part due to the problem of decoding random linear codes being known to be an NP-hard.

Again to spur the community into studying these problems, especially due to the NIST 'competition', a set of challenge problems have been created http://decodingchallenge. org/. The problems, much like the Darmstadt Lattice Challenge problems are divided into generic decoding problems, and problems related more closely to proposed cryptographic systems.

MQ Based PQC: It is well known that the SAT problem is NP-Complete, thus it is clearly an attractive proposition to try to base cryptographic schemes on problems related to SAT. One such attempt is to use so-called MQ based problems. In these problems one is given a large set of multi-variate quadratic equations over a finite field (usually one of characteristic two) and one is asked to find a solution. The first such important proposal in this space was by Matsumoto and Imai in 1988 [START_REF] Matsumoto | Public Quadratic Polynominal-Tuples for Efficient Signature-Verification and Message-Encryption[END_REF], who presented a proposal for public key signatures and public key encryption. This was, however, broken in 1995 by Patarin [START_REF] Patarin | Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt[END_REF].

The basic idea remains attractive. Whilst almost all work on public key encryption based on MQ systems has not led to a good system, the situation for public key signatures is very different. Patarin and his co-authors introduced the 'Balance Oil and Vinegar' signature scheme in 1997 [START_REF] Patarin | The Oil and Vinegar Algorithm for Signatures[END_REF] and then the 'Unbalanced Oil and Vinegar' scheme in 1999 [START_REF] Kipnis | Unbalanced Oil and Vinegar Signature Schemes[END_REF]. These ideas have kept being worked on, and a number of submissions to the NIST 'competition' are based on the Oil and Vinegar construction.

Again to help research in cryptanalysis of MQ based cryptography a web site with a set of challenges has been set up https://www.mqchallenge.org/.

Symmetric Key Based PQC: Another way to construct post-quantum signatures is to dispense with complex constructions based on hard mathematical problems, and simply base public key cryptography upon symmetric key cryptography. This is because quantum computers are not expected to pose much of a threat to standard symmetric key cryptography. Two of the main post-quantum signature schemes to precisely this.

The first construction based on hash-functions goes back to an old idea from 1979, namely the one-time signature scheme of Lamport [START_REF] Lamport | Constructing Digital Signatures from a One-way Function[END_REF]. This when combined with Merkle-trees can be used to form a statefull many-time signature scheme, [START_REF] Merkle | A Certified Digital Signature[END_REF]. To remove the statefull nature of the signature scheme, an algorithm called SPHINCS was proposed in 2015 [START_REF] Bernstein | SPHINCS: Practical Stateless Hash-Based Signatures[END_REF].

The second construction makes use of the difficulty of inverting one-way functions, and is based on a technique from theoretical cryptography called MPC-in-the-Head [START_REF] Ishai | Zeroknowledge from secure multiparty computation[END_REF]. This methodology was extended in a series of works [START_REF] Giacomelli | ZKBoo: Faster Zero-Knowledge for Boolean Circuits[END_REF][START_REF] Albrecht | Ciphers for MPC and FHE[END_REF]. When instantiated with low-complexity block ciphers such signature schemes are rather efficient.

Key Size Recommendation

The asymptotic complexity of GNFS to factor an integer N is of the following form, as N → ∞: L(N) 1+o (1) , with L(N) = exp (64/9) 1/3 (log N) 1/3 (log log N) 2/3 . Back almost 30 years ago, the complexity of MPQS was written with a similar shaped equation, with a larger exponent 1/2 instead of 1/3 in the exponent. But the (1 + o(1)) part was present there too. In that MPQS context, the RSA-129 paper contained the following cautious words, to guard against the temptation to ignore the o(1) and use simply the analogue of L(N) as an operation count: since o(1) is neither 0 nor constant, this practice hardly makes sense. Even knowing the computation time from one number N 1 gives only shallow ground for an extrapolation to another size N 2 based on the ratio L(N 2 )/L(N 1 ): this cannot account for the growth of what is hidden by o( 1). Yet, with due care, extrapolations based on such ratios were proposed over the years, based on known GNFS records, in order to answer the much-needed question: what key size will match the appropriate security level by year X ? Table 2 is given in [START_REF]Algorithms, Key Size and Protocols Report[END_REF] as a summary of recommendations from various sources. It summarizes the key size recommendations for the 'standard' algorithms currently in use, i.e. it ignores the current zoo of post-quantum algorithm proposals. The column 'Legacy' refers to key sizes which are currently in use and which should be retired as soon as possible (but not urgently); whereas near term refers to a time period until 2026 (ten years ahead for a report published in 2016), whereas long term refers to projecting security beyond that horizon. Another way of measuring security was also introduced by Lenstra and co-authors in [START_REF] Lenstra | Universal Security -From Bits and Mips to Pools, Lakes -and Beyond[END_REF]. In this paper the authors suggest measuring the energy required to break a cryptosystem. This idea stemmed from a remark made about the factorization of the RSA-768 challenge, in that the authors estimated that it used as much energy as would have sufficed to bring two Olympic size swimming pools to the boil from a starting temperature of 20 degrees Celsius.

The traditional 80-bit security level is equivalent to boiling the average daily rain fall of the Netherlands (which is apparently according to [START_REF] Lenstra | Universal Security -From Bits and Mips to Pools, Lakes -and Beyond[END_REF] the healthy equivalent to 2 15 swimming pools per day). To obtain 128-bit security one needs to expend the energy to boil off all the water on the planet. Thus with this metric one can rest assured that ciphers that require 2 128 operations to break them will remain secure for a very long time indeed.

Table 1 .

 1 5 . Apr 10, 1996 A. K.Lenstra et al. RSA-140 140 463 Feb 2, 1999 H. te Riele et al. RSA-150 150 496 Apr 16, 2004 K. Aoki et al. RSA-155 155 512 Aug 22, 1999 H. te Riele et al. RSA-160 160 530 Apr 1, 2003 J. Franke et al. RSA-170 170 563 Dec 29, 2009 D. Bonenberger and M. Krone RSA-576 174 576 Dec 3, 2003 J. Franke et al. RSA-180 180 596 May 8, 2010 S. A. Danilov and I. A. Popovyan RSA-190 190 629 Nov 8, 2010 A. Timofeev and I. A. Popovyan RSA-640 193 640 Nov 2, 2005 J. Franke et al. RSA-200 200 663 May 9, 2005 J. Franke et al. The solved RSA Challenges

	Challenge Name	Digits Bits Date Factored Factored by
	RSA-100 100 330 Apr 1, 1991 A. K. Lenstra
	RSA-110 110 364 Apr 14, 1992 A. K. Lenstra and M.S. Manasse
	RSA-120 120 397 Jul 9, 1993	T. Denny et al.
	RSA-130 130 430 RSA-210 210 696 Sep 26, 2013 R. Propper
	RSA-704 212 704 Jul 2, 2012	S. Bai, E. Thomé and
			P. Zimmermann
	RSA-220 220 729 May 13, 2016 S. Bai, P. Gaudry, A. Kruppa,
			E. Thomé and P. Zimmermann
	RSA-230 230 762 Aug 15, 2018 S. S. Gross
	RSA-768 232 768 Dec 12, 2009 T. Kleinjung et al.
	RSA-240 240 795 Nov 24, 2019 F. Boudot, P. Gaudry, A. Guille-
			vic, N. Heninger, E. Thomé and
			P. Zimmermann
	RSA-250 250 829 Feb 28, 2020 F. Boudot, P. Gaudry, A. Guille-
			vic, N. Heninger, E. Thomé and
			P. Zimmermann

Table 2 .

 2 Key Size Analysis, where (•) refers to the bit-length of the parameter.

				Future System Use
		Parameter Legacy Near Term Long Term
	Symmetric Key Size	k	80	128	256
	Hash Function Output Size	m	160	256	512
	MAC Output Size	m	80	128	256
	RSA Problem	(n) ≥	1024	3072	15360
	Finite Field DLP	(p n ) ≥	1024	3072	15360
		(p), (q) ≥ 160	256	512
	ECDLP	(q) ≥	160	256	512
	Pairing	(q n ) ≥	1024	3072	15360
		(p), (q) ≥ 160	256	512

The various ECRYPT reports can be found at https://www.ecrypt.eu.org/.

https://sites.google.com/site/itstheshappening/

Source https://en.wikipedia.org/wiki/RSA_Factoring_Challenge.

We leave the case of non-prime fields to later