¿Las firmas de Schnorr son resistentes a la computadora cuántica?

Aquí ( https://bitcoincore.org/en/2017/03/23/schnorr-signature-aggregation/ ) dice que Schnorr reemplaza a ECDSA, sabemos que las computadoras cuánticas pueden romper ECDSA. ¿Está Schnorr a salvo de las q-computadoras?

Respuestas (2)

No, ECDSA y EC-Schnorr, así como esquemas relacionados como EdDSA, pertenecen a la clase de criptografía de curva elíptica. Su seguridad se basa en la suposición de que el logaritmo discreto EC es increíblemente difícil de calcular. Esta suposición no es cierta si existiera una computadora cuántica de propósito general suficientemente fuerte.

Existen algoritmos de firma resistentes a la cuántica, pero todos se basan en firmas muy grandes, lo que puede hacer que sean increíblemente caros para propósitos como Bitcoin. Además, existe mucha menos investigación sobre las características superiores (como la derivación homomórfica como los usos de BIP32 o la agregación), lo que las convierte en un paso atrás en términos de funcionalidad si las adoptáramos en su lugar.

Sin embargo, no estoy muy preocupado por esto. La computación cuántica en general tiene un largo camino por recorrer antes de que se acerque siquiera a abordar problemas como resolver logaritmos discretos para curvas de nuestro tamaño. Se necesitaría un control de calidad de uso general con varios miles de qbits, y ni siquiera se sabe si es físicamente posible construir una computadora de este tipo.

Esta es básicamente una pregunta inválida. No importa cómo firmes los datos. Siempre que esté utilizando la curva elíptica y (EC) DLP (Problema de logaritmo discreto de curva elíptica), entonces una computadora cuántica debería ser (por definición, con el algoritmo de Shor) capaz de romperlo. Esto se debe a que la verificación de la firma requiere una clave pública disponible públicamente. Si tiene una computadora cuántica y una clave pública, obtiene la clave privada.

Preguntar si las computadoras cuánticas pueden romper las firmas digitales es como preguntar si cualquiera puede abrir una caja fuerte reforzada, mientras que la clave de esa caja fuerte es la información pública. No importa cómo refuerces la caja fuerte, si hay una manera de hacer una llave que abra esa caja fuerte por cualquiera.

Existen (supuestamente) algoritmos de firma digital seguros post-cuánticos, que involucran claves privadas y públicas. Sin embargo, esas claves no se basarán en variantes del problema del logaritmo discreto.
@PieterWuille Si entiendo su punto correctamente, está diciendo que hay firmas poscuánticas que involucran claves asimétricas y que son seguras. Sí, por supuesto, no hay desacuerdo allí. Mi crítica a la pregunta se basó en que afirmaba que la firma es "vulnerable" en lugar de centrarse en el algoritmo de generación de claves, que puede ser vulnerable o no, y cuáles son los componentes que suelen llevar la seguridad, ya que el titular de La participación de las computadoras cuánticas en la criptomoneda está rompiendo el ECDLP.
Eso es justo, aunque en teoría no es imposible que el algoritmo de generación de claves sea de seguridad cuántica, mientras que el algoritmo de firma no lo es. Eso es una exageración, por supuesto, generalmente se basarán en el mismo problema de dureza computacional. Pero no es imposible construir un esquema de firma (posiblemente inventado) para el cual este es el caso.
Por ejemplo, podría construir un esquema en el que una clave secreta sea solo bytes aleatorios y la clave pública sea un hash (tradicional, digamos SHA256) de la clave privada. Pero entonces la firma es una prueba de conocimiento cero basada en DL o emparejamiento de que ese hash se calculó correctamente, lo que además se compromete con el mensaje. Esto no necesariamente permitirá que un atacante cuántico encuentre la clave privada, pero podría falsificar firmas.
@PieterWuille Tiene sentido. Totalmente de acuerdo contigo. Ese es un caso que no estaba cubriendo en mi respuesta. ¡Salud!
¿Las firmas de Schnorr son resistentes a la computadora cuántica?
RespuestasAquíPolítica de privacidad1y, 0v