Abstract
With the emergence of technological revolution to host services over Internet, secure communication over World Wide Web becomes critical. Cryptographic protocols are being in practice to secure the data transmission over network. Researchers use complex mathematical problem, number theory, prime numbers etc. to develop such cryptographic protocols. RSA and Diffie Hellman public key crypto systems have proven to be secure due to the difficulty of factoring the product of two large primes or computing discrete logarithms respectively. With the advent of quantum computers a new paradigm shift on public key cryptography may be on horizon. Since superposition of the qubits and entanglement behavior exhibited by quantum computers could hold the potential to render most modern encryption useless. The aim of this chapter is to analyze the implications of quantum computing power on current public key cryptosystems and to show how these cryptosystems can be restructured to sustain in the new computing paradigm.
TopIntroduction
Today is an era where a smart phone provides anytime anywhere services and stores personal data, including photos, messages, mails and documents. Instead of files and folders people use icloud, Microsoft one drive, Google cloud as backups. From small start-ups to Microsoft, Google, IBM, AT&T, Amazon store their data in data-centres and cloud. With the emergence of technological revolution to host services over internet, it has resulted in exponential growth of data stored in data-centres and cloud. Storing data in data-centres and cloud entails securing data from thieves, who secede valuable or sensitive data from storage centers and eavesdroppers, who listen or capture data on the communication channel while it travels from provider to user over World Wide Web. Hence secure communication of this data becomes critical.
Cryptography is the collection of techniques to communicate data only to its intended user in presence of third parties. These techniques suggest that before the data enters the communication channel, hide the data using encryption techniques and then on reaching its destination unhide the data using decryption techniques. Hence cryptographic protocols are being in practice to secure the data transmission over network.
Traditionally cryptographic protocols involve use of a secret key, which is agreed upon by the sender and the receiver over a secure channel, to encrypt and decrypt this data. Ramification of this protocol is key distribution problem. To eliminate the use of a single key Diffie and Hellman devised a solution based on the concept given by Merkle(Merkle,1978). Merkle suggestion was to communicate the message over insecure channel by creating a puzzle and encrypting some information in the puzzle such that it requires exponentially more efforts from eavesdropper to solve the puzzle than the receiver.
Since the advent of quantum computing paradigm in 1980’s, Richard Feynman and David Duetsch envisioned the massive computing power of quantum systems. Quantum computation provides parallelism because of phenomenal characteristics of quantum physics like superposition and entanglement to perform operations on data. Shor(1994) proposed a quantum algorithm that has severe implication on current classical algorithms for public key cryptography. The traditional cryptosystems are challenged to sustain and provide adequate security. So there is need to replace the existing cryptosystem with new protocols, resistant against the attacks due to quantum computing power. The only solution with us is to either switch to quantum cryptography algorithms or to reformulate the classical cryptosystem resistant to quantum paradigm.
Key Terms in this Chapter
Abelian Group: An Abelian group is a group for which the elements commute (i.e., AB = BA for all elements A and B ). Abelian groups therefore correspond to groups with symmetric multiplication tables.
Asymmetric cryptography: Use two different but related keys for encryption and decryption.
Fast Fourier Transform: The fast Fourier transform (FFT), proposed by Cooley and Tukey (1965) AU73: The in-text citation "Cooley and Tukey (1965)" is not in the reference list. Please correct the citation, add the reference to the list, or delete the citation. , is a discrete Fourier transform algorithm which reduces the number of computations needed for N points from 2 N 2 to .
Hidden Subgroup Problem: Let G be a group and H ? G one of its subgroup. Let S be any set and f: G ? S a function that distinguishes cosets of H i.e. ? g1, g2 ? G, f (g1) = f (g2) ? g1H = g2H. The hidden subgroup problem (HSP) is to determine the subgroup H using calls to f.
Quantum Mechanics: The mechanics which governs atomic phenomenon.
Heisenberg Uncertainty Principle: Determining the position of a particle in a small region of space makes the momentum of the particle uncertain; and conversely, that measuring the momentum of a particle makes the position uncertain.
Non Abelian Group: A non-Abelian group, also sometimes known as a noncommutative group, is a group some of whose elements do not commute. The simplest non-Abelian group is the dihedral group D3, which is of group order six.
Symmetric cryptography: Also known as secret key encryption, only one key called secret key is used for both encryption and decryption.