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

Security and complexity of the McEliece cryptosystem based on quasi-cyclic low-density parity-check codes

Security and complexity of the McEliece cryptosystem 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.

In the context of public key cryptography, the McEliece cryptosystem represents a very smart solution based on the hardness of the decoding problem, which is believed to be able to resist the advent of quantum computers. Despite this, the original McEliece cryptosystem based on Goppa codes, has encountered limited interest in practical applications, partly because of some constraints imposed by this very special class of codes. The authors have recently introduced a variant of the McEliece cryptosystem including low-density parity-check codes, that are state-of-the-art codes, now used in many telecommunication standards and applications. In this study, the authors discuss the possible use of a bit-flipping decoder in this context, which gives a significant advantage in terms of complexity. The authors also provide theoretical arguments and practical tools for estimating the trade-off between security and complexity, in such a way to give a simple procedure for the system design.

References

    1. 1)
      • 1. McEliece, R.J.: ‘A public-key cryptosystem based on algebraic coding theory’. DSN Progress Report, 1978, pp. 114116.
    2. 2)
      • 2. Lee, P., Brickell, E.: ‘An observation on the security of McEliece's public-key cryptosystem’. Advances in Cryptology – EUROCRYPT 88, 1988, pp. 275280.
    3. 3)
      • 3. Stern, J.: ‘A method for finding codewords of small weight’, in Cohen, G., Wolfmann, J. (Eds.): ‘Coding theory and applications’, (Springer Verlag, LNCS, 388, 1989), pp. 106113.
    4. 4)
      • 4. Canteaut, A., Chabaud, F.: ‘A new algorithm for finding minimum-weight words in a linear code: application to McEliece's cryptosystem and to narrow-sense BCH codes of length 511’, IEEE Trans. Inf. Theory, 1998, 44, (1), pp. 367378 (doi: 10.1109/18.651067).
    5. 5)
      • 5. Bernstein, D.J., Lange, T., Peters, C.: ‘Attacking and defending the McEliece cryptosystem’. Post-Quantum Cryptography, Springer Verlag, 2008, (LNCS, 5299), pp. 3146.
    6. 6)
      • 6. Peters, C.: ‘Information-set decoding for linear codes over Fq’. Post-Quantum Cryptography, Springer Verlag, 2010, (LNCS, 6061), pp. 8194.
    7. 7)
      • 7. May, A., Meurer, A., Thomae, E.: ‘Decoding random linear codes in O(20.054n)’. ASIACRYPT 2011, Springer Verlag, 2011, (LNCS, 7073), pp. 107124.
    8. 8)
      • 8. Bernstein, D.J., Lange, T., Peters, C.: ‘Smaller decoding exponents: ball-collision decoding’. CRYPTO 2011, Springer Verlag, 2011, (LNCS, 6841), pp. 743760.
    9. 9)
      • 9. Becker, A., Joux, A., May, A., Meurer, A.: ‘Decoding random binary linear codes in 2n/20: how 1 + 1 = 0 improves information set decoding’. EUROCRYPT 2012, Springer Verlag, 2012, (LNCS7237), pp. 520536.
    10. 10)
      • 10. Niederreiter, H.: ‘Knapsack-type cryptosystems and algebraic coding theory’, Probl. Control Inf. Theory, 1986, 15, pp. 159166.
    11. 11)
      • 11. Sidelnikov, V., Shestakov, S.: ‘On cryptosystems based on generalized Reed-Solomon codes’, Diskretnaya Math., 1992, 4, pp. 5763.
    12. 12)
      • 12. Li, Y.X., Deng, R., Wang, X.M.: ‘On the equivalence of McEliece's and Niederreiter's public-key cryptosystems’, IEEE Trans. Inf. Theory, 1994, 40, (1), pp. 271273 (doi: 10.1109/18.272496).
    13. 13)
      • 13. Overbeck, R.: ‘Structural attacks for public key cryptosystems based on Gabidulin codes’, J. Cryptol., 2008, 21, (2), pp. 280301 (doi: 10.1007/s00145-007-9003-9).
    14. 14)
      • 14. Wieschebrink, C.: ‘Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes’. Post-quantum cryptography: PQCrypto 2010, Springer Verlag, 2010, (LNCS, 6061), pp. 6172.
    15. 15)
      • 15. Berger, T.P., Cayrel, P.-L., Gaborit, P., Otmani, A.: ‘Reducing key length of the McEliece cryptosystem’. Progress in Cryptology – AFRICACRYPT 2009, Springer Verlag, 2009, (LNCS, 5580), pp. 7797.
    16. 16)
      • 16. Misoczki, R., Barreto, P.S.L.M.: ‘Compact McEliece keys from Goppa codes’. Selected Areas in Cryptography, Springer Verlag, 2009, (LNCS, 5867), pp. 376392.
    17. 17)
      • 17. Baldi, M.: ‘LDPC codes in the McEliece cryptosystem: attacks and countermeasures’. NATO Science for Peace and Security Series – D: Information and Communication Security, 2009, vol. 23, pp. 160174.
    18. 18)
      • 18. Sobhi Afshar, A., Eghlidos, T., Aref, M.: ‘Efficient secure channel coding based on quasi-cyclic low-density parity-check codes’, IET Commun., 2009, 3, (2), pp. 279292 (doi: 10.1049/iet-com:20080050).
    19. 19)
      • 19. Umana, V.G., Leander, G.: ‘Practical key recovery attacks on two McEliece variants’. Proc. Second Int. Conf. on Symbolic Computation and Cryptography, Egham, UK, 2010, pp. 2744.
    20. 20)
      • 20. Faugère, J.-C., Otmani, A., Perret, L., Tillich, J.-P.: ‘Algebraic cryptanalysis of McEliece variants with compact keys’. EUROCRYPT 2010, Springer Verlag, 2010, (LNCS, 6110), pp. 279298.
    21. 21)
      • 21. Barbier, M., Barreto, P.: ‘Key reduction of McEliece's cryptosystem using list decoding’. Proc. IEEE Int. Symp. on Information Theory (ISIT 2011), Saint Petersburg, Russia, August 2011, pp. 26812685.
    22. 22)
      • 22. Faugère, J.-C., Otmani, A., Perret, L., Tillich, J.-P.: ‘Algebraic cryptanalysis of compact McEliece's variants – toward a complexity analysis’. Proc. Second Int. Conf. on Symbolic Computation and Cryptography, Egham, UK, June 2010, pp. 4555.
    23. 23)
      • 23. Gallager, R.G.: ‘Low-density parity-check codes’, IRE Trans. Inf. Theory, 1962, IT-8, pp. 2128 (doi: 10.1109/TIT.1962.1057683).
    24. 24)
      • 24. Tanner, R.M.: ‘A recursive approach to low complexity codes’, IEEE Trans. Inf. Theory, 1981, 27, (5), pp. 533547 (doi: 10.1109/TIT.1981.1056404).
    25. 25)
      • 25. MacKay, D.J.C.: ‘Good error correcting codes based on very sparse matrices’, IEEE Trans. Inf. Theory, 1999, 45, (2), pp. 399432 (doi: 10.1109/18.748992).
    26. 26)
      • 26. Richardson, T., Urbanke, R.: ‘The renaissance of Gallager's low-density parity-check codes’, IEEE Commun. Mag., 2003, 41, (8), pp. 126131 (doi: 10.1109/MCOM.2003.1222728).
    27. 27)
      • 27. Richardson, T.J., Urbanke, R.L.: ‘The capacity of low-density parity-check codes under message-passing decoding’, IEEE Trans. Inf. Theory, 2001, 47, (2), pp. 599618 (doi: 10.1109/18.910577).
    28. 28)
      • 28. Tanner, R., Sridhara, D., Fuja, T.: ‘A class of group-structured LDPC codes’. Proc. Int. Symp. on Communication Theory and Applications (ISCTA 01), Ambleside, UK, July 2001, pp. 365370.
    29. 29)
      • 29. Chen, L., Xu, J., Djurdjevic, I., Lin, S.: ‘Near-Shannon-limit quasi-cyclic low-density parity-check codes’, IEEE Trans. Commun., 2004, 52, (7), pp. 10381042 (doi: 10.1109/TCOMM.2004.831353).
    30. 30)
      • 30. Monico, C., Rosenthal, J., Shokrollahi, A.: ‘Using low density parity check codes in the McEliece cryptosystem’. Proc. IEEE Int. Symp. on Information Theory (ISIT 2000), Sorrento, Italy, June 2000, p. 215.
    31. 31)
      • 31. Baldi, M., Chiaraluce, F., Garello, R., Mininni, F.: ‘Quasi-cyclic low-density parity-check codes in the McEliece cryptosystem’. Proc. IEEE Int. Conf. on Communications (ICC 2007), Glasgow, Scotland, June 2007, pp. 951956.
    32. 32)
      • 32. Baldi, M., Chiaraluce, F.: ‘Cryptanalysis of a new instance of McEliece cryptosystem based on QC-LDPC codes’. Proc. IEEE Int. Symp. on Information Theory (ISIT 2007), Nice, France, June 2007, pp. 25912595.
    33. 33)
      • 33. Otmani, A., Tillich, J.P., Dallot, L.: ‘Cryptanalysis of two McEliece cryptosystems based on quasi-cyclic codes’, Mathematics in Computer Science, 2010, 3, (2), pp. 129140 (doi: 10.1007/s11786-009-0015-8).
    34. 34)
      • 34. 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.
    35. 35)
      • 35. Gallager, R.G.: ‘Low-density parity-check codes’ (MIT Press, 1963).
    36. 36)
      • 36. Baldi, M., Bambozzi, F., Chiaraluce, F.: ‘On a family of circulant matrices for quasi-cyclic low-density generator matrix codes’, IEEE Trans. Inf. Theory, 2011, 57, (9), pp. 60526067 (doi: 10.1109/TIT.2011.2161953).
    37. 37)
      • 37. Pearl, J.: ‘Reverend Bayes on inference engines: a distributed hierarchical approach’. Proc. Second National Conf. on Artificial Intelligence (AAAI-82), Pittsburgh, PA, August 1982, pp. 133136.
    38. 38)
      • 38. Sun, H.M.: ‘Improving the security of the McEliece public-key cryptosystem’. ASIACRYPT 1998, Springer Verlag, 1998, (LNCS, 1514), pp. 200213.
    39. 39)
      • 39. Engelbert, D., Overbeck, R., Schmidt, A.: ‘A summary of McEliece-type cryptosystems and their security’, J. Math. Cryptol., 2007, 1, (2), pp. 151199 (doi: 10.1515/JMC.2007.009).
    40. 40)
      • 40. Winograd, S.: ‘Arithmetic Complexity of Computations’. In CBMS-NSF Regional Conf. Series in Mathematics, (Society for Industrial and Applied Mathematics, Philadelphia, 1980, vol. 33).
    41. 41)
      • 41. Fan, H., Sun, J., Gu, M., Lam, K.-Y.: ‘Overlap-free Karatsuba-Ofman polynomial multiplication algorithms’, IET Inf. Sec., 2010, 4, (1), pp. 814 (doi: 10.1049/iet-ifs.2009.0039).
    42. 42)
      • 42. Hagenauer, J., Offer, E., Papke, L.: ‘Iterative decoding of binary block and convolutional codes’, IEEE Trans. Inf. Theory, 1996, 42, (2), pp. 429445 (doi: 10.1109/18.485714).
    43. 43)
      • 43. Baldi, M., Cancellieri, G., Chiaraluce, F.: ‘Finite-precision analysis of demappers and decoders for LDPC-coded M-QAM-systems’, IEEE Trans. Broadcast., 2009, 55, (2), pp. 239250 (doi: 10.1109/TBC.2009.2016498).
    44. 44)
      • 44. Zarrinkhat, P., Banihashemi, A.: ‘Threshold values and convergence properties of majority-based algorithms for decoding regular low-density parity-check codes’, IEEE Trans. Commun., 2004, 52, (12), pp. 20872097 (doi: 10.1109/TCOMM.2004.838738).
    45. 45)
      • 45. Miladinovic, N., Fossorier, M.P.C.: ‘Improved bit-flipping decoding of low-density parity-check codes’, IEEE Trans. Inf. Theory, 2005, 51, (4), pp. 15941606 (doi: 10.1109/TIT.2005.844095).
    46. 46)
      • 46. Cho, J., Sung, W.: ‘Adaptive threshold technique for bit-flipping decoding of low-density parity-check codes’, IEEE Commun. Lett., 2010, 14, (9), pp. 857859 (doi: 10.1109/LCOMM.2010.072310.100599).
    47. 47)
      • 47. Faugère, J.-C., Otmani, A., Perret, L., Tillich, J.-P.: ‘A distinguisher for high rate McEliece cryptosystems’. Proc. IEEE Information Theory Workshop (ITW), Paraty, Brazil, October 2011, pp. 282286.
    48. 48)
      • 48. Baldi, M., Chiaraluce, F., Garello, R.: ‘On the usage of quasi-cyclic low-density parity-check codes in the McEliece cryptosystem’. Proc. First Int. Conf. on Communications and Electronics (HUT-ICCE'06), Hanoi, Vietnam, October 2006, pp. 305310.
    49. 49)
      • 49. Canteaut, A.: ‘Attaques de cryptosystemes a mots de poids faible et construction de fonctions t-resilientes’, PhD dissertation, Universite Paris, 6 October 1996.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2012.0127
Loading

Related content

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