SCIENCE@home

Communication Complexity and Secure Function Evaluation

M. Naor,Kobbi Nissim

Published 2001 in Electron. Colloquium Comput. Complex.

ABSTRACT

We suggest two new methodologies for the design of efficient secure protocols, that differ with respect to their underlying computational models. In one methodology we utilize the communication complexity tree (or branching for f and transform it into a secure protocol. In other words, "any function f that can be computed using communication complexity c can be can be computed securely using communication complexity that is polynomial in c and a security parameter". The second methodology uses the circuit computing f, enhanced with look-up tables as its underlying computational model. It is possible to simulate any RAM machine in this model with polylogarithmic blowup. Hence it is possible to start with a computation of f on a RAM machine and transform it into a secure protocol. We show many applications of these new methodologies resulting in protocols efficient either in communication or in computation. In particular, we exemplify a protocol for the "millionaires problem", where two participants want to compare their values but reveal no other information. Our protocol is more efficient than previously known ones in either communication or computation.

PUBLICATION RECORD

  • Publication year

    2001

  • Venue

    Electron. Colloquium Comput. Complex.

  • Publication date

    2001-09-01

  • Fields of study

    Mathematics, Computer Science

  • Identifiers
    arXiv cs/0109011
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-45 of 45 references · Page 1 of 1

CITED BY

Showing 1-36 of 36 citing papers · Page 1 of 1