理想格上基于身份的加密算法研究_黄文晋.pdf

书书书第 21 卷第 4 期2022 年12 月广州大学学报(自然科学版)Journal of Guangzhou University(Natural Science Edition)Vol 21No 4Dec2022收稿日期:2022-09-10;修回日期:2022-10-13作者简介:黄文晋(1997)，男，硕士研究生 E-mail:1770508188 qq com*通信作者 E-mail:ctang shu edu cn引文格式:黄文晋，唐春明，贾惠文 理想格上基于身份的加密算法研究J 广州大学学报(自然科学版)，2022，21(4):37-45文章编号:1671-4229(2022)04-0037-09理想格上基于身份的加密算法研究黄文晋a，唐春明b，c*，贾惠文b，c(广州大学 a 数学与信息科学学院;b 广州数学中心;c 广东省广州市共建信息安全技术重点实验室，广东 广州510006)摘要:格上基于身份的加密算法(Identity-Based Encryption，IBE)可以抵抗量子攻击，能有效解决公钥密码管理系统效率低的问题，因此，国内外学者提出了一系列基于格的身份加密方案。文章运用 Jia 等提出的基于非球形高斯的原像采样算法，对 IBE 方案中用户私钥的提取进行了改进。实验结果表明，在保证 IBE 加密与解密正确性的情况下，可以有效降低用户私钥的尺寸，提升 IBE 方案的空间效率。文章运用的基于非球形高斯的用户私钥提取算法有 2 个模式:采用模式 1 后，在 42.6-bit 的安全性下，用户私钥的尺寸由 21.75 kB 减小至13.31 kB;在 109.8-bit 的安全性下，用户私钥的尺寸由 50.36 kB 减小至 32.25 kB;采用模式 2 后，在 42.6-bit的安全性下，用户私钥的尺寸由 21.75 kB 减小至 10.18 kB;在 109.8-bit 的安全性下，用户私钥的尺寸由 50.36kB 减小至 21.86 kB，相比于模式 1，模式 2 能更有效地节省用户私钥的内存开销。关键词:格密码;IBE;非球形高斯采样中图分类号:TP 309文献标志码:Aesearch on identity-based encryption algorithms on the ideal latticeHUANG Wen-jina，TANG Chun-mingb，c*，JIA Hui-wenb，c(a School of Mathematics and Information Science;b Guangzhou Center for Applied Mathematics;c The Key Laboratory of Information Security Technology，Guangzhou University Guangzhou 510006，China)Abstract:Identity-Based Encryption(IBE)on lattices resists quantum attacks and effectively solvesthe problem of low efficiency of public key cryptography management systems，so scholars at home andabroad have proposed a series of lattice-based identity encryption schemes In this paper，the extrac-tion of user private keys in the IBE scheme is improved by using the prototype sampling algorithmbased on non-spherical Gaussian proposed by Jia，et al Experimental results show that under the con-dition of ensuring the correctness of IBE encryption and decryption，the size of the users private keycan be effectively reduced and the space efficiency of the IBE scheme can be improved The non-spherical Gaussian-based user private key extraction algorithm used in this article has two modes:After adopting mode 1，the size of the users private key is reduced from 21.75 kB to 13.31 kBunder the security of 42.6-bit;under the security of 109.8-bit，the size of the users private key is re-duced from 50.36 kB to 32.25 kB;After adopting mode 2，under the security of 42.6-bit，thesize of the users private key is reduced from 21.75 kB to 10.18 kB;under the security of 109.8-bit，the size of the users private key is reduced from 50.36 kB to 21.86 kB，which can more effectivelysave the memory overhead of the users private key than mode 1Key words:lattice cryptography;IBE;non-spherical Gaussian广州大学学报(自然科学版)第 21 卷随着网络通信的用户数量骤增以及网络环境对安全性的要求越来越高，公钥密码基础设施(Public KeyInfrastructure，PKI)由于必须依赖数字证书，需要越来越强的存储能力、查询能力以及越来越高的安全性，其繁重的管理系统适应不了当今的网络环境。基于身份的加密机制(Identity-Based Encryption，IBE)是一种经典的公钥加密方案，其概念首次由 Shamir 提出，IBE 允许用户的身份信息作为公钥，比如用户的邮箱地址等等 1，加密时可以直接使用接收方的身份标识作为公钥，为公钥信息的管理提供了便利，解决了 PKI 效率低的问题。2001 年，Boneh 等2 正式给出 IBE 的定义和安全模型，后来基于双线性映射和二次剩余假设构造的 IBE 方案被相继提出，但都无法抵抗量子攻击。格密码(Lattices Cryptography)是一种后量子密码，经过十几年的快速发展，有着显著的特征和优势:能抵抗量子攻击、并行运算，以及格上某些困难问题存在最坏情况到平均情况的归约，给格密码方案提供了安全的保障。格密码的研究工作由 Ajtai 开始，他提出了格的困难问题可以作为格密码方案构造的安全基础 3，目前格的困难问题有 2 个:Ajtai 提出的小整数解问题 3(Small Integer Solution Problem，SIS)，还有非齐次版本的变体(Inhomogeneous Small Integer Solution Problem，I-SIS);egev 4 提出的容错学习问题(Learning With Er-rors Problem，LWE)，他们都给出最坏情况下基于格的问题向平均情况下 SIS 问题和 LWE 问题的规约。在2007 年和 2009 年，有学者分别提出这两种困难问题的基于环结构的变体5 6，即-SIS 问题和-LWE 问题，其优点是储存更低，运算效率更高，同时也存在最坏情况下基于理想格的问题向平均情况下-SIS 问题和-LWE 问题规约的优良特性。第一个基于格的 IBE 方案由 Gentry 等7 提出，是基于 Dual-egev 加密算法设计的。后来，有学者对此进行了研究和改进。2010 年，Agrawal 等8 构建了基于格的IBE 方案，称为 ABB 方案，他们使用的公钥矩阵是由两部分组成，私钥是分两步骤采样而得的，虽然后来有很多学者都一直沿用这种方案，但是公钥和私钥内存开销大，不切实际。2014 年，Ducas 等9 构造了一种基于 NT-U 格的 IBE 方案，公钥矩阵是由 NTU 格构建的，因此算法效率高。2018 年，Bert 等10提出基于-SIS 和-LWE 构建的 IBE 方案(Bert-Fouque-oux-Sabt，BFS)，他们利用了 MP 提出的(Micciancio-Peikert，MP)的原像采样算法 11，并结合 GM(Genise-Micciancio，GM)提出了 G-格采样和扰动向量的方法12，对私钥的提取作了改进和优化，虽然效率比 Ducas 等提出的基于 NTU 格构建的 IBE 方案要高，但是公钥和用户私钥的尺寸还是不够小。而最近的研究工作由钱心缘等13 提出了一种基于-SIS 和-LWE 构造的 IBE 方案(本文简称 QW方案)，对 BFS 方案进行了优化，并且采用了分块复用技术，降低了密文膨胀率，但是这种技术始终存在不能降低所有用户私钥的内存空间、用户私钥的内存开销仍然比较大的缺点，还有，笔者认为 QW 方案中私钥提取算法的安全性还不够高。结合以上的分析以及针对以上方案的不足，本文运用非球形高斯采样 14 的原理，对用户私钥提取算法进行改进，从而提升格上的 IBE 方案的空间效率。非球形高斯的原像采样原理由 Jia 等 14在 2020 年提出，这种原像的分布不会泄露陷门信息，并且他们给出了 2 种模式:第一种模式可以提升安全性，同时降低签名尺寸;第二种模式在安全性几乎不变的情况下进一步降低签名尺寸。本文运用以上的原理和方法，在理想格上研究，对 QW 方案的用户私钥提取算法作改进，减小私钥的内存开销，提升方案的空间效率，力图提升方案的安全性。1基本理论本部分介绍本文所需要的理论，包括格的相关定义及其理论、IBE 的基本架构、加解密原理和理想格上的原像采样算法。1 1格及其相关理论定义 1(格15)给定一组 n 维线性无关的向量b1，b2，bm，格定义为=L(b1，b2，bm)=mi=1xibixi Z ，其中 b1，b2，bm是格 的一组基，若定义 B 为格 的基矩阵，列由 b1，b2，bm组成，则格 可以由 B 生成，表示为=L(B)=Bx xZm，格 的秩为 m，维数为 n，当 n=m 时称其为满秩格。定义 2(分圆多项式环16 17)令 n 为正整数，有理数域Q上 n 次分圆域为Q()，同构于 Cn=Q x/n(x)，其中 是 n 次本原单位根，令(n)为 n 的欧拉函数，Cn为Q 上(n)维向量空间，n(x)为Z 上(n)次不可约多项式。而 2n(x)为 2n 次分圆多项式，其中 n为 2 的幂次方，定义 Z x/2n(x)，即 Z x/xn+1。令 q2 且为正整数，定义 q/q，表示多项式83第 4 期黄文晋等:理想格上基于身份的加密算法研究环 中每个多项式的系数模 q，即 qZq x/xn+1，本文基本在 q下进行讨论和研究。定义 3(理想格)易知Znq与环 q是同构的，因此，环 q可看作一种特殊的格。又因为，q，q，所以 q是 的理想。一般地，环 q是环 的理想且与格Znq同构，称之为理想格。定义 4(多项式的系数嵌入 18)和 q为定义 2中