在上一期的文章中，我们学习并且深入了解了GSW全同态加密系统的具体构造。通过这一构造，我们可以对加密的密文进行相加和相乘的操作，并且通过二进制分解的方法，把密文中噪声的增加速度控制在一个可控的区间之内。 GSW的有限级数限制 然而，根据我们对于模组$ q $和噪声取值$ B $的选择，我们只能对一组GSW加密的密文进行有限次数的Eval运算。由于乘法会导致噪音增加的更快，所以同样的parameters可以进行更多次加法计算。 当噪声的取值范围逐渐逼近$ \pm q/4 $之后，我们的密文就变成了一个“饱和”的密文，不能够进行任何同态计算了。因为一旦进行计算的话，代表0的一头与代表1的一头的噪音区间就会重叠在一起，这样我们在解密的时候，就不能通过一个简单的thresholding（即比较最后的结果是否接近0的一头还是$ q/2 $的一头）来完美还原出一开始的原文了。 这也就是说，GSW加密系统是有限级数同态的（Leveled FHE），这在上一期我们也讲到了。那如果我们需要计算一个深度为$ \mathcal{L} $的电路$ C $，需要怎么使用GSW来实现呢？ 第一种最简单的方法，莫非于我们根据需要计算的深度$ \mathcal{L} $来选择对应的$ q $与$ B $。这样一来，我们就可以确保整个系统可以同态计算$ C $并且噪音区间不会爆掉。这其实对于大多数的应用来说已经非常足够了。唯一美中不足的是，当我们要计算的电路复杂度（深度）变得非常大的时候，我们选择的模组也会相对着变得非常大，这对于计算与存储的效率来说是大打折扣的。 一直无法计算未知或者无限深度的电路$ C_\infty $这一件事情一直很烦扰着我们。有没有什么办法可以不用改变模组与噪音的大小，但是可以扩大有限级数系统的计算范围呢？如果更严谨的来问的话：有没有什么方法可以让模组$ q $与噪音$ B $的选择独立（independent）于我们计算的电路大小$ \lvert C \rvert $呢？ 这个时候，就轮到Bootstrapping登场了。 Bootstrapping的概念 Bootstrapping是FHE界的开山鼻祖Craig Gentry在2009年提出的一个idea。Gentry本人其实写过一篇非常方便理解这个idea的介绍性paper：Computing Arbitrary Functions of Encrypted Data。我们这里就基于Gentry在原文中的表述方法来尝试深入了解一下。 Alice的珠宝店 Alice开了一家珠宝店，每天她需要把不同的珠宝（钻石、黄金）加工拼接起来，然后把完成的首饰卖给顾客。 过了一阵子后，Alice觉得自己忙不过来，于是决定雇佣Bob作为她的员工。然而，Alice担心Bob会趁着她不注意，偷偷的把加工完剩余的边角料藏起来，或者是加工的时候偷工减料为自己牟利，所以一直放不下心来。 直到有一天，Alice突然想到了一个idea。 Alice买来了一个手套箱（Glove Box），就是那种做实验用的密封的箱子，中间有两个带有手套的洞，手可以伸进去碰到箱子里面。她的想法很简单：只需要把所有的原材料全部锁在箱子里，然后Alice保管着可以开锁的钥匙，Bob就偷不走了。Bob想要加工这些原材料也很简单，只需要把手伸进去隔着手套加工珠宝，就可以完成工作了。 这个手套箱还有一个巧妙的小设计，有一个单向的进口，外面的人可以投任何东西进来。Bob可以通过这个进口把部分的原材料从外面投入手套箱内，但是无法打开手套箱把它们取出来。 整个idea一切都很完美，正当Alice买回来了一个手套箱，准备进行实践的时候，她突然发现了这个箱子的几个问题： 首先，套上手套的Bob的加工手艺并没有以前那么精湛了。也许原本只需要半天的活，现在可能要磨蹭两三天才能干完。 其次，虽然手套箱上了锁之后，Alice就可以放心Bob不会偷走珠宝了。但是这样的代价就是，当Bob加工完了之后，他并没有办法直接把加工完的珠宝拿出来给顾客，而是得等Alice过来了才能打开来。这样一来如果Alice很忙的话，可能顾客得Alice忙完了才能拿到自己买的商品。 以上的两点问题，Alice勉强都可以接受，但是接下来的第三点是最致命的。Alice发现，这个手套箱具有一定的使用寿命，也就是说Bob只能在这个箱子里加工珠宝$ L $次，然后这个箱子就会坏掉，变得无法再继续加工。如果已经达到了损耗的临界值，然后Bob继续尝试使用的话，那么里面的珠宝就有可能会彻底的被搞坏，变得无法修复。 当Alice发现手套箱的这三个特点之后，她开始思考如何有效的让Bob使用这一新发明。 Alice的平行世界：FHE 看到这里，想必熟悉FHE构造的读者们一定会对Gentry举的这个Alice的珠宝店例子非常亲切。Alice发明的手套箱其实就是暗指FHE系统！我们来比较一下这两者之间的共同性： Alice拥有手套箱的钥匙，所以可以打开盒中的东西。这代表了FHE加密系统的解密正确性。 Bob可以通过单向的入口把东西投入手套箱中，但是无法取出任何东西。这代表了我们讨论的FHE加密系统是一个安全的public key（公钥）的加密系统，即任意第三方都可以创造密文但不能解开密文。 Bob可以通过两个手套口，任意的加工放在手套箱中的物品，但是效率比起直接加工要慢上许多。这一步对应了FHE中的同态计算（Eval）。 最后，手套箱的使用寿命，以及使用了若干次之后就会坏掉这一设定，完美的吻合了Lattice结构的FHE系统中的噪声以及上限。想要增加使用寿命，一种方法是把盒子做的更大、更昂贵，这对应着在FHE中把对应的parameters增大。 那么现在问题来了，Alice可以如何不改进手套箱，但是增加它的使用寿命呢？我们继续回到Alice的世界中来看看Gentry是怎么描述的。…

