不均衡な油と酢のスキーム

暗号学において、不均衡な油と酢（UOV）方式は、 J. パタリンが設計した油と酢方式の修正版である。どちらもデジタル署名プロトコルであり、多変量暗号の一種である。この署名方式のセキュリティは、NP困難な数学的問題に基づいている。署名を作成して検証するには、最小の二次方程式系を解く必要がある。n 変数を持つ m 方程式を解くことはNP困難である。m が n よりもはるかに大きいかはるかに小さい場合、問題は容易であるが[ 1 ] 、^{暗号目的にとって重要なことに、} mとnがほぼ等しい平均的なケースでは、量子コンピュータを使用する場合でも、問題は困難であると考えられている。量子耐性を実現することを目的として、多変量方程式に基づく複数の署名方式が考案されている。

UOV の大きな欠点は、キーのサイズが大きくなる可能性があることです。通常、変数の数n は、方程式の数mの 2 倍になるように選択されます。キー内のこれらすべての方程式の係数をエンコードするには、かなりのスペースが必要であり、デジタル署名アルゴリズムまたは楕円曲線デジタル署名アルゴリズムに匹敵するセキュリティを提供するシステムの場合は、少なくとも 200 キロバイトが必要です。

署名方式には、非公開に保持される署名キーと、公開される検証キーがあります。たとえば、RSAに基づく署名方式では、キーは両方とも指数です。UOV 方式、および他のすべての多変量署名方式では、キーはより複雑です。

数学の問題は、変数を含む方程式を解くことです。方程式システム全体が公開鍵です。 ${\displaystyle m}$${\displaystyle n}$

数学の問題を暗号化に使用するには、それを修正する必要があります。変数の計算には多くのリソースが必要です。標準的なコンピュータでは、これを許容できる時間内に計算することはできません。そのため、方程式システムに特別なトラップドアが挿入されます。このトラップドアが署名鍵です。これは、2 つのアフィン変換とおよび多項式ベクトル の3 つの部分で構成されます。両方の変換は、特定のグループ内の要素を変換するために使用されます。は に変換されます。2 番目の変換は、変数ベクトルを有効な署名に変換します。 ${\displaystyle n}$ ${\displaystyle T}$${\displaystyle S}$${\displaystyle {\acute {P}}}$${\displaystyle T}$${\displaystyle y}$${\displaystyle y_{1},y_{2},...,y_{n}}$${\displaystyle S}$

3 番目の秘密要素は、方程式を作成するための特定のツールを提供します。方程式は、署名キーの所有者のみが知っているルールを使用して構築されます。 ${\displaystyle {\acute {P}}}$

有効な署名を作成するには、次の方程式系を解く必要があります。

$${\displaystyle {\begin{aligned}y_{1}&=f_{1}(x_{1},\ldots ,x_{n})\\y_{2}&=f_{2}(x_{1},\ldots ,x_{n})\\&~\vdots \\y_{m}&=f_{m}(x_{1},\ldots ,x_{n})\\\end{aligned}}}$$

ここで は署名する必要がある特定のメッセージです。有効な署名は です。 ${\displaystyle y=(y_{1},y_{2},\ldots ,y_{m})}$${\displaystyle x=(x_{1},x_{2},\ldots,x_{n})}$

与えられた に署名するには、まずメッセージを方程式系に適合するように変換する必要があります。を使用して、メッセージを許容可能な部分に「分割」します。 次に、方程式を構築する必要があります。 各方程式は同じ形式です。 ${\displaystyle y}$${\displaystyle T}$${\displaystyle y_{1},y_{2},\ldots ,y_{m}}$

$${\displaystyle y_{i}=\sum {\gamma _{ijk}a_{j}{\acute {a}}_{k}}+\sum {\lambda _{ijk}{\acute {a}} _{j}{\急性 {a}}_{k}}+\sum {\xi _{ij}a_{j}}+\sum {{\急性 {\xi }}_{ij}{\急性{a}}_{j}}+\デルタ _{i}}$$

次の手順では、指定されたメッセージに署名し、結果として有効な署名が生成されます。 ${\displaystyle y}$${\displaystyle x}$

1. 係数は秘密に選択する必要があります。${\displaystyle \gamma _{ijk},\lambda _{ijk},\xi _{ij},{\acute {\xi }}_{ij},\delta _{i}}$
2. 酢変数（）はランダムに選択される${\displaystyle {\acute {a}}_{j}}$
3. 結果として得られる線形方程式系は、石油変数（）について解かれる。${\displaystyle a_{i}}$

