隠れた場の方程式

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

隠れた体方程式がどのように機能するかを理解するための中心的な概念の 1 つは、同じ基本体上の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 の累乗）と拡大体を考えます。が、ある に対して かつがgcd となるものとします。 gcd という条件は、への写像が 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 の多項式としてそれぞれ 1 つずつ明示的な方程式が得られます。^[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}$

上の次数を持つ非公開多項式 は の元である。多項式の項が上の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}$

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

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

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

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

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

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

HFE- と HFEv は署名スキームで非常に役立ちます。署名生成の速度低下を防ぎ、HFE の全体的なセキュリティも強化するからです。一方、暗号化の場合、HFE- と HFEv はどちらも復号化プロセスをかなり遅くするため、方程式をあまり多く削除したり (HFE-)、変数をあまり多く追加したり (HFEv) しないでください。HFE- と HFEv はどちらも Quartz を取得するために使用されました。

暗号化に関しては、復号化プロセスに同じ時間がかかるためHFE+の方が状況は良いですが、公開鍵には変数よりも方程式が多くなります。 ^{[1] [2]}

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

秘密鍵を復元する ( Shamir -Kipnis): この攻撃の重要な点は、秘密鍵を拡大体上のスパースな一変数多項式として復元することです。この攻撃は基本的な HFE に対してのみ機能し、そのすべてのバリエーションに対しては失敗します。 ${\displaystyle \mathbb {F} _{q^{n}}}$

高速グレブナー基底 (Faugère): Faugèreの攻撃のアイデアは、高速アルゴリズムを使用して多項式方程式系のグレブナー基底を計算することです。Faugère は 2002 年に HFE チャレンジ 1 を 96 時間で破り、2003 年には Faugère とJoux が協力して HFE のセキュリティに取り組みました。^[1]

• Nicolas T. Courtois、Magnus Daum、Patrick Felke、「HFE、HFEv-、Quartzのセキュリティについて」
• Andrey Sidorenko、隠れ場方程式、EIDMA セミナー 2004 アイントホーフェン工科大学
• Yvo G. Desmet、公開鍵暗号 - PKC 2003、ISBN  3-540-00324-X