nach oben

Journal of Cryptology

Erschienen in:

23.09.2016

More Efficient Oblivious Transfer Extensions

verfasst von: Gilad Asharov, Yehuda Lindell, Thomas Schneider, Michael Zohner

Erschienen in: Journal of Cryptology | Ausgabe 3/2017

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Oblivious transfer (OT) is one of the most fundamental primitives in cryptography and is widely used in protocols for secure two-party and multi-party computation. As secure computation becomes more practical, the need for practical large-scale OT protocols is becoming more evident. OT extensions are protocols that enable a relatively small number of “base-OTs” to be utilized to compute a very large number of OTs at low cost. In the semi-honest setting, Ishai et al. (Advances in cryptology—CRYPTO’03, vol 2729 of LNCS, Springer, 2003) presented an OT extension protocol for which the cost of each OT (beyond the base-OTs) is just a few hash function operations. In the malicious setting, Nielsen et al. (Advances in cryptology—CRYPTO’12, vol 7417 of LNCS, Springer, 2012) presented an efficient OT extension protocol for the setting of malicious adversaries that is secure in a random oracle model. In this work, we improve OT extensions with respect to communication complexity, computation complexity, and scalability in the semi-honest, covert, and malicious model. Furthermore, we show how to modify our maliciously secure OT extension protocol to achieve security with respect to a version of correlation robustness instead of the random oracle. We also provide specific optimizations of OT extensions that are tailored to the use of OT in various secure computation protocols such as Yao’s garbled circuits and the protocol of Goldreich–Micali–Wigderson, which reduce the communication complexity even further. We experimentally verify the efficiency gains of our protocols and optimizations.

Vorheriger Artikel Lattices with Symmetry

Nächster Artikel Differential-Linear Cryptanalysis Revisited

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

Nur mit Berechtigung zugänglich

Our implementation is available online at http://encrypto.de/code/OTExtension.

According to the summary of cryptographic key length recommendations at http://keylength.com.

Note that the implementation in [64] performs 1-out-of-4 OT, but we adapted their implementation since our protocol optimizations target 1-out-of-2 OT extension.

Y. Aumann, Y. Lindell. Security against covert adversaries: Efficient protocols for realistic adversaries, in Journal of Cryptology, vol. 23(2), (Springer, 2010) pp. 281–343

G. Asharov, Y. Lindell, T. Schneider, M. Zohner. More efficient oblivious transfer and extensions for faster secure computation, in ACM Computer and Communications Security (CCS’13), pp. 535–548. ACM, 2013. Code: http://encrypto.de/code/OTExtension

G. Asharov, Y. Lindell, T. Schneider, M. Zohner. More efficient oblivious transfer extensions with security for malicious adversaries, in Advances in Cryptology—EUROCRYPT’15, vol. 9056 of LNCS, (Springer, 2015) pp. 673–701. Full version: http://eprint.iacr.org/2015/061

J. Bringer, H. Chabanne, A. Patey. SHADE: secure hamming distance computation from oblivious transfer, in Financial Cryptography and Data Security (FC’13), vol. 7862 of LNCS, (Springer, 2013), pp. 164–176

D. Beaver. Efficient multiparty protocols using circuit randomization, in Advances in cryptology—-CRYPTO’91, vol. 576 of LNCS, (Springer, 1991), pp. 420–432

D. Beaver. Correlated pseudorandomness and the complexity of private computations, in Symposium on the theory of computing (STOC’96), (ACM, 1996), pp. 479–488

M. Bellare, V. Hoang, S. Keelveedhi, P. Rogaway. Efficient garbling from a fixed-key blockcipher, on IEEE Symposium on Security and Privacy (S&P’13), (IEEE, 2013), pp. 478–492

S. S. Burra, E. Larraia, J. B. Nielsen, P. S. Nordholt, C. Orlandi, E. Orsini, P. Scholl, and N. P. Smart. High performance multi-party computation for binary circuits based on oblivious transfer. Cryptology ePrint Archive, Report 2015/472, 2015. Online: http://eprint.iacr.org/2015/472.

A. Ben-David, N. Nisan, B. Pinkas. FairplayMP: a system for secure multi-party computation, in ACM Computer and Communications Security (CCS’08), (ACM, 2008) pp. 257–266

10.

R. Canetti. Security and composition of multiparty cryptographic protocols. J. Cryptology, 13(1):143–202, 2000.MathSciNetCrossRefMATH

11.

S.G. Choi, K.-W. Hwang, J. Katz, T. Malkin, D. Rubenstein. Secure multi-party computation of Boolean circuits with applications to privacy in on-line marketplaces, in Cryptographers’ Track at the RSA Conference (CT-RSA’12), vol. 7178 of LNCS, (Springer, 2012) pp. 416–432

12.

T. Chou, C. Orlandi. The simplest protocol for oblivious transfer, in Progress in Cryptology—LATINCRYPT’15, vol. 9230 of LNCS, (Springer, 2015), pp. 40–58

13.

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

14.

I. Damgård, R. Lauritsen, T. Toft. An empirical study and some improvements of the MiniMac protocol for secure computation, in Security and Cryptography for Networks (SCN’14), vol. 8642 of LNCS, (Springer, 2014), pp. 398–415

15.

D. Demmler, T. Schneider, M. Zohner. ABY—a framework for efficient mixed-protocol secure two-party computation, in Network and Distributed System Security (NDSS’15). The Internet Society, 2015

16.

I. Damgård, S. Zakarias. Constant-overhead secure computation of Boolean circuits using preprocessing, in Theory of cryptography conference (TCC’13), vol. 7785 of LNCS, (Springer, 2013), pp. 621–641

17.

Z. Erkin, M. Franz, J. Guajardo, S. Katzenbeisser, I. Lagendijk, T. Toft. Privacy-preserving face recognition, in Privacy Enhancing Technologies Symposium (PETS’09), vol. 5672 of LNCS, (Springer, 2009), pp. 235–253

18.

Y. Ejgenberg, M. Farbstein, M. Levy, Y. Lindell. SCAPI: the secure computation application programming interface. Cryptology ePrint Archive, Report 2012/629, 2012. Online: http://eprint.iacr.org/2012/629

19.

S. Even, O. Goldreich, A. Lempel. A randomized protocol for signing contracts, in Communications of the ACM, vol. 28(6), (ACM, 1985), pp. 637–647

20.

J.O. Eklundh. A fast computer method for matrix transposing, in IEEE Transactions on Computers, vol. C-21(7), (IEEE, 1972), pp. 801–803

21.

K. Frikken, M. Atallah, C. Zhang. Privacy-preserving credit checking, in Electronic Commerce (EC’05), (ACM, 2005), pp. 147–154

22.

T.K. Frederiksen, M. Keller, E. Orsini, P. Scholl. A unified approach to MPC with preprocessing using OT, in Advances in Cryptology—ASIACRYPT’15, vol. 9452 of LNCS, (Springer, 2015), pp. 711–735

23.

T. K. Frederiksen, J. B. Nielsen. Fast and maliciously secure two-party computation using the GPU, in Applied Cryptography and Network Security (ACNS’13), vol. 7954 of LNCS, (Springer, 2013), pp. 339–356

24.

S.D. Gordon, J. Katz, V. Kolesnikov, F. Krell, T. Malkin, M. Raykova, Y. Vahlis. Secure two-party computation in sublinear (amortized) time, in ACM Computer and Communications Security (CCS’12), (ACM, 2012), pp. 513–524

25.

O. Goldreich, S. Micali, A. Wigderson. How to play any mental game or a completeness theorem for protocols with honest majority, in Symposium on Theory of Computing (STOC’87), (ACM, 1987), pp. 218–229

26.

O. Goldreich. Foundations of Cryptography, vol. 2: Basic Applications. Cambridge University Press, 2004

27.

Y. Huang, P. Chapman, D. Evans. Privacy-preserving applications on smartphones, in Hot topics in security (HotSec’11). USENIX, 2011

28.

Y. Huang, D. Evans, J. Katz. Private set intersection: Are garbled circuits better than custom protocols? in Network and Distributed System Security (NDSS’12). The Internet Society, 2012

29.

Y. Huang, D. Evans, J. Katz, L. Malka. Faster secure two-party computation using garbled circuits, in USENIX Security’11, (USENIX, 2011), pp. 539–554

30.

