計算困難性の仮定

私たちはその仮定を言う${\displaystyle A}$仮定よりも強い${\displaystyle B}$いつ${\displaystyle A}$暗示する${\displaystyle B}$（そしてその逆は偽または不明である）。言い換えれば、仮定が${\displaystyle A}$仮定が間違っていた${\displaystyle B}$仮定は依然として真実である可能性があり、暗号プロトコルは${\displaystyle B}$それでも安全に使用できる可能性がある。したがって、暗号プロトコルを考案する際には、可能な限り弱い仮定を用いて安全性を証明できることが望まれる。

平均ケースの仮定は、特定の問題が明示的な分布から得られるほとんどのインスタンスで困難であることを示すのに対し、最悪ケースの仮定は、問題が一部のインスタンスで困難であることを示すだけです。ある問題については、平均ケースの困難性は最悪ケースの困難性を意味するため、同じ問題に対しては、平均ケースの困難性の仮定は最悪ケースの困難性の仮定よりも強いと言えます。さらに、比較不可能な問題であっても、指数時間仮説のような仮定は、植え付けクリーク予想のような平均ケースの仮定よりも好ましいと考えられることがよくあります。^{[ 1 ]}しかし、暗号アプリケーションでは、問題に困難なインスタンスが存在すること（問題が最悪ケースで困難であること）を知っていても、困難なインスタンスを生成する方法がわからないため、役に立ちません。^{[ 2 ]}幸いなことに、暗号で使用される多くの平均ケースの仮定（RSA、離散対数、およびいくつかの格子問題を含む）は、最悪ケースから平均ケースへの還元によって最悪ケースの仮定に基づいて構築できます。^{[ 3 ]}

計算困難性の仮定の望ましい特性は反証可能性、つまり仮定が偽であればそれを証明できるということです。特に、Naor (2003)は暗号学的反証可能性の形式的な概念を導入しました。^{[ 4 ]}大まかに言うと、計算困難性の仮定は、チャレンジ、つまり攻撃者と効率的な検証者の間の対話型プロトコルの観点から定式化できる場合に反証可能であると言われます。このプロトコルでは、効率的な攻撃者は、仮定が偽である場合に限り、検証者に受け入れるよう説得することができます。

