A joint encryption-encoding scheme using QC-LDPC codes based on finite geometry

Document Type : Article

Authors

1 Information Systems and Security Laboratory, Department of Electrical Engineering, Sharif University of Technology, Tehran 11155-11365, Iran

2 Electronics Research Institute, Sharif University of Technology, Tehran 11155-11365, Iran

Abstract

Joint encryption encoding schemes have been released to fulfill both reliability and security desires in a single step. Using Low Density Parity-Check (LDPC) codes in joint encryption encoding schemes, as an alternative to classical linear codes, would shorten the key size as well as improving error correction capability. In this article, a joint encryption encoding scheme using Quasi-Cyclic Low Density Parity-Check (QC-LDPC) codes based on finite geometry is presented. It is observed that our proposed scheme not only outperforms its predecessors in key size and transmission rate, but also remains secure against all known cryptanalyses of code-based secret key cryptosystems. In this paper, we have proposed an idea to make QC-LDPC based cryptosystems secure against reaction attacks. It is subsequently shown that our scheme benefits from low computational complexity. By taking the advantage of QC-LDPC codes based on finite geometry, the key size of our scheme is very close to its target security level. In addition, using the proposed scheme, a wide range of desirable transmission rates are achievable. This variety of codes makes our cryptosystem suitable for a number of different communication and cryptographic standards such as wireless personal area networks (WPAN) and digital video broadcasting (DVB).

Keywords


