Cet article est disponible sur arxiv sous licence CC 4.0.   Auteurs:  (1) Ruta Jawale ;  (2) Dakshita Khurana.  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é.       Cela découle directement de la complétude parfaite de Π.  Preuve. Complétude parfaite  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.    Étant donné (x, α, s) de AΠ : envoyez α à Π.Ext, recevez β de Π.Ext et envoyez β à AΠ. (1)    Dès réception de γ de AΠ : envoyer γ à Π.Ext. (2)    Afficher le résultat de Π.Ext sous la forme w. (3)  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.    . 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 : Computational Honest-Verifier Zero-Knowledge avec Quantum Simulator  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   . Cela atteint une contradiction avec la propriété de connaissance nulle de Π. Par conséquent, notre protocole doit être sans connaissance.  D  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).    . Cela fait suite au théorème 5.1 et au théorème 3.12. Preuve  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.    (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.3.  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   (·) tel que  q  Semblable à la section précédente, nous avons le lemme suivant.    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. Lemme 5.5.  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.    .   . 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 +,  Preuve Exactitude parfaite  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    Soit λ, k ∈ N et un mini-schéma de monnaie quantique à clé publique (   ). Soit les points q1, . . . , qk avec la structure suivante soit donné : un point q contient un numéro d'ordre s échantillonné selon   (1λ ). Lemme 5.7. NoteGen,Ver NoteGen  Les points q1, . . . , qk doit être distinct avec une probabilité écrasante.    . Chaque point contient un numéro de série échantillonné selon l'algorithme de génération de monnaie quantique,   (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. Preuve NoteGen  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). ).    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.  Preuve.  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 :    (ignore les témoins qu'il peut recevoir).  Entrée : x  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.    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 : Extractibilité non clonable.  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.    Il existe un polynôme   (·) tel que  Réclamation 5.9. q  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.    Il existe un polynôme   ′ (·) tel que  Réclamation 5.10. q  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.   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 devons d’abord argumenter que notre stratégie est bien définie, que nous serons capables de  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.    5.10. Étant donné que la revendication 5.9 est vraie, cela implique que  Preuve de réclamation  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.    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). Corollaire 5.11.    Cela découle du théorème 3.14 et du théorème 5.8. Preuve.  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.

EScholar Technologies

EScholar

Cet audio est produit dans la langue originale de l'histoire !

Trop long; Pour lire

CTA: Download the FREE AI Productivity Shift report

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

About Author

COMMENTAIRES

ÉTIQUETTES

CET ARTICLE A ÉTÉ PARU DANS

Related Stories

Croissance des crypto-monnaies : créer des profils d'utilisateurs efficaces

Guide de l'architecte pour créer une architecture de référence pour un datalake IA/ML

Libérer la puissance de l’IA. Une revue systématique des techniques de pointe : résumé et introduction

Appuyez pour gagner : Telegram pourrait intégrer les 10 prochains milliards d'utilisateurs de crypto avant Solana

Croissance des crypto-monnaies : créer des profils d'utilisateurs efficaces

Guide de l'architecte pour créer une architecture de référence pour un datalake IA/ML

Libérer la puissance de l’IA. Une revue systématique des techniques de pointe : résumé et introduction

Appuyez pour gagner : Telegram pourrait intégrer les 10 prochains milliards d'utilisateurs de crypto avant Solana

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps