量子公開鍵暗号システム、鍵生成装置、暗号化装置、復号装置、鍵生成方法、暗号化方法、及び復号方法
【課題】最大エンタングルメント状態の特性を利用し、より安全で利便性の高い量子公開鍵暗号システムを実現すること。
【解決手段】発生させた乱数に基づき、ｎ量子ビットに対するｍ種類のユニタリ演算Ｕｉ（ｉ＝１〜ｍ）、及び、ｍ量子ビットに対する２種類のユニタリ演算Ｌ、Ｒに、それぞれ対応する量子ゲートＵｉ、Ｌ、Ｒを生成し、ｍ量子ビットの入力状態に応じて量子ゲートＵｉの動作が制御されるように制御化された量子ゲートＣＵを生成し、量子ゲートＣＵに量子ゲートＬ、Ｒを付加して量子ゲートＧを生成し、量子ゲートＧを難読化して公開鍵Ｐを生成し、量子ゲートＣＵに対応するユニタリ演算ＣＵのエルミート共役ＣＵ†に対応する量子ゲートＣＵ†と、ユニタリ演算Ｒの複素共役Ｒ＊に対応する量子ゲートＲ＊とを生成し、量子ゲートＣＵ†と量子ゲートＲ＊とを接続して秘密鍵Ｓを生成する鍵生成装置が提供される。
【解決手段】発生させた乱数に基づき、ｎ量子ビットに対するｍ種類のユニタリ演算Ｕｉ（ｉ＝１〜ｍ）、及び、ｍ量子ビットに対する２種類のユニタリ演算Ｌ、Ｒに、それぞれ対応する量子ゲートＵｉ、Ｌ、Ｒを生成し、ｍ量子ビットの入力状態に応じて量子ゲートＵｉの動作が制御されるように制御化された量子ゲートＣＵを生成し、量子ゲートＣＵに量子ゲートＬ、Ｒを付加して量子ゲートＧを生成し、量子ゲートＧを難読化して公開鍵Ｐを生成し、量子ゲートＣＵに対応するユニタリ演算ＣＵのエルミート共役ＣＵ†に対応する量子ゲートＣＵ†と、ユニタリ演算Ｒの複素共役Ｒ＊に対応する量子ゲートＲ＊とを生成し、量子ゲートＣＵ†と量子ゲートＲ＊とを接続して秘密鍵Ｓを生成する鍵生成装置が提供される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、量子公開鍵暗号システム、鍵生成装置、暗号化装置、復号装置、鍵生成方法、暗号化方法、及び復号方法に関する。
【背景技術】
【０００２】
情報処理技術や通信技術の急速な発展に伴い、公文書、私文書を問わず、文書の電子化が急速に進んでいる。これに伴い、多くの個人や企業は、電子文書の安全管理に大きな関心を寄せている。こうした関心の高まりを受け、各方面で電子文書の盗聴や偽造等のタンパリング行為に対する安全性が盛んに議論されるようになってきた。電子文書の盗聴に対する安全性は、例えば、電子文書を暗号化することにより確保される。また、電子文書の偽造に対する安全性は、例えば、電子署名を利用することにより確保される。但し、暗号や電子署名には十分なタンパリング耐性が求められる。
【０００３】
現在広く利用されている公開鍵暗号は、古典的なコンピュータの計算量的複雑性を安全性の根拠としている。例えば、ＲＳＡ暗号は、「大きな合成数に対する素因数分解の困難性（以下、素因数分解問題）」を安全性の根拠としている。また、ＤＳＡ暗号やＥｌＧａｍａｌ暗号は、「離散対数問題に対する解答の困難性」を安全性の根拠としている。しかし、量子コンピュータは、素因数分解問題や離散対数問題に対する解答を効率的に算出することができると言われている。つまり、現在広く利用されている上記の暗号は、量子コンピュータが実用化されると、その安全性が保証されない。
【０００４】
なお、上記の「古典」という表現は、「量子」ではないという意味で用いている。また、「量子」という表現は、量子力学の原理に基づいているか、量子力学の原理を応用していることを意味している。例えば、量子コンピュータは、量子力学における重ね合わせの原理を応用した計算機である。また、ＢＢ８４等の量子鍵配送方式は、量子力学の不確定性原理を利用している。
【０００５】
こうした実状を背景に、量子コンピュータが実用化された際にも安全性が保証されるような公開鍵暗号系の研究が盛んに行われている。その一つの方向性は、量子コンピュータを用いても効率的に計算することが困難な問題（例えば、多変数多項式に対する解答の困難性）を安全性の根拠として古典通信路における公開鍵暗号系を実現しようとするものである。また、他の方向性は、量子通信路と量子演算とを用いて、量子コンピュータを用いた攻撃に対する安全性が保証されるような量子公開鍵暗号系を実現しようとするものである。例えば、下記の非特許文献１、特許文献１、２には、量子公開鍵暗号系に関する研究成果の一例が示されている。
【０００６】
非特許文献１、特許文献１に記載の量子公開鍵暗号系は、ナップサック問題の特殊な場合である部分和問題の計算量的な複雑性を安全性の根拠としている。この部分和問題とは、「与えられたｎ個の整数ａ１，…，ａｎから部分集合をうまく選び、その部分集合に属する数の和を、与えられた数Ｎに等しくすることができるか」を判定する問題である。この部分和問題は、計算量クラスＮＰ完全に属している。しかし、量子コンピュータを用いて部分和問題を解くことが極めて困難であるか否かは自明ではない。そのため、上記非特許文献１、特許文献１に記載の量子公開鍵暗号系は、量子コンピュータを用いた攻撃に対して必ずしも安全であるとは言えない。
【０００７】
また、特許文献１に記載の量子公開鍵暗号系は、量子状態を公開鍵として利用している。そのため、特許文献１に記載の量子公開鍵暗号系を利用すると、次のような問題が生じてしまう。通常、公開鍵暗号系で用いる公開鍵は認証局により認証を受ける。公開鍵が古典的に記述された情報（以下、古典情報）であれば、その公開鍵が確かに認証局による認証を受けたものであるか否かを検証できる。しかし、量子状態で表現された公開鍵（以下、量子公開鍵）に対する認証の有無を検証できるか否かは必ずしも自明ではない。例えば、量子状態は、測定により状態が変化してしまうため、量子公開鍵に対する認証の有無を検証すると、その量子公開鍵が公開鍵としての用を成さなくなる可能性がある。
【０００８】
一方、下記の特許文献２に記載の量子公開鍵暗号系は、量子状態と古典情報とを組み合わせたハイブリッド型の公開鍵（以下、ハイブリッド公開鍵）を利用している。ハイブリッド公開鍵は、古典情報の部分を含んでいる。そのため、古典情報の部分を利用して認証を行い、古典情報の部分を利用して認証の有無を検証することで、量子状態を攪乱せずに認証の有無を検証することが可能である。もちろん、量子状態に対する検証は行われない。しかし、量子状態が何らかの改竄を受けると、検証済みの古典情報との齟齬が生じるため、ハイブリッド公開鍵を用いた暗号化や秘密鍵を用いた復号に失敗する。従って、実際上、量子状態に対する検証が行われなくても問題はない。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特許第３６１５１３２号公報
【特許文献２】特開２００８−２９４６６６号公報
【非特許文献】
【００１０】
【非特許文献１】Ｔ． Ｏｋａｍｏｔｏ， Ｋ． Ｔａｎａｋａ， Ｓ． Ｕｃｈｉｙａｍａ． “Ｑｕａｎｔｕｍ Ｐｕｂｌｉｃ Ｋｅｙ Ｃｒｙｐｔｏｓｙｓｔｅｍｓ＆ｑｕｏｔ”，Ｐｒｏｃ． ｏｆ ＣＲＹＴＰＴＯ ２０００， ＬＮＣＳ １８８０，ｐｐ．１４７−ｐｐ．１６５， Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ（２０００）．
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかしながら、上記の特許文献２に記載のハイブリッド公開鍵は、やや利便性が低い。上記の通り、ハイブリッド公開鍵は、古典情報と量子状態との組み合わせで構成されている。つまり、配布される一つ一つの古典情報に対して個々に量子状態の鍵が対応する。従って、鍵生成に要するコストが増大してしまう。また、暗号化・復号の成否が復号処理の完了を待って確定されるため、暗号化・復号が失敗する場合、復号処理の完了まで余分な通信を行うこととなり、低効率化に繋がってしまう。以上説明した理由から、量子コンピュータによる攻撃に対して安全性が保証され、公開鍵の認証が可能であり、かつ、量子公開鍵暗号系の中で暗号化・復号処理の非効率化を招かないような仕組みが望まれている。
【００１２】
そこで、本発明は、上記問題に鑑みてなされたものであり、本発明の目的とするところは、より安全で利便性の高い量子公開鍵暗号系を実現することが可能な、新規かつ改良された量子公開鍵暗号システム、鍵生成装置、暗号化装置、復号装置、鍵生成方法、暗号化方法、及び復号方法を提供することにある。
【課題を解決するための手段】
【００１３】
上記課題を解決するために、本発明のある観点によれば、第１の量子情報処理装置と、量子通信路を介して前記第１の量子情報処理装置に接続された第２の量子情報処理装置と、古典通信路を介して前記第１及び第２の量子情報処理装置に接続された認証局と、を含み、前記第１の量子情報処理装置は、公開鍵と秘密鍵とを生成する鍵生成部と、前記鍵生成部により生成された公開鍵を、前記古典通信路を介して前記認証局に送信する第１古典送信部と、前記第２の量子情報処理装置から前記量子通信路を介して送信された、暗号化された量子状態を受信する第１量子受信部と、前記鍵生成部により生成された秘密鍵を用いて、前記第１量子受信部により受信された、前記暗号化された量子状態から元の量子状態を復元する復号部と、を有し、前記認証局は、前記第１の量子情報処理装置から前記古典通信路を介して送信された公開鍵を受信する第１古典受信部と、前記第１古典受信部により受信された公開鍵を認証する認証部と、前記認証部により認証された公開鍵を前記古典通信路を介して前記第２の量子情報処理装置に送信する第２古典送信部と、を有し、前記第２の量子情報処理装置は、前記認証局から前記古典通信路を介して送信された公開鍵を受信する第２古典受信部と、前記第２古典受信部により受信された公開鍵を用いて量子状態を暗号化する暗号化部と、前記暗号化部により暗号化された量子状態を前記量子通信路を介して前記第１の量子情報処理装置に送信する量子送信部と、を有する、量子公開鍵暗号システムが提供される。
【００１４】
また、前記鍵生成部は、乱数を発生させる乱数発生器と、前記乱数発生器を用いて発生させた乱数に基づき、ｎ量子ビットに対するｍ種類のユニタリ演算Ｕｉ（ｉ＝１〜ｍ）、及び、ｍ量子ビットに対する２種類のユニタリ演算Ｌ、Ｒに、それぞれ対応する量子プログラムＵｉ、Ｌ、Ｒを生成する量子プログラム生成部と、ｍ量子ビットの入力状態に応じて前記量子プログラムＵｉの動作が制御されるように制御化された量子プログラムＣＵを生成する量子プログラム制御化部と、前記量子プログラムＣＵに前記量子プログラムＬ、Ｒを付加して量子プログラムＧを生成する量子プログラム付加部と、前記量子プログラムＧを難読化して前記公開鍵に対応する量子プログラムＰを生成する量子プログラム難読化部と、前記量子プログラムＣＵに対応するユニタリ演算ＣＵのエルミート共役ＣＵ†に対応する量子プログラムＣＵ†と、前記ユニタリ演算Ｒの複素共役Ｒ＊に対応する量子プログラムＲ＊と、を生成する逆量子プログラム生成部と、前記量子プログラムＣＵ†と前記量子プログラムＲ＊とを接続して前記秘密鍵に対応する量子プログラムＳを生成する量子プログラム接続部と、を含んでいてもよい。
【００１５】
また、前記暗号化部は、量子コンピュータから成り、２ｍ量子ビットの最大エンタングルメント状態を生成し、当該２ｍ量子ビットの最大エンタングルメント状態のうち、ｍ量子ビットの量子状態と、送信すべきｎ量子ビットの量子状態｜ψｎ＞と、を前記公開鍵に対応する量子プログラムＰに入力して前記暗号化された量子状態を算出するように構成されていてもよい。
【００１６】
また、前記復号部は、量子コンピュータから成り、前記暗号化された量子状態を前記秘密鍵に対応する量子プログラムＳに入力して元の量子状態｜ψｎ＞を算出するように構成されていてもよい。
【００１７】
また、前記暗号化部は、２ｍ量子ビットの最大エンタングルメント状態を生成し、当該２ｍ量子ビットの最大エンタングルメント状態のうち、ｍ量子ビットの量子状態を保持しておき、残りｍ量子ビットの量子状態を、前記量子状態｜ψｎ＞と共に前記量子プログラムＰに入力し、前記量子状態｜ψｎ＞に対応する量子プログラムＰの出力に、保持しておいたｍ量子ビットの量子状態を付加して前記暗号化された量子状態を算出するように構成されていてもよい。
【００１８】
また、前記量子プログラム難読化部は、前記量子プログラムＧを、前記量子プログラムＧに対応するユニタリ演算と同じ演算内容を有する別の量子プログラムＧ’に置き換えることで前記量子プログラムＧを難読化するように構成されていてもよい。
【００１９】
また、前記量子プログラム難読化部は、前記量子プログラムＧの一部を成す部分量子プログラムｇを、当該部分量子プログラムｇと同じ演算内容を有する別の量子プログラムｇ’に置き換えることで前記量子プログラムＧを難読化するように構成されていてもよい。
【００２０】
また、上記課題を解決するために、本発明の別の観点によれば、乱数を発生させる乱数発生器と、前記乱数発生器を用いて発生させた乱数に基づき、ｎ量子ビットに対するｍ種類のユニタリ演算Ｕｉ（ｉ＝１〜ｍ）、及び、ｍ量子ビットに対する２種類のユニタリ演算Ｌ、Ｒに、それぞれ対応する量子プログラムＵｉ、Ｌ、Ｒを生成する量子プログラム生成部と、ｍ量子ビットの入力状態に応じて前記量子プログラムＵｉの動作が制御されるように制御化された量子プログラムＣＵを生成する量子プログラム制御化部と、前記量子プログラムＣＵに前記量子プログラムＬ、Ｒを付加して量子プログラムＧを生成する量子プログラム付加部と、前記量子プログラムＧを難読化して、公開鍵に対応する量子プログラムＰを生成する量子プログラム難読化部と、前記量子プログラムＣＵに対応するユニタリ演算ＣＵのエルミート共役ＣＵ†に対応する量子プログラムＣＵ†と、前記ユニタリ演算Ｒの複素共役Ｒ＊に対応する量子プログラムＲ＊と、を生成する逆量子プログラム生成部と、前記量子プログラムＣＵ†と前記量子プログラムＲ＊とを接続して、秘密鍵に対応する量子プログラムＳを生成する量子プログラム接続部と、を備える、鍵生成装置が提供される。
【００２１】
また、上記課題を解決するために、本発明の別の観点によれば、乱数を発生させる乱数発生器と、前記乱数発生器を用いて発生させた乱数に基づき、ｎ量子ビットに対するｍ種類のユニタリ演算Ｕｉ（ｉ＝１〜ｍ）、及び、ｍ量子ビットに対する２種類のユニタリ演算Ｌ、Ｒに、それぞれ対応する量子プログラムＵｉ、Ｌ、Ｒを生成する量子プログラム生成部と、ｍ量子ビットの入力状態に応じて前記量子プログラムＵｉの動作が制御されるように制御化された量子プログラムＣＵを生成する量子プログラム制御化部と、前記量子プログラムＣＵに前記量子プログラムＬ、Ｒを付加して量子プログラムＧを生成する量子プログラム付加部と、前記量子プログラムＧを難読化して、公開鍵に対応する量子プログラムＰを生成する量子プログラム難読化部と、を有する鍵生成装置により生成された公開鍵に対応する量子プログラムＰを保持する公開鍵保持部と、量子コンピュータを利用して、２ｍ量子ビットの最大エンタングルメント状態を生成するエンタングルメント状態生成部と、前記エンタングルメント状態生成部により生成された最大エンタングルメント状態と、送信すべきｎ量子ビットの量子状態と、を前記公開鍵に対応する量子プログラムＰに入力して前記暗号化された量子状態を算出する暗号化部と、を備える、暗号化装置が提供される。
【００２２】
また、上記課題を解決するために、本発明の別の観点によれば、乱数を発生させる乱数発生器と、前記乱数発生器を用いて発生させた乱数に基づき、ｎ量子ビットに対するｍ種類のユニタリ演算Ｕｉ（ｉ＝１〜ｍ）、及び、ｍ量子ビットに対する２種類のユニタリ演算Ｌ、Ｒに、それぞれ対応する量子プログラムＵｉ、Ｌ、Ｒを生成する量子プログラム生成部と、ｍ量子ビットの入力状態に応じて前記量子プログラムＵｉの動作が制御されるように制御化された量子プログラムＣＵを生成する量子プログラム制御化部と、前記量子プログラムＣＵに前記量子プログラムＬ、Ｒを付加して量子プログラムＧを生成する量子プログラム付加部と、前記量子プログラムＧを難読化して、公開鍵に対応する量子プログラムＰを生成する量子プログラム難読化部と、前記量子プログラムＣＵに対応するユニタリ演算ＣＵのエルミート共役ＣＵ†に対応する量子プログラムＣＵ†と、前記ユニタリ演算Ｒの複素共役Ｒ＊に対応する量子プログラムＲ＊と、を生成する逆量子プログラム生成部と、前記量子プログラムＣＵ†と前記量子プログラムＲ＊とを接続して、秘密鍵に対応する量子プログラムＳを生成する量子プログラム接続部と、を有する鍵生成装置により生成された秘密鍵に対応する量子プログラムＳを保持する秘密鍵保持部と、量子コンピュータを利用し、前記公開鍵に対応する量子プログラムＰを用いて生成された、暗号化された量子状態を前記秘密鍵に対応する量子プログラムＳに入力して元の量子状態を算出する復号部と、を備える、復号装置が提供される。
【００２３】
また、上記課題を解決するために、本発明の別の観点によれば、乱数を発生させる乱数発生ステップと、前記乱数発生ステップで発生させた乱数に基づき、ｎ量子ビットに対するｍ種類のユニタリ演算Ｕｉ（ｉ＝１〜ｍ）、及び、ｍ量子ビットに対する２種類のユニタリ演算Ｌ、Ｒに、それぞれ対応する量子プログラムＵｉ、Ｌ、Ｒを生成する量子プログラム生成ステップと、ｍ量子ビットの入力状態に応じて前記量子プログラムＵｉの動作が制御されるように制御化された量子プログラムＣＵを生成する量子プログラム制御化ステップと、前記量子プログラムＣＵに前記量子プログラムＬ、Ｒを付加して量子プログラムＧを生成する量子プログラム付加ステップと、前記量子プログラムＧを難読化して、公開鍵に対応する量子プログラムＰを生成する量子プログラム難読化ステップと、前記量子プログラムＣＵに対応するユニタリ演算ＣＵのエルミート共役ＣＵ†に対応する量子プログラムＣＵ†と、前記ユニタリ演算Ｒの複素共役Ｒ＊に対応する量子プログラムＲ＊と、を生成する逆量子プログラム生成ステップと、前記量子プログラムＣＵ†と前記量子プログラムＲ＊とを接続して、秘密鍵に対応する量子プログラムＳを生成する量子プログラム接続ステップと、を含む、鍵生成方法が提供される。
【００２４】
また、上記課題を解決するために、本発明の別の観点によれば、量子コンピュータを利用して、２ｍ量子ビットの最大エンタングルメント状態を生成するエンタングルメント状態生成ステップと、乱数を発生させる乱数発生器と、前記乱数発生器を用いて発生させた乱数に基づき、ｎ量子ビットに対するｍ種類のユニタリ演算Ｕｉ（ｉ＝１〜ｍ）、及び、ｍ量子ビットに対する２種類のユニタリ演算Ｌ、Ｒに、それぞれ対応する量子プログラムＵｉ、Ｌ、Ｒを生成する量子プログラム生成部と、ｍ量子ビットの入力状態に応じて前記量子プログラムＵｉの動作が制御されるように制御化された量子プログラムＣＵを生成する量子プログラム制御化部と、前記量子プログラムＣＵに前記量子プログラムＬ、Ｒを付加して量子プログラムＧを生成する量子プログラム付加部と、前記量子プログラムＧを難読化して、公開鍵に対応する量子プログラムＰを生成する量子プログラム難読化部と、を有する鍵生成装置により生成された公開鍵に対応する量子プログラムＰに対し、量子コンピュータを利用して、前記エンタングルメント状態生成ステップで生成された２ｍ量子ビットの最大エンタングルメント状態のうち、ｍ量子ビットの量子状態と、送信すべきｎ量子ビットの量子状態と、を入力して前記暗号化された量子状態を算出する暗号化ステップと、を含む、暗号化方法が提供される。
【００２５】
また、上記課題を解決するために、本発明の別の観点によれば、乱数を発生させる乱数発生器と、前記乱数発生器を用いて発生させた乱数に基づき、ｎ量子ビットに対するｍ種類のユニタリ演算Ｕｉ（ｉ＝１〜ｍ）、及び、ｍ量子ビットに対する２種類のユニタリ演算Ｌ、Ｒに、それぞれ対応する量子プログラムＵｉ、Ｌ、Ｒを生成する量子プログラム生成部と、ｍ量子ビットの入力状態に応じて前記量子プログラムＵｉの動作が制御されるように制御化された量子プログラムＣＵを生成する量子プログラム制御化部と、前記量子プログラムＣＵに前記量子プログラムＬ、Ｒを付加して量子プログラムＧを生成する量子プログラム付加部と、前記量子プログラムＧを難読化して、公開鍵に対応する量子プログラムＰを生成する量子プログラム難読化部と、前記量子プログラムＣＵに対応するユニタリ演算ＣＵのエルミート共役ＣＵ†に対応する量子プログラムＣＵ†と、前記ユニタリ演算Ｒの複素共役Ｒ＊に対応する量子プログラムＲ＊と、を生成する逆量子プログラム生成部と、前記量子プログラムＣＵ†と前記量子プログラムＲ＊とを接続して、秘密鍵に対応する量子プログラムＳを生成する量子プログラム接続部と、を有する鍵生成装置により生成された秘密鍵に対応する量子プログラムＳに対し、量子コンピュータを利用して、前記公開鍵に対応する量子プログラムＰを用いて生成された、暗号化された量子状態を入力して元の量子状態を算出する復号ステップを含む、復号方法が提供される。
【発明の効果】
【００２６】
以上説明したように本発明によれば、最大エンタングルメント状態の表現基底が非一意であるという性質を利用して、より安全で利便性の高い量子公開鍵暗号系が実現される。
【図面の簡単な説明】
【００２７】
【図１】本発明の一実施形態に係る量子公開鍵暗号システムの全体構成の一例を示す説明図である。
【図２】同実施形態に係る鍵生成装置の機能構成例を示す説明図である。
【図３】同実施形態に係る鍵生成方法における処理の流れを示す説明図である。
【図４】ユニバーサル量子回路の構築に利用する量子回路の一例を示す説明図である。
【図５】同実施形態に係る量子プログラム生成方法の一例を示す説明図である。
【図６】同実施形態に係る制御化方法の一例を示す説明図である。
【図７】同実施形態に係る量子プログラム付加方法の一例を示す説明図である。
【図８】同実施形態に係る難読化方法の一例を示す説明図である。
【図９】同実施形態に係る難読化方法の一例を示す説明図である。
【図１０】同実施形態に係る難読化方法の一例を示す説明図である。
【図１１】同実施形態に係る逆量子プログラムの生成方法の一例を示す説明図である。
【図１２】同実施形態に係る逆量子プログラムの接続方法の一例を示す説明図である。
【図１３】同実施形態に係る暗号化装置の機能構成例を示す説明図である。
【図１４】同実施形態に係る暗号化方法における処理の流れを示す説明図である。
【図１５】同実施形態に係る暗号化方法の一例を示す説明図である。
【図１６】同実施形態に係る復号装置の機能構成例を示す説明図である。
【図１７】同実施形態に係る復号方法における処理の流れを示す説明図である。
【図１８】同実施形態に係る復号方法の一例を示す説明図である。
【発明を実施するための形態】
【００２８】
以下に添付図面を参照しながら、本発明の好適な実施の形態について詳細に説明する。なお、本明細書及び図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。
【００２９】
［説明の流れについて］
ここで、以下に記載する本発明の実施形態に関する説明の流れについて簡単に述べる。まず、図１を参照しながら、本実施形態に係る量子公開鍵暗号システムの全体構成について説明する。次いで、図２を参照しながら、本実施形態に係る量子公開鍵暗号システムにおいて用いられる公開鍵、秘密鍵を生成するための鍵生成装置１００が有する機能構成について説明する。また、図３〜図１２を参照しながら、鍵生成装置１００により実行される鍵生成処理の流れ及び処理内容について説明する。
【００３０】
次いで、図１３を参照しながら、本実施形態に係る量子公開鍵暗号システムにおいて、送信すべき量子状態を暗号化するための暗号化装置２００の機能構成について説明する。また、図１４、図１５を参照しながら、暗号化装置２００により実行される暗号化処理の流れ及び処理内容について説明する。次いで、図１６を参照しながら、本実施形態に係る量子公開鍵暗号システムにおいて、暗号化された量子状態から元の量子状態を復号するための復号装置３００の機能構成について説明する。また、図１７、図１８を参照しながら、復号装置３００により実行される復号処理の流れ及び処理内容について説明する。
【００３１】
（説明項目）
１：量子公開鍵暗号システムの構成について
２：鍵生成方法について
２−１：鍵生成装置１００の機能構成
２−１−１：公開鍵生成部１１０の機能
２−１−２：秘密鍵生成部１３０の機能
２−２：鍵生成処理の詳細
２−２−１：公開鍵Ｐの生成方法
２−２−２：秘密鍵Ｓの生成方法
３：暗号化方法について
３−１：暗号化装置２００の機能構成
３−２：暗号化処理の詳細
４：復号方法について
４−１：復号装置３００の機能構成
４−２：復号処理の詳細
５：まとめ
【００３２】
＜１：量子公開鍵暗号システムの構成について＞
まず、図１を参照しながら、本発明の一実施形態に係る量子公開鍵暗号システムの全体像について説明する。図１は、本実施形態に係る量子公開鍵暗号システムの全体像、及び公開鍵認証・量子暗号文の送受信の流れについて説明するための説明図である。
【００３３】
図１に示すように、本実施形態に係る量子公開鍵暗号システムは、暗号文の受信者１０、暗号文の送信者２０、及び認証局３０により構成される。但し、暗号文の受信者１０は、説明の都合上、後述する鍵生成装置１００、復号装置３００を含む処理ブロックを擬人化したものである。同様に、暗号文の送信者２０は、説明の都合上、後述する暗号化装置２００を含む処理ブロックを擬人化したものである。また、認証局３０は、信頼できる第三者機関又は認証機関である。
【００３４】
（鍵生成→認証→暗号化→復号の流れ）
まず、暗号文の受信者１０は、公開鍵、秘密鍵のペアを生成する（Ｓｔｅｐ．１）。次いで、暗号文の受信者１０は、認証局３０に公開鍵を登録する。このとき、暗号文の受信者１０は、古典通信路を通じて公開鍵を認証局３０に送信する（Ｓｔｅｐ．２）。なお、本実施形態に係る量子公開鍵暗号システムで用いられる公開鍵は、後述するように古典情報のみで構成されている。また、秘密鍵は、暗号文の受信者１０により秘匿される。
【００３５】
次いで、認証局３０は、暗号文の受信者１０により登録された公開鍵を認証する（Ｓｔｅｐ．３）。次いで、認証局３０は、認証を与えた公開鍵を公開する。このとき、認証局３０は、古典通信路を通じて認証後の公開鍵を暗号文の送信者２０に送信する（Ｓｔｅｐ．４）。
【００３６】
暗号文の送信者２０は、古典通信路を通じて公開された公開鍵を入手すると、入手した公開鍵が認証済みのものか否かを検証する。そして、入手した公開鍵が認証済みであることを確認すると、暗号文の送信者２０は、量子コンピュータを利用し、その公開鍵を用いて暗号文を生成する（Ｓｔｅｐ．５）。
【００３７】
まず、暗号文の送信者２０は、送信したい古典情報を符号化して量子状態を生成するか、送信したい量子状態を用意する。次いで、暗号文の送信者２０は、最大エンタングルメント状態を生成する。次いで、暗号文の送信者２０は、生成又は用意した量子状態と、生成した最大エンタングルメント状態の一部とを公開鍵が示す量子プログラムの入力として与え、量子コンピュータにより暗号文（暗号化された量子状態）を生成する。
【００３８】
次いで、暗号文の送信者２０は、量子通信路を通じて、生成した暗号文を暗号文の受信者１０に送信する（Ｓｔｅｐ．６）。暗号文の受信者１０は、量子通信路を通じて受信した暗号文を秘密鍵が示す量子プログラムの入力として与え、量子コンピュータにより元の量子状態を復元する（Ｓｔｅｐ．７）。
【００３９】
以上説明したように、本実施形態に係る量子公開鍵暗号システムにおいて用いられる公開鍵は古典情報の形で記述された量子プログラムである。そのため、公開鍵が古典情報のみで記述されているため、公開鍵に対する認証の有無を容易に検証することができる。なお、暗号文の受信者１０による鍵生成（Ｓｔｅｐ．１）は、後述する鍵生成装置１００により実行される。また、暗号文の送信者２０による暗号文の生成（Ｓｔｅｐ．５）は、後述する暗号化装置２００により実行される。さらに、暗号文の受信者１０による復号（Ｓｔｅｐ．７）は、後述する復号装置３００により実行される。
【００４０】
（量子コンピュータのモデルについて）
上記の通り、本実施形態に係る量子公開鍵暗号システムは、暗号文の生成（Ｓｔｅｐ．５）、暗号文の復号（Ｓｔｅｐ．７）の際に量子コンピュータを用いる。また、本実施形態に係る公開鍵及び秘密鍵は、量子プログラムを示す古典情報である。そこで、本実施形態の説明を進めるにあたって、まず、量子コンピュータのモデル、及び量子プログラムの表現方法について概説する。
【００４１】
量子コンピュータは、量子プログラムと量子データとを入力とする。量子プログラムとは、量子アルゴリズムの実行方法を記述した古典情報である。一方、量子データとは、量子アルゴリズムの実行対象となる量子状態である。量子プログラムの表現方法は、利用する量子計算モデルにより異なる。
【００４２】
代表的な量子計算モデルとしては、例えば、量子回路モデル、量子チューリング機械モデル、観測ベース量子計算モデル等が知られている。量子回路モデルの場合、量子プログラムは、量子回路図を用いて表現される。量子チューリング機械モデルの場合、量子プログラムは、状態遷移図を用いて表現される。観測ベース量子計算モデルの場合、量子プログラムは、グラフ図を用いて表現される。以下の説明においては、量子回路モデルの表現を用いる。但し、量子回路モデルの違いは表現の違いであり、本実施形態の技術的範囲が量子回路モデルに限定されるものではない点に注意されたい。
【００４３】
なお、量子回路モデル、量子チューリング機械モデルについては、例えば、“Ｎｉｅｌｓｅｎ ａｎｄ Ｃｈｕａｎｇ， Ｑｕａｎｔｕｍ Ｃｏｍｐｕｔａｔｉｏｎ ａｎｄ Ｑｕａｎｔｕｍ Ｉｎｆｏｒｍａｔｉｏｎ，
Ｃａｍｂｒｉｄｇｅ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ”を参照されたい。また、観測ベース量子計算モデルについては、例えば、“Ｒ． Ｒａｕｓｓｅｎｄｏｒｆ ａｎｄ Ｈ． Ｊ． Ｂｒｉｅｇｅｌ， Ｐｈｙｓ． Ｒｅｖ． Ｌｅｔｔ．，
８６（５１８８）， ２００１．”を参照されたい。
【００４４】
以上、本実施形態に係る量子公開鍵暗号システムの全体像について説明した。以下では、本実施形態に係る公開鍵暗号システムにおける鍵生成方法、暗号化方法、復号方法について、順次、より詳細に説明する。
【００４５】
＜２：鍵生成方法について＞
まず、本実施形態に係る鍵生成方法について説明する。本実施形態に係る鍵生成方法により生成される公開鍵及び秘密鍵は、量子プログラムで表現される。量子プログラムとは、量子コンピュータにより実行されるユニタリ演算の組み合わせで表現された設計図である。上記の通り、量子プログラムの表現は幾通りも存在するが、本稿では一例として量子回路モデルの表現方法（以下、量子回路図）を採用する。
【００４６】
量子回路図は、例えば、図４に示すような量子回路を組み合わせて設計される。量子回路図に含まれる量子回路は、ユニタリ演算の表現である。なお、以下の説明では、量子回路のことを量子プログラムと表現する場合がある。さらに、ユニタリ演算と、そのユニタリ演算を実行する量子プログラムとを同一視し、同じ記号で表現する。例えば、ユニタリ演算Ｕ、Ｖの積ＵＶに関し、ユニタリ演算Ｕ、Ｖに対応する量子プログラムをＵ、Ｖと表現し、それらの積ＵＶに対応する量子プログラムをＵＶと表現する。
【００４７】
なお、量子プログラムで表現されるユニタリ演算の実現方法としては、例えば、古典的なコンピュータによる量子コンピュータのエミュレータを用いる方法、イオントラップ、キャビティＱＥＤ、ＮＭＲ、超伝導体、光学系等を用いた量子コンピュータを用いる方法等、様々な方法が考えられる。また、後述する本実施形態に係る暗号化方法、復号方法の実現に用いられる量子コンピュータは、いずれの動作原理に基づいてユニタリ演算を実行するものであってもよいし、将来新たに考案された他の動作原理に基づくユニタリ演算の実行手段であってもよい。
【００４８】
［２−１：鍵生成装置１００の機能構成］
以下、図２を参照しながら、本実施形態に係る鍵生成方法を実現するための鍵生成装置１００の機能構成について説明する。図２は、本実施形態に係る鍵生成装置１００の機能構成例を示す説明図である。
【００４９】
図２に示すように、鍵生成装置１００は、主に、公開鍵生成部１１０、及び秘密鍵生成部１３０により構成される。公開鍵生成部１１０は、公開鍵Ｐ（量子プログラムＰ）を生成する処理ブロックである。一方、秘密鍵生成部１３０は、秘密鍵Ｓ（量子プログラムＳ）を生成する処理ブロックである。以下、量子回路図を用いて各処理ブロックの機能について、より詳細に説明する。
【００５０】
なお、ここでは一例として量子回路図を用いるが、本実施形態の技術的範囲は量子回路モデルに限定されない。例えば、後述する量子回路図を構成するユニバーサル量子回路をグラフ図に置き換えることにより、量子回路モデルに基づく構成を観測ベース量子計算モデルに基づく構成に変形することができる。
【００５１】
このような変形を行っても、本実施形態に係る鍵生成処理の内容に影響を与えることはない。また、ユニバーサル量子回路をグラフ図に変換するのではなく、後述するユニバーサル量子回路の構築方法と同様の操作ステップを経てグラフ図を構築することでグラフ図に基づく鍵生成方法を実現することができる。
【００５２】
（２−１−１：公開鍵生成部１１０の機能）
まず、公開鍵生成部１１０の機能構成について説明する。
【００５３】
図２に示すように、公開鍵生成部１１０は、主に、乱数発生部１１２と、量子プログラム生成部１１４と、制御化部１１６と、量子プログラム付加部１１８と、難読化部１２０とにより構成される。以下、公開鍵の生成過程に沿って各構成要素の機能を説明する。
【００５４】
（乱数発生部１１２の機能）
まず、乱数発生部１１２は、乱数発生器を用いて乱数列を生成する。乱数発生器としては、例えば、熱雑音を利用した物理乱数発生器や、メルセンヌツイスター法等に基づく疑似乱数発生器等が利用される。乱数列を生成すると、乱数発生部１１２は、生成した乱数列を量子プログラム生成部１１４に入力する。
【００５５】
（量子プログラム生成部１１４の機能）
量子プログラム生成部１１４は、ｎ量子ビットの量子状態を入力とするユニタリ演算Ｕ１，…，Ｕｍの量子プログラムＵ１，…，Ｕｍと、ｍ量子ビットの量子状態を入力とするユニタリ演算Ｌ、Ｒの量子プログラムＬ、Ｒとを生成する。このとき、量子プログラム生成部１１４は、乱数発生部１１２により入力された乱数列を利用し、予め用意されたユニバーサル量子回路と呼ばれる数種類の量子回路をランダムに組み合わせて量子プログラムＵ１，…，Ｕｍ、Ｌ、Ｒを生成する。
【００５６】
ここで、図４、図５を参照しつつ、量子プログラム生成部１１４による量子プログラムＸ（Ｘ＝Ｕ１，…，Ｕｍ、Ｌ、Ｒ）の生成方法について、より具体的に説明する。
【００５７】
図４には、量子プログラムＸの生成に用いるユニバーサル量子回路の例が示されている。この例では、１量子ビットに対するアダマール回路Ｈ、１量子ビットに対するπ／８位相シフト回路Ｔ、１量子ビットに対する位相回路Ｓ、２量子ビットに対する制御ＮＯＴ回路ＣＮが量子プログラムＸの生成に用いるユニバーサル量子回路として利用される。また、量子プログラムＸの生成には、π／８位相シフト回路Ｔに対応するユニタリ演算Ｔのエルミート共役Ｈ†に対応するエルミート共役π／８位相シフト回路Ｔ†、位相回路Ｓに対応するユニタリ演算Ｓのエルミート共役Ｓ†に対応するエルミート共役位相回路Ｓ†が利用される。
【００５８】
また、ユニバーサル量子回路Ｈ、Ｔ、Ｓ、ＣＮには、図４に示すように、互いに異なる数字が予め割り当てられる。さらに、エルミート共役が元のユニバーサル量子回路と異なる場合、そのユニバーサル量子回路のエルミート共役Ｔ†、Ｓ†にも、互いに異なる数字が予め割り当てられる。
【００５９】
図４の例では、アダマール回路Ｈに０、π／８位相シフト回路Ｔに１、エルミート共役π／８位相シフト回路Ｔ†に２、位相回路Ｓに３、エルミート共役位相回路Ｓ†に４、制御ＮＯＴ回路ＣＮに５が割り当てられている。量子プログラム生成部１１４は、これらのユニバーサル量子回路を組み合わせて量子プログラムＸを生成する。ユニバーサル量子回路の組み合わせは、図５に示す方法により決定される。
【００６０】
なお、ここでは具体例として３本の量子レジスタ（量子レジスタ１〜３）を含む量子プログラムＸを生成する方法について考える。まず、量子プログラム生成部１１４は、０〜５の数字を乱数発生部１１２に生成させ、乱数発生部１１２から入力された数字を用いてユニバーサル量子回路を１つ選択する（Ｓｔｅｐ．１）。例えば、乱数発生部１１２から０が入力された場合、量子プログラム生成部１１４は、０が割り当てられたアダマール回路Ｈを選択する。
【００６１】
Ｓｔｅｐ．１で選択したユニバーサル量子回路が１量子ビットに対する量子回路である場合、量子プログラム生成部１１４は、１〜３の数字を乱数発生部１１２に１つ生成させ、乱数発生部１１２から入力された数字を用いてユニバーサル量子回路を配置する量子レジスタを選択する（Ｓｔｅｐ．２）。
【００６２】
一方、Ｓｔｅｐ．１で選択したユニバーサル量子回路が２量子ビットに対する量子回路である場合、量子プログラム生成部１１４は、１〜３の数字を乱数発生部１１２に２つ生成させ、乱数発生部１１２から入力された数字を用いてユニバーサル量子回路を配置する量子レジスタを選択する（Ｓｔｅｐ．２）。
【００６３】
例えば、Ｓｔｅｐ．１で制御ＮＯＴ回路ＣＮを選択した場合、量子プログラム生成部１１４は、乱数発生部１１２から最初に入力された数字に対応する量子レジスタを制御レジスタに設定し、次に入力された数字に対応する量子レジスタをターゲットレジスタに設定して、制御ＮＯＴ回路ＣＮを配置する。但し、乱数発生部１１２から同じ数字が２つ入力された場合、量子プログラム生成部１１４は、乱数発生部１１２に再び乱数を生成させる。
【００６４】
量子プログラム生成部１１４は、上記のＳｔｅｐ．１、Ｓｔｅｐ．２の操作をｎの多項式関数ｐ（ｎ）回程度繰り返し、乱数発生部１１２から入力される乱数列に基づいてユニバーサル量子回路を順次量子レジスタに配置して量子プログラムＸを生成する。上記の例では量子レジスタの数を３としたが、量子プログラム生成部１１４の機能はこれに限定されない。なお、図５は、上記のＳｔｅｐ．１、Ｓｔｅｐ．２の操作を５回繰り返して得られた量子プログラムＸの一例である。
【００６５】
量子プログラム生成部１１４は、上記の方法を繰り返し実行し、量子プログラムＵ１，…，Ｕｍ、Ｌ、Ｒを生成する。但し、ｎ量子ビットに対する量子プログラムＵ１，…，Ｕｍは、ｎ本の量子レジスタにより構成される。また、ｍ量子ビットに対する量子プログラムＬ、Ｒは、ｍ本の量子レジスタにより構成される。
【００６６】
このようにして量子プログラム生成部１１４により生成された量子プログラムＵ１，…，Ｕｍは、図２に示すように、制御化部１１６に入力される。また、量子プログラム生成部１１４により生成された量子プログラムＬ、Ｒは、量子プログラム付加部１１８に入力される。さらに、量子プログラム生成部１１４により生成された量子プログラムＲは、後述する秘密鍵生成部１３０の逆量子プログラム生成部１３２に入力される。
【００６７】
（制御化部１１６の機能）
制御化部１１６は、量子プログラム生成部１１４から入力された量子プログラムＵ１，…，Ｕｍを制御化して量子プログラムＣＵを生成する。ここで言う制御化とは、ｍ本の制御レジスタに入力される量子状態に応じて、演算に利用される量子プログラムＵ１，…，Ｕｍを選択できるようにすることを意味する。量子プログラムＣＵは、例えば、図６に示す量子回路図で表現される。
【００６８】
図６に示すように、量子プログラムＣＵは、ｍ＋ｎ本の量子レジスタを含む。そして、ｍ＋ｎ本の量子レジスタのうち、ｍ本の量子レジスタは、量子プログラムＵ１，…，Ｕｍの選択に利用される制御レジスタ（制御レジスタ１〜ｍ）である。また、残りｎ本の量子レジスタは、量子プログラムＵ１，…，Ｕｍが配置されるデータレジスタである。なお、量子プログラムＣＵの処理は、左側から右側に向かって進行する。また、各量子レジスタには、それぞれ１量子ビットの量子状態が入力される。
【００６９】
図６の例では、データレジスタ上に、左側から右側に向かって量子プログラムＵ１，…，Ｕｍが順に配置されている。そして、量子プログラムＵ１には制御レジスタ１が接続され、量子プログラムＵ２には制御レジスタ２が接続され、量子プログラムＵ３には制御レジスタ３が接続され、…、量子プログラムＵｍには制御レジスタｍが接続されている。そして、量子プログラムＵ１を含む回路を第１量子ビット制御Ｕ１回路、量子プログラムＵ２を含む回路を第２量子ビット制御Ｕ２回路、量子プログラムＵ３を含む回路を第３量子ビット制御Ｕ３回路、…、量子プログラムＵｍを含む回路を第ｍ量子ビット制御Ｕｍ回路と呼ぶことにする。
【００７０】
量子プログラムＣＵは、制御レジスタ１に１量子ビットの量子状態｜１＞が入力された場合、データレジスタに入力された量子状態に対して量子プログラムＵ１が実行されるように構成されている。同様に、量子プログラムＣＵは、制御レジスタｋ（ｋ＝２〜ｍ）に１量子ビットの量子状態｜１＞が入力された場合、データレジスタに入力された量子状態に対して量子プログラムＵｋが実行されるように構成されている。
【００７１】
そのため、データレジスタに入力された量子状態に対して実行される量子プログラムＵ１，…，Ｕｍの組み合わせは、制御レジスタ１〜ｍに入力される量子状態により制御される。なお、制御レジスタｋ’（ｋ’＝１〜ｍ）に量子状態｜０＞が入力された場合には、データレジスタに入力された量子状態に対して量子プログラムＵｋ’が実行されない。
【００７２】
このような制御化された量子プログラムＣＵは、次のようにして生成される。上記の通り、量子プログラム生成部１１４により生成された量子プログラムＵ１は、ユニバーサル量子回路で構成されている。
【００７３】
ユニバーサル量子回路を第１量子ビット制御Ｕ１回路のように制御化する方法は、“Ｎｉｅｌｓｅｎ ａｎｄ Ｃｈｕａｎｇ， Ｑｕａｎｔｕｍ Ｃｏｍｐｕｔａｔｉｏｎ ａｎｄ Ｑｕａｎｔｕｍ Ｉｎｆｏｒｍａｔｉｏｎ，
Ｃａｍｂｒｉｄｇｅ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ”に記載されている。そこで、この方法を量子プログラムＵ１に含まれる全てのユニバーサル量子回路に適用し、制御レジスタ１に対して全てのユニバーサル量子回路を制御化することで、第１量子ビット制御Ｕ１回路が生成される。同様に、第ｋ量子ビット制御Ｕｋ回路（ｋ＝２〜ｍ）が生成される。
【００７４】
このようにして制御化部１１６により生成された量子プログラムＣＵは、図２に示すように、量子プログラム付加部１１８に入力される。また、この量子プログラムＣＵは、後述する秘密鍵生成部１３０の逆量子プログラム生成部１３２に入力される。
【００７５】
（量子プログラム付加部１１８の機能）
上記の通り、量子プログラム付加部１１８には、量子プログラム生成部１１４により生成された量子プログラムＬ、Ｒ、及び制御化部１１６により生成された量子プログラムＣＵが入力される。量子プログラム付加部１１８は、量子プログラムＣＵに対して量子プログラムＬ、Ｒを付加し、図７に示すような量子プログラムＧを生成する。
【００７６】
まず、量子プログラム付加部１１８は、量子プログラムＲを第１量子ビット制御Ｕ１回路の前段に配置する。このとき、量子プログラム付加部１１８は、制御レジスタ１〜ｍへの入力が量子プログラムＲへの入力となり、量子プログラムＲの出力が量子プログラムＣＵの制御レジスタ１〜ｍへの入力となるように量子プログラムＲを配置する。
【００７７】
次に、量子プログラム付加部１１８は、量子プログラムＬを第ｍ量子ビット制御Ｕｍ回路の後段に配置する。このとき、量子プログラム付加部１１８は、量子プログラムＣＵの制御レジスタ１〜ｍへの入力が量子プログラムＬの入力となるように量子プログラムＬを配置する。
【００７８】
ここで、量子プログラムＣＵに量子プログラムＲ、Ｌを付加する意義について述べる。
【００７９】
例えば、量子プログラムＣＵに含まれる量子プログラムＵｋを実行させる場合、量子プログラムＣＵの制御レジスタｋに１量子ビットの量子状態｜１＞を入力する必要がある。そのため、量子プログラムＲの実行後に量子プログラムＣＵの制御レジスタｋに対して量子状態｜１＞が入力されるよう、量子プログラムＲの入力を制御する必要がある。
【００８０】
量子プログラムＲの回路構成を知っている者は、量子プログラムＲの入力を適切に制御して量子プログラムＣＵの制御レジスタｋに量子状態｜１＞を入力することができる。しかし、量子プログラムＲの回路構成を知らない者は、量子プログラムＣＵの制御レジスタｋに量子状態｜１＞を入力することができない。
【００８１】
つまり、量子プログラムＲを知らない者は、量子プログラムＣＵに含まれる量子プログラムＵｋを指定するために、どのような量子状態を量子プログラムＧに入力すればよいかが分からない。言い換えると、量子プログラムＲを付加する意義は、量子プログラムＣＵに含まれる量子プログラムＵｋの指定方法を隠蔽することにある。
【００８２】
一方、量子プログラムＬを付加する意義は、量子プログラムＲの秘匿性を高めることにある。仮に、量子プログラムＣＵが特徴的な構造を有する場合、量子プログラムＬを付加しないと、後述する難読化後に得られる量子プログラムＧの情報から量子プログラムＲが分離されてしまう恐れがある。そのため、量子プログラムＣＵに対して量子プログラムＲ、Ｌが付加される。
【００８３】
このようにして量子プログラム付加部１１８により生成された量子プログラムＧは、難読化部１２０に入力される。
【００８４】
（難読化部１２０の機能）
難読化部１２０は、図８に示すように、量子プログラム付加部１１８から入力された量子プログラムＧを別の量子プログラムＰへと変換（難読化）する。この量子プログラムＰは、量子プログラムＧに対応するユニタリ演算Ｇと同じ内容を有するユニタリ演算Ｐに対応する。
【００８５】
つまり、難読化部１２０は、ユニタリ演算の内容を変えずに量子プログラムＧを量子プログラムＰに変換する。この変換により量子プログラムＰから量子プログラムＲの情報を得ることが困難になる。その結果、量子プログラムＣＵの情報が秘匿される。難読化部１２０は、公開鍵Ｐとして量子プログラムＰを出力する。
【００８６】
ここで、図９、図１０を参照しながら、上記の難読化の方法について、より詳細に説明する。なお、ここでは多項式関数ｐ（ｎ）個程度のユニバーサル量子回路で構成される量子プログラムＵに対する難読化の方法について説明する。
【００８７】
まず、難読化部１２０は、量子プログラムＵを構成するユニバーサル量子回路を全て左側に詰める。この操作を行うことにより、同時に実行可能なユニバーサル量子回路の組が区別し易くなる。
【００８８】
次いで、難読化部１２０は、図９に示すように、同時実行可能なユニバーサル量子回路の組み合わせに対して個々に数字を割り当てる（ラベリング；Ｓｔｅｐ．１）。このとき、同時実行可能なユニバーサル量子回路の組み合わせは、各量子レジスタに対して１つ程度になる。
【００８９】
そのため、難読化部１２０は、量子レジスタの番号（以下、レジスタ番号）と、同時実行可能なユニバーサル量子回路の組み合わせに割り当てた番号（以下、組み合わせ番号）とを指定することにより、図１０に示すように、１つのユニバーサル量子回路を指定できるようになる。
【００９０】
次いで、難読化部１２０は、乱数発生器を利用して乱数ｒを発生させる。但し、乱数ｒは、１から組み合わせ番号の最大数までの数字である。そして、難読化部１２０は、乱数ｒに等しい組み合わせ番号に対応するユニバーサル量子回路の組を１つ指定する。次いで、難読化部１２０は、１〜ｎの乱数を発生させる乱数発生器を用いてｓ＝ｌｏｇ（ｎ）個程度の乱数列（ｒ１，ｒ２，…，ｒｓ）を発生させる。
【００９１】
次いで、難読化部１２０は、発生させた乱数列を用いて、指定した組に含まれるユニバーサル量子回路（ｒ，ｒｉ）＝｛（ｒ，ｒ１），（ｒ，ｒ２），…，（ｒ，ｒｓ）｝を指定する。但し、難読化部１２０は、指定した位置にユニバーサル量子回路が存在しない場合、その位置を無視する。また、難読化部１２０は、指定した位置の全てにユニバーサル量子回路が存在しない場合、乱数発生器を用いて乱数列を再度発生させる。
【００９２】
次いで、難読化部１２０は、指定したユニバーサル量子回路について、時間が正の方向に隣り合うユニバーサル量子回路を順次グループに加える。但し、難読化部１２０は、ユニバーサル量子回路をグループに加える過程で、制御ＮＯＴ回路ＣＮの制御部又はターゲット部のいずれか一方が、指定した量子レジスタの組（ｒ１，ｒ２，…，ｒｓ）とは異なる量子レジスタｒｓ＋１を指定する場合、その量子レジスタｒｓ＋１を新たに量子レジスタの組に加えて新たな量子レジスタの組（ｒ１，ｒ２，…，ｒｓ，ｒｓ＋１）を生成する。
【００９３】
そして、難読化部１２０は、新たな量子レジスタの組（ｒ１，ｒ２，…，ｒｓ，ｒｓ＋１）を対象として、時間が正の方向に隣り合うユニバーサル量子回路を順次グループに加える。難読化部１２０は、ユニバーサル量子回路の合計がｌｏｇ Ｏ（ｐ（ｎ））程度になるまでグループにユニバーサル量子回路を加え続ける。
【００９４】
このようにして生成されたユニバーサル量子回路の組［｛（ｒ，ｒｉ）｝，｛（ｒ，ｒｊ）｝，…，｛（ｒ，ｒｋ）｝］を部分量子プログラムｇと呼ぶことにする。上記の方法により、難読化部１２０は、量子プログラムＵの中から部分量子プログラムｇを選択する（Ｓｔｅｐ．２）。
【００９５】
なお、部分量子プログラムｇを選択する過程で、ユニバーサル量子回路の選択に任意性がある場合には乱数を用いて選択するものとする。次に、難読化部１２０は、選択した部分量子プログラムｇを、その部分量子プログラムｇにより表現されるユニタリ演算ｇを変更せずに、別の等価な部分量子プログラムｇ’に置き換える。
【００９６】
例えば、難読化部１２０は、部分量子プログラムｇに等価な部分量子プログラムの全数検索を実施し、検出された部分量子プログラムの中からランダムに１つの部分量子プログラムｇ’を選択する。
【００９７】
この例では、量子プログラムＵに含まれるユニバーサル量子回路の数がｌｏｇ Ｏ（ｐ（ｎ））程度であるため、置き換え可能な部分量子プログラムの表現は、Ｏ（ｐ（ｎ））以下となる。従って、部分量子プログラムの全数検索は、多項式時間以内に終了する。なお、置き換え可能な部分量子プログラムが存在しない場合には、ユニバーサル量子回路の数をｌｏｇ Ｏ（ｐ（ｎ））＋２程度に拡張すればよい。
【００９８】
上記の処理を多項式回数だが十分に繰り返すことにより、量子プログラムＧの難読化が実現される。なお、上記の難読化で、量子プログラムＲと量子プログラムＣＵとを跨ぐ部分の部分量子プログラムがｎの多項式回数だが十分な回数行われることが望ましい。
【００９９】
（難読化により実現される計算量的複雑性について）
これまで説明してきた通り、本実施形態に係る量子公開鍵暗号システムは、量子プログラムＲを取り出すことの困難性を安全性の根拠としている。逆に言えば、盗聴者は、量子プログラムＲを取り出すことができれば量子公開鍵暗号システムを破ることができる。本実施形態に係る量子公開鍵暗号システムにおいて、量子プログラムＲを取り出すことの困難性は上記の難読化により実現されている。本実施形態に係る難読化方法を用いると、量子プログラムに高い計算量的複雑性が実現される。
【０１００】
本実施形態に係る難読化方法を用いて生成された量子プログラムＰから量子プログラムＲを取り出す盗聴者の攻撃は、量子計算量的複雑性クラスＱｕａｎｔｕｍ Ｍｅｒｌｉｎ Ａｒｔｈｕｒ困難（ＱＭＡ困難）に属する。なお、本実施形態に係る難読化方法は任意の量子プログラムにも適用可能である。
【０１０１】
また、量子プログラムＰに加え、盗聴者以外の者が送信した暗号文を盗聴者が取得し、これらの情報から量子プログラムＲを取り出そうと試みるのではないか、と考えるかもしれない。しかし、このような攻撃は意味がない。なぜなら、盗聴者自身も公開鍵Ｐである量子プログラムＰを用いて任意の量子状態を暗号化できるからである。
【０１０２】
つまり、量子プログラムＰと暗号文との組み合わせから量子プログラムＲを取り出す攻撃は、量子プログラムＰから量子プログラムＲを取り出す攻撃と等価である。このように、本実施形態に係る難読化方法を適用することにより、高い安全性が保証される。
【０１０３】
以上、公開鍵生成部１１０の機能について説明した。
【０１０４】
（２−１−２：秘密鍵生成部１３０の機能）
次に、秘密鍵生成部１３０の機能について説明する。
【０１０５】
図２に示すように、秘密鍵生成部１３０は、主に、逆量子プログラム生成部１３２と、接続部１３４とにより構成される。以下、秘密鍵の生成過程に沿って各構成要素の機能を説明する。
【０１０６】
（逆量子プログラム生成部１３２の機能）
公開鍵生成部１１０の説明において述べた通り、逆量子プログラム生成部１３２には、量子プログラム生成部１１４により生成された量子プログラムＲ、及び制御化部１１６により生成された量子プログラムＣＵが入力される。
【０１０７】
まず、逆量子プログラム生成部１３２は、量子プログラムＲに対応するユニタリ演算Ｒの複素共役Ｒ＊に対応する量子プログラムＲ＊を生成する。また、逆量子プログラム生成部１３２は、量子プログラムＣＵに対応するユニタリ演算ＣＵのエルミート共役ＣＵ†に対応する量子プログラムＣＵ†を生成する。これら量子プログラムＲ＊、ＣＵ†の生成は、図１１のようにして実行される。
【０１０８】
図１１には、ユニバーサル量子回路Ａ、Ｂ、Ｃ、Ｄが左側から右側へと配置された量子プログラムＹに対する複素共役化及びエルミート共役化の方法が例示されている。
【０１０９】
量子プログラムＹをエルミート共役化する場合、逆量子プログラム生成部１３２は、まず、ユニバーサル量子回路Ａ、Ｂ、Ｃ、Ｄの並び順を逆に並べ替え、ユニバーサル量子回路Ｄ、Ｃ、Ｂ、Ａの順で左側から右側へと配置する。次いで、逆量子プログラム生成部１３２は、個々のユニバーサル量子回路Ａ、Ｂ、Ｃ、Ｄをそれぞれエルミート共役化したユニバーサル量子回路Ａ†、Ｂ†、Ｃ†、Ｄ†に置き換える。その結果、量子プログラムＹをエルミート共役化した量子プログラムＹ†が得られる。
【０１１０】
また、量子プログラムＹを複素共役化する場合、逆量子プログラム生成部１３２は、量子プログラムＹを構成するユニバーサル量子回路Ａ、Ｂ、Ｃ、Ｄを複素共役化したユニバーサル量子回路Ａ＊、Ｂ＊、Ｃ＊、Ｄ＊に置き換える。その結果、量子プログラムＹを複素共役化した量子プログラムＹ＊が得られる。
【０１１１】
なお、転置化した量子プログラムＹＴは、ユニバーサル量子回路Ａ、Ｂ、Ｃ、Ｄの並び順を逆にした後、ユニバーサル量子回路Ａ、Ｂ、Ｃ、Ｄをそれぞれ転置化したユニバーサル量子回路ＡＴ、ＢＴ、ＣＴ、ＤＴに置き換えることにより生成される。これらの各演算過程は、多項式関数ｐ（ｎ）個のユニバーサル量子回路で構成される量子プログラムに対し、２ｐ（ｎ）回程度の演算で完了する。
【０１１２】
このようにして逆量子プログラム生成部１３２により生成された量子プログラムＣＵ†、Ｒ＊は、接続部１３４に入力される。なお、量子プログラムＣＵ†は、量子プログラムＣＵの逆ユニタリ演算を実行するための量子プログラムである。また、量子プログラムＲ＊は、量子プログラムＲＴの逆ユニタリ演算を実行するための量子プログラムである。
【０１１３】
（接続部１３４の機能）
接続部１３４は、図１２に示すように、逆量子プログラム生成部１３２により生成された量子プログラムＣＵ†、Ｒ＊を接続して量子プログラムＳを生成する。このとき、接続部１３４は、量子プログラムＣＵ†の前段に量子プログラムＲ＊を配置する。また、接続部１３４は、量子プログラムＲ＊の出力が量子プログラムＣＵ†の制御レジスタ１〜ｍの入力となるように量子プログラムＲ＊と量子プログラムＣＵ†とを接続する。そして、接続部１３４は、秘密鍵Ｓとして量子プログラムＳを出力する。
【０１１４】
以上、秘密鍵生成部１３０の機能について説明した。
【０１１５】
以上説明した通り、鍵生成装置１００は、古典情報で記述される量子プログラムＰ、Ｓをそれぞれ公開鍵Ｐ、秘密鍵Ｓとして出力する。このように、公開鍵Ｐが古典情報で記述されているため、公開鍵Ｐの同定を行っても暗号鍵としての利用可能性を失わずに済む。また、量子プログラムＰが本実施形態に係る難読化方法で難読化されているため、量子コンピュータを用いた攻撃に対しても極めて高い安全性が保証される。
【０１１６】
［２−２：鍵生成処理の詳細］
次に、図３を参照しながら、本実施形態に係る鍵生成処理の流れについて説明する。図３は、本実施形態に係る鍵生成処理の流れを示す説明図である。なお、図３に示した鍵生成処理の各処理ステップは、上記の鍵生成装置１００により実行される。
【０１１７】
（２−２−１：公開鍵Ｐの生成方法）
まず、公開鍵Ｐの生成方法に係る処理の流れについて説明する。ここで説明する処理は、上記の公開鍵生成部１１０により実行される。
【０１１８】
公開鍵の生成処理がスタートすると、公開鍵生成部１１０は、まず、乱数発生部１１２の機能により乱数を発生させる（Ｓ１０２）。次いで、公開鍵生成部１１０は、発生した乱数列を利用して、量子プログラム生成部１１４の機能によりｍ個の量子プログラムＵ１，…，Ｕｍ、及び２個の量子プログラムＬ、Ｒを生成する（Ｓ１０４）。
【０１１９】
ステップＳ１０４にて生成されたｍ個の量子プログラムＵ１，…，Ｕｍは、次のステップＳ１０６の処理にて利用される。また、ステップＳ１０４にて生成された量子プログラムＬ、Ｒは、後段のステップＳ１０８にて利用される。さらに、ステップＳ１０４にて生成された量子プログラムＲは、秘密鍵生成方法に係る処理のステップＳ１１２にて利用される。
【０１２０】
ステップＳ１０６に処理が進行すると、公開鍵生成部１１０は、ステップＳ１０４で生成されたｍ個の量子プログラムＵ１，…，Ｕｍを利用し、制御化部１１６の機能により制御化された量子プログラムＣＵを生成する（Ｓ１０６）。ステップＳ１０６にて生成された量子プログラムＣＵは、次のステップＳ１０８、及び秘密鍵生成方法に係る処理のステップＳ１１２にて利用される。
【０１２１】
次いで、公開鍵生成部１１０は、ステップＳ１０４にて生成された量子プログラムＬ、Ｒ、及びステップＳ１０６にて生成された量子プログラムＣＵを利用し、量子プログラム付加部１１８の機能により量子プログラムＧを生成する（Ｓ１０８）。ステップＳ１０８にて生成された量子プログラムＧは、次のステップＳ１１０にて利用される。
【０１２２】
次いで、公開鍵生成部１１０は、難読化部１２０の機能によりステップＳ１０８にて生成された量子プログラムＧを難読化し、量子プログラムＰを生成する（Ｓ１１０）。ステップＳ１１０にて生成された量子プログラムＰは、公開鍵Ｐとして出力される。
【０１２３】
以上、公開鍵Ｐの生成方法に係る処理の流れについて説明した。
【０１２４】
（２−２−２：秘密鍵Ｓの生成方法）
次に、秘密鍵Ｓの生成方法に係る処理の流れについて説明する。ここで説明する処理は、主に上記の秘密鍵生成部１３０により実行される。
【０１２５】
秘密鍵の生成処理がスタートすると、秘密鍵生成部１３０は、まず、公開鍵生成方法に係る処理のステップＳ１０４、Ｓ１０６にて生成された量子プログラムＲ、ＣＵを利用し、逆量子プログラム生成部１３２の機能により量子プログラムＣＵ†、Ｒ＊を生成する（Ｓ１１２）。ステップＳ１１２にて生成された量子プログラムＣＵ†、Ｒ＊は、次のステップＳ１１４にて利用される。
【０１２６】
次いで、秘密鍵生成部１３０は、接続部１３４の機能によりステップＳ１１２にて生成された量子プログラムＣＵ†、Ｒ＊を接続して量子プログラムＳを生成する（Ｓ１１４）。ステップＳ１１４にて生成された量子プログラムＣＵ†、Ｒ＊は、秘密鍵Ｓとして出力される。
【０１２７】
以上、秘密鍵Ｓの生成方法に係る処理の流れについて説明した。
【０１２８】
以上説明したように、公開鍵Ｐ、秘密鍵Ｓは、古典情報として記述可能な量子プログラムＰ、Ｓにより構成される。そのため、公開鍵Ｐの確実な認証が容易になる。また、公開鍵Ｐは、ステップＳ１１０にて難読化部１２０により実施される難読化処理により量子コンピュータの攻撃に対する十分な安全性が保証されている。このように、本実施形態に係る鍵生成方法を適用することにより、より安全で利便性の高い量子公開鍵暗号システムが実現される。
【０１２９】
＜３：暗号化方法について＞
次に、本実施形態に係る暗号化方法について説明する。本実施形態に係る暗号化方法は、上記の鍵生成方法により生成された公開鍵Ｐを用いて実行される。つまり、本実施形態に係る暗号化方法による暗号化処理は、公開鍵Ｐである量子プログラムＰ、及び暗号化したい量子状態を量子コンピュータに入力することにより実行される。
【０１３０】
以下で説明する本実施形態に係る暗号化処理は、最大エンタングルメント状態を利用する点に１つの特徴がある。特に、本実施形態に係る暗号化方法は、最大エンタングルメント状態の基底の非一意性を利用することで、暗号文の送信者２０が量子プログラムＲの情報を一切知らずに正しく量子状態を暗号化できるようにする点に１つの特徴がある。
【０１３１】
以下、このような本実施形態に係る暗号化方法を実現することが可能な暗号化装置２００の機能構成、及び暗号化方法について順番に説明する。
【０１３２】
［３−１：暗号化装置２００の機能構成］
まず、図１３を参照しながら、本実施形態に係る暗号化装置２００の機能構成について説明する。図１３は、本実施形態に係る暗号化装置２００の機能構成例を示す説明図である。但し、暗号化装置２００は、鍵生成装置１００により生成された公開鍵Ｐ（量子プログラムＰ）を既に取得しているものとする。また、暗号化装置２００は、量子コンピュータ、又は量子コンピュータを利用する装置であるものとする。
【０１３３】
図１３に示すように、暗号化装置２００は、主に、エンタングルメント状態生成部２０２と、量子状態入力部２０４と、暗号化部２０６とにより構成される。また、暗号化部２０６は、鍵生成装置１００により生成された公開鍵Ｐである量子プログラムＰを保持している。なお、この公開鍵Ｐは、認証局３０により認証され、暗号文の送信者２０により同定されているものとする。以下、量子状態の暗号化過程に沿って各構成要素の機能を説明する。
【０１３４】
（エンタングルメント状態生成部２０２の機能）
まず、エンタングルメント状態生成部２０２は、２ｍ量子ビットの最大エンタングルメント状態を生成する。例えば、エンタングルメント状態生成部２０２は、下記の式（１）で表現される２ｍ量子ビットの基底状態を用意する。そして、エンタングルメント状態生成部２０２は、下記の式（１）のテンソル積で結合された基底状態のうち、前半ｍ量子ビットの各々の量子状態に対してアダマール演算を実行する。このアダマール演算を実行すると、下記の式（２）で表現される量子状態が生成される。
【０１３５】
次いで、エンタングルメント状態生成部２０２は、下記の式（２）で表現される量子状態のうち、アダマール演算の結果に対応する各量子ビットを制御量子ビットとして当該量子状態に制御ＮＯＴ演算を施す。この制御ＮＯＴ演算により、下記の式（３）で表現される２ｍ量子ビットの最大エンタングルメント状態が生成される。このようにしてエンタングルメント状態生成部２０２により生成された最大エンタングルメント状態｜Φｍ＞は、暗号化部２０６に入力される。
【０１３６】
【数１】
…（１）
…（２）
…（３）
【０１３７】
なお、上記の式（１）〜（３）に現れるｉは、二進表示したビット列を十進表示で表現したものである。例えば、２量子ビット状態について考えると、二進表示｜００＞は十進表示｜０＞、二進表示｜０１＞は十進表示｜１＞、二進表示｜１０＞は十進表示｜２＞、二進表示｜１１＞は十進表示｜３＞と表現される。また、上記の式（１）〜（３）に関する量子計算は、イオントラップを用いた量子コンピュータを用いて実行可能である。
【０１３８】
（量子状態入力部２０４の機能）
量子状態入力部２０４は、暗号文の受信者１０へと送信したい量子状態を用意し、暗号化部２０６に入力する機能を提供する。例えば、量子状態入力部２０４は、送信したい古典情報を符号化し、その古典情報に対応するｎ量子ビットの量子状態｜ψｎ＞を生成する。あるいは、量子状態入力部２０４は、暗号化装置２００の外部で生成された量子状態｜ψｎ＞を取得する。そして、量子状態入力部２０４は、生成又は取得した量子状態｜ψｎ＞を暗号化部２０６に入力する。
【０１３９】
（暗号化部２０６の機能）
暗号化部２０６は、量子状態入力部２０４により入力されたｎ量子ビットの量子状態｜ψｎ＞を公開鍵Ｐである量子プログラムＰを用いて暗号化する。この暗号化は、量子コンピュータを利用し、図１５に示すような方法で実行される。まず、暗号化部２０６は、最大エンタングルメント状態生成部２０２により生成された２ｍ量子ビットの最大エンタングルメント状態をｍ量子ビット毎に分け、一方（前半）をそのまま保持する。
【０１４０】
次いで、暗号化部２０６は、他方（後半）ｍ量子ビットの量子状態を量子プログラムＰの制御レジスタ１〜ｍに入力する。さらに、暗号化部２０６は、量子状態入力部２０４から入力された量子状態｜ψｎ＞を量子プログラムＰのデータレジスタに入力する。量子プログラムＰの実行が完了すると、暗号化部２０６は、量子プログラムＰの制御レジスタ１〜ｍから得られる出力を破棄する。そして、暗号化部２０６は、保持していたｍ量子ビットの量子状態に対し、量子プログラムＰのデータレジスタから得られる出力を付加して暗号文（暗号化された量子状態）を生成する。
【０１４１】
このようにして生成された暗号文は、下記の式（４）で表現される。また、暗号化部２０６により生成された暗号文は、量子通信路を介して暗号文の送信者２０から暗号文の受信者１０へと送信される。
【０１４２】
【数２】
…（４）
【０１４３】
（最大エンタングルメント状態の基底の非一意性について）
ここで、最大エンタングルメント状態の基底の非一意性について説明する。本実施形態に係る量子公開鍵暗号システムにおいては、この著しい性質により、量子プログラムＲの情報を一切用いずに正しく暗号化することができるのである。その結果、暗号文の受信者１０は、量子状態を含む暗号化用の鍵（公開鍵Ｐ）を用意しなくて済むようになる。以下、これらの点について説明する。
【０１４４】
２ｍ量子ビットの最大エンタングルメント状態｜Φｍ＞は、上記の式（４）で表現される。ユニタリ演算の性質（ユニタリ演算Ｒに対してＲ†＝ＲＴが成り立つ。また、Ｒｊｋ＝＜ｊ｜Ｒ｜ｋ＞＝＜ｋ｜ＲＴ｜ｊ＞である。）を用いて上記の式（４）を展開すると、最大エンタングルメント状態｜Φｍ＞は、下記の式（５）のように変形される。
【０１４５】
【数３】
…（５）
【０１４６】
上記の式（５）から明らかなように、最大エンタングルメント状態｜Φｍ＞の基底は、ユニタリ変換Ｒを用いて変換することができる。ここでは後段の説明に対する理解を助けるためにユニタリ変換をＲで表現したが、任意のユニタリ変換Ｒに対して上記の変換が実現される。この性質を最大エンタングルメント状態の基底の非一意性と呼ぶ。
【０１４７】
次に、上記の式（５）で表現される最大エンタングルメント状態｜Φｍ＞及び量子プログラムＰを用いてｎ量子ビットの量子状態｜ψｎ＞を暗号化する過程を式で示す。なお、本実施形態に係る量子公開鍵暗号システムにおいて量子プログラムＰは難読化した状態で用いられるが、ここでは簡単のために難読化前の量子プログラムＧを用いて量子状態｜ψｎ＞を暗号化する過程を式で示す。なお、量子プログラムＰは、量子プログラムＧの等価変形である。そのため、最終的に生成される暗号化された量子状態は同じものとなる。
【０１４８】
最大エンタングルメント状態｜Φｍ＞の前半ｍ量子ビットは保持され、後半ｍ量子ビットが量子プログラムＧの制御レジスタ１〜ｍに入力される。そして、量子プログラムＧに含まれるユニタリ演算Ｒが最大エンタングルメント状態｜Φｍ＞の後半ｍ量子ビットに施される。この演算操作は、下記の式（６）で表現される。
【０１４９】
なお、最大エンタングルメント状態｜Φｍ＞は、上記の式（５）で表現した最大エンタングルメント状態の基底の非一意性により、量子プログラムＲに対応するユニタリ演算Ｒを用いて表現することができる。そのため、下記の式（５）のように式を展開することができる。
【０１５０】
次に、下記の式（５）で表現される演算操作の結果が量子プログラムＣＵの制御レジスタ１〜ｍに入力される。量子プログラムＣＵの演算は、制御レジスタ１〜ｍに入力された量子状態と、データレジスタに入力される暗号化対象の量子状態｜ψｎ＞と施される。この演算操作は、下記の式（７）で表現される。量子プログラムＣＵの内容は、制御レジスタ１〜ｍの入力に応じて選択された量子プログラムＵｉをデータレジスタに入力された量子状態に｜ψｎ＞に作用させるというものである。そのため、量子プログラムＣＵによる演算は、下記の式（７）に示すように式展開される。
【０１５１】
次に、下記の式（７）で表現される演算操作の結果が量子プログラムＬに入力される。但し、量子プログラムＣＵの演算結果のうち、制御レジスタ１〜ｍの出力が量子プログラムＬに入力される。そのため、量子プログラムＬの出力は、下記の式（８）で表現される。さらに、量子プログラムＬの出力Ｌ｜ｉ＞が破棄されるため、この破棄する状態に関する部分トレースととることで、量子プログラムＧの最終的な出力（下記の式（９）に示される密度行列）が得られる。
【０１５２】
【数４】
…（６）
…（７）
…（８）
…（９）
【０１５３】
上記の式展開で重要なことは、最大エンタングルメント状態の基底の非一意性により、量子プログラムＰ（量子プログラムＧ）に対して量子プログラムＲの情報を入力していないにも関わらず、上記の式（６）で展開されたようにユニタリ演算Ｒの情報を用いて量子状態｜ψｎ＞が暗号化される点にある。言い換えると、暗号文の送信者２０は、量子プログラムＲの情報を全く知らないにも関わらず、ユニタリ演算Ｒ†の効果を打ち消して量子状態｜ψｎ＞の暗号化を実行できるのである。
【０１５４】
このように、最大エンタングルメント状態の著しい性質を有効に利用することで、完全に量子プログラムＲの情報が秘匿された安全な量子公開鍵システムが実現されるのである。なお、特開２００８−２９４６６６号公報に記載の量子公開鍵暗号システムは、量子プログラムＲを打ち消すような変換を与える量子情報を暗号文の送信者２０に与える必要があった。
【０１５５】
そのため、本実施形態に係る量子公開鍵暗号システムは、量子プログラムＲを打ち消すための情報を一切与えずに済むのであるから、より安全性の高いものであると言える。また、上記の性質により、暗号化用の鍵（公開鍵Ｐ）に量子状態を含めずに済むため、公開鍵Ｐを古典情報だけで記述することが可能になる。その結果、量子公開鍵暗号システムにおける公開鍵Ｐの確かな認証を可能にすることができる。
【０１５６】
［３−２：暗号化処理の詳細］
次に、図１４を参照しながら、本実施形態に係る暗号化処理の流れについて説明する。図１４は、本実施形態に係る暗号化処理の流れを示す説明図である。なお、図１４に示した暗号化処理の各処理ステップは、上記の暗号化装置２００により実行される。
【０１５７】
暗号化処理がスタートすると、暗号化装置２００は、エンタングルメント状態生成部２０２の機能により２ｍ量子ビットの最大エンタングルメント状態を生成し、暗号化部２０６の機能により前半ｍ量子ビットの量子状態を保持する（Ｓ２０２）。
【０１５８】
次いで、暗号化装置２００は、暗号化部２０６の機能により後半ｍ量子ビットの量子状態を量子プログラムＰの制御レジスタ１〜ｍに入力する（Ｓ２０４）。次いで、暗号化装置２００は、量子状態入力部２０４の機能により暗号化すべきｎ量子ビットの量子状態を生成し、暗号化部２０６の機能により量子プログラムＰのデータレジスタに入力する（Ｓ２０６）。
【０１５９】
次いで、暗号化装置２００は、暗号化部２０６の機能により制御レジスタ１〜ｍ、データレジスタに入力された量子状態を用いて量子プログラムＰの演算を実行する（Ｓ２０８）。次いで、暗号化装置２００は、暗号化部２０６の機能により量子プログラムＰの制御レジスタ１〜ｍから出力された量子状態を破棄する（Ｓ２１０）。
【０１６０】
次いで、暗号化装置２００は、暗号化部２０６の機能により、保持していた前半ｍ量子ビットの量子状態に対し、量子プログラムＰのデータレジスタから出力された量子状態を付加する（Ｓ２１２）。そして、暗号化装置２００は、ステップＳ２１２の付加処理にて得られた量子状態を暗号文として出力する。
【０１６１】
以上、本実施形態に係る暗号処理の流れについて説明した。
【０１６２】
以上説明したように、本実施形態に係る暗号化方法は、最大エンタングルメント状態の基底の非一意性を利用して、量子プログラムＲの情報を用いずに量子状態を暗号化するものである。その結果、暗号化用の鍵（公開鍵Ｐ）に量子状態を含めずに済むため、公開鍵Ｐを古典情報だけで記述できるようになる。さらに、量子プログラムＲの情報が完全に秘匿されるため、非常に高い安全性が実現される。
【０１６３】
＜４：復号方法について＞
次に、本実施形態に係る復号方法について説明する。本実施形態に係る復号方法は、上記の鍵生成方法により生成された秘密鍵Ｓを用いて実行される。つまり、本実施形態に係る復号方法による復号処理は、秘密鍵Ｓである量子プログラムＳ、及び暗号文（暗号化された量子状態）を量子コンピュータに入力することにより実行される。以下、本実施形態に係る復号方法を実現することが可能な復号装置３００の機能構成、及び復号方法について順番に説明する。
【０１６４】
［４−１：復号装置３００の機能構成］
まず、図１６を参照しながら、本実施形態に係る復号装置３００の機能構成について説明する。図１６は、本実施形態に係る復号装置３００の機能構成例を示す説明図である。但し、復号装置３００は、鍵生成装置１００により生成された秘密鍵Ｓ（量子プログラムＳ）を既に取得しているものとする。また、復号装置３００は、量子コンピュータ、又は量子コンピュータを利用する装置であるものとする。
【０１６５】
図１６に示すように、復号装置３００は、主に、暗号文入力部３０２と、復号部３０４とにより構成される。また、復号部３０４は、鍵生成装置１００により生成された秘密鍵Ｓである量子プログラムＳを保持している。以下、暗号化された量子状態の復号過程に沿って各構成要素の機能を説明する。
【０１６６】
（暗号文入力部３０２の機能）
暗号文入力部３０２は、暗号文の送信者２０から量子通信路を介して送信された暗号文（暗号化された量子状態）を取得する。そして、暗号文入力部３０２は、取得した暗号文を復号部３０４に入力する。
【０１６７】
（復号部３０４の機能）
復号部３０４は、ｎ＋ｍ量子ビットの量子状態である暗号文を秘密鍵Ｓである量子プログラムＳを用いて復号する。この復号は、量子コンピュータを利用し、図１８に示すような方法で実行される。まず、復号部３０４は、暗号化装置２００にて付加されたｍ量子ビットの量子状態に対応する暗号文の一部を量子プログラムＳの制御レジスタ１〜ｍに入力する。また、復号部３０４は、暗号化装置２００にて量子プログラムＰのデータレジスタから出力された量子状態を量子プログラムＳのデータレジスタに入力する。
【０１６８】
そして、復号部３０４は、量子コンピュータを利用して量子プログラムＳの演算を実行する。演算の実行後、復号部３０４は、量子プログラムＳの制御レジスタ１〜ｍから出力された量子状態を破棄する。さらに、復号部３０４は、量子プログラムＳのデータレジスタから出力されたｎ量子ビットの量子状態を取得する。このｎ量子ビットの量子状態は、暗号化元の量子状態｜ψｎ＞である。このようにして復号部３０４は、暗号文から元の量子状態｜ψｎ＞を復元する。
【０１６９】
（復号の処理過程について）
ここで、復号部３０４による復号処理の処理過程を式により表現する。復号を開始すると、復号部３０４は、ｍ量子ビットの量子状態に対応する暗号文の一部に対し、量子プログラムＳに含まれる量子プログラムＲ＊を実行する。
【０１７０】
この実行操作は、下記の式（１０）で表現される。次いで、復号部３０４は、量子プログラムＲ＊の出力を量子プログラムＣＵ†の制御レジスタ１〜ｍに入力し、暗号文の残りｎ量子ビットの量子状態を量子プログラムＣＵ†のデータレジスタに入力する。そして、復号部３０４は、量子プログラムＣＵ†の演算を実行する。この演算操作は、下記の式（１１）で表現される。この操作の結果、量子プログラムＣＵ†のデータレジスタから暗号化前の量子状態｜ψｎ＞が出力される。
【０１７１】
【数５】
…（１０）
…（１１）
【０１７２】
以上、復号装置３００の機能について説明した。
【０１７３】
［４−２：復号処理の詳細］
次に、図１７を参照しながら、本実施形態に係る復号処理の流れについて説明する。図１７は、本実施形態に係る復号処理の流れを示す説明図である。なお、図１７に示した復号処理の各処理ステップは、上記の復号装置３００により実行される。
【０１７４】
復号処理がスタートすると、復号装置３００は、暗号文入力部３０２の機能により取得した暗号文を復号部３０４の機能により量子プログラムＳに入力する（Ｓ３０２）。次いで、復号装置３００は、復号部３０４の機能により量子プログラムＳの演算を実行し、量子プログラムＳの制御レジスタ１〜ｍの出力を破棄する（Ｓ３０４）。
【０１７５】
さらに、復号装置３００は、復号部３０４の機能により、量子プログラムＳのデータレジスタから出力された量子状態｜ψｎ＞を取得する（Ｓ３０６）。そして、復号装置３００は、ステップＳ３０６にて取得された量子状態｜ψｎ＞を出力する。
【０１７６】
以上、本実施形態に係る復号処理の流れについて説明した。
【０１７７】
以上説明したように、本実施形態に係る復号方法を適用することにより、秘密鍵Ｓである量子プログラムＳを用いて、本実施形態に係る暗号化方法により生成された暗号文を容易に復号することができる。
【０１７８】
＜５：まとめ＞
最後に、本発明の実施形態に係る技術内容について簡単に纏める。
【０１７９】
本実施形態に係る技術は、量子公開鍵暗号系における鍵生成方法、暗号化方法、復号方法に関する。本実施形態に係る技術は、古典情報を符号化した量子状態、又は量子状態そのものを暗号化するものである。また、量子通信路を利用するものの、この量子公開鍵暗号系のエンティティ構成は古典的な公開鍵暗号系のものと同じ形式に設定することができる。従って、現在の安全性概念に適合させることが容易である。もちろん、高い安全性レベルが実現されることは既に述べた通りである。
【０１８０】
また、本実施形態に係る量子公開鍵暗号システムは、全ての暗号化処理を暗号文の送信者２０側にある量子コンピュータの動作だけで実行する。また、本実施形態に係る量子公開鍵暗号システムは、全ての復号処理を暗号文の受信者１０側にある量子コンピュータの動作だけで実行する。
【０１８１】
そのため、暗号文の送信者２０側にある量子コンピュータと暗号文の受信者１０側にある量子コンピュータとを量子通信路により接続したり、両量子コンピュータを協調的に動作させる必要がない。そのため、暗号文の送信者２０と暗号文の受信者１０との間で暗号化・復号に係る処理を実行する量子暗号系に比べて利便性が非常に高い。
【０１８２】
また、本実施形態に係る量子公開鍵暗号システムにおける暗号化は、認証された公開鍵と暗号文の送信者２０が生成する最大エンタングルメント状態とを用いて実施される。そのため、公開鍵は古典情報で記述することが可能になる。その結果、公開鍵に与えられる認証の有無を容易に検証することが可能になる。そして、認証が与えられた公開鍵を用いて暗号化が行われるため、確実に量子状態を暗号化することができる。
【０１８３】
（認証に関する補足説明）
上記の通り、本実施形態に係る量子公開鍵暗号システムは、古典情報として記述された公開鍵を用いる。そのため、暗号文の送信者２０は、公開鍵に対する認証の有無を容易に検証できる。また、古典情報のみで公開鍵を構成することにより安全性を向上させる効果が得られる。以下、これらの効果について説明を補足する。
【０１８４】
まず、量子公開鍵暗号システムにおける公開鍵の認証を確かに実現するための二つの要求について議論する。一つ目の要求は、配布された公開鍵が認証局３０により認証を受けたものであるかを暗号文の送信者２０が容易に検証（公開鍵の同定）できるようにすることである。二つ目の要求は、公開鍵の同定を行った後でも、その公開鍵が暗号化に利用可能な状態に維持されることである。
【０１８５】
ここで、公開鍵を量子状態で構成する場合について考えてみよう。公開鍵の同定を行うと、同定の結果が古典情報となる。つまり、同定により量子状態に対する何らかの測定が行われたことになる。このとき、量子状態の一部が、測定により古典情報に射影されてしまう。その結果、古典情報に射影された部分は、量子性を利用した暗号化に利用することができない。一方、古典情報に射影されていない部分は、同定が行われていない。つまり、同定と暗号鍵としての利用可能性とはトレードオフの関係にある。
【０１８６】
このトレードオフの関係は、量子状態の測定に関する問題に起因しており、解決することは極めて困難である。その点、本実施形態に係る公開鍵は、古典情報のみで記述されているため、公開鍵の同定に関する上記の問題は生じない。
【０１８７】
以上、添付図面を参照しながら本発明の好適な実施形態について説明したが、本発明は係る例に限定されないことは言うまでもない。当業者であれば、特許請求の範囲に記載された範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、それらについても当然に本発明の技術的範囲に属するものと了解される。
【符号の説明】
【０１８８】
１０ 暗号文の受信者
２０ 暗号文の送信者
３０ 認証局
１００ 鍵生成装置
１１０ 公開鍵生成部
１１２ 乱数発生部
１１４ 量子プログラム生成部
１１６ 制御化部
１１８ 量子プログラム付加部
１２０ 難読化部
１３０ 秘密鍵生成部
１３２ 逆量子プログラム生成部
１３４ 接続部
２００ 暗号化装置
２０２ エンタングルメント状態生成部
２０４ 量子状態入力部
２０６ 暗号化部
３００ 復号装置
３０２ 暗号文入力部
３０４ 復号部
【技術分野】
【０００１】
本発明は、量子公開鍵暗号システム、鍵生成装置、暗号化装置、復号装置、鍵生成方法、暗号化方法、及び復号方法に関する。
【背景技術】
【０００２】
情報処理技術や通信技術の急速な発展に伴い、公文書、私文書を問わず、文書の電子化が急速に進んでいる。これに伴い、多くの個人や企業は、電子文書の安全管理に大きな関心を寄せている。こうした関心の高まりを受け、各方面で電子文書の盗聴や偽造等のタンパリング行為に対する安全性が盛んに議論されるようになってきた。電子文書の盗聴に対する安全性は、例えば、電子文書を暗号化することにより確保される。また、電子文書の偽造に対する安全性は、例えば、電子署名を利用することにより確保される。但し、暗号や電子署名には十分なタンパリング耐性が求められる。
【０００３】
現在広く利用されている公開鍵暗号は、古典的なコンピュータの計算量的複雑性を安全性の根拠としている。例えば、ＲＳＡ暗号は、「大きな合成数に対する素因数分解の困難性（以下、素因数分解問題）」を安全性の根拠としている。また、ＤＳＡ暗号やＥｌＧａｍａｌ暗号は、「離散対数問題に対する解答の困難性」を安全性の根拠としている。しかし、量子コンピュータは、素因数分解問題や離散対数問題に対する解答を効率的に算出することができると言われている。つまり、現在広く利用されている上記の暗号は、量子コンピュータが実用化されると、その安全性が保証されない。
【０００４】
なお、上記の「古典」という表現は、「量子」ではないという意味で用いている。また、「量子」という表現は、量子力学の原理に基づいているか、量子力学の原理を応用していることを意味している。例えば、量子コンピュータは、量子力学における重ね合わせの原理を応用した計算機である。また、ＢＢ８４等の量子鍵配送方式は、量子力学の不確定性原理を利用している。
【０００５】
こうした実状を背景に、量子コンピュータが実用化された際にも安全性が保証されるような公開鍵暗号系の研究が盛んに行われている。その一つの方向性は、量子コンピュータを用いても効率的に計算することが困難な問題（例えば、多変数多項式に対する解答の困難性）を安全性の根拠として古典通信路における公開鍵暗号系を実現しようとするものである。また、他の方向性は、量子通信路と量子演算とを用いて、量子コンピュータを用いた攻撃に対する安全性が保証されるような量子公開鍵暗号系を実現しようとするものである。例えば、下記の非特許文献１、特許文献１、２には、量子公開鍵暗号系に関する研究成果の一例が示されている。
【０００６】
非特許文献１、特許文献１に記載の量子公開鍵暗号系は、ナップサック問題の特殊な場合である部分和問題の計算量的な複雑性を安全性の根拠としている。この部分和問題とは、「与えられたｎ個の整数ａ１，…，ａｎから部分集合をうまく選び、その部分集合に属する数の和を、与えられた数Ｎに等しくすることができるか」を判定する問題である。この部分和問題は、計算量クラスＮＰ完全に属している。しかし、量子コンピュータを用いて部分和問題を解くことが極めて困難であるか否かは自明ではない。そのため、上記非特許文献１、特許文献１に記載の量子公開鍵暗号系は、量子コンピュータを用いた攻撃に対して必ずしも安全であるとは言えない。
【０００７】
また、特許文献１に記載の量子公開鍵暗号系は、量子状態を公開鍵として利用している。そのため、特許文献１に記載の量子公開鍵暗号系を利用すると、次のような問題が生じてしまう。通常、公開鍵暗号系で用いる公開鍵は認証局により認証を受ける。公開鍵が古典的に記述された情報（以下、古典情報）であれば、その公開鍵が確かに認証局による認証を受けたものであるか否かを検証できる。しかし、量子状態で表現された公開鍵（以下、量子公開鍵）に対する認証の有無を検証できるか否かは必ずしも自明ではない。例えば、量子状態は、測定により状態が変化してしまうため、量子公開鍵に対する認証の有無を検証すると、その量子公開鍵が公開鍵としての用を成さなくなる可能性がある。
【０００８】
一方、下記の特許文献２に記載の量子公開鍵暗号系は、量子状態と古典情報とを組み合わせたハイブリッド型の公開鍵（以下、ハイブリッド公開鍵）を利用している。ハイブリッド公開鍵は、古典情報の部分を含んでいる。そのため、古典情報の部分を利用して認証を行い、古典情報の部分を利用して認証の有無を検証することで、量子状態を攪乱せずに認証の有無を検証することが可能である。もちろん、量子状態に対する検証は行われない。しかし、量子状態が何らかの改竄を受けると、検証済みの古典情報との齟齬が生じるため、ハイブリッド公開鍵を用いた暗号化や秘密鍵を用いた復号に失敗する。従って、実際上、量子状態に対する検証が行われなくても問題はない。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特許第３６１５１３２号公報
【特許文献２】特開２００８−２９４６６６号公報
【非特許文献】
【００１０】
【非特許文献１】Ｔ． Ｏｋａｍｏｔｏ， Ｋ． Ｔａｎａｋａ， Ｓ． Ｕｃｈｉｙａｍａ． “Ｑｕａｎｔｕｍ Ｐｕｂｌｉｃ Ｋｅｙ Ｃｒｙｐｔｏｓｙｓｔｅｍｓ＆ｑｕｏｔ”，Ｐｒｏｃ． ｏｆ ＣＲＹＴＰＴＯ ２０００， ＬＮＣＳ １８８０，ｐｐ．１４７−ｐｐ．１６５， Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ（２０００）．
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかしながら、上記の特許文献２に記載のハイブリッド公開鍵は、やや利便性が低い。上記の通り、ハイブリッド公開鍵は、古典情報と量子状態との組み合わせで構成されている。つまり、配布される一つ一つの古典情報に対して個々に量子状態の鍵が対応する。従って、鍵生成に要するコストが増大してしまう。また、暗号化・復号の成否が復号処理の完了を待って確定されるため、暗号化・復号が失敗する場合、復号処理の完了まで余分な通信を行うこととなり、低効率化に繋がってしまう。以上説明した理由から、量子コンピュータによる攻撃に対して安全性が保証され、公開鍵の認証が可能であり、かつ、量子公開鍵暗号系の中で暗号化・復号処理の非効率化を招かないような仕組みが望まれている。
【００１２】
そこで、本発明は、上記問題に鑑みてなされたものであり、本発明の目的とするところは、より安全で利便性の高い量子公開鍵暗号系を実現することが可能な、新規かつ改良された量子公開鍵暗号システム、鍵生成装置、暗号化装置、復号装置、鍵生成方法、暗号化方法、及び復号方法を提供することにある。
【課題を解決するための手段】
【００１３】
上記課題を解決するために、本発明のある観点によれば、第１の量子情報処理装置と、量子通信路を介して前記第１の量子情報処理装置に接続された第２の量子情報処理装置と、古典通信路を介して前記第１及び第２の量子情報処理装置に接続された認証局と、を含み、前記第１の量子情報処理装置は、公開鍵と秘密鍵とを生成する鍵生成部と、前記鍵生成部により生成された公開鍵を、前記古典通信路を介して前記認証局に送信する第１古典送信部と、前記第２の量子情報処理装置から前記量子通信路を介して送信された、暗号化された量子状態を受信する第１量子受信部と、前記鍵生成部により生成された秘密鍵を用いて、前記第１量子受信部により受信された、前記暗号化された量子状態から元の量子状態を復元する復号部と、を有し、前記認証局は、前記第１の量子情報処理装置から前記古典通信路を介して送信された公開鍵を受信する第１古典受信部と、前記第１古典受信部により受信された公開鍵を認証する認証部と、前記認証部により認証された公開鍵を前記古典通信路を介して前記第２の量子情報処理装置に送信する第２古典送信部と、を有し、前記第２の量子情報処理装置は、前記認証局から前記古典通信路を介して送信された公開鍵を受信する第２古典受信部と、前記第２古典受信部により受信された公開鍵を用いて量子状態を暗号化する暗号化部と、前記暗号化部により暗号化された量子状態を前記量子通信路を介して前記第１の量子情報処理装置に送信する量子送信部と、を有する、量子公開鍵暗号システムが提供される。
【００１４】
また、前記鍵生成部は、乱数を発生させる乱数発生器と、前記乱数発生器を用いて発生させた乱数に基づき、ｎ量子ビットに対するｍ種類のユニタリ演算Ｕｉ（ｉ＝１〜ｍ）、及び、ｍ量子ビットに対する２種類のユニタリ演算Ｌ、Ｒに、それぞれ対応する量子プログラムＵｉ、Ｌ、Ｒを生成する量子プログラム生成部と、ｍ量子ビットの入力状態に応じて前記量子プログラムＵｉの動作が制御されるように制御化された量子プログラムＣＵを生成する量子プログラム制御化部と、前記量子プログラムＣＵに前記量子プログラムＬ、Ｒを付加して量子プログラムＧを生成する量子プログラム付加部と、前記量子プログラムＧを難読化して前記公開鍵に対応する量子プログラムＰを生成する量子プログラム難読化部と、前記量子プログラムＣＵに対応するユニタリ演算ＣＵのエルミート共役ＣＵ†に対応する量子プログラムＣＵ†と、前記ユニタリ演算Ｒの複素共役Ｒ＊に対応する量子プログラムＲ＊と、を生成する逆量子プログラム生成部と、前記量子プログラムＣＵ†と前記量子プログラムＲ＊とを接続して前記秘密鍵に対応する量子プログラムＳを生成する量子プログラム接続部と、を含んでいてもよい。
【００１５】
また、前記暗号化部は、量子コンピュータから成り、２ｍ量子ビットの最大エンタングルメント状態を生成し、当該２ｍ量子ビットの最大エンタングルメント状態のうち、ｍ量子ビットの量子状態と、送信すべきｎ量子ビットの量子状態｜ψｎ＞と、を前記公開鍵に対応する量子プログラムＰに入力して前記暗号化された量子状態を算出するように構成されていてもよい。
【００１６】
また、前記復号部は、量子コンピュータから成り、前記暗号化された量子状態を前記秘密鍵に対応する量子プログラムＳに入力して元の量子状態｜ψｎ＞を算出するように構成されていてもよい。
【００１７】
また、前記暗号化部は、２ｍ量子ビットの最大エンタングルメント状態を生成し、当該２ｍ量子ビットの最大エンタングルメント状態のうち、ｍ量子ビットの量子状態を保持しておき、残りｍ量子ビットの量子状態を、前記量子状態｜ψｎ＞と共に前記量子プログラムＰに入力し、前記量子状態｜ψｎ＞に対応する量子プログラムＰの出力に、保持しておいたｍ量子ビットの量子状態を付加して前記暗号化された量子状態を算出するように構成されていてもよい。
【００１８】
また、前記量子プログラム難読化部は、前記量子プログラムＧを、前記量子プログラムＧに対応するユニタリ演算と同じ演算内容を有する別の量子プログラムＧ’に置き換えることで前記量子プログラムＧを難読化するように構成されていてもよい。
【００１９】
また、前記量子プログラム難読化部は、前記量子プログラムＧの一部を成す部分量子プログラムｇを、当該部分量子プログラムｇと同じ演算内容を有する別の量子プログラムｇ’に置き換えることで前記量子プログラムＧを難読化するように構成されていてもよい。
【００２０】
また、上記課題を解決するために、本発明の別の観点によれば、乱数を発生させる乱数発生器と、前記乱数発生器を用いて発生させた乱数に基づき、ｎ量子ビットに対するｍ種類のユニタリ演算Ｕｉ（ｉ＝１〜ｍ）、及び、ｍ量子ビットに対する２種類のユニタリ演算Ｌ、Ｒに、それぞれ対応する量子プログラムＵｉ、Ｌ、Ｒを生成する量子プログラム生成部と、ｍ量子ビットの入力状態に応じて前記量子プログラムＵｉの動作が制御されるように制御化された量子プログラムＣＵを生成する量子プログラム制御化部と、前記量子プログラムＣＵに前記量子プログラムＬ、Ｒを付加して量子プログラムＧを生成する量子プログラム付加部と、前記量子プログラムＧを難読化して、公開鍵に対応する量子プログラムＰを生成する量子プログラム難読化部と、前記量子プログラムＣＵに対応するユニタリ演算ＣＵのエルミート共役ＣＵ†に対応する量子プログラムＣＵ†と、前記ユニタリ演算Ｒの複素共役Ｒ＊に対応する量子プログラムＲ＊と、を生成する逆量子プログラム生成部と、前記量子プログラムＣＵ†と前記量子プログラムＲ＊とを接続して、秘密鍵に対応する量子プログラムＳを生成する量子プログラム接続部と、を備える、鍵生成装置が提供される。
【００２１】
また、上記課題を解決するために、本発明の別の観点によれば、乱数を発生させる乱数発生器と、前記乱数発生器を用いて発生させた乱数に基づき、ｎ量子ビットに対するｍ種類のユニタリ演算Ｕｉ（ｉ＝１〜ｍ）、及び、ｍ量子ビットに対する２種類のユニタリ演算Ｌ、Ｒに、それぞれ対応する量子プログラムＵｉ、Ｌ、Ｒを生成する量子プログラム生成部と、ｍ量子ビットの入力状態に応じて前記量子プログラムＵｉの動作が制御されるように制御化された量子プログラムＣＵを生成する量子プログラム制御化部と、前記量子プログラムＣＵに前記量子プログラムＬ、Ｒを付加して量子プログラムＧを生成する量子プログラム付加部と、前記量子プログラムＧを難読化して、公開鍵に対応する量子プログラムＰを生成する量子プログラム難読化部と、を有する鍵生成装置により生成された公開鍵に対応する量子プログラムＰを保持する公開鍵保持部と、量子コンピュータを利用して、２ｍ量子ビットの最大エンタングルメント状態を生成するエンタングルメント状態生成部と、前記エンタングルメント状態生成部により生成された最大エンタングルメント状態と、送信すべきｎ量子ビットの量子状態と、を前記公開鍵に対応する量子プログラムＰに入力して前記暗号化された量子状態を算出する暗号化部と、を備える、暗号化装置が提供される。
【００２２】
また、上記課題を解決するために、本発明の別の観点によれば、乱数を発生させる乱数発生器と、前記乱数発生器を用いて発生させた乱数に基づき、ｎ量子ビットに対するｍ種類のユニタリ演算Ｕｉ（ｉ＝１〜ｍ）、及び、ｍ量子ビットに対する２種類のユニタリ演算Ｌ、Ｒに、それぞれ対応する量子プログラムＵｉ、Ｌ、Ｒを生成する量子プログラム生成部と、ｍ量子ビットの入力状態に応じて前記量子プログラムＵｉの動作が制御されるように制御化された量子プログラムＣＵを生成する量子プログラム制御化部と、前記量子プログラムＣＵに前記量子プログラムＬ、Ｒを付加して量子プログラムＧを生成する量子プログラム付加部と、前記量子プログラムＧを難読化して、公開鍵に対応する量子プログラムＰを生成する量子プログラム難読化部と、前記量子プログラムＣＵに対応するユニタリ演算ＣＵのエルミート共役ＣＵ†に対応する量子プログラムＣＵ†と、前記ユニタリ演算Ｒの複素共役Ｒ＊に対応する量子プログラムＲ＊と、を生成する逆量子プログラム生成部と、前記量子プログラムＣＵ†と前記量子プログラムＲ＊とを接続して、秘密鍵に対応する量子プログラムＳを生成する量子プログラム接続部と、を有する鍵生成装置により生成された秘密鍵に対応する量子プログラムＳを保持する秘密鍵保持部と、量子コンピュータを利用し、前記公開鍵に対応する量子プログラムＰを用いて生成された、暗号化された量子状態を前記秘密鍵に対応する量子プログラムＳに入力して元の量子状態を算出する復号部と、を備える、復号装置が提供される。
【００２３】
また、上記課題を解決するために、本発明の別の観点によれば、乱数を発生させる乱数発生ステップと、前記乱数発生ステップで発生させた乱数に基づき、ｎ量子ビットに対するｍ種類のユニタリ演算Ｕｉ（ｉ＝１〜ｍ）、及び、ｍ量子ビットに対する２種類のユニタリ演算Ｌ、Ｒに、それぞれ対応する量子プログラムＵｉ、Ｌ、Ｒを生成する量子プログラム生成ステップと、ｍ量子ビットの入力状態に応じて前記量子プログラムＵｉの動作が制御されるように制御化された量子プログラムＣＵを生成する量子プログラム制御化ステップと、前記量子プログラムＣＵに前記量子プログラムＬ、Ｒを付加して量子プログラムＧを生成する量子プログラム付加ステップと、前記量子プログラムＧを難読化して、公開鍵に対応する量子プログラムＰを生成する量子プログラム難読化ステップと、前記量子プログラムＣＵに対応するユニタリ演算ＣＵのエルミート共役ＣＵ†に対応する量子プログラムＣＵ†と、前記ユニタリ演算Ｒの複素共役Ｒ＊に対応する量子プログラムＲ＊と、を生成する逆量子プログラム生成ステップと、前記量子プログラムＣＵ†と前記量子プログラムＲ＊とを接続して、秘密鍵に対応する量子プログラムＳを生成する量子プログラム接続ステップと、を含む、鍵生成方法が提供される。
【００２４】
また、上記課題を解決するために、本発明の別の観点によれば、量子コンピュータを利用して、２ｍ量子ビットの最大エンタングルメント状態を生成するエンタングルメント状態生成ステップと、乱数を発生させる乱数発生器と、前記乱数発生器を用いて発生させた乱数に基づき、ｎ量子ビットに対するｍ種類のユニタリ演算Ｕｉ（ｉ＝１〜ｍ）、及び、ｍ量子ビットに対する２種類のユニタリ演算Ｌ、Ｒに、それぞれ対応する量子プログラムＵｉ、Ｌ、Ｒを生成する量子プログラム生成部と、ｍ量子ビットの入力状態に応じて前記量子プログラムＵｉの動作が制御されるように制御化された量子プログラムＣＵを生成する量子プログラム制御化部と、前記量子プログラムＣＵに前記量子プログラムＬ、Ｒを付加して量子プログラムＧを生成する量子プログラム付加部と、前記量子プログラムＧを難読化して、公開鍵に対応する量子プログラムＰを生成する量子プログラム難読化部と、を有する鍵生成装置により生成された公開鍵に対応する量子プログラムＰに対し、量子コンピュータを利用して、前記エンタングルメント状態生成ステップで生成された２ｍ量子ビットの最大エンタングルメント状態のうち、ｍ量子ビットの量子状態と、送信すべきｎ量子ビットの量子状態と、を入力して前記暗号化された量子状態を算出する暗号化ステップと、を含む、暗号化方法が提供される。
【００２５】
また、上記課題を解決するために、本発明の別の観点によれば、乱数を発生させる乱数発生器と、前記乱数発生器を用いて発生させた乱数に基づき、ｎ量子ビットに対するｍ種類のユニタリ演算Ｕｉ（ｉ＝１〜ｍ）、及び、ｍ量子ビットに対する２種類のユニタリ演算Ｌ、Ｒに、それぞれ対応する量子プログラムＵｉ、Ｌ、Ｒを生成する量子プログラム生成部と、ｍ量子ビットの入力状態に応じて前記量子プログラムＵｉの動作が制御されるように制御化された量子プログラムＣＵを生成する量子プログラム制御化部と、前記量子プログラムＣＵに前記量子プログラムＬ、Ｒを付加して量子プログラムＧを生成する量子プログラム付加部と、前記量子プログラムＧを難読化して、公開鍵に対応する量子プログラムＰを生成する量子プログラム難読化部と、前記量子プログラムＣＵに対応するユニタリ演算ＣＵのエルミート共役ＣＵ†に対応する量子プログラムＣＵ†と、前記ユニタリ演算Ｒの複素共役Ｒ＊に対応する量子プログラムＲ＊と、を生成する逆量子プログラム生成部と、前記量子プログラムＣＵ†と前記量子プログラムＲ＊とを接続して、秘密鍵に対応する量子プログラムＳを生成する量子プログラム接続部と、を有する鍵生成装置により生成された秘密鍵に対応する量子プログラムＳに対し、量子コンピュータを利用して、前記公開鍵に対応する量子プログラムＰを用いて生成された、暗号化された量子状態を入力して元の量子状態を算出する復号ステップを含む、復号方法が提供される。
【発明の効果】
【００２６】
以上説明したように本発明によれば、最大エンタングルメント状態の表現基底が非一意であるという性質を利用して、より安全で利便性の高い量子公開鍵暗号系が実現される。
【図面の簡単な説明】
【００２７】
【図１】本発明の一実施形態に係る量子公開鍵暗号システムの全体構成の一例を示す説明図である。
【図２】同実施形態に係る鍵生成装置の機能構成例を示す説明図である。
【図３】同実施形態に係る鍵生成方法における処理の流れを示す説明図である。
【図４】ユニバーサル量子回路の構築に利用する量子回路の一例を示す説明図である。
【図５】同実施形態に係る量子プログラム生成方法の一例を示す説明図である。
【図６】同実施形態に係る制御化方法の一例を示す説明図である。
【図７】同実施形態に係る量子プログラム付加方法の一例を示す説明図である。
【図８】同実施形態に係る難読化方法の一例を示す説明図である。
【図９】同実施形態に係る難読化方法の一例を示す説明図である。
【図１０】同実施形態に係る難読化方法の一例を示す説明図である。
【図１１】同実施形態に係る逆量子プログラムの生成方法の一例を示す説明図である。
【図１２】同実施形態に係る逆量子プログラムの接続方法の一例を示す説明図である。
【図１３】同実施形態に係る暗号化装置の機能構成例を示す説明図である。
【図１４】同実施形態に係る暗号化方法における処理の流れを示す説明図である。
【図１５】同実施形態に係る暗号化方法の一例を示す説明図である。
【図１６】同実施形態に係る復号装置の機能構成例を示す説明図である。
【図１７】同実施形態に係る復号方法における処理の流れを示す説明図である。
【図１８】同実施形態に係る復号方法の一例を示す説明図である。
【発明を実施するための形態】
【００２８】
以下に添付図面を参照しながら、本発明の好適な実施の形態について詳細に説明する。なお、本明細書及び図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。
【００２９】
［説明の流れについて］
ここで、以下に記載する本発明の実施形態に関する説明の流れについて簡単に述べる。まず、図１を参照しながら、本実施形態に係る量子公開鍵暗号システムの全体構成について説明する。次いで、図２を参照しながら、本実施形態に係る量子公開鍵暗号システムにおいて用いられる公開鍵、秘密鍵を生成するための鍵生成装置１００が有する機能構成について説明する。また、図３〜図１２を参照しながら、鍵生成装置１００により実行される鍵生成処理の流れ及び処理内容について説明する。
【００３０】
次いで、図１３を参照しながら、本実施形態に係る量子公開鍵暗号システムにおいて、送信すべき量子状態を暗号化するための暗号化装置２００の機能構成について説明する。また、図１４、図１５を参照しながら、暗号化装置２００により実行される暗号化処理の流れ及び処理内容について説明する。次いで、図１６を参照しながら、本実施形態に係る量子公開鍵暗号システムにおいて、暗号化された量子状態から元の量子状態を復号するための復号装置３００の機能構成について説明する。また、図１７、図１８を参照しながら、復号装置３００により実行される復号処理の流れ及び処理内容について説明する。
【００３１】
（説明項目）
１：量子公開鍵暗号システムの構成について
２：鍵生成方法について
２−１：鍵生成装置１００の機能構成
２−１−１：公開鍵生成部１１０の機能
２−１−２：秘密鍵生成部１３０の機能
２−２：鍵生成処理の詳細
２−２−１：公開鍵Ｐの生成方法
２−２−２：秘密鍵Ｓの生成方法
３：暗号化方法について
３−１：暗号化装置２００の機能構成
３−２：暗号化処理の詳細
４：復号方法について
４−１：復号装置３００の機能構成
４−２：復号処理の詳細
５：まとめ
【００３２】
＜１：量子公開鍵暗号システムの構成について＞
まず、図１を参照しながら、本発明の一実施形態に係る量子公開鍵暗号システムの全体像について説明する。図１は、本実施形態に係る量子公開鍵暗号システムの全体像、及び公開鍵認証・量子暗号文の送受信の流れについて説明するための説明図である。
【００３３】
図１に示すように、本実施形態に係る量子公開鍵暗号システムは、暗号文の受信者１０、暗号文の送信者２０、及び認証局３０により構成される。但し、暗号文の受信者１０は、説明の都合上、後述する鍵生成装置１００、復号装置３００を含む処理ブロックを擬人化したものである。同様に、暗号文の送信者２０は、説明の都合上、後述する暗号化装置２００を含む処理ブロックを擬人化したものである。また、認証局３０は、信頼できる第三者機関又は認証機関である。
【００３４】
（鍵生成→認証→暗号化→復号の流れ）
まず、暗号文の受信者１０は、公開鍵、秘密鍵のペアを生成する（Ｓｔｅｐ．１）。次いで、暗号文の受信者１０は、認証局３０に公開鍵を登録する。このとき、暗号文の受信者１０は、古典通信路を通じて公開鍵を認証局３０に送信する（Ｓｔｅｐ．２）。なお、本実施形態に係る量子公開鍵暗号システムで用いられる公開鍵は、後述するように古典情報のみで構成されている。また、秘密鍵は、暗号文の受信者１０により秘匿される。
【００３５】
次いで、認証局３０は、暗号文の受信者１０により登録された公開鍵を認証する（Ｓｔｅｐ．３）。次いで、認証局３０は、認証を与えた公開鍵を公開する。このとき、認証局３０は、古典通信路を通じて認証後の公開鍵を暗号文の送信者２０に送信する（Ｓｔｅｐ．４）。
【００３６】
暗号文の送信者２０は、古典通信路を通じて公開された公開鍵を入手すると、入手した公開鍵が認証済みのものか否かを検証する。そして、入手した公開鍵が認証済みであることを確認すると、暗号文の送信者２０は、量子コンピュータを利用し、その公開鍵を用いて暗号文を生成する（Ｓｔｅｐ．５）。
【００３７】
まず、暗号文の送信者２０は、送信したい古典情報を符号化して量子状態を生成するか、送信したい量子状態を用意する。次いで、暗号文の送信者２０は、最大エンタングルメント状態を生成する。次いで、暗号文の送信者２０は、生成又は用意した量子状態と、生成した最大エンタングルメント状態の一部とを公開鍵が示す量子プログラムの入力として与え、量子コンピュータにより暗号文（暗号化された量子状態）を生成する。
【００３８】
次いで、暗号文の送信者２０は、量子通信路を通じて、生成した暗号文を暗号文の受信者１０に送信する（Ｓｔｅｐ．６）。暗号文の受信者１０は、量子通信路を通じて受信した暗号文を秘密鍵が示す量子プログラムの入力として与え、量子コンピュータにより元の量子状態を復元する（Ｓｔｅｐ．７）。
【００３９】
以上説明したように、本実施形態に係る量子公開鍵暗号システムにおいて用いられる公開鍵は古典情報の形で記述された量子プログラムである。そのため、公開鍵が古典情報のみで記述されているため、公開鍵に対する認証の有無を容易に検証することができる。なお、暗号文の受信者１０による鍵生成（Ｓｔｅｐ．１）は、後述する鍵生成装置１００により実行される。また、暗号文の送信者２０による暗号文の生成（Ｓｔｅｐ．５）は、後述する暗号化装置２００により実行される。さらに、暗号文の受信者１０による復号（Ｓｔｅｐ．７）は、後述する復号装置３００により実行される。
【００４０】
（量子コンピュータのモデルについて）
上記の通り、本実施形態に係る量子公開鍵暗号システムは、暗号文の生成（Ｓｔｅｐ．５）、暗号文の復号（Ｓｔｅｐ．７）の際に量子コンピュータを用いる。また、本実施形態に係る公開鍵及び秘密鍵は、量子プログラムを示す古典情報である。そこで、本実施形態の説明を進めるにあたって、まず、量子コンピュータのモデル、及び量子プログラムの表現方法について概説する。
【００４１】
量子コンピュータは、量子プログラムと量子データとを入力とする。量子プログラムとは、量子アルゴリズムの実行方法を記述した古典情報である。一方、量子データとは、量子アルゴリズムの実行対象となる量子状態である。量子プログラムの表現方法は、利用する量子計算モデルにより異なる。
【００４２】
代表的な量子計算モデルとしては、例えば、量子回路モデル、量子チューリング機械モデル、観測ベース量子計算モデル等が知られている。量子回路モデルの場合、量子プログラムは、量子回路図を用いて表現される。量子チューリング機械モデルの場合、量子プログラムは、状態遷移図を用いて表現される。観測ベース量子計算モデルの場合、量子プログラムは、グラフ図を用いて表現される。以下の説明においては、量子回路モデルの表現を用いる。但し、量子回路モデルの違いは表現の違いであり、本実施形態の技術的範囲が量子回路モデルに限定されるものではない点に注意されたい。
【００４３】
なお、量子回路モデル、量子チューリング機械モデルについては、例えば、“Ｎｉｅｌｓｅｎ ａｎｄ Ｃｈｕａｎｇ， Ｑｕａｎｔｕｍ Ｃｏｍｐｕｔａｔｉｏｎ ａｎｄ Ｑｕａｎｔｕｍ Ｉｎｆｏｒｍａｔｉｏｎ，
Ｃａｍｂｒｉｄｇｅ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ”を参照されたい。また、観測ベース量子計算モデルについては、例えば、“Ｒ． Ｒａｕｓｓｅｎｄｏｒｆ ａｎｄ Ｈ． Ｊ． Ｂｒｉｅｇｅｌ， Ｐｈｙｓ． Ｒｅｖ． Ｌｅｔｔ．，
８６（５１８８）， ２００１．”を参照されたい。
【００４４】
以上、本実施形態に係る量子公開鍵暗号システムの全体像について説明した。以下では、本実施形態に係る公開鍵暗号システムにおける鍵生成方法、暗号化方法、復号方法について、順次、より詳細に説明する。
【００４５】
＜２：鍵生成方法について＞
まず、本実施形態に係る鍵生成方法について説明する。本実施形態に係る鍵生成方法により生成される公開鍵及び秘密鍵は、量子プログラムで表現される。量子プログラムとは、量子コンピュータにより実行されるユニタリ演算の組み合わせで表現された設計図である。上記の通り、量子プログラムの表現は幾通りも存在するが、本稿では一例として量子回路モデルの表現方法（以下、量子回路図）を採用する。
【００４６】
量子回路図は、例えば、図４に示すような量子回路を組み合わせて設計される。量子回路図に含まれる量子回路は、ユニタリ演算の表現である。なお、以下の説明では、量子回路のことを量子プログラムと表現する場合がある。さらに、ユニタリ演算と、そのユニタリ演算を実行する量子プログラムとを同一視し、同じ記号で表現する。例えば、ユニタリ演算Ｕ、Ｖの積ＵＶに関し、ユニタリ演算Ｕ、Ｖに対応する量子プログラムをＵ、Ｖと表現し、それらの積ＵＶに対応する量子プログラムをＵＶと表現する。
【００４７】
なお、量子プログラムで表現されるユニタリ演算の実現方法としては、例えば、古典的なコンピュータによる量子コンピュータのエミュレータを用いる方法、イオントラップ、キャビティＱＥＤ、ＮＭＲ、超伝導体、光学系等を用いた量子コンピュータを用いる方法等、様々な方法が考えられる。また、後述する本実施形態に係る暗号化方法、復号方法の実現に用いられる量子コンピュータは、いずれの動作原理に基づいてユニタリ演算を実行するものであってもよいし、将来新たに考案された他の動作原理に基づくユニタリ演算の実行手段であってもよい。
【００４８】
［２−１：鍵生成装置１００の機能構成］
以下、図２を参照しながら、本実施形態に係る鍵生成方法を実現するための鍵生成装置１００の機能構成について説明する。図２は、本実施形態に係る鍵生成装置１００の機能構成例を示す説明図である。
【００４９】
図２に示すように、鍵生成装置１００は、主に、公開鍵生成部１１０、及び秘密鍵生成部１３０により構成される。公開鍵生成部１１０は、公開鍵Ｐ（量子プログラムＰ）を生成する処理ブロックである。一方、秘密鍵生成部１３０は、秘密鍵Ｓ（量子プログラムＳ）を生成する処理ブロックである。以下、量子回路図を用いて各処理ブロックの機能について、より詳細に説明する。
【００５０】
なお、ここでは一例として量子回路図を用いるが、本実施形態の技術的範囲は量子回路モデルに限定されない。例えば、後述する量子回路図を構成するユニバーサル量子回路をグラフ図に置き換えることにより、量子回路モデルに基づく構成を観測ベース量子計算モデルに基づく構成に変形することができる。
【００５１】
このような変形を行っても、本実施形態に係る鍵生成処理の内容に影響を与えることはない。また、ユニバーサル量子回路をグラフ図に変換するのではなく、後述するユニバーサル量子回路の構築方法と同様の操作ステップを経てグラフ図を構築することでグラフ図に基づく鍵生成方法を実現することができる。
【００５２】
（２−１−１：公開鍵生成部１１０の機能）
まず、公開鍵生成部１１０の機能構成について説明する。
【００５３】
図２に示すように、公開鍵生成部１１０は、主に、乱数発生部１１２と、量子プログラム生成部１１４と、制御化部１１６と、量子プログラム付加部１１８と、難読化部１２０とにより構成される。以下、公開鍵の生成過程に沿って各構成要素の機能を説明する。
【００５４】
（乱数発生部１１２の機能）
まず、乱数発生部１１２は、乱数発生器を用いて乱数列を生成する。乱数発生器としては、例えば、熱雑音を利用した物理乱数発生器や、メルセンヌツイスター法等に基づく疑似乱数発生器等が利用される。乱数列を生成すると、乱数発生部１１２は、生成した乱数列を量子プログラム生成部１１４に入力する。
【００５５】
（量子プログラム生成部１１４の機能）
量子プログラム生成部１１４は、ｎ量子ビットの量子状態を入力とするユニタリ演算Ｕ１，…，Ｕｍの量子プログラムＵ１，…，Ｕｍと、ｍ量子ビットの量子状態を入力とするユニタリ演算Ｌ、Ｒの量子プログラムＬ、Ｒとを生成する。このとき、量子プログラム生成部１１４は、乱数発生部１１２により入力された乱数列を利用し、予め用意されたユニバーサル量子回路と呼ばれる数種類の量子回路をランダムに組み合わせて量子プログラムＵ１，…，Ｕｍ、Ｌ、Ｒを生成する。
【００５６】
ここで、図４、図５を参照しつつ、量子プログラム生成部１１４による量子プログラムＸ（Ｘ＝Ｕ１，…，Ｕｍ、Ｌ、Ｒ）の生成方法について、より具体的に説明する。
【００５７】
図４には、量子プログラムＸの生成に用いるユニバーサル量子回路の例が示されている。この例では、１量子ビットに対するアダマール回路Ｈ、１量子ビットに対するπ／８位相シフト回路Ｔ、１量子ビットに対する位相回路Ｓ、２量子ビットに対する制御ＮＯＴ回路ＣＮが量子プログラムＸの生成に用いるユニバーサル量子回路として利用される。また、量子プログラムＸの生成には、π／８位相シフト回路Ｔに対応するユニタリ演算Ｔのエルミート共役Ｈ†に対応するエルミート共役π／８位相シフト回路Ｔ†、位相回路Ｓに対応するユニタリ演算Ｓのエルミート共役Ｓ†に対応するエルミート共役位相回路Ｓ†が利用される。
【００５８】
また、ユニバーサル量子回路Ｈ、Ｔ、Ｓ、ＣＮには、図４に示すように、互いに異なる数字が予め割り当てられる。さらに、エルミート共役が元のユニバーサル量子回路と異なる場合、そのユニバーサル量子回路のエルミート共役Ｔ†、Ｓ†にも、互いに異なる数字が予め割り当てられる。
【００５９】
図４の例では、アダマール回路Ｈに０、π／８位相シフト回路Ｔに１、エルミート共役π／８位相シフト回路Ｔ†に２、位相回路Ｓに３、エルミート共役位相回路Ｓ†に４、制御ＮＯＴ回路ＣＮに５が割り当てられている。量子プログラム生成部１１４は、これらのユニバーサル量子回路を組み合わせて量子プログラムＸを生成する。ユニバーサル量子回路の組み合わせは、図５に示す方法により決定される。
【００６０】
なお、ここでは具体例として３本の量子レジスタ（量子レジスタ１〜３）を含む量子プログラムＸを生成する方法について考える。まず、量子プログラム生成部１１４は、０〜５の数字を乱数発生部１１２に生成させ、乱数発生部１１２から入力された数字を用いてユニバーサル量子回路を１つ選択する（Ｓｔｅｐ．１）。例えば、乱数発生部１１２から０が入力された場合、量子プログラム生成部１１４は、０が割り当てられたアダマール回路Ｈを選択する。
【００６１】
Ｓｔｅｐ．１で選択したユニバーサル量子回路が１量子ビットに対する量子回路である場合、量子プログラム生成部１１４は、１〜３の数字を乱数発生部１１２に１つ生成させ、乱数発生部１１２から入力された数字を用いてユニバーサル量子回路を配置する量子レジスタを選択する（Ｓｔｅｐ．２）。
【００６２】
一方、Ｓｔｅｐ．１で選択したユニバーサル量子回路が２量子ビットに対する量子回路である場合、量子プログラム生成部１１４は、１〜３の数字を乱数発生部１１２に２つ生成させ、乱数発生部１１２から入力された数字を用いてユニバーサル量子回路を配置する量子レジスタを選択する（Ｓｔｅｐ．２）。
【００６３】
例えば、Ｓｔｅｐ．１で制御ＮＯＴ回路ＣＮを選択した場合、量子プログラム生成部１１４は、乱数発生部１１２から最初に入力された数字に対応する量子レジスタを制御レジスタに設定し、次に入力された数字に対応する量子レジスタをターゲットレジスタに設定して、制御ＮＯＴ回路ＣＮを配置する。但し、乱数発生部１１２から同じ数字が２つ入力された場合、量子プログラム生成部１１４は、乱数発生部１１２に再び乱数を生成させる。
【００６４】
量子プログラム生成部１１４は、上記のＳｔｅｐ．１、Ｓｔｅｐ．２の操作をｎの多項式関数ｐ（ｎ）回程度繰り返し、乱数発生部１１２から入力される乱数列に基づいてユニバーサル量子回路を順次量子レジスタに配置して量子プログラムＸを生成する。上記の例では量子レジスタの数を３としたが、量子プログラム生成部１１４の機能はこれに限定されない。なお、図５は、上記のＳｔｅｐ．１、Ｓｔｅｐ．２の操作を５回繰り返して得られた量子プログラムＸの一例である。
【００６５】
量子プログラム生成部１１４は、上記の方法を繰り返し実行し、量子プログラムＵ１，…，Ｕｍ、Ｌ、Ｒを生成する。但し、ｎ量子ビットに対する量子プログラムＵ１，…，Ｕｍは、ｎ本の量子レジスタにより構成される。また、ｍ量子ビットに対する量子プログラムＬ、Ｒは、ｍ本の量子レジスタにより構成される。
【００６６】
このようにして量子プログラム生成部１１４により生成された量子プログラムＵ１，…，Ｕｍは、図２に示すように、制御化部１１６に入力される。また、量子プログラム生成部１１４により生成された量子プログラムＬ、Ｒは、量子プログラム付加部１１８に入力される。さらに、量子プログラム生成部１１４により生成された量子プログラムＲは、後述する秘密鍵生成部１３０の逆量子プログラム生成部１３２に入力される。
【００６７】
（制御化部１１６の機能）
制御化部１１６は、量子プログラム生成部１１４から入力された量子プログラムＵ１，…，Ｕｍを制御化して量子プログラムＣＵを生成する。ここで言う制御化とは、ｍ本の制御レジスタに入力される量子状態に応じて、演算に利用される量子プログラムＵ１，…，Ｕｍを選択できるようにすることを意味する。量子プログラムＣＵは、例えば、図６に示す量子回路図で表現される。
【００６８】
図６に示すように、量子プログラムＣＵは、ｍ＋ｎ本の量子レジスタを含む。そして、ｍ＋ｎ本の量子レジスタのうち、ｍ本の量子レジスタは、量子プログラムＵ１，…，Ｕｍの選択に利用される制御レジスタ（制御レジスタ１〜ｍ）である。また、残りｎ本の量子レジスタは、量子プログラムＵ１，…，Ｕｍが配置されるデータレジスタである。なお、量子プログラムＣＵの処理は、左側から右側に向かって進行する。また、各量子レジスタには、それぞれ１量子ビットの量子状態が入力される。
【００６９】
図６の例では、データレジスタ上に、左側から右側に向かって量子プログラムＵ１，…，Ｕｍが順に配置されている。そして、量子プログラムＵ１には制御レジスタ１が接続され、量子プログラムＵ２には制御レジスタ２が接続され、量子プログラムＵ３には制御レジスタ３が接続され、…、量子プログラムＵｍには制御レジスタｍが接続されている。そして、量子プログラムＵ１を含む回路を第１量子ビット制御Ｕ１回路、量子プログラムＵ２を含む回路を第２量子ビット制御Ｕ２回路、量子プログラムＵ３を含む回路を第３量子ビット制御Ｕ３回路、…、量子プログラムＵｍを含む回路を第ｍ量子ビット制御Ｕｍ回路と呼ぶことにする。
【００７０】
量子プログラムＣＵは、制御レジスタ１に１量子ビットの量子状態｜１＞が入力された場合、データレジスタに入力された量子状態に対して量子プログラムＵ１が実行されるように構成されている。同様に、量子プログラムＣＵは、制御レジスタｋ（ｋ＝２〜ｍ）に１量子ビットの量子状態｜１＞が入力された場合、データレジスタに入力された量子状態に対して量子プログラムＵｋが実行されるように構成されている。
【００７１】
そのため、データレジスタに入力された量子状態に対して実行される量子プログラムＵ１，…，Ｕｍの組み合わせは、制御レジスタ１〜ｍに入力される量子状態により制御される。なお、制御レジスタｋ’（ｋ’＝１〜ｍ）に量子状態｜０＞が入力された場合には、データレジスタに入力された量子状態に対して量子プログラムＵｋ’が実行されない。
【００７２】
このような制御化された量子プログラムＣＵは、次のようにして生成される。上記の通り、量子プログラム生成部１１４により生成された量子プログラムＵ１は、ユニバーサル量子回路で構成されている。
【００７３】
ユニバーサル量子回路を第１量子ビット制御Ｕ１回路のように制御化する方法は、“Ｎｉｅｌｓｅｎ ａｎｄ Ｃｈｕａｎｇ， Ｑｕａｎｔｕｍ Ｃｏｍｐｕｔａｔｉｏｎ ａｎｄ Ｑｕａｎｔｕｍ Ｉｎｆｏｒｍａｔｉｏｎ，
Ｃａｍｂｒｉｄｇｅ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ”に記載されている。そこで、この方法を量子プログラムＵ１に含まれる全てのユニバーサル量子回路に適用し、制御レジスタ１に対して全てのユニバーサル量子回路を制御化することで、第１量子ビット制御Ｕ１回路が生成される。同様に、第ｋ量子ビット制御Ｕｋ回路（ｋ＝２〜ｍ）が生成される。
【００７４】
このようにして制御化部１１６により生成された量子プログラムＣＵは、図２に示すように、量子プログラム付加部１１８に入力される。また、この量子プログラムＣＵは、後述する秘密鍵生成部１３０の逆量子プログラム生成部１３２に入力される。
【００７５】
（量子プログラム付加部１１８の機能）
上記の通り、量子プログラム付加部１１８には、量子プログラム生成部１１４により生成された量子プログラムＬ、Ｒ、及び制御化部１１６により生成された量子プログラムＣＵが入力される。量子プログラム付加部１１８は、量子プログラムＣＵに対して量子プログラムＬ、Ｒを付加し、図７に示すような量子プログラムＧを生成する。
【００７６】
まず、量子プログラム付加部１１８は、量子プログラムＲを第１量子ビット制御Ｕ１回路の前段に配置する。このとき、量子プログラム付加部１１８は、制御レジスタ１〜ｍへの入力が量子プログラムＲへの入力となり、量子プログラムＲの出力が量子プログラムＣＵの制御レジスタ１〜ｍへの入力となるように量子プログラムＲを配置する。
【００７７】
次に、量子プログラム付加部１１８は、量子プログラムＬを第ｍ量子ビット制御Ｕｍ回路の後段に配置する。このとき、量子プログラム付加部１１８は、量子プログラムＣＵの制御レジスタ１〜ｍへの入力が量子プログラムＬの入力となるように量子プログラムＬを配置する。
【００７８】
ここで、量子プログラムＣＵに量子プログラムＲ、Ｌを付加する意義について述べる。
【００７９】
例えば、量子プログラムＣＵに含まれる量子プログラムＵｋを実行させる場合、量子プログラムＣＵの制御レジスタｋに１量子ビットの量子状態｜１＞を入力する必要がある。そのため、量子プログラムＲの実行後に量子プログラムＣＵの制御レジスタｋに対して量子状態｜１＞が入力されるよう、量子プログラムＲの入力を制御する必要がある。
【００８０】
量子プログラムＲの回路構成を知っている者は、量子プログラムＲの入力を適切に制御して量子プログラムＣＵの制御レジスタｋに量子状態｜１＞を入力することができる。しかし、量子プログラムＲの回路構成を知らない者は、量子プログラムＣＵの制御レジスタｋに量子状態｜１＞を入力することができない。
【００８１】
つまり、量子プログラムＲを知らない者は、量子プログラムＣＵに含まれる量子プログラムＵｋを指定するために、どのような量子状態を量子プログラムＧに入力すればよいかが分からない。言い換えると、量子プログラムＲを付加する意義は、量子プログラムＣＵに含まれる量子プログラムＵｋの指定方法を隠蔽することにある。
【００８２】
一方、量子プログラムＬを付加する意義は、量子プログラムＲの秘匿性を高めることにある。仮に、量子プログラムＣＵが特徴的な構造を有する場合、量子プログラムＬを付加しないと、後述する難読化後に得られる量子プログラムＧの情報から量子プログラムＲが分離されてしまう恐れがある。そのため、量子プログラムＣＵに対して量子プログラムＲ、Ｌが付加される。
【００８３】
このようにして量子プログラム付加部１１８により生成された量子プログラムＧは、難読化部１２０に入力される。
【００８４】
（難読化部１２０の機能）
難読化部１２０は、図８に示すように、量子プログラム付加部１１８から入力された量子プログラムＧを別の量子プログラムＰへと変換（難読化）する。この量子プログラムＰは、量子プログラムＧに対応するユニタリ演算Ｇと同じ内容を有するユニタリ演算Ｐに対応する。
【００８５】
つまり、難読化部１２０は、ユニタリ演算の内容を変えずに量子プログラムＧを量子プログラムＰに変換する。この変換により量子プログラムＰから量子プログラムＲの情報を得ることが困難になる。その結果、量子プログラムＣＵの情報が秘匿される。難読化部１２０は、公開鍵Ｐとして量子プログラムＰを出力する。
【００８６】
ここで、図９、図１０を参照しながら、上記の難読化の方法について、より詳細に説明する。なお、ここでは多項式関数ｐ（ｎ）個程度のユニバーサル量子回路で構成される量子プログラムＵに対する難読化の方法について説明する。
【００８７】
まず、難読化部１２０は、量子プログラムＵを構成するユニバーサル量子回路を全て左側に詰める。この操作を行うことにより、同時に実行可能なユニバーサル量子回路の組が区別し易くなる。
【００８８】
次いで、難読化部１２０は、図９に示すように、同時実行可能なユニバーサル量子回路の組み合わせに対して個々に数字を割り当てる（ラベリング；Ｓｔｅｐ．１）。このとき、同時実行可能なユニバーサル量子回路の組み合わせは、各量子レジスタに対して１つ程度になる。
【００８９】
そのため、難読化部１２０は、量子レジスタの番号（以下、レジスタ番号）と、同時実行可能なユニバーサル量子回路の組み合わせに割り当てた番号（以下、組み合わせ番号）とを指定することにより、図１０に示すように、１つのユニバーサル量子回路を指定できるようになる。
【００９０】
次いで、難読化部１２０は、乱数発生器を利用して乱数ｒを発生させる。但し、乱数ｒは、１から組み合わせ番号の最大数までの数字である。そして、難読化部１２０は、乱数ｒに等しい組み合わせ番号に対応するユニバーサル量子回路の組を１つ指定する。次いで、難読化部１２０は、１〜ｎの乱数を発生させる乱数発生器を用いてｓ＝ｌｏｇ（ｎ）個程度の乱数列（ｒ１，ｒ２，…，ｒｓ）を発生させる。
【００９１】
次いで、難読化部１２０は、発生させた乱数列を用いて、指定した組に含まれるユニバーサル量子回路（ｒ，ｒｉ）＝｛（ｒ，ｒ１），（ｒ，ｒ２），…，（ｒ，ｒｓ）｝を指定する。但し、難読化部１２０は、指定した位置にユニバーサル量子回路が存在しない場合、その位置を無視する。また、難読化部１２０は、指定した位置の全てにユニバーサル量子回路が存在しない場合、乱数発生器を用いて乱数列を再度発生させる。
【００９２】
次いで、難読化部１２０は、指定したユニバーサル量子回路について、時間が正の方向に隣り合うユニバーサル量子回路を順次グループに加える。但し、難読化部１２０は、ユニバーサル量子回路をグループに加える過程で、制御ＮＯＴ回路ＣＮの制御部又はターゲット部のいずれか一方が、指定した量子レジスタの組（ｒ１，ｒ２，…，ｒｓ）とは異なる量子レジスタｒｓ＋１を指定する場合、その量子レジスタｒｓ＋１を新たに量子レジスタの組に加えて新たな量子レジスタの組（ｒ１，ｒ２，…，ｒｓ，ｒｓ＋１）を生成する。
【００９３】
そして、難読化部１２０は、新たな量子レジスタの組（ｒ１，ｒ２，…，ｒｓ，ｒｓ＋１）を対象として、時間が正の方向に隣り合うユニバーサル量子回路を順次グループに加える。難読化部１２０は、ユニバーサル量子回路の合計がｌｏｇ Ｏ（ｐ（ｎ））程度になるまでグループにユニバーサル量子回路を加え続ける。
【００９４】
このようにして生成されたユニバーサル量子回路の組［｛（ｒ，ｒｉ）｝，｛（ｒ，ｒｊ）｝，…，｛（ｒ，ｒｋ）｝］を部分量子プログラムｇと呼ぶことにする。上記の方法により、難読化部１２０は、量子プログラムＵの中から部分量子プログラムｇを選択する（Ｓｔｅｐ．２）。
【００９５】
なお、部分量子プログラムｇを選択する過程で、ユニバーサル量子回路の選択に任意性がある場合には乱数を用いて選択するものとする。次に、難読化部１２０は、選択した部分量子プログラムｇを、その部分量子プログラムｇにより表現されるユニタリ演算ｇを変更せずに、別の等価な部分量子プログラムｇ’に置き換える。
【００９６】
例えば、難読化部１２０は、部分量子プログラムｇに等価な部分量子プログラムの全数検索を実施し、検出された部分量子プログラムの中からランダムに１つの部分量子プログラムｇ’を選択する。
【００９７】
この例では、量子プログラムＵに含まれるユニバーサル量子回路の数がｌｏｇ Ｏ（ｐ（ｎ））程度であるため、置き換え可能な部分量子プログラムの表現は、Ｏ（ｐ（ｎ））以下となる。従って、部分量子プログラムの全数検索は、多項式時間以内に終了する。なお、置き換え可能な部分量子プログラムが存在しない場合には、ユニバーサル量子回路の数をｌｏｇ Ｏ（ｐ（ｎ））＋２程度に拡張すればよい。
【００９８】
上記の処理を多項式回数だが十分に繰り返すことにより、量子プログラムＧの難読化が実現される。なお、上記の難読化で、量子プログラムＲと量子プログラムＣＵとを跨ぐ部分の部分量子プログラムがｎの多項式回数だが十分な回数行われることが望ましい。
【００９９】
（難読化により実現される計算量的複雑性について）
これまで説明してきた通り、本実施形態に係る量子公開鍵暗号システムは、量子プログラムＲを取り出すことの困難性を安全性の根拠としている。逆に言えば、盗聴者は、量子プログラムＲを取り出すことができれば量子公開鍵暗号システムを破ることができる。本実施形態に係る量子公開鍵暗号システムにおいて、量子プログラムＲを取り出すことの困難性は上記の難読化により実現されている。本実施形態に係る難読化方法を用いると、量子プログラムに高い計算量的複雑性が実現される。
【０１００】
本実施形態に係る難読化方法を用いて生成された量子プログラムＰから量子プログラムＲを取り出す盗聴者の攻撃は、量子計算量的複雑性クラスＱｕａｎｔｕｍ Ｍｅｒｌｉｎ Ａｒｔｈｕｒ困難（ＱＭＡ困難）に属する。なお、本実施形態に係る難読化方法は任意の量子プログラムにも適用可能である。
【０１０１】
また、量子プログラムＰに加え、盗聴者以外の者が送信した暗号文を盗聴者が取得し、これらの情報から量子プログラムＲを取り出そうと試みるのではないか、と考えるかもしれない。しかし、このような攻撃は意味がない。なぜなら、盗聴者自身も公開鍵Ｐである量子プログラムＰを用いて任意の量子状態を暗号化できるからである。
【０１０２】
つまり、量子プログラムＰと暗号文との組み合わせから量子プログラムＲを取り出す攻撃は、量子プログラムＰから量子プログラムＲを取り出す攻撃と等価である。このように、本実施形態に係る難読化方法を適用することにより、高い安全性が保証される。
【０１０３】
以上、公開鍵生成部１１０の機能について説明した。
【０１０４】
（２−１−２：秘密鍵生成部１３０の機能）
次に、秘密鍵生成部１３０の機能について説明する。
【０１０５】
図２に示すように、秘密鍵生成部１３０は、主に、逆量子プログラム生成部１３２と、接続部１３４とにより構成される。以下、秘密鍵の生成過程に沿って各構成要素の機能を説明する。
【０１０６】
（逆量子プログラム生成部１３２の機能）
公開鍵生成部１１０の説明において述べた通り、逆量子プログラム生成部１３２には、量子プログラム生成部１１４により生成された量子プログラムＲ、及び制御化部１１６により生成された量子プログラムＣＵが入力される。
【０１０７】
まず、逆量子プログラム生成部１３２は、量子プログラムＲに対応するユニタリ演算Ｒの複素共役Ｒ＊に対応する量子プログラムＲ＊を生成する。また、逆量子プログラム生成部１３２は、量子プログラムＣＵに対応するユニタリ演算ＣＵのエルミート共役ＣＵ†に対応する量子プログラムＣＵ†を生成する。これら量子プログラムＲ＊、ＣＵ†の生成は、図１１のようにして実行される。
【０１０８】
図１１には、ユニバーサル量子回路Ａ、Ｂ、Ｃ、Ｄが左側から右側へと配置された量子プログラムＹに対する複素共役化及びエルミート共役化の方法が例示されている。
【０１０９】
量子プログラムＹをエルミート共役化する場合、逆量子プログラム生成部１３２は、まず、ユニバーサル量子回路Ａ、Ｂ、Ｃ、Ｄの並び順を逆に並べ替え、ユニバーサル量子回路Ｄ、Ｃ、Ｂ、Ａの順で左側から右側へと配置する。次いで、逆量子プログラム生成部１３２は、個々のユニバーサル量子回路Ａ、Ｂ、Ｃ、Ｄをそれぞれエルミート共役化したユニバーサル量子回路Ａ†、Ｂ†、Ｃ†、Ｄ†に置き換える。その結果、量子プログラムＹをエルミート共役化した量子プログラムＹ†が得られる。
【０１１０】
また、量子プログラムＹを複素共役化する場合、逆量子プログラム生成部１３２は、量子プログラムＹを構成するユニバーサル量子回路Ａ、Ｂ、Ｃ、Ｄを複素共役化したユニバーサル量子回路Ａ＊、Ｂ＊、Ｃ＊、Ｄ＊に置き換える。その結果、量子プログラムＹを複素共役化した量子プログラムＹ＊が得られる。
【０１１１】
なお、転置化した量子プログラムＹＴは、ユニバーサル量子回路Ａ、Ｂ、Ｃ、Ｄの並び順を逆にした後、ユニバーサル量子回路Ａ、Ｂ、Ｃ、Ｄをそれぞれ転置化したユニバーサル量子回路ＡＴ、ＢＴ、ＣＴ、ＤＴに置き換えることにより生成される。これらの各演算過程は、多項式関数ｐ（ｎ）個のユニバーサル量子回路で構成される量子プログラムに対し、２ｐ（ｎ）回程度の演算で完了する。
【０１１２】
このようにして逆量子プログラム生成部１３２により生成された量子プログラムＣＵ†、Ｒ＊は、接続部１３４に入力される。なお、量子プログラムＣＵ†は、量子プログラムＣＵの逆ユニタリ演算を実行するための量子プログラムである。また、量子プログラムＲ＊は、量子プログラムＲＴの逆ユニタリ演算を実行するための量子プログラムである。
【０１１３】
（接続部１３４の機能）
接続部１３４は、図１２に示すように、逆量子プログラム生成部１３２により生成された量子プログラムＣＵ†、Ｒ＊を接続して量子プログラムＳを生成する。このとき、接続部１３４は、量子プログラムＣＵ†の前段に量子プログラムＲ＊を配置する。また、接続部１３４は、量子プログラムＲ＊の出力が量子プログラムＣＵ†の制御レジスタ１〜ｍの入力となるように量子プログラムＲ＊と量子プログラムＣＵ†とを接続する。そして、接続部１３４は、秘密鍵Ｓとして量子プログラムＳを出力する。
【０１１４】
以上、秘密鍵生成部１３０の機能について説明した。
【０１１５】
以上説明した通り、鍵生成装置１００は、古典情報で記述される量子プログラムＰ、Ｓをそれぞれ公開鍵Ｐ、秘密鍵Ｓとして出力する。このように、公開鍵Ｐが古典情報で記述されているため、公開鍵Ｐの同定を行っても暗号鍵としての利用可能性を失わずに済む。また、量子プログラムＰが本実施形態に係る難読化方法で難読化されているため、量子コンピュータを用いた攻撃に対しても極めて高い安全性が保証される。
【０１１６】
［２−２：鍵生成処理の詳細］
次に、図３を参照しながら、本実施形態に係る鍵生成処理の流れについて説明する。図３は、本実施形態に係る鍵生成処理の流れを示す説明図である。なお、図３に示した鍵生成処理の各処理ステップは、上記の鍵生成装置１００により実行される。
【０１１７】
（２−２−１：公開鍵Ｐの生成方法）
まず、公開鍵Ｐの生成方法に係る処理の流れについて説明する。ここで説明する処理は、上記の公開鍵生成部１１０により実行される。
【０１１８】
公開鍵の生成処理がスタートすると、公開鍵生成部１１０は、まず、乱数発生部１１２の機能により乱数を発生させる（Ｓ１０２）。次いで、公開鍵生成部１１０は、発生した乱数列を利用して、量子プログラム生成部１１４の機能によりｍ個の量子プログラムＵ１，…，Ｕｍ、及び２個の量子プログラムＬ、Ｒを生成する（Ｓ１０４）。
【０１１９】
ステップＳ１０４にて生成されたｍ個の量子プログラムＵ１，…，Ｕｍは、次のステップＳ１０６の処理にて利用される。また、ステップＳ１０４にて生成された量子プログラムＬ、Ｒは、後段のステップＳ１０８にて利用される。さらに、ステップＳ１０４にて生成された量子プログラムＲは、秘密鍵生成方法に係る処理のステップＳ１１２にて利用される。
【０１２０】
ステップＳ１０６に処理が進行すると、公開鍵生成部１１０は、ステップＳ１０４で生成されたｍ個の量子プログラムＵ１，…，Ｕｍを利用し、制御化部１１６の機能により制御化された量子プログラムＣＵを生成する（Ｓ１０６）。ステップＳ１０６にて生成された量子プログラムＣＵは、次のステップＳ１０８、及び秘密鍵生成方法に係る処理のステップＳ１１２にて利用される。
【０１２１】
次いで、公開鍵生成部１１０は、ステップＳ１０４にて生成された量子プログラムＬ、Ｒ、及びステップＳ１０６にて生成された量子プログラムＣＵを利用し、量子プログラム付加部１１８の機能により量子プログラムＧを生成する（Ｓ１０８）。ステップＳ１０８にて生成された量子プログラムＧは、次のステップＳ１１０にて利用される。
【０１２２】
次いで、公開鍵生成部１１０は、難読化部１２０の機能によりステップＳ１０８にて生成された量子プログラムＧを難読化し、量子プログラムＰを生成する（Ｓ１１０）。ステップＳ１１０にて生成された量子プログラムＰは、公開鍵Ｐとして出力される。
【０１２３】
以上、公開鍵Ｐの生成方法に係る処理の流れについて説明した。
【０１２４】
（２−２−２：秘密鍵Ｓの生成方法）
次に、秘密鍵Ｓの生成方法に係る処理の流れについて説明する。ここで説明する処理は、主に上記の秘密鍵生成部１３０により実行される。
【０１２５】
秘密鍵の生成処理がスタートすると、秘密鍵生成部１３０は、まず、公開鍵生成方法に係る処理のステップＳ１０４、Ｓ１０６にて生成された量子プログラムＲ、ＣＵを利用し、逆量子プログラム生成部１３２の機能により量子プログラムＣＵ†、Ｒ＊を生成する（Ｓ１１２）。ステップＳ１１２にて生成された量子プログラムＣＵ†、Ｒ＊は、次のステップＳ１１４にて利用される。
【０１２６】
次いで、秘密鍵生成部１３０は、接続部１３４の機能によりステップＳ１１２にて生成された量子プログラムＣＵ†、Ｒ＊を接続して量子プログラムＳを生成する（Ｓ１１４）。ステップＳ１１４にて生成された量子プログラムＣＵ†、Ｒ＊は、秘密鍵Ｓとして出力される。
【０１２７】
以上、秘密鍵Ｓの生成方法に係る処理の流れについて説明した。
【０１２８】
以上説明したように、公開鍵Ｐ、秘密鍵Ｓは、古典情報として記述可能な量子プログラムＰ、Ｓにより構成される。そのため、公開鍵Ｐの確実な認証が容易になる。また、公開鍵Ｐは、ステップＳ１１０にて難読化部１２０により実施される難読化処理により量子コンピュータの攻撃に対する十分な安全性が保証されている。このように、本実施形態に係る鍵生成方法を適用することにより、より安全で利便性の高い量子公開鍵暗号システムが実現される。
【０１２９】
＜３：暗号化方法について＞
次に、本実施形態に係る暗号化方法について説明する。本実施形態に係る暗号化方法は、上記の鍵生成方法により生成された公開鍵Ｐを用いて実行される。つまり、本実施形態に係る暗号化方法による暗号化処理は、公開鍵Ｐである量子プログラムＰ、及び暗号化したい量子状態を量子コンピュータに入力することにより実行される。
【０１３０】
以下で説明する本実施形態に係る暗号化処理は、最大エンタングルメント状態を利用する点に１つの特徴がある。特に、本実施形態に係る暗号化方法は、最大エンタングルメント状態の基底の非一意性を利用することで、暗号文の送信者２０が量子プログラムＲの情報を一切知らずに正しく量子状態を暗号化できるようにする点に１つの特徴がある。
【０１３１】
以下、このような本実施形態に係る暗号化方法を実現することが可能な暗号化装置２００の機能構成、及び暗号化方法について順番に説明する。
【０１３２】
［３−１：暗号化装置２００の機能構成］
まず、図１３を参照しながら、本実施形態に係る暗号化装置２００の機能構成について説明する。図１３は、本実施形態に係る暗号化装置２００の機能構成例を示す説明図である。但し、暗号化装置２００は、鍵生成装置１００により生成された公開鍵Ｐ（量子プログラムＰ）を既に取得しているものとする。また、暗号化装置２００は、量子コンピュータ、又は量子コンピュータを利用する装置であるものとする。
【０１３３】
図１３に示すように、暗号化装置２００は、主に、エンタングルメント状態生成部２０２と、量子状態入力部２０４と、暗号化部２０６とにより構成される。また、暗号化部２０６は、鍵生成装置１００により生成された公開鍵Ｐである量子プログラムＰを保持している。なお、この公開鍵Ｐは、認証局３０により認証され、暗号文の送信者２０により同定されているものとする。以下、量子状態の暗号化過程に沿って各構成要素の機能を説明する。
【０１３４】
（エンタングルメント状態生成部２０２の機能）
まず、エンタングルメント状態生成部２０２は、２ｍ量子ビットの最大エンタングルメント状態を生成する。例えば、エンタングルメント状態生成部２０２は、下記の式（１）で表現される２ｍ量子ビットの基底状態を用意する。そして、エンタングルメント状態生成部２０２は、下記の式（１）のテンソル積で結合された基底状態のうち、前半ｍ量子ビットの各々の量子状態に対してアダマール演算を実行する。このアダマール演算を実行すると、下記の式（２）で表現される量子状態が生成される。
【０１３５】
次いで、エンタングルメント状態生成部２０２は、下記の式（２）で表現される量子状態のうち、アダマール演算の結果に対応する各量子ビットを制御量子ビットとして当該量子状態に制御ＮＯＴ演算を施す。この制御ＮＯＴ演算により、下記の式（３）で表現される２ｍ量子ビットの最大エンタングルメント状態が生成される。このようにしてエンタングルメント状態生成部２０２により生成された最大エンタングルメント状態｜Φｍ＞は、暗号化部２０６に入力される。
【０１３６】
【数１】
…（１）
…（２）
…（３）
【０１３７】
なお、上記の式（１）〜（３）に現れるｉは、二進表示したビット列を十進表示で表現したものである。例えば、２量子ビット状態について考えると、二進表示｜００＞は十進表示｜０＞、二進表示｜０１＞は十進表示｜１＞、二進表示｜１０＞は十進表示｜２＞、二進表示｜１１＞は十進表示｜３＞と表現される。また、上記の式（１）〜（３）に関する量子計算は、イオントラップを用いた量子コンピュータを用いて実行可能である。
【０１３８】
（量子状態入力部２０４の機能）
量子状態入力部２０４は、暗号文の受信者１０へと送信したい量子状態を用意し、暗号化部２０６に入力する機能を提供する。例えば、量子状態入力部２０４は、送信したい古典情報を符号化し、その古典情報に対応するｎ量子ビットの量子状態｜ψｎ＞を生成する。あるいは、量子状態入力部２０４は、暗号化装置２００の外部で生成された量子状態｜ψｎ＞を取得する。そして、量子状態入力部２０４は、生成又は取得した量子状態｜ψｎ＞を暗号化部２０６に入力する。
【０１３９】
（暗号化部２０６の機能）
暗号化部２０６は、量子状態入力部２０４により入力されたｎ量子ビットの量子状態｜ψｎ＞を公開鍵Ｐである量子プログラムＰを用いて暗号化する。この暗号化は、量子コンピュータを利用し、図１５に示すような方法で実行される。まず、暗号化部２０６は、最大エンタングルメント状態生成部２０２により生成された２ｍ量子ビットの最大エンタングルメント状態をｍ量子ビット毎に分け、一方（前半）をそのまま保持する。
【０１４０】
次いで、暗号化部２０６は、他方（後半）ｍ量子ビットの量子状態を量子プログラムＰの制御レジスタ１〜ｍに入力する。さらに、暗号化部２０６は、量子状態入力部２０４から入力された量子状態｜ψｎ＞を量子プログラムＰのデータレジスタに入力する。量子プログラムＰの実行が完了すると、暗号化部２０６は、量子プログラムＰの制御レジスタ１〜ｍから得られる出力を破棄する。そして、暗号化部２０６は、保持していたｍ量子ビットの量子状態に対し、量子プログラムＰのデータレジスタから得られる出力を付加して暗号文（暗号化された量子状態）を生成する。
【０１４１】
このようにして生成された暗号文は、下記の式（４）で表現される。また、暗号化部２０６により生成された暗号文は、量子通信路を介して暗号文の送信者２０から暗号文の受信者１０へと送信される。
【０１４２】
【数２】
…（４）
【０１４３】
（最大エンタングルメント状態の基底の非一意性について）
ここで、最大エンタングルメント状態の基底の非一意性について説明する。本実施形態に係る量子公開鍵暗号システムにおいては、この著しい性質により、量子プログラムＲの情報を一切用いずに正しく暗号化することができるのである。その結果、暗号文の受信者１０は、量子状態を含む暗号化用の鍵（公開鍵Ｐ）を用意しなくて済むようになる。以下、これらの点について説明する。
【０１４４】
２ｍ量子ビットの最大エンタングルメント状態｜Φｍ＞は、上記の式（４）で表現される。ユニタリ演算の性質（ユニタリ演算Ｒに対してＲ†＝ＲＴが成り立つ。また、Ｒｊｋ＝＜ｊ｜Ｒ｜ｋ＞＝＜ｋ｜ＲＴ｜ｊ＞である。）を用いて上記の式（４）を展開すると、最大エンタングルメント状態｜Φｍ＞は、下記の式（５）のように変形される。
【０１４５】
【数３】
…（５）
【０１４６】
上記の式（５）から明らかなように、最大エンタングルメント状態｜Φｍ＞の基底は、ユニタリ変換Ｒを用いて変換することができる。ここでは後段の説明に対する理解を助けるためにユニタリ変換をＲで表現したが、任意のユニタリ変換Ｒに対して上記の変換が実現される。この性質を最大エンタングルメント状態の基底の非一意性と呼ぶ。
【０１４７】
次に、上記の式（５）で表現される最大エンタングルメント状態｜Φｍ＞及び量子プログラムＰを用いてｎ量子ビットの量子状態｜ψｎ＞を暗号化する過程を式で示す。なお、本実施形態に係る量子公開鍵暗号システムにおいて量子プログラムＰは難読化した状態で用いられるが、ここでは簡単のために難読化前の量子プログラムＧを用いて量子状態｜ψｎ＞を暗号化する過程を式で示す。なお、量子プログラムＰは、量子プログラムＧの等価変形である。そのため、最終的に生成される暗号化された量子状態は同じものとなる。
【０１４８】
最大エンタングルメント状態｜Φｍ＞の前半ｍ量子ビットは保持され、後半ｍ量子ビットが量子プログラムＧの制御レジスタ１〜ｍに入力される。そして、量子プログラムＧに含まれるユニタリ演算Ｒが最大エンタングルメント状態｜Φｍ＞の後半ｍ量子ビットに施される。この演算操作は、下記の式（６）で表現される。
【０１４９】
なお、最大エンタングルメント状態｜Φｍ＞は、上記の式（５）で表現した最大エンタングルメント状態の基底の非一意性により、量子プログラムＲに対応するユニタリ演算Ｒを用いて表現することができる。そのため、下記の式（５）のように式を展開することができる。
【０１５０】
次に、下記の式（５）で表現される演算操作の結果が量子プログラムＣＵの制御レジスタ１〜ｍに入力される。量子プログラムＣＵの演算は、制御レジスタ１〜ｍに入力された量子状態と、データレジスタに入力される暗号化対象の量子状態｜ψｎ＞と施される。この演算操作は、下記の式（７）で表現される。量子プログラムＣＵの内容は、制御レジスタ１〜ｍの入力に応じて選択された量子プログラムＵｉをデータレジスタに入力された量子状態に｜ψｎ＞に作用させるというものである。そのため、量子プログラムＣＵによる演算は、下記の式（７）に示すように式展開される。
【０１５１】
次に、下記の式（７）で表現される演算操作の結果が量子プログラムＬに入力される。但し、量子プログラムＣＵの演算結果のうち、制御レジスタ１〜ｍの出力が量子プログラムＬに入力される。そのため、量子プログラムＬの出力は、下記の式（８）で表現される。さらに、量子プログラムＬの出力Ｌ｜ｉ＞が破棄されるため、この破棄する状態に関する部分トレースととることで、量子プログラムＧの最終的な出力（下記の式（９）に示される密度行列）が得られる。
【０１５２】
【数４】
…（６）
…（７）
…（８）
…（９）
【０１５３】
上記の式展開で重要なことは、最大エンタングルメント状態の基底の非一意性により、量子プログラムＰ（量子プログラムＧ）に対して量子プログラムＲの情報を入力していないにも関わらず、上記の式（６）で展開されたようにユニタリ演算Ｒの情報を用いて量子状態｜ψｎ＞が暗号化される点にある。言い換えると、暗号文の送信者２０は、量子プログラムＲの情報を全く知らないにも関わらず、ユニタリ演算Ｒ†の効果を打ち消して量子状態｜ψｎ＞の暗号化を実行できるのである。
【０１５４】
このように、最大エンタングルメント状態の著しい性質を有効に利用することで、完全に量子プログラムＲの情報が秘匿された安全な量子公開鍵システムが実現されるのである。なお、特開２００８−２９４６６６号公報に記載の量子公開鍵暗号システムは、量子プログラムＲを打ち消すような変換を与える量子情報を暗号文の送信者２０に与える必要があった。
【０１５５】
そのため、本実施形態に係る量子公開鍵暗号システムは、量子プログラムＲを打ち消すための情報を一切与えずに済むのであるから、より安全性の高いものであると言える。また、上記の性質により、暗号化用の鍵（公開鍵Ｐ）に量子状態を含めずに済むため、公開鍵Ｐを古典情報だけで記述することが可能になる。その結果、量子公開鍵暗号システムにおける公開鍵Ｐの確かな認証を可能にすることができる。
【０１５６】
［３−２：暗号化処理の詳細］
次に、図１４を参照しながら、本実施形態に係る暗号化処理の流れについて説明する。図１４は、本実施形態に係る暗号化処理の流れを示す説明図である。なお、図１４に示した暗号化処理の各処理ステップは、上記の暗号化装置２００により実行される。
【０１５７】
暗号化処理がスタートすると、暗号化装置２００は、エンタングルメント状態生成部２０２の機能により２ｍ量子ビットの最大エンタングルメント状態を生成し、暗号化部２０６の機能により前半ｍ量子ビットの量子状態を保持する（Ｓ２０２）。
【０１５８】
次いで、暗号化装置２００は、暗号化部２０６の機能により後半ｍ量子ビットの量子状態を量子プログラムＰの制御レジスタ１〜ｍに入力する（Ｓ２０４）。次いで、暗号化装置２００は、量子状態入力部２０４の機能により暗号化すべきｎ量子ビットの量子状態を生成し、暗号化部２０６の機能により量子プログラムＰのデータレジスタに入力する（Ｓ２０６）。
【０１５９】
次いで、暗号化装置２００は、暗号化部２０６の機能により制御レジスタ１〜ｍ、データレジスタに入力された量子状態を用いて量子プログラムＰの演算を実行する（Ｓ２０８）。次いで、暗号化装置２００は、暗号化部２０６の機能により量子プログラムＰの制御レジスタ１〜ｍから出力された量子状態を破棄する（Ｓ２１０）。
【０１６０】
次いで、暗号化装置２００は、暗号化部２０６の機能により、保持していた前半ｍ量子ビットの量子状態に対し、量子プログラムＰのデータレジスタから出力された量子状態を付加する（Ｓ２１２）。そして、暗号化装置２００は、ステップＳ２１２の付加処理にて得られた量子状態を暗号文として出力する。
【０１６１】
以上、本実施形態に係る暗号処理の流れについて説明した。
【０１６２】
以上説明したように、本実施形態に係る暗号化方法は、最大エンタングルメント状態の基底の非一意性を利用して、量子プログラムＲの情報を用いずに量子状態を暗号化するものである。その結果、暗号化用の鍵（公開鍵Ｐ）に量子状態を含めずに済むため、公開鍵Ｐを古典情報だけで記述できるようになる。さらに、量子プログラムＲの情報が完全に秘匿されるため、非常に高い安全性が実現される。
【０１６３】
＜４：復号方法について＞
次に、本実施形態に係る復号方法について説明する。本実施形態に係る復号方法は、上記の鍵生成方法により生成された秘密鍵Ｓを用いて実行される。つまり、本実施形態に係る復号方法による復号処理は、秘密鍵Ｓである量子プログラムＳ、及び暗号文（暗号化された量子状態）を量子コンピュータに入力することにより実行される。以下、本実施形態に係る復号方法を実現することが可能な復号装置３００の機能構成、及び復号方法について順番に説明する。
【０１６４】
［４−１：復号装置３００の機能構成］
まず、図１６を参照しながら、本実施形態に係る復号装置３００の機能構成について説明する。図１６は、本実施形態に係る復号装置３００の機能構成例を示す説明図である。但し、復号装置３００は、鍵生成装置１００により生成された秘密鍵Ｓ（量子プログラムＳ）を既に取得しているものとする。また、復号装置３００は、量子コンピュータ、又は量子コンピュータを利用する装置であるものとする。
【０１６５】
図１６に示すように、復号装置３００は、主に、暗号文入力部３０２と、復号部３０４とにより構成される。また、復号部３０４は、鍵生成装置１００により生成された秘密鍵Ｓである量子プログラムＳを保持している。以下、暗号化された量子状態の復号過程に沿って各構成要素の機能を説明する。
【０１６６】
（暗号文入力部３０２の機能）
暗号文入力部３０２は、暗号文の送信者２０から量子通信路を介して送信された暗号文（暗号化された量子状態）を取得する。そして、暗号文入力部３０２は、取得した暗号文を復号部３０４に入力する。
【０１６７】
（復号部３０４の機能）
復号部３０４は、ｎ＋ｍ量子ビットの量子状態である暗号文を秘密鍵Ｓである量子プログラムＳを用いて復号する。この復号は、量子コンピュータを利用し、図１８に示すような方法で実行される。まず、復号部３０４は、暗号化装置２００にて付加されたｍ量子ビットの量子状態に対応する暗号文の一部を量子プログラムＳの制御レジスタ１〜ｍに入力する。また、復号部３０４は、暗号化装置２００にて量子プログラムＰのデータレジスタから出力された量子状態を量子プログラムＳのデータレジスタに入力する。
【０１６８】
そして、復号部３０４は、量子コンピュータを利用して量子プログラムＳの演算を実行する。演算の実行後、復号部３０４は、量子プログラムＳの制御レジスタ１〜ｍから出力された量子状態を破棄する。さらに、復号部３０４は、量子プログラムＳのデータレジスタから出力されたｎ量子ビットの量子状態を取得する。このｎ量子ビットの量子状態は、暗号化元の量子状態｜ψｎ＞である。このようにして復号部３０４は、暗号文から元の量子状態｜ψｎ＞を復元する。
【０１６９】
（復号の処理過程について）
ここで、復号部３０４による復号処理の処理過程を式により表現する。復号を開始すると、復号部３０４は、ｍ量子ビットの量子状態に対応する暗号文の一部に対し、量子プログラムＳに含まれる量子プログラムＲ＊を実行する。
【０１７０】
この実行操作は、下記の式（１０）で表現される。次いで、復号部３０４は、量子プログラムＲ＊の出力を量子プログラムＣＵ†の制御レジスタ１〜ｍに入力し、暗号文の残りｎ量子ビットの量子状態を量子プログラムＣＵ†のデータレジスタに入力する。そして、復号部３０４は、量子プログラムＣＵ†の演算を実行する。この演算操作は、下記の式（１１）で表現される。この操作の結果、量子プログラムＣＵ†のデータレジスタから暗号化前の量子状態｜ψｎ＞が出力される。
【０１７１】
【数５】
…（１０）
…（１１）
【０１７２】
以上、復号装置３００の機能について説明した。
【０１７３】
［４−２：復号処理の詳細］
次に、図１７を参照しながら、本実施形態に係る復号処理の流れについて説明する。図１７は、本実施形態に係る復号処理の流れを示す説明図である。なお、図１７に示した復号処理の各処理ステップは、上記の復号装置３００により実行される。
【０１７４】
復号処理がスタートすると、復号装置３００は、暗号文入力部３０２の機能により取得した暗号文を復号部３０４の機能により量子プログラムＳに入力する（Ｓ３０２）。次いで、復号装置３００は、復号部３０４の機能により量子プログラムＳの演算を実行し、量子プログラムＳの制御レジスタ１〜ｍの出力を破棄する（Ｓ３０４）。
【０１７５】
さらに、復号装置３００は、復号部３０４の機能により、量子プログラムＳのデータレジスタから出力された量子状態｜ψｎ＞を取得する（Ｓ３０６）。そして、復号装置３００は、ステップＳ３０６にて取得された量子状態｜ψｎ＞を出力する。
【０１７６】
以上、本実施形態に係る復号処理の流れについて説明した。
【０１７７】
以上説明したように、本実施形態に係る復号方法を適用することにより、秘密鍵Ｓである量子プログラムＳを用いて、本実施形態に係る暗号化方法により生成された暗号文を容易に復号することができる。
【０１７８】
＜５：まとめ＞
最後に、本発明の実施形態に係る技術内容について簡単に纏める。
【０１７９】
本実施形態に係る技術は、量子公開鍵暗号系における鍵生成方法、暗号化方法、復号方法に関する。本実施形態に係る技術は、古典情報を符号化した量子状態、又は量子状態そのものを暗号化するものである。また、量子通信路を利用するものの、この量子公開鍵暗号系のエンティティ構成は古典的な公開鍵暗号系のものと同じ形式に設定することができる。従って、現在の安全性概念に適合させることが容易である。もちろん、高い安全性レベルが実現されることは既に述べた通りである。
【０１８０】
また、本実施形態に係る量子公開鍵暗号システムは、全ての暗号化処理を暗号文の送信者２０側にある量子コンピュータの動作だけで実行する。また、本実施形態に係る量子公開鍵暗号システムは、全ての復号処理を暗号文の受信者１０側にある量子コンピュータの動作だけで実行する。
【０１８１】
そのため、暗号文の送信者２０側にある量子コンピュータと暗号文の受信者１０側にある量子コンピュータとを量子通信路により接続したり、両量子コンピュータを協調的に動作させる必要がない。そのため、暗号文の送信者２０と暗号文の受信者１０との間で暗号化・復号に係る処理を実行する量子暗号系に比べて利便性が非常に高い。
【０１８２】
また、本実施形態に係る量子公開鍵暗号システムにおける暗号化は、認証された公開鍵と暗号文の送信者２０が生成する最大エンタングルメント状態とを用いて実施される。そのため、公開鍵は古典情報で記述することが可能になる。その結果、公開鍵に与えられる認証の有無を容易に検証することが可能になる。そして、認証が与えられた公開鍵を用いて暗号化が行われるため、確実に量子状態を暗号化することができる。
【０１８３】
（認証に関する補足説明）
上記の通り、本実施形態に係る量子公開鍵暗号システムは、古典情報として記述された公開鍵を用いる。そのため、暗号文の送信者２０は、公開鍵に対する認証の有無を容易に検証できる。また、古典情報のみで公開鍵を構成することにより安全性を向上させる効果が得られる。以下、これらの効果について説明を補足する。
【０１８４】
まず、量子公開鍵暗号システムにおける公開鍵の認証を確かに実現するための二つの要求について議論する。一つ目の要求は、配布された公開鍵が認証局３０により認証を受けたものであるかを暗号文の送信者２０が容易に検証（公開鍵の同定）できるようにすることである。二つ目の要求は、公開鍵の同定を行った後でも、その公開鍵が暗号化に利用可能な状態に維持されることである。
【０１８５】
ここで、公開鍵を量子状態で構成する場合について考えてみよう。公開鍵の同定を行うと、同定の結果が古典情報となる。つまり、同定により量子状態に対する何らかの測定が行われたことになる。このとき、量子状態の一部が、測定により古典情報に射影されてしまう。その結果、古典情報に射影された部分は、量子性を利用した暗号化に利用することができない。一方、古典情報に射影されていない部分は、同定が行われていない。つまり、同定と暗号鍵としての利用可能性とはトレードオフの関係にある。
【０１８６】
このトレードオフの関係は、量子状態の測定に関する問題に起因しており、解決することは極めて困難である。その点、本実施形態に係る公開鍵は、古典情報のみで記述されているため、公開鍵の同定に関する上記の問題は生じない。
【０１８７】
以上、添付図面を参照しながら本発明の好適な実施形態について説明したが、本発明は係る例に限定されないことは言うまでもない。当業者であれば、特許請求の範囲に記載された範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、それらについても当然に本発明の技術的範囲に属するものと了解される。
【符号の説明】
【０１８８】
１０ 暗号文の受信者
２０ 暗号文の送信者
３０ 認証局
１００ 鍵生成装置
１１０ 公開鍵生成部
１１２ 乱数発生部
１１４ 量子プログラム生成部
１１６ 制御化部
１１８ 量子プログラム付加部
１２０ 難読化部
１３０ 秘密鍵生成部
１３２ 逆量子プログラム生成部
１３４ 接続部
２００ 暗号化装置
２０２ エンタングルメント状態生成部
２０４ 量子状態入力部
２０６ 暗号化部
３００ 復号装置
３０２ 暗号文入力部
３０４ 復号部
【特許請求の範囲】
【請求項１】
第１の量子情報処理装置と、量子通信路を介して前記第１の量子情報処理装置に接続された第２の量子情報処理装置と、古典通信路を介して前記第１及び第２の量子情報処理装置に接続された認証局と、を含み、
前記第１の量子情報処理装置は、
公開鍵と秘密鍵とを生成する鍵生成部と、
前記鍵生成部により生成された公開鍵を前記古典通信路を介して前記認証局に送信する第１古典送信部と、
前記第２の量子情報処理装置から前記量子通信路を介して送信された、暗号化された量子状態を受信する第１量子受信部と、
前記鍵生成部により生成された秘密鍵を用いて、前記第１量子受信部により受信された、前記暗号化された量子状態から元の量子状態を復元する復号部と、
を有し、
前記認証局は、
前記第１の量子情報処理装置から前記古典通信路を介して送信された公開鍵を受信する第１古典受信部と、
前記第１古典受信部により受信された公開鍵を認証する認証部と、
前記認証部により認証された公開鍵を、前記古典通信路を介して前記第２の量子情報処理装置に送信する第２古典送信部と、
を有し、
前記第２の量子情報処理装置は、
前記認証局から前記古典通信路を介して送信された公開鍵を受信する第２古典受信部と、
前記第２古典受信部により受信された公開鍵を用いて量子状態を暗号化する暗号化部と、
前記暗号化部により暗号化された量子状態を、前記量子通信路を介して前記第１の量子情報処理装置に送信する量子送信部と、
を有する、量子公開鍵暗号システム。
【請求項２】
前記鍵生成部は、
乱数を発生させる乱数発生器と、
前記乱数発生器を用いて発生させた乱数に基づき、ｎ量子ビットに対するｍ種類のユニタリ演算Ｕｉ（ｉ＝１〜ｍ）、及び、ｍ量子ビットに対する２種類のユニタリ演算Ｌ、Ｒに、それぞれ対応する量子プログラムＵｉ、Ｌ、Ｒを生成する量子プログラム生成部と、
ｍ量子ビットの入力状態に応じて前記量子プログラムＵｉの動作が制御されるように制御化された量子プログラムＣＵを生成する量子プログラム制御化部と、
前記量子プログラムＣＵに前記量子プログラムＬ、Ｒを付加して量子プログラムＧを生成する量子プログラム付加部と、
前記量子プログラムＧを難読化して前記公開鍵に対応する量子プログラムＰを生成する量子プログラム難読化部と、
前記量子プログラムＣＵに対応するユニタリ演算ＣＵのエルミート共役ＣＵ†に対応する量子プログラムＣＵ†と、前記ユニタリ演算Ｒの複素共役Ｒ＊に対応する量子プログラムＲ＊と、を生成する逆量子プログラム生成部と、
前記量子プログラムＣＵ†と前記量子プログラムＲ＊とを接続して前記秘密鍵に対応する量子プログラムＳを生成する量子プログラム接続部と、
を含む、請求項１に記載の量子公開鍵暗号システム。
【請求項３】
前記暗号化部は、量子コンピュータから成り、
２ｍ量子ビットの最大エンタングルメント状態を生成し、当該２ｍ量子ビットの最大エンタングルメント状態のうち、ｍ量子ビットの量子状態と、送信すべきｎ量子ビットの量子状態｜ψｎ＞と、を前記公開鍵に対応する量子プログラムＰに入力して前記暗号化された量子状態を算出する、請求項２に記載の量子公開鍵暗号システム。
【請求項４】
前記復号部は、量子コンピュータから成り、
前記暗号化された量子状態を前記秘密鍵に対応する量子プログラムＳに入力して元の量子状態｜ψｎ＞を算出する、請求項３に記載の量子公開鍵暗号システム。
【請求項５】
前記暗号化部は、
２ｍ量子ビットの最大エンタングルメント状態を生成し、当該２ｍ量子ビットの最大エンタングルメント状態のうち、ｍ量子ビットの量子状態を保持しておき、残りｍ量子ビットの量子状態を前記量子状態｜ψｎ＞と共に前記量子プログラムＰに入力し、前記量子状態｜ψｎ＞に対応する量子プログラムＰの出力に、保持しておいた前記ｍ量子ビットの量子状態を付加して前記暗号化された量子状態を算出する、請求項４に記載の量子公開鍵暗号システム。
【請求項６】
前記量子プログラム難読化部は、前記量子プログラムＧを、前記量子プログラムＧに対応するユニタリ演算と同じ演算内容を有する別の量子プログラムＧ’に置き換えることで前記量子プログラムＧを難読化する、請求項２に記載の量子公開鍵暗号システム。
【請求項７】
前記量子プログラム難読化部は、前記量子プログラムＧの一部を成す部分量子プログラムｇを、当該部分量子プログラムｇと同じ演算内容を有する別の量子プログラムｇ’に置き換えることで前記量子プログラムＧを難読化する、請求項６に記載の量子公開鍵暗号システム。
【請求項８】
乱数を発生させる乱数発生器と、
前記乱数発生器を用いて発生させた乱数に基づき、ｎ量子ビットに対するｍ種類のユニタリ演算Ｕｉ（ｉ＝１〜ｍ）、及び、ｍ量子ビットに対する２種類のユニタリ演算Ｌ、Ｒに、それぞれ対応する量子プログラムＵｉ、Ｌ、Ｒを生成する量子プログラム生成部と、
ｍ量子ビットの入力状態に応じて前記量子プログラムＵｉの動作が制御されるように制御化された量子プログラムＣＵを生成する量子プログラム制御化部と、
前記量子プログラムＣＵに前記量子プログラムＬ、Ｒを付加して量子プログラムＧを生成する量子プログラム付加部と、
前記量子プログラムＧを難読化して、公開鍵に対応する量子プログラムＰを生成する量子プログラム難読化部と、
前記量子プログラムＣＵに対応するユニタリ演算ＣＵのエルミート共役ＣＵ†に対応する量子プログラムＣＵ†と、前記ユニタリ演算Ｒの複素共役Ｒ＊に対応する量子プログラムＲ＊と、を生成する逆量子プログラム生成部と、
前記量子プログラムＣＵ†と前記量子プログラムＲ＊とを接続して、秘密鍵に対応する量子プログラムＳを生成する量子プログラム接続部と、
を備える、鍵生成装置。
【請求項９】
乱数を発生させる乱数発生器と、前記乱数発生器を用いて発生させた乱数に基づき、ｎ量子ビットに対するｍ種類のユニタリ演算Ｕｉ（ｉ＝１〜ｍ）、及び、ｍ量子ビットに対する２種類のユニタリ演算Ｌ、Ｒに、それぞれ対応する量子プログラムＵｉ、Ｌ、Ｒを生成する量子プログラム生成部と、ｍ量子ビットの入力状態に応じて前記量子プログラムＵｉの動作が制御されるように制御化された量子プログラムＣＵを生成する量子プログラム制御化部と、前記量子プログラムＣＵに前記量子プログラムＬ、Ｒを付加して量子プログラムＧを生成する量子プログラム付加部と、前記量子プログラムＧを難読化して、公開鍵に対応する量子プログラムＰを生成する量子プログラム難読化部と、を有する鍵生成装置により生成された公開鍵に対応する量子プログラムＰを保持する公開鍵保持部と、
量子コンピュータを利用して、
２ｍ量子ビットの最大エンタングルメント状態を生成するエンタングルメント状態生成部と、
前記エンタングルメント状態生成部により生成された最大エンタングルメント状態の一部と、送信すべきｎ量子ビットの量子状態と、を前記公開鍵に対応する量子プログラムＰに入力して前記暗号化された量子状態を算出する暗号化部と、
を備える、暗号化装置。
【請求項１０】
乱数を発生させる乱数発生器と、前記乱数発生器を用いて発生させた乱数に基づき、ｎ量子ビットに対するｍ種類のユニタリ演算Ｕｉ（ｉ＝１〜ｍ）、及び、ｍ量子ビットに対する２種類のユニタリ演算Ｌ、Ｒに、それぞれ対応する量子プログラムＵｉ、Ｌ、Ｒを生成する量子プログラム生成部と、ｍ量子ビットの入力状態に応じて前記量子プログラムＵｉの動作が制御されるように制御化された量子プログラムＣＵを生成する量子プログラム制御化部と、前記量子プログラムＣＵに前記量子プログラムＬ、Ｒを付加して量子プログラムＧを生成する量子プログラム付加部と、前記量子プログラムＧを難読化して、公開鍵に対応する量子プログラムＰを生成する量子プログラム難読化部と、前記量子プログラムＣＵに対応するユニタリ演算ＣＵのエルミート共役ＣＵ†に対応する量子プログラムＣＵ†と、前記ユニタリ演算Ｒの複素共役Ｒ＊に対応する量子プログラムＲ＊と、を生成する逆量子プログラム生成部と、前記量子プログラムＣＵ†と前記量子プログラムＲ＊とを接続して、秘密鍵に対応する量子プログラムＳを生成する量子プログラム接続部と、を有する鍵生成装置により生成された秘密鍵に対応する量子プログラムＳを保持する秘密鍵保持部と、
量子コンピュータを利用し、前記公開鍵に対応する量子プログラムＰを用いて生成された、暗号化された量子状態を前記秘密鍵に対応する量子プログラムＳに入力して元の量子状態を算出する復号部と、
を備える、復号装置。
【請求項１１】
乱数を発生させる乱数発生ステップと、
前記乱数発生ステップで発生させた乱数に基づき、ｎ量子ビットに対するｍ種類のユニタリ演算Ｕｉ（ｉ＝１〜ｍ）、及び、ｍ量子ビットに対する２種類のユニタリ演算Ｌ、Ｒに、それぞれ対応する量子プログラムＵｉ、Ｌ、Ｒを生成する量子プログラム生成ステップと、
ｍ量子ビットの入力状態に応じて前記量子プログラムＵｉの動作が制御されるように制御化された量子プログラムＣＵを生成する量子プログラム制御化ステップと、
前記量子プログラムＣＵに前記量子プログラムＬ、Ｒを付加して量子プログラムＧを生成する量子プログラム付加ステップと、
前記量子プログラムＧを難読化して、公開鍵に対応する量子プログラムＰを生成する量子プログラム難読化ステップと、
前記量子プログラムＣＵに対応するユニタリ演算ＣＵのエルミート共役ＣＵ†に対応する量子プログラムＣＵ†と、前記ユニタリ演算Ｒの複素共役Ｒ＊に対応する量子プログラムＲ＊と、を生成する逆量子プログラム生成ステップと、
前記量子プログラムＣＵ†と前記量子プログラムＲ＊とを接続して、秘密鍵に対応する量子プログラムＳを生成する量子プログラム接続ステップと、
を含む、鍵生成方法。
【請求項１２】
量子コンピュータを利用して、２ｍ量子ビットの最大エンタングルメント状態を生成するエンタングルメント状態生成ステップと、
乱数を発生させる乱数発生器と、前記乱数発生器を用いて発生させた乱数に基づき、ｎ量子ビットに対するｍ種類のユニタリ演算Ｕｉ（ｉ＝１〜ｍ）、及び、ｍ量子ビットに対する２種類のユニタリ演算Ｌ、Ｒに、それぞれ対応する量子プログラムＵｉ、Ｌ、Ｒを生成する量子プログラム生成部と、ｍ量子ビットの入力状態に応じて前記量子プログラムＵｉの動作が制御されるように制御化された量子プログラムＣＵを生成する量子プログラム制御化部と、前記量子プログラムＣＵに前記量子プログラムＬ、Ｒを付加して量子プログラムＧを生成する量子プログラム付加部と、前記量子プログラムＧを難読化して、公開鍵に対応する量子プログラムＰを生成する量子プログラム難読化部と、を有する鍵生成装置により生成された公開鍵に対応する量子プログラムＰに対し、
量子コンピュータを利用して、前記エンタングルメント状態生成ステップで生成された最大エンタングルメント状態のうち、ｍ量子ビットの量子状態と、送信すべきｎ量子ビットの量子状態と、を入力して前記暗号化された量子状態を算出する暗号化ステップと、
を含む、暗号化方法。
【請求項１３】
乱数を発生させる乱数発生器と、前記乱数発生器を用いて発生させた乱数に基づき、ｎ量子ビットに対するｍ種類のユニタリ演算Ｕｉ（ｉ＝１〜ｍ）、及び、ｍ量子ビットに対する２種類のユニタリ演算Ｌ、Ｒに、それぞれ対応する量子プログラムＵｉ、Ｌ、Ｒを生成する量子プログラム生成部と、ｍ量子ビットの入力状態に応じて前記量子プログラムＵｉの動作が制御されるように制御化された量子プログラムＣＵを生成する量子プログラム制御化部と、前記量子プログラムＣＵに前記量子プログラムＬ、Ｒを付加して量子プログラムＧを生成する量子プログラム付加部と、前記量子プログラムＧを難読化して、公開鍵に対応する量子プログラムＰを生成する量子プログラム難読化部と、前記量子プログラムＣＵに対応するユニタリ演算ＣＵのエルミート共役ＣＵ†に対応する量子プログラムＣＵ†と、前記ユニタリ演算Ｒの複素共役Ｒ＊に対応する量子プログラムＲ＊と、を生成する逆量子プログラム生成部と、前記量子プログラムＣＵ†と前記量子プログラムＲ＊とを接続して、秘密鍵に対応する量子プログラムＳを生成する量子プログラム接続部と、を有する鍵生成装置により生成された秘密鍵に対応する量子プログラムＳに対し、
量子コンピュータを利用して、前記公開鍵に対応する量子プログラムＰを用いて生成された、暗号化された量子状態を入力して元の量子状態を算出する復号ステップを含む、復号方法。
【請求項１】
第１の量子情報処理装置と、量子通信路を介して前記第１の量子情報処理装置に接続された第２の量子情報処理装置と、古典通信路を介して前記第１及び第２の量子情報処理装置に接続された認証局と、を含み、
前記第１の量子情報処理装置は、
公開鍵と秘密鍵とを生成する鍵生成部と、
前記鍵生成部により生成された公開鍵を前記古典通信路を介して前記認証局に送信する第１古典送信部と、
前記第２の量子情報処理装置から前記量子通信路を介して送信された、暗号化された量子状態を受信する第１量子受信部と、
前記鍵生成部により生成された秘密鍵を用いて、前記第１量子受信部により受信された、前記暗号化された量子状態から元の量子状態を復元する復号部と、
を有し、
前記認証局は、
前記第１の量子情報処理装置から前記古典通信路を介して送信された公開鍵を受信する第１古典受信部と、
前記第１古典受信部により受信された公開鍵を認証する認証部と、
前記認証部により認証された公開鍵を、前記古典通信路を介して前記第２の量子情報処理装置に送信する第２古典送信部と、
を有し、
前記第２の量子情報処理装置は、
前記認証局から前記古典通信路を介して送信された公開鍵を受信する第２古典受信部と、
前記第２古典受信部により受信された公開鍵を用いて量子状態を暗号化する暗号化部と、
前記暗号化部により暗号化された量子状態を、前記量子通信路を介して前記第１の量子情報処理装置に送信する量子送信部と、
を有する、量子公開鍵暗号システム。
【請求項２】
前記鍵生成部は、
乱数を発生させる乱数発生器と、
前記乱数発生器を用いて発生させた乱数に基づき、ｎ量子ビットに対するｍ種類のユニタリ演算Ｕｉ（ｉ＝１〜ｍ）、及び、ｍ量子ビットに対する２種類のユニタリ演算Ｌ、Ｒに、それぞれ対応する量子プログラムＵｉ、Ｌ、Ｒを生成する量子プログラム生成部と、
ｍ量子ビットの入力状態に応じて前記量子プログラムＵｉの動作が制御されるように制御化された量子プログラムＣＵを生成する量子プログラム制御化部と、
前記量子プログラムＣＵに前記量子プログラムＬ、Ｒを付加して量子プログラムＧを生成する量子プログラム付加部と、
前記量子プログラムＧを難読化して前記公開鍵に対応する量子プログラムＰを生成する量子プログラム難読化部と、
前記量子プログラムＣＵに対応するユニタリ演算ＣＵのエルミート共役ＣＵ†に対応する量子プログラムＣＵ†と、前記ユニタリ演算Ｒの複素共役Ｒ＊に対応する量子プログラムＲ＊と、を生成する逆量子プログラム生成部と、
前記量子プログラムＣＵ†と前記量子プログラムＲ＊とを接続して前記秘密鍵に対応する量子プログラムＳを生成する量子プログラム接続部と、
を含む、請求項１に記載の量子公開鍵暗号システム。
【請求項３】
前記暗号化部は、量子コンピュータから成り、
２ｍ量子ビットの最大エンタングルメント状態を生成し、当該２ｍ量子ビットの最大エンタングルメント状態のうち、ｍ量子ビットの量子状態と、送信すべきｎ量子ビットの量子状態｜ψｎ＞と、を前記公開鍵に対応する量子プログラムＰに入力して前記暗号化された量子状態を算出する、請求項２に記載の量子公開鍵暗号システム。
【請求項４】
前記復号部は、量子コンピュータから成り、
前記暗号化された量子状態を前記秘密鍵に対応する量子プログラムＳに入力して元の量子状態｜ψｎ＞を算出する、請求項３に記載の量子公開鍵暗号システム。
【請求項５】
前記暗号化部は、
２ｍ量子ビットの最大エンタングルメント状態を生成し、当該２ｍ量子ビットの最大エンタングルメント状態のうち、ｍ量子ビットの量子状態を保持しておき、残りｍ量子ビットの量子状態を前記量子状態｜ψｎ＞と共に前記量子プログラムＰに入力し、前記量子状態｜ψｎ＞に対応する量子プログラムＰの出力に、保持しておいた前記ｍ量子ビットの量子状態を付加して前記暗号化された量子状態を算出する、請求項４に記載の量子公開鍵暗号システム。
【請求項６】
前記量子プログラム難読化部は、前記量子プログラムＧを、前記量子プログラムＧに対応するユニタリ演算と同じ演算内容を有する別の量子プログラムＧ’に置き換えることで前記量子プログラムＧを難読化する、請求項２に記載の量子公開鍵暗号システム。
【請求項７】
前記量子プログラム難読化部は、前記量子プログラムＧの一部を成す部分量子プログラムｇを、当該部分量子プログラムｇと同じ演算内容を有する別の量子プログラムｇ’に置き換えることで前記量子プログラムＧを難読化する、請求項６に記載の量子公開鍵暗号システム。
【請求項８】
乱数を発生させる乱数発生器と、
前記乱数発生器を用いて発生させた乱数に基づき、ｎ量子ビットに対するｍ種類のユニタリ演算Ｕｉ（ｉ＝１〜ｍ）、及び、ｍ量子ビットに対する２種類のユニタリ演算Ｌ、Ｒに、それぞれ対応する量子プログラムＵｉ、Ｌ、Ｒを生成する量子プログラム生成部と、
ｍ量子ビットの入力状態に応じて前記量子プログラムＵｉの動作が制御されるように制御化された量子プログラムＣＵを生成する量子プログラム制御化部と、
前記量子プログラムＣＵに前記量子プログラムＬ、Ｒを付加して量子プログラムＧを生成する量子プログラム付加部と、
前記量子プログラムＧを難読化して、公開鍵に対応する量子プログラムＰを生成する量子プログラム難読化部と、
前記量子プログラムＣＵに対応するユニタリ演算ＣＵのエルミート共役ＣＵ†に対応する量子プログラムＣＵ†と、前記ユニタリ演算Ｒの複素共役Ｒ＊に対応する量子プログラムＲ＊と、を生成する逆量子プログラム生成部と、
前記量子プログラムＣＵ†と前記量子プログラムＲ＊とを接続して、秘密鍵に対応する量子プログラムＳを生成する量子プログラム接続部と、
を備える、鍵生成装置。
【請求項９】
乱数を発生させる乱数発生器と、前記乱数発生器を用いて発生させた乱数に基づき、ｎ量子ビットに対するｍ種類のユニタリ演算Ｕｉ（ｉ＝１〜ｍ）、及び、ｍ量子ビットに対する２種類のユニタリ演算Ｌ、Ｒに、それぞれ対応する量子プログラムＵｉ、Ｌ、Ｒを生成する量子プログラム生成部と、ｍ量子ビットの入力状態に応じて前記量子プログラムＵｉの動作が制御されるように制御化された量子プログラムＣＵを生成する量子プログラム制御化部と、前記量子プログラムＣＵに前記量子プログラムＬ、Ｒを付加して量子プログラムＧを生成する量子プログラム付加部と、前記量子プログラムＧを難読化して、公開鍵に対応する量子プログラムＰを生成する量子プログラム難読化部と、を有する鍵生成装置により生成された公開鍵に対応する量子プログラムＰを保持する公開鍵保持部と、
量子コンピュータを利用して、
２ｍ量子ビットの最大エンタングルメント状態を生成するエンタングルメント状態生成部と、
前記エンタングルメント状態生成部により生成された最大エンタングルメント状態の一部と、送信すべきｎ量子ビットの量子状態と、を前記公開鍵に対応する量子プログラムＰに入力して前記暗号化された量子状態を算出する暗号化部と、
を備える、暗号化装置。
【請求項１０】
乱数を発生させる乱数発生器と、前記乱数発生器を用いて発生させた乱数に基づき、ｎ量子ビットに対するｍ種類のユニタリ演算Ｕｉ（ｉ＝１〜ｍ）、及び、ｍ量子ビットに対する２種類のユニタリ演算Ｌ、Ｒに、それぞれ対応する量子プログラムＵｉ、Ｌ、Ｒを生成する量子プログラム生成部と、ｍ量子ビットの入力状態に応じて前記量子プログラムＵｉの動作が制御されるように制御化された量子プログラムＣＵを生成する量子プログラム制御化部と、前記量子プログラムＣＵに前記量子プログラムＬ、Ｒを付加して量子プログラムＧを生成する量子プログラム付加部と、前記量子プログラムＧを難読化して、公開鍵に対応する量子プログラムＰを生成する量子プログラム難読化部と、前記量子プログラムＣＵに対応するユニタリ演算ＣＵのエルミート共役ＣＵ†に対応する量子プログラムＣＵ†と、前記ユニタリ演算Ｒの複素共役Ｒ＊に対応する量子プログラムＲ＊と、を生成する逆量子プログラム生成部と、前記量子プログラムＣＵ†と前記量子プログラムＲ＊とを接続して、秘密鍵に対応する量子プログラムＳを生成する量子プログラム接続部と、を有する鍵生成装置により生成された秘密鍵に対応する量子プログラムＳを保持する秘密鍵保持部と、
量子コンピュータを利用し、前記公開鍵に対応する量子プログラムＰを用いて生成された、暗号化された量子状態を前記秘密鍵に対応する量子プログラムＳに入力して元の量子状態を算出する復号部と、
を備える、復号装置。
【請求項１１】
乱数を発生させる乱数発生ステップと、
前記乱数発生ステップで発生させた乱数に基づき、ｎ量子ビットに対するｍ種類のユニタリ演算Ｕｉ（ｉ＝１〜ｍ）、及び、ｍ量子ビットに対する２種類のユニタリ演算Ｌ、Ｒに、それぞれ対応する量子プログラムＵｉ、Ｌ、Ｒを生成する量子プログラム生成ステップと、
ｍ量子ビットの入力状態に応じて前記量子プログラムＵｉの動作が制御されるように制御化された量子プログラムＣＵを生成する量子プログラム制御化ステップと、
前記量子プログラムＣＵに前記量子プログラムＬ、Ｒを付加して量子プログラムＧを生成する量子プログラム付加ステップと、
前記量子プログラムＧを難読化して、公開鍵に対応する量子プログラムＰを生成する量子プログラム難読化ステップと、
前記量子プログラムＣＵに対応するユニタリ演算ＣＵのエルミート共役ＣＵ†に対応する量子プログラムＣＵ†と、前記ユニタリ演算Ｒの複素共役Ｒ＊に対応する量子プログラムＲ＊と、を生成する逆量子プログラム生成ステップと、
前記量子プログラムＣＵ†と前記量子プログラムＲ＊とを接続して、秘密鍵に対応する量子プログラムＳを生成する量子プログラム接続ステップと、
を含む、鍵生成方法。
【請求項１２】
量子コンピュータを利用して、２ｍ量子ビットの最大エンタングルメント状態を生成するエンタングルメント状態生成ステップと、
乱数を発生させる乱数発生器と、前記乱数発生器を用いて発生させた乱数に基づき、ｎ量子ビットに対するｍ種類のユニタリ演算Ｕｉ（ｉ＝１〜ｍ）、及び、ｍ量子ビットに対する２種類のユニタリ演算Ｌ、Ｒに、それぞれ対応する量子プログラムＵｉ、Ｌ、Ｒを生成する量子プログラム生成部と、ｍ量子ビットの入力状態に応じて前記量子プログラムＵｉの動作が制御されるように制御化された量子プログラムＣＵを生成する量子プログラム制御化部と、前記量子プログラムＣＵに前記量子プログラムＬ、Ｒを付加して量子プログラムＧを生成する量子プログラム付加部と、前記量子プログラムＧを難読化して、公開鍵に対応する量子プログラムＰを生成する量子プログラム難読化部と、を有する鍵生成装置により生成された公開鍵に対応する量子プログラムＰに対し、
量子コンピュータを利用して、前記エンタングルメント状態生成ステップで生成された最大エンタングルメント状態のうち、ｍ量子ビットの量子状態と、送信すべきｎ量子ビットの量子状態と、を入力して前記暗号化された量子状態を算出する暗号化ステップと、
を含む、暗号化方法。
【請求項１３】
乱数を発生させる乱数発生器と、前記乱数発生器を用いて発生させた乱数に基づき、ｎ量子ビットに対するｍ種類のユニタリ演算Ｕｉ（ｉ＝１〜ｍ）、及び、ｍ量子ビットに対する２種類のユニタリ演算Ｌ、Ｒに、それぞれ対応する量子プログラムＵｉ、Ｌ、Ｒを生成する量子プログラム生成部と、ｍ量子ビットの入力状態に応じて前記量子プログラムＵｉの動作が制御されるように制御化された量子プログラムＣＵを生成する量子プログラム制御化部と、前記量子プログラムＣＵに前記量子プログラムＬ、Ｒを付加して量子プログラムＧを生成する量子プログラム付加部と、前記量子プログラムＧを難読化して、公開鍵に対応する量子プログラムＰを生成する量子プログラム難読化部と、前記量子プログラムＣＵに対応するユニタリ演算ＣＵのエルミート共役ＣＵ†に対応する量子プログラムＣＵ†と、前記ユニタリ演算Ｒの複素共役Ｒ＊に対応する量子プログラムＲ＊と、を生成する逆量子プログラム生成部と、前記量子プログラムＣＵ†と前記量子プログラムＲ＊とを接続して、秘密鍵に対応する量子プログラムＳを生成する量子プログラム接続部と、を有する鍵生成装置により生成された秘密鍵に対応する量子プログラムＳに対し、
量子コンピュータを利用して、前記公開鍵に対応する量子プログラムＰを用いて生成された、暗号化された量子状態を入力して元の量子状態を算出する復号ステップを含む、復号方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【公開番号】特開２０１１−１３０１２０（Ｐ２０１１−１３０１２０Ａ）
【公開日】平成２３年６月３０日（２０１１．６．３０）
【国際特許分類】
【出願番号】特願２００９−２８５６９８（Ｐ２００９−２８５６９８）
【出願日】平成２１年１２月１６日（２００９．１２．１６）
【出願人】（０００００２１８５）ソニー株式会社 (34,172)
【Ｆターム（参考）】
【公開日】平成２３年６月３０日（２０１１．６．３０）
【国際特許分類】
【出願日】平成２１年１２月１６日（２００９．１２．１６）
【出願人】（０００００２１８５）ソニー株式会社 (34,172)
【Ｆターム（参考）】
[ Back to top ]