两类基于容错学习的多比特格公钥加密方案
李增鹏, 马春光, 张磊, 张雯雯
哈尔滨工程大学计算机科学与技术学院,黑龙江哈尔滨 150001
马春光 machunguang@hrbeu.edu.cn

作者简介: 李增鹏(1989—),男,山东,博士研究生,主要研究方向为密码学与信息安全;马春光(1974—),男,黑龙江,教授,博士,主要研究方向为密码学与信息安全;张磊(1982—),男,黑龙江,博士研究生,主要研究方向为隐私保护;张雯雯(1993—),女,黑龙江,硕士研究生,主要研究方向为隐私保护。

摘要

作为后量子密码的经典困难问题,LWE多用于设计各种基于格的公钥加密算法和密码协议。GENTRY等人基于LWE假设提出了对偶版本的Regev加密方案,即GPV加密方案,进一步推动了格公钥密码的发展。当前的密码算法构造多利用Regev方案或GPV方案作为基础密码学组件。然而,现有的基于格公钥加密方案的研究多集中在单比特加密,对于多比特加密的格公钥加密方案,通常采用两种简单的方式得到,或者通过直接对矩阵加密获得,或者通过累加迭代单比特加密方案获得。以上两种计算开销大且效率低下。文章受LI等人构造的多比特全同态加密方案启发,分别构造了两类新的公钥,使其公钥中包含了多个LWE实例,而不再只含有一个LWE实例。进而利用两种新的公钥,分别以Regev加密方案和GPV加密方案作为基础密码学组件,构造了两类格基多比特加密方案,并在LWE假设下,证明两个方案是选择明文安全的。

关键词: 格基密码; 容错学习; 多比特加密; 全同态加密
中图分类号:TP309 文献标志码:A 文章编号:1671-1122(2017)10-0001-07
Two Types LWE-based Multi-bit Lattice-based Encryption Schemes
LI Zengpeng, MA Chunguang, ZHANG Lei, ZHANG Wenwen
College of Computer Science and Technology, Harbin Engineering University, Harbin Heilongjiang 150001, China
Abstract

As a classical hard problem of post quantum cryptography, LWE was used to design various public-key encryption algorithms and cryptographic protocols based on lattice. Based on LWE assumption, Gentry proposed a dual version of the Regev encryption scheme, which further promoted the development of public key cryptography. It causes that most existing cryptographic algorithm constructions use Regev scheme or GPV as the basic cryptography building block. However, most existing researches on lattice-based public key encryption scheme focus on the single bit encryption, but two simple methods usually were used to obtain the multi bit encryption, i.e., either encrypting the matrix directly, or, iterating single bit encryption schemes. These two kinds of calculation are costly and inefficient. In this paper, inspired by the multi-bit fully homomorphic encryption scheme by Li et al., two kinds of new public keys are constructed respectively, which contain multiple LWE instances, instead of only one. Then we construct two kinds of multi-bit lattice-based encryption using two new public keys, i.e., Regev and GPV as the building blocks respectively, and proved them CPA secure under LWE assumption.

Key words: lattice-based cryptography; learning with errors; multi-bit encryption; FHE
0 引言

1997年, AJTAI[1]等人首次提出了一个基于格的困难假设的AD加密方案, 尽管当格的维数很高时, AD方案的效率不高, 且未实现可证明安全性分析, 但证明了基于格设计密码学原语的可能性。自此, 格公钥密码便广受关注。随后, 容错学习(Learning with Errors, LWE)假设的提出为格基公钥密码学引入新的发展动力。尤其是Regev格密码所基于的安全假设的平均难度与最大难度相当, 在一般情形下求解LWE问题并不比在最坏情形下求解一些著名格近似问题简单, 而且Regev格密码攻击算法大都为亚指数时间攻击算法, 使其可以抵抗量子攻击。此外, Regev格密码运算简单, 多为矩阵和向量运算(通常只需要线性运算), 且可并行操作, 操作数大多是机器字级别, 具有简单、快速实现的特点。正因为格基公钥密码在安全性和性能等方面具有独特的优势, 使其成为后量子密码密码领域的典型代表。

