同态加密（1）GSW 加密⽅案
GSW⽅案是由Craig Gentry, Amit Sahai与Brent Waters于2013年提出的⽅案, 发表于论⽂[GSW13] 中.
GSW⽅案确实如论⽂标题⼀样, 概念清晰明了, 其Intuition简单到⼀个刚学完线性代数的⼤⼀新⽣也能理解. GSW还⽀持基于属性的加密, 但本⽂中我们将不介绍这⼀部分内容.
当然, 完全理解GSW⽅案仍然需要⽤到⼀些⽐较进阶的知识, 如LWE问题的困难性等. 我们在本⽂中不会对这些知识做过多的介绍, 这些知识将在今后其他的博⽂中介绍. 关于同态加密的基础知识可以参阅博⽂同态加密(0) 基础概念, 这篇博⽂完成后, 地址将被更新到这⾥.Basic Intuition
密⽂的基本格式
同方蓝海国际最基本的GSW同态加密⽅案的私钥()是⼀个向量, ⽽所有的明⽂都被加密⼀个矩阵中, 其中是以为近
似特征向量并以为近似特征值的矩阵, 即我们要求这⾥可以看出， 我们只需要挑选中⾮的位(最好是选较⼤的位), 如第位, 并⽐较与的值就可以解出的值.
⼀个需要注意的地⽅就是, 虽然取⾃, 但被视作是中的元素, 因此具体的运算也是按照的运算⽅式来进⾏.
我们也可以将噪声(error)显式地写出来, 记作
其中是⾮常⼩的向量. 因此可以看出, 如果确实是⼀个较⼩的噪声, 那么我们就可以正确地解出.
乘法同态性质
现在我们来验证该加密⽅案具有同态性质. 现在假设有两个密⽂, 对对应的明⽂分别是, 即
其中均为较⼩的噪声, 那么令, 我们检验的解密结果
这⾥可以看出, 确实是⼀个⽐较⼩的噪声项, 但是要让的噪声⽐较⼩, 那么就需要让是⼀个较⼩的矩阵(即其最⼤的元素较⼩), 我们稍后会解释如何做到这⼀点.
虽然说是乘法同态性质, 但是由于, 我们也可以将视作是做了同态的与(AND)运算. 与运算相对来说是⽐较简单的, 但是仅有与运算是不够的, 因为与运算是单调的, 单调的电路不可能是完备的, 我们需要实现⼀个超强的逻辑门----与⾮门的同态运算.与⾮门的同态性质
设, 其中为阶单位矩阵, 则
根据之前的讨论, 如果是⼀个较⼩的项, 我们有把握能从中解出.
sk v ∈Z q N μ∈i {0,1}C ∈i Z q
N ×N C i v μi C v ≈i μv
i v 0j v j v j μv i j μi μi {0,1}Z q Z q C v =i μv +i e
e e μi C ,C 12μ,μ12C v =1μv +1e 1
C v =2μv +2e 2
e ,e 12C =×C ⋅1C 2C ×C v ×=(C ⋅C )v =C (μv +e )=μ(μv +e )+C e 1212221112
=μμv +μe +C e 122112
μe 21C ×C 1μ∈i {0,1}C ×C =NAND I −N C C 12I N N C v =NAND (I −N C C )v =12(1−μμ)v −12μe −21C e 12
C 1C NAN
botanyD NAND (μ,μ)12
到这⾥有没有⼀种⼼情舒畅的感觉? 与⾮门⽣万物, 我们确实可以通过不断地叠加与⾮门来实现相当复杂的函数运算, 并且由于与⾮门是完备的, 仅⽤与⾮门可以实现任何⼀个布尔函数.
别⾼兴得太早!
虽然与⾮门⾮常强⼤, 但是每⼀次进⾏与⾮门运算, 都会导致新密⽂得噪声变得更⼤, 因此较多层的运算后, 噪声可能⼤得导致解密错误! 因此我们必须评估我们究竟能进⾏多少次的运算, 以及在快要达到极限的时候使⽤Bootstrapping技术. 这⼀点我们将在详细介绍⽅案的时候来说明.
Lattice Gadget
这⾥我们要⾸先介绍⼀种⼯具, 我们称其为Lattice Gadget, 它的本质是⼀些代数运算, 能够辅助我们从标准的LWE加密⽅案⽣成满⾜同态性质的密⽂.
第⼀个运算是, 它的作⽤是将⼀个向量的每⼀位按照⼆进制展开, 即每⼀个元素表⽰成⼆进制的形式, 其中. 即
即将的每⼀位都展开成了⼆进制, 变成位, 整个结果⼀共是位. 显然, .
类似的, 我们可以定义的反函数, 令即将每⼀位的⼆进制表⽰重新组合成了表⽰. 但是要注意的是, 并没有要求参数⼀定要是只由构成的向量, 我们可以定义⼀个全新的函数
authorityoriented这个操作有什么意义? 它将那些不是全由构成的重新"抹平"成了由中的元素构成, 并且能够保持其⼀定
的性质.下⾯介绍另⼀个不是那么好看, 但是却⾮常简单的操作. 的功能也是将⼀个向量转换为向量, 但是却使⽤的是完全不⼀样的⽅式.即将的每⼀位, 展开为位, 并且后⼀位是前⼀位的两倍. 使得整个向量变成. 这样做的好处是, 如果分别是中的⼀位, 那么the shadow
前⾯⼀部分就是中第组的第位, ⽽后⼀部分就是中第组的第位, 那么显然有ml是什么
KaTeX par error: Expected 'EOF', got '\ranglet' at position 102: …of2}(\mathbf b)\r a n g l e t
如果将直接写成的形式, 我们还有
BitDecomp a =(a ,⋯,a )∈1n Z q n
a i a ,a ,⋯,a 01ℓℓ=⌊log q ⌋+1BitDecomp (a )=(a ,⋯,a ,⋯,a ,⋯,a )
1,01,ℓ−1n ,0n ,ℓ−1a ℓn ⋅ℓa =i 2⋅∑j =0ℓ−1j a i ,j BitDecomp BitDecomp −1a =′(a ,⋯,a ,⋯,a ,⋯,a )∈1,01,ℓn ,0n ,ℓZ q
n ⋅ℓBitDecomp (a )=−1′(2⋅j =0∑ℓ−1j a ,⋯,2⋅1,j j =0∑ℓ−1
j a )n ,j Z q BitDecomp {0,1}Flatten (a )=′BitDecomp (BitDecomp (a )
−1′{0,1}a ∈′Z n ⋅ℓ{0,1}Powerof2Powerof2b ∈Z q n b ∈′Z q n ⋅ℓ
Powerof2(b )=(b ,2b ,⋯,2b ,⋯,b ,2b ,⋯,2b )
11ℓ−11n n ℓ−1n b ℓb ′a ,b i i a ,b ∈Z q n a ⋅i b =i 2⋅j =1∑ℓ−1j a ⋅i ,j b =i (a )⋅j =1∑ℓ−1
i ,j (2⋅j b )j a ′i j b ′i j BitDecomp (a )a ′⟨a ,Powerof2(b )⟩=′⟨BitDecomp (a ),b ⟩=−1′⟨Flatten (a ),Powerof2(b )⟩
′
第⼀个等号左边, 可以通过对第⼀个等号右边的两项分别做和操作得到
第⼆个等号右边可以对第⼆个等号左边两项分别做和操作得到
实际上左右两边的两项都是由中间得到的, 这样就可以将左右两边连接在⼀起. 这样我们发现⼀个惊⼈的事实: 如果内积的第⼆项是标准的结果的形式, 那么对第⼀项做操作不会改变内积的结果! 实际上这也不难理解, 因为Flatten操作就是把数值过⾼的位分到权重更⾼的位⽽已. 但是这样做有⼀个好处就是, 使得变成每⼀位都是的.
我们将以上⼏种记号都推⼴到对矩阵可⽤, 例如对于, 令
其余⼏种记号也做类似的推⼴, 总之就是, 对矩阵的每⼀列的列向量做相应的操作. 这时我们发现, 如果密钥确实是某个向量进⾏的结果, 即, 那么就有
俄语字母表
这可以使得变成⼀个较⼩的矩阵, ⽽不改变最后与的相乘的结果! 这样使得可以代替进⾏下⼀层的同态运算使得我
们要求的项较⼩! 我们直接将的结果记作
管理者英文
GSW ⽅案
现在我们开始具体介绍⽅案. 我们要说的是, GSW⽅案根据解密算法的选区不同, 实际上有构造两套⽅案. 第⼀种是选择作为解密算法, 该算法仅能解出, 因此整个同态运算中主要⽤与⾮门构建逻辑电路进⾏计算. 另⼀个解密算法可以解出, 这样就可以⾃然地使⽤加法与乘法进⾏运算.
⾸先我们要说的是, GSW并不是⼀个标准假设下的全同态加密⽅案. GSW如果要做到全同态加密, 需要⽤到Bootstrapping, 进⽽需要⽤到LWE加密⽅案的Circular Security假设(即⽤⼀对公私钥中的公钥来加密私钥相关信息的加密结果是安全的). 我们这⾥不介绍Bootstrapping的具体过程, 仅介绍Somewhat HE.
: 我们⽤表⽰安全参数, 表⽰同态运算的层数, 则表⽰模数的位数. 选择和LWE的错误分布, 选择. 设和,
参数集.
这⾥的参数较多, 需要逐⼀解释⼀下. ⾸先是安全参数, 表⽰密码⽅案中基于的困难的问题的复杂程度, 所有的参数都应该(直接或间接)基于这个参数选择. 参数表⽰同态运算的层数, 由于同态运算的层数由噪声的占⽐决定, 因此想要做更多的同态运算次数, 那么噪声就不应该太快掩盖, 就应该相应地选择⼤⼀些. ⽽LWE问题的错误分布还有维数按理来说是应该根据来选择, 但是这两个参数是可以根据来进⾏权衡(tradeoff)的, 这⾥直接⽤基础参数来代替. ⽽参数则是为了⽅便我们进⾏表⽰⽽引⼊的记号, 并且他们在前⾯也出现过.
: 选择. 输出. 令.: ⽣成矩阵和. 令. 令, 输出公钥.实际上这⾥就是变相⽣成了⼀组LWE问题的实例, 如果对这⾥不熟悉, 可以跟进我的Blog学习知识. 相关博⽂更新后会在这⾥补充地址.
: ⽣成矩阵, 输出密⽂
BitDecomp Powerof2BitDecomp Powerof2Powerof2Flatten a ′{0,1}Flatten (a )′C =[c ,⋯,c ]1N Flatten (C )=[Flatten (c ),⋯,Flatten (c )]
1N v s Powerof2v =Powerof2(s )C v =i Flatten (C )v
i C =i ′Flatten (C )i v C i ′C i C 2NAND C =NAND Flatten (I −N C C )
12Dec μ∈i {0,1}MPDec μ∈i Z q Setup (1,1)λL λL ∣q ∣=κ(λ,L )q n =n (λ,L )χ=χ(λ,L )m =m (λ,L )=O (n log n )ℓ=⌊log q ⌋+1N =(n +1)⋅ℓparams =(n ,q ,χ,m )λL q q χn λq L q ℓ,N SecretKeyGen (params )t ←Z q n sk =s ←(1,−t )=(1,−t ,⋯,−t )∈1n Z q
n +1v =Powerof2(s )PublicKeyGen (params ,sk )B ←Z q m ×n e ←χm b =B t +e A =[b ∣B ]pk =A Enc (params ,sk ,μ)R ←{0,1}N ×m C =Flatten (μ⋅I +N BitDecomp (R ⋅A ))∈Z q
creamer
N ×N
这就是整个加密的过程, 其中操作是为了保证是⼀个较⼩的矩阵, 我们知道是⼀个向量, 那么也是⼀个⼩噪声, 因此密⽂符合我们的要求.
: 选择⼀个的系数. 设是的第列, 则计算, 输出解密结果.实际上这⾥的解密过程就是⽐较与的值. ⽽为了使得解密出错的概率最低, 所以选择较⼤的⼀项, 这样使得错误最多可以积累到⽽解密不出错.
: 参考[MP12] .
噪声分析
接下来我们看⼀下进⾏层同态运算后, 噪声的增长. 我们知道, 两个噪声为的密⽂⾏⼀次加法运算, 噪声
增长到. (这⾥, 表⽰解密中的噪声项), ⽽两个噪声为的密⽂乘法结果的的噪声项为, 最多为. 如果初始噪声为的密⽂进⾏层运算, 则噪声最多增长为, 由这⼀点可以看出, 我们最多可以进⾏对数次数的同态运算. 但是对数次的运算已经⾜够⽤于解密运算, 因此我们可以基于Circular Security假设, 使⽤Bootstrapping技术实现全同态.习题
1. 证明算法的CPA安全性.
注释
1. Craig Gentry是构造出第⼀个全同态加密⽅案的⼈, 可以说是同态加密⽅案的⿐祖. 现在的⼤多数同态加密⽅案都是在Gentry最初的⽅案的基础上改造⽽来的.
2. Craig Gentry, Amit Sahai and Brent Waters. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler,Asymptotically-Faster, Atribute-Bad. Annual Cryptology Conference . Springer, Berlin, Heidelberg, 201
3.
永恒的爱英文
3. 实际上这⾥并不是最终⽅案中的密钥
4. 所有的向量都是列向量, 即
小学英语课程5. 如果没有标明底数, 的底数都是2.
6. Daniele Micciancio and Chris Peikert. Trapdoors for lattices: Simpler, tighter, faster, smaller. In EUROCRYPT , pages 700-718, 2012.—Flatten C v Powerof2C v =(μ⋅I +N BitDecomp (R ⋅A ))v =μ⋅I ⋅N v +R ⋅A ⋅s =μ⋅v +R ⋅e
R ⋅e Dec (params ,pk ,C )v v =i 2∈i (q /4,2/q ]C i C i x =i ⟨C ,v ⟩i i μ=′⌊x /v ⌉i i C v v v i q /4MPDec (params ,sk ,C )L E 2E E =max e i ∈[N ]E μe +21C e 12(N +1)B 2E L (N +1)B L 2L
Enc v a =(a ,⋯,a )=1n [a ,⋯,a ]1n T
log
