新形态伪随机函数研究

doi:10.3969/j.issn.1671-1122.2023.05.002

摘要/Abstract

摘要：

随着云计算模式的普及应用，对密文数据的安全外包计算的研究已是必然趋势，由此，潜在的密文数据的安全计算和隐私保护问题愈加受到业界和学界的关注。新形态伪随机函数（Pseudorandom Function，PRF）作为解决密文安全计算与检索的重要工具之一，已是当前密码学的研究热点。当前，以密文安全计算为目标，结合全同态加密（Fully Homomorphic Encryption，FHE）与格密码、门限密码、安全多方计算（Multiparty Computing，MPC）和PRF等密码学原语，对新形态伪随机函数的研究主要集中在三方面：1）格基限制隐藏的PRF可验证性研究；2）格基受限PRF适应性安全研究；3）格基多点隐私可穿刺PRF应用性研究。因此，文章从PRF的可验证性、安全性和应用性三方面，较为全面地介绍当前重要的研究成果。

关键词: 格基密码学, 全同态加密, 安全多方计算, 伪随机函数, 密文安全计算

Abstract:

The outsourcing of computing and data storage services has become a common practice with the rise in popularity of the cloud computing model, and concerns about data security and privacy protection are receiving more and more attention from business community and academic community. One of the current research topics in cryptography is new forms of Pseudorandom Function (PRF), a tool for retrieval and a solution to one of the problems with ciphertext security. Many cryptographic primitives are currently being investigated to target encrypted data secure computing, such as fully homomorphic encryption (FHE), lattice-based cryptography, threshold cryptography, secure multiparty computing and PRF. The study of new forms of PRF is now primarily focused on three aspects: 1) lattice-based private constrained PRF with verifiability; 2) lattice-based constrained PRF with adaptive security; and 3) lattice-based multi-point puncturable PRF with applicability. In a nutshell, this paper thoroughly analyzed the significant research findings in this area.

Key words: lattice-based cryptography, fully homomorphic encryption, secure multiparty computing, pseudorandom function, encrypted data secure computing

中图分类号:

TP309

李增鹏, 王梅, 陈梦佳. 新形态伪随机函数研究[J]. 信息网络安全, 2023, 23(5): 11-21.

LI Zengpeng, WANG Mei, CHEN Mengjia. Research of New Forms of Pseudorandom Random Function[J]. Netinfo Security, 2023, 23(5): 11-21.

图/表 6

表1

表2

表3

表4

表5

表6

参考文献 71

[1]	WANG Xiaoyun, LIU Mingjie. Survey of Lattice-Based Cryptography[J]. Journal of Cryptologic Research, 2014, 1(1): 13-27. doi: 10.13868/j.cnki.jcr.000002
	王小云, 刘明洁. 格密码学研究[J]. 密码学报, 2014, 1(1): 13-27. doi: 10.13868/j.cnki.jcr.000002
[2]	REGEV O. On Lattices, Learning with Errors, Random Linear Codes, and Cryptography[J]. Journal of the ACM (JACM), 2009, 56(6): 1-40.
[3]	BONEH D, WATERS B. Constrained Pseudorandom Functions and Their Applications[C]// Springer. International Conference on the Theory and Application of Cryptology and Information Security. Berlin:Springer, 2013: 280-300.
[4]	KIAYIAS A, PAPADOPPULOS S, TRIANDOPOULOS N, et al. Delegatable Pseudorandom Functions and Applications[C]// ACM. Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security. New York: ACM, 2013: 669-684.
[5]	BOYLE E, GOLDWASSER S, IVAN I. Functional Signatures and Pseudorandom Functions[C]// Springer. International Workshop on Public Key Cryptography. Berlin:Springer, 2014: 501-519.
[6]	BONEH D, LEWI K, MONTGOMERY H, et al. Key Homomorphic PRFs and Their Applications[C]// Springer. Annual Cryptology Conference. Berlin:Springer, 2013: 410-428.
[7]	GENTRY C. Fully Homomorphic Encryption Using Ideal Lattices[C]// ACM. Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing. New York: ACM, 2009: 169-178.
[8]	BRAKERSKI Z, VAIKUNTANATHAN V. Efficient Fully Homomorphic Encryption from (Standard) LWE[J]. SIAM Journal on Control and Optimization, 2014, 43(2): 831-871. doi: 10.1137/S0363012902409568 URL
[9]	BRAKERSKI Z, VAIKUNTANATHAN V. Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages[C]// Springer. Annual Cryptology Conference. Berlin:Springer, 2011: 505-524.
	BRAKERSKI Z, GENTRY C, VAIKUNTANATHAN V. (Leveled) Fully Homomorphic Encryption Without Bootstrapping[J]. ACM Transactions on Computation Theory (TOCT), 2014, 6(3): 1-36.
