Optimized Point Addition Circuits for Elliptic Curve Discrete Logarithms

Este artículo presenta una arquitectura de circuito lógico cuántico detallada para la optimización de la suma de puntos en curvas elípticas sobre campos primos, logrando una reducción del 6.5% al 10% en el recuento de puertas Toffoli para secp256k1 en comparación con los resultados basados en pruebas de conocimiento cero de Babbush et al., incurriendo únicamente en un aumento marginal del 1.5% en el uso de cúbits.

Lo esencial

Imagina que estás intentando abrir una cerradura muy compleja. Durante décadas, los matemáticos han sabido que un tipo especial de "superllave" (una computadora cuántica) podría abrir esta cerradura casi instantáneamente, rompiendo la seguridad de la mayor parte de la encriptación de Internet. Esto se conoce como Algoritmo de Shor.

Sin embargo, construir esta superllave es increíblemente caro y difícil. Requiere una enorme cantidad de "energía mágica" (recursos cuánticos) para funcionar. El objetivo de este artículo es averiguar cómo construir una versión más pequeña y eficiente de esa llave.

Aquí está el desglose de lo que el autor, André Schrottenloher, logró, explicado mediante analogías de la vida cotidiana.

1. El gran problema: La mochila pesada

Piensa en ejecutar el algoritmo de Shor como si estuvieras haciendo senderismo por una montaña. Para llegar a la cima (romper el código), necesitas llevar una mochila pesada llena de suministros (bits cuánticos, o "qubits").

• Intentos anteriores: Otros investigadores construyeron recientemente una mochila muy eficiente que era más ligera que nunca. Sin embargo, mantuvieron los planos en secreto, usando un "truco de magia" (una prueba de conocimiento cero) para convencer a todos de que la mochila era ligera sin mostrarles cómo estaba hecha.
• El objetivo de este artículo: El autor quería construir una mochila que fuera tan ligera como la secreta, pero con los planos totalmente abiertos para que cualquiera pueda verificar el trabajo.

2. La tarea central: Añadir puntos en una curva

El trabajo principal del algoritmo es realizar una operación matemática específica llamada "adición de puntos" en una curva elíptica.

• La analogía: Imagina que estás caminando sobre un trampolín gigante y curvo. Necesitas saltar de un lugar a otro basándote en un conjunto de reglas. Hacer este salto perfectamente es difícil.
• El cuello de botella: La parte más difícil del salto es un movimiento específico llamado "multiplicación in situ". Es como intentar multiplicar dos números mientras solo se te permite usar el espacio donde estás parado actualmente, sin tener espacio extra para escribir notas de apoyo.

3. La solución: El "baile de dos pasos"

Para resolver el problema de "no tener papel de notas", el autor utilizó una estrategia astuta de dos pasos (basada en un método llamado Algoritmo de Euclides Extendido):

• Paso 1: La cinta de memoria (Registrar los movimientos)
  En lugar de hacer la matemática y conservar el resultado, la computadora primero simplemente registra qué movimientos habría hecho en una larga cinta de bits. Todamente no realiza el trabajo pesado todavía; solo escribe las instrucciones. Esta cinta es sorprendentemente corta.
• Paso 2: La reconstrucción (Reproducir los movimientos)
  Una vez escrita la cinta, la computadora la reproduce en reversa. Utiliza las instrucciones en la cinta para realizar la matemática real sobre los números.
• Por qué esto ayuda: Al separar la "planificación" del "hacer", la computadora ahorra una cantidad masiva de espacio. Es como escribir una receta en una nota adhesiva antes de empezar a cocinar, para no tener que sostener todos los ingredientes en tus manos a la vez.

4. El atajo: El primo "Pseudo-Mersenne"

El artículo se centra en un tipo de cerradura específica llamada secp256k1 (usada por Bitcoin). Esta cerradura tiene una forma especial.

• La analogía: Imagina que una cerradura genérica es un cuadrado perfecto. Pero la cerradura de Bitcoin es un cuadrado con una pequeña esquina cortada.
• La optimización: Debido a que la esquina está cortada, la matemática necesaria para abrirla es ligeramente más fácil. El autor diseñó herramientas especiales que aprovechan esta "esquina cortada" para saltarse pasos innecesarios.
  • Para una cerradura genérica (cualquier número primo), las herramientas son estándar y ligeramente más pesadas.
  • Para la cerradura de Bitcoin (secp256k1), las herramientas están optimizadas y son más ligeras porque saben exactamente dónde falta la esquina.

