Shared generation of pseudo-random functions

DOI10.1016/J.JCO.2003.08.021MaRDI QIDQ1827581zbMATH OpenOpenAlexWikidataFDO

Publication date 6 August 2004

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jco.2003.08.021

access structure cryptography cumulative maps pseudo-random functions resilient collection of sets secret sharing set-cover problem

Mathematics Subject Classification ID

Cryptography (94A60) Authentication, digital signatures and secret sharing (94A62)

Review text

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\).

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Shared generation of pseudo-random functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1827581)