Team for Research in
Ubiquitous Secure Technology

Citation
"• Secure function evaluation with ordered binary decision diagrams". L. Kruger, S. Jha, E. Goh, and D. Boneh (eds.), ACM Conference on Computer and Communications Security, 2006.

Abstract
Privacy-preserving protocols allow multiple parties with private inputs to perform joint computation while preserving the privacy of their respective inputs. An important cryptographic primitive for designing privacy-preserving protocols is secure function evaluation (SFE). The classic solution for SFE by Yao uses a gate representation of the function that the two parties want to jointly compute. Fairplay is a system that implements the classic solution for SFE. In this paper, we present a protocol for SFE that uses a graph-based representation of the function. Specifically we use the graph-based representation called ordered binary decision diagrams (OBDDs). For a large number of Boolean functions, OBDDs are more succinct than the gate-based representation. Preliminary experimental results based on a prototype implementation shows that for several functions, our protocol results in a smaller bandwidth than Fairplay. For example, for the classic millionaire's problem, our new protocol results in a approximately 45% bandwidth reduction over Fairplay. Therefore, our protocols will be particularly useful for applications for environments with limited bandwidth.

Electronic downloads

• HTML

   <a
  href="http://www.truststc.org/pubs/596.html"
  ><i>•	Secure function evaluation with
  ordered binary decision diagrams</i></a>, L.
  Kruger, S. Jha, E. Goh, and D. Boneh (eds.), ACM Conference
  on Computer and Communications Security, 2006.

• Plain text

   "•	Secure function evaluation with
  ordered binary decision diagrams". L. Kruger, S. Jha,
  E. Goh, and D. Boneh (eds.), ACM Conference on Computer and
  Communications Security, 2006.

• BibTeX

  @proceedings{KrugerJhaGohBoneh06_SecureFunctionEvaluationWithOrderedBinaryDecision,
      title = {•	Secure function evaluation with ordered binary
                decision diagrams},
      editor = {L. Kruger, S. Jha, E. Goh, and D. Boneh},
      organization = {ACM Conference on Computer and Communications
                Security},
      year = {2006},
      abstract = {Privacy-preserving protocols allow multiple
                parties with private inputs to perform joint
                computation while preserving the privacy of their
                respective inputs. An important cryptographic
                primitive for designing privacy-preserving
                protocols is secure function evaluation (SFE). The
                classic solution for SFE by Yao uses a gate
                representation of the function that the two
                parties want to jointly compute. Fairplay is a
                system that implements the classic solution for
                SFE. In this paper, we present a protocol for SFE
                that uses a graph-based representation of the
                function. Specifically we use the graph-based
                representation called ordered binary decision
                diagrams (OBDDs). For a large number of Boolean
                functions, OBDDs are more succinct than the
                gate-based representation. Preliminary
                experimental results based on a prototype
                implementation shows that for several functions,
                our protocol results in a smaller bandwidth than
                Fairplay. For example, for the classic
                millionaire's problem, our new protocol results in
                a approximately 45% bandwidth reduction over
                Fairplay. Therefore, our protocols will be
                particularly useful for applications for
                environments with limited bandwidth. },
      URL = {http://www.truststc.org/pubs/596.html}
  }
  

Posted by Jessica Gamble on 16 Mar 2009.
For additional information, see the Publications FAQ or contact webmaster at www truststc org.