概括来说, LWE假设是给定一个m× n的矩阵A和向量b=As+e(mod q)(其中, eZmq是一个“ 短” 错误向量)去计算sZnq。不难发现, 利用LWE假设的灵活性可实例化密码学的解(私钥)。目前, 基于LWE假设的公钥密码系统主要有两类, 一类是基于标准LWE假设的Regev公钥加密方案[2]; 一类是基于Dual-LWE假设的Gentry-Peikert-Vaikuntanathan(GPV)公钥加密方案[3]。以上两种公钥加密方案主要关注单比特加密。在基于格的多比特公钥密码系统方面研究成果并不理想, 很少有文献关注多比特加密。主要原因是目前基于格设计的公钥密码系统不能兼顾公钥密码的系统效率和安全证明。例如, KAWACHI[4]等人给出了一种多比特公钥密钥系统的通用构造, 只兼顾多比特方案的实现但没有严格的安全性分析。PEIKERT[5]等人为构造茫然传输协议, 给出了基于(Dual-mode)的多比特格公钥加密, 有安全证明但无效率。BRAKERSKI[6]等人为构造多比特加密的全同态加密方案[7, 8], 利用封装密文技术给出了一种多比特加密构造。但上述方案的本质可以看作是通过迭代单比特加密算法来实现多比特加密。基于此, 受LI[9]等人工作启发, 本文直接给出两种更为直接的格公钥加密方案, 并给出安全性证明。

1 预备知识
1.1 高斯错误分布

对于任意实数α > 0, 定义分布 Ψ̅α (n)Zq上的一个离散高斯分布, 均值为0, 标准差为\(\frac{\alpha}{\sqrt{2\pi}}\), 且模q近似到最近正整数。分布Ψ α T=R/Z上的一个连续高斯分布, 均值为0, 且标准差为\(\frac{\alpha}{\sqrt{2\pi}}\)。χ * k分布为kχ 分布的独立样本之和。

此外, R上正态高斯分布是一个连续正态分布, 并定义密度函数f(x)= 1σ2πexp(-(x-μ)22σ2)。为方便起见, 本文用参数s替代 1σ2π并假设均值μ 为0。此时, 概率密度函数为 Ds(x)= 1Sexp(-π||x||2S2)。同理, m维高斯分布可以定义为Ds(x)= 1Sexp(-π||x||2S2)。因此, 对于∀ xR, , x< sω(loglogn)

1.2 格

格指Rm上离散子群张成实向量空间。向量空间中的一组基通过整系数线性组合成格。故格可以看作m维格点。

定义1 格 令A={a1, a2, …, an}为Rmn维线性无关向量, 即矩阵ARm× n, 格是通过基A生成的集合L(A)= i=1nx1ai|xiZ

由此可见, 格为给定矩阵的列的整数线性组合。

1.3 LWE问题

LWE问题是由LPN问题[10]推广泛化而来, 是当前密码学领域基础且重要的密码学原语, 由REGEV[2]在2005年首次引入。本文只介绍LWE的判定问题。

定义2 LWE判定问题(Decision-LWE) 对于正整数m, n, q≥ 2且m× n, 向量sZnq, 存在如下两个分布:1)均匀选取的分布(A, y)← (Zqm× n× [0, q)m); 2)分布(A, ATs+e(mod q)), 其中, AZqn× m, eχ 。如果分布(A, y)和分布(A, ATs+e(mod q))是不可区分的, 则LWEm, n, q, χ 问题是困难的。

需要注意:1)令e选取自标准差为σ 的离散高斯分布Dσ , 对于e=(e1, …, em), eiDσ 独立抽m, i∈ [m]个样本。因此, ⎥⎥e⎥⎥2来自χ 2分布且均值为2, 有⎥⎥e⎥⎥≤ mσ。2)根据文献[11]中引理4.4, 有Pr(||e|| σm)1-(ke1-k22)m, 则对于k> 0, 存在||e|| mσ

2 多比特的Regeve格公钥加密

本文给出了两类多比特加密方案的构造方法。

2.1 Regev密码系统

利用单比特Regev密码[2]来定义多比特密码系统。单比特和多比特十分相似, 实际上, 多比特是用加密一个向量来代替加密多个比特。将χ 定义为-Ψ α (n)上的分布, 则有:

1) paramsSetup(1λ , n, m, q, α )

输入参数n, m, qZ, α (> 0)∈ R, t, r, lZ; 输出params:=(n, m, q, χ , t, r, l)。

2)(pk, sk)← KeyGen(params)

(1) skSecretKeyGen(1λ , params)