写在前面 越往后面写，笔者发现随着难度的进阶，很多内容并不是可以全部塞在一篇文章中一起发出来的了。每一篇文章的内容都有太多细节的地方需要满满的思考。 从这一期开始，为了方便阅读，我们缩短每一期的篇幅，每一期就详细的介绍一篇或者几篇有关的paper。这样可以方便我们充分的理解体系的构造以及安全性的证明。 在之前的文章中，我们已经充分的了解了IBE加密在格中的实现方法。IBE其实并不是一个什么大难题，因为我们已经有基于双线性配对（Bilinear Maps）的非常好的IBE系统了。 真正让Lattice突出它的强大的地方在于，我们可以从类似ABB10的IBE架构出发，逐步添加新的功能，最后就可以实现传说中的ABE（Attribute-based Encryption），即属性加密了。 这一期，我们来看一看从IBE开始向ABE跨越的第一步：支持内积运算。 ABE简介 乍一看支持内积运算这个词，大家都会感觉一头雾水。想要了解它是什么意思的话，我们需要了解一下ABE问题的具体定义。 想必现在网上已经有许多关于属性加密（ABE）的介绍了。我们在这里就不多说整个问题的背景知识了，而是直接给出大概的定义。 首先，整个系统和IBE是一样的，需要一组由管理员生成的MPK与MSK。拥有了MSK的管理员，就可以基于任何属性函数$ f(\cdot) $签发对应的私钥$ sk_f $。什么是属性函数呢？属性函数其实就是一个读取一个属性输入$ x $的函数，如果$ x $通过了函数的验证，那么这个函数就会输出1，反之就会输出0。（反过来也可以，如果通过了输出0，没有就输出1也是一样的。） 这样的话，如果Alice要发送一封消息，她可以根据MPK与自己选择的一个属性输入$ x $创建一个特殊的公钥，进而加密她的消息$ m $。这个时候，和IBE不同的是，这个消息并不是指向某个$ ID $的，而是任何人，只要拥有管理员签发的密钥$ sk_f $，并且$ f(x) = 1 $的话，那就可以解密这条消息。 不仅如此，管理员也可以签发多个$ f’ $的私钥$ sk_f’ $，并且分发给不同的人。这样就可以确保一条消息对应的属性$ x $只会有一部分人对应的函数$ f’ $可以验证通过。这样的构造对于人数众多的ACL（Access Control List）使用场景下非常有用。即如果我想要一条消息只让某个分组的人可以解密，就可以通过ABE系统来高效地实现。 对于这一类把属性函数存放在密钥sk中，然而把属性本身放在密文中的构造，我们一般都称之为KP-ABE（Key Policy ABE）。反之，如果我们把验证的函数放在密文中，然而把属性放在密钥中的话， 这种构造被叫做CP-ABE（Ciphertext Policy ABE）。 一般来说，CP-ABE更加贴合我们实际的使用逻辑一点——我们在创造密文的时候，可以决定验证的属性函数$ f $，就可以很轻松的选择到底谁能看到谁不能看到。每个人所拥有的属性密钥，就可以是他们的名字或者是身份证号。然而，现在最常见的构造仍然是KP-ABE的结构，因为CP-ABE的构造会更复杂一点（需要能够把函数嵌入在密文中并且可以快速验证属性输入）。 如果我们不需要高效这一点，我们可以把任意的KP-ABE结构转换成CP-ABE结构，即对调加密方和解密方的角色。假如我们拥有一个可以支持任意复杂度电路的属性函数的KP-ABE结构，这个时候，我们只需要生成一个对应于Universal Circuit（全能电路）$ U(\cdot, x) $的密钥$ sk_U $，就足够了。 Universal Circuit $ U(C, x) $是一个万能的电路，其功能如下：我们输入一个电路$ C $的描述，与$ C $的输入$ x $，然后全能电路就可以计算这个输入的电路在$ x $上的值$ U(C, x) = C(x) $随后输出。在KP-ABE的场景中，我们想要通过Key中的函数$ f $来验证密钥中的输入$ x $。当Key中的函数是$ U(\cdot, x) $，即内嵌了输入$ x $的Universal Circuit的时候，这个时候密钥中的输入就变成了CP-ABE中的属性函数$ f $的电路描述$ C $。换句话说，我们可以把对于属性函数电路的描述存放在密钥中，然后通过Key中嵌入的全能电路和输入$ x $来进行计算，最后得到$ C(x) $的值。…

