公開鍵暗号の概要

公開鍵暗号とは？ (What is Public Key Cryptography?) 🔗

暗号化に使う鍵と、復号に使う鍵が異なる方式です。

RSA、ElGamal、NTRUなどがあります。

長所：鍵を共有しやすく、必要な鍵の数が少なくなります。

短所：共通鍵暗号より低速です。

定義：公開鍵暗号PKEは、次のアルゴリズムで構成されます。

正当性

セキュリティパラメーターλとすべての平文Mについて、次が成立するとき、公開鍵暗号PKEは正しいといいます。

👨‍💻

Dec(sk, Enc(pk, M)) = M

ここで、(pk, sk)はKeyGen(λ)の出力です。

チャレンジャーCと攻撃者Aの間のゲームを考えます。

Aの目標は公開鍵暗号を破ること、つまり暗号文から平文Mを見つけることです。

Setup：チャレンジャーCは、セキュリティパラメーターλを入力し、(pk, sk)を出力します。

そのうち公開鍵pkをAへ渡します。
Phase1：AはCへ復号クエリを送ります。

つまり、Aは任意の暗号文 $C_i$ をCへ送り、Cは $Dec(sk, C_i) = M_i$ を返します。
Challenge：Aは二つの平文 $M_0, M_1$ を選び、Cはその一方を選択して（ $b \in \{1, 2\}$ ）、 $Enc(pk, M_b) = C_b$ を返します。

Aは、どちらの平文に対応する暗号文かを表す $b$ を推測します。
Phase2：AはCへ復号クエリを送ります。

つまり、Aは任意の暗号文 $C_i$ をCへ送り、Cは $Dec(sk, C_i) = M_i$ を返します。

Adv_{PKE}(\lambda) = Pr[b = b'] - \frac{1}{2}

👍

攻撃者がセキュリティパラメーターに対して無視できない優位性を得られないとき、その公開鍵暗号方式はIND-XXX安全です。

XXXは、攻撃者に許される復号オラクルによって決まります。