伪随机函数与密码算法

伪随机函数研究

胡红钢

中国科学技术大学

一 研究背景概述

一簇有效可计算的确定性函数被称为是伪随机的，如果不存在多项式时间的攻击者，能够以不可忽视的概率区分如下两种情况：一个函数是随机地选自该簇，还是选自真随机的函数簇。伪随机函数是密码学的基础性问题。在密码学中，伪随机函数可以用于模拟随机预言机（Random Oracle）。伪随机函数也是构造密码算法和协议极端重要的基本工具。如果不存在伪随机函数，就不可能存在安全的密码算法和协议。通过有效地利用伪随机函数，我们可以构造加密、消息认证码和身份认证等方案。此外，伪随机函数在复杂度理论领域也有重要的应用。

与伪随机函数相比，可验证的伪随机函数除了提供正常的输出以外，还会提供一个非交互的证明π。利用π，任何人都可以验证与π对应的输出是否正确，这就很好地将不可预测性（Unpredictability）与可验证性（Verifiability）结合到了一起。与带密钥的Hash函数相比，可验证的伪随机函数可以看成公钥版本的带密钥Hash函数。可验证的伪随机函数与其他密码学基本构件存在着深刻的联系，如基于身份的加密方案、非交互式零知识证明协议等。目前，密码学家还在继续开展这方面的研究。可验证的伪随机函数可应用于区块链领域。在区块链中，有些分布式共识协议在选择session leader或者committee member时，既需要不可预测性，又需要可验证性（如Algorand），可验证的伪随机函数正好满足这种需求。

二 主要科学问题

目前，该领域的主要问题是：构造可以抵抗量子计算攻击的伪随机函数，特别是可验证的伪随机函数。量子计算是计算技术的必然发展趋势。首先，这涉及计算复杂度问题：什么样的计算困难问题才能真正抵抗量子计算的攻击？（这个问题的难度非常大）其次，除了LPN、LWE、Ring-LWE这些受到广泛关注的问题以外，是否可以找到其他问题，不但支持高效复杂的运算，还具有可证明的难度？这涉及怎样嵌入更好的代数结构，以及怎么处理一般性的噪声模式。最后，面向分布式的网络环境，如P2P网络，怎样设计实用的可验证伪随机函数？现在，基于LWE等问题的密钥协商、加密、签名、密钥封装等结果已经很多，是否可以将这些结果或者其中的想法用于可验证伪随机函数的构造？

三 国际研究现状

1984年，Goldreich、Goldwasser和Micali^[1]提出了伪随机函数的概念。假设伪随机序列发生器存在的前提下，他们给出了第一个伪随机函数的树状构造方法，人们称之为GGM构造。1997年，Naor和Reingold^[2]给出了两类基于数论的有效构造方法：第一种基于DDH假设；第二种基于分解Blum整数的困难性。2000年，Naor、Reingold和Rosen^[3]给出了另一种基于整数分解的构造方法，效率更高。2012年，Banerjee、Peikert和Rosen^[4]提出了LWR问题，该问题的难度可以约化到LWE问题。基于LWR问题，并借鉴GGH构造中的技术，他们给出了基于格的伪随机函数构造方法。2013年，Boneh、Lewi、Montgomery等^[5]给出了基于格的密钥同态伪随机函数。2014年，Banerjee和Peikert^[6]改进了这个结果：降低了密钥规模，并提高了效率。2015年，Brakerski和Vaikuntanathan^[7]进一步推广了上述两个结果，可以将电路秘密地嵌入伪随机函数中。

1999年，Micali、Rabin和Vadhan^[8]提出了可验证伪随机函数的概念。基于RSA假设的一个变形，他们构造了第一类可验证的伪随机函数。2003年，Dodis^[9]利用椭圆曲线上的双线性对给出了一种新的构造方法，但效率较低。2005年，Dodis和Yampolskiy^[10]改进了这个构造，其安全基础来源于双线性判定Diffie-Hellman逆假设（DBDHI）。2009年，Abdalla、Catalano和Fiore^[11]发现，基于ID的密钥封装机制（IB-KEM）可以用于构造可验证伪随机函数。2014年，基于双线性判定L-弱Diffie-Hellman逆假设（L-wBDHI*），他们^[12]又给出了一种新的构造方法。2017年，Goyal、Hohenberger、Koppula等^[13]利用非交互证据不可区分证明（NIWI）等技术给出了一种新的构造可验证伪随机函数的方法，并利用LWE问题和LPN问题给出了具体实例。

