Conocimiento cero no interactivo no clonable en el modelo cuántico aleatorio de Oracle

Tabla de enlaces

Resumen e introducción

Resumen técnico

Preliminares

Conocimiento cero no interactivo no clonable en el modelo CRS

NIZK no clonable en el modelo Quantum Ramdon Oracle

Firmas de conocimiento no clonables

Referencias

5 NIZK no clonables en el modelo cuántico aleatorio de Oracle

5.1 Un protocolo Sigma modificado

Comenzaremos introduciendo un protocolo sigma ligeramente modificado. En las próximas secciones, nuestra construcción implicará la aplicación de Fiat-Shamir a este protocolo modificado.

Prueba. Completitud perfecta Esto se deriva directamente de la completitud perfecta de Π.

y cualquier x con λ ∈ N asociado que satisfaga

tenemos

Definimos Ext 3 con acceso de Oracle a Π.Ext y algo de A de la siguiente manera:

Entrada: x, S.

(1) Dado (x, α, s) de AΠ: envíe α a Π.Ext, reciba β de Π.Ext y envíe β a AΠ.

(2) Al recibir γ de AΠ: enviar γ a Π.Ext.

(3) Genere el resultado de Π.Ext como w.

Definimos el siguiente conjunto de parámetros: c = cΠ, p(·) = pΠ(·), negl0 (·) = negl0,Π(·) y negl1 (·) = negl1,Π(·).

Sea el circuito cuántico de tamaño polinómico A = (A 0, A 1) y (x, S) tal que

Ahora definimos AΠ = (A0,Π, A1,Π) con acceso de Oracle a A. A0,Π está cableado con S, toma la entrada x, envía (x, S) a A0, recibe ((x, α, s ), |sti) de A0 y salidas (α, |sti). A1, Π está cableado con S, toma la entrada (x, |sti, β), envía ((x, S), |sti, β) a A1, recibe γ de A1, genera γ. Por la estructura de nuestra prueba y definición de nuestro verificador, esto significa que

que satisface la restricción de la ecuación (15). Esto significa que tenemos, cuando lo combinamos con nuestra definición de Ext, que

Demostrando así que nuestro protocolo es un protocolo de prueba de conocimiento.

Conocimiento cero computacional Honest-Verifier con Quantum Simulator . Sea Π.Sim el simulador cuántico computacional de conocimiento cero y verificador honesto para Π. Definimos Sim con acceso de Oracle a Π.Sim de la siguiente manera:

Entrada: x, S.

(1) Calcular (α, β, γ) ← Π.Sim(1λ, x)

(2) Muestra s de S.

(3) Salida ((x, α, s), β, γ).

Sea un polinomio p(·), un circuito cuántico de tamaño polinómico D, λ ∈ N, y ((x, S), w) ∈ R tales que

Definimos una reducción a la propiedad de conocimiento cero de Π de la siguiente manera:

Reducción: a conocimiento cero de Π dado acceso del oráculo a D.

Cableado con: x, S.

(1) Recibir (real o simulado) (α, β, γ) del retador.

(2) Muestra s de S.

(3) Enviar ((x, α, s), β, γ) a D. Recibir b de D.

(4) Salida b.

Cuando el retador envía una prueba real (o simulada) para Π, la reducción genera una prueba que es idéntica a la prueba real (o simulada). Como tal, esta reducción preserva la ventaja distintiva de D. Esto llega a una contradicción con la propiedad de conocimiento cero de Π. Por lo tanto, nuestro protocolo debe ser de conocimiento cero.

Según la definición del honesto demostrador P.Com,

lo cual es una contradicción. De ahí que nuestro protocolo debe tener compromisos impredecibles.

Corolario 5.2. La heurística de Fiat-Shamir aplicada al protocolo sigma poscuántico definido en el Teorema 5.1 produce un NIZKPoK Π′ poscuántico clásico en la QROM (Definición 3.11).

Prueba . Esto se sigue del Teorema 5.1 y del Teorema 3.12.

5.2 Definiciones de no clonabilidad

Los NIZK no clonables en el modelo de oráculo aleatorio cuántico se definen de manera análoga al modelo CRS; repetimos estas definiciones en el modelo QRO para que estén completas a continuación.

Definición 5.3. (Seguridad no clonable para instancias difíciles). Una prueba (P,V) satisface la seguridad no clonable con respecto a un oráculo aleatorio cuántico O si para cada lenguaje L con la relación correspondiente RL, para cada familia de circuitos cuánticos de tamaño polinomial {Cλ}λ∈N, y para cada distribución dura {Xλ ,Wλ}λ∈N sobre RL, existe una función despreciable negl1 (·) tal que para cada λ ∈ N,

