How Elliptic Curve Cryptography (ECC) works and Quantum Attacks

Elliptic Curve Cryptography (ECC)

ECC is based on elliptic curves of the form \(y^2 = x^3 + ax + b\), \(a, b \in \mathbb{R}\).

First, we start off with a public generator point G (on the curve) and we make our own secret \(l\) with a random value that we choose to be 5. We can easily make a public key \(Y = lG = 5G\). However, it is challenging (e.g., Discrete Logarithm Problem) to find out the secret \(l = 5\) using public information \(Y, G, p\). Do take note that \(p\) is a prime number and it is used to calculate the public key.

Point addition (A + B and 2A = A + A)

We will explain how to add a point A to another point B (\(A + B = C\)) using the formulas below. 

\(A = (x_1, y_1)\)

\(B = (x_2, y_2)\)

\(A + B = C = (x_3, y_3)\)

\(\lambda = \frac{y_2 - y_1}{x_2-x_1} \mod p\)

\(x_3 = \lambda^2 - x_1 - x_2 \mod p\)

\(y_3 = \lambda(x_1 - x_3) - y_1 \mod p\)

To add a point A to itself, it is a similar process to point addition of 2 distinct points: the formulas are identical except for the calculation of \(\lambda\) 

\(2A = B = (x_3, y_3)\)

\(\lambda = \frac{3x_1^2 + a}{2y_1} \mod p\)

Scalar multiplication (A + ... + A = kA)

The most straightforward way is to apply the point addition formula \(k - 1\) times.

\(A + A = 2A\)

\(2A + A = 3A\)

...

\((k - 1)A + A = kA\) 

However, the most efficient way is to first break \(k\) into its binary components. For instance, \(k = 20 = 2^2 + 2^4 \Rightarrow kA = 20A = 2^2A + 2^4A\)

Repeated point doubling is performed to obtain the values required \(4A\) and \(16A\) and add them together to get the final point of the scalar multiplication.

\(2A = A + A\)

\(4A = 2A + 2A\)

\(8A = 4A + 4A\)

\(16A = 8A + 8A\)

\(\Rightarrow Y = 4A + 16A\)

As such, it only takes \(\log(k)\) steps to obtain the final point \(Y\).

Basics of quantum computing

Qubits are like bits in the sense that while bits are either in state 0 or state 1, a qubit can be in state 0, state 1, or both at the same time until it is measured, like Schrodinger's cat, which is dead or alive until the box is open.

For instance, one may define a qubit \(a\) and say that it is in state 1 and 0 and both states have equal probability of being measured, which is represented by the equation:

  \(|a\rangle = \frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle\)

The probability of measuring either state can be calculated by squaring the amplitudes of the state which will turn out to be 0.5 for both. Qubit \(a\) is also said to be in a superposition of 1 and 0.

Moving on, the bra-ket notation \(|\cdot\rangle\) is used to represent a register. A register is a set of any number of qubits that the writer defines.

For instance, \(|a\rangle\) doesn't mean anything until \(a\) is defined to be a register holding 6 qubits and that \(|a\rangle = |111111\rangle\) which means that the 6 qubits are all in a state of 1.

One more thing to note is that when representing any register with any state, the sum of the square of the amplitude of every state must add up to 1.

Example of invalid state:

\(|b\rangle = 0.5|0\rangle + 0.5|1\rangle\) since \(0.5^2 + 0.5^2 = 0.5 \neq 1\).

Example of valid state:

\(|a\rangle = \frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle\) since

\(\left(\frac{1}{\sqrt{2}}\right)^2 + \left(\frac{1}{\sqrt{2}}\right)^2 = 1\).

Quantum Fourier Transform (QFT)

QFT works as shown in the formula:

\(\text{QFT}|a\rangle = \frac{1}{\sqrt{q}} \sum_{c=0}^{q-1} e^{2\pi i a c / q} |c\rangle\)

An application is shown from Shor's algorithm: there are \(q\) states of \(|a\rangle|x^a \mod n\rangle\) and QFT is applied to register \(a\),

\(\frac{1}{\sqrt{q}} \sum_{a=0}^{q-1} |a\rangle|x^a \mod n\rangle\)

After QFT on the first register:

\(\frac{1}{q} \sum_{c=0}^{q-1} \sum_{a=0}^{q-1} e^{2\pi i a c / q} |c\rangle|x^a \mod n\rangle\)

Shor's algorithm for RSA

Given \(n = pq\), where \(p\) and \(q\) are prime numbers, how can \(n\) be factored into \(p\) and \(q\)? First, a coprime \(x\) of \(n\) where \(1 < x < n\) and \(\gcd(x, n) = 1\) is chosen. There is a function \(f(a)\) associated with these 2 numbers, \(x\) and \(n\). This function repeats every \(r\).

