⚛️ quantum physics

MPC in the Quantum Head (or: Superposition-Secure (Quantum) Zero-Knowledge)

Este artículo generaliza el paradigma de MPC-in-the-head al entorno cuántico, permitiendo la construcción de argumentos de conocimiento cero de tres rondadas tanto para NP como para QMA en el modelo de cadena de referencia común que permanecen seguros contra ataques de superposición basados en el supuesto estándar de Learning With Errors (LWE).

Autores originales: Andrea Coladangelo, Ruta Jawale, Dakshita Khurana, Giulio Malavolta, Hendrik Waldner

Publicado 2026-07-08

📖 6 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Andrea Coladangelo, Ruta Jawale, Dakshita Khurana, Giulio Malavolta, Hendrik Waldner

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

La visión general: Demostrar que conoces un secreto sin mostrarlo

Imagina que tienes una contraseña secreta (un "testigo") que demuestra que tienes permiso para entrar en un edificio seguro. Quieres convencer a un guardia (el "verificador") de que conoces la contraseña sin decirle realmente cuál es. Esto se llama una Prueba de Conocimiento Cero (Zero-Knowledge Proof).

En el mundo clásico (el mundo de las computadoras regulares), existe un truco famoso llamado "MPC-in-the-Head" para hacer esto.

La analogía: Imagina que eres una sola persona, pero pretendes ser un equipo de cinco amigos sentados en una habitación. Divides tu contraseña secreta en cinco partes (fragmentos o shares) y le das una parte a cada "amigo" dentro de tu cabeza.
El juego: Ejecutas una conversación entre estos cinco amigos para demostrar que la contraseña funciona. Luego, el guardia pide ver las notas de solo dos de los amigos.
El resultado: Si las notas coincen y tienen sentido, el guardia queda convencido de que todo el equipo (y por lo tanto tú) conoce la contraseña. Pero como el guardia solo vio a dos amigos, no puede averiguar la contraseña completa.

El nuevo problema: El ladrón de la "superposición"

Este artículo aborda un nuevo y aterrador problema: ¿Qué pasa si el guardia es una computadora cuántica?

En el mundo cuántico, una "superposición" es como estar en dos lugares a la vez. Un adversario cuántico (el malo) no solo pide ver las notas del Amigo A o del Amigo B. Puede pedir ver una superposición de ambos al mismo tiempo.

La metáfora: Imagina que el guardia no solo mira el papel; pone el papel en una caja mágica que le permite echar un vistazo a todas las combinaciones posibles de las notas de los amigos simultáneamente.
El riesgo: En los trucos antiguos, si solo mostrabas a dos amigos, el secreto estaba a salvo. Pero si el guardia puede echar un vistazo a una "superposición" de las notas, podría ser capaz de reconstruir matemáticamente toda la contraseña, rompiendo la seguridad.

Los autores se preguntan: ¿Podemos construir una prueba de conocimiento cero que se mantenga segura incluso si el guardia usa este superpoder de la "superposición"?

La solución: "MPC in the Quantum Head"

Los autores dicen que sí, y lo hacen mejorando el truco de "MPC-in-the-Head" para el mundo cuántico. Llaman a su nuevo método "MPC in the Quantum Head".

Así es como resuelven los dos desafíos principales:

1. Para secretos regulares (Problemas NP)

El viejo problema: Los intentos previos de hacer esto seguro para el mundo cuántico dependían de un tipo especial de "cerradura mágica" (un esquema de compromiso o commitment scheme) que era perfectamente oculto. Pero nadie sabe cómo construir estas cerraduras usando matemáticas estándar.
El nuevo truco: Los autores utilizan un tipo diferente de cerradura llamada "Compromiso de Modo Dual" (Dual-Mode Commitment).
- La analogía: Imagina una caja fuerte que tiene dos llaves.
  - Llave A (Vinculante/Binding): La caja fuerte está cerrada herméticamente. Una vez que pones una nota dentro, no puedes cambiarla. Pero si tienes una computadora superpotente, podrías ser capaz de adivinar la nota.
  - Llave B (Ocultadora/Hiding): La caja fuerte es tan opaca que incluso una computadora superpotente no puede ver qué hay dentro. Pero, si tienes una "puerta trasera" especial (que el probador sí tiene), puedes abrirla para revelar cualquier cosa que quieras.
