Packed Ciphertexts in LWE-based Homomorphic Encryption:解读

本节内容记录阅读该论文的笔记

介绍

首先,介绍了两种明文“打包”的方法:PVW和SV
《Packed Ciphertexts in LWE-based Homomorphic Encryption:解读》

PVW:对应论文(PVW:A framework for efficient and composable oblivious transfer),打包思想就是,将多个bit明文是为一个明文向量。

SV:对应论文(SV11:Fully homomorphic SIMD operations),打包思想:将多个明文通过“编码”插入到一个多项式上,转换成多项式的计算相当于这么多明文计算。多用于基于RLWE方案的。

Regev简介

原paper:On lattices, learning with errors, random linear codes, and cryptography

加密单比特数据:系统参数\(q\in Z\),明文比特\(b\in (0,1)\),私钥\(s\)和密文\(c\)都是向量\(Z^n\)

加解密

具体加解密参考:密码算法汇总

将明文\(b\)加密,密文是个向量,解密的私钥\(s\)也是向量,解密框架为:
\(z=<c,s>(mod q)=k.q+b.q/2+e(mod q)\),其中\(e,k\)是小整数,\(z\)的范围为\([-q/2,q/2]\),若\(|z|<q/4\),则解密为0,否则为1。

同态计算

(1)加法
Regev本身支持同态加法计算,即\(E(b_1+b_2)=c_1+c_2(mod q)\)
(2)乘法
在该paper:(BV11a:Efficient fully homomorphic encryption from (standard) LWE)中给出同态乘法运算:
这里的“乘法”是张量积,满足:\(E(b_1.b_2)=(c_1\bigotimes c_2\)),并满足\(<s_1,c_2>.<s_2,c_2>=<s_1\bigotimes s_2,c_1\bigotimes c_2>\)

