同态隐藏Homomorphic Hidings
2019.12.06 胡振远
我们采用逐步递进的方式来解决问题，首先我们假设Bob把
告诉Alice，那么问题的描述流程如下。
Alice->Bob: P(x)
Bob->Alice: s
Alice->Alice: 验证P(s)=0
现在我们需要把
隐藏起来，我们引入同态隐藏函数HH：)
。
同态隐藏函数
同态隐藏函数是如下形式的定义：
- 对于一个确定的，很难推算
- 如果
，那么%20%5Cneq%20E(y))
- 已知和
)
，可以计算和
的算术表达式的函数值，例如可以从和计算)
下面我们用一定的篇幅举例说明同态隐藏函数。
设
，
各为一个整数，
表示取模操作，用)
表示除以后的余数。例如%3D2)
，%3D1)
，我们一般用另外一种形式来描述，)
，)
。我们还可以对
定义基于模的加法操作，例如)
。我们可以把以及这个加法操作定义为一个整数群
对于一个质数
，我们还可以定义基于模的乘法操作，例如)
。我们可以生成一个新的群
，它具有以下性质：
- 它是一个循环群，意味着这里有一个属于的元素
，称之为生成元，能使得群里所有的元素都能被写成
的形式，其中
是属于
，特别的，当
时，
- 通过离散对数问题，我们知道，在中，如果是一个非常大的值，那么对于一个给定的元素
，很难找到一个范围内的整数满足)
-
里的元素相乘，即把元素的指数相加然后
)
，例如对于%7D)
，至于这里为什么是
，需要参阅费马小定理，以及充分的理解
现在我们可以构建一个同态隐藏函数HH，并且支持加法操作。这意味着我们可以从和计算。我们假设
的输入是
中的一个元素，范围是。现在我们定义%3Dg%5Ex%EF%BC%88mod%5Cquad%20p%EF%BC%89)
，满足同态隐藏函数的形式定义。并且对于一个给定的和，%20%3D%20g%5E%7Bx%2By(mod%5Cquad%20p-1)%7D%20%3D%20g%5Ex%20%5Ccdot%20g%5Ey%3D%20E(x)%20%5Ccdot%20E(y))
我们现在举例，设
，
，在下的计算
，
，
，
，
，
，
%20%3D%20g%5E%7B2%2B3(mod%5Cquad%207-1)%7D%20%3D%20g%5E5%20%3D%205)
%20%5Ccdot%20E(3)%3Dg%5E2%20%5Ccdot%20g%5E3%20(mod%207)%3D%202%20%5Ccdot%206%20(mod%207)%3D5)
因此%20%3D%20E(2)%20%5Ccdot%20E(3))
得到验证。
这里的举例的同态隐藏可以有这样的用处：假设我们不知道
的值分别是多少，但是如有结果表明%20%5Ccdot%20E(y)%3DE(5))
，我们就能确信
需要注意的是，在这里举例的同态隐藏是用素数同余类群进行的示范，实际应用中是采用的椭圆曲线，选择的%3Dg%5Ex)
，是椭圆曲线上的生成元。
