Une preuve de sécurité rigoureuse pour l'argent quantique de Wiesner?

50

Dans son célèbre article "Conjugate Coding" (écrit vers 1970), Stephen Wiesner a proposé un système de contrefaçon de la monnaie quantique sans condition, en supposant que la banque émettrice ait accès à un tableau géant de nombres aléatoires et que les billets de banque puissent être apportés. retour à la banque pour vérification. Dans le schéma de Wiesner, chaque billet de banque se compose d'un « numéro de série » classique , avec un état d'argent quantique | ψ s constitué de n enchevêtrées qubits, chacun d' eux soits|ψsn

|0, |1, |+=(|0+|1)/2, or |=(|0|1)/2.

La banque se souvient d'une description classique de pour chaque s . Et donc, quand | ψ s est ramené à la banque pour la vérification, la banque peut mesurer chaque qubit de | ψ s dans la base correcte (soit { | 0 , | 1 } ou | + , | - ), et vérifier qu'il obtient les résultats corrects.|ψss|ψs|ψs{|0,|1}|+,|

D'autre part, en raison de la relation d'incertitude (ou du théorème de non-clonage), il est "intuitivement évident" que, si un contrefacteur qui ne connaît pas les bases correctes tente de copier , alors la probabilité que les deux des états de sortie du contrefacteur passe le test de vérification de la banque peut être d' au plus c n , pour une constante c < 1 . De plus, cela devrait être vrai , peu importe quelle stratégie les utilisations contrefacteur, compatible avec la mécanique quantique (par exemple, même si l'utilisation de contrefacteur fantaisie empêtré sur les mesures | ψ s ).|ψscnc<1|ψs

Cependant, en écrivant un article sur d'autres systèmes de monnaie quantique, mon co-auteur et moi-même avons réalisé que nous n'avions jamais vu de preuve rigoureuse de cette affirmation, ni de limite supérieure explicite pour : ni dans l'article original de Wiesner ni dans un autre. .c

Ainsi, a une telle preuve (avec une limite supérieure ) été publiée? Si non, alors peut-on tirer une telle preuve de manière plus ou moins simple à partir de versions (approximatives) du théorème de non-clonage ou de résultats concernant la sécurité du schéma de distribution de clés quantiques BB84?c

Mise à jour: À la lumière de la discussion avec Joe Fitzsimons ci-dessous, je devrais préciser que je recherche plus qu'une réduction de la sécurité de BB84. Je cherche plutôt une limite supérieure explicite sur la probabilité de réussite de la contrefaçon (c'est-à-dire sur ) - et idéalement, une certaine compréhension de ce à quoi ressemble la stratégie optimale de contrefaçon. Par exemple, la stratégie optimale mesure-t-elle simplement chaque qubit de | ψ s indépendamment, par exemple dans la basec|ψs

{cos(π/8)|0+sin(π/8)|1,sin(π/8)|0cos(π/8)|1}?

Ou existe-t-il une stratégie de contrefaçon imbriquée qui donne de meilleurs résultats?

Mise à jour 2: À l’heure actuelle, les meilleures stratégies de contrefaçon que je connaisse sont (a) la stratégie ci-dessus et (b) la stratégie qui mesure simplement chaque qubit dans le base et « l' espoir pour le meilleur. » Il est intéressant de noter que ces deux stratégies aboutissent à une probabilité de réussite de (5/8) n . Donc, ma conjecture du moment est que (5/8) n pourrait être la bonne réponse. Dans tous les cas, le fait que 5/8 soit une valeur inférieure{|0,|1} bound on c exclut tout argument de sécurité pour le schéma de Wiesner qui soit "trop" simple (par exemple, tout argument selon lequel un contrefacteur ne peut rien faire de non négligeable, et la bonne réponse est donc c = 1/2).

Mise à jour 3: Non, la bonne réponse est (3/4) n ! Voir le fil de discussion ci-dessous la réponse d'Abel Molina.

