Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Leibniz international proceedings in informatics

Towards Characterizing Secure Samplability

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

Published Jan 1, 2026• 0 citations
Publisher

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.

DOI
10.4230/lipics.itc.2026.6

Related papers

Secure Two-Party Sampling Primitives are either Useless or Complete.

Ye Wang, Prakash Ishwar, Shantanu D. Rane

In the secure two-party sampling problem, two parties wish to generate outputs with a desired joint distribution via an interactive protocol, while ensuring that neither party learns more than what can be inferred from only their own output. For semi-honest parties and information-theoretic privacy guarantees, it is well-known that if only noiseless communication is available, then only the joint distributions, for which common information equals mutual information, can be securely sampled. We consider the problem where the parties may also interact via a given set of general communication primitives (multi-input/output channels). Our feasibility characterization of this problem can be stated as a zero-one law: primitives are either complete (enabling the secure sampling of any distribution) or useless (only enabling the secure sampling of trivial distributions). Our characterization of the complete primitives also extends to the more general class of secure two-party computation problems.

•Feb 18, 2014•0 citations

A Zero-One Law for Secure Multi-Party Computation with Ternary Outputs (full version).

Gunnar Kreitz

Abstract. There are protocols to privately evaluate any function in the passive (honest-but-curious) setting assuming that the honest nodes are in majority. For some specific functions, protocols are known which remain secure even without an honest majority. The seminal work by Chor and Kushilevitz [7] gave a complete characterization of Boolean functions, showing that each Boolean function either requires an honest majority, or is such that it can be privately evaluated regardless of the number of colluding nodes. The problem of discovering the threshold for secure evaluation of more general functions remains an open problem. Towards a resolution, we provide a complete characterization of the security threshold for functions with three different outputs. Surprisingly, the zero-one law for Boolean functions extends to Z3, meaning that each function with range Z3 either requires honest majority or tolerates up to n colluding nodes. 1

•Jan 1, 2011•3 citations

Information-Theoretic Secure Multiparty Computation

Ueli M. Maurer, Vassilis Zikas

Most of this book has considered two-party and multiparty computation with security with (unfair) abort. This security notion allows the adversary to force the honest parties to abort even depending on the outputs of corrupted parties. (Note, however, that the adversary is not allowed to bias the output of honest parties in any other manner.) This relaxation of security is necessary if one wishes to tolerate arbitrarily many corruptions. A further relaxation considers computational security, where the adversary is assumed to be computationally bounded, e.g., probabilistic polynomial time. In this setting, any circuit can be securely realized even when arbitrarily many parties are corrupted, as long as one is willing to sacrifice fairness and robustness.

IOS Press eBooks•Jan 1, 2013•0 citations

On Achieving the “Best of Both Worlds” in Secure Multiparty Computation

Yuval Ishai, Jonathan I. Katz, Eyal Kushilevitz Z +2 more

Two settings are traditionally considered for secure multiparty computation, depending on whether or not a majority of the parties are assumed to be honest. Existing protocols that assume an honest majority provide “full security” (and, in particular, guarantee output delivery and fairness) when this assumption holds, but are completely insecure if this assumption is violated. On the other hand, known protocols tolerating an arbitrary number of corruptions do not guarantee fairness or output delivery even if only a single party is dishonest. It is natural to wonder whether it is possible to achieve the “best of both worlds”: namely, a single protocol that simultaneously achieves the best possible security in both the above settings. Here, we rule out this possibility (at least for general functionalities) and show some positive results regarding what can be achieved.

SIAM Journal on Computing•Jan 1, 2011•32 citations

On secure multiparty sampling for more than two parties

Manoj Prabhakaran, Vinod M. Prabhakaran

We investigate secure multi-party sampling problems involving more than two parties. In the public discussion model, we give a simple characterization of the distributions that can be sampled without any setup. In a model which allows private point-to-point communication, we reduce the problem of characterizing distributions that can be securely sampled using pairwise setups to the problem of characterizing distributions that can be sampled without any setups.

IEEE Information Theory Workshop (ITW)•Sep 1, 2012•12 citations

On unconditionally secure multi-party sampling from scratch1

Ye Wang, Prakash Ishwar

