Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

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

© The Institution of Engineering and Technology
Received 25/02/2011, Accepted 28/01/2013, Revised 30/12/2012, Published

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.

Inspec keywords: public key cryptography; decoding; Goppa codes; cyclic codes; parity check codes

Other keywords: quasicyclic low-density parity-check codes; Goppa codes; telecommunication standards; bit-flipping decoder; public key cryptography; system design; McEliece cryptosystem complexity; decoding problem; quantum computers

Subjects: Cryptography; Cryptography theory; Codes

References

    1. 1)
      • 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. 282–286.
    2. 2)
      • 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. 520–536.
    3. 3)
      • 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. 2087–2097 (doi: 10.1109/TCOMM.2004.838738).
    4. 4)
      • 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. 45–55.
    5. 5)
      • 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. 106–113.
    6. 6)
      • 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. 6052–6067 (doi: 10.1109/TIT.2011.2161953).
    7. 7)
      • 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. 129–140 (doi: 10.1007/s11786-009-0015-8).
    8. 8)
      • 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. 1594–1606 (doi: 10.1109/TIT.2005.844095).
    9. 9)
      • 1. McEliece, R.J.: ‘A public-key cryptosystem based on algebraic coding theory’. DSN Progress Report, 1978, pp. 114–116.
    10. 10)
      • 49. Canteaut, A.: ‘Attaques de cryptosystemes a mots de poids faible et construction de fonctions t-resilientes’, PhD dissertation, Universite Paris, 6 October 1996.
    11. 11)
      • 2. Lee, P., Brickell, E.: ‘An observation on the security of McEliece's public-key cryptosystem’. Advances in Cryptology – EUROCRYPT 88, 1988, pp. 275–280.
    12. 12)
      • 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. 305–310.
    13. 13)
      • 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. 279–292 (doi: 10.1049/iet-com:20080050).
    14. 14)
      • 39. Engelbert, D., Overbeck, R., Schmidt, A.: ‘A summary of McEliece-type cryptosystems and their security’, J. Math. Cryptol., 2007, 1, (2), pp. 151–199 (doi: 10.1515/JMC.2007.009).
    15. 15)
      • 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. 1038–1042 (doi: 10.1109/TCOMM.2004.831353).
    16. 16)
      • 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. 271–273 (doi: 10.1109/18.272496).
    17. 17)
      • 6. Peters, C.: ‘Information-set decoding for linear codes over Fq’. Post-Quantum Cryptography, Springer Verlag, 2010, (LNCS, 6061), pp. 81–94.
    18. 18)
      • 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. 365–370.
    19. 19)
      • 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. 2681–2685.
    20. 20)
      • 24. Tanner, R.M.: ‘A recursive approach to low complexity codes’, IEEE Trans. Inf. Theory, 1981, 27, (5), pp. 533–547 (doi: 10.1109/TIT.1981.1056404).
    21. 21)
      • 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.
    22. 22)
      • 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. 27–44.
    23. 23)
      • 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. 239–250 (doi: 10.1109/TBC.2009.2016498).
    24. 24)
      • 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. 2591–2595.
    25. 25)
      • 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. 279–298.
    26. 26)
      • 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. 367–378 (doi: 10.1109/18.651067).
    27. 27)
      • 23. Gallager, R.G.: ‘Low-density parity-check codes’, IRE Trans. Inf. Theory, 1962, IT-8, pp. 21–28 (doi: 10.1109/TIT.1962.1057683).
    28. 28)
      • 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. 857–859 (doi: 10.1109/LCOMM.2010.072310.100599).
    29. 29)
      • 5. Bernstein, D.J., Lange, T., Peters, C.: ‘Attacking and defending the McEliece cryptosystem’. Post-Quantum Cryptography, Springer Verlag, 2008, (LNCS, 5299), pp. 31–46.
    30. 30)
      • 10. Niederreiter, H.: ‘Knapsack-type cryptosystems and algebraic coding theory’, Probl. Control Inf. Theory, 1986, 15, pp. 159–166.
    31. 31)
      • 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. 246–262.
    32. 32)
      • 35. Gallager, R.G.: ‘Low-density parity-check codes’ (MIT Press, 1963).
    33. 33)
      • 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. 61–72.
    34. 34)
      • 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. 160–174.
    35. 35)
      • 13. Overbeck, R.: ‘Structural attacks for public key cryptosystems based on Gabidulin codes’, J. Cryptol., 2008, 21, (2), pp. 280–301 (doi: 10.1007/s00145-007-9003-9).
    36. 36)
      • 26. Richardson, T., Urbanke, R.: ‘The renaissance of Gallager's low-density parity-check codes’, IEEE Commun. Mag., 2003, 41, (8), pp. 126–131 (doi: 10.1109/MCOM.2003.1222728).
    37. 37)
      • 11. Sidelnikov, V., Shestakov, S.: ‘On cryptosystems based on generalized Reed-Solomon codes’, Diskretnaya Math., 1992, 4, pp. 57–63.
    38. 38)
      • 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. 951–956.
    39. 39)
      • 7. May, A., Meurer, A., Thomae, E.: ‘Decoding random linear codes in O(20.054n)’. ASIACRYPT 2011, Springer Verlag, 2011, (LNCS, 7073), pp. 107–124.
    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)
      • 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. 599–618 (doi: 10.1109/18.910577).
    42. 42)
      • 8. Bernstein, D.J., Lange, T., Peters, C.: ‘Smaller decoding exponents: ball-collision decoding’. CRYPTO 2011, Springer Verlag, 2011, (LNCS, 6841), pp. 743–760.
    43. 43)
      • 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. 77–97.
    44. 44)
      • 41. Fan, H., Sun, J., Gu, M., Lam, K.-Y.: ‘Overlap-free Karatsuba-Ofman polynomial multiplication algorithms’, IET Inf. Sec., 2010, 4, (1), pp. 8–14 (doi: 10.1049/iet-ifs.2009.0039).
    45. 45)
      • 16. Misoczki, R., Barreto, P.S.L.M.: ‘Compact McEliece keys from Goppa codes’. Selected Areas in Cryptography, Springer Verlag, 2009, (LNCS, 5867), pp. 376–392.
    46. 46)
      • 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. 133–136.
    47. 47)
      • 42. Hagenauer, J., Offer, E., Papke, L.: ‘Iterative decoding of binary block and convolutional codes’, IEEE Trans. Inf. Theory, 1996, 42, (2), pp. 429–445 (doi: 10.1109/18.485714).
    48. 48)
      • 25. MacKay, D.J.C.: ‘Good error correcting codes based on very sparse matrices’, IEEE Trans. Inf. Theory, 1999, 45, (2), pp. 399–432 (doi: 10.1109/18.748992).
    49. 49)
      • 38. Sun, H.M.: ‘Improving the security of the McEliece public-key cryptosystem’. ASIACRYPT 1998, Springer Verlag, 1998, (LNCS, 1514), pp. 200–213.
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
Print this page
This is a required field
Please enter a valid email address