Elliptic Curve Cryptography#

Bloqs for breaking elliptic curve cryptography systems via the discrete log.

Elliptic curve cryptography is a form of public key cryptography based on the finite field of elliptic curves. For our purposes, we will denote the group operation as addition (whose definition we will explore later) \(A + B\). We will denote repeated addition as \([k] A = A + \dots + A\) (\(k\) times).

Within this algebra, the cryptographic scheme relates the public and private keys via

\[ Q = [k] P \]
for private key \(k\), public key \(Q\), and a choice of base point \(P\). The cryptographic security comes from the difficulty of inverting the multiplication. I.e. it is difficult to do a discrete logarithm in this field.

Using Shor’s algorithm for the discrete logarithm, we can find \(k\) in polynomial time with a quantum algorithm.

from qualtran import Bloq, CompositeBloq, BloqBuilder, Signature, Register
from qualtran import QBit, QInt, QUInt, QAny
from qualtran.drawing import show_bloq, show_call_graph, show_counts_sigma
from typing import *
import numpy as np
import sympy
import cirq

FindECCPrivateKey#

Perform two phase estimations to break elliptic curve cryptography.

This follows the strategy in Litinski 2023. We perform two phase estimations corresponding to ECCAddR(R=P) and ECCAddR(R=Q) for base point \(P\) and public key \(Q\).

The first phase estimation projects us into a random eigenstate of the ECCAddR(R=P) operator which we index by the integer \(c\). Per eq. 5 in the reference, these eigenstates take the form

\[\begin{split} |\psi_c \rangle = \sum_j^{r-1} \omega^{cj}\ | [j]P \rangle \\ \omega = e^{2\pi i / r} \\ [r] P = P \end{split}\]

This state is a simultaneous eigenstate of the second operator, ECCAddR(R=Q). By the definition of the operator, acting it upon \(|\psi_c\rangle\) gives:

\[ |\psi_c \rangle \rightarrow \sum_j w^{cj} | [j]P + Q \rangle\rangle \]

The private key \(k\) that we wish to recover relates the public key to the base point

\[ Q = [k] P \]
so our simultaneous eigenstate can be equivalently written as
\[\begin{split} \sum_j^{r-1} \omega^{cj} | [j+k] P \rangle \\ = \omega^{-ck} |\psi_c \rangle \end{split}\]

Therefore, the measured result of the second phase estimation is \(ck\). Since we have already measured the random index \(c\), we can divide it out to recover the private key \(k\).

Parameters#

  • n: The bitsize of the elliptic curve points’ x and y registers.

  • base_point: The base point \(P\) with unknown order \(r\) such that \(P = [r] P\).

  • public_key: The public key \(Q\) such that \(Q = [k] P\) for private key \(k\).

  • add_window_size: The number of bits in the ECAdd window.

  • mul_window_size: The number of bits in the modular multiplication window.

References#

from qualtran.bloqs.factoring.ecc import FindECCPrivateKey

from qualtran.bloqs.factoring.ecc import ECPoint

Example Instances#

n, p = sympy.symbols('n p')
Px, Py, Qx, Qy = sympy.symbols('P_x P_y Q_x Q_y')
P = ECPoint(Px, Py, mod=p)
Q = ECPoint(Qx, Qy, mod=p)
ecc = FindECCPrivateKey(n=n, base_point=P, public_key=Q)

Graphical Signature#

from qualtran.drawing import show_bloqs
show_bloqs([ecc],
           ['`ecc`'])

Call Graph#

from qualtran.resource_counting.generalizers import ignore_split_join
ecc_g, ecc_sigma = ecc.call_graph(max_depth=1, generalizer=ignore_split_join)
show_call_graph(ecc_g)
show_counts_sigma(ecc_sigma)
../../../_images/8d23856b20567b4a7a782cc28266c57c99962744cd1105678c8051f048966b01.svg

Counts totals:

  • PE$(_Rx0, _Ry0)$: 2

show_bloq(ecc.decompose_bloq())
../../../_images/27816d9dacfb50733130a2df48b06ba209f620b1dc69708c32a7cf11b96a563a.svg

ECPhaseEstimateR#

Perform a single phase estimation of ECAddR for a given point.

This is used as a subroutine in FindECCPrivateKey. First, we phase-estimate the addition of the base point \(P\), then of the public key \(Q\).

When the ellptic curve point addition window size is 1 we use the ECAddR bloq which has it’s own bespoke circuit; when it is greater than 1 we use the windowed circuit which uses pre-computed classical additions loaded into the circuit.

Parameters#

  • n: The bitsize of the elliptic curve points’ x and y registers.

  • point: The elliptic curve point to phase estimate against.

  • add_window_size: The number of bits in the ECAdd window.

  • mul_window_size: The number of bits in the modular multiplication window.

from qualtran.bloqs.factoring.ecc import ECPhaseEstimateR

Example Instances#

n, p = sympy.symbols('n p')
Rx, Ry = sympy.symbols('R_x R_y')
ec_pe = ECPhaseEstimateR(n=n, point=ECPoint(Rx, Ry, mod=p))

n = 3
Rx, Ry, p = sympy.symbols('R_x R_y p')
ec_pe_small = ECPhaseEstimateR(n=n, point=ECPoint(Rx, Ry, mod=p))

