CRYPTREC MT-1441-2020

暗号技術検討会
量子コンピュータ時代に向けた暗号の在り方
検討タスクフォース（第４回（2020年度第１回））
令和３年３月３日
１０：００～１２：００
オ ン ラ イ ン 開 催

議事次第
１

開会

２

議題
（１）本年度の検討内容等について（２）量子コンピュータに関する動向等について（３）量子コンピュータに対する暗号技術の動向等について（４）CRYPTREC暗号リストでの推奨候補暗号リストの取扱いについて（５）その他

３

閉会

配付資料一覧
資料１

これまでの議論と本年度の検討内容について

資料２

量子コンピューティング最前線

資料３

耐量子計算機暗号の動向等について

資料４

量子コンピュータにおける素因数分解の評価について

資料５

量子コンピュータにおける離散対数問題の求解実験について

資料６

CRYPTREC暗号リストでの推奨候補暗号リストの取扱いについて

参考資料

電子政府における調達のために参照すべき暗号のリスト（CRYPTREC暗号リスト）

資料１

これまでの議論と本年度の検討内容について

令和３年３月３日
CRYPTREC事務局

2019年度のＴＦ検討状況（量子コンピュータ等関係）
量子コンピュータ等の技術動向
 量子コンピュータの現状の規模（量子ビット数）は50程度だが、暗号解読には数千程度以上が必要。
 量子コンピュータの性能は、量子ビット数に加えて、ノイズ（計算誤り）や演算可能回数も重要な指標。
 現状はノイズ（誤り）等の問題があり、規模だけ拡大しても暗号解読に活用できる水準ではない。
→ 現状の暗号技術が近い将来に危殆化する可能性は低い旨、2020年２月に公表・周知した。
https://www.cryptrec.go.jp/topics/cryptrec-er-0001-2019.html

耐量子計算機暗号（PQC）の技術動向
 米国NIST（国立標準技術研究所）が標準化作業中で、2022〜2024年に標準化ドラフトが策定予定。
CRYPTREC暗号リスト（電子政府推奨暗号リスト）における位置付けについて
 CRYPTREC暗号リストは、利用環境によらない安全性の評価に加え、利用実績等も考慮して作成。
 PQCは、多数の方式が提案され安全性を検討している段階で、利用実績等に言及できる段階ではない。
 今後、利用が拡大すると想定される、IoT機器等に用いられる「軽量暗号」や、暗号状態で情報処理が可能な「高機能暗号」は、利用環境やアプリケーションが限定され、従来暗号とは取り扱いが異なる。
→ PQC、軽量暗号、高機能暗号は、CRYPTREC暗号リストに組み込まず、別途ガイドラインを作成する。
（暗号技術評価委員会にて、CRYPTREC暗号リストの改定作業（2022年度末目途）と並行して実施予定）

タスクフォースの今後の取組
 量子コンピュータやPQCの状況をフォローするため、2020年度以降もタスクフォースを継続して開催。

1

2019年度のＴＦ検討状況（CRYPTREC暗号リスト関係）
CRYPTREC暗号リストの構成
 CRYPTREC暗号リストは、次の３リスト構成となっている。

①電子政府推奨暗号リスト（安全性・実装性能が確認され、利用実績や普及見込みがあると判断されたもの）②推奨候補暗号リスト（安全性・実装性能が確認され、今後①のリストに掲載される可能性のあるもの）③運用監視暗号リスト（危殆化等により推奨すべき状態ではなく、互換性維持のために継続利用を容認するもの）

 ①と③のリストは維持するものの、②のリストには掲載から十分な期間を経ても普及したとは言えない暗号技術もあり、その必要性等について、引き続き検討が必要。
 各暗号技術は十分成熟しているため、技術分類は変更せず、新たな暗号技術の公募も実施しない。
暗号技術のパラメータ CRYPTREC暗号リストでは推奨する暗号技術（暗号アルゴリズム）を示してきたが、パラメータは提示していない。
 推奨パラメータの明示は、安全なシステム構築や計画的な暗号技術の移行を促進するために有用。
→ 推奨パラメータを規定する別の文書を新たに作成する。（CRYPTREC暗号リストから当該文書を参照する構成とする。）（暗号技術活用委員会にて作成に向けた検討を実施中）

CRYPTREC暗号リストの今後の改定
 2003年に作成、2013年に改定を行い、今般、2023年目途に改定作業中であり、10年単位で改定。
 常に危殆化等の監視を行い、必要に応じた暗号技術の加除等も行っており、10年単位とする必要もない。
→ 次の改定以後は、改定後５年以内を目途に暗号技術検討会において改定是非を判断することとする。
今後に向けた取組
 CRYPTREC暗号リストの構成等について議論するため、2020年度以降もタスクフォースを継続して開催。

2

2019年度のタスクフォースの検討結果を受けた対応
暗号技術検討会(2020年度第１回)決定事項
CRYPTREC暗号リストの在り方及び暗号技術の動向等について、
次のように取り扱う。
１ 耐量子計算機暗号、軽量暗号、高機能暗号について、
CRYPTREC暗号リストには含めず、それぞれ別の文書とする。また、
当該文書の重要性がわかるよう、取りまとめたものとする。
２ 2023年目途のCRYPTREC暗号リストの改定について、現行の３リスト構成の在り方については引き続き検討することとする。また、
技術分類については現行のものを踏襲し、公募は行わない方針とする。

暗号技術評価委員会にてガイドライン作成検討中
本年度のタスクフォース
において議論３ 推奨される暗号のパラメータについて、CRYPTREC暗号リストから参照する形で別の文書としてまとめる方針とする。

暗号技術活用委員会にて該当文書作成検討中

４ １及び３に係る新たな文書も含め、CRYPTREC暗号リストを含むCRYPTRECの文書の位置付けを整理する。

該当文書の作成検討と併せて検討予定

５ 量子コンピュータや耐量子計算機暗号の状況をフォローするため、及び引き続き継続検討とした内容の議論を行うため、2020年度
以降もタスクフォースを継続設置する。

本年度のタスクフォース
において議論3

全体スケジュール（イメージ）(2019.3)
暗号リストの改定方針議論

暗号技術
検討会

★

★

改定方針

タスクフォース

量子ｺﾝﾋﾟｭｰﾀを踏まえた
暗号リストの改定方針(2019.3)
技術報告書

暗号技術 PQCの研究・評価委員会 技術動向調査(2020.3)
技術報告書
量子コンピュータによる現行の共通鍵暗号への安全性に関する調査

暗号技術
活用委員会

(2022.3?)
ガイドライン作成(P)(2020.6)
暗号リストの改定方針議論★

（前倒し可能な場合）(2023.3?)
CRYPTREC暗号リスト改定
PQCガイドライン作成(P)★

改定方針（継続検討分）量子ｺﾝﾋﾟｭｰﾀの進展等の動向確認／
暗号リストの改定方針（継続検討分）ガイドライン検討

量子コンピュータの進展等の動向確認

ガイドライン案

安全性評価結果
ガイドライン案

PQCガイドライン検討
現行暗号の安全性評価 ＋ 軽量暗号ガイドライン検討
高機能暗号ガイドライン検討

パラメータに関する文書の検討

2019

2020

NIST Round2（2019.8）
Round2結果公表

2021

2022

2023

2024

NIST Round3（2022?）
Draft Standars︖

4

量子コンピューティング最前線

伊藤公平
慶應義塾大学 理工学部
慶應義塾大学IBM Q Network Hub @ Keio ファウンダー

