Welcome to the resource topic for 2024/1448
Title:
Randomness in Private Sequential Stateless Protocols
Authors: Hari Krishnan P. Anilkumar, Varun Narayanan, Manoj Prabhakaran, Vinod M. Prabhakaran
Abstract:A significant body of work in information-theoretic cryptography has been devoted to the fundamental problem of understanding the power of randomness in private computation. This has included both in-depth study of the randomness complexity of specific functions (e.g., Couteau and Ros ́en, ASIACRYPT 2022, gives an upper bound of 6 for n-party \mathsf{AND}), and results for broad classes of functions (e.g., Kushilevitz et al. STOC 1996, gives an O(1) upper bound for all functions with linear-sized circuits). In this work, we make further progress on both fronts by studying randomness complexity in a new simple model of secure computation called Private Sequential Stateless (PSS) model.
We show that functions with O(1) randomness complexity in the PSS model are exactly those with constant-width branching programs, restricting to “speak-constant-times” protocols and to “read-constant-times” branching programs.
Towards this our main construction is a novel PSS protocol for “strongly regular branching programs” (SRBP). As we show, any constant-width branching program can be converted to a constant-width SRBP, yielding one side of our characterization. The converse direction uses ideas from Kushilevitz et al. to translate randomness to communication.
Our protocols are concretely efficient, has a simple structure, covers the broad class of functions with small-width, read-once (or read-a-few-times) branching programs, and hence may be of practical interest when 1-privacy is considered adequate. Also, as a consequence of our general result for SRBPs, we obtain an improvement over the protocol of Couteau and Ros ́en for \mathsf{AND} in certain cases — not in terms of the number of bits of randomness, but in terms of a simpler protocol structure (sequential, stateless).
ePrint: https://eprint.iacr.org/2024/1448
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .