Verifiable Fully Homomorphic Encryption Based on Zero‑Knowledge Succinct Non‑interactive Arguments of Knowledge

doi:10.12068/j.issn.1005-3026.2024.11.003

Abstract

Abstract:

Homomorphic encryption （HE） is severely limited in its practical deployment due to low execution efficiency and the inability to ensure data integrity， particularly in scenarios with strict latency requirements. To address such issues and enhance general applicability， a new HE scheme is proposed. To improve execution efficiency， a multithreaded matrix multiplication （MMM） algorithm is designed. With the MMM algorithm， encryption tasks can be decomposed and distributed across multiple threads for parallel execution， thus achieving acceleration. To tackle data tampering in malicious server environments， a verifiable encryption mechanism is designed using zk-SNARK techniques to protect the integrity of ciphertext in outsourced computations. By combining MMM， an efficient verifiable fully homomorphic encryption based on zk-SNARK （zk-VFHE） was developed. Theoretical analysis and experimental results demonstrate that zk-VFHE outperforms similar protocols in terms of both execution speed and security.

Key words: fully homomorphic encryption, learning with errors, zero?knowledge succinct non?interactive arguments of knowledge（zk-SNARK）, verifiable computation, matrix codes

CLC Number:

TP 309.2

Jin-tong SUN, Fu-cai ZHOU, Qiang WANG, Che BIAN. Verifiable Fully Homomorphic Encryption Based on Zero‑Knowledge Succinct Non‑interactive Arguments of Knowledge[J]. Journal of Northeastern University(Natural Science), 2024, 45(11): 1537-1546.

Figures/Tables 15

Table 1 Symbols of LWE problem

符号	定义
n	正整数
q	正整数， $q ≥ 2$
$Λ$	格， $Λ ∈ R q$
$α$	误差参数， $α ∈ Z +$
$ρ σ, μ x$	高斯函数， $ρ σ, μ x = e x p ? (- π x - c 2 σ 2)$ ，其中 $σ = α 2 π, μ = 0$
$ρ σ, μ Λ$	格 $Λ$ 上的离散积分， $ρ σ, μ Λ = ∑ x ∈ Λ ρ σ, μ x$
$Ψ σ, μ, Λ (x)$	离散高斯分布， $Ψ σ, μ, Λ x = ρ σ, μ x ρ σ, μ Λ$

Table 1 Symbols of LWE problem

符号	定义
n	正整数
q	正整数， $q ≥ 2$
$Λ$	格， $Λ ∈ R q$
$α$	误差参数， $α ∈ Z +$
$ρ σ, μ x$	高斯函数， $ρ σ, μ x = e x p ? (- π x - c 2 σ 2)$ ，其中 $σ = α 2 π, μ = 0$
$ρ σ, μ Λ$	格 $Λ$ 上的离散积分， $ρ σ, μ Λ = ∑ x ∈ Λ ρ σ, μ x$
$Ψ σ, μ, Λ (x)$	离散高斯分布， $Ψ σ, μ, Λ x = ρ σ, μ x ρ σ, μ Λ$

Fig.1 Privacy?preserving verifiably outsourced computing

Table 2 Symbols of MMM

符号	定义
$A$	$A ∈ Z q s × r$ ，矩阵乘法的左因数
$B$	$B ∈ Z q s × t$ ，矩阵乘法的右因数
$m$	$A$ 的分片数
$n$	$B$ 的分片数
$A [·]$	$A$ 分片后得到的子矩阵数组
$B [·]$	$B$ 分片后得到的子矩阵数组
$T [·]$	线程序列
t	一个线程
$N$	线程的数量
$i d$	线程的标识符
$(x i d, y i d)$	线程 $i d$ 生成的用于拉格朗日插值的点坐标

Table 2 Symbols of MMM

