Este documento está disponible en arxiv bajo licencia CC 4.0.   Autores:  (1) Ruta Jawale;  (2) Dakshita Khurana.  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.       Esto se deriva directamente de la completitud perfecta de Π.  Prueba. Completitud perfecta  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.    Dado (x, α, s) de AΠ: envíe α a Π.Ext, reciba β de Π.Ext y envíe β a AΠ. (1)    Al recibir γ de AΠ: enviar γ a Π.Ext. (2)    Genere el resultado de Π.Ext como w. (3)  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.    . 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: Conocimiento cero computacional Honest-Verifier con Quantum Simulator  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   Esto llega a una contradicción con la propiedad de conocimiento cero de Π. Por lo tanto, nuestro protocolo debe ser de conocimiento cero.  D.  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).    . Esto se sigue del Teorema 5.1 y del Teorema 3.12. Prueba  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.    (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.3.  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   (·) tal que  q  Al igual que en la sección anterior, tenemos el siguiente lema.    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. Lema 5.5.  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.    .   . 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 +,  Prueba Perfecta correcció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    Sean λ, k ∈ N y un miniesquema de dinero cuántico de clave pública (   ). Sean los puntos q1, . . . , qk se dará con la siguiente estructura: un punto q contiene un número de serie s muestreado según   (1λ). Lema 5.7. NoteGen,Ver NoteGen  Los puntos q1, . . . , qk debe ser distinto con una probabilidad abrumadora.    . Cada punto contiene un número de serie muestreado según el algoritmo de generación de dinero cuántico,   (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. Prueba NoteGen  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 ).    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.  Prueba.  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:    (ignora los testigos que pueda recibir).  Entrada: x  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.    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: Capacidad de extracción no clonable.  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.    Existe un polinomio   (·) tal que  Reclamación 5.9. q  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.    Existe un polinomio   ′ (·) tal que  Reclamación 5.10. q  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.   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. Primero debemos argumentar que nuestra estrategia está bien definida y que podremos  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.    5.10. Dado que la afirmación 5.9 es válida, esto implica que  Prueba de Reclamación  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.    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). Corolario 5.11.    Esto se desprende del Teorema 3.14 y del Teorema 5.8. Prueba.  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.

EScholar Technologies

EScholar

Este audio es producido en el idioma original de la historia!

Demasiado Largo; Para Leer

Download free Tech Leaders Productivity Report!

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

About Author

COMENTARIOS

ETIQUETAS

ESTE ARTÍCULO FUE PRESENTADO EN

Related Stories

Liberando el poder de la IA. Una revisión sistemática de técnicas de vanguardia: resumen e introducción

Creación de productos criptográficos centrados en el usuario: la importancia de los comentarios de los clientes

Aumente su productividad con estas 18 herramientas para desarrolladores 🚀🔥

Las capas invisibles: por qué las entrevistas con los usuarios son un activo irremplazable

Liberando el poder de la IA. Una revisión sistemática de técnicas de vanguardia: resumen e introducción

Creación de productos criptográficos centrados en el usuario: la importancia de los comentarios de los clientes

Aumente su productividad con estas 18 herramientas para desarrolladores 🚀🔥

Las capas invisibles: por qué las entrevistas con los usuarios son un activo irremplazable

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps