Publications HAL

2022

Article dans une revue

titre
An Alternative Approach to Polynomial Modular Number System Internal Reduction
auteur
Nicolas Méloni
article
IEEE Transactions on Emerging Topics in Computing, 2022, ⟨10.1109/TETC.2022.3190368⟩
resume
The Polynomial Modular Number System (PMNS) is an alternative to the binary multi-precision representation that allows to transport the arithmetic of a finite field to a polynomial ring. The most important operation in that system is the internal reduction that follows any arithmetic operation. All recent works on the subject use the same algorithm derived from Montgomery's modular multiplications to perform this internal reduction. This paper designs and analyzes two new algorithms to perform the internal reduction, both based on Babai's Closest Vector algorithms. It allows to significantly reduce the number of additions needed to perform this operation. A comprehensive experimental analysis shows that one of those algorithms is also faster in practice. For that matter, a C code generation tool has been developed in order to produce implementations for any prime number field.
typdoc
Article dans une revue
DOI
DOI : 10.1109/TETC.2022.3190368
Accès au texte intégral et bibtex

2021

Communication dans un congrès

titre
Compact variable-base ECC scalar multiplication using Euclidean addition chains
auteur
Fabien Herbaut, Nicolas Méloni, Pascal Véron
article
18th International Conference on Security and Cryptography (SECRYPT 2021), Jul 2021, Online Event, Italy. pp.531-539, ⟨10.5220/0010551705310539⟩
resume
The random generation of Euclidean addition chains fits well with a GLV context (Dosso et al., 2018) and provides a method with decent performance despite the growth of the base field required to get the same level of security. The aim of this paper is to reduce the size of the base field required. Combined with an algorithmic improvement, we obtain a reduction of 21% of the memory usage. Hence, our method appears to be one of the most compact scalar multiplication procedure and is particularly suitable for lightweight applications.
typdoc
Communication dans un congrès
DOI
DOI : 10.5220/0010551705310539
Accès au texte intégral et bibtex

2018

Article dans une revue

titre
Euclidean addition chains scalar multiplication on curves with efficient endomorphism
auteur
Fangan-Yssouf Dosso, Fabien Herbaut, Nicolas Méloni, Pascal Véron
article
Journal of Cryptographic Engineering, In press, ⟨10.1007/s13389-018-0190-0⟩
resume
Random Euclidean addition chain generation has proven to be an efficient low memory and SPA secure alternative to standard ECC scalar multiplication methods in the context of fixed base point [21]. In this work, we show how to generalize this method to random point scalar multiplication on elliptic curves with an efficiently computable endomorphism. In order to do so we generalize results from [21] on the relation of random Euclidean chains generation and elliptic curve point distribution obtained from those chains. We propose a software implementation of our method on various platforms to illustrate the impact of our approach. For that matter, we provide a comprehensive study of the practical computational cost of the modular multiplication when using Java and C standard libraries developed for the arithmetic over large integers.
typdoc
Article dans une revue
DOI
DOI : 10.1007/s13389-018-0190-0
Accès au texte intégral et bibtex

2017

Communication dans un congrès

titre
Utilisation de chaines d'additions euclidiennes pour la multiplication scalaire sur des courbes elliptiques munies d'endomorphismes efficaces.
auteur
Fangan-Yssouf Dosso, Fabien Herbaut, Nicolas Méloni, Pascal Véron
article
Journées Codage et Cryptographie 2017, Apr 2017, La Bresse, France
typdoc
Communication dans un congrès
Accès au bibtex

2016

Communication dans un congrès

titre
Random Digit Representation of Integers
auteur
Nicolas Méloni, M. Anwar Hasan
article
ARITH 23, Jul 2016, San Francisco, United States
resume
—Modular exponentiation, or scalar multiplication , is core to today's main stream public key cryptographic systems. In this article we generalize the classical fractional wNAF method for modular exponentiation-the classical method uses a digit set of the form {1, 3,. .. , m} which is extended here to any set of odd integers of the form {1, d2,. .. , dn}. We propose a general modular exponentiation algorithm based on a generalization of the frac-wNAF recoding and a new precomputation scheme. We also give general formula for the average density of non-zero therms in these representations, prove that there are infinitely many optimal sets for a given number of digits and show that the asymptotic behavior, when those digits are randomly chosen, is very close to the optimal case.
typdoc
Communication dans un congrès
Accès au texte intégral et bibtex

