Hidden subgroup ยท Algorithms

Logical-resource estimate for breaking P-256

Theorem statement

Suppose a P-256 ECC instance has known base point $P$ of prime order $r$ and known public key point $Q=[m]P$ for unknown private scalar $m$. There exists a quantum algorithm that returns $m$ with probability at least $2/3$, using $2.33\times 10^3$ logical qubits, $1.26\times 10^{11}$ Toffoli gates, $1.16\times 10^{11}$ maximal Toffoli-gate depth, and $7$ classical arithmetic operations.
$$P$$
Known base point.
$$r$$
Prime subgroup order of the base point.
$$Q$$
Known public key point.
$$m$$
Unknown private scalar and returned output.

Sources

  1. Quantum resource estimates for computing elliptic curve discrete logarithms

    Martin Roetteler, Michael Naehrig, Krysta M. Svore, Kristin Lauter, 2017

  2. Recommendations for Discrete Logarithm-based Cryptography: Elliptic Curve Domain Parameters

    Lily Chen, Dustin Moody, Karen Randall, Andrew Regenscheid, Angela Robinson, 2023

Lean context

Copy a short prompt with the import, theorem name, citations, and public source link.

Open Lean source