nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

LWE with Side Information: Attacks and Concrete Security Estimation

verfasst von : Dana Dachman-Soled, Léo Ducas, Huijing Gong, Mélissa Rossi

Erschienen in: Advances in Cryptology – CRYPTO 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

We propose a framework for cryptanalysis of lattice-based schemes, when side information—in the form of “hints”—about the secret and/or error is available. Our framework generalizes the so-called primal lattice reduction attack, and allows the progressive integration of hints before running a final lattice reduction step. Our techniques for integrating hints include sparsifying the lattice, projecting onto and intersecting with hyperplanes, and/or altering the distribution of the secret vector. Our main contribution is to propose a toolbox and a methodology to integrate such hints into lattice reduction attacks and to predict the performance of those lattice attacks with side information.

While initially designed for side-channel information, our framework can also be used in other cases: exploiting decryption failures, or simply exploiting constraints imposed by certain schemes (LAC, Round5, NTRU).

We implement a Sage 9.0 toolkit to actually mount such attacks with hints when computationally feasible, and to predict their performances on larger instances. We provide several end-to-end application examples, such as an improvement of a single trace attack on Frodo by Bos et al. (SAC 2018). In particular, our work can estimates security loss even given very little side information, leading to a smooth measurement/computation trade-off for side-channel attacks.

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 Rounding in the Rings

Nächstes Kapitel A Key-Recovery Timing Attack on Post-quantum Primitives Using the Fujisaki-Okamoto Transformation and Its Application on FrodoKEM

One may then re-amplify the success probability by retrying the attack making guesses at different locations.

We are thankful to Thibauld Feneuil for pointing out an incorrect equation in a previous version of this paper.

While we would have preferred a full python implementation, we are making a heavy use of linear algebra over the rationals for which we could find no convenient python library.

Albrecht, M.R., et al.: Estimate all the \(\{\)LWE, NTRU\(\}\) schemes! In: Catalano, D., De Prisco, R. (eds.) SCN 2018. LNCS, vol. 11035, pp. 351–367. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-98113-0_19

Albrecht, M.R., Deo, A., Paterson, K.G.: Cold boot attacks on ring and module LWE keys under the NTT. IACR TCHES 2018, 173–213 (2018)

Albrecht, M.R., Göpfert, F., Virdia, F., Wunderer, T.: Revisiting the expected cost of solving uSVP and applications to LWE. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10624, pp. 297–322. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70694-8_11CrossRef

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

Bai, S., Miller, S., Wen, W.: A refined analysis of the cost for solving LWE via uSVP. Cryptology ePrint Archive, Report 2019/502 (2019)

Bolboceanu, M., Brakerski, Z., Perlman, R., Sharma, D.: Order-LWE and the hardness of ring-LWE with entropic secrets. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019. LNCS, vol. 11922, pp. 91–120. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34621-8_4CrossRef

Bootle, J., Delaplace, C., Espitau, T., Fouque, P.-A., Tibouchi, M.: LWE without modular reduction and improved side-channel attacks against BLISS. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018. LNCS, vol. 11272, pp. 494–524. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03326-2_17CrossRef

Bos, J.W., et al.: Frodo: take off the ring! Practical, quantum-secure key exchange from LWE, pp. 1006–1018 (2016)

Bos, J.W., Friedberger, S., Martinoli, M., Oswald, E., Stam, M.: Assessing the feasibility of single trace power analysis of Frodo. In: Cid, C., Jacobson Jr., M. (eds.) SAC 2018. LNCS, vol. 11349, pp. 216–234. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-10970-7_10CrossRef

10.

Chari, S., Rao, J.R., Rohatgi, P.: Template attacks. In: Kaliski, B.S., Koç, K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 13–28. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36400-5_3CrossRef

11.

Chen, Y., Nguyen, P.Q.: BKZ 2.0: better lattice security estimates. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 1–20. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25385-0_1CrossRef

12.

Cheon, J.H., Kim, D., Lee, J., Song, Y.: Lizard: cut off the tail! A practical post-quantum public-key encryption from LWE and LWR. In: Catalano, D., De Prisco, R. (eds.) SCN 2018. LNCS, vol. 11035, pp. 160–177. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-98113-0_9CrossRef

13.

Dachman-Soled, D., Ducas, L., Gong, H., Rossi, M.: LWE with side information: attacks and concrete security estimation. Cryptology ePrint Archive, Report 2020/292 (2020). https://eprint.iacr.org/2020/292

