CRYPTREC MT-1411-2019
資料１「量子コンピュータ時代に向けた暗号の在り方検討タスクフォース」
開催要綱（案）
１．名称
本検討会は「量子コンピュータ時代に向けた暗号の在り方検討タスクフォース」（以下「タスクフォース」という。）と称する。
２．開催の趣旨・目的
近年、耐量子計算機暗号の研究開発・標準化が各国で進められているところ、大規模な量子コンピュータの出現に向けて、我が国においても耐量子計算機暗号について議論を行う必要性が高まっていることから、量子コンピュータの動向及び耐量子計算機暗号を含む新たな暗号技術の動向等を踏まえた、次期
CRYPTREC 暗号リストに求められる要件や課題等を整理することを目的として開催する。
３．検討事項（１）大規模な量子コンピュータの動向を踏まえた次期 CRYPTREC 暗号リストに求められる要件等の検討（２）その他新たな暗号技術の動向等（軽量暗号や秘密計算に利用される準同型
暗号等）を踏まえた検討等
４．構成等（１）タスクフォースの構成員は、別紙のとおりとする。
（２）タスクフォースの座長は、構成員の互選により定める。
（３）座長は、タスクフォース構成員の中から座長代理を指名できる。
（４）座長は、タスクフォースの議事を掌握する。
（５）座長が、緊急の理由によりやむを得ず不在となった場合、座長代理が座長に代わり議事を掌握する。
（６）座長が必要と認めた者については、オブザーバとしてタスクフォースに出席することができる。
（７）座長が必要と認めるときは、暗号技術の提案者、関連する利害関係者その他の参考人から意見を聴取することができる。
（８）その他、タスクフォースの運営に関し必要な事項は、座長が定めるところによる。
５．議事の公開
タスクフォースは非公開とする。タスクフォースで使用した資料及びタスク
フォースの議事概要については、次の場合を除き、公開する。

1

（１）公開することにより当事者又は第三者の権利、利益や公共の利益を害する
おそれがあると座長が認める場合（２）その他、非公開とすることが必要と座長が認める場合
６．庶務
タスクフォースの庶務は、総務省、経済産業省、国立研究開発法人情報通信研究機構及び独立行政法人情報処理推進機構において処理する。

2

（別紙）
構成員・オブザーバ名簿（五十音順、敬称略）
（構成員）
宇根

正志

日本銀行

金融研究所

情報技術研究センター

情報技術研究グループ長
國廣

昇

筑波大学

システム情報系

高木剛

東京大学大学院

松井充

三菱電機株式会社

松本勉

横浜国立大学大学院

松本泰

セコム株式会社教授

情報理工学系研究科
開発本部

教授

役員技監

環境情報研究院教授

IS 研究所

コミュニケーションプラットフォームディビジョン
満塩尚史

マネージャー

内閣官房 情報通信技術(IT)総合戦略室 政府 CIO 補佐官（オブザーバ）内閣サイバーセキュリティセンター
警察庁
個人情報保護委員会事務局
総務省
法務省
外務省
財務省
文部科学省
厚生労働省
経済産業省
防衛省
警察大学校
国立研究開発法人産業技術総合研究所

3

資料２

量⼦コンピュータ時代に向けた暗号の在り⽅検討タスクフォースの設置について

令和元年６⽉２４⽇
CRYPTREC事務局

背景：暗号技術の課題• 遠くない将来に現在のRSA暗号や楕円曲線暗号は容易に解読されるようになるおそれ（コンピュータの性能向上や、⼤規模な量⼦コンピュータが実⽤化された場合）• ⼤規模システムの改修・更改には⼗年以上を要する
（単位）
FLOPS

（単位）

コンピュータ性能の向上に伴い、FLOPS
より鍵⻑の⻑いRSA暗号、楕円曲線暗号も危殆化のおそれ

コンピ

コンピ

タ性能

タ性能

図１：RSA暗号（※）の安全性評価

図２：楕円曲線暗号の安全性評価（※）桁数が⼤きい合成数の素因数分解が困難であることを安全性の根拠とした公開鍵暗号。過去、1024ビットの鍵⻑のものが使われていたが、その危殆化（解読されるおそれがあること）により、現在は2048ビット以上の鍵⻑のものが推奨されている。
（注）グラフの縦軸は、コンピュータが１秒間に処理可能な演算の回数（FLOPS：Floating-Point Operations Per Second）。

1

設置に⾄る経緯 現在のCRYPTREC暗号リストの策定（2013年3⽉1⽇）から6年が経過することや、
量⼦コンピュータの動向や新たな暗号技術の動向を踏まえて、次期CRYPTREC暗号
リストの改定⽅針の素案を、2018年度の暗号技術評価委員会及び暗号技術活⽤委員会において議論。
 両委員会の委員からは、改定⽅針よりも先に、次期CRYPTREC暗号リストに求められる要件を明確にすべきという意⾒。
 これらの議論を受けて、2018年度第1回暗号技術検討会（以下「検討会」という。）での審議の結果、検討会の下に「量⼦コンピュータ時代に向けた暗号の在り⽅検討タスク