四 国内研究现状

在这个领域，国内的相关结果较少。2007年，为了解决Barak等在2001年提出的关于可重置零知识证明的猜想，邓燚和林东岱教授^[14]提出了依赖于实例（Instance-Dependent）的可验证伪随机函数。他们证明了如果存在陷门置换，那么存在这种特殊的可验证伪随机函数，并给出了具体的构造方法。2016年，郁昱和Steinberger^[15]首次利用LPN构造了一类伪随机函数，因为它是并行的，该类函数效率较高。此外，在国内期刊上，受到Peikert和Rosen在2012年工作的启发，2014年，陈和风等^[16]利用短整数解问题（SIS问题）给出了两种伪随机函数的构造方法，第一种是并行结构，第二种是串行结构。

五 未来研究建议

面向未来的量子计算时代，构造安全的可验证伪随机函数。新的计算技术会带来新的安全问题和安全需求，对随机性的要求也更加严格。该领域有两个问题具有较大的理论意义和应用价值。

（1）现有构造方法的密码分析

基于格，密码学家已经找到了一些构造方法，但这些构造方法在量子计算下的真实安全水平，还有待进一步的密码分析来衡量。这涉及底层的计算困难问题，在量子计算下的真实困难程度。

（2）抗量子攻击的可验证伪随机函数

基于格来构造可验证的伪随机函数，需要利用底层计算困难问题的更多代数结构，以便嵌入更合适的陷门，同时还要借鉴基于格的数字签名和基于身份的加密方案中的技巧。

参考文献：

[1] GOLDREICH O, GOLDWASSER S, MICALI S. How to construct Randolli functions[C]//IEEE 25th Annual Symposium on Foundations of Computer Science. 1984: 464-479.

[2] NAOR M, REINGOLD O. Number-theoretic constructions of efficient pseudo-random functions[J]. Journal of the ACM (JACM). 2004, 51(2): 231-262.

[3] NAOR M, REINGOLD O, ROSEN A. Pseudorandom functions and factoring[J]. SIAM Journal on Computing. 2002, 31(5): 1383-1404.

[4] BANERJEE A, PEIKERT C, ROSEN A. Pseudorandom functions and lattices[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2012: 719-737.

[5] BONEH D, LEWI K, MONTGOMERY H, et al. Key homomorphic PRFs and their applications[C]//Advances in Cryptology–CRYPTO 2013. 2013: 410-428.

[6] BANERJEE A, PEIKERT C. New and improved key-homomorphic pseudorandom functions[C]// International Cryptology Conference. 2014: 353-370.

[7] BRAKERSKI Z, VAIKUNTANATHAN V. Constrained key-homomorphic PRFs from standard lattice assumptions[C]//Theory of Cryptography Conference. 2015: 1-30.

[8] MICALI S, RABIN M, VADHAN S. Verifiable random functions[C]//IEEE 40th Annual Symposium on Foundations of Computer Science. 1999: 120-130.

[9] DODIS Y. Efficient construction of (distributed) verifiable random functions[C]//International Workshop on Public Key Cryptography. 2003: 1-17.

[10] DODIS Y, YAMPOLSKIY A. A verifiable random function with short proofs and keys[C]//International Workshop on Public Key Cryptography. 2005: 416-431.

[11] ABDALLA M, CATALANO D, FIORE D. Verifiable random functions from identity-based key encapsulation[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques.2009: 554-571.

[12] ABDALLA M, CATALANO D, FIORE D. Verifiable random functions: relations to identity-based key encapsulation and new constructions[J]. Journal of Cryptology, 2014, 27(3): 544-593.

[13] GOYAL R, HOHENBERGER S, KOPPULA V, et al. A generic approach to constructing and proving verifiable random functions[C]//Theory of Cryptography Conference. 2017: 537-566.

[14] DENG Y, LIN D D. Instance-dependent verifiable random functions and their application to simultaneous resettability[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2007: 148-168.

[15] YU Y, STEINBERGER J. Pseudorandom functions in almost constant depth from low-noise LPN[C]// Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2016: 154-183.

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