Secure function evaluation with ordered binary decision diagrams
Authors: L. Kruger, S. Jha, E. Goh, and D. Boneh
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.
Reference:
In proceedings of the ACM Conference on Computer and Communications
Security (CCS) 2006, pp. 410-420