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:
Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

A Key Recovery Attack on MDPC with CCA Security Using Decoding Errors

verfasst von : Qian Guo, Thomas Johansson, Paul Stankovski

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

Algorithms for secure encryption in a post-quantum world are currently receiving a lot of attention in the research community, including several larger projects and a standardization effort from NIST. One of the most promising algorithms is the code-based scheme called QC-MDPC, which has excellent performance and a small public key size. In this work we present a very efficient key recovery attack on the QC-MDPC scheme using the fact that decryption uses an iterative decoding step and this can fail with some small probability. We identify a dependence between the secret key and the failure in decoding. This can be used to build what we refer to as a distance spectrum for the secret key, which is the set of all distances between any two ones in the secret key. In a reconstruction step we then determine the secret key from the distance spectrum. The attack has been implemented and tested on a proposed instance of QC-MDPC for 80 bit security. It successfully recovers the secret key in minutes.
A slightly modified version of the attack can be applied on proposed versions of the QC-MDPC scheme that provides IND-CCA security. The attack is a bit more complex in this case, but still very much below the security level. The reason why we can break schemes with proved CCA security is that the model for these proofs typically does not include the decoding error possibility.

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 Cryptographic Applications of Capacity Theory: On the Optimality of Coppersmith’s Method for Univariate Polynomials
Nächstes Kapitel A Tale of Two Shares: Why Two-Share Threshold Implementation Seems Worthwhile—and Why It Is Not
Fußnoten
1
As in NTRUEncrypt [16, 17], a secure approach is to require the decoding error probability to be less than \(2^{-\kappa }\) for the \(\kappa \)-bit security.
 
2
We assume that t is an even number for the ease of description; otherwise, we just pick \(\frac{t-1}{2}\) random pairs and randomly choose another position to fulfill the constraint on the error weight.
 
3
Here “change” means increasing by 1 or preserving the value.
 
4
See Table 4 for more details.
 
5
A reasonable setting for \(n_{t}\) is T, the number of distances bounded by \(\frac{r}{2}\).
 
6
The average child number of a node in the \(l^{\mathrm { \tiny th }}\) level drops exponentially in l.
 
7
A distance with multiplicity of 2 or more implies that there exists at least one length-4 cycle.
 
8
With respect to the decoding performance, the best known implementation using the suggested 80-bit secure parameter set outperforms the one using the suggested 128-bit secure parameters (\(10^{-8}\) in [8, 10] vs. \(10^{-7}\) in [29]).
 
9
One should decrease the decoding error probability for thwarting the proposed reaction attack within \(2^{128}\) operations.
 
