Unbalanced Oil and Vinegar
前提
この記事は以下の知識を前提とします :
線形代数
代数(特に有限体と多項式環)
計算複雑性理論と暗号理論の基礎
重要なことはその都度復習するので, 過去に一度勉強したことがあるくらいで十分です. 集合論と述語論理は説明なしに使わせてください.
参考
この記事は以下の文献の内容を解説したものです :
Aviad Kipnis, Jacques Patarin, and Louis Goubin. Unbalanced Oil and Vinegar Signature Schemes. EUROCRYPT’99, LNCS 1592, pp. 206–222, 1999.
はじめに
Shorのアルゴリズムとは, (理論的な)量子計算機の上で実行される量子アルゴリズムであり, 古典計算では困難であると考えられている素因数分解問題および離散対数問題を非常に少ない計算量で解くアルゴリズムです. これは言い換えると, 現在公開鍵暗号として広く使われているRSA暗号と楕円曲線暗号は量子計算機を用いて解読できるということを意味しています. もっとも, 量子計算機のハード面の開発が実用レベルに至っていないため, 現段階ではこれらの暗号を量子計算機を用いて解読したという報告はありません. ただし, 来たる量子時代に向けて, 今のうちにこの問題に対処することの必要性は高いわけです. そこで登場したのが耐量子計算機暗号という考え方です.
耐量子計算機暗号とはその名の通り, 量子計算機を用いた攻撃に耐性がある(だろうと考えられている)暗号です. ここで重要なのが, この暗号は古典計算機(従来の計算機)の上で実装されるという点です. 今までと同じ機械の上で今までと同じように振る舞うけれど, 量子計算機でも解けない数学の問題を軸に構成されているから量子計算機が実用化されても安全安心, それが耐量子計算機暗号です. 量子計算機の実力を買い被っている人には, にわかには信じられない代物かもしれませんが, そもそも量子計算機とは並列で計算ができて一部のアルゴリズムの計算量のオーダーを誤魔化せる程度のものであり, 耐量子計算機暗号の構築は意外と難しくありません. 実際, 耐量子計算機暗号は数多く提案されており, そのうちどれが安全性と可用性の面で優れているかを評価・選定している状態です.
ここではそんな耐量子計算機暗号の署名方式"Unbalanced Oil and Vinegar(UOV)"の仕組みを解説します.
デジタル署名
UOVの説明の前に, デジタル署名について復習しましょう. (知っている人は読み飛ばすか, 下の図だけ見て再確認してください.) 計算機の外で署名といえば, ペンで自分の名前を書くことを言います. なんでこんなことをするのかといえば, この操作は本人にしかできない(笑)という仮定のもとで, その「本人」を証明しているわけです. 捺印も同じで, この印鑑を持っているのはこの世界に一人だけ(笑)なので, その印影をもって, なりすまされていない真性の「本人」を認証します. これと同じことを計算機の上で実装したもの, およびそれにまつわる一連の社会/インターネット上のシステムをデジタル署名, または電子署名と言います. (多くの場合, この二つの用語は同じ意味で用いられますが, たまに電子署名という集合の一つの要素としてデジタル署名ということがあります. 話がややこしくなるだけなので今回は同じものと思ってください.)
デジタル署名は公開鍵暗号のアナロジーのような技術です. (指導教員にこう言うとめちゃくちゃ注意されました. 確かに全く異なる技術ですが, 初学者に教える際の例えとしては悪くないと思っています. 普通, 秘匿通信を先に勉強するものなので.) 公開鍵暗号の復習をしていると埒が開かなくなるのでしませんが, 知っている人は公開鍵暗号を思い出してください. これから, PDFなどのファイルに, 他の誰にもなりすませないような「署名」を施すことを考えます.
デジタル署名は3つのプロセスで構成されます. すなわち, 鍵生成, 署名, 検証の3つです. 鍵生成プロセスでは, 署名をしたい人が公開鍵と秘密鍵のペアを作成し, 公開鍵を公開します. 署名プロセスでは, 署名をしたい人が, 秘密鍵と署名を施したいファイル(実際はそのハッシュ値)を用いて署名を生成し, ファイルと署名を(証明したい相手に)送信します. 検証プロセスでは公開鍵と署名とファイル(のハッシュ値)から署名の正当性を検証します. 図にするとこんな感じです:
これにより, 以下の2点を実現します:
・送信元の認証 : なりすましを防止する
・改竄の検出 : 第三者による書き換えを検出する
以上がデジタル署名の復習になります. 大雑把なことしか述べていないので, 詳しいことは適当な暗号の本を参照してください. 以上のことから, 署名を攻撃するとは, 「正しい」署名の他に検証を突破するような署名を生成することで, なりすましや改竄を実現することを言います. 最初に述べたように, デジタル署名は公開鍵暗号のアナロジーのようなものであり, 安全性の要となる「問題」も現状では素因数分解問題や離散対数問題が使われています. よって量子計算機の前では無力だろうという懸念があります.
多変数多項式暗号
一般に, 有限体上の高次多変数多項式からなる連立方程式を解く問題はNP困難です. つまり, 以下のような連立方程式は, 変数と式が十分に多いとき, 計算機でも解くのは困難です.
また, 多項式の次数を2次に限定したとしても, この問題はNP困難です. これはMQ(Multivariate Quadratic)問題と呼ばれています. さらに, MQ問題は量子計算機でも解くのが困難だろうと考えられています. このMQ問題を安全性の根拠においた暗号系を多変数多項式暗号と言います. ちなみになぜ2次にこだわるのかといえば, 2次以上を考える理由が特にないので, 処理速度を上げるためにも2次多項式が最適だからです. また, 線形代数を勉強したことがある人は知っていると思いますが, 一次の連立方程式なら高速に解くことができます. この事実は後で使うので覚えておいてください. 余談ですが, 多変数多項式暗号の具体的なアルゴリズムを世界で初めて提案したのは, 日本人の松本勉さんと今井秀樹さんです. 彼らが提案した松本・今井暗号はその後解読されましたが, そのアイデアは今でも受け継がれています.
Unbalanced Oil and Vinegar
さて, 本題のUnbalanced Oil and Vinegar(UOV)の解説をします. UOVは1999年にフランスの暗号学者Jacques Patarinらによって提案されました. (ちなみに上で少し触れた松本・今井暗号を解読したのもPatarinです.) 1997年にPatarinはOil and VinegarというUOVの前身となる署名方式を提案しましたが, のちに解読され, その攻撃に耐性を持たせた修正版として再度提案されたのがUOVです. UOVは20年以上にわたって安全性やバリエーションについて研究され, 最近では元の論文よりかなり洗練されていますが, ここではPatarinらが1999年に提案した論文の言葉で説明します.
以下を定義します:
$${K = \mathbb{F}_q}$$ :(位数が比較的小さい)有限体
$${n, v \in \mathbb{N}}$$
$${y = (y_1, \cdots, y_n) \in K^n}$$ : 署名したいメッセージ(またはそのハッシュ値)
$${x = (x_1, \cdots, x_{n + v})}$$ : 署名
秘密鍵
1. $${s : K^{n + v} \rightarrow K^{n + v}}$$ : 全単射アフィン変換
まず, 送信者が任意にアフィン変換を定義し, 秘密にします. アフィン変換とは線形変換と平行移動によって定まる変換であり, すなわち全単射アフィン変換とは, 正則行列 $${A}$$ とベクトル $${c}$$ を用いて, $${x \mapsto Ax + c}$$ と表される写像です. 逆写像は$${x \mapsto A^{-1}(x - c)}$$ となります.
2. $${K}$$上の連立方程式
$$
y_i = \sum \gamma_{ijk}a_ja'_k + \sum \lambda_{ijk}a'_ja'_k + \sum \xi_{ij}a_j + \sum {\xi}'_{ij}a'_j + \delta_i (i = 1, \cdots, n)
$$
$${\gamma_{ijk}, \lambda_{ijk}, \xi_{ij}, {\xi}'_{ij}, \delta_i}$$ : 係数
$${a_1, \cdots, a_n}$$ : "oil" unknowns
$${a'_1, \cdots, a'_v}$$ : "vinegar" unknowns
さらに送信者は, 上の形式を持つ2次の連立方程式を定義し, 秘密にします. この連立方程式の未知数は $${a_1, \cdots, a_n, a'_1, \cdots, a'_v}$$ の $${n + v}$$ 個であり, それらを2種類の"Oil"と"Vinegar"にラベリングしてあります. また, 方程式の左辺は, 署名を施したいデータ(順序対)の要素です. そしてこれが重要なのですが, 上の方程式は $${a_ja_k}$$ の項, すなわち"Oil"unknownsだけからなる2次の項を持ちません.
まとめると, 署名をしたい送信者は全単射アフィン変換と, 特殊な形式をした連立方程式を秘密鍵として保持します.
公開鍵
送信者は, 秘密鍵のアフィン変換の逆写像によって定まる代入写像で秘密鍵の連立方程式を変換したものを公開します(ややこしい). つまり, 上の連立方程式を $${y_i = f_i(A) (A = (a_1, \cdots, a_n, a'_1, \cdots, a'_v))}$$ と書き直したとき, 公開鍵は連立方程式 $${y_i = f_i(s^{-1}(A))}$$ となります.
ちなみに, ここにOil and Vinegarの名前の由来があります. 順序対 $${A}$$ は前半が"Oil", 後半が"Vinegar"と, 2つの変数が分離していましたが, $${s^{-1}(A)}$$ の操作によって, 順序対のどの成分にもOil unknownsとVinegar unknownsが現れてきます. これを二層に分離したドレッシングを振って混ぜている様子に見立ててOil and Vinegarと呼ばれています.
署名
署名生成に際し, 送信者はまず秘密鍵の連立方程式を満たす$${A = (a_1, \cdots, a_n, a'_1, \cdots, a'_v)}$$を求めます. これはMQ問題なので一見不可能なように思えますが, 連立方程式が特殊な形式をしているため可能です. 方程式はOil unknownsに関して線形なので, ランダムなVinegar unknownsを代入することでOil unknownsに関する線形方程式となり, これを解くことで解が求まります. もちろん, この線型方程式に常に解が存在するわけではありませんが, 解がなければまた別のVinegar unknownsを代入します. 一般に有限体上の正方行列が正則となる確率が計算できて, それによると, 決して多くない試行回数で解が求まることがわかっています.
次に送信者は $${x = s^{-1}(A)}$$ を計算し, これを署名とします.
検証
署名を検証するには, 署名$${x}$$を公開鍵の連立方程式に代入し, $${y_i}$$ と一致するか確認します.
攻撃者が不正な署名を用いてこの検証を突破するには, 公開鍵の連立方程式を解く必要があり, 安全性はMQ問題の困難性に依拠します. (厳密には公開鍵から秘密鍵を復元できないという前提(EIP)も必要になります.)
Note
$${n = v}$$ のときを(Original) Oil and Vinegarと呼びます. これは既に解読され, $${n > v}$$ の場合も同様の手法で解読できます. よって $${n < v}$$ のときのみが生き残り, これをUnbalanced Oil and Vinegarと呼びます.
UOVは処理速度の面で非常に優れています. 一方UOVは鍵長が長く, これをいかに短縮するかという課題が, 今日に至るまで多くの暗号学者によって研究されています.
以上がUOVの概要になります. お疲れ様でした.
Unbalanced Oil and Vinegar (2周目)
これから, UOVについてもう一度言葉を変えて説明します. 上で説明した定義や記号は原論文に則したものですが, 以下では最近の論文で用いられるような言葉でUOVを表現します.
まず, 連立方程式は写像です. というのはさすがに語弊がありますが, 体$${K}$$上の$${m}$$変数多項式$${n}$$本からなる順序対 $${F(x) := (f_1(x), \cdots, f_n(x))}$$ は$${K^m}$$から$${K^n}$$への写像を定義します. よって, 連立方程式を解くとは, $${F}$$の逆写像を求めることに他なりません.
UOVにおける秘密の全単射アフィン変換を$${S}$$, 秘密の連立方程式を$${F}$$とおくと, 公開鍵は$${\overline{F}=F \circ S}$$となります. $${F}$$は上で述べたように特殊な形をしています. あれはOil and Vinegar形式やOil and Vinegar多項式と呼ばれています. ちなみに, アフィン変換を2つとって, $${\overline{F}=S_1\circ F \circ S_2}$$とする場合もありますが, これは多くの場合であまり重要ではなく, アフィン変換は内側の1個で十分だと考えられています. そしておそらくこのこと(= $${S_1\circ F \circ S_2}$$)から, $${F}$$は中心写像(central map)と呼ばれています.
署名生成に際し, 送信者は方程式$${F \circ S(x) = y}$$を解きます. そのためにまず, 両辺に左から$${F^{-1}}$$を作用します. $${F}$$はOil and Vinegar形式なのでこれは可能で, 上で述べたような方法で連立方程式を解きます. 次に両辺に$${S^{-1}}$$を作用すれば方程式の解が得られます. これを$${y}$$に対する署名とします. このような説明により, なぜ1周目の説明で$${s}$$ではなく$${s^{-1}}$$を使っていたのかが理解できると思います.
$${F}$$を二次多項式, $${S}$$を全単射アフィン変換で定義していましたが, $${F}$$を二次形式(二次の斉次多項式), $${S}$$を正則な線形変換で定義しても安全性を損なわないことがわかっています. したがって, $${F}$$は$${n}$$個の上三角または対称行列$${F_i}$$で表現され, 公開鍵もまた$${S^tF_iS}$$で表現されます. さらにこのとき, $${F}$$のOil and Vinegar形式より, $${F}$$を表現する行列は成分がすべて$${0}$$の$${m \times m}$$ブロックを持ちます. こういった表現を利用し, central mapをうまく制限して鍵長を短くする工夫がいくつか提案されていますが, それはまた別の記事で解説したいと思います.
追記(2022. 8. 6)
先日, 「耐量子計算機暗号と量子情報の数理」というイベントが九州大学で開催され, オンラインで参加してきました. そこでQR-UOVの古江さんが多変数多項式暗号について発表していたのですが, 今回の内容について, 筆者が知らなかったことや書き足りなかったことがいくつかあったので共有したいと思います.
MQ問題をNP困難と書きましたが, NP完全だそうです. これは説明すると長くなるのでしませんが, 安全性の側面から言えば良いことです.(雑)
多変数多項式暗号のほとんどは安全性証明ができていないそうです. これは安全性の側面から言えば当然良くないことです.
署名と暗号の最大の違いは一意性を要求するか否かです. 暗号では復号が一意に定まらなければいけませんが, 署名では検証を突破するような署名が複数あっても構いません. 実際UOVでも変数の数$${n + v}$$より式の数$${n}$$の方が少ないので, 当然解は一意に定りません. 多変数多項式暗号で暗号(KEM)を構築しようとすると, 式の数が増えトラップドアの構築に制限がかかるため, 非常に難しくなります. そのため多変数多項式暗号は署名向きだと言われています.
この記事が気に入ったらサポートをしてみませんか？