Shared generation of pseudo-random functions with cumulative maps

Huaxiong Wang, Josef Pieprzyk

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)


In Crypto'95, Micali and Sidney proposed a method for shared generation of a pseudo-random function f(·) among n players in such a way that for all the inputs x, any u players can compute f(cursive Greek chi) 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 poly-random collection of functions, among the n players, each player gets a subset of 5, 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 d f(cursive Greek chi) = ⊕ fSi,(cursive Greek chi), i=1 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 In 2.

Original languageEnglish
Pages (from-to)281-294
Number of pages14
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publication statusPublished - 2003


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

Cite this