On the provable security of an efficient RSA-based pseudorandom generator

Pseudorandom Generators (PRGs) based on the RSA inversion (one-wayness) problem have been extensively studied in the literature over the last 25 years. These generators have the attractive feature of provable pseudorandomness security assuming the hardness of the RSA inversion problem. However, despite extensive study, the most efficient provably secure RSA-based generators output asymptotically only at most O(logn) bits per multiply modulo an RSA modulus of bitlength n, and hence are too slow to be used in many practical applications. To bring theory closer to practice, we present a simple modification to the proof of security by Fischlin and Schnorr of an RSA-based PRG, which shows that one can obtain an RSA-based PRG which outputs Ω(n) bits per multiply and has provable pseudorandomness security assuming the hardness of a well-studied variant of the RSA inversion problem, where a constant fraction of the plaintext bits are given. Our result gives a positive answer to an open question posed by Gennaro (J. of Cryptology, 2005) regarding finding a PRG beating the rate O(logn) bits per multiply at the cost of a reasonable assumption on RSA inversion.

使用压缩函数的非平衡Feistel结构的伪随机性和超伪随机性

从可证明安全的角度研究使用压缩函数的非平衡Feistel结构(UFN-C)的安全性,证明了k+1轮UFN-C是伪随机的,k+2轮UFN-C是超伪随机的;进一步地,探讨了UFN-C的有效构造,降低了Naor和Reingold在1999年文章中类似结构对伪随机函数个数的要求.最后,针对一类具体的UFN-C--SMs4,分析其广义形式SMS4-like结构的伪随机性和超伪随机性,为设计与使用该类结构的分组密码提供了可证明安全的理论依据.

优化MISTY型结构的伪随机性

该文对4轮MISTY和3轮双重MISTY两种结构进行了优化。在保持其安全性不变的情况下，把4轮MISTY结构中第1轮的伪随机置换，用一个XOR-泛置换代替，第2，第3轮采用相同的伪随机置换，3轮结构中第1轮的伪随机置换用XOR-泛置换代替，其它轮相同。伪随机置换的数量分别由原来的4个变为2个，3个变为1个，从而缩短了运行时间，节省了密钥量，大大降低了结构的实现成本。