符号	定义
$A$	$A ∈ Z q s × r$ ，矩阵乘法的左因数
$B$	$B ∈ Z q s × t$ ，矩阵乘法的右因数
$m$	$A$ 的分片数
$n$	$B$ 的分片数
$A [·]$	$A$ 分片后得到的子矩阵数组
$B [·]$	$B$ 分片后得到的子矩阵数组
$T [·]$	线程序列
t	一个线程
$N$	线程的数量
$i d$	线程的标识符
$(x i d, y i d)$	线程 $i d$ 生成的用于拉格朗日插值的点坐标

Table 3 MMM algorithm

M M M (A, B) → A T B

输入： $A, B$

输出： $A T B$

1. $A [m] ← S p l i t A, m$

2. $B [n] ← S p l i t B, n$

3. 调用N个线程并行执行 $T O (T [i], i, A [?], B [?])$

4. 接收最先返回的 $m n$ 个结果记为： $T O 0, …, T O m n - 1$

5. $P [m n] = N u l l$

6. for $i = 0$ to $m n - 1$ do

7. $P [i] = T O i$

8. end for

9. $C O E [m n] = L I (P [?])$

10. $R [m] [n] = N u l l$

11. for $i = 0$ to $n - 1$ do

12. for $j = 0$ to $m - 1$ do

13. $R [j] [i] = C O E [j + i × m]$

14. end for

15. end for

16. Return

R [?] [?]

Table 3 MMM algorithm

M M M (A, B) → A T B

输入： $A, B$

输出： $A T B$

1. $A [m] ← S p l i t A, m$

2. $B [n] ← S p l i t B, n$

3. 调用N个线程并行执行 $T O (T [i], i, A [?], B [?])$

4. 接收最先返回的 $m n$ 个结果记为： $T O 0, …, T O m n - 1$

5. $P [m n] = N u l l$

6. for $i = 0$ to $m n - 1$ do

7. $P [i] = T O i$

8. end for

9. $C O E [m n] = L I (P [?])$

10. $R [m] [n] = N u l l$

11. for $i = 0$ to $n - 1$ do

12. for $j = 0$ to $m - 1$ do

13. $R [j] [i] = C O E [j + i × m]$

14. end for

15. end for

16. Return

R [?] [?]

Table 4 TO algorithm

T O (T, i d, A [?], B [?]) → (x i d, y i d)

输入： $T, i d, A [?], B [?]$

输出： $(x i d, y i d)$

1. $x i d = i d + 1$

2. $y i d = 0$

3. $A' = 0$

4. $B' = 0$

5. for $i = 0$ to $m - 1$ do

6. $A' + = A [i] × ? x i d i$

7. end for

8. for $i = 0$ to n $- 1$ do

9. $B' + = B [i] × ? x i d i m$

10. end for

11. $y i d = A' T B'$

12. Return

(x i d, y i d)

Table 4 TO algorithm

T O (T, i d, A [?], B [?]) → (x i d, y i d)

输入： $T, i d, A [?], B [?]$

输出： $(x i d, y i d)$

1. $x i d = i d + 1$

2. $y i d = 0$

3. $A' = 0$

4. $B' = 0$

5. for $i = 0$ to $m - 1$ do

6. $A' + = A [i] × ? x i d i$

7. end for

8. for $i = 0$ to n $- 1$ do

9. $B' + = B [i] × ? x i d i m$

10. end for

11. $y i d = A' T B'$

12. Return

(x i d, y i d)

Table 5 KeyGen algorithm

K e y G e n (λ, f) → (p k, s k, p a r a m)

输入： $λ, f$

输出： $p k, s k, p a r a m$

1. $α, β u, β v, β w, γ, z, A 1, R, r p, r p - 1, e, E (x) ←$ $K e y P a r G e n λ$

2. $A C ← A C G e n (f)$

3. $Q ← Q A P G e n (C i)$

4. $A ← M a t r i x G e n (M M M R, A 1, - A 1)$

5. $T ← M a t r i x G e n (I, R)$

6. $e k = N u l l$

7. $v k = N u l l$

8. for $i = 1$ to $n$ do