上期回顾 上期文章中，我们了解了Lattice Trapdoor的第一个实践用处——即身份加密IBE。同时，我们也看到了最简单的CHKP10 IBE身份加密系统。 粗略的概括一下CHKP10做了什么：我们把代表Identity（身份）的$ ID $拆分成二进制的bits，然后每一位都对应选择一个LWE的矩阵$ \mathbf{A}_i^b $。我们最终把这些选好的矩阵全部拼接起来，再通过实现预留的Trapdoor找到对应这个大矩阵的密钥，就可以进行Dual Regev的加解密了。 像这种根据Identity的每一个bit选择矩阵组合起来变成一个新矩阵的构造在密码学中非常常见，这里先留作一个悬念，如果后面有机会写到基于GGH15的Multilinear Map而实现的Indistinguishability Obfuscation（iO）的话，我们会发现非常相似的构造。 在上期的最后，我们同样也发现了CHKP10构造的一个缺陷：公钥的大小和ID的长度是等比线性增长的，这会大大影响这个IBE体系的存储空间和计算效率。 其实呢，CHKP10只是我们了解完Lattice Trapdoor之后入门的第一种IBE构造。同样是在2010年，整个密码学圈子里还诞生出了另一种IBE的构造——ABB10。 【ABB10】IBE加密系统 ABB10，顾名思义，是由Agrawal，Boneh与Boyan三位在2010年提出的。ABB10不同于CHKP10的是：它的加密矩阵$ \mathbf{F}_{ID} $是恒定大小的，并不会随着$ ID $的长度变长而变大。我们来看看ABB10的具体构造吧。 公共参数生成 ABB10的公共参数生成较为简单。首先，我们需要指定两个随机的问题矩阵$ \mathbf{A}_0, \mathbf{A}_1 $，以及SIS问题的结果向量$ \mathbf{u} $。最后，我们还需要借助之前讨论过的工具矩阵$ \mathbf{G} $。 我们生成$ \mathbf{A}_0 $的时候，需要通过之前的Trapdoor生成方法来生成。$ \mathbf{A}_0 $的Trapdoor $ \mathbf{R} $就是我们的MSK了。 乍一看，参数生成的部分和CHKP10基本相似。真正有区别的地方在于ID矩阵的生成。 生成ID矩阵 首先，我们设定用户的身份$ ID $为一个正整数。 计算ID矩阵$ \mathbf{F}{ID} $的方法很简单，我们只需要把$ ID $的值乘以$ \mathbf{G} $矩阵，然后叠加在$ \mathbf{A}1 $上即可： $$ \mathbf{F}{ID} = [\mathbf{A}0 \vert \mathbf{A}1 + ID \times \mathbf{G}] $$ 对应某个$ ID $的密钥$ \mathbf{e}{ID} $和之前一样，就是基于$ \mathbf{F}{ID} $的SIS问题的短向量解： $$ \mathbf{F}{ID} \cdot \mathbf{e}_{ID} = \mathbf{u} \text{ mod }q $$ 找到这个密钥的方法也和CHKP10是一样的，因为我们知道了$ \mathbf{A}_0 $的Trapdoor $ \mathbf{R} $，所以不管我们怎么变换$ \mathbf{A}1 $位置上的值，永远都可以找到整个$ \mathbf{F}{ID} $的SIS解。…

