### An Efficient Pseudo-Random Generator with Applications to Public-Key Encryption and Constant-Round Multiparty Computation

Ivan Damgård and Jesper Buus Nielsen

##### Abstract

We present a pseudo-random bit generator expanding a uniformly random bit-string r of length k/2, where k is the security parameter, into a pseudo-random bit-string of length 2k &#8722; log^2(k) using one modular exponentiation. In contrast to all previous high expansion-rate pseudo-random 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 pseudo-random bit generator we exploit its efficiency to optimise Paillier’s crypto-system 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 constant-round 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^2|C|) 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.

Available format(s)
Category
Cryptographic protocols
Publication info
Preprint.
Contact author(s)
jbn @ cs au dk
History
Short URL
https://ia.cr/2014/024

CC BY

BibTeX

@misc{cryptoeprint:2014/024,
author = {Ivan Damgård and Jesper Buus Nielsen},
title = {An Efficient Pseudo-Random Generator with Applications to Public-Key Encryption and Constant-Round 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}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.