Results 1501 - 1510 of 23856

In Crypto'19, Goyal, Jain, and Sahai introduced the elegant notion of *secret-sharing of an NP statement* (NPSS). Roughly speaking, a t-out-of-n secret sharing of an NP statement is a reduction that maps a circuit-SAT instance f into n circuit-SAT instances (f_1, ..., f_n) over a common set of variables, such that: (1) Given a satisfying assignment x for f, it is possible to sample partial assignments (y_1,...,y_n) that consistently satisfy (f_1,...,f_n), and where the marginal distribution of every collection of t-1 partial assignments leaks no information about the witness x; (2) Conversely, any collection of t partial assignments that consistently satisfy t of the instances can be efficiently translated into an assignment x that satisfies f.

We present the first information-theoretic construction of NPSS for arbitrary values of t and n. Previously, it was only known how to achieve computational privacy for the special case of t=n. Our constructions rely on a new notion of secure multiparty computation protocols that may be of independent interest. We use our NPSS to obtain several applications in the domain of zero-knowledge proofs and secure-multiparty computation. If time permits, we will also discuss a related construction of leakage-resilient NPSS that gives rise to NIZK amplifiers resolving open questions of Goyal, Jain, and Sahai (Crypto'19) and Bitansky and Geier (Crypto'24).

Based on joint works with Eliran Kachlon.

A new round collapsing technique for achieving constant around MPC while preserving the communication efficiency. Based on the following work: https://eprint.iacr.org/2025/508

Many works aiming to optimize round complexity assume that broadcast comes "for free." In practice, however, broadcast must be implemented either through a bulletin board or via protocols over point-to-point channels—both of which incur significant costs. This raises a natural question: what guarantees can still be achieved if the broadcast rounds in round-optimal protocols are replaced with point-to-point communication? This question has been thoroughly investigated in the computational setting, both in the dishonest majority case with setup ([CGZ20], EUROCRYPT'20) and without setup ([CDRSXY23], TCC'23), as well as in the honest majority setting with setup ([DMRSY21], CRYPTO'21; [DRSY23], EUROCRYPT'23). More recently, this question was investigated in the context of round-optimal information-theoretic MPC ([CDRSY], currently under submission). This talk will survey the current state-of-the-art in this area and present key upper and lower bound techniques developed so far.

An important requirement in synchronous protocols is that, even when a party receives all its messages for a given round ahead of time, it must wait until the round officially concludes before sending its messages for the next round. In practice, however, implementations often overlook this waiting requirement. This leads to a mismatch between the security analysis and real-world deployments, giving adversaries a new, unaccounted-for capability: the ability to "peek into the future." Specifically, an adversary can force certain honest parties to advance to round r+1, observe their round r+1 messages, and then use this information to determine its remaining round r messages. We refer to adversaries with this capability as "super-rushing" adversaries.

We initiate a study of secure computation in the presence of super-rushing adversaries. We focus on understanding the conditions under which existing synchronous protocols remain secure in the presence of super-rushing adversaries. We show that not all protocols remain secure in this model, highlighting a critical gap between theoretical security guarantees and practical implementations. Even worse, we show that security against super-rushing adversaries is not necessarily maintained under sequential composition.

Despite those limitations, we present a general positive result: secret-sharing based protocols in the perfect setting, such as BGW, or those that are based on multiplication triplets, remain secure against super-rushing adversaries. This general theorem effectively enhances the security of such protocols "for free." It shows that these protocols do not require parties to wait for the end of a round, enabling potential optimizations and faster executions without compromising security. Moreover, it shows that there is no need to spend efforts to achieve perfect synchronization when establishing the communication networks for such protocols.

This ia a joint work with Gilad Asharov, Anirudh Chandramouli, and Yuval Ishai.

The talk provides an overview of the optimal round complexity of secure multi-party computation with unanimous abort security in the plain model in settings where the adversary may corrupt a majority of the parties. The focus will be on outlining the main challenges and key techniques involved in constructing such protocols using cryptographic primitives in a black-box way.

Secure Multi-party Computation (MPC) is the standard-bearer and holy-grail problem in Cryptography that permits a collection of data-owners to compute a collaborative result, without any of them gaining any knowledge about the data provided by the other, except what is derivable from the result of the computation. Communication complexity is one of the most prominent complexity measures of MPC with information-theoretic security. In this talk, I will draw a high-level picture of how the communication complexity study progressed over the years and my contributions to this area.