9 minute read

quantum-bomb

A small and cute quantum bomb.

Introduction

In this article, we’ll implement Shor’s algorithm to solve the Elliptic Curve Discrete Logarithm Problem (ECDLP) using Qiskit. We can call it the “Quantum Bomb” for its potential to break cryptographic systems.

However, note that neither current quantum hardware nor classical simulators are capable of running this algorithm to break real-world cryptographic systems like the Elliptic Curve Digital Signature Algorithm (ECDSA) used in Bitcoin or Ethereum. This implementation is purely an educational exercise to understand the algorithm’s inner workings and how to translate it into a quantum program using a minimal example.

Reminder: Shor’s Algorithm

In a previous article, we explored Shor’s algorithm, a quantum algorithm that efficiently solves problems like integer factorization and discrete logarithms in polynomial time. You can revisit that article here.

As its core, Shor’s algorithm is a period-finding algorithm. The key challenge lies in encoding the function whose period needs to be determined into a quantum circuit. For ECDLP, this involves transforming elliptic curve scalar multiplication into a form that can be executed on quantum registers.

Shor’s Algorithm for ECDLP

In the case of ECDLP, the function we are looking to encode is the following:

\[f(a, b) = aP + bQ.\]

Here, $P$ is a fixed point on the elliptic curve, and $Q$ is the public key point. The periods $r_a$ and $r_b$ of this function reveal the scalar $k$ such that $Q = kP$:

\[\begin{aligned} & aP + bQ = (a + r_a)P + (b + r_b)Q \\ \implies & r_a P + r_b Q = 0 \\ \implies & Q = -r_a r_b^{-1} P \quad \therefore k = -r_a r_b^{-1}. \end{aligned}\]

Implementing this function as a quantum circuit requires modular arithmetic for operations like point addition and scalar multiplication on elliptic curves. These modular operations—addition, multiplication, and inversion—pose implementation challenges.

We will use a custom Qiskit library that implements these arithmetic operations in a quantum circuit, using methods as described in the paper by Roetteler, Naehrig, Svore, and Lauter. If you are interested in the details, you can read the paper here.

Implementation

In this section, we will walk through the step-by-step implementation of Shor’s algorithm for solving ECDLP using Qiskit. You’ll have a working quantum circuit to simulate the algorithm and find the private key in our toy elliptic curve example. All the code is available and executable in this Google Colab Notebook.

0. Installing Required Python Packages

pip install https://p51lee.github.io/assets/python/wheel/qiskit_ecdlp-0.1-py3-none-any.whl
pip install qiskit-aer-gpu

The notebook starts by installing the required Python packages. The first package is my custom build of Qiskit ECDLP library (developed by Lukas), which implements elliptic curve arithmetic as quantum circuits. The second package qiskit-aer-gpu enhances simulation speed with GPU support.

1. Defining Elliptic Curve Parameters

import math

# Define the elliptic curve parameters
EC_MODULUS = 5  # Prime modulus of the field
EC_A = 3        # Coefficient A in the elliptic curve equation
EC_B = 2        # Coefficient B in the elliptic curve equation
EC_ORDER = 5    # Order of the elliptic curve group
NUM_BITS = math.ceil(math.log2(EC_MODULUS))  # Number of bits needed for the modulus

# Base point (P) and private key
point_p = (2, 1)  # Generator point on the curve
private_key = 3   # Private key (for demonstration)

The elliptic curve parameters define a toy example of an elliptic curve over a finite field. Here, we use:

  • $y^2 = x^3 + 3x + 2 \mod 5$ as a curve with a small prime modulus $p = 5$.
  • Base point $P = (2, 1)$: a generator point on the curve.
  • Private key $k = 3$: the scalar to generate the public key $Q = kP$.

In real-world scenarios, elliptic curves have much larger parameters to ensure cryptographic security. Here, we keep the parameters small for simplicity and computational feasibility.

2. Generating the Public Key

def classical_point_self_addition(point):
    pass # code omitted here for brevity

def classical_point_addition(point1, point2):
    pass # code omitted here for brevity

