Gaussian Sampling in Lattice Based Cryptography

János Folláth

doi:10.2478/tmmp-2014-0022

Abstract

Modern lattice-based cryptosystems require sampling from discrete Gaussian distributions. We review lattice based schemes and collect their requirements for sampling from discrete Gaussians. Then we survey the algorithms implementing such sampling and assess their practical performance. Finally we draw some conclusions regarding the best candidates for implementation on different platforms in the typical parameter range

References

[1] MIKLÓS, A.: Generating hard instances of lattice problems, Electronic Colloquium on Computational Complexity (ECCC) 3 (1996), 29 p.
Search in Google Scholar
[2] AKAVIA, A.-GOLDWASSER, S.-VAIKUNTANATHAN, V: Simultaneous hardcore bits and cryptography against memory attacks, in: Theory of Cryptography, 6th Theory of Cryptography Conf.-TCC ’09, San Francisco, CA, USA, 2009 (O. Reingold, ed.), Lecture Notes in Comput. Sci., Vol. 5444, Springer, Berlin, 2009, pp. 474-495.
Search in Google Scholar
[3] ALWEN, J.-PEIKERT, CH.: Generating shorter bases for hard random lattices, in: 26th Internat. Symp. on Theoretical Aspects of Comput. Sci.-STACS ’09, Freiburg, Germany, 2009 (S. Albers et al., eds.), Leibniz Internat. Proc. in Informatics (LIPICS), Vol. 3, Schloss Dagstuhl - Leibniz Zentrum f¨ur Informatik, Wadern, 2009, pp. 75-86 (electronic only).
Search in Google Scholar
[4] BABAI, L.: On Lov´asz’ lattice reduction and the nearest lattice point problem, Combinatorica 6 (1986), 1-13.10.1007/BF02579403
Search in Google Scholar
[5] BAI, SH.-GALBRAITH, S. D.: An improved compression technique for signatures based on learning with errors, in: Topics in Cryptology-CT-RSA ’14, The Cryptographer’s Track at the RSA Conf. 2014, San Francisco, CA, USA, 2014 (J. Benaloh, ed.), Lecture Notes in Comput. Sci., Vol. 8366, Springer, Berlin, 2014, pp. 28-47.
Search in Google Scholar
[6] BELLARE, M.-ROGAWAY, P.: Random oracles are practical: A paradigm for designing efficient protocols, in: Proc. of the 1st ACM Conf. on Computer and Communications Security-CCS ’93, ACM, New York, NY, USA, 1993, pp. 62-73.10.1145/168588.168596
Search in Google Scholar
[7] BUCHMANN, J.-CABARCAS, D.-G¨OPFERT, F.-H¨ULSING, A.-WEIDEN, P.: Discrete Ziggurat: A time-memory trade-off for sampling from a Gaussian distribution over the integers, in: Selected Areas in Cryptography-SAC ’13, Burnaby, BC, Canada, 2013 (P. Lisonek et al., eds.), Lecture Notes in Comput. Sci., Vol. 8282, Springer, Berlin, 2013, pp. 402-417.
Search in Google Scholar
[8] DETREY, J.-DE DINECHIN, F.: Table-based polynomials for fast hardware function evaluation, in: Application-Specific Systems, Architecture Processors-ASAP ’05, 16th IEEE Internat. Conf., EEE Computer Society Washington, DC, USA, 2005, pp. 328-333.
Search in Google Scholar
[9] DEVROYE, L.: Non-Uniform Random Variate Generation. Springer, New York, 1986.10.1007/978-1-4613-8643-8
Search in Google Scholar
[10] DIFFIE, W.-HELLMAN, M.: New directions in cryptography, IEEE Trans. Inform. Theory 22 (2006), 644-654.10.1109/TIT.1976.1055638
Search in Google Scholar
[11] DUCAS, L.-NGUYEN, P. Q.: Faster Gaussian lattice sampling using lazy floating-point arithmetic, in: Advances in Cryptology-ASIACRYPT ’12, 18th Internat. Conf. on the Theory and Appl. of Crypt. and Inform. Security, Beijing, China, 2012 (X. Wang et al., eds.), Lecture Notes in Comput. Sci., Vol. 7658, Springer, Berlin, 2012, pp. 415-432.
Search in Google Scholar
[12] DUCAS, L.-DURMUS, A.-LEPOINT, T.-LYUBASHEVSKY, V.: Lattice signatures and bimodal gaussians, in: Advances in Cryptology-CRYPTO ’13, 33rd Annual Cryptology Conf., Santa Barbara, CA, USA, 2013 (R. Canetti et al., eds.), Lecture Notes in Comput. Sci., Vol. 8042, Springer, Berlin, 2013, pp. 40-56.
Search in Google Scholar
[13] DUCAS, L.-NGUYEN, P. Q.: Learning a zonotope and more: Cryptanalysis of NTRUSign countermeasures, in: Advances in Cryptology-ASIACRYPT ’12, 18th Internat. Conf. on the Theory and Appl. of Cryptology and Information Security, Beijing, China, 2012 (X. Wang and K. Sako, eds.), Lecture Notes in Comput. Sci., Vol. 7658, Springer, Berlin, 2012, pp. 433-45010.1007/978-3-642-34961-4_27
Search in Google Scholar
[14] DWARAKANATH, N. C.-GALBRAITH, S. D.: Sampling from discrete gaussians for lattice-based cryptography on a constrained device, Appl. Algebra Engrg. Comm. Comput. 25 (2014), 159-180.10.1007/s00200-014-0218-3
Search in Google Scholar
[15] GENTRY, C.-PEIKERT, CH.-VAIKUNTANATHAN, V.: Trapdoors for hard lattices and new cryptographic constructions, in: Proc. of the 40th Annual ACM Symp. on Theory of Computing-STOC ’08, Victoria, Canada, ACM, New York, 2008, pp. 197-206.10.1145/1374376.1374407
Search in Google Scholar
[16] GENTRY, C.-SZYDLO, M.: Cryptanalysis of the revised NTRU signature scheme, in: Advances in Cryptology-EUROCRYPT ’02, 21st Internat. Conf. on the Theory and Appl. of Cryptographic Techniques, Amsterdam, the Netherlands, 2002 (L. Knudsen, ed.), Lecture Notes in Comput. Sci., Vol. 2332, Springer, Berlin, 2002, pp. 299-320.
Search in Google Scholar
[17] GÜNEYSU, T.-LYUBASHEVSKY, V.-P¨OPPELMANN, TH.: Practical lattice-based cryptography: A signature scheme for embedded systems, in: Cryptographic Hardware and Embedded Systems-CHES ’12, 14th Internat. Workshop, Leuven, Belgium, 2012, (E. Prouff and P. Schaumont, eds.), Lecture Notes in Comput. Sci., Vol. 7428, Springer, Berlin, 2012, pp. 530-547.
Search in Google Scholar
[18] GOLDREICH, O.-GOLDWASSER, SH.-HALEVI, SH.: Public-key cryptosystems from lattice reduction problems, in: Advances in Cryptology-CRYPTO ’97, 17th Annual Internat. Cryptology Conf., Santa Barbara, CA, USA, 1997, (B. S. Kaliski, jr., ed.), Lecture Notes in Comput. Sci., Vol. 1294, Springer, Berlin, 1997, pp. 112-131.
Search in Google Scholar
[19] HOFFSTEIN, J.-HOWGRAVE-GRAHAM, N.-PIPHER, J.-SILVERMAN, J. H.- -WHYTE, W.: NTRUSign: Digital signatures using the NTRU lattice, in: Topics in Cryptology-CT-RSA ’03, The Cryptographers’ Track at the RSA Conf., San Francisco, CA, USA, 2003 (M. Joye, ed.), Lecture Notes in Comput. Sci., Vol. 2612, Springer, Berlin, 2003, pp. 122-140.
Search in Google Scholar
[20] HOFFSTEIN, J.-PIPHER, J.-SILVERMAN, J. H.: Nss: An ntru lattice-based signature scheme, in: Advances in Cryptology-EUROCRYPT ’01, Internat. Conf. on the Theory and Appl. of Cryptographic Tech., Innsbruck, Austria, 2001 (B. Pfitzmann, ed.), Lecture Notes in Comput. Sci., Vol. 2045, Springer, Berlin, 2001, pp. 211-228.
Search in Google Scholar
[21] KARNEY, C. F. F.: Sampling exactly from the normal distribution, 2014, http://arxiv.org/abs/1303.6257.
Search in Google Scholar
[22] KAWACHI, A.-TANAKA, K.-XAGAWA, K.: Multi-bit cryptosystems based on lattice problems, in: Public Key Cryptography-PKC ’07, 10th Internat. Conf. on Practice and Theory in Public-Key Cryptography, Beijing, China, 2007 (T. Okamoto et al., eds.), Lecture Notes in Comput. Sci., Vol. 4450, Springer, Berlin, 2007, pp. 315-329.
Search in Google Scholar
[23] KLEIN, P.: Finding the closest lattice vector when it’s unusually close, in: Proc. of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA, 2000, SIAM, Philadelphia, PA, 2000, pp. 937-941.
Search in Google Scholar
[24] KNUTH, D. E.-YAO, A. C.: The complexity of nonuniform random number generation, in: Algorithms and Complexity: New Directions and Recent Results, Pittsburgh, 1976 (J. F. Traub, ed.), Academic Press, New York, 1976.
Search in Google Scholar
[25] LINDNER, R.-PEIKERT, CH.: Better key sizes (and attacks) for lwe-based encryption, in: Topics in cryptology-CT-RSA ’11, The Cryptographers’ Track at the RSA Conf., 2011, San Francisco, CA, USA, 2011, (A. Kiayias, ed.), Lecture Notes in Comput. Sci., Vol. 6558, Springer, Berlin, 2011, pp. 319-339 10.1007/978-3-642-19074-2_21
Search in Google Scholar
[26] LYUBASHEVSKY, V.: Fiat-shamir with aborts: Applications to lattice and factoringbased signatures, in: Advances in Cryptology-ASIACRYPT ’09, 15th Internat. Conf. on the Theory and Appl. of Cryptology and Inform. Security, Tokyo, Japan, 2009 (M. Matsui, ed.), Lecture Notes in Comput. Sci., Vol. 5912, Springer, Berlin, 2009, pp. 598-616.
Search in Google Scholar
[27] LYUBASHEVSKY, V.: Lattice signatures without trapdoors, in: Advances in Cryptology- -EUROCRYPT ’12, 31st Annual Internat. Conf. on the Theory and Appl. of Cryptographic Techniques, Cambridge, UK, 2012 (D. Pointcheval and Th. Johansson, eds.), Lecture Notes in Comput. Sci., Vol. 7237, Springer, Berlin, 2012, pp. 738-755.
Search in Google Scholar
[28] LYUBASHEVSKY, V.-PEIKERT, CH.-REGEV, O.: On ideal lattices and learning with errors over rings, in: Advances in Cryptology-EUROCRYPT ’10, 29th Annual Internat. Conf. on the Theory and Appl. of Cryptographic Techniques, French Riviera, 2010 (H. Gilbert, ed.), Lecture Notes in Comput. Sci., Vol. 6110, Springer, Berlin, 2010, pp. 1-23.
Search in Google Scholar
[29] MARSAGLIA, G.-TSANG, W. W.: The ziggurat method for generating random variables, J. Statist. Software 5 (2000), 1-7.10.18637/jss.v005.i08
Search in Google Scholar
[30] MICCIANCIO, D.-PEIKERT, CH.: Trapdoors for lattices: Simpler, tighter, faster, smaller, in: in: Advances in Cryptology-EUROCRYPT ’12, 31st Annual Internat. Conf. on the Theory and Appl. of Cryptographic Techniques, Cambridge, UK, 2012 (D. Pointcheval and Th. Johansson, eds.), Lecture Notes in Comput. Sci., Vol. 7237, Springer, Berlin, 2012, pp. 700-718.
Search in Google Scholar
[31] MICCIANCIO, D.-REGEV, O.: Worst-case to average-case reductions based on gaussian measures, SIAM J. Comput. 37 (2007), 267-302.10.1137/S0097539705447360
Search in Google Scholar
[32] MULLER, J.-M.: Elementary Functions. Algorithms and Implementation. Birkh¨auser, Boston, 1997.
Search in Google Scholar
[33] NGUYEN, P. Q.-REGEV, O.: Learning a parallelepiped: Cryptanalysis of ggh and ntru signatures, in: Advances in Cryptology-EUROCRYPT ’06, 25th Annual Internat. Conf. on the Theory and Appl. of Cryptographic Techniques, St. Petersburg, Russia, 2006 (S. Vaudenay, ed.), Lecture Notes in Comput. Sci., Vol. 4004, Springer, Berlin, 2006, pp. 271-288.
Search in Google Scholar
[34] NGUYEN, P. Q.-REGEV, O.: Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures, J. Cryptology 22 (2009), 139-160.10.1007/s00145-008-9031-0
Search in Google Scholar
[35] OLVER, F. W.-LOZIER, D. W.-BOISVERT, R. F.-CLARK, CH. W.: NIST Handbook of Mathematical Functions. Cambridge University Press, Cambridge, 2010.
Search in Google Scholar
[36] PEIKERT, CH.: An efficient and parallel gaussian sampler for lattices, in: Advances in Cryptology-CRYPTO ’10, 30th Annual Cryptology Conf., Santa Barbara, CA, USA, 2010 (T. Rabin, ed.), Lecture Notes in Comput. Sci., Vol. 6223, Springer, Berlin, 2010, pp. 80-97.
Search in Google Scholar
[37] PEIKERT, CH.: Public-key cryptosystems from the worst-case shortest vector problem: Extended abstract, in: Proc. of the 41 Annual ACM Symp. on Theory of Comput.- -STOC ’09, ACM, New York, NY, USA, 2009, pp. 333-342.10.1145/1536414.1536461
Search in Google Scholar
[38] PEIKERT, CH.-VAIKUNTANATHAN, V.-WATERS, B.: A framework for efficient and composable oblivious transfer, in: Advances in Cryptology-CRYPTO ’08, 28th Annual Internat. Cryptology Conf., Santa Barbara, CA, USA, 2008 (D.Wagner, ed.), Lecture Notes in Comput. Sci., Vol. 5157, 554-571 (2008) Springer, Berlin, 2008, pp. 554-571.
Search in Google Scholar
[39] REGEV, O.: On lattices, learning with errors, random linear codes, and cryptography, in: Proc. of the 37th Annual ACM Symp. on Theory of Computing-STOC ’05, Baltimore, MD, USA, 2005, ACM, New York, NY, pp. 84-93.10.1145/1060590.1060603
Search in Google Scholar
[40] ROY, S. S.-VERCAUTEREN, F.-VERBAUWHEDE, I.: High precision discrete gaussian sampling on FPGAs, in: Selected Areas in Cryptography-SAC ’13, 20th Internat. Conf., Burnaby, BC, Canada, 2013 (T. Lange et al., eds.), Lecture Notes in Comput. Sci., Vol. 8282, Springer, Berlin, 2013, pp. 383-401.
Search in Google Scholar
[41] SHOUP, V.: NTL: A library for doing number theory, 2013, www.shoup.net/ntl.
Search in Google Scholar
[42] SPECKER, W. H.: A class of algorithms for ln x, exp x, sin x, cos x, tan−1 x, and cot−1 x, in: j-IEEE-trans-elec-comput, EC-14(1):85-86, 1965.10.1109/PGEC.1965.264066
Search in Google Scholar
[43] WEIDEN, P.-H¨ULSING, A.-CABARCAS, D.-BUCHMANN, J.: Instantiating treeless signature schemes, Cryptology ePrint Archive 65:1-18, 2013
Search in Google Scholar

Gaussian Sampling in Lattice Based Cryptography

Abstract

Paradigm

My account