Welcome to the resource topic for 2021/1037
Title:
Randomness Bounds for Private Simultaneous Messages and Conditional Disclosure of Secrets
Authors: Akinori Kawachi, Maki Yoshida
Abstract:In cryptography, the private simultaneous messages (PSM) and conditional disclosure of secrets (CDS) are closely related fundamental primitives. We consider k-party PSM and CDS protocols for a function f with a \rho-bit common random string, where each party P_i generates an \lambda_i-bit message (i\in[k]), and sends it to a referee P_0. We consider bounds for the optimal length \rho of the common random string among k parties (or, {\it randomness complexity}) in PSM and CDS protocols with perfect and statistical privacy through combinatorial and entropic arguments. (i) We provide general connections from the optimal total length \lambda = \sum_{i\in[k]}\lambda_i of the messages (or, {\it communication complexity}) to the randomness complexity \rho. (ii) We also prove randomness lower bounds in PSM and CDS protocols for general functions. (iii) We further prove randomness lower bounds for several important explicit functions. They contain the following results: For PSM protocols with perfect privacy, we prove \rho\ge \lambda-1 and \rho\le \lambda as the general connection. To prove the upper bound, we provide a new technique for randomness sparsification for {\it perfect}/ privacy, which would be of independent interest. From the general connection, we prove \rho\ge 2^{(k-1)n}-1 for a general function f:(\{0,1\}^n)^k\rightarrow\{0,1\} under universal reconstruction, in which P_0 is independent of f. This implies that the Feige-Killian-Naor protocol for a general function [Proc.~STOC '94, pp.554–563]\ is optimal with respect to randomness complexity. We also provide a randomness lower bound \rho> kn-2 for a generalized inner product function. This implies the optimality of the 2-party PSM protocol for the inner-product function of Liu, Vaikuntanathan, and Wee [Proc.~CRYPTO 2017, pp.758–790]. For CDS protocols with perfect privacy, we show \rho\ge\lambda-\sigma and \rho\le\lambda as the general connection by similar arguments to those for PSM protocols, where \sigma is the length of secrets. We also obtain randomness lower bounds \rho\ge (k-1)\sigma for XOR, AND, and generalized inner product functions. These imply the optimality of Applebaum and Arkis’s k-party CDS protocol for a general function [Proc. TCC 2018, pp.317–344]\ up to a constant factor in a large k.
ePrint: https://eprint.iacr.org/2021/1037
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 .