基于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* \ulcorner\dfrac{c}{p}\lrcorner）mod \ 2 = Lsb(c) \ XOR \ Lsb(\ulcorner\dfrac{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開發、密碼學和區塊鏈科研內容：
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/293790.html
標籤：區塊鏈
下一篇：變被動為主動 歐科云鏈助警升維