Paper published in a book (Scientific congresses, symposiums and conference proceedings)
A Family of Lightweight Twisted Edwards Curves for the Internet of Things
Ghatpande, Sankalp; Groszschädl, Johann; Liu, Zhe
2018 • In Blazy, Olivier; Yeun, Chan Y. (Eds.) Information Security Theory and Practice, 12th IFIP WG 11.2 International Conference, WISTP 2018, Brussels, Belgium, December 10-11, 2018, Proceedings
Internet of Things (IoT); Lightweight Cryptography; Elliptic Curve Cryptography; Twisted Edwards Curve; Montgomery Curve; Pseudo-Mersenne Prime Field
Abstract :
[en] We introduce a set of four twisted Edwards curves that satisfy common security requirements and allow for fast implementations of scalar multiplication on 8, 16, and 32-bit processors. Our curves are defined by an equation of the form -x^2 + y^2 = 1 + dx^2y^2 over a prime field Fp, where d is a small non-square modulo p. The underlying prime fields are based on "pseudo-Mersenne" primes given by p = 2^k - c and have in common that p is congruent to 5 modulo 8, k is a multiple of 32 minus 1, and c is at most eight bits long. Due to these common features, our primes facilitate a parameterized implementation of the low-level arithmetic so that one and the same arithmetic function is able to process operands of different length. Each of the twisted Edwards curves we introduce in this paper is birationally equivalent to a Montgomery curve of the form -(A+2)y^2 = x^3 + Ax^2 + x where 4/(A+2) is small. Even though this contrasts with the usual practice of choosing A such that (A+2)/4 is small, we show that the Montgomery form of our curves allows for an equally efficient implementation of point doubling as Curve25519. The four curves we put forward roughly match the common security levels of 80, 96, 112 and 128 bits. In addition, their Weierstraß representations are isomorphic to curves of the form y^2 = x^3 - 3x + b so as to facilitate inter-operability with TinyECC and other legacy software.
Disciplines :
Computer science
Author, co-author :
Ghatpande, Sankalp ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
Groszschädl, Johann ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
Liu, Zhe ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > Computer Science and Communications Research Unit (CSC)
External co-authors :
no
Language :
English
Title :
A Family of Lightweight Twisted Edwards Curves for the Internet of Things
Publication date :
December 2018
Event name :
12th International Conference on Information Security Theory and Practice (WISTP 2018)
Event place :
Brussels, Belgium
Event date :
from 10-12-2018 to 11-12-2018
Audience :
International
Main work title :
Information Security Theory and Practice, 12th IFIP WG 11.2 International Conference, WISTP 2018, Brussels, Belgium, December 10-11, 2018, Proceedings
Bernstein, D.J.: Curve25519: new Diffie-Hellman speed records. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.) PKC 2006. LNCS, vol. 3958, pp. 207– 228. Springer, Heidelberg (2006). https://doi.org/10.1007/11745853_14
Bernstein, D.J., Birkner, P., Joye, M., Lange, T., Peters, C.: Twisted edwards curves. In: Vaudenay, S. (ed.) AFRICACRYPT 2008. LNCS, vol. 5023, pp. 389– 405. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-68164-9_26
Bernstein, D.J., Chuengsatiansup, C., Lange, T.: Curve41417: karatsuba revisited. In: Batina, L., Robshaw, M. (eds.) CHES 2014. LNCS, vol. 8731, pp. 316–334. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44709-3_18
Bernstein, D.J., Lange, T.: Faster addition and doubling on elliptic curves. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 29–50. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-76900-2_3
Bernstein, D.J., Lange, T.: SafeCurves: Choosing safe curves for elliptic-curve cryptography (2013). http://safecurves.cr.yp.to
Bernstein, D.J., Lange, T.: Security dangers of the NIST curves. Presentation given at the 3rd Workshop on International View of the State-of-the-Art of Cryptography and Security and its Use in Practice, Athens, Greece, 30–31 May 2013 (2013). http://www.hyperelliptic.org/tanja/vortraege/20130531.pdf
Blake, I.F., Seroussi, G., Smart, N.P.: Elliptic Curves in Cryptography. London Mathematical Society Lecture Notes Series, vol. 265. Cambridge University Press, Cambridge (1999)
Bos, J.W., Costello, C., Longa, P., Naehrig, M.: Selecting elliptic curves for cryptography: an efficiency and security analysis. J. Cryptogr. Eng. 6(4), 259–286 (2016)
Bos, J.W., Halderman, J.A., Heninger, N., Moore, J., Naehrig, M., Wustrow, E.: Elliptic curve cryptography in practice. In: Christin, N., Safavi-Naini, R. (eds.) FC 2014. LNCS, vol. 8437, pp. 157–175. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45472-5_11
Brier, E., Joye, M.: Fast point multiplication on elliptic curves through isogenies. In: Fossorier, M., Høholdt, T., Poli, A. (eds.) AAECC 2003. LNCS, vol. 2643, pp. 43–50. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-44828-4_6
Chu, D., Großschädl, J., Liu, Z., Müller, V., Zhang, Y.: Twisted Edwards-form elliptic curve cryptography for 8-bit AVR-based sensor nodes. In: Xu, S., Zhao, Y. (eds.) Proceedings of the 1st ACM Workshop on Asia Public-Key Cryptography (AsiaPKC 2013), pp. 39–44. ACM Press (2013)
Costello, C., Longa, P., Naehrig, M.: A brief discussion on selecting new elliptic curves. Technical report MSR-TR-2015-46, Microsoft Research, June 2015. http://research.microsoft.com/apps/pubs/default.aspx?id=246915
ECC Brainpool Consortium. ECC Brainpool standard curves and curve generation (2005). http://www.ecc-brainpool.org/download/Domain-parameters.pdf
Edwards, H.M.: A normal form for elliptic curves. Bull. Am. Math. Soc. 44(3), 393–422 (2007)
Ericsson. Ericsson Mobility Report November 2017 (2017). http://www.ericsson.com/assets/local/mobility-report/documents/2017/ericsson-mobility-report-november-2017.pdf
Flori, J.-P., Plût, J., Reinhard, J.-R., Ekerå, M.: Diversity and transparency for ECC. Cryptology ePrint Archive, Report 2015/659 (2015). http://eprint.iacr.org
Hamburg, M.: Fast and compact elliptic-curve cryptography. Cryptology ePrint Archive, Report 2012/309 (2012). http://eprint.iacr.org
Hamburg, M.: Ed448-Goldilocks, a new elliptic curve. Cryptology ePrint Archive, Report 2015/625 (2015). http://eprint.iacr.org
Hankerson, D.R., Menezes, A.J., Vanstone, S.A.: Guide to Elliptic Curve Cryptography. Springer, New York (2004). https://doi.org/10.1007/b97644
Langley, A., Hamburg, M., Turner, S.: Elliptic curves for security. Internet Engineering Task Force, Internet Research Task Force, RFC 7748, January 2016
Liu, A., Ning, P.: TinyECC: a configurable library for elliptic curve cryptography in wireless sensor networks. In: Proceedings of the 7th International Conference on Information Processing in Sensor Networks (IPSN 2008), pp. 245–256. IEEE Computer Society Press (2008)
Liu, Z., Wenger, E., Großschädl, J.: MoTE-ECC: energy-scalable elliptic curve cryptography for wireless sensor networks. In: Boureanu, I., Owesarski, P., Vaudenay, S. (eds.) ACNS 2014. LNCS, vol. 8479, pp. 361–379. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-07536-5_22
Miller, V.S.: Use of elliptic curves in cryptography. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 417–426. Springer, Heidelberg (1986). https://doi.org/10.1007/3-540-39799-X_31
Montgomery, P.L.: Speeding the Pollard and elliptic curve methods of factorization. Math. Comput. 48(177), 243–264 (1987)
National Institute of Standards and Technology (NIST). Digital Signature Standard (DSS). FIPS Publication 186-4, July 2013. http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf
Struik, R.: Alternative elliptic curve representations. Internet Engineering Task Force, Light-Weight Implementation Guidance (LWIG) Working Group, Internet draft draft-struik-lwip-curve-representations-02 (work in progress), July 2018
Yan, L., Zhang, Y., Yang, L.T., Ning, H.: The Internet of Things: From RFID to the Next-Generation Pervasive Networked Systems. Auerbach Publications (2008)