合成整数が与えられた場合${\displaystyle n}$、特に2つの大きな素数の積であるもの${\displaystyle n=p\cdot q}$整数因数分解問題は、${\displaystyle p}$そして${\displaystyle q}$（より一般的には、素数を見つける）${\displaystyle p_{1},\dots ,p_{k}}$そのため${\displaystyle n=\prod _{i}p_{i}}$)表現のサイズの多項式時間で実行される整数因数分解アルゴリズムを見つけることは、大きな未解決問題です (${\displaystyle \log n}$多くの暗号プロトコルの安全性は、整数因数分解が困難である（つまり、多項式時間で解けない）という仮定に基づいています。この仮定と同等の安全性を持つ暗号システムには、ラビン署名や岡本・内山暗号システムなどがあります。さらに多くの暗号システムは、 RSA、剰余問題、φ隠蔽など、より強力な仮定に基づいています。

与えられた要素${\displaystyle a}$そして${\displaystyle b}$グループから${\displaystyle G}$離散対数問題では整数が求められる${\displaystyle k}$そのため${\displaystyle a=b^{k}}$離散対数問題は整数因数分解に匹敵するとは知られていないが、それらの計算複雑性は密接に関連している。

離散対数問題に関連するほとんどの暗号プロトコルは、実際にはより強力なディフィー・ヘルマン仮定に依存しています。${\displaystyle g,g^{a},g^{b}}$、 どこ${\displaystyle g}$はジェネレーターであり、${\displaystyle a,b}$ランダムな整数なので、見つけるのは難しい${\displaystyle g^{a\cdot b}}$この仮定を用いるプロトコルの例としては、オリジナルのディフィー・ヘルマン鍵交換や、より強力な決定型ディフィー・ヘルマン（DDH）方式に基づくエルガマル暗号などが挙げられる。

格子上の最も基本的な計算問題は最短ベクトル問題 (SVP)です。格子が与えられたとき、${\displaystyle L}$最短の非ゼロベクトルを見つける${\displaystyle v\in L}$ほとんどの暗号システムでは、最短独立ベクトル問題（SIVP）、GapSVP ^{[ 10 ]}、Unique-SVP ^{[ 11 ]}などの SVP の変種に対してより強い仮定が必要となります。

暗号学において最も有用な格子困難性の仮定は、エラーを伴う学習(LWE) 問題に関するものです。${\displaystyle (x,y)}$、 どこ${\displaystyle y=f(x)}$ある線形関数に対して${\displaystyle f(\cdot )}$学ぶのは簡単です${\displaystyle f(\cdot )}$線形代数を使用する。LWE問題では、アルゴリズムへの入力にはエラーがあり、つまり各ペアに対して${\displaystyle y\neq f(x)}$わずかな確率で。誤差は（適切なパラメータの場合）問題を扱いにくくすると考えられています。特に、SVP の変種から最悪ケースから平均ケースへの削減が知られています。^{[ 12 ]}

量子コンピュータにとって、因数分解や離散対数問題は容易だが、格子問題は困難であると推測されている。^{[ 13 ]}このため、格子ベースの暗号システムの中には、ポスト量子暗号の候補となるものもある。

格子問題の困難性を利用する暗号システムには、以下のようなものがある。

• NTRU ( NTRUEncryptとNTRUSign の両方)
• 完全準同型暗号の候補のほとんど

多くの最悪のケースの計算問題は、ある複雑性クラスにおいては困難または完全であることが知られている。${\displaystyle C}$特にNP困難（ただし、PSPACE困難、PPAD困難などにも該当することが多い）。これは、少なくともそのクラスのどの問題よりも難しいことを意味する。${\displaystyle C}$問題が発生した場合${\displaystyle C}$計算困難性仮定が満たされない限り、（多項式時間還元に関して）多項式時間アルゴリズムでは解くことができない。${\displaystyle P\neq C}$誤りです。

指数時間仮説（ETH）は、${\displaystyle P\neq NP}$困難性仮定とは、ブール充足可能性問題（SAT）には多項式時間アルゴリズムが存在しないだけでなく、指数時間（${\displaystyle 2^{\オメガ (n)}}$^{[ 17 ]}さらに強い仮定である強指数時間仮説（SETH）では、${\displaystyle k}$-SATは${\displaystyle 2^{(1-\varepsilon _{k})n}}$時間、${\displaystyle \lim _{k\rightarrow \infty }\varepsilon _{k}=0}$ETH、SETH、および関連する計算困難性の仮定により、例えば多項式時間と準多項式時間^{を区別する結果[} 1 ^]や、${\displaystyle n^{1.99}}$対${\displaystyle n^{2}}$[ ^{18 ]このような仮定は、}パラメータ化された複雑性においても有用である。^{[ 19 ]}

計算問題の中には、特定のインスタンス分布において平均的に難しいと想定されるものがある。例えば、植栽クリーク問題では、入力はエルデシュ・レニーランダムグラフをサンプリングし、そこにランダムなグラフを「植える」ことによって得られるランダムグラフである。${\displaystyle k}$- 仲間、つまり、つながり${\displaystyle k}$一様ランダムなノード（${\displaystyle 2\log _{2}n\ll k\ll {\sqrt {n}}}$）そして目標は植えられたものを見つけることです${\displaystyle k}$-クリーク（whp は一意です）。^{[ 20 ]}もう 1 つの重要な例は、 3-SATのランダムなインスタンスに関する計算困難性の仮定であるFeigeの仮説です(節と変数の特定の比率を維持するようにサンプリングされています)。^{[ 21 ]}平均ケースの計算困難性の仮定は、統計学のように入力に自然な分布があるアプリケーションで平均ケースの困難性を証明するのに役立ちます。^{[ 22 ]}さらに、植栽クリーク困難性の仮定は、指数時間仮説と同様に、他の問題の多項式と準多項式の最悪ケースの時間計算量を区別するためにも使用されています。^{[ 23 ]}

ユニークラベルカバー問題は制約充足問題であり、各制約は${\displaystyle C}$2つの変数を含む${\displaystyle x,y}$、そして各値について${\displaystyle x}$独自の価値がある${\displaystyle y}$満たす${\displaystyle C}$すべての制約を満たすことができるかどうかを判断するのは簡単ですが、ユニークゲーム予想(UGC) は、ほぼすべての制約を満たすことができるかどうかを判断するのは簡単ではないと仮定しています (${\displaystyle (1-\varepsilon )}$任意の定数に対する分数${\displaystyle \varepsilon >0}$）は満たされるか、ほとんど満たされないか（${\displaystyle \varepsilon }$-fraction) を満たすことができるのは NP 困難です。^{[ 16 ]}近似問題は UGC を仮定すると NP 困難であることがよく知られています。このような問題は UG 困難と呼ばれます。特に、UGC を仮定すると、多くの重要な問題に対して最適な近似保証を達成する半正定値計画アルゴリズムが存在します。^{[ 24 ]}

与えられたセット${\displaystyle n}$3SUM問題は、合計がゼロになる3つの数の組み合わせが存在するかどうかを問う問題です。3SUMには2次時間アルゴリズムが存在し、3SUMを「真に2次時間未満」で解くアルゴリズムは存在しないと予想されています。3SUM予想とは、3SUMを解くアルゴリズムが存在しないという計算困難性の仮定です。${\displaystyle O(n^{2-\varepsilon })}$-3SUM の時間アルゴリズム (任意の定数に対して)${\displaystyle \varepsilon >0}$この予想は、主に計算幾何学におけるいくつかの問題に対して、ほぼ二次的な下限を証明するのに役立ちます。^{[ 27 ]}