Polar codes are novel and efficient error-correcting codes with low encoding and decoding complexities. These codes have a channel-dependent generator matrix, which is determined by the code dimension, code length and transmission channel parameters. A variant of the McEliece public-key cryptosystem based on polar codes, called the PKC-PC, is studied. Since the structure of the polar codes’ generator matrix depends on the parameters of the channel, the authors have used an efficient approach to conceal their generator matrix. The proposed approach is based on a random selection of rows of the matrix by which a random generator matrix is constructed. Using the characteristics of polar codes and introducing an efficient approach, they could reduce the public and secret key sizes, and computational complexity compared to the McEliece cryptosystem. Moreover, they show that PKC-PC yields an increased security level against conventional attacks as well as possible vulnerabilities to the code-based public-key cryptosystems. Furthermore, they prove the security of the authors’ cryptosystem and show that its security is reduced to solve NP-complete problems, called polar parameterised syndrome decoding and polar parameterised codeword existence.

References

1. 1)
  - 22. Couvreur, A., Tillich, J. P., Otmani, A.: ‘Polynomial time attack on wild McEliece over quadratic extensions’. Proc. EUROCRYPT, Copenhagen, Denmark, 11–15 May 2014, pp. 17–39.
2. 2)
  - 39. Pointcheval, D.: ‘Chosen-ciphertext security for any one-way cryptosystem’. Proc. Int. Workshop on Public Key Cryptography (PKC), Melbourne, Victoria, Australia, 18–20 January 2000, pp. 129–146.
3. 3)
  - 17. Johansson, T., Londahl, C.: ‘A new version of McEliece PKC based on convolutional codes’. Proc. Int. Conf. on Inf. and Commun. Security (ICICS), Hong Kong, China, 29–31 October 2012, pp. 461–470.
4. 4)
  - 10. 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., 2013, 7, (3), pp. 212–220.
5. 5)
  - 43. Couvreur, A., Gaborit, P., Gauthier- Umaña, V., et al ‘Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes’, Des. Codes Cryptography, 2014, 73, (2), pp. 641–666.
6. 6)
  - 21. Koochak Shooshtari, M., Ahmadian-Attari, M., Johansson, T., et al: ‘Cryptanalysis of McEliece cryptosystem variants based on quasi-cyclic low-density parity check codes’, IET Inf. Secur., 2015, 7, (3), pp. 194–202.
7. 7)
  - 6. McEliece, R.J.: ‘A public-key cryptosystem based on algebraic coding theory’. DNS Progress Rep., Jet Propulsion Laboratory, CA, Pasadena, 1978, pp. 114–116.
8. 8)
  - 14. Barreto, P.S.L.M., Lindner, R., Misoczki, R.: ‘Monoidic codes in cryptography’. Proc. 4th Int. Workshop on Post-Quantum Cryptography (PQCrypto), Taipei, Taiwan, 2011, November 29–December 2, pp. 179–199.
9. 9)
  - 36. Goli, H. A., Hassani, S. H., Urbanke, R.: ‘Universal bounds on the scaling behavior of polar codes’. Proc. IEEE Int. Symp. Inf. Theory (ISIT), Cambridge, MA, USA, 1–6 July 2012, pp. 1957–1961.
10. 10)
  - 8. Sidelnikov, V. M.: ‘A public-key cryptosytem based on Reed-Muller codes’, Discrete Math. Appl., 1994, 4, (3), pp. 191–207.
11. 11)
  - 12. Bernstein, D. J., Lange, T., Peters, C.: ‘Wild McEliece’. Proc. Int. Workshop on Selected Areas in Cryptography (SAC), Waterloo, Canada, 2010, pp. 143–158.
12. 12)
  - 11. Koochak Shooshtari, M., Ahmadian-Attari, M., Payandeh, A.: ‘Improving the security of McEliece-like public key cryptosystem based on LDPC codes’. Proc. 11th Int. Conf. on Advanced Communication Technology (ICACT), Phoenix Park, South Korea, 15–18 February 2009, pp. 1050–1053.
