証明可能なセキュリティ – ウィキペディア

証明可能なセキュリティ 現代の暗号学の概念です。暗号化の歴史には、発明者によって安全であると考えられていたが、まだ壊れている可能性があるシステムの多くの例があります。したがって、正式な方法で証明することにより、システムの安全性を自分自身に納得させることが望ましいです。これを行うには、暗号化システムと達成されるセキュリティの両方を正式化する必要があります。

クロード・シャノンは1949年を定義しました 完全に安全です 暗号化方法と、それらが存在する条件を示しました。完全に安全な暗号化プロセスは、それで生成された重要なテキストが、対応するプレーンテキストについて結論を導き出さないという事実によって特徴付けられます。このような手順では、キーテキストを知っている攻撃者が、プレーンテキストの長さを除いて、それに関するさらなる情報を取得できないことが数学的に証明されています。したがって、彼は重要なテキストを解読したり、手順全体を破ることさえできません。シャノンは、1回限りのパッドが完全に安全であることを証明することができました。 ^[初め]

情報の理論的証拠は、コンピューティング能力に限定されていない攻撃者に対するセキュリティも保証します。ただし、そのような攻撃者は、AESのような手順であらゆる種類のキーを試してみることができます。ただし、実際のコンピューターでは、これには時間がかかりすぎます。したがって、セキュリティの概念をより現実的にするために、攻撃者は、使用されるキーの長さ（または安全パラメーター）に応じて、彼のコンピューティング能力が制限されています。次に、このような攻撃者に対してシステムが安全であることが示されます。攻撃者の努力は、ユーザーの努力よりもはるかに速く成長することが示されています。キーの長さを選択することにより、攻撃を実質的に除外できます。ただし、キーの長さは、利用可能なコンピューティングパワーに適応する必要があります。これは、RSAに使用される768ビットのキー長が安全でないと見なされるという事実の1つです。ここでは漸近挙動のみが検討されるため、セキュリティは漸近または複雑さ理論とも呼ばれます。

ほとんどの暗号化手順では、システムの安全性は、さらなる仮定なしでは証明することはできません。使用される最も初期の仮定の1つは、因数分解の問題が困難であるということです。セキュリティの証明は、システムを破壊して問題を解決することとの間の減少です。たとえば、RSA暗号システムの公開鍵から秘密を計算できるすべての攻撃者は、因数分解問題を解決できることも証明できます（より正確には、成功した攻撃者は効率的なはんだを構築できます）。ただし、そのような恋人は存在できないため、攻撃者が成功することはできません。したがって、セキュリティはもはや攻撃者がシステムを破ることは完全に不可能であることを意味しませんが、これは実際には不可能です。言い換えれば、彼の成功の可能性は無視できます。

漸近安全証拠の場合、システムは安全パラメーターの特定の値（キー長）から安全であることのみが示されています。このようなシステムを植え付けたい場合は、特定のパラメーターを選択する必要があります。これを行うには、証明をより正確に実行する必要があり、使用するリソース（期間、Oracle Quinquiresの数）に応じて攻撃者の成功の確率のために、厳しいトップバリアが与えられます。そのような依存関係を与えることができる場合、具体的なセキュリティについて話します。

Elgamal暗号化プロセスは、決定的なDiffie-Hellmanの問題が困難であると仮定して、IND-CPAプルーフです。証拠は、システムの安全性に対するすべての成功した攻撃者からDDH問題のはんだが構築される削減で構成されています。 DDHは難しいと認められていたため、そのような攻撃者が存在できないことは明らかです。

彼がエルガマルに対するIND-CPA実験に勝ったことを除いて、攻撃者Aが知られています。だから彼が公開鍵を受け取った場合、彼は2つのメッセージを提供します

${displaystyle m_ {0}、m_ {1}}$

out。 1つが公開鍵の下の2つのうちの1つの暗号化を彼に与えた場合、彼は確率でできます

${displaystyle 1/2+epsilon}$

どのメッセージが暗号化されたかを言います。

この攻撃者から、次のようにDDHの恋人を構築します。これは、プロデューサーとグループの説明を受け取ります

${displaystyle g}$

そしてトリプル

${displaystyle（g^{x}、g^{y}、g^{z}）}$

入力として。 Sは、キープロダクションをシミュレートし、提供します

${displaystyle g^{x}}$

関連する秘密の鍵には、Aの公開鍵としてはわかりませんが、それを知ることはできません。しばらくすると2つのメッセージが表示されます

${displaystyle m_ {0}、m_ {1}}$

out。
Sは暗号化をシミュレートする必要があります。彼はランダムなビットを選択します

${displaystyle b}$

そして、暗号を追加します

${displaystyle g^{y}、g^{z} m_ {b}}$

。攻撃者Aは少し与えます

${displaystyle b ‘}$

戻る。
今でしょ

${displaystyle g^{z} = g^{xy}}$

したがって、暗号評議会は、通常生産されるものと区別することはできません。は

${displaystyle g^{z}}$

ランダムなグループ要素である攻撃者は、確率で1/2にアドバイスし、勝つことができます。したがって、sの文字列は次のとおりです。

${displaystyle g^{z} = g^{xy}}$

。 Aが間違っている場合、それはそれを想定しています

${displaystyle g^{z}}$

ランダムな要素でした。 Sの成功の確率が含まれています

${displaystyle 1/2+epsilon /2}$

。

証明可能なセキュリティのパラドックスは、安全であると証明されているシステムが必ずしも実際に安全ではないということです。これは、証拠にいくつかの仮定と形式化が必要であるという事実によるものです。システム、攻撃者、およびセキュリティの目標は、正式に（暗号化のためのIND-CPAセキュリティなど）記述する必要があり、その証明は、重大度が想定された問題の減少にすぎません。証拠で想定されている人よりも強い攻撃者は、システムを破る可能性があります。また、セキュリティの目標が十分に策定されていないこと、つまり攻撃者にとっては少ない成功で十分であることが起こります。たとえば、セキュリティの目標が「攻撃者が秘密のテキストからプレーンテキストを導き出すことができないはず」である場合、証拠は、プレーンテキストの最初の3文字だけを体験したい攻撃者について声明を出しません。もう1つの問題は、実際の暗号システムが正式なものを正確に描写していないことです。これは、既存のシステムの正式または形式化を実装するときにどちらのエラーが作成されたためです。システムを壊す可能性は低い方法は、セキュリティに基づいた数学的問題を解決することです。最後に、証拠はもちろん単に間違っていることができます。これらの多くの問題にもかかわらず、現代の暗号学における安全性の証拠は貴重なツールです。

1. ↑ クロード・シャノン： 秘密システムのコミュニケーション理論 。の： ベルシステムテクニカルジャーナル 。 バンド 28 、 いいえ。 4 、1949年、 S. 656–715 （ netlab.cs.ucla.edu [PDF; 549 KB ]）。