上期回顾 上一期，我们了解了Lattice Trapdoor的具体构造。基于Trapdoor，我们可以有效的逆向计算基于SIS与LWE的两个单向函数$ f_\mathbf{A}, g_\mathbf{A} $。 我们再来快速的回顾一下Lattice Trapdoor的构造。 首先，我们需要选择一个Uniform Random的矩阵$ \mathbf{B} \in \mathbb{Z}q^{n \times m’} $，然后再选择一个高斯分布的短矩阵$ \mathbf{R} \in \mathbb{Z}q^{m’ \times n \log{q}} $。随后，我们就可以构造我们的问题矩阵$ \mathbf{A} $： $$ \mathbf{A} = [\mathbf{B} \vert \mathbf{G - BR}] $$ 这个矩阵对应的Trapdoor就是矩阵$ \mathbf{R} $了，因为我们可以通过$ \mathbf{R} $来把$ \mathbf{A} $转换到到工具矩阵$ \mathbf{G} $上： $$ \mathbf{A} \cdot \begin{bmatrix}\mathbf{R}\\mathbf{I}\end{bmatrix} = \mathbf{G} $$ 通过这个构造，我们就可以把基于$ \mathbf{A} $的单向函数问题$ f\mathbf{A}, g\mathbf{A} $转换为基于$ \mathbf{G} $的单向函数问题$ f_\mathbf{G}, g_\mathbf{G} $。因为工具矩阵$ \mathbf{G} $的结构公开已知，所以我们可以很轻易的求解$ f_\mathbf{G}^{-1}, g_\mathbf{G}^{-1} $从而计算$ f_\mathbf{A}^{-1}, g_\mathbf{A}^{-1} $。 Lattice Trapdoor的构造非常简单，设计也很巧妙。接下来，这一期我们来看看基于Lattice Trapdoor最直观的应用：身份加密（IBE）。…

前期回顾 上一期，我们了解了格密码学中的一个非常重要的primitive，即Trapdoor（陷门）。 如果快速回顾一下的话，我们学到最重要的莫非就是基于SIS与LWE的两个单向函数（OWF）的构造了。 基于SIS的OWF $ f_\mathbf{A} $的构造如下：我们选择一个随机分布的矩阵$ \mathbf{A} \in \mathbb{Z}q^{n \times m} $。这个OWF的输入是一个短向量$ \mathbf{x} \in \mathbb{Z}{{0, \pm1}}^m $，输出则是： $$ f_\mathbf{A}(\mathbf{x}) = \mathbf{Ax} \text{ mod }q $$ 基于LWE的OWF $ g_\mathbf{A} $的构造是这样的：我们同样选择随机分布的$ \mathbf{A} \in \mathbb{Z}_q^{n \times m} $。这个OWF的输入是一个任意的向量$ \mathbf{s} \in \mathbb{Z}_q^m $，与一个在噪音分布空间内的噪音向量$ \mathbf{e} \in \mathcal{X}B $，输出为： $$ g\mathbf{A}(\mathbf{s, e}) = \mathbf{s}^t \mathbf{A} + \mathbf{e}^t \text{ mod }q $$ 如果我们比较这两个OWF的输入与输出空间之间的映射的话，我们会发现基于SIS的OWF是满射（surjective）的，而基于LWE的OWF是单射（injective）的。 我们还讲到了$ f_\mathbf{A}, g_\mathbf{A} $这两个OWF，如果我们有了Trapdoor构造出了对应的反函数$ f_\mathbf{A}^{-1}, g_\mathbf{A}^{-1} $，那么这两个反函数输出的特点也会和原本的OWF相对应。$ f_\mathbf{A}^{-1} $会输出很多种符合要求的解的一个高斯分布，而$ g_\mathbf{A}^{-1} $则只会输出一个唯一的解。 随后，我们对Lattice中的Trapdoor到底长什么样子做了一个简单的探索：看到了所谓的Type 1 Trapdoor其实就是OWF对应的Lattice $ \Lambda $的一组好的基向量（good basis），符合了短并且近似垂直的特性。基于此类Trapdoor，我们还大概了解了一下如何解决格中的一些难题（比如CVP）。…

