Paper 2014/024
An Efficient PseudoRandom Generator with Applications to PublicKey Encryption and ConstantRound Multiparty Computation
Ivan Damgård and Jesper Buus Nielsen
Abstract
We present a pseudorandom bit generator expanding a uniformly random bitstring r of length k/2, where k is the security parameter, into a pseudorandom bitstring of length 2k − log^2(k) using one modular exponentiation. In contrast to all previous high expansionrate pseudorandom bit generators, no hashing is necessary. The security of the generator is proved relative to Paillier’s composite degree residuosity assumption. As a first application of our pseudorandom bit generator we exploit its efficiency to optimise Paillier’s cryptosystem by a factor of (at least) 2 in both running time and usage of random bits. We then exploit the algebraic properties of the generator to construct an efficient protocol for secure constantround multiparty function evaluation in the cryptographic setting. This construction gives an improvement in communication complexity over previous protocols in the order of nk^2, where n is the number of participants and k is the security parameter, resulting in a communication complexity of O(nk^2C) bits, where C is a Boolean circuit computing the function in question.
Note: This paper was made public on the homepage of one of the authors almost a decade ago. It was never published elsewhere. However, it has by now been cited a number of times, so we make it available on eprint for archival purposes / future availability.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Preprint.
 Contact author(s)
 jbn @ cs au dk
 History
 20140108: received
 Short URL
 https://ia.cr/2014/024
 License

CC BY
BibTeX
@misc{cryptoeprint:2014/024, author = {Ivan Damgård and Jesper Buus Nielsen}, title = {An Efficient PseudoRandom Generator with Applications to PublicKey Encryption and ConstantRound Multiparty Computation}, howpublished = {Cryptology ePrint Archive, Paper 2014/024}, year = {2014}, note = {\url{https://eprint.iacr.org/2014/024}}, url = {https://eprint.iacr.org/2014/024} }