基于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确认消息签名的正确性

图片7

基于ElGamal 的同态乘法

  • ElGamal 的加密满足乘法同态 图片8

转换成加法同态

  • 将 m 编码为 g^m,对 g^m 进行加密;
  • 则 m*n 就相应变为 g^(m+n),满足加法同态;
  • 优势:性能上比 Paillier 要好一些;
  • 局限性:解密时需要将 g^m 解码为m,需要求离散对数,所以一般只适用于 m 较小的场合(可以查表);

微信图片_20230221115423

Reference

  1. 百度百科 ElGamal: https://baike.baidu.com/item/Elgamal/856288
  2. 公钥加密算法 ElGamal: http://rangerway.com/way/public-key-one-elgamal

results matching ""

    No results matching ""