一方向関数

コンピュータサイエンスにおいて、一方向性関数とは、あらゆる入力に対して計算が容易であるが、ランダムな入力のイメージが与えられた場合には逆関数の計算が困難な関数のことである。ここで、「容易」および「困難」は、計算複雑性理論、具体的には多項式時間問題の理論の意味で理解される。関数が一方向性であるとは、1対1でないことが十分であるとは考えられない（以下の理論的定義を参照）。

このような一方向性関数の存在は未だに未解決の仮説である。その存在は複雑性クラス PとNPが等しくないことを証明し、理論計算機科学の最大の未解決問題を解決する。^{[1] : 例2.2、70ページ}逆は真であるとは知られていない。つまり、P≠NPの証明の存在は一方向性関数の存在を直接意味しない。^[2]

応用分野では、「簡単」と「難しい」という用語は通常、特定のコンピューティング エンティティに関連して解釈されます。つまり、通常は「正当なユーザーにとっては十分に安価」で「悪意のあるエージェントにとっては法外に高価」です。 ^[要出典]この意味での一方向性関数は、暗号化、個人識別、認証、およびその他のデータ セキュリティアプリケーションの基本ツールです。この意味での一方向性関数の存在も未解決の推測ですが、数十年にわたる厳しい調査に耐えてきた候補がいくつかあります。それらのいくつかは、世界中の ほとんどの通信、電子商取引、電子銀行システムに不可欠な要素です。

関数f  : {0, 1} ^* → {0, 1} ^*が一方向性であるとは、関数 f が多項式時間アルゴリズムで計算できるが、関数fの擬似逆関数を計算しようとする多項式時間ランダム化アルゴリズムはいずれも、ほとんど確率を 持たずに成功する場合をいう。(上付き文字 * は任意の繰り返し回数を意味する。クリーネスターを参照。) つまり、すべてのランダム化アルゴリズム 、すべての正の整数c、および十分に大きいすべてのn = length( x ) について、 ${\displaystyle F}$${\displaystyle F}$

${\displaystyle \Pr[f(F(f(x)))=f(x)]<n^{-c},}$

ここで確率は{0, 1}  ⁿ上の離散一様分布からxを選択する確率であり、ランダム性は^[3]である。${\displaystyle F}$

この定義では、関数は最悪の場合ではなく、平均的な場合に「逆変換が困難」でなければならないことに注意してください。これは、複雑性理論の多く (たとえば、NP 困難性) とは異なります。複雑性理論では、「困難」という用語は最悪の場合を意味します。そのため、一方向性関数の候補 (以下で説明) の一部がNP 完全であることがわかっていても、それが一方向性を意味するわけではありません。後者の特性は、問題を解決するための既知のアルゴリズムが不足していることにのみ基づいています。

一方向関数にするには、関数を「損失がある」（1対1ではない）ものにするだけでは不十分です。特に、長さnの任意の入力に対してn 個のゼロの文字列を出力する関数は、同じ出力になる入力を簡単に考え出すことができるため、一方向関数ではありません。より正確には、ゼロの文字列を単純に出力する関数の場合、入力 f ( x ) に対して長さ n の任意の文字列を出力するアルゴリズムFは、出力文字列を見つけるために最初に使用された入力でなくても、出力の適切な原像を「見つけ」ます。

一方向性置換は、一方向性関数であり、また置換でもあります。つまり、一方向性関数は全単射です。一方向性置換は重要な暗号プリミティブですが、一方向性関数の存在によって一方向性置換の存在が暗示されるかどうかはわかっていません。

トラップドア一方向性関数またはトラップドア順列は、特殊な種類の一方向性関数です。このような関数は、トラップドアと呼ばれる秘密の情報が知られていない限り、逆関数にすることは困難です。

衝突のないハッシュ関数 fは、衝突耐性も備えた一方向関数である。つまり、ランダム化多項式時間アルゴリズムでは、無視できない確率で衝突（f ( x ) = f ( y )となる異なる値x、y）を見つけることができない。^[4]

fが一方向関数である場合、 fの逆関数は、出力を計算するのは困難 (定義により) ですが、チェックは容易 ( f を計算するだけで) な問題になります。したがって、一方向関数の存在は、FP  ≠  FNPを意味し、これは P ≠ NP を意味します。ただし、 P ≠ NP は一方向関数の存在を意味するものではありません。

一方向関数の存在は、次のような他の多くの有用な概念の存在を意味します。

• 疑似乱数ジェネレータ
• 擬似ランダム関数族
• ビットコミットメントスキーム
• 秘密鍵暗号化方式は適応型選択暗号文攻撃に対して安全である
• メッセージ認証コード
• デジタル署名方式（適応型選択メッセージ攻撃に対して安全）

以下は、一方向関数の候補です (2009 年 4 月現在)。明らかに、これらの関数が実際に一方向であるかどうかは不明ですが、これまでの広範な研究でも、いずれの関数に対しても効率的な逆変換アルゴリズムは生成されていません。^{[引用が必要]}