A. Holzer, M. Franz, S. Katzenbeisser, H. Veith. Secure two-party computations in ANSI C, in ACM Computer and Communications Security (CCS’12), (ACM, 2012) pp. 772–783

31.

D. Harnik, Y. Ishai, E. Kushilevitz, J. Buus Nielsen. OT-combiners via secure computation, in Theory of Cryptography Conference (TCC’08), vol. 4948 of LNCS, (Springer, 2008), pp. 393–411

32.

W. Henecka, S. Kögl, A.-R. Sadeghi, T. Schneider, I. Wehrenberg. TASTY: Tool for Automating Secure Two-partY computations, in ACM Computer and Communications Security (CCS’10), (ACM, 2010), pp. 451–462

33.

Y. Huang, L. Malka, D. Evans, J. Katz. Efficient privacy-preserving biometric identification, in Network and Distributed Security Symposium (NDSS’11). The Internet Society, 2011

34.

W. Henecka, T. Schneider. Faster secure two-party computation with less memory, in ACM Symposium on Information, Computer and Communications Security (ASIACCS’13), (ACM, 2013), pp. 437–446

35.

Y. Ishai, J. Kilian, K. Nissim, E. Petrank. Extending oblivious transfers efficiently, in Advances in Cryptology—CRYPTO’03, vol. 2729 of LNCS, (Springer, 2003), pp. 145–161

36.

Y. Ishai, E. Kushilevitz, R. Ostrovsky, A. Sahai. Cryptography with constant computational overhead, in ACM Symposium on Theory of Computing (STOC’08), (ACM, 2008), pp. 433–442

37.

Y. Ishai, M. Prabhakaran, and A. Sahai. Founding cryptography on oblivious transfer - efficiently, in Advances in Cryptology—CRYPTO’08, vol. 5157 of LNCS, (Springer, 2008), pp. 572–591

38.

R. Impagliazzo, S. Rudich. Limits on the provable consequences of one-way permutations, in Advances in Cryptology—CRYPTO’88, vol. 403 of LNCS, (Springer, 1988), pp. 8–26

39.

F. Kerschbaum. Automatically optimizing secure computation, in ACM Computer and Communications Security (CCS’11), (ACM, 2011), pp. 703–714

40.

V. Kolesnikov, R. Kumaresan. Improved OT extension for transferring short secrets, in Advances in Cryptology—CRYPTO’13, vol. 8043 of LNCS, (Springer, 2013) pp. 54–70

41.

M. Keller, E. Orsini, P. Scholl. Actively secure OT extension with optimal overhead, in Advances in Cryptology—CRYPTO’15, vol. 9215 of LNCS, (Springer, 2015), pp. 724–741

42.

V. Kolesnikov, T. Schneider. Improved garbled circuit: free XOR gates and applications, in International Colloquium on Automata, Languages and Programming (ICALP’08), vol. 5126 of LNCS, (Springer, 2008), pp. 486–498

43.

B. Kreuter, A. Shelat, C. Shen. Billion-gate secure computation with malicious adversaries, in USENIX Security’12, (USENIX, 2012), pp. 285–300

44.

M. Keller, P. Scholl, N.P. Smart. An architecture for practical actively secure MPC with dishonest majority, in ACM Computer and Communications Security (CCS’13), (ACM, 2013), pp. 549–560

45.

E. Larraia. Extending oblivious transfer efficiently, or - how to get active security with constant cryptographic overhead, in Progress in Cryptology– LATINCRYPT’14, vol. 8895 of LNCS, (Springer, 2014), pp. 368–386

46.

E. Larraia, E. Orsini, N.P. Smart. Dishonest majority multi-party computation for binary circuits, in Advances in Cryptology—CRYPTO’14, vol. 8617 of LNCS, (Springer, 2014), pp. 495–512

47.

L. Lovász, M.D. Plummer. Matching Theory. Akadémiai Kiadó, Budapest, 1986. Also published as vol. 121 of the North-Holland Mathematics Studies, North-Holland Publishing, Amsterdam

48.

Y. Lindell, B. Pinkas. Secure two-party computation via cut-and-choose oblivious transfer, in Theory of Cryptography Conference (TCC’11), vol. 6597 of LNCS, (Springer, 2011), pp. 329–346

