Paper 2021/1037
Randomness Bounds for Private Simultaneous Messages and Conditional Disclosure of Secrets
Akinori Kawachi and 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 \lambda1$ 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^{(k1)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 FeigeKillianNaor protocol for a general function [Proc.~STOC '94, pp.554563]\ is optimal with respect to randomness complexity. We also provide a randomness lower bound $\rho> kn2$ for a generalized inner product function. This implies the optimality of the $2$party PSM protocol for the innerproduct function of Liu, Vaikuntanathan, and Wee [Proc.~CRYPTO 2017, pp.758790]. 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 (k1)\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.317344]\ up to a constant factor in a large $k$.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Keywords
 Private simultaneous messagesconditional disclosure of secretsrandomness complexitycommunication complexity
 Contact author(s)
 kawachi @ info mieu ac jp
 History
 20210816: received
 Short URL
 https://ia.cr/2021/1037
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/1037, author = {Akinori Kawachi and Maki Yoshida}, title = {Randomness Bounds for Private Simultaneous Messages and Conditional Disclosure of Secrets}, howpublished = {Cryptology ePrint Archive, Paper 2021/1037}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/1037}}, url = {https://eprint.iacr.org/2021/1037} }