📝
不思議な量子暗号：削除可能暗号
従来の暗号化方式の弱点
送信者が送りたい平文を暗号化して、安全でないネットワークを通じて受信者に送る。受信者は自身が持っている復号鍵を使って暗号文を復号する。現代暗号技術を使えば、盗聴者が暗号文を入手できても解読はできない。Amazonで買い物する時も、Lineで友達とチャットする時も、暗号通信のお陰で私たちの重要な個人情報は簡単に流出しない。しかしながら、従来の暗号には一つ重大な欠陥がある。
「一度送った暗号文はとり消しできない」
現代暗号学はこれまでは離散対数、平方剰余など数学の難問を使って、色々な暗号を設計している。しかし、これらの数学の難問を解くハードルはあくまで仮説に過ぎない。1970年代にナップサック問題を使って公開鍵暗号を設計する試みがあったが、80年代に入るとその暗号の解読法が判明した。現在広く使われているRSA暗号も、量子コンピュータの普及によって破られると懸念されている。
ここまで述べたように、技術の進歩で既存の暗号が安全ではないと判明されることはしばしばある。また、先ほど述べた通り、「一度送った暗号文はとり消しできない」。したがって、盗聴で入手した暗号文を保存して、解読技術が見つかったら解読を試みるという戦略が成立する。このズルい戦略によって過去の通信は危険に晒されている。
新たな暗号通信方式と挑戦
この難題を解決すべく、研究者は量子通信の力を借りて削除可能暗号（Cryptography with Certified Deletion ）という暗号通信の方式を提案した[1]。その通信の方式は従来の暗号通信といくつかの違いがある
- 平文の一部の情報を量子状態として送る
- 暗号文が復号される前に、受信者は量子状態に特別な測定をすることで、平文の情報を削除できる
- 特別な測定で受け取った量子状態から削除の証明書を生成できる。その証明書を送信者に送ることで、受け取った暗号文を削除したことを証明できる
鋭い読者ならすでに気づいたかもしれないが、削除可能暗号はあらかじめ復号鍵を相手に送ってはならない。もし復号用の鍵を持っていれば、受信者が削除を行う前に暗号文を復号し平文を入手できてしまう。ところが、鍵を後に送りつける方式は現在の暗号通信との相性が最悪と言ってもいい。
共通鍵をあらかじめ共有しない共通鍵暗号を想像してみてください。送信者が平文を暗号化して送って、その後受信者に復号の鍵を送る。暗号文を傍受できる盗聴者なら後に送った鍵も入手できる。暗号化は全く意味がない。
せっかく削除可能暗号を考案したのに、このままでは運用方法に困る。
削除可能暗号と相性が良い応用として目をつけられたのは、コミットメントだ（詳しくは と ）。コミットメントはコミット・フェーズ（commit phase）と公開フェーズ（reveal phase）に分けられる。コミット・フェーズに送信者は暗号化された1ビット を受信者に送り、公開フェーズでは の値を受信者に証明する。削除可能暗号の仕組みをコミット・フェーズに適用することで、公開フェーズに入る前に受信者はコミット・フェーズで受け取ったメッセージを削除できる。つまり、コミット・フェーズと公開フェーズの間でコミットメントのプロトコルを中止できる。
コミットメントを利用するプロトコルの中では、ゼロ知識証明が研究者の目を引いた。ゼロ知識証明の中では-プロトコル（詳しくは を参照）という種類のプロトコルが知られている。ここではNP完全問題のグラフ彩色問題を例として説明する。
入力：
- Proverが入力のグラフの各頂点の色に対し、コミットメントのコミット・フェーズを実行する。メッセージはVerifierに送るとする
- Verifierがグラフの辺を一つ選んで、辺の2つの頂点の色の「公開」をProverに要求する
- Proverはその２つの頂点の色に対し、コミットメントの公開フェーズを実行する。Verifierは選んだ2つの頂点の色が一致しない場合のみ受理する
このようにコミットメントのコミット・フェーズを利用し、証拠全体を暗号化したままVerifierに送って、Verifierがその証拠の一部の整合性をチェックする。これが-プロトコルの基本的な流れである。ここに削除可能暗号を適用することで、ステップ３に公開されていない部分の証拠を削除することができる。ステップ１にコミットした証拠がプロトコル終了後に解読される心配は、削除可能暗号によって解消された。
ゼロ知識証明は何の役に立つの？
ログインのためにパスワードを送りたいが、盗聴されてアカウントを不正アクセスされるのが怖い。電子契約に署名したいが、横流しされて知らない書類にサインさせられるのが心配。ブロックチェーン上の取引の整合性を証明したいが、内容を公開したくない。ここで書かれているシーンでは、ゼロ知識証明がピッタリである。また、ゼロ知識証明は現代暗号学の基本部品として、ここでは書ききれないほどのプロトコルに使われている。
量子通信で削除可能な暗号を実現
この節では削除可能暗号の実現方法について解説する。本題に入る前に量子情報の基礎を解説する。量子情報に詳しい読者はBB84状態と共役符号化（Conjugate Coding） まで読み飛ばしていただいて構わない。
量子ビット
量子情報処理にあたって、「データ」は量子レジスタに格納されている。量子レジスタに格納される「データ」は単位ベクトルで表されている。特に2次元のベクトルを格納する量子レジスタは量子ビットと呼ばれる。普通のビットと同じように量子ビットは と の状態が存在して次のようにベクトルと対応している。
図3のようにとはそれぞれx軸とy軸の方向を向いているため、それら合わせて計算基底と呼ばれることが多い。とはビットの0と1に見なしても大丈夫ですが、量子ビットは古典ビットでは表せない重ね合わせ状態も表せる。アダマール基底と呼ばれるとはその一例である。
測定
量子ビットから古典情報を取り出すには測定という操作が必要である。シュレディンガーのネコという有名な例え話の通り、量子ビットを観測すると量子ビットの状態は変わる。そして測定の結果はランダムに決まる。
一般的な解説では混乱を招くため、ここでは計算基底（基底）での測定を例にして説明する。量子状態 と への射影をそれぞれ と とする。このとき、測定結果 が出る確率は で、測定後の状態は となる。同様に測定結果 が出る確率は で、測定後の状態は となる。図4a.では を計算基底で測定した場合の測定結果を計算した。
アダマール基底での測定も同じように定義できる。ただし、量子状態から と への射影を考える。そして測定後の状態も と に置き換える。
BB84状態と共役符号化（Conjugate Coding）
量子暗号学では計算基底とアダマール基底を使って符号化する共役符号化がよく使われる。計算基底で1ビットの情報を符号化する場合は、 と でそれぞれ と を表す。同様に、アダマール基底では と でそれぞれ と を表す。
このルールを一般的な ビット列 に拡張すると次の手順が得られる
- ランダムに ビットの列 をとる
- に対して、（ の ビット目）を1ビットの時と同じく符号化する。ただし を符号化する基底は （ の ビット目）で決める。 が の場合は計算基底で、 の場合はアダマール基底で を符号化する
この手順で符号化した状態は量子鍵配送にも使われるため、これからはBB84状態と呼ぶ。そして符号化された と基底を表す を使って と書く。
削除可能暗号の構成
BB84状態の計算基底に一部の情報を隠して、アダマール基底に削除を確認するための証明書を隠すことで削除可能暗号を構成できる。以下ではセキュリティ・パラメータ を導入する。
送信者：入力
- をランダムにサンプリングする
- を で共役符号化したとき、計算基底で符号化された の部分のパリティを とする
- 受信者に暗号化された () とBB84状態 を送る
受信者（復号時）：
- () を復号して、 を入手する。
- 基底 で を測定し を入手し、 を計算する。
- と の xor をとる。ここで、 が成り立ち、送信者の入力 がわかる。
パリティとは
01列に出てくる1の数の偶奇性（偶 = 0, 奇 = 1）はパリティと言う。例えば、0110は２個の１を含むため、0110のパリティは0である。また、本稿では部分列のパリティを使う。これに関しても同様に、その部分列に出てくる1の数の偶奇性とする。
ここまでの暗号化と復号は従来の暗号とさほど変わらない。従来の暗号と違うのはプロトコルには暗号文を削除する手順も含まれることである。受信者が暗号文を復号する前にその手順を実行すれば、暗号文を削除した証明を手に入れられる。そして、送信者はその証明によって暗号文が削除されたことを確認できる。
削除の手順：
- 受信者がBB84状態 の全てのビットをアダマール基底で測定し、得られた測定結果 を送信者に送る
- 送信者が のビットの中のアダマール基底で符号化されている箇所と、の中のこれらの箇所のビットの値が一致しているかをチェックする。これらの箇所全てチェックを通った場合のみ、送信者は受信者が正しく削除を行ったと認める。
この削除という段階こそが従来の暗号との最大の違いである。ステップ2で送信者が削除を認めた後、例え無限の計算能力があろうとも の値を知ることはできない。
量子情報の特性で実現した削除
前節では削除可能暗号の実現、削除可能暗号が従来の暗号との安全性の違いについて説明した。しかし、なぜその安全性が成り立つのだろうか？例えば、削除してないのに削除したと言い張る受信者のウソを、送信者は見破ることができるのでしょうか。このプロトコルの安全性を形式的に証明するには、本稿はあまりにも短すぎる。ここではあくまでもイメージを掴むための説明をする。
削除を実現できたのは、測定する際に量子ビットに与える撹乱のおかげである。送信者に削除を認めてもらうために、受信者は のほぼ全ての量子ビットをアダマール基底で測定しなければならない。測定の影響で、計算基底で符号化されている量子ビットはそれぞれ 1/2 の確率で 、 になる。これによって元々計算基底で符号化されている情報は失われた。具体的には に関する情報がなくなったため、暗号文を解読しても を復元できない。
まとめ
本稿は導入に暗号通信を振り返り、暗号設計に使われる数学難問が解決されることを暗号通信の弱点とした。その後、この弱点を克服できる削除可能暗号という仕組みを紹介し、削除可能暗号の応用も紹介した。そして量子情報の基礎を一旦挟んで、削除可能暗号の実現方法について説明した。
参考文献
- Anne Broadbent and Rabib Islam. Quantum encryption with certified deletion. In Rafael Pass and Krzysztof Pietrzak, editors, Theory of Cryptography, pages 92–122, Cham, 2020. Springer International Publishing.
- James Bartusek, Dakshita Khurana, Cryptography with Certified Deletion, Cryptology ePrint Archive, Paper 2022/1178
- Taiga Hiroka, Tomoyuki Morimae, Ryo Nishimaki, and Takashi Yamakawa. Certified everlasting zero-knowledge proof for QMA. CRYPTO, 2022. https://ia.cr/2021/1315.