nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Sharper Bounds in Lattice-Based Cryptography Using the Rényi Divergence

verfasst von : Thomas Prest

Erschienen in: Advances in Cryptology – ASIACRYPT 2017

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

The Rényi divergence is a measure of divergence between distributions. It has recently found several applications in lattice-based cryptography. The contribution of this paper is twofold.

First, we give theoretic results which renders it more efficient and easier to use. This is done by providing two lemmas, which give tight bounds in very common situations – for distributions that are tailcut or have a bounded relative error. We then connect the Rényi divergence to the max-log distance. This allows the Rényi divergence to indirectly benefit from all the advantages of a distance.

Second, we apply our new results to five practical usecases. It allows us to claim 256 bits of security for a floating-point precision of 53 bits, in cases that until now either required more than 150 bits of precision or were limited to 100 bits of security: rejection sampling, trapdoor sampling (61 bits in this case) and a new sampler by Micciancio and Walter. We also propose a new and compact approach for table-based sampling, and squeeze the standard deviation of trapdoor samplers by a factor that provides a gain of 30 bits of security in practice.

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 Coded-BKW with Sieving

Nächstes Kapitel Faster Packed Homomorphic Operations and Efficient Circuit Bootstrapping for TFHE

Nur mit Berechtigung zugänglich

[Str14] and https://www.imperialviolet.org/2016/11/28/cecpq1.html.

http://csrc.nist.gov/groups/ST/post-quantum-crypto/.

\((1+x/n)^n \le e^x\) for \(x,n>0\).

The call to a sampler over

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-70694-8_13/451390_1_En_13_IEq181_HTML.gif

is often done several times per query. In the context of signatures, we typically have \(m =\) the lattice dimension. Here we take \(m = 2^{10}\).

We note that the support is now

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-70694-8_13/451390_1_En_13_IEq216_HTML.gif

instead of

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-70694-8_13/451390_1_En_13_IEq217_HTML.gif

, but switching between the two cases is algorithmically easy.

Actually, storing the 11 elements as 64-bit integers yields better relative precision and is easier to handle in practice.

