笔记分享|浙大暑期密码学课程：Lattice-based Crypto l 和ll
上篇笔记是对Idealized Model的整理，详情请见笔记分享|浙大暑期密码学课程：Idealized Model l和笔记分享|浙大暑期密码学课程：Idealized Model ll。
本篇笔记对Feng-Hao Liu老师在浙江大学的暑期Crypto School的《Lattice-based Crypto》课程进行了整理，可前往以下b站链接或点击下列视频观看完整课程。
浙大暑期Crypto课程- Lattice-based Crypto l（上）Feng-Hao Liu
https://www.bilibili.com/video/BV1rP411C7i4/?spm_id_from=333.788&vd_source=15b7926a3a203446fa868f18be9bc87e
浙大暑期Crypto课程- Lattice-based Crypto l（下）Feng-Hao Liu
https://www.bilibili.com/video/BV1oX4y1H7jA/?spm_id_from=333.788&vd_source=15b7926a3a203446fa868f18be9bc87e
浙大暑期Crypto课程- Lattice-based Crypto ll（上）Feng-Hao Liu
https://www.bilibili.com/video/BV1Ck4y1K7DT/?spm_id_from=333.788&vd_source=15b7926a3a203446fa868f18be9bc87e
浙大暑期Crypto课程- Lattice-based Crypto ll（下）Feng-Hao Liu
https://www.bilibili.com/video/BV1DV411K7dF/?spm_id_from=333.788&vd_source=15b7926a3a203446fa868f18be9bc87e
Lattice-based Crypto (格密码)
Chris Peikert在2015年写了一篇综述，叫做：格密码的十年(Decade of Lattice Cryptography)。这次暑校的Lattice Crypto部分主要涉及这一篇文章，以及Fenghao Liu老板的一些个人体会。
什么是格密码：基于格这个代数结构上面的困难问题，设计密码系统。
做格密码离不开可证明安全性和现代密码学的工具，比如归约（Reduction）之类的东西。
作为Lattice Crypto的基础课程，本文在可证明安全的框架下，从经典密码学逐渐走向格密码。
现代密码学的一个回顾
怎么样证明一个密码系统是安全的？怎么构建一个密码系统？
这个问题具体阐述如下：我们基于某个计算困难的问题构建密码系统。为了建立密码系统，我们将构造一个归约(Reduction)：假设一个攻击者可以破解这个密码系统，那么将存在一个规约使得攻击者可以解决这个计算困难的问题。
所有现代密码系统的套路都是这样的，未有出其右者。
自然而然地，我们要问两个问题：
哪些困难问题是合适的困难问题？ 怎么设计密码系统来完成这个归约？
例. 下列是密码学中经典的困难问题，以他们为例的原因是在格里面也会有类似的Decisional和Computational的困难问题：
DDH(Decisional Diffie-Hellman)：给定交换群和其中元素，区分和，其中为自然数指数，简记为——可以根据DDH问题构造ElGamal加密方案。 CDH(Computational Diffie-Hellman)：给定，计算。 DL(Discrete Logarithm)：给定和，求。
如果一个攻击者可以破解ElGamal方案，那么根据归约，他可以解DDH问题（但是如果DDH问题是困难的，那么攻击者很难破解ElGamal方案），记为
上述三个问题也可以进行难易的比较。难易的比较通过归约来实现。
其中是平凡的：如果攻击者能破解CDH，那么攻击者肯定能破解DDH。因为在DDH问题中给定两个三元组和，可以直接用CDH Oracle来求解，进而完成对DDH的破解。
问题. 我们知道DDH可以构造安全的密码，那么CDH和DL可不可以拿来构造密码系统？我们为什么还需要考虑CDH和DL？
我们基于一个比较困难的问题还是基于比较简单的问题来构造密码系统，是有区别的。
比如在归约关系中，如果我们分别假设DDH、CDH、DL是难的，那么哪一个是比较弱的假设？
假设“DL问题是难的” 弱于
假设“CDH问题是难的” 和 假设“DDH问题是难的”。
因为通过之前的归约，我们知道DL和CDH是比DDH难的。
直观地理解，假设“一个（实际上）比较困难问题是困难的”，这个是一个较弱的假设，因为实际上这个问题很可能确实很难，这里面假设的成分就不太强。反之，假设“一个（实际上）比较简单的问题是困难的”，就是一个强的假设。
那么我们基于一个比较弱的密码学假设构建密码系统，这意味着整体的结论是强的。理论密码学在思考的一个问题就是在比较弱的假设下构造密码系统。
直观地理解，假设一个实际不困难的问题很难，就是变相地限制了攻击者的能力，所以得到的密码系统可能没办法抵御更强的攻击者，这就是较弱的结论；假设一个实际困难的问题很难，就要求攻击者的能力强，得到的就是较强的密码系统（较强的结论）。
问题. 什么样的构造是更有效率的？因为做密码系统标准的时候需要兼顾理论上的安全性和实际的工程指标。
在传统密码学中，会有从DL衍生的不同困难问题，他们有着不同的强度，其中有些问题可以拿来构造密码系统。这样的思路可以推广到其他的困难问题中。
有规约的密码系统是不是一定就是难的？
一个例子是：.
根据归约，假设一个人可以破ElGamal，他就可以破DDH。但是这个结论还不是非常地精细。我们在破解密码系统中还要考虑归约的时间成本，是不是一个比较紧的规约？
归约成本和归约损失
假设存在一个攻击者，可以在多项式时间内并且有优势破解一个密码系统，记为。一般地说，在安全归约中，我们假设求解困难问题的oracle有，其中
可以理解为归约的（时间）成本。 可以理解为归约的安全性损失（因子）。最小的损失因子为1，这意味着在归约中不损失安全性。
假设存在的攻击者破解ElGamal方案，即存在的归约破解DDH。
我们希望，，这样的规约被称为紧的规约。
如果存在一个紧的规约，这意味着密码系统的强度和困难问题的强度差不多。
一个不严谨的比方：
如果规约不紧，假如DDH是100困难值，构造的密码系统可能只有20困难值。 对于紧的规约，假如DDH是100困难值，构造的密码系统可以保证99困难值。
Concrete security 和 Asymptotic security
归约的渐进（Asymtotically）安全性。对于所有的安全参数，我们都可以导出一组密码系统的参数，使得对于所有的多项式时间的攻击者，在安全参数够大时，密码系统被破解的概率是可忽略的。
但是在渐进框架下，我们只知道在安全参数足够大的情况下是安全的，并不知道什么叫“足够大”。这个问题需要由concrete security来回答。
Concrete security还取决于你怎么攻击加密算法。
格 （Lattice）和相关困难问题
格可以被想象成是一个空间中很多有规律分布的、离散的点。
比如上图，在二维空间中，构成二维空间的基底，我们对这个基底做整数线性组合就得到了一个二维格。图中规律排列的红点就是这个二维格的一部分。
格上的困难问题（SIS, LWE）
为什么要考虑Lattice Problem?
仍然提一句DL问题。量子计算机破解DL问题是比较容易的。当密码系统的底层问题不再困难时，就没有办法保证密码系统的安全性。假设有人做出了量子计算机，那么传统的基于DDH的密码系统都不能再用了。格上的困难问题可能具有较好的抗量子安全性。美国标准局（NIST）在2016年就已经开始征求后量子密码的标准了。NIST已经决定了三个方案来做标准，全是基于格的方案。
而且基于格也可以设计出很多好玩的密码系统，一个重要的例子就是全同态加密（支持数据的可算不可见）。
综上，对Why Lattice这个问题的回答是：
Post-quantum crypto (PQC) plausible（人们对格上困难问题的抗量子安全性有信心）。 格密码也可以导出很多进阶的密码系统（比如NIST对征集方案的要求是加密、签名、密钥交换等基础功能，而格密码都可以做出来，还可以实现更多的功能比如IBE, FHE, ABE等）。 已经有人在做了。
SIS(Short Integer Solution) 问题
定义 ()：给定任意的，其中是一个矩阵。我们的目标是，寻找向量，使得。其中，。即需要是一个短的非0向量。
如果要求，这意味着对向量的长度没有限制，那么这个问题就很简单。当小时，这个问题就难了起来。
取，难度从左到右逐渐变小。
定理. (在一定参数下的一些归约) 取时，, 。
我们给出上面涉及到的困难问题的定义。
定义. ：给定格，我们的目标是输出为线性无关的短向量，使得 ，其中定义为格中第短的向量。
定义. ：给定任意的格，找到这个格里的最短向量。
定义. ：给定任意的格，找到格里的短向量（并不是最短，允许有一个松弛），使得。
定义. ：给定任意的格，给定一个正实数，近似参数：
输出1，如果。 输出0，如果 其他情况下（Gap），输出0或1均可。
平均情形和最差情形
显然地，GapSVP是一个判定(decisional)的问题，SVP,SIVP是搜索(search)的问题。
上面定义的SIS问题是一个平均情形的问题。SIVP和GapSVP是最差情形的问题，因为从定义来看，解SIVP和GapSVP问题意味着给定任意的符合条件的输入都要能够输出解。隐式地，需要有最差情形到平均情形的归约。
假设有SIS oracle，可以在平均意义下求解SIS问题，那么根据归约，可以解所有具有合法输入的SIVP问题。
例如，
这个密码系统可以基于SIS（平均情形下的问题），SIS又可以基于SIVP（最坏情形下的问题）。那这意味着，密码系统可以基于一个最坏情形下的困难问题。
传统的RSA算法是基于平均意义下的困难问题——大数分解。现在已经存在许多针对特定条件下大数分解的攻击方案，这意味着一个随机生成的大数分解实例可能是容易被攻破的实例。但是对于基于最坏情形下的格问题构建的密码系统，我们只需要根据参数随机生成实例就可以了，不用担心一些特殊情况。
在真实世界中，我们一般不会真的用SIVP设计密码系统，因为SIVP-SIS的归约损失(reduction loss)还是比较大的。现在比较常见做法是直接看SIS的concrete hardness，进而推断密码系统的hardness。不用SIVP的另一个原因是可能会导致密码系统的实用性不强。
定理. 可以从SIS构造一个CRHF，即（Collision Resistent Hash Function, 防撞哈希函数）。
CRHF ，对于任意的多项式时间攻击者，
证明. 我们构造：，其中
下面证明：在SIS 下是CRHF。
构造归约。假设攻击者可以构造Hash碰撞，我们让攻击者破解SIS。为了解SIS问题，攻击者收到一个矩阵。在下，攻击者找到了两个Hash碰撞，使得，即，即。于是我们找到了一个短向量，其-范数是1。证毕。
我们进行一些推广，将输入域扩大：。
存在一定的加法同态性：。带有一定的加法同态（在一个增广空间上的同态）。
更强的结论：假设SIS是难的，定义域最大取都很难找碰撞。
具有同态性质的HF不能用来模拟random oracle。因为根据定义，random oracle对任何输入都回传一个真正均匀随机的输出（但是对相同的输入，该预言机每次都会用同一方法输出）。同态性破坏了这一点。你可以在给定的前提下计算和，于是可以在不查询这个CRHF的情况下获得。这和random oracle的基本思想相违背。
CRHF和同态并不冲突，但是这两个概念放在一块就和random oracle冲突了。
同态的Hash，这个东西有用吗？一个有意义的例子是联邦学习。
假设有一个云，有很多的用户。他们将各自的输入上传到云，云上进行求和并且回传。
你怎么确保云正确地求了这个和？让云将求和的结果做Hash。
在比较大的时候，Hash可以进行信息的压缩，于是这些用户可以进行求和的完整性验证。
另外，SIS还可以构造签名，但是需要额外的技巧。在下一讲会进行介绍。
LWE(Learning with Errors)问题
定义. 一个黑盒里，装有一个秘密。我们输入若干个到黑盒中去，黑盒对每个都会返回，其中是内积。是随机error（一般选离散高斯分布，分布的选择仍然在探讨中）。
目标是返回。
如果没有error ，这就是线性代数问题。用一手高斯消元可解。
当的方差很大，则高斯分布mod q会趋向于均匀分布，中的更像one-time pad，这个问题就难以求解了。
由此可见，error的大小会影响问题的难度。error越小，问题越容易。
当我们把上述LWE问题矩阵化，就可以得到一个LWE实例：
对于LWE问题，也可以考虑搜索LWE问题和decision-LWE问题。
search：给定，求。 Decision：。
定理. 。
这就是一个给定和，怎么做reduction的问题。
证明. 我们假设有一个SIS Oracle. 有和，统一记为。我们用SIS求解一个短向量，可以做到。如果，那么是小的。如果，那么大概率是不小的。此即求解了DLWE问题。证毕。
一个平凡的结论是。那么反过来有没有这样的结果呢？
答案是有，但是对一些特定的模数才行：
定理. ，对于。
原始的LWE问题中，是均匀(uniform)分布的。那么，秘密一定要uniform吗？服从别的分布时，是难的吗？
回答是：如果有足够的熵，那么LWE是难的。
均匀分布是满熵，对应的LWE实例自然是难以攻击的；
定理. 。如果我会破解entropic-LWE，那么我能破解正常LWE。
如果我们有LWE，我们就可以做对称加密。
定理. 对称加密。(ChosenPlaintxetAttack security，对选择明文攻击是安全的)。
CPA安全在公钥加密中基本和语义安全性等价，但是在对称加密中不是等价的。
证明. 构造：
。。
。，。。输出。
。，，若接近0，则，若接近，则。
下面我们基于混合论证（Hybrid Argument）证明它满足CPA security。
真实世界：一个具有CPA oracle的攻击者，他可以查询，得到。相应地，他可以查询和，并且分别获得对应的密文，最后输出。 ：我们将攻击者手中的CPA oracle换成随机oracle，攻击者查询，获得的永远是，其中是均匀随机项。
如果攻击者的胜率在真实世界中和中可以区分，则攻击者可以破解LWE问题。
断言：如果LWE是困难的，那么区分真实世界和是困难的。
断言：攻击者在中的advantage为0 (One-time pad encryption)。
LWE还可以做PRF（伪随机函数）、PKE(cca1\cca2)、签名、IBE、ABE、FHE、ZK、NIZK、OT。
考虑到密码系统的效率，直接基于LWE或者SIS构造密码系统的情形不多，一般都会基于理想格和环结构构建密码系统，比如全同态加密(Fully Homomorphic Encryption, FHE)中的一些经典方案。
(PS：笔记里是作者自己整理，可能会有一些不太准确的表达，也会有一些不当的理解，欢迎大家在留言区指出，一起学习交流)
往期推荐
1.学习同态加密：第二代全同态加密经典论文合集
2.学习同态加密：第一代全同态加密经典论文合集笔记分享|浙大暑期密码学课程：Idealized Model l4.笔记分享|浙大暑期密码学课程：Idealized Model ll