第 16 回情報セキュリティ シンポジウム 2015 年 3 月 11 日 ( 水 ) - 講演 3- 量子コンピュータによる解読に耐えうる 格子暗号 を巡る最新動向 日本銀行金融研究所情報技術研究センター清藤武暢 本発表は ( 独 ) 情報通信研究機構青野良範研究員 横浜国立大学四方順司准教授と共

量子コンピュータによる解読に耐えうる

『格子暗号』を巡る最新動向

1

日本銀行金融研究所

情報技術研究センター

清藤武暢

第

16回情報セキュリティ・シンポジウム

2015年3月11日（水）

-講演3- 本発表は、（独）情報通信研究機構 青野良範研究員、横浜国立大学 四方順司准教授と共同で実施した

研究に基づく。また、本発表に示されている意見は、発表者個人に属し、日本銀行、（独）情報通信研究機構

及び横浜国立大学の公式見解を示すものではない。

本講演の概要

■ 金融分野に限らず、データの保護や通信相手の認証等を行うため

に暗号アルゴリズムが広く利用されている。



暗号アルゴリズムの種類：公開鍵暗号、共通鍵暗号等

■ 現在主流の公開鍵暗号である

RSAや楕円曲線暗号は、

「量子コン

ピュータ（量子デジタル型

※

_{）」が実現すれば容易に解読できること}

が知られている。



技術進歩により、同コンピュータの実現可能性は高まっていくものと

推測される。

■ 耐量子暗号の

1つとして「

格子暗号」が学界で注目されている。

■ 本講演では、格子暗号の概要や研究動向について紹介したうえ

で、同暗号の利用を考えた場合に留意すべき点等について考察

する。

量子コンピュータでも容易に解読できない

暗号アルゴリズム（

耐量子暗号

）の研究が不可欠

※学界では、量子デジタル型は「量子ゲート方式（量子チューリングマシン）」と呼ばれる。

本講演の流れ

3

■ 量子コンピュータが暗号アルゴリズムに与える影響

■ 格子暗号：

 概要

 イメージ

 安全性評価動向

■ おわりに

量子コンピュータが

暗号アルゴリズムに与える影響

金融分野における暗号アルゴリズムの利用

5

ICカード

PC

携帯端末

利用者

ATM/POS

ICカードの真正性確認

（

AES、RSA

）

金融機関の

ホストシステム等

・ 通信内容の保護

（

TripleDES,AES,Camellia等）

・ 通信相手の認証

（

RSA、楕円曲線暗号等

）

通信内容の保護

インターネット

公開鍵暗号：概要

送信者

公開鍵

_受信者

メッセージ

（平文）

メッセージ

_（平文）

秘密鍵

暗号文

暗号化

復号

公開鍵暗号の安全性：

公開鍵から秘密鍵を求めるのが困難⇒「数学的問題」により保証

 例：素因数分解問題（RSAの安全性の根拠）

N（=P×Q）

素数

P,Q

公開鍵

容易

秘密鍵

困難

桁数

2桁：

33

→

3×11

桁数

3桁：

989

→

43×23

桁数

5桁：

73,903 →

263×281

桁数が大きくなるほど難しい

（推奨桁長：

600桁程度）

数値例：

安全ではない

通信路

RSAと楕円曲線暗号の潜在的な脅威と耐量子暗号

7

2000

2010

2030

_2xxx

年

RSA

楕円曲線

暗号

1,024ビット

2,048ビット

3,072ビット

160ビット

224ビット

256ビット

_{量子コンピュータ}

（量子デジタル型）

の実用化

■ 量子コンピュータ（量子デジタル型）が実用化されると、

RSA（素因

数分解問題）や楕円曲線暗号（楕円曲線離散対数問題）が容易に

解けることが知られている。

同コンピュータでも容易に解読できない公開鍵暗号

（

耐量子暗号

）は、将来的に必ず必要となる技術。

耐量子暗号

耐量子暗号の1つ：格子暗号

■ これまでにいろいろな種類の耐量子暗号が提案されている。

■ 近年、量子コンピュータへの耐性に加えて、利便性の高い機能を

実現可能な格子暗号が学界で注目されている。



特に、クラウドサービスや医療分野等への

同暗号の応用に関する研究が活発化

しており、既に製品化も始まっている

[1]。

本講演では、耐量子暗号として格子暗号にフォーカス

暗号アルゴリズムの分類

耐量子暗号の代表例

公開鍵暗号

 格子暗号

 符号ベース暗号

 多変数暗号

情報理論的暗号

 量子暗号

格子暗号：概要

格子暗号：概要

■ 格子暗号（

Lattice-based Cryptography）

