多変数署名方式とその安全性解析について
池松 泰彦(九州大学マス・フォア・インダストリ研究所)
情報数理セミナー@⽇⼤
2024年8月21日
1

概要

2/11

ü 多変数多項式問題を使った暗号技術がある(MPKC)ü UOVが昔から⽣き残っている⽅式として知られている
ü アメリカの標準化コンペにおいてUOVが注⽬を集めている
ü UOVは署名⻑が短く・処理効率が良い

解説内容• MPKC、特にUOVを解説• 安全性解析について時間が許す限り説明§1 研究背景
n 暗号理論3/11
メリットたくさん

公開鍵暗号基盤
RSA暗号(1978)
楕円曲線暗号(1985)

量⼦計算機の出現
Shorのアルゴリズム

耐量⼦計算機暗号(Post-Quantum Cryptography)n いつまでに︖
ü ⼤規模量⼦計算機の開発にはまだまだ時間はかかると予想されている
ü しかし暗号の変更・移⾏はかなりの労⼒・期間を要する
ü さらに今ある暗号⽂が量⼦計算機開発後に解読される可能性もü そのため、PQCの開発は喫緊の課題である

§2 NIST PQC標準化計画

4/11• デジタル署名，公開鍵暗号，鍵共有の3つの暗号アルゴリズムを選定し標準化するための(アメリカの)プロジェクト
PQC研究が活発に

2016

NIST PQC 標準化計画
標準化4方式
発表

82件

69件

26件

15件

公募開始

Round 1Round 2Round 3

2017
IBM Q
公開201820192020

Google量子超越性発表

2021

Round 4

2022

2023

署名追加公募も新たにスタート

NIST・・・National Institute of Standards and Technology (アメリカ国⽴標準技術研究所)
https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization

2024
Round 140件

§3 PQCの研究

5/11

n PQCには素因数分解、離散対数以外の数学問題が使われる•

格⼦問題・・・格⼦の最短ベクトル、最近ベクトル探索•符号問題・・・ランダム誤り訂正符号の復号•

同種写像問題・・・楕円曲線間の同種写像計算•

多変数多項式問題・・・多変数⼆次連⽴⽅程式の求解第⼀回NIST PQC標準化では1つも選ばれなかった

n 現在、暗号の重要な転換期にある• 今標準化されると今後⻑く使⽤される• 多変数多項式から標準化される⽅式を開発したい!

§4 多変数多項式暗号(MPKC)

6/11

n 多変数多項式暗号(Multivariate Public Key Cryptography)
ü 多変数⼆次多項式問題(MQ問題)の求解困難性を利⽤した暗号技術
例:

