NPを打ち負かすのが難しいと思われる公開鍵暗号化アルゴリズムはありますか？ [閉まっている]

Question

実用的な量子コンピューティングが現実になった場合、整数因数分解や離散対数ではなく、NP完全問題に基づいた公開鍵暗号アルゴリズムがあるかどうか疑問に思います。

編集：

「計算複雑性理論における量子コンピューティング」をご覧ください。のセクション 量子コンピューターに関するWiki記事。量子コンピューターが答えることができる問題のクラス（BQP ）は、NP完全よりも厳密に簡単であると考えられています。

編集2：

「NP完全に基づく」は、私が興味を持っていることを表現するのに悪い方法です。

私が尋ねようとしたのは、暗号化を破るための任意の方法を使用して根本的なNP完全問題を破ることができるというプロパティを持つ公開キー暗号化アルゴリズムです。つまり、暗号化を破るとP = NPであることが証明されます。

Answer 1

この古いスレッドには非常に一般的で重要な質問であり、ここでの回答はすべて不正確だからです。

元の質問に対する短い答えは、明確な「いいえ」です。 NP完全問題に基づいた既知の暗号化スキーム（公開キーはもちろん）はありません（したがって、それらすべては、多項式時間の削減の下で）。一部は「より近い」ものですただし、他の人は、詳しく説明します。

ここで明確にすることはたくさんあるので、「NP完全問題に基づいて」の意味から始めましょう。これについての一般的に合意された解釈は、「NP完全問題の多項式時間アルゴリズムが存在しないと仮定して、特定の形式モデルで安全であることが証明できる」です。さらに正確に言うと、NP完全問題を常に解決するアルゴリズムは存在しないと仮定します。これは非常に安全な仮定です。これはアルゴリズムにとって非常に難しいことです。問題のランダムなインスタンスを高い確率で解決するアルゴリズムを考え出すことは、一見非常に簡単なようです。

ただし、暗号化スキームにはこのような証明はありません。わずかな例外（下記参照）を除いて文献を見ると、セキュリティ定理は次のようになります。

  

定理：この暗号化スキームは、   多項式時間アルゴリズムは   問題Xのランダムなインスタンスの解決。

「ランダムインスタンス」に注意してください。部。具体例として、2つのランダムなnビット素数の積を何らかの確率で因数分解するための多項式時間アルゴリズムが存在しないと仮定する場合があります。これは、2つのランダムなnビット素数の all 積を因数分解する always のための多項式時間アルゴリズムが存在しないという仮定とは非常に異なります（安全性は低い）。

＆quot;ランダムインスタンス＆quot;対「最悪の場合のインスタンス」問題は、上記のいくつかのレスポンダーをつまずかせたことです。 McElieceタイプの暗号化スキームは、線形コードをデコードする非常に特別なランダムバージョンに基づいており、NP完全である実際の最悪のバージョンには基づいていません。

この「ランダムインスタンス」を超えてプッシュするこの問題は、理論的なコンピューターサイエンスのいくつかの深くて美しい研究を必要としました。 MiklósAjtaiの仕事から始めて、セキュリティの仮定が「最悪のケース」である暗号化アルゴリズムを見つけました。 （より安全な）ランダムなケースではなく仮定。残念ながら、最悪の場合の仮定は、NP完全であることが知られていない問題に関するものであり、いくつかの理論的証拠は、NP完全問題を使用するようにそれらを適応できないことを示唆しています。興味のある方は、「格子ベースの暗号化」をご覧ください。

Answer 2

NP困難問題に基づく暗号システムがいくつか提案されています（ Merkle-Hellman サブセットサム問題に基づく暗号システム、および Naccache-Sternナップザック暗号システムベースナップザックの問題について）、しかし、それらはすべて壊れています。どうしてこれなの？スコットアーロンソンの理論的コンピュータサイエンスの素晴らしいアイデアの講義16これについて何かを言います。次のとおりです。

理想的には、セキュリティがNP完全問題に基づいている[暗号化擬似乱数ジェネレータ]または暗号システムを構築します。残念ながら、NP完全問題は常に最悪の場合に関するものです。暗号では、これは＆＃8220; 存在するのようなメッセージを解読するのが難しいというメッセージに変換しますが、これは暗号システムの良い保証ではありません！メッセージは、圧倒的な確率で解読するのが難しいはずです。数十年の努力にもかかわらず、NP完全問題の最悪ケースを平均ケースに関連付ける方法はまだ発見されていません。そして、これが計算上安全な暗号システムが必要な場合、P＆＃8800; NPよりも強い仮定をする必要がある理由です。

Answer 3

これは1998年の未解決の質問でした：

Pを前提とした暗号化の可能性について！ = NP Oded Goldreich、Rehovot Israel、Shafi Goldwasser

要約から：＆quot;私たちの結論は、質問は未解決のままだということです＆quot;。

-過去10年間でそれが変わったのだろうか？

編集：

私が知る限り、質問はまだ開かれていますが、そのようなアルゴリズムは存在しないという答えへの最近の進歩があります。

Adi Akavia、Oded Goldreich、Shafi Goldwasser、およびDana Moshkovitzが2006年にACMでこの論文を公開しました： NP硬度に基づく一方向関数に基づく＆quot;主な調査結果は、次の2つの否定的な結果です＆quot;