In the problem of secure multi-party sampling, n parties wish to securely sample an n-variate joint distribution, with each party receiving a sample of one of the correlated variables. The objective is to correctly produce the samples using a distributed message passing protocol, while maintaining privacy against a coalition of passively cheating parties. In the two-party case, we fully characterize the joint distributions that can be securely sampled under perfect correctness and privacy requirements as well as under weakened correctness and privacy requirements. Furthermore, we show that the distributions that can be securely sampled can be produced with a protocol that only uses one round of unidirectional communication. For the n-party case, any distribution can be securely sampled with privacy against a strict minority coalition, due to well-known results in secure multi-party computation. However, when privacy against a majority coalition is required, not all distributions can be securely sampled. We give necessary conditions and sufficient conditions for distributions that can be securely sampled. However, the exact characterization of the distributions that can be securely sampled remains open.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2011•10 citations
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.
In the secure two-party sampling problem, two parties wish to generate outputs with a desired joint distribution via an interactive protocol, while ensuring that neither party learns more than what can be inferred from only their own output. For semi-honest parties and information-theoretic privacy guarantees, it is well-known that if only noiseless communication is available, then only the joint distributions, for which common information equals mutual information, can be securely sampled. We consider the problem where the parties may also interact via a given set of general communication primitives (multi-input/output channels). Our feasibility characterization of this problem can be stated as a zero-one law: primitives are either complete (enabling the secure sampling of any distribution) or useless (only enabling the secure sampling of trivial distributions). Our characterization of the complete primitives also extends to the more general class of secure two-party computation problems.
Abstract. There are protocols to privately evaluate any function in the passive (honest-but-curious) setting assuming that the honest nodes are in majority. For some specific functions, protocols are known which remain secure even without an honest majority. The seminal work by Chor and Kushilevitz [7] gave a complete characterization of Boolean functions, showing that each Boolean function either requires an honest majority, or is such that it can be privately evaluated regardless of the number of colluding nodes. The problem of discovering the threshold for secure evaluation of more general functions remains an open problem. Towards a resolution, we provide a complete characterization of the security threshold for functions with three different outputs. Surprisingly, the zero-one law for Boolean functions extends to Z3, meaning that each function with range Z3 either requires honest majority or tolerates up to n colluding nodes. 1
Most of this book has considered two-party and multiparty computation with security with (unfair) abort. This security notion allows the adversary to force the honest parties to abort even depending on the outputs of corrupted parties. (Note, however, that the adversary is not allowed to bias the output of honest parties in any other manner.) This relaxation of security is necessary if one wishes to tolerate arbitrarily many corruptions. A further relaxation considers computational security, where the adversary is assumed to be computationally bounded, e.g., probabilistic polynomial time. In this setting, any circuit can be securely realized even when arbitrarily many parties are corrupted, as long as one is willing to sacrifice fairness and robustness.
Two settings are traditionally considered for secure multiparty computation, depending on whether or not a majority of the parties are assumed to be honest. Existing protocols that assume an honest majority provide “full security” (and, in particular, guarantee output delivery and fairness) when this assumption holds, but are completely insecure if this assumption is violated. On the other hand, known protocols tolerating an arbitrary number of corruptions do not guarantee fairness or output delivery even if only a single party is dishonest. It is natural to wonder whether it is possible to achieve the “best of both worlds”: namely, a single protocol that simultaneously achieves the best possible security in both the above settings. Here, we rule out this possibility (at least for general functionalities) and show some positive results regarding what can be achieved.
In the problem of secure multi-party sampling, n parties wish to securely sample an n-variate joint distribution, with each party receiving a sample of one of the correlated variables. The objective is to correctly produce the samples using a distributed message passing protocol, while maintaining privacy against a coalition of passively cheating parties. In the two-party case, we fully characterize the joint distributions that can be securely sampled under perfect correctness and privacy requirements as well as under weakened correctness and privacy requirements. Furthermore, we show that the distributions that can be securely sampled can be produced with a protocol that only uses one round of unidirectional communication. For the n-party case, any distribution can be securely sampled with privacy against a strict minority coalition, due to well-known results in secure multi-party computation. However, when privacy against a majority coalition is required, not all distributions can be securely sampled. We give necessary conditions and sufficient conditions for distributions that can be securely sampled. However, the exact characterization of the distributions that can be securely sampled remains open.