张量积:参考(点积、张量积和范数
《Packed Ciphertexts in LWE-based Homomorphic Encryption:解读》

下面就是如何构造乘法后的正确解密:
\(c^*=\left \lceil 2/q.(c_1\bigotimes c_2)\right \rfloor\)
则:\(z^*=<s\bigotimes s.c^*>=k^*.q+b_1b_2.q/2+e^*(mod q)\),其中\(k^*,e^*\)也是相对较小的,所以参数选取适当的情况下,乘法后能正常解密!

可以看出,如果\(c_1,c_2\)是一个\(n\)维的向量的话,则\(c_1\bigotimes c_2\)是一个\(n^2\)维的矩阵,若在此基础上再进行一次乘法,则新密文的维数为\(n^4\),可见存在一个问题:密文维数随着乘法次数而变大(指数级)。

所以需要一种方法去“降维”,即(BV11a)中给出的重线性化技术(re-linearization)将密文维数\(n^2\)将为\(n\)

重线性化,实质上就是密钥交换技术(Key Switching),即给出两个密钥\(s,s’\),使用密钥交换技术将密钥\(s’\)对应的密文转换为\(s\)对应的密文。密钥交换矩阵实际上包含用\(s’\)加密的\(s\),这是一个矩阵(密钥交换矩阵),其实也是将\(s\bigotimes s\)转换为\(s\)

打包“压缩”明文

前面提到原始的Regev方案是加密单bit明文,密文和密钥都是向量,这样效率较低。

可以将多个密钥\(s_i\)按行组成一个矩阵\(S\),可以加密一个明文向量\(b\),解密时:\(z=S.c=k.q+b.q/2+e\),其中\(k,e\)是小向量。(这里的密钥有多种?)

(1)打包明文的计算
还是和上面说的类似,加法(mod q),乘法通过张量积。

只不过在乘法后执行重线性化时有些变化:
假设\(c^*\)是一个高维的“打包”密文,对于每\(i\)个明文\(b_ib_i’\),对应的密钥为\(s_i\bigotimes s_i\),现在如何进行重线性化呢?

选择一个合适的密钥交换矩阵(用\(s_i\)加密的\(s_i\bigotimes s_i\)),可以将\(c^*\)转换为一个新的密文\(c’\),对应的密钥为 \(s_i\)

(2)其他计算
可以在“打包”明文基础上实现SIMD同态计算、密文置换(permutation),并且使用PVW方法进行密文置换比使用SV方法更有优势。

SV方法,是通过自同构(automorphisms)实现,但是需要其他计算;而PVW是通过密钥交换实现的。

密文置换:移动密文内的slot,实现密文置换,解密后相当于明文置换。

基础

符号

(1)范数
\(||v||_1\):欧式范数
\(||v||_{\infty }\):无穷范数
《Packed Ciphertexts in LWE-based Homomorphic Encryption:解读》

具体参考:点积、张量积和范数

(2)其他符号
\(Z_q\):表示范围在\([-q/2,+q/2]\)内的整数
\([a]_q\):表示\(a mod q\)
\(\left \lceil a \right \rfloor\):表示四舍五入
\(\left \lceil a \right \rfloor_q\):表示\(\left [\left \lceil a \right \rfloor \right ]_q\)

LWE问题

安全参数\(n\),模数\(q>poly(n)\)\(\chi\)表示均值为0,标准差为\(q/ \beta\)的离散高斯分布,\(\beta =poly(n)\)

问:poly()表示什么意思?

关于LWE问题的困难性,在[Regev09]中给出了证明,表明能将LWE问题通过量子规约(quantum reductions)到\(n\)维格上的困难问题;在[Pei09]中给出了经典规约的方法(classical reductions)

SLWE

即搜索版本的LWE(search-LWE):
对于\((a_i\in Z_q^n,b_i=[<s,a_i>+e_i]_q)\)\(e_i\in \beta\) ,给出\(a_i,b_i\),难以计算出\(s\)

DLWE

即判绝版本的LWE(decision-LWE):
给出\(<a_i’\in Z_q^n,b_i’\in Z_q^n>\)\((a_i\in Z_q^n,b_i=[<s,a_i>+e_i]_q)\)是难以区分的

Regev方案

一个基于LWE问题的公钥加密方案,这里给出了一个对称加密方案,可以通过范型变换(generic transformations)获得一个公钥加密方案。

范型变换?

明文空间\(Z_2=(0,1)\),模数\(q\),安全参数\(n’\),\(n=n’+1\)

这里介绍对称加密方案

密钥生成

密钥\(s’\in \chi ^{n’}\),明文\(\sigma\in Z_2\),选取\(a\in Z_q^{n’}\),\(e\in \chi\)(小向量)

加解密

计算\(b=[\sigma q/2-<s’,a>+e]_q\),输出密文\((b,a)\)

解密:
计算\(d=[b+<s’,a>]_q=[\sigma q/2+e]_q\),若\(d>q/4\),则输出1,否则输出0。
解密成功的关键在于\(||e||_{\infty}<<q/4\)

上述解密可以看作:\(\sigma =\left \lceil [<s,c>]_q /(q/2)\right \rfloor_2\),其中\(s=(s|s’),c=(b|a)\)都是\(n\)维向量。

\(<s,c>=kq+\sigma q/2+e\)\(||<s,c>||_{\infty}<<q^2,|k|<<q\)

以上基础的加密方案只需\(|e|<<q/4\),下面在同态计算中,需要\(k,e<<q\)

同态计算

\(c_1,c_2\)是两个有效密文,分别对应的明文为\(b_1,b_2\in Z_2\),使用的密钥是\(s\),从上面可知,满足:\(<s,c_i>=k_iq+b_iq/2+e_i\),其中\(k_i,e_i\)是很小的数。

(1)加法
对于\(c’=[c_1+c+2]\),满足\(<s,c’>=k’q+(b_1\bigoplus b_2)q/2+e_i’\),其中\(k’=k_1+k_2\)\(k_1+k_2\pm 1<<q\)\(e’=e_1+e_2 <<q\)。(这里的加法是异或)

所以\(c’\)\(b_1+b_2\)的有效加密。
(2)乘法
在【BV11】和【Bra12】中给出了Regev的乘法同态。

对于\(c^*=c_1\bigotimes c_2\)\(n^2\)维向量),\(s^*=s\bigotimes s\),有乘法:
《Packed Ciphertexts in LWE-based Homomorphic Encryption:解读》

