An article on Post-Quantum Cryptography
While technological advancement has contributed significantly to the development and transformation of our lives, it also poses serious security challenges and increases potential threats.
Quantum computing is considered a technology that could pose a major challenge for the future.
Due to its powerful processing capabilities, hackers can use quantum computing to decrypt sensitive information, hack into bank accounts, transfer funds at will, and monitor corporate networks, actions that seriously affect trust in digital platforms.
Ensuring security is therefore crucial, and cryptography is a key tool for securing communications and data. Through the use of complex codes or algorithms, cryptography ensures that only those with the correct decryption key can access information, effectively blocking unauthorized access.
The strength of cryptography lies in its ability to ensure that the integrity of data has not been tampered with during transmission, which is essential for maintaining trust. It also develops mechanisms to prevent entities from denying the authenticity of their information or documents and provides secure channels of communication. Given the complexity and sophistication of quantum technologies, cryptography must also evolve to meet these challenges.
Post-quantum cryptography is an algorithm designed to defend against attacks based on quantum computers. Before exploring how post-quantum cryptography works and functions, we first need to understand the basics of how quantum computing works.
Quantum: the double-edged sword of innovation and risk
Quantum mechanics is considered the key theory that explains the behavior of all physical phenomena, and even the operation of computers is affected by this theory, even though these computers are not quantum computers.
Timeline from quantum mechanics to quantum computing
Quantum computers perform calculations using special transformations of internal states that take place under tightly controlled conditions according to the rules of quantum mechanics. In the physical system of a quantum computer, each logical bit must be precisely encoded to prevent any physical interaction from occurring without programmatic control.
Such interactions, even if seemingly unrelated to the classical system, could be catastrophic for a quantum computer.
This concept is based on Randall's insight that all information is ultimately physical - whether it is binary information in a classical computer or recorded in a physical system.
Quantum bits and their ability to be in a superposition are crucial, dramatically increasing the ability to handle specific tasks. In addition, quantum computing relies on the core principle of quantum entanglement, which allows quantum bits to interact with each other even if they are far apart, which is crucial for boosting computational efficiency and improving error correction mechanisms. This mechanism enhances the correct computational paths and eliminates the wrong ones, thus improving the overall efficiency of the system.
These quantum computers perform calculations by manipulating quantum bits, utilizing their unique properties to process information in a way that surpasses conventional computers. These systems require extremely low temperatures and isolation from all external environments to ensure that quantum states are maintained and decoherence is avoided - an extremely challenging task.
Solutions to these challenges will drive changes in quantum computing in areas such as cryptography, drug development and optimization challenges. For many years, research efforts have focused on finding solutions and have delved into the impact that quantum computing may have on cybersecurity, particularly in the field of cryptography.
New Challenges in Breaking Encryption, Accelerating Decoding
One of the most popular and widely used encryption algorithms is the RSA algorithm developed by Rivest, Shamir and Adleman. This algorithm is a core component of the security infrastructure provided by companies such as Nokia and Microsoft.
Another widely used encryption technique is the Advanced Encryption Standard (AES), which is primarily used for client-side and server-side data encryption, similar to encrypting network traffic. These algorithms are based on complex mathematical principles, and the longer the key length, the more difficult it is to crack, thus enhancing the security of the network.
The time required to crack these algorithms is extremely long, making them very secure with current technology. The most common is 256-bit encryption, which contains 256 binary bits. However, the ability of quantum technology to crack RSA encryption up to 2,048 bits long in as little as eight hours highlights the challenges facing quantum computing and its potential impact.
The acceleration of quantum computing lies in the property of quantum bits, which can exist in multiple states at the same time, a phenomenon also known as quantum parallelism, which significantly increases decryption speed.
In terms of digital infrastructure security, most systems currently use Secure Sockets Layer (SSL) and Transport Layer Security (TLS) protocols to ensure authentication, integrity and confidentiality of services. These protocols rely on complex symmetric encryption algorithms to encrypt data and generate Message Authentication Codes (MACs).
Quantum algorithms, such as Shore's algorithm, are able to efficiently handle large integers and break encryption, similar to the RSA algorithm (which is commonly used for key exchange).
According to research, advances in other quantum algorithms, such as the Grover algorithm, could halve the theoretical validity of keys, meaning that the security of a 256-bit key could be considered equivalent to that of a 128-bit key. These developments highlight the serious challenges facing the field and why research needs to be intensified to ensure better protections.
The “most famous” quantum algorithm poses security challenges
Peter Shor
Shor's algorithm, proposed by Peter Shor in 1994, is one of the most famous algorithms in the field of quantum computing.
The algorithm's popularity is due to its ability to perform factorization at an exponential rate, far faster than traditional algorithms, and for a wide variety of applications. Shore's algorithm is particularly well suited for factorizing randomly chosen integers, as long as these integers are smaller than the number to be factored.
In the core phase of the algorithm, we set a to be a number and N to be a mutually prime number. The next key step is to find the quantum period by quantum Fourier transform, where the period r is the smallest positive integer that satisfies a^r = 1 mod N. The next key step is to find the quantum period by quantum Fourier transform. The resulting period or number is used to calculate the factor of the target number, a process that reveals the unique properties of the number being processed.
In short, instead of using a single key to unlock the door, Shore's algorithm quickly narrows down the range of potentially valid keys and avoids trying them one by one.
Shore's algorithm contains three main components: classical, quantum, and anticlassical computations. In addition, the algorithm includes at least four key subcomponents, one of which is phase estimation, which determines the period of the factorization through modular arithmetic. Another important subcomponent is the inverse quantum Fourier transform (inverse QFT), which converts quantum results into classical information and extracts them from quantum circuits for measurement.
Flow of the Shor Algorithm
The use of the Shore algorithm poses a threat to existing RSA and other cryptosystems because it significantly reduces decryption time and performs decryption at an exponential rate, thus contributing to the shift in security towards quantum-resistant algorithms.
Three technical routes to post-quantum encryption
Over the years, the field of Post-Quantum Cryptography (PQC) and Quantum Cryptography has developed a wide range of cryptographic techniques and algorithms that significantly improve the ability to combat quantum threats.
Unlike quantum cryptography, post-quantum cryptography does not rely on any mathematical problems based on quantum properties. Its focus is on avoiding the use of integer factorization and discrete logarithm problems to encrypt data. One approach to post-quantum cryptography is to develop new algorithms that utilize different methods.
For example, code-based cryptography utilizes the theory of error-correcting codes and relies on the difficulty of decoding randomly generated linear codes.The McEliece cryptosystem, developed in 1978, was one of the early systems capable of resisting cryptanalytic attacks, including quantum attacks. However, its main problem was the large key size, which caused difficulties in practical applications in conventional computing.
Homology-based cryptography involves a non-constant mapping between elliptic curves, which can be expressed in polynomial form, and this mapping is compatible with the addition operation of two curves. Its key size is relatively small, and variants of it, such as SIIDH, are key exchange algorithms that improve quantum resistance. The method is based on the fact that each party has a private key and a public key, which is calculated based on the homology of the elliptic curve. The parties exchange public keys and then each computes the homology of a new curve using the other party's public key and its own private key.
Homology between elliptic curves. As shown in the figure, if we have two elliptic curves (E1 and E2), we can create a function that maps a point (P) on E1 to a point Q on E2. this function is called homology. If we can map this function, every point on E1 can be mapped to E2. secret keys are homologous and public keys are elliptic curves. For key exchange, Alice and Bob mix their homology curves with each other to generate a secret curve
Another method is hash-based cryptography, which converts the input data into a fixed-size string of bytes by means of a mathematical function, and is often used to create digital signatures. Its security relies heavily on the collision resistance of the hash function, a property that is said to remain strong even in a quantum computing environment. However, the signature size of these keys is usually larger than that of conventional keys.
Among all these techniques, lattice-based cryptography is the most prominent and reliable. It is based on a high-dimensional mathematical structure consisting of infinitely extended points. In this structure, the points are formed by linear combinations of integer coefficients, and there are n linearly independent vectors that serve as the base points of the lattice. The problem is to find points with specific properties, such as the short vector problem or the nearest vector problem. While quantum computers can handle a wide range of possibilities in high-dimensional spaces, the complexity of the lattice problem makes it difficult to solve it simply in a parallel fashion, and there are no algorithms that effectively reduce the complexity of this approach.
Lattice cryptosystems are constructed using a geometric structure called a “lattice” and are represented using a mathematical array called a matrix.
NIST's PQC process
The National Institute of Standards and Technology (NIST) plays a critical role in developing and standardizing quantum-resistant cryptography, with the goal of protecting digital infrastructure from the complexities and challenges posed by quantum technologies.
As the authority responsible for managing and directing cybersecurity, NIST is committed to identifying future risks that may threaten individuals or businesses and taking appropriate measures to address or mitigate those risks. In light of the advances in quantum technology, NIST has initiated a dedicated project aimed at developing Post-Quantum Cryptography (PQC) algorithms that can withstand quantum computing attacks. The goal of the project is to develop a variety of techniques and methods to enhance and maintain the security and integrity of digital infrastructure and to ensure that communication proceeds smoothly, uninterrupted by advances in quantum technology.
As reported in 2023, four algorithms were selected for standardization from a large pool of candidate algorithms.
Each of these algorithms has its own distinctive features, including an algorithm based on public key encapsulation techniques and three digital signature schemes, and are seen as an important step in protecting security from quantum threats.
1) CRYSTAL-Kyber.
The Key Encapsulation Mechanism (KEM) is a mechanism that encompasses three algorithms, including an algorithm for generating key pairs, an encapsulation algorithm that computes the session key and ciphertext using the public key, and a decapsulation algorithm that generates the session key using the ciphertext and the private key. Cryptographic Suite for Algebraic Lattices (CRYSTAL) Kyber works on the lattice principle and utilizes the learning with errors (LWE) problem to enhance the computational difficulty of key exchange.
computational difficulty to enhance the security of key exchange.
The process starts with the generation of a pair of keys, where the private key is kept secret and the public key is shared publicly. The key generation process involves the manipulation of the lattice, which is closely related to the LWE problem.
When a sender needs to establish a secure connection, they will create or encapsulate a key using the public key and subsequently decapsulate it using the private key to recover the session key, ensuring that both parties can securely encrypt and decrypt messages.
Kyber is recognized for its efficiency, which not only minimizes resource and bandwidth usage, but also makes it more suitable for a wide range of applications through performance-optimized key sizes.
2) CRYSTALS-Dilithium
CRYSTALS-Dilithium is a lattice-based digital signature method that focuses on ensuring authenticity, integrity verification and non-repudiation of digital communications. This approach utilizes LWE and its variants and involves the development of a key pair: a private key for signing documents and a public key for verifying signatures.
Due to the inherent complexity and untraceability of the lattice problem, this increases the security of the signing process and improves the flexibility of signature verification. In addition, Dilithium implementations typically use uniformly distributed samples, avoiding complex and inefficient sampling from Gaussian distributions. Its modular structure also facilitates the use of polynomial multiplication, which can be performed in a consistent manner regardless of the security level, thus ensuring seamless switching between different security levels.
3) FALCON
FALCON is a signature scheme based on the Gentry-Peikert-Vaikuntanathan (GPV) blueprint that combines lattice-based signature techniques with trapdoor functions. For example, by assuming that the Short Integer Solution (SIS) problem in the lattice is intractable, an efficient Gaussian sampler can be used to construct the NTRU lattice, thus creating a secure system.
At the heart of the development of FALCON lies the utilization of efficient Fourier transform techniques for all computations. This algorithm is known for its compactness and efficiency. The ring structure used, as well as the error distribution, optimizes the computational process and effectively mitigates the effects of Gaussian error distortion, thus improving performance. However, one of its drawbacks is the high complexity of the overall structure and implementation details involved, which may add to the difficulty of understanding and implementation.
4) SPHINCS+
SPHINCS+ is the only hash-based encryption algorithm selected that combines technological innovations with other cryptographic techniques that improve security and efficiency. The algorithm generates a pair of keys where the private key is used as a random seed to derive the other components of the signature scheme through a secure hash function, ensuring reverse engineering is difficult.
When signing a message, the private key is used to generate a unique signature for the message, including the creation of a one-time signature, which is then linked back to the public key through a multilayered tree structure and an intermediate key, indicating that the signer owns the key while protecting the privacy of the key. To verify the signature, the recipient uses the public key to confirm that the message was signed by the corresponding private key. A major drawback of this approach is the large signature size and high computational overhead,
which is a common feature of hash-based approaches.
The four selected algorithms highlight NIST's efforts to advance the field of post-quantum cryptography (PQC), aiming to move away from traditional algorithms and toward systems that can resist quantum computing. To ensure security and technological advancement, NIST is continuing to emphasize and develop additional measures and technological innovations that enhance the efficacy and simplify the implementation complexity of these four solutions.
Emerging Crypto Tackles Quantum Challenges
The focus on quantum computing has also driven fundamental changes in the field of digital security as the complexity and challenges of quantum computing have grown.
Quantum computing brings complexity to existing encryption methods, prompting us to explore new encryption techniques. Post-Quantum Cryptography (PQC) is just one of the many emerging techniques. Quantum-based methods such as quantum key distribution (QKD) are seen as cutting-edge technologies to improve system resilience. QKD based on quantum mechanics can provide a level of security that is theoretically independent of computing power and technological advances, including the development of quantum computing. Its core principles, such as superposition, entanglement and no-cloning theorems, pave the way for the development of new security protocols such as BB84 and E91. Despite the limitations imposed by photon loss, this technology has been more widely used in government communications and banking transactions.
Despite the rapid progress in research, the development of quantum-secure encryption techniques that can withstand the computational power of quantum computers is receiving increasing attention. These techniques aim to ensure that data is protected through the use of mathematical puzzles that are difficult even for quantum computers to solve.
Developments in quantum computing are not limited to software or algorithms, but also include hardware-based solutions such as quantum random number generators to increase the unpredictability of the system. These devices utilize fundamental uncertainty quantum events that ensure unpredictability and generate random numbers through systematic superposition measurements, entanglement, and photon arrival times.
These new technologies face multiple challenges, including integration difficulties with existing infrastructure, lack of standardization, and design issues for algorithm deployment. Often, there is a trade-off between performance and security that needs to be carefully considered. New technologies must ensure their effectiveness and security against quantum attacks while minimizing negative impacts that may affect system performance.
New procedures must also ensure that communications are secure and fair even when there is a high level of distrust between participants. With advances in technology, digital signatures can now be exchanged in a way that maintains their temporary nature until important details of the transaction are disclosed, further demonstrating the technology's capabilities and fair intentions.
In conclusion, quantum-secure encryption is an approach to the challenges of quantum computing that demonstrates the future direction of digital security.
Promoting digital communications, data storage and online transactions
Post-Quantum Cryptography (PQC) has made significant progress in protecting digital communications, data storage and online transactions from potential quantum attacks. By abandoning traditional strategies and mathematical methods and adopting more sophisticated mathematical models, PQC strengthens digital security and ensures that encrypted information remains confidential and tamper-proof.
Although quantum technology is still in the developmental stage, developing techniques that can counter the power of quantum computing has become particularly important given its potential attack applications. The U.S. National Institute of Standards and Technology (NIST) has played a leading role in this shift, developing key communications technologies that can withstand eavesdropping and interception. This is especially critical in the areas of diplomacy, corporate communications and the military, where sensitive information must remain absolutely secure.
PQC-based digital signature technology ensures the verifiability, tamper-proofness and authenticity of documents, greatly enhancing the security of online transactions in the financial sector. The rollout of this technology can even be extended to the voting process. As this field continues to progress, we can foresee the emergence of many more applications and features that will help to meet the challenges posed by future environments, whether traditional or quantum computing.
IBM has been a leader in the field of quantum computing for many years and has played a critical role in advancing quantum computing technology and Post-Quantum Cryptography (PQC).IBM's influence is not limited to theoretical research, but extends to the development of practical tools and platforms to support advances in PQC.
IBM is responsible for the development of a number of important algorithms, including CRYSTALS-Kyber, one of the candidates in the NIST Post-Quantum Cryptography Algorithm Selection Event. Virtually all four shortlisted PQC algorithms had direct involvement or significant contributions from IBM researchers.IBM is fully aware of the threats that quantum computing can pose and has remained at the forefront of global cryptographic standardization efforts, working with industry leaders to advance the development of standards.
Another notable contribution is the Qiskit SDK, an IBM-developed open source platform designed to facilitate the development, research and implementation of quantum algorithms. The tool includes a suite of basic building blocks and additional features, such as simulation applications, which allow researchers to use a variety of tests to develop algorithms that comply with the new standard. In the field of post-quantum encryption, the SDK helps to simulate quantum attacks on cryptographic protocols, which is essential for testing the resilience of algorithms and exploring the integration of different approaches.
Google has been working on quantum computing for many years, developing and investing in related technologies, including partnerships with universities and businesses to advance quantum computing technology.
The company has also played a key role in exploring the Schorr's Factorization of Large Numbers algorithm, an algorithm that effectively reveals vulnerabilities in existing encryption methods.
An important tool introduced by Google is an open source library called Cirq, which enables researchers and developers to design, simulate and run quantum circuits on simulators and quantum computers.Cirq is designed to enable users to take full advantage of quantum processors by providing the necessary tools to easily design and simulate quantum algorithms, and to test their resilience to quantum attacks in a real-world environment to ensure that the algorithms are used in applications of effectiveness and utility. Researchers have already developed and tested new algorithms using Cirq and Qiskit, and these tests are compliant with Post-Quantum Cryptography (PQC) requirements, highlighting the importance of these two tools.
Another tool is TensorFlow Quantum, which was developed in collaboration with TensorFlow to bridge the gap between machine learning and quantum computing. The tool provides a powerful resource for researchers to build, train and simulate quantum machine learning models and test the potential of these models in different applications.TensorFlow Quantum is crucial for working with quantum data as it helps to demonstrate the usefulness of machine learning models in various scenarios and further develops new algorithms in PQC environments to ensure higher security and protection.
Since its inception, Microsoft has been a pioneer in the field of data security with its operating systems and cloud services, and the company has also played a key role in advancing the development of Post-Quantum Cryptography (PQC) by utilizing advanced technologies. Microsoft's focus on ensuring that existing protocols can adapt to the changing needs of the environment and work together efficiently has led to the development of tools such as the PQC VPN. PQC VPN is said to be an improvement on traditional VPN technology that encrypts and secures network data transmission, and has become one of the key tools for achieving quantum security.
Microsoft is also adapting the Transport Layer Security (TLS) protocol to meet the requirements of PQC with the support of the OpenSSL development platform for smoother integration of the algorithm into existing infrastructure. In addition, Microsoft has developed Post-Quantum SSH, a “secure shell” network protocol for securely operating network services in insecure networks. The development of PQC-based SSH involves integrating algorithms into the protocol to enhance its ability to combat cyber threats.
Often, the integration of PQC with Quantum Key Distribution (QKD) works to ensure the best of both worlds. An example of this is the quantum-secure IPsec VPN developed by Juniper Networks, which uses both PQC, which provides algorithms to resist computational attacks and safeguard data integrity and security, and QKD, which provides a secure method of key exchange capable of detecting any potential interception attempts using the principles of quantum mechanics.
The main reason that QKD and PQC can work together is that QKD does not require the high processing power found in quantum computing, but does employ the principles of quantum mechanics.The security of QKD is based on the fundamental principles of quantum physics, which are crucial security against computational attacks. However, implementation of such a system would require appropriate modifications to existing fiber optic communication endpoints.
Enhancing Data Security Globally
Most technology leaders recognize that Post-Quantum Cryptography (PQC) is critical to meeting the challenges posed by quantum computing. The emergence of quantum computing could trigger major disruptions similar to the Y2K incident. The implementation of PQC is extremely important to ensure the security of data until quantum computing matures, which has the potential to break current encryption techniques.
Increased concerns about security have also prompted countries to invest more. For example, some countries and regions are focusing on enhancing data protection measures. This has led to significant investments in the area of PQC and the development of new protocols and algorithms utilizing PQC concepts.
In addition, interest and investment is growing around the world, including in the Middle East.KAUST and Zapata Computing are leading software companies that offer NISQ-based quantum applications and are collaborating on how quantum computing can simulate and optimize the design process for automotive aerodynamics. It is claimed that this will help save design time, optimize design results, and expand the scope of quantum computing applications. Further, it has been observed that Saudi Aramco's Wa'ed Ventures has invested about $100 million in quantum computer startup PASQAL. These investments show the growing interest in the field and will accelerate the development of the technology.
The emergence and continued advancement of quantum computing is seen as a key driver in accelerating the development and deployment of PQCs. As investment and research in this area continues to increase, there is an urgent need to develop more quantum resilient systems to ensure that the technology does not cause disruption or severe damage. Current algorithms and encryption techniques are largely based on mathematical problems that quantum computers are claimed to be able to easily crack, reducing their effectiveness. This has prompted the National Institute of Standards and Technology (NIST) to spearhead the development of a new PQC algorithm that reconsiders security and encryption and focuses on solving complex mathematical problems that are difficult for quantum computers to exploit.
The new lattice-based algorithm not only improves security, but also facilitates the development of new applications. In summary, while PQC will help mitigate the threats posed by quantum computing, the disruption caused by this change could be quite significant.
