Post-Quantum Key Agreement Protocols Based on Modified Matrix-Power Functions over Singular Random Integer Matrix Semirings

Abstract

Post-quantum cryptography is essential for securing digital communications against threats posed by quantum computers. Researchers have focused on developing algorithms that can withstand attacks from both classical and quantum computers, thereby ensuring the security of data transmissions over public networks. A critical component of this security is the key agreement protocol, which allows two parties to establish a shared secret key over an insecure channel. This paper introduces two novel post-quantum key agreement protocols that can be easily implemented on standard computers using rectangular or rank-deficient matrices, exploiting the generalizations of the matrix power function, which is a generator of NP-hard problems. We provide basic concepts and proofs, pseudocodes, and examples, along with a discussion of complexity.