nach oben

Journal of Cryptology

Erschienen in:

28.08.2017

Improved Security Proofs in Lattice-Based Cryptography: Using the Rényi Divergence Rather than the Statistical Distance

verfasst von: Shi Bai, Tancrède Lepoint, Adeline Roux-Langlois, Amin Sakzad, Damien Stehlé, Ron Steinfeld

Erschienen in: Journal of Cryptology | Ausgabe 2/2018

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 closeness of two probability distributions. We show that it can often be used as an alternative to the statistical distance in security proofs for lattice-based cryptography. Using the Rényi divergence is particularly suited for security proofs of primitives in which the attacker is required to solve a search problem (e.g., forging a signature). We show that it may also be used in the case of distinguishing problems (e.g., semantic security of encryption schemes), when they enjoy a public sampleability property. The techniques lead to security proofs for schemes with smaller parameters, and sometimes to simpler security proofs than the existing ones.

Vorheriger Artikel Characterization of Secure Multiparty Computation Without Broadcast

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

Note that LWE with uniform noise in a small interval is also investigated in Alwen et al. [24], with a focus on the number of LWE samples. The reduction from Micciancio et al. [24] does not preserve the LWE dimension either.

Note that [11, 22] consider the unnormalized Gaussian function \(\rho '_{\sigma ,\mathbf {c}}(\mathbf {x})=\exp (-\Vert \mathbf {x}-\mathbf {c}\Vert /(2\sigma ^2))\) instead of \(\rho _{s,\mathbf {c}}\). We have \(\rho _{s,\mathbf {c}} = \rho '_{\sigma ,\mathbf {c}}\) when \(\sigma =s/\sqrt{2\pi }\).

E. Alkim, L. Ducas, T. Pöppelmann, P. Schwabe, Post-quantum key exchange—a new hope, in 25th USENIX Security Symposium (USENIX Security 16) (USENIX Association, Austin, 2016), pp. 327–343

M. Ajtai, Generating hard instances of lattice problems (extended abstract), in Proceedings of STOC (ACM, 1996), pp. 99–108

J. Alwen, S. Krenn, K. Pietrzak, D. Wichs, Learning with rounding, revisited—new reduction, properties and applications, in Proceedings of CRYPTO. LNCS, vol. 8042 (Springer, 2013), pp. 57–74

A. Bogdanov, S. Guo, D. Masny, S. Richelson, A. Rosen, On the hardness of learning with rounding over small modulus, in Proceedings of TCC A. LNCS, vol. 9562 (Springer, 2016), pp. 209–224

S. Bai, A. Langlois, T. Lepoint, D. Stehlé, R. Steinfeld, Improved security proofs in lattice-based cryptography: using the Rényi divergence rather than the statistical distance, in Proceedings of ASIACRYPT, Part I. LNCS, vol. 9452 (Springer, 2015), pp. 3–24

Z. Brakerski, A. Langlois, C. Peikert, O. Regev, D. Stehlé, Classical hardness of learning with errors, in Proceedings of STOC (ACM, 2013), pp. 575–584

A. Banerjee, C. Peikert, A. Rosen, Pseudorandom functions and lattices, in Proceedings of EUROCRYPT. LNCS, vol. 7237 (Springer, 2012), pp. 719–737

Z. Brakerski, V. Vaikuntanathan, Efficient fully homomorphic encryption from (standard) LWE, in Proceedings of FOCS (IEEE Computer Society Press, 2011), pp. 97–106

M. Chiani, D. Dardari, M.K. Simon, New exponential bounds and approximations for the computation of error probability in fading channels. IEEE Trans. Wireless. Commun. 2(4):840–845 (2003)

10.

C.-W. Chow, On Algorithmic Aspects of the Learning with Errors Problem and Its Variants, Masters thesis, The Chinese University of Hong Kong (2003)

11.

L. Ducas, A. Durmus, T. Lepoint, V. Lyubashevsky, Lattice signatures and bimodal Gaussians, in Proceedings of CRYPTO. LNCS, vol. 8042 (Springer, 2013), pp. 40–56

12.

N. Döttling, J. Müller-Quade, Lossy codes and a new variant of the learning-with-errors problem, in Proceedings of EUROCRYPT. LNCS, (Springer, 2013), pp. 18–34

13.

L. Ducas, Accelerating Bliss: The Geometry of Ternary Polynomials. Cryptology ePrint Archive, Report 2014/874 (2014). http://eprint.iacr.org/

14.

S. Garg, C. Gentry, S. Halevi, Candidate multilinear maps from ideal lattices, in Proceedings of EUROCRYPT. LNCS, vol. 7881 (Springer, 2013), pp. 1–17