フォース」（以下「タスクフォース」という。）を設置し、次期CRYPTREC暗号リストに求められる要件や課題等を整理することとした。
（参考）2018年度 暗号技術検討会 資料5別添 「量⼦コンピュータ時代に向けた暗号の在り⽅検討タスクフォース」の設置について（案）２．検討事項① ⼤規模な量⼦コンピュータの動向を踏まえた次期CRYPTREC暗号リストに求められる要件等の検討② その他新たな暗号技術の動向等（軽量暗号や秘密計算に利⽤される準同型暗号等）を踏まえた検討等2

CRYPTREC活動体制（2019年度）
暗号技術検討会（１）CRYPTREC暗号のセキュリティ及び信頼性確保のための調査・検討（２）CRYPTREC暗号リストの改定に関する調査・検討（３）関係機関と連携した暗号技術の普及による情報セキュリ
ティ対策の推進検討・提⾔

量⼦コンピュータ時代に向けた暗号の在り⽅検討タスクフォース

暗号技術評価委員会

暗号技術活⽤委員会（１）暗号技術の安全性及び実装に係る監視及び評価（２）新世代暗号に係る調査（３）暗号技術の安全な利⽤⽅法に関する調査（１）暗号の普及促進・セキュリティ産業の競争⼒強化に係る検討（２）暗号技術の利⽤状況に係る調査及び必要な対策の検討（３）暗号政策の中⻑期的視点からの取組の検討

暗号技術調査WG(暗号解析評価)

TLS暗号設定
ガイドラインWG
3

今後の進め⽅（案） タスクフォースは、四半期に１回程度の開催を想定し、原則、会合毎に検討事項を絞った議論を⾏う。
 議論の結果は、暗号技術検討会（年度末を予定）で報告の上、次期CRYPTREC
暗号リストの策定に活⽤。
第1回〜第3回までの進め⽅イメージ① 耐量⼦計算機暗号関係
 量⼦コンピュータの動向把握
 耐量⼦計算機暗号の動向把握
 次期CRYPTREC暗号リストへの追加にあたっての論点整理

第1回（今回）
第2回（9⽉頃）② その他、新しい暗号技術関係
 軽量暗号や秘密計算に利⽤される準同型暗号等、新たな暗号技術の研究開発・標準化動向

第3回（12⽉頃）

 次期CRYPTREC暗号リストへの追加にあたっての論点整理
4

資料３

量子コンピュータの動向について（素因数分解を例にして）

國廣 昇（筑波大学）「量子コンピュータ時代に向けた暗号の在り方検討
タスクフォース」第1回会合
2019年6月24日
1

素因数分解はそもそも難しいのか？
現状把握(1) 理論的に知られていること• 多項式時間アルゴリズムは知られていない• 知られている最善のアルゴリズムは，準指数関数時間//(2) 実験で確認されていること• 2009年12月：768ビット (232桁)の素因数分解• 数体ふるい法を使用• ふるいフェーズ：1500年 AMD Opteron processor(2.2 GHz with 2 GB RAM)2

未来を予測(3) 計算機能力の向上• ムーアの法則：
集積回路上のトランジスタ数は「18か月ごとに2倍になる」• スーパーコンピュータの性能向上
暗号の将来の脆弱性をできるだけ正確に予測するには．．．
(1) 理論的にどこまでわかっているか？
(2) 現在の技術で，実際にどこまで破られるか？
(3) 計算機能力向上の将来動向を調査することにより行う．
3

この発表で話したいこと
量子計算機を用いた場合は？
（古典計算機では，根拠を積み重ねて評価している）「安全」，「危険」の極論ではなく，• できるだけ正確に危険性を理解したい．
• もしくは，理解に向けて少しでも前進したい．
量子計算機の場合でも．．．
(1) 理論的にどこまでわかっているか？
(2) 現在の技術で，実際にどこまで破られるか？
(3) 計算機能力向上の将来動向を知りたい．

4量子アルゴリズム
1985年: Deutschが，量子Turing Machineを提案
1994年: Simonのアルゴリズム（周期関数の位数発見）
1994年: Shorの素因数分解アルゴリズム，
離散対数問題の解法アルゴリズムの提案（可換隠れ部分群問題への拡張）
1996年： Groverのアルゴリズム（探索問題）
参考：これ以外のアルゴリズム
Quantum Algorithm Zoo
https://math.nist.gov/quantum/zoo/5量子計算機と暗号を取り巻く環境の変化
1.ポスト量子暗号の募集
2015年8月：NSAが，ポスト量子暗号への移行を表明
2016年2月：NISTが，ポスト量子暗号の標準化計画を公表
量子計算機の実現に備えて，素因数分解，離散対数問題の困難さに依存しない暗号の募集
69件が応募2019年1月30日， Round 2 algorithmsを公表
2022〜2024年までに標準化