写在前面 前一段时间写完基于格的GSW全同态加密系统（FHE）后，笔者对格产生了很大的兴趣。由于上学期在学校上的CS355（高阶密码学）讲完FHE之后就结课了，所以还有很多关于格的知识没有讲到。 正如开学的时候CS355第一节课上说的一样：对于其他专业的学生来说，这会是你们密码学方向学习的最后一节课。但是对于密码学方向的人来说，这将会是你们真正入门密码学的第一节课。 这节课结束之后，后面就没有系统性的课程了。在过去的两个月内，为了更加全面的学习格密码学，笔者只好去网上与各个学校搜刮讲座和课件，拼凑起来从头开始学习Lattice的基础定义和几大难题。对于格有一个大致的了解之后，就可以看懂更加进阶的东西，比如IBE、ABE、NIZK、Multilinear Map、iO等等。了解完一圈下来，不得不说格密码学真的是万能的一个密码学分支，可以基本上实现所有密码学的应用（Crypto-Complete）。 关于Lattice-based Crypto的入门知识，有兴趣的大家可以去看笔者的【Lattice学习笔记】这一专题。在这里就假设大家对格已经有一个大致的了解了。从这一期开始，我们开一个新的专题【格密码学进阶】，学习一下更加进阶的格密码学的算法和构造。 这一期，我们来看看格密码学中的一个非常重要的工具：Trapdoor Functions（陷门函数）。 Trapdoor Function（陷门函数）简介 Trapdoor Function（TDF），即陷门函数，是一个密码学中非常常见的一个基础工具。简单的概括一下的话，TDF就是一个普通的函数$ f: D \rightarrow R $，即输入空间为$ D $，输出空间为$ R $。这个函数有两个非常重要的特性： 首先，如果只知道这个函数的本身，那么这个函数就是一个单向函数（OWF）。单向函数是什么意思呢，就是给定一个输入$ x $，我们可以非常快速（efficient）地计算$ f(x) $。但是如果我们只能看到这个函数的输出$ f(x) $的话，我们很难从这个值推算出原本输入$ x $的值来。 虽然OWF的定义在密码学应用上很有用了（比如可以构造出PRG、PRF、Hash Function等等），但是TDF更加特殊的属性是，在生成一个TDF实例的时候，我们会额外生成一个这个函数的一个Trapdoor $ t $。如果不知道Trapdoor $ t $的值，那么原本的TDF仍然是一个OWF。但是如果一旦有人知道了Trapdoor $ t $，那么就可以直接打破单向性，即可以有效的从$ f(x) $中还原回$ x $出来。 Wikipedia上对于TDF使用了上述的一张图片来解释。理解起来很简单：从$ D $到$ R $很容易，但是从$ R $到$ D $很困难。但是如果知道了Trapdoor $ t $，那么从$ R $到$ D $也会非常简单。 TDF在密码学上的应用多不胜数，比如我们最常见的RSA加密算法就基于RSA的一个TDF。在RSA一开始的密钥生成的过程中，我们会生成一对加密和解密的密钥$ (e, d) $。我们可以基于这一对密钥来定义RSA的TDF： $$ f_{RSA}(m) = m^e \text{ mod }N\ f_{RSA}^{-1}(c) = c^d \text{ mod }N\ f_{RSA}^{-1}(f_{RSA}(m)) = (m^e)^d = m \text{ mod }N $$ 因为大整数的有限域（$ \text{mod }N $）中，已知$ m^e $的话，我们很难还原出一开始的$ m $。但是如果我们知道了这个系统的Trapdoor $ t = d $的话，那么我们就可以直接计算$ m^{ed} $然后还原出最初的$ m $来。…

