A Cryptographic System Based on a New Class of Binary Error-Correcting Codes

Dömösi, Pál; Hannusch, Carolin; Horváth, Géza

doi:10.2478/tmmp-2019-0007

Abstract

In this paper we introduce a new cryptographic system which is based on the idea of encryption due to [McEliece, R. J. A public-key cryptosystem based on algebraic coding theory, DSN Progress Report. 44, 1978, 114–116]. We use the McEliece encryption system with a new linear error-correcting code, which was constructed in [Hannusch, C.—Lakatos, P.: Construction of self-dual binary 2²k, 2²k−1, 2^k-codes, Algebra and Discrete Math. 21 (2016), no. 1, 59–68]. We show how encryption and decryption work within this cryptosystem and we give the parameters for key generation. Further, we explain why this cryptosystem is a promising post-quantum candidate.

References

[1] BALDI, M.—BODRATO, M.—CHIARALUCE, F.: A new analysis of the Mceliece cryptosystem based on qc-ldpc codes. In: Security and Cryptography for Networks, Springer-Verlag, Berlin, 2008, pp. 246–262.10.1007/978-3-540-85855-3_17
Search in Google Scholar Back to article
[2] BERGER, T. P.—CAYREL, P.-L.—GABORIT, P.—OTMAN, A.: Reducing key length of the Mceliece cryptosystem, In: Progress in Cryptology–AFRICACRYPT, Springer-Verlag, Berlin 2009, pp.77–97.10.1007/978-3-642-02384-2_6
Search in Google Scholar Back to article
[3] BERGER, T. P., LOIDREAU, P.: How to mask the structure of codes for a cryptographic use. Designs, Codes and Cryptography, 35 (2005), no. 1, 63–79.10.1007/s10623-003-6151-2
Search in Google Scholar Back to article
[4] BERNSTEIN, D.,LANGE, T., PETERS, C.: Attacking and defending the McEliece cryptosystem. In: Proc. 2nd Internationsl Workshop on Post-Quantum Cryptography, PQ Crypto 2008, Cincinnati, OH, USA, October 17–19; Lecture Notes in Comput. Sci., Vol. 299, Springer-Verlag, 2008, pp. 31-46.
Search in Google Scholar Back to article
[5] BERSTEIN, D. J.—CHOU, T.—LANGE, T.—VON MAURICH, I.— MISOCZKI, D.—NIEDERHAGEN, D.—PERSICHETTI, E.—PETERS, S.—SCHSWABE, P.–SENDRIER, N.—SZEFER, J.—WANG, W.: Classic McEliece: conservative code-based cryptography, The First NIC PQC Workshop, 2018, April 11–13, 2018; https://classic.mceliece.org/nist/mceliece-20171129.pdf
Search in Google Scholar Back to article
[6] CAYREL, P.-L., GUEYE, C. T., NDIAYE, O., NIEBUHR, R.: Critical attacks in code-based cryptography, Int. J. Information and Coding Theory, 3 (2015), no. 2, 158–176.10.1504/IJICOT.2015.072639
Search in Google Scholar Back to article
[7] CHEN L.—LIU Y-K.—JORDAN S.—MOODY, D.—PERALTA, R.—PERLNER, R.–SMIDT-TONE, D.: Report on Post-Quantum Cryptography. NISTIR 8105, U.S. Department of Commerce, 2016.10.6028/NIST.IR.8105
Search in Google Scholar Back to article
[8] DIFFIE, W.—HELLMAN, M. E.: New directions in cryptography, IEEE Transactions on Information Theory, IT-22 (1976), 644–654.10.1109/TIT.1976.1055638
Search in Google Scholar Back to article
[9] DMÖSI, P.—HANNUSCH, C.—HORVÁTH, G.: Public Key Cryptographic Method and Apparatus for Data Encryption and Decryption Based on Error-Correcting Codes. Hungarian Intellectual Property Office, Budapest, 2018, Patent Application, P1800038.
Search in Google Scholar Back to article
[10] DUMER, I.—KABATIANSKY, G.—TAVERNIER, C.: On complexity of decoding Reed-Muller codes within their code distance. In: Proc. Eleventh International Workshop on Algebraic and Combinatorial Coding Theory 2008, pp. 82–85
Search in Google Scholar Back to article
[11] ELGAMAL, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. a.) In: Advances in cryptology: Proceedings of CRYPTO 84. Lecture Notes in Comput. Sci. Vol. 196. Springer-Verlag, Santa Barbara, California, United States, pp. 10–18; b.) IEEE Trans. on Inf. Theory 31 (1985), 469–472.10.1109/TIT.1985.1057074
Search in Google Scholar Back to article
[12] FABŠIČ, T.—HROMADA, V.—STANKOVSKI, P.—ZAJAC, P.—GUO, Q.—JOHANSSON, T.: A reaction attack on the QC-LDPC McEliece Cryptosystem. (T. Lange and T. Takagi, eds.), Post-Quantum Cryptography, Proc. 8th International Workshop, PQCrypto 2017, Utrecht, The Netherlands, June 26-28, 2017, Lecture Notes in Comput. Sci. Vol. 10346, Springer-Verlag, Berlin, 2017, pp.51–68.10.1007/978-3-319-59879-6_4
Search in Google Scholar Back to article
[13] GOPALAN, P.—KLIVANS, A. R.—ZUCKERMAN, D.: List-decoding Reed-Muller codes over small fields.In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, ACM, 2008, pp. 265–274.10.1145/1374376.1374417
Search in Google Scholar Back to article
[14] GUO, Q.—JOHANSSON, T.—STANKOVSKI, P.: A key recovery attack on MDPC with CCA security using decoding errors. In: (J. H. Cheon and T. Takagi, eds.) Advances in Cryptology. ASIACRYPT 2016, Proc. 22nd Int. Conf. on the Theory and Appplication of Cryptology and Information Security, Hanoi, Vietnam, December 4-8-2016, Part 1, Lecture Notes in Comput. Sci. Vol. 10031, Springer-Verlag, Berliln, 2016, pp. 789–815.10.1007/978-3-662-53887-6_29
Search in Google Scholar Back to article
[15] HANNUSCH, C.—LAKATOS, P.: : Construction of self-dual binary 2²k, 2²k−1, 2^k-codes, Algebra and Discrete Math. 21 (2016), no. 1, 59–68.
Search in Google Scholar Back to article
[16] KOBARA, K.—IMAI, H.: Semantically secure Mceliece public-key cryptosystems-conversions for Mceliece PKC.In:Public Key Cryptography, Cheju, Island, 2001, (K. Kim, ed.), Lecture Notes in Comput. Sci. Vol. 1992, Springer-Verlag, Berlin, 2001, pp. 19–35.10.1007/3-540-44586-2_2
Open DOI Search in Google Scholar Back to article
[17] LÖNDAHL, C.—JOHANSSON, T.: A new version of Mceliece PKC based on convolutional codes.In: Information and Communications Security, International Conference on Information and Communications Security, ICICS 2012; Lecture Notes in Comput. Sci. Vol. 7618, Springer-Verlag, Berlin, 2012, pp. 461–470.10.1007/978-3-642-34129-8_45
Search in Google Scholar Back to article
[18] JANWA, H.—MORENO, O.: Mceliece public key cryptosystems using algebraic-geometric codes. Designs, Codes and Cryptography, 8 (1996), no. 3, 293–307.10.1023/A:1027351723034
Search in Google Scholar Back to article
[19] MCELIECE, R. J.: A public-key cryptosystem based on algebraic coding theory, In: The Deep Space Network Progress Report, DSN PR 42-44, January and February 1978, pp. 114-116; https://ipnpr.jpl.nasa.gov/progress_report2/42-44/44N.PDF
Search in Google Scholar Back to article
[20] MISOCZKI, R.—BARRETO, P.: Compact Mceliece keys from Goppa codes. In: Selected Areas in Cryptography, Springer-Verlag, Berlin, 2009, pp. 376–392.10.1007/978-3-642-05445-7_24
Open DOI Search in Google Scholar Back to article
[21] MACWILLIAMS, F.J.—SLOANE, N. J. A.: The Theory of Error-Correcting Codes. Elsevier, 1977.
Search in Google Scholar Back to article
[22] MISOCZKI, R.—TILLICH, J.-P.—SENDRIER, N.—BARRETO, P.: MDPC-McEliece, New McEliece variants from moderate density parity-check codes). In: Information Theory Proceedings (ISIT), 2013, pp. 2069–2073.10.1109/ISIT.2013.6620590
Search in Google Scholar Back to article
[23] NIEDERREITER, H.: Knapsack-type cryptosystems and algebraic coding theory, Problems Control Inform. Theory/Problemy Upravlen. Teor. Inform. 15 (1986), no. 2, 159–166.
Search in Google Scholar Back to article
[24] PATERSON, K. G.—JONES, A. E.: An efficient decoding algorithms for generalized Reed-Muller codes, IEEE Transactions on Communications, 48 (2000) no. 8, (2000) 1272–1285.10.1109/26.864165
Search in Google Scholar Back to article
[25] REED, I. S.: A Class of Multiple Error Correcting Codes and the Decoding Scheme, Massachusettts Institute of Technology, Lincoln Laboratory, 1953, Technial Report no. 44.
Search in Google Scholar Back to article
[26] REPKA, M.: McEliece PKC Calculator, Journal Electr. Eng. 65 (2014), no. 6, 342–348.10.2478/jee-2014-0056
Search in Google Scholar Back to article
[27] REPKA, M.—ZAJAC, P.: : Overview of the McEliece cryptosystem and its security, Tatra Mt. Math. Publ. 60 (2014), 57–83.10.2478/tmmp-2014-0025
Search in Google Scholar Back to article
[28] RIVEST, R. L.—SHAMIR, A.—ADLEMAN, L. M.: Cryptographic Communications System and Method, Patent US 4405829 A, Massachusetts Institute of Technology, September 20, 1983; https://patentimages.storage.googleapis.com/49/43/9c/b155bf231090f6/US4405829.pdf
Search in Google Scholar Back to article
[29] SIDELNIKOV, V. M.: A public-key cryptosystem based on binary Reed-Muller codes, Discrete Math. Appl. 4 (1994), no. 3, 191–208.10.1515/dma.1994.4.3.191
Search in Google Scholar Back to article
[30] WANG, J.: Quantum resistant random linear code based public key encryption scheme RLCE, Cryptology ePrint Archive, 298 (2015), 1–12.10.1109/ISIT.2016.7541753
Search in Google Scholar Back to article

A Cryptographic System Based on a New Class of Binary Error-Correcting Codes

Abstract

Paradigm

My account