笔记分享｜浙大暑期密码学课程：Lattice-based Crypto lll 和lV
上篇笔记是浙江大学2023年暑期学校（ZJU Crypto School 2023）中Lattice 1-2相关内容的总结，详情请见笔记分享|浙大暑期密码学课程：Lattice-based Crypto l 和ll。
本文是浙江大学2023年暑期学校（ZJU Crypto School 2023）中Lattice 3-4相关内容的总结。在本文，我们将涉及以下内容：
，此即，我们可以基于LWE构造公钥加密 进一步地，我们如何构造签名？FHE？怎么优化参数？
此即：构造
（在后两者中，我们将使用格Trapdoor技巧）
1PKE
首先，我们回顾Oded Regev的PKE构造方案（的一种构造方式）。它是很多IBE/FHE方案的基础。
：我们生成。（这里需要是一个矮胖的矩阵，即）。是一个短向量，不妨认为。计算。于是：
公钥 私钥。
：我们生成均匀随机(uniformly random)的，计算
其中都是噪声。则为密文。
：计算。其中是取整。
我们考察解密正确性，即计算。
其中后面的是小的。于是，我们只需要考察是接近于0还是接近于（在意义下）。
在这里。我们需要知道是一个短向量。如果太大，那么无法保证解密的正确性。
2PKE的安全性
下面，我们考虑上述PKE方案的安全性。我们首先观察密文的形式：
注意到长得都比较像LWE的sample。显然就是一个LWE。如果是uniformly random的向量，那么也将是一个LWE的sample。
但是，从构造上来看，其实并不是在上uniformly random的。因为是在上均匀随机的而不是在上均匀随机的。
但是$u实际上和uniformly random（在统计上）不可区分的。
为了说明这样一件事情，我们引入Leftover Hash Lemma.
它大概是说，你如果从中均匀随机选，那么的分布和均匀随机（在统计上）不可区分。
3剩余哈希引理 (LHL)
引理（Leftover Hash Lemma, LHL）. ，，。如果，那么
其中，指统计距离的差为。
即，和是统计上不可区分的。
我们在这里不会去证明LHL。但是，我们提供一种理解LHL的思路：LHL本质上是一种对随机性的提取或者降维(Randomness extraction)。
假设存在一个随机源。这个均匀采样于，但是如果把这个放在下，那么它显然不是上均匀随机的。
我们计算。这个就是一个提取（或者压缩）随机性的过程。矮胖的矩阵就是提取器。
取对数底数为2，于是的熵是。如果是真随机的，那么的熵就是。
因此，如果比大一点点，那么可以认为中包含的随机性足够萃取成一个上的随机向量。我们就可以在计算上认为就是随机的。
从这里的分析来看，引理中涉及的不等式似乎是存在一些不准确的地方。
定理. 上述PKE是安全的，并且密文是伪随机的。
我们需要证明，和是统计不可区分的。
，
我们有和不可区分(LHL)。这里是真·均匀随机。
于是和不可区分。
根据LWE问题（和LHL），和是不可区分的。其中是真·均匀随机。
最后，由于一次性密码本，和是不可区分的。
4PKE的另一种形式
：
，其中。是一个高矩阵。
：生成向量。注意到是小的。则。注意到，这里我们在加密的时候没有加噪声，那么密文的形式不再是LWE。于是在分析安全性的时候，就不能用到LWE了。
：给定密文，计算。
（希望大家可以根据上下文分清作为维度和作为明文的区别。本文中这么写并不严谨，但是希望不会影阅响读）
解密的正确性：
安全性分析：我们将简述的证明思路，其中是真·均匀随机。
于是根据DLWE，我们无法区分和。其中是真·均匀随机。
又根据LHL，我们无法区分和均匀随机向量、和随机向量。
名词拓展：Dual Mode Encryption。我们真实的pk是，但是这个pk是和是不可区分的。如果我们用真实的pk加密，就会得到上面的分布，用sk解密的话也能恢复明文的信息。但是如果用进行加密，那么你得到的结果就是均匀随机的东西。DME大概的意思是，你有可能在KeyGen时生成真实世界的pk，然后加解密过程就一切如常。但是在分析的时候，我们可以生成一个和真实世界不可区分的pk，那么在加密后，你的消息会被完完全全地掩盖。于是安全性得到了保证。
5
格中的陷门
陷门这个东西，可以拿来构造一些诸如签名、IBE、FHE的方案。
首先，什么是陷门？一种未经证实的类比，陷门类似于软件的后门。一个黑客直接攻破一个App难度很大。但是如果我们有软件后门，那么攻破这个App就有可能变得简单。
给定LWE/SIS问题，如果我们有了陷门，那么求解SIS/LWE问题就是简单的。如果没有陷门，那么求解SIS/LWE问题就是难的。
我们以SIS问题为例。随机选定, 任意给定，我们想找一个短向量，使得。这就是SIS问题。找到符合要求的就意味着破解了SIS。
但是，如果我们换个顺序，给定，计算，这就是很简单的事情。
陷门的存在就支持我们做这样的更换顺序的事情。具体地，SIS陷门意味着给你一个矩阵，你就可以把上述SIS问题变成给定，计算的问题。如果没有这个，你就做不到这个事情。
早期，GPV方案构造了一个陷门，但是构造比较复杂。
后来，MP12方案构建了一个非常漂亮的陷门：G-Trapdoor。G-Trapdoor的命名来源于构造中产生的一个特定矩阵。可以基于MP12方案构造很多有意思的东西。
给定矩阵和向量，我们要找小的，使得。如果和是随机的，那么这个事情不容易啊。但是，如果我们非常巧合地把选成了单位矩阵，那么这个事情就有可能是非常简单的。
具体地，假如我们在格上随机采样选取格基和，把它捏成矩阵（于是是单位矩阵），那么对于任意的向量，求解的过程将变成无聊的报坐标过程。但是如果我们对做一个线性变换，搞出来一个随机矩阵，那么求解就基本意味着解SIS了。
今天，我们假设有这样一个让整件事情变得容易的。如果对于选定的随机矩阵，存在一个矩阵，使得，那么如何找到，使得？
我们可以走如下的步骤：
采样，使得 输出。于是。
此处，就是陷门。其实，给定随机的矩阵，寻找是很困难的。
能做到的事情还不止这些。
给定，找出和也是比较简单的。
我们假设这样的存在。那么我们是不是也可以构造一个LWE的陷门呢？
假设我们知道，那么我们有。于是可以顺利地求解出和。在这里，我们说这个可以做LWE Inversion。
注意，我们对于有一些额外的要求：如果过大，那么就是大的，可能导致解密的失败。
在前述的SIS陷门中也有同样的要求：如果太大，也不可避免地会变大（输出的就不是短向量了）。
下面的问题就是，能不能以及如何找到一个高品质的（小的）。
构造方法：
首先，和经典的、不带Trapdoor的LWE一样，采样（A是一个矮胖的矩阵）
Trapdoor采样：采样。并且，如果我们把遮住，我们希望看着就像均匀随机。MP12中的构造方法如下：
构造，其中。来自均匀采样，，其中均匀随机。
这里，我们还没说怎么生成，但是我们先假设存在这样的。
几个问题：
这里的为什么和Uniformly random不可区分？因为LHL。
怎么把转换到？即？
我们构造，于是。这里，矩阵决定了的构造品质（范数）。
需要注意，并不唯一。但是，存在构造的方法（比如下面将要介绍的构造）。
是什么，需要满足什么性质？
给定，，可以找到短向量。 当用作为LWE中的矩阵时，LWE问题应当是简单的。
MP12中给出了的构造：
选取向量。于是，其中是Kroneckor积。
有了这个向量，给定数字，我们可以求解，使得。（二进制分解）
同理，也可以进行计算。其中是向量。
上面的步骤构造了基于SIS的陷门。
这个陷门如何用于LWE问题呢？
假设。我们给定如前所述的向量，采样LWE example：。其中，是数字，是向量。LWE问题的的目标是，寻找和。
我们将向量拆解。是对这两个向量（都在意义下）求和：
我们考虑。我们总是可以将写成。于是。
在的时候，你可以把模掉，于是得到：。通过rounding就可以从中提取到。这意味着，我们提取到了的最低比特位。重复这一步骤，于是我们可以求解出数字的每一个比特位，于是求解到整个。
最后，在SIS Trapdoor中，实际过程并不是输出这么简单。它确实是输出短向量，但是这个短向量有可能泄露的信息。于是另一个问题是，我有一个Trapdoor，我可以找到一个短向量，但是这个短向量并不泄露的信息。处理的方法是给整套流程再添加一些随机项。
最后达到的目的就是，我们采样的样本只和格有关系，而和我们使用哪一组Trapdoor无关。
6基于陷门的签名
有了Trapdoor以后，GPV方案基于它构造了签名：
：——产生陷门。。
。计算，使得。其中，是的哈希值。注意，需要有私钥的参与才能完成签名。
关于验签，我们只需要验证两件事：
是一个短向量； 。
定理. 在SIS问题的安全性假设以及random oracle（用于哈希）的安全性假设下，签名函数是安全的。
证明思路. 我们假设存在攻击者，他可以攻破这个签名函数。我们的证明目标是，存在归约，使得攻击者可以攻破SIS。
签名安全性的大致内容：一个对消息的签名如果是不安全的，那么意味着可以找到碰撞，使得对进行签名的结果是一样的。
首先，我们生成对，将公开。攻击者知道签名，于是知道，但是不知道私钥和签名对应的明文。
根据定义，攻击者可以通过查询RO来获取消息对应的哈希值。这意味着，RO需要维护一张表，对于给定的输入，RO要能查到对应的，并且返回。
现在假设攻击者要伪造使得。
于是有。
这意味着攻击者可以攻破SIS。
7全同态加密
首先，看一下全同态加密的概念。
我们任意选取若干的明文。与此同时有一个特殊的加密方案。我们可以计算一个函数。现在我们分别对这些明文进行加密，得到。这个特殊加密方案还支持对密文做一些密文的运算。计算之后解密的结果，和在明文状态下计算的结果是一样的。这就是同态加密的概念。
同态加密到目前为止经历了四代：
第一代：Gentry在2009年提出的基于ideal lattice的加密方案。 第二代：BV, BGV, BFV等方案——基于RLWE问题，支持对一个整数向量进行加密，进而支持SIMD运算。 第三代：GSW，一个非常简洁的方案。FHEW, TFHE等。 第四代：CKKS方案，支持浮点向量的运算。但是，第四代和第二代的方法没有什么本质上的差别，主要是编码消息时使用的技巧(基于Canonical Embedding)有所不同。但是这个方案因为可以对浮点数进行操作，所以在隐私保护机器学习中还是比较火的。
这一部分将基于GSW方案进行介绍。
这个方案有一个特征，就是在时需要对外暴露两个Key。一个是公钥，一个是在做同态计算时用到的密钥。
下面，我们来看具体的实现。
. 首先生成随机矩阵，采样私钥，计算公钥
，其中，是误差。可以根据LHL证明的伪随机性。. 对比特进行加密。给定比特，计算，其中。
. 假如我们直接计算，我们会发现仍然无法计算出。其中，。
下面的问题在于如何提取。我们找一个向量，使得
于是有：。只需要考察更接近0还是就可以了。
下面，我们考察加法的计算。假设有和。
可以直接得到：。
但是做乘法不是那么容易。假设有和。我们所希望的是，做乘法之后的密文仍然有类似于的密文形式。
一个直观的想法是计算。
首先，我们可以计算矩阵的逆。则有。
于是计算密文乘法的过程就类似于：
于是转化成了我们想要的形式。
我们观察上述的乘法操作，可以发现：
大概将噪声扩大了倍。
假如给定密文，它们的噪声界分别为，那么你计算和计算的噪声界存在差别，因为乘法的先后次序不同，引入的噪声是不一样的。
在这个情况下，计算的噪声要比要小。
全同态加密的自举操作
由于时间不够，课件里主要从high level讲了Bootstrapping。这里，我们引用本人的这篇博客给出的关于自举的简介：
为了理解Bootstrapping的原理，我们看一个故事。
Alice是一个资深的珠宝加工匠，她也管着一家珠宝店，某个聪明的年轻人Bob是她的学徒。
俗话说教会徒弟饿死师傅。Alice不想让Bob看到珠宝加工的每一个步骤执行之后半成品是什么样子的，因为如果Bob看见了加工过程中每一步的中间件的话，他就能悟出来加工的全过程，然后自己出来单干，用效率和年龄卷死自己。
不信的话，可以让另一个人在你的背上划拉一个字，对比一下看到划拉字的全过程和只靠触觉的话，辨识出来这个字是啥的可能性有多大。
但是两个人干活总是比一个人干活的产出要多。Alice舍不得撵走这样一个好用的劳动力。
Alice的核心需求：让Bob在看不见珠宝胚子的情况下还能做加工。
这天Alice发明了一个手套箱子，就像下面这张图里的一样：
只见这手套箱：
通体漆黑，从外面看不到里面有什么东西。有两扇门，一扇门上了锁，在开锁了之后可以往外取东西也可以往里放东西；另一扇门是单向的，可以往里面扔任何的东西，但是拿不出来。
于是Alice把手套箱交给Bob，让他来做珠宝加工。具体地，每次Alice会把珠宝坯子扔到手套箱里，让Bob对它按照固化的流程进行加工。等到加工完了之后，Alice再把手套箱的锁打开，把成品取出来。
如此这般这般如此了一段时间之后，Alice发现Bob隔着手套箱摸索着工作效率不行，以及由于手套箱自身设计的原因，在每一步加工过程中都会引入一些误差，相应地，在一个手套箱里加工珠宝最多只能加工L次，否则误差积累到足够大之后，在手套箱里的珠宝就会被加工废掉，成了残次品了。Alice暂时的解决方案是隔几个步骤就把中间件拿出来，自己再精琢一番，但是这么做实在是太费事了。
直到有一天，Alice又买了一个手套箱。为了区别，旧有的手套箱叫手套箱A，新买的手套箱叫手套箱B。
Alice自己把两个手套箱的钥匙都做了备份。今天开工前，Alice把坯子放在了手套箱A里，然后把手套箱A的钥匙放在了手套箱B中。
于是，当Bob隔着手套箱A做了若干次加工之后，他就把手套箱A整个扔到了手套箱B中。用已经放在手套箱B中的A的钥匙把A中的半成品取出来，在手套箱B中继续加工。
9现实
到这里故事就讲完了。和现实世界对比，很显然珠宝坯子是私密数据，手套箱是同态加密方案，单向门意味着公钥，钥匙就是私钥。
这里的手套箱套娃操作，其实就是bootstrapping了。
本质上，bootstrapping这个操作就是在密文下走完解密-加密的一个流程。
一般的同态加密涉及加密、运算和解密三样东西。可以看到，手套箱故事能不能拿到现实中来应用，很大程度上取决于能不能在加密的情况下实现加解密函数。
来源：李启闻
分享仅供学习参考，若有不当，请联系我们处理。
END
1.论文合集丨10篇大模型（LLM）优秀论文，来自Meta AI、浙大、清华、苏黎世联邦理工学院等前沿机构
文推荐