次の 2#!上の連⽴⼆次多項式を考える︓!! = 11$!" + 24$!$" + 5$!$# + 22$"" + $"$# + 17$#",!" = 27$!" + 29$!$" + 24$"" + 27$"$# + 19$#",!# = 4$!" + 6$!$" + $!$# + 25$"" + 27$"$# + 26$#".
. ∶= (!!, !", !#) ∶ 2##! ⟶ 2##!

($!, $", $#) = (0,1,1). $!, $", $# = (9,8,16). 0,1,1 = (9,8,16)($!, $", $#) = ±(0,1,1)

代⼊計算は易しい
求解は難しいü 1988年に⽇本の松本・今井らにより導⼊[1]ü 耐量⼦計算機暗号(PQC)の候補として現在活発に研究されている
ü NIST PQC 追加公募ではUOV[2]が注⽬を集めている
NIST would like submissions for signature schemes that have short signatures and fast verification (e.g., UOV).
[1] Matsumoto, T et al.: Public quadratic polynomial-tuples for efficient signature-verification and message-encryption, EUROCRYPT1988[2] Aviad Kipnis, Jacques Patarin, and Louis Goubin. Unbalanced Oil and Vinegar signature schemes, EUROCRYPTʼ99

§5 MQ問題

7/11

n2MQ(MultivariateQuadratic) 問題-5
多変数公開鍵暗号!8 , … , !9 ∈ %: &8 , … , &;

⼆次多項式
(!)

(!)

!! (#! , … , #" ) = ∑!#$#%#" )$,% #$ #% + ∑!#$#" +$ #$ + , (!) ,⋮())())!) (#! , … , #" ) = ∑!#$#%#" )$,% #$ #% + ∑!#$#" +$#$ + , ()) .

Find ' ∈ %;: s.t. !8 ' = ⋯ = !9 ' = 0.
この問題はNP-完全であることが⽰されている[GJ79][GJ79] M. R. Garey et al., Computers and Intractability: A guide to the theory of NP-completenessn Fukuoka MQ Challenge*

ü MQ問題の困難性評価を⽬的としたコンテスト
ü 問題は6つのTypeに分かれる
TypeⅠⅡⅢⅣⅤ

Ⅵ

$%(')

$%(2)

$%(256)$%(31)$%(2)$%(256)$%(31)

変数.

.

.

.

.

.

式数

2.

2.

2.

2./3

2./3

2./3

TypeⅠ,Ⅱ,Ⅲは暗号⽅式、Type Ⅳ,Ⅴ,Ⅵは署名⽅式に対応する*https://www.mqchallenge.org§6 ⼀般的構成

8/11
(!)

!! (#! , … , #" ) = ∑!#$#%#" )$,% #$ #% ,n 定義. ⼆次中⼼写像⋮+ ∶= (.8 , … , .9 ): %;: ⟶ %9: を⼆次写像として,())!) (#! , … , #" ) = ∑!#$#%#" )$,% #$ #%任意の元 3 ∈ %9: に対して, +(&) = 3 は少ない計算量で解けるもの.

n 秘密鍵
n 公開鍵

+ ∶ %;: ⟶ %9:""! ∶ $! ⟶ $!
94 ∶ %9: ⟶ %:⼆次中⼼写像
ランダムな可逆な線型写像

5 ∶= 4 ∘ + ∘ 7 ∶ %;: ⟶ %9
⼆次写像:= (!8 , … , !9 )!の構造が隠れる

MQ問題が安全性と関連している

§7 Unbalanced Oil Vinegar(UOV) 9/11
次の!8 上の⼆次⽅程式の解は簡単に⾒つかる!
"! ≔ 2%!" + %! %" + %"" + %" %# + %#" + %! %$ + %" %$ + %# %% = 1"" ≔ %!" − %! %" + 2%"" + %" %# − %#" + %! %% − %" %$ + %# %$ − %# %% = 2' =−10−130

1 −1 0 1
3 1 2 32 −1 2 30 3 0 0
1 3 1 3"9 ≔ $9 % & ' を計算すると*! = %!" + 2%! %" + 2%"" − %" %# + 2%#" + %! %$ + 2%! %% − %" %$ − %" %%−%# %$ + %# %% + %$" + %$ %% + 3%%" = 1*" = 2%!" − %! %# + 3%"" + 2%#" + 3%! %% + 3%" %% + %# %$ + 2%# %%−%%" = 1

§8 UOVの⼀般的構成
n パラメータ: B, 9 ∈ ℕ,4.7 Rainbow 方式

0 =B+9% = %! , … , %& , %′ = %&'! , … , %&'( ,vinegar変数

n UOV 中⼼多項式

10/110-変数

oil変数

係数は%: から全てランダムに選択する!
"! (%, % ) = ∑4*,, %* %&', + 5647 89:;. =0 %)⋮("( (%, % ) ) = ∑4*,, %* %&', + 5647 89:;. =0 %n UOV 秘密鍵n UOV 公開鍵! ≔ "! , , … , "( ∶ @.- ⟶ @(G: @.- ⟶ @.正則線型写像
E ≔ ! ∘ G = 8! , , … , 8( ∶ @.- ⟶ @(-§9 UOVのパラメータ

11/11

1999年 Unbalanced Oil & Vinegar (UOV)署名⽅式が提案される[1]pNIST追加公募で提案されたパラメータ(by Beullens et al.)NIST security
category

parameter:, ;, <

Public key
size

SignsizeI

16,96,64

66.6 KB

96 B

I(256,68,44)43.6 KB

128 B

III

256,112,72

189.2 KB

200 B

V

256,148,96

446.9 KB

260 B

ü 公開鍵サイズが格⼦・同種ベースと⽐べて⼤きいü UOVの改良⽅式がNISTの追加公募にいくつも投稿された