量子デジタル署名

量子デジタル署名 (QDS)とは、従来のデジタル署名、またはより一般的には紙の文書に手書きされた署名の量子力学的同等物を指します。手書きの署名と同様に、デジタル署名は、デジタル契約などの文書を、別の当事者または参加当事者の 1 人による偽造から保護するために使用されます。

電子商取引が社会でより重要になるにつれ、交換される情報の出所を証明する必要性が生じています。現代のデジタル署名は、大きな数の因数を見つける（RSAアルゴリズムで使用される）などの数学的問題を解く難しさに基づいてセキュリティを強化します。残念ながら、これらの問題を解決するタスクは、量子コンピュータが利用可能になったときに実現可能になります（ショアのアルゴリズムを参照）。この新しい問題に対処するために、量子コンピュータを所有し、強力な量子不正戦略を使用する当事者による改ざんに対しても保護を提供する新しい量子デジタル署名スキームが開発されています。

公開鍵暗号方式では、送信者が署名鍵を使用してメッセージ（多くの場合、メッセージの暗号化ハッシュのみ）に署名し、対応する公開鍵を使用して受信者がメッセージの信頼性をチェックできるようにします。これを可能にするために、公開鍵はすべての潜在的な受信者に広く公開されます。メッセージの正当な作成者だけがメッセージに有効に署名できるようにするために、一方向関数を使用して、ランダムな秘密署名鍵から公開鍵が作成されます。これは、入力が与えられた場合に結果を計算するのは非常に簡単ですが、結果が与えられた場合に入力を計算するのは非常に困難になるように設計されています。典型的な例は、2つの非常に大きな素数の乗算です。乗算は簡単ですが、素数を知らずに積を因数分解することは通常、実行不可能と見なされます。

${\displaystyle x\mapsto f(x)}$ 簡単

${\displaystyle f(x)\mapsto x}$ 非常に難しい

従来のデジタル署名と同様に、量子デジタル署名は非対称鍵を使用します。したがって、メッセージに署名したい人は、署名とそれに対応する公開鍵のペアを 1 つ以上作成します。一般に、量子デジタル署名方式は次の 2 つのグループに分けられます。

1. 秘密の古典的なビット文字列から公開の量子ビット鍵を作成する方式: ${\displaystyle k\mapsto |f_{k}\rangle }$
2. 秘密の量子ビット文字列から公開の量子ビット鍵を作成する方式: ${\displaystyle |k\rangle \mapsto |f_{k}\rangle }$

どちらの場合も、f は古典的な一方向関数と同じ特性を持つ一方向量子関数です。つまり、結果は簡単に計算できますが、古典的なスキームとは対照的に、強力な量子不正戦略を使用しても関数を反転することは 不可能です。

上記の最初の方法の最も有名なスキームは、ゴッテスマンとチュアン^{[1]によって提供されています。}

従来のデジタル署名方式の要件のほとんどは、量子デジタル署名方式にも適用されます。

詳細

1. この制度は、次のような改ざんに対するセキュリティを提供する必要がある。
   1. メッセージが署名された後の送信者（ビットコミットメントを参照）
   2. 受信者
   3. 第三者
2. 署名付きメッセージの作成は簡単でなければならない
3. メッセージの有効性（有効、無効）をテストする場合、すべての受信者は同じ回答を受け取る必要があります。

^{[1] [2]}

上で述べたように、古典的な一方向性関数は古典的な実行不可能な数学的タスクに基づいていますが、量子の一方向性関数は不確定性原理を利用しており、量子コンピュータでさえ逆関数を計算することは不可能です。これは、入力文字列を再現するために十分な情報を得ることができない量子出力状態を提供することによって行われます。最初のグループのスキームの場合、これはホレボの定理によって示され、与えられたn量子ビットの量子状態からnビットを超える古典的情報を抽出できないことを示しています。^[3] スキームが特定の長さのビット文字列に対してより少ない量子ビットを使用することを保証する1つの可能性は、ほぼ直交する状態を使用することです。

${\displaystyle |\langle f_{k}|f_{k}'\rangle |<\delta \qquad {\text{ for }}k\neq k'\land 0\leq \delta \leq 1}$

これにより、2つ以上の状態を持つ基底を誘導することが可能になります。^[1] そのため、ビットの情報を表すには、n個未満の量子ビットを使用できます。3量子ビット基底の例 ${\displaystyle 2^{n}}$

• ${\displaystyle |0\rangle }$
• ${\displaystyle |1\rangle }$
• ${\displaystyle {\frac {1}{\sqrt {2}}}(|0\rangle +|1\rangle )}$

が成り立つ場合、n 個の古典ビットを記述するには m 個の量子ビットのみが必要です。 ${\displaystyle 3^{m}=2^{n}}$