\(f(a) = x^a \mod n\)

\(f(a + r) = f(a)\)

It is through this value of \(r\) that \(n\) can be factored. The quantum algorithm prepares a superposition over \(a\), computes \(x^a \mod n\), applies QFT, and measures to obtain information about \(r\).

Theory of Shor's algorithm adapted for ECC

This section is based on “Revisiting Shor's quantum algorithm for computing general discrete logarithms [EKERA26]”.

First, 3 registers are prepared, each with \(n + 1\) qubits except the last one which has \(2n\) qubits where \(n\) is the number of bits required to represent the prime number \(p\). The first 2 registers hold the superposition of all values from 0 to \(2^{n+1} - 1\), while the last register is initialized to the 0 state.

\(|\psi_1\rangle = \frac{1}{q} \sum_{k,l=0}^{q-1} |k\rangle|l\rangle|0\rangle,\quad q = 2^{n+1}\)

Next, compute \([k]P - [l]Q\). \(P\) is the public point (generator) used to reach \(Q\) through the secret \(m \in [1, r]\) such that \(Q = [m]P\), where \(r\) is the order of the curve.

\(|\psi_2\rangle = \frac{1}{q} \sum_{k,l=0}^{q-1} |k\rangle|l\rangle|[k]P - [l]Q\rangle\)

QFT is applied separately to the first 2 registers:

\(|\psi_3\rangle = \frac{1}{q^2} \sum_{c_1,c_2=0}^{q-1} \sum_{k,l=0}^{q-1} e^{2\pi i (kc_1 + lc_2)/q} |c_1\rangle|c_2\rangle|[k - ml]P\rangle\)

Afterwards, measure \(c_1, c_2\) and feed the values to the classical [EKERA26] algorithm from the referenced paper to retrieve the secret.

Applying the theory to construct the circuit and break ECC 

The following work is carried out on QuICScript, pQCee's quantum simulator.

The goal is to reach the quantum state \(|\psi\rangle = \frac{1}{q} \sum_{k,l=0}^{q-1} |k\rangle|l\rangle|[k]P - [l]Q\rangle\) so that QFT can be applied and the classical algorithm can work on the outputs.

Example curve

In this example, the curve \(y^2 = x^3 + 2x + 1\) over the prime field \(p = 3\) and \(P = (0,1)\) is chosen. This means that \(n = 2\) as it takes exactly 2 bits to represent \(p = 3\). The secret is set to be \(m = 2\), so \(Q = 2P = (1,1)\). The curve's order is known beforehand: \(r = 7\).

Hadamard gates are applied on all qubits of the \(k\) and \(l\) registers, putting them into a superposition of all values from 0 to \(2^{3} - 1\).

The initial point of the point register is set to \((p,p)\), treated as the point at infinity.

Converting l to r - l

Point addition circuits are used, so to perform \(-l[Q]\), the circuit computes \((r - l)[Q]\) instead. A bitwise NOT and incrementor circuit convert \(l\) to \(-l\), then ancilla qubits are used to add \(r\) and obtain \(r - l\).

Finally, point addition circuits (+P, +2P, +4P, +Q, +2Q, +4Q) and QFT are appended.

The Azure’s Standard D8as v5 (8 vcpus, 32 GiB memory) platform is used to run QuICScript. After running the circuit, random values of \(c_1\) and \(c_2\) are measured and fed into the classical [EKERA26] algorithm. For most outcomes, the algorithm finds the secret \(m = 2\) with an average execution time of 34 seconds.

Resource estimates (Qubits, Circuit Depth, Gates)

The current circuit requires \(11n + 11 + \lfloor \log_2(n + 1) \rfloor\) qubits where \(n\) is the size of the private key in bits.

The circuit was generated and its depth and gate counts (X, Swap, Hadamard, QFT phase gates) were measured from \(n = 2\) to \(n = 20\). These values were used in cubic polynomial regression to estimate depth and gate counts for higher values of \(n = 256, 384, 521\).

Next steps: for n > 2

For \(n = 2\), the qubit count is 35. For \(n = 3\), there are 47 qubits, which cannot be fully simulated on modern classical computers due to memory limits. However, by tracking only the necessary registers (k, l, and the point register) and ignoring ancilla qubits, the number of states can be kept under \(2^{35}\) for \(n = 4\).

Simulations for prime numbers from \(n = 2\) to \(n = 4\) show that the lower bound probability of finding the secret per run is at 100%, using \(B_\eta = 100\), \(B_T = 100\), resulting in at most 10000 iterations.