nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

On the Efficiency of Polynomial Multiplication for Lattice-Based Cryptography on GPUs Using CUDA

verfasst von : Sedat Akleylek, Özgur Dağdelen, Zaliha Yüce Tok

Erschienen in: Cryptography and Information Security in the Balkans

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Polynomial multiplication is the most time-consuming part of cryptographic schemes whose security is based on ideal lattices. Thus, any efficiency improvement on this building block has great impact on the practicability of lattice-based cryptography. In this work, we investigate several algorithms for polynomial multiplication on a graphical processing unit (GPU), and implement them in both serial and parallel way on the GPU using the compute unified device architecture (CUDA) platform. Moreover, we focus on the quotient ring \(({\mathbb Z}/ p{\mathbb Z}) [x]/(x^n+1)\), where p is a prime number and n is a power of 2. We stress that this ring constitutes the most common setting in lattice-based cryptography for efficiency reasons. As an application we integrate the different implementations of polynomial multiplications into a lattice-based signature scheme proposed by Güneysu et al. (CHES 2012) and identify which algorithm is the preferable choice with respect to the ring of degree n.

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 Closing the Gap: A Universal Privacy Framework for Outsourced Data

Nächstes Kapitel cuHE: A Homomorphic Encryption Accelerator Library

Akleylek, S., Tok, Z.Y.: Efficient arithmetic for lattice-based cryptography on GPU using the CUDA platform. In: 22nd Signal Processing and Communications Applications Conference (SIU 2014), pp. 854–857. IEEE Press (2014)

Akleylek, S., Tok, Z.Y.: Efficient interleaved montgomery modular multiplication for lattice-based cryptography. IEICE Electron. Express 11(22), 1–6 (2014)CrossRef

Akleylek, S., Tok, Z.Y.: Computational aspects of lattice-based cryptography on graphical processing unit. In: El Sayed, M.S., El-Alfy, M.H., (eds.) Improving Information Security Practices through Computational Intelligence, pp. 255–284. IGI Global (2015)

Aysu, A., Patterson, C., Schaumont, P.: Low-cost and area efficient FPGA implementations of lattice-based cryptography. In: IEEE HOST 2013, pp. 81–86. IEEE Press (2013)

Bai, T., Davis, S., Li, J., Jiang, H.: Analysis and acceleration of NTRU lattice-based cryptographic system. In: SNPD, pp. 1–6. IEEE Press (2014)

Banerjee, A., Peikert, C., Rosen, A.: Pseudorandom functions and lattices. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 719–737. Springer, Heidelberg (2012)CrossRef

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. Circ. Syst. I: Regul. Pap. 62(1), 157–166 (2015)

Emeliyanenko, P.: Efficient multiplication of polynomials on graphics hardware. In: Dou, Y., Gruber, R., Joller, J.M. (eds.) APPT 2009. LNCS, vol. 5737, pp. 134–149. Springer, Heidelberg (2009)CrossRef

Gathen, J.V.Z., Gerhard, J.: Modern Computer Algebra, 3rd edn. Cambridge University Press, Cambridge (2013)CrossRefMATH

10.

Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing (STOC), pp. 169–178. ACM, NY (2009)

11.

Göttert, N., Feller, T., Schneider, M., Buchmann, J., Huss, S.: On the design of hardware building blocks for modern lattice-based encryption schemes. In: Prouff, E., Schaumont, P. (eds.) CHES 2012. LNCS, vol. 7428, pp. 512–529. Springer, Heidelberg (2012)CrossRef

12.

Güneysu, T., Lyubashevsky, V., Pöppelmann, T.: Lattice-based signatures: optimization and implementation on reconfigurable hardware. IEEE Trans. Comput. 64, 1954–1967 (2014). doi:10.1109/TC.2014.2346177 CrossRefMathSciNet

13.

Györfi, T., Cret, O., Borsos, Z.: Implementing modular FFTs in FPGAs - a basic block for lattice-based cryptography. In: Euromicro Conference on Digital System Design (DSD 2013), pp. 305–308. IEEE Press (2013)

14.

Györfi, T., Cret, O., Hanrot, G., Brisebarre, N.: High-throughput Hardware Architecture for the (SWIFFT)/(SWIFFTX) Hash Functions. In: IACR, Cryptology ePrint Archive 2012, p. 343 (2012)

15.

Hermans, J., Schneider, M., Buchmann, J., Vercauteren, F., Preneel, B.: Parallel shortest lattice vector enumeration on graphics cards. In: Bernstein, D.J., Lange, T. (eds.) AFRICACRYPT 2010. LNCS, vol. 6055, pp. 52–68. Springer, Heidelberg (2010)CrossRef

16.

Kuo, P.-C., Schneider, M., Dagdelen, Ö., Reichelt, J., Buchmann, J., Cheng, C.-M., Yang, B.-Y.: Extreme enumeration on GPU and in clouds. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 176–191. Springer, Heidelberg (2011)CrossRef

17.

Lyubashevsky, V., Micciancio, D., Peikert, C., Rosen, A.: SWIFFT: a modest proposal for FFT hashing. In: Nyberg, K. (ed.) FSE 2008. LNCS, vol. 5086, pp. 54–72. Springer, Heidelberg (2008)CrossRef

18.

NVIDIA CUDA Toolkit Documentation (2014). http://docs.nvidia.com/cuda/eula/index.html

19.

Pollard, J.M.: The fast fourier transform in a finite field. Math. Comput. 25(114), 365–374 (1971)CrossRefMathSciNetMATH

20.

Güneysu, T., Pöppelmann, T.: Towards efficient arithmetic for lattice-based cryptography on reconfigurable hardware. In: Hevia, A., Neven, G. (eds.) LatinCrypt 2012. LNCS, vol. 7533, pp. 139–158. Springer, Heidelberg (2012)CrossRef

21.

Pöppelmann, T., Ducas, L., Güneysu, T.: Enhanced lattice-based signatures on reconfigurable hardware. In: Batina, L., Robshaw, M. (eds.) CHES 2014. LNCS, vol. 8731, pp. 353–370. Springer, Heidelberg (2014)

22.

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

23.

Pöppelmann, T., Güneysu, T.: Area optimization of lightweight lattice-based encryption on reconfigurable hardware. In: IEEE International Symposium on Circuits and Systems (ISCAS 2014), pp. 2796–2799. IEEE Press (2014)

24.

Qiao, S.: A jacobi method for lattice basis reduction. In: Spring Congress on Engineering and Technology (S-CET 2012), pp. 1–4 (2012)

25.

Roy, S.S., Vercauteren, F., Mentens, N., Chen, D.D., Verbauwhede, I.: Compact ring-LWE cryptoprocessor. In: Batina, L., Robshaw, M. (eds.) CHES 2014. LNCS, vol. 8731, pp. 371–391. Springer, Heidelberg (2014)

26.

Shor, P.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)CrossRefMathSciNetMATH

27.

Solinas, J.A.: Generalized Mersenne Numbers. Technical report CORR99-39, Center for Applied Cryptographic Research, University of Waterloo (1999)

28.

Wang, W., Chen, Z., Huang, X.: Accelerating leveled fully homomorphic encryption using GPU. In: IEEE International Symposium on Circuits and Systems (ISCAS 2014), pp. 2800–2803. IEEE Press (2014)

Titel: On the Efficiency of Polynomial Multiplication for Lattice-Based Cryptography on GPUs Using CUDA
verfasst von: Sedat Akleylek
Özgur Dağdelen
Zaliha Yüce Tok
Verlag: Springer International Publishing
Buch: Cryptography and Information Security in the Balkans
Print ISBN: 978-3-319-29171-0

Electronic ISBN: 978-3-319-29172-7

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-319-29172-7_10

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner