nach oben

Erschienen in:

2021 | OriginalPaper | Buchkapitel

VOLE-PSI: Fast OPRF and Circuit-PSI from Vector-OLE

verfasst von : Peter Rindal, Phillipp Schoppmann

Erschienen in: Advances in Cryptology – EUROCRYPT 2021

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this work we present a new construction for a batched Oblivious Pseudorandom Function (OPRF) based on Vector-OLE and the PaXoS data structure. We then use it in the standard transformation for achieving Private Set Intersection (PSI) from an OPRF. Our overall construction is highly efficient with O(n) communication and computation. We demonstrate that our protocol can achieve malicious security at only a very small overhead compared to the semi-honest variant. For input sizes \(n = 2^{20}\), our malicious protocol needs 6.2 s and less than 59 MB communication. This corresponds to under 450 bits per element, which is the lowest number for any published PSI protocol (semi-honest or malicious) to date. Moreover, in theory our semi-honest (resp. malicious) protocol can achieve as low as 219 (resp. 260) bits per element for \(n=2^{20}\) at the added cost of interpolating a polynomial over n elements.

As a second contribution, we present an extension where the output of the PSI is secret-shared between the two parties. This functionality is generally referred to as Circuit-PSI. It allows the parties to perform a subsequent MPC protocol on the secret-shared outputs, e.g., train a machine learning model. Our circuit PSI protocol builds on our OPRF construction along with another application of the PaXoS data structure. It achieves semi-honest security and allows for a highly efficient implementation, up to 3x faster than previous work.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Function Secret Sharing for Mixed-Mode and Fixed-Point Secure Computation

In our malicious OPRF construction (Sect. 3.2), we will instead use a random oracle \({\mathsf {H}} \), and set \(M\boldsymbol{P}^\intercal = ({\mathsf {H}} (x_0), {\mathsf {H}} (x_1), \dots , {\mathsf {H}} (x_n))^\intercal \). We stick to the semi-honest variant here for ease of presentation.

In the case of a malicious Receiver and depending on the choice of \({\mathsf {row}} \), it may be possible for \(|X|>n\) with noticeable probability. However, for PaXoS this can be bounded as \(|X|\le m\approx 2.4n\) while interpolation ensures that \(|X|\le m=n\).

In the \({\mathcal {F}_{\textsf {oprf}}}\) hybrid where F is truly random.

In low communication settings (10 Mbps and 1 Mbps), [CM20] takes 15% longer than [Pin+19b], but at the same time up to 75% longer than our protocol.

[App+17]

Applebaum, B., Damgård, I., Ishai, Y., Nielsen, M., Zichron, L.: Secure arithmetic computation with constant computational overhead. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 223–254. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_8CrossRef

[BM74]

Borodin, A., Moenck, R.: Fast modular transforms. J. Comput. Syst. Sci. 8(3), 366–386 (1974)MathSciNetCrossRef

[Boy+18]

Boyle, E., Couteau, G., Gilboa, N., Ishai, Y.: Compressing vector OLE. In: ACM Conference on Computer and Communications Security, pp. 896–912. ACM (2018)

[Boy+19]

Boyle, E., et al.: Efficient two-round OT extension and silent non-interactive secure computation. In: ACM Conference on Computer and Communications Security, pp. 291–308. ACM (2019)

[Bud+20]

Buddhavarapu, P., Knox, A., Mohassel, P., Sengupta, S., Taubeneck, E., Vlaskin, V.: Private matching for compute. IACR Cryptology ePrint Archive 2020, p. 599 (2020)

[CKT10]

De Cristofaro, E., Kim, J., Tsudik, G.: Linear-complexity private set intersection protocols secure in malicious model. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 213–231. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-17373-8_13CrossRefMATH

[CM20]

Chase, M., Miao, P.: Private set intersection in the internet setting from lightweight oblivious PRF. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12172, pp. 34–63. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56877-1_2CrossRef

[CO18]

Ciampi, M., Orlandi, C.: Combining private set-intersection with secure two-party computation. In: Catalano, D., De Prisco, R. (eds.) SCN 2018. LNCS, vol. 11035, pp. 464–482. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-98113-0_25CrossRef

[CT10]

De Cristofaro, E., Tsudik, G.: Practical private set intersection protocols with linear complexity. In: Sion, R. (ed.) FC 2010. LNCS, vol. 6052, pp. 143–159. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14577-3_13CrossRef

[DCW13]

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

[Dem+18]

Demmler, D., Rindal, P., Rosulek, M., Trieu, N.: PIRPSI: scaling private contact discovery. Proc. Priv. Enhancing Technol. 2018(4), 159–178 (2018) CrossRef

[Gil99]

Gilboa, N.: Two party RSA key generation. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 116–129. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48405-1_8CrossRef

[HEK12]

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

[HGS]

Hubert, B., Geul, J., Séhier, S.: wondershaper: Command-line utility for limiting an adapter bandwidth. https://github.com/magnific0/wondershaper

[Igr]

igraph: Library for the analysis of networks. https://github.com/igraph/igraph

[Ion+20]

