1. bookVolume 2022 (2022): Edizione 1 (January 2022)
Dettagli della rivista
License
Formato
Rivista
eISSN
2299-0984
Prima pubblicazione
16 Apr 2015
Frequenza di pubblicazione
4 volte all'anno
Lingue
Inglese
access type Accesso libero

Circuit-PSI With Linear Complexity via Relaxed Batch OPPRF

Pubblicato online: 20 Nov 2021
Volume & Edizione: Volume 2022 (2022) - Edizione 1 (January 2022)
Pagine: 353 - 372
Ricevuto: 31 May 2021
Accettato: 16 Sep 2021
Dettagli della rivista
License
Formato
Rivista
eISSN
2299-0984
Prima pubblicazione
16 Apr 2015
Frequenza di pubblicazione
4 volte all'anno
Lingue
Inglese
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)10.1145/2508859.2516738 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)10.1007/978-3-030-75248-4_13 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)10.1145/62212.62213 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)10.1007/978-3-030-26954-8_16 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)10.1109/SFCS.2001.959888 Search in Google Scholar

[8] Chase, M., Miao, P.: Private set intersection in the internet setting from lightweight oblivious PRF. In: CRYPTO (2020)10.1007/978-3-030-56877-1_2 Search in Google Scholar

[9] Ciampi, M., Orlandi, C.: Combining private set-intersection with secure two-party computation. In: SCN (2018)10.1007/978-3-319-98113-0_25 Search in Google Scholar

[10] Couteau, G.: New protocols for secure equality test and comparison. In: ACNS (2018)10.1007/978-3-319-93387-0_16 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)10.1007/978-3-642-17373-8_13 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)10.14722/ndss.2015.23113 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)10.14722/ndss.2017.23097 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)10.1145/2508859.2516701 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)10.1007/978-3-540-30576-7_17 Search in Google Scholar

[18] Freedman, M.J., Nissim, K., Pinkas, B.: Efficient private matching and set intersection. In: EUROCRYPT (2004)10.1007/978-3-540-24676-3_1 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)10.1007/978-3-030-17659-4_6 Search in Google Scholar

[21] Ghosh, S., Simkin, M.: The communication complexity of threshold private set intersection. In: CRYPTO (2019)10.1007/978-3-030-26951-7_1 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)10.1145/28395.28420 Search in Google Scholar

[24] Hallgren, P.A., Orlandi, C., Sabelfeld, A.: Privatepool: Privacy-preserving ridesharing. In: CSF (2017)10.1109/CSF.2017.24 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)10.1007/978-3-540-45146-4_9 Search in Google Scholar

[27] Karakoç, F., Küpçü, A.: Linear complexity private set intersection for secure two-party protocols. In: CANS (2020)10.1007/978-3-030-65411-5_20 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)10.1145/3339252.3339264 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)10.1137/080728743 Search in Google Scholar

[30] Kolesnikov, V., Kumaresan, R.: Improved OT extension for transferring short secrets. In: CRYPTO (2013)10.1007/978-3-642-40084-1_4 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)10.1145/2976749.2978381 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)10.1145/3133956.3134065 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)10.1109/SP.1986.10022 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)10.7146/brics.v8i32.21692 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)10.1007/978-3-030-26954-8_13 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)10.1145/3460120.3484778 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)10.1007/978-3-030-17659-4_5 Search in Google Scholar

[44] Pinkas, B., Schneider, T., Weinert, C., Wieder, U.: Efficient circuit-based PSI via cuckoo hashing. In: EUROCRYPT (2018)10.1007/978-3-319-78372-7_5 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)10.1145/3154794 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)10.1145/3372297.3417274 Search in Google Scholar

[48] Rindal, P., Schoppmann, P.: VOLE-PSI: fast OPRF and circuit-psi from vector-ole. In: EUROCRYPT (2021)10.1007/978-3-030-77886-6_31 Search in Google Scholar

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

[50] Shamir, A.: On the power of commutativity in cryptography. In: ICALP (1980)10.1007/3-540-10003-2_100 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)10.1145/3372297.3417276 Search in Google Scholar

[52] Yao, A.C.: How to generate and exchange secrets (extended abstract). In: FOCS (1986)10.1109/SFCS.1986.25 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)10.1515/popets-2017-0010 Search in Google Scholar

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

Articoli consigliati da Trend MD

Pianifica la tua conferenza remota con Sciendo