nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Solving LWR via BDD Strategy: Modulus Switching Approach

verfasst von : Huy Quoc Le, Pradeep Kumar Mishra, Dung Hoang Duong, Masaya Yasuda

Erschienen in: Cryptology and Network Security

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 typical approach in attacking an LWR\(_{m,n,q,p}(\chi _s)\) instance parameterized by four integers m, n, q, p \( (q \ge p)\) and a probability distribution \(\chi _s\) is just by simply regarding it as a Learning with Errors (LWE) modulo q instance and then trying to adapt known LWE attacks to this LWE instance. In this paper, we show that for an LWR\(_{m,n,q,p}(\chi _s)\) instance whose parameters satisfy a certain sufficient condition, one can use the BDD strategy to recover the secret with higher advantages if one transforms the LWR instance to an LWE modulo \(q'\) instance with \(q'\) chosen appropriately instead of an LWE modulo q instance. The optimal modulus \(q'\) used in our BDD attack is quite close to p as well as typically smaller than q. Especially, our experiments confirm that our BDD attack is much better in solving search-LWR in terms of root Hermite factor, success probability and even running time either in case the ratio \(\log (q)/ \log (p)\) is big or/and the dimension n is sufficiently large.

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 Breaking the Hardness Assumption and IND-CPA Security of HQC Submitted to NIST PQC Project

Nächstes Kapitel Acceleration of Index Calculus for Solving ECDLP over Prime Fields and Its Limitation

BKZ of blocksize 20 is usually used in practice because of its time/quality trade-off property.

We cannot use either (5) or (6) if the error \(\mathbf {e}\) has a complex behavior. Such a kind of error is the \(q'\)-error that we will see in Sect. 5.

It is easy to check that the function \(x\ln (x)\) is concave over \((0, +\infty )\).

Albrecht, M.R., Faugère, J.-C., Fitzpatrick, R., Perret, L.: Lazy modulus switching for the BKW algorithm on LWE. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 429–445. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54631-0_25CrossRef

Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. Cryptology ePrint Archive, Report 2015/046 (2015). https://eprint.iacr.org/2015/046

Arora, S., Ge, R.: New algorithms for learning in presence of errors. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, vol. 6755, pp. 403–415. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22006-7_34CrossRef

Baan, H., et al.: Round2: KEM and PKE based on GLWR. Submission to NIST proposal, Round 1 (2017). https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-1-Submissions

Babai, L.: On lovász’ lattice reduction and the nearest lattice point problem. Combinatorica 6(1), 1–13 (1986). https://doi.org/10.1007/BF02579403MathSciNetCrossRefMATH

Banerjee, A., Peikert, C., Rosen, A.: Pseudorandom functions and lattices. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 719–737. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_42CrossRef

Bischof, C., Buchmann, J., Dagdelen, Ö., Fitzpatrick, R., Göpfert, F., Mariano, A.: Nearest planes in practice. In: Ors, B., Preneel, B. (eds.) Cryptography and Information Security in the Balkans, pp. 203–215. Springer International Publishing, Cham (2015)CrossRef

Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS 2012, pp. 309–325. ACM, New York (2012). https://doi.org/10.1145/2090236.2090262

Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehlé, D.: Classical hardness of learning with errors. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC 2013, pp. 575–584. ACM, New York (2013). https://doi.org/10.1145/2488608.2488680

10.

Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. In: Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, pp. 97–106. IEEE Computer Society, Washington (2011). https://doi.org/10.1109/FOCS.2011.12

11.

Brakerski, Z., Vaikuntanathan, V.: Fully homomorphic encryption from ring-LWE and security for key dependent messages. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 505–524. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22792-9_29CrossRef

12.

Cheon, J.H., Kim, D., Lee, J., Song, Y.: Lizard public key encryption. Submission to NIST proposal, Round 1 (2017). https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-1-Submissions

13.

Duc, A., Tramér, F., Vaudenay, S.: Better algorithms for LWE and LWR. Cryptology ePrint Archive, Report 2015/056 (2015). https://eprint.iacr.org/2015/056

14.

Fang, F., Li, B., Lu, X., Liu, Y., Jia, D., Xue, H.: (Deterministic) hierarchical identity-based encryption from learning with rounding over small modulus. In: Proceedings of the 11th ACM on Asia Conference on Computer and Communications Security, ASIA CCS 2016, pp. 907–912. ACM, New York (2016). https://doi.org/10.1145/2897845.2897922

15.

Gama, N., Nguyen, P.Q.: Predicting lattice reduction. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 31–51. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78967-3_3CrossRef

16.

Göpfert, F., van Vredendaal, C., Wunderer, T.: A hybrid lattice basis reduction and quantum search attack on LWE. In: Lange, T., Takagi, T. (eds.) PQCrypto 2017. LNCS, vol. 10346, pp. 184–202. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-59879-6_11CrossRef

17.

Kudo, M., Yamaguchi, J., Guo, Y., Yasuda, M.: Practical analysis of key recovery attack against search-LWE problem. In: Ogawa, K., Yoshioka, K. (eds.) IWSEC 2016. LNCS, vol. 9836, pp. 164–181. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-44524-3_10CrossRef

18.

Laine, K., Lauter, K.: Key recovery for LWE in polynomial time. Cryptology ePrint Archive, Report 2015/176 (2015). https://eprint.iacr.org/2015/176

19.

Lenstra, A.K., Lenstra, H.W., Lovasz, L.: Factoring polynomials with rational coefficients. Math. Ann. 261, 515–534 (1982)MathSciNetCrossRef

20.

Lindner, R., Peikert, C.: Better key sizes (and attacks) for LWE-based encryption. In: Kiayias, A. (ed.) CT-RSA 2011. LNCS, vol. 6558, pp. 319–339. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19074-2_21CrossRef

21.

Micciancio, D., Regev, O.: Lattice-based cryptography. In: Bernstein, D.J., Buchmann, J., Dahmen, E. (eds.) Post-Quantum Cryptography, pp. 147–191. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-540-88702-7_5CrossRefMATH

22.

Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6), 34:1–34:40 (2009). https://doi.org/10.1145/1568318.1568324MathSciNetCrossRefMATH

23.

Schnorr, C.P., Euchner, M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Program. 66(1), 181–199 (1994). https://doi.org/10.1007/BF01581144MathSciNetCrossRefMATH

24.

Stein, W., et al.: Sage Mathematics Software (Version 8.1). The Sage Development Team (2018). http://www.sagemath.org

Titel: Solving LWR via BDD Strategy: Modulus Switching Approach
verfasst von: Huy Quoc Le
Pradeep Kumar Mishra
Dung Hoang Duong
Masaya Yasuda
Verlag: Springer International Publishing
Buch: Cryptology and Network Security
Print ISBN: 978-3-030-00433-0

Electronic ISBN: 978-3-030-00434-7

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-030-00434-7_18

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"

Premium Partner