基于短整数解问题的伪随机函数新构造

doi:10.3969/j.issn.1000-436x.2014.10.016

通信学报 ›› 2014, Vol. 35 ›› Issue (10): 138-144.doi: 10.3969/j.issn.1000-436x.2014.10.016

• 论文Ⅰ 空间信息传输网络 • 上一篇下一篇

基于短整数解问题的伪随机函数新构造

陈和风¹,马文平¹,高胜²,张成丽¹

¹ 西安电子科技大学综合业务网理论及关键技术国家重点实验室，陕西西安 710071
² 数据通信科学技术研究所，北京 100191

出版日期:2014-10-25 发布日期:2017-06-14
基金资助:
国家自然科学基金资助项目;国家自然科学基金资助项目;高等学校创新引智计划基金资助项目;高等学校博士学科点专项科研基金资助项目;“十二五”国家蜜码发展基金资助项目

New pseudorandom functions based on SIS

He-feng CHEN¹,Wen-ping MA¹,Sheng GAO²,Cheng-li ZHANG¹

¹ State Key Laboratory of Integrated Service Networks,Xidian University,Xi’an 710071,China
² Data Communication Science and Technology Research Institute,Beijing 100191,China

Online:2014-10-25 Published:2017-06-14
Supported by:
The National Natural Science Foundation of China;The National Natural Science Foundation of China;The Research Fund for the Doctoral Program of Higher Education of China;The National Development Foundation for Cryptological Research;The National Development Foundation for Cryptological Research

摘要/Abstract

摘要：

伪随机函数是构造密码原型的重要工具。基于短整数解问题，在格上设计出2个伪随机函数，第一个利用树状伪随机综合器的思想，达到并行化效果，第二个虽是串行构造，但降低了公钥尺寸。二者均具有小模数，而且是可证明安全的。与A Banerjer，C Peikert和A Rosen 3人提出的方案（EUROCRYPT 2012）相比，此提出的伪随机函数具有渐少的密钥量；在构造方法上，由于避免了凑整技术的使用，伪随机函数的生成效率得到了提高。

关键词: 伪随机函数, 格, 短整数解问题, 混合论证

Abstract:

Pseudorandom functions are vital tools in the construction of cryptographic primitives.Under the hard assumption of SIS (short integer solution),two lattice-based pseudorandom functions are proposed.The first one has parallel structure by the ideal of tree-like pseudorandom synthesizer,and the second one is serial structure whose public key size is reduced.Both constructions have small modulus and provable security.Compared with A Banerjer,C Peikert and A Rosen’s construction (EUROCRYPT 2012),their key sizes are asymptotically smaller,and efficiency are improved by avoiding the “rounding” technology.

Key words: pseudorandom function, lattice, short integral solution problem, hybrid argument

陈和风,马文平,高胜,张成丽. 基于短整数解问题的伪随机函数新构造[J]. 通信学报, 2014, 35(10): 138-144.

He-feng CHEN,Wen-ping MA,Sheng GAO,Cheng-li ZHANG. New pseudorandom functions based on SIS[J]. Journal on Communications, 2014, 35(10): 138-144.

参考文献 13

