<sc>Prism</sc>: <underline>Pr</underline>ivacy-Preserving and Ver<underline>i</underline>fiable <underline>S</underline>et Computation Over <underline>M</underline>ulti-Owner Secret Shared Outsourced Databases
Authors: 
Shantanu Sharma, 
Yin Li, Sharad Mehrotra, Nisha Panwar, Peeyush Gupta, Dhrubajyoti GhoshAuthors Info & Claims
Pages 1355 - 1371
Abstract
Private set computation over multi-owner databases is an important problem with many applications — the most well studied of which is private set intersection (PSI). This article proposes <sc>Prism</sc>, a secret-sharing based approach to compute private set operations (i.e., intersection and union, as well as aggregates such as count, sum, average, maximum, minimum, and median) over outsourced databases belonging to multiple owners. <sc>Prism</sc> enables data owners to pre-load the data onto non-colluding servers and exploits the additive and multiplicative properties of secret-shares to compute the above-listed operations. <sc>Prism</sc> takes (at most) two rounds of communication between non-colluding servers (storing the secret-shares) and the querier for executing the above-mentioned operations, resulting in a very efficient implementation. <sc>Prism</sc> also supports result verification techniques for each operation to detect malicious adversaries. Experimental results show that <sc>Prism</sc> scales both in terms of the number of data owners and database sizes, to which prior approaches do not scale.
References
[1]
A. Abadi et al., “VD-PSI: Verifiable delegated private set intersection on outsourced private datasets,” in Proc. Int. Conf. Financial Cryptogr. Data Secur., 2016, pp. 149–168.
[2]
A. Abadi, S. Terzis, R. Metere, and C. Dong, “Efficient delegated private set intersection on outsourced private datasets,” IEEE Trans. Dependable Secure Comput., vol. 16, no. 4, pp. 608–624, Jul./Aug. 2019.
[3]
T. Araki et al., “High-throughput semi-honest secure three-party computation with an honest majority,” in Proc. ACM Asia Conf. Comput. Commun. Secur., 2016, pp. 805–817.
[4]
D. W. Archer et al., “From keys to databases - real-world applications of secure multi-party computation,” Comput. J., vol. 61, no. 12, pp. 1749–1771, 2018.
[5]
J. Bater et al., “SMCQL: Secure query processing for private data networks,” in Proc. VLDB Endowment, vol. 10, no. 6, pp. 673–684, 2017.
[6]
M. Blum et al., “How to generate cryptographically strong sequences of pseudo-random bits,” SIAM J. Comput., vol. 13, no. 4, pp. 850–864, 1984.
[7]
D. Bogdanov et al., “Sharemind: A framework for fast privacy-preserving computations,” in Proc. Eur. Symp. Res. Comput. Secur., 2008, pp. 192–206.
[8]
D. Bogdanov et al., “A practical analysis of oblivious sorting algorithms for secure multi-party computation,” in Proc. Nordic Conf. Secure IT Syst., 2014, pp. 59–74.
[9]
M. Burkhart et al., “Fast privacy-preserving top-k queries using secret sharing,” in Proc. 19th Int. Conf. Comput. Commun. Netw., 2010, pp. 1–7.
[10]
M. Burkhart et al., “SEPIA: Privacy-preserving aggregation of multi-domain network events and statistics,” in Proc. USENIX Conf. Secur., 2010, Art. no.
[11]
R. Canetti, “Security and composition of multiparty cryptographic protocols,” J. Cryptol., vol. 13, no. 1, pp. 143–202, 2000.
[12]
R. Canetti et al., “Adaptively secure multi-party computation,” in Proc. 28th Annu. ACM Symp. Theory Comput., 1996, pp. 639–648.
[13]
D. Cash et al., “Leakage-abuse attacks against searchable encryption,” in Proc. ACM Asia Conf. Comput. Commun. Secur., 2015, pp. 668–679.
[14]
H. Chen et al., “Fast private set intersection from homomorphic encryption,” in Proc. ACM Asia Conf. Comput. Commun. Secur., 2017, pp. 1243–1255.
[15]
J. H. Cheon et al., “Multi-party privacy-preserving set intersection with quasi-linear complexity,” IEICE Trans. Fundam. Electron. Commun. Comput. Sci., vol. 95-A, no. 8, pp. 1366–1378, 2012.
[16]
K. Chida et al., “An efficient secure three-party sorting protocol with an honest majority,” IACR Cryptol. ePrint Arch., vol. 2019, 2019, Art. no.
[17]
S. G. Choi et al., “Efficient three-party computation from cut-and-choose,” in Proc. Annu. Cryptol. Conf., 2014, pp. 513–530.
[18]
R. M. Corless and N. Fillion, A Graduate Introduction to Numerical Methods, Berlin, Germany: Springer, 2013.
[19]
H. Corrigan-Gibbs et al., “Prio: Private, robust, and scalable computation of aggregate statistics,” in Proc. USENIX Conf. Networked Syst. Des. Implementation, 2017, pp. 259–282.
[20]
E. D. Cristofaro et al., “Linear-complexity private set intersection protocols secure in malicious model,” in Proc. Int. Conf. Theory Appl. Cryptol. Inf. Secur., 2010, pp. 213–231.
[21]
E. D. Cristofaro et al., “Fast and private computation of cardinality of set intersection and union,” in Proc. Int. Conf. Cryptol. Netw. Secur, 2012, pp. 218–231.
[22]
I. Damgård et al., “Unconditionally secure constant-rounds multi-party computation for equality, comparison, bits and exponentiation,” in Proc. Theory Cryptogr. Conf., 2006, pp. 285–304.
[23]
C. Dong et al., “When private set intersection meets big data: An efficient and scalable protocol,” in Proc. ACM Asia Conf. Comput. Commun. Secur., 2013, pp. 789–800.
[24]
R. Egert et al., “Privately computing set-union and set-intersection cardinality via bloom filters,” in Proc. Australas. Conf. Inf. Secur. Privacy, 2015, pp. 413–430.
[25]
R. Fagin, “Combining fuzzy information from multiple systems,” J. Comput. Syst. Sci., vol. 58, no. 1, pp. 83–99, 1999.
[26]
B. H. Falk et al., “Private set intersection with linear communication from general assumptions,” 18th ACM Workshop Privacy Electron. Soc., 2019, pp. 14–25.
[27]
M. J. Freedman et al., “Efficient private matching and set intersection,” in Proc. Int. Conf. Theory Appl. Cryptographic Techn., 2004, pp. 1–19.
[28]
M. J. Freedman et al., “Keyword search and oblivious pseudorandom functions,” in Proc. Theory Cryptogr. Conf., 2005, pp. 303–324.
[29]
J. Furukawa et al., “High-throughput secure three-party computation for malicious adversaries and an honest majority,” in Proc. Annu. Int. Conf. Theory Appl. Cryptographic Techn., 2017, pp. 225–255.
[30]
O. Goldreich et al., “How to construct random functions,” J. ACM, vol. 33, no. 4, pp. 792–807, 1986.
[31]
O. Goldreich et al., “How to play ANY mental game or A completeness theorem for protocols with honest majority,” in Proc. Conf. Symp. Theory Comput., 1987, pp. 218–229.
[32]
D. M. Goldschlag et al., “Onion routing,” Commun. ACM, vol. 42, no. 2, pp. 39–41, 1999.
[33]
P. Gupta et al., “Obscure: Information-theoretic oblivious and verifiable aggregation queries,” in Proc. VLDB Endowment, vol. 12, no. 9, pp. 1030–1043, 2019.
[34]
H. Hacigümüs et al., “Executing SQL over encrypted data in the database-service-provider model,” in Proc. ACM SIGMOD Int. Conf. Manage. Data, 2002, pp. 216–227.
[35]
K. Hamada et al., “Practically efficient multi-party sorting protocols from comparison sort algorithms,” in Proc. Int. Conf. Inf. Secur. Cryptol., 2012, pp. 202–216.
[36]
C. Hazay et al., “Scalable multi-party private set-intersection,” in Proc. IACR Int. Workshop Public Key Cryptogr., 2017, pp. 175–203.
[37]
Y. Huang et al., “Private set intersection: Are garbled circuits better than custom protocols?,” in Proc. Annu. Netw. Distrib. Syst. Secur. Symp., 2012.
[38]
R. Inbar et al., “Efficient scalable multiparty private set-intersection via garbled bloom filters,” in Proc. Int. Conf. Secur. Cryptogr. Netw., 2018, pp. 235–252.
[39]
M. Ion et al., “On deploying secure computing commercially: Private intersection-sum protocols and their business applications,” IACR Cryptol. ePrint Arch., vol. 2019, 2019, Art. no.
[40]
M. S. Islam et al., “Access pattern disclosure on searchable encryption: Ramification, attack and mitigation,” in Proc. Annu. Netw. Distrib. Syst. Secur. Symp., vol. 20, 2012, pp. 12.
[41]
W. Jiang et al., “Transforming semi-honest protocols to ensure accountability,” Data Knowl. Eng., vol. 65, no. 1, pp. 57–74, 2008.
[42]
S. Kamara et al., “Scaling private set intersection to billion-element sets,” in Proc. Int. Conf. Financial Cryptogr. Data Secur., 2014, pp. 195–215.
[43]
F. Kerschbaum, “Collusion-resistant outsourcing of private set intersection,” in Proc. Annu. ACM Symp. Appl. Comput., 2012, pp. 1451–1456.
[44]
F. Kerschbaum ., “Outsourced private set intersection using homomorphic encryption,” in Proc. 7th ACM Symp. Inf. Comput. Commun. Secur., 2012, pp. 85–86.
[45]
L. Kissner et al., “Privacy-preserving set operations,” in Proc. Annu. Int. Cryptol. Conf., 2005, pp. 241–257.
[46]
V. Kolesnikov et al., “Efficient batched oblivious PRF with applications to private set intersection,” IACR Cryptol. ePrint Arch., vol. 2016, 2016, Art. no.
[47]
V. Kolesnikov et al., “Efficient batched oblivious PRF with applications to private set intersection,” in Proc. ACM Asia Conf. Comput. Commun. Secur., 2016, pp. 818–829.
[48]
V. Kolesnikov et al., “Practical multi-party private set intersection from symmetric-key techniques,” in Proc. ACM Asia Conf. Comput. Commun. Secur., 2017, pp. 1257–1272.
[49]
P. H. Le et al., “Two-party private set intersection with an untrusted third party,” in Proc. ACM Asia Conf. Comput. Commun. Secur., 2019, pp. 2403–2420.
[50]
R. Li et al., “An unconditionally secure protocol for multi-party set intersection,” in Proc. Int. Conf. Appl. Cryptogr. Netw. Secur., 2007, pp. 226–236.
[51]
Y. Li et al., “Delegatable order-revealing encryption,” in Proc. 7th ACM Symp. Inf. Comput. Commun. Secur., 2019, pp. 134–147.
[52]
Y. Lindell ., “Secure multiparty computation (MPC),” IACR Cryptol. ePrint Arch., vol. 2020, 2020, Art. no.
[53]
F. Liu et al., “Encrypted set intersection protocol for outsourced datasets,” in Proc. IEEE Int. Conf. Cloud Eng., 2014, pp. 135–140.
[54]
S. Madden et al., “TAG: A tiny aggregation service for ad-hoc sensor networks,” in Proc. USENIX Symp. Operating Syst. Des. Implementation, 2002.
[55]
D. Many, M. Burkhart, and X. Dimitropoulos, “Fast private set operations with sepia,” ETZ G93, 2012.
[56]
G. S. Narayanan et al., “Multi party distributed private matching, set disjointness and cardinality of set intersection with information theoretic security,” in Proc. Int. Conf. Cryptol. Netw. Secur., 2009, pp. 21–40.
[57]
T. Nishide et al., “Multiparty computation for interval, equality, and comparison without bit-decomposition protocol,” in Proc. Int. Workshop Public Key Cryptogr., 2007, pp. 343–360.
[58]
B. Pinkas et al., “Faster private set intersection based on OT extension,” in Proc. USENIX Secur. Sump., 2014, pp. 797–812.
[59]
B. Pinkas et al., “Phasing: Private set intersection using permutation-based hashing,” in Proc. USENIX Secur. Symp., 2015, pp. 515–530.
[60]
B. Pinkas et al., “Scalable private set intersection based on OT extension,” ACM Trans. Priv. Secur., vol. 21, no. 2, pp. 7:1–7:35, 2018.
[61]
B. Pinkas et al., “SpOT-Light: Lightweight private set intersection from sparse OT extension,” in Proc. Annu. Int. Cryptol. Conf., 2019, pp. 401–431.
[62]
B. Pinkas et al., “PSI from PaXoS: Fast, malicious private set intersection,” in Proc. Annu. Int. Conf. Theory Appl. Cryptographic Techn., 2020, pp. 739–767.
[63]
S. Qiu et al., “Identity-based private matching over outsourced encrypted datasets,” IEEE Trans. Cloud Comput., vol. 6, no. 3, pp. 747–759, 2018.
[64]
P. Rindal et al., “Malicious-secure private set intersection via dual execution,” in Proc. ACM Asia Conf. Comput. Commun. Secur., 2017, pp. 1229–1242.
[65]
A. Shamir, “How to share a secret,” Commun. ACM, vol. 22, no. 11, pp. 612–613, 1979.
[66]
J. Vaidya et al., “Privacy-preserving top-K queries,” in Proc. 21st Int. Conf. Data Eng., 2005, pp. 545–546.
[67]
J. Vaidya et al., “Secure set intersection cardinality with application to association rule mining,” J. Comput. Secur., vol. 13, no. 4, pp. 593–622, 2005.
[68]
N. Volgushev et al., “Conclave: Secure multi-party computation on big data,” in Proc. 14th EuroSys Conf., 2019, pp. 3:1–3:18.
[69]
C. Wang et al., “Secure ranked keyword search over encrypted cloud data,” in Proc. IEEE 30th Int. Conf. Distrib. Comput. Syst., 2010, pp. 253–262.
[70]
F. Wang et al., “Splinter: Practical private queries on public data,” in Proc. USENIX Conf. Networked Syst. Des. Implementation, 2017, pp. 299–313.
[71]
A. C. Yao, “How to generate and exchange secrets (extended abstract),” in Proc. 27th Annu. Symp. Foundations Comput. Sci., 1986, pp. 162–167.
[72]
E. Zhang et al., “Efficient multi-party private set intersection against malicious adversaries,” in Proc. ACM SIGSAC Conf. Cloud Comput. Secur. Workshop, 2019, pp. 93–104.
[73]
Q. Zheng et al., “Verifiable delegated set intersection operations on outsourced encrypted data,” in Proc. IEEE Int. Conf. Cloud Eng., 2015, pp. 175–184.
Recommendations
PRISM: Private Verifiable Set Computation over Multi-Owner Outsourced Databases
SIGMOD '21: Proceedings of the 2021 International Conference on Management of DataThis paper proposes Prism, a secret sharing based approach to compute private set operations (i.e., intersection and union), as well as aggregates over outsourced databases belonging to multiple owners. Prism enables data owners to pre-load the data ...
Obscure : Information-Theoretically Secure, Oblivious, and Verifiable Aggregation Queries on Secret-Shared Outsourced DataDespite exciting progress on cryptography, secure and efficient query processing over outsourced data remains an open challenge. We develop a communication-efficient and information-theoretically secure system, entitled <sc>Obscure</sc> for aggregation ...
Privacy-Preserving Computation and Verification of Aggregate Queries on Outsourced Databases
PETS '09: Proceedings of the 9th International Symposium on Privacy Enhancing TechnologiesOutsourced databases provide a solution for data owners who want to delegate the task of answering database queries to third-party service providers. However, distrustful users may desire a means of verifying the integrity of responses to their database ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
1545-5971 © 2023 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.
Publisher
IEEE Computer Society Press
Washington, DC, United States
Publication History
Published: 24 May 2023
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 13 Dec 2024