http://iet.metastore.ingenta.com
1887

Cryptanalysis of McEliece cryptosystem variants based on quasi-cyclic low-density parity check codes

Cryptanalysis of McEliece cryptosystem variants based on quasi-cyclic low-density parity check codes

For access to this article, please select a purchase option:

Buy article PDF
$19.95
(plus tax if applicable)
Buy Knowledge Pack
10 articles for $120.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Information Security — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

One of the approaches to modify the McEliece cryptosystem to overcome its large key size is replacing binary Goppa codes with a new structured code. However, this modification makes such cryptosystems encounter some new attacks. There are a few modified McEliece cryptosystem variants which are known to be secure. One of them is the cryptosystem introduced by Baldi et al. which uses quasi-cyclic low-density parity check (QC-LDPC) codes. This cryptosystem is still unbroken as no efficient attack has been reported against it since 2008. In this study, an attack has been applied to this cryptosystem which is feasible when the code length is a multiple of a power of 2. Also an important weakness of this kind of cryptosystem has been pointed out, namely utilising a too low-weight intentional error vector. The authors have established a new security level for this cryptosystem which is applicable to other McEliece-like cryptosystems using QC-LDPC codes. This security level for instance is 29.18 times lower than previous ones in the case of n = 4 × 4096 when only one ciphertext is available. The gain of the attack in this study can be increased if more than one ciphertext is available.

