Cramer-Shoup暗号
暗号文 ( u 1 , u 2 , e , v ) {\displaystyle (u_{1},u_{2},e,v)} を秘密鍵 ( x 1 , x 2 , y 1 , y 2 , z ) {\displaystyle (x_{1},x_{2},y_{1},y_{2},z)} で復号する。
まず α = H ( u 1 , u 2 , e ) {\displaystyle \alpha =H(u_{1},u_{2},e)\,} を計算し、 u 1 x 1 u 2 x 2 ( u 1 y 1 u 2 y 2 ) α = v {\displaystyle {u}_{1}^{x_{1}}u_{2}^{x_{2}}({u}_{1}^{y_{1}}u_{2}^{y_{2}})^{\alpha }=v\,} が成立するかを確かめる。もしこのテストが失敗した場合、復号を止め拒否する。
テストが成功した場合、 m = e / ( u 1 z ) {\displaystyle m=e/({u}_{1}^{z})\,} を計算し、 m {\displaystyle m} を出力する。
u 1 z = g 1 k z = h k {\displaystyle {u}_{1}^{z}={g}_{1}^{kz}=h^{k}\,} と m = e / h k {\displaystyle m=e/h^{k}\,} より、正しい暗号文であれば、正しく復号される。
もし、取りうる平文空間が G {\displaystyle G} の位数よりも大きい場合には、ハイブリッド暗号を利用することができる。メッセージを短く分割してそれぞれを暗号化する、という単純な方法では、安全性が保てないことに注意。
位数 q {\displaystyle q} の巡回群 G {\displaystyle G} の記述と、その生成元 g 1 , g 2 {\displaystyle g_{1},g_{2}} を生成する。
5つのランダムな値 ( x 1 , x 2 , y 1 , y 2 , z ) {\displaystyle (x_{1},x_{2},y_{1},y_{2},z)} を { 0 , ... , q − 1 } {\displaystyle \{0,\ldots ,q-1\}} からランダムに選ぶ。
以下を計算する。 c = g 1 x 1 g 2 x 2 {\displaystyle c=g_{1}^{x_{1}}g_{2}^{x_{2}}} d = g 1 y 1 g 2 y 2 {\displaystyle d=g_{1}^{y_{1}}g_{2}^{y_{2}}} h = g 1 z {\displaystyle h=g_{1}^{z}}
公開鍵は ( c , d , h ) {\displaystyle (c,d,h)} と G , q , g 1 , g 2 {\displaystyle G,q,g_{1},g_{2}} の記述である。秘密鍵は ( x 1 , x 2 , y 1 , y 2 , z ) {\displaystyle (x_{1},x_{2},y_{1},y_{2},z)} である。