[1]	GOLDREICH O , GOLDWASSER S , MICALI S . How to construct random functions[J]. J ACM, 1986,33(4): 792-807.
[2]	NAOR M , REINGOLD O . Synthesizers and their application to the parallel construction of pseudorandom functions[J]. Journal of Computer and System Sciences, 1999,58: 336-375.
[3]	AJTAI M . Generating hard instances of lattice problems[A]. STOC 1996[C]. Philadelphia,Pennsylvania, 1996. 99-108.
[4]	REGEV O . On lattices,learning with errors,random linear codes,and cryptography[J]. Journal of the ACM, 2009,56(6): 1-40.
[5]	PEIKERT C , WATERS B . Lossy trapdoor functions and their applications[A]. STOC 2008[C]. Victoria,British Columbia, 2008. 187-196.
[6]	GENTRY C , PEIKERT C , VAIKUNTANATHAN V . Trapdoors for hard lattices and new cryptographic constructions[A]. STOC 2008[C]. Victoria,British Columbia, 2008. 197-206.
[7]	GENTRY C . Fully homomorphic encryption using ideal lattices[A]. STOC 2009[C]. Bethesda,Maryland,USA, 2009. 169-178.
[8]	CASH D , HOFHEINZ D , KILTZ E ,et al. Bonsai trees,or how to delegate a lattice basis[A]. Cryptology-EUROCRYPT 2010[C]. French Riviera, 2010. 523-552.
[9]	AGRAWAL S , BONEH D , BOYEN X . Efficient lattice (H)IBE in the standard model[A]. Cryptology–EUROCRYPT 2010[C]. French Riviera, 2010. 553-572.
[10]	BANERJER A , PEIKERT C , ROSEN A . Pseudorandom functions and lattices[A]. Cryptology – EUROCRYPT 2012[C]. Cambridge,UK, 2012. 719-737.
[11]	GORDON S D , KATZ J , VAIKUNTANATHAN V . A group signature scheme from lattice assumptions[A]. Cryptology-ASIACRYPT 2010[C]. Singapore, 2010. 395-412.
[12]	LYUBASHEVSKY V . Lattice signatures without trapdoors[A]. Cryptology-EUROCRYPT 2012[C]. Cambridge,UK, 2012. 738-755.
[13]	MICCIANCIO D , MOL P . Pseudorandom knapsacks and the sample complicity of LWE search-to-decision reductions[A]. CryptologyCRYPTO 2011[C]. Santa Barbara,CA,USA, 2011. 465-484.

[1]	陈晓玉, 孙连峰, 张钇涵. 具有大零相关区宽度的Ⅱ型偶长Z-互补对构造方法[J]. 通信学报, 2023, 44(6): 167-174.
[2]	廉欢欢, 侯慧莹, 赵运磊. 后量子基于验证元的三方口令认证密钥交换协议[J]. 通信学报, 2022, 43(4): 95-106.
[3]	曹阳, 钟烨, 彭醇陵, 彭小峰. 基于混合供能和能量协作的异构网络能量效率优化算法[J]. 通信学报, 2022, 43(3): 135-147.
[4]	毛伊敏, 甘德瑾, 廖列法, 陈志刚. 基于Spark框架和ASPSO的并行划分聚类算法[J]. 通信学报, 2022, 43(3): 148-163.
[5]	郭渊博, 尹安琪. 基于格的口令认证密钥交换协议综述[J]. 通信学报, 2022, 43(12): 172-187.
[6]	郭红伟, 朱策, 杨栩, 罗雷. 基于失真反向传播的时域依赖率失真优化[J]. 通信学报, 2022, 43(12): 222-232.
[7]	董有恒, 赵耿, 马英杰. 基于分区初等元胞自动机的二维伪随机耦合映像格系统及其动态特性[J]. 通信学报, 2022, 43(1): 71-82.
[8]	田苗苗, 陈静, 仲红. 格上基于身份的增量签名方案[J]. 通信学报, 2021, 42(1): 108-117.
[9]	王宏禹,邱天爽. 特征算子谱表示与特征展开的研究[J]. 通信学报, 2020, 41(5): 1-8.
[10]	房礼国,付正欣,胡浩,沈刚,郁滨. 基于区域递增式彩色视觉密码的栅格地图多级分存算法研究[J]. 通信学报, 2019, 40(9): 24-32.
[11]	王天荆,李秀琴,白光伟,沈航. 无线传感器网络中基于自适应网格的多目标定位算法[J]. 通信学报, 2019, 40(7): 197-207.
[12]	田苗苗,高闯,陈洁. 格上基于身份的云存储完整性检测方案[J]. 通信学报, 2019, 40(4): 128-139.
[13]	曾锋,王润华,彭佳,陈志刚. 口碑参与模式下移动众包网络的用户博弈研究[J]. 通信学报, 2019, 40(3): 125-138.
[14]	赵耿,马艳艳,马英杰. 基于混沌序列的SCMA码本设计及系统性能分析[J]. 通信学报, 2019, 40(2): 137-144.
[15]	吴宣利,陈旭. 干扰门限与回程容量限制下UDN的能效与谱效联合优化算法[J]. 通信学报, 2019, 40(12): 86-97.

基于短整数解问题的伪随机函数新构造

New pseudorandom functions based on SIS

在线阅读

PDF下载

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献 13

相关文章 15

Metrics

推荐阅读 0