Quantum Computing

Public-Key Cryptography in the Quantum Computing Era


Computer Science


Scientists have made some great breakthroughs in the field of Quantum Computing in recent times. Even though quantum computers aren't ready for commercial use as of now, scientists believe that they might be able to achieve the technology to make viable and affordable quantum computers for commercial use in the next 10-15 years. <a href="https://www.s-tronomic.in/post/88">In the last article</a>, I talked about public-key cryptography. Quantum computers can prove to be a real threat to public-key cryptography. Though there are some quantum-safe cryptographic algorithms as well. Today we will discuss quantum-safe cryptographic algorithms and try to understand how these algorithms are classified as Quantum-Safe. <b><h2><center>Quantum Computers and Public-Key Cryptography</b></h2></center> Before discussing quantum-safe algorithms, it is important to discuss why quantum computers can prove to be a threat to public-key cryptographic systems. <i>Quantum computers can create vast multidimensional spaces in which it can represent very large problems and solve them.</i> <img src="https://bl6pap004files.storage.live.com/y4mHX63jy7Ku1jqQAtPSQ_ePO7RWkThxt82oSF4oxOp1mfmmmSZULmR29Oi9kVhVOca-3e3VpQcYtCNAG9e6d7okKIBSk9ciYAOC1w6dak3yQZ_Pl6qzCkSEztHygfHmfJQgPeJ5UQPuvbWodvODopG6Hx_iXD6ssq05KYnEG7lLv9xyBUBfo4h51Z6JkshWCJr?width=256&height=170&cropmode=none" width="256" height="170" /> Public-key cryptography relies upon mathematical problems that are believed to be difficult to solve given the computational power available now and in the medium term. However, popular <b>cryptographic schemes based on these hard problems - including RSA and Elliptic Curve Cryptography - will be easily broken by a quantum computer</b>. Public-key cryptography is very important for banking systems, cryptocurrencies, and other blockchain-related technologies. <b><h2><center>Quantum-Safe Cryptography</b></h2></center> Using Shor's Algorithm, a 1024-qubit Quantum Algorithm can break the RSA algorithm in just a few days. <b>Shor's algorithm</b> solves the discrete logarithm problem and the integer factorization problem in polynomial time. Basically, it can factorize integers in polynomial time. Experts agree that within 7-10 years, a large-scale quantum computer may exist that can run Shor's algorithm and break current public-key cryptography. <b>Quantum-safe cryptography</b> refers to efforts to identify algorithms that are resistant to attacks by both classical and quantum computers, to keep information assets secure even after a large-scale quantum computer has been built. Hash-based algorithms like SHA-256, SHA-512 are considered quantum-safe. <img src="https://bl6pap004files.storage.live.com/y4mZ6b5gwGRJ5w0YNUWmWQZWcMIsl4ZIQ_X4lTEhRG-adY4Gxdo4br8qre9LpbgcgX1vkKMPcdxrvhX_iMh1B4nRvKhwXw_bl0t7Qr6AS_9rYzhKTQl2r-_vkJXYtb9ccjzfIF1Msas3cEMS9TbWcxvxXOltChmfcETG7RAu2EmLnfwDJIquj1nOA40hP2d6tY3?width=256&height=176&cropmode=none" width="256" height="176" /> While some of the public-key quantum-safe algorithms have been developed as well. They include lattice-based algorithms, multivariate cryptography, hash-based cryptography, etc. Different algorithms have different advantages. For example, it is generally thought that hash-based cryptography provides the most secure algorithms for digital signatures. On the other hand, lattice-based key exchanges are the fastest, while isogeny-based key exchanges have the shortest key sizes. Some of the lattice-based cryptographic algorithms are GLYPH, Bliss, etc. <b><h2><center>How Are Algorithms Classified As Quantum-Safe?</b></h2></center> Most of the public key cryptography that is used on the Internet today is based on algorithms that are vulnerable to quantum attacks. These include public key algorithms such as RSA, ECC, Diffie-Hellman, and DSA. All of these examples are easily broken by Shor's algorithms which can be implemented on a quantum computer. The reason Shor's algorithms break these public-key cryptosystems is that they are based on two specific computational problems - namely, <b>Integer factorization and discrete logarithm</b>. These problems are believed to be hard for a classical computer to solve but are known to be easily solved by a quantum computer. <img src="https://bl6pap004files.storage.live.com/y4mQ_UCqCQE5ZoadSQVLVBHV48UAOlAKaLWtoz9dmh2QDQtSIKZg7lF78X5KbXgyBryjskPoVGYNxEY8k--UstsyLMWlnOddztCdtwAtIFiOVR4lB83g8TG74-Qy_bEbMJUalggcs0y6LxmK1wEZk_K9mZG_QH3hQkA179GTw6vMg019_xxn_50OpJR7CCl4d6X?width=256&height=124&cropmode=none" width="256" height="124" /> Currently, it is believed that <i>lattice cryptography, coding theory, and multivariate cryptography are very hard to break using quantum computers</i> (at least through brute force) as they can sustain Shor's Algorithm. But we don't know if researchers and mathematicians develop a new algorithm to break these quantum-safe algorithms in the future. Mathematical keys can be cracked by developing some algorithms. But there exists a different method of public-key cryptography that is considered "unbreakable". This cryptographic system is based on quantum particles (like photons) for transferring keys between two parties. This is known as <b>Quantum Key Distribution</b> and deserves a separate blog of its own.

- Ojas Srivastava, 09:36 PM, 16 Oct, 2021