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
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Optimization of \(\mathsf {LPN}\) Solving Algorithms

verfasst von : Sonia Bogos, Serge Vaudenay

Erschienen in: Advances in Cryptology – ASIACRYPT 2016

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

In this article we focus on constructing an algorithm that automatizes the generation of \(\mathsf {LPN}\) solving algorithms from the considered parameters. When searching for an algorithm to solve an \(\mathsf {LPN}\) instance, we make use of the existing techniques and optimize their use. We formalize an \(\mathsf {LPN}\) algorithm as a path in a graph G and our algorithm is searching for the optimal paths in this graph. Our results bring improvements over the existing work, i.e. we improve the results of the covering code from ASIACRYPT’14 and EUROCRYPT’16. Furthermore, we propose concrete practical codes and a method to find good codes.

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 Reverse Cycle Walking and Its Applications
Nächstes Kapitel The Kernel Matrix Diffie-Hellman Assumption
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
As for [36], we only reported the results based on \(\mathsf {LF2}\) which are better than with \(\mathsf {LF1}\), as the \(\mathsf {LF(4)}\) operation is incorrect [9].
 
2
But the \( k^3 + k \chi 2^{\chi }\) terms is missing in [22].
 
3
In Bogos et al. [7], the number of queries was approximated to \(\frac{\frac{n}{2^b} \left( \frac{n}{2^b} -1 \right) }{2}\) which is less favorable.
 
4
The second term \(k'n'\) illustrates the cost of constructing the function f. In cases where \(n' > 2^{k'}\) this is the dominant term and it should not be ignored. This was missing in several works  [7, 22]. For the instance \(\mathsf {LPN}_{592,0.125}\) from Guo et al. [22] this makes a big difference as \(k'=64\) and \(n' = 2^{69}\); the complexity of \(\mathsf {WHT}\) with the second term is \(2^{75}\) vs \(2^{70}\) [22]. Given that is must be repeated \(2^{13}\) (as 35 bits of the secret are guessed), the cost of \(\mathsf {WHT}\) is \(2^{88}\).
 