2015

Article dans une revue

titre
Efficient Double Bases for Scalar Multiplication
auteur
Nicolas Méloni, M. A. Hasan
article
IEEE Transactions on Computers, 2015, 64 (8), pp.2204-2212. ⟨10.1109/TC.2014.2360539⟩
resume
In this paper we present efficient algorithms to take advantage of the double-base number system in the context of elliptic curve scalar multiplication. We propose a generalized version of Yao's exponentiation algorithm allowing the use of general double-base expansions instead of the popular double base chains. We introduce a class of constrained double base expansions and prove that the average density of non-zero terms in such expansions is $O\left(\frac{\log k}{\log \log k}\right)$ for any large integer $k$. We also propose an efficient algorithm for computing constrained expansions and finally provide a comprehensive comparison to double-base chain expansions, including a large variety of curve shapes and various key sizes.
typdoc
Article dans une revue
DOI
DOI : 10.1109/TC.2014.2360539
Accès au texte intégral et bibtex

Communication dans un congrès

titre
Full Hardware Implementation of Short Addition Chains Recoding for ECC Scalar Multiplication
auteur
Julien Proy, Nicolas Veyrat-Charvillon, Arnaud Tisserand, Nicolas Méloni
article
Compas: Conférence d’informatique en Parallélisme, Architecture et Système, Jun 2015, Lille, France
resume
Ensuring uniform computation profiles is an efficient protection against some side channel attacks (SCA) in embedded systems. Typical elliptic curve cryptography (ECC) scalar multiplication methods use two point operations (addition and doubling) scheduled according to secret scalar digits. Euclidean addition chains (EAC) offer a natural SCA protection since only one point operation is used. Computing short EACs is considered as a very costly operation and no hardware implementation has been reported yet. We designed an hardware recoding unit for short EACs which works concurrently to scalar multiplication. It has been integrated in an in-house ECC processor on various FPGAs. The implementation results show similar computation times compared to non-protected solutions, and faster ones compared to typical protected solutions (e. g. 18 % speed-up over 192 b Montgomery ladder).
typdoc
Communication dans un congrès
Accès au texte intégral et bibtex

2012

Article dans une revue

titre
Block Recombination Approach for Subquadratic Space Complexity Binary Field Multiplication based on Toeplitz Matrix-Vector Product
auteur
Anwar Hasan, Nicolas Méloni, Ashkan Hosseinzadeh Namin, Christophe Negre
article
IEEE Transactions on Computers, Institute of Electrical and Electronics Engineers, 2012, 61 (2), pp.151-163. ⟨10.1109/TC.2010.276⟩
resume
In this paper, we present a new method for parallel binary finite field multiplication which results in subquadratic space complexity. The method is based on decomposing the building blocks of the Fan-Hasan subquadratic Toeplitz matrix-vector multiplier. We reduce the space complexity of their architecture by recombining the building blocks. In comparison to other similar schemes available in the literature, our proposal presents a better space complexity while having the same time complexity. We also show that block recombination can be used for efficient implementation of the GHASH function of Galois Counter Mode (GCM).
typdoc
Article dans une revue
DOI
DOI : 10.1109/TC.2010.276
Accès au bibtex

2011

Article dans une revue

