ノイズストレージモデル

ノイズストレージモデル[1]は、量子暗号 で用いられる暗号モデルを指します。プロトコルを破ろうとする攻撃者（敵対者）の量子メモリデバイスが不完全（ノイズが多い）であると仮定します。このモデルの主な目的は、ビットコミットメント、忘却転送、安全な識別といった 二者間暗号プリミティブの安全な実装を可能にすることです

動機

量子通信は、暗号鍵の配布において非常に有用であることが証明されています。遠く離れたアリスとボブという2人の当事者は、量子ビット（量子ビット）を互いに送信することで、小さな初期の秘密鍵を任意の長さの秘密鍵に拡張することができます。最も重要なのは、通信を盗聴しようとする盗聴者が、長い鍵に関する情報を傍受できないことが証明されていることです。これは量子鍵配布（QKD） として知られています

しかし、量子通信でさえ、他の多くの2者間暗号タスクの安全な実装は許可しないことが示されている。[2] [3] [4] [5]これらはすべて、安全な関数評価の例です。 一例として、忘却転送があります。 これらのタスクを鍵配布と区別する特徴は、お互いを信頼していないアリスとボブの2者間の問題を解決することを目的としていることです。 つまり、盗聴者のような外部の当事者は存在せず、アリスとボブだけが存在するということです。 直感的には、この信頼の欠如が問題を困難にしていると言えます。量子鍵配布とは異なり、アリスとボブは盗聴行為を検出するために協力することができません。 その代わりに、各当事者が自力で対処しなければなりません。

安全な識別のようなタスクは実用的な関心事であるため、敵対者の能力についてある程度の仮定を立てる必要がある。これらの仮定が満たされる限り、セキュリティは維持される。量子ツールを用いない古典暗号においては、これらのほとんどは計算上の仮定である。このような仮定は2つの要素から構成される。まず、特定の問題の解決が困難であると仮定する。例えば、大きな整数を素因数分解するのは難しいと仮定する（例：15=5x3）。次に、敵対者の計算能力は限られており、つまり、選択された問題を解くのに必要な（と考えられる）能力よりも低いと仮定する。

制限付きストレージ

情報理論的暗号学においては、いかなる困難性仮定にも依存せず、単に他の資源の限界を仮定する物理的仮定が登場する。古典暗号学において、ウエリ・マウラーによって導入された有限記憶モデルは、攻撃者が一定数の古典ビットしか記憶できないと仮定している。 [6] [7]攻撃者の記憶容量が小さい限り、あらゆる暗号タスクを（原理的には）安全に実装できるプロトコルが知られている。非常に直感的に言えば、この仮定の下では、攻撃者はどの情報を保持するかを選択しなければならないため、セキュリティが実現可能となる。つまり、プロトコルは事実上、攻撃者の記憶装置をオーバーフローさせ、攻撃者にとって必然的に情報不足をもたらす。後に、正当な当事者が実行するためにビットを記憶することを要求する古典プロトコルは、約ビット以上を記憶できる攻撃者によって破られることが発見された。[8]つまり、プロトコルの実行に必要なものとセキュリティを破るのに必要なものの差は比較的小さい。 n {\displaystyle n} O （ n 2 ） {\displaystyle O(n^{2})}

有限量子ストレージ

このギャップは、量子通信[9]を使用すると劇的に変化します 。つまり、アリスとボブはプロトコルの一部として互いに量子ビットを送信できます。同様に、敵対者の量子ストレージは特定の数の量子ビットに制限されていると仮定します。敵対者が保存できる古典ビットの数に制限はありません。これは有限量子ストレージモデルとして知られています。[9] [10]正直な当事者が実行するために量子ストレージを全く必要としない量子プロトコルが存在することが示されましたが、それでもアリスが敵対者が保存できる量子ビット数の2倍以上を送信する限り安全です

ノイズの出る保管場所