随机均匀选取秘密向量sZnq(s=(s[1], …, s[n])∈ Znq), 输出私钥sk=s

(2)pkPublicKeyGen(1λ , params)

随机均匀选取AZqm× n, 定义向量b=As+e(mod q)Zmq, 其中, 错误向量eZmq中每个元素选自分布 Ψ̅α (n)(均值为0, 标准差为σ ); 输出pk=(A, b)。

3)cEnc(pk, μ )

对于任意的消息μ ∈ {0, 1}, 均匀选取随机参数向量rZm2, 计算并输出密文 C=ATr, bTr+q2μq=(c0, c1)qZqn×Zq

4)μ 'Dec(sk, c)

对于私钥sk=s及对应解密密文c=(c0, c1)∈ Zqn+1, 执行如下操作:

[c1-sT· c0]q=[bTr+ q2μ -sTATr]q =[eT· r+ q2· μ ]q=[e+ q2· μ ϵ Zq](1)

其中, e=eTr为系统引起的错误(噪声), μ 为明文, 如公式(2)所示。需要说明的是, 参数q要远大于标准差σ n=dim(b)才能正确解密(参考文献[2]中的引理5.1)。

μ=0μ'=01μ'=q2(2)

因篇幅限制, 本文省略Regev加密算法的正确性和安全性分析, 详细分析可参考文献[2]。

2.2 多比特的Regeve格公钥加密方案设计

目前格公钥加密方案多针对单个比特进行加密, 但单比特加密模式的效率过于低下, 为了提高格公钥加密方案的效率, 特别是随着全同态加密的发展[7], 若干多比特加密的全同态加密方案随之被提出[6, 9, 12, 13]。现阶段, 基于LWE假设的多比特全同态加密方案主要有两类, 一类是Brakerski-Vaikuntanathan(BV)多比特加密[13, 14, 15]; 另一类是Gentry-Sahai-Waters(GSW)[16]的多比特加密[9, 10, 11, 12]。但这两类方案均未对其基础密码学组件(Regev或GPV加密方案)的多比特加密进行讨论。

因此, 本文着重讨论多比特的Regev和GPV加密方案, 采用了PVW密文打包技术[5]。本文给出了一种多比特的Regeve格公钥加密方案(mRegev), 具体来说, PEIKERT[5]等人发现相同的Regev密文向量可以利用多个密钥向量来加密多个比特, 而解密第i个比特是用第i个私钥通过解密算法Dec(⋅ )来实现。将所有的密钥si作为矩阵S的行, 如果整数向量z=Sc形如z=k· q+u· q2+e, 其中, ke都是小整数向量, 那么就得到一个加密明文比特向量的密文。

此外, 加密单比特明文的密文维数为(m+1), 利用迭代方法, 加密l个明文比特得到的密文维数为l⋅ (m+1)。PVW密文打包技术通过将多个明文比特打包到单个密文中降低其密文维数扩展率, 获得一个(m+l)维的密文。

实际上, 多比特方案是通过加密一个向量来代替单比特方案中逐比特加密的。错误分布χ 为分布 Ψ̅α (n)上的分布, 对于多比特方案, 给定参数, 执行如下程序:

1)paramsSetup(1λ , n, m, q, χ , t, r, z)

输入参数n, m, qZ, α (> 0)∈ R, t, r, lZ; 输出params:=(m, n, q, χ , l)。

2)(pk, sk)← KeyGen(params)

(1) skSecretKeyGen(params)

均匀随机选取秘密矩阵向量S=(s[1, 1], …, s[n, l])∈ Znq× l; 输出私钥sk=S

(2)skPublicKeyGen(params)

均匀随机选取矩阵AZqm× n, 并定义向量B=AS+E(mod q)∈ Znq× l, 其中, 错误矩阵向量EZqm× l中每个元素选自分布 Ψ̅α (n); 输出pk=(A, B)。

3)cEnc(pk, uZtl)

对于任意消息uZtl, 执行如下操作:

(1)均匀选取随机参数向量r∈ {-r, -r+1, …, r}m

(2)计算密文c:=[(ATr, BTr+f(u))]q=[(c0, c1)]qZnq× Zql, 定义函数f:∈ Zlt→ ∈ Zql, 使得Zlt中每个元素乘以后映射到Zql中, 并取近似最小正整数, 即f(u)= qtu

4)uDec(sk, cZqn+l)