5
Normally, the values \(\hat{f}(\nu )\) have an order of magnitude of \(\sqrt{n'}\) so we have \(\frac{1}{2}\log _2n'\) bits.
 
6
Note that Zhang et al. [36] implicitly does the same assumption as they use the average bias as well.
 
7
The random codes that we used are provided as an additional material to this paper.
 
8
Complete results are provided as an additional material to this paper.
 
Literatur
1.
Alekhnovich, M.: More on average case vs approximation complexity. In: Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 11–14 October 2003, Cambridge, MA, USA, pp. 298–307. IEEE Computer Society (2003)
2.
Arlazarov, V.L., Dinic, E.A., Kronrod, M.A., Faradzev, I.A.: On economical construction of the transitive closure of a directed graph. Sov. Math. Dokl. 11, 1209–1210 (1970)MATH
3.
Baicheva, T.S., Bouyukliev, I., Dodunekov, S.M., Fack, V.: Binary and ternary linear quasi-perfect codes with small dimensions. IEEE Trans. Inf. Theory 54(9), 4335–4339 (2008)MathSciNetCrossRefMATH
4.
5.
6.
Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. In: Frances Yao, F., Luks, E.M. (eds.) Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 21–23 May 2000, Portland, OR, USA, pp. 435–440. ACM (2000)
7.
Bogos, S., Tramèr, F., Vaudenay, S.: On solving LPN using BKW and variants - implementation and analysis. Crypt. Commun. 8(3), 331–369 (2016)MathSciNetCrossRefMATH
8.
9.
10.
Bringer, J., Chabanne, H., Dottax, E.: HB\({}^{\text{++}}\): a lightweight authentication protocol secure against some attacks. In: Second International Workshop on Security, Privacy and Trust in Pervasive and Ubiquitous Computing (SecPerU 2006), 29 June 2006, Lyon, France, pp. 28–33. IEEE Computer Society (2006)
11.
Carrijo, J., Tonicelli, R., Imai, H., Nascimento, A.C.A.: A novel probabilistic passive attack on the protocols HB and HB\({}^{\text{+ }}\). IEICE Trans. 92–A(2), 658–662 (2009)CrossRef
12.
Cohen, G., Honkala, I., Litsyn, S., Lobstein, A.: Covering Codes. North-Holland Mathematical Library, Elsevier Science, Amsterdam (1997)MATH
13.
Cohen, G.D., Karpovsky, M.G., Mattson Jr., H.F., Schatz, J.R.: Covering radius - survey and recent results. IEEE Trans. Inf. Theory 31(3), 328–343 (1985)MathSciNetCrossRefMATH
14.
Damgård, I., Park, S.: Is public-key encryption based on LPN practical? IACR Cryptology ePrint Arch. 2012, 699 (2012)
15.
Döttling, N., Müller-Quade, J., Nascimento, A.C.A.: IND-CCA secure cryptography based on a variant of the LPN problem. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 485–503. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-34961-4_​30 CrossRef
16.
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). doi:10.​1007/​978-3-642-38553-7_​6 CrossRef
17.
Etzion, T., Mounits, B.: Mounits.: quasi-perfect codes with small distance. IEEE Trans. Inf. Theory 51(11), 3938–3946 (2005)MathSciNetCrossRefMATH
18.
Fossorier, M.P.C., Mihaljević, M.J., Imai, H., Cui, Y., Matsuura, K.: An algorithm for solving the LPN problem and its application to security evaluation of the HB protocols for RFID authentication. In: Barua, R., Lange, T. (eds.) INDOCRYPT 2006. LNCS, vol. 4329, pp. 48–62. Springer, Heidelberg (2006). doi:10.​1007/​11941378_​5 CrossRef
19.
Gilbert, H., Robshaw, M.J.B., Seurin, Y.: HB#: increasing the security and efficiency of HB\(^{+}\). In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 361–378. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-78967-3_​21 CrossRef
20.
Gilbert, H., Robshaw, M.J.B., 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. LNCS, vol. 5126, pp. 679–690. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-70583-3_​55 CrossRef
21.
22.
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). doi:10.​1007/​978-3-662-45611-8_​1
23.
24.
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). doi:10.​1007/​11535218_​18 CrossRef
25.
26.
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). doi:10.​1007/​978-3-642-20465-4_​3 CrossRef
27.
Kirchner, P., Fouque, P.-A.: An improved BKW algorithm for LWE with applications to cryptography and lattices. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 43–62. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-47989-6_​3 CrossRef
28.
Levieil, É., Fouque, P.-A.: An improved LPN algorithm. In: Prisco, R., Yung, M. (eds.) SCN 2006. LNCS, vol. 4116, pp. 348–359. Springer, Heidelberg (2006). doi:10.​1007/​11832072_​24 CrossRef
29.
Lyubashevsky, V.: The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX/RANDOM - 2005. LNCS, vol. 3624, pp. 378–389. Springer, Heidelberg (2005). doi:10.​1007/​11538462_​32 CrossRef
30.
Lyubashevsky, V., Masny, D.: Man-in-the-middle secure authentication schemes from LPN and weak PRFs. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 308–325. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-40084-1_​18 CrossRef
31.
May, A., Meurer, A., Thomae, E.: Decoding random linear codes in \(\tilde{\cal{O}}(2^{0.054n})\). In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 107–124. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-25385-0_​6 CrossRef
32.
Peterson, W.W., Weldon, E.J.: Error-Correcting Codes. MIT Press, Cambridge (1972)MATH
33.
Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow, H.N., Fagin, R. (eds.) Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, 22–24 May 2005, pp. 84–93. ACM (2005)
34.
35.
Stern, J.: A method for finding codewords of small weight. In: Cohen, G.D., Wolfmann, J. (eds.) Coding Theory 1988. LNCS, vol. 388, pp. 106–113. Springer, Heidelberg (1989). doi:10.​1007/​BFb0019850 CrossRef
36.
Metadaten
Titel
Optimization of Solving Algorithms
verfasst von
Sonia Bogos
Serge Vaudenay
Copyright-Jahr
2016
Verlag
Springer Berlin Heidelberg
Buch
Advances in Cryptology – ASIACRYPT 2016

Print ISBN: 978-3-662-53886-9

Electronic ISBN: 978-3-662-53887-6

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-662-53887-6_26