Definición 5.4 ((k−1)-to-k-NIZK extraíble no clonable en QROM). Sea el parámetro de seguridad λ ∈ N y la relación NP R con el lenguaje correspondiente L. Sea Π = (P,V) tal que P y V sean algoritmos cuánticos de tamaño poli(λ). Tenemos que para cualquier (x, ω) ∈ R, P recibe una instancia y un par de testigos (x, ω) como entrada y genera π, y V recibe una instancia x y una prueba π como entrada y genera un valor en {0, 1}.

Π es un protocolo NIZKPoK no interactivo (k − 1) a k no clonable para el lenguaje L con respecto a un oráculo aleatorio O si se cumple lo siguiente:

• Π es un protocolo NIZKPoK para el lenguaje L en el modelo de oráculo aleatorio cuántico (Definición 3.11).

• (k−1)-to-k-No clonable con extracción: existe un circuito cuántico de tamaño polinómico E asistido por un oráculo tal que para cada circuito cuántico de tamaño polinómico A, para cada tupla de k − 1 pares de instancia-testigo ( x1, ω1), . . . ,(xk−1, ωk−1) ∈ R, para cada x donde definimos

tal que existe un polinomio p(·) donde

entonces también existe un polinomio q (·) tal que

Al igual que en la sección anterior, tenemos el siguiente lema.

Lema 5.5. Sea Π = (Setup, P,V) un protocolo cuántico de conocimiento cero no interactivo 1 a 2 que no se puede clonar (Definición 5.4). Entonces, Π satisface la Definición 5.3.

Para una demostración del Lema 5.5, nos referimos al Apéndice A.

5.3 NIZK no clonable implica dinero cuántico de clave pública en QROM

Teorema 5.6. Sea O un oráculo aleatorio cuántico. Sea (X ,W) una distribución estricta sobre un lenguaje L ∈ NP. Sea Π = (P,V) un protocolo de conocimiento computacional cero, perfectamente completo, no interactivo, no clonable, 1 a 2 para L en el modelo QRO (Definición 5.4).

Entonces (P,V) implica un miniesquema de dinero cuántico de clave pública en el modelo QRO (Definición 3.15) como se describe en la Figura 4.

Prueba . Perfecta corrección . Esto se sigue directamente de la perfecta completitud de Π. Inforjabilidad. Sea p(·) un polinomio y A un adversario cuántico en tiempo polinómico tal que para un número infinito de λ ∈ N +,

Construimos una reducción que rompe la definición de no clonabilidad (Definición 5.3) que mostramos (en el Apéndice A) está implícita en nuestra definición (Definición 5.4). El retador, con acceso al oráculo aleatorio O, toma muestras de un par de instancia-testigo (x, w) ← (X,Y) y una prueba π ← PO(x, w). Luego, el retador envía (x, π) a la reducción, que también tiene acceso oráculo a O. La reducción luego establece |$i = π y s = x. La reducción envía (|$i, s) al adversario A quien regresa (|$0, s0, |$1, s1). Luego, la reducción analiza y establece πi = |$ii para i ∈ {0, 1}. La reducción luego envía π0 y π1 de regreso al retador.

5.4 Construcción y Análisis

Lema 5.7. Sean λ, k ∈ N y un miniesquema de dinero cuántico de clave pública ( NoteGen,Ver ). Sean los puntos q1, . . . , qk se dará con la siguiente estructura: un punto q contiene un número de serie s muestreado según NoteGen (1λ).

Los puntos q1, . . . , qk debe ser distinto con una probabilidad abrumadora.

Prueba . Cada punto contiene un número de serie muestreado según el algoritmo de generación de dinero cuántico, NoteGen (1λ). Debido a la imprevisibilidad de los números de serie del dinero cuántico (Definición 3.13), todos los k números de serie generados honestamente deben ser distintos con una probabilidad abrumadora. Por lo tanto, estos k puntos serán distintos con una probabilidad abrumadora.

Ahora presentamos nuestra construcción en la Figura 5 y demostramos el teorema principal de esta sección.

Teorema 5.8. Sea k(·) un polinomio. Sea la relación NP R con el lenguaje correspondiente L.

Sea ( NoteGen, Ver ) un miniesquema de dinero cuántico de clave pública (Definición 3.13) y Π = (P,V) un protocolo sigma post-cuántico (Definición 3.4).

(P,V) como se define en la Figura 5 será un sonido de conocimiento no interactivo, conocimiento computacionalmente cero y (k − 1)-a-k-inclonable con protocolo de extracción para L en el modelo de oráculo aleatorio cuántico (Definición 3.11 ).