It is easy reduce any input z to the case \(|z| < 1/2\) by taking \(z' \leftarrow z \bmod (\ln 2)\) and observing that \(e^{\ln 2} = 2\). The precision loss is negligible.

For negative values, \(\exp \) may be computed by inversion, or if it is not available, by also precomputing \(\exp (-\frac{2^i}{2\sigma ^2})\).

If they did behave like perfect Gaussians when \(\sigma \rightarrow 0\), then they would effectively solve the closest vector problem, which is a NP-hard problem.

Or alternatively,

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-70694-8_13/451390_1_En_13_IEq472_HTML.gif

(see e.g. [Pei10, Lemma 5.2]).

As an example, for NTRU matrices, this is true up to a factor \(1.17^2\) [DLP14].

In a sense, this is what we did at the end of Sect. 4.2, as the algorithm 10 from [DDLL13] is meant to be used in conjunction with two other Algorithms (11 and 12).

[ABB10a]

Agrawal, S., Boneh, D., Boyen, X.: Efficient lattice (H)IBE in the standard model. In: Gilbert [Gil10], pp. 553–572

[ABB10b]

Agrawal, S., Boneh, D., Boyen, X.: Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE. In: Rabin [Rab10], pp. 98–115

[ADPS16]

Alkim, E., Ducas, L., Pöppelmann, T., Schwabe, P.: Post-quantum key exchange - a new hope. In: Holz, T., Savage, S. (eds.) 25th USENIX Security Symposium, USENIX Security 16, Austin, TX, USA, 10–12 August 2016, pp. 327–343. USENIX Association (2016)

[Ass06]

Van Assche, W.: Padé and hermite-padé approximation and orthogonality (2006)

[Bab85]

Babai, L.: On Lovász’ lattice reduction and the nearest lattice point problem. In: Mehlhorn, K. (ed.) STACS 1985. LNCS, vol. 182, pp. 13–20. Springer, Heidelberg (1985). https://doi.org/10.1007/BFb0023990 CrossRef

[Bab86]

Babai, L.: On lovasz’ lattice reduction and the nearest lattice point problem. Combinatorica 6(1), 1–13 (1986)MathSciNetCrossRefMATH

[BGG+14]

Boneh, D., Gentry, C., Gorbunov, S., Halevi, S., Nikolaenko, V., Segev, G., Vaikuntanathan, V., Vinayagamurthy, D.: Fully key-homomorphic encryption, arithmetic circuit ABE and compact garbled circuits. In: Nguyen and Oswald [NO14], pp. 533–556

[BGM+16]

Bogdanov, A., Guo, S., Masny, D., Richelson, S., Rosen, A.: On the hardness of learning with rounding over small modulus. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9562, pp. 209–224. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49096-9_9 CrossRef

[BLL+15]

Bai, S., Langlois, A., Lepoint, T., Stehlé, D., Steinfeld, R.: Improved security proofs in lattice-based cryptography: using the Rényi divergence rather than the statistical distance. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9452, pp. 3–24. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48797-6_1 CrossRef

[Boy10]

Boyen, X.: Lattice mixing and vanishing trapdoors: a framework for fully secure short signatures and more. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 499–517. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13013-7_29 CrossRef

[Boy13]

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

[BS16]

Bun, M., Steinke, T.: Concentrated differential privacy: simplifications, extensions, and lower bounds. In: Hirt, M., Smith, A. (eds.) TCC 2016. LNCS, vol. 9985, pp. 635–658. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53641-4_24 CrossRef

[Cac97]

Cachin, C.: Entropy measures and unconditional security in cryptography. Ph.D. thesis (1997)

[CHKP10]

Cash, D., Hofheinz, D., Kiltz, E., Peikert, C.: Bonsai trees, or how to delegate a lattice basis. In: Gilbert [Gil10], pp. 523–552

[DDLL13]

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

[DG14]

Dwarakanath, N.C., Galbraith, S.D.: Sampling from discrete gaussians for lattice-based cryptography on a constrained device. Appl. Algebra Eng. Commun. Comput. 25(3), 159–180 (2014)MathSciNetCrossRefMATH

[DLP14]

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

[DN12a]

Ducas, L., Nguyen, P.Q.: Faster Gaussian lattice sampling using lazy floating-point arithmetic. In: Wang and Sako [WS12], pp. 415–432

[DN12b]

Ducas, L., Nguyen, P.Q.: Learning a Zonotope and more: cryptanalysis of NTRUSign countermeasures. In: Wang and Sako [WS12], pp. 433–450

[DP16]

Ducas, L., Prest, T.: Fast fourier orthogonalization. In: Abramov, S.A., Zima, E.V., Gao, X.-S. (eds.) Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC 2016, Waterloo, ON, Canada, 19–22 July 2016, pp. 191–198. ACM (2016)

[EFGT17]

Espitau, T., Fouque, P.-A., Gérard, B., Tibouchi, M.: Generalized Howgrave-Graham-Szydlo and side-channel attacks against BLISS. Publication status unknown (2017). https://almasty.lip6.fr/~espitau/bin/SCBliss

[GGH97]

Goldreich, O., Goldwasser, S., Halevi, S.: Public-key cryptosystems from lattice reduction problems. In: Kaliski, B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 112–131. Springer, Heidelberg (1997). https://doi.org/10.1007/BFb0052231

[Gil10]

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

[GJSS01]

Gentry, C., Jonsson, J., Stern, J., Szydlo, M.: Cryptanalysis of the NTRU signature scheme (NSS) from Eurocrypt 2001. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 1–20. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45682-1_1 CrossRef

[GLP12]

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. LNCS, vol. 7428, pp. 530–547. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33027-8_31 CrossRef

[GPV08]

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

[GS02]

Gentry, C., Szydlo, M.: Cryptanalysis of the revised NTRU signature scheme. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 299–320. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-46035-7_20 CrossRef

[HHGP+03]

Hoffstein, J., Howgrave-Graham, N., Pipher, J., Silverman, J.H., Whyte, W.: NTRUSign: digital signatures using the NTRU lattice. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 122–140. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36563-X_9 CrossRef

[Kle00]

Klein, P.N.: Finding the closest lattice vector when it’s unusually close. In: SODA (2000)

[LD13]

Lepoint, T., Ducas, L.: Proof-of-concept software implementation of BLISS (2013). http://bliss.di.ens.fr/bliss-06-13-2013.zip

[LP15]

Lyubashevsky, V., Prest, T.: Quadratic time, linear space algorithms for Gram-Schmidt orthogonalization and Gaussian sampling in structured lattices. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 789–815. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46800-5_30

[LPSS14]

Ling, S., Phan, D.H., Stehlé, D., Steinfeld, R.: Hardness of k-LWE and applications in traitor tracing. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8616, pp. 315–334. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44371-2_18 CrossRef

[LSS14]

Langlois, A., Stehlé, D., Steinfeld, R.: GGHLite: more efficient multilinear maps from ideal lattices. In: Nguyen and Oswald [NO14], pp. 239–256

[Lyu09]

Lyubashevsky, V.: Fiat-Shamir with aborts: applications to lattice and factoring-based signatures. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 598–616. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10366-7_35 CrossRef

[Lyu12]

Lyubashevsky, V.: Lattice signatures without trapdoors. In: Pointcheval and Johansson [PJ12], pp. 738–755

[Mir17]

Mironov, I.: Renyi differential privacy. In: Proceedings of 30th IEEE Computer Security Foundations Symposium (2017). http://arxiv.org/abs/1702.07476

[MP12]

Micciancio, D., Peikert, C.: Trapdoors for lattices: simpler, tighter, faster, smaller. In: Pointcheval and Johansson [PJ12], pp. 700–718

[MR04]

Micciancio, D., Regev, O.: Worst-case to average-case reductions based on Gaussian measures. In: 45th FOCS, Rome, Italy, 17–19 October 2004, pp. 372–381. IEEE Computer Society Press (2004)

[MR07]

Micciancio, D., Regev, O.: Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput. 37, 267–302 (2007)MathSciNetCrossRefMATH

[MW17]

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

[NO14]

Nguyen, P.Q., Oswald, E. (eds.): EUROCRYPT 2014. LNCS, vol. 8441. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-55220-5

[NR06]

Nguyen, P.Q., Regev, O.: Learning a parallelepiped: cryptanalysis of GGH and NTRU signatures. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 271–288. Springer, Heidelberg (2006). https://doi.org/10.1007/11761679_17 CrossRef

[Pad92]

Padé, H.: Sur la représentation approchée d’une fonction par des fractions rationnelles. Ph.D. thesis (1892)

[PDG14]

Pöppelmann, T., Ducas, L., Güneysu, T.: Enhanced lattice-based signatures on reconfigurable hardware. In: Batina, L., Robshaw, M. (eds.) CHES 2014. LNCS, vol. 8731, pp. 353–370. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44709-3_20

[Pei10]

Peikert, C.: An efficient and parallel Gaussian sampler for lattices. In: Rabin [Rab10], pp. 80–97

[PJ12]

Pointcheval, D., Johansson, T. (eds.): EUROCRYPT 2012. LNCS, vol. 7237. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4 MATH

[POG15]

Pöppelmann, T., Oder, T., Güneysu, T.: High-performance ideal lattice-based cryptography on 8-bit ATxmega microcontrollers. In: Lauter, K., Rodríguez-Henríquez, F. (eds.) LATINCRYPT 2015. LNCS, vol. 9230, pp. 346–365. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-22174-8_19 CrossRef

[Pop14]

Poppelmann, T.: Proof-of-concept hardware implementation of BLISS (2014). https://www.sha.rub.de/media/attachments/files/2014/09/lattice_processor_final_publication.zip

[Pre15]

Prest, T.: Gaussian sampling in lattice-based cryptography. Theses, École Normale Supérieure December 2015

[Rab10]

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

[R61]

Rnyi, A.: On measures of entropy and information. In: Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics, Berkeley, California, pp. 547–561. University of California Press (1961)

[Saa15]

Saarinen, M.-J.O.: Gaussian sampling precision in lattice cryptography. Cryptology ePrint Archive, Report 2015/953 (2015). http://eprint.iacr.org/2015/953

[Str14]

Swan, S.: Bimodal lattice signature scheme (BLISS) (2014). https://wiki.strongswan.org/projects/strongswan/wiki/BLISS

[TT15]

Takashima, K., Takayasu, A.: Tighter security for efficient lattice cryptography via the Rényi divergence of optimized orders. In: Au, M.-H., Miyaji, A. (eds.) ProvSec 2015. LNCS, vol. 9451, pp. 412–431. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-26059-4_23

[vEH14]

van Erven, T., Harremoës, P.: IEEE Trans. Inf. Theory 60(7), 3797–3820 (2014)CrossRef

[Wan10]

Wan, A.: Learning, cryptography, and the average case. Ph.D. thesis, Columbia University (2010)

[WS12]

Wang, X., Sako, K. (eds.): ASIACRYPT 2012. LNCS, vol. 7658. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34961-4

Titel: Sharper Bounds in Lattice-Based Cryptography Using the Rényi Divergence
verfasst von: Thomas Prest
Verlag: Springer International Publishing
Buch: Advances in Cryptology – ASIACRYPT 2017
Print ISBN: 978-3-319-70693-1

Electronic ISBN: 978-3-319-70694-8

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-70694-8_13

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"