1. bookVolume 2017 (2017): Issue 4 (October 2017)
Journal Details
License
Format
Journal
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English
access type Open Access

Private Set Intersection for Unequal Set Sizes with Mobile Applications

Published Online: 10 Oct 2017
Page range: 177 - 197
Received: 28 Feb 2017
Accepted: 02 Jun 2017
Journal Details
License
Format
Journal
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English

Private set intersection (PSI) is a cryptographic technique that is applicable to many privacy-sensitive scenarios. For decades, researchers have been focusing on improving its efficiency in both communication and computation. However, most of the existing solutions are inefficient for an unequal number of inputs, which is common in conventional client-server settings. In this paper, we analyze and optimize the efficiency of existing PSI protocols to support precomputation so that they can efficiently deal with such input sets. We transform four existing PSI protocols into the precomputation form such that in the setup phase the communication is linear only in the size of the larger input set, while in the online phase the communication is linear in the size of the smaller input set. We implement all four protocols and run experiments between two PCs and between a PC and a smartphone and give a systematic comparison of their performance. Our experiments show that a protocol based on securely evaluating a garbled AES circuit achieves the fastest setup time by several orders of magnitudes, and the fastest online time in the PC setting where AES-NI acceleration is available. In the mobile setting, the fastest online time is achieved by a protocol based on the Diffie-Hellman assumption.

Keywords

[1] M. R. Albrecht, C. Rechberger, T. Schneider, T. Tiessen, and M. Zohner, “Ciphers for MPC and FHE,” in Advances in Cryptology – EUROCRYPT’15, ser. LNCS, vol. 9056. Springer, 2015, pp. 430–454.Search in Google Scholar

[2] G. Asharov, Y. Lindell, T. Schneider, and M. Zohner, “More efficient oblivious transfer and extensions for faster secure computation,” in ACM Computer and Communications Security (CCS’13). ACM, 2013, pp. 535–548.Search in Google Scholar

[3] ——, “More efficient oblivious transfer extensions with security for malicious adversaries,” in Advances in Cryptology – EUROCRYPT’15, ser. LNCS, vol. 9056. Springer, 2015, pp. 673–701.Search in Google Scholar

[4] N. Asokan, A. Dmitrienko, M. Nagy, E. Reshetova, A. Sadeghi, T. Schneider, and S. Stelle, “CrowdShare: Secure mobile resource sharing,” in Applied Cryptography and Network Security (ACNS’13), ser. LNCS, vol. 7954. Springer, 2013, pp. 432–440.Search in Google Scholar

[5] P. Baldi, R. Baronio, E. De Cristofaro, P. Gasti, and G. Tsudik, “Countering GATTACA: efficient and secure testing of fully-sequenced human genomes,” in ACM Computer and Communications Security (CCS’11). ACM, 2011, pp. 691–702.Search in Google Scholar

[6] D. Beaver, “Precomputing oblivious transfer,” in Advances in Cryptology – CRYPTO’95, ser. LNCS, vol. 963. Springer, 1995, pp. 97–109.Search in Google Scholar

[7] M. Bellare, V. T. Hoang, S. Keelveedhi, and P. Rogaway, “Efficient garbling from a fixed-key blockcipher,” in IEEE Symposium on Security and Privacy (S&P’13). IEEE, 2013, pp. 478–492.Search in Google Scholar

[8] L. Bouncy Castle Inc., “Bouncy Castle crypto APIs,” https://www.bouncycastle.org/, 2017, accessed: 2017-03-10.Search in Google Scholar

[9] J. Boyar and R. Peralta, “A new combinational logic minimization technique with applications to cryptology,” in Symposium on Experimental Algorithms (SEA’10), ser. LNCS, vol. 6049. Springer, 2010, pp. 178–189.Search in Google Scholar

[10] H. Carter, C. Amrutkar, I. Dacosta, and P. Traynor, “For your phone only: custom protocols for efficient secure function evaluation on mobile devices,” Security and Communication Networks, vol. 7, no. 7, pp. 1165–1176, 2014.Search in Google Scholar

[11] E. D. Cristofaro and G. Tsudik, “Practical private set intersection protocols with linear complexity,” in Financial Cryptography and Data Security (FC’10), ser. LNCS, vol. 6052. Springer, 2010, pp. 143–159.Search in Google Scholar