Prueba. Sean los parámetros y primitivas como se indican en el enunciado del teorema. Argumentamos que la integridad se deriva de la construcción del protocolo en la Figura 5, y probamos las propiedades restantes a continuación.

tenemos

Sean dados el circuito cuántico de tamaño polinomial A y x tales que

Definamos AF S con acceso de Oracle a algunos A y O de la siguiente manera:

Entrada: x, S.

(1) Dada una consulta (x, α, s) de A: envíe (x, α, s) a O, reciba β de O y envíe β a A.

(2) Al recibir π = (|$i, s, α, β, γ) de A: salida πF S = ((x, α, s), β, γ).

Por la estructura de nuestra prueba y definición de nuestro verificador, esto significa que

que satisface la restricción de la ecuación (16). Esto significa que tenemos, cuando se combina con nuestra definición de Ext y S, que

Demostrando así que nuestro protocolo es un protocolo de prueba de conocimiento.

Conocimiento Cero. Sea SimF S el simulador de Π′ en el Corolario 5.2 (donde Π ejemplifica el Teorema 5.1). Sea RF S la relación para Π′ con respecto a R. Definimos Sim con acceso de Oracle a SimF S y programamos el acceso a algún Oracle aleatorio O de la siguiente manera:

Entrada: x (ignora los testigos que pueda recibir).

Sea un distinguidor D asistido por Oracle que sólo puede realizar consultas (x, w) ∈ R, y un polinomio p(·) tal que

Definimos una reducción a la propiedad de conocimiento cero de Π′ de la siguiente manera:

Reducción: a conocimiento cero de Π′ dado acceso al oráculo a D y acceso al programa a O.

Para cada (x, w) de D:

La vista de D coincide con la de nuestro protocolo en la Figura 5 o Sim. Como tal, nuestra reducción debería tener la misma ventaja al romper la propiedad de conocimiento cero de Π′. Llegamos a una contradicción, de ahí que nuestro protocolo debe ser de conocimiento cero.

Capacidad de extracción no clonable. Sea Ext el circuito cuántico del extractor que definimos anteriormente (en nuestra prueba de que la Figura 5 es una prueba de conocimiento). Sea Sim el circuito cuántico del simulador que definimos anteriormente (en nuestra prueba de que la Figura 5 es un protocolo de conocimiento cero). Definimos un extractor E con acceso de Oracle a algún A de la siguiente manera:

Cableado con: alguna elección de I ⊆ [k − 1], J ⊆ [k], x1, . . . , xk−1 ∈ R, x.

(1) Muestras ℓ ∈ J uniformemente al azar.

(2) Crea una instancia de un oráculo aleatorio O simulable y extraíble. Ejecuta Ext en O durante toda la interacción con A (lo que puede implicar rebobinar, en cuyo caso rebobinaríamos A y repetiríamos los siguientes pasos). Requerir que Ext extraiga con respecto a la salida de prueba ℓ de A.

(3) Calcule πι ← Sim(xι) para ι ∈ [k − 1] donde almacenamos todos los puntos que Sim programaría en una lista P.

(4) Envíe {πι}ι∈[k−1] a A.

(5) Para cada consulta de A, si la consulta está en P, responda con la respuesta de P. De lo contrario, reenvíe la consulta a O y envíe la respuesta de regreso a A. Sea Ob el oráculo aleatorio modificado.

(7) Genera el resultado de Ext como w.

Dada la ecuación (24), podemos estar en uno de los dos casos siguientes: o A genera dos pruebas de aceptación que tienen el mismo número de serie que una prueba generada honestamente, o A no. Consideramos estos dos escenarios por separado y mostramos que cada uno llega a una contradicción.

Escenario uno

Digamos que A genera dos pruebas de aceptación que tienen el mismo número de serie que una prueba generada honestamente. Al aplicar una unión ligada a la Ecuación (24), tenemos que este evento podría ocurrir con al menos 1/2p(λ) de probabilidad. Simbólicamente,

Escenario dos

Alternativamente, digamos que A no genera dos pruebas de aceptación que tengan el mismo número de serie que una prueba generada honestamente. Según el principio del casillero, esto significa que A genera una prueba de aceptación con un número de serie que no se encuentra entre los que recibió. Al aplicar una unión ligada a la Ecuación (24), tenemos que este evento podría ocurrir con al menos 1/2p(λ) de probabilidad. En resumen, tenemos que

