nach oben

Erschienen in:

2021 | OriginalPaper | Buchkapitel

Exact Lattice Sampling from Non-Gaussian Distributions

verfasst von : Maxime Plançon, Thomas Prest

Erschienen in: Public-Key Cryptography – PKC 2021

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

We propose a new framework for (trapdoor) sampling over lattices. Our framework can be instantiated in a number of ways. It allows for example to sample from uniform, affine and “product affine” distributions. Another salient point of our framework is that the output distributions of our samplers are perfectly indistinguishable from ideal ones, in contrast with classical samplers that are statistically indistinguishable. One caveat of our framework is that all our current instantiations entail a rather large standard deviation.

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 Master-Key KDM-Secure ABE via Predicate Encoding

Nächstes Kapitel Efficient Adaptively-Secure IB-KEMs and VRFs via Near-Collision Resistance

Nur mit Berechtigung zugänglich

It has been conjectured by Voronoi [35] that every parallelohedron \(\mathcal {T}\subset \mathcal {R}^n\) is affine equivalent to the Voronoi cell of some lattice \(\mathcal {L}' \subset \mathcal {R}^n\).

From a practical viewpoint, one can think of the trapdoor as a short basis. The trapdoor can contain more information, such as the Gram-Schmidt orthogonalization (or GSO) of the basis, or any precomputation on the lattice.

The difference with uniform is that in general the integrals of f over \(\varOmega \backslash (\mathcal {L}\cap \varOmega + \mathcal {T})\) and \((\mathcal {L}\cap \varOmega + \mathcal {T}) \cap (\varOmega '\backslash \varOmega )\) do not compensate each other.

Remind that testing that a vector is in the set \(\varOmega \) has to be easy. In the examples we develop, such a test reduces to computing an \(\ell _p\) norm for p in \(\lbrace 1,2,\infty \rbrace \), and an inequality.

For example, although it does not use trapdoor sampling, the signature scheme Dilithium [17] relies for its security on the MSIS problem with the \(\ell _{\infty }\) norm.

Aggarwal, D., Dadush, D., Regev, O., Stephens-Davidowitz, N.: Solving the shortest vector problem in \(2^n\) time using discrete Gaussian sampling: Extended abstract. In: Servedio, R.A., Rubinfeld, R., (eds.) 47th ACM STOC, pp. 733–742. ACM Press (2015)

Aggarwal, D., Dadush, D., Stephens-Davidowitz, N.: Solving the closest vector problem in \(2^n\) time - the discrete Gaussian strikes again! In: Guruswami, V. (eds.) 56th FOCS, pp. 563–582. IEEE Computer Society Press (2015)

Agrawal, S., Boneh, D., Boyen, X.: Efficient lattice (H)IBE in the standard model. In: Gilbert, H. (ed.) EUROCRYPT 2010, vol. 6110, pp. 553–572. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_28CrossRef

Agrawal, S., Boneh, D., Boyen, X.: Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 98–115. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_6CrossRefMATH

Alazard, T.: Analyse et équations aux dérivées partielles (2017)

Alkim, E., Ducas, L., Pöppelmann, T., Schwabe, P.: Post-quantum key exchange - a new hope. In: Holz, T., Savage, S. (eds.) USENIX Security 2016, pp. 327–343. USENIX Association (2016)

Babai, L.: On lovász’lattice reduction and the nearest lattice point problem. Combinatorica 6(1), 1–13 (1986)MathSciNetCrossRef

Barthe, F., Guédon, O., Mendelson, S., Naor, A., et al.: A probabilistic approach to the geometry of the pn-ball. Ann. Probabil. 33(2), 480–513 (2005)CrossRef

Bos, J.W., et al.: Frodo: take off the ring! practical, quantum-secure key exchange from LWE. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 2016, pp. 1006–1018. ACM Press (2016)

10.

Boyen, X.: Attribute-based functional encryption on lattices. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 122–142. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36594-2_8CrossRef

11.

Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehlé, D.: Classical hardness of learning with errors. In: Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.) 45th ACM STOC, pp. 575–584. ACM Press (2013)

12.

Cash, D., Hofheinz, D., Kiltz, E., Peikert, C.: Bonsai trees, or how to delegate a lattice basis. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 523–552. Springer, Berlin, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_27CrossRef

13.

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. LNCS, vol. 11923, pp. 3–32. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-030-34618-8_1CrossRef

14.

Conway, J.H., Sloane, N.J.A.: Low-dimensional lattices. vi. voronoi reduction of three-dimensional lattices. Proc. R. Soc. Lond. Ser. A: Math. Phys. Sci. 436(1896), 55–68 (1992)

15.

Cumbus, C.: Uniform sampling in the hypersphere via latent variables and the Gibbs sampler (1996)

16.

Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schwabe, P., Seiler, G., Stehlé, D.: CRYSTALS-Dilithium: a lattice-based digital signature scheme. IACR TCHES 2018(1), 238–268 (2018). https://tches.iacr.org/index.php/TCHES/article/view/839

17.

Ducas, L., Lepoint, T., Lyubashevsky, V., Schwabe, P., Seiler, G., Stehlé, D: Crystals-dilithium: Digital signatures from module lattices (2018)

18.

Ducas, L., Nguyen, P.Q.: Faster Gaussian lattice sampling using lazy floating-point arithmetic. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 415–432. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34961-4_26CrossRef

19.

Espitau, T., Fouque, P.-A., Gérard, B., Tibouchi, M.: Side-channel attacks on BLISS lattice-based signatures: exploiting branch tracing against strongSwan and electromagnetic emanations in microcontrollers. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017, pp. 1857–1874. ACM Press (2017)

20.

Fouque, P.-A., Kirchner, P., Tibouchi, M., Wallet, A., Yang, Yu.: Key recovery from Gram-Schmidt norm leakage in hash-and-sign signatures over NTRU lattices. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. Lecture Notes in Computer Science, vol. 12107, pp. 34–63. Springer, Heidelberg (2020). https://doi.org/10.1007/978-3-030-45727-3_2CrossRef

21.

Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Ladner, R.E., Dwork, C. (eds.) 40th ACM STOC, pp. 197–206. ACM Press (2008)

22.

Gilbert, H. (ed.): Advances in Cryptology – EUROCRYPT 2010. LNCS, vol. 6110. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5 CrossRefMATH

23.

Klein, P.N.: Finding the closest lattice vector when it’s unusually close. In: Shmoys, D.B. (ed.) 11th SODA, pp. 937–941. ACM-SIAM (2000)

24.

Lieb, E.H., Loss, M., Loss, M.A., American Mathematical Society: Analysis. Crm Proceedings & Lecture Notes. American Mathematical Society (2001)

25.

Lyubashevsky, V., Wichs, D.: Simple lattice trapdoor sampling from a broad class of distributions. In: Katz, J. (ed.) PKC 2015. LNCS, vol. 9020, pp. 716–730. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46447-2_32CrossRef

26.

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)CrossRef

27.

Muscalu, C., Schlag, W.: Harmonic functions; poisson kernel. Cambridge Studies in Advanced Mathematics, vol. 1, pp. 28–51. Cambridge University Press (2013)

28.

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

29.

Prest, T.: Sharper bounds in lattice-based cryptography using the Rényi divergence. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017, Part I. LNCS, vol. 10624, pp. 347–374. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-319-70694-8_13CrossRef

30.

Rabin, T. (ed.): CRYPTO 2010. LNCS, vol. 6223. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7CrossRefMATH

31.

Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow, H.N., Fagin, R. (eds.) 37th ACM STOC, pp. 84–93. ACM Press (2005)

32.

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

33.

Shao, M.-Z., Badler, N.: Spherical sampling by archimedes’ theorem. Technical reports (CIS), pp. 184 (1996)

34.

Stein, E.M., Murphy, T.S., Princeton University Press: Harmonic Analysis: Real-variable Methods, Orthogonality, and Oscillatory Integrals. Monographs in harmonic analysis. Princeton University Press (1993)

35.

Voronoi, G.: Nouvelles applications des paramètres continus à la théorie des formes quadratiques. deuxième mémoire. recherches sur les parallélloèdres primitifs. Journal für die reine und angewandte Mathematik 134, 198–287 (1908)

Titel: Exact Lattice Sampling from Non-Gaussian Distributions
verfasst von: Maxime Plançon
Thomas Prest
Verlag: Springer International Publishing
Buch: Public-Key Cryptography – PKC 2021
Print ISBN: 978-3-030-75244-6

Electronic ISBN: 978-3-030-75245-3

Copyright-Jahr: 2021
DOI: https://doi.org/10.1007/978-3-030-75245-3_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"