View all Seminars  |  Download ICal for this event

On Perfectly Secure Two-Party Computation for Symmetric Functionalities with Correlated Randomness

Series: IISc-CRYPTO Seminars

Speaker: Bar Alon Ph.D. student Ariel University

Date/Time: Nov 24 17:00:00

Location: Microsoft Teams - ON-LINE

Faculty Advisor:

A multiparty computation protocol is perfectly secure for some function f if it perfectly emulates an ideal computation of f. Thus, perfect security is the strongest and most desirable notion of security, as it guarantees security in the face of any adversary and eliminates the dependency on any security parameter. Ben-Or et al. [STOC 88] and Chaum et al. [STOC 88] showed that any function can be computed with perfect security if strictly less than one-third of the parties can be corrupted. For two-party sender-receiver functionalities (where only one party receives an output), Ishai et al. [TCC 13] showed that any function can be computed with perfect security in the correlated randomness model. Unfortunately, they also showed that perfect security cannot be achieved in general for two-party functions that give outputs to both parties (even in the correlated randomness model). We study the feasibility of obtaining perfect security for deterministic symmetric two-party functionalities (i.e., where both parties obtain the same output) in the face of malicious adversaries. We explore both the plain model as well as the correlated randomness model. We provide positive results in the plain model, and negative results in the correlated randomness model. As a corollary, we obtain the following results. - We provide a characterization of symmetric functionalities with (up to) four possible outputs that can be computed with perfect security. The characterization is further refined when restricted to three possible outputs and to Boolean functions. All characterizations are the same for both the plain model and the correlated randomness model. -We show that if a functionality contains an embedded XOR or an embedded AND, then it cannot be computed with perfect security (even in the correlated randomness model).

Speaker Bio:
Bar Alon is a Ph.D. student at Ariel University and I work under the supervision of Dr. Eran Omri. Microsoft teams link:

Host Faculty: Prof. Arpita Patra