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

Circuit-PSI With Linear Complexity via Relaxed Batch OPPRF

Published Online: 20 Nov 2021
Page range: 353 - 372
Received: 31 May 2021
Accepted: 16 Sep 2021
Journal Details
License
Format
Journal
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English
Abstract

In 2-party Circuit-based Private Set Intersection (Circuit-PSI), P0 and P1 hold sets S0 and S1 respectively and wish to securely compute a function f over the set S0 ∩ S1 (e.g., cardinality, sum over associated attributes, or threshold intersection). Following a long line of work, Pinkas et al. (PSTY, Eurocrypt 2019) showed how to construct a concretely efficient Circuit-PSI protocol with linear communication complexity. However, their protocol requires super-linear computation.

In this work, we construct concretely efficient Circuit-PSI protocols with linear computational and communication cost. Further, our protocols are more performant than the state-of-the-art, PSTY – we are ≈ 2.3× more communication efficient and are up to 2.8× faster. We obtain our improvements through a new primitive called Relaxed Batch Oblivious Programmable Pseudorandom Functions (RB-OPPRF) that can be seen as a strict generalization of Batch OPPRFs that were used in PSTY. This primitive could be of independent interest.

Keywords

[1] Asharov, G., Lindell, Y., Schneider, T., Zohner, M.: More efficient oblivious transfer and extensions for faster secure computation. In: CCS (2013) Search in Google Scholar

[2] Badrinarayanan, S., Miao, P., Raghuraman, S., Rindal, P.: Multi-party threshold private set intersection with sublinear communication. In: PKC (2021) Search in Google Scholar

[3] Beaver, D.: Efficient multiparty protocols using circuit randomization. In: CRYPTO (1991) Search in Google Scholar

[4] Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: STOC (1988) Search in Google Scholar

[5] Boyle, E., Couteau, G., Gilboa, N., Ishai, Y., Kohl, L., Scholl, P.: Efficient pseudorandom correlation generators: Silent OT extension and more. In: CRYPTO (2019) Search in Google Scholar

[6] Brassard, G., Crépeau, C., Robert, J.: All-or-nothing disclosure of secrets. In: CRYPTO (1986) Search in Google Scholar

[7] Canetti, R.: Universally composable security: A new paradigm for cryptographic protocols. In: FOCS (2001) Search in Google Scholar

[8] Chase, M., Miao, P.: Private set intersection in the internet setting from lightweight oblivious PRF. In: CRYPTO (2020) Search in Google Scholar

[9] Ciampi, M., Orlandi, C.: Combining private set-intersection with secure two-party computation. In: SCN (2018) Search in Google Scholar

[10] Couteau, G.: New protocols for secure equality test and comparison. In: ACNS (2018) Search in Google Scholar

[11] Cristofaro, E.D., Kim, J., Tsudik, G.: Linear-complexity private set intersection protocols secure in malicious model. In: ASIACRYPT (2010) Search in Google Scholar

[12] Demmler, D., Schneider, T., Zohner, M.: ABY - A framework for efficient mixed-protocol secure two-party computation. In: NDSS (2015) Search in Google Scholar

[13] Dessouky, G., Koushanfar, F., Sadeghi, A., Schneider, T., Zeitouni, S., Zohner, M.: Pushing the communication barrier in secure computation using lookup tables. In: NDSS (2017) Search in Google Scholar

[14] Dong, C., Chen, L., Wen, Z.: When private set intersection meets big data: an efficient and scalable protocol. In: CCS (2013) Search in Google Scholar

[15] Encrypto Group: OPPRF-PSI. https://github.com/encryptogroup/OPPRF-PSI, Accessed: 2020-10-07 Search in Google Scholar

[16] Falk, B.H., Noble, D., Ostrovsky, R.: Private set intersection with linear communication from general assumptions. In: ACM WPES@CCS (2019) Search in Google Scholar

[17] Freedman, M.J., Ishai, Y., Pinkas, B., Reingold, O.: Keyword search and oblivious pseudorandom functions. In: TCC (2005) Search in Google Scholar

[18] Freedman, M.J., Nissim, K., Pinkas, B.: Efficient private matching and set intersection. In: EUROCRYPT (2004) Search in Google Scholar

[19] Garay, J.A., Schoenmakers, B., Villegas, J.: Practical and secure solutions for integer comparison. In: PKC (2007) Search in Google Scholar

[20] Ghosh, S., Nilges, T.: An algebraic approach to maliciously secure private set intersection. In: EUROCRYPT (2019) Search in Google Scholar

[21] Ghosh, S., Simkin, M.: The communication complexity of threshold private set intersection. In: CRYPTO (2019) Search in Google Scholar

[22] Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions (extended abstract). In: FOCS (1984) Search in Google Scholar

[23] Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or A completeness theorem for protocols with honest majority. In: STOC (1987) Search in Google Scholar

[24] Hallgren, P.A., Orlandi, C., Sabelfeld, A.: Privatepool: Privacy-preserving ridesharing. In: CSF (2017) Search in Google Scholar

[25] Huang, Y., Evans, D., Katz, J.: Private set intersection: Are garbled circuits better than custom protocols? In: NDSS (2012) Search in Google Scholar

[26] Ishai, Y., Kilian, J., Nissim, K., Petrank, E.: Extending oblivious transfers efficiently. In: CRYPTO (2003) Search in Google Scholar

[27] Karakoç, F., Küpçü, A.: Linear complexity private set intersection for secure two-party protocols. In: CANS (2020) Search in Google Scholar

[28] Karakoç, F., Nateghizad, M., Erkin, Z.: SET-OT: A secure equality testing protocol based on oblivious transfer. In: ARES (2019) Search in Google Scholar

[29] Kirsch, A., Mitzenmacher, M., Wieder, U.: More robust hashing: Cuckoo hashing with a stash. SIAM J. Comput. 39(4) (2009) Search in Google Scholar

[30] Kolesnikov, V., Kumaresan, R.: Improved OT extension for transferring short secrets. In: CRYPTO (2013) Search in Google Scholar

[31] Kolesnikov, V., Kumaresan, R., Rosulek, M., Trieu, N.: Efficient batched oblivious PRF with applications to private set intersection. In: CCS (2016) Search in Google Scholar

[32] Kolesnikov, V., Matania, N., Pinkas, B., Rosulek, M., Trieu, N.: Practical multi-party private set intersection from symmetric-key techniques. In: CCS (2017) Search in Google Scholar

[33] Kreuter, B.: Secure multiparty computation at google. In: RWC (2017) Search in Google Scholar

[34] Lindell, Y.: How to simulate it - a tutorial on the simulation proof technique. Cryptology ePrint Archive, Report 2016/046 (2016) Search in Google Scholar

[35] Meadows, C.A.: A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party. In: IEEE S & P (1986) Search in Google Scholar

[36] mpc-msri: EzPC. https://github.com/mpc-msri/EzPC, Accessed: 2020-10-07 Search in Google Scholar

[37] Oleksandr-Tkachenko: HashingTables. https://github.com/Oleksandr-Tkachenko/HashingTables, Accessed: 2020-10-07 Search in Google Scholar

[38] osu-crypto: libOTe. https://github.com/osu-crypto/libOTe, Accessed: 2020-10-07 Search in Google Scholar

[39] Pagh, R., Rodler, F.F.: Cuckoo hashing. In: Algorithms -ESA (2001) Search in Google Scholar

[40] Pinkas, B., Rosulek, M., Trieu, N., Yanai, A.: Spot-light: Lightweight private set intersection from sparse OT extension. In: CRYPTO (2019) Search in Google Scholar

[41] Pinkas, B., Rosulek, M., Trieu, N., Yanai, A.: PSI from paxos: Fast, malicious private set intersection. In: EURO-CRYPT (2020) Search in Google Scholar

[42] Pinkas, B., Schneider, T., Segev, G., Zohner, M.: Phasing: Private set intersection using permutation-based hashing. In: USENIX Security (2015) Search in Google Scholar

[43] Pinkas, B., Schneider, T., Tkachenko, O., Yanai, A.: Efficient circuit-based PSI with linear communication. In: EUROCRYPT (2019) Search in Google Scholar

[44] Pinkas, B., Schneider, T., Weinert, C., Wieder, U.: Efficient circuit-based PSI via cuckoo hashing. In: EUROCRYPT (2018) Search in Google Scholar

[45] Pinkas, B., Schneider, T., Zohner, M.: Scalable private set intersection based on OT extension. ACM Trans. Priv. Secur. 21(2) (2018) Search in Google Scholar

[46] Rabin, M.O.: How to exchange secrets with oblivious transfer. Cryptology ePrint Archive, Report 2005/187 (2005) Search in Google Scholar

[47] Rathee, D., Rathee, M., Kumar, N., Chandran, N., Gupta, D., Rastogi, A., Sharma, R.: Cryptflow2: Practical 2-party secure inference. In: CCS (2020) Search in Google Scholar

[48] Rindal, P., Schoppmann, P.: VOLE-PSI: fast OPRF and circuit-psi from vector-ole. In: EUROCRYPT (2021) Search in Google Scholar

[49] Shamir, A.: How to share a secret. Commun. ACM 22(11) (1979) Search in Google Scholar

[50] Shamir, A.: On the power of commutativity in cryptography. In: ICALP (1980) Search in Google Scholar

[51] Yang, K., Weng, C., Lan, X., Zhang, J., Wang, X.: Ferret: Fast extension for correlated OT with small communication. In: CCS (2020) Search in Google Scholar

[52] Yao, A.C.: How to generate and exchange secrets (extended abstract). In: FOCS (1986) Search in Google Scholar

[53] Zhao, Y., Chow, S.S.M.: Are you the one to share? secret transfer with access structure. PoPETs 2017(1), 149–169 (2017) Search in Google Scholar

[54] Zhao, Y., Chow, S.S.M.: Can you find the one for me? In: WPES@CCS (2018) Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo