We present in this paper an algorithm for exchanging session keys, coupled with a hashing encryption module. We show schemes designed for their potential invulnerability to classical and quantum attacks. In turn, if the parameters included were appropriate, brute-force attacks exceed the (five) security levels used in the NIST competition of new post-quantum standards. The original idea consists of products of rectangular matrices in Zp as public values and whose factorization is proved to be an NP-complete problem. We present running times as a function of the explored parameters and their link with operational safety. To our knowledge there are no classical and quantum attacks of polynomial complexity available at hand, remaining only the systematic exploration of the private-key space.
We present in this paper an algorithm for exchanging session keys, coupled with a hashing encryption module. We show schemes designed for their potential invulnerability to classical and quantum attacks. In turn, if the parameters included were appropriate, brute-force attacks exceed the (five) security levels used in the NIST competition of new post-quantum standards. The original idea consists of products of rectangular matrices in Zp as public values and whose factorization is proved to be an NP-complete problem. We present running times as a function of the explored parameters and their link with operational safety. To our knowledge there are no classical and quantum attacks of polynomial complexity available at hand, remaining only the systematic exploration of the private-key space.
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.
We present an improved post-quantum version of Sakalauskas matrix power function key agreement protocol, using rectangular matrices instead of the original square ones. Sakalauskas matrix power function is an efficient and secure way to generate a shared secret key, and using rectangular matrices provides additional flexibility and security. This method reduces the computational complexity by allowing smaller random integer matrices while maintaining a high level of security. We dont rely on matrices with special formatting to achieve commutativity, instead, we use full random values on those structures, increasing their entropy. Another advantage of using rectangular matrices over key agreement protocols is that they offer better protection against various linearization attacks.
Nowadays, we are surrounded by devices collecting and transmitting private information. Currently, the two main mathematical problems that guarantee security on the Internet are the Integer Factorization Problem and the Discrete Logarithm Problem. However, Shor's quantum algorithm can easily solve both problems. Therefore, research into cryptographic algorithms that run in classical computers and are resistant to quantum computers is extremely necessary. This area is known as post-quantum cryptography and usually studies asymmetric cryptography. By means of asymptotic analysis, the purpose of this paper is to provide an evaluation of security and its performance for the types of cryptographic systems considered safe against quantum attacks in the second-round NIST Post-Quantum Standardization Process, namely isogeny cryptosystems based on supersingular elliptic curves, error correction code-based encryption system, and lattice-based ring learning with errors. We performed a security comparison of Key Agreements protocols based on these three post-quantum cryptographic primitives and compared them with Discrete Logarithm Problem and Integer Factorization Problem. The comparison of security and its performance is presented by security level, the former by complexity analyses to achieve theoretical minimum key sizes, and the latter by simulation to assess a practical performance comparison. In the complexity analysis, as we increase the security level and then the size of the cryptographic keys increases, techniques based on isogeny outperform all other post-quantum algorithms in relation to key sizes at practical security level. In the performance comparison, the results show that the code-based protocol presents the best results among the others.
Abstract Quantum computing poses fascinating challenges for current cryptography, threatening the security of many schemes and protocols widely used today. To adapt to this reality, the U.S. National Institute for Standards and Technology (NIST) is currently running a standardization process in search of post‐quantum (classical, yet resistant to quantum attacks ) cryptographic tools, focusing on signature schemes and key encapsulation mechanisms. Many of the competing proposals also include designs for two‐party key exchange, which can be combined in different ways to fit scenarios involving parties, that is, yielding group key exchange protocols. However, very few implementations of such group protocols are available to practitioners, which face a non‐trivial challenge when deciding how to implement a protocol for establishing secure group sessions in this new post‐quantum scenario. With this in mind, the authors report on the implementation of a secure post‐quantum group key exchange protocol in the so‐called Quantum Random Oracle Model . The protocol decided to implement is based on a KEM called Kyber , which is one of the finalists of the NIST competition. Not only this group construction is the only one available in the literature using a NIST finalist, but also, among all post‐quantum designs the authors are aware of, it uses this strongest security model (as, e.g. in other proposals, the adversarial interaction with the hash functions of the system is assumed to be exclusively classical). Furthermore, experimental evidence is provided supporting this choice in terms of performance, even if the number of involved entities is large (up to 2000). All data and code are publicly available.
Abstract This work introduces a new post-quantum key exchange protocol based on the computational hardness of the Nilpotent Commutator Inversion Problem (NCIP) in Heisenberg Lie algebras over GF(p), where p ≈ 2256. Compared to traditional methods based on integer factorization or discrete logarithms, our scheme relies on the non-linear algebraic properties of nilpotent matrices for quantum security. The protocol performs extremely well in sparse environments with 64-byte public keys requiring 0.024ms for 3 × 3 matrices and 128-bit post-quantum security. Through comprehensive comparison with NIST-standardized schemes (Kyber, SPHINCS+), we show superior performance in memory footprint (0.01KB) and computational overhead, particularly for IoT applications. Experimental evaluation confirms 95.1% success rates for 8 × 8 matrices (256-bit security) with sub-millisecond latency, while security analysis establishes resistance to both classical linear algebra attacks and quantum algorithms (Shor’s, Grover’s) through the NCIP hardness assumption. The work provides concrete parameter recommendations aligned with NIST security levels and demonstrates practical implementation in Python using optimized matrix operations over GF(pn). This Lie algebra-based approach offers a mathematically distinct alternative to existing post-quantum primitives, with particular advantages for scalable, lightweight deployments in edge computing and large-scale networks. Future work directions include hardware acceleration, formal security reductions, and integration with low-power network protocols.
Abstract It is viewed as revolutionary technology, offering incredible potential in terms of computing power within different scientific and industrial sectors. Quantum computers provide remarkable computing power; however, they also present significant security risks to existing public-key cryptography systems used to secure digital communication, online banking systems, government, medical applications, cloud computing systems, and IoT systems. Security of commonly used encryption schemes like RSA, DH, and ECC depends on mathematical problems that are impossible for classical computers to solve but can be easily resolved with the help of powerful enough quantum computers by using Shor’s algorithm. Furthermore, Grover’s algorithm makes exhaustive search attacks much faster, thus effectively lowering the security level of symmetric encryption schemes since it provides the speed-up for brute-force attacks. Post-Quantum Cryptography (PQC) turned out to be an effective and scalable method to protect digital data from attacks using quantum computing. In contrast to quantum cryptography, which requires a special quantum communication channel, PQC uses classical cryptographic algorithms that cannot be broken down by either classical or quantum computer due to certain mathematical problems. This research paper offers an extensive exploration of post-quantum cryptography through the analysis of the development of quantum computing, weaknesses of current cryptographic techniques, and mathematics behind quantum-resistant algorithms. Moreover, this paper explores the major classes of PQC techniques such as lattice-based, code-based, hash-based, multivariate, and isogeny-based cryptography and provides details about their security and application. Moreover, the report gives an overview of the NIST Post-Quantum Cryptography Standardization Project and analyzes recent standardizations of quantum-proof algorithms to be utilized in future digital infrastructures. Keywords: Post-Quantum Encryption, Quantum Security, Quantum-Proof Public-Key Cryptography, Lattice-Based Security Protocols, ML-KEM Key Encapsulation Mechanism, ML-DSA Digital Signature Algorithm, NIST Post-Quantum Cryptography, Contemporary Cybersecurity, Secure Communications, Cryptographic Algorithms.