Connaissance zéro non interactive non clonable dans le modèle Oracle quantique aléatoire

Tableau des liens

Résumé et introduction

Aperçu technique

Préliminaires

Connaissance nulle non interactive et non clonable dans le modèle CRS

NIZK non clonable dans le modèle Oracle Quantum Ramdon

Signatures de connaissances inclonables

Les références

5NIZK non clonable dans le modèle Oracle aléatoire quantique

5.1 Un protocole Sigma modifié

Nous commencerons par introduire un protocole sigma légèrement modifié. Dans les sections à venir, notre construction consistera à appliquer Fiat-Shamir à ce protocole modifié.

Preuve. Complétude parfaite Cela découle directement de la complétude parfaite de Π.

et tout x associé à λ ∈ N satisfaisant

nous avons

Nous définissons Ext 3 avec un accès oracle à Π.Ext et certains A comme suit :

Entrée : x, S.

(1) Étant donné (x, α, s) de AΠ : envoyez α à Π.Ext, recevez β de Π.Ext et envoyez β à AΠ.

(2) Dès réception de γ de AΠ : envoyer γ à Π.Ext.

(3) Afficher le résultat de Π.Ext sous la forme w.

Nous définissons l'ensemble de paramètres suivant : c = cΠ, p(·) = pΠ(·), negl0 (·) = negl0,Π(·) et negl1 (·) = negl1,Π(·).

Soit le circuit quantique de taille polynomiale A = (A 0, A 1) et (x, S) tel que

Nous définissons maintenant AΠ = (A0,Π, A1,Π) avec accès oracle à A. A0,Π est câblé avec S, prend l'entrée x, envoie (x, S) à A0, reçoit ((x, α, s ), |sti) de A0 et les sorties (α, |sti). A1,Π est câblé avec S, prend l'entrée (x, |sti, β), envoie ((x, S), |sti, β) à A1, reçoit γ de A1, produit γ. Par la structure de notre preuve et la définition de notre vérificateur, cela signifie que

qui satisfait la contrainte de l’équation (15). Cela signifie que nous avons, une fois combiné avec notre définition de Ext, que

Montrant ainsi que notre protocole est un protocole de preuve de connaissance.

Computational Honest-Verifier Zero-Knowledge avec Quantum Simulator . Soit Π.Sim le simulateur quantique informatique à connaissance nulle et vérificateur honnête pour Π. Nous définissons Sim avec accès oracle à Π.Sim comme suit :

Entrée : x, S.

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

(2) Échantillons de S.

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

Soit un polynôme p(·), un circuit quantique de taille polynomiale D, λ ∈ N, et ((x, S), w) ∈ R tels que

Nous définissons une réduction à la propriété de connaissance nulle de Π comme suit :

Réduction : à une connaissance nulle de Π étant donné l'accès oracle à D.

Câblé avec : x, S.

(1) Recevoir (réel ou simulé) (α, β, γ) du challenger.

(2) Échantillons de S.

(3) Envoyez ((x, α, s), β, γ) à D. Recevez b de D.

(4) Résultat b.

Lorsque le challenger envoie une preuve réelle (ou simulée) pour Π, la réduction génère une preuve identique à la preuve réelle (resp. simulée). En tant que telle, cette réduction préserve l’avantage distinctif de D . Cela atteint une contradiction avec la propriété de connaissance nulle de Π. Par conséquent, notre protocole doit être sans connaissance.

Selon la définition du prouveur honnête P.Com,

ce qui est une contradiction. Notre protocole doit donc comporter des engagements imprévisibles.

Corollaire 5.2. L'heuristique de Fiat-Shamir appliquée au protocole sigma post-quantique défini dans le théorème 5.1 donne un NIZKPoK Π' post-quantique classique dans le QROM (Définition 3.11).

Preuve . Cela fait suite au théorème 5.1 et au théorème 3.12.

5.2 Définitions d'impossibilité de clonage

Les NIZK non clonables dans le modèle oracle aléatoire quantique sont définis de manière analogue au modèle CRS – nous répétons ces définitions dans le modèle QRO pour être complet ci-dessous.

Définition 5.3. (Sécurité non clonable pour les instances dures). Une preuve (P, V) satisfait la sécurité non clonable par rapport à un oracle aléatoire quantique O si pour chaque langage L avec la relation correspondante RL, pour chaque famille de circuits quantiques de taille polynomiale {Cλ}λ∈N, et pour chaque distribution dure {Xλ ,Wλ}λ∈N sur RL, il existe une fonction négligeable negl1 (·) telle que pour tout λ ∈ N,

