nach oben

Applicable Algebra in Engineering, Communication and Computing

Erschienen in:

01.06.2014 | Original Paper

Sampling from discrete Gaussians for lattice-based cryptography on a constrained device

verfasst von: Nagarjun C. Dwarakanath, Steven D. Galbraith

Erschienen in: Applicable Algebra in Engineering, Communication and Computing | Ausgabe 3/2014

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Modern lattice-based public-key cryptosystems require sampling from discrete Gaussian (normal) distributions. The paper surveys algorithms to implement such sampling efficiently, with particular focus on the case of constrained devices with small on-board storage and without access to large numbers of external random bits. We review lattice encryption schemes and signature schemes and their requirements for sampling from discrete Gaussians. Finally, we make some remarks on challenges and potential solutions for practical lattice-based cryptography.

Nächster Artikel VSH and multiplicative modular relations between small primes with polynomial exponents

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 "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

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

As will be discussed later, even if \(\Pr (a)\) is very small then this only requires around two random input bits on average. But we do need to calculate the binary tree for the Knuth–Yao algorithm for each case, which seems inconvenient.

Since the parameter is \(9\) and so \(\sigma = 3.6\) we will actually only generate integers in the range \(| x_i | < 12 \sigma \approx 43\). Hence only 7 bits are needed to represent each entry of the vector and the storage can be reduced to about \(0.3\) Gb.

Arora, S., Ge, R.: New algorithms for learning in presence of errors, In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol. 6755, pp. 403–415. Springer, Heidelberg (2011)

Bai, S., Galbraith, S.D.: An improved compression technique for signatures based on learning with errors. In: J. Benaloh (ed.), CT-RSA 2014, pp. 28–47. Springer LNCS 8366 (2014)

Buchmann, J., Cabarcas, D., Göpfert, F., Hülsing, A., Weiden, P.: Discrete Ziggurat: a time-memory trade-off for sampling from a Gaussian distribution over the integers. In: Proceedings of SAC (2013, appear)

Detrey, J., de Dinechin, F.: Table-based polynomials for fast hardware function evaluation. In: Application-specific Systems, Architectures and Processors (ASAP 2005), IEEE, pp. 328–333 (2005)

Devroye, L.: Non-Uniform Random Variate Generation, Springer, New York (1986). http://www.nrbook.com/devroye/

de Dinechin, F., Tisserand, A.: Multipartite table methods. IEEE Trans. Comput. 54(3), 319–330 (2005)CrossRef

Ding, J.: Solving LWE problem with bounded errors in polynomial time, eprint 2010/558 (2010)

Ducas, L., Nguyen, P.Q.: Faster Gaussian lattice sampling using lazy floating-point arithmetic. In: Wang, X., Sako K. (eds.) ASIACRYPT 2012, pp. 415–432. Springer LNCS 7658 (2012)

Ducas, L., Durmus, A., Lepoint, T., Lyubashevsky, V.: Lattice Signatures and Bimodal Gaussians. In: Canetti R., Garay, J.A. (eds.) CRYPTO 2013, pp. 40–56. Springer LNCS 8042 (2013)

10.

Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Dwork C. (ed.), STOC 2008, pp. 197–206. ACM (2008)

11.

Güneysu, T., Lyubashevsky, V., Pöppelmann, T.: Practical lattice-based cryptography: a signature scheme for embedded systems. In: Prouff, E., Schaumont, P. (eds.) CHES 2012, pp. 530–547. Springer, LNCS 7428 (2012)

12.

Karney, C.F.F.: Sampling exactly from the normal distribution. arXiv:1303.6257 (2013)

13.

Knuth, D.E., Yao, A.C.: The complexity of non uniform random number generation. In: Traub, J.F. (ed.) Algorithms and Complexity, pp. 357–428. Academic Press, New York (1976)

14.

Lindner, R., Peikert, C.: Better key sizes (and attacks) for LWE-based encryption. In: Kiayias, A. (ed.) CT-RSA 2011, pp. 319–339. Springer, LNCS 6558 (2011)

15.

Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. In: Gilbert, H. (ed.), EUROCRYPT 2010, pp. 1–23. Springer, LNCS 6110 (2010)

16.

Lyubashevsky, V., Peikert, C., Regev, O.: A Toolkit for ring-LWE cryptography. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013, pp. 35–54. Springer LNCS 7881 (2013)

17.

Lyubashevsky, V.: Fiat-Shamir with aborts: applications to lattice and factoring-based signatures. In: Matsui, M. (ed.) ASIACRYPT 2009, pp. 598–616. Springer, LNCS 5912 (2009)

18.

Lyubashevsky, V.: Lattice Signatures without Trapdoors. In: Pointcheval, D., Johansson, T. (eds.), EUROCRYPT 2012, pp. 738–755. Springer, LNCS 7237 (2012)

19.

Micciancio, D., Peikert, C.: Trapdoors for lattices: simpler, tighter, faster, smaller. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012, pp. 700–718. Springer LNCS 7237 (2012)

20.

Muller, J.-M.: Elementary Functions, Algorithms and Implementation, 2nd edn. Birkhauser, Boston (2005)

21.

Olver, F.W.J., Lozier, D.W., Boisvert, R.F., Clark, C.W.: NIST Handbook of Mathematical Functions. Cambridge University Press, Cambridge (2010)MATH

22.

Peikert, C.: An efficient and parallel Gaussian sampler for lattices. In: Rabin, T. (ed.) CRYPTO 2010, pp. 80–97. Springer LNCS 6223 (2010)

23.

Regev, O.: On lattices, learning with errors, random linear codes, and cryptography, STOC 2005, pp. 84–93. ACM (2005)

24.

Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6), 34 (2009)CrossRefMathSciNet

25.

Sinha Roy, S., Vercauteren, F., Verbauwhede, I.: High precision discrete Gaussian sampling on FPGAs. In: Proceedings of SAC (2013, appear)

26.

Specker, W.H.: A class of algorithms for \(\ln x, \exp x, \sin x, \cos x, \tan ^{-1} x\), and \(\cot ^{-1} x\). IEEE Trans. Electron. Comput. EC–14(1), 85–86 (1965)CrossRef

Titel: Sampling from discrete Gaussians for lattice-based cryptography on a constrained device
verfasst von: Nagarjun C. Dwarakanath
Steven D. Galbraith
Publikationsdatum: 01.06.2014
Verlag: Springer Berlin Heidelberg
Erschienen in: Applicable Algebra in Engineering, Communication and Computing / Ausgabe 3/2014
Print ISSN: 0938-1279
Elektronische ISSN: 1432-0622
DOI: https://doi.org/10.1007/s00200-014-0218-3

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 "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3/2014

Erratum to: On the error linear complexity spectrum of $$p^{n}$$ p n -periodic binary sequences

An algorithm for computing the error sequence of $$p^{n}$$ p n -periodic binary sequences

VSH and multiplicative modular relations between small primes with polynomial exponents

The linear complexity of generalized cyclotomic sequences with period $$2p^n$$ 2 p n

Some results on the differential functions over finite fields

Premium Partner