6

2. Noisy Intermediate-scale Quantum (NISQ)の開発
小さいながらも，実際の量子計算機が出来てきた
Noisy Intermediate-scale Quantum (NISQ) system• Google 72量子ビット• IBM 50量子ビット• Intel 49量子ビット
ただし，ノイズは大きい
このまま，大規模化が進むのか？

7

(3) 将来の量子計算機の動向を予測する
Quantum Computing: Progress and Prospects (2018)*• 大規模でノイズの小さい（誤り訂正機能付き）量子計算機がいつ出来るかの予測をするには早すぎる(it is still too early to be able to predict the time horizon
for a scalable quantum computer.)• NISQの開発を当分を目指す．まずは，できるものを作る．
• 商業的に成功すれば，もっと大きい物を目指す*National Academies of Sciences, Engineering, and Medicine発行

https://www.nap.edu/catalog/25196/quantum-computing-progress-and-prospects8(1) 量子計算機による素因数分解に関する事実
1. 素因数分解，離散対数問題を多項式時間で解くことができる
2. 実際の回路構成や精密なリソース（量子ビット数，
ゲートの個数）はよく理解されている．
• 素因数分解 (K05, TK08, HRS16)• 楕円離散対数問題 (RNSL17)nビットの素因数分解を行うのに．．．
• 標準的な回路構成では，
3n+2 量子ビット，O(n3)個の基本ゲート• 量子ビットを削減した回路では，2n+2量子ビット， O(n4)個の基本ゲート（理想的な環境下：誤りは全く無い，各量子ビットは完全結合）

9Shorの素因数分解アルゴリズムの概略
戦略： 合成数N，自然数aに対して, ar = 1(mod N)となる最小の自然数 r （位数）を求める，
Step1: 初期状態 |0＞|1＞を構成
Step2: Hadamard変換を適用



Step3: べき乗剰余演算を適用



Step:4 逆QFTを適用

2 m 1

1

j 1

2
m

j 0

2 m 1

1

j a mod N

2
j

m

j 0

s
1 r 1 ~us
r s 0 r

Step5: 第1レジスタを観測：

~
s

r

Step6: 連分数展開を行い r を求める．

10

x1
x2
x3
x4
|1

H
H

Inverse
QFT

H
H

Ua

aとk を固定すると，は，量子回路で記述可能
11

回路の（一部分の）例：(11010011)2=211の加算
b0
b1
b2
b3
b4
b5
b6
b7

c1
c2
c3
c4
c5
c6
c7
b8

C-NOT gate
c
c
t

t c

Toffoli gate
c1
c1
c2
c2
t

t  (c1  c2 )12

素因数分解をするのに必要な量子ビット数，ゲート数*
768ビット合成数

2048ビット合成数# of qubits# of gates# of qubits # of gates

標準的な構成2306

1.22×1011

6146

3.04×1012

量子ビット削減
回路

1539

--

4099

1.35×1015

上記の近似版

1539

8.68×1011

4099

1.22×1013* N. Kunihiro, “Exact Analysis of Computational Time for Factoringin Quantum Computers,” IEICE Trans. Vol. 88-A, No.1 2005.
• 1500〜4000量子ビットが必要• 1011〜1013程度の量子ゲートが必要
ただし，量子誤りが全くないという前提

13

(2) Shorのアルゴリズムに基づく素因数分解実験[1] Experimental realization of Shor's quantum factoring algorithm
using nuclear magnetic resonance, Nature, 2001.
[2] Shor’s Quantum Factoring Algorithm on a Photonic Chip,
Science, 2009.
[3] Computing prime factors with a Josephson phase qubit quantum
processor, Nature Physics, 2012.
[4] Realization of a scalable Shor algorithm, Science, 2016.
[5] Experimental realisation of Shor’s quantum factoring algorithm
using qubit recycling, Nature Photonics, 2012.

14

Device

研究機関

Year

合成数

Journal

NMR

IBM

2001

15

NaturePhotonic chip

U. of Bristol

2009

15

ScienceSuperconductivity UCSB

2012

15

Nature Physics

Ion Trap

U. Innsbruck

2016

15

Science

PhotonU. of Bristol

2012

21

NaturePhotonics• 標準的な回路構成では，10〜14 qubit必要．
• いずれも，かなり少ないqubit数で実験を行っている．
• 汎用的ではない回路構成になっている．
15

[1]で用いられた回路（IBM, NMR）
1
2

| |1 ⟶

x7 mod 15
x2
y0
y2

1
2

| |7 mod 15
x4 mod 15

x1
x3
y1
y3
x3=1なら， 7倍x2=1なら,y0 と y2をSWAP

x2=1なら,y1 と y3をSWAP

16この回路は， N=15 であることを利用
1 → x3==1のとき，1に6を足す→ x2==1のとき， 4y mod 15を実行

y=(y3 y2 y1 y0)2とすると，
4 y= (y3 y2 y1 y0 00)2=16× (y3 y2)2+(y1 y0 00)2
4 y mod 15= (y3 y2)2+(y1 y0 00)2=(y1 y0 y3 y2)22個のSWAPで実行可能

17

[4]で用いられた回路 (Innsbruck, Ion Trap)
a=2, 7, 8, 13を使用
x 4 mod 15x

HHx a mod 15
H

H

IQFT

y0
y1
y2

U4

Ua
a=2, 7,
8, 13

y3

18

X

＋
X X
＋
X X＋
X＋

X

X

X X
X X
X
U2

X

X

X ＋

X

X X ＋
X

X

X
U8

X
U7

X
X

X
X
||

U4

U13

X X

X

SWAP

＋
＋

X

＋
X
＋
X ＋
＋
X

C-SWAP
X
X
||

U11

19

[2]で用いられた回路 (U. of Bristol, Photonic chip)
x1
x2
x3
y0
y1

a=7を使用70=1, 71= 7, 72 =4, 73=13, 74=1であることを使用
Trick: 以下のencodeを使用
1→ (00)2, 7 → (01)2, 4 →(10)2, 13 → (11)2.
U7: (00)2 (01)2,
U4: (0x)2(1x)2
この回路は，位数が4であるという事実を使いすぎている．
そもそも，Shorのアルゴリズムの目的は位数を求めること．
20

21の素因数分解実験 [5]a=4を使用．回路構成において，4の21を法とした位数が3(43 mod 21=1)であることを使用．
4i mod 63 for i=0, 1, 2,… において，1, 4, 16しか現れない|1>
41 mod 63 = 4x4
42 mod 63 =16
x 16
44 mod 63 = 4|4>
48 mod 63 =16|16>|0>
符号化： 1 → 0, 4 → 1, 16 → 2 U+
U+: |x> → |x+1 mod 3>
U|1>
U-: |x> → |x-1 mod 3>|2>
qubitではなく，qutrit (=3量子状態を持つ) を利用

21

実際の回路
|0>

H

H

H

H

H

IQFT

H
・・・

|0>

U+

U-

U+

回路設計において，位数が3であるという事実を使っている．
しかし，Shorのアルゴリズムの目的は，位数を求めることだった．

22

[2][5]の回路の一般化
Shorのアルゴリズムのもともとの形
1
2

1| |1 ⟶

2

| |

mod

“simplified” or “compiled”版のShorのアルゴリズム
1
2| |0 ⟶

1
2| | modr は，そもそも計算したかったもの．
Shorのアルゴリズム（の簡略版）としては不適当
23Oversimplifying Quantum Factoring*aを位数2の元とする (a2 mod N = 1)
1
1
| |1 ⟶| | mod22“oversimplified”版Shorのアルゴリズム
1
2
|0>

H

| |0 ⟶

1
2| | mod 2

H

|0>
•
•

論文中では，20,000-bit！の素因数分解を示している
ビットサイズだけを追求しても意味はないことを主張* A Smolin, John & Smith, Graeme & Vargo, Alexander. (2013).
Oversimplifying quantum factoring. Nature. 499. 163-165.

24

N, aの具体的な計算法
SageMathによる実装
k=4096p=random_prime(2^k-1, false, 2^(k-1))
q=random_prime(2^k-1, false, 2^(k-1))
N=p*q
a= crt(1, -1, p, q)
計算時間：2048-bit RSAの場合：一瞬
4096-bit RSAの場合：1秒程度
8192-bit RSAの場合：10秒程度

25量子計算機を用いた素因数分解実験の現状把握• 素因数分解された合成数で最大のものは15• ただし，「15」であることを利用している．

Quantum Factoringのレベルの提言
Level 1 QF: 位数の情報を回路に組み込む
Level 2 QF: 特殊な合成数だけに有効
Level 3 QF: 全ての合成数に有効
現状では，Level 1とLevel 2の実装のみであり，Level 3での実装は2019年現在，存在しない．
26

Quantum Computing: Progress and Prospectsの主張の抜粋（関連部分のみ）
Key Finding 1:
Given the current state of quantum computing and recent rates ofprogress, it is highly unexpected that a quantum computer that cancompromise RSA 2048 or comparable discrete logarithm based publickey cryptosystems will be built within the next decade.
Key Finding 10:
Even if a quantum computer that can decrypt current cryptographic
ciphers is more than a decade off, the hazard of such a machine ishigh enough - and the time frame for transitioning to a new security
protocol is sufficiently long and uncertain - that prioritization of thedevelopment, standardization, and deployment of post-quantum
cryptography is critical for minimizing the chance of a potential
security and privacy disaster.

