基于LWR问题的无证书全同态加密方案.pdf
《基于LWR问题的无证书全同态加密方案.pdf》由会员分享,可在线阅读,更多相关《基于LWR问题的无证书全同态加密方案.pdf(17页珍藏版)》请在咨信网上搜索。
1、Computer Science and Application 计算机科学与应用计算机科学与应用,2023,13(10),1948-1964 Published Online October 2023 in Hans.https:/www.hanspub.org/journal/csa https:/doi.org/10.12677/csa.2023.1310193 文章引用文章引用:李明祥.基于 LWR 问题的无证书全同态加密方案J.计算机科学与应用,2023,13(10):1948-1964.DOI:10.12677/csa.2023.1310193 基于基于LWR问题的无证书全同态加密
2、方案问题的无证书全同态加密方案 李明祥李明祥 河北金融学院金融研究所,河北 保定 收稿日期:2023年9月20日;录用日期:2023年10月18日;发布日期:2023年10月25日 摘摘 要要 无证书全同态加密无证书全同态加密(CLFHE)把全同态加密和无证书加密两者的优势结合了起来,它吸引了人们关注的目把全同态加密和无证书加密两者的优势结合了起来,它吸引了人们关注的目光。目前人们基于带误差学习光。目前人们基于带误差学习(LWE)问题提出了几个问题提出了几个CLFHE方案。带舍入学习方案。带舍入学习(LWR)问题是问题是LWE问题的问题的变形。它免除了变形。它免除了LWE问题中计算代价高昂的高
3、斯噪声抽样。迄今为止人们尚未提出基于问题中计算代价高昂的高斯噪声抽样。迄今为止人们尚未提出基于LWR问题的问题的CLFHE方案。本文利用方案。本文利用Gentry、Sahai和和Waters提出的近似特征向量技术,基于提出的近似特征向量技术,基于LWR问题设计了一个问题设计了一个CLFHE方案,并在随机预言机模型下证明了它满足方案,并在随机预言机模型下证明了它满足INDr-CPA安全性。与已有的基于安全性。与已有的基于LWE问题的问题的CLFHE方案相比,所设计的方案免除了耗时的高斯噪声抽样而具有更高的计算效率。方案相比,所设计的方案免除了耗时的高斯噪声抽样而具有更高的计算效率。关键词关键词
4、全同态加密,无证书,全同态加密,无证书,LWE问题,问题,LWR问题,随机预言机模型问题,随机预言机模型 Certificateless Fully Homomorphic Encryption Scheme Based on the LWR Problem Mingxiang Li Institute of Financial Research,Hebei Finance University,Baoding Hebei Received:Sep.20th,2023;accepted:Oct.18th,2023;published:Oct.25th,2023 Abstract Certifi
5、cateless fully homomorphic encryption(CLFHE)combines the advantages of fully homo-morphic encryption and certificateless encryption.Itcatches the attention of researchers.Several CLFHE schemes have been proposed based on the learning with errors(LWE)problem.The learn-ing with rounding(LWR)problem is
6、 a variant of the LWE problem.It dispenses withthe costly Gaussian noise sampling required in the LWE problem.So far,no CLFHE scheme based on the LWR problem has been proposed.This paper designs a CLFHE scheme based on the LWR problem using 李明祥 DOI:10.12677/csa.2023.1310193 1949 计算机科学与应用 Gentry,Saha
7、i,and Waterss approximate eigenvector technique and proves that the designed scheme satisfies INDr-CPA securityin the random oracle model.Compared with existing CLFHE schemes based on the LWE problem,the proposedschemedispenses with the costly Gaussian noise sampling and enjoys higher computational
8、efficiency.Keywords Fully Homomorphic Encryption,Certificateless,LWE Problem,LWR Problem,Random Oracle Model Copyright 2023 by author(s)and Hans Publishers Inc.This work is licensed under the Creative Commons Attribution International License(CC BY 4.0).http:/creativecommons.org/licenses/by/4.0/1.引言
9、引言 全同态加密(Fully Homomorphic Encryption,FHE)是一种具有特殊性质的公钥加密体制。它能在不解密的情形下对密文数据进行任意计算,即()()()()()11DecEnc,Enc,=?ff,其中 f 为任意函数。2009 年 Gentry 1基于理想格提出了第一个全同态加密方案。Genry 开拓性的工作迅速掀起了全同态加密研究的浪潮。2013 年 Gentry、Sahai 和 Waters 2提出了一种构造全同态加密方案的新技术,他们称之为近似特征向量技术。Gentry、Sahai 和 Waters 2利用近似特征向量技术,基于带误差学习(Learning wit
10、h Errors,LWE)问题3构造了一个层次型全同态加密(leveledFHE)方案。在层次型全同态加密方案中,方案的参数取决于方案所能计算的电路深度。利用 Gentry 1提出的自举技术可以把层次型全同态加密方案转换为全同态加密方案。本文的工作专注于层次型全同态加密方案,故在下文的叙述中经常省去“层次型”一词。无证书加密(Certificateless Encryption,CLE)4是一种新型公钥加密体制。它消除了基于身份的加密(Identity-Based Encryption,IBE)5固有的密钥托管问题,同时,它也避免了传统公钥加密系统中的公钥证书管理问题。无证书全同态加密(Cer
11、tificateless Fully Homomorphic Encryption,CLFHE)结合了全同态加密和无证书加密两者的优势,它引起了人们的研究兴趣。2017 年 Chen 等人6利用近似特征向量技术,基于 LWE 问题提出了一个无证书全同态加密方案,并在随机预言机模型下证明了它满足 IND-CPA 安全性。最近,Li 7利用近似特征向量技术,基于 LWE 问题又提出了一个在随机预言模型下可证明安全的无证书全同态加密方案和一个在标准模型下可证明安全的无证书全同态加密方案。带舍入学习(Learning with Rounding,LWR)问题8是 LWE 问题3的变形。LWE 问题需要
12、进行高斯噪声抽样。高斯噪声抽样的计算开销非常大,严重制约了基于 LWE 问题的全同态加密方案的计算性能。LWR 问题不需要进行高斯噪声抽样。近几年来,人们基于 LWR 问题构造了几个全同态加密方案9 10。与 Gentry、Sahai 和 Waters 2提出的基于 LWE 问题的全同态加密方案相比,这些全同态加密方案9 10由于舍弃了计算代价高昂的高斯噪声抽样其计算效率有了很大提高。截至目前,人们尚未提出基于 LWR问题的无证书全同态加密方案。鉴于无证书全同态加密的研究现状,本文致力于基于 LWR 问题的无证书全同态加密方案的设计与分析。首先,利用 Gentry、Sahai 和 Waters
13、 2提出的近似特征向量技术,基于 LWR 问题设计了一个无证书全同态加密方案。其次,在随机预言机模型下证明了所设计的方案满足 INDr-CPA 安全性。INDr-CPA比 IND-CPA 的安全性更强,它包括 IND-CPA 安全性和接收方匿名性。最后,本文具体给出了所设计的Open AccessOpen Access李明祥 DOI:10.12677/csa.2023.1310193 1950 计算机科学与应用 方案的系统参数设置。相比于现有的基于 LWE 问题的无证书全同态加密方案6 7,本文所设计的方案省掉了耗时的高斯噪声抽样,其计算效率更高。2.预备知识预备知识 2.1.符号约定符号约定
14、 下面介绍本文的符号约定,如表 1 所示。Table 1.Notations and descriptions 表表 1.符号及其描述 符号 描述 自然数集 整数集 实数集 q 商环,并且为(2,2qq,其中q,且2q()log 对数,且底为 2 向上取整?四舍五入 a 向量,且为列向量形式 Ta 向量a的转置 A 矩阵,A亦可看作其列向量的有序集合12,aa TA 矩阵A的转置 张量积 a 向量a的 Euclidean 范数,定义为()122=aiia,其中ia是向量a的分量 A 矩阵A的 Euclidean 范数,定义为max=Aajj,其中aj是矩阵A的列向量 a 向量a的范数,定义为m
15、ax=aiia,其中ia是向量a的分量 A 矩阵A的范数,定义为,max=Ai ji ja,其中,i ja是矩阵A的元素 T?向量集合T的 Gram-Schmidt 正交化,O o 算法渐近符号()poly n()f n,且对某一常数 c,使得()()=cf nO n()negl n()f n,且对每一固定常数 c,都使得()()=cf no n 李明祥 DOI:10.12677/csa.2023.1310193 1951 计算机科学与应用 2.2.格格 下面简单介绍一下格理论,详细内容可参阅11。定义定义 1 设1,=Bbb?nm是一组线性无关向量,格定义为 1:,=xcxBcbmnmiii
16、c,其中B称为的一组基。这里,n 为的维数,m 为的秩,且mn。在=mn时,称为满秩格。定义定义 2 对正整数 q、矩阵An mq和向量unq,定义 m 维满秩整数格:():mod=AeAemq0():mod=uAeAeumq.可以看出,如果()utA,则()()=+uAAt。即()uA是()A的陪集。定义定义 3 对任意的向量cn和实数0,n上高斯函数定义为 xn,()()22,exp=cxxc,它以c为中心,以为参数。对任意的向量cn、实数0以及 n 维格,上的离散高斯分布定义为 x,()()()(),=cccccxxxxD.当下标和c的值分别为 1 和0时,可省去不写。2.3.格上的算法
17、格上的算法 引理引理 1(12)令0为任意固定常数。存在概率多项式时间算法()TrapGen,n q,它输入正整数 n、2q和()53log+mnq,输出An mq和Tm m,并满足以下条件:A的分布统计接近n mq上的均匀分布,T为()A的一组基,()logT?Onq。引理引理 2(13)存在概率多项式时间算法()SamplePre,A TuA,它输入矩阵An mq、()A的一组基TA、向量unq和参数()logT?Am,其中2q,mn,输出向量em,并且e的分布 统计接近分布(),uAD。引理引理 3(13)令 n 和 q 为正整数,且 q 为素数,令2 logmnq。则对几乎所有的An
18、mq以及任意的()logm,mod=uA eq的分布统计接近nq上的均匀分布,其中,emD。引理引理 4(14)对任意 n 维格、向量cn以及实数01cxxcnDn,其中()是光滑参数。对的任意一组基B,有()()log B?n。2.4.困难问题困难问题 定义定义 4 令为安全参数,令()=nn和()=qq为整数,令()=为上的概率分布。,LWEn q问题可叙述为:对任意()poly=mn,令An mq,snq,em,umq,()T,+A Ase和(),A u是计算不可区分的。李明祥 DOI:10.12677/csa.2023.1310193 1952 计算机科学与应用 定义定义 5 对整数上
19、的分布系集nn,如果()Prnegl=neeBn,则称分布系集nn是 B 有界的。引理引理 5(3 15)对任意0,存在()2=nqq n、()=n和()=BB n,且是 B 有界的,2nq B,使得,LWEn q至少和GapSVP的经典困难性以及SIVP的量子困难性一样困难,其中()2=n。定义定义 6 对整数 q 和 p,且2qp,取整函数?p定义为?:?qpppxxq。通过逐项处理,可把?p扩展到q上的向量或矩阵。定义定义 7 令为安全参数,令()=nn、()=qq和()=pp为整数,且2qp,,LWRn q p问题可 叙述为:对任意()poly=mn,令An mq,snq,ump,()
20、T,AAs?p和(),A u是计算不可区分的。引理引理 6(8)令是上可有效抽样的 B 有界分布,令()1qp B n,则求解任一分布上nqs的,LWRn q p问题,至少与求解同一分布上nqs的,LWEn q 问题的一样困难。3.CLFHE 的定义及安全模型的定义及安全模型 3.1.定义定义 CLFHE 由系统参数生成 Setup、部分私钥抽取 Extract、公私钥生成 KeyGen、加密 Encrypt、解密Decrypt 和密文计算 Eval 六个多项式时间算法组成。其中 Setup 和 Extract 算法由密钥生成中心(Key Generation Center,KGC)执行。()
21、Setup 1,1L:输入安全参数和电路深度 L,输出系统主公钥 mpk 和主私钥 msk。()Extract,mpk msk id:输入主公钥 mpk、主私钥 msk 和身份0,1id,输出身份 id 的部分私钥idd。()KeyGen,idmpk id d:输入主公钥 mpk、身份 id 和部分私钥idd,输出用户的公钥idpk和私钥idsk。()Encrypt,idmpk id pk:输入主公钥 mpk、接收方身份 id、接收方公钥idpk以及消息,这里为消息空间,输出密文c或错误标识,这里为密文空间。()Decrypt,idmpk skc:输入主公钥 mpk、接收方私钥idsk以及密文
22、c,输出消息或错误标识。()1Eval,?mpk id f cc:输入主公钥 mpk、身份 id、电路:?f和身份 id 下的一组密文1,?cc,输出密文fc。CLFHE 应满足正确性约束。即 假定()(),Setup 1,1Lmpk msk,()Extract,iddmpk msk id,()(),KeyGen,idididpkskmpk id d,则对全部()1Eval,?fcmpk id f cc,其中:?f,()1,Encrypt,?iidiicmpk id pk,都有()()1Decrypt,=?idfmpk skcf。3.2.安全模型安全模型 我们这里给出INDr-CPA的安全定义
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 LWR 问题 证书 同态 加密 方案
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。