Définition 5.4 (NIZK extractible ((k−1)-to-k-Unclonable dans QROM). Soit le paramètre de sécurité λ ∈ N et la relation NP R avec le langage correspondant L. Soit Π = (P, V) tel que P et V soient des algorithmes quantiques de taille poly (λ). Nous avons que pour tout (x, ω) ∈ R, P reçoit une paire instance et témoin (x, ω) en entrée et en sortie π, et V reçoit une instance x et une preuve π en entrée et génère une valeur dans {0, 1}.

Π est un protocole NIZKPoK non interactif (k − 1) vers k non clonable pour le langage L par rapport à un oracle aléatoire O si les conditions suivantes sont remplies :

• Π est un protocole NIZKPoK pour le langage L dans le modèle d'oracle aléatoire quantique (Définition 3.11).

• (k−1)-to-k-Inclonable avec extraction : il existe un circuit quantique de taille polynomiale E assisté par oracle tel que pour chaque circuit quantique de taille polynomiale A, pour chaque tuple de k − 1 paires instance-témoin ( x1, ω1), . . . ,(xk−1, ωk−1) ∈ R, pour tout x où l'on définit

tel qu'il existe un polynôme p(·) où

alors il existe aussi un polynôme q (·) tel que

Semblable à la section précédente, nous avons le lemme suivant.

Lemme 5.5. Soit Π = (Setup, P,V) un protocole quantique à connaissance nulle non interactif 1 à 2 non clonable (Définition 5.4). Alors, Π satisfait à la définition 5.3.

Pour une preuve du lemme 5.5, nous nous référons à l’annexe A.

5.3 NIZK non clonable implique de l'argent quantique à clé publique dans QROM

Théorème 5.6. Soit O un oracle aléatoire quantique. Soit (X ,W) une distribution dure sur un langage L ∈ NP. Soit Π = (P, V) un protocole 1 à 2 non clonable, non interactif, parfaitement complet et à connaissance nulle pour L dans le modèle QRO (Définition 5.4).

Alors (P, V) implique un mini-schéma de monnaie quantique à clé publique dans le modèle QRO (Définition 3.15), comme décrit dans la Figure 4.

Preuve . Exactitude parfaite . Cela découle directement de la parfaite complétude de Π. Inforgeabilité. Soit p(·) un polynôme et A un adversaire en temps polynomial quantique tel que pour un nombre infini de λ ∈ N +,

Nous construisons une réduction qui brise la définition de l'inclonabilité (Définition 5.3) dont nous montrons (dans l'Annexe A) qu'elle est impliquée par notre définition (Définition 5.4). Le challenger, ayant accès à l'oracle aléatoire O, échantillonne une paire instance-témoin dur (x, w) ← (X ,Y) et une preuve π ← PO(x, w). Le challenger transmet ensuite (x, π) à la réduction, qui a également un accès oracle à O. La réduction définit alors |$i = π et s = x. La réduction envoie (|$i, s) à l'adversaire A qui renvoie (|$0, s0, |$1, s1). La réduction analyse et définit ensuite πi = |$ii pour i ∈ {0, 1}. La réduction renvoie ensuite π0 et π1 au challenger.

5.4 Construction et analyse

Lemme 5.7. Soit λ, k ∈ N et un mini-schéma de monnaie quantique à clé publique ( NoteGen,Ver ). Soit les points q1, . . . , qk avec la structure suivante soit donné : un point q contient un numéro d'ordre s échantillonné selon NoteGen (1λ ).

Les points q1, . . . , qk doit être distinct avec une probabilité écrasante.

Preuve . Chaque point contient un numéro de série échantillonné selon l'algorithme de génération de monnaie quantique, NoteGen (1λ ). En raison de l’imprévisibilité des numéros de série de la monnaie quantique (Définition 3.13), tous les k numéros de série générés honnêtement doivent être distincts avec une probabilité écrasante. Par conséquent, ces k points seront distincts avec une probabilité écrasante.

Nous introduisons maintenant notre construction sur la figure 5 et démontrons le théorème principal de cette section.

Théorème 5.8. Soit k(·) un polynôme. Soit la relation NP R avec le langage correspondant L.

Soit ( NoteGen, Ver ) un mini-schéma d'argent quantique à clé publique (Définition 3.13) et Π = (P,V) un protocole sigma post-quantique (Définition 3.4).

(P, V), tel que défini sur la figure 5, sera un son de connaissance non interactif, sans connaissance informatique et (k − 1)-en-k-inclonable avec protocole d'extraction pour L dans le modèle d'oracle aléatoire quantique (Définition 3.11). ).