27

Key Finding 3:
Research and development into practical commercial applicationsof noisy intermediate scale quantum (NISQ) computers is an issueof immediate urgency for the field. The results of this work will
have a profound impact on the rate of development of large-scalequantum computers and on the size and robustness of a commercial
market for quantum computers.
Key Finding 4:
Given the information available to the committee, it is still too early
to be able to predict the time horizon for a scalable quantum
computer. Instead, progress can be tracked in the near term bymonitoring the scaling rate of physical qubits at constant averagegate error rate, as evaluated using randomized benchmarking, andin the long term by monitoring the effective number of logical(error corrected) qubits that a system represents.

28

まとめ
量子計算機と暗号技術の関係について整理(1) 理論的には，多項式時間で解読可能• 回路構成，必要なリソースもよく知られている(2) 実際の素因数分解実験を紹介• いくつかの物は，素因数分解実験としては不適当• いくつかの物は，ターゲットとする合成数に強く依存• 汎用的な回路による実験が望ましい(3) 量子計算機の将来の動向を調査• 将来を予測することは難しい• 量子計算機の到来時期を正確に予測できるのは，当分先の話（＝準備をしなくて良いということではない）• 色々な方面から研究を進める必要がある．
29

資料４
量子コンピュータ時代に向けた暗号の在り方検討タスクフォース
令和元年6月24日

耐量子計算機暗号の動向について高木 剛
東京大学大学院情報理工学系研究科
http://crypto.mist.i.u-tokyo.ac.jp/

01/22

講演概要
• 耐量子計算機暗号(PQC)• NIST PQC標準化• CRYPTREC における PQC への取り組み• 暗号の安全性評価方法• 格子暗号CRYPTREC暗号技術評価委員会「耐量子計算機暗号の研究動向調査報告書」
2019年4月5日公開済 https://www.cryptrec.go.jp/
02/22

公開鍵暗号の歴史
Shorのアルゴリズム NMR量子計算機 (7量子ビット)
1980
｜

1990
｜ ×

2000
｜×

2010
｜

×

IBM Q (20量子ビット)
2020
｜

2030
|

RSA暗号 (素因数分解問題)

広く普及 楕円曲線暗号 (離散対数問題)
量子計算機で危殆化‼

耐量子計算機暗号(PQC)(格子, 符号，多変数多項式, ハッシュ関数など)実用化に向けた
研究段階
03/22

量子クラウド IBM Q

https://www.research.ibm.com/ibm-q/network/より転載

IBM Q、2017年11月、20量子ビットの量子計算機
近い将来に50量子ビットに拡張予定

https://jp.techcrunch.com/2018/03/06/2018-03-05-googles-new-bristlecone-processor-brings-it-one-step-closer-to-quantum-supremacy/より転載
http://www.itmedia.co.jp/news/articles/1801/10/news099.htmlより転載

Google Bristlecone 72量子ビット、 Intel Tangle Lake: 49量子ビット
04/22

量子コンピュータの規模予測

Interface 2019年 3月号、CQ出版社から転載
05/22

PQCrypto 2016

• 参加者240名(北米80名、欧州60名、アジア60名、日本40名)• NISTが耐量子計算機暗号の標準化計画を発表した
06/22

NIST PQC 標準化計画
http://csrc.nist.gov/groups/ST/post-quantum-crypto/

公開鍵暗号プリミティブを公募(2017年11月30日〆切)- 鍵交換方式 (SP 800-56 B)- 暗号化 (SP 800-56 A)- ディジタル署名 (FIPS PUB 186-4)

公募〆切後、3～5年かけて安全性と効率性を評価する。
利用される数学問題- 格子暗号 (Lattice-based cryptography)- 符号暗号 (Code-based cryptography)- 多変数多項式暗号 (Multivariate polynomial cryptography)- ハッシュ関数署名 (Hash-based signature)- 同種写像暗号 (Isogeny-based cryptography)
07/22

2017年12月応募状況 (69件)•

格子暗号 (24件)

Compact LWE, CRYSTALS-DILITHIUM, CRYSTALS-KYBER, Ding Key Exchange, DRS,
EMBLEM and R.EMBLEM, FALCON, Frodo, HILA5, KINDI, LAC, LIMA, Lizard, LOTUS,
NewHope, NTRU-HRSS-KEM, NTRU Prime, NTRUEncrypt, Odd Manhattan, pqNTRUSign,
qTESLA, Round2, SABER, Titanium•

符号暗号 (16件)

