DROPS

Document

DOI: 10.4230/LIPIcs.ITC.2026.6

Towards Characterizing Secure Samplability

Authors: Hari Krishnan P. Anilkumar, Keval Jain, Manoj Prabhakaran, and Vinod M. Prabhakaran

Published in: LIPIcs, Volume 385, 7th Conference on Information-Theoretic Cryptography (ITC 2026)

Abstract

This work deals with the fundamental problem of characterizing which multiparty distributions can be securely sampled with information-theoretic security against passive corruption, when there is no setup or honest-majority. We focus on the case of 4-party distributions with boolean outputs for each party. We show that such a distribution is securely samplable if and only if every 2-party distribution derived from it by partitioning the parties into two sets is securely samplable. This extends a similar characterization previously known for 3-party distributions.

Cite as

Hari Krishnan P. Anilkumar, Hari Krishnan P. Anilkumar, Keval Jain, Keval Jain, Manoj Prabhakaran, Manoj Prabhakaran, Vinod M. Prabhakaran, and Vinod M. Prabhakaran. Towards Characterizing Secure Samplability. In 7th Conference on Information-Theoretic Cryptography (ITC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 385, pp. 6:1-6:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{anilkumar_et_al:LIPIcs.ITC.2026.6,
  author =	{Anilkumar, Hari Krishnan P. and Jain, Keval and Prabhakaran, Manoj and Prabhakaran, Vinod M.},
  title =	{{Towards Characterizing Secure Samplability}},
  booktitle =	{7th Conference on Information-Theoretic Cryptography (ITC 2026)},
  pages =	{6:1--6:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-426-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{385},
  editor =	{Dodis, Yevgeniy},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2026.6},
  URN =		{urn:nbn:de:0030-drops-270991},
  doi =		{10.4230/LIPIcs.ITC.2026.6},
  annote =	{Keywords: secure sampling, information-theoretic MPC}
}

Document

DOI: 10.4230/LIPIcs.ICALP.2016.88

Rényi Information Complexity and an Information Theoretic Characterization of the Partition Bound

Authors: Manoj M. Prabhakaran and Vinod M. Prabhakaran

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract

In this work we introduce a new information-theoretic complexity measure for 2-party functions, called Rényi information complexity. It is a lower-bound on communication complexity, and has the two leading lower-bounds on communication complexity as its natural relaxations: (external) information complexity and logarithm of partition complexity. These two lower-bounds had so far appeared conceptually quite different from each other, but we show that they are both obtained from Rényi information complexity using two different, but natural relaxations: 1. The relaxation of Rényi information complexity that yields information complexity is to change the order of Rényi mutual information used in its definition from infinity to 1. 2. The relaxation that connects Rényi information complexity with partition complexity is to replace protocol transcripts used in the definition of Rényi information complexity with what we term "pseudotranscripts", which omits the interactive nature of a protocol, but only requires that the probability of any transcript given inputs x and y to the two parties, factorizes into two terms which depend on x and y separately. While this relaxation yields an apparently different definition than (log of) partition function, we show that the two are in fact identical. This gives us a surprising characterization of the partition bound in terms of an information-theoretic quantity. We also show that if both the above relaxations are simultaneously applied to Rényi information complexity, we obtain a complexity measure that is lower-bounded by the (log of) relaxed partition complexity, a complexity measure introduced by Kerenidis et al. (FOCS 2012). We obtain a sharper connection between (external) information complexity and relaxed partition complexity than Kerenidis et al., using an arguably more direct proof. Further understanding Rényi information complexity (of various orders) might have consequences for important direct-sum problems in communication complexity, as it lies between communication complexity and information complexity.

Cite as

Manoj M. Prabhakaran and Vinod M. Prabhakaran. Rényi Information Complexity and an Information Theoretic Characterization of the Partition Bound. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 88:1-88:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{prabhakaran_et_al:LIPIcs.ICALP.2016.88,
  author =	{Prabhakaran, Manoj M. and Prabhakaran, Vinod M.},
  title =	{{R\'{e}nyi Information Complexity and an Information Theoretic Characterization of the Partition Bound}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{88:1--88:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.88},
  URN =		{urn:nbn:de:0030-drops-61970},
  doi =		{10.4230/LIPIcs.ICALP.2016.88},
  annote =	{Keywords: Information Complexity, Communication Complexity, R\'{e}nyi Mutual Information}
}

Search Results

Documents authored by Prabhakaran, Vinod M.

Towards Characterizing Secure Samplability

Abstract

Cite as

Rényi Information Complexity and an Information Theoretic Characterization of the Partition Bound

Abstract

Cite as

Thanks for your feedback!

Could not send message