Preuve. Soit les paramètres et les primitives tels que donnés dans l'énoncé du théorème. Nous soutenons que l’exhaustivité découle de la construction du protocole dans la figure 5, et nous prouvons les propriétés restantes ci-dessous.

nous avons

Soit le circuit quantique de taille polynomiale A et x tels que

Soit AF S défini avec un accès Oracle à certains A et O comme suit :

Entrée : x, S.

(1) Étant donné une requête (x, α, s) de A : envoyer (x, α, s) à O, recevoir β de O et envoyer β à A.

(2) Lors de la réception de π = (|$i, s, α, β, γ) de A : sortie πF S = ((x, α, s), β, γ).

Par la structure de notre preuve et la définition de notre vérificateur, cela signifie que

qui satisfait la contrainte de l’équation (16). Cela signifie que nous avons, une fois combiné avec notre définition de Ext et S, que

Montrant ainsi que notre protocole est un protocole de preuve de connaissance.

Zéro Connaissance. Soit SimF S le simulateur de Π′ dans le corollaire 5.2 (où Π instancie le théorème 5.1). Soit RF S la relation pour Π ′ par rapport à R. Nous définissons Sim avec un accès oracle à SimF S et un accès programmatique à un oracle aléatoire O comme suit :

Entrée : x (ignore les témoins qu'il peut recevoir).

Soit un distinguateur assisté par oracle D qui ne peut effectuer que des requêtes (x, w) ∈ R, et un polynôme p(·) tel que

Nous définissons une réduction à la propriété de connaissance nulle de Π′ comme suit :

Réduction : à une connaissance nulle de Π ' étant donné l'accès oracle à D et l'accès programme à O.

Pour chaque (x, w) de D :

La vue de D correspond à celle de notre protocole dans la figure 5 ou Sim. En tant que telle, notre réduction devrait avoir le même avantage pour briser la propriété de connaissance nulle de Π′ . Nous atteignons une contradiction, notre protocole doit donc être sans connaissance.

Extractibilité non clonable. Soit Ext le circuit quantique de l'extracteur que nous avons défini précédemment (dans notre preuve que la figure 5 est une preuve de connaissance). Soit Sim le circuit quantique du simulateur que nous avons défini précédemment (dans notre preuve que la figure 5 est un protocole à connaissance nulle). Nous définissons un extracteur E avec accès oracle à certains A comme suit :

Câblé avec : un choix de I ⊆ [k − 1], J ⊆ [k], x1, . . . , xk−1 ∈ R, x.

(1) Échantillons ℓ ∈ J uniformément au hasard.

(2) Instancie un oracle aléatoire O simulable et extractible. Exécute Ext sur O tout au long de l'interaction avec A (ce qui peut impliquer un rembobinage, auquel cas nous rembobinerions A et répéterions les étapes suivantes). Exiger que Ext extrait par rapport à la ℓième preuve sortie par A.

(3) Calculer πι ← Sim(xι) pour ι ∈ [k − 1] où nous stockons tous les points que Sim programmerait dans une liste P.

(4) Envoyez {πι}ι∈[k−1] à A.

(5) Pour chaque requête de A, si la requête est dans P, répondez avec la réponse de P. Sinon, transmettez la requête à O et renvoyez la réponse à A. Laissez Ob désigner cet oracle aléatoire modifié.

(7) Affiche le résultat de Ext sous la forme w.

Étant donné l’équation (24), nous pouvons nous trouver dans l’un des deux cas suivants : soit A génère deux preuves acceptantes qui ont le même numéro de série qu’une preuve générée honnêtement, soit A ne le fait pas. Nous considérons ces deux scénarios séparément et montrons que chacun aboutit à une contradiction.

Scénario un

Supposons que A génère deux preuves d'acceptation qui ont le même numéro de série qu'une preuve générée honnêtement. En appliquant une union liée à l’équation (24), nous avons que cet événement pourrait se produire avec une probabilité d’au moins 1/2p(λ). Symboliquement,

Scénario deux

Alternativement, disons que A ne génère pas deux preuves d'acceptation qui ont le même numéro de série qu'une preuve générée honnêtement. Par le principe du casier, cela signifie que A génère une épreuve d'acceptation avec un numéro de série qui ne fait pas partie de ceux qu'il a reçus. En appliquant une union liée à l’équation (24), nous avons que cet événement pourrait se produire avec une probabilité d’au moins 1/2p(λ). En résumé, nous avons cela

Grâce à un argument de moyenne, nous pouvons fixer l'indice j ∈ J ce qui nous donne le même événement avec un avantage de 1/(2kp(λ)). Nous allons maintenant passer à un hybride où nous fournissons à A des preuves simulées aux indices I.

Réclamation 5.9. Il existe un polynôme q (·) tel que

Nous verrons plus tard une preuve de la revendication 5.9. Pour l’instant, en supposant que cette affirmation soit vraie, nous pouvons définir un adversaire dont Ext peut extraire un témoin valide pour x.

Réclamation 5.10. Il existe un polynôme q ′ (·) tel que

Nous verrons bientôt une preuve pour la revendication 5.10. En attendant, si cette affirmation est vraie, nous aurons alors une contradiction directe avec l’équation (19). Ainsi, tout ce qui reste à prouver sont les deux affirmations : la revendication 5.9 et la revendication 5.10. Nous commençons par prouver la première affirmation.

Preuve de réclamation 5.9. Nous devons d’abord argumenter que notre stratégie est bien définie, que nous serons capables de programmer indépendamment ces k points. Nous pouvons alors argumenter sur l’impossibilité de distinguer le passage une par une aux preuves simulées. Nous soutiendrons que notre simulateur fonctionnera en temps polynomial attendu. D'après le lemme 5.7, les k points que notre simulateur programmera seront distincts avec une probabilité écrasante. De plus, puisque nous avons supposé que notre oracle aléatoire quantique peut être programmé en plusieurs points distincts Définition 3.10, notre simulateur est bien défini.

Nous argumentons maintenant sur l’indiscernabilité des preuves simulées des preuves honnêtement générées via un argument hybride. Supposons, par souci de contradiction, que la différence de probabilité entre l'équation (21) et l'équation (22) soit de 1/p′ (λ) pour un polynôme p ′ (·). Nous construisons une série d'hybrides consécutifs pour chaque i ∈ [k − 1] où nous passons la i ème preuve du prouveur généré à la simulée. D'après cet argument hybride, il doit y avoir une position ℓ ∈ [k − 1] où le changement de la ℓ ème preuve a une différence de probabilité d'au moins 1/(kp′ (λ)). Nous formalisons maintenant une réduction qui permet de distinguer ces deux paramètres :

Nous soutenons d’abord que la vision que la réduction fournit à A correspond à l’un des jeux : où toutes les preuves jusqu’au ℓ ième sont simulées ou où toutes les preuves jusqu’au ℓ ième inclus sont simulées. D'après le lemme 5.7, le point calculé ou programmé par le challenger sera distinct des points que programme la réduction. En tant que telle, la réduction est autorisée à modifier 5 l'oracle avec lequel A s'interface (voir étape (4)). En résumé, A aura accès à un oracle cohérent avec toutes les preuves qu’il reçoit.

Étant donné que A a une vue qui correspond directement à sa vue attendue dans l'un ou l'autre jeu, alors l'avantage de la réduction est le même que l'avantage de A qui est d'au moins 1/(kp′ (λ)). C'est une contradiction avec la propriété de connaissance nulle de notre protocole. Ainsi, notre affirmation initiale doit être vraie.

Maintenant, nous continuons à prouver cette dernière affirmation.

Preuve de réclamation 5.10. Étant donné que la revendication 5.9 est vraie, cela implique que

Nous devons d'abord affirmer que la vision de A reste identique au jeu qui apparaît à la fois dans l'équation (24) et dans l'équation (25). L'oracle avec lequel A s'interface (voir étape (4)) sera cohérent avec toutes les preuves qu'il reçoit.

Grâce à l’équation (25), nous arrivons à la conclusion que

Par la définition d'une preuve de connaissance (Définition 3.11) qui a des paramètres polynômes p ∗ (·) et des fonctions négligeables negl0 (·) et negl1 (·), on a qu'il existe un polynôme q ′ (·) tel que

ce qui complète la preuve de notre affirmation.

En complétant les preuves de nos affirmations, nous concluons la preuve de notre énoncé de théorème.

Corollaire 5.11. En supposant que les fonctions injectives unidirectionnelles existent et que l'iO post-quantique existe, il existe un son de connaissances non interactif, une connaissance nulle par calcul et (k - 1) -à-kunclonable avec un protocole d'extraction pour NP dans l'oracle aléatoire quantique modèle (Définition 5.4).

Preuve. Cela découle du théorème 3.14 et du théorème 5.8.

Nous avons ainsi montré que la figure 5 est un NIZK PoK non clonable dans le modèle ROM tel que défini selon notre définition d'unclonabilité, définition 5.4.