私钥sk=s及对应解密密文c=(c0, c1)∈ Zqn+l, 操作如下:

(1)定义函数f-1Zlq→ ϵ Zlt, 使得分布Zlq上的元素映射到分布Zlt上, 且取近似最近正整数。

(2)解密密文c=(c0, c1)∈ Zqn+l为f-1(c1-STc0)=f-1(e+ qtu), 即

[c1-STc0]q=[BTr+ q2u-STATr]q=[e+ q2· u]qϵ Zlq(mod q) (3)

其中, e=ETr为系统引起的噪声。

2.3 性能分析

2.3.1 正确性分析

通过分析算法加密和解密过程中引起的错误(噪声)规模来分析方案的正确性。

引理1 令q, n, N, ⎢χ ⎥≤ B为Regev公钥加密方案的参数; 令sZn为任意向量; 消息m∈ {0, 1}为明文比特; 密文c是消息m在公钥P下加密得到的(令PPublicKeyGen(S), cEnc(P, u))。则对于e(⎢e⎥≤ mB, ⎢e⎥≤ mlB)仍保持 c, (I, -S)=q2u+(mod q)

证明:令r为随机元素样本, u为扩张之后的消息向量。在mRegev加密方案下, 有

(4)

对于f1, 由于P:=[B||A]∈ Z(n+l), 则有

F1=rT· P· (I, -S)= rT· (B, A) · (I, -S)=( rT· B, rTA)· (I, -S)= rTBI- rTAS= rT· (B-A· S) rTE= r, E(mod q)(5)

由于f2= q2(u, 0, , 0)TI, S=q2u(mod q), 由f1和f2可得 c, (I, -S)=f1+f2=r, E+q2u(mod q)

由于所有的运算操作均在Zq上进行, 因此, 不妨在(-q/2, q/2]中取值。为保证f1+f2与m有相同的奇偶性, 则限制||f1+f2||< q/2。令Bχ -界为从分布χ 中取样的元素规模, 即Bχ =sup{||a||:aχ }, 方便描述, 简记为Bχ , 因此有

||c, (I, -S)||q2u+r, E=q2u+||i=1m1mj=1I1lr[i]Eij||q2uγRi=1m|ri||ei|(6)

因为e[i]= j=1I1lEi[j], 根据切比雪夫不等式

||c, (I, -S)||q2uγRi=1Nj=0d-10d-1rij2|ei|q2uγRi=1N1Nj=0d-10d-112|ei|q2uγRdi=1N1NlBx(7)

可知, 若要解密正确, 则存在 γRdNlBx< q/4, 可以得到Bχ < (q/4-⎣q/2⎦)/m。注意到, 由于||ei||≤ Bχ , 如果d=1, 那么需要eϵ -q2-q2m, , q2-q2mm才能够保证解密正确。又因为|〈r, E〉|≤ mlB, 所以引理得证。

引理2 令sZn为秘密向量, 密文cZqn+1使得〈c, (1, s)〉= q2u+e(mod q), 且u∈ {0, 1}, |e|< ⎣q/2⎦/2, 则有Dec(s, c)=u

证明:c0=[〈c, (1, s)〉]q= q2u+e(mod q), 其中, [ 2·c0q]2=[ 2·q2·u+e)/q]2=[ 2·q2u+2e/ q]2。因为|2e/q|< 2(q/4)/q=1/2, 所以解密正确。

2.3.2 安全性证明

引理3(安全性[17]) 令q, n, χ (|χ |≤ B)为LWEn, m, q, χ 的参数。对于任意的m∈ {0, 1}, 如果有sSecretKeyGen(1λ ), PPublicKeyGen(s), cEnc(P, m), 则LWEn, m, q, χ 的联合分布(P, c)与均匀分布Z(n+1)× Z(n+1)计算不可区分(即使攻击者已知s)。

下面将证明mRegev方案是INDCPA安全的。

定理1 对于任意概率多项式时间(PPT)的敌手A, 有Pr[(pk, sk)← Gen(1λ ); b← {0, 1}; b’ ← ALoRb(· , · )(pk)b’ =b-1/2]|negl(λ ), 那么Regev方案是INDCPA安全的。如果有Multi-Message Oracle LoR(m0, m1)返回Enc(pk, m0), 那么对于∀ PPT A有:

AdvPKE, ACPA=|prExpPKECPA1-Pr[ExpPKECPA0=1]|=PrPrb'=1b=1-PrPrb'=1b=0=negl(λ)(8)

