同态加密GSW ⽅案学习笔记1-GSW 最初⽅案概述
概述
2013 年，Gentry 等⼈使⽤近似特征向量技术，设计了⼀个⽆需计算密钥的全同态加密⽅案：GSW，拉开了第三代全同态加密的帷幕。2014年，Chris Peikert 等⼈提出了⼀个更简单的对称 GSW ⽅案，并⽤之设计了⼀个快速的⾃举算法。
党员联系群众制度⾸先看 2013 年 GSW ⽅案的论⽂标题：Homomorphic Encryption from Learning with Errors Conceptually-Simpler,Asymptotically-Faster, Attribute-Bad 同态加密和 LWE 问题不再赘述。
Conceptually-Simpler：从概念上更加简单。因为在 GSW ⽅案中所使⽤的的密⽂都是矩阵。因此在进⾏同态运算加或乘的时候，只需将矩阵进⾏加或乘即可。在这之前，同态加密运算乘法⾮常复杂。
Asymptotically-Faster：渐进更快。在理论上每次乘法的计算量为 ，其中 是矩阵乘法常数。以往的⽅案中重线性化都需要 的计算量。First identity-bad FHE scheme：本⽂提出了第⼀个基于⾝份的 FHE ⽅案，即相同⾝份 (ID) 下的密⽂可以进⾏同态运算。First attribute-bad FHE scheme：本⽂提出了第⼀个基于属性的 FHE ⽅案，即相同属性下的密⽂可以进⾏同态运算。此外，由于该⽅案是基于 BGV ⽅案设计的同态加密⽅案，因此从 BGV ⽅案中继承了许多优点：这是⼀个不需要⾃举的层次同态（多项式层）没有模转换 (modulus switching)安全性保障：Bad on classical GapSVP (基于经典 GapSVP)
右脚底有痣的女人
如果使⽤⾃举：Bad on LWE for quasi-polynomial factors (基于拟多项式参数的 LWE)
GSW ⽅案整体思想：近似特征向量技术
基础设置
⾸先假设我们有这样的⼀个设置：⼀个矩阵 乘以 等于⼀个特征值乘以 ， 是这个矩阵的特征向量，这⾥的 是特征值：现在想象⼀下，把 看作密⽂， 看作密钥，要加密的消息是 ：新员工座谈会
很容易可以发现这个形式具有同态的性质：密⽂的加或乘相当于明⽂的加或者乘。即假设 mod ，并且 mod ，则 mod 然⽽，这个形式虽然具有同态的性质，但是很明显⾮常的不安全，因为找到⼀个矩阵的特征向量很简单，密钥很容易得到。为了保证安全
性，我们可以将其转换为 LWE 的形式： 是系数很⼩的噪声向量 (<<q)
是⼀个近似特征向量 (approximate eigenvector)
⽅案的同态性质最软的石头
现在我们来看看同态的性质是否还在：
发现同态加和乘仍然成⽴，但是乘法中有新的噪声项。
⽅案的噪声处理
为了让这个噪声项尽量⼩，我们对这个新的噪声进⾏分析：
开车玩手机扣几分n ωω<2.3727n 3C v v v μC v μC ⋅1v =μ⋅1v q C ⋅2v =μ⋅2v q C ⋅1C ⋅2v =μ⋅1μ⋅2v q
e v
可以减⼩ ，即让消息空间变⼩。要达到这个⽬的仅需将消息空间设置成 即可。GSW ⽅案中使⽤与⾮门 (NAND gats) 可将消息空间设置成 。
可以使密⽂ 变⼩。密⽂可能是两个密⽂的乘法，即使初始的密⽂很⼩，计算后也可能得到较⼤的密⽂。是否能有什么技术能够使得密⽂⼀直保持在很⼩的范围内（甚⾄在 {0, 1} 内）？⽂中提出⼀种 Flatten ciphertext 的技术。如果我们能够限制密⽂的⼤⼩：
超清美女壁纸
同态乘法会将噪声扩⼤⾄多 倍（全部代⼊ 1 可得）
在噪声达到 之前可以评估深度为 的电路
令 ⾜够⼤，例如令 ，则我们可以评估多项式深度，并且得到⼀个层次全同态⽅案。
限制密⽂⼤⼩
那么我们怎么限制密⽂的⼤⼩？这⾥需要使⽤分解技术。⾸先先定义⼀些符号：
其中 是维度， 是模。 是 的对数定义⼀些函数： 是 的每个系数的⽐特分解，从最低位到最⾼位 (least to most significant)。 是上⾯那个⽐特分解函数的逆函数。
是⼀个系数都在 中的向量。有⼀些显⽽易见的结论：
对于任意 ，有 对于任意 和 ，有 这些函数和结论如何在同态加密⽅案中应⽤呢？现在我们给出近似特征向量的⼀个特殊形式： 其中 是随机的开始 Flatten Ciphertext （展平密⽂）：假设对于⼀个与⾮门（NAND）： 令 为 每⼀⾏的展平结果， 中所有的系数都在集合 中。
则 ，我们没有改变加密的消息，甚⾄没有增加噪声。
现在，我们拥有了⼀个层次全同态。
GSW 基本加密⽅案
μ2{0,1}{0,1}C n +1q Θ(log q )n +1q q =2n Θ(1)∈a
a Z q k
凿壁偷光的主人公是谁k q l =⌊log ⌋+q 1q N =k ⋅l
BitDecomp ()=a a (a ,...,a ,...,a ,...,a )1,01,l −1k ,0k ,l −1a a BitDecomp (∈−1b Z )=q N
(2b mod q ,...,2b mod q )∑j j 1,j ∑j j k ,j Flatten (∈b Z )=q N BitDecomp (BitDecomp ())−1b {0,1}Powersof 2(s )=(s ,2s ,...,2s ,...,s ,2s ,...,2s )mod q
11l −11k k l −1k ,∈a a s s Z q k <,>a a s s =<BitDecomp (),Powersof 2()>
a a s s
b ∈b Z q N ∈s s Z q k <b ,Powersof 2()>b s s =<BitDecomp (b ),>−1b s s =<Flatten (b ),Powersof 2()>b s s v =Powersof 2(s )s C =NAND I −N C ⋅1C mod q
2C ←3Flatten (C )NAND C NAND C 3{0,1}C ⋅3v =C ⋅NAND v mod q
设置 ：选择⼀个 bit 的模 ，格的维度参数是 ，适当地为 LWE 取误差分布 使得在已知攻击下达到 的安全性。同时，选择参数 。令参数集 ，令
。
密钥⽣成
英语电影台词
：采样 ，输出 。令 公钥⽣成 ：均匀⽣成⼀个矩阵 和⼀个向量 ，设 ，设 为 -列矩阵，由 和 的 列组成。设置公钥为 （注意：观察到 ），这⾥公钥看作⼀个LWE实例，是由向
量组成的矩阵，且与密钥点积得到的结果很⼩。加密 ：为了加密消息 ，均匀采样⼀个矩阵 ，可得 的每⼀⾏为 的加密，因为他们与密钥的点积的结果⾮常⼩。同时输出如下的密⽂ ：
解密 ：计算 ，从 中获得明⽂ 。
同态操作：在密⽂上进⾏加法/乘法后，展平密⽂。
整个⽅案的安全性可规约到 LWE 困难问题（通过左哈希引理 leftover hash lemma）。
基于该⽅案可构造 IBE 或 ABE
参考资料
参考论⽂：Gentry C, Sahai A, Waters B. Homomorphic encryption from learning with errors: Conceptually-simpler,asymptotically-faster, attribute-bad[C]//Annual Cryptology Conference. Springer, Berlin, Heidelberg, 2013: 75-92.参考论⽂：Alperin-Sheriff, Jacob, and Chris Peikert. “Faster bootstrapping with polynomial error.” Annual Cryptology Conference. Springer, Berlin, Heidelberg, 2014.
参考视频：/watch?v=uabmoq4-tGQ
参考视频：/watch?v=tczcle2T-Ak
参考 PPT ：yuyu.hk/files/FHE.pdf
参考⽂章：blog.csdn/Artisgrammer/article/details/99436600
参考⽂章：blog.csdn/yuxinqingge/article/details/104566212Setup (1,1)n L k =k (λ,L )q n =n (λ,L )X =X (λ,L )2λm =m (λ,L )=O (nlog q )params =(n ,q ,X ,m )l =⌊log ⌋+q 1,N =(n +1)⋅l SecretKeyGen (params )←t Z q n sk =←s (1,−t ,...,−t )∈1n Z q
n +1v ←Powersof 2(s )∈Z q
N PublicKeyGen (params ,sk )B ←Z q
m ×n ←e χm =b B ⋅+t e A (n +1)b B n pk =A A ⋅=s e Enc (A ,μ)μ∈Z q R ∈{0,1}N ×m A ⋅R 0C C =Flatten (μ⋅I +N BitDecomp (R ⋅A ))∈Z q
N ×N Dec (C ,v )C ⋅v =μ⋅v +Bitdesomp (⋅R )⋅A v =μ⋅v +⋅R ⋅A =s s μ⋅v +small 2+l −1small μ
