基于LWE问题构造密码方案综述
2022-05-27田有亮
杨 楠，田有亮
(1.贵州大学 计算机科学与技术学院，贵州 贵阳 550025；2.黔南民族师范学院 数学与统计学院， 贵州 都匀 558000；3.公共大数据国家重点实验室，贵州 贵阳 550025)
格理论作为几何学中的经典理论，其研究可以追溯到17世纪KEPLER猜想，德国数学家GAUSS通过引入格的概念证明了猜想。MINKOWSKI、HERMITE、BOURGAIN、HLAWKA等的研究促进格理论的进一步发展，在组合优化、信息安全等领域有着广泛的应用。最初，格理论作为密码分析工具被引入到密码学中，用于分析RSA、MH-knapsack等密码体制的安全性。
1996年, AJTAI[1]取得开创性成果，构造出整数格中的随机格类，第一次将任意格上一类困难问题的最坏情况问题归约到求解随机格类的平均困难情况上，使得基于格问题构造可证明安全性的密码体制成为可能。AJTAI等[2]在1997年的计算理论研讨会(symposium on theory of computing, STOC)上，基于格上唯一最短向量问题(unique shortest vector problem, uSVP)的困难性，构造出第一个基于格的公钥密码体制。随后，基于格的公钥密码体制不断出现，但存在密钥尺寸过大、效率不高或缺乏安全性证明的问题。
2005年，REGEV[3]提出容错学习(learning with errors, LWE)问题，利用一个量子多项式规约算法，将求解平均困难情况的LWEn,q,m,x问题归约到求解任意的n维格上最坏情况困难问题判定型近似最短向量问题(decisional approximate shortest vector problem, GapSVPγ)、近似最短独立向量问题(approximate shortest independent vectors problem, SIVPγ)上，从而将任何求解LWE的算法(无论是经典算法还是量子算法)转化为求解格问题的量子算法。目前除了一般的量子加速外，还没有已知求解GapSVPγ或SIVPγ的量子算法显著优于经典算法。
LWE问题有两个主要的版本：搜索型LWE(Search-LWE)问题和判定型LWE (Decision-LWE)问题。通过选择恰当的参数，这两个版本是等价的。在利用LWE问题构造密码方案时，多数使用判定型LWE问题。文献[3]构造出第一个基于LWE问题的公钥加密方案，其加密过程是对明文逐位加密，每次只能加密1 bit，效率较低。为进一步提高效率，在不增加密文大小的情况下，KAWACHI等[4]提出基于LWE问题的多比特公钥加密方案。PEIKERT等[5]给出更大明文空间上的基于LWE问题的有损陷门函数(lossy trapdoor functions, lossy TDFs)，随后 MICCIANICO等[6]对该方案进行优化。
由于LWE 使用中固有的二次开销，造成上述方案的效率相当低。为解决这一问题，2010年，LYUBASHEVSKY等[7]构造出LWE的一个代数变体环-LWE (Ring-LWE, R-LWE)。该方案相对于LWE方案的主要优势是减少密钥尺寸，降低开销。R-LWE问题的困难性可以归约到任意理想格上的近似最短向量问题(approximate shortest vector problem, SVPγ)上。与LWE问题类似，R-LWE问题有两个主要的版本：搜索型R-LWE(Search-R-LWE)问题和判定型R-LWE(Decision-R-LWE)问题。
1994年，SHOR[8]提出著名的Shor量子算法，可以在多项式时间内高效解决大整数分解和离散对数问题，对当时主流公钥密码体制构成潜在威胁。设计可以抵抗量子计算攻击的密码体制是后量子密码的主要任务，基于格的公钥密码被认为是最有可能抵御量子计算威胁的密码体制。在美国国家标准与技术研究院(national institute of standards and technology, NIST)公布的第三轮后量子密码系统的7个提案中，基于格的提案有5个。基于LWE问题构建的密码体制是基于格密码发展实用前景最好的两种构建方案之一。
本文从基于LWE问题构建基于属性加密方案、全同态加密方案、函数加密方案、密钥交换协议、数字签名等5个方面，总结基于LWE问题构建的密码体制取得的重要研究成果。
1 基本知识
1.1 格
定义1格(lattice)。格是Rm中n个线性无关的向量a1,…,an的整数系数线性组合的全体，记为
L=L(a1,…,an)
={x1a1+…+xnan|xi∈Z,i∈[n]}
其中：向量组a1,…,an是格L的一个基；m是格L的维数；n是格L的秩；常用的格是整数格。
1.2 格中困难问题
最短向量问题(shortest vector problem, SVP)。对于给定的一个格，找到它的最短非零格向量。
近似最短向量问题(SVPγ)。L是一个m维格，实数d>1，找到一个格向量v∈L，使得‖v‖≤dλ1(L)。
γ-唯一最短向量问题(uSVP)。给定一个格L，满足λ2(L)>γλ1(L)，找到格中最短非零格向量。
判定型近似最短向量问题(GapSVPγ)。L是一个m维格，实数d>0，若λ1(L)≤d，则yes，若λ1(L)>γ(n)d，则no。
近似最短独立向量问题(SIVPγ)。L是一个秩为n的格，找到n个线性无关的格向量，使得向量的长度不超过γ(n)λn(L)。
1.3 LWE问题
1.4 R-LWE问题
定义5R-LWE分布(R-LWE distribution)。令R=Z[x]/(xn+1)，其中n是2的方幂，Rq=Zq[x]/(xn+1)，从Rq中随机选取一个称为秘密的元素s，χ是R上的一个分布，Rq×Rq上的R-LWE分布As,χ满足：随机均匀选取a∈Rq，从R上的分布χ中抽样得到e，输出(a,b=s·a+emodq)。
定义6搜索型环容错学习(search-R-LWE)问题。从Rq中均匀随机抽取一个秘密s，给定m个从R-LWE分布As,χ中独立抽样的随机对(ai,bi)∈Rq×Rq(随机对中的秘密均为s)，求解出s。
定义7判定型环容错学习(decision-R-LWE)问题。给定m个独立抽样(ai,bi)∈Rq×Rq，其中每一个抽样的分布要么服从As,χ(服从As,χ分布的所有抽样，其均匀选择的秘密固定为s)分布，要么服从Rq×Rq上的均匀分布，判定型环容错学习问题就是以不可忽略的概率区分出每一个抽样满足哪一种分布。
2 基于LWE问题构造密码方案
2.1 基于LWE问题构造基于属性加密方案
基于属性加密(attribute-based encryption, ABE)方案是公钥加密方案的扩展, 提供了高效而简单的数据共享机制，支持细粒度的访问控制。自SAHAI等[9]在2005年欧密会上提出基于模糊身份加密方案，引入ABE思想后，ABE已成为一种具有应用价值的密码原语，由此产生了一系列在效率、表达性、安全性和基本假设之间实现各种权衡的工作[10-19]。
前面提到的大多数工作的安全性与基于双线性映射的假设有关，鉴于已知量子计算对基于群结构的攻击，构建基于格的ABE方案，实现量子计算攻击下的安全性尤为重要。
在AJTAI[1,20]、REGEV[3]等开创性工作的基础上，第一个基于格的基于身份加密 (identity-based encryption, IBE)方案被构造出来[21-23]，其在选择模型下是安全的；AGRAWAL等[24]提出一个具有全安全(full security)的结构。
此后，许多学者对基于LWE问题的ABE方案进行了研究。BOYEN[25]利用格上的LWE问题，通过建立一种新的适合处理复杂访问策略的格操作框架，构造出一个基于密钥策略的属性加密(key policy-ABE,KP-ABE)的方案，在标准模型下是安全的。GORBUNOV等[26]构造了一个新的、高效的，用于短密钥分支程序P的ABE方案，其中短密钥的长度是∣P∣+poly(λ)，λ是安全参数；在具有多项式近似因子的LWE假设下，具有选择性安全(selectively-secure)。BRAKERSKI等[27]针对部分ABE方案中存在属性的长度(表示为二进制字符串)必须在初始化期间确定的问题，通过构造一个基于LWE的ABE方案，使得公共参数的大小在安全参数中是一个固定的多项式，利用这些固定长度参数，对任意长度的属性进行加密；同时，安全性满足半选择性安全(semi-selectively secure)，即敌手可以在得到公共参数之后，但在任何解密密钥之前选择挑战属性，而在此之前，基于LWE问题的结构只能实现选择性安全。AGRAWAL等[28]基于LWE假设，构造了第一个基于对称密钥属性用于非确定性有限自动机(nondeterministic finite automata, NFA)加密方案。方案支持长度无界输入和长度无界机器，即在方案中，私钥与一个长度无界的NFA M有关，密文与一个元组(x,m)有关，x是长度无界的公开属性，m是秘密消息比特，解密恢复m，当且仅当M(x)=1。TSABARY[29]首次为函数类t-合取范式(t-conjunctive normal form，t-CNF)构造了一个基于D-LWE、基于密文策略的属性加密 (ciphertext policy-ABE，CP-ABE)方案，其构造支持无限规模的函数，即每个函数由多项式个子句组成。这些函数类包括NP-验证策略(NP-verification policies)、比特固定策略(bit-fixing policies)和t-阈值策略(t-threshold policies)。
2.2 基于LWE问题构造全同态加密方案
全同态加密(fully homomorphic encryption, FHE)思想，由RIVEST等[30]在1978年提出，允许在不知道私钥的情况下，对密文进行无限量的运算，可以间接地对原文进行相应操作。这一开创性的构想一经提出，整个学术界为之轰动，但经过几十年的探索，一直未能找到既满足全同态加密的所有条件，又容易证明安全性的方案。
2009年，GENTRY[31]基于理想格提出第一个FHE方案。在方案中，作者通过自举(Bootstrapping)密文处理方法，将噪音接近临界值的密文转变为噪音较低的密文，从而实现全同态加密，但是该方案存在效率低、密钥尺寸大的问题。这是一个概念上和实践上都不实用的方案。该方案被称为第一代FHE方案。
在2011年FOCS(Annual Symposium on Foundations of Computer Science)会议上，BRAKERSKI等[32]不同于之前的方案(依赖于各种环中的理想相关的复杂性假设),基于LWE问题，采用重线性技术(re-linearization technique)控制密文的维数，利用维数-模数约减(dimension-modulus reduction)技术，避开稀疏子集和假设(sparse subset-sum assumption)，减少了计算复杂性，构造出第一个可自举的基于LWE问题的有限同态加密方案。在2012年ITCS(Innovations in Theoretical Computer Science Conference)会议上，BRAKERSKI等[33]基于R-LWE问题，采用密钥转换技术(key-switching technique)控制密文维数膨胀问题，用模数转换技术(modulus-switching technique)降低密文运算中的噪声规模增长问题，实现无需自举就可以做到多项式深度的同态运算。但上述两个同态加密方案的密文用向量表示，通过向量的张量积进行密文同态乘法运算会导致密文的维数急剧膨胀。上述两方案被称为第二代FHE方案。
在2013年的欧密会上，基于LWE问题，GENTRY等[34]借助近似特征向量(approximate eigenvector)方法，构造了一个FHE方案，简称GSW13方案。相对之前的方案，GSW13方案中密文由一个矩阵构成，多数情况下，同态运算的加法和乘法是矩阵的加法和乘法，因此该方案渐进性更快，避免了密文维数膨胀问题，同时，不需要密钥转换技术和模数转换技术。相对于文献[32-33]中的BV11方案和BGV12方案，GSW13方案在进行同态加密运算时，不需要获得用户的求解密钥(evaluation key)，求值器(evaluator)可以在知道一些基本参数，不知道用户公钥的情况下进行同态运算。由于需要生成矩阵密文，GSW13方案需要较大的存储空间。该方案被称为第三代FHE方案。
ALPERIN-SHERIFF等[35]介绍了构造FHE的新方法，避免文献[36]中因使用Barrington转换带来的巨大开销。文献[35]把解密看作一个算术电路，解密中的内积可以用一组循环排列计算；其利用这一特性，构造了一个自举程序，该程序比文献[36]的方案更快地更新密文。HIROMASA等[37]在GSW13加密方案中提出了一种加密矩阵技术，使用这种技术来优化文献[36]的自举方案。GSW13的后续工作主要是构建基于R-LWE的方案[38-40]。
多密钥全同态加密(multi-key full homomorphic encryption, MKFHE)可以对不同公钥(用户)下加密的数据进行任意操作，最终的密文可以由所有相关用户共同解密。因此，MKFHE在安全多方计算(security multi-party computation, MPC)方面具有天然的优势和应用价值。2012年，LPEZ-ALT等[41]基于NTRU(number theory research unit)密码体制，提出了第一个MKFHE方案，但该方案的安全性基于多项式环上的非标准假设。在2015年的欧密会上，CLEAR等[42]构造出第一个基于LWE问题的GSW-多密钥全同态加密方案，其安全性可以归约到理想格上最坏情况困难问题上。
2.3 基于LWE问题构造函数加密方案
函数加密(functional encryption, FE)方案[43-44]是公钥加密方案的一种推广。它克服了公钥加密方案中固有的全有或全无、基于用户的数据访问，支持细粒度、基于角色的访问，并允许用户精确地控制由密文透露给给定接收者的信息量。FE允许拥有秘密函数解密密钥的用户获得被加密消息的特定函数值，即在用于函数类F的FE方案中，加密消息x得到密文CTx，由函数f导出秘密函数解密密钥dkf,持有dkf的给定接收者可以获得f(x)，不会获得关于信息x的其他信息。
现在，通用FE方案被视为现代密码学的圣杯。一些工作已经朝着这个目标取得了进展，但没有从标准假设中构造出通用结构。由于通用的FE方案距离实现还很遥远，不同的工作专注于为特殊的函数类构建FE方案，比如谓词加密或内积函数加密(inner-product functional encryption，IPFE)方案。
IPFE是FE方案的一种特殊形式。在方案中，被加密的信息是向量x，函数解密密钥dky与向量y有关,向量y与向量x具有相同的维数，解密得到内积
针对文献[45]中存在的问题，在2016年的欧密会上，AGRAWAL等[46]提出的构造是由密钥空间上具有同态性质的哈希证明系统(hash proof systems)获得的，可以抵抗自适应攻击，其基于多提示扩展LWE (multi-hint extended-LWE, mheLWE)问题的构造，能够对内积取素数模的运算进行安全的函数加密，同时作者证明素数域上的内积，可以用来构造用于所有电路有界碰撞的IPFE方案。
GORDON等[47]提出多用户函数加密方案(multi-client functional encryption, MCFE)。MCFE方案是FE方案的自然延伸，在MCFE方案中，数据来自不同的用户端，这些用户可能彼此不信任，并可能被敌手独立、自适应地破坏。在设计MCFE时需要克服的主要挑战是，密文的不同部分必须在不能共享任何随机性的情况下进行设计。文献[47]中的MCFE方案是支持加密标签的，它允许加密器在解密过程中限制可能发生的混合和匹配(mix-and-match)的数量，通过只允许对基于相同标签生成的密文进行解密来实现。JEREMY等[48]在2018年亚密会上和ABDALLA等[49]在2019年亚密会上，对这种柔性形式的FE方案进行了研究。前者基于不同的标准假设提供了一个通用结构，但其密文大小随用户数量二次方增长；后者基于分布文献处理(distributed document handling, DDH)假设给出MCFE方案，该假设需要较小的内积空间，限制了适用范围。针对文献[48-49]中的不足，在随机预言机模型下，ABDALLA等[50]提出基于MDDH (Matrix- DIFFIE-HELLMAN), 判定型合数剩余(decisional composite residuosity, DCR) 和 LWE三种假设的线性长度密文结构。在文献[50]中，基于LWE问题的MCFE方案为LWE问题引入噪声项，因此在安全证明期间无法模拟通过加密查询泄露的信息；作者使用噪声泛洪技术(noise flooding techniques)克服这一挑战，并通过将密文舍入到更小的空间来避免低效率的缺点，这样，在舍入操作期间噪声项就消失了。
2.4 基于LWE问题构造密钥交换协议
密钥交换协议使得通信双方可以在不可信的信道上交换密钥。第一个著名的密钥交换协议是DIFFIE和HELLMAN[51]提出的，称为Diffie-Hellman(DH)密钥交换协议。它的安全性基于离散对数这一数论困难问题，这一困难问题很难抵御量子计算机攻击[52]。构建基于格中困难问题的密钥交换协议被认为是后量子密钥交换协议的候选方案之一。
PEIKERT[53]认为基于LWE问题的密钥交换协议在技术上是可行的，但本人并没有给出具体的方案。LINDNER等[54]给出了基于LWE问题的类DH密钥交换技术的框架。文献[53-54]中，作者试图要解决的问题是误差消除，即如何从两个近似值中抽取共享秘密，使通信双方通过计算协商得到密钥。DING[55]提出第一个可证明安全性的基于LWE问题的密钥交换协议，该协议计算效率高，可推广到R-LWE问题中；协议利用信号函数四舍五入，从两个非常接近的值中提取共享密钥，解决了上述误差消除问题。LWE问题本身可以被视为具有小误差的某种形式的内积，在某些应用中可以通过某种方式消除；而该协议可以看作是这一思想在双线性配对情况下的扩展，即带有误差的双线性形式配对。协议的有效性取决于非交换环(LWE问题)和交换环(R-LWE问题)中乘法的结合性和交换性。
ALKIM等[56]构造出一个新的基于R-LWE问题的密钥交换协议；该协议提出了一个新的误差消除算法，主要贡献是将R-LWE问题中的秘密和误差服从的离散高斯分布改为二项分布，使得抽样参数更加容易。SAARINEN等[57]提出文献[56]中密钥交换协议的一个变种，并优化了文献[56]中的误差消除算法，给出了该算法的快速实现。DING等[58]提出了一种基于小整数解(short integer solution，SIS)问题和LWE问题的密钥交换算法。即甲方使用LWE问题来确保他发送给乙方的内容的安全性，乙方使用SIS问题来确保他发送给甲方的内容的安全性。很明显，系统不是对称的。切换后，通过文献[55]提出的基于LWE问题的密钥交换中的信号函数，可以从两个非常接近的值中提取共享密钥。
2.5 基于LWE问题构造数字签名方案
数字签名方案是密码学中的一个基本原语，是各种高级密码协议的重要组成部分。自问世以来，在标准模型下，学者提出众多方案，这些方案的困难性可以归约到困难的数论问题上(整数分解问题、离散对数问题等)；鉴于密码分析的预期进展，为目前使用的签名方案(如RSA算法和椭圆曲线数字签名算法(elliptic curve digital signature algorithm, ECDSA))找到替代方案是很重要的，最有希望取代这些方案的是基于格的签名方案。
第一个紧安全性归约(tight security reduction)基于格的数字签名方案是GPV方案[59]，它的实例化是安全的，但效率不高。在其后几年构造出的基于格的数字签名方案中，既没有紧的归约性，也没有可证明安全性的实例化；虽然可以通过应用分叉引理(Forking Lemma)证明这些方案的安全性，但该引理本质上导致了不紧的安全性归约(non-tight security reduction)。
ABDALLA等[60]基于R-LWE问题构造了一个数字签名方案，该方案是对KATZ等[61]方案的改进，避开了分叉引理，但是它的紧归约性涉及到一个不实用的大的模数。GÜNEYSU等[62]构造了一个基于R-LWE问题的签名方案。该方案是通过对文献[63-64]中方案进行组合和优化来实现的，使用文献[64]中的方法对文献[63]中的方案进行改进，显示了如何通过将问题从R-SIS改为R-LWE，显著减小密钥和签名的大小。AKLEYLEK等[65]基于R-LWE问题构造了第一个具有可证明实例化的数字签名方案。
上述文献[60，62，65]中，基于R-LWE问题构造的数字签名方案，都是随机预言机模型下安全的。ZHANG等[66]基于LWE问题，构造出一个在标准模型下紧安全的签名方案来对抗多用户自适应选择消息攻击。
3 优势和挑战
3.1 优势
由于可以将格上最坏情况困难问题归约到LWE问题及其变体上，基于其构造密码方案时不需要考虑格上困难问题，就可以达到抗量子攻击的目的。在构造方案时，运算过程仅涉及到一些简单的整数上代数运算，例如向量、矩阵的运算或者特殊代数结构上的多项式运算，故运算过程简单，效率高，易于实现。相对于基于格构造的密码方案，基于LWE问题及其变体构造的密码方案，大幅度减少了方案中的密钥和密文的尺寸。
在后量子密码学中，实现后量子密码算法主要有4种方法：基于多变量的密码算法、基于哈希的密码算法、基于编码的密码算法，基于格的密码算法。基于多变量的密码算法虽然计算速度快，但存在公钥尺寸较大的问题；基于编码的密码算法也存在公钥尺寸大的问题；基于哈希的密码算法存在输出长度较长的问题。相对于前3种算法，基于格的算法在安全性、计算效率、密钥尺寸上，实现了更好的平衡。由于基于格的密码算法的安全性是基于格中困难问题的，在相同的安全性要求下，与前3种算法相比，基于格的密码算法的公私钥尺寸更小，计算效率更高。
3.2 挑战
本文总结了基于LWE问题构造的5类密码方案，虽然LWE问题及其变体在各类密码方案的设计和安全性方面有很大的潜力和优势，但仍然有很多挑战有待于密码学家进一步研究、解决。
基于LWE问题及其变体构造方案时，为保证方案的安全性，矩阵的维数或多项式的阶较高，造成存储开销过大。同时，由于安全性要求，矩阵的维数、系数的维度和模数取值较大，相对于经典的密码方案，基于LWE问题及其变体的密钥尺寸较大。 运算时，环上多项式乘法、取模操作等累加到一起，会造成计算效率低。
3.2.1构造基于属性加密方案
目前，基于LWE问题构造ABE方案的工作主要围绕构造安全性更高的方案，设计高效的CP-ABE方案，以及方案更广泛的使用范围开展研究。主要存在以下挑战：
1)目前的方案，其安全性主要是选择性安全的，仅有的几个全安全的方案，仅仅支持弱的访问策略。选择性安全是一种弱的安全，对敌手的能力有很强的约束，不能抵抗现实世界中的许多类型的攻击。
2)目前的方案中更多的是KP-ABE方案，如何构造高效的CP-ABE方案仍然是一项具有挑战性的工作。
3)基于LWE问题，对于一些重要的访问策略，是否存在一个真正去中心化的MA-ABE(multi-authority ABE)密码方案还需要进一步深入研究。
3.2.2构造全同态加密方案
部分同态加密方案由于对运算的要求，可以在经典密码学中实现；但是FHE方案目前只能基于格问题来构造，在实用化方面取得一定进展的是第二代、第三代FHE方案，它们都是基于R-LWE问题构造的。
目前，在基于LWE问题构造FHE方案的工作中, 由于GENTRY的自举程序是实现FHE方案的唯一方法，如何对自举程序进行优化是目前的主要工作之一，同时，对GSW13方案的优化也是一项重要工作。基于LWE问题的FHE方案存在的最大不足就是效率低(自举程序)和巨大的存储消耗(矩阵运算)，如何进一步改进方案，使方案实用化是亟须解决的问题。
3.2.3构造函数加密方案
由于构造用于一般函数的通用FE方案距离实现还很遥远，目前基于LWE问题的FE方案主要是针对小范围内的特殊函数，例如线性函数或多项式，较为热门的是基于LWE的IPFE方案。该方案主要存在两个不足：不能指定接收者的身份和不能认证密钥发布者的身份，这两个不足会造成在一些应用场景中使用该方案时的安全问题，同时，如何在更大的范围构造基于LWE问题的FE方案是一项具有挑战性的工作。
3.2.4构造密钥交换协议
目前基于R-LWE问题构造的密钥交换协议基本上都是根据PEIKERT[67]建立的Reconciliation技术实现的，如何在此基础上设计新的、较实用的密钥交换协议是值得思考的问题。同时，相对于经典的公钥算法构造的密钥交换协议，基于R-LWE问题构造的密钥交换协议的一个瓶颈是通信开销过大；因此，今后工作的一个重要方向就是在保证基于R-LWE问题构造的密钥交换协议的安全性和性能平衡的同时，如何有效地降低通信开销。
3.2.5构造数字签名方案
大多数基于格的数字签名方案的构造主要基于两种途径：hash-and-sign签名方法和Fiat-Shamir方法，相对于第一种方法，第二种方法更加简单、高效。近几年，基于格中困难问题构造的数字签名方案基本上基于第二种方法，但在构造过程中存在的一个最大挑战是签名长度过大，这也是其不能实用化的一个最大障碍。
4 总结
本文概述了基于LWE问题及其变体构造的各类密码方案，与经典密码方案相比，基于LWE问题及其变体构造的密码方案在抗量子攻击方面具有很大的潜力，但在效率和实用性方面还有很大的差距。这表明其还有待于进一步完善与发展，无论是理论研究还是实用化，基于LWE问题及其变体的密码方案的设计都有很大的理论价值和实际意义。