References

    1. 1)
      • 1. McEliece, R.J.: ‘A public-key cryptosystem based on algebraic coding theory’. DSN Progress Report, 1978, pp. 114116.
    2. 2)
    3. 3)
      • 3. Shor, P.W.: ‘Algorithms for quantum computation: discrete logarithms and factoring’. 35th Annual Symp. on Foundations of Computer Science, November 1994, pp. 124134.
    4. 4)
      • 4. Niederreiter, H.: ‘Knapsack-type crytosystems and algebraic coding theory’, Probl. Control Inf. Theory, 1986, 15, pp. 159166.
    5. 5)
    6. 6)
      • 6. Monico, C., Rosenthal, J., Shokrollahi, A.: ‘Using low density parity check codes in the McEliece cryptosystem’. Proc. of IEEE Int. Symp. on Information Theory (ISIT 2000), Sorrento, Italy, June 2000, p. 215.
    7. 7)
      • 7. Gaborit, P.: ‘Shorter keys for code based cryptography’. Proc. of Int. Workshop on Coding and Cryptography, Springer Verlag, 2005(LNCS, 6110), pp. 8191.
    8. 8)
      • 8. Berger, T.P., Cayrel, P.-L., Gaborit, P., et al: ‘Reducing key length of the McEliece cryptosystem’. Progress in Cryptology – AFRICACRYPT 2009, Springer Verlag, 2009(LNCS, 5580), pp. 7797.
    9. 9)
      • 9. Löndahl, C., Johansson, T.: ‘A new version of McEliece PKC based on convolutional codes’. Information and Communications Security, Springer Verlag, 2012(LNCS, 7618), pp. 461470.
    10. 10)
      • 10. Baldi, M., Chiaraluce, F., Garello, R., et al: ‘Quasi-cyclic low-density parity-check codes in the McEliece cryptosystem’. Proc. of IEEE Int. Conf. on Communications (ICC 2007), Glasgow, Scotland, June 2007, pp. 951956.
    11. 11)
      • 11. Baldi, M., Chiaraluce, F.: ‘Cryptanalysis of a new instance of McEliece cryptosystem based on QC-LDPC codes’. Proc. of IEEE Int. Symp. on Information Theory (ISIT 2007), Nice, France, June 2007, pp. 25912595.
    12. 12)
      • 12. Baldi, M., Bodrato, M., Chiaraluce, F.: ‘A new analysis of the McEliece cryptosystem based on QC-LDPC codes’. Security and Cryptography for Networks, Springer Verlag, 2008(LNCS, 5229), pp. 246262.
    13. 13)
      • 13. Baldi, M.: ‘LDPC codes in the McEliece cryptosystem: attacks and countermeasures’. NATO Science for Peace and Security Series - D: Information and Communication Security, IOS Press, 23, 2009, pp. 160174.
    14. 14)
    15. 15)
      • 15. Baldi, M., Bianchi, M., Maturo, N., et al: ‘Improving the efficiency of the LDPC code-based McEliece cryptosystem through irregular codes’. Proc. of IEEE Symp. on Computers and Communications (ISCC 2013), Split, Croatia, July 2013.
    16. 16)
      • 16. Koochak Shooshtari, M., Ahmadian, M., Payandeh, A.: ‘Improving the security of McEliece-like public key cryptosystem based on LDPC codes’. Proc. of 11th Int. Conf. on Advanced Communication Technology (ICACT 2009), February 2009, pp. 10501053.
    17. 17)
      • 17. Misoczki, R., Barreto, P.S.L.M.: ‘Compact McEliece keys from Goppa codes’. Selected Areas in Cryptography, Springer Verlag, 2009(LNCS, 5867), pp. 376392.
    18. 18)
      • 18. Bernstein, D.J., Lange, T., Peters, C.: ‘Wild McEliece’. Selected Areas in Cryptography, Springer Verlag, 2010(LNCS, 6544), pp. 143158.
    19. 19)
      • 19. Bernstein, D.J., Lange, T., Peters, C.: ‘Wild McEliece incognito’. Post-Quantum Cryptography (PQCrypto 2011), Springer Verlag, 2011(LNCS, 7071), pp. 244254.
    20. 20)
      • 20. Misoczki, R., Tillich, J-P., Sendrier, N., et al: ‘MDPC-McEliece: new McEliece variants from moderate density parity-check codes’. Proc. of IEEE Int. Symp. on Information Theory (ISIT 2013), Istanbul, Turkey, July 2013, pp. 20692073.
    21. 21)
    22. 22)
    23. 23)
      • 23. Umana, V.G., Leander, G.: ‘Practical key recovery attacks on two McEliece variants’. Proc. of Symbolic Computation and Cryptography Conf., Egham, UK, 2010, pp. 2744.
    24. 24)
      • 24. Faugère, J.C., Otmani, A., Perret, L., et al: ‘Algebraic cryptanalysis of McEliece variants with compact keys’. Eurocrypt 2010, Springer Verlag, 2010(LNCS, 6110), pp. 279298.
    25. 25)
      • 25. Couvreur, A., Otmani, A., Tillich, J.P.: ‘Polynomial time attack on wild McEliece over quadratic extensions’. EUROCRYPT 2014, Springer Verlag, 2014(LNCS, 8441), pp. 1739.
    26. 26)
      • 26. Löndahl, C., Johansson, T., Koochak Shooshtari, M., et al: ‘A new attack on McEliece public-key cryptosystems using quasi-cyclic codes of even dimension’. Design, Code and Cryptography, Springer Verlag, 2015, doi: 10.1007/s10623-015-0099-x.
    27. 27)
      • 27. Misoczki, R., Tillich, J.-P., Sendrier, N., et al: ‘MDPC-McEliece: new McEliece variants from moderate density parity-check codes’. ePrint Archive 2012/409, 2012.
    28. 28)
      • 28. Stern, J.: ‘A method for finding codewords of small weight’. Coding Theory and Applications, Springer Verlag, 1989(LNCS, 388), pp. 106113.
    29. 29)
      • 29. Bernstein, D.J., Lange, T., Peters, C.: ‘Attacking and defending the McEliece cryptosystem’. Post-Quantum Cryptography (PQCrypto 2008), Springer Verlag, 2008(LNCS, 5299), pp. 3146.
    30. 30)
      • 30. Johansson, T., Löndahl, C.: ‘An improvement to Stern's algorithm’. Internal Report, 2011. http://lup.lub.lu.se/record/2204753.
    31. 31)
      • 31. May, A., Meurer, A., Thomae, E.: ‘Decoding random linear codes in O~(20.054n)’. ASIACRYPT 2011, Springer Verlag, 2011(LNCS, 7073), pp. 107124.
    32. 32)
      • 32. Becker, A., Joux, A., May, A., et al: ‘Decoding random binary linear codes in 2n/20: how 1 + 1 = 0 improves information set decoding’. EUROCRYPT 2012, Springer Verlag, 2012(LNCS, 7237), pp. 520536.
    33. 33)
      • 33. Sendrier, N.: ‘Decoding one out of many’. Post-Quantum Cryptography (PQCrypto 2011), Springer Verlag, 2011(LNCS, 7071), pp. 5167.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2015.0064
Loading

Related content

content/journals/10.1049/iet-ifs.2015.0064
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
This is a required field
Please enter a valid email address