- Cómo funciona: El probador utiliza el modo "Ocultador" para enviar las notas. Debido a que las notas están ocultas, el guardia cuántico no puede aprender el secreto incluso si las mira en superposición. Los autores demuestran que, incluso con esta cerradura ligeramente más débil, las matemáticas se mantienen.

2. Para secretos cuánticos (Problemas QMA)

Esta es la parte más difícil. ¿Qué pasa si el secreto mismo es un estado cuántico (como una delicada e invisible nube de probabilidad) en lugar de una simple contraseña?

El desafío: En la versión clásica, los "amigos" se pasan notas de un lado a otro. En la versión cuántica, los "amigos" pasan partículas cuánticas (qubits). No puedes simplemente "escribir" las notas de una partícula cuántica sin destruir el secreto. No hay un "registro" o "transcripción" que se pueda revisar.
El nuevo truco: Los autores utilizan una técnica llamada "Reducción de Circuito a Hamiltoniano" (Circuit-to-Hamiltonian Reduction).
- La analogía: Imagina que la conversación cuántica entre los amigos es una película. Normalmente, no puedes revisar la película sin verla toda.
- En su lugar, convierten la película en una escultura congelada (un Hamiltoniano). Esta escultura tiene una forma específica. Si los amigos jugaron correctamente, la escultura tiene una "energía" muy baja (es suave y perfecta). Si hicieron trampa, la escultura es irregular y tiene una energía alta.
- La verificación: El guardia no pide ver toda la película. Simplemente toca la escultura en algunos puntos aleatorios para medir la energía.
  - Si la energía es baja, el juego se jugó correctamente.
  - Debido a que la escultura está hecha de muchas partes diminutas, tocar algunos puntos no revela toda la película (el secreto).
La "Cabeza Cuántica" (Quantum Head): El probador divide el secreto cuántico entre los amigos, lo encripta y crea esta "escultura congelada" de la conversación. El guardia revisa la energía de la escultura.

Por qué esto es importante (Según el artículo)

El artículo afirma haber construido dos herramientas específicas:

Una prueba para secretos regulares (NP): Funciona basándose en un problema matemático estándar llamado LWE (Learning With Errors), que se cree que es difícil incluso para las computadoras cuánticas.
Una prueba para secretos cuánticos (QMA): Este es un gran avance. Es la primera vez que se construye una prueba de conocimiento cero para problemas cuánticos que sea segura contra estos ataques de "superposición", también basada en el supuesto LWE.

Resumen

El artículo toma un truco clásico para demostrar secretos ("MPC-in-the-Head"), lo actualiza para manejar la mecánica cuántica y resuelve el problema de los "ataques de superposición". Lo logran:

Utilizando cerraduras especiales de "modo dual" que son difíciles de romper incluso para las computadoras cuánticas.
Convirtiendo las conversaciones cuánticas en "esculturas congeladas" (Hamiltonianos) que pueden ser revisadas sin revelar el secreto.

Esto asegura que, incluso si una futura computadora cuántica intenta echar un vistazo a una prueba en una "superposición" de todas las posibilidades, el secreto permanezca a salvo.

Resumen Técnico: MPC en la Cabeza Cuántica (Zero-Knowledge con Seguridad de Superposición)

Declaración del Problema

El artículo aborda la construcción de protocolos de Conocimiento Cero (ZK - Zero-Knowledge) que sigan siendo seguros incluso cuando un verificador malicioso puede emitir desafíos y recibir respuestas en superposición cuántica. Esta "seguridad de superposición" es un fortalecimiento crítico de la seguridad clásica, motivado por escenarios donde adversarios cuánticos podrían interactuar con dispositivos criptográficos clásicos o donde las primitivas clásicas están embebidas dentro de protocolos cuánticos más grandes.

