警惕,前方数学高能….

同态隐藏,英文缩写为 HH ,本文意在解释 HH 是什么,它的应用实例以及构建过程

参数为 x 的 HH 函数 E(x) 满足以下条件:

  1. 对于绝大多数的 x,在给定 E(x)的情况下难以找到 x
  2. 不同的输入对应不同的输出 ,即如果 x $\neq$ y,那么 E(x) $\neq$ E(y)
  3. 如果知道 E(x)和 E(y),那么可以生成 x 和 y 的算术表达式的同态隐藏,即可基于 E(x)和E(y)来计算 E(x+y)

举个例子来说明 HH 在零知识证明系统中的作用:
假设 Alice 想向 Bob 证明她知道数字 X,y 及
x+y=7

  1. Alice 向 Bob 发送 E(x) 和 E(y)
  2. Bob 基于这些值来计算 E(x+y)
  3. Bob 同时计算E(7),并检查 E(x+y)是否等于 E(7) ,当且仅当等式成立时,Bob 才会接受 Alice 的证明

因为不同的输入由 E 映射到不同的加密隐藏 ,所以 Bob 只有在 Alice 发送 x,y 的加密隐藏以证明 x+y =7 。从另一方面来说,Bob 并不知道 x 和 y ,他只有访问 x 和 y 的加密隐藏的权限。

我们不能用常规的整数构造它们,这里需要用到有限群:
设 n 为某整数 ,A mod n 意味着取 A 除以 n 之后所留的余数,以此可以使用 mod n 操作来定义数字的加法运算{0,…..,n-1} :
进行常规的加法操作过后,对其使用 mod n 操作,使结果在 {0,….,n-1} 区间

对于素数 p ,基于 mod p 操作可以在 {1,….p-1} 上定义乘法运算,使乘法结果总是在 {1,…,p-1}集合内 ,通过在常规的整数乘法结果添加 mod p,举个例子 2*4 =1 (mod 7)

附带操作运算符的元素集合统称为 $\mathbb{Z}^*_p$ 组
$\mathbb{Z}^*_p$ 组有以下几种属性:

  1. 它是一个循环群,即在 $\mathbb{Z}^*_p$ 组中存在生成器 g,使得 $\mathbb{Z}^*_p$ 组中所有的元素都可以写作 $g^a$ ,其中 a 的取值范围落在 {0,…,p-2} 集合中,并且 $g^0$=1
  2. 当 p 取值很大时,给定 $\mathbb{Z}^*_p$ 中的元素 h ,很难找到落在 {0,…,p-2} 集合中的 a,使得 $g^a=h$(mod p)
  3. 落在集合 {0,….,p-2}中的元素 a,b ,有 $g^a*g^b$ = $g^{a+b(mod p-1)}$

基于这些性质,可以构建支持加法的同态隐藏,即 E(X+y) 可由 E(x)和 E(y) 计算获得
假定 E(x) 的输入 x 来自 $\mathbb{Z}_{p-1}$,因此它的区间是 {0,….,p-2}

对于每个这样的 x ,定义 E(x)=$g^x$ ,并且声明E 满足 HH 的性质:
第一个性质使 $\mathbb{Z}_{p-1}$中的 x 映射到不同的输出;
第二个性质使在给定 E(x)=$g^x$的情况下难以找到 x

最后使用第三个性质,给定 E(x) 和 E(y) ,可以计算出 E(x+y) ,因为 E(x+y)=$g^{x+y}$ = $g^x * g^y$ = $E(x)*E(y)$

Leave a Reply

Your email address will not be published.