基于DGHV的同态加密
基本概念、学习笔记、参考内容：
概念、个人笔记：
- 同态加密的原理详解与go实践
- DGHV:整数上的同态加密(1)-算法构建
- DGHV:整数上的同态加密(2)-解决噪声与构建全同态蓝图
参考：
- 论文：《一种基于智能合约的全同态加密方法》
- [1] M. Dijk, C. Gentry, S. Halevi, and V.Vaikuntanathan. Fully homomorphic encryption over the integers[J]. Applications of Cryptographic Techniques: Springer, Berlin, 2010, 24-43.
- http://blog.sciencenet.cn/blog-411071-617182.html
同态加密等计算量大的算法不适合在合约中计算，合约仅作为测试
本项目代码地址: https://github.com/xwjahahahaha/DGHV
基本设计
1. 随机数
我们所说的随机函数都是伪随机函数即PRF
随机函数的一般构成是：随机种子 + 随机数生成算法
目前有很多优秀的伪随机算法已经实现，但是在区块链智能合约上的最大困难是区块链的封闭性
可以将区块链看作一个封闭式的信息世界，所以不像一般网络中有丰富的熵增源.
Solidity通常采用keccak256哈希函数 作为随机数的生成器，该函数有一定的随机数性质，但是随机数生成的过程容易被攻击。
传统的随机数生成过程需要本结点的 Nonce值作为随机数种子，恶意节点会大量计算Nonce的值，直到随机事件的结果对自己有利，所以项目采用区块时间戳作为随机种子。
使用线性求余法生成随机数，再采用keccak256 Hash函数将区块时间戳与随机数合并取最终的随机数
生成公式如下：
{
X
n
+
1
=
(
a
X
n
+
c
)
m
o
d
m
,
n
≥
0
R
n
+
1
=
k
e
c
c
a
k
256
(
x
n
+
1
+
B
l
o
c
k
_
T
i
m
e
S
t
a
m
p
)
m
o
d
k
{
X
n
+
1
=
(
a
X
n
+
c
)
m
o
d
m
,
n
≥
0
R
n
+
1
=
k
e
c
c
a
k
256
(
x
n
+
1
+
B
l
o
c
k
_
T
i
m
e
S
t
a
m
p
)
m
o
d
k
begin{cases} X_{n+1} = (aX_n+c) mod m, n geq 0 \ R_{n+1} = keccak256(x_{n+1} + Block_TimeStamp) mod k end{cases}begin{cases} X_{n+1} = (aX_n+c) mod m, n geq 0 \ R_{n+1} = keccak256(x_{n+1} + Block_TimeStamp) mod k end{cases}
{Xn+1=(aXn+c) mod m, n≥0Rn+1=keccak256(xn+1 + Block_TimeStamp) mod k{Xn+1=(aXn+c) mod m, n≥0Rn+1=keccak256(xn+1 + Block_TimeStamp) mod k
2. 整数上的全同态加密
定义一套对称加密方法：
k e y G e n ( λ ) keyGen(lambda) keyGen(λ)根据安全参数 λ lambda λ生成一个**大奇数 p p p**密钥, η eta η（bit）是生成密钥 p p p的位数
E n c r y p t o ( p k , m ) Encrypto(pk, m) Encrypto(pk,m)表示加密,其中 p k pk pk表示公钥, m是明文，根据Dijk中的规定 m ∈ { 0 , 1 } m in {0,1} m∈{0,1}也即明文m只有一位;
r , q r, q r,q都是正随机数, 长度分别为 ρ 、 γ rho、 gamma ρ、γ , 其中的要求是 q > p q>p q>p 且 q q q是公开的 , r r r是一个随机小整数（可为负数）
则加密过程为:
E
n
c
r
y
p
t
o
(
p
k
,
m
)
=
m
+
2
r
+
p
q
Encrypto(pk, m) = m + 2r + pq
Encrypto(pk,m)=m+2r+pq
对应的解密过程
D
e
c
r
y
p
t
o
(
s
k
,
c
)
Decrypto(sk, c)
Decrypto(sk,c), 其中
s
k
sk
sk表示私钥、
c
c
c表示密文:
D
e
c
r
y
p
t
o
(
s
k
,
c
)
=
(
c
m
o
d
p
)
m
o
d
2
=
（
c
−
p
∗
┌
c
p
┘
）
m
o
d
2
=
L
s
b
(
c
)
X
O
R
L
s
b
(
┌
c
p
┘
)
Decrypto(sk, c) = (c mod p) mod 2 = （c - p* ulcornerdfrac{c}{p}lrcorner）mod 2 = Lsb(c) XOR Lsb(ulcornerdfrac{c}{p}lrcorner)
Decrypto(sk,c)=(c mod p) mod 2=（c−p∗┌pc┘）mod 2=Lsb(c) XOR Lsb(┌pc┘)
这里是对称加密，所以公钥和私钥是相同的，即 p k = s k = p pk =sk = p pk=sk=p
正确性的验证：
对于解密算法显然可以看出 m o d p mod p mod p将 p q pq pq项消除， m o d 2 mod2 mod2将随机数 r r r项消除，最后的结果就是 m m m
安全性讨论：
论文中已说明当参数 r ≈ 2 η , q ≈ 2 η 3 r approx 2 ^{sqrt{eta}} , q approx 2^{eta^3} r≈2η,q≈2η3时，该方案是安全的
功能测试
合约实现了输入为单Bit（即 m ∈ { 0 , 1 } m in {0, 1} m∈{0,1}）的加法同态加密（使用对称秘钥）
step_1 选择参数
编译、运行syn_DGHV.go
对于参数η，加法同态始终满足，但是乘法同态满足有要求（因为算法噪音）：
- 经测试η>=9时，乘法同态满足（小于9时不稳定，可见评估结果输出）
- 智能合约中3<=η<=5, 因为η过大会导致参数q过大无法部署合约（solidity最大为int256，没有大数操作）
go build -o dghv.exe ./ && chmod +x dghv.exe
./dghv.exe 5
# 参数1：η （建议>=9, 合约中<=5）
运行结果中包含：
- 生成的秘钥
p - 参数
q
输出示例（输出包含了多组测试，选择一组参数即可）：
==============================================
p =
31
q = 42535295865117307932921825928971026418
m0 = 0, m1 = 1
解密结果：n0 = 0, n1 = 1
加法测试：0 + 1 , true
加法测试：0 + 0 , true
加法测试：1 + 1 , true
加法测试：1 + 0 , true
==============================================
乘法测试：0 * 1 , true
乘法测试：0 * 0 , true
乘法测试：1 * 1 , true
乘法测试：1 * 0 , true
==============================================
step_2 部署合约，输入参数
以remix IDE为例
输出初始化参数：
step_3 测试
1的密文为：1318594171818636545920576603798101818973
0的密文为：1318594171818636545920576603798101818962
同态加法
1+0 = 1
1+1 = 0
0+0 = 0
拓展与改进
-
在合约中实现字符串大数的基本计算就可以实现合约上的同态乘法（或许有更好的办法）
-
虽然输入只支持1bit，但是可以通过组合电路实现高阶的计算：
- 同态加法 等价于 逻辑异或
- 同态乘法 等价于 逻辑与
- 逻辑与与逻辑异或具有完备性，可以实现组合电路任意高阶计算
（图片来自论文）
-
设计电路时注意使用Bootstappable算法减少噪声，不然会失效
欢迎Start，后续会继续更新
觉得不错的话，请点赞关注呦～～你的关注就是博主的动力
关注公众号，查看更多go开发、密码学和区块链科研内容：
最后
以上就是酷炫便当最近收集整理的关于DGHV:整数上的同态加密(3)-golang、智能合约实现尝试基于DGHV的同态加密基本设计功能测试拓展与改进的全部内容，更多相关DGHV:整数上内容请搜索靠谱客的其他文章。
发表评论 取消回复