nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography

verfasst von : Nicholas Genise, Daniele Micciancio, Chris Peikert, Michael Walter

Erschienen in: Public-Key Cryptography – PKC 2020

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

Discrete Gaussian distributions over lattices are central to lattice-based cryptography, and to the computational and mathematical aspects of lattices more broadly. The literature contains a wealth of useful theorems about the behavior of discrete Gaussians under convolutions and related operations. Yet despite their structural similarities, most of these theorems are formally incomparable, and their proofs tend to be monolithic and written nearly “from scratch,” making them unnecessarily hard to verify, understand, and extend.

In this work we present a modular framework for analyzing linear operations on discrete Gaussian distributions. The framework abstracts away the particulars of Gaussians, and usually reduces proofs to the choice of appropriate linear transformations and elementary linear algebra. To showcase the approach, we establish several general properties of discrete Gaussians, and show how to obtain all prior convolution theorems (along with some new ones) as straightforward corollaries. As another application, we describe a self-reduction for Learning With Errors (LWE) that uses a fixed number of samples to generate an unlimited number of additional ones (having somewhat larger error). The distinguishing features of our reduction are its simple analysis in our framework, and its exclusive use of discrete Gaussians without any loss in parameters relative to a prior mixed discrete-and-continuous approach.

As a contribution of independent interest, for subgaussian random matrices we prove a singular value concentration bound with explicitly stated constants, and we give tighter heuristics for specific distributions that are commonly used for generating lattice trapdoors. These bounds yield improvements in the concrete bit-security estimates for trapdoor lattice cryptosystems.

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 On QA-NIZK in the BPK Model

Nächstes Kapitel Almost Tight Security in Lattices with Polynomial Moduli – PRF, IBE, All-but-many LTF, and More

https://csrc.nist.gov/Projects/Post-Quantum-Cryptography.

Our security analysis is a simple BKZ estimate, which is not a state-of-the-art concrete security analysis. However, we are only interested in the change in concrete security when changing from previous bounds to our new ones. Our point is that the underlying SIS problem is slightly harder in this trapdoor lattice regime than previously thought.

Of course, one can view the discrete Gaussian as a randomly rounded continuous one, but this is equivalent to the indirect, loose approach described above.

The pseudoinverse can also be defined for arbitrary matrices, but the definition is more complex, and we will not need this level of generality.

