Privacy-Preserving Fully Online Matching with Deadlines
Pages 105 - 116
Abstract
In classical secure multi-party computation (SMPC) it is assumed that a fixed and a priori known set of parties wants to securely evaluate a function of their private inputs. This assumption implies that online problems, in which the set of parties that arrive and leave over time are not a priori known, are not covered by the classical setting. Therefore, the notion of online SMPC has been introduced, and a general feasibility result has been proven that shows that any online algorithm can be implemented as a distributed protocol that is secure in this setting [22, 23]. However, so far, no online SMPC protocol that implements a concrete online algorithm has been proposed and evaluated such that the practicality of the constructive proof is an open question.
We close this gap and propose the first privacy-preserving online SMPC protocol for the prominent problem of fully online matching with deadlines. In this problem an (a priori unknown) set of parties with their inputs arrive over time and can then be matched with other parties until they leave when their individual deadline is reached. We prove that our protocol is statistically secure in the presence of a semi-honest adversary that controls strictly less than half of the parties present at each point in time. We extensively evaluate the performance of our protocol in three different network settings, various input sizes and different matching conditions, as well as various numbers of parties.
References
[1]
Susanne Albers. 2003. Online algorithms: a survey. Mathematical Programming, Vol. 97 (2003), 3--26.
[2]
Balamurugan Anandan and Chris Clifton. 2017. Secure minimum weighted bipartite matching. In Conference on Dependable and Secure Computing. 60--67.
[3]
Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. 1988. Completeness Theorems For Non-Cryptographic Fault-Tolerant Distributed Computation. In Symposium on Theory of Computing. ACM, 1--10.
[4]
Marina Blanton and Siddharth Saraph. 2015. Oblivious Maximum Bipartite Matching Size Algorithm with Applications to Secure Fingerprint Identification. In Computer Security -- ESORICS 2015 (Lecture Notes in Computer Science ). Springer International Publishing, 384--406.
[5]
Malte Breuer, Ulrike Meyer, and Susanne Wetzel. 2022. Privacy-Preserving Maximum Matching on General Graphs and its Application to Enable Privacy-Preserving Kidney Exchange. In Proceedings of the 12th ACM Conference on Data and Application Security and Privacy (CODASPY '22). Association for Computing Machinery, 53--64.
[6]
Ran Canetti. 2000. Security and Composition of Multiparty Cryptographic Protocols. Journal of Cryptology, Vol. 13 (2000), 143--202.
[7]
Ran Canetti. 2001. Universally Composable Security: A New Paradigm for Cryptographic Protocols. In International Conference on Cluster Computing. 136--145.
[8]
Ran Canetti. 2020. Universally Composable Security. J. ACM, Vol. 67 (2020), 28:1--28:94.
[9]
Octavian Catrina and Sebastiaan de Hoogh. 2010. Improved Primitives for Secure Multiparty Integer Computation. In Security and Cryptography for Networks (Lecture Notes in Computer Science ). Springer, 182--199.
[10]
Arka Rai Choudhuri, Aarushi Goel, Matthew Green, Abhishek Jain, and Gabriel Kaptchuk. 2020. Fluid MPC: Secure Multiparty Computation with Dynamic Participants. Cryptology ePrint Archive, Report 2020/754.
[11]
Yvo Desmedt and Sushil Jajodia. 1994. Redistributing secret shares to new access structures and its applications. Technical Report ISSE TR-97-01. George Mason University.
[12]
Amos Fiat and Gerhard Woeginger (Eds.). 1998. Online Algorithms: The State of the Art. Springer.
[13]
Buddhima Gamlath, Michael Kapralov, Andreas Maggiori, Ola Svensson, and David Wajc. 2019. Online Matching with General Arrivals. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). 26--37.
[14]
Oded Goldreich. 2004. Foundations of Cryptography: Basic Applications. Cambridge University Press.
[15]
Oded Goldreich, Silvio Micali, and Avi Wigderson. 1987. How to play ANY mental game. In Symposium on Theory of Computing. ACM, 218--229.
[16]
Philippe Golle. 2006. A Private Stable Matching Algorithm. In International Conference on Financial Cryptography and Data Security. Springer, 65--80.
[17]
James Heather and David Lundin. 2009. The Append-Only Web Bulletin Board. In Formal Aspects in Security and Trust. Springer, 242--256.
[18]
Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang, and Xue Zhu. 2018. How to match when all vertices arrive online. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018). Association for Computing Machinery, 17--29.
[19]
Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang, and Xue Zhu. 2020. Fully Online Matching. J. ACM, Vol. 67 (2020), 17:1--17:25.
[20]
R. M. Karp, U. V. Vazirani, and V. V. Vazirani. 1990. An Optimal Algorithm for On-line Bipartite Matching. In Symposium on Theory of Computing (STOC '90). ACM, 352--358.
[21]
Marcel Keller. 2020. MP-SPDZ: A Versatile Framework for Multi-Party Computation. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security (CCS '20). Association for Computing Machinery, 1575--1590.
[22]
Andreas Klinger and Ulrike Meyer. 2021. Towards Secure Evaluation of Online Functionalities. In The 16th International Conference on Availability, Reliability and Security (ARES 2021). Association for Computing Machinery.
[23]
Andreas Klinger and Ulrike Meyer. 2022. Towards Secure Evaluation of Online Functionalities (Corrected and Extended Version). Cryptology ePrint Archive, Paper 2022/1755.
[24]
Ming Li, Ning Cao, Shucheng Yu, and Wenjing Lou. 2011. FindU: Privacy-preserving personal profile matching in mobile social networks. In International Conference on Computer Communications. 2435--2443.
[25]
Adi Shamir. 19799. How to Share a Secret. Commun. ACM, Vol. 22 (19799), 612--613.
[26]
Tomas Toft. 2009. Solving Linear Programs Using Multiparty Computation. In Financial Cryptography and Data Security (Lecture Notes in Computer Science ). Springer, 90--107.
[27]
Stefan Wüller, Michael Vu, Ulrike Meyer, and Susanne Wetzel. 2017. Using Secure Graph Algorithms for the Privacy-Preserving Identification of Optimal Bartering Opportunities. In Workshop on Privacy in the Electronic Society. ACM, 123--132.
[28]
Andrew C. C. Yao. 1986. How to generate and exchange secrets. In Symposium on Foundations of Computer Science. 162--167. io
Index Terms
- Privacy-Preserving Fully Online Matching with Deadlines
Recommendations
Anonymous System for Fully Distributed and Robust Secure Multi-Party Computation
CODASPY '23: Proceedings of the Thirteenth ACM Conference on Data and Application Security and PrivacyIn secure multi-party computation (SMPC), it is considered that multiple parties that are known to each other evaluate a function over their private inputs in a secure fashion. The participating parties do not learn anything about each other's private ...
Towards Secure Evaluation of Online Functionalities
ARES '21: Proceedings of the 16th International Conference on Availability, Reliability and SecurityTo date, ideal functionalities securely realized with secure multi-party computation (SMPC) mainly considers functions of the private input of a fixed number of a priori known parties. In this paper, we generalize these definitions such that protocols ...
Estimating the Runtime and Global Network Traffic of SMPC Protocols
CODASPY '24: Proceedings of the Fourteenth ACM Conference on Data and Application Security and PrivacySecure multi-party computation (SMPC) enables multiple parties to evaluate functions of their private inputs, in a way such that none of the parties can learn anything about the other parties' private input but what can be learned from their own input ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
April 2023
304 pages
ISBN:9798400700675
DOI:10.1145/3577923
- General Chair:
- Mohamed Shehab,
- Program Chairs:
- Maribel Fernandez,
- Ninghui Li
Copyright © 2023 ACM.
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 the author(s) 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: 24 April 2023
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Conference
CODASPY '23
Sponsor:
CODASPY '23: Thirteenth ACM Conference on Data and Application Security and Privacy
April 24 - 26, 2023
NC, Charlotte, USA
Acceptance Rates
Overall Acceptance Rate 149 of 789 submissions, 19%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 117Total Downloads
- Downloads (Last 12 months)41
- Downloads (Last 6 weeks)0
Reflects downloads up to 14 Dec 2024
Other Metrics
Citations
Cited By
View allView Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in