titre
High performance GHASH and impacts of a class of unconventional bases
auteur
Nicolas Méloni, Christophe Negre, Anwar Hasan
article
Journal of Cryptographic Engineering, Springer, 2011, 1 (3), pp.201-218. ⟨10.1007/s13389-011-0013-z⟩
resume
This work presents a new method to compute the GHASH function involved in the Galois/Counter Mode of operation for block ciphers. If $X= X_1\dots X_n$ is a bit string made of $n$ blocks of 128 bits each, then the GHASH function essentially computes $X_1H^n + X_2H^{n-1} + \cdots+ X_nH$, where $H$ is the hash key and an element of the binary field $\Fd_{2^{128}}$. This operation is usually computed by using $n$ successive multiply-and-add operations over $\Fd_{2^{128}}$. Our proposed method replaces all but a fixed number of those multiplications by additions on the field. This is achieved by using the characteristic polynomial of $H$. We present both how to use this polynomial to speed up the GHASH function and how to efficiently compute it for each session that uses a new $H$. We also show that the proposed technique can be parallelized to compute GHASH even faster. In order to try to completely eliminate the need for a field multiplication, we investigate a different set of bases for the field element representation and report their architectural and possible security impacts.
typdoc
Article dans une revue
DOI
DOI : 10.1007/s13389-011-0013-z
Accès au bibtex

2010

Communication dans un congrès

titre
Random Euclidean Addition Chain Generation and Its Application to Point Multiplication
auteur
Fabien Herbaut, Pierre-Yvan Liardet, Nicolas Méloni, Yannick Teglia, Pascal Véron
article
INDOCRYPT 2010, Dec 2010, Hyderabad, India. pp.238-261, ⟨10.1007/978-3-642-17401-8_18⟩
resume
Efficiency and security are the two main objectives of every elliptic curve scalar multiplication implementations. Many schemes have been proposed in order to speed up or secure its computation, usually thanks to efficient scalar representation [30,10,24], faster point operation formulae [8,25,13] or new curve shapes [2]. As an alternative to those general methods, authors have suggested to use scalar belonging to some subset with good computational properties [15,14,36,41,42], leading to faster but usually cryptographically weaker systems. In this paper, we use a similar approach. We propose to modify the key generation pro- cess using a small Euclidean addition chain c instead of a scalar k. This allows us to use a previous scheme, secure against side channel attacks, but whose efficiency relies on the computation of small chains computing the scalar. We propose two different ways to generate short Euclidean addition chains and give a first theoretical analysis of the size and dis- tribution of the obtained keys. We also propose a new scheme in the context of fixed base point scalar multiplication.
typdoc
Communication dans un congrès
DOI
DOI : 10.1007/978-3-642-17401-8_18
Accès au texte intégral et bibtex
titre
High Performance GHASH Function for Long Messages
auteur
Nicolas Méloni, Christophe Negre, M. Anwar Hasan
article
ACNS: Applied Cryptography and Network Security, 2010, Beijing, China. pp.154-167, ⟨10.1007/978-3-642-13708-2_10⟩
resume
This work presents a new method to compute the GHASH function involved in the Galois/Counter Mode of operation for block ciphers. If $X= X_1\dots X_n$ is a bit string made of $n$ blocks of 128 bits each, then the GHASH function effectively computes $X_1H^n + X_2H^{n-1} + \dots X_nH$, where $H$ is an element of the binary field $\Fd_{2^{128}}$. This operation is usually computed by using $n$ successive multiply-add operations over $\Fd_{2^{128}}$. In this work, we propose a method to replace all but a fixed number of those multiplications by additions on the field. This is achieved by using the characteristic polynomial of $H$. We present both how to use this polynomial to speed up the GHASH function and how to efficiently compute it for each session that uses a new $H$.
typdoc
Communication dans un congrès
DOI
DOI : 10.1007/978-3-642-13708-2_10
Accès au texte intégral et bibtex

2009

Communication dans un congrès

