隠れた場の方程式

隠れ体方程式（HFE ）はHFEトラップドア関数とも呼ばれ、1996年にEurocryptで発表された公開鍵暗号システムで、松本・今井のシステムのアイデアを踏襲してジャック・パタラン（フランス語）が提案した。これは異なるサイズの有限体上の多項式に基づいており、秘密鍵と公開鍵の関係を隠蔽する。HFEは実際には基本的なHFEとHFEの組み合わせバージョンで構成されるファミリである。HFEファミリの暗号システムは、拡大体と秘密多項式を隠すために秘密アフィン変換を使用するため、多変数二次方程式のシステムの解を見つける問題（いわゆるMQ問題）の困難さに基づいている。隠れ体方程式は、QuartzやSflashなどのデジタル署名スキームの構築にも使用されている。^{[ 1 ]}${\displaystyle \mathbb {F} _{q}}$

数学的背景

隠れた体方程式の仕組みを理解するための中心的な概念の一つは、同じ基底体上の2つの拡大体に対して、上の変数の多変数多項式系を、上の の適切な基底を用いることで関数として解釈できるという点です。ほとんどすべての応用において、多項式は2次式、すなわち次数2です。^{[ 2 ]}まず、最も単純な種類の多項式、すなわち単項式から始め、それがどのようにして2次方程式系につながるかを示します。 ${\displaystyle \mathbb {F} _{q^{n}}}$ ${\displaystyle \mathbb {F} _{q^{m}}}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle \mathbb {F} _{q^{n}}\to \mathbb {F} _{q^{m}}}$ ${\displaystyle \mathbb {F} _{q^{n}}}$ ${\displaystyle \mathbb {F} _{q}}$

有限体 （ は2のべき乗）と拡大体 （ ）を考える。ある に対してが成り立ち、が絶対逆数 となるとする。絶対逆数 の条件は、への写像が1対1であり、その逆写像が（ は の逆数）であることを要求するのと同値である。 ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle q}$ ${\displaystyle K}$ ${\displaystyle 0<h<q^{n}}$ ${\displaystyle h=q^{\theta }+1}$ ${\displaystyle \theta}$ ${\displaystyle (h,q^{n}-1)=1}$ ${\displaystyle (h,q^{n}-1)=1}$ ${\displaystyle u\to u^{h}}$ ${\displaystyle K}$ ${\displaystyle u\to u^{h'}}$ ${\displaystyle h'}$ ${\displaystyle h\ {\bmod {q}}^{n}-1}$

ランダムな要素を取ります。定義は ${\displaystyle u\in \mathbb {F} _{q^{n}}}$ ${\displaystyle w\in \mathbb {F} _{q^{n}}}$

${\displaystyle w=u^{h}=u^{q^{\theta }}u\ \ \ \ (1)}$

をベクトル空間の基底とする。を基底に関して 、と表す。を基底に関する線型変換の行列、すなわち と する。${\displaystyle \beta _{1},...,\beta _{n}}$ ${\displaystyle K}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle u}$ ${\displaystyle u=(u_{1},...,u_{n})}$ ${\displaystyle w=(w_{1},...,w_{n})}$ ${\displaystyle A^{(k)}={a_{ij}^{(k)}}}$ ${\displaystyle u\to u^{q^{k}}}$ ${\displaystyle \beta _{1},...,\beta _{n}}$

${\displaystyle \beta _{i}^{q^{k}}=\sum _{j=1}^{n}a_{ij}^{k}\beta _{j},\ \ a_{ij}^{k}\in \mathbb {F} _{q}}$

について。さらに、基底元のすべての積を基底を用いて書き表す。すなわち、 ${\displaystyle 1\leq i,k\leq n}$

${\displaystyle \beta _{i}\beta _{j}=\sum _{l=1}^{n}m_{ijl}\beta _{l},\ \ m_{ijl}\in \mathbb {F} _{q}}$

各 について。で明示的かつ で二次方程式となる連立方程式は、(1) を展開し、 の係数を 0 とすることで得られる。 ${\displaystyle 1\leq i,j\leq n}$ ${\displaystyle n}$ ${\displaystyle w_{i}}$ ${\displaystyle u_{j}}$ ${\displaystyle \beta _{i}}$