5. Los resultados: Una mochila ligeramente más ligera

El autor construyó el "plano" completo para esta nueva mochila y la probó.

• Espacio (Qubits): La nueva mochila es aproximadamente un 1.5% más pesada que la versión secreta de otros investigadores. Es un intercambio minúsculo.
• Energía (Puertas): Sin embargo, la nueva mochila es entre un 6.5% y un 10% más eficiente en términos de la energía (puertas Toffoli) necesaria para ejecutarla.
• Fiabilidad: El autor demostró que esta mochila funciona con la misma fiabilidad que la versión secreta. Si intentas usarla con entradas aleatorias, tiene éxito casi siempre, al igual que la versión secreta.

Resumen

En términos simples, este artículo dice: "Descubrimos cómo construir la computadora cuántica necesaria para romper la encriptación moderna. No solo lo adivinamos; escribimos las instrucciones exactas. Nuestra versión es ligeramente mayor en tamaño, pero utiliza menos energía para ejecutarse que la versión 'secreta' anterior, y demostramos que funciona tanto para cerraduras genéricas como para la cerradura específica utilizada por Bitcoin".

El autor enfatiza que este es un diseño lógico (el plano teórico). Esto no significa que podamos construirlo hoy, pero nos dice exactamente cuánta "energía mágica" necesitaremos cuando las computadoras cuánticas finalmente sean lo suficientemente potentes como para intentarlo.

Resumen técnico

Planteamiento del Problema
El artículo aborda la estimación de recursos del algoritmo de Shor para el cálculo de logaritmos discretos de curvas elípticas (ECDL), una amenaza principal para la criptografía de clave pública actual. Si bien trabajos recientes de Babbush et al. (arXiv 2026) demostraron reducciones significativas en el conteo de puertas y cúbits para la curva secp256k1, estos dependían de una prueba de conocimiento cero para validar sus resultados sin revelar los circuitos cuánticos lógicos subyacentes. Esta falta de transparencia dificulta la reproducibilidad y la verificación independiente. El objetivo del artículo es proporcionar una arquitectura de circuito cuántico lógico totalmente detallada y reproducible que logre una eficiencia comparable a la de Babbush et al., revelando explícitamente los principios de diseño y los detalles de implementación.

Metodología
Los autores emplean un enfoque descendente (top-down), partiendo de la estructura de alto nivel del algoritmo de Shor y refinando los componentes aritméticos. El núcleo de la optimización reside en la implementación de la suma de puntos con ventana (windowed point addition) en curvas elípticas sobre campos primos.

1. Estructura de Alto Nivel: El algoritmo utiliza una transformada de Fourier semiclásica con reciclaje de cúbits para reducir la multiplicación de puntos $|u, v\rangle|0\rangle \to |u, v\rangle|[u]P + [v]Q\rangle$ a una secuencia de sumas de puntos con ventana. Los puntos se representan en coordenadas afines.
2. Multiplicación Modular In-Situ: La operación más costosa en la suma de puntos es la multiplicación modular in-situ $|x, y\rangle \to |x, yx \pmod q|$. Los autores adaptan una técnica de [14] que desacopla el Algoritmo de Euclides Extendido (EEA) en dos fases distintas:
   • Algoritmo de Euclides (Hacia adelante): En lugar de calcular directamente los coeficientes de Bézout, esta fase procesa las entradas $(q, x)$ y genera un vector de bits de "basura" (garbage) que codifica la secuencia de operaciones (intercambios, sustracciones, divisiones por 2). Esto reduce la complejidad espacial.
   • Reconstrucción de Bézout (Hacia atrás): Esta fase toma el vector de bits de basura y aplica las operaciones registradas a un par $(y, 0)$ para calcular $|y, yx^{-1} \pmod q\rangle$. Al ejecutar esto en reversa o con entradas específicas, los autores logran la multiplicación y la inversión in-situ simultáneamente.
