NICT サイバーセキュリティシンポジウム 20192019年2月7日

耐量子計算機暗号の最新動向

国立研究開発法人情報通信研究機構
サイバーセキュリティ研究所
セキュリティ基盤研究室
篠原 直行
1

概要
Q: 耐量子計算機暗号（PQC: Post-quantum cryptography） とは？

A: 十分な規模の量子計算機が実用化されても安全性を保つことができる暗号.
Q: 量子計算機が実用化されると何が問題に？
A: 現在利用されている公開鍵暗号は安全性が低下する.

Q: PQC について NICT が取り組んでいることは？
A: PQC の最新動向調査及びPQC の開発・安全性評価.
2

3

ネットワーク社会の安全を守る暗号技術
ネットワークの発展とともに、暗号技術は通信・交通・ビジネスの根幹を支える身近な技術へ

4

暗号技術の身近な利用例• インターネットショッピングなどで見かける
https://www.********- Hyper Text Transfer Protocol Secure:
SSL/TLS プロトコル（暗号技術）を利用してHTTP通信を行う。
共通鍵暗号（AES 等）
同じ鍵を利用鍵共有に公開鍵暗号（RSA, ECC 等）を利用

5公開鍵暗号の歴史
1980｜

1990｜

2000｜

2010｜

2020｜

2030
|

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

広く普及 楕円曲線暗号 (離散対数問題)
ペアリング暗号 (クラウド時代向けの暗号)標準化、製品化耐量子計算機暗号（PQC）: 格子理論, 多変数多項式,符号理論,同種写像
完全準同型暗号, 多重線形性暗号

研究段階
6公開鍵暗号と数学と量子計算機
量子計算機とShor’s algorithm で効率よく解くことができる• 現在使用されている公開鍵暗号⁃ RSA 暗号: 整数の素因数分解⁃ 楕円曲線暗号: 楕円曲線上の離散対数問題• PQC として期待される公開鍵暗号⁃ 格子に基づく暗号: 格子問題（LWE 問題等）
⁃ 符号に基づく暗号: LPN 問題⁃ 多変数多項式に基づく暗号: MP 問題, IP 問題⁃ 同種写像に基づく暗号: 同種写像問題
7

PQC の実用化に向けた世界的な動き• 背景– もし十分な規模の量子計算機が実用化されるとRSA 暗号や楕円曲線暗号は安全性を保てない.

–

今後２０年以内に十分な規模の量子計算機が構築されると予想されている.

– 現在利用されている暗号は, 普及するまで２０年近くかかっている.
– 今から PQC の実用化に取り組む必要がある.
参照（NIST）：https://csrc.nist.gov/projects/post-quantum-cryptography8• 世界各国の動き– 米国（NIST）: PQCを公募し（締め切り：2017.11.30）、現在は評価の段階– 欧州（ETSI）：PQCの調査を実施- 日本（CRYPTREC）: PQCの調査を実施

PQCに関する最新の動向を把握する必要性が高まっている.
9

10

暗号技術における NICTの取り組み【中長期計画】1-4. サイバーセキュリティ分野 (3) 暗号技術
機能性暗号技術

暗号技術の安全性評価

プライバシー保護技術

IoTの展開に伴って生じる新たな社会ニーズに対応するため、新しい機能を備えた機能性暗号や軽量暗号・認証技術の研究開発に取り組む

暗号技術の安全性評価を実施し、新たな暗号技術の普及・標準化に貢献するとともに、安心・安全なICTシステムの維持・構築に貢献

パーソナルデータの利活用に貢献するためのプライバシー保護技術の研究開発を行い、適切なプライバシー対策を技術面から支援

 暗号技術の安全性評価における日本随一の研究拠点
 中立公平で信頼性の高い安全性評価情報の継続的発信 セキュリティ＆プライバシー保護技術の研究連携拠点に
 S＆Pの新たな研究開発テーマでの国内外研究連携拠点を目指す

 社会で活用される研究開発成果の創出と社会展開
 パーソナルデータ利活用や改正個人情報保護法施行に資する技術開発
11

CRYPTREC とは•

CRYPTREC (Cryptography Research and Evaluation Committees)– 電子政府推奨暗号の安全性を評価・監視し、暗号技術の適切な実装法・運用法を調査・検討するプロジェクト
暗号技術検討会
事務局：総務省、経済産業省

暗号技術評価委員会

暗号技術活用委員会

事務局：NICT, IPA

事務局：IPA, NICT

暗号技術の安全性・実装評価を中心とした技術的な検討課題を担当

暗号解析評価WG

セキュリティ対策の推進、暗号技術の利用促進
及び産業化を中心とした暗号利用に関する検討課題を担当

PQC の最新動向の調査を実施

12

PQCの最新動向調査計画• 活動内容(2017 年度及び 2018 年度)
PQCの代表的な四方式について三つの機能を中心に調査し, 結果をまとめる。
四つの暗号方式・格子に基づく暗号・符号に基づく暗号・多変数多項式に基づく暗号・同種写像に基づく暗号調査の中間報告（2018年2月）

執筆方針を決定（2018年6月）

執筆内容を決定（2018年10月）
報告書完成（2019年2月）

文献等の調査三つの機能・暗号・署名・鍵交換

調査報告書の執筆方針を決定

第2回WG

第1回WG
2017年度

第1回WG

調査報告書を執筆

第2回WG
2018年度

第3回WG

13

14

安全性評価へのNICTの取り組み
現在利用されている暗号技術

今後の利用が想定される
暗号技術

・ 電子政府推奨暗号・ 国際標準暗号・ その他デファクト暗号
RSA, ECC, AES, SHA*, …

・ 格子に基づく暗号・ 多変数多項式に基づく暗号・ 準同型暗号・・・

安全性評価
安心・安全なICTシステムの維持・構築に貢献
安全性を評価する技術及び理論

安全性評価
新たな暗号技術の信頼性向上・普及・標準化に貢献

数体篩法、関数体篩法、格子理論、代数方程式理論（グレブナー基底）など
15

公開鍵暗号と数学と量子計算機
量子計算機とShor’s algorithm で効率よく解くことができる• 現在使用されている公開鍵暗号⁃ RSA 暗号: 整数の素因数分解⁃ 楕円曲線暗号: 楕円曲線上の離散対数問題

今日のお話• PQC として期待される公開鍵暗号⁃ 格子に基づく暗号: 格子問題（LWE 問題等）
⁃ 符号に基づく暗号: LPN 問題⁃ 多変数多項式に基づく暗号: MP 問題, IP 問題⁃ 同種写像に基づく暗号: 同種写像問題

16

格子に基づく暗号• 格子問題を解く計算の困難性を暗号の安全性の根拠とする暗号
最短ベクトル問題(SVP)：一番原点に近い格子点を探す

b2

O

最近ベクトル問題(CVP)：与えられた点に一番近い格子点を探す

b1• CVPの仲間の、LWE(Learning with errors)問題とその亜種がよく使われる17

LWE（Learning With Errors）問題とは
𝑚×1• 秘密情報：𝒔 ∈ 𝐙𝑞𝑛×1 と 𝒆 ∈ 𝜓𝛼𝑞• 公開情報： 𝐀 ∈ 𝐙𝑞𝑛×𝑚 と 𝒃 ∈ 𝑍𝑞𝑚×1
b= sA+e(mod q)e=(e1,…,em) はノイズ

• 𝒔 または 𝒆 を計算せよ• 素因数分解や離散対数問題とは異なる問題
18

公開鍵暗号の安全性評価• 公開鍵暗号の鍵長と安全性
000

低00 0

安全性

00 0・・・・

00 0高• ＲＳＡ暗号の場合
15 = 3・5,687947247083 = 765881・898243• 現時点での技術力で解ける鍵長の最大値を解読実験の世界記録から見積もる
19

格子に基づく暗号の安全性評価• TU Darmstadt LatticeChallenge
http://www.latticechallenge.org/- 独ダルムシュタット工科大学
が2008年より主催している
さまざまな格子問題のコンテスト› Lattice Challenge› SVP Challenge› Ideal Lattice Challenge› LWE Challenge
20格子に基づく暗号の安全性評価（世界記録の更新）
TU Darmstadt LWE Challenge

問題生成中
未解読問題
ノイズの大きさNICT・九大共同研究チームで出した記録

解かれた問題次元21

22

PQC の開発•LOTUS(ロータス)• Learning with errOrs based encryption with chosenciphertexT secUrity for poSt quantum era• LWE 問題を利用した公開鍵暗号
共通鍵暗号（AES 等）
同じ鍵を利用鍵共有に公開鍵暗号を利用

23

NIST の公募に提案

参照（NIST）：https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Workshops-and-Timeline

24

LOTUS と FrodoKEM の比較
公開鍵のサイズ

暗号文のサイズ

双方の和のサイズ

LOTUS

658.9 KB

1.1 KB660 KB

FrodoKEM

9.6 KB

9.7KB

19.3 KB

LWE 問題を利用

詳しくはNISTIR 8240参照

25

概要(まとめ)
Q: 耐量子計算機暗号（PQC: Post-quantum cryptography） とは？

A: 十分な規模の量子計算機が実用化されても安全性を保つことができる暗号.
Q: 量子計算機が実用化されると何が問題に？
A: 現在利用されている公開鍵暗号は安全性が低下する.

Q: PQC について NICT が取り組んでいることは？
A: PQC の最新動向調査及びPQC の開発・安全性評価.
26