Shared generation of pseudo-random functions (Q1827581)

This is a continuation of the idea of \textit{S. Micali} and \textit{R. Sidney} [Lect. Notes Comput. Sci. 963, 185--196 (1995; Zbl 0868.94030)] for shared generation of a pseudo-random function \(f\) among \(n\) players such that \(u\) of the players can compute \(f(x)\) while \(t\) or fewer of them do not do it, for each input \(x\). To study this problem, the notion of a ramp access structure is introduced and discussed. The main results are obtained for a special case of these objects, so-called \((t,u,n)\) ramp access structures with \((t,u,n)\) cumulative maps, which for \(t=u-1\) form the \((u,n)\) threshold access structures with \((u,n)\) cumulative maps studied by Micali and Sidney. For the minimal \((t,u,n)\) cumulative maps lower and upper bounds are derived. The paper has been crowned with an algorithm that designs a \((t,u,n)\) cumulative map as the solution of a special case of the set-cover problem. This construction achieves the optimum bound by a factor of at most \(u\ln2\).