計算困難性の仮定

計算複雑性理論において、計算困難性仮定とは、特定の問題が効率的に解決できないという仮説です (ここで、効率的とは、通常、「多項式時間」を意味します)。本質的に有用な問題に対して (無条件に) 困難性を証明する方法はわかっていません。代わりに、コンピューター科学者は、新しい問題または複雑な問題の困難性を、よりよく理解されている問題に関する計算困難性仮定に正式に関連付けるために、縮 約に依存しています。

計算困難性の仮定は、暗号学において特に重要です。暗号学における主要な目標は、証明可能なセキュリティを備えた暗号プリミティブを作成することです。場合によっては、暗号プロトコルが情報理論的セキュリティを備えていることがわかっています。ワンタイム パッドは一般的な例です。ただし、情報理論的セキュリティは常に達成できるとは限りません。そのような場合、暗号学者は計算的セキュリティに頼ります。大まかに言えば、これは、すべての敵対者が実際にはそうであるように、敵対者が計算的に制限されていると仮定すると、これらのシステムが安全であることを意味します。

計算困難性の仮定は、アルゴリズム設計者を導くためにも役立ちます。単純なアルゴリズムでは、 P ≠ NPなどの十分に研究された計算困難性の仮定を反証することはほとんどありません。

コンピューター科学者は、どの困難性の仮定がより信頼できるかを評価するさまざまな方法を持っています。

が暗示される場合（そしてその逆は偽または不明の場合）、仮定は仮定より強いと言えます。言い換えれば、仮定が偽であっても、仮定は依然として真である可能性があり、仮定に基づく暗号化プロトコルは依然として安全に使用できる可能性があります。したがって、暗号化プロトコルを考案する場合、可能な限り最も弱い仮定を使用してセキュリティを証明できることが期待されます。 ${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle B}$

平均ケースの仮定は、特定の問題が、ある明示的な分布から見て、ほとんどのインスタンスで困難であることを示すのに対し、最悪ケースの仮定は、問題が一部のインスタンスで困難であることを示すだけです。与えられた問題では、平均ケースの困難さは最悪ケースの困難さを意味するため、平均ケースの困難さの仮定は、同じ問題に対する最悪ケースの困難さの仮定よりも強力です。さらに、比較できない問題であっても、指数時間仮説のような仮定は、植え付けられたクリーク予想のような平均ケースの仮定よりも好ましいと考えられることがよくあります。^[1] しかし、暗号アプリケーションでは、問題に何らかの困難なインスタンスがあること (最悪の場合に問題が困難である) を知っていても役に立ちません。なぜなら、困難なインスタンスを生成する方法を提供しないからです。^[2]幸いなことに、暗号で使用される多くの平均ケースの仮定 (RSA、離散対数、および一部の格子問題を含む) は、最悪ケースから平均ケースへの縮小によって、最悪ケースの仮定に基づくことができます。^[3]

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

使用されている暗号化の難しさの仮定は数多くあります。これは、最も一般的な仮定のいくつかと、それらを使用する暗号化プロトコルのリストです。