とは、「

格子

」と呼ばれる数学的な構造を

利用した公開鍵暗号の総称。

格子（

2次元）の1例

■ 格子暗号の特徴：

メリット

 量子コンピュータでも

容易に解読できないと期待されている。

 データを暗号化したまま処理を行う技術（

暗号化状態処理技術）

を実現可能

[1]。

デメリット

 鍵サイズが大きい。

 データを暗号化したままキーワード検索（秘匿検索）。

 データを暗号化したまま統計解析等の数値計算（秘匿計算）。

 公開鍵のサイズについては、数キロビットの方式もあるが、

数ペタ（10

_{）ビットとなる方式もある。}

格子暗号：主な実現方式の整理（1/2）

11

■ 現在提案されている格子暗号の主な実現方式は

4種類存在し、

「

観点

1：暗号化処理に利用する数学的な構造

」や「

観点

2：安全

性の根拠

」から、それらの特徴を整理できる。

実現方式

の名称

暗号化処理に

利用する数学的構造

暗号化処理（イメージ）

LWE方式[2]

NTRU方式[3]

GGH方式[4]

AD方式[5]

[暗号文

]=[乱数]×[公開鍵

],

[暗号文

]=[乱数]×[公開鍵

]＋[平文].

暗号文

=2×

公開鍵

×

乱数

＋

平文

.

暗号文

=平文×公開鍵+乱数.

・ 平文

=1の場合：暗号文=乱数×公開鍵.

・ 平文

=0の場合：暗号文=乱数.

[2]O. Regev, “On Lattices, Learning with Errors, Random Linear Codes, and Cryptography,” J.ACM 56(6), 2009. [3]J. Hoffstein, J. Pipher, and J. H. Silverman, “NTRU: A Ring based Public Key Cryptosystem,” ANTS-III, 1998.

[4]O. Goldreich, S. Goldwasser, and S. Halevi, “Public-Key Cryptosystems from Lattice Reduction Problems,”CRYPTO1997. [5]M. Ajtai and C. Dwork, “A Public-Key Cryptosystem with Worst/Average Case Equivalence,” STOC1997.

観点

1：暗号化処理（イメージ）

はじめて安全性が厳密に証明された格子暗号

行列演算

多項式演算

格子暗号：主な実現方式の整理（2/2）

観点

2：安全性の根拠

実現方式

の名称

安全性と格子上の

数学的問題の関係

LWE方式

同方式を解く問題

=最近ベクトル問題

NTRU方式

同方式を解く問題

<最短ベクトル問題

GGH方式

同方式を解く問題

<最近ベクトル問題

AD方式

同方式を解く問題

=最短ベクトル問題。

■ 「格子上で定義される数学的問題」を安全性の根拠として利用す

る公開鍵暗号が「格子暗号」と呼ばれる。



利用される主な数学的問題：最近ベクトル問題（

Closest Vector Problem）、

最短ベクトル問題（

Shortest Vector Problem）。



これらの問題は、量子コンピュータで効率よく解けないと期待されている。

[6]Y. Chen and P. Nguyen, “BKZ2.0: Better Lattice Security Estimate,” ASIACRYPT2011.

[7]P. Nguyen, “Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from CRYPTO’97,” CRYPTO1999. [8]P. Nguyen and J. Stern, “Cryptanalysis of the Ajtai-Dwork Cryptosystem,” CRYPTO1998.

これらの方式を解く問題の難

しさの下限は明らかにされて

いないため、安全性評価の

進展に伴い、安全性が低下

する場合あり

[6,7]。

安全性と実用性のバランス

が現時点では相対的に良い。

安全に利用するために必要な

パラメータ（次元数、鍵長）が膨

大なため、実用性は低い

[8]。

・問題A=問題B：問題AとBが同程度に難しいことが厳密に証明。

・問題

A<問題B：問題AよりもBの方が難しいことが厳密に証明。

※補足

格子暗号：実用化動向

13

■ 暗号化状態処理技術の実現への利用事例（

LWE方式

）

[1,9,10]：

処理の名称

主な用途

処理性能

秘匿検索

ビッグデータ

分析

1万6千文字の暗号化データの全数検索

が約

1秒で可能。

秘匿計算

100万件の暗号化データ（16ビット整数）

の共分散や相関係数が約

20分で可能。

100万件の暗号化データの線形回帰係数

の計算が約

40分で可能。

生体認証

生体情報（

2,048次元の生体特徴ベクト

ル）の照合が約

5ミリ秒で可能。

■ 国際標準化（

NTRU方式

）：



IEEE1363.1 Public-Key Cryptographic Techniques Based on Hard

Problems over Lattices（2009年）.



ANSI X9.98 Lattice-Based Polynomial Public-Key Establishment

Algorithm for the Financial Services Industry（2010年）.

[9]安田・下山・小暮、「準同型暗号による秘匿統計計算」、SCIS2015

[10]青野・林・フォン・王、「セキュリティアップデータブル準同型暗号を用いた秘匿データの線形回帰計算」、SCIS2015

 ただし、これらの標準の規格化後も安全性評価の進展に伴い、同標準に記載

されている推奨パラメータの安全性は低下しうることに留意が必要。

格子暗号：イメージ

14

本講演では、暗号化処理と安全性の根拠に格子を利用し、かつ処理の

流れを視覚化できる「

GGH方式

」をベースとした格子暗号のイメージを紹介。

基底ベクトル

の種類

2次元空間

（基底ベクトル：

2本）

3次元空間

（基底ベクトル：

3本）

数千次元空間

（基底ベクトル：数千本）

（ ：格子点）

準備：格子の定義

15

■ 「格子」とは、空間上に規則正しく並んでいる点の集合。「次元」や

「基底ベクトル」と呼ばれるパラメータにより、格子の構造や特徴

が一意に定まる。

直交している

基底ベクトル

直交していない

基底ベクトル

本講演では、

2次元空間上の格子を利用して格子暗号の

イメージについて説明（暗号で利用される格子は主に数千次元）。

・・・

原点

原点

・・・

15

数千

・・・

？

原点

_原点

・・・

数千

・・・

？

性質1

性質2

 全ての格子点は基底ベク

トル（

n個のベクトルの組、

nは次元数）の組合せで

表現可能。

 1つの格子において、複数の基底ベクトルが存在。

準備：格子の2つの性質

(2,0)

(0,1)

原点

(4,2)

2

2

+

(2,0)

(0,1)

原点

(20,4)

4

20

(0,4)

(6,1)

(4,1)

2

₂

(8,2)

+

=

+

秘密鍵

公開鍵

格子暗号：鍵の設定（イメージ）

17

■ 鍵の設定：

①秘密鍵として直交している基底ベクトル

（

,

）を選ぶ。

原点

(2,0)

(0,1)

② （

, ）を利用して、同じ格子を表現で

きる直交していない基底ベクトル（

, ）

を計算する。

(6,1)

(4,1)

原点

(2,0)

(0,1)

ある点に近い格子点を見つけやすい

点

原点

ある点に近い格子点を見つけにくい

格子暗号では、これらの特徴を利用。

容易

困難

原点

？

点

最も近い格子点？

(6,1)

(4,1)

どの直交ベクトルを使って

いるのか特定できない

特徴

 格子上の任意の格子点を表現しやすい

（格子の全体像を把握するのが容易）。

特徴

 格子上の任意の格子点を表現しにくい

（格子の全体像を把握するのが困難）。

最も近い格子点！

格子暗号：暗号化処理（イメージ）

■ 暗号化処理：

格子点

P=m

₁

×

+m

₂

×

1. 暗号化したい平文を2つの整数（m

₁

,m

₂

）で表現。

2. 公開鍵（

、

）を利用して、格子点

P

を以下のように計算。

3. 小さな実数ベクトル をランダムに選び、暗号文

C

=P+

を計算。

(6,1)

(4,1)

2

2

(8,2)

(14,3)

(20.2,4.2)

ベクトル を足して

格子点

P

の位置をずらす

(20,4)

暗号文

C

格子点

P

例：

(m

, m

)=(2,2), =(0.2,0.2)の場合：

格子暗号の安全性：格子点

Pを求めることの難しさ

秘密鍵を利用した場合

公開鍵を利用した場合

 秘密鍵（ ,

）から、格子の全体像を

把握するのは容易。

 格子点

P

を容易に求めることができる。

 公開鍵（ , ）では、格子の全体像を把握す

るのが難しい。

 暗号文

C

の周辺にある格子点

P

となり得る候

補をしらみつぶしに探索する必要がある。

格子暗号：復号処理と安全性（イメージ）

19

■ 復号処理：

格子点

P

を求めることができれば、以下の手順で平文

（

m

₁

,m

₂

）を容易に計算できる。

,

,

,

.

①格子点

Pを基底ベクトルの式で表現

②

2元1次連立方程式を解き、

_平文（

_m

,m

）を計算。

未知数

(2,0)

(0,1)

原点

暗号文

C

格子点

P

この探索は指数関数時間かかる。

（次元数

nを大きくすると解くのが困難）

最近ベクトル問題

原点

？

(6,1)

(4,1)

暗号文

C

,

.

