Paper 2021/1037

Randomness Bounds for Private Simultaneous Messages and Conditional Disclosure of Secrets

Akinori Kawachi, Mie University
Maki Yoshida, National Institute of Information and Communications Technology
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)
PDF
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.