Privacy-Preserving Multi-User Outsourced Computation for Boolean Circuits
Authors: 
Xueqiao Liu, Guomin Yang, Willy Susilo, Kai He, Robert H. Deng, Jian WengAuthors Info & Claims
Pages 4929 - 4943
Abstract
With the prevalence of outsourced computation, such as Machine Learning as a Service, protecting the privacy of sensitive data throughout the whole computation is a critical yet challenging task. The problem becomes even more tricky when multiple sources of input and/or multiple recipients of output are involved, who would encrypt/decrypt data using different keys. Considering many computation tasks demand binary operands and operations but there are only outsourced computation constructions for arithmetic calculations, in this paper, the authors propose a privacy-preserving outsourced computation framework for Boolean circuits. The proposed framework can protect sensitive data throughout the whole computation, i.e., input, output and all the intermediate values, ensuring privacy for general outsourced tasks. Moreover, it compresses the ciphertext domain of Liu et al., (2016) and attains secure protocols for four logic gates (AND, OR, NOT, and XOR) which are the basic operations in Boolean circuits. With the proposed framework as a building block, a novel Privacy-preserved (encrypted) Bloom Filter and a Multi-keyword Searchable Encryption scheme under the multi-user setting are presented. Security proof and experimental results show that the proposal is reliable and practical.
References
[1]
X. Liu, R. H. Deng, K. R. Choo, and J. Weng, “An efficient privacy-preserving outsourced calculation toolkit with multiple keys,” IEEE Trans. Inf. Forensics Security, vol. 11, no. 11, pp. 2401–2414, Nov. 2016.
[2]
Z. Shan, K. Ren, M. Blanton, and C. Wang, “Practical secure computation outsourcing: A survey,” ACM Comput. Surveys, vol. 51, no. 2, pp. 1–40, Mar. 2019.
[3]
Y. Yang, X. Liu, and R. H. Deng, “Multi-user multi-keyword rank search over encrypted data in arbitrary language,” IEEE Trans. Depend. Secure Comput., vol. 17, no. 2, pp. 320–334, Mar. 2020.
[4]
L. Liuet al., “Toward highly secure yet efficient KNN classification scheme on outsourced cloud data,” IEEE Internet Things J., vol. 6, no. 6, pp. 9841–9852, Dec. 2019.
[5]
X. Liu, G. Yang, W. Susilo, J. Tonien, X. Liu, and J. Shen, “Privacy-preserving multi-keyword searchable encryption for distributed systems,” IEEE Trans. Parallel Distrib. Syst., vol. 32, no. 3, pp. 561–574, Mar. 2021.
[6]
R. Cramer, I. Damgård, and J. B. Nielsen, “Multiparty computation from threshold homomorphic encryption,” in Proc. Int. Conf. Theory Appl. Cryptograph. Techn. Cham, Switzerland: Springer, 2001, pp. 280–300.
[7]
B. H. Bloom, “Space/time trade-offs in hash coding with allowable errors,” Commun. ACM, vol. 13, no. 7, pp. 422–426, Jul. 1970.
[8]
S. Kamara, P. Mohassel, and M. Raykova, “Outsourcing multi-party computation,” IACR Cryptol. ePrint Arch., vol. 2011, p. 272, Oct. 2011.
[9]
C. Ding, D. Pei, and A. Salomaa, “Chinese Remainder Algorithm: Applications in Computing, Coding, Cryptography. Singapore: World Scientific, 1996, pp. 13–32.
[10]
B. Kaliski, “Quadratic residuosity problem,” in Encyclopedia of Cryptography and Security. Boston, MA, USA: Springer, 2005. 10.1007/0-387-23483-7_336.
[11]
R. Canetti and M. Varia, “Decisional Diffie–Hellman problem,” in Encyclopedia of Cryptography and Security. Boston, MA, USA: Springer, 2011. 10.1007/978-1-4419-5906-5_443.
[12]
P. Christen, A. Vidanage, T. Ranbaduge, and R. Schnell, “Pattern-mining based cryptanalysis of Bloom filters for privacy-preserving record linkage,” in Proc. Pacific–Asia Conf. knowl. Discovery Data Mining. Cham, Switzerland: Springer, 2018, pp. 530–542.
[13]
P. Christen, R. Schnell, D. Vatsalan, and T. Ranbaduge, “Efficient cryptanalysis of Bloom filters for privacy-preserving record linkage,” in Proc. Pacific–Asia Conf. Knowl. Discovery Data Mining. Cham, Switzerland: Springer, 2017, pp. 628–640.
[14]
M. Kuzu, M. Kantarcioglu, E. Durham, and B. Malin, “A constraint satisfaction cryptanalysis of Bloom filters in private record linkage,” in Proc. Int. Symp. Privacy Enhancing Technol. Symp. Cham, Switzerland: Springer, 2011, pp. 226–245.
[15]
M. Kuzu, M. Kantarcioglu, E. A. Durham, C. Toth, and B. Malin, “A practical approach to achieve private medical record linkage in light of public resources,” J. Amer. Med. Inform. Assoc., vol. 20, no. 2, pp. 285–292, Mar. 2013.
[16]
F. Niedermeyer, S. Steinmetzer, M. Kroll, and R. Schnell, “Cryptanalysis of basic Bloom filters used for privacy preserving record linkage,” German Rec. Linkage Center, Nuremberg, Germany, White Paper no. WP-GRLC-2014-04, 2014.
[17]
J. D. Cohen and M. J. Fischer, A Robust and Verifiable Cryptographically Secure Election Scheme. Portland, OR, USA: IEEE, 1985. 10.1109/SFCS.1985.2.
[18]
R. Cramer, R. Gennaro, and B. Schoenmakers, “A secure and optimally efficient multi-authority election scheme,” Eur. Trans. Telecommun., vol. 8, no. 5, pp. 481–490, Sep. 1997.
[19]
I. Damgård and M. Jurik, “A generalisation, a simplification and some applications of Paillier’s probabilistic public-key system,” in Proc. 4th Int. Workshop Pract. Theory Public Key Cryptosyst., Cheju Island, South Korea, Jan. 2001, pp. 119–136.
[20]
A. Akavia, D. Feldman, and H. Shaul, “Secure search on the cloud via coresets and sketches,” 2017, arXiv:1708.05811.
[21]
A. Akavia, D. Feldman, and H. Shaul, “Secure search on encrypted data via multi-ring sketch,” in Proc. ACM SIGSAC Conf. Comput. Commun. Secur., Toronto, ON, Canada, Oct. 2018, pp. 985–1001.
[22]
C. Gentry, A Fully Homomorphic Encryption Scheme, vol. 20, no. 9. Stanford, CA, USA: Stanford Univ., 2009.
[23]
M. Belland, W. Xue, M. Kurdi, and W. Chu, “Somewhat homomorphic encryption,” Massachusetts Inst. Technol., Cambridge, MA, USA, Tech. Rep. 22, 2017.
[24]
P. Paillier, “Public-key cryptosystems based on composite degree residuosity classes,” in Proc. Int. Conf. Theory Appl. Cryptograph. Techn., Jan. 1999, pp. 223–238.
[25]
E. Bresson, D. Catalano, and D. Pointcheval, “A simple public-key cryptosystem with a double trapdoor decryption mechanism and its applications,” in Proc. 9th Int. Conf. Theory Appl. Cryptol. Inf. Secur., Adv. Cryptol. (ASIACRYPT), Taipei, Taiwan, Nov./Dec. 2003, pp. 37–54.
[26]
R. L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Commun. ACM, vol. 21, no. 2, pp. 120–126, Feb. 1978.
[27]
T. Elgamal, “A public key cryptosystem and a signature scheme based on discrete logarithms,” IEEE Trans. Inf. Theory, vol. IT-31, no. 4, pp. 469–472, Jul. 1985.
[28]
B. Joshi, B. Joshi, A. Mishra, V. Arya, A. K. Gupta, and D. Peraković, “A comparative study of privacy-preserving homomorphic encryption techniques in cloud computing,” Int. J. Cloud Appl. Comput., vol. 12, no. 1, pp. 1–11, Sep. 2022.
[29]
P. Bogetoft, I. Damgård, T. Jakobsen, K. Nielsen, J. Pagter, and T. Toft, “A practical implementation of secure auctions based on multiparty integer computation,” in Proc. Int. Conf. Financial Cryptogr. Data Secur. Cham, Switzerland: Springer, 2006, pp. 142–147.
[30]
T. Nishide and K. Ohta, “Multiparty computation for interval, equality, and comparison without bit-decomposition protocol,” in Proc. Int. Workshop Public Key Cryptogr. Cham, Switzerland: Springer, 2007, pp. 343–360.
[31]
L. Liu, R. Chen, X. Liu, J. Su, and L. Qiao, “Towards practical privacy-preserving decision tree training and evaluation in the cloud,” IEEE Trans. Inf. Forensics Security, vol. 15, pp. 2914–2929, 2020.
[32]
D. Malkhi, “Fairplay—A secure two-party computation system,” in Proc. 13th USENIX Secur. Symp., 2004, pp. 1–17.
[33]
Y. Lindell, B. Pinkas, and N. P. Smart, “Implementing two-party computation efficiently with security against malicious adversaries,” in Proc. Int. Conf. Secur. Cryptogr. Netw. Cham, Switzerland: Springer, 2008, pp. 2–20.
[34]
Y. Huang, D. Evans, J. Katz, and L. Malka, “Faster secure two-party computation using garbled circuits,” in Proc. 20th USENIX Secur. Symp., 2011, pp. 1–16.
[35]
I. Damgård, M. Geisler, M. Krøigaard, and J. B. Nielsen, “Asynchronous multiparty computation: Theory and implementation,” in Proc. Int. Workshop Public Key Cryptogr. Cham, Switzerland: Springer, 2009, pp. 160–179.
[36]
M. Burkhart, M. Strasser, D. Many, and X. Dimitropoulos, “SEPIA: Privacy-preserving aggregation of multi-domain network events and statistics,” in Proc. 19th USENIX Secur. Symp., 2010, pp. 1–17.
[37]
S. Goldwasser, “How to play any mental game, or a completeness theorem for protocols with an honest majority,” in Proc. 19th Annu. ACM (STOC), 1987, pp. 218–229.
[38]
A. Ben-David, N. Nisan, and B. Pinkas, “FairplayMP: A system for secure multi-party computation,” in Proc. 15th ACM Conf. Comput. Commun. Secur., Oct. 2008, pp. 257–266.
[39]
S. G. Choi, K.-W. Hwang, J. Katz, T. Malkin, and D. Rubenstein, “Secure multi-party computation of Boolean circuits with applications to privacy in on-line marketplaces,” in Proc. Cryptographers’ Track RSA Conf. Cham, Switzerland: Springer, 2012, pp. 416–432.
[40]
A. C. Yao, “Protocols for secure computations,” in Proc. 23rd Annu. Symp. Found. Comput. Sci. (SFCS), Nov. 1982, pp. 160–164.
[41]
C. Peikert, V. Vaikuntanathan, and B. Waters, “A framework for efficient and composable oblivious transfer,” in Proc. Annu. Int. Cryptol. Conf. Cham, Switzerland: Springer, 2008, pp. 554–571.
[42]
Y. Lindell and B. Pinkas, “Secure two-party computation via cut-and-choose oblivious transfer,” J. Cryptol., vol. 25, no. 4, pp. 680–722, Oct. 2012.
[43]
L. Fan, P. Cao, J. Almeida, and A. Z. Broder, “Summary cache: A scalable wide-area web cache sharing protocol,” IEEE/ACM Trans. Netw., vol. 8, no. 3, pp. 281–293, Jun. 2000.
[44]
M. Mitzenmacher, “Compressed Bloom filters,” IEEE/ACM Trans. Netw., vol. 10, no. 5, pp. 604–612, Oct. 2002.
[45]
E.-J. Goh, “Secure indexes,” Cryptol. ePrint Arch., Paper 2003/216, 2003. [Online]. Available: https://eprint.iacr.org/2003/216
[46]
S. G. Choi, D. Dachman-Soled, S. D. Gordon, L. Liu, and A. Yerukhimovich, “Compressed oblivious encoding for homomorphically encrypted search,” in Proc. ACM SIGSAC Conf. Comput. Commun. Secur., Nov. 2021, pp. 2277–2291.
[47]
D. Derler, K. Gellert, T. Jager, D. Slamanig, and C. Striecks, “Bloom filter encryption and applications to efficient forward-secret o-RTT key exchange,” J. Cryptol., vol. 34, no. 2, pp. 1–59, Apr. 2021.
[48]
D. Xiaoding Song, D. Wagner, and A. Perrig, “Practical techniques for searches on encrypted data,” in Proc. IEEE Symp. Secur. Privacy. (S&P), May 2000, pp. 44–55.
[49]
D. Boneh, G. Di. Crescenzo, R. Ostrovsky, and G. Persiano, “Public key encryption with keyword search,” in Proc. Int. Conf. Theory Appl. Cryptograph. Techn. Cham, Switzerland: Springer, 2004, pp. 506–522.
[50]
Mamta, B. B. Gupta, K.-C. Li, V. C. M. Leung, K. E. Psannis, and S. Yamaguchi, “Blockchain-assisted secure fine-grained searchable encryption for a cloud-based healthcare cyber-physical system,” IEEE/CAA J. Autom. Sinica, vol. 8, no. 12, pp. 1877–1890, Dec. 2021.
[51]
D. Mamta, B. B. Gupta, and S. T. Ali, “ISEkFT: An IBE-based searchable encryption scheme with k-keyword fuzzy search trapdoor,” J. Inf. Technol. Res., vol. 12, no. 3, pp. 133–153, Jul. 2019.
[52]
Y. Yang, X. Liu, and R. Deng, “Expressive query over outsourced encrypted data,” Inf. Sci., vols. 442–443, pp. 33–53, May 2018.
Recommendations
Multi-level privacy preserving data publishing
Policedata is an important source of social media data and can be regarded as a technical assistance to increase government accountability and transparency. Notably, it contains large amounts of personal private information that should be preserved ...
Privacy-Preserving Computation
APF 2012: Revised Selected Papers of the First Annual Privacy Forum on Privacy Technologies and Policy - Volume 8319Private data is commonly revealed to the party performing the computation on it. This poses a problem, particularly when outsourcing storage and computation, e.g., to the cloud. In this paper we present a review of security mechanisms and a research ...
Privacy-preserving face recognition with outsourced computation
Face recognition is one of the most important biometrics pattern recognitions, which has been widely applied in a variety of enterprise, civilian and law enforcement. The privacy of biometrics data raises important concerns, in particular if ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
1556-6021 © 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 Press
Publication History
Published: 01 January 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 28 Nov 2024
Other Metrics
Citations
Cited By
View allView Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in