NDLI: Secure Multiparty Computation with General Interaction Patterns

Please wait, while we are loading the content...

Can Almost Everybody be Almost Happy?

Permanent v. Determinant: An Exponential Lower Bound Assuming Symmetry

Local Algorithms for Block Models with Side Information

Strategic Classification

Obfuscating Conjunctions under Entropic Ring LWE

Timeability of Extensive-Form Games

Rational Proofs with Multiple Provers

Coordination Complexity: Small Information Coordinating Large Populations

Spectral Embedding of k-Cliques, Graph Partitioning and k-Means

How To Bootstrap Anonymous Communication

Information Complexity Density and Simulation of Protocols

Mechanisms With Costly Knowledge

On Hardness of Approximating the Parameterized Clique Problem

Distribution Design

A PAC Approach to Application-Specific Algorithm Selection

Secure Multiparty Computation with General Interaction Patterns

Auction Revenue in the General Spiteful-Utility Model

Lower Bounds: From Circuits to QBF Proof Systems

On a Natural Dynamics for Linear Programming

On Sketching Quadratic Forms

Time-Lock Puzzles from Randomized Encodings

Satisfiability on Mixed Instances

On the Computational Complexity of Optimal Simple Mechanisms

The Complexity of DNF of Parities

Sampling Correctors

An Axiomatic Approach to Community Detection

Fully Succinct Garbled RAM

How to Incentivize Data-Driven Collaboration Among Competing Parties

Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility

On the Space Complexity of Linear Programming with Preprocessing

Energy-Efficient Algorithms

Is There an Oblivious RAM Lower Bound?

On the Computational Complexity of Limit Cycles in Dynamical Systems

Smooth Boolean Functions are Easy: Efficient Algorithms for Low-Sensitivity Functions

On Being Far from Far and on Dual Problems in Property Testing: [Extended Abstract]

Cryptography for Parallel RAM from Indistinguishability Obfuscation

From Nash Equilibria to Chain Recurrent Sets: Solution Concepts and Topology

The Space "Just Above" BQP

Simultaneous Private Learning of Multiple Concepts

Weighted Gate Elimination: Boolean Dispersers for Quadratic Varieties Imply Improved Circuit Lower Bounds

Secure Multiparty Computation with General Interaction Patterns

Content Provider	ACM Digital Library
Author	Ishai, Yuval Kushilevitz, Eyal Rabin, Tal Halevi, Shai Jain, Abhishek
Abstract	We present a unified framework for studying secure multiparty computation (MPC) with arbitrarily restricted interaction patterns such as a chain, a star, a directed tree, or a directed graph. Our study generalizes both standard MPC and recent models for MPC with specific restricted interaction patterns, such as those studied by Halevi et al. (Crypto 2011), Goldwasser et al. (Eurocrypt 2014), and Beimel et al. (Crypto 2014). Since restricted interaction patterns cannot always yield full security for MPC, we start by formalizing the notion of "best possible security" for any interaction pattern. We then obtain the following main results: Completeness theorem. We prove that the star interaction pattern is complete for the problem of MPC with general interaction patterns. Positive results. We present both information-theoretic and computationally secure protocols for computing arbitrary functions with general interaction patterns. We also present more efficient protocols for computing symmetric functions, both in the computational and in the information-theoretic setting. Our computationally secure protocols for general functions necessarily rely on indistinguishability obfuscation while the ones for computing symmetric functions make simple use of multilinear maps. Negative results. We show that, in many cases, the complexity of our information-theoretic protocols is essentially the best that can be achieved. All of our protocols rely on a correlated randomness setup, which is necessary in our setting (for computing general functions). In the computational case, we also present a generic procedure to make any correlated randomness setup reusable, in the common random string model. Although most of our information-theoretic protocols have exponential complexity, they may be practical for functions on small domains (e.g., f0; 1g20), where they are concretely faster than their computational counterparts.
Starting Page	157
Ending Page	168
Page Count	12
File Format	PDF
ISBN	9781450340571
DOI	10.1145/2840728.2840760
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-01-14
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Obfuscation Secure multi party computation Interaction pattern
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Secure Multiparty Computation with General Interaction Patterns

Distribution Design

Adaptively secure multi-party computation with dishonest majority.

Quorum-based secure multi-party computation (1998)

Secure Multi-party Computations and Privacy Preservation: Results and Open Problems

A Domain-Specific Language for Low-Level Secure Multiparty Computation Protocols

A Secure Multiparty Computation Solution to Healthcare Frauds and Abuses

Two-Round Adaptively Secure MPC from

Behavioral Identification of Trusted Third Party in Secure Multiparty Computing Protocol

Secure Multiparty Computation with General Interaction Patterns

Similar Documents

Secure Multiparty Computation with General Interaction Patterns

Distribution Design

Adaptively secure multi-party computation with dishonest majority.

Quorum-based secure multi-party computation (1998)

Secure Multi-party Computations and Privacy Preservation: Results and Open Problems

A Domain-Specific Language for Low-Level Secure Multiparty Computation Protocols

A Secure Multiparty Computation Solution to Healthcare Frauds and Abuses

Two-Round Adaptively Secure MPC from

Behavioral Identification of Trusted Third Party in Secure Multiparty Computing Protocol

Secure Multiparty Computation with General Interaction Patterns