Aunque Damgård et al. [19] fueron pioneros en esta noción para NP, su construcción dependía de compromisos de modo dual perfectamente ocultos e incondicionalmente vinculantes, una primitiva que no se conoce que exista bajo supuestos criptográficos estándar. Además, sus técnicas no se extendían naturalmente a QMA (Merlin-Arthur Cuántico), el análogo cuántico de NP, debido a la dificultad fundamental de verificar computaciones cuánticas sin revelar el testigo cuántico.

Las alternativas existentes, como las pruebas de Conocimiento Cero No Interactivo (NIZK), son o bien desconocidas para QMA bajo supuestos estándar o dependen de modelos heurísticos (por ejemplo, oráculos aleatorios cuánticos o ofuscación). Además, los NIZK son generalmente más pesados que los protocolos $\Sigma$ de tres rondas preferidos por su eficiencia.

Metodología

Los autores proponen una generalización del paradigma MPC-in-the-Head (MPC en la cabeza) [30] al entorno cuántico, denominada "MPC in the Quantum Head" (MPC en la cabeza cuántica). La metodología central involucra dos construcciones distintas pero relacionadas:

1. ZK con Seguridad de Superposición para NP

Los autores revisan el protocolo de Damgård et al. [19] pero reemplazan el requisito de compromisos perfectamente ocultos por compromisos de modo dual (estadísticamente ocultos, computacionalmente vinculantes en un modo; perfectamente vinculantes, computacionalmente ocultos en el otro).

Técnica: La estrategia de prueba utiliza un argumento de híbrido. En el mundo real, los compromisos son hacia las vistas de MPC. En un híbrido, los compromisos se cambian al modo estadísticamente oculto. Crucialmente, los autores introducen un híbrido donde el probador se compromete a 0 (en lugar de vistas honestas) pero aún puede abrirlos a las vistas honestas usando la propiedad de vinculación computacional (que se rompe mediante un simulador no acotado).
Argumento de Seguridad: Una vez que los compromisos son hacia 0, las vistas abiertas (un subconjunto de las partes/shares) y los compromisos no abiertos forman un esquema de intercambio secreto perfectamente seguro. Los autores aprovechan un lema de [19] que establece que el intercambio secreto perfecto sigue siendo seguro contra ataques de superposición si se consultan menos de $2t$ partes (donde $t$ es el umbral de privacidad). Esto permite que la prueba de seguridad proceda sin requerir compromisos perfectamente ocultos.

2. MPC en la Cabeza Cuántica para QMA

Extender esto a QMA requiere manejar testigos cuánticos y circuitos de verificación cuánticos.

El Obstáculo: En el MPC-in-the-Head clásico, el probador revela "vistas" (transcripciones) de las partes. En la Computación Cuántica Multipartita (MPQC), las partes intercambian mensajes cuánticos, lo que significa que no hay una transcripción clásica para revelar; una parte solo posee un estado cuántico final.
La Solución: Los autores modelan el protocolo MPQC global como un circuito cuántico (reemplazando el paso de mensajes con puertas SWAP). Aplican la reducción de Circuito-a-Hamiltoniano de Kitaev [34] a este circuito.
- El "testigo" se convierte en el estado de historia del Hamiltoniano, el cual tiene baja energía si y solo si el MPQC acepta.
- El probador se compromete a este estado de historia (qubit por qubit) utilizando un Quantum One-Time Pad (QOTP) y se compromete a las claves del QOTP usando compromisos de modo dual.
- El verificador desafía al probador a abrir qubits específicos correspondientes a términos locales del Hamiltoniano.
Verificación: El verificador mide los qubits abiertos para verificar los términos locales del Hamiltoniano. Si la energía es baja, el estado de historia corresponde a una ejecución válida.
Zero-Knowledge: La propiedad de ZK depende del hecho de que abrir un subconjunto de qubits correspondientes a un término del Hamiltoniano local no revela más información de la que revela el control de un subconjunto de las partes en el protocolo MPQC subyacente. Los autores utilizan un protocolo MPQC perfectamente $2t$ -privado [17, 39] para asegurar que el estado de historia de la computación sobre un testigo compartido en secreto sea indistinguible de un estado de historia sobre una entrada ficticia, incluso bajo consultas de superposición.