より一般的には、攻撃者が記憶装置に記憶できる情報量が限られている限り、セキュリティは可能である。この直感は、ノイジー記憶モデル[1]によって捉えられており、このモデルには、限定量子記憶モデルが特別なケースとして含まれている[11] 。このような制限は、例えば、記憶装置が非常に大きいが、非常に不完全な場合に生じる。情報理論では、このような不完全な記憶装置は、ノイジー通信路とも呼ばれる。このより一般的なモデルの目的は3つある。第1に、攻撃者が利用できる可能性のある、はるかに一般的な記憶装置について、ステートメントを生成できることである。第2に、送信される信号、または記憶装置自体が、次元が無限で、追加の制約なしに限定記憶仮定では捉えられないような連続変数を使用する場合でも、セキュリティのステートメントを生成できる。第3に、信号自体の次元が小さくても、ノイジー記憶解析によって、限定記憶自体がセキュリティのステートメントを生成できる領域を超えたセキュリティが実現できる。たとえば、ストレージ チャネルがエンタングルメント破壊である場合、ストレージ デバイスが任意の大きさであっても (つまり、まったく制限がない場合でも) セキュリティは実現可能です。

仮定

ノイズストレージモデルの仮定は、プロトコルに導入された待機時間の間、攻撃者はノイズのある記憶装置にのみ量子情報を保存できるというものです。[11]このような装置は、入力状態をノイズのある出力状態に変換する量子チャネルにすぎません。それ以外の場合、攻撃者は万能です。例えば、無制限の量の古典情報を保存し、あらゆる計算を瞬時に実行できます Δ t {\displaystyle \Delta t} F ： S （ H i n ） → S （ H お あなた t ） {\displaystyle {\mathcal {F}}:{\mathcal {S}}({\mathcal {H}}_{\rm {in}})\rightarrow {\mathcal {S}}({\mathcal {H}}_{\rm {out}})} ρ i n ∈ S （ H i n ） {\displaystyle \rho_{\rm{in}}\in{\mathcal{S}}({\mathcal{H}}_{\rm{in}})} ρ お あなた t ∈ S （ H お あなた t ） {\displaystyle \rho _{\rm {out}}\in {\mathcal {S}}({\mathcal {H}}_{\rm {out}})}

待機時間中はストレージデバイスを使用する必要があります。 Δ t {\displaystyle \Delta t}

後者の仮定は、たとえ計算的に非常に困難（つまり、長時間かかる）であっても、ノイズの多い記憶装置の使用前後で、あらゆる形式の誤り訂正符号化を実行できることも意味します。この文脈では、これは一般的に符号化攻撃および復号化攻撃と呼ばれます。攻撃者の古典的メモリは任意の大きさになる可能性があるため、符号化は記憶装置への入力として何らかの量子状態を生成するだけでなく、古典情報を出力する可能性もあります。攻撃者の復号化攻撃は、この追加の古典情報だけでなく、待機時間の経過後に攻撃者が得る可能性のある追加情報も利用できます。 E {\displaystyle {\mathcal {E}}} D {\displaystyle {\mathcal {D}}} E {\displaystyle {\mathcal {E}}} F {\displaystyle {\mathcal {F}}} D {\displaystyle {\mathcal {D}}}

実際には、メモリセルで構成されるストレージデバイスがしばしば検討されますが、各メモリセルはノイズの影響を受けます。情報理論的に言えば、これはデバイスが の形を持つことを意味します。ここで、は次元 のメモリセルに作用するノイズのある量子チャネルです。 N {\displaystyle N} F ＝ N ⊗ N {\displaystyle {\mathcal {F}}={\mathcal {N}}^{\otimes N}} N ： S （ C d ） → S （ C d ） {\displaystyle {\mathcal {N}}:S(\mathbb {C} ^{d})\rightarrow S(\mathbb {C} ^{d})} d {\displaystyle d}

例

  • ストレージデバイスは量子ビットで構成されており、各量子ビットは脱分極ノイズの影響を受けます。つまり、は2次元の脱分極チャネルです N {\displaystyle N} F ＝ N ⊗ N {\displaystyle {\mathcal {F}}={\mathcal {N}}^{\otimes N}} N （ ρ ） ＝ λ ρ + （ 1 − λ ） i d / 2 {\displaystyle {\mathcal {N}}(\rho )=\lambda \rho +(1-\lambda ){\mathsf {id}}/2}
  • ストレージデバイスは、ノイズのない量子ビットで構成されています。これは、境界付き量子ストレージの特殊なケースに対応します。つまり、であり、は恒等チャネルです。 N {\displaystyle N} F ＝ i d ⊗ N {\displaystyle {\mathcal {F}}={\mathsf {id}}^{\otimes N}} i d {\displaystyle {\mathsf {id}}}