这里的\(e”\)多项式大于(polynomially (n) larger )\(e_1,e_2\)的,因为\(k_1,k_2\)是有范围的\(poly(n)\)

这里如何理解:polynomially larger?
见参考【1】
《Packed Ciphertexts in LWE-based Homomorphic Encryption:解读》
在这里的意思就是\(e”/e_1\)或者\(e”/e_2\)是有范围的!

下面将\(2/q.c^*\)四舍五入为整数向量,即求\(\left \lceil 2/q.c^*\right \rfloor=2/q.c^*+e\),其中\(e\)是舍入误差,\(||e||_{\infty} \leq 1/2\),则:
《Packed Ciphertexts in LWE-based Homomorphic Encryption:解读》

其中\(e^*\)是误差集合,\(k^*\)是一些整数,由于\(s^*=s\bigotimes s\)\(e\)中元素很小,所以\(<s^*,e>\)也很小,且\(|e^*|<<q\)

最后令\(c”=\left \lceil 2/q.c^*\right \rfloor_q\),满足:
《Packed Ciphertexts in LWE-based Homomorphic Encryption:解读》

其中\(e^*<<q\)\(k^*\)满足:
《Packed Ciphertexts in LWE-based Homomorphic Encryption:解读》

所以\(c”\)\(b_1b_2\)的有效加密,密钥为\(s^*=s\bigotimes s\)

密钥交换

上面可以看出,密文相乘后,维数扩张严重(指数级)。在【BV11a】中给出了方法-密钥交换技术,作用就是降维。

从上面密钥交换的简单介绍中,可知道主要功能:将一个维数为\(n^2\)维的密文\(c’\),对应的密钥为\(s’\),转换为一个新的密文\(c\),其维数为\(n\),对应的密钥为\(s\)

下面介绍一种密钥交换的变体技术,相对更加简单。

(1)密钥交换需要一个密钥交换矩阵
密钥交换(\(s^*->s\))可以看成:在密钥\(s\)下加密的\(s^*\),详细点说:对于每一个\(s^*[i]\),构造一个公开的“计算密钥”\(w_i\)(rational “ciphertext” ),满足:\(<s,w_i>=k_iq+s^*[i]+e_i\),其中\(k_1\)是一个整数,\(|e_i|\leq poly(n)/q\),将所有的\(w_i\)按列组成一个\(n*n^2\)的矩阵\(W\),满足\(s.W=kq+s*+e\),其中\(k\)是一个整数向量,\(||e_i||_{\infty}\leq poly(n)/q\)

(2)然后将高维密文转换为低维密文
给出一个\(n^2\)维密文向量\(c^*\)满足:\(<s^*,c^*>=k’q+b(q/2)+e’\),其中\(k’\)是小整数,\(e’ <<q ,b\in Z_2\)。定义\(c=\left \lceil Wc^* \right \rfloor_q=Wc^* +e^* +k^*q\),其中\(e^*\)是舍入误差,\(k^*\)是整数,则:
《Packed Ciphertexts in LWE-based Homomorphic Encryption:解读》

其中的\(\widetilde{e}\)是有界限的:
《Packed Ciphertexts in LWE-based Homomorphic Encryption:解读》

\(|\widetilde{e}|<<q\),那么对于\(\widetilde{k}\),有:
《Packed Ciphertexts in LWE-based Homomorphic Encryption:解读》

总的来说,对于维数为\(n\)的新密文\(c\),满足\(<s,c>=\widetilde{k}q+b(q/2)+\widetilde{e}\),其中\(\widetilde{k},\widetilde{e}<<q\),所以能够将一个高维\(n^2\)密文\(c^*\),转换为低维\(n\)的密文\(c\),且对应的明文都是\(b\),即新密文\(c\)是有效的加密,其中密钥是\(s\)

“打包”明文的计算

介绍

从上面可以看出,1bit的明文加密后的密文是\(n’+1\)维,在【PVW08】中给出了一种“打包”明文的方法,提升计算效率,简单点说就是,\(m’\)bit的明文加密后的密文是\(m=n’+m’\)

这里选取\(m’\)个向量(\(m’\)个大小为\(n’\)的向量),即\(s_i\in \chi^{n’}\),将其组成一个\(m’.n’\)的矩阵\(S’\)(按行),之前使用的是\(n’+1\)维的密钥向量\(s=(1|s’)\),现在使用的是\(m’.m\)的密钥矩阵\(S=(I|S’)\),其中,\(I\)是i个\(m’.m’\)的单位矩阵。

上面是密钥生成,下面开始加解密:

(1)加密
对于明文\(b\in Z_2^{m’}\),即明文是一个比特串(向量),随机取向量\(z\in Z_q^{n’}\),误差向量\(x\in \chi ^m\),计算\(d=[b.q/2-S’a+x]_q\),输出密文向量\(c=(d|a)\in Z_q^m\)

(2)解密
计算\(Sc=d+S’a=b.q/2+x(mod q)\),对于计算结果(向量),观察其中每个元素,若元素大于\(q/4\),则为1,否则为0。其中\(x\)中的每个元素远小于\(q\),解密也可以表示为\(b=\left \lceil [Sc]_q/(q/2) \right \rfloor_2\)

总的来说,对于密文\(c\),对应密钥为\(S\),有效的解密为:
《Packed Ciphertexts in LWE-based Homomorphic Encryption:解读》
其中\(\left\|k \right\|_{\infty },\left\|x \right\|_{\infty }<<q\)

(3)同态计算
从加解密来看,对于两个密文\(c_1,c_2\in Z_q^m\),分别对应明文是\(b_1,b_2\in Z_2^{m’}\),密钥为\(S\in Z_q^{m’.m}\)

密文相加\(c’=[c_1+c_2]_q\),分别对应于明文\((b_1\bigoplus b_2)\)

密文相乘\(c”=[2/q.c_1 \bigotimes c_2]_q\),分别对应明文\(b_1\bigodot b_2\in Z_2^{m’}\)(bitwise product,按位乘)。

密钥交换

密钥交换是需要“计算密钥”(public key key-switching gadgets)的,利用计算密钥使得\(s_i^*->s_i\),但是这样对于每一个密文转换\((c”->c)\),都需要一个计算密钥,我们想要的是使用一个计算密钥,将高维密文\(c”\)(对应的密钥为\(s^*\)),转换为一个低维密文\(c\)(对应密钥为\(s\))。

计算密钥能得到密钥交换矩阵\(W\)

密钥交换的“计算密钥”可以看作是用密钥\(s\)加密\(s^*\)构成的。具体来看,就是把\(s_i\)作为密钥,加密所有的\(s_i^*\)

这里的密钥交换矩阵\(W\),满足\(SW=S*+E(mod q)\),其中\(E\)是误差矩阵。具体说,\(m=n’+m’\),可以利用\(W\in Q^{m.m^2}\),将\(S^*\in Z^{m’.m^2}\)对应的密文转换为\(S=(I|S’)\in Z^{m’.m}\)对应的密文,那\(W\)如何求呢?

《Packed Ciphertexts in LWE-based Homomorphic Encryption:解读》
上面比较重要的内容是:想要安全性高,那就要提升模数\(n’\)的大小。