BIG QUAKE, BIKE, Classic McEliece, DAGS, Edon-K, HQC, LEDAkem, LEDApkc, McNie,
NTS-KEM, pqsigRM, QC-MDPC KEM, RaCoSS, Ramstake, RLCE-KEM, RQC•

多変数多項式暗号 (10件)

CFPKM, DME, DualModeMS, GeMSS, Gui, HiMQ-3, LUOV, MQDSS, Rainbow, SRTPI•

ハッシュ関数署名 (2件)

Gravity-SPHINCS, SPHINCS+•

同種写像暗号 (1件)

SIKE

•

その他 (16件)

Giophantus, Guess Again, HK17, LAKE, Lepton, LOCKER, Mersenne-756839,
OKCN/AKCN/CNKE, Ouroboros-R, Picnic, Post-quantum RSAEncryption, Post-quantum
RSASignature, RankSign, RVB, Three Bears, WalnutDSA

08/22

2019年1月から第2ラウンド (26件)
格子暗号
鍵交換・暗号化 (9方式): CRYSTALS-KYBER, Frodo-KEM, LAC,
NewHope, NTRU, NTRU Prime, Round5, SABER, Three Bears
ディジタル署名 (3方式): CRYSTALS-DILITHIUM, FALCON, qTESLA

符号暗号
鍵交換・暗号化 (7方式): BIKE, Classic McEliece, HQC,
ROLLO, LEDAenc, NTS-KEM, RQC

多変数多項式暗号
ディジタル署名 (4方式): GeMSS, LUOV, MQDSS, Rainbow

ハッシュ関数署名
ディジタル署名 (1方式): SPHINCS+

同種写像暗号
鍵交換・暗号化 (1方式)：SIKE

その他
ディジタル署名 (1方式)： Picnic

09/22

NIST PQC 標準化スケジュール
https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Workshops-and-Timeline• 2017年12月～2018年12月: 第1ラウンド評価期間• 2019年1月: 第2ラウンド選出暗号発表• 2019年～2020年: 第2ラウンド評価期間• 2020年/2021年: 最終候補選出 or 第3ラウンド開始• 2022年/2024年: 標準規格ドラフト• 2030年まで SP 800-56, FIPS PUB 186-4を利用可能
10/22

2030年の移行問題
耐量子計算機暗号を利用？
RSA暗号の鍵長を伸ばして利用？
x 2030年: RSA暗号(2048ビット)の使用終了
耐量子暗号への移行期間
x

2022年-2024年: 耐量子計算機暗号の標準規格ドラフトx

2020年: 最終候補選定または第3ラウンド開始x

2019年8月: 第2回NIST PQC標準化会議
11/22

PQC標準化をめぐる国内外の動き
国内

暗号解析評価WG

CRYPTRECPQCに関連する活動

2019.3 PQC技術報告書発行

2015.3「格子問題等の困難性に関する調査」発行

暗号技術評価委員会
暗号技術検討会

CRYPTRECにおける
PQC対応 検討開始
2013.3.1
CRYPTREC暗号リスト発表

2013

2014

2015

2023.3
CRYPTREC暗号リスト
改定？

2016

2017

2018

2019

2020

2021

2022

2023

2024

2025

最速スケジュールNIST
PQC標準化国際

2019.1.30
2016.4.28 2016.12.20 2017.11.30
NISTIR 8105 募集要項 応募締切 Round 2候補発表
発表
リリース
Round 1Round 2PQC のDraft Standards 公開(2022～2024年)
2020～2021年に開始またはRound 3なしで選定完了(Round 3)

12/22

RSA暗号の公開鍵

13/22

RSAチャレンジ問題の解読記録推移
解読達成日

解読桁長

計算時間(パソコン1台換算)

1991年4月

100桁 (330ビット)

1993年6月

120桁 (397ビット)

1996年4月

130桁 (430ビット)

1999年2月

140桁 (463ビット)

1999年8月

155桁 (512ビット)

2003年12月

174桁 (576ビット)

2005年5月

200桁 (663ビット)

約55年 (Opteron 2.2 GHz)2009年12月

231桁 (768ビット)

約1500年 (Opteron 2.2 GHz)

未解読

308桁 (1024ビット)

未解読

616桁 (2048ビット)

約7年 (1500 MIPS年)

約36年 (8000 MIPS年)

14/22

数体篩法
この数値 (FLOPS)
は、スーパーコンピュータを年間利用したときの計算時間を意味する。

計算時間

1

1030 1025 -□1020 □

1015 □

1010 105 ~
~

0

桁数
|

|

231桁 308桁(768ビット) (1024ビット)|

616桁(2048ビット)

15/22

素因数分解の困難性に関する計算量評価(http://www.cryptrec.jp/)

16/22

量子コンピュータによる素因数分解
計算時間1030 1025 -□1020 □

1015 -

指数時間のスピードアップ□

1010 105 ~~0(log N)3||

231桁 308桁(768ビット) (1024ビット)|

616桁(2048ビット)

桁数
17/22

格子暗号

18/22

ノイズ付き連立一次方程式(LWE問題)・連立一次方程式: 容易に解が求まる

・ノイズ付き連立一次方程式： 解を求めるのは困難
e1, e2 ： ノイズ(次元 or ノイズ： 増加させると)LWE問題は計算が困難となる
19/22

NIST PQC 第2ラウンド
格子暗号の技術分類
分類

公開鍵暗号・鍵交換方式

ディジタル署名NTRU暗号系

NTRU, NTRU Prime

FALCON

LWE問題

Frodo-KEM-

Ring-LWE問題

NewHopeqTESLA

CRYSTALS-KYBER

CRYSTALS-DILITHIUM

LWR問題

Round5, SABER-

他のLWE問題

LAC, Three Bears-

LWE
Module-LWE問題
問題系

20/22

ダルムシュタットLWE問題チャレンジ(ノイズ)

2018-19: G6K algorithm (部分篩法)+ 埋め込み法(Albrecht, Ducas, Herold, Kirshanova,
Postlethwaite, Stevens)

128ビット量子安全性

2017: RSR algorithm + 埋め込み法(柏原, 照屋)

2016: Progressive-BKZ algorithm+ 埋め込み法(王, 青野, 林, 高木)
2016: BKZ 2.0 algorithm+ 最近平面法(Xui, 福島, 清元, 高木)
(次元)

21/22

まとめ
• 耐量子計算機暗号の最新動向
米国標準技術研究所NISTによる標準化計画
CRYPTRECにおける PQCへの取り組み• 格子暗号
ダルムシュタットLWE問題チャレンジ

CRYPTREC暗号技術評価委員会「耐量子計算機暗号の研究動向調査報告書」
2019年4月5日公開済 https://www.cryptrec.go.jp/

22/22

参考資料
（平成 31 年３月 29 日 暗号技術検討会 資料５）

次期 CRYPTREC 暗号リストの改定に向けた議論について
現在の CRYPTREC 暗号リストの策定（2013 年 3 月 1 日）から６年が経過することや、量子コンピュータの動向や新たな暗号技術の動向等を踏まえ、次期 CRYPTREC 暗号リストの改定に向けて、CRYPTREC 事務局で作成した改定方針等の素案について、暗号技術評価委員会及び暗号技術活用委員会でいただいたご意見を紹介する。

次期 CRYPTREC 暗号リストについて（CRYPTREC 事務局において作成した素案）
1 改定方針-【改定時期】現在の CRYPTREC 暗号リストは 2013 年 3 月 1 日に改定されており、改定より 10 年後の 2023 年 3 月の改定を目指して検討を開始する。

-【リスト構成】現在の「電子政府推奨暗号リスト」「推奨候補暗号リスト」「運用監視暗号リスト」から大幅見直しは行わない。

-【暗号公募について】一般への暗号公募は行わない。

-【新たに追加する暗号技術の候補について】主として標準化動向をもとに事務局で選出を行い、暗号技術検討会で審議の上決定する。学会に提案されている
新たな暗号技術については、仕様、安全性評価、知的財産権、調達可能性等の観点で問題ないと判断できれば候補になりうる。

-【暗号技術評価委員会の役割】暗号技術評価委員会では、安全性評価および実装評価を行う。評価対象は新たに追加する暗号技術の候補のみとする。現リストに掲載されている暗号技術については安全性監視を継続しており、改めて評価を行うことはしない。

-【暗号技術活用委員会の役割】暗号技術活用委員会では、利用実績調査を行う。

-【選考基準について】選考基準は 2021 年度までに両委員会で議論の上、暗号技術検討会で決定する。

2 耐量子計算機暗号への対応
 次期 CRYPTREC 暗号リストへの反映-

2022 年度開始までに NIST PQC 標準化で選定された方式を、新たに追加する暗号技術の候補の参考とする。

-

Hash-based signature については IETF 標準をベースに新たに追加する暗号技術の候補の参考とする。



PQC への移行計画策定については、その時期を含めて NISC でご検討頂く。



RSA-2048 からの移行については既に始まっているところもあり、何をすべきか議論を開始する。
1

3 軽量認証暗号・軽量ハッシュ関数への対応
 次期 CRYPTREC 暗号リストへの反映-

2022 年度開始までに NIST 軽量暗号標準化で選定された方式を、新たに追加する暗号技術の候補の参考とする。
NIST 軽量暗号標準化
軽量認証暗号と軽量ハッシュ関数のみ(2019.2.25 応募締切、2-4 年後完了)“some algorithms could be selected for standardization after two
to four years”

4 その他
次期 CRYPTREC 暗号リストの改定に向けて議論すべき項目は何か、追加・削除を検討
すべき技術分類はあるか。
例)-