Notice that it is possible for \(\varSigma \succeq \varSigma '\) and \(\varSigma \ne \varSigma '\), and still \(\varSigma \not \succ \varSigma '\).

Clearly, \(\mathbf {T} \varLambda \) is an additive group, and it is not too difficult to show that \(\mathbf {T} \varLambda \) has a minimal nonzero element (i.e., it is discrete), so it is a lattice.

To see this, notice that the probability under \(\mathbf {S}(\mathcal {D})\) of any vector \(\varSigma \mathbf {x} \in \mathrm {span}(\mathbf {S}\mathbf {S}^t) = \mathrm {span}(\mathbf {S})\) in its support is \(\rho (\{{\mathbf {z} : \mathbf {S}\mathbf {z} = \varSigma \mathbf {x}}\}) = \rho (\mathbf {T}^t\mathbf {x} + \ker (\mathbf {S})) = \rho (\mathbf {S}^t\mathbf {x})\cdot \rho (\ker (\mathbf {T}))\) because \(\mathbf {S}^t\mathbf {x}\) is orthogonal to \(\ker (\mathbf {S})=\{{\mathbf {z} : \mathbf {S}\mathbf {z} = \mathbf {0}}\}\). Moreover, \(\rho (\ker (\mathbf {S})) = 1\) and \(\rho (\mathbf {S}^t\mathbf {x}) = \rho (\Vert \mathbf {S}^t\mathbf {x}\Vert ) = \rho (\sqrt{\mathbf {x}^t\varSigma \mathbf {x}})\) depends only on \(\varSigma \).

For any nonempty set A with zero measure, one can first define \(A_\varepsilon = A + \{\mathbf {x} :\Vert \mathbf {x}\Vert < \varepsilon \}\), which has nonzero measure for any \(\varepsilon >0\). Then, \([\mathcal {D}_{\mathbf {S}}]_A\) is defined as the limit of \([\mathcal {D}_{\mathbf {S}}]_{A_\varepsilon }\) as \(\varepsilon \rightarrow 0\), if this limit exists.

For example, if \(\varLambda \) is the lattice generated by the vectors (1, 0) and \((\sqrt{2},1)\), and \(\mathbf {T}(x,y) = x\) is the projection on the first coordinate, then \(\mathbf {T} \varLambda = \mathbb {Z}+\sqrt{2}\mathbb {Z}\) is a countable but dense subset of \(\mathbb {R}\). In particular, \(\sum _{x \in \mathbf {T} \varLambda } \rho (x) = \infty \) and so the conditional distribution \(\mathcal {D}_{\mathbf {T}\varLambda , \mathbf {T}}\) is not well defined.

A principal minor of a matrix is the determinant of a square submatrix obtained by removing the rows and columns having the same index set.

Trapdoor inversions are independent samples of the form \(\mathbf {x} \leftarrow \mathcal {D}_{\mathbf {y}^* + \varLambda _{q}^\perp (\mathbf {A}), s}\).

See [MP12, Section 3.4] for the further details.

Sieving in dimension k has heuristic time-complexity \(2^{.292k+16.4}\) [BDGL16].

We use this simplistic method to estimate security since we are interested in the difference in concrete security. More sophisticated methods to estimate the concrete security of lattice-based schemes can be found in [Duc18, ADH+19].

[ACD+18]

Albrecht, M.R., et al.: Estimate all the LWE, NTRU schemes! In: SCN, pp. 351–367 (2018)

[ACPS09]

Applebaum, B., Cash, D., Peikert, C., Sahai, A.: Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 595–618. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03356-8_35CrossRef

[ADH+19]

Albrecht, M.R., Ducas, L., Herold, G., Kirshanova, E., Postlethwaite, E.W., Stevens, M.: The general sieve kernel and new records in lattice reduction. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019, Part 2. LNCS, vol. 11477, pp. 717–746. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17656-3_25CrossRefMATH

[AGHS13]

Agrawal, S., Gentry, C., Halevi, S., Sahai, A.: Discrete Gaussian leftover hash lemma over infinite domains. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part 1. LNCS, vol. 8269, pp. 97–116. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-42033-7_6CrossRef

[Ajt96]

Ajtai, M.: Generating hard instances of lattice problems. Quaderni di Matematica 13, 1–32 (2004). Preliminary version in STOC 1996MathSciNetMATH

[AP09]

Alwen, J., Peikert, C.: Generating shorter bases for hard random lattices. In: STACS, pp. 75–86 (2009)

[APS15]

Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. J. Math. Cryptol. 9(3), 169–203 (2015)MathSciNetCrossRef

[AR16]

Aggarwal, D., Regev, O.: A note on discrete Gaussian combinations of lattice vectors. Chicago J. Theor. Comput. Sci. (2016)

[BDGL16]

Becker, A., Ducas, L., Gama, N., Laarhoven, T.: New directions in nearest neighbor searching with applications to lattice sieving. In: SODA, pp. 10–24 (2016)

[BF11]

Boneh, D., Freeman, D.M.: Linearly homomorphic signatures over binary fields and new tools for lattice-based signatures. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.) PKC 2011. LNCS, vol. 6571, pp. 1–16. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19379-8_1CrossRef

[BPMW16]

Bourse, F., Del Pino, R., Minelli, M., Wee, H.: FHE circuit privacy almost for free. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part 2. LNCS, vol. 9815, pp. 62–89. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53008-5_3CrossRef

[CGM19]