13. 13)
  - 42. Faugere, J.C., Gauthier-Umana, V., Otmani, A., et al: ‘A distinguisher for high-rate McEliece cryptosystems’, IEEE Trans Inf. Theory, 2013, 59, (10), pp. 6830–6844.
14. 14)
  - 47. Hooshmand, R., Koochak Shooshtari, M., Eghlidos, T., et al: ‘Reducing the key length of McEliece cryptosystem using polar codes’. Proc. Int. ISC Conf. on Inf. Security and Cryptology (ISCISC), Iran, Tehran, 3–4 September 2014, pp. 104–108.
15. 15)
  - 31. Hooshmand, R., Aref, M.R.: ‘Efficient polar code-based physical layer encryption scheme’, IEEE Wirel. Commun. Lett., 2017, 6, (6), pp. 710–713.
16. 16)
  - 41. Finiasz, M.: ‘NP-completeness of certain sub-classes of the syndrome decoding problem’, arXiv: 0912.0453v1, 2009.
17. 17)
  - 32. Bardet, M., Chaulet, J., Dragoi, V., et al: ‘Cryptanalysis of the McEliece public key cryptosystem based on polar codes’. Proc. Int. Workshop on Post-Quantum Cryptography (PQCrypto), Fukuoka, Japan, 24–26 February 2016, pp. 118–143.
18. 18)
  - 44. Shrestha, S.R., Kim, Y.S.: ‘New McEliece cryptosystem based on polar codes as a candidate for post-quantum cryptography’. Proc. Int. Symp. on Commun. and Inf. Technologies (ISCIT), Incheon, South Korea, 24–26 September 2014, pp. 368–372.
19. 19)
  - 33. Arıkan, E., ‘Systematic polar coding’, IEEE Commun. Lett., 2011, 15, (8), pp. 860–862.
20. 20)
  - 9. Baldi, M., Chiaraluce, F.: ‘Cryptanalysis of a new instance of McEliece cryptosystem based on QC-LDPC codes’. Proc. IEEE Int. Symp. Inf. Theory (ISIT), Nice, France, 2007, pp. 2591–2595.
21. 21)
  - 25. Faugère, J.C., Otmani, A., Perret, L., et al ‘Structural cryptanalysis of McEliece schemes with compact keys’, Des. Codes Cryptogr., 2015, 79, (1), pp. 87–112.
22. 22)
  - 35. Goela, G., Korada, S. B., Gastpar, M.: ‘On LP decoding of polar codes’. Proc. IEEE Inf. Theory Workshop (ITW), Dublin, Ireland, 30 Aug.-3 Sept 2010, pp. 1–5.
23. 23)
  - 19. Sidelnikov, V.M., Shestakov, S. O., ‘On the insecurity of cryptosystems based on generalized Reed-Solomon codes’, Discrete Math. Appl., 1992, 1, (4), pp. 439–444.
24. 24)
  - 34. Arıkan, E.: ‘A performance comparison of polar codes and Reed-Muller codes’, IEEE Commun. Lett., 2008, 12, (6), pp. 447–449.
25. 25)
  - 7. Niederreiter, H.: ‘Knapsack-type cryptosystems and algebraic coding theory’, Probl. Control Inf. Theory, 1986, 15, (2), pp. 159–166.
26. 26)
  - 20. Minder, L., Shokrollahi, M.A.: ‘Cryptanalysis of the Sidelnikov cryptosystem’, 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2007), Barcelona, Spain, 2007, pp. 347–360.
27. 27)
  - 45. Prange, E., ‘The use of information sets in decoding cyclic codes’, IRE Trans. Inf. Theory, 1962, 8, (5), pp. 5–9.
28. 28)
  - 29. Hooshmand, R., Aref, M.R.: ‘Polar code-based secure channel coding scheme with small key size’, IET Commun., 2017, 11, (15), pp. 2357–2361.
29. 29)
  - 2. Bernstein, D. J., Buchmann, J., Dahmen, E.: ‘Post-quantum cryptography’ (Springer-Verlag Berlin Heidelberg, 2009, 1st edn.).
30. 30)
  - 30. Hooshmand, R., Aref, M. R., Eghlidos, T.: ‘Physical layer encryption scheme using finite-length polar codes’, IET Commun., 2015, 9, (15), pp. 1857–1866.
