nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Actively Secure 1-out-of-N OT Extension with Application to Private Set Intersection

verfasst von : Michele Orrù, Emmanuela Orsini, Peter Scholl

Erschienen in: Topics in Cryptology – CT-RSA 2017

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

This paper describes a 1-out-of-N oblivious transfer (OT) extension protocol with active security, which achieves very low overhead on top of the passively secure protocol of Kolesnikov and Kumaresan (Crypto 2011). Our protocol obtains active security using a consistency check which requires only simple computation and has a communication overhead that is independent of the total number of OTs to be produced. We prove its security in both the random oracle model and the standard model, assuming a variant of correlation robustness. We describe an implementation, which demonstrates our protocol only costs around 5–30% more than the passively secure protocol.

Random 1-out-of-N OT is a key building block in recent, very efficient, passively secure private set intersection (PSI) protocols. Our random OT extension protocol has the interesting feature that it even works when N is exponentially large in the security parameter, provided that the sender only needs to obtain polynomially many outputs. We show that this can be directly applied to improve the performance of PSI, allowing the core private equality test and private set inclusion subprotocols to be carried out using just a single OT each. This leads to a reduction in communication of up to 3 times for the main component of PSI.

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 My Traces Learn What You Did in the Dark: Recovering Secret Signals Without Key Guesses

Nächstes Kapitel Low-Leakage Secure Search for Boolean Expressions

We observe an interesting connection between our protocol and additively homomorphic UC commitment schemes [FJNT16, CDD+16]: our protocol essentially runs a homomorphic commitment protocol and hashes the resulting commitments to obtain random OTs. However, this mechanism seems very specific to the workings of these commitment schemes and appears unlikely to lead to a generic transformation.

Note that our security reduction requires fixing the adversary’s random coins, so is non-uniform. Obtaining a uniform reduction seems to need at least \(\kappa + s\) base OTs, for statistical security parameter s.

http://www.sagemath.org.

http://users-cs.au.dk/orlandi/simpleOT/.

[ALSZ13]

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

[ALSZ15]

Asharov, G., Lindell, Y., Schneider, T., Zohner, M.: More efficient oblivious transfer extensions with security for malicious adversaries. In: Proceedings of Advances in Cryptology - EUROCRYPT 2015, Sofia, Bulgaria, Part I, pp. 673–701, 26–30 April 2015

[ALSZ16]

Asharov, G., Lindell, Y., Schneider, T., Zohner, M.: More efficient oblivious transfer extensions. J. Cryptol. 1–54 (2016)

[ANWOW13]

Aumasson, J.-P., Neves, S., Wilcox-O’Hearn, Z., Winnerlein, C.: BLAKE2: simpler, smaller, fast as MD5. In: Jacobson, M., Locasto, M., Mohassel, P., Safavi-Naini, R. (eds.) ACNS 2013. LNCS, vol. 7954, pp. 119–135. Springer, Heidelberg (2013). doi:10.1007/978-3-642-38980-1_8 CrossRef

[Bea96]

Beaver, D.: Correlated pseudorandomness and the complexity of private computations. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 479–488. ACM (1996)

[CDD+16]

Cascudo, I., Damgård, I., David, B., Döttling, N., Nielsen, J.B.: Rate-1, linear time and additively homomorphic UC commitments. In: Proceedings of Advances in Cryptology - CRYPTO 2016, Santa Barbara, CA, USA, Part III, pp. 179–207, 14–18 August 2016

[CO15]

Chou, T., Orlandi, C.: The simplest protocol for oblivious transfer. In: Progress in Cryptology - LATINCRYPT 2015, Guadalajara, Mexico, pp. 40–58, 23–26 August 2015

[EGL85]

Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. Commun. ACM 28(6), 637–647 (1985)MathSciNetCrossRefMATH

[FJNT16]

Frederiksen, T.K., Jakobsen, T.P., Nielsen, J.B., Trifiletti, R.: On the complexity of additively homomorphic UC commitments. In: Proceedings of Theory of Cryptography - TCC 2016-A, Tel Aviv, Israel, 10–13 January 2016, Part I, pp. 542–565 (2016)

[IKNP03]

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). doi:10.1007/978-3-540-45146-4_9 CrossRef

[IR89]

Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, pp. 44–61. ACM (1989)

[KK13]

Kolesnikov, V., Kumaresan, R.: Improved OT extension for transferring short secrets. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 54–70. Springer, Heidelberg (2013). doi:10.1007/978-3-642-40084-1_4 CrossRef

[KKRT16]

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, CCS (2016)

[KOS15]

Keller, M., Orsini, E., Scholl, P.: Actively secure OT extension with optimal overhead. In: Advances in Cryptology - CRYPTO Santa Barbara, CA, USA, pp. 724–741, 16–20 August 2015

[KOS16]

Keller, M., Orsini, E., Scholl, P.: MASCOT: faster malicious arithmetic secure computation with oblivious transfer. In: ACM Conference on Computer and Communications Security, Vienna, Austria, pp. 830–842 (2016)

[Lam16]

Lambæk, M.: Breaking and fixing private set intersection protocols. Cryptology ePrint Archive, Report 2016/665 (2016)

[LOS14]

Larraia, E., Orsini, E., Smart, N.P.: Dishonest majority multi-party computation for binary circuits. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8617, pp. 495–512. Springer, Heidelberg (2014). doi:10.1007/978-3-662-44381-1_28 CrossRef

[NNOB12]

Nielsen, J.B., Nordholt, P.S., Orlandi, C., Burra, S.S.: A new approach to practical active-secure two-party computation. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 681–700. Springer, Heidelberg (2012). doi:10.1007/978-3-642-32009-5_40 CrossRef

[NP99]

Naor, M., Pinkas, B.: Oblivious transfer and polynomial evaluation. In: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, Atlanta, GA, USA, pp. 245–254 (1999)

[PSSZ15]

Pinkas, B., Schneider, T., Segev, G., Zohner, M.: Phasing: private set intersection using permutation-based hashing. In: 24th USENIX Security Symposium, Washington, D.C., USA, 12–14 August 2015, pp. 515–530 (2015)

[PSZ14]

Pinkas, B., Schneider, T., Zohner, M.: Faster private set intersection based on OT extension. In: 23rd USENIX Security Symposium, San Diego, CA, pp. 797–812, August 2014

[PVW08]

Peikert, C., Vaikuntanathan, V., Waters, B.: A framework for efficient and composable oblivious transfer. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 554–571. Springer, Heidelberg (2008). doi:10.1007/978-3-540-85174-5_31 CrossRef

[Rab81]

Rabin, M.O.: How to exchange secrets with oblivious transfer (1981)

[SSR08]

Shankar, B., Srinathan, K., Rangan, C.P.: Alternative protocols for generalized oblivious transfer. In: 9th International Conference on Distributed Computing and Networking, ICDCN (2008)

[Yao82]

Yao, A.C.-C.: Protocols for secure computations (extended abstract). In: 23rd Annual Symposium on Foundations of Computer Science, pp. 160–164 (1982)

Titel: Actively Secure 1-out-of-N OT Extension with Application to Private Set Intersection
verfasst von: Michele Orrù
Emmanuela Orsini
Peter Scholl
Verlag: Springer International Publishing
Buch: Topics in Cryptology – CT-RSA 2017
Print ISBN: 978-3-319-52152-7

Electronic ISBN: 978-3-319-52153-4

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-52153-4_22

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