2 つの秘密のアフィン変換 およびを選択します。つまり、 の要素を持つ2 つの可逆行列および と、上の長さの2 つのベクトルおよびを選択し、 およびを次のように定義します。 ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle n\times n}$ ${\displaystyle M_{S}=\{S_{ij}\}}$ ${\displaystyle M_{T}=\{T_{ij}\}}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle v_{S}}$ ${\displaystyle v_{T}}$ ${\displaystyle n}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle x}$ ${\displaystyle y}$

${\displaystyle u=Sx=M_{S}x+v_{S}\ \ \ \ w=Ty=M_{T}y+v_{T}\ \ \ \ (2)}$

(2)のアフィン関係を用いて を に置き換えると、連立方程式はについて線形となり、について2次となる。線型代数を適用すると、 について2次多項式として明示的な方程式が得られる。^{[ 3 ]}${\displaystyle u_{j},w_{i}}$ ${\displaystyle x_{k},y_{l}}$ ${\displaystyle n}$ ${\displaystyle y_{l}}$ ${\displaystyle x_{k}}$ ${\displaystyle n}$ ${\displaystyle y_{l}}$ ${\displaystyle x_{k}}$

多変数暗号システム

HFE ファミリーの多変数暗号システムとしての基本的な考え方は、ある有限体(通常は値が使用される)上の1 つの未知数の多項式 から始めて秘密鍵を構築することです。この多項式は上で簡単に逆変換できます。つまり、方程式の解が存在する場合は、任意の解を見つけることができます。復号化および/または署名の秘密変換は、この逆変換に基づいています。上で説明したように、 は固定基底を使用した方程式のシステムと同一視できます。暗号システムを構築するには、公開情報が元の構造を隠し、逆変換を防ぐように多項式を変換する必要があります。これは、有限体を上のベクトル空間と見なし、2 つの線形アフィン変換と を選択することによって行われます。この 3 つ組が秘密鍵を構成します。秘密多項式は 上で定義されます。^{[ 1 ] [ 4 ]}公開鍵は です。以下は、 HFE における MQ トラップドアの図です。${\displaystyle P}$ ${\displaystyle x}$ ${\displaystyle \mathbb {F} _{q^{n}}}$ ${\displaystyle q=2}$ ${\displaystyle \mathbb {F} _{q^{n}}}$ ${\displaystyle P(x)=y}$ ${\displaystyle P}$ ${\displaystyle n}$ ${\displaystyle (p_{1},...,p_{n})}$ ${\displaystyle (p_{1},...,p_{n})}$ ${\displaystyle \mathbb {F} _{q^{n}}}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle (S,P,T)}$ ${\displaystyle P}$ ${\displaystyle \mathbb {F} _{q^{n}}}$ ${\displaystyle (p_{1},...,p_{n})}$ ${\displaystyle (S,P,T)}$

${\displaystyle {\text{input}}x\to x=(x_{1},...,x_{n}){\overset {{\text{secret}}:S}{\to }}x'{\overset {{\text{secret}}:P}{\to }}y'{\overset {{\text{secret}}:T}{\to }}{\text{output}}y}$

HFE多項式

上の次数を持つ非公開多項式 は の元である。多項式の項が の2乗以下の項を持つ場合、公開多項式は小さくなる。^{[ 1 ]}の形の単項式、すなわち指数に の2乗を持つ場合がHFEの基本版であり、次のように選択される。 ${\displaystyle P}$ ${\displaystyle d}$ ${\displaystyle \mathbb {F} _{q^{n}}}$ ${\displaystyle \mathbb {F} _{q^{n}}[x]}$ ${\displaystyle P}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle P}$ ${\displaystyle x^{q^{s_{i}}+q^{t_{i}}}}$ ${\displaystyle q}$ ${\displaystyle P}$

${\displaystyle P(x)=\sum c_{i}x^{q^{s_{i}}+q^{t_{i}}}}$