Scott Aaronson
la source
3
Bienvenue sur TP.SE Scott! C'est bon de te voir ici.
Joe Fitzsimons
1
Il semble que le schéma de Wiesner corresponde exactement au BB84 où vous postez select sur Bob ayant choisi exactement les mêmes bases de mesure que celles d'Alice pour la préparation (puisque la banque est à la fois Alice et Bob). Clairement, la banque pourrait au lieu de cela choisir la base de mesure de manière aléatoire et simuler BB84, ce qui donnerait une sécurité strictement plus faible lié la sécurité du système de monnaie quantique. Peut-être que je manque quelque chose cependant.
Joe Fitzsimons
Merci pour l'accueil et la réponse, Joe! FWIW, je partage votre intuition selon laquelle une preuve de sécurité pour le schéma de Wiesner devrait être "strictement plus facile" qu'une preuve de sécurité pour BB84. Cependant, avec cet argument (comme avec tous les autres), je reviens toujours à la même question: "alors, quelle est la limite supérieure de c?"
Scott Aaronson
Sûrement, il est limité par la probabilité de déterminer la clé dans BB84.
Joe Fitzsimons
En outre, bien qu'il soit correct de déduire la sécurité du schéma de Wiesner de la sécurité de BB84 si c'est la seule / meilleure alternative, je garde l'espoir qu'il devrait y avoir une preuve plus directe et informative. De plus, il semble plausible qu'une preuve directe soit nécessaire pour obtenir une limite supérieure explicite sur c, ou pour obtenir une telle limite "raisonnable" (plus proche de 0,9 que de 0,99999).
Scott Aaronson

Réponses:

33

Il semble que cette interaction puisse être modélisée de la manière suivante:

  1. |000|101(|0+|1)|10/2(|0|1)|11/2
  2. Bob effectue un canal quantique arbitraire qui envoie son qubit à deux qubits, qui sont ensuite renvoyés à Alice.
  3. Alice effectue une mesure projective sur le qubit quatre en sa possession.

Si je ne me trompe pas à ce sujet (et désolé si je le suis), cela relève du formalisme de Gutoski et Watrous présenté ici et ici , ce qui implique que:

  1. Dans le second théorème 4.9, il est préférable que Bob agisse de manière indépendante lorsque Alice répète ce processus avec plusieurs qubits de manière indépendante, si l'objectif de Bob est de toujours tromper Alice.
  2. Il est possible d’obtenir la valeur de c à partir d’un petit programme semi-défini. Vous trouverez plus de détails sur l’obtention de ce programme à la section 3 ici . Voir les commentaires pour le code cvx du programme et sa valeur.
