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

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)

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)

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)

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)

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

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)

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)

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)

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)

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)

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

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)

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

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

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

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

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

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

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