15.

S. Goldwasser, Y.T. Kalai, C. Peikert, V. Vaikuntanathan, Robustness of the learning with errors assumption, in Proceedings of ICS (Tsinghua University Press, 2010), pp. 230–240

16.

C. Gentry, C. Peikert, V. Vaikuntanathan, Trapdoors for hard lattices and new cryptographic constructions, in Proceedings of STOC (ACM, 2008), pp. 197–206

17.

W. Hoeffding, Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58(301):13–30 (1963)

18.

B. Libert, S. Ling, F. Mouhartem, K. Nguyen, H. Wang, Signature Schemes with Efficient Protocols and Dynamic Group Signatures from Lattice Assumptions. Cryptology ePrint Archive, Report 2016/101 (2016). http://eprint.iacr.org/

19.

V. Lyubashevsky, C. Peikert, O. Regev, On ideal lattices and learning with errors over rings. J. ACM 60(6):43 (2013)

20.

S. Ling, D.H. Phan, D. Stehlé, R. Steinfeld, Hardness of \(k\)-LWE and applications in traitor tracing, in Proceedings of CRYPTO, Part I. LNCS, vol. 8616 (Springer, 2014), pp. 315–334. Full version available at http://eprint.iacr.org/2014/494

21.

A. Langlois, D. Stehlé, R. Steinfeld, GGHLite: more efficient multilinear maps from ideal lattices, in Proceedings of EUROCRYPT. LNCS (Springer, 2014), pp. 239–256. Full version available at http://eprint.iacr.org/2014/487

22.

V. Lyubashevsky, Lattice signatures without trapdoors, in Proceedings of EUROCRYPT. LNCS, vol. 7237, ed. By D. Pointcheval, T. Johansson (Springer, 2012), pp. 738–755

23.

D. Micciancio, P. Mol. Pseudorandom knapsacks and the sample complexity of LWE search-to-decision reductions, in Proceeding of CRYPTO. LNCS, vol. 6841 (Springer, 2011), pp. 465–484

24.

D. Micciancio, C. Peikert. Hardness of SIS and LWE with small parameters, in Proceeding of CRYPTO. LNCS, vol. 8042 (Springer, 2013) pp. 21–39

25.

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

26.

D. Micciancio, O. Regev, Lattice-based cryptography, in Post-Quantum Cryptography, ed By D.J. Bernstein, J. Buchmann, E. Dahmen (Springer, 2009), pp. 147–191

27.

T. Pöppelmann, L. Ducas, T. Güneysu, Enhanced lattice-based signatures on reconfigurable hardware, in Proceeding of CHES (2014), pp. 353–370

28.

C. Peikert, Public-key cryptosystems from the worst-case shortest vector problem, in Proceeding of STOC (ACM, 2009), pp. 333–342

29.

C. Peikert, A Decade of Lattice Cryptography. Cryptology ePrint Archive, Report 2015/939 (2015). http://eprint.iacr.org/

30.

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

31.

O. Regev, Lecture Notes of Lattices in Computer Science, Computer Science Tel Aviv University (2009). Available at http://www.cims.nyu.edu/~regev

32.

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

33.

A. Rényi, On measures of entropy and information, in Proceeding of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, vol. 1 (1961), pp. 547–561

34.

K. Takashima, A. Takayasu, Tighter security for efficient lattice cryptography via the rényi divergence of optimized orders, in Proceeding of ProvSec. LNCS (Springer, 2015), pp. 412–431

35.

T. van Erven, P. Harremoes, Rényi divergence and Kullback–Leibler divergence. IEEE Trans. Inf. Theory 60(7):3797–3820 (2014)

Titel: Improved Security Proofs in Lattice-Based Cryptography: Using the Rényi Divergence Rather than the Statistical Distance
verfasst von: Shi Bai
Tancrède Lepoint
Adeline Roux-Langlois
Amin Sakzad
Damien Stehlé
Ron Steinfeld
Publikationsdatum: 28.08.2017
Verlag: Springer US
Erschienen in: Journal of Cryptology / Ausgabe 2/2018
Print ISSN: 0933-2790
Elektronische ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-017-9265-9

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"

Weitere Artikel der Ausgabe 2/2018

Robust Encryption

Practical Cryptanalysis of Bluetooth Encryption with Condition Masking

Multi-input Functional Encryption in the Private-Key Setting: Stronger Security from Weaker Assumptions

Multivariate High-Order Attacks of Shuffled Tables Recomputation

Characterization of Secure Multiparty Computation Without Broadcast

Deterministic Encryption with the Thorp Shuffle

Premium Partner