9. $e k . a d d (E (z i), E (α z i), E (Q . u i (z)), E (α Q . u i (z)),$

$E (β u Q . u i (z)), E (Q . v i (z)), E (α Q . v i (z)), E (β v Q . v i (z)),$

$E (Q . w i (z)), E (α Q . w i (z)), E (β w Q . w i (z)))$

10. end for

11. $e k . a d d (E (Q . t z), E (α Q . t (z)), E (β u Q . t (z)), E (β v Q . t (z)),$

$E (β w Q . t (z)))$

12. $v k . a d d (E (1), E (α), E (γ), E (β u γ), E (β v γ), E (β w γ),$

$E (β w γ), E (Q . h (z)), E (α Q . h (z)))$

13. $p a r a m = (f, C i, Q, E, e)$

14. $p k = (A, r p, e k)$

15. $s k = (T, r p - 1, v k)$

16. Return

p k, s k, p a r a m

Table 5 KeyGen algorithm

K e y G e n (λ, f) → (p k, s k, p a r a m)

输入： $λ, f$

输出： $p k, s k, p a r a m$

1. $α, β u, β v, β w, γ, z, A 1, R, r p, r p - 1, e, E (x) ←$ $K e y P a r G e n λ$

2. $A C ← A C G e n (f)$

3. $Q ← Q A P G e n (C i)$

4. $A ← M a t r i x G e n (M M M R, A 1, - A 1)$

5. $T ← M a t r i x G e n (I, R)$

6. $e k = N u l l$

7. $v k = N u l l$

8. for $i = 1$ to $n$ do

9. $e k . a d d (E (z i), E (α z i), E (Q . u i (z)), E (α Q . u i (z)),$

$E (β u Q . u i (z)), E (Q . v i (z)), E (α Q . v i (z)), E (β v Q . v i (z)),$

$E (Q . w i (z)), E (α Q . w i (z)), E (β w Q . w i (z)))$

10. end for

11. $e k . a d d (E (Q . t z), E (α Q . t (z)), E (β u Q . t (z)), E (β v Q . t (z)),$

$E (β w Q . t (z)))$

12. $v k . a d d (E (1), E (α), E (γ), E (β u γ), E (β v γ), E (β w γ),$

$E (β w γ), E (Q . h (z)), E (α Q . h (z)))$

13. $p a r a m = (f, C i, Q, E, e)$

14. $p k = (A, r p, e k)$

15. $s k = (T, r p - 1, v k)$

16. Return

p k, s k, p a r a m

Table 6 Enc algorithm

E n c p k (b) ? → c

输入： $b$

输出： $c$

1. $b', s, e ← E n c P a r G e n l, l 1, Z N r$

2. $m = b b'$

3. $c i n v = M M M p k . A, s T + N e T + m T ? m o d ? q$

4. $c = p k . r p (c i n v)$

5. Return

c

Table 6 Enc algorithm

E n c p k (b) ? → c

输入： $b$

输出： $c$

1. $b', s, e ← E n c P a r G e n l, l 1, Z N r$

2. $m = b b'$

3. $c i n v = M M M p k . A, s T + N e T + m T ? m o d ? q$

4. $c = p k . r p (c i n v)$

5. Return

c

Table 7 Eval calculation algorithm

$E v a l p k (c, w, p a r a m) ? → (c', τ')$
输入： $c, w, p a r a m$
输出： $c', τ'$
1. $δ 1, δ 2, δ 3 ← E v a l P a r G e n Z q$ 2. $c', S ← A C . e v a l (p a r a m . f, c, w)$
3. $u = 0, ? v = 0, ? w = 0, ? α u = 0, ? α v = 0, ? α w = 0, u u = 0, ? v v = 0,$ $w w = 0$ 4. $τ' = N u l l$ 5. for $i = 1$ to $n$ do 6. $u · = e k . E u i z s i$ 7. $v · = e k . E v i z s i$ 8. $w · = e k . E w i z s i$ 9. $α u · = e k . E α u i z s i$ 10. $α v · = e k . E α v i z s i$ 11. $α w · = e k . E α w i z s i$ 12. $u u · = e k . E β u u i z s i$ 13. $v v · = e k . E (β v v i z) s i$ 14. $w w · = e k . E β w w i z s i$ 15. end for $16 . ? τ' . a d d u · e k . E t z δ 1, v · e k . E t z δ 2,$ $???????? w · e k . E t z δ 3, α u · e k . E α t z δ 1, α v · e k . E α t z δ 2,$ $???????? α w · e k . E α t z δ 3, E δ 1, E δ 2, E δ 3, v δ 1, u δ 2,$ $???????? u u · v v · w w · e k . E β u t z δ 1 · e k . E β v t z δ 2 ·$ $??????? e k . E β w t z δ 3$
17. Return $c', τ'$

Table 7 Eval calculation algorithm

$E v a l p k (c, w, p a r a m) ? → (c', τ')$
输入： $c, w, p a r a m$
输出： $c', τ'$
1. $δ 1, δ 2, δ 3 ← E v a l P a r G e n Z q$ 2. $c', S ← A C . e v a l (p a r a m . f, c, w)$
3. $u = 0, ? v = 0, ? w = 0, ? α u = 0, ? α v = 0, ? α w = 0, u u = 0, ? v v = 0,$ $w w = 0$ 4. $τ' = N u l l$ 5. for $i = 1$ to $n$ do 6. $u · = e k . E u i z s i$ 7. $v · = e k . E v i z s i$ 8. $w · = e k . E w i z s i$ 9. $α u · = e k . E α u i z s i$ 10. $α v · = e k . E α v i z s i$ 11. $α w · = e k . E α w i z s i$ 12. $u u · = e k . E β u u i z s i$ 13. $v v · = e k . E (β v v i z) s i$ 14. $w w · = e k . E β w w i z s i$ 15. end for $16 . ? τ' . a d d u · e k . E t z δ 1, v · e k . E t z δ 2,$ $???????? w · e k . E t z δ 3, α u · e k . E α t z δ 1, α v · e k . E α t z δ 2,$ $???????? α w · e k . E α t z δ 3, E δ 1, E δ 2, E δ 3, v δ 1, u δ 2,$ $???????? u u · v v · w w · e k . E β u t z δ 1 · e k . E β v t z δ 2 ·$ $??????? e k . E β w t z δ 3$
17. Return $c', τ'$

Table 8 Ver verification algorithm

V e r s k (c, τ) ? → a c c

输入： $c, τ$

输出： $a c c$

1. 生成 $i, j, k ∈ Z q +$

2. 初始化 acc = 0

3. if （ $c o n s t r a i n 1 i, τ ? ∧ ? c o n s t r a i n 2 j, τ ? ∧ ?$

$??????????? c o n s t r a i n 3 k, τ ? ∧ ? c o n s t r a i n 4 s k . v k, τ ? ∧ ?$

$??????????? c o n s t r a i n 5 s k . v k, τ ? ∧ ? c o n s t r a i n 6 s k . v k, τ$ ）

4. $a c c = 1$

5. Return

a c c

Table 8 Ver verification algorithm

V e r s k (c, τ) ? → a c c

输入： $c, τ$

输出： $a c c$

1. 生成 $i, j, k ∈ Z q +$

2. 初始化 acc = 0

3. if （ $c o n s t r a i n 1 i, τ ? ∧ ? c o n s t r a i n 2 j, τ ? ∧ ?$

$??????????? c o n s t r a i n 3 k, τ ? ∧ ? c o n s t r a i n 4 s k . v k, τ ? ∧ ?$

$??????????? c o n s t r a i n 5 s k . v k, τ ? ∧ ? c o n s t r a i n 6 s k . v k, τ$ ）

4. $a c c = 1$

5. Return

a c c

Table 9 Dec decryption algorithm

