実用的な量子コンピューティングが実現した場合、整数因数分解や離散対数ではなく、NP 完全問題に基づく公開鍵暗号アルゴリズムが存在するかどうか疑問に思っています。
編集：
量子コンピューターに関する wiki 記事の「計算複雑性理論における量子コンピューティング」セクションを確認してください 。 量子コンピューターが解決できる問題のクラス (BQP) は、NP 完全よりも厳密に簡単であると考えられていることを指摘しています。
編集2：
「NP完全に基づく」は、私が興味を持っていることを表現する悪い方法です.
私が求めようとしていたのは、暗号を破るためのあらゆる方法を使用して、根底にある NP 完全問題を破ることができるという特性を持つ公開鍵暗号化アルゴリズムです。これは、暗号を破ると P=NP が証明されることを意味します。
これは非常に一般的で重要な質問であり、ここでの回答はすべて不正確であるため、私はこの古いスレッドに返信しています。
元の質問に対する短い答えは、明白な「NO」です。NP 完全問題に基づく既知の暗号化スキーム (公開鍵スキームは言うまでもなく) はありません (したがって、多項式時間削減の下でのすべての暗号化スキーム)。ただし、他のものよりも「近い」ものもありますので、詳しく説明しましょう。
ここで明確にしなければならないことがたくさんあるので、「NP 完全問題に基づく」という意味から始めましょう。これについて一般的に合意されている解釈は次のとおりです。さらに正確に言うと、NP 完全問題を常に解決するアルゴリズムは存在しないと仮定します。これはアルゴリズムにとって非常に難しいことなので、非常に安全な仮定です。問題のランダムなインスタンスを適切な確率で解決するアルゴリズムを考え出す方がはるかに簡単に思えます。
ただし、暗号化スキームにはそのような証明はありません。文献を見ると、ごくわずかな例外 (以下を参照) を除いて、セキュリティ定理は次のようになっています。
定理:この暗号化スキームは、ある問題 X のランダムなインスタンスを解くための多項式時間アルゴリズムが存在しないと仮定すると、安全であることが証明されてい ます。
「ランダムインスタンス」の部分に注意してください。具体的な例として、2 つのランダムな n ビットの素数の積をある程度の確率で因数分解するための多項式時間アルゴリズムが存在しないと仮定する場合があります。これは、2 つのランダムな n ビット素数のすべての積を常に因数分解するための多項式時間アルゴリズムが存在しないと仮定することとは (安全性が低く) 大きく異なります。
「ランダムなインスタンス」対「最悪のインスタンス」の問題は、上記のいくつかのレスポンダーをつまずかせているものです。McEliece タイプの暗号化スキームは、線形コードをデコードする非常に特別なランダム バージョンに基づいており、NP 完全である実際の最悪のケースのバージョンには基づいていません。
この「ランダムなインスタンス」の問題を解決するには、理論的なコンピューター サイエンスに関する深く美しい研究が必要です。Miklós Ajtai の研究から始めて、セキュリティの仮定がランダムなケースではなく「最悪のケース」(より安全な) の仮定である暗号化アルゴリズムを発見しました。残念ながら、最悪の仮定は NP 完全であることが知られていない問題に対するものであり、いくつかの理論的証拠は、それらを NP 完全問題を使用するように適応させることができないことを示唆しています。興味のある方は、「格子ベースの暗号化」を調べてください。
NP 困難な問題に基づくいくつかの暗号システム (部分和問題に基づくMerkle-Hellman暗号システム、ナップザック問題に基づくNaccache-Stern ナップザック暗号システムなど) が提案されていますが、それらはすべて壊れています。どうしてこれなの？Scott Aaronson's Great Ideas in Theoretical Computer Scienceの講義 16 は、これについて何かを述べています。それが言うことは次のとおりです。
理想的には、[Cryptographic Pseudorandom Generator] またはセキュリティが NP 完全問題に基づく暗号システムを構築したいと考えています。残念ながら、NP 完全問題は常に最悪のケースです。暗号化では、これは「解読するのが難しいメッセージが存在する」などのステートメントに変換されますが、これは暗号化システムにとって適切な保証ではありません! メッセージは、圧倒的な確率で解読するのが難しいはずです。何十年にもわたる努力にもかかわらず、NP完全問題の最悪のケースを平均的なケースに関連付ける方法はまだ発見されていません。これが、計算上安全な暗号システムが必要な場合、P≠NP よりも強力な仮定を行う必要がある理由です。
これは 1998 年には未解決の問題でした。
Oded Goldreich、Rehovot Israel、Shafi Goldwasser による、P != NP という仮定に基づく暗号化の可能性について
要約から：「私たちの結論は、問題は未解決のままであるということです」.
――ここ10年で変わったのかな？
編集：
私が知る限り、質問はまだ未解決であり、そのようなアルゴリズムは存在しないという答えに向けた最近の進歩があります。
Adi Akavia、Oded Goldreich、Shafi Goldwasser、および Dana Moshkovitzは、2006 年に ACM で次の論文を発表しました。
スタンフォードのサイト、 Complexity Zooは、これら 2 つの否定的な結果が何を意味するかを説明するのに役立ちます。
格子暗号は、（過度に）一般化された持ち帰りメッセージを提供します。実際、平均的なケースを破ることは、特定のNP困難な問題（通常、最短ベクトル問題または最も近いベクトル問題）を解決するのと同じくらい難しい暗号システムを設計できます。
http://eprint.iacr.org/2008/521の紹介セクションを読んでから、暗号システムへの参照を追跡することをお勧めします。
また、 http：//www.cs.ucsd.edu/~daniele/CSE207C/の講義ノートを参照し、必要に応じて本のリンクを追跡してください。
多くの形式が壊れていますが、NP 完全な「ナップザック問題」の形式に基づいたMerkle-Hellmanを調べてください。
NP 完全および公開鍵暗号化をグーグルで検索すると、実際には安全ではない偽陽性が見つかります。この漫画風の pdfは、最小支配集合問題に基づく公開鍵暗号化アルゴリズムを示しているように見えます。さらに読むと、アルゴリズムが安全であると嘘をつくことを認めます...根本的な問題はNP-Completeですが、PKアルゴリズムでの使用は難しさを維持しません。
もう 1 つの偽陽性の Google の発見: Crypto '97 の Goldreich-Goldwasser-Halevi 暗号システムの Cryptanalysis。要約から：
Crypto '97 で、Goldreich、Goldwasser、および Halevi は、NP 困難であることが知られている、格子内の最近接ベクトル問題に基づく公開鍵暗号システムを提案しました。スキームの設計には2つの意味を持つ大きな欠陥があることを示します.暗号文は平文の情報を漏らし、暗号文を復号化する問題は、一般的な問題よりもはるかに簡単な特別な最も近いベクトルの問題に縮小できます. .
これが私の推論です。私が間違っている場合は修正してください。
(i) NP および co-NP では、暗号システムを「破る」ことは必然的に問題になります。(暗号システムを破るには、1 対 1 で多項式時間で計算可能な暗号化関数を反転する必要があります。したがって、暗号文が与えられた場合、平文は多項式時間で検証できる証明書です。したがって、暗号文は NP と co-NP にあります。)
(ii) NP と co-NP に NP 困難な問題がある場合、NP = co-NP です。(この問題は NP 完全であり、co-NP にあります。任意の NP 言語はこの co-NP 言語に還元可能であるため、NP は co-NP のサブセットです。ここで対称性を使用します: co-NP の任意の言語 L には -L があります(その補数) NP で、ここで -L は co-NP にある--- つまり、L = --L は NP にある。)
(iii) NP != co-NP であると一般に信じられていると思います。それ以外の場合は、ブール式が充足可能でないという多項式サイズの証明があるためです。
結論: 複雑性理論の推測は、NP 困難な暗号システムが存在しないことを意味します。
(そうでなければ、NP と co-NP に NP 困難な問題があり、そこから NP = co-NP になります。これは誤りであると考えられています。)
あなたの興味に関連するかもしれない Web サイトがあります: Post-Quantum Cryptography .
他の多くのポスターで指摘されているように、暗号化はNP困難またはNP完全問題に基づいている可能性があります。
ただし、暗号化の一般的な方法は、難しい数学に基づいています（つまり、解読が困難です）。真実は、NP困難な問題を解決する標準化された文字列を作成するよりも、従来のキーとして数値をシリアル化する方が簡単であるということです。したがって、実用的な暗号化は、NP困難またはNP完全であることがまだ証明されていない数学的問題に基づいています（したがって、これらの問題のいくつかはPにあると考えられます）。
ElGamalまたはRSA暗号化では、それを破るには離散対数を破る必要があるので、このウィキペディアの記事を見てください。
一般的な離散対数logbgを計算するための効率的なアルゴリズムは知られていません。素朴なアルゴリズムは、目的のgが見つかるまで、bをますます高い累乗kに上げることです。これは、試行乗算と呼ばれることもあります。このアルゴリズムでは、グループGのサイズで線形の実行時間が必要であり、したがって、グループのサイズの桁数で指数関数的です。ただし、Peter Shorによる効率的な量子アルゴリズムが存在します（http://arxiv.org/abs/quant-ph/9508027）。
離散対数の計算は明らかに困難です。最悪の場合の効率的なアルゴリズムが知られていないだけでなく、ランダムな自己還元性を使用して、平均的な場合の複雑さを少なくとも最悪の場合と同じくらい難しいことを示すことができます。
同時に、離散べき乗の逆問題はそうではありません（たとえば、2乗によるべき乗を使用して効率的に計算できます）。この非対称性は、素因数分解と整数乗算の間の非対称性に類似しています。両方の非対称性は、暗号化システムの構築に利用されてきました。
これらはNP完全であると広く信じられていますが、証明できない可能性があります。量子コンピューターは暗号を効率的に破ることができることに注意してください！
RSA やその他の広く使用されている暗号化アルゴリズムは整数因数分解の難しさ (NP 完全であることが知られていない) に基づいていますが、NP 完全問題に基づいた公開鍵暗号アルゴリズムもいくつかあります。「公開鍵」と「np-complete」をグーグルで検索すると、それらのいくつかが明らかになります。
(以前、量子コンピューターは NP 完全問題を高速化すると誤って言いましたが、これは真実ではありません。私は訂正します。)
誰も実際に質問に答えなかったので、私はあなたにヒントを与えなければなりません：「マックエリス」。それでいくつかの検索を行います。その実績のあるNP困難な暗号化アルゴリズム。O（n ^ 2）の暗号化と復号化の時間が必要です。サイズO（n ^ 2）の公開鍵もありますが、これは悪いことです。しかし、これらすべての限界を下げる改善があります。