Ion, M., et al.: On deploying secure computing: private intersection- sum-with-cardinality. In: EuroS&P, pp. 370–389. IEEE (2020)

[Ish+03]

Ishai, Y., Kilian, J., Nissim, K., Petrank, E.: Extending oblivious transfers efficiently. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 145–161. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_9CrossRef

[Kal+19]

Kales, D., Rechberger, C., Schneider, T., Senker, M., Weinert, C.: Mobile private contact discovery at scale. In: USENIX Security Symposium, pp. 1447–1464. USENIX Association (2019)

[Kis+17]

Kiss, Á., Liu, J., Schneider, T., Asokan, N., Pinkas, B.: Private set intersection for unequal set sizes with mobile applications. Proc. Priv. Enhancing Technol. 2017(4), 177–197 (2017)CrossRef

[Kol+16]

Kolesnikov, V., Kumaresan, R., Rosulek, M., Trieu, N.: Efficient batched oblivious PRF with applications to private set intersection. In: ACM Conference on Computer and Communications Security, pp. 818–829. ACM (2016)

[KS12]

Kobayashi, K., Shibuya, T.: Generalization of Lu’s linear time encoding algorithm for LDPC codes. In: ISITA, pp. 16–20. IEEE (2012)

[LM10]

Lu, J., Moura, J.M.F.: Linear time encoding of LDPC codes. IEEE Trans. Inf. Theory 56(1), 233–249 (2010)MathSciNetCrossRef

[Mea86]

Meadows, C.A.: A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party. In: IEEE Symposium on Security and Privacy, pp. 134–137. IEEE Computer Society (1986)

[OOS17]

Orrù, M., Orsini, E., Scholl, P.: Actively secure 1-out-of-N OT extension with application to private set intersection. In: Handschuh, H. (ed.) CT-RSA 2017. LNCS, vol. 10159, pp. 381–396. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-52153-4_22CrossRef

[Pin+15]

Pinkas, B., Schneider, T., Segev, G., Zohner, M.: Phasing: private set intersection using permutation-based hashing. In: USENIX Security Symposium, pp. 515–530. USENIX Association (2015)

[Pin+18]

Pinkas, B., Schneider, T., Weinert, C., Wieder, U.: Efficient circuit-based PSI via cuckoo hashing. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10822, pp. 125–157. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78372-7_5CrossRef

[Pin+19a]

Pinkas, B., Schneider, T., Tkachenko, O., Yanai, A.: Efficient circuit-based PSI with linear communication. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11478, pp. 122–153. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17659-4_5CrossRef

[Pin+19b]

Pinkas, B., Rosulek, M., Trieu, N., Yanai, A.: SpOT-light: lightweight private set intersection from sparse OT extension. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11694, pp. 401–431. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26954-8_13CrossRef

[Pin+20]

Pinkas, B., Rosulek, M., Trieu, N., Yanai, A.: PSI from PaXoS: fast, malicious private set intersection. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12106, pp. 739–767. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45724-2_25CrossRef

[PSZ14]

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

[PSZ18]

Pinkas, B., Schneider, T., Zohner, M.: Scalable private set intersection based on OT extension. ACM Trans. Priv. Secur. 21(2), 71–735 (2018)CrossRef

[Rin]

Rindal, P.: libOTe: A fast, portable, and easy to use Oblivious Transfer Library. https://github.com/osu-crypto/libOTe

[RR17a]

Rindal, P., Rosulek, M.: Improved private set intersection against malicious adversaries. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10210, pp. 235–259. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56620-7_9CrossRef

[RR17b]

Rindal, P., Rosulek, M.: Malicious-secure private set intersection via dual execution. In: ACM Conference on Computer and Communications Security, pp. 1229–1242. ACM (2017)

[Sch+19a]

Schoppmann, P., Gascón, A., Reichert, L., Raykova, M.: Distributed vector-OLE: improved constructions and implementation. In: ACM Conference on Computer and Communications Security, pp. 1055–1072. ACM (2019)

[Sch+19b]

Schoppmann, P., Gascón, A., Raykova, M., Pinkas, B.: Make some ROOM for the zeros: data sparsity in secure distributed machine learning. In: ACM Conference on Computer and Communications Security, pp. 1335–1350. ACM (2019)

[Wen+20]

Weng, C., Yang, K., Katz, J., Wang, X.: Wolverine: fast, scalable, and communication-efficient zero- knowledge proofs for Boolean and arithmetic circuits. IACR Cryptology ePrint Archive 2020, p. 925 (2020)

[Yan+20]

Yang, K., Weng, C., Lan, X., Zhang, J., Wang, X.: Ferret: fast extension for correlated OT with small communication. In: CCS, pp. 1607–1626. ACM (2020)

Titel: VOLE-PSI: Fast OPRF and Circuit-PSI from Vector-OLE
verfasst von: Peter Rindal
Phillipp Schoppmann
Verlag: Springer International Publishing
Buch: Advances in Cryptology – EUROCRYPT 2021
Print ISBN: 978-3-030-77885-9

Electronic ISBN: 978-3-030-77886-6

Copyright-Jahr: 2021
DOI: https://doi.org/10.1007/978-3-030-77886-6_31

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner