基于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:整数上内容请搜索靠谱客的其他文章。
发表评论 取消回复