Camenish-Shoup暗号

加法準同型性 paillier暗号

検証可能な暗号（復号の途中に不正な暗号を検出できる）

加法準同型性を持つ （ベースが Paillier暗号なんだな）

鍵生成

  • 安全素数 p = 2p'+1, q=2q'+1 を選び、 n = p * q, n' = p'*q' を計算する

  • x_1, x_2, x_3 \in \lbrack 1, \frac{n^2}{4} \rbrack と g' \in \lbrack 1, n^2 \rbrack をランダムに選ぶ

  • g=g'^{2n} \mod n^2, y_1 = g^{x_1}, y_2 = g^{x_2}, y_3 = g^{x_3} を計算する

  • 適当なハッシュ用の鍵 hk を生成する

公開鍵： hk, n, g, y_1, y_2, y_3

秘密鍵： hk, n, g, x_1, x_2, x_3

パラメータ： h = 1 + n \mod n^2

暗号化

Lはラベル。平文と似たようなもので、検証用

  • r \in \lbrack 1, \frac{n^2}{4} \rbrack をランダムに選ぶ

  • u = g^r, e = y_1^rh^m, v = | (y_2y_3^{Hash(u, e, L)})^r | とする

復号・検証

検証

  • |v| = v と v^2 = u^{2(x_2 + Hash(u, e, L)x_3)} を確かめる

復号

  • t = 2^{-1} \mod n と m' = \frac{e}{u^{x_1}}^{2t} = h^m を計算する

  • paillerと同様に m' を復号