Shared generation of pseudo-random functions

Huaxiong Wang*, Josef Pieprzyk

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


In Crypto'95, Micali and Sidney proposed a method for shared generation of a pseudorandom function f(·) among n players in such a way that for all the inputs x, any u players can compute f(x) while t or fewer players fail to do so, where 0≤t<u≤n. The idea behind the Micali-Sidney scheme is to generate and distribute secret seeds S = {s1, ...,sd} of a polyrandom collection of functions, among the n players, each player gets a subset of S, in such a way that any u players together hold all the secret seeds in S while any t or fewer players will lack at least one element from S. The pseudo-random function is then computed as A figure is presented. where fsi(·)'s are poly-random functions. One question raised by Micali and Sidney is how to distribute the secret seeds satisfying the above condition such that the number of seeds, d, is as small as possible. In this paper, we continue the work of Micali and Sidney. We first provide a general framework for shared generation of pseudo-random function using cumulative maps. We demonstrate that the Micali-Sidney scheme is a special case of this general construction. We then derive an upper and a lower bound for d. Finally we give a simple, yet efficient, approximation greedy algorithm for generating the secret seeds S in which d is close to the optimum by a factor of at most u ln 2.

Original languageEnglish
Pages (from-to)458-472
Number of pages15
JournalJournal of Complexity
Issue number2-3
Publication statusPublished - Apr 2004


  • Cryptography
  • Pseudo-random functions
  • Secret sharing


Dive into the research topics of 'Shared generation of pseudo-random functions'. Together they form a unique fingerprint.

Cite this