ExpCPAPKE(b)定义如下:

1)挑战者C执行(pk, sk)← KeyGen(1λ )并将pk发送给敌手A

2)敌手A选取两个消息m0m1, 并将其发送给挑战者C

3)预言机LoR(m0, m1)执行Q(k)次查询。

4)挑战者会计算生成挑战密文cEncpk(mb; r), 并将其发送给敌手A

5)敌手A返回给挑战者自己的猜测b'

证明:对于多比特INDCPA游戏, 敌手可以访问多次加密预言机Encpk, b(⋅ , ⋅ )。输入两个相同长度的消息m0m1, 消息m=(m(1), m(2), …, m(Q(kappa))), 令Enc(pk, b)(m0, m1)=defEncpk(mb)。

1)Game.0=ExpCPAPKE(0)是多比特的INDCPA游戏, 具体如下。

(1)初始化:挑战者C执行(pk, sk)← KeyGen(1λ ), 并将pk发送给敌手A

(2)查询1:敌手A选取两个消息m0(1)m1(1), 并将其发回给挑战者C执行1次查询。

(3)挑战1:挑战者C接收消息后计算生成挑战密文c(1)Encpk(m0(1); r), 并将其发送给敌手A

(4)查询2:敌手A选取两个消息m0(2)m1(2), 并将其发送给挑战者C执行1次查询。

(5)挑战2:挑战者C接收消息后计算生成挑战密文c(2)Encpk(m0(2); r), 并将其发送给敌手A

(6)重复查询Q(k)次。

(7)查询Q:敌手A选取两个消息m0(Q)m1(Q), 并将其发送给挑战者C执行1次查询。

(8)挑战2:挑战者C接收消息后计算生成挑战密文c(Q)Encpk(m0(Q); r), 并将其发送给敌手A

(9)猜测:敌手A返回给挑战者自己的猜测b'

2) Game.1:Game.1与Game.0相同, 只是在Game.1中, 敌手A选取消息m0m1的第2个比特, 具体过程如下。

(1)初始化:挑战者C执行(pk, sk)← KeyGen(1k), 并将pk发送给敌手A

(2)查询1:敌手A选取两个消息m0(1)m1(1), 并将其发送给挑战者C执行1次查询。

(3)挑战1:挑战者C接收消息后计算生成挑战密文c* ← Encpk(mβ (1)r1), 并将其发送给敌手A

(4)查询2:敌手A选取两个消息m0(2)m1(2), 并将其发送给挑战者C执行1次查询。

(5)挑战2:挑战者C接收消息后计算生成挑战密文c(2)Encpk(m0(2); r2), 并将其发送给敌手A

(6)重复查询Q(λ )次。

(7)查询Q:敌手A选取两个消息m0(Q)m1(Q), 并将其发送给挑战者C执行1次查询。

(8)挑战2:挑战者C接收消息后计算生成挑战密文c(Q)Encpk(m0(Q); r), 并将其发送给敌手A

(9)猜测:敌手A返回给挑战者自己的猜测b'

3)证明Game.0和Game.1计算不可区分Game.0≈ cGame.1, 即⎢Pr[Game.1=1]-Pr[Game.0=1]⎥≤ AdvCPAA', PKE(λ )。

(1)初始化:挑战者C'执行密钥生成算法(pk, sk)← KeyGen(1λ ), 并将公钥pk发送给敌手A'(这里, A'同时充当敌手A的挑战者C, 为避免混淆, 以下记为A'/C), 而A'/C不做任何处理又将接收到的公钥pk直接发送给敌手A

(2) 查询1:敌手A选取两个消息m0(1)m1(1)发送给

A'/C, 而A'/C不做任何处理又直接将消息m0(1)m1(1)发送给挑战者C'

(3)挑战1:挑战者随机选取β ← {0, 1}, 计算生成挑战密文c* Encpk(mβ (1); r1), 并将其发送给A'/C, 而A'/C不做任何处理又将挑战密文c* 直接发送给敌手A

(4)查询2:敌手A选取两个消息m0(2)m1(2)发送给A'/C, 而A'/C在接收到两个消息m0(2)m1(2)后, 计算生成挑战密文c(2)Encpk(mβ (1); r2), 并将其挑战密文c(2)发送给敌手A

(5)执行步骤(4)Q-1次。

