セマンティックセキュリティ

暗号学において、意味的に安全な 暗号システムとは、暗号文から平文に関するごくわずかな情報しか抽出できない暗号システムである。具体的には、あるメッセージの暗号文（任意のメッセージ分布から取得）とメッセージの長さが与えられたあらゆる確率的多項式時間アルゴリズム（PPTA）は、メッセージの長さのみにアクセスでき（暗号文にはアクセスできない）他のすべてのPPTAよりも無視できないほど高い確率でメッセージの部分的な情報を特定できない。^{[1]この概念は、}シャノンの完全秘密性の概念に類似した計算複雑性である。完全秘密性は、暗号文が平文に関する情報をまったく明らかにしないことを意味するが、意味的安全性は、明らかにされたいかなる情報も抽出できないことを意味する。^{[2] [3] : 378–381}${\displaystyle m}$

セマンティックセキュリティの概念は、1982年にゴールドワッサーとミカリによって初めて提唱されました。 ^{[1] [4]} しかし、彼らが最初に提案した定義では、実用的な暗号システムのセキュリティを証明するための直接的な手段が提供されていませんでした。その後、ゴールドワッサー/ミカリは、セマンティックセキュリティが、選択平文攻撃下での暗号文の区別不能性と呼ばれるセキュリティの別の定義と同等であることを実証しました。 ^[5] この後者の定義は、実用的な暗号システムのセキュリティの証明を容易にするため、セマンティックセキュリティの元の定義よりも一般的です。

対称鍵アルゴリズム暗号システムの場合、攻撃者は暗号文から平文に関する情報を計算できないようにする必要があります。これは、長さが同じ 2 つの平文とそれぞれの 2 つの暗号文が与えられた場合、攻撃者はどの暗号文がどの平文に属しているかを判断できないためと考えられます。

非対称鍵暗号化アルゴリズム暗号システムが意味的に安全であるためには、計算能力が制限された攻撃者が、暗号文とそれに対応する公開暗号化鍵のみを与えられた場合に、メッセージ (平文) に関する重要な情報を導き出すことが不可能でなければなりません。意味的セキュリティは、「受動的な」攻撃者、つまり、公開鍵と選択した平文を使用して暗号文を生成し、観察する攻撃者の場合のみを考慮します。他のセキュリティ定義とは異なり、意味的セキュリティは、攻撃者が選択した暗号文の復号を要求できる選択暗号文攻撃(CCA) の場合を考慮しません。また、意味的に安全な暗号化方式の多くは、選択暗号文攻撃に対して明らかに安全ではありません。したがって、意味的セキュリティは、汎用暗号化方式を保護するための条件としては不十分であると考えられています。

選択平文攻撃（IND-CPA ）による区別不能性は、一般的に次の実験によって定義されます。^[6]

1. を実行するとランダムなペアが生成されます。${\displaystyle (pk,sk)}$${\displaystyle Gen(1^{n})}$
2. 確率的多項式時間制限付き攻撃者に公開鍵が与えられ、攻撃者はそれを使用して任意の数の暗号文を生成できます（多項式制限内）。${\displaystyle pk}$
3. 攻撃者は 2 つの等しい長さのメッセージを生成し、公開鍵とともにチャレンジ オラクルへ送信します。${\displaystyle m_{0}}$${\displaystyle m_{1}}$
4. チャレンジ オラクルでは、公平なコインを投げて (ランダム ビットを選択) メッセージの 1 つを選択し、公開キーでメッセージを暗号化して、結果として得られるチャレンジ暗号文を敵対者に返します。${\displaystyle b\in \{0,1\}}$${\displaystyle m_{b}}$ ${\displaystyle c}$

敵対者が、オラクルによって 2 つのメッセージのどちらが選択されたかを判別できない場合、その確率はランダム推測の成功率より大幅に高いため、基礎となる暗号システムは IND-CPA です (したがって、選択平文攻撃に対して意味的に安全です)。この定義のバリエーションでは、選択暗号文攻撃と適応型選択暗号文攻撃( IND-CCA、IND-CCA2 ) に対する区別不可能性を定義します。${\displaystyle 1/2}$

上記のゲームでは、敵対者が公開暗号化キーを所有しているため、意味的に安全な暗号化方式は、定義上、確率的であり、ランダム性の要素を備えている必要があります。そうでない場合、敵対者は、との決定論的暗号化を計算し、これらの暗号化を返された暗号文と比較して、オラクルの選択を推測することができます。 ${\displaystyle m_{0}}$${\displaystyle m_{1}}$${\displaystyle c}$

意味的に安全な暗号化アルゴリズムには、Goldwasser-Micali、ElGamal、Paillierなどがあります。これらの方式は、その意味的安全性が何らかの難しい数学的問題 (たとえば、決定的 Diffie-Hellmanまたは2 次残差問題)を解くことに帰着するため、証明可能に安全であると見なされています。RSAなどの他の意味的に安全でないアルゴリズムは、最適非対称暗号化パディング(OAEP)などのランダム暗号化パディング方式を使用することで (より強い仮定の下で) 意味的に安全にすることができます。