本文取材于Vinod Vaikuntanathan的讲义。讲义本身取材于Noah Stephens-Davidowitz的笔记。 回顾：从SIS到Ring-SIS 在之前的笔记中有所提到从SIS到Ring-SIS的转变，现在我们回顾一下。 $$ h_\mathbf{A}(\mathbf{e}) = f_\mathbf{A}(\mathbf{e}) = \mathbf{Ae} \text{ mod }q $$ 由SIS构造的哈希函数$ h_\mathbf{A} $具有单向且Collision Resistant的特性。但是缺点很明显：因为SIS问题矩阵$ \mathbf{A} \in \mathbb{Z}_q^{n \times m} $的大小的原因，导致了计算这个哈希函数的计算复杂度达到了$ O(nm \log{q}) \approx O(n^2) $之高。 然而，当我们看SIS这个问题的安全性的时候，却发现我们只要靠猜，就能在$ 2^{O(m)} \approx 2^{O(n)} $的时间内就能猜出来。这样一来其实这个哈希函数并没有什么太大的优势：计算复杂度太高，从而导致破解复杂度与计算复杂度的比例过低。 理论上我们需要一个可以快速验算（$ \widetilde{O}(m) $复杂度），并且破解难度保持相等（$ 2^{\widetilde{O}(m)} $复杂度）的一个哈希函数。 之前的笔记中提到的一个尝试就是把矩阵$ \mathbf{A} $横向切成$ l = m/n $份，然后每一份都是一个正方形的等宽矩阵。随后，我们赋予这个等宽矩阵一个特殊的构造：旋转矩阵$ Rot(\mathbf{a}) $。举个例子，如果$ n = 4 $： $$ \mathbf{a} = \begin{bmatrix}1&8&3&4\end{bmatrix}^T\ Rot(\mathbf{a}) =\begin{bmatrix} 1&4&3&8\ 8&1&4&3\ 3&8&1&4\ 4&3&8&1 \end{bmatrix} $$ 这样一来，我们只需要记住向量$ \mathbf{a} $的值，就可以重现整个旋转矩阵了，等于是我们把原本的$ \mathbf{A} $压缩到了$ \frac{1}{n} $的大小。…

Lattice学习笔记08：SIS OWF的应用 到这儿，和SIS有关的内容就了解的差不多了。最后一篇来讲讲SIS OWF的实际应用。 SIS的压缩属性与CRHF 首先我们看SIS OWF的结构： $$ \mathbf{A} \in \mathbb{Z}q^{n \times m}, \mathbf{x} \in {0,1}^m, f\mathbf{A}(\mathbf{x}) = \mathbf{Ax} \text{ mod }q $$ 因为Ajtai给出的安全定义——即$ m > n \log{q} $，这也就是说我们原来有$ m $ bits的信息量，我们等于是把它压缩到了$ n $个$ q $模中的数字，即$ n \log{q} $个bits的信息量。这也正好符合了SIS OWF满射（surjective）的特性，输入空间比输出空间大得多。 基于这一压缩的特性，我们很自然的就可以用SIS OWF来做一个Collision Resistant Hash Function。具体的CR和单向性我们之前也讨论过了。为了巩固知识，我们再来推一边。 首先，SIS OWF的单向性不用多说，因为SIS是一个公认的格中难题，如果我们可以逆向计算SIS的话，那也就代表我们可以解决格中的SIVP问题。 接着，我们需要证明如果SIS OWF是单向的，那么它也是Collision Resistant的。这个证明也不难，我们反过来推，如果我们可以找到SIS OWF的碰撞，那么我们就可以破解它的单向性。 假如给定一个$ \mathbf{A, y} $，我们想要找到一个$ \mathbf{x} $使得： $$ f_\mathbf{A}(\mathbf{x}) = \mathbf{y} $$ 那么，我们首先可以在矩阵$ \mathbf{A} $的任意一个column中（假设是第$ i $列，即$ \mathbf{a}_i $）加上$ \mathbf{y} $的值，构成$ \mathbf{A}’ $。注意因为$ \mathbf{A} $是一个随机的矩阵，所以就算某一列加上了$ \mathbf{y} $，这个矩阵仍然还是随机的。…