References:
1. McEliece, R.J. "A public-key cryptosystem based on algebraic coding theory", DSN Progress Report, 42(44), pp. 114-116 (1978). NASA Code 310-10-67-11.
2. Berlekamp, E., McEliece, R., and van Tilborg, H. "On the inherent intractability of certain coding problems (corresp.)", IEEE Transactions on Information Theory, 24(3), pp. 384-386 (1978). DOI: 10.1109/TIT.1978.1055873.
3. Rao, T.R.N. "Joint encryption and error correction schemes", ACM SIGARCH Computer Architecture News, 12(3), pp. 240-241 (1984). DOI: 10.1145/773453.808188.
4. Rao, T. and Nam, K.H. "Private-key algebraiccoded cryptosystems", in Advances in Cryptology - CRYPTO' 86, 263, (Santa Barbara, California, USA), pp. 35-48, Springer, August (1986). DOI: 10.1007/3- 540-47721-7 3.
5. Struik, R. and van Tilburg, J. "The Rao-Nam scheme is insecure against a chosen-plaintext attack", in Advances in Cryptology - CRYPTO '87, 293, (Santa Barbara, California, USA), pp. 445-457, Springer, August (1987). DOI: 10.1007/3-540-48184-2 40.
6. Barbero, A.I. and Ytrehus, . "Modifications of the rao-nam cryptosystem", in Coding Theory, Cryptography and Related Areas, (Berlin, Heidelberg), pp. 1-12, Springer (2000). DOI: 10.1007/978-3-642-57189-3 1.
7. Hooshmand, R., Eghlidos, T., and Aref, M.R. "Improving the Rao-Nam secret key cryptosystem using regular EDF-QC-LDPC codes", The ISC International Journal of Information Security, 4(1), pp. 3-14 (2012). DOI: 10.22042/isecure.2015.4.1.2.
8. Esmaeili, M., Dakhilalian, M., and Gulliver, T.A. "New secure channel coding scheme based on randomly punctured quasi-cyclic-low density parity check codes", IET Communications, 8(14), pp. 2556-2562 (2014). DOI: 10.1049/iet-com.2014.0101.
9. Esmaeili, M. and Gulliver, T.A. "Joint channel codingcryptography based on random insertions and deletions in quasi-cyclic-low-density parity check codes", IET Communications, 9(12), pp. 1555-1560 (2015). DOI: 10.1049/iet-com.2015.0026.
10. Esmaeili, M. and Gulliver, T.A. "A secure code based cryptosystem via random insertions, deletions, and errors", IEEE Communications Letters, 20(5), pp. 870-873 (2016). DOI: 10.1109/LCOMM.2016.2540625.
11. Esmaeili, M. and Gulliver, T.A. "Code-based security with random interleaving", IET Communications, 11(8), pp. 1195-1198 (2017). DOI: 10.1049/ietcom. 2016.0303.
12. Lee, Y., Kim, Y.-S., and No, J.-S. "Ciphertextonly attack on linear feedback shift register-based Esmaeili-Gulliver cryptosystem", IEEE Communications Letters, 21(5), pp. 971-974 (2017). DOI: 10.1109/LCOMM.2017.2654238.
13. Mafakheri, B., Eghlidos, T., and Pilaram, H. "An efficient secure channel coding scheme based on polar codes", The ISC International Journal of Information Security, 9(2), pp. 13-20 (2017). DOI: 10.22042/isecure. 2017.84609.380.
14. Han, X., Chen, D., Zhang, C., et al. "Joint encryption and channel coding scheme based on balancing indices and polar codes", in 2019 IEEE 19th International Conference on Communication Technology (ICCT), pp. 276-282, October (2019). DOI: 10.1109/ICCT46805.2019.8947156.
15. Stuart, C.M. and Deepthi, P. "Nonlinear cryptosystem based on qc-ldpc codes for enhanced security and reliability with low hardware complexity and reduced key size", Wireless Personal Communications, 96(3), pp. 4177-4197 (2017). DOI: 10.1007/s11277-017-4376- z.
16. Guan, W. and Liang, L. "Efficient secure channel coding based on qpp-block-ldpc codes", Wireless Personal Communications, 98(1), pp. 1001-1014 (2018). DOI: 10.1007/s11277-017-4905-9.
17. Bagheri, K., Eghlidos, T., Sadeghi, M.R., et al. "A joint encryption, channel coding and modulation scheme using QC-LDPC lattice-codes", IEEE Transactions on Communications, 68(8), pp. 4673-4693 (2020). DOI: 10.1109/TCOMM.2020.2996781.
18. Baldi, M., Chiaraluce, F., Garello, R., et al. "Quasicyclic low-density parity-check codes in the mceliece cryptosystem", in Proc. 2007 IEEE International Conference on Communications, (Glasgow, UK), pp. 951- 956, June (2007). DOI: 10.1109/ICC.2007.161.
19. Baldi, M. and Chiaraluce, F. "Cryptanalysis of a new instance of McEliece cryptosystem based on QC-LDPC codes", in Proc. 2007 IEEE International Symposium on Information Theory, (Nice, France), pp. 2591-2595, June (2007). DOI: 10.1109/ISIT.2007.4557609.
20. Baldi, M., Bianchi, M., Maturo, N., et al. "Improving the efficiency of the LDPC code-based McEliece cryptosystem through irregular codes", in Proc. 2013 IEEE Symposium on Computers and Communications (ISCC), (Split, Croatia), pp. 197-202, July (2013). DOI: 10.1109/ISCC.2013.6754945.
21. Lin, S. and Costello, D.J., Error Control Coding: Fundamentals and Applications., Pearson-Prentice Hall (2004). ISBN: 0130426725.
22. Ryan, W. and Lin, S., Channel Codes: Classical and Modern. Cambridge University Press (2009). ISBN 1139483013, 9781139483018.
23. Fabsic, T., Hromada, V., Stankovski, P., et al. "A reaction attack on the QC-LDPC McEliece cryptosystem", in Post-Quantum Cryptography, (Cham), pp. 51-68, Springer, June (2017). DOI: 10.1007/978-3-319-59879- 6 4.
24. Ben-Israel, A. and Greville, T.N., Generalized Inverses: Theory and Applications, 15. Springer Science & Business Media (2003). DOI: 10.1007/b97366.
25. ETSI, "Digital video broadcasting (dvb); implementation guidelines for the second generation system for broadcasting, interactive services, news gathering and other broadband satellite applications; part 1: Dvbs2" (2015).
26. IEEE, "Wireless medium access control (mac) and physical layer (phy) specifications for high rate wireless personal area networks (wpans) amendment 2: Millimeter-wave-based alternative physical layer extension" (2009).
27. ITU-T, "Unified high-speed wireline-based home networking transceivers - system architecture and physical layer specification" (2015). 
28. Baldi, M., Bianchi, M., and Chiaraluce, F. "Optimization of the parity-check matrix density in qc-ldpc code-based mceliece cryptosystems", in Proc. 2013 IEEE International Conference on Communications Workshops (ICC), (Budapest, Hungary), pp. 707-711, June (2013). DOI: 10.1109/ICCW.2013.6649325.
29. Dent, A.W. "Fundamental problems in provable security and cryptography", Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 364(1849), pp. 3215-3230 (2006). DOI: 10.1098/rsta.2006.1895.
30. Bellare, M., Desai, A., Jokipii, E., et al. "A concrete security treatment of symmetric encryption", in Proc. 38th Annual Symposium on Foundations of Computer Science, (Miami Beach, FL, USA), pp. 394-403, IEEE, October (1997). DOI: 10.1109/SFCS.1997.646128.
31. Menezes, A. "Another look at provable security", in Advances in Cryptology - EUROCRYPT 2012, 7237, (Cambridge, UK), p. 8, Springer, April (2012). DOI: 10.1007/978-3-642-29011-4 2.
32. Lee, P.J. and Brickell, E.F. "An observation on the security of McEliece's public-key cryptosystem", in Advances in Cryptology - EUROCRYPT '88, 330, (Davos, Switzerland), pp. 275-280, Springer, May (1988). DOI: 10.1007/3-540-45961-8 25.
33. Becker, A., Joux, A., May, A., et al. "Decoding random binary linear codes in 2 n/20: how 1 + 1 = 0 improves information set decoding", in Advances in Cryptology - EUROCRYPT 2012, 7237, (Cambridge, UK), pp. 520-536, Springer, April (2012). DOI: 10.1007/978-3- 642-29011-4 31.
34. May, A. and Ozerov, I. "On computing nearest neighbors with applications to decoding of binary linear codes", in Advances in Cryptology-EUROCRYPT 2015, 9056, (Sofia, Bulgaria), pp. 203-228, April (2015). DOI: 10.1007/978-3-662-46800-5 9.
35. Berson, T.A. "Failure of the McEliece public-Key cryptosystem under message-resend and related-message attack", in Advances in Cryptology - CRYPTO '97, 1294, (Santa Barbara, California, USA), pp. 213-220, Springer, August (1997). DOI: 10.1007/BFb0052237.
36. Rao, T. and Nam, K.H. "Private-key algebraic-code encryptions", IEEE Transactions on Information Theory, 35(4), pp. 829-833 (1989). DOI: 10.1109/18.32159.
37. Guo, Q., Johansson, T., and Stankovski, P. "A key recovery attack on mdpc with cca security using decoding errors", in Advances in Cryptology - ASIACRYPT 2016, 10031, (Berlin, Heidelberg), pp. 789- 815, Springer, November (2016). DOI: 10.1007/978-3- 662-53887-6 29.
38. Santini, P., Baldi, M., Cancellieri, G., et al. "Hindering reaction attacks by using monomial codes in the mceliece cryptosystem", in 2018 IEEE International Symposium on Information Theory (ISIT), pp. 951- 955 (2018). DOI: 10.1109/ISIT.2018.8437553.
39. Tillich, J.-P. "The decoding failure probability of mdpc codes", in 2018 IEEE International Symposium on Information Theory (ISIT), pp. 941-945 (2018). DOI: 10.1109/ISIT.2018.8437843.
40. Santini, P., Battaglioni, M., Baldi, M., et al. "Analysis of the error correction capability of ldpc and mdpc codes under parallel bit- ipping decoding and application to cryptography", IEEE Transactions on Communications, 68(8), pp. 4648-4660 (2020). DOI: 10.1109/TCOMM.2020.2987898.
41. Santini, P., Battaglioni, M., Baldi, M., et al. "Harddecision iterative decoding of ldpc codes with bounded error rate", in ICC 2019 - 2019 IEEE International Conference on Communications (ICC), pp. 1-6 (2019). DOI: 10.1109/ICC.2019.8761536.
42. Santini, P., Battaglioni, M., Chiaraluce, F., et al. "Analysis of reaction and timing attacks against cryptosystems based on sparse parity-check codes", in Code-Based Cryptography, (Cham), pp. 115-136, Springer, July (2019). DOI: 10.1007/978-3-030-25922- 8 7.
43. Berbain, C., Billet, O., Canteaut, A., et al. "Sosemanuk, a fast software-oriented stream cipher", Lecture Notes in Computer Science, 4986, pp. 98-118 (2008). DOI: 10.1007/978-3-540-68351-3 9.
44. Sobhi Afshar, A., Eghlidos, T., and Aref, M.R. "Efficient secure channel coding based on quasi-cyclic low-density parity-check codes", IET Communications, 3(2), pp. 279-292 (2009). DOI: 10.1049/ietcom: 20080050.
45. Zhang, Z., Dolecek, L., Nikolic, B., et al. "Lowering ldpc error  floors by postprocessing", in IEEE GLOBECOM 2008 - 2008 IEEE Global Telecommunications Conference, pp. 1-6 (2008). DOI: 10.1109/GLOCOM. 2008.ECP.590.
46. Zhang, S. and Schlegel, C. "Controlling the error floor in ldpc decoding", IEEE Transactions on Communications, 61(9), pp. 3566-3575 (2013). DOI: 10.1109/TCOMM.2013.071813.120659.
47. Angarita, F., Valls, J., Almenar, V., et al. "Reducedcomplexity min-sum algorithm for decoding ldpc codes with low error- floor", IEEE Transactions on Circuits and Systems I: Regular Papers, 61(7), pp. 2150-2158 (2014). DOI: 10.1109/TCSI.2014.2304660.
48. Baldi, M., Bodrato, M., and Chiaraluce, F. "A new analysis of the mceliece cryptosystem based on qcldpc codes", Security and Cryptography for Networks, 5229, pp. 246-262 (2008). DOI: 10.1007/978-3-540- 85855-3 17.
Volume 31, Issue 17
Transactions on Computer Science & Engineering and Electrical Engineering (D)
November and December 2024
Pages 1504-1516