def classical_point_doubling(point, multiplier):
    res = None, None  # Point at Infinity
    acc = point

    while multiplier > 0:
        bit = multiplier & 1
        if bit == 1:
            res = classical_point_addition(res, acc)
        acc = classical_point_self_addition(acc)
        multiplier >>= 1
    return res

point_q = classical_point_doubling(point_p, private_key)
print(f"Base Point (P): {point_p}")
print(f"Public Key (Q = {private_key}P): {point_q}")

Base Point (P): (2, 1)
Public Key (Q = 3P): (1, 1)

We define the functions for elliptic curve arithmetic operations in classical computing. These functions are used to generate the public key $Q$ from the base point $P$ and the private key, say, $k$. The public key is calculated as the result of scalar multiplication of the private key and base point: $Q = kP$.

Note that we are using classical arithmetic operations here. In the quantum implementation, these operations will be replaced by quantum circuits.

3. Initializing the Quantum Circuit

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister

# Define the quantum and classical registers
qreg_x = QuantumRegister(1, "x")
qreg_psi = QuantumRegister(2 * NUM_BITS, "\\psi")
qreg_ancilla = QuantumRegister(2 * NUM_BITS + 2 + 2, "anc")
creg_qft = ClassicalRegister(2 * NUM_BITS + 2, "cl_qft")

# Initialize the circuit
circuit = QuantumCircuit(qreg_x, qreg_psi, qreg_ancilla, creg_qft)

This code snippet initializes the quantum circuit with the required quantum and classical registers. The quantum registers include:

  • qreg_x: A register for controlling the point addition operation. Same role to the first register in the QPE algorithm.
  • qreg_psi: A register for storing the quantum state $\ket{\psi}$ of the elliptic curve points. Same role to the second register in the QPE algorithm.
  • qreg_ancilla: An ancilla register (helper register) for intermediate computations: arithmetic operations like modular addition, modular multiplication, and modular inversion need additional qubits to store intermediate results.
  • creg_qft: A classical register for storing the measurement outcomes of the quantum Fourier transform (QFT) operation, which we will use in post-processing.

If you’ve read the Shor’s algorithm article before, you’ll have a feel for what each register means.

4. Building the Quantum Circuit

points = []
for i in range(0, NUM_BITS + 1):
    points.append(classical_point_doubling(point_p, 2**i))

for j in range(0, NUM_BITS + 1):
    points.append(classical_point_doubling(point_q, 2**j))

Remember that the QPE algorithm requires the operations $U^{2^0},U^{2^1},\ldots,U^{2^{n-1}}$ to be applied to the quantum state $\ket{\psi}$, where $U$ is the unitary operator representing the function $f(a, b) = aP + bQ$. In this case, we are applying the addition of the points $P, 2P, 4P, \ldots, 2^n P$ and $Q, 2Q, 4Q, \ldots, 2^n Q$ to the quantum state $\ket{\psi}$.

for k in range(0, 2 * NUM_BITS + 2):
    circuit.h(qreg_x[0])
    point_addition_circuit = (
        CircuitChooser()
        .choose_component(
            "QCECPointAdderIP",
            (NUM_BITS, points[k], EC_MODULUS, 1, True),
            dirty_available=0,
            clean_available=len(qreg_ancilla),
        )
        .get_circuit()
    )
    circuit.append(point_addition_circuit, [qreg_x[0]] + list(qreg_psi) + list(qreg_ancilla))

    apply_semiclassical_qft_phase_component(
        circuit, [qreg_x[0]], creg_qft, 2 * NUM_BITS + 2, k
    )
    circuit.h(qreg_x[0])
    circuit.measure(qreg_x[0], creg_qft[k])

This code block builds the quantum circuit for the Shor’s algorithm. It applies the point addition operation with points $P, 2P, 4P, \ldots, 2^n Q$ (with the help of the QCECPointAdderIP component from the Qiskit ECDLP library) and then applies the quantum Fourier transform (QFT), followed by measurement.

This building process is roughly equivalent to the one in the previous Shor’s algorithm article, but with the addition of the elliptic curve point addition operation. Also, the QFT is semi-classical, which is slightly different from the standard QFT we explained in the previous article, semi-classical QFT is more efficient, but they serve the same purpose.

