基于ElGamal的乘法同态及加法同态变换
ElGamal 算法由来
- ElGamal 算法是由 Tather ElGamal 于1985年提出来的,它是一种基于Discrete Logarithm Problem (离散对数难题) 的加密体系。
- ElGamal 可以用于加解密,也可以用于签名。
ElGamal 的加解密方法
密钥生成
- 秘密信息接收方 Alice 基于一个安全的循环群 G 生成;
加密过程
- 发送方 Bob 对秘密信息 m 进行加密处理,m 需要提前被映射为 G 上的一个元素
- 为了保证安全,Bob 最好每次都重新选择一个 y
解密过程
- Alice 接收到 (C1, C2)之后,进行解密
ElGamal 的签名及验签
- Alice 发送消息 m 给 Bob, Bob确认消息签名的正确性
基于ElGamal 的同态乘法
- ElGamal 的加密满足乘法同态
转换成加法同态
- 将 m 编码为 g^m,对 g^m 进行加密;
- 则 m*n 就相应变为 g^(m+n),满足加法同态;
- 优势:性能上比 Paillier 要好一些;
- 局限性:解密时需要将 g^m 解码为m,需要求离散对数,所以一般只适用于 m 较小的场合(可以查表);
Reference
- 百度百科 ElGamal: https://baike.baidu.com/item/Elgamal/856288
- 公钥加密算法 ElGamal: http://rangerway.com/way/public-key-one-elgamal