Graphical Signature#

from qualtran.drawing import show_bloqs
show_bloqs([ec_pe, ec_pe_small],
           ['`ec_pe`', '`ec_pe_small`'])

Call Graph#

from qualtran.resource_counting.generalizers import ignore_split_join
ec_pe_g, ec_pe_sigma = ec_pe.call_graph(max_depth=1, generalizer=ignore_split_join)
show_call_graph(ec_pe_g)
show_counts_sigma(ec_pe_sigma)
../../../_images/6eea9429af7921424b5108224e328e9026698353e62f8c5cc2f88ddf148740dc.svg

Counts totals:

  • ECAddR: $\displaystyle \left\lfloor{n}\right\rfloor$

  • MeasureQFT: 1

ECAddR#

Perform elliptic curve addition of constant R.

Given the constant elliptic curve point \(R\) and an input point \(A\) factored into the x and y registers such that \(|A\rangle = |(a_x,a_y)\rangle\), this bloq takes

\[ |A\rangle \rightarrow |A+R\rangle \]

Parameters#

  • n: The bitsize of the two registers storing the elliptic curve point.

  • R: The elliptic curve point to add.

Registers#

  • ctrl: A control bit.

  • x: The x component of the input elliptic curve point of bitsize n.

  • y: The y component of the input elliptic curve point of bitsize n.

References#

from qualtran.bloqs.factoring.ecc import ECAddR

Example Instances#

n, p, Rx, Ry = sympy.symbols('n p R_x R_y')
ec_add_r = ECAddR(n=n, R=ECPoint(Rx, Ry, mod=p))

n = 5  # fits our mod = 17
P = ECPoint(15, 13, mod=17, curve_a=0)
ec_add_r_small = ECAddR(n=n, R=P)

Graphical Signature#

from qualtran.drawing import show_bloqs
show_bloqs([ec_add_r, ec_add_r_small],
           ['`ec_add_r`', '`ec_add_r_small`'])

Call Graph#

from qualtran.resource_counting.generalizers import ignore_split_join
ec_add_r_g, ec_add_r_sigma = ec_add_r.call_graph(max_depth=1, generalizer=ignore_split_join)
show_call_graph(ec_add_r_g)
show_counts_sigma(ec_add_r_sigma)
../../../_images/5131696c70b78cb98a074ecbc2ecfe9353b14716bc54931868ce092a2725ade3.svg

Counts totals:

  • ECAddR: 1

for j in range(1, 20+1):
    bloq = ECAddR(n=5, R=j*P)
    ctrl, x, y = bloq.call_classically(ctrl=1, x=P.x, y=P.y)
    print(f'+[{j:2d}] P  ->  ({x:2d}, {y:2d})')

+[ 1] P  ->  ( 2, 10)
+[ 2] P  ->  ( 8,  3)
+[ 3] P  ->  (12,  1)
+[ 4] P  ->  ( 6,  6)
+[ 5] P  ->  ( 5,  8)
+[ 6] P  ->  (10, 15)
+[ 7] P  ->  ( 1, 12)
+[ 8] P  ->  ( 3,  0)
+[ 9] P  ->  ( 1,  5)
+[10] P  ->  (10,  2)
+[11] P  ->  ( 5,  9)
+[12] P  ->  ( 6, 11)
+[13] P  ->  (12, 16)
+[14] P  ->  ( 8, 14)
+[15] P  ->  ( 2,  7)
+[16] P  ->  (15,  4)
+[17] P  ->  ( 0,  0)
+[18] P  ->  (15, 13)
+[19] P  ->  ( 2, 10)
+[20] P  ->  ( 8,  3)

ECWindowAddR#

Perform elliptic curve addition of many multiples of constant R.

This adds R, 2R, … 2^window_size into the register.

Parameters#

  • n: The bitsize of the two registers storing the elliptic curve point

  • R: The elliptic curve point to add (NOT in montgomery form).

  • add_window_size: The number of bits in the ECAdd window.

  • mul_window_size: The number of bits in the modular multiplication window.

Registers#

  • ctrl: window_size control bits.

  • x: The x component of the input elliptic curve point of bitsize n in montgomery form.

  • y: The y component of the input elliptic curve point of bitsize n in montgomery form.

References#

from qualtran.bloqs.factoring.ecc import ECWindowAddR

Example Instances#

n = 16
P = ECPoint(2, 2, mod=7, curve_a=3)
ec_window_add_r_small = ECWindowAddR(n=n, R=P, add_window_size=4)

Graphical Signature#

from qualtran.drawing import show_bloqs
show_bloqs([ec_window_add_r_small],
           ['`ec_window_add_r_small`'])

Call Graph#

from qualtran.resource_counting.generalizers import ignore_split_join
ec_window_add_r_small_g, ec_window_add_r_small_sigma = ec_window_add_r_small.call_graph(max_depth=1, generalizer=ignore_split_join)
show_call_graph(ec_window_add_r_small_g)
show_counts_sigma(ec_window_add_r_small_sigma)
../../../_images/a979457be0fccc7edda42183c4cd83ffe718182ea87f3106d362bdcda9e96400.svg

Counts totals:

  • ECAdd: 1

  • QROAMCleanAdjoint: 1

  • QROAMClean: 1