プロトコル

ほとんどのプロトコルは2つのステップで進行します。まず、アリスとボブは2つまたは3つの相互に偏りのない基数で符号化された量子ビットを交換します。これは、量子鍵配送のBB84プロトコルまたは6状態プロトコルで使用されるものと同じ符号化です。通常、これはアリスがそのような量子ビットをボブに送信し、ボブは到着後すぐにそれらを測定するという形をとります。これには、アリスとボブがプロトコルを実行するために量子ストレージを必要としないという利点があります。さらに、そのような量子ビットを作成することは実験的に比較的容易であるため、現在利用可能な技術を使用してそのようなプロトコルを実装することが可能です。[12] n {\displaystyle n}

2番目のステップは、ステップ1で得られた測定データに対して従来の後処理を実行することです。使用される手法はプロトコルによって異なり、プライバシー増幅、誤り訂正符号、最小エントロピーサンプリング、インタラクティブハッシュなどが含まれます。

一般

すべての二者間暗号タスクが安全に実装できることを示すための一般的なアプローチは、安全な関数評価のために普遍的であることが知られている単純な暗号プリミティブを実装できることを示すことです。つまり、そのような暗号プリミティブのプロトコルを構築できれば、他のすべてのタスクは、このプリミティブを基本的な構成要素として使用して実装できます。そのようなプリミティブの1つが忘却転送です。そして、忘却転送は、弱い文字列消去と呼ばれるさらに単純な構成要素と、 プライバシー増幅などの暗号技術を組み合わせて構築できます

これまでに提案されたすべてのプロトコルは、当事者の一方（アリス）が、たとえ無制限の量のノイズフリー量子メモリを持つことを許容しています。つまり、ノイズストレージ仮定は当事者の一方（ボブ）にのみ適用されます。形式のストレージデバイスでは、以下の条件のいずれかが満たされる場合、2者間暗号タスクは、弱い文字列消去と忘却転送によって安全に実装できることが知られています。 F ＝ N ⊗ N {\displaystyle {\mathcal {F}}={\mathcal {N}}^{\otimes N}}

  • 有限量子ストレージ（すなわち、 ）の場合、アリスがBB84でエンコードされた量子ビット を送信するプロトコルを用いることでセキュリティを実現できます。[11]つまり、アリスがボブが保存できる量子ビット数の2倍以上を送信した場合にセキュリティを実現できます。また、ボブの視点から見ると、ボブがアリスが送信した量子ビットの半分未満、すなわち を保存できる場合にセキュリティを実現できると言えます。 N ＝ i d {\displaystyle {\mathcal {N}}={\mathsf {id}}} n > 2 N {\displaystyle n>2N} N < n / 2 {\displaystyle N<n/2}
  • 高次元メモリセル（すなわち、各セルは量子ビットではなく量子ディット）を使用する境界付き量子ストレージでは、アリスが可能な相互に偏りのない基数のいずれかをエンコードした高次元量子ディットを送信するプロトコルでセキュリティを実現できます。大きな次元の限界では、 のときはいつでもセキュリティを実現できます。つまり、ボブが送信信号の一定の割合を保存できる限り、セキュリティは常に実現できます。[13]不正なボブはアリスが送信したすべての量子ディットを保存できるため、これは検討中のプロトコルに最適です。BB84でエンコードされた量子ビットのみを使用して同じことが可能かどうかはわかっていません。 n {\displaystyle n} n ⪆ N {\displaystyle n\gtrapprox N} n ＝ N {\displaystyle n=N}
  • ノイズストレージと形式のデバイスでは、アリスがBB84エンコードされた量子ビットを送信するプロトコルを使用することでセキュリティを実現できます。 F ＝ N ⊗ N {\displaystyle {\mathcal {F}}={\mathcal {N}}^{\otimes N}} n {\displaystyle n}
  • n > 2 ⋅ N ⋅ C （ N ） {\displaystyle n>2\cdot N\cdot C({\mathcal {N}})} , [11]ここでは量子通信路の古典容量であり、いわゆる強逆性質に従う。[14]あるいは、 C （ N ） {\displaystyle C({\mathcal {N}})} N {\displaystyle {\mathcal {N}}} N {\displaystyle {\mathcal {N}}}
  • n > 2 ⋅ N ⋅ E C （ N ） {\displaystyle n>2\cdot N\cdot E_{C}({\mathcal {N}})} [ 15]ここで、は量子通信路のエンタングルメントコストである。これは一般に古典容量の条件よりもはるかに優れているが、 を評価するのはより困難である。 E C （ N ） {\displaystyle E_{C}({\mathcal {N}})} N {\displaystyle {\mathcal {N}}} E C （ N ） {\displaystyle E_{C}({\mathcal {N}})}
  • n > Q （ N ） N {\displaystyle n>Q({\mathcal {N}})N} , [16]ここでは の量子容量であり、 の強逆パラメータはそれほど小さくない。 Q {\displaystyle Q} N {\displaystyle {\mathcal {N}}} N {\displaystyle {\mathcal {N}}}

3つの相互にバイアスのない基底は、量子鍵配送の6状態プロトコルにおける符号化と同じである。最後の条件は、ほとんどの通信路において最もよく知られている条件であるが、量子容量と強い逆パラメータは一般に容易に決定できない。

特定のタスク

このような基本的なプリミティブを構成要素として使用することは、必ずしも暗号タスクを解決するための最も効率的な方法とは限りません。特定の問題を解決することを目的とした特殊なプロトコルの方が、一般的に効率的です。既知のプロトコルの例は以下のとおりです

  • ノイズ記憶モデルにおけるビットコミットメント[11] [13]および制限付き量子記憶の場合[10]
  • ノイズ記憶モデルにおける忘却転送[11]および境界付き量子記憶の場合[9] [10]
  • 境界付き量子記憶モデルにおける安全な識別[17] [18]

ノイズのある記憶とQKD

量子記憶の限界という仮定は、安全関数の評価の領域外にも適用されています。特に、量子鍵配送における盗聴者がメモリ限界を持っている場合、実験的な実装ではより高いビット誤り率を許容できることが示されています。 [10]

参照

参考文献

  1. ^ ab Wehner, S.; C. Schaffner; B. Terhal (2008). 「Cryptography from noisy-storage」. Physical Review Letters . 100 (22) 220502. arXiv : 0711.2895 . Bibcode :2008PhRvL.100v0502W. doi :10.1103/PhysRevLett.100.220502. PMID  18643410. S2CID  2974264
  2. ^ Lo, H.; H. Chau (1997). 「量子ビットコミットメントは本当に可能か？」. Physical Review Letters . 78 (17): 3410. arXiv : quant-ph/9603004 . Bibcode :1997PhRvL..78.3410L. doi :10.1103/PhysRevLett.78.3410. S2CID  3264257.
  3. ^ Lo, H (1997). 「量子秘密計算の安全性」. Physical Review A. 56 ( 2): 1154–1162 . arXiv : quant-ph/9611031 . Bibcode :1997PhRvA..56.1154L. doi :10.1103/PhysRevA.56.1154. S2CID  17813922.
  4. ^ Mayers, D. (1997). 「無条件に安全な量子ビットコミットメントは不可能」. Physical Review Letters . 78 (17): 3414––3417. arXiv : quant-ph/9605044 . Bibcode :1997PhRvL..78.3414M. doi :10.1103/PhysRevLett.78.3414. S2CID  14522232.
  5. ^ D'Ariano, G.; D. Kretschmann; D. Schlingemann; RF Werner (2007). 「量子ビットコミットメント再考：可能性と不可能」. Physical Review A. 76 ( 3) 032328. arXiv : quant-ph/0605224 . Bibcode :2007PhRvA..76c2328D. doi :10.1103/PhysRevA.76.032328. S2CID  119340261.
  6. ^ Maurer, U. (1992). 「条件付き完全秘密性と証明可能安全なランダム化暗号」. Journal of Cryptology . 5 (1): 53– 66. doi : 10.1007/bf00191321 . S2CID  12079602.
  7. ^ Cachin, Christian; Maurer, Ueli (1997). 「メモリ制限のある敵対者に対する無条件セキュリティ」. Advances in Cryptology — CRYPTO '97 . Lecture Notes in Computer Science. Vol. 1294. pp.  292– 306. doi :10.1007/BFb0052243. ISBN  978-3-540-63384-6。
  8. ^ Dziembowski, Stefan; Maurer, Ueli (2004). 「限定記憶域モデルにおける初期鍵の生成について」.暗号学の進歩 - EUROCRYPT 2004.コンピュータサイエンス講義ノート. 第3027巻. pp.  126– 137. doi :10.1007/978-3-540-24676-3_8. ISBN  978-3-540-21935-4。
  9. ^ abc I., Damgaard; S. Fehr; L. Salvail; C. Schaffner (2005). 「有界量子ストレージモデルにおける暗号化」.第46回IEEEコンピュータサイエンス基礎シンポジウム (FOCS'05) . pp.  449– 458. arXiv : quant-ph/0508222 . Bibcode :2005quant.ph..8222D. doi :10.1109/SFCS.2005.30. ISBN  978-0-7695-2468-9. S2CID  174322.
  10. ^ abcd Damgaard, I.; S. Fehr; R. Renner; L. Salvail; C. Schaffner (2007). 「高次エントロピー量子不確定性に関する緊密な関係とその応用」.暗号学の進歩 - CRYPTO 2007.コンピュータサイエンス講義ノート. 第4622巻. pp. 360–378. arXiv : quant-ph/0612014 . Bibcode :2006quant.ph.12014D. doi :10.1007/978-3-540-74143-5_20. ISBN  978-3-540-74142-8. S2CID  2557603.
  11. ^ abcdef ケーニッヒ、ロバート、S. ウェナー、J. ウルシュレガー (2009). 「ノイズのある量子ストレージからの無条件セキュリティ」. IEEE Transactions on Information Theory . 58 (3): 1962– 1984. arXiv : 0906.1030 . Bibcode :2009arXiv0906.1030K. doi :10.1109/TIT.2011.2177772. S2CID  12500084
  12. ^ Wehner, S.; M. Curty; C. Schaffner; H. Lo (2010). 「ノイズストレージモデルにおける2者間プロトコルの実装」. Physical Review A. 81 ( 5) 052336. arXiv : 0911.2302 . Bibcode :2010PhRvA..81e2336W. doi :10.1103/PhysRevA.81.052336. S2CID  6187112.
  13. ^ ab Mandayam, P.; S. Wehner (2011). 「境界貯蔵モデルの物理的限界の達成」. Physical Review A. 83 ( 2) 022329. arXiv : 1009.1596 . Bibcode :2011PhRvA..83b2329M. doi :10.1103/PhysRevA.83.022329. S2CID  11753298.
  14. ^ Koenig, R.; S. Wehner (2009). 「エンタングル入力を用いた古典チャネル符号化の強い逆元」. Physical Review Letters . 103 (7) 070504. arXiv : 0903.2838 . Bibcode :2009PhRvL.103g0504K. doi :10.1103/PhysRevLett.103.070504. PMID:  19792627. S2CID  : 25002853.
  15. ^ Berta, M.; F. Brandao; M. Christandl; S. Wehner (2013). 「量子チャネルのエンタングルメントコスト」. IEEE Transactions on Information Theory . 59 (10): 6779– 6795. arXiv : 1108.5357 . Bibcode :2011arXiv1108.5357B. doi :10.1109/TIT.2013.2268533. S2CID  322613.
  16. ^ Berta, M.; O. Fawzi; S. Wehner (2014). 「量子から古典へのランダムネス抽出器」. IEEE Transactions on Information Theory . 60 (2): 1168– 1192. arXiv : 1111.2026 . Bibcode :2011arXiv1111.2026B. doi :10.1109/TIT.2013.2291780. S2CID  10018325.
  17. ^ Damgaard, I.; Fehr, S.; Salvail, L.; Schaffner, C. (2007). 「境界量子記憶モデルにおける安全な識別とQKD」. Advances in Cryptology - CRYPTO 2007. Lecture Notes in Computer Science. Vol. 4622. pp.  342– 359. arXiv : 0708.2557 . doi :10.1007/978-3-540-74143-5_19. ISBN  978-3-540-74142-8. S2CID  97510
  18. ^ Damgaard, Ivan; Fehr, Serge; Salvail, Louis; Schaffner, Christian (2007). 「境界量子記憶モデルにおける安全な識別とQKD」arXiv : 1105.6212 [quant-ph]
「https://en.wikipedia.org/w/index.php?title=Noisy-storage_model&oldid=1322616642」より取得