titre
Chaînes d'addition euclidienne et logarithme discret
auteur
Fabien Herbaut, Nicolas Méloni, Pascal Véron
article
Journées C2, Oct 2009, Fréjus, France
typdoc
Communication dans un congrès
Accès au bibtex
titre
Elliptic Curve Point Scalar Multiplication Combining Yao's Algorithm and Double Bases
auteur
Nicolas Méloni, M. A. Hasan
article
Cryptographic Hardware and Embedded Systems - CHES 2009- 11th international workshop, Sep 2009, Lausanne, Switzerland. pp.304--316, ⟨10.1007/978-3-642-04138-9_22⟩
resume
In this paper we propose to take one step back in the use of double base number systems for elliptic curve point scalar multiplication. Using a modified version of Yao's algorithm, we go back from the popular double base chain representation to a more general double base system. Instead of representing an integer $k$ as $\sum^n_{i=1}2^{b_i}3^{t_i}$ where $(b_i)$ and $(t_i)$ are two decreasing sequences, we only set a maximum value for both of them. Then, we analyze the efficiency of our new method using different bases and optimal parameters. In particular, we propose for the first time a binary/Zeckendorf representation for integers, providing interesting results. Finally, we provide a comprehensive comparison to state-of-the-art methods, including a large variety of curve shapes and latest point addition formulae speed-ups.
typdoc
Communication dans un congrès
DOI
DOI : 10.1007/978-3-642-04138-9_22
Accès au texte intégral et bibtex

2007

Article dans une revue

titre
Comparison of Simple Power Analysis Attack Resistant Algorithms for an Elliptic Curve Cryptosystem
auteur
Andrew Byrne, Nicolas Méloni, Arnaud Tisserand, Emanuel Popovici, William P. Marnane
article
Journal of Computers (JCP), Academy Publisher, 2007, 2 (10), pp.52-62
resume
There has been a lot of interest in recent years in the problems faced by cryptosystems due to side channel attacks such as Simple Power Analysis (SPA) attacks. Algorithms for elliptic curve point scalar multiplication such as the double and add method are prone to these attacks. The protected double and add algorithm provides a simple solution to this problem but is costly in terms of performance. Another class of algorithm for point scalar multiplication that makes use of special addition chains can be used to protect against SPA attacks. A reconfigurable architecture for a cryptographic processor is presented and a number of algorithms for point multiplication are implemented and compared. These algorithms have a degree of parallelism within their operations where a number of multiplications can be executed in parallel. Sophisticated scheduling techniques can exploit this parallelism in order to optimize the performance of the calculation. Post place and route results for the processor are given.
typdoc
Article dans une revue
Accès au texte intégral et bibtex
titre
SPA Resistant Elliptic Curve Cryptosystem Using Addition Chains
auteur
Andrew Byrne, Francis Crowe, William P. Marnane, Nicolas Méloni, Arnaud Tisserand, Emanuel Popovici
article
International Journal of High Performance Systems Architecture (IJHPSA), InterScience, 2007, 1 (2), pp.133-142. ⟨10.1504/IJHPSA.2007.015399⟩
resume
There has been a lot of interest in recent years in the problems faced by cryptosystems due to side channel attacks. Algorithms for elliptic curve point scalar multiplication such as the double-and-add method are prone to such attacks. By making use of special addition chains, it is possible to implement a Simple Power Analysis (SPA) resistant cryptosystem. In this paper, a reconfigurable architecture for a cryptographic processor is presented. A SPA resistant algorithm for point multiplication is implemented and is shown to be faster than the double-and-add method. Post place and route results for the processor are given.
typdoc
Article dans une revue
DOI
DOI : 10.1504/IJHPSA.2007.015399
Accès au texte intégral et bibtex

Communication dans un congrès

