求问：是否存在具备乘法保持性质的低复杂度同态哈希函数？

存在满足乘法保持性质的同态哈希函数，且不少方案的复杂度显著低于RSA，以下是两种实用的选项：

1. 基于离散对数的乘法哈希 #

• 构造方式：选取大素数p，以及有限域GF(p)的生成元g，哈希函数定义为：
  H(x) = g^x mod p
• 乘法同态验证：H(x·y) = g^(x·y) mod p = (g^x)^y mod p = H(x)^y mod p，同理也等于H(y)^x mod p，严格满足乘法保持性。
• 复杂度优势：仅涉及素数域上的模幂运算，密钥生成只需确定素数p和生成元g，比RSA的大合数模运算更快，资源消耗更低。

2. 基于多项式环的乘法哈希 #

• 构造方式：选取小素数q和GF(q)上的不可约多项式f(x)，构造有限环GF(q)[x]/(f(x))；将消息编码为GF(q)上的多项式m(x)后，哈希函数定义为：
  H(m) = m(x) mod f(x)
• 乘法同态验证：H(m₁·m₂) = (m₁(x)·m₂(x)) mod f(x) = (H(m₁)·H(m₂)) mod f(x)，直接满足乘法同态要求。
• 复杂度优势：运算均在小素数域的多项式环上进行，计算量远小于RSA，适合嵌入式设备等资源受限场景。

关键注意点 #

• 抗碰撞性依赖参数选择：离散对数方案需保证p的长度至少为2048位以抵抗离散对数攻击；多项式环方案需匹配多项式长度与素数大小来保障安全性。
• 若仅需哈希的乘法同态性而非加密功能，上述方案完全可替代RSA类加密算法，实现更简单、运算更高效。

内容的提问来源于stack exchange，提问作者Sara