D e c s k (c) ? → b

输入： $c$

输出： $b$

1. $T * ← D e c P a r G e n (l, l 2)$

2. $c i n v = s k . r p - 1 (c)$

3. $y = M M M T, c i n v (m o d ? q)$

4. $b = M M M (T *, y) m o d ? N$

5. Return $b$

Table 9 Dec decryption algorithm

D e c s k (c) ? → b

输入： $c$

输出： $b$

1. $T * ← D e c P a r G e n (l, l 2)$

2. $c i n v = s k . r p - 1 (c)$

3. $y = M M M T, c i n v (m o d ? q)$

4. $b = M M M (T *, y) m o d ? N$

5. Return $b$

Table 10 Symbol definition in performance analysis

符号	定义
n′	函数转换成算术电路后线路的数量
l	密文的长度和密钥矩阵的行数
r	密钥矩阵的列数
s	MMM函数分割矩阵的子矩阵个数
$p o l y (f)$	外包函数的执行时间
$t e$	双线性映射的执行时间
$t E$	同态编码的执行时间
$t G$	$G$ 群运算的执行时间
$t G T$	$G T$ 群运算的执行时间

Table 10 Symbol definition in performance analysis

符号	定义
n′	函数转换成算术电路后线路的数量
l	密文的长度和密钥矩阵的行数
r	密钥矩阵的列数
s	MMM函数分割矩阵的子矩阵个数
$p o l y (f)$	外包函数的执行时间
$t e$	双线性映射的执行时间
$t E$	同态编码的执行时间
$t G$	$G$ 群运算的执行时间
$t G T$	$G T$ 群运算的执行时间

Table 11 Comparison with prior schemes

方案	GHV^[2]	VFHE^[6]	SL-CP-ABE^[16]	zk-VFHE
明文结构	矩阵	矩阵	向量	向量
密文结构	矩阵	矩阵	向量集合	向量
验证支持	不支持	不支持	不支持	支持
同态性	全同态	部分同态	部分同态	全同态
加密效率	$O (l r)$	$O (l r)$	$O (l r)$	$O (l · l g 2 ? (s) l g ? (l g ? (s)))$
解密效率	$O (l r)$	$O (l r)$	$O (l r)$	$O (l · l g 2 ? (s) l g ? (l g ? (s)))$
密文运算效率	$O (1)$	$O (1)$	$O (1)$	$O (1)$
外包运算效率	$O (p o l y (f))$	$O (p o l y (f))$	$O (p o l y (f))$	$O (p o l y (f)) + O (t E)$
验证效率	—	$O (l r)$	—	$O (t e) + O (t G) + O (t G T)$

Table 11 Comparison with prior schemes

方案	GHV^[2]	VFHE^[6]	SL-CP-ABE^[16]	zk-VFHE
明文结构	矩阵	矩阵	向量	向量
密文结构	矩阵	矩阵	向量集合	向量
验证支持	不支持	不支持	不支持	支持
同态性	全同态	部分同态	部分同态	全同态
加密效率	$O (l r)$	$O (l r)$	$O (l r)$	$O (l · l g 2 ? (s) l g ? (l g ? (s)))$
解密效率	$O (l r)$	$O (l r)$	$O (l r)$	$O (l · l g 2 ? (s) l g ? (l g ? (s)))$
密文运算效率	$O (1)$	$O (1)$	$O (1)$	$O (1)$
外包运算效率	$O (p o l y (f))$	$O (p o l y (f))$	$O (p o l y (f))$	$O (p o l y (f)) + O (t E)$
验证效率	—	$O (l r)$	—	$O (t e) + O (t G) + O (t G T)$

Table 12 Asymptotic time complexity of zk-VFHE

函数	渐进复杂度
KeyGen	$(11 n + 7) t E$
Enc	$O (l · l g 2 ? (s) l g ? (l g ? (s)))$
Eval	$2 p o l y (f) + 14 t E$
Ver	$O (l · l g 2 ? (s) l g ? (l g ? (s))) + 18 t e + 6 t G T + t G$

