Description:
The best algorithms for factoring large integers have subexponential complexity (i.e., complexity that is greater that any polynomial complexity and smaller than the exponential complexity). This complexity is not good enough to factor numbers above 200 decimal digits, even assuming that all computers in the world were in use for hundreds of years. In 1994, Peter Shor from AT&T Bell Labs has discovered a factorization algorithm that runs in polynomial time, permitting in theory factoring numbers of almost arbitrary size. The algorithm can be implemented, however, only using a special type of a computing machine, referred as a quantum computer. As opposed to a classical computer, where logic states are represented using bits, that is as a binary "zero" or "one," in a quantum computer, logic states are represented using qubits, that is as a superposition of classical "zero" and classical "one". Every qubit may have infinitely many different values, and thus can carry much more information than a classical bit. A quantum computer is not a general purpose machine; it was shown to be able to solve very few problems, but among those almost all computationally intensive problems public key cryptography is based on. Therefore, if ever developed, quantum computation would mean the demise of RSA and other public key cryptosystems. So far, only simple quantum gates have been shown to work based on various physical principles, and there are plenty of problems to overcome before a quantum machine that can factor even a two digit number is built. It is unclear whether such a machine if ever developed can be scaled up to a computer consisting of billions of gates required to factor numbers of the size used in today's implementations of RSA. Shor's algorithm has two phases; first, based on quantum computing, second on classical computations. The classical phase involves efficient algorithms known from number theory such as continued fraction expansion and Euclid's algorithm. The entire algorithm is probabilistic, meaning that several repetitions of one or both phases, with different initial parameters may be necessary to factor a number. Your task is to analyze the algorithm, determine the expected number of repetitions necessary to complete factorization, and estimate the number of operations and quantum gates necessary to factor a number of a given size taking into account redundancy introduced by quantum error correction codes.
Literature:
Description:
Many public key cryptosystems (such as El-Gamal encryption scheme, Diffie-Hellman key exchange, Digital Signature Standard, etc.) are based on the difficulty of computing discrete logarithms in the group GF(p) of integers modulo large prime P. The best classical algorithms for computing discrete logarithms have the same complexity as the best factorization algorithms. This means that the size of P used in implementations of these cryptoalgorithms must be as large as the size of the modulus N in RSA (above 200 decimal digits). Peter Shor who discovered a polynomial algorithm for factorization of large integers using a quantum computer (see project PA-1), has shown that quantum computations can be used as well to compute discrete logarithms. The algorithm, in general case, is more sophisticated than the algorithm for factorization, but has the same polynomial complexity. Your task is to understand the algorithm and develop a graphical representation of particular phases of the algorithm (similar to the representation used for the factorization algorithm). Additionally, you are asked to determine the expected number of repetitions of the algorithm necessary to complete computations, and estimate the number of operations and quantum gates necessary to implement the algorithm for a given size of the modulus P taking into account redundancy introduced by quantum error correction codes. The other open problem is the applicability of the Shor's algorithm to breaking elliptic curve cryptosystems.
Literature:
Description:
Quantum cryptography permits exchange of a secret key between two people who never met before. Its security is considered as almost absolute, as it is based on fundamental laws of quantum physics (in particular on the Heisenberg uncertainty principle) as opposed to unproven mathematical assumptions, such as the difficulty of factoring large integers, public key cryptography relies on. On top of this, quantum cryptography permits communicating parties to discover any attempt of an adversary to passively eavesdrop the channel, the property considered as impossible to achieve by any classical means. The idea of quantum cryptography was first invented by Stephen Wiesner in the late 1960's, but his paper written at that time had been rejected by reviewers, and waited for publication more than ten years. Rediscovered at the beginning of 1980's, quantum cryptography was still considered as a science fiction, smart but unrealistic idea of a couple of crazy physicists. Surprisingly, the first apparatus implementing quantum cryptography was built as early as in 1989. Although the first version was still primitive, permitting only communication in the open air at the distance of about one foot; subsequent versions developed by various groups in U.S., Canada, and Europe allowed communication through a standard commercial optical cable for distances in excess of 20 km Currently, it seems that the main barriers to acceptance of quantum cryptography are: the cost of quantum communication equipment, and the limited distance between communicating parties. Security of the quantum key exchange in current implementations cannot be considered as absolute either because of the discrepancy between the theoretical model of a protocol and its actual implementation (e.g., the use of faint light pulses instead of single photons). Your task is to investigate different schemes for quantum key exchange, and assess their security against various eavesdropping strategies.
Literature: