Malleability of transformations on the ciphertext in noisy Quantum public key encryption

技術要約：ノイズが存在する量子公開鍵暗号における暗号文の可塑性（Malleability）について

問題提起
本論文は、ノイズが存在する状況下での量子公開鍵暗号（QPKE）および量子鍵配送（QKD）における「エバーラスティング・セキュリティ（永久的な安全性）」を厳密に定式化するという課題に取り組んでいる。MalavoltaとWalter [3] による先行研究では、無ノイズの設定におけるエバーラスティング・セキュリティの枠組みを確立しており、アリスとボブの間の2往復の相互作用のみでセキュリティが達成されることを示した。これに対し、本研究は、ノイズの導入がプロトコルのセキュリティ閾値にどのように影響するかを調査している。具体的には、暗号操作にノイズが注入された際の、暗号文変換の可塑性とプロトコルのセキュリティとの関係を探求している。核心となる問題は、平文および暗号文の変換の可塑性に関する仮定を用いて、理想的な無ノイズの場合から、ノイズが存在する設定へと無視関数（アドバーサリの優位性を定量化するもの）を一般化することである。

手法
著者らは、ノイズが存在するQPKE-QKDプロトコルを分析するために、量子情報理論と抽象暗号論を組み合わせた手法を用いている。その手法は、以下の主要な構成要素によって構造化されている。

1. 可塑性によるノイズ注入： 著者らは、MaurerとTackmann [9] によって、「認証してから暗号化（authenticate then encrypt）」と「暗号化してから認証（encrypt then authenticate）」のプロトコルを比較するために導入された可塑性の概念を適応させている。著者らは、転送エラー（forwarding error）、消失エラー（deleting error）、再構成エラー（reconstruction error）という3つの誤差確率によって特徴付けられる、平文空間上のノイズを含む変換を定義している。これらのエラーは、ノイズが暗号文に与える影響をモデル化するために使用される。
2. トレース距離と穏やかな測定補題（Gentle Measurement Lemma, GML）： 中心的な技術的ツールは、量子情報理論における「穏やかな測定補題」[18] の適応である。著者らは、特定の演算子のトレースの下限に基づき、2つの量子状態（実実験と理想的な実験を表す）の間のトレース距離の上限を確立するためにこの補題を使用している。これにより、ノイズが存在する場合の無視関数の一般化が可能となる。
3. ノイズが存在する量子多項式時間（NQPT）マシン： 本論文は、ノイズが存在する設定を、ノイズが存在する量子多項式時間（NQPT）マシンおよびノイズが存在する完全正トレース保存（CPTP）写像を定義することで定式化している。これらのオブジェクトは、ノイズのない条件下でのアリス、ボブ、およびアドバーサリ（イヴ）の挙動を置き換えてモデル化するものである。
4. 射影演算子と状態分解： 分析には、標準的な射影演算子 $\Pi$ にノイズ項（例：$|\sigma + \text{noise}\rangle$）を組み込んだ、ノイズを含む射影演算子（$\tilde{\Pi}$）の構築が含まれる。著者らは、ノイズのない射影演算子とノイズを含む射影演算子、トレース演算、およびケット/ブラの状態の比率を比較することにより、トレース距離の上限を導出している。
5. リソース理論的アプローチ： 論文は [9] のリソース理論的枠組みを利用し、プロトコルによって構築されるリソースの不可識別性という観点から、セキュリティと可用性を定義している。これには、プロトコルの合成およびハイブリッド実験の不可識別性の分析が含まれる。

主な貢献

• ノイズが存在するエバーラスティング・セキュリティの定式化： 本論文は、ノイズが存在するQPKEプロトコルに対する「エバーラスティング・セキュリティ」を定義し（定義37）、ノイズを含むハイブリッド実験間のトレース距離が、ノイズを含むセキュリティパラメータ $\lambda'$ に依存する無視関数によって抑えられることを確立した。
• 無視関数の一般化： 著者らは、ノイズが存在する設定におけるトレース距離と、無視関数 $NEGL(\lambda')$ との関係を導出した。特定のノイズに関する仮定の下で、ノイズが存在する設定における無視関数が、無ノイズの場合よりも高いセキュリティ閾値に関連することを示している。
• GMLによるトレース距離の境界： 主要な技術的貢献は、穏やかな測定補題を用いたトレース距離の上限の導出である。著者らは以下を示す：
  $$Td(\tilde{Exp}, Exp) \lesssim \sqrt{NEGL(\lambda' - \lambda)}$$
  これは、ノイズを含む状態とノイズのない状態（$\tilde{\rho} - \tau$）を含む特定の演算子のトレースの下限を証明することによって達成される。
• 可塑性の仮定： 本研究は、プロトコルのセキュリティと、暗号文変換の可塑性を明示的に結びつけている。それは、ノイズを含む変換の転送、消失、および再構成のエラー確率が、無ノイズ（$\lambda$）とノイズを含む（$\lambda'$）プロトコルのセキュリティ閾値の差とどのように関連するかを定量化している。
• 計算実行時間のトレードオフ： 本論文は、ノイズが存在するプロトコルと無ノイズのプロトコルの計算実行時間（エンコーディング、デコーディング、および鍵生成）のトレードオフを分析している。もしノイズが存在するプロトコルの実行時間が大幅に大きい場合、セキュリティ閾値の差 $\lambda' - \lambda$ は、実行時間の差に関連する指数関数または多項式関数として特定の形でスケールすることを示唆している。

結果

• 主要定理： 本論文は、正当性条件を満たすノイズが存在するQPKE-QKDプロトコルにおいて、ノイズを含むハイブリッド実験（ビット0および1で初期化されたもの）の間のトレース距離が、ノイズを含むセキュリティパラメータの無視関数によって抑えられることを証明している：
  $$Td(\tilde{Exp}_{A_{\lambda'}}(1^{\lambda'}, 1), \tilde{Exp}_{A_{\lambda'}}(1^{\lambda'}, 0)) \lesssim NEGL(\lambda')$$
• 優位関数に関する系： 著者らは、異なるハイブリッド実験（$\tilde{Adv}(0), \tilde{Adv}(1), \tilde{Adv}(2)$）に対するノイズを含む優位関数がすべて同じ無視関数 $NEGL(\lambda')$ によって抑えられることを示し、異なる実験設定間でのセキュリティ定義の一貫性を確認している。
• トレースの下限： 本論文は、ノイズを含む状態とノイズのない状態の差を含む特定の演算子のトレースが、無視関数の逆数の定数によって下から抑えられるという詳細な導出を提供しており、これが穏やかな測定補題を適用するための前提条件となっている。

意義と主張
本論文は、ノイズが存在する量子公開鍵暗号に対してエバーラスティング・セキュリティの概念を拡張するための、厳密な数学的枠組みを提供することを目的としている。穏やかな測定補題を適応させることで、著者らは、暗号文変換の可塑性に関する仮定を通じてノイズが特徴付けられる限り、無ノイズプロトコルのセキュリティ保証をノイズが存在する設定へと一般化できることを示している。

著者らは、ノイズの導入が一般に（パラメータ $\lambda'$ の観点から）より高いセキュリティ閾値をもたらす（つまり、より弱いセキュリティ保証を意味する）ものの、導出された境界値によって、ノイズを含むプロトコルと無ノイズのプロトコルとの定量的な比較が可能であることを強調している。本研究は理論的な足掛かりとして提示されており、無条件の安全性およびエバーラスティング・セキュリティの要件を実験的に実現することは困難であるが、提案された枠組みは、暗号学的文脈におけるノイズを含む量子計算の限界を分析するための価値ある出発点を提供すると述べている。結論として、トレース距離を抑えるために導出された計算は、ゲーム理論的なアプローチを中心とした設定においてもさらに検討できる可能性があると示唆しているが、具体的な実験的実装や、理論的分析以外の直接的な応用については提案していない。