31. 31)
  - 37. Kobara, K., Imai, H.: ‘Semantically secure McEliece public-key cryptosystems conversions for McEliece PKC’. Proc. Int. Workshop on Practice and Theory in Public Key Cryptosystems, Cheju Island, Korea, 13–15 February 2001, pp. 19–35.
32. 32)
  - 23. Perret, L., de Portzamparc, F., Faug`ere, J.C.: ‘Algebraic attack against variants of McEliece with Goppa polynomial of a special form’. Proc. ASIACRYPT, Kaohsiung, Taiwan, 7–11 December 2014, pp. 21–41.
33. 33)
  - 38. Fujisaki, E., Okamoto, T., ‘Secure integration of asymmetric and symmetric encryption schemes’, J. Cryptol., 2013, 26, (1), pp. 80–101.
34. 34)
  - 4. Berlekamp, E.R., McEliece, R.J., van Tilborg, H.C.A.: ‘On the inherent intractability of certain coding problems’, IEEE Trans. Inf. Theory, 1978, 24, (5), pp. 384–386.
35. 35)
  - 46. Stern, J.: ‘A method for finding codewords of small weight’. Proc. Int. Colloquium on Coding Theory and Applications, Toulon, France, 1988, pp. 106–113.
36. 36)
  - 40. Baldi, M., Barenghi, A., Chiaraluce, F., et al: ‘LEDAkem and LEDApkc, website, https://www.ledacrypt.org/.
37. 37)
  - 16. Misoczki, R., Tillich, J.P., Sendrier, N., et al: ‘MDPC-McEliece: new McEliece variants from moderate density parity-check codes’. Proc. IEEE Int. Symp. on Inf. Theory (ISIT), Istanbul, Turkey, 2013, pp. 2069–2073.
38. 38)
  - 24. Landais, G., Tillich, J. P.: ‘An efficient attack of a McEliece cryptosystem variant based on convolutional codes’. Proc. PQCrypto, Limoges, France, 4–7 June 2013, pp. 102–117.
39. 39)
  - 13. Lange, T., Peters, C., Bernstein, D. J.: ‘Wild McEliece incognito’. Proc. Int. Workshop on Post-Quantum Cryptography (PQCrypto), Taipei, Taiwan, 2011, November 29 – December 2, pp. 244–254.
40. 40)
  - 3. ‘Post-Quantum Cryptography Project’, accessed 25 November 2018.
41. 41)
  - 26. Arıkan, E.: ‘Channel polarization: a method for constructing capacity-achieving codes for symmetric binary-input memoryless channels’, IEEE Trans. Inf. Theory, 2009, 55, (7), pp. 3051–3073.
42. 42)
  - 28. Hooshmand, R., Aref, M.R., Eghlidos, T.: ‘Secret key cryptosystem based on non-systematic polar codes’, Wirel. Pers. Commun., 2015, 84, (2), pp. 1345–1373.
43. 43)
  - 5. Johansson, T., Jonsson, F.: ‘On the complexity of some cryptographic problems based on the general decoding problem’, IEEE Trans. Inf. Theory, 2002, 8, (10), pp. 2669–2678.
44. 44)
  - 18. Hooshmand, R., Aref, M.R.: ‘Public key cryptosystem based on low density lattice codes’, Wirel. Personal Commun., 2016, 92, (3), pp. 1107–1123.
45. 45)
  - 27. Mahdavifar, H., Vardy, A., ‘Achieving the secrecy capacity of wiretap channels using polar codes’, IEEE Trans. Inf. Theory, 2011, 57, (10), pp. 6428–6443.
46. 46)
  - 1. Shor, P.W.: ‘Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer’, SIAM J. Comput., 1997, 26, (5), pp. 1484–1509.
47. 47)
  - 15. Misoczki, R., Tillich, J.P., Sendrier, N., et al: ‘MDPC-McEliece: new McEliece variants from moderate density parity-check codes’, IACR Cryptology ePrint Archive, Report 2012/409, 2012.

PKC-PC: A variant of the McEliece public-key cryptosystem based on polar codes

References

Related content