Post Quantum Digital Signature Based on the McEliece Cryptosystems with Dual Inverse Matrix

Haidary Makoui, Farshid; Gulliver, Thomas Aaron; Dakhilalian, Mohammad

doi:10.22042/isecure.2023.419559.1026

Post Quantum Digital Signature Based on the McEliece Cryptosystems with Dual Inverse Matrix

Document Type : Research Article

Authors

Farshid Haidary Makoui ¹

Thomas Aaron Gulliver ¹

Mohammad Dakhilalian ²

¹ Department of Electrical and Computer Engineering, University of Victoria, Victoria, B.C., Canada

² Department of Electrical and Computer Engineering, Isfahan University of Technology, Isfahan, Iran

https://doi.org/10.22042/isecure.2023.419559.1026

Abstract

Digital signatures are used to ensure legitimate access through identity authentication. They are also used in blockchains and to authenticate transactions. Code-based digital signatures are not widely used due to their complexity. This paper presents a new code-based signature algorithm with
lower complexity than existing methods and a high success rate. The key generation algorithm constructs three-tuple public keys using a dual inverse matrix. The proposed signing scheme is based on the McEliece cryptosystem. It includes an integrity check to mitigate forgery before verification.

Keywords

Cryptography

Code-Based Cryptosystem

Coding Theory

Digital Signature

Public Key Cryptography (PKC)

[1] Marco Baldi. Post-quantum cryptographic schemes based on codes. In 2017 International Conference on High Performance Computing & Simulation (HPCS), pages 908–910. IEEE, 2017.
[2] Kil-Hyun Nam. Private-key algebraic-coded cryptosystems. In Conference on the Theory and Application of Cryptographic Techniques, pages 35–48. Springer, 1986.
[3] Reza Hooshmand and Mohammad Reza Aref. Efficient secure channel coding scheme based on low-density lattice codes. IET Communications, 10(11):1365–1373, 2016.
[4] TRN Rao. Joint encryption and error correction schemes. ACM SIGARCH Computer Architecture News, 12(3):240–241, 1984.
[5] Robert J McEliece. A public-key cryptosystem based on algebraic. Coding Thv, 4244:114–116, 1978.
[6] Nicolas Sendrier. Code-based cryptography: State of the art and perspectives. IEEE Security & Privacy, 15(4):44–50, 2017.
[7] Pierre-Louis Cayrel and Mohammed Meziani. Post-quantum cryptography: Code-based signatures. In International Conference on Advanced Computer Science and Information Technology, pages 82–99. Springer, 2010.
[8] Wang Xinmei. Digital signature scheme based on error-correcting codes. Electronics Letters, 26(13):898–899, 1990.
[9] Nicolas T Courtois, Matthieu Finiasz, and Nicolas Sendrier. How to achieve a mceliece-based digital signature scheme. In Advances in Cryptology—ASIACRYPT 2001: 7th International Conference on the Theory and Application of Cryptology and Information Security Gold Coast, Australia, December 9–13, 2001 Proceedings 7, pages 157–174. Springer, 2001.
[10] Farshid Haidary Makoui, Thomas Aaron Gulliver, and Mohammad Dakhilalian. A new code-based digital signature based on the mceliece cryptosystem. IET Communications, pages 1199–1207, 2023.
[11] Mostafa Esmaeili. Application of linear block codes in cryptography. PhD thesis, 2019.
[12] Farshid Haidary Makoui, T Aaron Gulliver, and Mohammad Dakhilalian. Post quantum code-based cryptosystems with dual inverse matrix. In 2023 13th International Conference on Information Technology in Asia (CITA), pages 43–47. IEEE, 2023.
[13] Matthieu Finiasz. Parallel-cfs: Strengthening the cfs mceliece-based signature scheme. In Selected Areas in Cryptography: 17th International Workshop, SAC 2010, Waterloo, Ontario, Canada, August 12-13, 2010, Revised Selected Papers 17,
pages 159–170. Springer, 2011.
[14] Thomas P¨oppelmann, L´eo Ducas, and Tim G¨uneysu. Enhanced lattice-based signatures on reconfigurable hardware. In Cryptographic Hardware and Embedded Systems–CHES 2014: 16th International Workshop, Busan, South Korea,
September 23-26, 2014. Proceedings 16, pages 353–370. Springer, 2014.
[15] James Howe, Thomas P¨oppelmann, M´aire O’neill, Elizabeth O’sullivan, and Tim G¨uneysu. Practical lattice-based digital signature schemes. ACM Transactions on Embedded Computing Systems (TECS), 14(3):1–24, 2015.
[16] Dipayan Das, Jeffrey Hoffstein, Jill Pipher, William Whyte, and Zhenfei Zhang. Modular lattice signatures, revisited. Designs, Codes and Cryptography, 88:505–532, 2020.
[17] Thammavarapu RN Rao and Kil-Hyun Nam. Private-key algebraic-coded cryptosystems. In Conference on the Theory and Application of Cryptographic Techniques, pages 35–48. Springer, 1986.
[18] Shafi Goldwasser, Silvio Micali, and Ronald L Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal on computing, 17(2):281–308, 1988.
[19] Denis Diemert, Kai Gellert, Tibor Jager, and Lin Lyu. More efficient digital signatures with tight multi-user security. In IACR International Conference on Public-Key Cryptography, pages 1–31. Springer, 2021.
[20] Mihir Bellare, Chanathip Namprempre, and Gregory Neven. Security proofs for identity-based identification and signature schemes. Journal of Cryptology, 22(1):1–61, 2009.