Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Tightly CCA-Secure Encryption Without Pairings Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Faster Algorithms for Solving LPN

verfasst von : Bin Zhang, Lin Jiao, Mingsheng Wang

Erschienen in: Advances in Cryptology – EUROCRYPT 2016

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The LPN problem, lying at the core of many cryptographic constructions for lightweight and post-quantum cryptography, receives quite a lot attention recently. The best published algorithm for solving it at Asiacrypt 2014 improved the classical BKW algorithm by using covering codes, which claimed to marginally compromise the 80-bit security of HB variants, LPN-C and Lapin. In this paper, we develop faster algorithms for solving LPN based on an optimal precise embedding of cascaded concrete perfect codes, in a similar framework but with many optimizations. Our algorithm outperforms the previous methods for the proposed parameter choices and distinctly break the 80-bit security bound of the instances suggested in cryptographic schemes like HB\(^+\), HB\(^\#\), LPN-C and Lapin.

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 Provably Weak Instances of Ring-LWE Revisited
Nächstes Kapitel Provable Security Evaluation of Structures Against Impossible Differential and Zero Correlation Linear Cryptanalysis
Fußnoten
1
The authors of [15] redeclared their results in their presentation at Asiacrypt 2014, for the original results are incorrect due to an insufficient number of samples used to learn an LPN secret via Walsh-Hadamard Transform.
 
2
The authors of [15] have chosen \({4l\mathrm {ln}2}/{\epsilon _f^2}\) to correct the original estimate of \(1/{\epsilon _f^2}\) as the number of queries in their presentation at Asiacrypt 2014.
 
3
With the corrected number of queries, the algorithm in [15] exceeds the security bound of 80-bit. In order to obtain a complexity smaller than \(2^{80}\), the LF2 reduction step is actually applied.
 
4
We feel that there are some problems in the bias estimation in Bogos et. al. paper. In their work, the bias is computed as \(1-2 \text{ Pr }[(x,e)=1\mid wt(x)=c]\) with the conditional probability other than the normal probability Pr[(x,e)=1]. Note that the latter can be derived from the total probability formula by traversing all the conditions. Further, the weights of several secret chunks are assumed in a way that facilitates the analysis, which need to be divided at last to assure its occurrence. Here instead of summing up these partial conditional probabilities, they should be multiplied together. The Asiacrypt’14 paper has the similar problem in their analysis. Our theoretical derivation is different and new. We compute \(\text{ Pr }[(x,e)=1]\) according to the total probability formula strictly and thus the resultant bias precisely without any assumption, traversing all the conditional probabilities \(\text{ Pr }[(x,e)=1\mid wt(e)=i]\).
 
5
There is just a group of particular parameters for (512, 1 / 8)-LPN instance given in their presentation at Asiacrypt 2014, but the other LPN instances are missing.
 
6
There exists exactly one decodable code word for each vector in the space, which facilitates the definition of the basic function in the Walsh transform. For other codes, the covering sphere may be overlapped, which may complicate the bias/complexity analysis in an unexpected way. It is our future work to study this problem further.
 
7
It is also analyzed that it calls for a number of \({8l\mathrm {ln}2}/{\epsilon _f^2}\) to bound the failure probability in [6]. However, it uses the Hoeffding inequality, which is the different analysis method from ours.
 
8
Can LF(4) be equivalent to two consecutive LF2 steps? The answer is no. We can illustrate this in the aspect of the number of vectors remained. If we adopt LF(4) one step, then the number of vectors remained is about \(s ={n \atopwithdelims ()4} \cdot {2^{ - b}} = \frac{{{n^4}}}{{4!}}\cdot {2^{ - b}}\). While if we first to reduce the last \(b_1\) positions with LF2, then the number of vectors remained is \({t_1} = {n \atopwithdelims ()2} \cdot {2^{ - {b_1}}} = \frac{{{n^2}}}{2} \cdot {2^{ - {b_1}}}\). Then, we do the second LF2 step regarding to the next \(b-b_1\) positions and the number of vectors remained changes into \({t_2} ={{t_1} \atopwithdelims ()2} \cdot {2^{ - (b - {b_1})}} = \frac{( n^2/2 \cdot 2^{ - {b_1}} )^2}{2} \cdot 2^{ - (b - {b_1})} = \frac{n^4}{8} \cdot 2^{ - b - {b_1}}\). We can see that s is obviously not equal to \(t_2\), so they are not equivalent. Indeed, LF(k) is algorithmically converted into several LF2, the point here is that we need to run the process a suitable number of times to find a sufficient number of samples.
 
9
Here, we adjust the parameter of https://static-content.springer.com/image/chp%3A10.1007%2F978-3-662-49890-3_7/420599_1_En_7_IEq686_HTML.gif -LPN instance in Table 6 that c changes into 16. Then the complexity of time, initial data, memory and pre-computation are respectively \(C=2^{72.177}\), \(N=2^{69.526}\), \(M=2^{68.196}\) and \({Pre}=2^{68.020}\).
 
Literatur
1.
Albrecht, M., Cid, C., Faugère, J.C., Fitzpatrick, R., Perret, L.: On the complexity of the BKW algorithm on LWE. Des. Codes Crypt. 74(2), 325–354 (2015)MathSciNetCrossRefMATH
2.
Berbain, C., Gilbert, H., Maximov, A.: Cryptanalysis of grain. In: Robshaw, M. (ed.) FSE 2006. LNCS, vol. 4047, pp. 15–29. Springer, Heidelberg (2006)CrossRef
3.
4.
Bernstein, D.J., Lange, T.: Never trust a bunny. In: Hoepman, J.-H., Verbauwhede, I. (eds.) RFIDSec 2012. LNCS, vol. 7739, pp. 137–148. Springer, Heidelberg (2013)
5.
Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM 50(4), 506–519 (2003)MathSciNetCrossRefMATH
6.
7.
Chose, P., Joux, A., Mitton, M.: Fast correlation attacks: an algorithmic point of view. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, p. 209. Springer, Heidelberg (2002)CrossRef
8.
Cramér, H.: Mathematical Methods of Statistics, vol. 9. Princeton University Press, Princeton (1999)MATH
9.
Drost, F., Kallenberg, W., Moore, D., Oosterhoff, J.: Power approximations to multinomial tests of fit. J. Am. Stat. Assoc. 84(405), 130–141 (1989)MathSciNetCrossRefMATH
10.
Dodis, Y., Kiltz, E., Pietrzak, K., Wichs, D.: Message authentication, revisited. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 355–374. Springer, Heidelberg (2012)CrossRef
11.
Duc, A., Vaudenay, S.: HELEN: a public-key cryptosystem based on the LPN and the decisional minimal distance problems. In: Youssef, A., Nitaj, A., Hassanien, A.E. (eds.) AFRICACRYPT 2013. LNCS, vol. 7918, pp. 107–126. Springer, Heidelberg (2013)CrossRef
12.
Gilbert, H., Robshaw, M., Seurin, Y.: HB\(^{\#}\): increasing the security and efficiency of HB\(^{+}\). In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 361–378. Springer, Heidelberg (2008)CrossRef
13.
Gilbert, H., Robshaw, M., Seurin, Y.: How to encrypt with the LPN problem. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol. 5126, pp. 679–690. Springer, Heidelberg (2008)CrossRef
14.
Gilbert, H., Robshaw, M., Sibert, H.: Active attack against HB\(^+\): a provably secure lightweight authentication protocol. Electron. Lett. 41(21), 1169–1170 (2005)CrossRef
15.
Guo, Q., Johansson, T., Löndahl, C.: Solving LPN using covering codes. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 1–20. Springer, Heidelberg (2014)
16.
Heyse, S., Kiltz, E., Lyubashevsky, V., Paar, C., Pietrzak, K.: Lapin: an efficient authentication protocol based on ring-LPN. In: Canteaut, A. (ed.) FSE 2012. LNCS, vol. 7549, pp. 346–365. Springer, Heidelberg (2012)CrossRef
17.
Lipmaa, H., Moriai, S.: Efficient algorithms for computing differential properties of addition. In: Matsui, M. (ed.) FSE 2001. LNCS, vol. 2355, p. 336. Springer, Heidelberg (2002)CrossRef
18.
Hopper, N.J., Blum, M.: Secure human identification protocols. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 52–66. Springer, Heidelberg (2001)CrossRef
19.
Juels, A., Weis, S.A.: Authenticating pervasive devices with human protocols. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 293–308. Springer, Heidelberg (2005)CrossRef
20.
Kiltz, E., Pietrzak, K., Cash, D., Jain, A., Venturi, D.: Efficient authentication from hard learning problems. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 7–26. Springer, Heidelberg (2011)CrossRef
21.
22.
Levieil, É., Fouque, P.-A.: An improved LPN algorithm. In: De Prisco, R., Yung, M. (eds.) SCN 2006. LNCS, vol. 4116, pp. 348–359. Springer, Heidelberg (2006)CrossRef
23.
Lu, Y., Vaudenay, S.: Faster correlation attack on bluetooth keystream generator E0. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 407–425. Springer, Heidelberg (2004)CrossRef
24.
Van Lint, J.H.: Introduction to Coding Theory, vol. 86. Springer Science+Business Media, Berlin (1999)CrossRefMATH
25.
Wagner, D.: A generalized birthday problem. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 288–304. Springer, Heidelberg (2002)CrossRef
Metadaten
Titel
Faster Algorithms for Solving LPN
verfasst von
Bin Zhang
Lin Jiao
Mingsheng Wang
Copyright-Jahr
2016
Verlag
Springer Berlin Heidelberg
Buch
Advances in Cryptology – EUROCRYPT 2016

Print ISBN: 978-3-662-49889-7

Electronic ISBN: 978-3-662-49890-3

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-662-49890-3_7

Premium Partner

    Bildnachweise