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

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

Journal on Communications ›› 2014, Vol. 35 ›› Issue (10): 138-144.doi: 10.3969/j.issn.1000-436x.2014.10.016

• Papers • Previous Articles Next Articles

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

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

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.

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

[1]	Huanhuan LIAN, Huiying HOU, Yunlei ZHAO. Post-quantum verifier-based three-party password authenticated key exchange protocol [J]. Journal on Communications, 2022, 43(4): 95-106.
[2]	Yuanbo GUO, Anqi YIN. Research on password-authenticated key exchange protocol over lattices [J]. Journal on Communications, 2022, 43(12): 172-187.
[3]	Youheng DONG, Geng ZHAO, Yingjie MA. Two-dimensional pseudo-random coupled map lattices system based on partitioned elementary cellular automata and its dynamic properties [J]. Journal on Communications, 2022, 43(1): 71-82.
[4]	Miaomiao TIAN, Jing CHEN, Hong ZHONG. Identity-based incremental signature scheme from lattices [J]. Journal on Communications, 2021, 42(1): 108-117.
[5]	Miaomiao TIAN,Chuang GAO,Jie CHEN. Identity-based cloud storage integrity checking from lattices [J]. Journal on Communications, 2019, 40(4): 128-139.
[6]	Yatao YANG,Xinguang HAN,Jierun HUANG,Yang ZHAO. Bidirectional authentication key agreement protocol supporting identity’s privacy preservation based on RLWE [J]. Journal on Communications, 2019, 40(11): 180-186.
[7]	Xixi YAN,Yuan LIU,Zichen LI,Yongli TANG,Qing YE. Privacy-preserving attribute-based encryption scheme on ideal lattices [J]. Journal on Communications, 2018, 39(3): 128-135.
[8]	Caifen WANG,Li CHEN. Three-party password authenticated key agreement protocol with user anonymity based on lattice [J]. Journal on Communications, 2018, 39(2): 21-30.
[9]	Shao-bo YU,Ling-da WU,Xi-tao ZHANG. Research on space information representation model based on formal concept analysis [J]. Journal on Communications, 2017, 38(Z2): 78-85.
[10]	Yong-li TANG,Ming-xing HU,Kun LIU,Qing YE,Xi-xi YAN. Novel identity-based fully homomorphic encryption scheme from lattice [J]. Journal on Communications, 2017, 38(5): 39-47.
[11]	Qing YE,Ming-xing HU,Yong-li TANG,Kun LIU,Xi-xi YAN. Novel hierarchical identity-based encryption scheme from lattice [J]. Journal on Communications, 2017, 38(11): 54-64.
[12]	Ran DUAN,Chun-xiang GU,Yue-fei ZHU,Yong-hui ZHENG,Li CHEN. Efficient identity-based fully homomorphic encryption over NTRU [J]. Journal on Communications, 2017, 38(1): 66-75.
[13]	Hong-can YAN,Feng ZHANG,Bao-xiang LIU. Rough decision rules extraction and reduction based on granular computing [J]. Journal on Communications, 2016, 37(Z1): 30-35.
[14]	Ze-dong SUN,Yue-fei ZHU,Chun-xiang GU,Yong-hui1 ZHENG. RLWE-based key-policy ABE scheme [J]. Journal on Communications, 2016, 37(Z1): 125-131.
[15]	Can CUI,Yi SUN,Jun LU,Jian-hong HAO. Research on a hexagonal lattice optimal clustering routing algorithm based on hybrid CS for WSN [J]. Journal on Communications, 2016, 37(5): 176-183.

New pseudorandom functions based on SIS

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

References 13

Related Articles 15

Metrics

Recommended 0