多項式の次数はセキュリティパラメータとも呼ばれ、その値が大きいほどセキュリティが向上します。これは、結果として得られる二次方程式の集合がランダムに選択された二次方程式の集合に似ているためです。一方で、次数が大きいと解読速度が低下します。は最大次数の多項式であるため、 で表される の逆元は演算で計算できます。^{[ 5 ]}${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle P}$ ${\displaystyle d}$ ${\displaystyle P}$ ${\displaystyle P^{-1}}$ ${\displaystyle d^{2}(\ln d)^{O(1)}n^{2}\mathbb {F} _{q}}$

暗号化と復号化

公開鍵は上の多変数多項式によって与えられます。したがって、メッセージを暗号化するにはから へ転送する必要があります。つまり、はベクトル であると仮定します。メッセージを暗号化するには、各を で評価します。暗号文は です。 ${\displaystyle n}$ ${\displaystyle (p_{1},...,p_{n})}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle M}$ ${\displaystyle \mathbb {F} _{q^{n}}\to \mathbb {F} _{q}^{n}}$ ${\displaystyle M}$ ${\displaystyle (x_{1},...,x_{n})\in \mathbb {F} _{q}^{n}}$ ${\displaystyle M}$ ${\displaystyle p_{i}}$ ${\displaystyle (x_{1},...,x_{n})}$ ${\displaystyle (p_{1}(x_{1},...,x_{n}),p_{2}(x_{1},...,x_{n}),...,p_{n}(x_{1},...,x_{n}))\in \mathbb {F} _{q}^{n}}$

復号化を理解するために、暗号化を で表してみましょう。送信者はこれらの値を参照できないことに注意してください。メッセージにおいてを評価することで、まず を適用し、 という結果を得ます。この時点では から に転送されるため、を超える秘密多項式 を適用することができ、この結果は で表されます。再び がベクトルに転送され、変換が適用され、最終的な出力は から生成されます。 ${\displaystyle S,T,P}$ ${\displaystyle p_{i}}$ ${\displaystyle S}$ ${\displaystyle x'}$ ${\displaystyle x'}$ ${\displaystyle \mathbb {F} _{q^{n}}\to \mathbb {F} _{q^{n}}}$ ${\displaystyle P}$ ${\displaystyle \mathbb {F} _{q^{n}}}$ ${\displaystyle y'\in \mathbb {F} _{q^{n}}}$ ${\displaystyle y'}$ ${\displaystyle (y_{1}',...,y_{n}')}$ ${\displaystyle T}$ ${\displaystyle y\in \mathbb {F} _{q^{n}}}$ ${\displaystyle (y_{1},...,y_{n})\in \mathbb {F} _{q}^{n}}$

を復号化するには、上記の手順を逆の順序で実行します。これは、秘密鍵がわかっている場合に可能です。 解読で重要な手順は、と の逆変換ではなく、 の解の計算です。は必ずしも一対一ではないため、この逆変換には複数の解が見つかる可能性があります (は次数 d の多項式であるため、最大で d つの異なる解が存在します)。 として示される冗長性は、解の集合から正しいものを選択するために、最初のステップでメッセージに追加されます。^{[ 1 ] [ 3 ] [ 6 ]}下の図は、暗号化の基本的な HFE を示しています。 ${\displaystyle y}$ ${\displaystyle (S,P,T)}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle P(x')=y'}$ ${\displaystyle P}$ ${\displaystyle X'=(x_{1}',...,x_{d}')\in \mathbb {F} _{q^{n}}}$ ${\displaystyle P}$ ${\displaystyle r}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle X'}$

${\displaystyle M{\overset {+r}{\to }}x{\overset {{\text{secret}}:S}{\to }}x'{\overset {{\text{secret}}:P}{\to }}y'{\overset {{\text{secret}}:T}{\to }}y}$

HFEのバリエーション

隠れ場方程式には、+、-、v、fという 4 つの基本的なバリエーションがあり、それらを様々な方法で組み合わせることができます。基本原理は次のとおりです。

01. +記号は、公開方程式といくつかのランダム方程式を線形混合したもので構成されます。

02. -記号はAdi Shamirによるもので、公開方程式の冗長性「r」を削除することを目的としています。

03. f記号は、公開鍵のいくつかの入力変数を固定することから構成され、この変形は投影のpと呼ばれることもあります。${\displaystyle f}$

04. v記号は、ビネガー変数と呼ばれる変数のうちいくつかvが固定されている場合にのみ関数の逆関数が見つかるような、時には非常に複雑な構成として定義されます。このアイデアはジャック・パタランによるものです。

05. IP記号は内部摂動を意味し、秘密方程式にランダムな二次多項式を加えることで実現されます。ただし、このランダムな二次多項式は低階数の線形写像で構成されているため、逆行列を求めることができます。

06. LL'バリアントは、すべての公開方程式に、線形写像の積の少数のランダムな線形結合を追加するものです。これは暗号化モードで使用することを目的としています。

上記の操作により、関数のトラップドア可解性がある程度維持されます。

HFE-とHFEvは署名方式において有用であった。署名生成の遅延を防ぎ、HFE全体のセキュリティを向上させるからである。一方、暗号化においては、HFE-とHFEvはどちらも復号処理を遅くするため、方程式を過度に削除したり（HFE-）、変数を過度に追加したり（HFEv）すべきではない。HFE-とHFEvはどちらもQuartzを生成するために用いられた。しかし、Ding、Petzoldt、Taoによる新たなMin-Ranks攻撃により、これらの方式は時代遅れとなった。^{[ 7 ]}

署名には現在、HFE IPまたはHFE IPvの使用が推奨されています。^{[ 8 ]} IPバリアントは特定の種類のMin-Rank攻撃（Min-Rank S）に対して非常に効果的ですが、vまたは-バリアントは他のすべての攻撃（主にMin-Rank TまたはGröbner基底攻撃）に対して効果的です。

暗号化に関しては、現在推奨されている方式はHFE LL'のみです。^{[ 9 ]}

HFE攻撃

HFE に対する有名な攻撃は 2 つあります。

秘密鍵の復元（シャミール-キプニス）：この攻撃の鍵は、秘密鍵を拡大体上の疎な一変数多項式として復元することです。この攻撃は基本的なHFEに対してのみ有効であり、そのすべてのバリエーションに対しては失敗します。 ${\displaystyle \mathbb {F} _{q^{n}}}$

高速グレブナー基底（フォージェール）：フォージェール攻撃のアイデアは、高速アルゴリズムを用いて多項式方程式系のグレブナー基底を計算するというものである。フォージェールは2002年にHFEチャレンジ1を96時間で破り、2003年にはフォージェールとジューが共同でHFEの安全性に関する研究を行った。^{[ 1 ]}

参考文献

1. クリストファー・ウルフとバート・プレニール「非対称暗号：隠れた体方程式」
2. Nicolas T. Courtois「多変数署名のみの公開鍵暗号システムについて」
3. イリア・トリ 隠し多項式暗号システム
4. Jean-Charles FaugèreとAntoine Joux、グレブナー基底を用いた隠れ体方程式 (HFE) 暗号システムの代数的暗号解析 2008年11月11日アーカイブ、 Wayback Machine
5. Nicolas T. Courtois、「隠れた場の方程式の安全性」
6. ジャック・パタリン、「隠れた場の方程式（HFE）と同型多項式（IP）：非対称アルゴリズムの2つの新しいファミリー」
7. 「HFEv署名スキームの改良された鍵回復」 2020年。
8. 「HFEバリアントの最先端技術では、適切な摂動によってHFEを修復できるのか？」 2024年。
9. 「LL摂動による多変量暗号化 - 暗号化におけるHFEの修復は可能か? -」 2024年。

• ニコラス・T・クルトワ、マグナス・ダウム、パトリック・フェルケ、「HFE、HFEv-、および石英の安全性について」
• Andrey Sidorenko、隠れ場方程式、EIDMA セミナー 2004 アイントホーフェン工科大学
• Yvo G. Desmet, 公開鍵暗号-PKC 2003, ISBN 3-540-00324-X