Literatur
1.
2.
Baldi, M., Chiaraluce, F., Garello, R., Mininni, F.: Quasi-cyclic low-density parity-check codes in the McEliece cryptosystem. In: Proceedings of IEEE International Conference on Communications, ICC 2007, Glasgow, Scotland, 24–28, pp. 951–956. IEEE (2007). http://​dx.​doi.​org/​10.​1109/​ICC.​2007.​161
3.
Becker, A., Joux, A., May, A., Meurer, A.: Decoding random binary linear codes in \(2^{\frac{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). doi:10.​1007/​978-3-642-29011-4_​31 CrossRef
4.
Bellare, M., Desai, A., Pointcheval, D., Rogaway, P.: Relations among notions of security for public-key encryption schemes. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 26–45. Springer, Heidelberg (1998). doi:10.​1007/​BFb0055718 CrossRef
5.
Bernstein, D.J., Buchmann, J., Dahmen, E.: Post-Quantum Cryptography. Springer, Heidelberg (2009)CrossRefMATH
6.
Berson, T.A.: Failure of the McEliece public-key cryptosystem under message-resend and related-message attack. In: Kaliski, B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 213–220. Springer, Heidelberg (1997). doi:10.​1007/​BFb0052237 CrossRef
7.
Canteaut, A., Sendrier, N.: Cryptanalysis of the original Mceliece cryptosystem. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 187–199. Springer, Heidelberg (2000). doi:10.​1007/​3-540-49649-1_​16
8.
9.
Chen, L., Jordan, S., Liu, Y.K., Moody, D., Peralta, R., Perlner, R., Smith-Tone, D.: Report on post-quantum cryptography. National Institute of Standards and Technology Internal Report 8105 (2016)
10.
11.
Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, New York (2009)CrossRefMATH
12.
Gallager, R.G.: Low-Density Parity-Check Codes. Ph.D. thesis, MIT Press, Cambridge (1963)
13.
Goppa, V.D.: A new class of linear correcting codes. In: Problemy Peredachi Informatsii vol. 6, pp. 24–30 (1970)
14.
Hall, C., Goldberg, I., Schneier, B.: Reaction attacks against several public-key cryptosystem. In: Varadharajan, V., Mu, Y. (eds.) ICICS 1999. LNCS, vol. 1726, pp. 2–12. Springer, Heidelberg (1999). doi:10.​1007/​978-3-540-47942-0_​2 CrossRef
15.
Heyse, S., Maurich, I., Güneysu, T.: Smaller keys for code-based cryptography: QC-MDPC McEliece implementations on embedded devices. In: Bertoni, G., Coron, J.-S. (eds.) CHES 2013. LNCS, vol. 8086, pp. 273–292. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-40349-1_​16 CrossRef
16.
Hoffstein, J., Pipher, J., Schanck, J.M., Silverman, J.H., Whyte, W., Zhang, Z.: Choosing Parameters for NTRUEncrypt. Cryptology ePrint Archive, Report 2015/708 (2015). http://​eprint.​iacr.​org/​
17.
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). doi:10.​1007/​BFb0054868 CrossRef
18.
Howgrave-Graham, N., Nguyen, P.Q., Pointcheval, D., Proos, J., Silverman, J.H., Singer, A., Whyte, W.: The impact of decryption failures on the security of NTRU encryption. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 226–246. Springer, Heidelberg (2003). doi:10.​1007/​978-3-540-45146-4_​14 CrossRef
19.
Howgrave-Graham, N., Silverman, J.H., Singer, A., Whyte, W.: NTRU Cryptosystems: NAEP: Provable Security in the Presence of Decryption Failures. IACR Cryptology ePrint Archive 2003, 172 (2003)
20.
Johansson, T., Jönsson, F.: On the complexity of some cryptographic problems based on the general decoding problem. IEEE Trans. Inf. Theory 48(10), 2669–2678 (2002)MathSciNetCrossRefMATH
21.
Kobara, K., Imai, H.: Semantically secure McEliece public-key cryptosystems -conversions for McEliece PKC. In: Kim, K. (ed.) PKC 2001. LNCS, vol. 1992, pp. 19–35. Springer, Heidelberg (2001). doi:10.​1007/​3-540-44586-2_​2 CrossRef
22.
Löndahl, C., Johansson, T.: A new version of McEliece PKC based on convolutional codes. In: Chim, T.W., Yuen, T.H. (eds.) ICICS 2012. LNCS, vol. 7618, pp. 461–470. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-34129-8_​45 CrossRef
23.
MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error Correcting Codes, vol. 16. Elsevier, Amsterdam (1977)MATH
24.
von Maurich, I., Güneysu, T.: Lightweight code-based cryptography: QC-MDPC McEliece encryption on reconfigurable devices. In: Proceedings of the conference on Design, Automation & Test in Europe, p. 38. European Design and Automation Association (2014)
25.
von Maurich, I., Güneysu, T.: Towards side-channel resistant implementations of QC-MDPC McEliece encryption on constrained devices. In: Mosca, M. (ed.) PQCrypto 2014. LNCS, vol. 8772, pp. 266–282. Springer, Heidelberg (2014). doi:10.​1007/​978-3-319-11659-4_​16
26.
von Maurich, I., Heberle, L., Güneysu, T.: IND-CCA secure hybrid encryption from QC-MDPC niederreiter. In: Takagi, T. (ed.) PQCrypto 2016. LNCS, vol. 9606, pp. 1–17. Springer, Heidelberg (2016). doi:10.​1007/​978-3-319-29360-8_​1 CrossRef
27.
Maurich, I.V., Oder, T., Güneysu, T.: Implementing QC-MDPC McEliece encryption. ACM Trans. Embed. Comput. Syst. (TECS) 14(3), 44 (2015)
28.
McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. DSN Prog. Rep. 42–44, 114–116 (1978)
29.
Misoczki, R., Tillich, J.P., Sendrier, N., Barreto, P.S.: MDPC-McEliece: New McEliece variants from moderate density parity-check codes. In: 2013 IEEE International Symposium on Information Theory Proceedings (ISIT), pp. 2069–2073. IEEE (2013)
30.
Overbeck, R., Sendrier, N.: Code-based cryptography. In: Bernstein, D.J., Buchmann, J., Dahmen, E. (eds.) Post-Quantum Cryptography, pp. 95–145. Springer, Heidelberg (2009)CrossRef
31.
Repka, M., Zajac, P.: Overview of the Mceliece cryptosystem and its Security. Tatra Mountains Math. Publ. 60(1), 57–83 (2014)MathSciNetMATH
32.
33.
Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: 35th Annual Symposium on Foundations of Computer Science, 20–22 November 1994, Santa Fe, New Mexico, USA, pp. 124–134. IEEE Press (1994)
Metadaten
Titel
A Key Recovery Attack on MDPC with CCA Security Using Decoding Errors
verfasst von
Qian Guo
Thomas Johansson
Paul Stankovski
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_29

Premium Partner

    Bildnachweise