Paper 2021/1037
Randomness Bounds for Private Simultaneous Messages and Conditional Disclosure of Secrets
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, 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, 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 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$.
Note: Theorem 6 in the first version had a technical flaw. We have deleted it and the related theorems in the current revised version.
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- Private simultaneous messages conditional disclosure of secrets randomness complexity communication complexity
- Contact author(s)
-
kawachi @ info mie-u ac jp
maki-yos @ nict go jp - History
- 2022-12-18: revised
- 2021-08-16: received
- See all versions
- 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} }