Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Designs, Codes and Cryptography
Published in: Designs, Codes and Cryptography 2/2016

01-08-2016

Squaring attacks on McEliece public-key cryptosystems using quasi-cyclic codes of even dimension

Authors: Carl Löndahl, Thomas Johansson, Masoumeh Koochak Shooshtari, Mahmoud Ahmadian-Attari, Mohammad Reza Aref

Published in: Designs, Codes and Cryptography | Issue 2/2016

Login to get access

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We present a general purpose algorithm for finding low-weight codewords as well as for decoding a received codeword in any quasi-cyclic code whose length and dimension is a multiple of a power of 2. In this paper, we apply the algorithm on a McEliece variant recently proposed by Misoczki et al. (MDPC-McEliece: New McEliece variants from moderate density parity-check codes, 2013). In their paper, the authors present instances of LDPC codes with increased weight for use in a McEliece type PKC. They claim that all message-recovery and key-recovery attacks can be avoided. We show that this is not true for certain parameters and public-key matrices.
previous article Homomorphic AES evaluation using the modified LTV scheme
next article Codes over and some DNA applications
Footnotes
1
In the early version of the publication.
 
Literature
1.
Baldi M.: LDPC codes in the McEliece cryptosystem: attacks and countermeasures. In: NATO Science for Peace and Security Series—D: Information and Communication Security. LNCS, vol. 23 of , pp. 160–174 (2009).
2.
Baldi M., Bodrato M., Chiaraluce F.: A new analysis of the McEliece cryptosystem based on QC–LDPC codes. In: Ostrovsky, R., De Prisco, R., Visconti, I. (eds.) 6th International Conference on Security and Cryptography for Networks (SCN 2008). LNCS, vol. 5229, pp. 246–262. Springer, Berlin (2008).
3.
Baldi M., Bambozzi F., Chiaraluce F.: On a family of circulant matrices for quasi-cyclic low-density generator matrix codes. IEEE Trans. Inf. Theory 57(9), 6052–6067 (2011).
4.
Baldi M., Bianchi M., Chiaraluce F.: Security and complexity of the McEliece cryptosystem based on quasi-cyclic low-density parity-check codes. IET Inf. Secur. 7(3), 212–220 (2013).
5.
Baldi M., Bianchi M., Chiaraluce F.: Optimization of the parity-check matrix density in QC–LDPC code-based McEliece cryptosystems. In: Workshop on Information Security Over Noisy and Lossy Communication Systems (IEEE ICC 2013) (2013).
6.
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), pp. 951–956 (2007).
7.
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, Berlin (2012).
8.
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, Berlin (2008).
9.
Dumer I., Micciancio D., Sudan M.: Hardness of approximating the minimum distance of a linear code. IEEE Trans. Inf. Theory 49(1):22–37 (2007).
10.
Faugère J.C., Otmani A., Perret L., Tillich J-P.: Algebraic cryptanalysis of McEliece variants with compact keys. In: Gilbert, H. (eds.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 279–298. Springer, Berlin (2010).
11.
Gaborit P.: Shorter keys for code based cryptography. In: International Workshop on Coding and Cryptography. LNCS, vol. 6110, pp. 81–91 (2005).
12.
Heyse S., von Maurich I., Güneysu T.: Smaller keys for code-based cryptography: QC-MDPC McEliece implementations on embedded devices. In: Bertoni, G., Coron, J. (eds.) CHES 2013. LNCS, vol. 8086, pp. 273–292. Springer, Berlin (2013).
13.
14.
Koochak Shooshtari M., Ahmadian M., Payandeh A.: Improving the security of McEliece-like public key cryptosystem based on LDPC codes. In: Proceedings of the 11th International Conference on Advanced Communication Technology (ICACT’09), pp. 1050–1053. IEEE Press, New York (2009).
15.
16.
Löndahl C., Johansson T.: A new version of McEliece PKC based on convolutional codes. In: Information and Communications Security. LNCS, vol. 7618, pp. 461–470. Springer, Berlin (2012).
17.
Löndahl C., Johansson T.: Improved algorithms for finding low-weight polynomial multiples in \({\mathbb{F}}_{2}^{}[x]\) and some cryptographic applications. Des. Codes Cryptogr. 73(2), 625–640 (2014).
18.
May A., Meurer A., Thomae E.: Decoding random linear codes in \(\tilde{O}({2^{0.054n}})\). In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 107–124. Springer, Berlin (2011).
19.
McEliece R.J.: A public-key cryptosystem based on algebraic coding theory. DSN Prog. Rep. 42(44), 114–116 (1978).
20.
Misoczki R., Tillich J-P., Sendrier N., Barreto P.S.L.M.: MDPC-McEliece: new McEliece variants from moderate density parity-check codes ePrint archive 2012/409 (2013).
21.
Misoczki R., Tillich J-P., Sendrier N., Barreto P.S.L.M.: MDPC-McEliece: new McEliece variants from moderate density parity-check codes. In: IEEE International Symposium on Information Theory (ISIT’2013), pp. 2069–2073 (2013).
22.
Monico C., Rosenthal J., Shokrollahi A.: Using low density parity check codes in the McEliece cryptosystem. In: IEEE International Symposium on Information Theory (ISIT’2000), p. 215 (2000).
23.
Sendrier N.: Decoding one out of many. In Yang, B. (eds.) Post-Quantum Cryptography. LNCS, vol. 7071, pp. 51–67. Springer, Berlin (2011).
24.
Shor P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: 35th Annual Symposium on Foundations of Computer Science, 20–22 Nov 1994, Santa Fe, pp. 124–134. IEEE Press, New York (1994).
25.
Sidelnikov V.M., Shestakov S.O.: On the insecurity of cryptosystems based on generalized Reed–Solomon codes. Discret. Math. Appl. 2(4), 439–444 (1992).
26.
Stern J.: A method for finding codewords of small weight. In: Wolfmann, J., Cohen, G.D. (eds.) Coding Theory and Applications. LNCS, vol. 388, pp. 106–113. Springer, Berlin (1989).
Metadata
Title
Squaring attacks on McEliece public-key cryptosystems using quasi-cyclic codes of even dimension
Authors
Carl Löndahl
Thomas Johansson
Masoumeh Koochak Shooshtari
Mahmoud Ahmadian-Attari
Mohammad Reza Aref
Publication date
01-08-2016
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 2/2016
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-015-0099-x

Other articles of this Issue 2/2016

Designs, Codes and Cryptography 2/2016 Go to the issue

OriginalPaper

Characterising pointsets in that correspond to conics

OriginalPaper

Homomorphic AES evaluation using the modified LTV scheme

OriginalPaper

Complete weight enumerators of some cyclic codes

OriginalPaper

A construction and decomposition of orthogonal arrays with non-prime-power numbers of symbols on the complement of a Baer subplane

OriginalPaper

Convolutional block codes with cryptographic properties over the semi-direct product

OriginalPaper

Dimensional dual hyperovals in classical polar spaces

Premium Partner

    Image Credits