In the last post, we have learned what an elliptic curve is, how it is used in cryptography and we saw an example of how Alice can encrypt her message to Bob using Bob’s public key and her own private key. We also saw how Bob is able to decrypt this message by multiplying Alice’s public key with his private key and subtracting the result from the encrypted message to get the clear text message.
An eavesdropper, by the name of Eve, has seen the exchanges between Alice and Bob and she wants to be able to decrypt the message of Alice. However, she only sees the public keys of Alice and Bob, the encrypted message, the elliptic curve equation used and the modulus. How can she decrypt the message?
Discrete Logarithm Problem
Eve knows both the public key of Alice and Bob. If she can somehow compute the private key, she will be able to decrypt the message. The public key of Alice is
Where is the private key of Alice and is the base point of the elliptic curve agreed before hand by Alice and Bob. Using a group theoretic notation, we can also write this as
where the group “multiplication” operation is defined at the addition of points defined in the last blog post, that is,
and , the identity element (point at infinity).
If , then
Solving for is called the discrete logarithm problem.
If Eve has access to a quantum computer, she can use Shor’s Algorithm to find the value of . The trick to using Shor’s algorithm is to create a periodic function such that the period of is . To do this, define
If and , notice that if . To see this,
Eve will prepare 2 input registers and prepare the quantum state to be a superposition of all values of the basis vectors
She will then apply an operator defined as
where is the periodic function defined as above.
A measurement of the output register system will then yield a specific value , which corresponds to values of and because of the periodic nature of the function:
To solve for , we apply the Quantum Fourier Transform as defined here:
The probability of getting a specify and is given by the square of the amplitudes:
If we let
we can write the quantity in underbrace as
which is maximum when is an integer, that is,
After a measurement of the input registers, we get a specific value of and . We can then compute the private key using:
where is the inverse of .
Suppose after we measure the input registers, we get the values x=51, y=44. We can compute for the private key as follows:
Decrypting the Message
Suppose we are given the following parameters: The elliptic curve equation is , the base point is , Alice’s public key is , Bob’s public key is and the encrypted message is .
Eve uses the Quantum Computer to compute Alice private key to get . She can then multiply Bob’s public key with Alice’s private key to get . Subtracting this from the encrypted text, we get , which is the decrypted message.