49.

Y. Lindell, B. Riva. Blazing fast 2pc in the offline/online setting with security for malicious adversaries, in ACM Computer and Communications Security (CCS’15), (ACM, 2015), pp. 579–590

50.

Y. Lindell, H. Zarosim. On the feasibility of extending oblivious transfer, in Theory of Cryptography Conference (TCC’13), vol. 7785 of LNCS, (Springer, 2013), pp. 519–538

51.

L. Malka. VMCrypt—modular software architecture for scalable secure computation, in ACM Computer and Communications Security (CCS’11), (ACM, 2011), pp. 715–724

52.

D. Malkhi, N. Nisan, B. Pinkas, Y. Sella. Fairplay—a secure two-party computation system, in USENIX Security’04, (USENIX, 2004), pp. 287–302

53.

P. MacKenzie, A. Oprea, M.K. Reiter. Automatic generation of two-party computations, in ACM Computer and Communications Security (CCS’03), (ACM, 2003), pp. 210–219

54.

J.B. Nielsen. Extending oblivious transfers efficiently—how to get robustness almost for free. Cryptology ePrint Archive, Report 2007/215, 2007. Online: http://eprint.iacr.org/2007/215

55.

NIST. NIST Special Publication 800-57, Recommendation for Key Management Part 1: General (Rev. 3). Technical report, NIST, 2012

56.

J. B. Nielsen, P.S. Nordholt, C. Orlandi, S.S. Burra. A new approach to practical active-secure two-party computation. In Advances in Cryptology – CRYPTO’12, vol. 7417 of LNCS, (Springer, 2012), pp. 681–700

57.

M. Naor, B. Pinkas. Efficient oblivious transfer protocols, in Symposium on Discrete Algorithms (SODA’01), (ACM/SIAM, 2001), pp. 448–457

58.

V. Nikolaenko, U. Weinsberg, S. Ioannidis, M. Joye, D. Boneh, N. Taft. Privacy-preserving ridge regression on hundreds of millions of records, in IEEE Symposium on Security and Privacy (S&P’13), (IEEE, 2013), pp. 334–348

59.

B. Pinkas, T. Schneider, G. Segev, M. Zohner. Phasing: Private set intersection using permutation-based hashing, in USENIX Security’15, (USENIX, 2015), pp. 515–530

60.

B. Pinkas, T. Schneider, M. Zohner. Faster private set intersection based on ot extension, in USENIX Security’14, (USENIX, 2014), pp. 797–812

61.

C. Peikert, V. Vaikuntanathan, B. Waters. A framework for efficient and composable oblivious transfer, in Advances in Cryptology—CRYPTO’08, vol. 5157 of LNCS, (Springer, 2008) pp. 554–571

62.

M.O. Rabin. How to exchange secrets with oblivious transfer, TR-81 edition, 1981. Aiken Computation Lab, Harvard University.

63.

A. Schröpfer, F. Kerschbaum. Demo: secure computation in JavaScript, in ACM Computer and Communications Security (CCS’11), (ACM, 2011), pp. 849–852

64.

T. Schneider, M. Zohner. GMW vs. Yao? Efficient secure two-party computation with low depth circuits, in Financial Cryptography and Data Security (FC’13), vol. 7859 of LNCS, (Springer, 2013), pp. 275–292

65.

A.C. Yao. How to generate and exchange secrets, in Foundations of Computer Science (FOCS’86), (IEEE, 1986), pp. 162–167

Titel: More Efficient Oblivious Transfer Extensions
verfasst von: Gilad Asharov
Yehuda Lindell
Thomas Schneider
Michael Zohner
Publikationsdatum: 23.09.2016
Verlag: Springer US
Erschienen in: Journal of Cryptology / Ausgabe 3/2017
Print ISSN: 0933-2790
Elektronische ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-016-9236-6

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"

Weitere Artikel der Ausgabe 3/2017

Differential-Linear Cryptanalysis Revisited

Short Signatures from Diffie–Hellman: Realizing Almost Compact Public Key

Reconciling Non-malleability with Homomorphic Encryption

Integral Cryptanalysis on Full MISTY1

Instantiability of RSA-OAEP Under Chosen-Plaintext Attack

Lattices with Symmetry