合成 整数 、特に 2 つの大きな素数の積である合成整数が与えられた場合、整数因数分解問題は、と を見つけること（より一般的には、となる素数 を見つけること）です。表現のサイズ ( ) の多項式の時間で実行される整数因数分解アルゴリズムを見つけることは、大きな未解決問題です。多くの暗号化プロトコルのセキュリティは、整数因数分解が困難である（つまり、多項式時間で解決できない）という仮定に依存しています。この仮定と同等のセキュリティを持つ暗号システムには、ラビン暗号システムや岡本–内山暗号システムがあります。RSA、残差問題、ファイ隠蔽など、より強い仮定に依存する暗号システムは他にもたくさんあります。 ${\displaystyle n}$ ${\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 問題です。この問題は難しいと推測されますが、 を因数分解すれば簡単になります。RSA暗号システムでは、は公開鍵、はメッセージ の暗号化、 の因数分解は復号化に使用する秘密鍵です。 ${\displaystyle n}$${\displaystyle e}$${\displaystyle c:=m^{e}(\mathrm {mod} \;n)}$${\displaystyle m}$${\displaystyle n}$${\displaystyle (n,e)}$${\displaystyle c}$${\displaystyle m}$${\displaystyle n}$

合成数と整数が与えられたとき、残差問題とは、 ${\displaystyle n}$${\displaystyle y,d}$${\displaystyle x}$

${\displaystyle x^{d}\equiv y{\pmod {n}}.}$

重要な特殊なケースとしては、二次残余問題と決定的合成残余問題があります。RSA の場合と同様に、この問題 (およびその特殊なケース) は困難であると推測されますが、 を因数分解すると簡単になります。残余問題の困難性に依存する暗号システムには、次のものがあります。 ${\displaystyle n}$

• Goldwasser-Micali 暗号システム(二次残余問題)
• Blum Blum Shub ジェネレータ(二次残差問題)
• Paillier暗号システム（決定的合成残余問題）
• ベナロー暗号システム（高位残差問題）
• ナカチェ・シュテルン暗号システム（高位残差問題）

合成数 の場合、そのオイラーのトーティエント関数 を効率的に計算する方法はわかっていません。ファイ隠蔽仮定は を計算することが困難であり、さらにの素因数を計算することさえ困難であると仮定しています。この仮定は Cachin–Micali–Stadler PIRプロトコルで使用されています。^[5]${\displaystyle m}$ ${\displaystyle \phi (m)}$${\displaystyle \phi (m)}$${\displaystyle \phi (m)}$

離散対数問題は、グループの要素と が与えられた場合、となる整数を求める問題です。離散対数問題は整数因数分解と比較できるかどうかはわかっていませんが、計算の複雑さは密接に関連しています。 ${\displaystyle a}$${\displaystyle b}$ ${\displaystyle G}$${\displaystyle k}$${\displaystyle a=b^{k}}$

離散対数問題に関連するほとんどの暗号化プロトコルは、実際にはより強力なDiffie-Hellman 仮定に依存しています。つまり、グループ要素 が与えられ、がジェネレータで、がランダムな整数である場合、 を見つけることは困難です。この仮定を使用するプロトコルの例には、オリジナルのDiffie-Hellman 鍵交換や、ElGamal 暗号化(さらに強力なDecisional Diffie-Hellman (DDH)バリアントに依存) などがあります。 ${\displaystyle g,g^{a},g^{b}}$${\displaystyle g}$${\displaystyle a,b}$${\displaystyle g^{a\cdot b}}$

多重線型写像とは、任意のおよびに対して、 ${\displaystyle e:G_{1},\dots ,G_{n}\rightarrow G_{T}}$${\displaystyle G_{1},\dots ,G_{n},G_{T}}$${\displaystyle g_{1},\dots ,g_{n}\in G_{1},\dots G_{n}}$${\displaystyle a_{1},\dots ,a_{n}}$

${\displaystyle e(g_{1}^{a_{1}},\dots ,g_{n}^{a_{n}})=e(g_{1},\dots ,g_{n})^{a_{1}\cdots a_{n}}}$。

暗号化アプリケーションでは、マップとグループ演算を効率的に計算できるようなグループとマップを構築したいが、離散対数問題は依然として困難である。^[6] 一部のアプリケーションでは、より強い仮定、例えばDiffie-Hellman仮定の多重線形類似体が必要となる。 ${\displaystyle G_{1},\dots ,G_{n},G_{T}}$${\displaystyle e}$${\displaystyle G_{1},\dots ,G_{n},G_{T}}$${\displaystyle G_{1},\dots ,G_{n}}$

の特殊なケースでは、信頼できるセキュリティを備えた双線形写像が、WeilペアリングとTateペアリングを使用して構築されています。^[7] については近年多くの構成が提案されていますが、その多くは破られており、現在のところ安全な候補についてのコンセンサスは得られていません。^[8]${\displaystyle n=2}$${\displaystyle n>2}$

多重線形困難性仮定に依存する暗号システムには次のものがあります。

• ボネ・フランクリン方式（双線形ディフィー・ヘルマン）
• Boneh–Lynn–Shacham (双線形ディフィー・ヘルマン)
• 判別不能難読化と機能的暗号化のためのGarg-Gentry-Halevi-Raykova-Sahai-Waters候補（多重線型ジグソーパズル）^[9]

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

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

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

格子問題の困難性に依存する暗号システムには次のものがあります。

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

暗号学への応用と同様に、困難性仮定は計算複雑性理論において、無条件に証明することが難しい数学的命題の証拠を提供するために用いられる。これらの応用では、命題自体が正しいことを証明するのではなく、困難性仮定が何らかの望ましい複雑性理論的命題を暗示していることを証明する。このタイプの仮定で最もよく知られているのはP ≠ NPという仮定であるが、^[14]他には指数時間仮説、^{[15] 、}植え付けられたクリーク予想、ユニークゲーム予想などがある。^[16]

多くの最悪の計算問題は、ある複雑性クラス、特にNP 困難(ただし、多くの場合PSPACE 困難、PPAD 困難など) に対して困難または完全であることが知られています。これは、それらの問題が少なくともそのクラスのどの問題と同じくらい難しいことを意味します。問題が-困難 (多項式時間削減に関して) である場合、計算困難性の仮定が偽でない限り、多項式時間アルゴリズムでは解決できません。 ${\displaystyle C}$${\displaystyle C}$${\displaystyle C}$${\displaystyle P\neq C}$

指数時間仮説 (ETH) は困難性仮定を強化したもので、ブール充足可能性問題(SAT) には多項式時間アルゴリズムがないだけでなく、指数時間 ( ) が必要であると推測しています。^[17] さらに強力な仮定である強い指数時間仮説(SETH)は、 -SAT には時間が必要であると推測しています。ここで。ETH、SETH、および関連する計算困難性仮定により、きめ細かい計算複雑性の結果を推論できます。たとえば、多項式時間と準多項式時間を区別する結果、^[1]または とを比較する結果などです。^{[18]このような仮定は、パラメーター化}された計算複雑性 にも役立ちます。^[19]${\displaystyle P\neq NP}$${\displaystyle 2^{\Omega (n)}}$${\displaystyle k}$${\displaystyle 2^{(1-\varepsilon _{k})n}}$${\displaystyle \lim _{k\rightarrow \infty }\varepsilon _{k}=0}$${\displaystyle n^{1.99}}$${\displaystyle n^{2}}$

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

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

ユニークラベルカバー問題と密接に関連しているのが、小集合拡張 (SSE)問題です。グラフが与えられた場合、 辺の拡張が最小となる頂点の小集合 (サイズ)を見つけます。SSE を近似するのが難しい場合、ユニークラベルカバーも近似することが難しいことが知られています。したがって、 SSE を近似するのが難しいと仮定する小集合拡張仮説 は、ユニークゲーム予想よりも強い (しかし密接に関連している) 仮定です。^[25] 一部の近似問題は SSE 困難であることが知られています^[26] (つまり、少なくとも SSE を近似するのと同じくらい困難)。 ${\displaystyle G=(V,E)}$${\displaystyle n/\log(n)}$

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

• セキュリティレベル