Article

SpOT-Light: Lightweight Private Set Intersection from Sparse OT Extension

Authors:

Avishay YanaiAuthors Info & Claims

Advances in Cryptology – CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings, Part III

Pages 401 - 431

https://doi.org/10.1007/978-3-030-26954-8_13

Published: 18 August 2019 Publication History

Abstract

We describe a novel approach for two-party private set intersection (PSI) with semi-honest security. Compared to existing PSI protocols, ours has a more favorable balance between communication and computation. Specifically, our protocol has the lowest monetary cost of any known PSI protocol, when run over the Internet using cloud-based computing services (taking into account current rates for CPU + data). On slow networks (e.g., 10 Mbps) our protocol is actually the fastest.

Our novel underlying technique is a variant of oblivious transfer (OT) extension that we call sparse OT extension. Conceptually it can be thought of as a communication-efficient multipoint oblivious PRF evaluation. Our sparse OT technique relies heavily on manipulating high-degree polynomials over large finite fields (i.e. elements whose representation requires hundreds of bits). We introduce extensive algorithmic and engineering improvements for interpolation and multi-point evaluation of such polynomials, which we believe will be of independent interest.

Finally, we present an extensive empirical comparison of state-of-the-art PSI protocols in several application scenarios and along several dimensions of measurement: running time, communication, peak memory consumption, and—arguably the most relevant metric for practice—monetary cost.

References

[1]

Asharov, G., Lindell, Y., Schneider, T., Zohner, M.: More efficient oblivious transfer and extensions for faster secure computation. In: ACM CCS, pp. 535–548 (2013)

[2]

Ateniese G, De Cristofaro E, and Tsudik G Catalano D, Fazio N, Gennaro R, and Nicolosi A (If) size matters: size-hiding private set intersection Public Key Cryptography – PKC 2011 2011 Heidelberg Springer 156-173

[3]

Beaver, D.: Correlated pseudorandomness and the complexity of private computations. In: STOC, pp. 479–488 (1996)

[4]

Bernstein DJ Yung M, Dodis Y, Kiayias A, and Malkin T Curve25519: new Diffie-Hellman speed records Public Key Cryptography - PKC 2006 2006 Heidelberg Springer 207-228

Digital Library

[5]

Brickell, J., Porter, D.E., Shmatikov, V., Witchel, E.: Privacy-preserving remote diagnostics. In: ACM CCS, pp. 498–507 (2007)

[6]

Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: FOCS, pp. 136–145 (2001)

[7]

Cerulli A, De Cristofaro E, and Soriente C Preneel B and Vercauteren F Nothing refreshes like a RePSI: reactive private set intersection Applied Cryptography and Network Security 2018 Cham Springer 280-300

Digital Library

[8]

Chen, H., Laine, K., Rindal, P.: Fast private set intersection from homomorphic encryption. In: ACM CCS 2017, pp. 1243–1255 (2017)

[9]

Cho C, Dachman-Soled D, and Jarecki S Sako K Efficient concurrent covert computation of string equality and set intersection Topics in Cryptology - CT-RSA 2016 2016 Cham Springer 164-179

Digital Library

[10]

Cormen TH, Leiserson CE, Rivest RL, and Stein C Introduction to Algorithms 2009 3 Cambridge MIT Press

Digital Library

[11]

De Cristofaro E, Gasti P, and Tsudik G Pieprzyk J, Sadeghi A-R, and Manulis M Fast and private computation of cardinality of set intersection and union Cryptology and Network Security 2012 Heidelberg Springer 218-231

[12]

De Cristofaro E, Kim J, and Tsudik G Abe M Linear-complexity private set intersection protocols secure in malicious model Advances in Cryptology - ASIACRYPT 2010 2010 Heidelberg Springer 213-231

[13]

De Cristofaro E and Tsudik G Katzenbeisser S, Weippl E, Camp LJ, Volkamer M, Reiter M, and Zhang X Experimenting with fast private set intersection Trust and Trustworthy Computing 2012 Heidelberg Springer 55-73

Digital Library

[14]

Czumaj A, Riley C, and Scheideler C Arora S, Jansen K, Rolim JDP, and Sahai A Perfectly balanced allocation Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques 2003 Heidelberg Springer 240-251

[15]

Demmler D, Rindal P, Rosulek M, and Trieu N PIR-PSI: scaling private contact discovery Proc. Priv. Enhancing Technol. 2018 2018 4 159-178

[16]

Dong, C., Chen, L., Wen, Z.: When private set intersection meets big data: an efficient and scalable protocol. In: ACM CCS 2013, pp. 789–800 (2013)

[17]

Even S, Goldreich O, and Lempel A A randomized protocol for signing contracts Commun. ACM 1985 28 637-647

Digital Library

[18]

Falk, B.H., Noble, D., Ostrovsky, R.: Private set intersection with linear communication from general assumptions. ePrint Archive, Report 2018/238 (2018)

[19]

Freedman MJ, Ishai Y, Pinkas B, and Reingold O Kilian J Keyword search and oblivious pseudorandom functions Theory of Cryptography 2005 Heidelberg Springer 303-324

Digital Library

[20]

Ghosh, S., Nielsen, J.B., Nilges, T.: Maliciously secure oblivious linear function evaluation with constant overhead. Cryptology ePrint Archive, Report 2017/409 (2017). http://eprint.iacr.org/2017/409

[21]

Ghosh S, Nielsen JB, and Nilges T Takagi T and Peyrin T Maliciously secure oblivious linear function evaluation with constant overhead Advances in Cryptology – ASIACRYPT 2017 2017 Cham Springer 629-659

[22]

Ghosh S and Nilges T Ishai Y and Rijmen V An algebraic approach to maliciously secure private set intersection Advances in Cryptology – EUROCRYPT 2019 2019 Cham Springer 154-185

Digital Library

[23]

Hazay C and Lindell Y Canetti R Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries Theory of Cryptography 2008 Heidelberg Springer 155-175

[24]

Hazay C and Venkitasubramaniam M Fehr S Scalable multi-party private set-intersection Public-Key Cryptography – PKC 2017 2017 Heidelberg Springer 175-203

[25]

He, X., Machanavajjhala, A., Flynn, C.J., Srivastava, D.: Composing differential privacy and secure computation: a case study on scaling private record linkage. In: ACM CCS, pp. 1389–1406 (2017)

[26]

Henecka, W., Schneider, T.: Faster secure two-party computation with less memory. In: ASIA CCS, pp. 437–446 (2013)

[27]

Huang, Y., Evans, D., Katz, J.: Private set intersection: are garbled circuits better than custom protocols? In: NDSS (2012)

[28]

Huberman, B.A., Franklin, M.K., Hogg, T.: Enhancing privacy and trust in electronic communities. In: EC, pp. 78–86 (1999). https://dblp.org/rec/conf/sigecom/HubermanFH99

[29]

Impagliazzo R and Rudich S Goldwasser S Limits on the provable consequences of one-way permutations Advances in Cryptology — CRYPTO 1988 1990 New York Springer 8-26

[30]

Ion, M., et al.: Private intersection-sum protocol with applications to attributing aggregate ad conversions. ePrint Archive 2017/738 (2017)

[31]

Ishai Y, Kilian J, Nissim K, and Petrank E Boneh D Extending oblivious transfers efficiently Advances in Cryptology - CRYPTO 2003 2003 Heidelberg Springer 145-161

[32]

Ishai Y, Prabhakaran M, and Sahai A Reingold O Secure arithmetic computation with no honest majority Theory of Cryptography 2009 Heidelberg Springer 294-314

Digital Library

[33]

Kiss Á, Liu J, Schneider T, Asokan N, and Pinkas B Private set intersection for unequal set sizes with mobile applications PoPETs 2017 2017 4 177-197

[34]

Kolesnikov V and Kumaresan R Canetti R and Garay JA Improved OT extension for transferring short secrets Advances in Cryptology – CRYPTO 2013 2013 Heidelberg Springer 54-70

[35]

Kolesnikov, V., Kumaresan, R., Rosulek, M., Trieu, N.: Efficient batched OPRF with applications to PSI. In: ACM CCS (2016)

[36]

Kolesnikov, V., Matania, N., Pinkas, B., Rosulek, M., Trieu, N.: Practical multi-party private set intersection from symmetric-key techniques. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 17, pp. 1257–1272. ACM Press (2017)

[37]

Lambæk, M.: Breaking and fixing private set intersection protocols. Master’s thesis, Aarhus University (2016)

[38]

Manulis M, Pinkas B, and Poettering B Zhou J and Yung M Privacy-preserving group discovery with linear complexity Applied Cryptography and Network Security 2010 Heidelberg Springer 420-437

[39]

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

[40]

Moenck, R., Borodin, A.: Fast modular transforms via division. In: Switching and Automata Theory, pp. 90–96 (1972)

[41]

Naor, M., Pinkas, B.: Oblivious transfer and polynomial evaluation. In: 31st ACM STOC, pp. 245–254. ACM Press, May 1999

[42]

Naor, M., Pinkas, B.: Efficient oblivious transfer protocols. In: Kosaraju, S.R. (ed.) 12th SODA, pp. 448–457. ACM-SIAM (2001)

[43]

Patra, A., Sarkar, P., Suresh, A.: Fast actively secure OT extension for short secrets. In: NDSS (2017)

[44]

Pinkas, B., Schneider, T., Segev, G., Zohner, M.: Phasing: private set intersection using permutation-based hashing. In: USENIX 2015 (2015)

[45]

Pinkas, B., Schneider, T., Zohner, M.: Faster private set intersection based on OT extension. In: USENIX 2014, pp. 797–812 (2014)

[46]

Rabin, M.O.: How to exchange secrets with oblivious transfer. ePrint Archive 2005/187, (2005)

[47]

Resende, A.C.D., Aranha, D.F.: Unbalanced approximate private set intersection. ePrint Archive 2017/677 (2017)

[48]

