Secure Function Evaluation: Achieving Efficiency in Communication and Computation

Title: Secure Function Evaluation: Achieving Efficiency in Communication and Computation

Abstract: Secure function evaluation is a process that allows two parties, Alice and Bob, to jointly compute a function of their inputs without revealing more information than necessary. The main goal of this research is to create efficient protocols for secure function evaluation, either in communication or in computation. The study presents two new methodologies for designing efficient secure protocols: one based on the communication complexity tree representation of functions and the other using circuit computing enhanced with look-up tables. These methodologies result in protocols that are either communication-efficient or computation-efficient, depending on the specific requirements of the situation. The paper also provides examples of these protocols, including one for the "millionaires problem," where Alice and Bob want to compare their values without revealing any other information. This protocol is more efficient than previously known ones in either communication or computation.

Main Research Question: How can we design efficient protocols for secure function evaluation that balance the need for communication and computation resources?

Methodology: The study uses two main methodologies to achieve its goals:

1. Communication Complexity Tree Representation: This methodology starts with an efficient (insecure) protocol for a function and transforms it into a secure protocol. It utilizes the communication complexity tree (or branching program) representation of the function, which allows for efficient transformation of the protocol.

2. Circuit Computing with Look-up Tables: This methodology uses the circuit computing of a function enhanced with look-up tables as its underlying computational model. It is possible to simulate any RAM machine in this model with pol ylogarithmic blowup, which allows for the transformation of an insecure computation into a secure protocol.

Results: The research presents several applications of these new methodologies, resulting in protocols that are either communication-efficient or computation-efficient. The paper provides an example of a protocol for the "millionaires problem," which is more efficient than previously known ones in either communication or computation.

Implications: The development of efficient secure protocols has significant implications for the field of cryptography and computer science. These protocols can be applied to a wide range of tasks and problems, making them a valuable tool for protecting sensitive information and ensuring the privacy of individuals. Additionally, the research contributes to the ongoing efforts to balance the need for communication and computation resources in secure computing systems.

Link to Article: https://arxiv.org/abs/0109011v1 Authors: arXiv ID: 0109011v1