Holevo の定理と、m が n よりはるかに小さいという事実により、n ビットのメッセージから取得できるのは m ビットだけです。より一般的には、公開鍵のコピーを T 個取得した場合、秘密鍵から最大 Tm ビットを抽出できます。が大きい場合、非常に大きくなり、不正な人が署名鍵を推測することは不可能になります。 ${\displaystyle \delta}$${\displaystyle n-Tm}$

注: 同一の状態が少量しかない場合、非直交状態を区別することはできません。これが量子一方向関数の仕組みです。
ただし、従来の公開鍵では秘密鍵に関する情報が漏洩し、秘密鍵に関する情報がまったくまたはすべて取得できないのに対し、量子一方向関数では秘密鍵に関する情報が漏洩します。${\displaystyle |f_{k}\rangle }$

古典的なケースでは、古典的な署名鍵から古典的な公開鍵を作成するため、公開鍵のコピーをすべての潜在的な受信者に提供するのは簡単です。公開鍵は自由に配布できます。これは量子の場合、状態自体が不明である限り、複製禁止定理によって量子状態のコピーが禁止されるため、より困難になります。^[4] そのため、公開鍵は、作成したい量子状態を正確に知っている人、つまり署名鍵を知っている人によってのみ作成および配布できます (送信者またはより一般的には信頼できる機関)。ただし、古典的な公開鍵とは対照的に、署名鍵を推測してスキームのセキュリティを危険にさらすことなく作成できる公開量子鍵Tの数には上限があります (大きくする必要があります)。 ${\displaystyle n-Tm}$

メッセージの真正性をテストする際に、すべての受信者が同一の結果を得ることを確実にするために、配布された公開鍵は同じでなければなりません。これは古典的なケースでは簡単です。なぜなら、2つの古典的なビット列を簡単に比較して、それらが一致するかどうかを確認することができるからです。しかし、量子状態ではより複雑です。2つの公開量子状態が同じかどうかをテストするには、次のものを比較する必要があります。