格子暗号：安全性評価動向

 同手法に要する時間は

指数関数時間（次元数

n

が大きくなると現実的な

時間で解くのが困難）。

 量子コンピュータで効率

よく解けないと期待され

ている。

処理①：探索範囲の絞り込み

（格子基底簡約処理）

主な方式

・

LLL手法

・

BKZ手法

・

BKZ2.0手法

格子暗号：攻撃手法の整理

21

■ 格子暗号に対する一般的な攻撃手法



攻撃者の目的：

格子点

P

の特定

暗号文

C

確率の高い

探索範囲

処理②しらみつぶしに探索（探索処理）

主な方式

・

Babai手法

・ランダムサンプリング手法

暗号文

C

格子点

P

の探索

公開鍵

公開鍵

攻撃者が利用可能な情報：公開鍵（

, ）、

暗号文

C

攻撃者

格子点

P

「耐量子暗号」に

分類される根拠

格子暗号：安全性評価の動向

■ 等価安全性に基づく格子暗号と

RSA、楕円曲線暗号の鍵長比較：



RSA、楕円曲線暗号（ECC）は、NISTの評価[11]を参照。



格子暗号の各方式（LWE方式、GGH方式、AD方式）の鍵長と次元数は、

文献[10,12]の評価手法に基づき、最低限必要な値を算出。



NTRU方式は、国際標準ANSI X9.98を参照。

[11]NIST, “SP800-57:Recommendation for Key Management –Part I: General (Revision 3),” 2012. [12]R. Linder and C. Peikert, “Better Key Sizes (and Attacks) for LWE-Based Encryption,” CT-RSA2011.

鍵長

128ビット安全性

1Mビット

（

10

）

1Gビット

（

10

）

RSA

（

3,024）

ECC

（

256）

NTRU方式

（約7,000）

次元数：約

600

GGH方式

（約280M）

次元数：約

5,000

AD方式

（約490P）

次元数：約

15,000

～

_～

LWE方式

（約

7.8M）

次元数：約

250

1Pビット

（

10

）

格子暗号：研究動向

23

■ 格子暗号の各実現方式に関する最近の主な研究動向：



主にパラメータ（鍵長等）の効率性向上や安全性評価に関する研究が活発。

方式の名称

主な研究動向

LWE方式

鍵長を数千分の

1程度（数K～数十Kビット）まで削減できる改良

方式（

ring-LWE方式

）が提案され

[13]、学界で活発に研究され

ている。ただし、安全性については、格子上の数学的問題と同

程度に難しいことが、現時点では証明されていない。

NTRU方式

 同方式とLWE方式を組み合わせることにより、より厳密な安

全性を証明可能な改良方式が提案

[14]。

 NTRU方式で用いている格子は、特殊な構造を有しているた

め、同構造に特有の脆弱性を利用した攻撃手法の提案およ

び安全性の再評価が行われている（

[6]等)。

GGH方式

安全に利用するために必要な鍵長等のパラメータが大きく、か

つ大幅な効率化も難しいと考えられているため、これらの方式

に関する研究については大きな進展なし。

AD方式

[13]V. Lyubashevsky, C. Peikert, and O. Regev, “On Ideal Lattices and Learning with Errors over Rings,” EUROCRYPT2010. [14]D. Stehle and R. Steinfeld, “Making NTRU as Secure as Worst-Case Problems over Ideal Lattices,” EUROCRYPT2011.

おわりに

■ 耐量子暗号の

1つ「

格子暗号」



量子コンピュータにより、現在主流の公開鍵暗号である

RSAや楕円曲線暗

号は容易に解読できることが知られている（鍵長を伸ばしたとしても、安全

性を確保できない）。



格子暗号は、量子コンピュータが実用化された状況下においても、容易に

解読できないと期待されている。



近年、格子暗号（LWE方式）を利用した暗号化状態処理（秘匿検索、

秘匿計算）の実装および製品化事例が増加。



一部の実現方式（

NTRU方式）は、国際標準IEEEやANSIにおいて規定。

■ 格子暗号を選択する際の留意点



格子暗号を利用する際には、その特徴（鍵長が長い等）も理解したうえで

適切な環境下での利用を検討する。



例：

ICカードや組込み機器等の計算機性能（メモリ等）が制限されている環境

での利用には、現時点では適さない点等。



さらに、最新の安全性評価の結果に基づき、パラメータ（次元、基底、鍵長

等）を適切に選択する必要がある。ただし、同評価の基準は定まっていない

ため、学界における評価動向を定期的にフォローすることが重要である。

【付録】量子コンピュータの研究開発動向

25