(6) 挑战2:敌手A选取两个消息m0(Q)m1(Q)发送给A'/C, 而A'/C接收到两个消息m0(Q)m1(Q)后, 计算生成挑战密文c(Q)Encpk(mβ (Q); rQ), 并将其挑战密文c(Q)发送给敌手A

(7)猜测:敌手A给出自己的猜测b'返回给A'/C, 而此时A'/C直接将b'返回给挑战者C'

4)Game.2:Game.2与Game.1相同, 只是在Game.1中, 敌手A选取两个消息m0m1的第3个比特, 即m0(3)m1(3), 故此处不再赘述。

5)证明Game.1与Game.2计算不可区分Game.1≈ cGame.2, 即⎢Pr[Game.2=1]-Pr[Game.1=1]⎥≤ AdvCPAA', PKE(λ )。

(1)初始化:挑战者C'执行密钥生成算法(pk, sk)←

KeyGen(1λ ), 并将公钥pk发送给敌手A'(这里, A'同时充当敌手A的挑战者C, 为避免混淆, 以下记为A'/C), 而

A'/C不做任何处理又将接收到的公钥pk直接发送给敌手A

(2)查询-挑战1:敌手A选取两个消息m0(1)m1(1)发送给A'/C, 而A'/C接收到两个消息m0(1)m1(1)后, 计算生成挑战密文, 并将其挑战密文c(1)发送给敌手A

(3)查询2:敌手A选取消息m0(2)m1(2)发送给A'/C,

A'/C不做任何处理又直接将消息m0(1)m1(1)发送给挑战者C'

(4)挑战2:挑战者C'随机选取β ← {0, 1}, 计算生成挑战密文c* Encpk(mβ (1); r1), 并将挑战密文c* 发送给A'/C, 而A'/C不做任何处理又直接将密文c* 发送给敌手A

(5)执行步骤(4)Q-1次。

(6)查询-挑战Q:敌手A选取两个消息m0(Q)m1(Q)发送给A'/C, 而A'/C接收到两个消息m0(Q)m1(Q)后, 计算生成挑战密文, 并将其挑战密文c(Q)发送给敌手A

(7)猜测:敌手A给出自己的猜测b'返回给A'/C, 而此时A'/C直接将b'返回给挑战者C'

重复执行Q次查询, 则有

3 多比特的GPV格公钥加密

本文与mRegev方案类似, 给出了基于Dual-LWE假设的格基公钥加密方案(mGPV)。由于mn⎡logq⎤+2λ , 因此基于Dual-LWE的格公钥加密方案[3]具有更大的密文尺寸mlog2q, 而不是基于LWE的nlog2q。因此, 本文给出了基于Dual-LWE假设的多比特公钥加密方案。

1)paramsSetup(1λ , n, m, q, α ), 其中, n, m, qZ, α (> 0)∈ R, t, r, lZ

2)(pk, sk)← KeyGen(1λ , params)。

(1)skSecretKeyGen(params):均匀随机选取秘密向量eDZm, r, 其中, e=(e[1], …, e[m])∈ DZm, r, 并利用n个私钥向量e构成私钥矩阵EDZm× n, r, E=(e1, e2, …, en), 故私钥的规模为O((mn)log q)而不再是O(mlog q)。

(2)pkPublicKeyGen(1λ , params):随机均匀选取矩阵AZqn× m, 计算U=fA(E)=AE(mod q)∈ Zqn× n, 输出pk=(A, U)∈ Zqn× m× Zqn× n。这里公钥的规模不再为O(n(m+1)⋅ log q), 而是O(n(m+n)⋅ log q)。

3)cEnc(pk, uZl2):这里要同时加密多个比特, 算法如下。

对于任意消息μ ∈ {0, 1}l, 执行以下操作:

(1)均匀选取随机参数向量sZnq, x1χ m, x2χ n

(2)计算 密文的规模为O(n(m+n)⋅ log q)。

(3)输出密文c

4)μ 'Dec(sk, c)。对于私钥sk=e及对应解密密文c=(c0, c1)∈ Zqm+n, 执行以下操作:

公式(10)中, 记E=ETx+x2=n⎢⎥e⎢⎥, 其中, e=eTx+x为单比特加密系统引起的错误。

mGPV方案的正确性和安全性分析类似于mRegev方案, 因此在LWE假设下, 本文的方案是INDCPA安全的。因篇幅有限, 此处不再赘述。