Chen, Y., Genise, N., Mukherjee, P.: Approximate trapdoors for lattices and smaller hash-and-sign signatures. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019, Part 3. LNCS, vol. 11923, pp. 3–32. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34618-8_1CrossRef

[Che13]

Chen, Y.: Réduction de réseau et sécurité concréte du chiffrement complétement homomorphe. Ph.D. thesis, Paris 7 (2013)

[DDLL13]

Ducas, L., Durmus, A., Lepoint, T., Lyubashevsky, V.: Lattice signatures and bimodal Gaussians. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part 1. LNCS, vol. 8042, pp. 40–56. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_3CrossRef

[DGPY19]

Ducas, L., Galbraith, S., Prest, T., Yu, Y.: Integral matrix Gram root and lattice Gaussian sampling without floats. Cryptology ePrint Archive, Report 2019/320 (2019). https://eprint.iacr.org/2019/320

[DLP14]

Ducas, L., Lyubashevsky, V., Prest, T.: Efficient identity-based encryption over NTRU lattices. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014, Part 2. LNCS, vol. 8874, pp. 22–41. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45608-8_2CrossRef

[Duc18]

Ducas, L.: Shortest vector from lattice sieving: a few dimensions for free. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part 1. LNCS, vol. 10820, pp. 125–145. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78381-9_5CrossRef

[Gen09]

Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC, pp. 169–178 (2009)

[GM18]

Genise, N., Micciancio, D.: Faster Gaussian sampling for trapdoor lattices with arbitrary modulus. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part 1. LNCS, vol. 10820, pp. 174–203. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78381-9_7CrossRef

[GPV08]

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

[LPR13]

Lyubashevsky, V., Peikert, C., Regev, O.: A toolkit for ring-LWE cryptography. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 35–54. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38348-9_3CrossRef

[MG02]

Micciancio, D., Goldwasser, S.: Complexity of Lattice Problems - A Cryptographic Perspective. The Kluwer International Series in Engineering and Computer Science, vol. 671. Springer, Heidelberg (2002). https://doi.org/10.1007/978-1-4615-0897-7CrossRefMATH

[MP12]

Micciancio, D., Peikert, C.: Trapdoors for lattices: simpler, tighter, faster, smaller. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 700–718. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_41CrossRef

[MP13]

Micciancio, D., Peikert, C.: Hardness of SIS and LWE with small parameters. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part 1. LNCS, vol. 8042, pp. 21–39. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_2CrossRef

[MR04]

Micciancio, D., Regev, O.: Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput. 37(1), 267–302 (2007). Preliminary version in FOCS 2004MathSciNetCrossRef

[MW17]

Micciancio, D., Walter, M.: Gaussian sampling over the integers: efficient, generic, constant-time. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part 2. LNCS, vol. 10402, pp. 455–485. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63715-0_16CrossRef

[MW18]

Micciancio, D., Walter, M.: On the bit security of cryptographic primitives. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part 1. LNCS, vol. 10820, pp. 3–28. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78381-9_1CrossRef

[Pei10]

Peikert, C.: An efficient and parallel Gaussian sampler for lattices. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 80–97. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_5CrossRef

[Reg05]

Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6), 1–40 (2009). Preliminary version in STOC 2005MathSciNetCrossRef

[SE94]

Schnorr, C., Euchner, M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Program. 66, 181–199 (1994)MathSciNetCrossRef

[Ver12]

Vershynin, R.: Introduction to the non-asymptotic analysis of random matrices. In: Compressed Sensing, pp. 210–268. Cambridge University Press (2012)

[Ver18]

Vershynin, R.: High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press (2018)

Titel: Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography
verfasst von: Nicholas Genise
Daniele Micciancio
Chris Peikert
Michael Walter
Verlag: Springer International Publishing
Buch: Public-Key Cryptography – PKC 2020
Print ISBN: 978-3-030-45373-2

Electronic ISBN: 978-3-030-45374-9

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-45374-9_21

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"