Ajtai OWF的参数大小 讨论完了Ajtai OWF（SIS）的安全性之后，现在问题来了：因为SIS问题的定义需要一系列的参数$ m, n, q $，如何定义这些参数，才可以满足之前的安全性证明呢？ Ajtai在96年的paper中指出来，只要$ m, n, q $足够大（large enough），那么$ f_\mathbf{A} $就是单向/collision resistant的。对于$ m, n $的值我们不去变它，因为这个决定了矩阵的维度。但是$ q $这个模组的大小，其实对于Ajtai OWF的安全性来说，差异是不会有太大的，所以大家的目光都放在如何尽可能的压缩$ q $的大小。在这篇paper中，Ajtai要求$ q = n^{O(1)} $，才可以满足安全性证明。 随后，在MR04这一篇paper中，Micciancio与Regev两个人进一步优化了这一证明，使得$ q \approx n^{2.5} $的情况下可以满足安全性。 在GPV08中，Gentry，Peikert，Vaikuntanathan三个大佬又对证明做了一次优化，使得$ q \approx n $的情况下仍然安全。 最后，在MP13中，Micciancio与Peikert把$ q $的大小压到了更小。在paper中，他们指出只要$ q \ge \sqrt{n} $，那么Ajtai OWF就是安全的。原文中的定理是这样的：如果我们可以破解$ \sqrt{n} < q < n $情况下的$ f_\mathbf{A} $，那么我们就可以把这个破解算法当作一个blackbox，然后逐步破解更大的$ q $的Ajtai OWF，即模组为$ q’ = q^c : c > 1 $。 压缩SIS中的模组$ q $ 接下来，我们可以看一下，如何通过反证法来保证$ q > \sqrt{n} $的情况下，Ajtai OWF（即SIS）是安全的。…

Average Case Hardness（平均困难度） Lattice问题最有趣的一点就在于困难度的论证。因为我们知道格中的一些问题是难的，比如说之前讨论的SVP、CVP、SIVP等等，所以基于这些问题构造的新的问题也是难的。反之，如果我们能够解决基于这些难题构造的新问题，那么我们也就可以解决这些难题本身。这一推理的过程，我们称之为reduction（规约）。 在讨论困难度的时候，最常见的一种方法就是讨论平均的困难度，即Average Case Hardness。 举个最简单的例子，在讨论像RSA一样依靠Factorization难度的系统的时候，我们会依靠我们的模组$ N $难以被factor这一难点来构造系统。比如说一个Modular Squaring的函数： $$ f_\mathbf{N}(\mathbf{x}) = \mathbf{x}^2 \text{ mod } \mathbf{N}:\mathbf{N} = p \cdot q $$ 这个函数就是计算一个数字$ \mathbf{x} $在模组中的平方，得到一个Quadratic Residue。这个函数也是Rabin的密码学系统的精髓，它的难度在于如果可以逆向计算$ f_\mathbf{N}(\mathbf{x}) $，我们也可以成功的factor $ \mathbf{N} $。 那么$ f_\mathbf{N}(\mathbf{x}) $这个函数到底有多难计算呢？我们需要看这个函数实例对应的$ \mathbf{N} $这个模组有多难被factor。因为它们之间的安全关系是一一对应的。Rabin给出的安全性证明为：在密码学定义上，只要大部分$ \mathbf{N} = p \cdot q $是难以被factor的，那么$ f_\mathbf{N} $这个函数也是难以被invert的。 理解这个定义很简单，假如我们随便拿到了一个$ f_\mathbf{N} $的实例，那么我们能够逆向它的可能性就基于我们随便拿到一个$ \mathbf{N} $可以factor它的可能性是相似的。这也就是说平均的看（在Average case上），只要我们大概率拿到的$ \mathbf{N} $是难的，那么$ f_\mathbf{N} $也是难的。 Ajtai的OWF（SIS）的平均困难度 同理可得，我们可以用这样的方法来分析之前提到的Ajtai OWF（即SIS）。 我们的OWF $ f_\mathbf{A}(\mathbf{x}) = \mathbf{Ax} \text{ mod }q $的构造其实和之前的Quadratic Residue的构造很相似，同时我们在之前也指出了想要逆向计算$ f_\mathbf{A} $的话，我们等于是需要求解Lattice $ \Lambda(\mathbf{A}) $中的SVP问题。所以$ \Lambda(\mathbf{A}) $的SVP难度与我们的OWF的安全性也是挂钩的。…