■ 量子デジタル型：計算過程で利用する量子の「重ね合わせ状態」

を維持することが難しく、現時点では理論研究および実験段階で

あり、実用化段階には至っていない。



同コンピュータ上で動く「ショア（

Shor）のアルゴリズム

」により、素因数分解

問題や楕円曲線離散対数問題が容易に解けることが知られているが

[15]、

現時点では「

15=3×5」の素因数分解を実験的に計算可能な段階[16]。

■ 量子アナログ型

※

_{：カナダの}

D-Wave Systems, Incが同コン

ピュータを販売したと発表（

2011年）[17]。



量子人工知能研究所（

GoogleとNASA等が

共同開設）や、ロッキード・マーチン社等が

購入したとの報道

[18]。

[15]P. Shor, “Algorithms for Quantum Computation: Discrete Logarithms and Factoring,” STOC1994.

[16]L. M. K. Vandersypen, M. Steffen, G. Breyta, C. S. Yannoni, M. H. Sherwood, and I. L. Chuang, “Experimental Realization of Shor’s Quantum Factoring Algorithm using Nnclear Magnetic Resonance,” Nature 414, 2001.

[17]D-Wave Systems Press Releases, “D-Wave Systems sells its first Quantum Computing System to Lockheed Martin Corporation,” 2011/5/25. [18]http://www.dwavesys.com/our-company/customers [19]http://www.dwavesys.com/tutorials/background-reading-series/introduction-d-wave-quantum-hardware

[19]

※学界では、量子アナログ型は「量子イジングマシン方式」

と呼ばれる。

【付録】量子コンピュータの共通鍵暗号への影響

■

量子コンピュータ（量子デジタル型）で動く「グローバー（Grover）のアルゴリズ

ム[20]」により、共通鍵暗号（AES等）に対する鍵の全数探索の回数を削減でき

ることが知られている[21]。

[20]L. K. Grover, “A Fast Quantum Mechanical Algorithm for Database Search,” STOC1996.

[21]C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, “A Fast Quantum Mechanical Algorithm for Database Search,”SIAM J. Compt. 26(5), 1997.

等価安全性

鍵サイズ

（

AES）

鍵の全数探索に要する計算量

従来の

コンピュータ環境

量子

コンピュータ環境

128ビット

128ビット

₂

₂

256ビット

256ビット

₂

₂

指数部の値が

半分になる。

（等価安全性の

レベル低下）

■

同脅威への対策：鍵長を

2倍に増やすことにより対応可能。

等価安全性

対策後の

鍵サイズ（

AES）

鍵の全数探索に要する計算量

従来の

コンピュータ環境

量子

コンピュータ環境

128ビット

256ビット

₂

₂

256ビット

512ビット

2

2

等価安全性のレベル

を維持できると

考えられている。

【付録】格子暗号：安全性評価の動向

27

鍵長

1Mビット

（

10

_）

1Gビット

_（

₁₀

_）

NTRU方式

（約

13,000）

次元数：約

1,200

GGH方式

（約

1.6G）

次元数：約

11,400

AD方式

（約

2.2E）

次元数：約

21,000

～

_～

LWE方式

（約

30M）

次元数：約

460

1Eビット

（

10

_）

■ 「256ビット安全性」を実現するために必要な各方式の鍵長比較：

256ビット安全性

RSA

（

15,360）

ECC

（

512）

【付録】量子コンピュータが暗号アルゴリズムの安全性に与える影響（まとめ）

112ビット

128ビット

RSA（3,072）

ECC（256）

RSA（2,048）

ECC（224）

RSA（15,360）

ECC（512）

AES（128）

_AES（256）

AES（256）

現在の

コ

ン

ピ

ュ

ー

タ

環境

量子コ

ン

ピ

ュ

ータ

が

実現し

た

場合

ビット安全性

256ビット

公開鍵

暗号

共通鍵

暗号

_3KeyTDES

RSA（2,048）

ECC（224）

公開鍵

暗号

共通鍵

暗号

？

※カッコ内は鍵長。

2010年～2030年

2031年～

AES（128）

AES（256）

格子暗号

危殆化！

（鍵長を伸ばしても容易に解読）

同コンピュータが実現した場合

でも安全に利用できると期待。

LWE方式（約7.8×10

_）

LWE方式（約6.6×10

_）

_{LWE方式（約30×10}

_）

NTRU方式（約7,000）

NTRU方式（約6,000）

NTRU方式（約13,000）

GGH方式（約280×10

_）

GGH方式（約180×10

_）

_{GGH方式（約1.6×10}

_）

AD方式（約490×10

_）

AD方式（約360×10

_）

_{AD方式（約2,2×10}

_）