Innovators: The future of Quantum Computing
格子暗号
格子暗号の実用化に向けて
NICT NEWS
●格子暗号
格子暗号の概念図を図4に示します。格子とは、図の（A）、（B）のように空間内に規則的に並んだ点の集合（図は2次元空間の例）であり、コンピュータの内部ではベクトルの集合（図中の黒矢印の組）として表現されます。このベクトルを適当に整数倍して足すことで、すべての格子点を網羅することができます。
格子暗号を用いた通信は、メッセージの送信者が受信者に対して通信処理の要求を出した後、①準備、②暗号文の生成・送信、③メッセージの復元の3ステップで行われます。
https://www.nict.go.jp/publication/NICT-News/1303/02.html
サイエンスZERO 「量子コンピューターでも解読不可能！？新しい暗号誕生なるか」
2018年6月26日 NHK Eテレ
【出演】高木剛、小島瑠璃子、森田洋平
インターネット上の情報は、「暗号化」によって第三者には解読できないよう加工され、安全が保たれている。現在の暗号は、「巨大な数字の素因数分解」という問題設定で、スーパーコンピューターでも解けない。
ところが、量子コンピューターの開発が加速し、その安全が脅かされようとしている。研究者たちは、新たな暗号の開発に乗り出した。注目を集めるのは「格子問題」。新たな暗号とはどんなものか？情報の安全は保たれるのか？
https://www.nhk-ondemand.jp/goods/G2018087537SA000/
『暗号技術の教科書』
吹田智章／著 ラトルズ 2018年発行
迫りくる量子コンピュータの驚異～量子コンピュータとは
2011年に発表されたD-Wave Systems（カナダ）による世界初の商用量子コンピュータは量子アニーリング方式で、組み合わせ最適化問題に特化されている。
一方の量子ゲート方式は汎用計算が可能で、既存のコンピュータに置き換わるものとなる。2016年、IBMは5量子ビットの量子コンピュータの準備を発表し、クラウドを通じて一般に公開した。2017年11月にIBMは商用向けの20量子ビットの量子コンピュータの提供と50量子ビットの量子コンピュータの準備を発表している。
しかし、量子の状態を安定的に保持し、その状態を検知するのは容易なことではない。エラー発生の原因となる外来ノイズや磁気、温度などの影響を防ぐため、量子ゲートデバイスの外部をシールドし、安定した空間の複数の量子による冗長性や誤り訂正が必要となる。現在の超電導に基づくデバイスは絶対零度に冷却しなければならないなど量子ビット数を増やすのは容易ではない。
・
何故、驚異となるのか
アメリカ国家安全保障局NSAが暗号解読用に量子コンピュータの開発を、7,970万ドルの研究費用でおこなわれているとエドワード・スノーデンがウィキリークスに提供した文書の中にある。当然、ロシアや中国などでもそのような目的で研究は行なわれていることだろう。この量子コンピュータは暗号にとってどれほど驚異となるのだろう。
それはまず従来のコンピュータに比べてより高速な演算が可能なことである。半加算器を論理回路のNANDゲートで作成すると5ゲート必要となるが、量子コンピュータでは2ゲートで実現できる。基本的に使用する素子数が少ない程高速化が可能となる。また、重ね合わせの並列化により一度に多くの情報を保持し、処理をおこなうことが可能になる。量子ビット数が増えることで指数関数的に扱えるデータ量が増えることは先に述べた通りだ。
次に、暗号解読の困難さとされる素因数分解のための量子アルゴリズムを光速に解くことが可能な「ショアのアルゴリズム（Shor's Factorization）」を利用することができるからだ。
素因数分解アルゴリズムのステップ数は、指数関数的に増える（指数関数時間）。しかし、ショアのアルゴリズムでは因数分解を多項式時間で高速に解くことが可能になる。また、少し改造することで離散対数問題（楕円曲線暗号など）にも対応が可能となる。
GoogleはD-Wave SystemのD=Wave2X（量子アニーリング方式）を評価し、最適化問題で論理上スーパーコンピュータの3,600倍の速度、単一コアプロセッサの10の8乗倍高速であると発表している。同様に量子ゲート方式においても従来のコンピュータと比較し高速であることが想像される。このことから「素因数分解の暗号解読の困難さ」はあっという間に危殆化してしまうのだ。
次世代暗号のキーワードは「格子」
暗号技術がプライバシー保護や経済活動へと広く浸透している現在、量子コンピュータの実用化によって従来の暗号がその機能を失ってしまうことは、社会生活にも大きな制約が生じることとなってしまう。インターネットでのショッピングではネット上での決済はできず、個人情報も通信経路での保護ができなくなってしまうといった具合だ。
そこで量子コンピュータに対して耐性を持った暗号が求められている。
2016年12月から１年間、米国国立標準技術研究所（NIST）が量子耐性アルゴリズムの次世代公開鍵暗号の公募をおこない、世界中から82件の応募があり、そのうち69件の提案が評価されることとなった。日本からも産学合同チームや各法人組織がこれに応募した。
2018年4月には米国フロリダでNIST主催の量子耐性暗号である新暗号標準化会議が初めて開催された。その中でも注目されているキーワードが格子（Lattice）だ。この格子を利用する暗号に関しては1996年にMiklos AjtaiとCynthia Dworkにより提案されたのが始まりだ。