titre
New Point Addition Formulae for ECC Applications
auteur
Nicolas Méloni
article
WAIFI: Workshop on the Arithmetic of Finite Fields, Jun 2007, Madrid, Spain. pp.189-201, ⟨10.1007/978-3-540-73074-3_15⟩
resume
In this paper we propose a new approach to point scalar multiplication on elliptic curves defined over fields of characteristic greater than 3. It is based on new point addition formulae that suit very well to exponentiation algorithms based on Euclidean addition chains. However finding small chains remains a very difficult problem, so we also develop a specific exponentiation algorithm, based on Zeckendorf representation (i.e. representing the scalar $k$ using Fibonacci numbers instead of powers of 2), which takes advantage of our formulae.
typdoc
Communication dans un congrès
DOI
DOI : 10.1007/978-3-540-73074-3_15
Accès au texte intégral et bibtex
titre
SPA Resistant Elliptic Curve Cryptosystem using Addition Chains
auteur
Andrew Byrne, Nicolas Méloni, Francis Crowe, William P. Marnane, Arnaud Tisserand, Emanuel Popovici
article
ITNG'07: 4th International Conference on Information Technology, Apr 2007, Las Vegas, Nevada, U.S.A., pp.995-1000, ⟨10.1109/ITNG.2007.185⟩
resume
There has been a lot of interest in recent years in the problems faced by cryptosystems due to side channel attacks. Algorithms for elliptic curve point scalar multiplication such as the double and add method are prone to such attacks. By making use of special addition chains, it is possible to implement a Simple Power Analysis (SPA) resistant cryptosystem. In this paper a reconfigurable architecture for a cryptographic processor is presented. A SPA resistant algorithm for point multiplication is implemented and is shown to be faster than the double-and-add method. Post place and route results for the processor are given.
typdoc
Communication dans un congrès
DOI
DOI : 10.1109/ITNG.2007.185
Accès au texte intégral et bibtex

Thèse

titre
Arithmetic for Cryptography based on Elliptic Curves
auteur
Nicolas Méloni
article
Cryptographie et sécurité [cs.CR]. Université de Montpellier 2, 2007. Français. ⟨NNT : ⟩
resume
Dans cette thèse, nous nous intéressons au problème de l'implantation de la multiplication de point par un scalaire sur les courbes elliptiques définies sur des corps premiers. Nous abordons ce problème aussi bien au niveau des algorithmes de multiplication de points, que de l'arithmétique de la courbe ou du corps sous-jacent. L'originalité des travaux présentés ici est qu'ils ne traitent pas de chaque aspects séparément. En effet nous avons toujours cherché à développer l'arithmétique à un niveau donné en gardant à l'esprit son lien avec les niveaux inférieurs ou supérieurs. La présente thèse compose de trois parties. La première partie est consacré à l'état de l'art concernant l'arithmétique des courbes elliptiques. Le chapitre 1 est un tour d'horizon des principales propriétés des courbes elliptiques et des différentes formules d'addition de points selon le système de coordonnées choisi. Dans le chapitre 2, nous présentons les principales méthodes de multiplication de points par un scalaire, aussi bien pour les courbes définies sur des corps premiers que pour les courbes définies sur des corps binaires. La deuxième partie a pour objet l'étude de nouvelles formules d'addition de points sur les courbes et les nouveaux algorithmes de multiplication de points que l'on peut en déduire. Le chapitre 3 détaille les nouvelles formules d'addition de points, ainsi que l'algorithme dit de "Fibonacci" et addition. Dans le chapitre 4 nous présentons un type de chaînes d'additions, les chaînes d'additions différentielles, naturellement adaptées aux formules introduites dans le chapitre précédent, puis, nous proposons une construction de chaînes particulières, afin d'en déduire un algorithme de multiplication de point le plus efficace possible. La troisième partie traite de la représentation RNS et de son adaptation à l'arithmétique des courbes elliptiques. Dans le chapitre 5 nous faisons un rappel des propriétés principale de la représentation RNS. Nous proposons, dans le chapitre 6, des bases RNS particulières permettant d'améliorer l'efficacité des calculs. Ensuite, dans le chapitre 7, nous proposons un algorithme d'inversion modulaire en RNS. Enfin, le chapitre 8 est consacré à l'étude de la complexité des sommes de produits modulaires en fonction du système de représentation choisi, puis à l'aménagement des formules d'additions de points sur les courbes afin de tirer avantages des spécificité du RNS.
typdoc
Thèse
Accès au texte intégral et bibtex

2006

Communication dans un congrès