文科省 光・量子飛躍フラッグシッププログラム（Q-LEAP ）量子情報処理分野プログラムディレクタ (PD)JSTさきがけ「量子の状態制御と機能化」領域総括

古典コンピュータで不可能な問題
極めて大きな場合の数を含む計算
例：六本木ミッドタウンから日比谷ミッドタウンへの最適ルート探し

コンピュータで不可能な問題
量子物質の構造・反応計算や機械学習による分類分け

量子空間での直接的分類分け：非構造データの量子カーネル関数の開発

量子コンピュータの科学的可能性-

古典情報（いわゆる世間のビッグデータ）を量子状態に変換する（量子コンピュータに読み込ませる）ためには膨大な計算量が必要となる
量子力学に基づく情報（素粒子、原子、分子など）を直接量子ビットで担う（量子状態を量子状態で表す）．科学的可能性としてはそのような計算を量子ビットで実行すべき．（金融、最適化といった産業応用は別問題）

H12分子の結合長

現状の延長では…

量子ハード・ソフト協調の子育てが必要

量子コンピュータの時代？
1. Quantum Leap (Quantum Supremacy)は得られるか？
2. スパコンに勝てる日は来るか？
3. 一社に一台量子コンピュータの時代は来る？
コンピュータの性能向上
クラウド計算（セキュリティ）
古典計算
人工知能

スパコン

量子計算 準量子計算

古典計算
人工知能

スパコン

量子計算 準量子計算

超並列計算（量子並列性）
量子ビット (qubit)
0
0
0
0
1
1
1
1

0
0
1
1
0
0
1
1

2進数

0
1
0
1
0
1
0
1

0
1
2
3
4
5
6
7

10進数

2n通りの数が一気に処理できる

280量子ビット→2200~1083
宇宙の原子数！
8量子コンピュータの種類
量子コンピュータ
（別称：ゲート方式・
万能量子コンピュータ）
IBM
GoogleRigettiIntel
Ion Q
Honeywell
Microsoft
etc.

イジングマシン方式（最適化装置）
アニーリング方式

D-WaveNEC

レーザーネットワーク
方式（準量子）
国立情報学研究所とNTTチーム古典コンピュータによる量子アルゴリズム（量子ソフトウェア）の実施
シミュレータ・シミュレーション

日立 CMOSアニーラー
富士通 デジタルアニーラー
東芝 シミュレーテッド分岐アルゴリズム9超伝導量子コンピュータ
Google

引⽤︓ https://gigazine.net/news/20180307-google-new-quantum-processor/

IBM

引⽤︓https://www.technologyreview.jp/s/62657/ibm-raises-the-bar-with-a-50-qubit-quantum-computer/

Intel

Riken

引⽤︓ https://www.engadget.com/2018/01/08/
intel-s-quantum-computing-efforts-take-a-major-step-forward/

Rigetti computing

引⽤︓ https://www.rigetti.com/

Nist 2ion

Innsbruck

0.2 mmCourtesy D. Wineland, NIST

2020

シリコン量子コンピュータ

https://www.intel.com/content/www/us/en/research/quantum-computing.html

12Gate-defined
MOS spin qubits
Nature 526, 410 (2015)

光量子コンピューティング
東大 古澤明教授

Teleportation of Schrodinger’s cat
wave-packets of light
Science, 332, 330 (2011)

Continuous-variable entanglement
on a chipNature Photonics, 9, 316 (2015)

量子コンピュータ性能の発展予想
性能指標：Quantum volume
2020年の64は、2の6乗．6つの量子ビットで6段の高精度計算が可
2021年は128 (?)、 2の7乗．7つの量子ビットで7段の高精度計算が可Quantum volumeの決定方法（実際の例）
Example; find the quantum volume of a 27-qubit quantum computer
Success means >2/3 measuring success with >97.725% confidence interval)
Step 1: Try random 2-qubit circuit of depth 2, run it lots of times -> success
Step 2: Try random 3-qubit circuit of depth 3, run it lots of times -> success
Step 3: Try random 4-qubit circuit of depth 4, run it lots of times -> success
Step 4: Try random 5-qubit circuit of depth 5, run it lots of times -> success
Step 5: Try random 6-qubit circuit of depth 6, run it lots of times -> success
Step 6: Try random 7-qubit circuit of depth 7, run it lots of times -> fail

Quantum volume is 26=64

IBM Q Network Hub @ Keio University
理工学部矢上キャンパス(Keio Q Hub)

クラウド量子計算

IBMワトソン研究所(New York)

プログラム送信
計算結果

常に進化し続ける

量子ソフトウェア開発
http://research.ibm.com/ibm-q/

量子コンピュータ IBM Q 開発
18

慶應義塾大学における取り組み

19

Keio Q Hub Team の構成< 量子化学チーム >金融派生商品価格評価のIBM
Qシミュレータ・実機による検証

IBM Q 実機を用いたリチウム
空気電池の化学反応計算< 量子AIチーム >分類・回帰問題のIBM Qシミュレータ・
実機による検証

抽象量子回路と実機を結ぶソフトウエアを開発
抽象量子回路と実機を結ぶソフトウエアを開発

基盤< システムチーム< システムチーム>>

基礎・ 応用< 量子金融チーム >20

Keio Quantum AI Team：Quantum Support Vector Machine
Classification problem

Keio Q Hub 量⼦AIチームの研究成果
ü IBM⼿法の改良版を提案。
＜Keio Q Hub 量⼦AIチーム 改良⼿法＞
データセットAIチームの手法によるデータ分布の有効性をチェック
AIのKernel
計算

NEW
NO

量子空間に
エンコードする

YES

古典コンピュータ
量⼦コンピュータ
AI予測

22

IBM Q実機での分類分け
20 Qubit IBM Q
Accuracy︓0.88

Simulator
Accuracy︓1.00

23

量子創薬・生命科学イニシアチブ
慶應義塾（理工学部、医学部）+ 早稲田大学

非構造データの量子カーネル関数の開発

文科省 Q-LEAP(2018 PRISM)

24

量子化学チーム
変分型量子固有値ソルバー(VQE)による化学反応過程のシミュレーション：リチウム水素電池への応用

July 28, 2019
Li-air battery research collaboration between industry and academia goes back to
the mid-1990s, said Dr. Naoki Yamamoto, associate professor and the chair of the
Keio University Quantum Computing Center, which is part of the IBM Q Hub.
“Because both the charge and discharge process in the lithium-air battery are very
complicated and sensitive to the surrounding environment, it is still hard to elucidate
the reaction mechanism at the atomic level, which has limited the progress of thetechnology.”

Reactant

TS

Product|φ(θ)#

in Eq.
S1: goal of this problem is to obtain the ground energy of a g
The(#y)(2θ
d so as to decrease=!(Rtowardthegroundenergy.
(Ry (2θ1 ) ⊗ Ry (2θ2 ))|0# ⊗ |0#,3) ⊗ Ry (2θ4 ))Uent
energy E(θ) = !ψ(θ)|H|ψ(θ)",where|ψ(θ)" is a parameterized a変分型量子固有値ソルバー(Variational
Quantum
Eigensolver,
VQE):
unitary
operatortheH
quantum
circuitand|ψthethe initial
state
nergy
of a given
Hamiltonian
minimizing
mean
where
Uent of= |0#%0|⊗byI+|1#%1|⊗ σx thedenotes
0 " CNOTrgy of,E(θ)
a#given
Hamiltonian
H4,
byminimizing
the
mean
(
)
(
)
(
)
(
)
(
)
ameterized
ansatzstate|ψ(θ)"
=
U
(θ)|ψ
"
with
U
(θ)
./
./
4,rotation
towardthegroundenergy,typicallyby thetheoperator
ordinary gradien
gate
and
R
(θ)
denotesthesingle-qubit
=
#
⨂/
#
#
⨂/
#
(S1)
0
y
0
1
0
3
567
0
8
0
9
The
VQE
problem:tor
which
is applied
to two-qubits
theasformshown
eterized
ansatzstate|ψ(θ)"=issystem
Uupdated(θ)|ψhasUto(θ)decreasetheAnsatzstate:
0 " withdefinedbyinitialstate;
theparameterθso
The goalof this problem
is to obtain
thedecrease
ground energy of a given Ha!
itial
state;
the methodparameterθ is updated
so as to
∂E(θ)
#
"
nary
gradient
!s
(k+1)
(k)
energyE(θ)=!ψ(θ)|H|ψ(θ)",where|ψ(θ)"
isaparameterized
ansatzθ=θ−η
が小さくなるようにパラメータを更新!
エネルギー値− sin(θ/2)−iθσy /2 on cos(θ/2)
ry gradientmethod information
6;<=/8
upplementarythe
VQE
experiment
.
R
(θ)
=
e
=
∂θ
θ
y
where!/operator
the Y-rotating
single-qubit
gateinitialand ,567= |the0⟩⟨0|⨂
unitary
quantum
circuit
and
|ψ
"
the
state;
pa
0 (#) = :of the issin(θ/2)cos(θ/2)
0∂E(θ)!
! toward−∂E(θ)
ηE(θ), learning! η thethegroundenergy,typically
by|work
theordinary
gradientmeth
withcoefficient.
In
this
the
following
two-qu
!
(k)
⟩
⟩|
⟩
|
the
controlled-Z
gate.
Also
the
initial
state
is
'
=
0
1
;
the
parameters∂θθ=θa typical hardware-efficientansatz, illustrated in
VQE! for
LiOx:,This is2量子ビットでモデル化（３種のハミルトニアンすべてで）/η0 (#∂θ(S1)
8 )⨂/θ=θ
0 (#(k)
9 )4,
"
#!
"
Fig. 4.
(-)∂E(θ)= (#9 , #unitary= (0,0,0,0is),chosen:
andtheR
ansatzproce
wing #two-qubits(k+1)
U thus(θ)θ=(θθ3(k))state⊗−Rηyof(θtheU!! c−ZR
8 , #3 , #1 )operatory=4 ) VQEy,ng #two-qubits
operator
is chosen:∂θ θ=θ(k)"(-) unitary#⟩|R1y⟩.(θ
|⊗
E'(#
)F(θ=
0the
The
corresponding
Hamiltonians
for the reactant,TS, and p
blem
is
to
obtaingroundgiven
HamiltonianHbyminimizi−iθY/2energy of a
)
U
R
)
)
,
4
c−Z
y
1
2
where
R
(θ)
=
e
is
the
y-rotating
single-qubit
gate
and
Uc−
#
" single-qubit#and ,567 = |0⟩⟨0|⨂@ + |1⟩⟨1|⨂C isrotating
gateywithRηywherelearning
In this ansatz
work thefollowingH|ψ(θ)",|ψ(θ)"
iscoefficient.
parameterizedstate|ψ(θ)" two-qubits= U (θ)|ψ0 "uni
w
Uc−Z
(θthe
)⊗
Rythe
(θ2Table)initial, a S5.
1Also
ingate.
SupplementaryIn
particular,
diagonalizationof the Hamiltonianmstate
is |ψ0by"=|1"|0"; the parameters
are inegate
quantum
circuitandtheinitialstate;
parameter
θ# is updated
so (0
a
" the
"
⟩=
⟩|1|ψ
|'-=
|0ansatz
nitialstate
parameters
initialized
toand|0"!0|⊗⟩;0I"the+|1"!1|⊗Z
isare
thecontrolled-Z
c−Z
andUis
thus
the
state
of
the
VQE
procedure
begins
with
|θ
U
(θ)
=, θ controlled-Z
R
(θ(0,
R
(θ4 ) Uc−Z Ry (θ1 ) ⊗
(0)
y=
3) ⊗
y0),
energy,typicallybytheordinary
gradient
method()UGHI5),
theeigenvalues
shown
in
Eq.
S2:
ed and=|0"!0|⊗
I+|1"!1|⊗
Zisthemetersare
initialized
to
θ
=
(θ
,
θ
,
θ
)
0,
0,
c−Z
1 2 3 4), and thus
the
of
the
VQE
procedure begins with(0) ansatz state
(0)
ns
with
|θ
"
=
|1"|0".
ters areinitializedFIG.
to−iθYθ4: /2The= (θhardware-efficient(0, 0, 0,with0), 2 qubits.
1 , θ2 , θ3 , θ4 ) != ansatz
Hamiltonian:
∂E(θ)
where
R
(θ)
=
e
is
the
y-rotating
single-qubit
gate and Uc−Z = |0
!
(0) y
(k+1)
(k)
with
|θ
"
=
|1"|0".
θInvestigations= following
θ of
−TS,
η and
, Hamiltonians
nding Hamiltonians
forthereactant,
productaregiven! SuperoxideInthisthework
thetwo-qubits
are studied
Computational
theLithium
Dimer Rearrangement(k) the parameters
FIG. 5:gate.
Also
initial
state
is
|ψ
"
=
|1"|0";∂θθ=θ
(J3 , J8 , J9 , J- ) = (0.398602, 0.060722,)are
0−0.115761, −0.116459, initialize(S2
The
Fubini-Study
metric(3)
iscalculatedas(0)for J.
theo
onbyNoisy
Quantum
Devices,Q.
Gao,H. Nakamura,T. P. Gujarati,
G. O.|θJones,
andthus
theansatz
state
of
the
VQE
procedure
beginswith"=|1"
ticular,diagonalizationoftheHamiltonian
matrixofreactantarestudied.
First
thereactant
Hamiltonian
is
given
by
HRice,
=
athe
I⊗
I M.
+ Pistoia,
a1 Ztwo-qubits⊗J.ZM.+Garcia,
a2 X
⊗
XN.+
b(I
Z
efficient. In E.
this
work
following
unitary
operatoris −chosen:reac
0Wood,(θ1⊗, θ2I),θ
S. P.
andYamamoto, ⊗Z0sin(2θ
2 ) by 0
reEq.
studied.
First"the reactant1Hamiltonianisgiven
molecule
S2:
arXiv:1906.10675.
#"#
Z−
Zwhere⊗I)+a=c(IX )+XRa⊗S3:I=−Z⊗1 XR+ a
X 0⊗
Z),
(1)
Hamiltonian:0(θcos(2θ
)
⊗Eq.
and
in
0.0568,−0.0374,=
0.1351,=. 0.0471, and c
Uthe(θ)eigenstates
R⊗
(θ
)
U
(θ
)
⊗
R
(θ
0 =
1
2
y
3
y
4
c−Z
y
1
y
2 )1 b, F =}量子化学チーム：リチウム空気電池の反応解析
慶應義塾 + 三菱ケミカル + IBM
中間体の基底エネルギーの高精度計算

読取誤差補正なし あり

厳密解

IBM Q 実機を用いてリチウム空気電池の化学反応計算に成功！
27

IBM Q による実験結果

Reactant

Transition State

TS, Product の場合は、基底状態と第１励起状態のエネルギー差が大きいà ほぼ基底状態が得られた。

Product

Reactant の場合は、基底状態と第１励起状態がエネルギー縮退に近い
à 生成された状態の解析が必要

-1

10

a=1/3

量子金融チーム：高速モンテカルロ計算
10
-2

Error

慶應義塾 + みずほ + MUFG + IBM
-3

10

-4

10

 target value

asse
the

15

10

whe
nian
the

-5

10

( )

5

10

2

0

3

4

10
10
20
40
80
The
numberof 60
oracle calls

0

10
100



-1
FIG. 1.

The price of a stock in the Black-Scholes-Merton
10model behavesstochastically as a geometric Brownian mo-

-2

whe
Thi
both
unli
cost
divi

U
add
tion
equ

10

-3

10

II.

BLACK-SCHOLES-MERTON OPTIONPRICING

The Black-Scholes-Merton (BSM) model [4, 5] con-4
sidersthe pricing of financial derivatives (‘options’).
The original model assumes a single benchmark asset(‘stock’), whose price is stochastically driven by a Brownian motion, see Fig 1. In addition, it assumes a risk
free investment into a bank account (‘bond’). We follow
closely the discussion in the literature [2] in the following.

10

-5

see
The

Error

Error

( )

a=1/6

・・・

・・・

( )

tion, changing each time step according to a log-normal distribution. In the above plot, five sample price evolutions of asingle stock are plotted as a function of time. The resultant
distribution is log-normally distributed, with mean (dashedblack line) and one standard deviation (dotted red lines) illustrated. Pricing an option requires estimating the expectedvalue of a payo↵ function on the stock at various times. The
parameters are: initial price S0 = 3, drift ↵ = 0.1, and volatility= 0.25.

5

Thi
term
Let
opti
opti
stoc

Defi
opti

1. A Brownian motion W is a stochastic
10Definition
process characterized by following attributes:
2
3
4
5 whe
Figure 1: Schematic picture of the proposed amplitude estimation algorithm 1.10W = 0;
10
10
10 T
2. W is continuous;
using the maximum likelihood estimation.
the
The number of oracle callson
3. W has independent increments;t0t

基礎理論構築 & IBM Q シミュレータ・実機による検証
t

4. Wt

Ws ⇠ N (0, ts) for t > s.

deri
prob
Sim
an
rent
fram

29with mean µ andN (µ,) is the normal distribution
set of multidimensional random variables !h = (h0 , h1 , · · · , hM ) is independently
variance. Point 3 means that the random variable
Figurebetweenthenumb
W 2:WThefor t relationships> s is independent ofany previous
time!
!
random variable W , u < s. The probability measure un2

2

t

s

u

新規振幅推定アルゴリズムと金融問題への展開
振幅推定アルゴリズム --- モンテカルロ計算などで量子２乗加速を保証
従来法
グローバー
＋位相推定

…
…

補助
入力

出力

提案法
異なるグローバーアルゴリズムを並列で実行、結果を統計処理(位相推定は不要)
出力
入力

︙ ︙

︙
統計処理

(最尤推定)

Amplitude estimation without phase estimation, Y. Suzuki, S. Uno, R. Raymond,
T. Tanaka, T. Onodera and N. Yamamoto, arXiv:1904.10246

モンテカルロ積分への応用
古典計算機

70000

量子演算の回数
CX演算の回数[-]

0.1

精度(誤差)
推定誤差[-]

提案法

0.01

従来法

60000

提案法

50000
40000
30000
20000
10000
0

0.001
100

1000
Number of Oracle calls[-]10000

計算コスト(オラクルコール)
従来法と同等の性能
グラフ タイトル[実験] 減衰ラビ振動(+ 不明項) を観測

1

10
Number of Q calls[-]100

計算コスト(オラクルコール)
演算の長さを従来法に対して約95%削減

1.2

1
0.8
0.6

--- 実機に対する統計解析理論の構築が必要(進行中)

0.4
0.2
0

理論値
ポケプシー
boeblingen
1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67 70 73 76 79

量子金融チーム（暗号）：ショアアルゴリズムの実装
慶應義塾 + 東京大学 + MUFG + みずほ

ショアアルゴリズム – 素因数分解を現実的な時間で解いてしまう。
RSA暗号方式に大きな影響。

IBM Q 実機を用いて ショアアルゴリズムの実装に挑戦！
32

資料３

耐量子計算機暗号の動向等について米国NIST PQC 標準化• 2016年募集開始• 2022-2024年完了予定- 標準ドラフト公開

2017.11

世界中から
82方式 応募
書類選考

2017.122019.12020.7

69方式
Round 1
評価
26方式

7(＋α)
方式

Round 2
評価
Round 3
評価?

https://csrc.nist.gov/Projects/post-quantum-cryptography/workshops-and-timeline

2

NIST第３ラウンドの７方式（＋α）• 格子に基づく暗号 鍵交換・暗号化：CRYSTALS-KYBER、NTRU、SABER、（FrodoKEM、NTRU Prime）
 署名：CRYSTALS-DILITHIUM、FALCON• 符号に基づく暗号 鍵交換・暗号化：Classic McEliece、（BIKE、HQC）• 多変数多項式に基づく暗号 署名：Rainbow、（GeMSS）• ハッシュ関数に基づく署名
 署名：（SPHINCS+）

Finalist に昇格？

• 同種写像に基づく暗号 鍵交換・暗号化:（SIKE）• その他
 署名：（Picnic）
3

資料4

量子コンピュータにおける素因数分解の評価について
高安敦（NICT）
2021/3/3
1

量子計算機の脅威
Shorの“量子”アルゴリズム[Sho@FOCS’94]により，素因数分解・離散対数問題が理論的には多項式時間で解けることがわかった．

現代暗号への脅威
2016年2月：NISTが耐量子計算機暗号の標準化計画を発表
2017年11月：提案締め切り
2017年12月：Round 1 Algorithms発表
2019年1月：Round 2 Algorithms 発表
2020年7月：Round 3 Algorithms発表
2/9

Shorのアルゴリズムの現実的な脅威
Shorのアルゴリズムは理論的には脅威だが，実装上はこれまで小さなパラメータにしか適用できていない．
• 素因数分解15 = 3 × 5, 21 = 3 × 7• （素体・楕円曲線上）離散対数問題
2𝑥𝑥 = 1 mod 3

現実的にどれだけの脅威となるのか評価する必要がある

3/9

量子素因数分解アルゴリズムの実装動向• Shorのアルゴリズム
15 = 3 × 5, 21 = 3 × 7• 量子アニーリング
376289 = 571 × 659

S. Jiang et al. Quantum annealing for prime factorization. Scientific Reports, 2018.

• Groverのアルゴリズム
4088459 = 2017 × 2027

A. Dash et al. Exact search algorithm to factorize large biprimes and a triprime on IBM
quantum computer. arXiv: 1805.10478, 2018.

古典アルゴリズムより速いという理論的根拠があるのはShorだけ
4/9

𝑛𝑛量子ビット𝑚𝑚量子ビット（ 𝑚𝑚 = 𝑂𝑂(𝑛𝑛)）素因数分解の量子回路
𝑂𝑂(𝑛𝑛3 )量子ゲート

𝑎𝑎 𝑥𝑥 を計算
5/9

素因数分解の実装結果
研究グループ

合成数[VSB+01][LWL+07][LBYP07][PMO09][LBC+12][MLLL+12][SSV13][MNM+16][ASK19][DLQ+20]

15
15
15
15
15
21
20000ビット
15
21
15

𝑎𝑎

11, 7
4, 2
11
4
4

2, 7, 8, 11, 13
2
7, 8

量子ビット数

冪乗計算
ゲート数

7, 7
7, 5
5
5
3
1 + log 2 3
25, 5, 5, 5, 5
6
3

2, 9
2, 2
2
6
2

1
11, 15, 11, 2, 15
19
3
6/9

Shorのアルゴリズムによる素因数分解の実装結果まとめ• これまで適切に素因数分解されたと言えるのは15, 21のみで，15の素因数分解は特別に簡単• いずれの実験もなるべく簡略化した量子回路を用いており，一般的に同様の簡略化は難しそう．
• 求める位数の情報を使った実装があるが，そのような場合には任意に大きな合成数を素因数分解できるため不適切• 適切に21 = 3 × 7の素因数分解を行なった論文においても， 35 = 5 × 7の素因数分解に失敗している．
• 小さなパラメータにおいて離散対数問題の実験結果も報告されている．
 現在の量子コンピュータで暗号で用いられるような大きなパラメータ7/9の問題が解けるとは考えにくい．

素因数分解アルゴリズムの漸近的な比較（[GE19]のTABLE I）
研究グループ量子ビット数

測定の深さ[VBE96][Zal98][Bea03]

Toffoli
ゲート数

7𝑛𝑛 + 15𝑛𝑛 + 𝑂𝑂 1
2𝑛𝑛 + 380𝑛𝑛3 + 𝑂𝑂 𝑛𝑛2
600𝑛𝑛3 + 𝑂𝑂 𝑛𝑛
144𝑛𝑛3 + 𝑂𝑂 𝑛𝑛2 log 𝑛𝑛

80𝑛𝑛3 + 𝑂𝑂 𝑛𝑛2
52𝑛𝑛3 + 𝑂𝑂 𝑛𝑛2[FMMC12][HRS17][GE19]

3𝑛𝑛 + 𝑂𝑂 1
2𝑛𝑛 + 23𝑛𝑛 + 0.002𝑛𝑛 log 𝑛𝑛

40𝑛𝑛3 + 𝑂𝑂 𝑛𝑛2
52𝑛𝑛3 + 𝑂𝑂 𝑛𝑛2
500𝑛𝑛2 + 𝑛𝑛2 log 𝑛𝑛

576𝑛𝑛3 log 𝑛𝑛+ 𝑂𝑂 𝑛𝑛3 log 𝑛𝑛

40𝑛𝑛3 + 𝑂𝑂 𝑛𝑛2
64𝑛𝑛3 log 𝑛𝑛 + 𝑂𝑂 𝑛𝑛3
0.3𝑛𝑛3 + 0.0005𝑛𝑛3 log 𝑛𝑛

ゲートの分解などを行い実装に適したアルゴリズムが年々改良されている．

[GE19]: C. Gidney and M. Ekera. How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits.
8/9
arXiv:1905.09749, (2019)素因数分解アルゴリズムのパラメータごとの比較（[GE19]のTABLE I）
比較しているのは，量子ビット数（100万個）×計算時間（日）研究グループ[VBE96][Zal98][Bea03][FMMC12][HRS17][GE19]

𝑛𝑛 = 1024
240
16
32000
53
230
0.5

𝑛𝑛 = 2048
4100
250
380000
850
2800
5.9

𝑛𝑛 = 3072
23000
540
1700000
4600
13000
21

[GE19]による共通の設定：ゲート誤り率0.1%, 表面符号測定時間1マイクロ秒，
反応時間10マイクロ秒，格子結合（超伝導量子ビット）
9/9参考文献(6ページ)[ASK19] Mirko Amico et al. Experimental study of shor’s factoring algorithm using the ibm q experience.
Phys. Rev. A, 100:012305, 2019.
[DLQ+20] Zhao-Chen Duan et al. Proof-of-principle demonstration of compiled Shor ’s algorithm using aquantum dot single-photon source. Optics Express, 28:18917–18930, 2020.
[LBC+12] E. Lucero et al. Computing prime factors with a Josephson phase qubit quantum processor.
Nature Physics, 8:719–723, 2012.
[LBYP07] Chao-Yang Lu et al. Demonstration of a compiled version of Shor ’s quantum factoring algorithm
using photonic qubits. Phys. Rev. Lett., 99, 2007.
[LWL+07] B. P. Lanyon et al. Experimental demonstration of a compiled version of Shor’s algorithm withquantum entanglement. Phys. Rev. Lett., 99, 2007.
[MLLL+12] E. Martin-Lopez et al. Experimental realisation of Shor ’s quantum factoring algorithm using
qubit recycling. Nature Photon, 6:773–776, 2012.
[MNM+16] T. Monz et al. Realization of a scalable Shor algorithm. Science, 351:1068–1070, 2016.
[PMO09] A. Politi, J. C. F. Matthews, and J. L. O ’Brien. Shor ’s quantum factoring algorithm on a photonic
chip. Science, 325:1221, 2009.
[SSV13] John A. Smolin et al. Oversimplifying quantum factoring. Nature, 499:163–165, 2013.
[VSB+01] L. Vandersypen et al. Experimental realization of shor’s quantum factoring algorithm using
nuclear magnetic resonance. Nature, 414:883–887, 2001.

参考文献(8ページ)[Bea03] S. Beauregard. Circuit for shor’s algorithm using 2n + 3 qubits. Quantum Inf. Comput.,
3:175–185, 2003.

[FMMC12] Austin G. Fowler et al. Surface codes: Towards practical large-scale quantum
computation. Phys. Rev. A, 86:032324, 2012.

[GE19] C. Gidney and M. Ekera. How to factor 2048 bit RSA integers in 8 hours using 20 million
noisy qubits. arXiv preprint arXiv:1905.09749, 2019.

[HRS17] Thomas Haener et al. Factoring using 2n + 2 qubits with toffoli based modular
multiplication. Quantum Information and Computation, 18(7-8):673–684, 2017.

[VBE96] Vlatko Vedral et al. Quantum networks for elementary arithmetic operations. Phys. Rev.
A, 54:147–153, 1996.

[Zal98] Christof Zalka. Fast versions of Shor’s quantum factoring algorithm. arXiv preprint
quantum-ph/9806084, 1998.

量子コンピュータにおける離散対数問題の求解実験について

発表者：青野 良範（NICT）
mail: aono@nict.go.jp
日時：2021/03/03 CRYPTREC TF

資料５

本日の概要資料５

超電導量子回路を用いた離散対数問題の求解実験• 2020/12/11 QIT43発表[青野-Liu-田中-宇野-Van Meter-篠原-野島]• IBM Q(Melbourne, Paris)を用いた計算機実験の報告【大目標】量子計算機とショアのアルゴリズムが現在用いられているDLPベースの署名方式に与える影響の将来予測と移行時期の見積もり【報告内容】• 最新の量子計算機でどの程度の大きさのインスタンスが解けるのかの調査• 2𝑧𝑧 ≡ 1 mod 3: 解けている？ 2𝑧𝑧 ≡ 2 mod 3: 難しい• 将来予測を行うために解決すべき問題点の洗い出し• 量子計算機の性能をどう測るのか• 実験の成功（問題が解けたということ）をどう定量的に評価するのか資料５

量子コンピューの暗号解読能力量子コンピュータと暗号の危殆化
いつ頃暗号が解けるのかを知りたい
現在使われている暗号を解くために
十分な能力

★

西暦

2021(Now)
移行期間
このあたりから移行準備したい暗号移行モデル[Mosca, 2015]

機密保護期間

移行開始時期を逆算

余裕期間

資料５

【ターゲット】有限体F𝑝𝑝 上の離散対数問題(DLP; Discrete
Logarithm Problem)
素数𝑝𝑝と自然数𝑔𝑔, 𝑎𝑎 ≤ 𝑝𝑝 − 1に対して
𝑔𝑔 𝑧𝑧 ≡ 𝑎𝑎 (mod 𝑝𝑝)を満たす自然数𝑧𝑧を求めよ• 素因数分解問題に関しては、多くの実験データが存在（[Vandersypen et al.2001]～[Monz et al.2016]）• 離散対数問題に関しては実験データが無い【方針】インスタンスを表す三つ組み(𝑔𝑔, 𝑎𝑎, 𝑝𝑝)に対して、関数𝐹𝐹 𝑥𝑥, 𝑦𝑦 = 𝑔𝑔 𝑥𝑥 𝑎𝑎−𝑦𝑦 mod 𝑝𝑝は周期 𝑧𝑧, 1 , (𝑝𝑝, 0)を持つため、それらを位相推定を用いて発見すると、問題の解zが導かれる(𝑧𝑧, 1)(𝑝𝑝, 0)F(x,y)の値を濃淡によって表現した図資料５【量子回路設計】標準的なShorのアルゴリズムを用いる• 最も複雑（コストが高い）のが中央のべき乗回路• 素因数分解の先行研究[Monz et al.2016]と同様の簡略化を行う• p=3,7におけるmod 計算のシフト演算への置き換え等の論理回路レベルでの簡略化• IBM Qのトポロジーに合わせた実行レベル簡略化• 現行の量子デバイスでは簡略化無しの動作は困難[大西et al.,
QIT41]

【測定結果からの解の取り出し】

資料５• QFTの結果を複数回測定し、後処理アルゴリズムPPを用いてDLPの解zを復元
𝑑𝑑𝑥𝑥 ∈ 𝐙𝐙

𝑑𝑑𝑦𝑦 ∈ 𝐙𝐙• 量子回路でDLPが解ける：

𝐹𝐹 𝑥𝑥, 𝑦𝑦 の周期 𝑧𝑧, 1 , (𝑝𝑝, 0)が張る格子の双対格子の点の近似が高確率で得られる

Pr[PP(𝑜𝑜1 , … , 𝑜𝑜𝐾𝐾 )→ 𝑧𝑧]が大きい• （論文内での）計算機実験成功の定義：
𝐷𝐷𝐾𝐾𝐾𝐾 (𝐷𝐷𝐷𝐷𝐷𝐷𝐷𝐷𝐷𝐷𝐷𝐷||𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼) が小さい
実際にはランダムノイズとのダイバージェンスを大小比較

実験のターゲットと回路

資料５• Qiskitフレームワークを用いて構成• qubits数を決めるパラメータ𝑛𝑛𝑥𝑥 , 𝑛𝑛𝑦𝑦 を導入#qubits𝑛𝑛𝑥𝑥 qubit

𝑛𝑛𝑦𝑦 qubit
DLP bits• 𝑁𝑁𝐿𝐿 : circuit.size()の出力（論理ゲート数のカウント）の順にインスタンスI,II,…,VIと名付ける• 𝑁𝑁𝑔𝑔 : ゲートセットを{c1,c2,c3,cx}のみに制限したときのゲート数カウント

実験デバイス• ibmq_16_melbourne• 2018年リリース• QV=8• Connectivity:〇• Error rate:△• ibmq_paris• 2020年リリース• QV=32• Connectivity:△• Error rate:〇

資料５

実験結果
•

II

資料５

Paris, Melbourne,シミュレーターの出力分布比較(n=8192)
Paris ≈
シミュレーター
Melborune??

III
Paris,Melborune
ある程度近い？

IV
Paris,Melborune
ほぼランダムノイズ

実験結果の解釈(KL-divergence)
KL-div. 𝐷𝐷(𝑝𝑝dev ||𝑞𝑞)• Kullback-Leibler divergenceの比較：

資料５

•
•
•
•

I: Melbourune,Parisともに良い出力
II: Parisはそれなりに良い出力
III: KL-div.の観点からはランダムに近い
IV以降: ランダムノイズ■Shorアルゴリズムを用いてDLPを解く際の「成功」に関して合意が得られている定義は無いが，ParisのKL-div.の比較からI,IIに関しては良い出力が得られていると考えられる

解読能力の伸びの予測

資料５× 計算問題ではなく、デバイスの評価
× For modest size (m 50)

m=#qubits• Quantum Volume[Cross et al. ]はわかりやすいが注意が必要〇[Cross et al. ]≈ 2 𝑚𝑚𝑚𝑚 [Metwalli et al. ]〇 1年間で2倍になる（少し前のIBM Roadmap）

d=Depth

• 暗号評価に必要なqubits数は数千以上• 2n+2 qubit 素因数分解回路[高橋-國廣2006] [Häner et al.2017]に
n=2048を代入すると4098qubit必要• 離散対数を考えても同様の規模【今後の方針】QVほど汎用的な基準ではなくても良いので、暗号の予測ができるものが欲しい

資料６

CRYPTREC暗号リストでの推奨候補暗号リストの取扱いについて

令和３年３月３日
CRYPTREC事務局

論点︓リスト構成（推奨候補暗号リスト）について①
CRYPTREC暗号リストは、①電子政府推奨暗号リスト ※１ ②推奨候補暗号リスト ※２③運用監視暗号リスト※３ の３リスト構成となっており、この構成を維持すべきか。
※１ CRYPTRECにより安全性及び実装性能が確認された暗号技術について、市場における利用実績が十分であるか今後の普及が見込まれると判断され、当該技術の利用を推奨するもののリスト。
※２ CRYPTRECにより安全性及び実装性能が確認され、今後、電子政府推奨暗号リストに掲載される可能性のある暗号技術のリスト。
※３ 実際に解読されるリスクが高まるなど、推奨すべき状態ではなくなったとCRYPTRECにより確認された暗号技術のうち、互換性維持のために継続利用を容認するもののリスト。互換性維持以外の目的での利用は推奨しない。

 昨年度、「②推奨候補暗号リスト」については、次の点から引き続き継続検討することとされた。
• 現行リスト改定の際に「②推奨候補暗号リスト」を含めた３リスト構成としたのは、国産暗号技術の普及展開を促進することもその目的の一つ※であるが、３リスト構成とした意図が十分に活用されている状況とは言いがたい。
※2011年度第1回暗号技術検討会資料3-2• 一方、 「②推奨候補暗号リスト」は、（利用実績等が十分でないものの）安全性及び実装性能が確認されていることから、将来的に「①電子政府推奨暗号リスト」に載る可能性がある暗号アルゴリズムの受け皿としての機能もある。
• 現状の「②推奨候補暗号リスト」には、将来的に普及することが予想され「①電子政府推奨暗号リスト」に載る可能性がある暗号技術と、掲載から十分な期間を経てもあまり普及したとは言えない暗号技術とが混在している。
• 「②推奨候補暗号リスト」から暗号技術を削除する際の基準や手続きが定まっていない。
1

論点︓リスト構成（推奨候補暗号リスト）について②
 「①電子政府推奨暗号リスト」に掲載される暗号技術は、複数の利用実績等があるものが選定されており、市場からの製品調達に当たって選択性が確保されているという観点がある。
 「②推奨候補暗号リスト」は、利用実績等が十分確認できていないものの、安全性及び実装
性能を確認したものであることから、調達状況によっては有用な場合も考えられる。
 また、利用実績等の調査については、調査工数が大きく容易にできるものではないことを鑑みれば、予見可能性を高める観点からも、「①電子政府推奨暗号リスト」の予備軍として「②推奨候補暗号リスト」があることは有意義と考えられる。
→ 以上から、 「②推奨候補暗号リスト」は維持することとしてよいのではないか。
 一方で、「②推奨候補暗号リスト」は、｢「①電子政府推奨暗号リスト」に掲載される可能性のある暗号技術｣とされているが、長年掲載され続けている（利用実績等がない）ものもある。
 「②推奨候補暗号リスト」に掲載されている以上は、暗号技術の安全性に関する継続的な監視活動や再評価が必要となる。
 今後、耐量子計算機暗号（PQC）や、軽量暗号、高機能暗号に関する評価・検討活動が必要となることから、活動リソースの最適化が必要。
→ 以上から、 「②推奨候補暗号リスト」からの移行ルールを明確化すべきではないか。
2

論点︓リスト構成（推奨候補暗号リスト）について③①電子政府推奨暗号リスト
次の条件のいずれかを満たすと暗号技術検討会が決定した場合
1. ５年ごとの利用実績調査により、複数の利用実績を確認した場合
2. その他、普及していることが明らかな場合

安全性維持が困難（危殆化した）と
暗号技術検討会が決定した場合※電子政府推奨暗号リストに掲載された暗号技術は、利用者がいる前提であり、原則として、危殆化以外の理由
では遷移させず、また、移行のための時間を確保する必要があるため、いきなりリストから削除することはしない。

標準化等により将来的な利用が見込まれ、安全性や実装性能が十分にあると②推奨候補暗号リスト
暗号技術検討会が決定した場合（公募や事務局提案等）

CRYPTREC暗号リストへの掲載から20年を超えた後に実施する最初の利用実績調査までに、十分な利用実績を確認できなかったもの③運用監視暗号リスト

安全性維持が困難(危殆化した)と判断した場合※暗号アルゴリズムの設計寿命は20年程度以上であることが期待されているが、実際にはセキュリティ向上のため、DES→TDES→AESの世代交代や公開鍵暗号の鍵長変更が20年程度で行われていることを踏まえると、20年超後に電子政府推奨暗号リストとなり活用される見込みが低い※利用実績調査の具体的な実施内容
・評価基準については、暗号技術活用
委員会において検討し、暗号技術検討会の承認を経た上で実施する。

2019年度暗号技術検討会で決定
次の条件のいずれかを満たすと暗号技術検討会が決定した場合、削除猶予期間を定めて周知を行った上で、その期間の満了後に自動的に削除する。
1. 運用監視暗号リストに掲載している注釈で示した互換性維持のための利用形態が必要なくなり、削除が妥当と判断した場合
2. 互換性維持の継続利用として使うにしても安全性維持が極めて困難で、互換性維持の継続利用が容認できないと判断した場合
3. その他、運用監視暗号リストに掲載している必要性の根拠を満たさなくなったと判断した場合

リストから削除3

（参考）統一基準群における記載状況＜参考：政府機関等の対策基準策定のためのガイドライン（平成30年度版）（平成30年7月25日 内閣官房 内閣サイバーセキュリ
ティセンター）＞
6.1.5 暗号・電子署名＜遵守事項＞(1) 暗号化機能・電子署名機能の導入(b) 情報システムセキュリティ責任者は、暗号技術検討会及び関連委員会（CRYPTREC）により安全性及び実装性能が確認された「電子政府推奨暗号リスト」を参照した上で、情報システムで使用する暗号及び電子署名のアルゴリズム並びにそれを利用した安全なプロトコル及びその運用方法について、以下の事項を含めて定めること。
(ア) 職員等が暗号化及び電子署名に対して使用するアルゴリズム及びそれを利用した安全なプロトコルについて、「電子政府推奨暗号リスト」に記載された暗号化及び電子署名のアルゴリズムが使用可能な場合には、それを使用させること。
(イ) 情報システムの新規構築又は更新に伴い、暗号化又は電子署名を導入する場合には、やむを得ない場合を除き、「電子政府推奨暗号リスト」に記載されたアルゴリズム及びそれを利用した安全なプロトコルを採用すること。
(ウ) 暗号化及び電子署名に使用するアルゴリズムが危殆化した場合又はそれを利用した安全なプロトコルに脆弱性が確認された場合を想定した緊急対応手順を定めること。
(エ) 暗号化された情報の復号又は電子署名の付与に用いる鍵について、管理手順を定めること。
（解説）
遵守事項6.1.5(1)(b)(イ)「やむを得ない場合」について
情報システムの新規構築又は更新に伴い、暗号化又は電子署名を導入する場合においては、「電子政府推奨暗号リスト」に記載されたアルゴリズムを採用することが原則であるが、連携する他の情報システム側で対応していないなどの場合も想定される。このような場合においては、「電子政府推奨暗号リスト」に記載されたアルゴリズム以外のものを採用することもやむを得ないと考えられるが、「推奨候補暗号リスト」や「運用監視暗号リスト」を参照の上、安全性が高いアルゴリズムを採用することが必要である。

4

CRYPTREC LS-0001-2012R5

電子政府における調達のために参照すべき暗号のリスト（CRYPTREC暗号リスト）
平成25年３月１日
総務省・経済産業省（最終更新：令和２年12月21日）

電子政府推奨暗号リスト
暗号技術検討会1 及び関連委員会（以下、「CRYPTREC」という。）により安全性及び実装性能が確認された暗号技術2について、市場における利用実績が十分であるか今後の普及が見込まれると判断され、当該技術の利用を推奨するもののリスト。
技術分類

暗号技術
DSA
ECDSA

署名

RSA-PSS（注１）
RSASSA-PKCS1-v1_5（注１）

公開鍵暗号

RSA-OAEP（注１）
DH

守秘
鍵共有
64ビットブロック暗号
共通鍵暗号

（注２）

128ビットブロック暗号

ECDH
該当なし
AES
Camellia
KCipher-2

ストリーム暗号

SHA-256
SHA-384

ハッシュ関数

SHA-512
CBC
CFB
CTR
OFB

秘匿モード
暗号利用モード
認証付き秘匿モード（注13）

CCM
GCM（注４）
CMAC
HMAC

メッセージ認証コード
認証暗号

該当なし
ISO/IEC 9798-2
ISO/IEC 9798-3

エンティティ認証1

総務省サイバーセキュリティ統括官及び経済産業省商務情報政策局長が有識者の参集を求め、暗号技術の普及による情報
セキュリティ対策の推進を図る観点から、専門家による意見等を聴取することにより、総務省及び経済産業省における施策の検討に資することを目的として開催。
2
暗号利用モード、メッセージ認証コード、エンティティ認証は、他の技術分類の暗号技術と組み合わせて利用することとされているが、その場合、CRYPTREC暗号リストに掲載されたいずれかの暗号技術と組み合わせること。

1

（注１）

「政府機関の情報システムにおいて使用されている暗号アルゴリズムSHA-1及び
RSA1024に係る移行指針」（平成20年４月情報セキュリティ政策会議決定、平成24年 10 月 情 報 セ キ ュ リ テ ィ 対 策 推 進 会 議 改 定 ） を 踏 ま え て 利 用 す る こ と 。
https://www.nisc.go.jp/active/general/pdf/angou_ikoushishin.pdf（平成25年３月１日現在）（注２）

CRYPTREC暗号リストにおいて、64ビットブロック暗号により、同一の鍵を用いて暗号化する場合、220ブロックまで、同一の鍵を用いてCMACでメッセージ認証コードを生成する場合、221ブロックまでとする。

（注４）

初期化ベクトル長は96ビットを推奨する。

（注13）

CRYPTREC暗号リスト掲載のブロック暗号を、認証付き秘匿モードと組み合わせて、「認証暗号」として使うことができる。

2

推奨候補暗号リスト
CRYPTRECにより安全性及び実装性能が確認され、今後、電子政府推奨暗号リス
トに掲載される可能性のある暗号技術3のリスト。
技術分類
公開鍵暗号

共通鍵暗号

暗号技術

署名
守秘

該当なし
該当なし

鍵共有

PSEC-KEM（注５）
CIPHERUNICORN-E

64ビットブロック暗号（注６）

Hierocrypt-L1
MISTY1CIPHERUNICORN-A
CLEFIA
Hierocrypt-3

128ビットブロック暗号

SC2000
Enocoro-128v2
ストリーム暗号MUGI
MULTI-S01（注７）SHA-512/256
SHA3-256
SHA3-384

ハッシュ関数

暗号利用モード

SHA3-512SHAKE128（注12）
秘匿モード
認証付き秘匿モード（注14）

SHAKE256（注12）
XTS（注17）
該当なし

メッセージ認証コード
認証暗号

PC-MAC-AES
ChaCha20-Poly1305

エンティティ認証

ISO/IEC 9798-4（注５）

KEM (Key Encapsulating Mechanism) – DEM (Data Encapsulating Mechanism) 構成
における利用を前提とする。

（注６）

CRYPTREC暗号リストにおいて、64ビットブロック暗号により、同一の鍵を用いて暗号化する場合、220ブロックまで、同一の鍵を用いてCMACでメッセージ認証コードを生成する場合、221ブロックまでとする。

（注７）

平文サイズは64ビットの倍数に限る。

（注12） ハッシュ長は256ビット以上とすること。
（注14）

CRYPTREC暗号リスト掲載のブロック暗号を、認証付き秘匿モードと組み合わせて、「認証暗号」として使うことができる。

（注17）

ブロック暗号には、CRYPTREC暗号リスト掲載128ビットブロック暗号を使う。利用用
途はストレージデバイスの暗号化に限り、実装方法はNIST SP800-38Eに従うこと。

3

暗号利用モード、メッセージ認証コード、エンティティ認証は、他の技術分類の暗号技術と組み合わせて利用することとされているが、その場合、CRYPTREC暗号リストに掲載されたいずれかの暗号技術と組み合わせること。

3

運用監視暗号リスト
実際に解読されるリスクが高まるなど、推奨すべき状態ではなくなったと
CRYPTRECにより確認された暗号技術4のうち、互換性維持のために継続利用を容認するもののリスト。互換性維持以外の目的での利用は推奨しない。
技術分類

暗号技術

署名

該当なし

公開鍵暗号

守秘
鍵共有
64ビットブロック暗号（注15）

RSAES-PKCS1-v1_5（注８）（注９）
該当なし
3-key Triple DES

共通鍵暗号

128ビットブロック暗号
ストリーム暗号

該当なし
128-bit RC4（注10）

ハッシュ関数RIPEMD-160
SHA-1（注８）

秘匿モード
認証付き秘匿モード（注16）メッセージ認証コード

該当なし
該当なし
CBC-MAC（注11）

認証暗号
エンティティ認証

該当なし
該当なし

暗号利用モード（注８）「政府機関の情報システムにおいて使用されている暗号アルゴリズムSHA-1及び
RSA1024に係る移行指針」（平成20年４月 情報セキュリティ政策会議決定、平成24年 10 月 情 報 セ キ ュ リ テ ィ 対 策 推 進 会 議 改 定 ） を 踏 ま え て 利 用 す る こ と 。
https://www.nisc.go.jp/active/general/pdf/angou_ikoushishin.pdf（平成25年３月１日現在）（注９）

TLS 1.0, 1.1, 1.2で利用実績があることから当面の利用を認める。

（注10） 互換性維持のために継続利用をこれまで容認してきたが、今後は極力利用すべきでない。TLSでの利用を含め、電子政府推奨暗号リストに記載された暗号技術への移行を速やかに検討すること。
（注11）

安全性の観点から、メッセージ長を固定して利用すべきである。

（注15）

CRYPTREC暗号リストにおいて、64ビットブロック暗号により、同一の鍵を用いて暗号化する場合、220ブロックまで、同一の鍵を用いてCMACでメッセージ認証コードを生成する場合、221ブロックまでとする。

（注16）

CRYPTREC暗号リスト掲載のブロック暗号を、認証付き秘匿モードと組み合わせて、「認証暗号」として使うことができる。

4

暗号利用モード、メッセージ認証コード、エンティティ認証は、他の技術分類の暗号技術と組み合わせて利用することとされているが、その場合、CRYPTREC暗号リストに掲載されたいずれかの暗号技術と組み合わせること。

4

変更履歴情報
変更日付
変更箇所
平成27年 （注10）３月27日

変更前の記述変更後の記述128-bit RC4は、SSL（TLS1.0 互換性維持のために継続利用を以上）に限定して利用するこ これまで容認してきたが、今後は極力利用すべきでない。SSL/TLSと。
での利用を含め、電子政府推奨暗号リストに記載された暗号技術への移行を速やかに検討すること。
SHA-512/256
平成28年 推奨候補暗号リスト 該当なし
SHA3-256
３月29日 (技術分類：ハッシュ
SHA3-384
関数)
SHA3-512SHAKE256（注12）（注12）[新規追加]
ハッシュ長は256ビット以上とすること。
SHA-512/256
平成29年 推奨候補暗号リスト SHA-512/256
SHA3-256
３月30日 （技術分類：ハッシュ SHA3-256
SHA3-384
SHA3-384
関数）
SHA3-512
SHA3-512（注12）
SHAKE256SHAKE128（注12）
SHAKE256（注12）
平成30年 （注２）より長いブロック長の暗号が CRYPTREC暗号リストにおいて、３月29日 （注６）
利用できるのであれば、128 64ビットブロック暗号により、同一ビットブロック暗号を選択する の鍵を用いて暗号化する場合、220
ことが望ましい。
ブロックまで、同一の鍵を用いてCMACでメッセージ認証コードを生（注15）[新規追加]
成する場合、221 ブロックまでとする。
電子政府推奨暗号リ 3-key Triple DES（注３）
該当なし
スト（技術分類：共通
鍵暗号）
（注３）
3-key Triple DESは、以下の [削除]条件を考慮し、当面の利用を認める。
１） NIST SP 800-67として規定されていること。
２） デファクトスタンダードとしての位置を保っていること。
3-Key Triple DES（注１５）
運用監視暗号リスト 該当なし
（技術分類：共通鍵
暗号）
電子政府推奨暗号リ [技術分類の新設]
技術分類：認証暗号
スト
暗号技術：該当なし
推奨候補暗号リスト
技術分類：認証暗号
暗号技術：ChaCha20-Poly1305
運用監視暗号リスト
技術分類：認証暗号
暗号技術：該当なし

5

（注13）（注14）（注16）[新規追加]CRYPTREC暗号リスト掲載のブロ
ック暗号を、認証付き秘匿モードと組み合わせて、「認証暗号」として使うことができる。
暗号技術

電子政府推奨暗号リ 名称
スト（見出し）推奨候補暗号リスト（見出し）
運用監視暗号リスト（見出し）
令 和 ２ 年 推奨候補暗号リスト 該当なし
12月21日 （ 技 術 分 類 ： 暗 号 利
用 モ ー ド 秘匿 モ ード）（注17）[新規追加]

XTS（注17）

ブロック暗号には、CRYPTREC暗号リスト掲載128ビットブロック暗号を使う。利用用途はストレージデバ
イスの暗号化に限り、実装方法はNIST SP800-38Eに従うこと。

6