14.

D’Anvers, J.-P., Vercauteren, F., Verbauwhede, I.: On the impact of decryption failures on the security of LWE/LWR based schemes. IACR Cryptology ePrint Archive, 2018:1089 (2018)

15.

The FPLLL Development Team: FPLLL, a lattice reduction library (2016). https://github.com/fplll/fplll

16.

Garcia-Morchon, O., et al.: Round5. Technical report, NIST (2019)

17.

Groot Bruinderink, L., Hülsing, A., Lange, T., Yarom, Y.: Flush, gauss, and reload–a cache attack on the BLISS lattice-based signature scheme. In: Gierlichs, B., Poschmann, A.Y. (eds.) CHES 2016. LNCS, vol. 9813, pp. 323–345. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53140-2_16CrossRefMATH

18.

Groot Bruinderink, L., Pessl, P.: Differential fault attacks on deterministic lattice signatures. IACR TCHES 2018, 21–43 (2018)

19.

Hoffstein, J., Howgrave-Graham, N., Pipher, J., Whyte, W.: Practical lattice-based cryptography: NTRUEncrypt and NTRUSign. In: Nguyen, P., Vallée, B. (eds.) The LLL Algorithm. ISC, pp. 349–390. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02295-1_11CrossRef

20.

Howgrave-Graham, N.: A hybrid lattice-reduction and meet-in-the-middle attack against NTRU. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 150–169. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74143-5_9CrossRefMATH

21.

Kannan, R.: Minkowski’s convex body theorem and integer programming. Math. Oper. Res. 12, 415–440 (1987)MathSciNetCrossRef

22.

Khachiyan, L.: On the complexity of approximating extremal determinants in matrices. J. Complex. 11, 138–153 (1995)MathSciNetCrossRef

23.

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

24.

Liu, L.-P.: Linear transformation of multivariate normal distribution: marginal, joint and posterior. http://www.cs.columbia.edu/~liulp/pdf/linear_normal_dist.pdf. Accessed Sept 2019

25.

Lu, X., et al.: PQC round-2 candidate: LAC. Technical report, NIST (2019). https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions

26.

Martinet, J.: Perfect Lattices in Euclidean Spaces, vol. 327. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-662-05167-2CrossRefMATH

27.

McCann, D., Oswald, E., Whitnall, C.: Towards practical tools for side channel aware software engineering: ‘grey box’ modelling for instruction leakages. In: 26th USENIX Security Symposium (USENIX Security 2017), Vancouver, BC, pp. 199–216. USENIX Association, August 2017

28.

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

29.

Naehrig, M., et al.: FrodoKEM. Technical report, National Institute of Standards and Technology (2017). https://csrc.nist.gov/projects/post-quantum-cryptography/round-1-submissions

30.

Nguyen, P.: Giophanthus and *LWR-based submissions (2019). Comment on the NIST PQC forum. https://groups.google.com/a/list.nist.gov/d/msg/pqc-forum/nZBIBvYmmUI/J0pug16CBgAJ

31.

Pöppelmann, T., et al.: NewHope. Technical report, NIST (2019)

32.

Ravi, P., Jhanwar, M.P., Howe, J., Chattopadhyay, A., Bhasin, S.: Side-channel assisted existential forgery attack on Dilithium - a NIST PQC candidate. Cryptology ePrint Archive, Report 2018/821 (2018)

33.

Ravi, P., Jhanwar, M.P., Howe, J., Chattopadhyay, A., Bhasin, S.: Exploiting determinism in lattice-based signatures: practical fault attacks on pqm4 implementations of NIST candidates. In: Asia CCS 2019, pp. 427–440. Association for Computing Machinery (2019)

34.

Schwabe, P., et al.: CRYSTALS-KYBER. Technical report, NIST (2019)

35.

Zhang, Z., et al.: PQC round-2 candidate: NTRU. Technical report, NIST (2019). https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions

Titel: LWE with Side Information: Attacks and Concrete Security Estimation
verfasst von: Dana Dachman-Soled
Léo Ducas
Huijing Gong
Mélissa Rossi
Verlag: Springer International Publishing
Buch: Advances in Cryptology – CRYPTO 2020
Print ISBN: 978-3-030-56879-5

Electronic ISBN: 978-3-030-56880-1

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-56880-1_12

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"