3. Optimización Aritmética:
   • Compromiso entre Espacio y Puertas: Los autores cambian estratégicamente entre el sumador CDKM (bajo espacio) y el sumador Gidney (bajo conteo de puertas, mayor espacio) dependiendo de la disponibilidad de cúbits ancilla durante las diferentes etapas del algoritmo.
   • Aritmética Aproximada: Para reducir el conteo de puertas, los autores introducen circuitos de aritmética aproximada. Las comparaciones se realizan utilizando únicamente los bits más significativos (MSB) en lugar de comparaciones de ancho completo. Esto introduce una probabilidad de fallo, la cual se gestiona optimizando las constantes para asegurar el éxito en entradas aleatorias con alta probabilidad (específicamente, probabilidad de fallo $\le 2^{-13.3}$).
   • Optimización Específica de la Instancia: Para la curva secp256k1, que utiliza un primo pseudo-Mersenne ($q = 2^{256} - 4294968273$), los circuitos de reducción modular se simplifican aún más. Los autores aprovechan la pequeña diferencia $f$ en la forma $2^u - f$ para reemplazar las costosas sustracciones modulares por manipulaciones de bits simples y adiciones de $f$.

Contribuciones Clave

• Arquitectura de Circuito Reproducible: El artículo detalla el primer circuito cuántico lógico totalmente especificado para ECDL en secp256k1 que iguala las afirmaciones de eficiencia del trabajo opaco de Babbush et al. El código está implementado y disponible a través de la biblioteca Qarton.
• Conteos de Recursos Optimizados: Los autores presentan dos variantes del circuito:
  • Optimizado para el espacio: Utiliza aproximadamente $4.36n + O(\sqrt{n})$ cúbits.
  • Optimizado para puertas: Utiliza aproximadamente $4.36n + O(\sqrt{n})$ cúbits pero reduce el conteo de puertas Toffoli.
• Variante Genérica: Se proporciona una versión del circuito que es válida para cualquier campo primo, no solo para secp256k1, aunque incurre en un costo de puertas ligeramente superior debido a la falta de optimizaciones de pseudo-Mersenne.
• Análisis de Costos Detallado: El artículo proporciona un desglose granular de los costos de puertas Toffoli, distinguiendo entre la construcción del GCD, la reconstrucción de Bézout y los componentes de aritmética modular.

Resultados
Los autores reportan las siguientes estimaciones de recursos para la curva secp256k1 (donde $n=256$):

• Conteo de Cúbits:
  • Variante optimizada para el espacio: 1,192 cúbits (comparado con 1,175 en Babbush et al.).
  • Variante optimizada para puertas: 1,446 cúbits (comparado con 1,425 en Babbush et al.).
  • Esto representa un ligero incremento de aproximadamente 1.5% en el conteo de cúbits.
• Conteo de Puertas (Toffolis):
  • Variante optimizada para el espacio: $2^{21.19}$ (aprox. $2.3 \times 10^6$).
  • Variante optimizada para puertas: $2^{20.83}$ (aprox. $1.8 \times 10^6$).
  • Esto representa una reducción del 6.5% al 10% en el conteo de puertas Toffoli en comparación con Babbush et al.
• Costo del Algoritmo Completo: Para el algoritmo de Shor completo en secp256k1, la variante optimizada para puertas requiere aproximadamente $2^{25.78}$ puertas Toffoli y 1,462 cúbits. Esto es una mejora significativa respecto al trabajo previo de Litinski (arXiv 2023), el cual requería aproximadamente $2^{27.57}$ puertas Toffoli y el doble de cúbits.

Significancia
El artículo reclama su significancia principalmente en el ámbito de la reproducibilidad y la transparencia. Al proporcionar la arquitectura explícita del circuito lógico, los autores permiten que la comunidad criptográfica verifique las estimaciones de recursos para romper la criptografía de curva elíptica, que anteriormente estaban ocultas tras una prueba de conocimiento cero. El trabajo demuestra que se puede lograr una eficiencia similar o ligeramente mejorada mediante elecciones de diseño explícitas, específicamente la separación del EEA en una fase de registro y una fase de reconstrucción, combinada con aritmética aproximada. Los autores señalan que sus circuitos no son exactos y dependen de una alta probabilidad de éxito en entradas aleatorias, una propiedad compartida con el trabajo que replican. Los resultados confirman que el costo de romper secp256k1 es menor de lo estimado previamente por algunos modelos de circuitos lógicos, reforzando la urgencia de la migración post-cuántica.