1、密码学报ISSN 2095-7025 CN 10-1195/TNJournal of Cryptologic Research,2023,10(2):360371密码学报编辑部版权所有.E-mail:http:/Tel/Fax:+86-10-82789618分布拟合技术及其在密码函数构造中的应用*朱率率1,2,韩益亮11.中国人民武装警察部队工程大学 密码工程学院,西安 7100862.网络与信息安全武警部队重点实验室,西安 710086通信作者:韩益亮,E-mail:zhu_摘要:在计算平台上生成符合目标参数的分布样本是数值计算中的基本问题.通过优化形成高拟合度的分布参数,对探索新型密码函数
2、的设计方法,尤其是安全的单向函数映射有着重要的意义.本文围绕密码学安全意义,讨论了通用情况下真实分布的参数与敌手的攻击优势之间满足的约束关系,提出了一种基于距离监督的分布拟合方法,用于生成与理想分布样本逼近的近似分布参数组合.使用分布隐含模型(DLM)构造真实分布的输出模型,采用复合距离测度优化参数组合,使 DLM 成为满足安全距离约束条件的目标分布样本生成器.构造了一类通用的单向陷门置换函数(OWTP),在计算上满足统计上的样本不可区分性,从理论上已经初步具备了用于直接构造部分密码算法的能力.关键词:分布拟合;密码函数;单向陷门函数;统计距离中图分类号:TP309.7文献标识码:ADOI:1
3、0.13868/ki.jcr.000599中文引用格式:朱率率,韩益亮.分布拟合技术及其在密码函数构造中的应用J.密码学报,2023,10(2):360371.DOI:10.13868/ki.jcr.000599英文引用格式:ZHU S S,HAN Y L.Distribution fitting and its applications in construction of cryptographicfunctionsJ.Journal of Cryptologic Research,2023,10(2):360371.DOI:10.13868/ki.jcr.000599Distributi
4、on Fitting and Its Applications in Construction ofCryptographic FunctionsZHU Shuai-Shuai1,2,HAN Yi-Liang11.College of Cryptography Engineering,Engineering University of PAP,Xian 710086,China2.Network and Information Security Key Laboratory of PAP,Xian 710086,ChinaCorresponding author:HAN Yi-Liang,E-
5、mail:zhu_Abstract:Generating samples being in compliance with desirable parameters is one of the fundamen-tal problems on computing platforms.Optimizing the sampling method to generate ideal distributionis helpful in the design of new cryptographic functions,especially one-way functions in public ke
6、ycryptography.This paper studies the constraints between parameters of real distributions and the ad-vantages of adversaries,and presents a distribution approaching method based on distance supervisionto generate the parameters of sub-optimal distribution.By constructing a latent distribution model*
7、基金项目:陕西省自然科学基金基础研究计划(2021JM-252);武警工程大学创新团队项目(KYTD201805);武警工程大学基础前沿创新研究基金(WJY202222)Foundation:Basic Research Program of Natural Science Foundation of Shaanxi Province(2021JM-252);InnovativeTeam Project of Engineering University of PAP(KYTD201805);Fundamental Innovation Project of Engineering Uni-v
8、ersity of PAP(WJY202222)收稿日期:2022-03-21定稿日期:2022-06-27朱率率 等:分布拟合技术及其在密码函数构造中的应用361(DLM)to generate real distribution,and optimizing the model using a compound distance measure,a sample generator compliance with the target distribution is designed.Based on the constructedDLM,a generic method is propo
9、sed to obtain one-way trapdoor permutation(OWTP)that satisfiescomputational indistinguishability,which proves the effectiveness of the construction ability of theDLM.Key words:distribution fit;cryptographic function;one-way trapdoor function;statistical distance1引言现有公钥密码算法的安全基础是其密码函数的安全性,即算法中隐含的单向陷门
10、置换的安全性.例如,在 RSA 中,给定大的模数 N,在(N)中求某个公钥 pk 对应的私钥 sk.从经典的信息论角度,一个理想的密码函数应满足不可预测性和不可区分性.在公钥密码设计理论中,对于安全参数为 的密码函数(r),通常使用挑战者 C 和敌手 A 之间的语义安全游戏来实现定量评估密码函数的这两个性质,敌手赢得该游戏的优势作为定量的安全性指标,一般表示为:AdvA=P A赢得游戏(r),(不可预测性)2P A赢得游戏(r)1,(不可区分性).(1)对于基于某个数学困难问题的密码函数,理想情况下可以通过精巧的设计等方法,很好地满足不可预测性和不可区分性.但在计算平台上运行的实例化后的密码系
11、统,由于受到参数精度、随机抽样方法和数值表达方式等因素影响,其工作过程和理想中的密码函数并不能取得完全一致.只有当计算平台上的密码系统所产生的结果样本与理想的密码函数结果分布足够接近,才能从统计上保证充分的不可预测性和不可区分性.通过大量的理论研究表明,在计算平台上实现的密码系统与理想密码函数相比,其输出结果的安全特性存在区别,并可以用统计等方法规约到语义安全攻击的优势上.同时,近期的一些研究14侧重如何确定密码函数的真实输入参数与理想的输入参数之间的关系,从而在具体计算平台上建立参数域需要满足的约束关系,以实现预期的安全特性.因此,当前公钥密码算法设计的基本路径是,首先找到理想的数学困难问题
12、用于构造密码函数,例如,格5、LWE6以及 NTRU7等后量子密码结构;然后,选择足够安全且计算量适中的参数域,采用某种具体的参数抽样的方法,例如,均匀分布抽样8、离散高斯抽样9或拉普拉斯抽样10等计算平台可实现的方法,得到参数域的输入值;最后,经过密码函数的处理得到满足不可区分性、不可伪造性和不可预测性等安全假设的输出结果.即使在可证明安全框架下,所设计的方案得到了理论上的安全性证明,这种设计流程也具有对构造技巧不同程度的依赖性,使得算法实例与算法设计之间不可避免地出现安全性偏差,这一结论在文献 1 中已得到证明.另一方面,人工智能技术的潜力已经远远超出了当初设计者的预期,在关系匹配、特征搜
13、索和高维度非限定性约束求解等问题上展现出巨大的自适应性和准确性.尤其是随着深度置信网络、生成式对抗网络和自编码网络等数据分布隐含工具的开发,实现高精度的逼近理想的概率分布、以及自动构造高维度的映射关系已经具备了较大的可行性.鉴于一般意义下密码函数的作用是建立安全可靠的从参数域到密文域的映射,基于现有的以概率逼近和样本统计为核心的人工智能理论,本文认为跳过上述三个步骤,而直接从密码函数自动化设计本身入手,搜索满足安全和效率要求的映射关系具有一定的可行性.因此,本文在现有工作基础上,借助 Renyi 散度构造的真实分布与理想分布间约束条件,推广了其应用范围,并进一步引入 Wasserstein 距
14、离,从而在参数域和密文域间构造了在密码函数上更具有一般意义的约束条件,为密码函数的自动化设计提供必备的理论基础.362Journal of Cryptologic Research 密码学报 Vol.10,No.2,Apr.20232相关工作在密码函数的设计方面,主要技术体现在两个方面,一是基于流程化处理的混淆网络,如 Feistel 结构、SPN 结构等设计的对称密码算法,二是基于单向陷门置换函数的非对称密码算法,如代数编码结构、格密码结构、LWE 类、多变量困难问题类等经典结构,以及近年来出现的 R-LWE11、M-LWE12和M-LWR13等后量子密码的候选结构.这两个方面的设计均以实现
15、满足一定强度的不可区分性和不可预测性为目的.在对密码算法进行安全评估时,安全框架往往基于理想的输入参数分布,得到敌手的优势,而在具体的计算平台上,这种优势必然存在着安全强度偏差1.近年来,人们围绕输入参数的真实分布,对经典的安全性证明理论进行了大量研究.在刻画密码算法输出的分布方面,Bhatia 等人14研究了一类传统的散列函数在椭圆曲线上的真实映射分布,从而在统计角度发现散列函数的抗碰撞性缺陷.文献 15 研究了二次剩余和模复合整数的非剩余类的分布情况,并探讨了在设计密码算法时对安全强度的影响,但仅讨论了二次剩余困难问题下的情形,没有给出一般意义下的分布要求.Dodis 等人1在假定输入参数
16、服从均匀分布的情况下,研究了理想分布与真实分布对密码原语在安全强度上造成的影响,并指出,真实分布必须满足最小熵和碰撞熵的下限才能获得密码算法预期的安全性.Matsuda 等人2使用 Renyi 散度度量真实分布与理想分布的距离,将 Dodis 的结果推广到一般输入分布的情况,尤其是格上的抽样分布,使真实分布的度量更具有一般意义.Skorski 等人16的研究表明以均方类定义的距离度量是在真实分布中减少熵损失的必要条件,从而使真实分布度量方法构造更加清晰.Agrawal17设计了基于 KL 散度的伪随机函数提取器,其参数规模和随机特性与现有计算平台的基于总体方差的高斯抽样器性能接近.在安全评估方面,人们希望使用简单、通用的定量测度实现一般意义下的安全强度,即在真实计算条件下,获得密码原语的不可区分性(例如符合 IND-CPA/CCA 安全的加密函数、伪随机数发生器等)和不可预测性(例如散列函数、认证码函数等)14,18,19.Cotan 等人20针对匿名身份类加密算法的身份不可区分性进行了分析和测试,并提出了多项式环上广义的定量测试语义安全强度的方法.Chen 等人21设计了基于深度学习