Rindal, P., Rosulek, M.: Malicious-secure private set intersection via dual execution. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 17, pp. 1229–1242. ACM Press (2017)

[49]

Sanders P, Egner S, and Korst J Fast concurrent access to parallel disks Algorithmica 2003 35 1 21-55

[50]

Shamir A de Bakker J and van Leeuwen J On the power of commutativity in cryptography Automata, Languages and Programming 1980 Heidelberg Springer 582-595

[51]

Troncoso-Pastoriza, J.R., Katzenbeisser, S., Celik, M.U.: Privacy preserving error resilient DNA searching through oblivious automata. In: ACM CCS, pp. 519–528 (2007)

Cited By

Wang PLiu YLi ZLi R(2024)An LDP Compatible Sketch for Securely Approximating Set Intersection CardinalitiesProceedings of the ACM on Management of Data10.1145/36392812:1(1-27)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639281
Ning JTan ZZhang KYe W(2024)Low Communication-Cost PSI Protocol for Unbalanced Two-Party Private SetsIET Information Security10.1049/2024/60526512024Online publication date: 17-Feb-2024
https://dl.acm.org/doi/10.1049/2024/6052651
Liu KLi XTakagi T(2024)Review the Cuckoo Hash-Based Unbalanced Private Set Union: Leakage, Fix, and OptimizationComputer Security – ESORICS 202410.1007/978-3-031-70890-9_17(331-352)Online publication date: 16-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70890-9_17
Show More Cited By

Recommendations

Efficient Batched Oblivious PRF with Applications to Private Set Intersection
CCS '16: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security

We describe a lightweight protocol for oblivious evaluation of a pseudorandom function (OPRF) in the presence of semihonest adversaries. In an OPRF protocol a receiver has an input r; the sender gets output s and the receiver gets output F(s; r), where ...
Scalable Private Set Intersection Based on OT Extension

Private set intersection (PSI) allows two parties to compute the intersection of their sets without revealing any information about items that are not in the intersection. It is one of the best studied applications of secure computation and many PSI ...
Faster private set intersection based on OT extension
SEC'14: Proceedings of the 23rd USENIX conference on Security Symposium

Private set intersection (PSI) allows two parties to compute the intersection of their sets without revealing any information about items that are not in the intersection. It is one of the best studied applications of secure computation and many PSI ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Advances in Cryptology – CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings, Part III

Aug 2019

863 pages

ISBN:978-3-030-26953-1

DOI:10.1007/978-3-030-26954-8

Editors:
Alexandra Boldyreva
Georgia Institute of Technology, Atlanta, GA, USA
,
Daniele Micciancio
University of California at San Diego, La Jolla, CA, USA

© International Association for Cryptologic Research 2019.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 18 August 2019

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

54
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang PLiu YLi ZLi R(2024)An LDP Compatible Sketch for Securely Approximating Set Intersection CardinalitiesProceedings of the ACM on Management of Data10.1145/36392812:1(1-27)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639281
Ning JTan ZZhang KYe W(2024)Low Communication-Cost PSI Protocol for Unbalanced Two-Party Private SetsIET Information Security10.1049/2024/60526512024Online publication date: 17-Feb-2024
https://dl.acm.org/doi/10.1049/2024/6052651
Liu KLi XTakagi T(2024)Review the Cuckoo Hash-Based Unbalanced Private Set Union: Leakage, Fix, and OptimizationComputer Security – ESORICS 202410.1007/978-3-031-70890-9_17(331-352)Online publication date: 16-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70890-9_17
Garimella GGoff BMiao P(2024)Computation Efficient Structure-Aware PSI from Incremental Function Secret SharingAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68397-8_10(309-345)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68397-8_10
Chen YZhang MZhang CDong MLiu W(2024)Private Set Operations from Multi-query Reverse Private Membership TestPublic-Key Cryptography – PKC 202410.1007/978-3-031-57725-3_13(387-416)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57725-3_13
Carpent XHwang STsudik G(2024)Element Distinctness and Bounded Input Size in Private Set Intersection and Related ProtocolsApplied Cryptography and Network Security10.1007/978-3-031-54770-6_2(26-57)Online publication date: 5-Mar-2024
https://dl.acm.org/doi/10.1007/978-3-031-54770-6_2
Zhang CChen YLiu WZhang MLin DCalandrino JTroncoso C(2023)Linear private set union from multi-query reverse private membership testProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620257(337-354)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620257
Chakraborti AFanti GReiter MCalandrino JTroncoso C(2023)Distance-aware private set intersectionProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620256(319-336)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620256
Wu MYuen TCalandrino JTroncoso C(2023)Efficient unbalanced private set intersection cardinality and user-friendly privacy-preserving contact tracingProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620254(283-300)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620254
Wu GHe QJiang JZhang ZZhao YZou YZhang JWei CYan YZhang H(2023)Topgun: An ECC Accelerator for Private Set IntersectionACM Transactions on Reconfigurable Technology and Systems10.1145/360311416:4(1-30)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1145/3603114
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents