多変数多項式暗号入門
中村 周平（茨城大学）

第 6 回情報数理セミナー @ 呉工業高等専門学校
２０２ 4 年 1 月 6 日

2024.1.6
Shuhei Nakamura

暗号と数学問題例:
やり取りしている相手は本物なのか ?

本物にしかできないことをみせてもらう！

(cf.https://ja.wikipedia.org/wiki/Transport_Layer_Security)

本物にしか解けない困難な数学問題を出題

検証2024.1.6

解答

Shuhei Nakamura

公開鍵暗号
・ RSA 暗号

数学問題

・ EC 暗号・素因数分解問題
・離散対数問題

安全性

困難性
2

量子計算機を利用した情報社会

量子計算機の急速な開発
主な対応：① 耐量子計算機暗号

現在の我々の情報社会
情報セキュリティ
暗号（公開鍵暗号）
危殆化

・ RSA 暗号・ EC 暗号

耐量子計算機暗号

困難な数学問題 … 安全性の根拠
多項式時間での求解可能

・素因数分解問題
・離散対数問題① 耐量子計算機暗号

量子計算機でも求解困難

・格子暗号
・符号暗号・最短ベクトル問題
・復号問題

・ハッシュ暗号・ハッシュ関数衝突問題

・多変数暗号・同種暗号

2024.1.6② 量子暗号（量子鍵配送）

・連立代数方程式問題
・同種写像問題

Shuhei Nakamura

3

NIST （米国標準技術研究所）による耐量子計算機暗号標準化プロジェクト
これまでの経過2016: 公募開始
2017: Round 1 の候補発表
2019: Round 2 の候補発表
2020: Round 3 の最終候補
代替候補

暗号化 署名82 件 = 59 + 23
69 件 = 48 + 21
26 件 = 17 + 9
7件 = 4+3
8件 = 5+32022:
・格子暗号・ Hash 暗号の標準化を決定
・残りの暗号化方式は引き続き Round 4 へ・署名方式の追加プロセスを 2023 年から開始(cf. https://csrc.nist.gov/projects/post-quantum-cryptography)

耐量子計算機暗号標準化プロセス : 2022 年度標準化決定方式
Type

PKE/KEM

格子暗号

CRYSTALS-Kyber

Signature
CRYSTALS-Dilithum, FALCON

Hash 暗号SPHINCS+

2024.1.6

Shuhei Nakamura

4耐量子計算機暗号標準化プロセス : Round 4
Type

PKE/KEM

符号暗号

BIKE, Classical McEliece, HQC

同種暗号

SIKE

耐量子計算機暗号 追加署名方式プロセス : Round 1 (40 件 , 2023.7.1)
Type符号暗号

Signature
Enhanced pqsigRM, FuLeeca, LESS, MEDS, Wave

同種暗号

SQIsign

格子暗号
MPC 系
多変数系

EagleSign, EHTv3 and EHTv4, HAETAE, HAWK, HuFu, Raccoon,SQUIRRELSCROSS, MIRA, MiRitH, MQOM, Biscuit, PERK, RYDE, SDitH
3WISE, DME‐Sign, HPPC, MAYO, PROV, QR‐UOV, SNOVA, TUOV,UOV, VOX

共通鍵系

AIMer, Ascon‐Sign, FAEST, SPHINCS‐alpha

その他

ALTEQ, eMLE‐Sig 2.0, KAZ‐SIGN, Preon, Xifrat1‐Sign.I

2024.1.6

Shuhei Nakamura

5※ D. Moody, The onramp submissions, In response to NIST’s call for
additional digital signatures, NIST PQC Seminars, 2023.6.9
2024.1.6

Shuhei Nakamura

6

MPKC ( 多変数公開鍵暗号 )名称・多変数暗号 , 多変数多項式暗号 , 多変数公開鍵暗号
・ Multivariate cryptograrphy, Multivariate public key cryptography (MPKC),MQ-based cryptography
主な特徴・メリット… 短い署名長の実現 , 高速な検証の実現

・デメリット… 公開鍵サイズの大きさ
種類

UOV 系 (e.g. Rainbow), HFE 系 (e.g. GeMSS), One-way 系 (e.g. MQDSS)
その他 (e.g. TTS, ABC)
トラップドア型
線型写像

2024.1.6

中心写像

線型写像

Shuhei Nakamura

7

MPKC の簡単な歴史
NIST PQC
標準化プロジェクト
1st Round(2017~) 11 candidates

2nd Round(2019~)

3rd Round(2020~)

トラップドア系
PatarinOV (1997)
Kipnis,Shamir
1998

Kipnis,Patarin,
UOV (1999)
GoubinLUOV

One-Way 系

Matsumoto, Imai

C* (1988)

PatarinRainbow
Rainbow
Beullens 2020, 2022

Patarin1995HFE (1996)5-pass SHH ID

GeMSS (HFEv-)

MQDSS

GeMSS

Tao, Petzoldt, Ding 2020

直近の状況

・ NIST PQC 第 3 ラウンドまで Rainbow (UOV 系 ), GeMSS (HFE 系 ) が署名方式として残いたが , 2019
年の Bardet et al. によるランク符号暗号への Support Minors MinRank 攻撃が , Rainbow や GeMSS にも改良して適用でき , 致命的な攻撃であることが知られるようになった .
・一般に UOV は Rainbow より構造を持たないため安全性においてよいことが知られているが , 標準化プ
ロジェクトではプレーンな UOV が提案されていなかった .

2024.1.6

Shuhei Nakamura

8耐量子計算機暗号 追加署名方式プロセス : Round 1 (40 件 , 2023.7.1)
Type
符号暗号

Signature
Enhanced pqsigRM, FuLeeca, LESS, MEDS, Wave

同種暗号

SQIsign

格子暗号
MPC 系
多変数系

EagleSign, EHTv3 and EHTv4, HAETAE, HAWK, HuFu, Raccoon,SQUIRRELSCROSS, MIRA, MiRitH, MQOM, Biscuit, PERK, RYDE, SDitH
3WISE, DME‐Sign, HPPC, MAYO, PROV, QR‐UOV, SNOVA, TUOV,UOV, VOX

共通鍵系

AIMer, Ascon‐Sign, FAEST, SPHINCS‐alpha

その他

ALTEQ, eMLE‐Sig 2.0, KAZ‐SIGN, Preon, Xifrat1‐Sign.I※ UOV 系

2024.1.6

Shuhei Nakamura※ HFE 系

※ Other9現行署名 , 標準化決定署名との比較：（ SL1,SL2 での鍵サイズ , 署名サイズ）
SPHINCS+SPHINCS+
Dilithium (SL2) MAYO
SNOVA

Falcon (SL1)QR-UOV

RSA

UOV

EdDSA

cf. PQShield Post-Quantum signatures zoo (https://pqshield.github.io/nist-sigs-zoo/)

Falcon 512 (pk: 897 B, sig: 666 B)
Dilithium (pk: 1,312 B, sig: 2,420 B)
RSA 2048 (pk: 272 B, pk: 256 B)
EdDSA Ed25519 (pk: 32 B, sig: 64 B)
2024.1.6

UOV Is-pkc (pk: 66,576 B, sig: 96 B)
UOV Is-classic (pk: 412,160 B, sig: 96 B)
QR-UOV I (pk: 23,657 B, sig: 157 B)
MAYO1 (pk: 1,068 B, sig: 321 B)
SNOVA 24 (pk: 1,016 B, sig: 248 B)

Shuhei Nakamura

102024.1.6

cf. PQShield Post-Quantum signatures zoo (https://pqshield.github.io/nist-sigs-zoo/)
Shuhei Nakamura
11

MPKC ：多項式写像
多項式写像

多項式写像

主なクラス1)（斉次）一次写像2)（斉次）二次写像※ 本講演では簡単のため , 斉次多項式により定められた多項式写像のみを考える .
また , ベクトルは行ベクトルによる表記とする .
2024.1.6

Shuhei Nakamura

12多項式写像の合成

2024.1.6

Shuhei Nakamura

13

MPKC … 多変数多項式公開鍵暗号は主に次の 3 つのアルゴリズムからなる .
① 写像生成（鍵生成）全単射一次多項式写像
次を満たす二次多項式写像（中心写像）
・ “逆像元計算容易”

秘密鍵

・ “ほとんど全射” ( 署名方式 ) or “ ほとんど単射” ( 暗号化方式 )公開鍵② 逆像元計算（署名生成／復号）③ 代入計算（署名検証／暗号化）

2024.1.6

Shuhei Nakamura

14

MPKC ：署名方式
例：署名を用いて公開鍵の持ち主かどうか検証する
公開鍵やり取りしている相手は

① 鍵生成

秘密鍵

公開鍵 P の持ち主本人か ?

文書② 署名生成署名③ 検証

2024.1.6

Shuhei Nakamura

15

MPKC ：直接攻撃

公開鍵※ 公開鍵を持つ本人と思わせる .

★ 公開鍵の作成者本人 (= 秘密鍵を知る者 ) のみが , 公開鍵の署名が作れるようにすることが要求される . つまり , 次の問題が困難であることが要求される .
署名偽造

2024.1.6

Shuhei Nakamura

16

MPKC ： 暗号化方式
例：相手に秘匿な情報を暗号化して送る

公開鍵

① 鍵生成

秘密鍵

平文
③ 暗号化
暗号文
② 復号

2024.1.6

Shuhei Nakamura

17

MPKC ：直接攻撃※ 秘匿された文を読むことができる★ 公開鍵の作成者本人 (= 秘密鍵を知る者 ) のみが , 暗号文から平文が作れるようにすることが要求される . つまり , 次の問題が困難であることが要求される .
暗号文解読2024.1.6

Shuhei Nakamura

18

MPKC ：直接攻撃
直接攻撃（署名偽造＆暗号文解読）

連立二次方程式問題（ＭＱ問題）★ 多変数多項式暗号の安全性はMQ 問題に依存している
2024.1.6

Shuhei Nakamura

19

MQ 問題・より正確に言えば MQ 問題には次の 3 つのタイプがある :1) 判定型 : 解を持つか判定する .
2) 探索型 : 解があれば一つ返す .
3) 決定型 : 解を全て求める .
・連立代数方程式問題を MP(Multivariate Polynomial) 問題としばしば呼ぶ .
・ MP 問題は “次数簡約操作” により MQ 問題へ帰着することができる .

・ MP 問題は NP 完全である . 特に MQ 問題も NP 完全である .
3-SAT 問題

2024.1.6

MP 問題

Shuhei Nakamura

MQ 問題

20

MPKC ：行列表示と鍵サイズ一次写像の場合
対応行列二次写像の場合

2024.1.6

対応行列 ※ 奇標数の場合

Shuhei Nakamura21合成写像写像の場合

対応行列関係

公開鍵サイズ：
秘密鍵サイズ：2024.1.6

Shuhei Nakamura

22