[12] ——, “Experimenting with fast private set intersection,” in Trust and Trustworthy Computing (TRUST’12), ser. LNCS, vol. 7344. Springer, 2012, pp. 55–73.Search in Google Scholar

[13] D. Demmler, T. Schneider, and M. Zohner, “Ad-hoc secure two-party computation on mobile devices using hardware tokens,” in USENIX Security Symposium’14. USENIX, 2014, pp. 893–908.Search in Google Scholar

[14] ——, “ABY - A framework for efficient mixed-protocol secure two-party computation,” in Network and Distributed System Security Symposium (NDSS’15). The Internet Society, 2015.Search in Google Scholar

[15] W. Diffie and M. E. Hellman, “New directions in cryptography,” IEEE Trans. Information Theory, vol. 22, no. 6, pp. 644–654, 1976.10.1109/TIT.1976.1055638Open DOISearch in Google Scholar

[16] I. Dinur, Y. Liu, W. Meier, and Q. Wang, “Optimized interpolation attacks on LowMC,” in Advances in Cryptology – ASIACRYPT’15, ser. LNCS, vol. 9453. Springer, 2015, pp. 535–560.Search in Google Scholar

[17] C. Dobraunig, M. Eichlseder, and F. Mendel, “Higher-order cryptanalysis of LowMC,” in Information Security and Cryptology (ICISC’15), ser. LNCS, vol. 9558. Springer, 2015, pp. 87–101.Search in Google Scholar

[18] C. Dong, L. Chen, and Z. Wen, “When private set intersection meets big data: an efficient and scalable protocol,” in ACM Computer and Communications Security (CCS’13). ACM, 2013, pp. 789–800.Search in Google Scholar

[19] L. Fan, P. Cao, J. M. Almeida, and A. Z. Broder, “Summary cache: A scalable wide-area web cache sharing protocol,” in SIGCOMM’98. ACM, 1998, pp. 254–265.Search in Google Scholar

[20] M. Fischlin, B. Pinkas, A. Sadeghi, T. Schneider, and I. Visconti, “Secure set intersection with untrusted hardware tokens,” in Topics in Cryptology – CT-RSA’11, ser. LNCS, vol. 6558. Springer, 2011, pp. 1–16.Search in Google Scholar

[21] F. S. Foundation, “The GNU multiple precision arithmetic library,” https://gmplib.org, 2017, accessed: 2017-03-10.Search in Google Scholar

[22] M. J. Freedman, Y. Ishai, B. Pinkas, and O. Reingold, “Keyword search and oblivious pseudorandom functions,” in Theory of Cryptography Conference (TCC’05), ser. LNCS, vol. 3378. Springer, 2005, pp. 303–324.Search in Google Scholar

[23] M. J. Freedman, K. Nissim, and B. Pinkas, “Efficient private matching and set intersection,” in Advances in Cryptology – EUROCRYPT’04, ser. LNCS, vol. 3027. Springer, 2004, pp. 1–19.Search in Google Scholar

[24] P. Gasti and K. B. Rasmussen, “Privacy-preserving user matching,” in ACM Workshop on Privacy in the Electronic Society (WPES’15). ACM, 2015, pp. 111–120.Search in Google Scholar

[25] C. Gentry, “Fully homomorphic encryption using ideal lattices,” in ACM Symposium on Theory of Computing (STOC’09). ACM, 2009, pp. 169–178.Search in Google Scholar

[26] N. Gilboa and Y. Ishai, “Distributed point functions and their applications,” in Advances in Cryptology – EUROCRYPT’ 14, ser. LNCS, vol. 8441. Springer, 2014, pp. 640–658.Search in Google Scholar

[27] D. Giry, “BlueKrypt cryptogrphic key length recommendation,” http://www.keylength.com, 2017, accessed: 2017-02-28.Search in Google Scholar

[28] S. D. Gordon, J. Katz, V. Kolesnikov, F. Krell, T. Malkin, M. Raykova, and Y. Vahlis, “Secure two-party computation in sublinear (amortized) time,” in ACM Conference on Computer and Communications Security (CCS’12). ACM, 2012, pp. 513–524.Search in Google Scholar

