Search Results

Achieving malicious security with high efficiency in dishonest-majority secure multiparty computation is a formidable challenge. The milestone works SPDZ and TinyOT have spawn a large family of protocols in this direction. For boolean circuits, state-of-...

We consider two natural variants of the problem of minimum spanning tree (MST) of a graph in the parallel setting: MST verification (verifying if a given tree is an MST) and the sensitivity analysis of an MST (finding the lowest cost replacement edge for ...

Multiparty garbling is the most popular approach for constant-round secure multiparty computation (MPC). Despite being the focus of significant research effort, instantiating prior approaches to multiparty garbling results in constant-round MPC that can ...

In MPC, we usually represent programs as circuits. This is a poor fit for programs that use complex control flow, as it is costly to compile control flow to circuits. This motivated prior work to emulate CPUs inside MPC. Emulated CPUs can run complex ...

We present a deterministic algorithm for solving a wide range of dynamic programming problems in trees in O(log D) rounds in the massively parallel computation model (MPC), with O(nδ) words of local memory per machine, for any given constant 0 < δ < 1. ...

We consider the classic k-center problem in a parallel setting, on the low-local-space Massively Parallel Computation (MPC) model, with local space per machine of O (nδ), where δ ∈ (0,1) is an arbitrary constant. As a central clustering problem, the k-...

The growing volumes of data collected and its analysis to provide better services create worries about digital privacy. The literature has relied on secure multiparty computation techniques to address privacy concerns and give practical solutions. ...

We study the private k-median and k-means clustering problem in d dimensional Euclidean space. By leveraging tree embeddings, we give an efficient and easy to implement algorithm, that is empirically competitive with state of the art non private methods. ...

This paper presents an O(log log đ) round massively parallel algorithm for 1 + ε approximation of maximum weighted b-matchings, using near-linear memory per machine. Here đ denotes the average degree in the graph and ε is an arbitrarily small positive ...

The Transport Layer Security (TLS) protocol is a fundamental building block for ensuring security on Internet. It provides an easy to use framework for the purposes of establishing an authenticated and secure channel between two parties that have never ...

We study distributed algorithms for string matching problem in presence of wildcard characters. Given a string T (a text), we look for all occurrences of another string P (a pattern) as a substring of string T. Each wildcard character in the pattern ...

LowMC is a parameterizable block cipher developed for use in Multi-Party Computation (MPC) and Fully Homomorphic Encryption (FHE). In these applications, linear operations are much less expensive in terms of resource utilization compared to the non-...

With the rapid development of technology, user privacy and data security are drawing much attention over the recent years. On one hand, how to protect user privacy while making use of customers? data is a challenging task. On the other hand, data silos ...

With the rapid development of technology, data is becoming ubiquitous. User privacy and data security are drawing much attention over the recent years, especially with the European Union's General Data Protection Regulation (GDPR) and other laws coming ...

We design a generic method to reduce the task of finding weighted matchings to that of finding short augmenting paths in unweighted graphs. This method enables us to provide efficient implementations for approximating weighted matchings in the massively ...

While secure multi-party computation (MPC) is a vibrant research topic and a multitude of practical MPC applications have been presented recently, their development is still a tedious task that requires expert knowledge. Previous works have made first ...

Protocols for secure multiparty computation enable a set of parties to compute a function of their inputs without revealing anything but the output. The security properties of the protocol must be preserved in the presence of adversarial behavior. The ...

Practical hardness results are necessary to select parameters for cryptographic schemes. Cryptographic challenges proved to be useful for determining the practical hardness of computational problems that are used to build public-key cryptography. ...

Multiparty computation (MPC) protocols among n parties secure against t active faults are known to exist if and only if

• t < n/2, when the channels are synchronous, and
• t < n/3, when the channels are asynchronous, respectively.

In this work we analyze ...