公開鍵暗号と離散対数系

公開鍵で暗号化し秘密鍵で復号する暗号方式。安全性は素因数分解や離散対数の困難性に依拠する。古典的だが準同型暗号やゼロ知識証明の土台でもある。

離散対数問題 (DLP)

巡回群 $(G,|G|,g)$ と $h=g^x$ から $x$ を求める問題。多項式時間では解けないと仮定する。判定版の DDH 仮定は $(g^a,g^b,g^{ab})$ と乱数を区別できないという仮定で、多くの方式の根拠。

Diffie-Hellman 鍵共有 (DHKE)

大きな素数 $p$ と生成元 $g$ で、Alice が $A=g^a$、Bob が $B=g^b$ を交換し、それぞれ $K=B^a=A^b=g^{ab}$ を共有鍵とする。盗聴者は $A,B$ から $K$ を多項式時間で計算できない。群として ${\mathbb{F}}_p^{\times }$（$p\ge 2^{1024}$）や楕円曲線上の有理点群（位数 $\ge 2^{250}$）を使う。軌道が小さい群は線形に DLP が解けてしまうため不可。

ElGamal 暗号

DLP ベースの公開鍵暗号。$h=g^s$ を公開鍵とし、暗号文 $(c_1,c_2)=(g^r,m\cdot h^r)$、復号は $m=c_2/c_1^s$。乗法準同型性を持ち、lifted-ElGamal は加法 1 回だけの SHE になる。

Paillier 暗号

合成数剰余の困難性に基づき、加法準同型性を持つ公開鍵暗号。暗号文同士の積が平文の和に対応するため、秘密集計・電子投票に使われる。

RSA

素因数分解の困難性に基づく。鍵生成・暗号化の仕組みは典型的だが、Common Modulus Attack など多数の攻撃が知られる（CTF 文脈での攻撃は別ページ参照）。素因数分解の高速アルゴリズムとして一般数体篩法 (GNFS) がある。

発展

• 双線型ペアリング: 3 つの群上の双線形写像。zk-SNARK や ID ベース暗号の基盤。
• ID ベース暗号: 公開鍵を ID（メールアドレス等）から導出する方式。

関連クラスタ: _moc-crypto