${\displaystyle |f_{k}'\rangle =|f_{k}\rangle }$

これは、1 つのフレドキン ゲート F、1 つのアダマール ゲート H 、および補助量子ビットaを使用する次の量子回路で行われます。まず、補助量子ビットが対称状態に設定されます。 ${\displaystyle |a\rangle ={\frac {1}{\sqrt {2}}}(|0\rangle +|1\rangle )}$

補助量子ビットがターゲットの制御およびFredkin Gate で 使用された直後。${\displaystyle |f_{k}\rangle \ }$${\displaystyle \ |f_{k}'\rangle }$

さらに、補助量子ビットにアダマールゲートを適用し、最終的に最初の量子ビットを測定します。両方の状態が同じであれば、結果が測定されます。両方の状態がほぼ直交している場合、結果はまたはのいずれかになります。^[1]${\displaystyle |0\rangle }$${\displaystyle |0\rangle \ }$${\displaystyle \ |1\rangle }$

スワップテストの計算の詳細:

全体的な状態

${\displaystyle |\psi _{0}\rangle =|a\rangle |f_{k}\rangle |f_{k}'\rangle }$

${\displaystyle |\psi _{0}\rangle ={\frac {1}{\sqrt {2}}}{\bigg (}|0\rangle +|1\rangle {\bigg )}|f_{k }\rangle |f_{k}'\rangle }$

${\displaystyle |\psi _{0}\rangle ={\frac {1}{\sqrt {2}}}{\bigg (}|0\rangle |f_{k}\rangle |f_{k}'\ラングル +|1\rangle |f_{k}\rangle |f_{k}'\rangle {\bigg )}}$

フレドキンゲートを適用した 後

${\displaystyle \Rightarrow {\frac {1}{\sqrt {2}}}{\bigg (}|0\rangle |f_{k}\rangle |f_{k}'\rangle +|1\rangle \mathbf {|f_{k}'\rangle |f_{k}\rangle } {\bigg )}}$

最初の量子ビットに アダマールゲートを適用した後

${\displaystyle \Rightarrow {\frac {1}{2}}{\bigg [}{\bigg (}|0\rangle +|1\rangle {\bigg )}|f_{k}\rangle |f_{k}'\rangle +{\bigg (}|0\rangle -|1\rangle {\bigg )}|f_{k}'\rangle |f_{k}\rangle {\bigg ]}}$

並べ替えた後${\displaystyle |0\rangle {\text{ and }}|1\rangle }$

${\displaystyle \Rightarrow |\psi \rangle ={\frac {1}{2}}{\bigg [}|0\rangle {\bigg (}|f_{k}\rangle |f_{k}'\rangle +|f_{k}'\rangle |f_{k}\rangle {\bigg )}+|1\rangle {\bigg (}|f_{k}\rangle |f_{k}'\rangle -|f_{k}'\rangle |f_{k}\rangle {\bigg )}{\bigg ]}}$

ここで、 の状態であれば となり、測定すると必ず 0 になるということが 簡単にわかります。${\displaystyle |f_{k}\rangle =|f_{k}'\rangle \ }$${\displaystyle \ |\psi \rangle =|0\rangle |f_{k}\rangle |f_{k}\rangle }$

人 A (アリス) が人 B (ボブ) にメッセージを送信するとします。ハッシュ アルゴリズムは考慮されないため、アリスはメッセージのすべてのビットに署名する必要があります。メッセージ ビットb 。 ${\displaystyle \in \{0,1\}}$

アリスはM組の秘密鍵を選択する${\displaystyle \{k_{0}^{i},k_{1}^{i}\}\quad 1\leq i\leq M}$

• b = 0 の場合、すべてのキーがメッセージ ビットの署名に使用されます。${\displaystyle k_{0}}$
• b = 1 の場合、すべてのキーがメッセージ ビットの署名に使用されます。${\displaystyle k_{1}}$

マッピングする関数はすべての関係者に知られています。アリスは対応する公開鍵を計算し、それらをすべて受信者に渡します。アリスは必要な数だけコピーを作成できますが、セキュリティを危険にさらさないように注意する必要があります。 ${\displaystyle k\mapsto |f_{k}\rangle }$${\displaystyle \{|f_{k_{0}}^{i}\rangle ,|f_{k_{1}}^{i}\rangle \}}$${\displaystyle \left(n\gg Tm{\text{ has to hold }}\right)}$

彼女のセキュリティレベルは、彼女が作成できる同一の公開鍵の数を制限する。

もし

• メッセージビットb = 0 の場合、彼女はすべての秘密鍵をメッセージビットbとともにボブに送信します。${\displaystyle k_{0}}$
• メッセージビットb = 1 の場合、彼女はすべての秘密鍵をメッセージビットbとともにボブに送信します。${\displaystyle k_{1}}$

覚えておいてください: この例では、アリスは1ビットbだけを選んで署名します。彼女はメッセージのすべてのビットに対してこれをしなければなりません。

ボブは今

• メッセージビットb
• 対応する秘密鍵${\displaystyle k_{0}{\text{ or }}k_{1}}$
• すべての公開鍵${\displaystyle \{|f_{k_{0}}\rangle ,|f_{k_{1}}\rangle \}}$

ここで、ボブは受信したすべての秘密鍵 ( ) について計算します。 ${\displaystyle |f_{k_{b}}\rangle }$${\displaystyle k_{0}{\text{ or }}k_{1}}$

その後、スワップ テストを使用して、計算された状態と受信した公開鍵を比較します。スワップ テストでは間違った答えが出る可能性もあるため、すべてのM 個の鍵に対してスワップ テストを実行し、間違った鍵がいくつ取得されるかを数えます。Mは、ある種のセキュリティ パラメーターであることは明らかです。Mが大きいほど、少し間違った検証が行われる可能性は低くなります。

• 間違ったキーが数個だけ取得された場合、計算されたキーと公開キーは同じであると思われるため、そのビットはおそらく有効です。
• 間違ったキーを何度も受け取った場合、誰かがメッセージを偽造した可能性が高くなります。

特にM が小さい場合に発生する問題の 1 つは、受信者ごとに測定される不正なキーの数が確率によって異なることです。したがって、1 つのしきい値のみを定義するだけでは不十分です。不正なキーの数rが定義されたしきい値に非常に近い場合、メッセージの検証が異なってしまうためです。

これを防ぐには、複数のしきい値を定義する必要があります。エラーの数はMに比例して増加するため、しきい値は次のように定義されます。

受け入れ ${\displaystyle T_{a}=c_{1}M}$

拒絶 ${\displaystyle T_{r}=c_{2}M}$

• 不正なキーの数rが以下であれば、ビットは高い確率で有効である。${\displaystyle T_{a}}$
• 不正なキーの数rが を超える場合、ビットが偽造されている確率は高い。${\displaystyle T_{r}}$
• 不正なキーの数rが両方のしきい値の間にある場合、受信者はビットを検証するときに別の受信者が同じ結果を受け取ったかどうかを確信できません。さらに、メッセージを正しく検証したかどうかも確信できません。

^[1]

ノイズのない完璧なチャネルを想定すると、ビットは転送によって変更されないため、比較された状態が同じであればスワップテストは常に合格するため、しきい値をゼロに設定できます。${\displaystyle T_{a}}$

メッセージ認証コード（MAC）は主にデータ発信元の認証を目的としていますが、信頼できる第三者が関与する特定の現実的なシナリオでは否認防止も提供できます。原理的には、同じアイデアを量子MACのフレームワークで活用できます。ただし、幅広いクラスの量子MACは、従来のMACに比べて何の利点も提供していないようです。^[5]

• ランポート署名- 1970 年代に発明され、量子コンピューティング攻撃に対しても安全であると考えられている実用的なデジタル署名方式。
• 量子暗号
• 量子指紋