(57)【要約】【課題】再認証が不可能であり、公開鍵を頒布する人数に上限がない量子電子署名システム及びその処理方法を提供する。【解決手段】署名者装置が、少なくとも１つのキュービットからなる量子状態をランダムに生成して、公開する。上記署名の対象となるビットごとに、そのビットの値に応じて、上記量子状態と同一の量子状態、又は、上記量子状態と直交する量子状態を生成して、検証者装置に文書と共に送信する。検証者装置が、受信した量子状態と、その量子状態に対応する公開された量子状態とをスワップテストにかけて、受諾されるか拒絶されるかを決定する。署名の対象となった各ビットごとに、上記スワップテストにおいて、そのビットを署名した量子状態が受諾又は拒絶された確率を求め、その確率がそのビットの値に応じて定まる一定の範囲内にある場合には、そのビットを受理又は不受理する。【選択図】図１
2008048102.tif 000002
【特許請求の範囲】
【請求項１】
送信文書を構成するビットのうちどのビットを署名の対象とするのか、及び、その署名の対象となるビットを公開鍵生成過程で生成された量子状態のうちどの量子状態で検証するのかが定められており、
複素乱数発生手段が、複素数の乱数を発生する複素乱数発生過程と、
公開鍵生成手段が、上記複素乱数発生過程で生成された乱数から、少なくとも１つのキュービットからなる量子状態をランダムに生成する上記公開鍵生成過程と、
公開鍵公開手段が、上記公開鍵生成過程で生成された量子状態を公開する公開鍵公開過程と、
署名生成手段が、上記署名の対象となるビットごとに、そのビットの値に応じて、上記公開鍵生成過程で生成された量子状態のうち上記そのビットを検証する量子状態と同一の量子状態、又は、上記公開鍵生成過程で生成された量子状態のうち上記そのビットを検証する量子状態と直交する量子状態を上記複素乱数発生過程で生成された乱数から生成する署名生成過程と、
署名送信手段が、送信文書に、上記署名生成過程で生成された量子状態を付加して送信する署名送信過程と、
公開鍵受信手段が、上記公開鍵公開過程で公開された量子状態を受信する公開鍵受信過程と、
署名受信手段が、上記署名送信過程で送信された送信文書と付加された量子状態を受信する署名受信過程と、
スワップテスト手段が、上記署名受信過程で受信した量子状態と、その量子状態に対応する、上記公開鍵受信過程で受信した量子状態とをスワップテストにかけて、受諾されるか拒絶されるかを決定するスワップテスト過程と、
第一判断手段が、署名の対象となった各ビットごとに、上記スワップテスト過程において、そのビットを署名した量子状態が受諾又は拒絶された確率を求め、その確率がそのビットの値に応じて定まる一定の範囲内にある場合には、そのビットを受理又は不受理すると判断する第一判断過程と、
を有する量子電子署名システムの処理方法。
【請求項２】
請求項１に記載の量子電子署名システムの処理方法において、
上記署名生成過程は、上記署名の対象となるビットごとに、上記公開鍵生成過程で生成された量子状態のうち上記そのビットを検証する量子状態と直交する量子状態を上記複素乱数発生過程で生成された乱数から生成する過程であり、
上記第一判断過程は、署名の対象となった各ビットごとに、上記スワップテスト過程において、そのビットを署名した量子状態が受諾又は拒絶された確率を求め、その確率が一定の範囲内にある場合には、そのビットを受理又は不受理すると判断する過程である、
ことを特徴とする量子電子署名システムの処理方法。
【請求項３】
請求項１又は２に記載の量子電子署名システムの処理方法において、
さらに、
第二判断手段が、署名の対象となったすべてのビットのうち、上記第一判断過程において受理又は不受理すると判断されたビットの割合を求め、その割合が所定の範囲内にある場合には、送信文書を正当なものであると判断する第二判断過程、
を有することを特徴とする量子電子署名システムの処理方法。
【請求項４】
請求項１に記載の量子電子署名システムの処理方法において、
上記第一判断過程は、署名の対象となったビットのうちそのビットの値が０であるビットを署名した量子状態について、上記スワップテスト過程において、受諾又は拒絶された確率を求め、その確率がそのビットの値に応じて定まる一定の範囲内にある場合、及び／又は、署名の対象となったビットのうちそのビットの値が１であるビットを署名した量子状態について、上記スワップテスト過程において、受諾又は拒絶された確率を求め、その確率がそのビットの値に応じて定まる一定の範囲内にある場合には、送信文書を正当なものであると判断する過程である、
ことを特徴とする量子電子署名システムの処理方法。
【請求項５】
請求項２に記載の量子電子署名システムの処理方法において、
上記第一判断過程は、署名の対象となったビットを署名した量子状態について、上記スワップテスト過程において、受諾又は拒絶された確率を求め、その確率が一定の範囲内にある場合には、送信文書を正当なものであると判断する過程である、
ことを特徴とする量子電子署名システムの処理方法。
【請求項６】
請求項１に記載の量子電子署名システムの処理方法であって、
さらに、
署名対象決定手段が、送信文書を構成するビットのうちどのビットを署名の対象とするのかを決定する署名対象決定過程と、
署名検証量子状態決定手段が、上記署名対象決定過程で決定された署名の対象となるビットを上記公開鍵生成過程で生成された量子状態のうちどの量子状態で検証するのかを決める署名検証量子状態決定過程と、
を有し、
上記署名生成過程は、上記署名対象決定過程で決定された署名の対象となるビットの値に応じて、上記公開鍵生成過程で生成された量子状態のうち上記署名検証量子状態決定過程で決まったそのビットを検証する量子状態と同一の量子状態、又は、上記公開鍵生成過程で生成された量子状態のうち上記署名検証量子状態決定過程で決まったそのビットを検証する量子状態と直交する量子状態を上記複素乱数発生過程で生成された乱数から生成する過程であり、
上記署名送信過程は、さらに、上記署名対象決定過程で決定された署名の対象となるビットについての情報と、上記署名検証量子状態決定過程で決まったそのビットをどの量子状態で検証するのかについての情報とを送信する過程であり、
上記署名受信過程は、さらに、上記署名対象決定過程で決定された署名の対象となるビットについての情報と、上記署名検証量子状態決定過程で決まったそのビットをどの量子状態で検証するのかについての情報とを受信する過程であり、
上記スワップテスト過程は、上記署名受信過程で受信した送信文書を構成するビットのうち上記署名受信過程が受信した情報により定まる署名の対象となるビットごとに、上記署名受信過程で受信した量子状態と、上記署名受信過程が受信した情報により定まるその量子状態に対応する、上記公開鍵受信過程で受信した量子状態とをスワップテストにかけて、受諾されるか拒絶されるかを決定する過程である、
上記第一判断過程は、上記署名受信過程が受信した情報により定まる署名の対象となった各ビットごとに、上記スワップテスト過程において、上記署名受信過程が受信した情報により定まるそのビットを署名した量子状態が受諾又は拒絶された確率を求め、その確率がそのビットの値に応じて定まる一定の範囲内にある場合には、そのビットを受理又は不受理すると判断する過程である、
ことを特徴とする量子電子署名システムの処理方法。
【請求項７】
請求項６に記載の量子電子署名システムの処理方法であって、
上記署名生成過程は、上記署名対象決定過程で決定された署名の対象となるビットごとに、上記公開鍵生成過程で生成された量子状態のうち上記署名検証量子状態決定過程で決まったそのビットを検証する量子状態と直交する量子状態を上記複素乱数発生過程で生成された乱数から生成する過程であり、
上記第一判断過程は、上記署名受信過程が受信した情報により定まる署名の対象となった各ビットごとに、上記スワップテスト過程において、上記署名受信過程が受信した情報により定まるそのビットを署名した量子状態が受諾又は拒絶された確率を求め、その確率が一定の範囲内にある場合には、そのビットを受理又は不受理すると判断する過程である、
ことを特徴とする量子電子署名システムの処理方法。
【請求項８】
送信文書を構成するビットのうちどのビットを署名の対象とするのか、及び、その署名の対象となるビットを公開鍵生成手段で生成された量子状態のうちどの量子状態で検証するのかが定められており、
複素数の乱数を発生する複素乱数発生手段と、
上記複素乱数発生手段で生成された乱数から、少なくとも１つのキュービットからなる量子状態をランダムに生成する上記公開鍵生成手段と、
上記公開鍵生成手段で生成された量子状態を公開する公開鍵公開手段と、
上記署名の対象となるビットごとに、そのビットの値に応じて、上記公開鍵生成手段で生成された量子状態のうち上記そのビットを検証する量子状態と同一の量子状態、又は、上記公開鍵生成手段で生成された量子状態のうち上記そのビットを検証する量子状態と直交する量子状態を上記複素乱数発生手段で生成された乱数から生成する署名生成手段と、
送信文書に、上記署名生成手段で生成された量子状態を付加して送信する署名送信手段と、
上記公開鍵公開手段で公開された量子状態を受信する公開鍵受信手段と、
上記署名送信手段で送信された送信文書と付加された量子状態を受信する署名受信手段と、
上記署名受信手段で受信した量子状態と、その量子状態に対応する、上記公開鍵受信手段で受信した量子状態とをスワップテストにかけて、受諾されるか拒絶されるかを決定するスワップテスト手段と、
署名の対象となった各ビットごとに、上記スワップテスト手段において、そのビットを署名した量子状態が受諾又は拒絶された確率を求め、その確率がそのビットの値に応じて定まる一定の範囲内にある場合には、そのビットを受理又は不受理すると判断する第一判断手段と、
を有する量子電子署名システム。
【請求項９】
請求項８に記載の量子電子署名システムにおいて、
上記署名生成手段は、上記署名の対象となるビットごとに、上記公開鍵生成手段で生成された量子状態のうち上記そのビットを検証する量子状態と直交する量子状態を上記複素乱数発生手段で生成された乱数から生成する手段であり、
上記第一判断手段は、署名の対象となった各ビットごとに、上記スワップテスト手段において、そのビットを署名した量子状態が受諾又は拒絶された確率を求め、その確率が一定の範囲内にある場合には、そのビットを受理又は不受理すると判断する手段である、
ことを特徴とする量子電子署名システム。
【請求項１０】
送信文書を構成するビットのうちどのビットを署名の対象とするのか、及び、その署名の対象となるビットを公開鍵生成手段で生成された量子状態のうちどの量子状態で検証するのかが定められており、
複素数の乱数を発生する複素乱数発生手段と、
上記複素乱数発生手段で生成された乱数から、少なくとも１つのキュービットからなる量子状態をランダムに生成する上記公開鍵生成手段と、
上記公開鍵生成手段で生成された量子状態を公開する公開鍵公開手段と、
上記署名の対象となるビットごとに、そのビットの値に応じて、上記公開鍵生成手段で生成された量子状態のうち上記そのビットを検証する量子状態と同一の量子状態、又は、上記公開鍵生成手段で生成された量子状態のうち上記そのビットを検証する量子状態と直交する量子状態を上記複素乱数発生手段で生成された乱数から生成する署名生成手段と、
送信文書に、上記署名生成手段で生成された量子状態を付加して送信する署名送信手段と、
を有する量子電子署名システムの署名者装置。
【請求項１１】
請求項１０に記載の量子電子署名システムの署名者装置において、
上記署名生成手段は、上記署名の対象となるビットごとに、上記公開鍵生成手段で生成された量子状態のうち上記そのビットを検証する量子状態と直交する量子状態を上記複素乱数発生手段で生成された乱数から生成する手段であり、
上記第一判断手段は、署名の対象となった各ビットごとに、上記スワップテスト手段において、そのビットを署名した量子状態が受諾又は拒絶された確率を求め、その確率が一定の範囲内にある場合には、そのビットを受理又は不受理すると判断する手段である、
ことを特徴とする量子電子署名システムの署名者装置。
【請求項１２】
請求項１０に記載の量子電子署名システムの署名者装置において、
さらに、
送信文書を構成するビットのうちどのビットを署名の対象とするのかを決定する署名対象決定手段と、
上記署名対象決定手段で決定された署名の対象となるビットを上記公開鍵生成手段で生成された量子状態のうちどの量子状態で検証するのかを決める署名検証量子状態決定手段と、
を有し、
上記署名生成手段は、上記署名対象決定手段で決定された署名の対象となるビットの値に応じて、上記公開鍵生成手段で生成された量子状態のうち上記署名検証量子状態決定手段で決まったそのビットを検証する量子状態と同一の量子状態、又は、上記公開鍵生成手段で生成された量子状態のうち上記署名検証量子状態決定手段で決まったそのビットを検証する量子状態と直交する量子状態を上記複素乱数発生手段で生成された乱数から生成する手段であり、
上記署名送信手段は、さらに、上記署名対象決定手段で決定された署名の対象となるビットについての情報と、上記署名検証量子状態決定手段で決まったそのビットをどの量子状態で検証するのかについての情報とを送信する手段である、
ことを特徴とする量子電子署名システムの署名者装置。
【請求項１３】
請求項１２に記載の量子電子署名システムの署名者装置において、
上記署名対象決定手段で決定された署名の対象となるビットごとに、上記公開鍵生成手段で生成された量子状態のうち上記署名検証量子状態決定手段で決まったそのビットを検証する量子状態と直交する量子状態を上記複素乱数発生手段で生成された乱数から生成する手段であり、
上記署名受信手段が受信した情報により定まる署名の対象となった各ビットごとに、上記スワップテスト手段において、上記署名受信手段が受信した情報により定まるそのビットを署名した量子状態が受諾又は拒絶された確率を求め、その確率が一定の範囲内にある場合には、そのビットを受理又は不受理すると判断する手段である、
ことを特徴とする量子電子署名システムの署名者装置。
【請求項１４】
送信文書を構成するビットのうちどのビットを署名の対象とするのか、及び、その署名の対象となるビットを公開鍵生成手段で生成された量子状態のうちどの量子状態で検証するのかが定められており、
上記公開鍵公開手段で公開された量子状態を受信する公開鍵受信手段と、
上記署名送信手段で送信された送信文書と付加された量子状態を受信する署名受信手段と、
上記署名受信手段で受信した量子状態と、その量子状態に対応する、上記公開鍵受信手段で受信した量子状態とをスワップテストにかけて、受諾されるか拒絶されるかを決定するスワップテスト手段と、
署名の対象となった各ビットごとに、上記スワップテスト手段において、そのビットを署名した量子状態が受諾又は拒絶された確率を求め、その確率がそのビットの値に応じて定まる一定の範囲内にある場合には、そのビットを受理又は不受理すると判断する第一判断手段と、
を有する量子電子署名システムの検証者装置。
【請求項１５】
請求項１４に記載の量子電子署名システムの検証者装置であって、
署名の対象となった各ビットごとに、上記スワップテスト手段において、そのビットを署名した量子状態が受諾又は拒絶された確率を求め、その確率が一定の範囲内にある場合には、そのビットを受理又は不受理すると判断する手段である、
ことを特徴とする量子電子署名システムの検証者装置。
【請求項１６】
請求項１４又は請求項１５に記載の量子電子署名システムの検証者装置であって、
さらに、
署名の対象となったすべてのビットのうち、上記第一判断手段において受理又は不受理すると判断されたビットの割合を求め、その割合が所定の範囲内にある場合には、送信文書を正当なものであると判断する第二判断手段、
を有することを特徴とする量子電子署名システムの検証者装置。
【請求項１７】
請求項１４に記載の量子電子署名システムの検証者装置であって、
上記第一判断手段は、署名の対象となったビットのうちそのビットの値が０であるビットを署名した量子状態について、上記スワップテスト手段において、受諾又は拒絶された確率を求め、その確率がそのビットの値に応じて定まる一定の範囲内にある場合、及び／又は、署名の対象となったビットのうちそのビットの値が１であるビットを署名した量子状態について、上記スワップテスト手段において、受諾又は拒絶された確率を求め、その確率がそのビットの値に応じて定まる一定の範囲内にある場合には、送信文書を正当なものであると判断する手段である、
ことを特徴とする量子電子署名システムの検証者装置。
【請求項１８】
請求項１５に記載の量子電子署名システムの検証者装置であって、
上記第一判断手段は、署名の対象となったビットを署名した量子状態について、上記スワップテスト手段において、受諾又は拒絶された確率を求め、その確率が一定の範囲内にある場合には、送信文書を正当なものであると判断する手段である、
ことを特徴とする量子電子署名システムの検証者装置。
【請求項１９】
請求項１４に記載の量子電子署名システムの検証者装置であって、
上記署名受信手段は、さらに、署名対象決定手段で決定された署名の対象となるビットについての情報と、署名検証量子状態決定手段で決まったそのビットをどの量子状態で検証するのかについての情報とを受信する手段であり、
上記スワップテスト手段は、上記署名受信手段で受信した送信文書を構成するビットのうち上記署名受信手段が受信した情報により定まる署名の対象となるビットごとに、上記署名受信手段で受信した量子状態と、上記署名受信手段が受信した情報により定まるその量子状態に対応する、上記公開鍵受信手段で受信した量子状態とをスワップテストにかけて、受諾されるか拒絶されるかを決定する手段である、
上記第一判断手段は、上記署名受信手段が受信した情報により定まる署名の対象となった各ビットごとに、上記スワップテスト手段において、上記署名受信手段が受信した情報により定まるそのビットを署名した量子状態が受諾又は拒絶された確率を求め、その確率がそのビットの値に応じて定まる一定の範囲内にある場合には、そのビットを受理又は不受理すると判断する手段である、
ことを特徴とする量子電子署名システムの検証者装置。
【請求項２０】
請求項１９に記載の量子電子署名システムの検証者装置であって、
上記署名生成手段は、上記署名対象決定手段で決定された署名の対象となるビットごとに、上記公開鍵生成手段で生成された量子状態のうち上記署名検証量子状態決定手段で決まったそのビットを検証する量子状態と直交する量子状態を上記複素乱数発生手段で生成された乱数から生成する手段であり、
上記第一判断手段は、上記署名受信手段が受信した情報により定まる署名の対象となった各ビットごとに、上記スワップテスト手段において、上記署名受信手段が受信した情報により定まるそのビットを署名した量子状態が受諾又は拒絶された確率を求め、その確率が一定の範囲内にある場合には、そのビットを受理又は不受理すると判断する手段である、
ことを特徴とする量子電子署名システムの検証者装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、量子デバイスを用いた情報通信システムにおける情報セキュリティ技術に関するものであり、送信された情報が受信されるまでの間に、第三者によってその情報が改ざんされたか否かを、受信者が検証することができる量子電子署名システム、その処理方法、その署名者装置及びその検証者装置に関する。
【背景技術】
【０００２】
暗号と署名は、情報セキュリティ技術における最も基本的な技術である。暗号は、送信者が受信者に情報を送る際に、第三者による盗聴を防ぐ技術である。これに対して、電子署名は、送信情報が第三者によって改ざんされた場合に、その事実を受信者による検証で可能にする技術である。
電子署名は、一方向性関数を用いる方法が1970年代に提案された。
ここで、一方向性関数ｆとは、ｘからｆ（ｘ）を計算することは多項式時間でできるが、ｆ（ｘ）からｘを計算することは多項式時間ではできない関数である。そのような関数の存在は厳密には証明されていないが、たくさんの候補が知られている。たとえば、２つの素数の積は容易に計算できるが、その逆関数である素因数分解は、一般に困難な計算である。そのため、素数の積の計算は一方向性関数だと予想されている。
【０００３】
従来技術による電子署名プロトコルは以下のように実現される。まず、アリスは２整数ｋ０，ｋ１をランダムに選ぶ。次に、関数ｆの具体的定義（一方向性関数を用いる）と整数の二つの組（０，ｆ（ｋ０））と（１，ｆ（ｋ１））を公開する。アリスが、1ビットの情報ｂ（＝０または１）をボブに送信する場合、（ｂ，ｋｂ）を送信する。この情報を受信したボブは、ｋｂからｆ（ｋｂ）を計算し、（ｂ，ｆ（ｋｂ））が、アリスの公開した（０，ｆ（ｋ０））または（１，ｆ（ｋ１））と一致していれば、送信結果を受理する。
【０００４】
第三者イブは、アリスの送信情報を改竄して、ボブに別の情報を送ることができるだろうか。イブが通信網を切断し、アリスから送信された情報（ｂ，ｋｂ）を傍受して、ボブに（１−ｂ，ｋ１−ｂ））を送信しようとしても、ｆが一方向性関数なので、公開情報のｆ（ｋｂ）からｋｂを計算することは困難である。このようにして、ボブは送信された情報が、確かにアリスから送られた情報だと判断することができる。
この方法の安全性は、一方向性関数の逆関数計算の計算量的な困難さに由来する。しかし、ｆが一方向性関数だとしても、ｋｂの選択方法によっては、電子署名を破ることができる。たとえば、ｋｂのビット数が小さすぎると、全探索によりｆ（ｋｂ）からｋｂを計算することが可能である。したがって、ｋｂとして数百ビットの数字を使う必要がある。それだけの長さの署名を添付したとしても、安全性は計算機の性能などに依存するため、電子署名が絶対に改竄不可能とは言い切れない。特に、近年因数分解などが高速に実行できると予想されている量子コンピュータの開発が活発化しており、一方向性関数を利用する電子署名に関する見直しが必要だと考えられている。
【０００５】
しかし、理論的に一方向性関数の存在と安全な電子署名の存在の同値性が知られている（例えば、非特許文献１参照）。
言い換えれば、これは「古典通信による電子署名の安全性は一方向性関数の逆関数の計算が困難な程度に制限される」事を意味している。つまり無条件に安全な電子署名という物は存在しない事を意味している。
一方、光伝送技術の発達は、情報をレーザーのパルスではなく、一つ一つの光子にのせて送ることを可能にした。光子を利用することによって、量子力学特有の性質を利用することができる。量子通信技術を用いた著しい成果は、暗号通信における無条件に安全な暗号通信である。量子通信を用いることにより、暗号以外にもさまざまな新しいプロトコルが提案されており、その一つが無条件に安全な電子署名である（例えば、非特許文献２参照）。
【０００６】
非特許文献２で提案されている量子電子署名を使うと、量子コンピュータが開発されても第三者による改竄が不可能な電子署名が可能である。この従来技術を説明するには二つの用語(量子一方向性関数、スワップテスト)の用語説明が必要である。
まず、量子一方向性関数ｆ：２Ｌ→ＨＮの説明をする。ここで、Ｈは、一つのキュービットがなす空間のことである。また、次の２条件を満たすＬbit整数からＮqubit量子状態の空間への全射写像を量子一方向性関数ｆと言う。
１．ｋ≠ｋ’の時〈ｆ（ｋ）｜ｆ（ｋ’）〉≦１−εである事  
２．Ｌ＞Ｎである事
上の条件を満たす場合写像ｆが量子一方向性関数と呼ばれる理由は以下にある。ｆの具体的な定義が公開されており、Ｌ／Ｎ以下の個数だけ|ｆ（ｋ）〉が与えられているという場合を考える。この設定において「ｋ」を確実に当てる事は原理的に不可能である場合が、一つの量子一方向性関数ｆにおいて必ず一つはあることが証明できる。まさに順方向は「計算できる」が逆方向は「計算できない」ために量子一方向性関数と名付けられている。
【０００７】
量子一方向性関数は、古典的な一方向性関数と違って具体的な例をもってその存在が知られている。
次に、スワップテストの説明をする。同一のヒルベルト空間中の二つの状態|φ〉と|ψψ〉が与えられた時、スワップテストとは|〈ψ|φ〉|＝δとした時に（１＋δ２）／２の確率で受諾され、（１−δ２）／２の確率で拒絶されるものである。ここで、（１＋δ２）／２は、スワップテストにおいて０が観測される確率であり、（１−δ２）／２は、スワップテストにおいて１が観測される確率である。二つの状態|φ〉と|ψ〉が同一の状態の時には、|〈ψ|φ〉|＝１となり、（１＋δ２）／２＝（１＋１２）／２＝１となるため、必ず受諾される。また、二つの状態|φ〉と|ψ〉が異なる場合には、（１＋δ２）／２が必ずしも１とはならないため、拒絶される可能性が必ずある。スワップテストは、物理的には以下の回路を作り、図５の観測１００における観測結果が０の場合に受諾し、１の場合に拒絶する事で実現される。
【０００８】
この図５において、［Ｈ］と描いてある演算はアダマール演算である。すなわち、次の行列
【数１】
2008048102.tif 000003
【０００９】
で定義される演算である。また、［Ｓｗａｐ］と描いてある演算は制御Ｂｉｔ（一番上のビット）が１の場合に下の２つの入力の状態を入れ替える演算である。
非特許文献２で提案されている量子電子署名は以下のように実現される。まず、アリスは２整数列（ｋ０（１），ｋ０（２），…）と（ｋ１（１），ｋ１（２），…）をランダムに選ぶ。ここで選ばれた整数と量子一方向性関数ｆを使って、量子状態列（|ｆ（ｋ０（１））〉，|ｆ（ｋ０（２））〉，…）と（|ｆ（ｋ１（１））〉，|ｆ（ｋ１（２））〉，…）を作る。ここで、ｆと（０，|ｆ（ｋ０（１））〉，|ｆ（ｋ０（２））〉，…）と（１，|ｆ（ｋ１（１））〉，|ｆ（ｋ１（２））〉，…）を公開する。アリスが、１ビットの情報ｂ（＝０または１）をボブに送信する場合、（ｂ，ｋｂ（１），ｋｂ（２），…）を送信する。この情報を受信したボブは、ｋｂ（ｎ）から|ｆ（ｋｂ（ｎ））〉を計算する。この量子状態と、アリスの公開した（０，|ｆ（ｋ０（１））〉，|ｆ（ｋ０（２））〉，…）と（１，|ｆ（ｋ１（１））〉，|ｆ（ｋ１（２））〉，…）の対応する量子状態とをスワップテストにかける。全てのｋｂ（ｎ）から作られる量子状態においてスワップテストが受諾された場合に、送信結果を受理する。この量子電子署名方法は、スワップテストにおいて、２つの量子状態が同一の場合には、必ず「０」が観測されるが（言い換えると、必ず「受諾」されるが）、２つの量子状態が同一でない場合には、「０」が観測されるとは限らない（言い換えると、「受諾」されるとは限らない）、という性質を利用するものである。
【００１０】
以上のプロトコルにおいて、量子状態を公開する対象人数をＭ、整数をＬbit、量子状態をＮqubitとしたとき、Ｌ−ＭＮ＞＞０となる様に設定するものする。
第三者イブは、アリスの送信情報を改竄して、ボブに別の情報を送ることができるだろうか。イブが通信網を切断し、アリスから送信された情報（ｂ，ｋｂ（１），ｋｂ（２），…）を傍受して、ボブに（１−ｂ，ｋ１−ｂ（１），ｋ１−ｂ（２），…）を送信しようとしても、ｆが量子一方向性関数なので、公開情報の|ｆ（ｋｂ（ｎ））〉からｋｂ（ｎ）を確実に計算することは理論上不可能である。このようにして、ボブは送信された情報が、確かにアリスから送られた情報だと判断することができる。
【非特許文献１】P. Rompel, 「One-way functions are necessary and sufficient for secure signatures」, Proc. 22th Annual ACM symposium on Theory of Computing (STOC ’90) 387-394.
【非特許文献２】D. Gottesman and I. L. Chuang, 「Quantum Digital Signature」, quant-ph/0105032.
【発明の開示】
【発明が解決しようとする課題】
【００１１】
従来技術としての量子電子署名技術は無条件に安全という意味で、電子署名技術よりも本質的に優れているものであるが、そのコンセプトを示したプロトコルにすぎないため、電子署名では存在しなかった実用上における難点が存在する。それは、公開鍵を作成した後に、その公開鍵を配布することができる人間の数を無制限に増やすことができないという難点である。これは、上記の式Ｌ−ＭＮ＞＞０の条件が満たされている場合には、上記の量子電子署名方法の安全性が保証されることが一般に知られているが、公開鍵を作成した後に、上記の式Ｌ−ＭＮ＞＞０の条件が成立しなくなるほど、公開鍵として用いる量子状態を公開する対象人数Ｍを多くすると、上記の量子電子署名方法の安全性が保証されなくなるためである。
【００１２】
また、上記の難点の裏返しとして、公開鍵の作成時点で、公開人数の上限値を知る必要があるという問題がある。しかし、公開人数の上限値は、文書の性質（どの様な人に配るかなど）を知っていなければ一般的にはわからないものである。また、公開鍵という特質上、一般的には公開鍵作成時点では知らないというのが現実である。
また、従来技術における署名プロトコルは、認証された文書の正確性を確認した上で他人に再送し他の人が行う署名の認証に再利用する事が可能である。なぜなら、上記の量子電子署名方法においては、署名は古典的な情報であり、古典的な情報においては、ビットごとのコピーをされた後は、原本と複製とが原理的に見分ける事が不可能であるためである。このため、ソフトウェアのコピーを入手した者であっても、古典情報で表わされた署名を用いて、ウィルス等が混入していないかどうか、そのソフトウェアが正当なものであるかどうかを確認することができ、上記の量子電子署名方法は、ソフトウェアの不正複製を助長する一要因となり得るという問題がある。
【課題を解決するための手段】
【００１３】
請求項１に係る発明によれば、送信文書を構成するビットのうちどのビットを署名の対象とするのか、及び、その署名の対象となるビットを公開鍵生成過程で生成された量子状態のうちどの量子状態で検証するのかが定められており、複素乱数発生手段が、複素数の乱数を発生する。公開鍵生成手段が、上記複素乱数発生過程で生成された乱数から、少なくとも１つのキュービットからなる量子状態をランダムに生成する。公開鍵公開手段が、上記公開鍵生成過程で生成された量子状態を公開する。署名生成手段が、上記署名の対象となるビットごとに、そのビットの値に応じて、上記公開鍵生成過程で生成された量子状態のうち上記そのビットを検証する量子状態と同一の量子状態、又は、上記公開鍵生成過程で生成された量子状態のうち上記そのビットを検証する量子状態と直交する量子状態を上記複素乱数発生過程で生成された乱数から生成する。署名送信手段が、送信文書に、上記署名生成過程で生成された量子状態を付加して送信する。公開鍵受信手段が、上記公開鍵公開過程で公開された量子状態を受信する。署名受信手段が、上記署名送信過程で送信された送信文書と付加された量子状態を受信する。スワップテスト手段が、上記署名受信過程で受信した量子状態と、その量子状態に対応する、上記公開鍵受信過程で受信した量子状態とをスワップテストにかけて、受諾されるか拒絶されるかを決定する。第一判断手段が、署名の対象となった各ビットごとに、上記スワップテスト過程において、そのビットを署名した量子状態が受諾又は拒絶された確率を求め、その確率がそのビットの値に応じて定まる一定の範囲内にある場合には、そのビットを受理又は不受理する。
【発明の効果】
【００１４】
本発明では、公開鍵として用いる量子状態がまったくランダムに生成されるため、安全性が高く、その公開鍵を配布する人数に上限はない。
また、本発明では、署名として量子情報が用いられており、一度その署名を用いて文書の正当性を確認したのちは、すなわち、その量子状態を観測後は、その署名は破壊されてしまう。このため、その署名を再度利用することができない。すなわち、再認証が不可能となる。したがって、1つの署名に対して正しいと確信を持って利用することができる人はひとりだけとなり、安全に利用可能な利用者を管理者の管理の下に置くことが可能になる。
【発明を実施するための最良の形態】
【００１５】
［概要と具体例］
＜例１＞
まず、下記の例を用いて、本発明の内容を簡単に説明する。まず、アリスは量子状態列（|φ（１）〉，|φ（２）〉，…）をランダムに選び公開する。アリスが、1ビットの情報0（または１）をボブに送信する場合、（０，|φ（１）〉，|φ（２）〉，…）（または（１，|φ’（１）〉，|φ’（２）〉，…）)を送信する。ここで、|φ’（ｎ）〉は、|φ（ｎ）〉に直交する量子状態である。この情報を受信したボブは、|φ（ｎ）〉(または|φ’（ｎ）〉)と、アリスの公開した（|φ（１）〉，|φ（２）〉，…）に対応する量子状態とをスワップテストにかける。全ての量子状態においてスワップテストを受諾（または半分に十分近い数の量子状態がスワップテストで受諾）された場合に、送信結果を受理する。
【００１６】
署名の安全性の保証は、任意の状態|φ（ｎ）〉が有限個与えられた時にこれに直交する状態|φ’（ｎ）〉を確実に生成する事が不可能であり、かつ、偶然に生成に成功してもそれを確実に確認することが不可能である事による。
再認証不可能性は、任意の直交する２状態|φ（ｎ）〉と|φ’（ｎ）〉が有限個与えられた時|φ（ｎ）〉を全く壊さずにこの二つ状態が直交している事を確認する事が不可能である事による。上述の不可能性は量子力学的原理から証明される事である。
例えば、図６に示すように、アリス（送信者・署名者）は、ランダムに生成した量子状態列(|φ（１）〉＝（０．３４−０．１１ｉ）|０〉−（０．６７＋０．６５ｉ）|１〉，|φ（２）〉＝（０．２９＋０．４７ｉ）|０〉−（０．３７＋０．８８ｉ）|１〉，…，|φ（ｍ）〉＝（０．３７＋０．５３ｉ）|０〉＋（０．３４−０．６８ｉ）|１〉，|φ（ｍ＋１）〉＝（０．３５−０．８７ｉ）|０〉−（０．３２＋０．１２ｉ）|１〉，…)を公開する。アリスが、２ビットの情報１０をボブ（受信者・検証者）に送信し、第一のビット「１」を上記量子状態|φ（１）〉，|φ（２）〉，…で署名・検証し、第二のビット「０」を上記量子状態|φ（ｍ）〉，|φ（ｍ＋１）〉，…で署名・検証すると予め定められているものとする。かかる場合、アリスは、（１，|φ’（１）〉，|φ’（２）〉，…）と（０，|φ（ｍ）〉，|φ（ｍ＋１）〉，…）をボブに送信する。すなわち、（１，（０．６７−０．６５ｉ）|０〉＋（０．３４＋０．１１ｉ）|１〉，（０．３７−０．８８ｉ）|０〉＋（０．２９−０．４７ｉ）|１〉，…）と（０，（０．３７＋０．５３ｉ）|０〉＋（０．３４−０．６８ｉ）|１〉，（０．３５−０．８７ｉ）|０〉−（０．３２＋０．１２ｉ）|１〉)，…）を送信する。この情報を受信したボブは、事前に公開されている対応している量子状態と対でスワップテストにかける。具体的には、署名の量子状態|φ’（１）〉と公開鍵の量子状態|φ（１）〉、署名の量子状態|φ’（２）〉と公開鍵の量子状態|φ（２）〉、…、署名の量子状態|φ（ｍ）〉と公開鍵の量子状態|φ（ｍ）〉、署名の量子状態|φ（ｍ＋１）〉と公開鍵の量子状態|φ（ｍ＋１）〉、…をスワップテストにかけて、受諾されるか、拒絶されるかを検証する。第一のビット「１」については、上記|φ’（１）〉と|φ（１）〉、上記|φ’（２）〉と|φ（２）〉、…についての各スワップテストで、５０％の確率で受諾された場合には、第一のビットは正当なものであると判断される。また、第二のビット「０」については、上記|φ（ｍ）〉と|φ（ｍ）〉、上記|φ（ｍ＋１）〉と|φ（ｍ＋１）〉、…についてのスワップテストにおいて、それぞれ１００％の確率で受諾された場合には、第二のビットは正当なものであると判断される。第一のビットと第二のビットの両方が正当なものであると判断された場合には、送信文書全体を正当なものであるとして受理することができる。
【００１７】
＜例２＞
下記に例示するように、本発明を実施することもできる。
アリスは１量子ビット２つの組の列（（|φ０（１）〉，|φ１（１）〉），（|φ０（２）〉，|φ１（２）〉），…）をランダムに選び公開する。アリスが、１ビットの情報ｂをボブに送信する場合、（ｂ，（|φｂ’（１）〉，|φｂ’（２）〉，…）を送信する。この情報を受信したボブは、|φｂ’（ｎ）〉と、アリスの公開した（（|φ０（１）〉，|φ１（１）〉），（|φ０（２）〉，|φ１（２）〉），…）に対応する量子状態とをスワップテストにかける。全ての量子状態においてスワップテストを半分に十分近い数の量子状態が受諾された場合に、送信結果を受理する。
【００１８】
この実施例における署名の安全性の保証も、任意の状態|φ〉が有限個与えられた時にこれに直交する状態|φ’〉を確実に生成する事が不可能であり、かつ、偶然に生成に成功してもそれを確実に確認することが不可能である事による。
再認証不可能性も、任意の直交する２状態|φ〉と|φ’〉が有限個与えられた時|φ〉を全く壊さずにこの二つ状態が直交している事を確認する事が不可能である事による。上述の不可能性は量子力学的原理から証明される事である。
例えば、図７に示すように、アリスは１量子ビット２つの組の列
｛（|φ０（１）〉＝（０．２４−０．５１ｉ）|０〉−（０．７８−０．２８ｉ）|１〉，|φ１（１）〉＝（０．０３−０．１５ｉ）|０〉−（０．９２＋０．３７ｉ）|１〉），
（|φ０（２）〉＝（０．７６＋０．０６ｉ）|０〉−（０．５１＋０．３９ｉ）|１〉，|φ１（２）〉＝（０．４０＋０．５３ｉ）|０〉＋（０．１１−０．７４ｉ）|１〉），…，
（|φ０（ｍ）〉＝（０．３６＋０．６４ｉ）|０〉−（０．６１＋０．２９ｉ）|１〉，|φ１（ｍ）〉＝（０．４７＋０．５５ｉ）|０〉−（０．６３−０．２８ｉ）|１〉），
（|φ０（ｍ＋１）〉＝（０．６５−０．６５ｉ）|０〉＋（０．２４＋０．３１ｉ）|１〉，|φ１（ｍ＋１）〉＝（０．５７＋０．６０ｉ）|０〉＋（０．００−０．５７ｉ）|１〉），…｝
をランダムに選び公開する。アリスが、２ビットの情報１０をボブに送信し、第一のビット「１」を｛（|φ０（１）〉，|φ１（１）〉），（|φ０（２）〉，|φ１（２）〉），…｝の量子ビットの組の列で署名・検証し、第二のビット「０」を｛（|φ０（ｍ）〉，|φ１（ｍ）〉），（|φ０（ｍ＋１）〉，|φ１（ｍ＋１）〉），…｝の量子ビットの組の列で署名・検証すると予め定められているものとする。このとき、アリスは、（１，|φ１’（１）〉，|φ１’（２）〉，…），（０，|φ０’（ｍ）〉，|φ０’（ｍ＋１）〉，…）をボブに送信する。すなわち、（１，（０．９２−０．３７ｉ）|０〉＋（０．０３＋０．１５ｉ）|１〉，（０．１１＋０．７４ｉ）|０〉−（０．４０−０．５３ｉ）|１〉，…），（０，（０．６１−０．２９ｉ）|０〉＋（０．３６−０．６４ｉ）|１〉，（０．２４−０．３１ｉ）|０〉−（０．６５＋０．６５ｉ）|１〉，…）を送信する。この情報を受信したボブは、事前に公開されている対応している量子状態と対でスワップテストにかける。
【００１９】
具体的には、署名の量子状態|φ１’（１）〉と公開鍵の量子状態|φ１（１）〉、署名の量子状態|φ１’（２）〉と公開鍵の量子状態|φ１（２）〉、…、署名の量子状態|φ０’（ｍ）〉と公開鍵の量子状態|φ（ｍ）〉、署名の量子状態|φ０’（ｍ＋１）〉と公開鍵の量子状態|φ（ｍ＋１）〉、…をそれぞれスワップテストにかけて、受諾されるか、拒絶されるかを検証する。スワップテストの結果、５０％の確率で受諾された場合には、各ビット及び送信文書を正当なものとして受理することができる。
以上が、本発明の概要と具体例である。以下、本発明の具体的な内容について説明する。上記例１の発明を一般化したものが第一実施形態であり、上記例２の発明を一般化したものが第二実施形態である。
【００２０】
［第一実施形態］
以下、図１を参照して、本発明の第一実施形態による量子電子署名システム１を説明する。図１は、量子電子署名システム１の量子電子署名システムの機能構成を例示する図である。量子電子署名システム１は、例えば、署名者装置２、検証者装置３から構成される。署名者装置２と検証者装置３は、例えば、光ファイバーで結ばれている。
署名者装置２は、例えば、複素乱数発生部２１、公開鍵生成部２２、公開鍵公開部２３、文書記録部２４、署名生成部２５、署名送信部２６、署名検証量子状態決定部２７、署名対象決定部２８から構成される。
検証者装置３は、例えば、公開鍵受信部３１、署名受信部３２、スワップテスト部３３、判断部３７、文書記録部３９から構成される。判断部３７は、例えば、第一判断部３４、第二判断部３５から構成される。
【００２１】
＜ステップＳ１＞
複素乱数発生部２１が、複素数をランダムに発生させる。発生させる複素数の数は、後に生成しようとする量子状態|φ（ｎ）>の数及び量子状態|φ（ｎ）>のキュービットの数に依存する。例えば、１つのキュービットからなる量子状態を、Ｎ個生成する場合には、２×Ｎ個の複素数の乱数（ｘ０（１），ｘ１（１），ｘ０（２），ｘ１（２），…，ｘ０（Ｎ），ｘ１（Ｎ））を生成する。生成された複素数は、公開鍵生成部２２と署名検証量子状態決定部２７に出力される。
【００２２】
＜ステップＳ２＞
公開鍵生成部２２は、複素乱数発生部２１が生成した複素数の乱数（ｘ０（１），ｘ１（１），ｘ０（２），ｘ１（２），…，ｘ０（Ｎ），ｘ１（Ｎ））から、公開鍵として用いる量子状態（|φ（１）>，|φ（２）>，…，|φ（Ｎ）>）を生成する。例えば、量子状態|φ（ｎ）>が１つのキュービットからなる場合には、|φ（ｎ）>＝（１／（|ｘ０（ｎ）|２＋|ｘ１（ｎ）|２）１／２）（ｘ０（ｎ）|０>＋ｘ１（ｎ）|１>），ｎ＝１，２，…，Ｎとなるように、量子状態|φ（ｎ）>を生成する。生成された量子状態（|φ（１）>，|φ（２）>，…，|φ（Ｎ）>）は、公開鍵公開部２３に出力される。
【００２３】
なお、本発明では、キュービットとして、例えば、光子を用いる。具体的にどのような装置構成で本発明を実施するための処理を行うのかについては、下記の参考文献１に詳しい。
≪参考文献１≫Michael A. Nielsen, Isaac L.Chuang共著、木村達也訳「量子コンピュータと量子通信II―量子コンピュータとアルゴリズム―」オーム社
なお、量子状態|φ（ｎ）>は任意の数のキュービットで構成することができるが、１つのキュービットで構成すると、最も効率が良くなり、かつ、安全性が高くなる。本発明では、後述するように、２つの量子状態が同一又は直交しているかどうかを検出することにより、署名の正当性を確認するが、量子状態|φ（ｎ）>が２以上のキュービットから構成されている場合には、署名の正当性の確認のために直交しているかどうかを検出する精度が悪くなるためである。また、量子状態|φ（ｎ）>が２以上のキュービットから構成されている場合には、任意の量子状態|φ（ｎ）>に、ほとんど直交する量子状態を作りやすいためである。
また、生成する量子状態|φ（ｎ）>の数は、本発明の利用者が求める安全性のレベルに応じて定めることができる。一般に、生成する量子状態|φ（ｎ）>の数が多くなるほど、安全性のレベルが高くなる。
【００２４】
＜ステップＳ３＞
公開鍵公開部２３は、公開鍵生成部２２が生成した公開鍵として用いる量子状態（|φ（１）>，|φ（２）>，…，|φ（Ｎ）>）を公開する。文書ｍｅの送信先が予め決まっている場合には、公開鍵として用いる量子状態（|φ（１）>，|φ（２）>，…，|φ（Ｎ）>）を、その送信先に送信しても良い。すなわち、公開鍵として用いる量子状態を特定の者のみに対して公開するようにしても良い。特定の者のみに公開することにより、より安全性が増すというメリットがある。
【００２５】
＜ステップＳ４＞
署名対象決定部２８は、文書記録部２４から読み出した文書ｍｅを構成するビットのうちどのビットを署名の対象とするのかを決定する。例えば、文書ｍｅを構成するビットのうちすべてのビットを署名の対象として決定することができる。また、文書ｍｅを構成するビットからランダムにビットを選択して、それらのランダムに選択したビットを署名の対象として決定することができる。さらに、文書ｍｅを構成するビットのうち、奇数番目のビット、又は、偶数番目のビットを署名の対象としても良い。署名の対象となったビットについての情報は、署名検証量子状態決定部２７と署名送信部２６に送信される。
【００２６】
なお、一般に署名の対象となるビットの数が多ければ多いほど、本発明による署名の安全性が増すというメリットがあるが、処理の負担も増えるというデメリットもある。署名の対象となるビットの数、及び、どのビットを署名の対象とするのかは、このメリットとデメリットを考慮した上で、本発明の実施者が任意に決定しても良い。すなわち、本発明の実施者が、文書ｍｅを構成するビットのうちどのビットを署名の対象とするのかを予め決めておき、その決められた署名の対象となるビットについて後述する処理を行うようにしても良い。
【００２７】
＜ステップＳ５＞
署名検証量子状態決定部２７は、署名対象決定部２８が決定した署名の対象となるビットを、公開鍵として用いる量子状態（|φ（１）>，|φ（２）>，…，|φ（Ｎ）>）のうちどの量子状態で検証するのかを決定する。言い換えると、署名検証量子状態決定部２７は、署名の対象となるビットを、公開鍵として用いる量子状態（|φ（１）>，|φ（２）>，…，|φ（Ｎ）>）と同一又は直交の量子状態のうちどの量子状態で署名するのかを決定する。
【００２８】
例えば、図２に示すように、文書ｍｅのビット列が（０，１，０，１，１，…）であり、これらのすべてのビットについて署名をする場合を考える。かかる場合には、例えば、図２の※１で示すように、第一のビット「０」については|φ（１）>，…，|φ（１００）>、第二のビット「１」については|φ（１０１）>，…，|φ（２００）>、第三のビット「０」については|φ（２０１）>，…，|φ（３００）>、第四のビット「１」については|φ（３０１）>，…，|φ（４００）>、第五のビット「１」については|φ（４０１）>，…，|φ（５００）>を用いて署名及び検証すると署名検証量子状態決定部２７は決定する。すなわち、例えば、署名の対象となるすべてのビットについて、１００個の量子状態を用いて署名及び検証すると決定することができる。
【００２９】
また、図２の※２で示すように、第一のビット「０」については|φ（１）>，|φ（２）>，|φ（３）>、第二のビット「１」については|φ（４）>、第三のビット「０」については|φ（５）>，|φ（６）>、第四のビット「１」については|φ（７）>，|φ（８）>、第五のビット「１」については|φ（９）>，|φ（１０）>，|φ（１１）>を用いて署名及び検証すると署名検証量子状態決定部２７は決定しても良い。すなわち、署名の対象となる各ビットごとに、異なる数の量子状態を用いて署名及び検証すると決定することができる。
【００３０】
また、図２の※３で示すように、第一のビット「０」については|φ（１）>、第二のビット「１」については|φ（２）>、第三のビット「０」については|φ（３）>、第四のビット「１」については|φ（４）>、第五のビット「１」については|φ（５）>を用いて署名及び検証すると署名検証量子状態決定部２７は決定しても良い。すなわち、署名の対象となる各ビットを、１つの量子状態で署名及び検証すると決定することができる。
また、図２の※４で示すように、例えば、第一のビット「０」については|φ（３）>、第二のビット「１」については|φ（１）>、第三のビット「０」については|φ（１０）>、第四のビット「１」については|φ（７）>、第五のビット「１」については|φ（５）>を用いて署名及び検証すると署名検証量子状態決定部２７は決定しても良い。すなわち、署名の対象となる各ビットを、公開鍵として用いる量子状態のうちランダムに選択した量子状態で署名及び検証すると決定することができる。
【００３１】
さらに、図２の※５で示すように、文書ｍｅを構成するビットのうち少なくとも第一のビットと第三のビットと第五のビットが署名の対象となっている場合には、これらのビットのみについて、署名及び検証に用いる量子状態を決めることができる。
署名の対象となるビットを署名及び検証する量子状態の数が多いほど、本発明による署名の信頼性は増すというメリットがあるが、処理の負担も増すというデメリットがある。これらのメリットとデメリットを考慮した上で、署名の対象となるビットを署名及び検証する量子状態の数が、本発明の実施者が望む範囲に収まるように、署名検証量子状態決定部２７は、署名の対象となるビットを署名及び検証する量子状態を決定する。
【００３２】
なお、後述するように、検証装置は、スワップテストにおいて、約５０％の確率で受諾されたかどうかにより、そのビットを受理するかどうかを決定する場合がある。したがって、かかる場合には、ひとつのビットを署名及び検証する量子状態の数は、奇数ではなく、偶数になるように設定されることが望ましい。
署名の対象となるビットを署名及び検証するために用いる量子状態についての情報は、署名生成部２５と署名送信部２６に送られる。
【００３３】
＜ステップＳ６＞
署名生成部２５は、署名の対象となるビットの値に応じて、公開鍵生成部２２が生成した量子状態と同一の量子状態、又は、公開鍵生成部２２が生成した量子状態と直交する量子状態を、複素乱数発生部２１が生成した複素数を用いて生成する。
署名生成部２５は、例えば、図２の※１に示すように、文書ｍｅを構成する各ビットについてそれぞれ、１００個の量子状態を用いて署名及び検証する場合には、第一のビットが「０」であるため、|φ（１）>，…，|φ（１００）>と同一の量子状態|φ（１）>，…，|φ（１００）>を、複素乱数発生部２１が生成した複素数を用いて、第一のビットに対する署名として生成する。また、第二のビットが「１」であるため、|φ（１０１）>，…，|φ（２００）>と直交する量子状態|φ’（１０１）>，…，|φ’（２００）>を、複素乱数発生部２１が生成した複素数を用いて、第二のビットに対する署名として生成する。また、第三のビットが「０」であるため、|φ（２０１）>，…，|φ（３００）>と同一の量子状態|φ（２０１）>，…，|φ（３００）>を、複素乱数発生部２１が生成した複素数を用いて、第三のビットに対する署名として生成する。また、第四のビットが「１」であるため、|φ（３０１）>，…，|φ（４００）>と直交する量子状態|φ’（３０１）>，…，|φ’（４００）>を、複素乱数発生部２１が生成した複素数を用いて、第四のビットに対する署名として生成する。また、第五のビットが「１」であるため、|φ（４０１）>，…，|φ（５００）>と直交する量子状態|φ’（４０１）>，…，|φ’（５００）>を、複素乱数発生部２１が生成した複素数を用いて、第五のビットに対する署名として生成する。
【００３４】
署名生成部２５は、図２の※２〜※５のように、署名の対象となるビットを署名及び検証する量子状態を定めた場合においても、上記※１についての説明と同様に、ビットの値が「０」である場合には、公開鍵に用いる量子状態のうちそのビットを検証する量子状態と同一の量子状態を、複素乱数発生部２１が生成した複素数を用いて、そのビットに対する署名として生成する。また、ビットの値が「１」である場合には、公開鍵に用いる量子状態のうちそのビットを検証する量子状態と直交する量子状態を、複素乱数発生部２１が生成した複素数を用いて、そのビットに対する署名として生成する。
【００３５】
なお、署名生成部２５は、ビットの値が「０」の場合に、公開鍵に用いる量子状態のうちそのビットを検証する量子状態と直交する量子状態を、そのビットに対する署名として生成し、ビットの値が「１」の場合に、公開鍵に用いる量子状態のうちそのビットを検証する量子状態と同一の量子状態を、そのビットに対する署名として生成しても良い。
文書ｍｅを構成するビットのうちの署名の対象となるビットについての情報、及び、そのビットを署名する量子状態についての情報には、署名対象決定部２８及び署名検証量子状態決定部２７から送られてくる情報を用いる。
【００３６】
生成された署名は、署名送信部２６に出力される。
＜ステップＳ７＞
署名送信部２６は、文書記録部２４から読み出した文書ｍｅと、署名生成部２５が生成した署名と、署名対象決定部２８が生成した署名の対象となるビットについての情報と、署名検証量子状態決定部２７が生成した、署名の対象となるビットをどの量子状態で署名及び検証するのかについての情報と、を検証者装置３に送信する。
なお、安全性の確保のため、署名の対象となるビットについての情報及び署名の対象となるビットをどの量子状態で署名・検証するのかについての情報は、文書ｍｅ及び署名とは別に、検証者装置３に送信しても良い。
【００３７】
＜ステップＳ８＞
検証者装置３の公開鍵受信部３１は、署名者装置２の公開鍵公開部２３が公開した公開鍵に用いる量子状態（|φ（１）>，|φ（２）>，…，|φ（Ｎ）>）を受信する。受信した量子状態は、スワップテスト部３３に出力される。
＜ステップＳ９＞
署名受信部３２は、署名者装置２の署名送信部２６が送信した文書ｍｅと、署名と、署名の対象となるビットについての情報と、署名の対象となるビットをどの量子状態で署名及び検証するのかについての情報と、を受信する。文書ｍｅは、スワップテスト部３３と判断部３７に出力される。署名と、署名の対象となるビットについての情報と、署名の対象となるビットをどの量子状態で署名及び検証するのかについての情報とは、スワップテスト部３３に出力される。
【００３８】
＜ステップＳ１０＞
スワップテスト部３３は、署名の対象となったすべてのビットについて、そのビットを署名した量子状態と、その量子状態に対応した、公開鍵に用いる量子状態とをスワップテストにかける。スワップテストの結果、「０」が観測された場合には「受諾」され、「０」が観測されなかった場合、つまり、「１」が観測された場合には「拒絶」される。スワップテストの結果、すなわち「受諾」又は「拒絶」は、第一判断部３４に出力される。
例えば、あるビットの値が「０」であり、そのビットを署名した量子状態（|φ（ｋ）>，|φ（ｋ’）>，|φ（ｋ’’）>）が３つあり、|φ（ｋ）>に対応する公開鍵に用いる量子状態が|φ（ｌ）>、|φ（ｋ’）>に対応する公開鍵に用いる量子状態が|φ（ｌ’）>、|φ（ｋ’’）>に対応する公開鍵に用いる量子状態が|φ（ｌ’’）>であるとする。かかる場合には、|φ（ｋ）>と|φ（ｌ）>、|φ（ｋ’）>と|φ（ｌ’）>、|φ（ｋ’’）>と|φ（ｌ’’）>をそれぞれスワップテストにかけて、観測する。「受諾」又は「拒絶」の結果は、|φ（ｋ）>と|φ（ｌ）>、|φ（ｋ’）>と|φ（ｌ’）>、|φ（ｋ’’）>と|φ（ｌ’’）>のそれぞれの量子状態の組ごとに得られる。
【００３９】
なお、「０」が観測された場合に「拒絶」され、「１」が観測された場合に「受諾」されると判断し、「拒絶」又は「受諾」の結果を、判断部３７に出力しても良い。
＜ステップＳ１１＞
判断部３７の第一判断部３４は、署名の対象となったビットごとに、そのビットを署名した量子状態と、その量子状態に対応した、公開鍵に用いる量子状態とについて行ったスワップテストの結果を集計して、そのビットを受理するかどうかを判断する。具体的には、署名の対象となったビットが「０」であるときには、そのビットを署名したすべての量子状態について行ったスワップテストにおいて、約１００％の確率で「受諾」された場合に、そのビットを受理すると判断する。また、署名の対象となったビットが「１」であるときには、そのビットを署名したすべての量子状態について行ったスワップテストにおいて、約５０％の確率で「受諾」された場合に、そのビットを受理すると判断する。
【００４０】
署名の対象となるビットについての情報と、署名の対象となるビットをどの量子状態で署名及び検証するのかについての情報は、署名受信部３２から受信したものを用いる。
なお、署名者装置２の署名生成部２５が、ビットの値が「０」の場合に、公開鍵に用いる量子状態のうちそのビットを検証する量子状態と直交する量子状態を、そのビットに対する署名として生成し、ビットの値が「１」の場合に、公開鍵に用いる量子状態のうちそのビットを検証する量子状態と同一の量子状態を、そのビットに対する署名として生成した場合には、署名の対象となったビットが「０」であるときの上記の約１００％の確率と、署名の対象となったビットが「１」であるときの上記の約５０％の確率とが入れ替わる。すなわち、かかる場合には、判断部３７は、署名の対象となったビットが「０」であるときには、そのビットを署名したすべての量子状態についてしたスワップテストにおいて、約５０％の確率で「受諾」された場合に、そのビットを受理すると判断する。また、署名の対象となったビットが「１」であるときには、そのビットを署名したすべての量子状態について行ったスワップテストにおいて、約１００％の確率で「受諾」された場合に、そのビットを受理すると判断する。
【００４１】
なお、上記では、約１００％の確率で「受諾」されるか、又は、約５０％の確率で「受諾」されるかどうかにより、そのビットを受理するかどうかを判断するとしたが、上記の約１００％の幅、及び、上記の約５０％の幅は、本発明の実施者が求める安全性に応じて、かつ、署名者装置及び検証者装置の品質や量子通信の通信路の状況に応じて、かつ、そのビットを署名・検証する量子状態の数に応じて、適宜設定することができる。例えば、求める安全性のレベルが高いときには、１００％に近い割合で「受諾」された場合、又は、５０％に近い割合で「受諾」された場合のみ、そのビットを受理すると判断することができる。逆に、求める安全性のレベルがそれほど高くない場合には、例えば、９０〜１００％の割合で「受諾」された場合、又は、４０〜６０％の割合で「受諾」された場合に、そのビットを受理すると判断することができる。
【００４２】
また、上記では、「受諾」される確率をもとにして、そのビットを受理するかどうかを判断したが、「拒絶」される確率をもとにして、そのビットを受理するかどうかを判断しても良い。具体的には、第一判断部３４は、「拒絶」される確率＝１−「受諾」される確率であるため、約０％の確率で「拒絶」された場合、又は、約５０％の割合で「受諾」された場合に、そのビットを受理すると判断することができる。
また、スワップテスト部３３が、「０」が観測された場合に「拒絶」され、「１」が観測された場合に「受諾」されると判断し、その「拒絶」又は「受諾」の結果を、判断部３７に出力したときには、第一判断部３４は、ビットの値が「１」である場合には、「受諾」される確率が約５０％のときに、そのビットを受理し、ビットの値が「０」である場合には、「受諾」される確率が約０％のときに、そのビットを受理すると判断することができる。
このようにして、第一判断部３４は、各ビットを受理するかどうかを判断する。各ビットについての受理、不受理の結果は、第二判断部３５に出力される。
【００４３】
＜ステップＳ１２＞
第二判断部３５は、第一判断部３４が行った文書ｍｅの各ビットについての受理、不受理の判断の結果を受けて、その文書ｍｅが正当なものであるかどうかを判断する。文書ｍｅが正当なものであると判断された場合には、その文書ｍｅを文書記録部３９に格納する。
【００４４】
文書ｍｅが正当なものであるかの判断は、文書ｍｅの署名の対象となったすべてのビットの中で、第一判断部３４により受理、又は、不受理とされたビットの割合が、一定の範囲内にあるかどうか判断することにより行う。具体的には、受理された割合が、９５〜１００％のとき、又は、不受理とされた割合が０〜５％のときに、その文書ｍｅが正当なものであると判断することができる。もちろん、署名の対象となったビットのすべてについて受理された場合（１００％の確率で受理された場合）、又は、署名の対象となったビットのうち不受理とされたビットがひとつもなかった場合に（すなわち、不受理とされた確率が０％である場合）、その文書ｍｅを正当なものであると判断しても良い。
受理、又は、不受理とされたビットの割合の範囲は、本発明の実施者が、求める安全性のレベルに応じて適宜設定することができる。すなわち、求める安全性のレベルが高いほど、受理された割合が１００％に近い範囲内にある場合、又は、不受理された割合が０％に近い範囲内にある場合に、その文書ｍｅが正当なものであると判断することができる。
なお、第二判断部３５が上記の判断をせずに、判断部３７が、第一判断部３４が受理したビットのみを、文書記録部３９に記録しても良い。
【００４５】
＜ステップＳ１１’＞
また、図２の※２〜※５で示したように、ひとつのビットについて署名・検証する量子状態の数が少ない場合には、上記ステップＳ１１とステップ１２の替わりに、以下に説明するステップＳ１１’の処理を行っても良い。ステップＳ１１’は、文全体において通信の受理不受理の決定を行うものである。すなわち、判断部３７の第三判断部３６が、署名の対象となったすべてのビットを、そのビットの値に応じて、２つのグループに分ける。すなわち、ビットの値が「０」のグループと、ビットの値が「１」のグループとに分ける。第三判断部３６は、ビットの値が「０」のグループに含まれるビットについての、スワップテスト部３３における「受諾」の割合を調べ、その割合が約１００％であり、かつ、ビットの値が「１」のグループに含まれるビットについての、スワップテスト部３３における「受諾」の割合を調べ、その割合が約５０％である場合には、文書ｍｅが正当なものであると判断する。
【００４６】
なお、ビットの値が「１」のグループに含まれるビットについてのスワップテスト部３３における「受諾」の割合が約５０％である場合には、ビットの値が「０」のグループに含まれるビットについてのスワップテスト部３３における［受諾］の割合が約１００％である可能性が高い。したがって、計算処理の量を軽減したい場合には、ビットの値が「１」のグループに含まれるビットについてのスワップテスト部３３における「受諾」の割合が約５０％であるかのみを検証しても良い。
なお、ステップＳ１１で説明したのと同様に、「拒絶」の割合に基づいて文書ｍｅの正当性について判断しても良く、また、上記の割合は適宜変更される。
【００４７】
以上が、本実施形態の概要である。
本発明による署名の安全性の保証は、任意の状態|φ〉が有限個与えられた時にこれに直交する状態|φ’〉を確実に生成する事が不可能であり、かつ、偶然に生成に成功してもそれを確実に確認することが不可能である事による。再認証不可能性は、任意の直交する２状態|φ〉と|φ’〉が有限個与えられた時|φ〉を全く壊さずにこの二つ状態が直交している事を確認する事が不可能である事による。上述の不可能性は量子力学的原理から証明される事である。
【００４８】
［第二実施形態］
以下、図３を参照して、本発明の第二実施形態による量子電子署名システム１’を説明する。図３は、量子電子署名システム１’の機能構成を例示する図である。
第二実施形態の量子電子署名システム１’は、以下の点で第一実施形態の量子電子署名システム１と異なる。以下では、第二実施形態の量子電子署名システム１’の機能構成のうち、第一実施形態の量子電子署名システム１と同様の処理を行うものについては同じ符号番号を付けて説明を省略する。
【００４９】
量子電子署名システム１’の署名者装置４は、量子電子署名システム１の署名者装置２とは異なり、複素乱数発生部４１、公開鍵生成部４２、署名生成部４５、署名検証量子状態決定部４７を有している。また、量子電子署名システム１’の検証者装置５は、量子電子署名システム１の検証者装置３とは異なり、判断部５７、第一判断部５４、第三判断部５６を有している。
複素乱数発生部４１は、複素数の乱数（ｘ０，０（１），ｘ１，０（１），ｘ０，１（１），ｘ１，１（１）ｘ０，０（２），ｘ１，０（２），ｘ０，１（２），ｘ１，１（２），…，ｘ０，０（Ｎ），ｘ１，０（Ｎ），ｘ０，１（Ｎ），ｘ１，１（Ｎ））を生成して、公開鍵生成部に出力する。
【００５０】
公開鍵生成部４２は、複素乱数発生部４１が生成した複素数から、「０」の値のビットに用いる量子状態と、「１」の値のビットに用いる量子状態とを生成する。例えば、量子状態|φｂ（ｎ）>がひとつのキュービットからなる場合には、|φｂ（ｎ）>＝（１／（|ｘｂ，０（ｎ）|２＋|ｘｂ，１（ｎ）|２）１／２）（ｘｂ，０（ｎ）|０>＋ｘｂ，１（ｎ）|１>），ｂ＝１，２，ｎ＝１，２，…，Ｎとなるように、量子状態|φｂ（ｎ）>を生成する。
署名検証量子状態決定部４７は、署名対象決定部２８が決定した署名の対象となるビットを、署名・検証する量子状態を決定する。第一実施形態の場合とは異なり、署名検証量子状態決定部４７は、署名の対象となるビットの値を調べ、そのビットの値が「０」の場合には、上記「０」の値のビットに用いる量子状態の中から、そのビットを署名・検証するために用いる量子状態を決定し、また、そのビットの値が「１」の場合には、上記「１」の値のビットに用いる量子状態の中から、そのビットを署名・検証するために用いる量子状態を決定する。例えば、図２の※１〜※５を用いて、第一実施形態の署名検証量子状態決定部２７について説明したのと同様に、図４の※１〜※５に示すように、署名の対象となるビットを署名・検証する量子状態を決定することができる。署名の対象となるビットを署名・検証する量子状態についての情報は、署名生成部４５と署名送信部２６に出力される。
【００５１】
署名生成部４５は、公開鍵に用いる量子状態列のうち、上記決定された、署名の対象となるビットを署名・検証する量子状態に直交する量子状態|φｂ（ｎ）>を、複素乱数発生部４１が生成した複素数を用いて生成する。生成された量子状態|φｂ（ｎ）>は、署名送信部２６に出力される。第一実施形態においては、ビットの値に応じて、同一の量子状態、又は、直交する量子状態を生成したが、第二実施形態は、ビットの値に関わらず直交する量子状態のみを生成する点で、大きく異なる。
上記第一判断過程は、署名の対象となった各ビットごとに、スワップテスト部３３において、そのビットを署名した量子状態が受諾又は拒絶された確率を求め、その確率が一定の範囲内にある場合には、そのビットを受理又は不受理する。先に説明したように、第二実施形態においては、署名生成部４５は、ビットの値に関わらず直交する量子状態のみを生成しているため、第二実施形態における第一判断部５４は、スワップテスト部３３において、そのビットを署名した量子状態が受諾又は拒絶された確率が、約５０％であるかどうかによって、そのビットを受理するかどうかを決定する。約５０％の幅については、第一実施形態で説明したのと同様である。
【００５２】
文全体において通信の受理不受理を行う場合の判断部である第三判断部５６は、署名の対象となったすべてのビットについて、スワップテスト部３３において、そのビットを署名した量子状態について「受諾」された割合を調べ、その割合が約５０％である場合には、文書ｍｅが正当なものであると判断する。なお、求める安全性のレベルがそれほど高くない場合には、署名の対象となったすべてのビットではなく、所定のビットのみについて「受諾」された割合を調べて、文書ｍｅが正当なものであるかどうかを確認しても良い。
なお、第一実施形態の署名生成部２５と第二実施形態の署名生成部４５は、公開鍵公開部２３が公開した量子状態と同一状態又は直交状態であるのかの確率的な検証が可能なような量子状態を、複素乱数発生部２１、４１で生成された乱数から生成する手段であるという点で共通するということができる。
また、第一実施形態のスワップテスト部３３及び判断部３７と、第二実施形態のスワップテスト部３３と判断部５７とは、署名受信部３２が受信した量子状態と、その量子状態に対応する公開鍵受信部３１が受信した量子状態とが同一状態又は直交状態であるかを確率的に検証することにより、その文書が正当なものであるかどうかを判定する手段である点で共通するということができる。
【００５３】
［変形例］
上記実施形態では、署名対象決定部２８が、文書ｍｅを構成するビットのうち署名の対象となるビットを決定し、署名検証量子状態決定部２７又は署名検証量子状態決定部４７が、署名の対象となるビットを署名・検証する量子状態を決定していた。しかし、予め署名の対象となるビットと、署名の対象となるビットを署名・検証する量子状態の一方又は両方を予め定めておき、署名者装置２、署名者装置４、検証者装置３、検証者装置５がそれぞれ、この予め定められた署名の対象となるビットと、署名の対象となるビットを署名・検証する量子状態とに基づいて処理を行っても良い。
【００５４】
また、上記の実施形態では、図５に示した量子回路で実現されるスワップテストを用いて、２つの量子状態が同一であるかどうか、直交しているかどうかを検証した。しかし、２つの量子状態が同一であるかどうか、直交しているかどかを検証することができる手段であれば、図５に示した量子回路で実現されるスワップテスト以外の手段を用いても良い。
本発明である量子電子署名システム、その処理方法、その署名者装置及びその検証者装置は上記の実施形態及び変形例に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【図面の簡単な説明】
【００５５】
【図１】本発明による量子電子署名システム１の機能構成を例示した図。
【図２】本発明の第一実施形態における、署名の対象となるビットを署名・検証する量子状態の定め方を例示した図。
【図３】本発明による量子電子署名システム１’の機能構成を例示した図。
【図４】本発明の第二実施形態における、署名の対象となるビットを署名・検証する量子状態の定め方を例示する図。
【図５】スワップテストを実現するための量子回路を例示した図。
【図６】例１の具体例の説明を補助するための図。
【図７】例２の具体例の説明を補助するための図。
【図１】
2008048102.tif 000004
【図２】
2008048102.tif 000005
【図３】
2008048102.tif 000006
【図４】
2008048102.tif 000007
【図５】
2008048102.tif 000008
【図６】
2008048102.tif 000009
【図７】
2008048102.tif 000010