JST > 戦略的創造研究推進事業 > ERATO
ERATO
Exploratory Research for Advanced Technology 
戦略的創造研究推進事業(総括実施型研究)
創造科学犠実推進事業
TOP お問い合わせ サイトマップ English
HOME ERATOとは 研究プロジェクト 中間・事後評価 募集について
HOME > 研究プロジェクト > 終了プロジェクト > 今井量子計算機構プロジェクト > 研究成果集 > 量子公開鍵暗号の提案
研究成果集

量子公開鍵暗号の提案

研究成果の概略

 暗号は情報理論的な(秘密鍵共有タイプ)暗号と計算量理論的な(鍵が非対称なタイプの)暗号(通称、公開鍵暗号)に大別される。情報理論的な方式は安全性を高く設定できるが、利便性の面で問題がある。一方、計算量理論的な方式は利便性がよい反面、素因数分解問題が難しいなどのある種の計算量的仮定が必要である。現在の量子暗号研究の中心であるBennettとBrassardによる量子鍵配送プロトコルは情報理論的な暗号であり、現在の情報処理では不可能な秘密鍵暗号通信の安全性を達成できることが知られている。その一方でShorのアルゴリズムとその後続研究により、量子計算機の前では現在の殆どの公開鍵暗号が破られてしまう。そこで本プロジェクトでは量子計算機に対しても安全な公開鍵暗号の構成のために、二つの量子状態が量子計算機でも効率的に識別することができないという、量子状態の計算量的識別不可能性という新しい暗号概念を導入し、それに基づいた量子公開鍵暗号を提案した(図6)。具体的にはある特殊な2種類の量子状態を構成し、その二つをそれぞれ0と1に対応させることで暗号に利用する。これらの状態はある秘密情報を知っていると簡単に識別できるため、秘密情報を知っている受信者は容易に解読できるが、秘密情報を知らない盗聴者が解読するには現在量子計算機でさえ高速に解けていない問題(グラフ自己同型性判定問題)を解く必要があるため、量子アルゴリズムにブレークスルーをもたらすような技術革新なくしてその解読は困難である。本プロジェクトが提案した公開鍵暗号は量子計算機でさえ困難と思われる問題を解かない限り解読できないという意味で最初の計算量的安全性の証明を持つ量子公開鍵暗号である。この成果は(1.)において発表されている。
成果展開可能なシーズ、用途等

 本プロジェクトで提案した量子状態の識別問題は非常に基本的な問題であるので、量子公開鍵暗号だけではなく、例えば電子署名といった様々な暗号システムの構成に応用することが考えられる。
特許出願

無し。
報告書他
  1. Akinori Kawachi, Takeshi Koshiba, Harumichi Nishimura, and Tomoyuki Yamakami, “Computational Indistinguishability between Quantum States and Its Cryptographic Application,” Advance in Cryptography-Eurocrypt 2005, Lecture Notes in Computer Science 3494, pp.268-284, 2005.
  2. Akinori Kawachi, Takeshi Koshiba, “Quantum Computational Cryptography,” (Chapter 7 of Quantum Computation and Information: H. Imai and M. Hayashi eds., Springer 2006.)
研究者名

河内 亮周, 小柴 健史, 西村 治道

図6

図6.量子公開鍵暗号:送信者は公開鍵+πを使ってビット0を送りたければ量子状態+πに、ビット1を送りたければ量子状態-πに暗号化。受信者だけが知る秘密情報πなしでは 二つの状態を区別できない。

戻る

 
独立行政法人
科学技術振興機構 過去のお知らせはこちら ERATO
Exploratory Research for Advanced Technology 
戦略的創造研究推進事業(総括実施型研究)
創造科学技術推進事業 ERATO