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:
Graph Modification Problems: A Modern Perspective Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

Improved Information Set Decoding for Code-Based Cryptosystems with Constrained Memory

verfasst von : Maoning Wang, Mingjie Liu

Erschienen in: Frontiers in Algorithmics

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

The decoding of random linear codes is one of the most fundamental problems in both computational complexity theory and algorithmic cryptanalysis. Specifically, the best attacks known against existing code-based cryptosystems, such as McEliece, are unstructural, i.e., these attacks directly use generic decoding algorithms that treat the hidden binary codes as random linear codes. This topic is also attracting increasing interest in a post-quantum context as this area becomes increasingly active. In an attempt to solve this problem, several algorithms and their variants have recently been proposed, with increasingly lower time complexities. However, their memory complexities, which are even more important in practice for real attacks, are neglected.
In this paper, we consider the performance of information set decoding (ISD) algorithms for the problem of syndrome decoding for random binary linear codes with restricted memory. Using Finiasz and Sendrier’s standard framework for ISD algorithms, we propose an exact algorithm that performs better when the memory is constrained; also this improvement can be mathematically proven. From a practical standpoint, our approach can yield good time complexities for any given space bound, hence providing a good measure of the effectiveness of a cryptanalytic attack on code-based cryptosystems. Our method can also be seen as an extended application of the dissection technique proposed by Dinur et al. at CRYPTO 2012 [11].

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 Approximate Model Counting via Extension Rule
Nächstes Kapitel Truthful Strategy and Resource Integration for Multi-tenant Data Center Demand Response
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
The polynomial factors hidden by the notation \(\tilde{O}\) originate from the operations of merging the two lists to obtain collisions that are described in Algorithm 2, such as computing the indexes and sorting, and their concrete coefficients and powers are determined by the data structures. In addition, later in this paper, we will often omit the notations \(\tilde{O}\) and \(O\) for simplicity of presentation when there is no ambiguity arising from the context.
 
2
For convenience and clarity, we continue to use the notations \(<\), \(>\), \(\le \) and \(\ge \); however, when they appear in an expression that contains script characters such as \(\mathcal {N}\) and \(\mathcal {T}\), these symbols denote that the inequality relations hold for the exponents.
 
Literatur
1.
Austrin, P., Kaski, P., Koivisto, M., Määttä, J.: Space-time tradeoffs for subset sum: An improved worst case algorithm. CoRR, abs/1303.0609 (2013)
2.
3.
Becker, A., Coron, J.-S., Joux, A.: Improved generic algorithms for hard knapsacks. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 364–385. Springer, Heidelberg (2011) CrossRef
4.
Becker, A., Joux, A., May, A., Meurer, A.: Decoding random binary linear codes in 2\(^{n/20}\): How 1 + 1 = 0 improves information set decoding. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 520–536. Springer, Heidelberg (2012) CrossRef
5.
Berlekamp, E., McEliece, R., Van Tilborg, H.: On the inherent intractability of certain coding problems (corresp.). IEEE Trans. Inf. Theory 24(3), 384–386 (1978)MATHCrossRef
6.
Bernstein, D.J., Lange, T., Peters, C.: Smaller decoding exponents: ball-collision decoding. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 743–760. Springer, Heidelberg (2011) CrossRef
7.
Bernstein, D.J., Lange, T., Peters, C.: Attacking and defending the McEliece cryptosystem. In: Buchmann, J., Ding, J. (eds.) PQCrypto 2008. LNCS, vol. 5299, pp. 31–46. Springer, Heidelberg (2008) CrossRef
8.
Bisson, G., Sutherland, A.V.: A low-memory algorithm for finding short product representations in finite groups. Des. Codes Crypt. 63(1), 1–13 (2012)MATHMathSciNetCrossRef
9.
Bjorklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Computing the Tutte polynomial in vertex-exponential time. In: IEEE 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, pp. 677–686. IEEE (2008)
10.
Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. In: IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 97–106. IEEE (2011)
11.
Dinur, I., Dunkelman, O., Keller, N., Shamir, A.: Efficient dissection of composite problems, with applications to cryptanalysis, knapsacks, and combinatorial search problems. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 719–740. Springer, Heidelberg (2012) CrossRef
12.
Faugère, J.-C., Otmani, A., Perret, L., Tillich, J.-P.: Algebraic cryptanalysis of mceliece variants with compact keys. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 279–298. Springer, Heidelberg (2010) CrossRef
13.
Finiasz, M., Sendrier, N.: Security bounds for the design of code-based cryptosystems. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 88–105. Springer, Heidelberg (2009) CrossRef
14.
Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: a ring-based public key cryptosystem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 267–288. Springer, Heidelberg (1998) CrossRef
15.
Howgrave-Graham, N., Joux, A.: New generic algorithms for hard knapsacks. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 235–256. Springer, Heidelberg (2010) CrossRef
16.
Joux, A.: A tutorial on high performance computing applied to cryptanalysis. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 1–7. Springer, Heidelberg (2012) CrossRef
17.
Koivisto, M., Parviainen, P.: A space-time tradeoff for permutation problems.In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 484–492. Society for Industrial and Applied Mathematics (2010)
18.
Lee, P.J., Brickell, E.F.: An observation on the security of McEliece’s public-key cryptosystem. In: Günther, C.G. (ed.) EUROCRYPT 1988. LNCS, vol. 330, pp. 275–280. Springer, Heidelberg (1988) CrossRef
19.
Lenstra, A.K., Lenstra, H.W., Manasse, M.S., Pollard, J.M.: The factorization of the ninth Fermat number. Math. Comput. 61(203), 319–349 (1993)MATHMathSciNetCrossRef
20.
Lyubashevsky, V., Micciancio, D., Peikert, C., Rosen, A.: SWIFFT: a modest proposal for FFT hashing. In: Nyberg, K. (ed.) FSE 2008. LNCS, vol. 5086, pp. 54–72. Springer, Heidelberg (2008) CrossRef
21.
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) CrossRef
22.
May, A., Ozerov, I.: On computing nearest neighbors with applications to decoding of binary linear codes. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 203–228. Springer, Heidelberg (2015)
23.
McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. DSN Prog. Rep. 42(44), 114–116 (1978)
24.
Meurer, A.: A coding-theoretic approach to cryptanalysis. Ph.D. thesis (2013)
25.
Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM (JACM) 56(6), 34 (2009)MathSciNetCrossRef
26.
Stern, J.: A method for finding codewords of small weight. In: Cohen, G., Wolfmann, J. (eds.) Coding Theory and Applications. LNCS, vol. 388, pp. 106–113. Springer, Heidelberg (1989) CrossRef
27.
28.
Wiener, M.J.: Efficient DES key search. School of Computer Science, Carleton Univ. (1994)
29.
Metadaten
Titel
Improved Information Set Decoding for Code-Based Cryptosystems with Constrained Memory
verfasst von
Maoning Wang
Mingjie Liu
Copyright-Jahr
2015
Buch
Frontiers in Algorithmics

Print ISBN: 978-3-319-19646-6

Electronic ISBN: 978-3-319-19647-3

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-319-19647-3_23

Premium Partner

    Bildnachweise