関数f は、2 進表記の2 つの素数pとq を入力として受け取り、それらの積を返します。この関数は、入力の合計ビット数をbとすると、 O ( b ² )時間で「簡単に」計算できます。この関数を反転するには、指定された整数Nの因数を見つける必要があります。既知の最良の因数分解アルゴリズムは、N を表すために必要なビット数を b とすると、 O ( b 2 ) 時間で実行されます。 ${\displaystyle O\left(\exp {\sqrt[{3}]{{\frac {64}{9}}b(\log b)^{2}}}\right)}$

この関数は、pとq が半素数の適切な集合にわたって範囲をとることを許可することで一般化できます。ランダムに選択された整数p、q > 1に対しては、 f は一方向ではないことに注意してください。これは、積の因数が 2 になる確率が 3/4 になるためです (任意のpが奇数である確率は 1/2 であり、qについても同様であるため、これらを独立に選択すると、両方が奇数である確率は 1/4 になります。したがって、 p または q が偶数である確率は1 − 1/4 = 3/4です)。

ラビン関数^[1]：⁵⁷または を法とする2乗（ pとqは素数）は、一方向性関数の集合であると考えられている。 ${\displaystyle N=pq}$

${\displaystyle \operatorname {ラビン} _{N}(x)\triangleq x^{2}{\bmod {N}}}$

Nを法とする二乗を表す:ラビンコレクションの特定のメンバー。平方根を抽出すること、つまりラビン関数の逆関数は、計算上N を因数分解することと同等である (多項式時間削減の意味で) ことが示されます。したがって、因数分解が困難な場合にのみ、ラビンコレクションは一方向性であることが証明できます。これは、pとqが同じビット長である特殊なケースにも当てはまります。ラビン暗号システムは、このラビン関数が一方向性であるという仮定に基づいています。

モジュラー指数演算は多項式時間で実行できます。この関数の逆関数を求めるには、離散対数を計算する必要があります。現在、基になる離散対数を多項式時間で計算するアルゴリズムが知られていない、いくつかの一般的なグループがあります。これらのグループはすべて有限アーベル群であり、一般的な離散対数問題は次のように記述できます。

G を濃度 nの有限アーベル群とする。群演算を乗算で表す。原始元 α ∈ Gと別の元β ∈ Gを考える。離散対数問題は、1 ≤ k ≤ nとなる正の整数k を求めることである。

${\displaystyle \alpha ^{k}=\underbrace {\alpha \cdot \alpha \cdot \ldots \cdot \alpha } _{k\;\mathrm {times} }=\beta }$

方程式α ^k = βを解く整数k は、 αを底とするβの離散対数と呼ばれます。k = log _α βと書きます。

離散対数暗号における群Gの一般的な選択肢は、巡回群( Z _p ) ^× (例: ElGamal 暗号化、Diffie-Hellman 鍵交換、デジタル署名アルゴリズム) と有限体上の楕円曲線の巡回部分群(楕円曲線暗号を参照) です。

楕円曲線は、 y ² = x ³ + ax + bを満たす体の元のペアの集合です。曲線の元は、「点の加算」と呼ばれる演算（体の加算演算とは異なります）によって群を形成します。点Pと整数kの乗算kP（つまり、整数の加法群の群作用）は、点をそれ自体に繰り返し加算することとして定義されます。kとPがわかっている場合は、 R = kPを計算するのは簡単ですが、RとPだけがわかっている場合は、 k を計算するのは困難であると考えられます。

SHA 256など、計算が高速な暗号ハッシュ関数は数多くあります。より単純なバージョンのいくつかは高度な分析に屈しましたが、最も強力なバージョンは、一方向の計算のための高速で実用的なソリューションを提供し続けています。これらの関数の理論的なサポートのほとんどは、以前に成功した攻撃の一部を阻止するためのテクニックです。

一方向関数の他の候補としては、ランダム線形コードの復号の困難性、特定の格子問題の困難性、部分集合和問題（ナッカシュ・シュテルンナップザック暗号システム）などが挙げられます。

一方向関数が存在する場合のみ、一方向であることが証明された明示的な関数fが存在する。 ^[5]言い換えれば、任意の関数が一方向であれば、fも一方向である。この関数は、最初に証明された組み合わせ的完全一方向関数であるため、「普遍的な一方向関数」として知られている。したがって、一方向関数を見つける問題は、おそらく非構成的に、そのような関数が存在することを証明することに帰着する。

多項式時間制限付きコルモゴロフ複雑性が平均的にやや困難である場合、一方向性関数も存在します。一方向性関数の存在は、多項式時間制限付きコルモゴロフ複雑性が平均的にやや困難であることを意味するため、この関数は普遍的な一方向性関数です。^[6]

• 一方向圧縮機能
• 暗号ハッシュ関数
• 幾何学的暗号
• トラップドア機能

• Jonathan Katz、Yehuda Lindell (2007)。現代暗号入門。CRC Press。ISBN 1-58488-551-3。 
• マイケル・シプサー（1997年）。計算理論入門。PWS出版。ISBN 978-0-534-94728-6。セクション10.6.3: 一方向関数、374〜376ページ。
• Christos Papadimitriou (1993)。計算複雑性（第 1 版）。Addison Wesley。ISBN 978-0-201-53082-7。セクション12.1: 一方向関数、pp. 279–298。