スタンフォードのサイト Complexity Zoo は、これら2つの否定的な結果の意味を説明するのに役立ちます。

Answer 4

多くのフォームが壊れていますが、 Merkle-Hellman をチェックしてください。 NP完全な「ナップザック問題」の形式。

Answer 5

ラティス暗号は、平均ケースを破ることが特定のNPハード問題（通常、最短ベクトル問題または最も近いベクトル問題）を解くのと同じくらい難しい暗号システムを実際に設計できる（過剰な）一般化された持ち帰りメッセージを提供します。

http://eprint.iacr.org/2008/521の紹介セクションを読むことをお勧めします。 暗号化システムへの参照を追跡します。

また、 http：//www.cs.ucsdの講義ノートを参照してください。 edu /〜daniele / CSE207C / 、必要に応じて本のリンクを追跡します。

Answer 6

NP完全および公開キー暗号化のグーグル検索では、実際には安全ではない誤検知が見つかります。この漫画のPDF は、 最小支配セットの問題に基づく公開鍵暗号化アルゴリズム。さらに読むと、アルゴリズムが安全であるとうそをつきます...根本的な問題はNP完全ですが、PKアルゴリズムでの使用は難易度を維持しません。

別の誤検出Google検索： CryptoのGoldreich-Goldwasser-Halevi暗号システムの暗号解析 ' 97 。要約から：

Crypto '97で、Goldreich、Goldwasser、およびHaleviは、NP困難であることが知られている格子内の最も近いベクトル問題に基づく公開鍵暗号システムを提案しました。暗号文がプレーンテキストの情報を漏らし、暗号文を解読する問題は、一般的な問題よりもはるかに簡単な特別な最も近いベクトルの問題に還元できるという、2つの意味を持つスキームの設計に大きな欠陥があることを示します。

Answer 7

あなたの興味に関連するウェブサイトがあります：ポスト量子暗号。

Answer 8

これが私の推論です。間違っている場合は修正してください。

（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 （その賛辞）NPでは、-Lはco-NPにあります----つまりL = --LはNPにあります。）

（iii）NP！= co-NPと一般に信じられていると考えます、そうでなければ、ブール式が満足できないという多項式サイズの証明があります。

結論：複雑さの理論的推測は、NP-hard暗号システムが存在しないことを意味します。

（それ以外の場合、NPとco-NPにNP困難な問題があります。NP= co-NP ---これは偽と考えられます。）

Answer 9

RSAおよびその他の広く使用されている暗号化アルゴリズムは、整数因数分解の難しさに基づいていますが（NP完全ではないことが知られています）、NP完全問題に基づく公開鍵暗号アルゴリズムもいくつかあります。 「公開鍵」のGoogle検索および「np-complete」それらのいくつかを明らかにします。

（量子コンピューターがNP完全問題を高速化すると前に間違って言ったが、これは真実ではない。私は訂正した。）

Answer 10

他の多くのポスターで指摘されているように、NPハード問題またはNP完全問題に基づいて暗号化を行うことは可能です。

ただし、暗号化の一般的な方法は、難しい数学（つまり、解読が困難）に基づいています。真実は、NP困難な問題を解決する標準化された文字列を作成するよりも、従来のキーとして数値をシリアル化する方が簡単だということです。したがって、実用的な暗号は、NP困難またはNP完全であることがまだ証明されていない数学的問題に基づいています（したがって、これらの問題の一部はPにあると考えられます）。

ElGamalまたはRSA暗号化では、暗号化を解除するには離散対数を解読する必要があるため、この wikipedia 記事。

  

一般的な離散対数logbgを計算するための効率的なアルゴリズムは知られていません。単純なアルゴリズムは、希望するgが見つかるまでbをより高いk乗することです。これは、試行乗算と呼ばれることもあります。このアルゴリズムは、グループGのサイズで線形の実行時間を必要とするため、グループのサイズで桁数の指数関数的です。ただし、Peter Shorによる効率的な量子アルゴリズムが存在します（ http://arxiv.org/abs/ quant-ph / 9508027 ）。

     

離散対数の計算は明らかに困難です。最悪の場合の効率的なアルゴリズムが知られていないだけでなく、ランダムな自己還元性を使用すると、平均的な場合の複雑さは少なくとも最悪の場合と同じくらい難しいことがわかります。

     

同時に、離散べき乗の逆問題はありません（たとえば、2乗によるべき乗を使用して効率的に計算できます）。この非対称性は、整数因数分解と整数乗算の間の非対称性に類似しています。両方の非対称性が暗号システムの構築に活用されています。

広く普及しているのは、これらはNP完全なものであるということですが、それは証明できないかもしれません。量子コンピューターは暗号を効率的に破る可能性があることに注意してください！

Answer 11

質問に本当に誰も答えなかったので、ヒントを提供しなければなりません：＆quot; McEliece＆quot;。いくつかの検索を行います。実績のあるNP-Hard暗号化アルゴリズム。 O（n ^ 2）暗号化および復号化時間が必要です。サイズがO（n ^ 2）の公開キーもありますが、これは良くありません。しかし、これらすべての限界を下げる改善があります。