Cryptology ePrint Archive: Report 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 \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$.

Category / Keywords: foundations / Private simultaneous messages, conditional disclosure of secrets, randomness complexity, communication complexity

Date: received 10 Aug 2021

Contact author: kawachi at info mie-u ac jp

Available format(s): PDF | BibTeX Citation

Version: 20210816:130824 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]