64 ビットブロック暗号の利用について-

64 ビットブロック暗号を安全に利用するための暗号利用モード-

現リストに掲載されている暗号技術に対する量子計算機の影響（鍵長、パラメータ等）-

秘密分散(ISO/IEC 19592) や準同型暗号(ISO/IEC 18033-6)など

図：これまでの電子政府推奨暗号リストおよび CRYPTREC 暗号リストの改定の流れ

2

3

暗号技術評価委員会（2018 年 7 月 19 日、2019 年 3 月 11 日開催）で頂いた主な意見
「耐量子計算機暗号について」-

量子計算機の性能については、不確定要素が多いことから、予想通りには進展しないかもしれないが、進展した場合に備えて暗号技術評価委員会で PQC に関する技術的な検討を行う必要がある。

-

PQC への移行計画を考えるのは時期尚早であろう。また、簡単ではない。

-

PQC への移行について、複数の方式を対応する「暗号 Agility」の考え方で対応が検討さ
れている。



「RSA-2048 からの移行について」-

PQC への移行以前に、RSA-2048 からの移行問題が先にあり、20 年という期間の対応が求められている認証局ではすでに移行が始まっている。それは電子政府関係も無縁ではない。例えば電子パスポートについては、国際的な観点から ICAO の動きに対応して移行が検討されている。ICAO 仕様のルート証明書に ECDSA が含まれている。

「量子コンピュータの共通鍵暗号への影響について」-

共通鍵暗号分野においても、量子計算機による影響について適切に監視する必要がある。

「軽量暗号について」-

NIST では軽量暗号の認証暗号やハッシュ関数の標準化公募を始めようとしている。2023
年のリスト改定に向けては、PQC だけではなく軽量暗号のことも考えておいた方が良い。

-

軽量暗号技術は、その性質上、セキュリティマージンを厳しく設定していることが多く、一般的な実装とは思想的に違う位置づけになるのかもしれない。64 ビットブロック暗号も多いということから、CRYPTREC 暗号リストの枠組みとの整合性を整理した上でリストの改定にのぞむべきである。

-

NIST の公募と CRYPTREC における軽量暗号の範囲との関係を整理する必要がある。

「CRYPTREC 暗号リスト（の改定）について」-

次期 CRYPTREC 暗号リストの改定方針について議論する前に、そもそも次期リストに求める要件を明確にする必要がある。

-

リストの構成は、このままでよいのかという点を改めて議論してもよいと思われる。

-

産業界や政府、NISC などにヒアリングして、これまで CRYPTREC がどのように役に立ってきたのかを確認してはどうか。その際に、従来の暗号技術の評価と監視だけではなく、別の役割を求められているのならそれを含めて検討した方が良い。

4

暗号技術活用委員会（2019 年 3 月 14 日開催）で頂いた主な意見
「改定方針を前提とするのではなく、リストの位置づけから根本的に見直したほうがよい」-

改定方針には、暗号そのものを考える暗号アルゴリズムに閉じた世界ではなくて、今後どうやって暗号を使ってもらうのかということが盛り込まれていて欲しい。

-

他の政策テーマやアーキテクチャなどの連携との関連性を整理して暗号リストを位置づけてもらいたい。何のための暗号リストなのかの大方針を明確にすべきである。

-

現在リストが 3 個あるが、その形態が妥当であるかについても考える必要がある。

「次の暗号アルゴリズムの移行に向けて政策的な議論をする場が必要である」-

前回（RSA1024 から RSA2048 への移行）は移行のためのリソースや体制等があり業界全体が一致して動いたが、今はそれだけのリソースも体制もない。資金手当てを含めた政策的な誘導がないと移行が進まないし、時間もかかると思われる。

-

PQC への移行は相当困難である。暗号技術活用委員会としては、暗号を移行できる（暗号アジリティ（Crypto-agility）を持った）システムを作らせるという活動をすべきである。
PQC への移行を考える前に、暗号を移行できるシステムを作るということを念頭においた活動を行わないと、現実的には PQC への移行は破綻するのではないかと思われる。

-

RSA2048 から（PQC ではなく、より強度が高い公開鍵暗号）の移行が、少なくともルート
認証局では始まっており、新しく建てるルート認証局では RSA2048 はなくなりつつあると思われるので、実態調査を実施した方がよい。

-

スマホでどの程度の強度の暗号がハードウェアでサポートされているのかなど、RSA2048
よりも強度の高いアルゴリズムがどのように使われるか、今現在使えるのか、といった点について、実態調査を実施した方がよい。

-

RSA2048 からの移行は直近に移行完了させなければならない課題ではないので、無理なく暗号を移行できるために必要なプロセスの洗い出しから始めたほうがよい。それを専門に検討するチームで議論してもらうべきである。

5