Nathan: What is RSA, how does it work, what are its vulnerabilities?
So what exactly is RSA encryption? RSA, or Rivest-Shamir-Adleman, its creators, is "a public-key cryptosystem that allows us to encrypt messages between two communicating parties so that an eavesdropper who overhears the encrypted messages will not be able to decode them" (Cormen). A public-key cryptosystem also allows for a party to send a digital signature along with their message. This signature loses its validity if any bit of the message is changed which provides authentication of both the message and the sender. This makes RSA encryption the perfect tool for authenticating any electronic communications.
Each party in a public-key cryptosystem has both a public key and a secret key.
Keshav:
Victor:
- Introduction
// TODO
David:
The Quantum Threat to RSA Security: Shor's Factoring Algorithm
Peter Shor's discovery in 1994 of a quantum algorithm that finds the prime factors of an integer in an amount of time that only grows as a polynomial with the size of the integer opened up fundamentally new possibilities for cryptography. Most importantly, it showed it was possible to combine the parallelism inherent in quantum states with useful theorems from number theory to produce a serious threat to the security of systems based on RSA, since RSA assumes that factoring can never be carried out in polynomial time. All known classical factoring algorithms do not break this computational "speed limit," but Shor's algorithm shows that this security assumption is not valid in a world with large, error-correcting quantum computers.
To describe Shor's algorithm, first, we need to define what quantum states are mathematically, and second, we need to see how quantum states give probabilities for different outcomes via the Born rule. Fortunately, we can set aside questions about how to picture quantum states with our intuitions molded by the classical world, and instead give a definition in terms of vector spaces. A quantum state is a vector with complex number entries, and a quantum state space is a vector space spanned by linear combinations of specific vectors chosen to represent mutually exclusive outcomes of an experiment. These vectors are called basis states, since every other member of the larger quantum state space can be expressed as a linear combination of them using complex numbers. So, a quantum state Q can be expressed as Q = z1B1 + z2B2 + . . . + znBn, where {B1, . . . , Bn} is a basis for the state space and z1, . . . , zn are complex numbers. Many applications involve finite-dimensional quantum state spaces, and Shor's algorithm falls under this category since the quantum portion of it uses qubits. A qubit is the quantum analog of the classical bit formed by linear combinations of the basis states 0 and 1, so a qubit is a 2-dimensional state space. This already suggests that it might be worthwhile to look for ways to process information with a quantum rather than a classical computer since a bit only has 2 possible states, 0 or 1, whereas a qubit has as many possible states as there are complex numbers, so continuously many. These definitions can't be the whole story, since actually interacting with a qubit only ever produces a 0 or a 1 with some probability, never a "fuzzy" version of these possible values. We need the Born rule to bridge the gap between a quantum state and the chances of what actually occurs in the world. The Born rule states that the probability of seeing an outcome associated with a basis state is the product of the complex coefficient of that basis state with its complex conjugate. The complex conjugate of a complex number a + ib is a - ib. Geometrically, this corresponds to reflecting the first complex number over the real axis in the complex plane to reach the second. So, for a qubit QB = z1(0) + z2(1), where z1 = a + ib, the probability of seeing the outcome 1 is (a + ib)(a - ib). (Just as with classical bits, we don't need to end up with a number on a dial; all that's required is that the events named "0" and "1" be mutually exclusive, like a device being turned on or off.)
It might look as if the Born rule comes out of nowhere, but in the context of the vector definition of quantum states, it makes sense for finding probabilities, which can never be negative and have to sum to 1. For the first property, the Born rule makes sure that negative probabilities never arise because multiplying a complex number by its complex conjugate always gives a non-negative real number, which we can see by algebra:
(a + ib)(a - ib) = a2 - iab + iab - i2b2 = a2 - (-1)b2 = a2 + b2.
For the second property, since we're working with vector spaces, we can divide the entries of a basis state vector by the length of the vector to get a vector of length 1.
Here are APA citations for several possible sources. We don't need to use all of them but any of them could be useful, especially for comparing the quantum situation with classical and post-quantum. Manin & Zilber includes discussion of both quantum logic as a broader topic, and the character of Shor's quantum algorithm for prime factorization and how it fundamentally changed the security situation for public-key systems that rely on factoring being inefficient. Aaronson has a lot of interesting and more intuitive discussions about both theory and practical problems like quantum computers and the potential dangers they pose, and separating hype from what could feasibly happen. Garey & Johnson has a long list of NP-complete problems across different areas of math and computer science that could be interesting for comparison across topics. Cormen et al, could be a good reference for parts of the classical domain, especially RSA and related public-key systems.
Aaronson, S. (2013). Quantum computing since Democritus. Cambridge University Press.
Beltrametti, E. G. & Cassinelli, G. (1981). The logic of quantum mechanics (Peter A. Carruthers, Ed.). Addison-Wesley
Publishing Company.
Bengtsson, I. & Życzkowski, K. (2017). Geometry of quantum states: An introduction to quantum entanglement (2nd ed.).
Cambridge University Press.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd ed.). MIT Press.
Garey, R. G. & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman
and Company.
Hughes, R. I. G. (1989). The structure and interpretation of quantum mechanics. Harvard University Press.
Jordan, T. F. (1986). Quantum mechanics in simple matrix form. Dover Publications.
Kitaev, A. Y., Shen, A. H., & Vyalyi, M. N. (2002). Classical and quantum computation. American Mathematical Society.
Loepp, S. & Wootters, W. K. (2006). Protecting information: From classical error correction to quantum cryptography.
Cambridge University Press.
Manin, Y. I. & Zilber, B. (2010). A course in mathematical logic for mathematicians (2nd ed.). Springer.
Peres, A. (2002). Quantum theory: Concepts and methods. Kluwer Academic Publishers.
Pierce, J. R. (1980). An introduction to information theory: Symbols, signals and noise (2nd ed.). Dover
Publications.
Sipser, M. (2013). Introduction to the theory of computation (3rd ed.). Cengage Learning.
von Neumann, J. (1955). Mathematical foundations of quantum mechanics. (R. T. Beyer, Trans.). Princeton University Press.
- Victor: sources summary
ir.inflibnet.ac.in:8080/ir/bitstream/1944/212/3/03cali_43.pdf https://www.geeksforgeeks.org/classical-cryptography-and-quantum-cryptography/amp/ https://thetechbrook.com/quantum-ethics/ https://link.springer.com/content/pdf/10.1007/s10676-017-9439-z.pdf https://onlinelibrary.wiley.com/doi/epdf/10.1002/9781119795667.ch2 https://www.quantropi.com/differences-between-classical-quantum-post-quantum-cryptography/#:~:text=Classical%20cryptography%20uses%20difficult%20mathematical,and%20can%20withstand%20quantum%20attacks. https://medium.com/edge-elections/cryptography-conventional-quantum-post-quantum-9f7f4ec84732 https://link.springer.com/chapter/10.1007/978-3-540-88702-7_1 https://arxiv.org/pdf/1804.00200.pdf