4 方案分析
4.1 方案对比

表1给出了多比特加密方案的参数对比。通过表1对比可以发现, 利用PVW技术, 同样可以有效地实现将多比特加密的密文维度由l(m+1)压缩到(m+l)。

表1 多比特加密方案对比

4.2基于小秘密的方案优化

基于LWE公钥加密的贡献主要是秘密向量不再从随机均匀分布中取样, 而是从能产生更小实体的分布中取样, 或者说, 将原始LWE问题直接拓展成一个简单的小秘密情形。BRAKERSKI[18]等人和MICCIANCIO[19]等人分别提出LWE问题的一个变体, 即私钥向量不再选自sZnq, 而是均匀选自集合{0, 1}n或者{-1, 0, 1}n, 解决该问题需O(2n)次操作或者O(3n)次操作。显然该问题比标准的LWE问题简单, 且给出的规约证明需增大维度参数n来保证该变体是困难的, 即n(log2(q))=O(nlog2(n)) (qq(n)多项式), 对于标准LWE参数n=256, 则对于该变体需n(log2(n))=2048。BRAKERSKI[18]等人从理论角度证明了Binary-LWE问题与Standard-LWE问题在安全性上是等价的。GOLDWASSER[20]等人已经证明这种情形下, 只要秘密向量具有充分的熵, Binary-LWE与LWE具有同等的困难性, 但是具有更小的维度和噪声。BAI[21]等人则给出对Binary-LWE问题的维度只需O(nloglogn), 即维度为768可保证安全性。因此, 私钥向量均匀选自集合{0, 1}n或{-1, 0, 1}n来构造多比特加密方案是一个有趣且必要的优化。因技术细节与上述mRgev和mGPV相似, 故不再赘述。

5 结束语

多比特格基础公钥加密方案受限于如何正确解密。本文给出了一种更为简单实用的多比特格基公钥加密方案, 并给出安全性证明。方案最后利用Binary-LWE来优化计算效率[22], 尽管已知基于小秘密会明显带来计算效率的提升, 但同样也会带来参数的膨胀。下一步工作将给出基于门限的格基公钥加密。

The authors have declared that no competing interests exist.

