[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/1180405.1180455acmconferencesArticle/Chapter ViewAbstractPublication PagesccsConference Proceedingsconference-collections
Article

Secure function evaluation with ordered binary decision diagrams

Published: 30 October 2006 Publication History

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.

References

[1]
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.
[2]
Beate Bollig and Ingo Wegener. Improving the variable ordering of OBDDs is NP-complete. IEEE Transactions on Computers, 45(9), September 1996.
[3]
Randal E. Bryant. Graph-based algorithms for boolean function manipulation. IEEE Transactions on Computers, 35(8):677--691, 1986.
[4]
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.
[5]
Buddy. http://sourceforge.net/projects/buddy.
[6]
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.
[7]
E.M. Clarke, O. Grumberg, and D.A. Peled. Model Checking. The MIT Press, 2000.
[8]
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.
[9]
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.
[10]
Lorrie Faith Cranor. Internet privacy. Communications of the ACM, 42(2):28--38, 1999.
[11]
J. Feigenbaum, B. Pinkas, R. Ryger, and F. Saint-Jean. Secure computation of surveys. In 2004 EU Workshop on Secure Multiparty Protocols (SMP), 2004.
[12]
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.
[13]
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.
[14]
O. Goldreich. The Foundations of Cryptography --- Volume 2. Cambridge University Press, 2004.
[15]
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.
[16]
Javabdd - java binary decision diagram library. http://javabdd.sourceforge.net/.
[17]
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.
[18]
Y. Lindell and B. Pinkas. Privacy preserving data mining. Journal of Cryptology, 15(3), 2002.
[19]
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.
[20]
B. Pinkas M. Naor and R. Sumner. Privacy preserving auctions and mechanism design. In Proceedings of the 1st ACM conf. on Electronic Commerce, 1999.
[21]
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.
[22]
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.
[23]
Moni Naor and Benny Pinkas. Efficient oblivious transfer protocols. In Proceedings of the Twelfth Annual Symposium on Discrete Algorithms (SODA), pages 448--457, 2001.
[24]
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.
[25]
Joseph Turow. Americans and online privacy: The system is broken. Technical report, Annenberg Public Policy Center, June 2003.
[26]
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.
[27]
A.C. Yao. How to generate and exchange secrets. In Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, 1986.

Cited By

View all
  • (2021)Lattice based access control for protecting user data in cloud environments with hybrid securityComputers and Security10.1016/j.cose.2020.102074100:COnline publication date: 1-Jan-2021
  • (2020)Practical Data-in-Use Protection Using Binary Decision DiagramsIEEE Access10.1109/ACCESS.2020.29701208(23847-23862)Online publication date: 2020
  • (2019)A Hybrid Approach to Secure Function Evaluation using SGXProceedings of the 2019 ACM Asia Conference on Computer and Communications Security10.1145/3321705.3329835(100-113)Online publication date: 2-Jul-2019
  • Show More Cited By

Index Terms

  1. Secure function evaluation with ordered binary decision diagrams

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    CCS '06: Proceedings of the 13th ACM conference on Computer and communications security
    October 2006
    434 pages
    ISBN:1595935185
    DOI:10.1145/1180405
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 30 October 2006

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. binary decision diagrams
    2. secure function evaluation

    Qualifiers

    • Article

    Conference

    CCS06
    Sponsor:
    CCS06: 13th ACM Conference on Computer and Communications Security 2006
    October 30 - November 3, 2006
    Virginia, Alexandria, USA

    Acceptance Rates

    Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

    Upcoming Conference

    CCS '25

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)7
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 25 Dec 2024

    Other Metrics

    Citations

    Cited By

    View all
    • (2021)Lattice based access control for protecting user data in cloud environments with hybrid securityComputers and Security10.1016/j.cose.2020.102074100:COnline publication date: 1-Jan-2021
    • (2020)Practical Data-in-Use Protection Using Binary Decision DiagramsIEEE Access10.1109/ACCESS.2020.29701208(23847-23862)Online publication date: 2020
    • (2019)A Hybrid Approach to Secure Function Evaluation using SGXProceedings of the 2019 ACM Asia Conference on Computer and Communications Security10.1145/3321705.3329835(100-113)Online publication date: 2-Jul-2019
    • (2018)Privacy-Preserving Secure Multiparty Computation on Electronic Medical Records for Star Exchange TopologyArabian Journal for Science and Engineering10.1007/s13369-018-3122-543:12(7747-7756)Online publication date: 12-Mar-2018
    • (2016)Secure outsourced garbled circuit evaluation for mobile devicesJournal of Computer Security10.3233/JCS-15054024:2(137-180)Online publication date: 19-Apr-2016
    • (2015)Three-Party ORAM for Secure ComputationProceedings, Part I, of the 21st International Conference on Advances in Cryptology -- ASIACRYPT 2015 - Volume 945210.1007/978-3-662-48797-6_16(360-385)Online publication date: 29-Nov-2015
    • (2014)WhitewashProceedings of the 30th Annual Computer Security Applications Conference10.1145/2664243.2664255(266-275)Online publication date: 8-Dec-2014
    • (2014)Reuse It Or Lose ItProceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security10.1145/2660267.2660285(582-596)Online publication date: 3-Nov-2014
    • (2014)For your phone onlySecurity and Communication Networks10.1002/sec.8517:7(1165-1176)Online publication date: 1-Jul-2014
    • (2013)Challenges and opportunities of Mobile Cloud Computing2013 9th International Wireless Communications and Mobile Computing Conference (IWCMC)10.1109/IWCMC.2013.6583636(660-666)Online publication date: Jul-2013
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media