titre
Residue systems efficiency for modular products summation: Application to Elliptic Curves Cryptography
auteur
Jean-Claude Bajard, Sylvain Duquesne, Milos Ercegovac, Nicolas Méloni
article
Proceedings of SPIE : Advanced Signal Processing Algorithms, Architectures, and Implementations XVI, Aug 2006, pp.0
resume
Residue systems of representation, like Residue Number Systems (RNS) for primary field($GF (p)$) or Trinomial Residue Arithmetic for binary field ($GF (2^k )$), are characterized by efficient multiplication and costly modular reduction. On the other hand, conventional representations allow in some cases very efficient reductions but require costly multiplications. The main purpose of this paper is to analyze the complexity of those two different approaches in the summations of products. As a matter of fact, the complexities of the reduction in residue systems and of the multiplication in classical representations are similar. One of the main features of this reduction is that it doesn't depend on the field. Moreover, the cost of multiplication in residue systems is equivalent to the cost of reduction in classical representations for special well-chosen fields. Taking those properties into account, we remark that an expression like $A * B + C * D$, which requires two products, one addition and one reduction, evaluates faster in a residue system than in a classical one. So we propose to study types of expressions to offer a guide for choosing a most appropriate representation. One of the best domain of application is the Elliptic Curves Cryptography where addition and doubling points formulas are composed of products summation. The different kinds of coordinates like affine, projective, and Jacobean, offer a good choice of expressions for our study.
typdoc
Communication dans un congrès
Accès au texte intégral et bibtex

Rapport

titre
Combining Montgomery Ladder for Elliptic Curves Defined over $\F_p$ and RNS Representation
auteur
Jean-Claude Bajard, Sylvain Duquesne, Nicolas Méloni
article
[Research Report] 06041, LIR. 2006
resume
In this paper, we combine the RNS representation and the Montgomery ladder on elliptic curves in Weierstrass form. These two techniques are relevant for implementation of elliptic curve cryptogra- phy on embedded devices since they have leak-resistance properties. We optimize formulae for addition and doubling of the Montgomery lad- der in terms of modular reductions to obtain a competitive and secure implementation. Afterwards, we explain the advantages of the RNS rep- resentation, especially in hardware and for embedded devices, and show that, contrary to other approaches, ours takes optimal advantage of a dedicated parallel architecture.
typdoc
Rapport
Accès au texte intégral et bibtex

2005

Communication dans un congrès

titre
Study of Modular Inversion in RNS
auteur
Jean-Claude Bajard, Nicolas Méloni, Thomas Plantard
article
SPIE'05: Advanced Signal Processing AlgorithmsArchitectures and Implementations XV, Jul 2005, San Diego, CA (USA)
typdoc
Communication dans un congrès
Accès au bibtex
titre
Efficient RNS Bases for Cryptography
auteur
Jean-Claude Bajard, Nicolas Méloni, Thomas Plantard
article
17th IMACS World Congress Scientific Computation, Applied Mathematics and Simulation, Jul 2005, Paris, France
resume
Residue Number Systems (RNS) are useful for distributing large dynamic range computations over small modular rings, which allows the speed up of computations. This feature is well known, and already used in both DSP and cryptography. In this paper we deal with implementa- tion for huge numbers like those used for ciphering as with RSA or ECC on prime finite fields. Modular multiplication is the main operation of these protocols. We find very interesting modular multiplication algorithms in RNS where the conversion from an RNS basis to another represents the main part of the complexity. Hence, we propose in this paper an analysis of the criteria for selecting some bases giving efficient conversions. We conclude by giving methods for constructing an efficient basis in function of the size of different parameters like the basic operators, the key of the cryptosystem, etc. Residue Number Systems (RNS) are useful for distributing large dynamic range computations over small modular rings, which allows the speed up of computations. This feature is well known, and already used in both DSP and cryptography. In this paper we deal with implementation for huge numbers like those used for ciphering as with RSA or ECC on prime finite fields. Modular multiplication is the main operation of these protocols. We find very interesting modular multiplication algorithms in RNS where the conversion from an RNS basis to another represents the main part of the complexity. Hence, we propose in this paper an analysis of the criteria for selecting some bases giving efficient conversions. We conclude by giving methods for constructing an efficient basis in function of the size of different parameters like the basic operators, the key of the cryptosystem, etc.
typdoc
Communication dans un congrès
Accès au texte intégral et bibtex