参考文献
[1] AJTAI M, DWORK C. A Public-key Cryptosystem with Worst-case/Average-case Equivalence[C]//ACM. 29th Annual ACM Symposium on the Theory of Computing, May 4-6, 1997, Texas, USA. New York: ACM, 1997: 284-293. [本文引用:5]
[2] REGEV O. On Lattices, Learning with Errors, Rand om Linear Codes, and Cryptography[C]//ACM. 37th Annual ACM Symposium on Theory of Computing, May 22-24, 2005, Baltimore, MD, USA. New York: ACM, 2005: 84-93. [本文引用:5]
[3] GENTRY C, PEIKERT C, VAIKUNTANATHAN V. Trapdoors for Hard Lattices and New Cryptographic Constructions[C]//ACM. 40th Annual ACM Symposium on Theory of Computing, May 17-20, 2008, Victoria, British Columbia, Canada. New York: ACM, 2008: 197-206. [本文引用:2]
[4] KAWACHI A, TANAKA K, XAGAWA K. Multi-bit Cryptosystems Based on Lattice Problems[C]//Springer. 10th International Conference on Practice and Theory in Public-Key Cryptography, April 16-20, 2007, Beijing, China. Heidelberg: Springer, 2007: 315-329. [本文引用:1]
[5] PEIKERT C, VAIKUNTANATHAN V, WATERS B. A Framework for Efficient and Composable Oblivious Transfer[C]//IACR. 28th Annual International Cryptology Conference on Cryptology: Advances in Cryptology, August 17-21, 2008, Santa Barbara, CA, USA. Heidelberg: Springer, 2008: 554-571. [本文引用:3]
[6] BRAKERSKI Z, GENTRY C, HALEVI S. Packed Ciphertexts in LWE-based Homomorphic Encryption[C]//IACR. 16th International Conference on Practice and Theory in PublicKey Cryptography, February 26-March 1, 2013, Nara, Japan. Heidelberg: Springer, 2013: 1-13. [本文引用:2]
[7] GENTRY C. Fully Homomorphic Encryption Using Ideal Lattices[C]//ACM. 41st Annual ACM Symposium on Theory of Computing, May 31-June 2, 2009, Bethesda, MD, USA. New York: ACM, 2009: 169-178. [本文引用:2]
[8] 吕海峰, 丁勇, 代洪艳, . LWE上的全同态加密方案研究[J]. 信息网络安全, 2015(1): 32-38. [本文引用:1]
[9] LI Zengpeng, MA Chunguang, MORAIS E, et al. Multi-bit Leveled Homomorphic Encryption via Dual. LWE-based[C]//Springer. 2016 International Conference on Information Security and Cryptology, November 4-6, 2016, Beijing, China. Heidelberg: Springer, 2016: 221-242. [本文引用:3]
[10] BLUM A, KALAI A, WASSERMAN H. Noise-tolerant Learning, the Parity Problem, and the Statistical Query Model[J]. ACM, 2003, 50(4): 506-519. [本文引用:2]
[11] LYUBASHEVSKY V. Lattice Signatures without Trapdoors[C]//IACR. 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, April 15-19, 2012, Cambridge, UK. Heidelberg: Springer, 2012: 738-755. [本文引用:2]
[12] HIROMASA R, ABE M, OKAMOTO T. Packing Messages and Optimizing Bootstrapping in GSW-FHE[C]//IACR. 18th IACR International Conference on Practice and Theory in Public Key Cryptography, March 30-April 1, 2015, Gaithersburg, MD, USA. Heidelberg: Springer, 2015: 699-715. [本文引用:2]
[13] LI Zengpeng, MA Chunguang, DU Gang, et al. Dual LWE-based Fully Homomorphic Encryption with Errorless Key Switching[C]//IEEE. 22nd IEEE International Conference on Parallel and Distributed Systems, December 13-16, 2016, Wuhan, China. New Jersey: IEEE, 2017: 1169-1174. [本文引用:2]
[14] BRAKERSKI Z, VAIKUNTANATHAN V. Efficient Fully Homomorphic Encryption from(Stand ard) LWE[C]//IEEE. IEEE 52nd Annual Symposium on Foundations of Computer Science, October 22-25, 2011, CA, USA. New Jersey: IEEE, 2011: 97-106. [本文引用:1]
[15] BRAKERSKI Z. Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages[C]//IACR. 31st Annual Conference on Advances in Cryptology, August 14-18, 2011, Santa Barbara, CA, USA. Heidelberg: Springer, 2011: 505-524. [本文引用:1]
[16] GENTRY C, SAHAI A, WATERS B. Homomorphic Encryption from Learning with Errors: Conceptually-simpler, Asymptotically-faster, Attribute-based[C]//IACR. 33rd Annual Conference on Advances in Cryptology, August 18-22, 2013, Santa Barbara, CA, USA. Heidelberg: Springer, 2013: 75-92. [本文引用:1]
[17] BRAKERSKI Z. Fully Homomorphic Encryption without Modulus Switching from Classical Gapsvp[C]//IACR. 32nd Annual Conference on Advances in Cryptology, August 19-23, 2012, Santa Barbara, CA, USA. Heidelberg: Springer, 2012: 868-886. [本文引用:1]
[18] BRAKERSKI Z, LANGLOIS A, PEIKERT C, et al. Classical Hardness of Learning with Errors[C]//ACM. 45th Annual ACM Symposium on Theory of Computing, June 1-4, 2013, Palo Alto, CA, USA. New York: ACM, 2013: 575-584. [本文引用:2]
[19] MICCIANCIO D, PEIKERT C. Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller[C]//IACR. 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, April 15-19, 2012, Cambridge, UK. Heidelberg: Springer, 2012: 700-718. [本文引用:1]
[20] GOLDWASSER S, KALAI Y, PEIKERT C, et al. Robustness of the Learning with Errors Assumption[C]//Tsinghua University. 1st Symposium on Innovations in Computer Science, January 5-7, 2010Beijing, China. Beijing: WanFang Data, 2010: 230-240. [本文引用:1]
[21] BAI S, GALBRAITH S D. Lattice Decoding Attacks on Binary LWE[C]//Springer. 19th Australasian Conference on Information Security and Privacy, July 7-9, 2014, Wollongong, NSW, Australia. Heidelberg: Springer, 2014: 322-337. [本文引用:1]
[22] 王志刚, 马春光, 史晓倩. 基于Binary LWE的全同态加密方案研究[J]. 信息网络安全, 2015(7): 41-50. [本文引用:1]