对于\(j\in (1,2,…,m^2)\)\(\widetilde{s}_j \in Z^{m’}\)组成矩阵\(S^*\)(按列),\(a_i\in Z_Q^{n’}\)组成矩阵\(W\)(按行),\(e_j\in Z^{m’}\)是误差向量,计算\(d_j=[2^l.\widetilde{s}_j-S’a_j+e_j]_Q\),输出\(w_j=(d_j|a_j)^T/2^l\in Q^m\),按行组成\(W\)

\(d_j\)也可以表示为\(d_j=2^l.\widetilde{s}_j-S’a_j+e_j+kQ\),则满足:
《Packed Ciphertexts in LWE-based Homomorphic Encryption:解读》

也即是:
《Packed Ciphertexts in LWE-based Homomorphic Encryption:解读》
其中整数矩阵\(K\)和误差矩阵\(E\)满足\(\left\|E \right\|_{\infty }\leq poly(n)/q\)

总结

给出一个高维密文\(c^*\),对应密钥为\(S*\),利用密钥交换矩阵\(W\),可得低维新密文\(c=\left \lceil Wc^* \right \rfloor_q\),对应密钥为\(S\),且解密后的明文是一样的。

若对于\(S^*.c^*=k^*.q+b(q/2)+e^*\)\(S.c=k.q+b(q/2)+e\),需要满足\(k^*,e^*,k,e<<q\)

在一个Leveled-FHE方案中,需要提前生成多个互相独立的密钥矩阵\(S_k\),使得在每次乘法后执行密钥交换,转换为新的密钥,所以在该方案中,乘法的次数就受限于密钥的个数。

《Packed Ciphertexts in LWE-based Homomorphic Encryption:解读》

安全性是基于LWE问题。上面的引理是在\(S^*\)\(S\)是独立关系的前提下,假如\(S^*\)\(S\)不是独立的,那这就依赖于“循环安全假设”(circular security)了。

密文置换

使用以上技术,可以实现“压缩”版的SIMD同态计算,就是每计算一次相当于计算多次!
在密文计算量更大的需求下,“压缩”实为是一种好的实现,对于密文置换,可以利用密钥交换实现。

介绍

什么是密文置换?

规定一种置换映射\(\pi()\)

对于一个密文\(c\),对应密钥为\(S\),解密后的密文为\(b\in Z_2^{m’}\),将其作用在\(\pi()\)上,得到\(c’=\pi(c)\)。用\(S\)去解密\(c’\),会得到\(\pi(b)\)

使用密钥交换实现很简单:准备一个密钥交换矩阵\(W\),可以得到将\((\pi(S)->S)\)
对于\(\pi(c)\),对应密钥为\(\pi(S)\),解密明文为\(\pi(b)\),使用密钥交换,将其转换为一个新的密文\(c’\),对应的密钥为\(S\),解密明文为\(\pi(b)\)

总结

本文基于LWE问题,设计了一种PVW变体的压缩明文方案,这就类似于SV压缩方案,在环上的便利。

基于整数环和多项式环上的对比

(1)基于多项上环比实数环的方案具有更好的渐进效率(asymptotic efficiency)
(2)两种情况下密文的大小大致相同:多项式环上的密文是一个多项式,其中包含\(O(n)\)个整数。
(3)对于密文乘法(tensor product multiplication),基于整数的密文大小扩大为\(O(n^2)\)倍,基于多项式的密文大小仍是\(O(n)\)
(4)对于重线性化,基于整数的密钥交换矩阵为\(O(n^3)\),基于多项式的密钥交换矩阵为\(O(n)\),基于整数上的计算会产生更多开销。
(5)对于密文中的“slot”个数,基于多项式的是由底层环结构决定的,基于整数的slot个数可以任意设置。
(6)在密文置换上,基于整数的比基于多项式更优。
(7)对于密钥交换,基于整数的比基于多项式的更方便和高效。

参考

1、【论文阅读笔记】-针对RSA的短解密指数的密码学分析(Cryptanalysis of Short RSA Secret Exponents)
2、范数||x||(norm)笔记

    原文作者:PamShao
    原文地址: https://www.cnblogs.com/pam-sh/p/16271420.html
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