Contribuciones Clave

Generalización de MPC-in-the-Head: El artículo presenta la primera instanciación del paradigma MPC-in-the-Head para funcionalidades cuánticas (MPQC), creando efectivamente un "Quantum MPC-in-the-Head".
ZK con Seguridad de Superposición para NP: Los autores construyen un protocolo $\Sigma$ de tres rondas para NP seguro contra ataques de superposición basado en cualquier compromiso de modo dual post-cuántico (por ejemplo, de LWE). Esto mejora a [19] al eliminar la necesidad de compromisos no estándar perfectamente ocultos.
ZK con Seguridad de Superposición para QMA: El artículo construye el primer protocolo $\Sigma$ de tres rondas para QMA seguro contra ataques de superposición, basado en el supuesto de Learning With Errors (LWE). Esto llena un vacío donde no existen NIZKs para QMA bajo supuestos estándar.
Nuevas Técnicas de Prueba:
- Un nuevo argumento de híbrido para NP que cambia los compromisos a 0 para aprovechar las propiedades del intercambio secreto perfecto contra ataques de superposición.
- Una técnica para QMA que combina la reducción de Circuito-a-Hamiltoniano con MPQC y QOTP, utilizando la indistinguibilidad de los pares EPR y los one-time pads para simular el protocolo en presencia de consultas de superposición.

Resultados

El artículo establece los siguientes teoremas (informales):

Teorema 1.1: Asumiendo la seguridad post-cuántica de LWE, existen protocolos $\Sigma$ de tres rondas para QMA en el modelo de Cadena de Referencia Común (CRS) que satisfacen el conocimiento cero contra verificadores maliciosos que realizan consultas de superposición.
Teorema 1.2: Asumiendo la existencia de cualquier compromiso de modo dual post-cuántico, existen protocolos $\Sigma$ de tres rondas para NP en el modelo CRS que satisfacen el conocimiento cero contra verificadores maliciosos que realizan consultas de superposición.

Los protocolos logran solidez estadística y conocimiento cero computacional (incluso contra adversarios de tiempo polinómico cuántico con acceso a superposición).

Significancia y Reivindicaciones

Los autores posicionan este trabajo como una extensión natural y necesaria de la criptografía de conocimiento cero hacia el régimen cuántico.

Importancia Teórica: Resuelve el problema abierto de construir ZK con seguridad de superposición para QMA bajo supuestos estándar, una tarea que anteriormente se consideraba difícil debido a la falta de NIZKs o esquemas de compromiso adecuados.
Relevancia Práctica: La estructura de tres rondas hace que estos protocolos sean significativamente más ligeros que los NIZK, ofreciendo un camino práctico para firmas post-cuánticas y compiladores de computación multipartita segura (por ejemplo, compiladores estilo GMW) que deben permanecer seguros contra adversarios cuánticos capaces de ataques de superposición.
Avance Conceptual: El marco "MPC in the Quantum Head" se presenta como una técnica generalizable que podría aplicarse a otros protocolos de commit-and-open o cut-and-choose que requieran la verificación parcial de computaciones cuánticas.

El artículo señala explícitamente que, si bien existen NIZKs para QMA en modelos de oráculo o con verificadores designados, su enfoque en protocolos de tres rondas con supuestos estándar y configuración pública (CRS) proporciona una solución más directa y eficiente para el modelo de amenaza específico de los ataques de superposición.