Table 12 Asymptotic time complexity of zk-VFHE

函数	渐进复杂度
KeyGen	$(11 n + 7) t E$
Enc	$O (l · l g 2 ? (s) l g ? (l g ? (s)))$
Eval	$2 p o l y (f) + 14 t E$
Ver	$O (l · l g 2 ? (s) l g ? (l g ? (s))) + 18 t e + 6 t G T + t G$

Fig.2 Running time of zk-VFHE

Fig.3 Time efficiency comparison of homomorphic encryptions

References 16

1	Brakerski Z， Gentry C， Vaikuntanathan V.（Leveled） fully homomorphic encryption without bootstrapping［J］.ACM Transactions on Computation Theory （TOCT），2014，6（3）：1-36.
2	Gentry C， Halevi S， Vaikuntanathan V.A simple BGN-type cryptosystem from LWE［C］//Annual International Conference on the Theory and Applications of Cryptographic Techniques.Heidelberg：Springer，2010：506-522.
3	Zhang Z F， Plantard T， Susilo W.Reaction attack on outsourced computing with fully homomorphic encryption schemes［C］//International Conference on Information Security and Cryptology.Heidelberg：Springer，2012：419-436.
4	Gennaro R， Gentry C， Parno B.Non‑interactive verifiable computing：outsourcing computation to untrusted workers［C］//Annual Cryptology Conference. Heidelberg：Springer，2010：465-482.
5	Gennaro R， Wichs D.Fully homomorphic message authenticators［C］//International Conference on the Theory and Application of Cryptology and Information Security.Heidelberg：Springer，2013：301-320.
6	Huang R， Li Z， Zhao J.A verifiable fully homomorphic encryption scheme［C］//Security，Privacy，and Anonymity in Computation，Communication，and Storage：12th International Conference，SpaCCS 2019.Atlanta，2019：412-426.
7	Fiore D， Nitulescu A， Pointcheval D.Boosting verifiable computation on encrypted data［C］//IACR International Conference on Public‑Key Cryptography.Cham：Springer，2020：124-154.
8	Ganesh C， Nitulescu A， Soria‑Vazquez E.Rinocchio：SNARKs for ring arithmetic［J］.Journal of Cryptology，2023，36（4）：41-93.
9	Brakerski Z， Vaikuntanathan V.Fully homomorphic encryption from ring-LWE and security for key dependent messages［C］//Annual Cryptology Conference. Heidelberg：Springer，2011：505-524.
10	Lu C F， Shieh S P.Secure key‑evolving for public key cryptosystems based on the discrete logarithm problem［J］.Journal of Information Science and Engineering，2004，20（2）：391-400.
11	Fiore D， Gennaro R， Pastro V.Efficiently verifiable computation on encrypted data［C］//Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security.Scottsdale，2014：844-855.
12	Pinto A M.An introduction to the use of zk-SNARKs in blockchains［C］//Mathematical Research for Blockchain Economy：1st International Conference MARBLE 2019.Santorini：Springer International Publishing，2020：233-249.
13	El‑Yahyaoui A， El Kettani M D E C.A verifiable fully homomorphic encryption scheme to secure big data in cloud computing［C］//International Conference on Wireless Networks and Mobile Communications.Rabat：IEEE，2017：1-5.
14	Regev O.On lattices，learning with errors，random linear codes，and cryptography［J］.Journal of the ACM，2009，56（6）：1-40.
15	Kedlaya K S， Umans C.Fast polynomial factorization and modular composition［J］.SIAM Journal on Computing，2011，40（6）：1767-1802.
16	Sravya G， Kumar P S， Padmavathy R.Secure lattice‑based ciphertext‑policy attribute‑based encryption from module‑LWE for cloud storage［C］//2023 IEEE 16th International Conference on Cloud Computing （CLOUD）.Chicago：IEEE，2023：554-556.