Abel Molina
la source
10
À la suite de la suggestion d'Abel, il apparaît que la valeur optimale est c = 3/4.
3
Je viens d'obtenir la même valeur de 3/4. Son pouvoir explicatif est faible, mais le code informatique est à cs.uwaterloo.ca/~amolinap/scriptWeisner.m et cs.uwaterloo.ca/~amolinap/prtrace.m .
Abel Molina
4
La stratégie est donnée par un canal quantique dont la représentation de Choi-Jamielkowski constitue une solution optimale au programme semi-défini. Voir cs.uwaterloo.ca/~amolinap/optSolution.txt pour un lien vers une telle solution (le qubit le moins significatif est celui reçu par Bob et les deux autres sont ceux qu'il envoie à Alice). Si mes calculs sont corrects, le canal correspondant envoie | 0> à (| 01> + | 10>) / √2 avec une probabilité de 1/6 et à (3 | 00> + | 11>) / √10 avec une probabilité de 5 / 6. | 1> est envoyé à (| 01> + | 10>) / √2 avec une probabilité de 1/6, et à (| 00> +3 | 11>) / √10 avec une probabilité de 5/6
Abel Molina
4
De même, (| 0> + | 1>) / √2 est envoyé à (| 11> - | 00>) / √2 avec une probabilité de 1/6 et à (| 00> +1/2 | 01> +1 / 2 | 10> + | 11>) / √ (5/2) avec probabilité de 5/6. De même, (| 0> - | 1>) / √2 est envoyé à (| 11> - | 00>) / √2 avec une probabilité de 1/6 et à (| 00> -1/2 | 01> -1 / 2 | 10> + | 11>) / √ (5/2) avec probabilité de 5/6.
Abel Molina
3
Puisque la réponse de @ AbelMolina a également été convertie en papier arXiv, arxiv.org/abs/1202.4010 , j’ajoute le lien pour les futurs lecteurs.
Frédéric Grosshans
19

α|0+β|1αβR

(12+18)2n.72855n
n(58)n

i=12AiρAi

A1=(12+18001801812180)    A2=(01218180180012+18).

i=12AiρAi

A1=112(30010110)    A2=112(01101003).

Celles-ci proviennent clairement de la même famille de transformations, mais ont été optimisées pour satisfaire différentes fonctions objectives. Cette famille de transformations covariantes semble être donnée par

A1=12x2+4y2(x+y00y0yxy0)    A2=12x2+4y2(0xyy0y00x+y).
Peter Shor
la source
Merci Peter! Il serait bon de montrer l'optimalité ou même presque l'optimalité de leur cloneur. Pour cela, je suppose que la première étape serait de montrer que l’attaque optimale est individuelle plutôt que collective.
Scott Aaronson
Si l'approche d'Abel Molina fonctionne, cela devrait le démontrer. Si ce n'est pas le cas, vous devriez pouvoir utiliser les techniques décrites dans les papiers de clonage optimaux pour obtenir une limite supérieure, mais je ne sais pas immédiatement ce que ce serait.
Peter Shor
(|0+i|1)/2(|0i|1)/2c=2/3x=y=1
x=y=1
16

Je ne connais pas de preuve de sécurité publiée. Je pense que le moyen le plus simple et le plus solide serait de ne pas cloner approximativement, mais je suppose que vous auriez besoin d’une version spécialisée pour les États BB84. Même une réduction par rapport à BB84 n’est pas évidente, car la condition de sécurité pour BB84 est différente.

Je pense que vous pouvez obtenir directement une preuve grâce à la preuve de sécurité du cryptage impossible à cloner ( quant-ph / 0210062 ). La probabilité de tricherie ne sera pas limitée au maximum, mais au moins, cela sécurisera.

ρk

Ceci peut être utilisé pour créer un schéma d’argent quantique: La banque A utilise un cryptage non clonable pour crypter une chaîne aléatoire appelée "message". Il existe un schéma de chiffrement inclinable qui est essentiellement BB84, ce qui pourrait donner le schéma de Weisner. Eve intercepte l'argent, interagit avec celui-ci et envoie l'original modifié à la banque B. Elle essaie également d'en faire une copie, qui est ensuite envoyée à la banque C. Les banques B et C acceptent si l'État qui leur est fourni passe le test d'écoute de chiffrement impossible à cloner. , et s’ils décodent la chaîne de "message" aléatoire correcte. La propriété de chiffrement non clonable b indique qu'avec une probabilité élevée, la copie de B échoue au test d'écoute électronique ou la copie de C ne contient presque aucune information sur le message. C'est plus fort que nécessaire, mais suffisant pour prouver la sécurité.

Pour quant à la meilleure attaque asymptotique, j'imagine, en raison de quantum de Finetti, que la meilleure attaque collective est la même que la meilleure attaque individuelle.


la source
Merci beaucoup, Daniel! Je continuerai à chercher un argument donnant une borne explicite sur c, mais entre-temps, c'est extrêmement utile. Je suis allé de l'avant et marqué votre réponse comme "accepté".
Scott Aaronson