Again, if you are interested in the details of the quantum circuit, you can refer to the paper by Roetteler et al. (link provided in the introduction).

5. Running the Quantum Circuit

from qiskit_aer import AerSimulator
from qiskit import transpile

NUM_SHOTS = 4  # note: 1 shots per minute

# Transpile and simulate the circuit
simulator = AerSimulator()
transpiled_circuit = transpile(circuit, simulator, optimization_level=3)

result = simulator.run(transpiled_circuit, shots=NUM_SHOTS).result()
counts = result.get_counts()
print("Simulation Results:", counts)

Simulation Results: {'11010011': 1, '00100010': 1, '00100111': 1, '11100001': 1}

This code block runs the quantum circuit on a simulator. The circuit is transpiled for the Aer simulator with optimization level 3, that is, the gates are transformed to the gates supported by the simulator, and the circuit is optimized for the best performance. (We will explore the transpilation process in a future article.)

The circuit is then executed on the simulator with a specified number of shots. Despite the small example elliptic curve used here, the size of the quantum circuit (e.g., the number of qubits and gates) is large enough to make my laptop and Google’s Colab notebook struggle to simulate it. Therefore, the number of shots is kept low to avoid long simulation times.

Once the simulation is complete, the measurement outcomes are retrieved and printed. The measurement outcomes are in the form of bit strings, where each bit represents the measurement outcome of a qubit. The bit strings are the results of the quantum Fourier transform (QFT) operation, which we will use to determine the period of the function $f(a, b)$ to find the private key.

6. Post-Processing the Results

from quaspy.math.groups import (
    PointOnShortWeierstrassCurveOverPrimeField,
    ShortWeierstrassCurveOverPrimeField,
)
from quaspy.logarithmfinding.general.postprocessing import solve_j_k_for_d_given_r

result_list = []
for key, value in counts.items():
    # split result measurements
    m_stage1 = int(key[: NUM_BITS // 2], 2)
    m_stage2 = int(key[NUM_BITS // 2 :], 2)

    result_list.append((m_stage1, m_stage2, value))

num_correct = 0
num_wrong = 0
m = -1

quaspy_curve = ShortWeierstrassCurveOverPrimeField(EC_A, EC_B, EC_MODULUS)

for j, k, freq in result_list:
    m_cand = solve_j_k_for_d_given_r(
        # code omitted here for brevity
    )

    if m_cand is not None and (
        classical_point_doubling(point_p, m_cand) == point_q
    ):
        if m != -1:
            m = min(m, int(m_cand))
        else:
            m = int(m_cand)
        num_correct += freq
    else:
        num_wrong += freq

m_correct = classical_point_doubling(point_p, m) == point_q

print(f"Correct: {num_correct}, Wrong: {num_wrong}")
print(f"Private key: {private_key}, Found key: {m}, Correct: {m_correct}")

Correct: 4, Wrong: 0
Private key: 3, Found key: 3, Correct: True

Fortunately, there are python libraries that can help us post-process the measurement outcomes to determine the private key. We first split the measurement outcomes into two parts, m_stage1 and m_stage2, which correspond to the $a$ and $b$ parts in the input of the function $f(a, b) = aP + bQ$. We then use the solve_j_k_for_d_given_r function to find the private key $k$ from the measurement outcomes.

The code block prints the number of correct and wrong measurement outcomes and the found private key. In this case, the private key is correctly found as 3!

What’s Next?

If you’ve executed the code in the Google Colab notebook, you may have noticed that the simulation time is quite long even for this small example. This is because simulating quantum circuits on classical hardware becomes exponentially harder as the number of qubits increases. While real quantum hardware bypasses simulation, it comes with its own set of challenges, including time and space.

To address these challenges, optimizing quantum circuits is critical for improving performance and resource efficiency.

In the next article, we’ll take a look at quantum circuit optimization techniques, focusing on Qiskit’s powerful transpiler and its optimization passes. These tools allow us to refine and optimize quantum circuits for better performance and resource usage.

Leave a comment

You may also enjoy