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 new 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, such as applications for wireless and sensor networks.
- Gagan Aggarwal, Nina Mishra, and Benny Pinkas. Secure computation of the k-th ranked element. In Christian Cachin and Jan Camenisch, editors, Proceedings of Eurocrypt 2004, volume 3027 of LNCS, pages 40--55. Springer-Verlag, May 2004.Google Scholar
- Beate Bollig and Ingo Wegener. Improving the variable ordering of OBDDs is NP-complete. IEEE Transactions on Computers, 45(9), September 1996. Google ScholarDigital Library
- Randal E. Bryant. Graph-based algorithms for boolean function manipulation. IEEE Transactions on Computers, 35(8):677--691, 1986. Google ScholarDigital Library
- Randal E. Bryant and Yirng-An Chen. Verification of arithmetic circuits with binary moment diagrams. In Proceedings of the 32nd Conference on Design Automation (DAC), 1995. Google ScholarDigital Library
- Buddy. http://sourceforge.net/projects/buddy.Google Scholar
- A. Campailla, S. Chaki, E. M. Clarke, S. Jha, and H. Veith. Efficient filtering in publish-subscribe systems using binary decision diagrams. In Proceedings of the 23rd International Conference on Software Engineering (ICSE), 2001. Google ScholarDigital Library
- E.M. Clarke, O. Grumberg, and D.A. Peled. Model Checking. The MIT Press, 2000.Google ScholarDigital Library
- E.M. Clarke, M. Khaira, and X. Zhao. Hybrid decision diagrams: Overcoming the limitations of MTBDDs and BMDs. In Proceedings of the International Conference on Computer-Aided Design (ICCAD), 1995. Google ScholarDigital Library
- Lorrie Cranor, Marc Langheinrich, Massimo Marchiori, Martin Presler-Marshall, and Joseph Reagle. The Platform for Privacy Preferences 1.0 (P3P1.0) Specification. W3C Recommendation, 16 April 2002.Google Scholar
- Lorrie Faith Cranor. Internet privacy. Communications of the ACM, 42(2):28--38, 1999. Google ScholarDigital Library
- J. Feigenbaum, B. Pinkas, R. Ryger, and F. Saint-Jean. Secure computation of surveys. In 2004 EU Workshop on Secure Multiparty Protocols (SMP), 2004.Google Scholar
- Michael Freedman, Kobbi Nissim, and Benny Pinkas. Efficient private matching and set intersection. In Christian Cachin and Jan Camenisch, editors, Proceedings of Eurocrypt 2004, volume 3027 of LNCS, pages 1--19. Springer-Verlag, May 2004.Google Scholar
- Ian Goldberg, David Wagner, and Eric Brewer. Privacy-enhancing technologies for the internet. In Proc. of 42nd IEEE Spring COMPCON. IEEE Computer Society Press, February 1997. Google ScholarDigital Library
- O. Goldreich. The Foundations of Cryptography --- Volume 2. Cambridge University Press, 2004. Google ScholarDigital Library
- O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game -- a completeness theorem for protocols with honest majority. In 19th STOC, pages 218--229, 1987. Google ScholarDigital Library
- Javabdd - java binary decision diagram library. http://javabdd.sourceforge.net/.Google Scholar
- R. M. Jensen and M. M. Veloso. Obdd-based universal planning for multiple synchronized agents in non-deterministic domains. In Proceedings of the Fifth International Conference on Artificial Intelligence Planning Systems (AIPS), 2000.Google ScholarDigital Library
- Y. Lindell and B. Pinkas. Privacy preserving data mining. Journal of Cryptology, 15(3), 2002.Google ScholarDigital Library
- Yehuda Lindell and Benny Pinkas. A proof of Yao's protocol for secure two-party computation. Cryptology ePrint Archive, Report 2004/175, 2004. http://eprint.iacr.org/2004/175.Google Scholar
- B. Pinkas M. Naor and R. Sumner. Privacy preserving auctions and mechanism design. In Proceedings of the 1st ACM conf. on Electronic Commerce, 1999. Google ScholarDigital Library
- Philip D. MacKenzie, Alina Oprea, and Michael K. Reiter. Automatic generation of two-party computations. In Proceedings of ACM Conference on Computer and Communications Security, 2003. Google ScholarDigital Library
- D. Malkhi, N. Nisan, B. Pinkas, and Y. Sella. Fairplay --- a secure two-party computation system. In Proceedings of the 13th Usenix Security Symposium, San Diego, CA, USA, August 2004. Google ScholarDigital Library
- Moni Naor and Benny Pinkas. Efficient oblivious transfer protocols. In Proceedings of the Twelfth Annual Symposium on Discrete Algorithms (SODA), pages 448--457, 2001. Google ScholarDigital Library
- D. M. Rind, I. S. Kohane, P. Szolovits, C. Safran, H. C. Chueh, and G. O. Barnett. Maintaining the confidentiality of medical records shared over the internet and the world wide web. Annals of Internal Medicine, 127(2), July 1997.Google ScholarCross Ref
- Joseph Turow. Americans and online privacy: The system is broken. Technical report, Annenberg Public Policy Center, June 2003.Google Scholar
- J. Whaley and M. S. Lam. Cloning-based context-sensitive pointer alias analysis using binary decision diagrams. In Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation (PLDI), 2004. Google ScholarDigital Library
- A.C. Yao. How to generate and exchange secrets. In Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, 1986.Google ScholarDigital Library
Index Terms
- Secure function evaluation with ordered binary decision diagrams
Recommendations
Secure and Private Function Evaluation with Intel SGX
CCSW'19: Proceedings of the 2019 ACM SIGSAC Conference on Cloud Computing Security WorkshopSecure function evaluation (SFE) allows two parties to jointly evaluate a publicly known function without revealing their respective inputs. SFE can be realized via well-known cryptographic protocols, such as Yao's garbled circuits (GC) and the protocol ...
Computationally Secure Oblivious Transfer
We describe new computationally secure protocols of 1-out-of-N oblivious transfer, k-out-of-N oblivious transfer, and oblivious transfer with adaptive queries. The protocols are very efficient compared with solutions based on generic two-party ...
Secure Computation of the Median (and Other Elements of Specified Ranks)
We consider the problem of securely computing the kth-ranked element of the union of two or more large, confidential data sets. This is a fundamental question motivated by many practical contexts. For example, two competitive companies may wish to ...
Comments