酢と油の変数は事前署名を構築します。最後にプライベート変換によって変換され、有効な署名が生成されます。 ${\displaystyle A=(a_{1},\ldots ,a_{n},{\acute {a}}_{1},\ldots ,{\acute {a}}_{v})}$${\displaystyle A}$${\displaystyle S}$${\displaystyle x=S^{-1}(A)}$

酢の変数が固定されている場合、方程式のシステムは線形になります。方程式では、油の変数が他の油の変数と乗算されることはありません。したがって、油の変数は、たとえばガウス削減アルゴリズムを使用して簡単に計算できます。署名の作成自体は高速で、計算も簡単です。

署名は通信相手に送信されます。署名の検証は方程式システムである公開鍵を使用して実行されます。

$${\displaystyle {\begin{aligned}y_{1}&={f_{1}}^{*}(x_{1},x_{2},\ldots ,x_{n})\\y_{2}&={f_{2}}^{*}(x_{1},x_{2},\ldots ,x_{n})\\&~\vdots \\y_{m}&={f_{m}}^{*}(x_{1},x_{2},\ldots ,x_{n})\\\end{aligned}}}$$

この方程式システムは、署名作成に必要なシステムを少し変更したものです。攻撃者が秘密の係数や油と酢の変数の特殊なフォーマットに関する情報を取得できないように変更されています。署名を検証するには、公開鍵のすべての方程式を解く必要があります。入力は署名そのものです。すべての結果が元のメッセージの対応する部分と等しい場合、検証は成功です。 ${\displaystyle y_{i}}$

主な利点は、アルゴリズムで解く数学的問題が量子耐性を持つことです。ショアのアルゴリズムを使用して大きな合成数を因数分解できる量子コンピュータが構築されると、離散対数問題が解けないことを前提とするRSAやElGamalなどの商用署名方式が破られます。多変量方程式を解く際に量子コンピュータに大きな利点を与えるアルゴリズムが知られていないため、UOV は安全なままである可​​能性があります。

2 つ目の利点は、方程式で使用される演算が比較的単純なことです。署名は「小さな」値の加算と乗算のみで作成および検証されるため、この署名はスマート カードに見られるようなリソースの少ないハードウェアでも実行可能です。

UOV の欠点は、公開鍵が非常に長い鍵長を使用する点です。公開鍵には方程式のシステム全体が含まれるため、数百キロバイト必要になることがあります。UOV は広く使用されていません。すでにいくつかの攻撃方法が知られていますが、UOV が広く使用されるようになれば、さらに多くの攻撃方法が現れるかもしれません。UOV は、セキュリティをさらに調査する必要があるため、まだ商用利用の準備ができていません。 ${\displaystyle m}$

Rainbow暗号システムはUOVに基づいており、NISTの量子耐性デジタル署名標準コンペティションの最終候補3つのうちの1つですが、NISTコンペティションで提案されたセキュリティに関して最近重大な懸念が浮上しました。Rainbowに対する新しいMinRank攻撃が発見され、提案されたRainbowインスタンスのセキュリティがNISTによって設定された要件を下回るレベルに低下しました。^[2] Beullensは2022年に新しい攻撃を発見しました。これは、週末にRainbow L1パラメータセットの秘密鍵を復元します。^[3] UOV自体はこの攻撃の影響を受けません。

• ブッフマン、ヨハネス。コロナド、カルロス。ドーリング、マーティン。エンゲルベルト、ダニエラ。ルートヴィヒ、クリストフ。オーヴァーベック、ラファエル。シュミット、アーサー。ヴォルマー、ウルリッヒ。ワインマン、ラルフ・フィリップ: ポスト量子署名、 –、2004 年 10 月 29 日
• ウルフ、クリストファー：公開鍵暗号における多変数二次多項式、DIAMANT/EIDMA シンポジウム 2005
• Braeken, An; Wolf, Christopher; Preneel, Bart: 不均衡な油と酢の署名方式のセキュリティに関する研究、ESAT-COSIC、2004 年 9 月 2 日
• Coron, Jean-Sebastien; de Weger, Benne: 暗号化で使用される主な計算問題の難しさ、ECRYPT D.AZTEC.6、2007 年 3 月 14 日
• キプニス、アヴィアド：不均衡な油と酢の署名スキーム - 拡張版、EURO-CRYPT、1999
• フォージェール、ジャン＝シャルル、ペレ、ルドヴィック。UOV のセキュリティについて。暗号学 eprint アーカイブ。レポート 2009/483。2009