[11]	GENTRY C, SAHAI A, WATERS B. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based[C]// Springer. Annual Cryptology Conference. Berlin:Springer, 2013: 75-92.
[12]	BEN-EFRAIM A, LINDELL Y, OMRI E. Efficient Scalable Constant-Round MPC via Garbled Circuits[C]// Springer. International Conference on the Theory and Application of Cryptology and Information Security. Berlin:Springer, 2017: 471-498.
[13]	BOGDANOV A, ROSEN A. Pseudorandom Functions: Three Decades Later[C]// Springer. Tutorials on the Foundations of Cryptography. Berlin:Springer, 2017: 79-158.
[14]	BANERJEE A, PEIKERT C, ROSEN A. Pseudorandom Functions and Lattices[C]// Springer. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2012: 719-737.
[15]	BANERJEE A, PEIKERT C. New and Improved Key-Homomorphic Pseudorandom Functions[C]// Springer. Annual Cryptology Conference. Berlin:Springer, 2014: 353-370.
[16]	SAHAI A, WATERS B. How to Use Indistinguishability Obfuscation:Deniable Encryption, and More[C]// ACM. Proceedings of the 46th Annual ACM Symposium on Theory of Computing. New York: ACM, 2014: 475-484.
[17]	BONEH D, KIM S, MONTGOMERY H. Private Puncturable PRFs from Standard Lattice Assumptions[C]// Springer. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2017: 415-445.
[18]	CANETTI R, CHEN Yilei. Constraint-Hiding Constrained PRFs for NC1 from LWE[C]// Springer. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2017: 446-476.
[19]	BONEH D, LEWI K, WU D J. Constraining Pseudorandom Functions Privately[C]// Springer. IACR International Workshop on Public Key Cryptography. Berlin:Springer, 2017: 494-524.
[20]	BONEH D, KIM S, WU D J. Constrained Keys for Invertible Pseudorandom Functions[C]// Springer. Theory of Cryptography Conference. Beilin:Springer, 2017: 237-263.
[21]	COHEN A, HOLMGREN J, NISHIMAKI R, et al. Watermarking Cryptographic Capabilities[C]// ACM. Proceedings of the 48th Annual ACM Symposium on Theory of Computing. New York: ACM, 2016: 1115-1127.
[22]	KIM S, WU D J. Watermarking Cryptographic Functionalities from Standard Lattice Assumptions[C]// Springer. Annual International Cryptology Conference. Berlin:Springer, 2017: 503-536.
[23]	YAMADA S. Asymptotically Compact Adaptively Secure Lattice IBEs and Verifiable Random Functions via Generalized Partitioning Techniques[C]// Springer. Annual International Cryptology Conference. Berlin:Springer, 2017: 161-193.
[24]	FUCHSBAUER G. Constrained Verifiable Random Functions[C]// International Conference on Security and Cryptography for Networks. Berlin:Springer, 2014: 95-114.
[25]	CHANDRAN N, RAGHURAMAN S, VINAYAGAMURTHY D. Constrained Pseudorandom Functions: Verifiable and Delegatable[EB/OL]. (2014-05-22)[2023-02-15]. https://eprint.iacr.org/2014/522.
[26]	COHEN A, GOLDWASSER S, VAIKUNTANATHAN V. Aggregate Pseudorandom Functions and Connections to Learning[C]// Theory of Cryptography Conference. Berlin:Springer, 2015: 61-89.
[27]	ZHANDRY M. How to Avoid Obfuscation Using Witness PRFs[C]// Springer. Theory of Cryptography Conference. Berlin:Springer, 2016: 421-448.
[28]	BRAKERSKI Z, VAIKUNTANATHAN V. Constrained Key-Homomorphic PRFs from Standard Lattice Assumptions[C]// Springer. Theory of Cryptography Conference. Berlin:Springer, 2015: 1-30.
[29]	BANERJEE A, FUCHSBAUER G, PEIKERT C, et al. Key-Homomorphic Constrained Pseudorandom Functions[C]// Springer. Theory of Cryptography Conference. Berlin:Springer, 2015: 31-60.
[30]	FUCHSBAUER G, KONSTANTINOV M, PIETRZAK K, et al. Adaptive Security of Constrained PRFs[C]// Springer. International Conference on the Theory and Application of Cryptology and Information Security. Berlin:Springer, 2014: 82-101.
[31]	HOHENBERGER S, KOPPULA V, WATERS B. Adaptively Secure Puncturable Pseudorandom Functions in the Standard Model[C]// Springer. International Conference on the Theory and Application of Cryptology and Information Security. Berlin:Springer, 2015: 79-102.
[32]	DESHPANDE A, KOPPULA V, WATERS B. Constrained Pseudorandom Functions for Unconstrained Inputs[C]// Springer. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2016: 124-153.
[33]	BRAKERSKI Z, TSABARY R, VAIKUNTANATHAN V, et al. Private Constrained PRFs (and More) from LWE[C]// Springer. Theory of Cryptography Conference. Berlin:Springer, 2017: 264-302.
[34]	PEIKERT C, SHIEHIAN S. Privately Constraining and Programming PRFs, the LWE Way[C]// Springer. IACR International Workshop on Public Key Cryptography. Berlin:Springer, 2018: 675-701.
[35]	ATTRAPADUNG N, MATSUDA T, NISHIMAKI R, et al. Constrained PRFs for NC1 in Traditional Groups. (from CRYPTO 2018)[J]. Cryptology ePrint Archive, 2018, 118(212): 543-574.
[36]	BITANSKY N. Verifiable Random Functions from Non-Interactive Witness-Indistinguishable Proofs[J]. Journal of Cryptology, 2020, 33(2): 459-493. doi: 10.1007/s00145-019-09331-1
[37]	GOYAL R, HOHENBERGER S, KOPPULA V, et al. A Generic Approach to Constructing and Proving Verifiable Random Functions[C]// Springer. Theory of Cryptography Conference. Berlin:Springer, 2017: 537-566.
[38]	NAOR M, PINKAS B, REINGOLD O. Distributed Pseudo-Random Functions and KDCs[C]// Springer. International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 1999: 327-346.
[39]	GORBUNOV S, VAIKUNTANATHAN V, WEE H. Attribute-Based Encryption for Circuits[J]. Journal of the ACM (JACM), 2015, 62(6): 1-33.
[40]	BONEH D, GENTRY C, GORBUNOV S, et al. Fully Key-Homomorphic Encryption, Arithmetic Circuit ABE and Compact Garbled Circuits[C]// Springer. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2014: 533-556.
[41]	BARAK B, GOLDREICH O, IMPAGLIAZZO R, et al. On the (Im) possibility of Obfuscating Programs[C]// Springer. Annual International Cryptology Conference. Berlin:Springer, 2001: 1-18.
[42]	BONEH D, SILVERBERG A. Applications of Multilinear Forms to Cryptography[J]. Contemporary Mathematics, 2003, 324(1): 71-90.
[43]	GENTRY C, GORBUNOV S, HALEVI S. Graph-Induced Multilinear Maps from Lattices[C]// Springer. Theory of Cryptography Conference. Berlin:Springer, 2015: 498-527.
[44]	MICALI S, RABIN M, VADHAN S. Verifiable Random Functions[C]// IEEE. 40th Annual Symposium on Foundations of Computer Science. New York: IEEE, 1999: 120-130.
[45]	DENG Yi, LIN Dongdai. Instance-Dependent Verifiable Random Functions and Their Application to Simultaneous Resettability[C]// Springer. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2007: 148-168.
[46]	BRAKERSKI Z, GOLDWASSER S, ROTHBLUM G N, et al. Weak Verifiable Random Functions[C]// Springer. Theory of Cryptography Conference. Berlin:Springer, 2009: 558-576.
[47]	FIORE D, SCHRODER D. Uniqueness is a Different Story: Impossibility of Verifiable Random Functions from Trapdoor Permutations[C]// Springer. Theory of Cryptography Conference. Berlin:Springer, 2012: 636-653.
[48]	KUROSAWA K, NOJIMA R, PHONG L T. Relation Between Verifiable Random Functions and Convertible Undeniable Signatures, and New Constructions[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2014, 97(1): 215-224.
[49]	KUCHTA V, MANULIS M. Unique Aggregate Signatures with Applications to Distributed Verifiable Random Functions[C]// Springer. International Conference on Cryptology and Network Security. Berlin:Springer, 2013: 251-270.
[50]	BADRINARAYANAN S, GOYAL V, JAIN A, et al. A Note on VRFs from Verifiable Functional Encryption[EB/OL]. (2017-09-17)[2023-02-15]. https://www.xueshufan.com/publication/2899823642.
[51]	LYSYANSKAYA A. Unique Signatures and Verifiable Random Functions from the DH-DDH Separation[C]// Springer. Annual International Cryptology Conference. Berlin:Springer, 2002: 597-612.
[52]	DODIS Y. Efficient Construction of (Distributed) Verifiable Random Functions[C]// Springer. Proceedings of the 6th International Workshop on Public Key Cryptography. Berlin:Springer, 2003: 1-17.
[53]	DODIS Y, YAMPAMPOLSKIY A. A Verifiable Random Function with Short Proofs and Keys[C]// Springer. International Workshop on Public Key Cryptography. Berlin:Springer, 2005: 416-431.
[54]	JAGER T. Verifiable Random Functions from Weaker Assumptions[C]// Springer. Theory of Cryptography Conference. Berlin:Springer, 2015: 121-143.
[55]	HOFHEINZ D, JAGER T. Verifiable Random Functions from Standard Assumptions[C]// Springer. Theory of Cryptography Conference. Berlin:Springer, 2016: 336-362.
[56]	LIANG Bei, LIHongda, CHANGJinyong. Constrained Verifiable Random Functions from Indistinguishability Obfuscation[C]// Springer. International Conference on Provable Security. Berlin:Springer, 2015: 43-60.
[57]	LIANG Bei, LIHongda, CHANGJinyong. Verifiable Random Functions from (Leveled) Multilinear Maps[C]// Springer. International Conference on Cryptology and Network Security. Berlin:Springer, 2015: 129-143.
[58]	MICALI S, REYZIN L. Soundness in the Public-Key Model[C]// Springer. Annual International Cryptology Conference. Berlin:Springer, 2001: 542-565.
[59]	LISKOV M. Updatable Zero-Knowledge Databases[C]// Springer. International Conference on the Theory and Application of Cryptology and Information Security. Berlin:Springer, 2005: 174-198.
[60]	AU M H, SUSILO W, MU Yi. Practical Compact E-Cash[C]// Springer. Australasian Conference on Information Security and Privacy. Berlin:Springer, 2007: 431-445.
[61]	BELENKIY M, CHASE M, KOHLWEISS M, et al. Compact E-Cash and Simulatable VRFs Revisited[C]// Springer. International Conference on Pairing-Based Cryptography. Berlin:Springer, 2009: 114-131.
[62]	LIBERT B, LING S, NGUYEN K, et al. Zero-Knowledge Arguments for Lattice-Based PRFs and Applications to E-Cash[C]// Springer. International Conference on the Theory and Application of Cryptology and Information Security. Berlin:Springer, 2017: 304-335.
[63]	FAN Lei, ZHOU Hongsheng. A Scalable Proof-of-Stake Blockchain in the Open Setting (or, How to Mimic Nakamoto’s Design via Proof-of-Stake)[EB/OL]. (2017-06-05)[2023-02-15]. https://eprint.iacr.org/2017/656.pdf.
[64]	BONEH D, BOYEN X. Efficient Selective-ID Secure Identity-Based Encryption Without Random Oracles[C]// Springer. International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2004: 223-238.
[65]	CHATTERJEE S, KOBLITZ N, MENEZES A, et al. Another Look at Tightness II: Practical Issues in Cryptography[C]// Springer. International Conference on Cryptology in Malaysia. Berlin:Springer, 2016: 21-55.
[66]	HOFHEINZ D, KAMATH A, KOPPULA V, et al. Adaptively Secure Constrained Pseudorandom Functions[C]// Springer. International Conference on Financial Cryptography and Data Security. Berlin:Springer, 2019: 357-376.
[67]	NAOR M, REINGOLD O. Number-Theoretic Constructions of Efficient Pseudo-Random Functions[J]. Journal of the ACM (JACM), 2004, 51(2): 231-262. doi: 10.1145/972639.972643 URL
[68]	HOFHEINZ D. Fully Secure Constrained Pseudorandom Functions Using Random Oracles[J]. Cryptology ePrint Archive, 2014, 9: 1-24.
[69]	GORBUNOV S, VAIKUNTANATHAN V, WEE H. Predicate Encryption for Circuits from LWE[C]// Springer. Annual Cryptology Conference. Berlin:Springer, 2015: 503-523.
[70]	GORBUNOV S, VAIKUNTANATHAN V, WICHS D. Leveled Fully Homomorphic Signatures from Standard lattices[C]// ACM. Proceedings of the 47th Annual ACM Symposium on Theory of Computing. New York: ACM, 2015: 469-477.
[71]	BONEH D, ZHANDRY M. Multiparty Key Exchange, Efficient Traitor Tracing, and More from Indistinguishability Obfuscation[C]// Springer. International Cryptology Conference. Berlin:Springer, 2017: 1233-1285.

PRF类型	相关研究
khPRFs	文献[6,15,28,29]方案
cPRFs	文献[3-5,28-32]方案
pcPRFs	文献[4,17,18,33-35]方案
VRFs	文献[23,36,37]方案
cVRFs	文献[24,25]方案

方案	假设	工具	模型	功能	密钥数	Eval.O	备注
文献[3]方案	OWF	GGM	标准	puncture	N/A	N/A
文献[3]方案	BDDH	Pairing	ROM	left/right	multi	√
文献[4]方案	OWF	GGM	标准	puncture	N/A	N/A
文献[5]方案	OWF	GGM	标准	puncture	N/A	N/A
文献[28]方案	LWE&1D-SIS	Lattice	标准	circuit	single	√	key-hom
文献[29]方案	LWE	Lattice	标准	prefix-fixing	multi	√	key-hom
文献[37]方案	L-power DDH	Lattice	标准	sub-match	single	×
文献[37]方案	$\phi $-hiding	Lattice	标准	sub-match	single	×
文献[36]方案	DDH	Lattice	标准	sub-match	single	×

受限伪随机函数	相关研究	密钥
prefix-constrained PRF	文献[3-5]方案	keys for sets ${{S}_{p}}=\{p\|\|z\|\in {{\{0,1\}}^{n-\|p\|}}\}$
bit-fixing PRF	文献[3]方案	keys for sets defined by $u\in {{\{0,1,?\}}^{n}}$ as ${{S}_{v}}=\{z\in {{\{0,1\}}^{n}}\|\forall i:{{z}_{i}}={{v}_{i}}\vee {{v}_{i}}=\}$
circuit-constrained PRF	文献[3]方案	keys defined by circuit C ${{S}_{C}}=\{z\in {{\{0,1\}}^{n}}\|C(z)=1\}$

方案	假设	工具	模型	功能	密钥数	Eval.O	备注
文献[4] 方案	OWF	GGM	标准	puncture	N/A	N/A
文献[19]方案	iO	Obf	标准	puncture	multi	√	programmable
文献[19]方案	iO	Obf	标准	bit-fixing	multi	√
文献[17]方案	LWE& 1D-SIS	Lattice	标准	puncture	N/A	N/A
文献[18]方案	LWE	Lattice	标准	bit-fixing	single	√
文献[18]方案	LWE	Lattice	标准	NC1	single	√
文献[33]方案	LWE	Lattice	标准	circuit	single	√
文献[34]方案	LWE	Lattice	标准	circuit	single	√	programmable
文献[35]方案	DDH	Group	标准	bit-fixing	single	√

假设	相关研究
Bilinear Pairing	文献[51-54]方案
DLIN	文献[55]方案
MDDH	文献[24,25,56,57]方案
Lattice	文献[37]方案