Mediante un argumento de promedio, podemos fijar el índice j ∈ J lo que nos da el mismo evento con una ventaja de 1/(2kp(λ)). Ahora cambiaremos a un híbrido en el que proporcionaremos a A pruebas simuladas en los índices I.

Reclamación 5.9. Existe un polinomio q (·) tal que

Más adelante veremos una prueba de la afirmación 5.9. Por ahora, suponiendo que esta afirmación sea cierta, podemos definir un adversario del cual Ext pueda extraer un testigo válido para x.

Reclamación 5.10. Existe un polinomio q ′ (·) tal que

Pronto veremos una prueba de la afirmación 5.10. Mientras tanto, si esta afirmación es cierta, entonces tendremos una contradicción directa con la ecuación (19). Por lo tanto, lo único que queda por probar son las dos afirmaciones: Reclamación 5.9 y Reclamación 5.10. Comenzamos demostrando la afirmación anterior.

Prueba de Reclamación 5.9. Primero debemos argumentar que nuestra estrategia está bien definida y que podremos programar estos k puntos de forma independiente. Entonces podemos argumentar la indistinguibilidad de cambiar una por una a pruebas simuladas. Argumentaremos que nuestro simulador se ejecutará en el tiempo polinómico esperado. Según el Lema 5.7, los k puntos que programará nuestro simulador serán distintos con una probabilidad abrumadora. Además, dado que asumimos que nuestro oráculo aleatorio cuántico se puede programar en múltiples puntos distintos, Definición 3.10, nuestro simulador está bien definido.

Ahora argumentamos la indistinguibilidad de las pruebas simuladas de las pruebas generadas honestamente mediante un argumento híbrido. Supongamos, en aras de la contradicción, que la diferencia de probabilidad entre la ecuación (21) y la ecuación (22) fuera 1/p′ (λ) para algún polinomio p ′ (·). Construimos una serie de híbridos consecutivos para cada i ∈ [k − 1] donde cambiamos la i-ésima prueba de demostrador generado a simulado. Según este argumento híbrido, debe haber alguna posición ℓ ∈ [k − 1] donde cambiar la ℓésima prueba tenga una diferencia de probabilidad de al menos 1/(kp′ (λ)). Formalizamos ahora una reducción que permite distinguir entre estos dos escenarios:

Primero argumentamos que la visión que la reducción proporciona a A coincide con uno de los juegos: donde todas las pruebas hasta el ℓ ésimo son simuladas o donde todas las pruebas hasta el ℓ ésimo inclusive son simuladas. Según el Lema 5.7, el punto calculado o programado por el retador será distinto de los puntos que programa la reducción. Como tal, se permite que la reducción modifique 5 el oráculo con el que A interactúa (ver paso (4)). En resumen, A tendrá acceso a un oráculo que sea consistente con todas las pruebas que reciba.

Dado que A tiene una vista que coincide directamente con la vista esperada en cualquier juego, entonces la ventaja de la reducción es la misma que la ventaja de A, que es al menos 1/(kp′ (λ)). Esto es una contradicción con la propiedad de conocimiento cero de nuestro protocolo. Por tanto, nuestra afirmación original debe ser cierta.

Ahora, continuamos demostrando esta última afirmación.

Prueba de Reclamación 5.10. Dado que la afirmación 5.9 es válida, esto implica que

Primero debemos argumentar que la visión de A sigue siendo idéntica al juego que aparece tanto en la Ecuación (24) como en la Ecuación (25). El oráculo con el que A interactúa (ver paso (4)) será consistente con todas las pruebas que reciba.

A través de la Ecuación (25), llegamos a la conclusión de que

Por la definición de una prueba de conocimiento (Definición 3.11) que tiene algunos parámetros polinomio p ∗ (·) y funciones insignificantes negl0 (·) y negl1 (·), tenemos que existe algún polinomio q ′ (·) tal que

lo que completa la prueba de nuestro reclamo.

Al completar las pruebas de nuestras afirmaciones, concluimos la prueba de nuestro enunciado de teorema.

Corolario 5.11. Suponiendo que existen funciones inyectivas unidireccionales y que existe iO post-cuántica, existe un sonido de conocimiento no interactivo, conocimiento computacionalmente cero y (k − 1) a kunclonable con protocolo de extracción para NP en el oráculo aleatorio cuántico. modelo (Definición 5.4).

Prueba. Esto se desprende del Teorema 3.14 y del Teorema 5.8.

Por lo tanto, hemos demostrado que la Figura 5 es un NIZK PoK que no se puede clonar en el modelo ROM tal como se define de acuerdo con nuestra definición de no clonabilidad, Definición 5.4.