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
£12.50
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.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 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)
      • R.J. McEliece . (1978)
        1. McEliece, R.J.: ‘A public-key cryptosystem based on algebraic coding theory’. DSN Progress Report, 1978, pp. 114116.
        .
    2. 2)
      • P. Lee , E. Brickell .
        2. Lee, P., Brickell, E.: ‘An observation on the security of McEliece's public-key cryptosystem’. Advances in Cryptology – EUROCRYPT 88, 1988, pp. 275280.
        . Advances in Cryptology – EUROCRYPT 88 , 275 - 280
    3. 3)
      • J. Stern . (1989)
        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)
      • A. Canteaut , F. Chabaud .
        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).
        . IEEE Trans. Inf. Theory , 1 , 367 - 378
    5. 5)
      • D.J. Bernstein , T. Lange , C. Peters .
        5. Bernstein, D.J., Lange, T., Peters, C.: ‘Attacking and defending the McEliece cryptosystem’. Post-Quantum Cryptography, Springer Verlag, 2008, (LNCS, 5299), pp. 3146.
        . Post-Quantum Cryptography , 31 - 46
    6. 6)
      • C. Peters .
        6. Peters, C.: ‘Information-set decoding for linear codes over Fq’. Post-Quantum Cryptography, Springer Verlag, 2010, (LNCS, 6061), pp. 8194.
        . Post-Quantum Cryptography , 81 - 94
    7. 7)
      • A. May , A. Meurer , E. Thomae .
        7. May, A., Meurer, A., Thomae, E.: ‘Decoding random linear codes in O(20.054n)’. ASIACRYPT 2011, Springer Verlag, 2011, (LNCS, 7073), pp. 107124.
        . ASIACRYPT 2011 , 107 - 124
    8. 8)
      • D.J. Bernstein , T. Lange , C. Peters .
        8. Bernstein, D.J., Lange, T., Peters, C.: ‘Smaller decoding exponents: ball-collision decoding’. CRYPTO 2011, Springer Verlag, 2011, (LNCS, 6841), pp. 743760.
        . CRYPTO 2011 , 743 - 760
    9. 9)
      • A. Becker , A. Joux , A. May , A. Meurer .
        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.
        . EUROCRYPT 2012 , 520 - 536
    10. 10)
      • H. Niederreiter .
        10. Niederreiter, H.: ‘Knapsack-type cryptosystems and algebraic coding theory’, Probl. Control Inf. Theory, 1986, 15, pp. 159166.
        . Probl. Control Inf. Theory , 159 - 166
    11. 11)
      • V. Sidelnikov , S. Shestakov .
        11. Sidelnikov, V., Shestakov, S.: ‘On cryptosystems based on generalized Reed-Solomon codes’, Diskretnaya Math., 1992, 4, pp. 5763.
        . Diskretnaya Math. , 57 - 63
    12. 12)
      • Y.X. Li , R. Deng , X.M. Wang .
        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).
        . IEEE Trans. Inf. Theory , 1 , 271 - 273
    13. 13)
      • R. Overbeck .
        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).
        . J. Cryptol. , 2 , 280 - 301
    14. 14)
      • C. Wieschebrink .
        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.
        . Post-quantum cryptography: PQCrypto 2010 , 61 - 72
    15. 15)
      • T.P. Berger , P.-L. Cayrel , P. Gaborit , A. Otmani .
        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.
        . Progress in Cryptology – AFRICACRYPT 2009 , 77 - 97
    16. 16)
      • R. Misoczki , P.S.L.M. Barreto .
        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.
        . Selected Areas in Cryptography , 376 - 392
    17. 17)
      • M. Baldi .
        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.
        . NATO Science for Peace and Security Series – D: Information and Communication Security , 160 - 174
    18. 18)
      • A. Sobhi Afshar , T. Eghlidos , M. Aref .
        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).
        . IET Commun. , 2 , 279 - 292
    19. 19)
      • V.G. Umana , G. Leander .
        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.
        . Proc. Second Int. Conf. on Symbolic Computation and Cryptography , 27 - 44
    20. 20)
      • J.-C. Faugère , A. Otmani , L. Perret , J.-P. Tillich .
        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.
        . EUROCRYPT 2010 , 279 - 298
    21. 21)
      • M. Barbier , P. Barreto .
        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.
        . Proc. IEEE Int. Symp. on Information Theory (ISIT 2011) , 2681 - 2685
    22. 22)
      • J.-C. Faugère , A. Otmani , L. Perret , J.-P. Tillich .
        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.
        . Proc. Second Int. Conf. on Symbolic Computation and Cryptography , 45 - 55
    23. 23)
      • R.G. Gallager .
        23. Gallager, R.G.: ‘Low-density parity-check codes’, IRE Trans. Inf. Theory, 1962, IT-8, pp. 2128 (doi: 10.1109/TIT.1962.1057683).
        . IRE Trans. Inf. Theory , 21 - 28
    24. 24)
      • R.M. Tanner .
        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).
        . IEEE Trans. Inf. Theory , 5 , 533 - 547
    25. 25)
      • D.J.C. MacKay .
        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).
        . IEEE Trans. Inf. Theory , 2 , 399 - 432
    26. 26)
      • T. Richardson , R. Urbanke .
        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).
        . IEEE Commun. Mag. , 8 , 126 - 131
    27. 27)
      • T.J. Richardson , R.L. Urbanke .
        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).
        . IEEE Trans. Inf. Theory , 2 , 599 - 618
    28. 28)
      • R. Tanner , D. Sridhara , T. Fuja .
        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.
        . Proc. Int. Symp. on Communication Theory and Applications (ISCTA 01) , 365 - 370
    29. 29)
      • L. Chen , J. Xu , I. Djurdjevic , S. Lin .
        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).
        . IEEE Trans. Commun. , 7 , 1038 - 1042
    30. 30)
      • C. Monico , J. Rosenthal , A. Shokrollahi .
        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.
        . Proc. IEEE Int. Symp. on Information Theory (ISIT 2000) , 215
    31. 31)
      • M. Baldi , F. Chiaraluce , R. Garello , F. Mininni .
        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.
        . Proc. IEEE Int. Conf. on Communications (ICC 2007) , 951 - 956
    32. 32)
      • M. Baldi , F. Chiaraluce .
        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.
        . Proc. IEEE Int. Symp. on Information Theory (ISIT 2007) , 2591 - 2595
    33. 33)
      • A. Otmani , J.P. Tillich , L. Dallot .
        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).
        . Mathematics in Computer Science , 2 , 129 - 140
    34. 34)
      • M. Baldi , M. Bodrato , F. Chiaraluce .
        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.
        . Security and Cryptography for Networks , 246 - 262
    35. 35)
      • R.G. Gallager . (1963)
        35. Gallager, R.G.: ‘Low-density parity-check codes’ (MIT Press, 1963).
        .
    36. 36)
      • M. Baldi , F. Bambozzi , F. Chiaraluce .
        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).
        . IEEE Trans. Inf. Theory , 9 , 6052 - 6067
    37. 37)
      • J. Pearl .
        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.
        . Proc. Second National Conf. on Artificial Intelligence (AAAI-82) , 133 - 136
    38. 38)
      • H.M. Sun .
        38. Sun, H.M.: ‘Improving the security of the McEliece public-key cryptosystem’. ASIACRYPT 1998, Springer Verlag, 1998, (LNCS, 1514), pp. 200213.
        . ASIACRYPT 1998 , 200 - 213
    39. 39)
      • D. Engelbert , R. Overbeck , A. Schmidt .
        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).
        . J. Math. Cryptol. , 2 , 151 - 199
    40. 40)
      • S. Winograd .
        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).
        . CBMS-NSF Regional Conf. Series in Mathematics, (Society for Industrial and Applied Mathematics, Philadelphia
    41. 41)
      • H. Fan , J. Sun , M. Gu , K.-Y. Lam .
        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).
        . IET Inf. Sec. , 1 , 8 - 14
    42. 42)
      • J. Hagenauer , E. Offer , L. Papke .
        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).
        . IEEE Trans. Inf. Theory , 2 , 429 - 445
    43. 43)
      • M. Baldi , G. Cancellieri , F. Chiaraluce .
        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).
        . IEEE Trans. Broadcast. , 2 , 239 - 250
    44. 44)
      • P. Zarrinkhat , A. Banihashemi .
        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).
        . IEEE Trans. Commun. , 12 , 2087 - 2097
    45. 45)
      • N. Miladinovic , M.P.C. Fossorier .
        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).
        . IEEE Trans. Inf. Theory , 4 , 1594 - 1606
    46. 46)
      • J. Cho , W. Sung .
        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).
        . IEEE Commun. Lett. , 9 , 857 - 859
    47. 47)
      • J.-C. Faugère , A. Otmani , L. Perret , J.-P. Tillich .
        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.
        . Proc. IEEE Information Theory Workshop (ITW) , 282 - 286
    48. 48)
      • M. Baldi , F. Chiaraluce , R. Garello .
        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.
        . Proc. First Int. Conf. on Communications and Electronics (HUT-ICCE'06) , 305 - 310
    49. 49)
      • A. Canteaut . (1996)
        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