[29] L. Grassi, C. Rechberger, D. Rotaru, P. Scholl, and N. P. Smart, “MPC-friendly symmetric key primitives,” in ACM Computer and Communications Security (CCS’16). ACM, 2016, pp. 430–443.Search in Google Scholar

[30] C. Hazay and Y. Lindell, “Constructions of truly practical secure protocols using standard smartcards,” in ACM Computer and Communications Security (CCS’08). ACM, 2008, pp. 491–500.Search in Google Scholar

[31] ——, “Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries,” in Theory of Cryptography Conference (TCC’08), ser. LNCS, vol. 4948. Springer, 2008, pp. 155–175.Search in Google Scholar

[32] W. Henecka and T. Schneider, “Faster secure two-party computation with less memory,” in Computer and Communications Security (ASIACCS’13). ACM, 2013, pp. 437–446.Search in Google Scholar

[33] Y. Huang, P. Chapman, and D. Evans, “Privacy-preserving applications on smartphones,” in USENIX Workshop on Hot Topics in Security (HotSec’11). USENIX, 2011.Search in Google Scholar

[34] Y. Huang, D. Evans, and J. Katz, “Private set intersection: Are garbled circuits better than custom protocols?” in Network and Distributed System Security Symposium (NDSS’12). The Internet Society, 2012.Search in Google Scholar

[35] B. A. Huberman, M. K. Franklin, and T. Hogg, “Enhancing privacy and trust in electronic communities,” in ACM Conference on Electronic Commerce (EC’99), 1999, pp. 78–86.Search in Google Scholar

[36] Y. Ishai, J. Kilian, K. Nissim, and E. Petrank, “Extending oblivious transfers efficiently,” in Advances in Cryptology – CRYPTO’03, ser. LNCS, vol. 2729. Springer, 2003, pp. 145–161.Search in Google Scholar

[37] S. Jarecki and X. Liu, “Efficient oblivious pseudorandom function with applications to adaptive OT and secure computation of set intersection,” in Theory of Cryptography Conference (TCC’09), ser. LNCS, vol. 5444. Springer, 2009, pp. 577–594.Search in Google Scholar

[38] M. Keller, E. Orsini, and P. Scholl, “Actively secure OT extension with optimal overhead,” in Advances in Cryptology – CRYPTO’15, ser. LNCS, vol. 9215. Springer, 2015, pp. 724–741.Search in Google Scholar

[39] V. Kolesnikov, R. Kumaresan, M. Rosulek, and N. Trieu, “Efficient batched oblivious PRF with applications to private set intersection,” in ACM Computer and Communications Security (CCS’16). ACM, 2016, pp. 818–829.Search in Google Scholar

[40] V. Kolesnikov and T. Schneider, “Improved garbled circuit: Free XOR gates and applications,” in International Colloquium on Automata, Languages and Programming (ICALP’08), ser. LNCS, vol. 5126. Springer, 2008, pp. 486–498.Search in Google Scholar

[41] E. Kushilevitz and R. Ostrovsky, “Replication is NOT needed: SINGLE database, computationally-private information retrieval,” in Foundations of Computer Science (FOCS ’97). IEEE Computer Society, 1997, pp. 364–373.Search in Google Scholar

[42] Y. Lindell and B. Pinkas, “A proof of security of Yao’s protocol for two-party computation,” Journal of Cryptology, vol. 22, no. 2, pp. 161–188, 2009.10.1007/s00145-008-9036-8Open DOISearch in Google Scholar

[43] C. Liu, X. S. Wang, K. Nayak, Y. Huang, and E. Shi, “ObliVM: A programming framework for secure computation,” in Symposium on Security and Privacy (S&P’15). IEEE Computer Society, 2015, pp. 359–376, implementation available at: https://github.com/oblivm/ObliVMGC.Search in Google Scholar

[44] C. A. Meadows, “A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party,” in IEEE Symposium on Security and Privacy (S&P’86). IEEE, 1986, pp. 134–137.Search in Google Scholar

[45] T. Meskanen, J. Liu, S. Ramezanian, and V. Niemi, “Private membership test for Bloom filters,” in International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom’15). IEEE, 2015, pp. 515–522.Search in Google Scholar

