Multiset Hashing 改进

已有的 multiset hashing 算法步骤：

  1. inner cryptographic hash：将消息用 Poseidon2 映射为一个哈希值
  2. middle map-to-group：将该哈希值以及一个 8-bit 调整值映射为椭圆曲线上的 x 坐标（如 7 次扩域 $F_{p^7} = F_p[z]/(z^7 + 2z - 8)$）
  3. outer encoding function：最终得到椭圆曲线上的点 (x, y)

改进的算法去掉了第一步：

  1. middle map-to-group：直接将消息映射为椭圆曲线上的 x 坐标（如 7 次扩域 $F_{p^7} = F_p[z]/(z^7 + 2z - 8)$）
  2. outer encoding function：最终得到椭圆曲线上的点 (x, y)

如何将消息直接映射到椭圆曲线上的 x 坐标：
1.png

对于消息 m 和调整空间 T（可取值为 256），映射方式为 x = m * T + k，如果对应的 y 是二次剩余，则停止搜索，最多尝试 T 次。实际上，对于有 small cofactor h 的椭圆曲线，每次尝试成功的概率为 1/2h，如果 h = 1，则每次尝试成功的概率为 1/2。当椭圆曲线的阶为素数的时候，h = 1

2.png

enc(u + v) 和某个 enc(w) 发生碰撞的概率接近于 |M| / p，其中 |M| 是消息空间大小，p 是椭圆曲线的阶。所以为了降低碰撞风险，需限制消息空间 M 的大小。假如 p 是 koala bear 的七次扩域，大概是 $|F_q|=p^7 \approx 2^{32*7}=2^{224}$，是 224-bit，如果想提供 120-bit 的抗碰撞性的话，|M| 应小于 224 - 120 = 104-bit

3.png

参考

Constraint-Friendly Map-to-Elliptic-Curve-Group Relations and Their Applications