Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Efficient RKA-Secure KEM and IBE Schemes Against Invertible Functions Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

High-Performance Ideal Lattice-Based Cryptography on 8-Bit ATxmega Microcontrollers

verfasst von : Thomas Pöppelmann, Tobias Oder, Tim Güneysu

Erschienen in: Progress in Cryptology -- LATINCRYPT 2015

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Over the last years lattice-based cryptography has received much attention due to versatile average-case problems like Ring-LWE or Ring-SIS that appear to be intractable by quantum computers. But despite of promising constructions, only few results have been published on implementation issues on very constrained platforms. In this work we therefore study and compare implementations of Ring-LWE encryption and the Bimodal Lattice Signature Scheme (BLISS) on an 8-bit Atmel ATxmega128 microcontroller. Since the number theoretic transform (NTT) is one of the core components in implementations of lattice-based cryptosystems, we review the application of the NTT in previous implementations and present an improved approach that significantly lowers the runtime for polynomial multiplication. Our implementation of Ring-LWE encryption takes 27 ms for encryption and 6.7 ms for decryption. To compute a BLISS signature, our software takes 329 ms and 88 ms for verification. These results outperform implementations on similar platforms and underline the feasibility of lattice-based cryptography on constrained devices.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Fast Implementation of Curve25519 Using AVX2
Nächstes Kapitel An Efficient Software Implementation of the Hash-Based Signature Scheme MSS and Its Variants
Fußnoten
1
The NTT can be regarded as Fast Fourier Transform over \(\mathbb {Z}_{q}\).
 
3
Actually, this is overly restrictive and the NTT is also defined for certain composite numbers (n has to divide \(p-1\) for every prime factor p of \(q\)). However, for the given target parameter sets common in lattice-based cryptography we can restrict ourselves to prime moduli and refer to [41] for further information on composite moduli NTTs.
 
4
Similar to exponentiation being the main operation of RSA or point multiplication being the main operation of ECC.
 
5
Up to our knowledge, all security evaluations of RLWEenc (and also BLISS) only consider best known attacks executed on a classical computer. The security levels are thus denoted as pre-quantum. A security assessment that considers quantum computers is certainly necessary but is not in the scope of this paper.
 
6
Most of the techniques discussed in this section have already been proposed in the context of the fast Fourier transform (FFT). However, they have not yet been considered to speed up ideal lattice-based cryptography (at least not in works like [7, 12, 43, 48]). Moreover, some optimizations and techniques are mutually exclusive and a careful selection and balancing has to be made.
 
7
It is debatable which precision is really necessary in RLWEenc and what impact less precision would have on the security of the scheme, e.g., \(\lambda =40\). But as the implementation of the CDT for small standard deviations \(\sigma \) is rather efficient and for better comparison with related work like [6, 7, 12] we chose to implement high precision sampling and set \(\lambda =128\).
 
8
While the ATxmega128 and ATxmega64 compared to the ATmega64 differ in their operation frequency and some architectural differences cycle counts are mostly comparable.
 
9
One exception is a Master thesis by Monteverde [39], but the implemented NTRU251:3 variant is not secure anymore according to recent recommendations in [28].
 
Literatur
1.
Bai, S., Galbraith, S.D.: An improved compression technique for signatures based on learning with errors. In: Benaloh, J. (ed.) CT-RSA 2014. LNCS, vol. 8366, pp. 28–47. Springer, Heidelberg (2014) CrossRef
2.
Balasch, J., Ege, B., Eisenbarth, T., Gérard, B., Gong, Z., Güneysu, T., Heyse, S., Kerckhof, S., Koeune, F., Plos, T., Pöppelmann, T., Regazzoni, F., Standaert, F.-X., Van Assche, G., Van Keer, R., van Oldeneel tot Oldenzeel, L., von Maurich, I.: Compact implementation and performance evaluation of hash functions in ATtiny devices. In: Mangard, S. (ed.) CARDIS 2012. LNCS, vol. 7771, pp. 158–172. Springer, Heidelberg (2013) CrossRef
3.
Batina, L., Robshaw, M. (eds.): CHES 2014. LNCS, vol. 8731. Springer, Heidelberg (2014)
4.
5.
6.
7.
Boorghany, A., Sarmadi, S.B., Jalili, R.: On constrained implementation of lattice-based cryptographic primitives and schemes on smart cards. Eprint 2014, 514 (2014). http://​eprint.​iacr.​org/​2014/​514, successive version of [6]
8.
9.
Cabarcas, D., Weiden, P., Buchmann, J.: On the efficiency of provably secure NTRU. In: Mosca [40], pp. 22–39
10.
Chen, D.D., Mentens, N., Vercauteren, F., Roy, S.S., Cheung, R.C.C., Pao, D., Verbauwhede, I.: High-speed polynomial multiplication architecture for ring-LWE and SHE cryptosystems. IEEE Trans. Circuits Syst. 62–I(1), 157–166 (2015)CrossRef
11.
Chu, E., George, A.: Inside the FFT Black Box Serial and Parallel Fast Fourier Transform Algorithms. CRC Press, Boca Raton (2000) MATH
12.
13.
Cooley, J.W., Tukey, J.W.: An algorithm for the machine calculation of complex Fourier series. Math. Comput. 19, 297–301 (1965)MathSciNetCrossRefMATH
14.
Crandall, R., Fagin, B.: Discrete weighted transforms and large-integer arithmetic. Math. Comput. 62(205), 305–324 (1994)MathSciNetCrossRef
15.
Crandall, R., Pomerance, C.: Prime Numbers: A Computational Perspective. Springer, Heidelberg (2001)CrossRef
16.
17.
Ducas, L., Durmus, A., Lepoint, T., Lyubashevsky, V.: Lattice signatures and bimodal Gaussians. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 40–56. Springer, Heidelberg (2013) CrossRef
18.
19.
Ducas, L., Lyubashevsky, V., Prest, T.: Efficient identity-based encryption over NTRU lattices. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014, Part II. LNCS, vol. 8874, pp. 22–41. Springer, Heidelberg (2014)
20.
Düll, M., Haase, B., Hinterwälder, G., Hutter, M., Paar, C., Sánchez, A.H., Schwabe, P.: High-speed Curve25519 on 8-bit, 16-bit and 32-bit microcontrollers. Des. Codes Crypt. (to appear)
21.
Dwarakanath, N.C., Galbraith, S.D.: Sampling from discrete Gaussians for lattice-based cryptography on a constrained device. Appl. Algebra Eng. Commun. Comput. 25(3), 159–180 (2014)MathSciNetCrossRefMATH
22.
Gentleman, W.M., Sande, G.: Fast Fourier transforms: for fun and profit. In: AFIPS Conference Proceedings, AFIPS 1966, vol. 29, pp. 563–578. AFIPS/ACM/Spartan Books, Washington D.C. (1966)
23.
Göttert, N., Feller, T., Schneider, M., Buchmann, J., Huss, S.A.: On the design of hardware building blocks for modern lattice-based encryption schemes. In: Prouff and Schaumont [46], pp. 512–529
24.
Güneysu, T., Lyubashevsky, V., Pöppelmann, T.: Practical lattice-based cryptography: a signature scheme for embedded systems. In: Prouff and Schaumont [46], pp. 530–547
25.
Güneysu, T., Oder, T., Pöppelmann, T., Schwabe, P.: Software speed records for lattice-based signatures. In: Gaborit, P. (ed.) PQCrypto 2013. LNCS, vol. 7932, pp. 67–82. Springer, Heidelberg (2013) CrossRef
26.
Gura, N., Patel, A., Wander, A., Eberle, H., Shantz, S.C.: Comparing elliptic curve cryptography and RSA on 8-bit CPUs. In: Joye, M., Quisquater, J.-J. (eds.) CHES 2004. LNCS, vol. 3156, pp. 119–132. Springer, Heidelberg (2004) CrossRef
27.
Heyse, S., von Maurich, I., Güneysu, T.: Smaller keys for code-based cryptography: QC-MDPC McEliece implementations on embedded devices. In: Bertoni, G., Coron, J.-S. (eds.) CHES 2013. LNCS, vol. 8086, pp. 273–292. Springer, Heidelberg (2013) CrossRef
28.
Hirschhorn, P.S., Hoffstein, J., Howgrave-Graham, N., Whyte, W.: Choosing NTRUEncrypt parameters in light of combined lattice reduction and MITM approaches. In: Abdalla, M., Pointcheval, D., Fouque, P.-A., Vergnaud, D. (eds.) ACNS 2009. LNCS, vol. 5536, pp. 437–455. Springer, Heidelberg (2009) CrossRef
29.
Hoffstein, J., Pipher, J., Schanck, J.M., Silverman, J.H., Whyte, W.: Practical signatures from the partial Fourier recovery problem. In: Boureanu, I., Owesarski, P., Vaudenay, S. (eds.) ACNS 2014. LNCS, vol. 8479, pp. 476–493. Springer, Heidelberg (2014)
30.
Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: a ring-based public key cryptosystem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 267–288. Springer, Heidelberg (1998) CrossRef
31.
Hutter, M., Schwabe, P.: NaCl on 8-bit AVR microcontrollers. In: Youssef, A., Nitaj, A., Hassanien, A.E. (eds.) AFRICACRYPT 2013. LNCS, vol. 7918, pp. 156–172. Springer, Heidelberg (2013) CrossRef
32.
Lindner, R., Peikert, C.: Better key sizes (and attacks) for LWE-based encryption. In: Kiayias, A. (ed.) CT-RSA 2011. LNCS, vol. 6558, pp. 319–339. Springer, Heidelberg (2011) CrossRef
33.
Liu, M., Nguyen, P.Q.: Solving BDD by enumeration: an update. In: Dawson, E. (ed.) CT-RSA 2013. LNCS, vol. 7779, pp. 293–309. Springer, Heidelberg (2013) CrossRef
34.
Liu, Z., Großschädl, J., Kizhvatov, I.: Efficient and side-channel resistant RSA implementation for 8-bit AVR microcontrollers. In: SECIOT 2010. IEEE Computer Society Press (2010)
35.
36.
Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 1–23. Springer, Heidelberg (2010) CrossRef
37.
38.
Melchor, C.A., Boyen, X., Deneuville, J., Gaborit, P.: Sealing the leak on classical NTRU signatures. In: Mosca [40], pp. 1–21
39.
Monteverde, M.: NTRU software implementation for constrained devices. Master’s thesis, Katholieke Universiteit Leuven (2008)
40.
Mosca, M. (ed.): PQCrypto 2014. LNCS, vol. 8772. Springer, Heidelberg (2014) MATH
41.
Nussbaumer, H.J.: Fast Fourier Transform and Convolution Algorithms, Springer Series in Information Sciences, vol. 2. Springer, Heidelberg (1982)
42.
Oder, T., Pöppelmann, T., Güneysu, T.: Beyond ECDSA and RSA: lattice-based digital signatures on constrained devices. In: DAC 2014, pp. 1–6. ACM (2014)
43.
Pöppelmann, T., Ducas, L., Güneysu, T.: Enhanced lattice-based signatures on reconfigurable hardware. In: Batina and Robshaw [3], pp. 353–370
44.
Pöppelmann, T., Güneysu, T.: Towards practical lattice-based public-key encryption on reconfigurable hardware. In: Lange, T., Lauter, K., Lisoněk, P. (eds.) SAC 2013. LNCS, vol. 8282, pp. 68–86. Springer, Heidelberg (2014) CrossRef
45.
46.
Prouff, E., Schaumont, P. (eds.): CHES 2012. LNCS, vol. 7428. Springer, Heidelberg (2012)
47.
48.
Roy, S.S., Vercauteren, F., Mentens, N., Chen, D.D., Verbauwhede, I.: Compact ring-LWE cryptoprocessor. In: Batina and Robshaw [3], pp. 371–391
49.
Schönhage, A., Strassen, V.: Schnelle multiplikation grosser zahlen. Computing 7(3), 281–292 (1971)CrossRefMATH
50.
Shor, P.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994, pp. 124–134. IEEE (1994)
51.
Stehlé, D., Steinfeld, R.: Making NTRU as secure as worst-case problems over ideal lattices. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 27–47. Springer (2011)
52.
Winkler, F.: Polynomial Algorithms in Computer Algebra. Texts and Monographs in Symbolic Computation, 1st edn. Springer, Heidelberg (1996) CrossRefMATH
Metadaten
Titel
High-Performance Ideal Lattice-Based Cryptography on 8-Bit ATxmega Microcontrollers
verfasst von
Thomas Pöppelmann
Tobias Oder
Tim Güneysu
Copyright-Jahr
2015
Buch
Progress in Cryptology -- LATINCRYPT 2015

Print ISBN: 978-3-319-22173-1

Electronic ISBN: 978-3-319-22174-8

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-319-22174-8_19