[46] S. Nagaraja, P. Mittal, C. Hong, M. Caesar, and N. Borisov, “Botgrep: Finding P2P bots with structured graph analysis,” in USENIX Security Symposium’10. USENIX, 2010, pp. 95–110.Search in Google Scholar

[47] M. Nagy, E. D. Cristofaro, A. Dmitrienko, N. Asokan, and A. Sadeghi, “Do I know you?: efficient and privacy-preserving common friend-finder protocols and applications,” in Annual Computer Security Applications Conference (ACSAC’ 13), 2013, pp. 159–168.Search in Google Scholar

[48] M. Naor and O. Reingold, “Number-theoretic constructions of efficient pseudo-random functions,” J. ACM, vol. 51, no. 2, pp. 231–262, 2004.Search in Google Scholar

[49] A. Narayanan, N. Thiagarajan, M. Lakhani, M. Hamburg, and D. Boneh, “Location privacy via private proximity testing,” in Network and Distributed System Security Symposium (NDSS’11). The Internet Society, 2011.Search in Google Scholar

[50] R. Nojima and Y. Kadobayashi, “Cryptographically secure Bloom-filters,” Trans. Data Privacy, vol. 2, no. 2, pp. 131–139, 2009.Search in Google Scholar

[51] A. Pagh, R. Pagh, and S. S. Rao, “An optimal Bloom filter replacement,” in ACM-SIAM Symposium on Discrete Algorithms (SODA’05). SIAM, 2005, pp. 823–829.Search in Google Scholar

[52] A. Partow, “Bloom filter implementation,” https://github.com/ArashPartow/bloom, 2017, accessed: 2017-03-10.Search in Google Scholar

[53] B. Pinkas, T. Schneider, G. Segev, and M. Zohner, “Phasing: Private set intersection using permutation-based hashing,” in USENIX Security Symposium’15. USENIX, 2015, pp. 515–530.Search in Google Scholar

[54] B. Pinkas, T. Schneider, N. P. Smart, and S. C. Williams, “Secure two-party computation is practical,” in Advances in Cryptology – ASIACRYPT’09, ser. LNCS, vol. 5912. Springer, 2009, pp. 250–267.Search in Google Scholar

[55] B. Pinkas, T. Schneider, and M. Zohner, “Faster private set intersection based on OT extension,” in USENIX Security Symposium’14. USENIX, 2014, pp. 797–812.Search in Google Scholar

[56] ——, “Scalable private set intersection based on OT extension,” IACR Cryptology ePrint Archive, vol. 2016/930, 2016, http://ia.cr/2016/930.Search in Google Scholar

[57] S. Ramezanian, “A Study of Privacy Preserving Queries with Bloom Filters,” Master’s thesis, University of Turku, Finland, 2016.Search in Google Scholar

[58] K. Shimizu, K. Nuida, H. Arai, S. Mitsunari, N. Attrapadung, M. Hamada, K. Tsuda, T. Hirokawa, J. Sakuma, G. Hanaoka, and K. Asai, “Privacy-preserving search for chemical compound databases,” BMC Bioinformatics, vol. 16, no. 18, p. S6, 2015.Search in Google Scholar

[59] R. Sion and B. Carbunar, “On the practicality of private information retrieval,” in Network and Distributed System Security Symposium (NDSS’07). The Internet Society, 2007.Search in Google Scholar

[60] S. Tamrakar, J. Liu, A. Paverd, J. Ekberg, B. Pinkas, and N. Asokan, “The circle game: Scalable private membership test using trusted hardware,” in ACM Asia Computer and Communications Security (AsiaCCS’17). ACM, 2017, pp. 31–44.Search in Google Scholar

[61] A. C.-C. Yao, “How to generate and exchange secrets,” in Foundations of Computer Science (FOCS’86). IEEE, 1986, pp. 162–167.Search in Google Scholar

[62] A. C. Yao, “Protocols for secure computations (extended abstract),” in Foundations of Computer Science (FOCS’82). IEEE, 1982, pp. 160–164.Search in Google Scholar

[63] S. Zahur, M. Rosulek, and D. Evans, “Two halves make a whole - reducing data transfer in garbled circuits using half gates,” in Advances in Cryptology – EUROCRYPT’15, ser. LNCS, vol. 9057. Springer, 2015, pp. 220–250.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo