TU Darmstadt / ULB / TUbiblio

Faster Oblivious Transfer Extension and Its Impact on Secure Computation

Zohner, Michael (2017)
Faster Oblivious Transfer Extension and Its Impact on Secure Computation.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

Abstract

Secure two-party computation allows two parties to evaluate a function on their private inputs while keeping all information private except what can be inferred from the outputs. A major building block and the foundation for many efficient secure computation protocols is oblivious transfer (OT). In an OT protocol a sender inputs two messages (x_{0}, x_{1}) while a receiver with choice bit c wants to receive message x_{c}.The OT protocol execution guarantees that the sender learns no information about c and the receiver learns no information about x_{1−c}. This thesis focuses on the efficient generation of OTs and their use in secure computation. In particular, we show how to compute OTs more efficiently, improve generic secure computation protocols which can be used to securely evaluate any functionality, and develop highly efficient special-purpose protocols for private set intersection (PSI). We outline our contributions in more detail next.

More Efficient OT Extensions. The most efficient OT protocols are based on public-key cryptography and require a constant number of exponentiations per OT. However, for many practical applications where millions to billions of OTs need to be computed, these exponentiations become prohibitively slow. To enable these applications, OT extension protocols [Bea96, IKNP03] can be used, which extend a small number of public-key-based OTs to an arbitrarily large number using cheap symmetric-key cryptography only. We improve the computation and communication efficiency of OT extension protocols and show how to achieve security against malicious adversaries, which can arbitrarily deviate from the protocol, at low overhead. Our resulting protocols can compute several million of OTs per second and we show that, in contrast to previous belief, the local computation overhead for computing OTs is so low that the main bottleneck is the network bandwidth. Parts of these results are published in: • G. Asharov, Y. Lindell, T. Schneider, M. Zohner. More Efficient Oblivious Transfer and Extensions for Faster Secure Computation. In 20th ACM Conference on Computer and Communications Security (CCS’13). • G. Asharov, Y. Lindell, T. Schneider, M. Zohner. More Efficient Oblivious Transfer Extensions with Security for Malicious Adversaries. In 34th Advances in Cryptology – EUROCRYPT’15. • G. Asharov, Y. Lindell, T. Schneider, M. Zohner. More Efficient Oblivious Transfer Extensions. To appear in Journal of Cryptology. Online at http://eprint.iacr.org/2016/602.

Communication-Efficient Generic Secure Two-Party Computation. Generic secure two-party computation techniques allow to evaluate a function, represented as a circuit of linear (XOR) and non-linear (AND) gates. One of the most prominent generic secure two-party computation protocols is Yao’s garbled circuits [Yao86], for which many optimizations have been proposed. Shortly after Yao’s protocol, the generic secure protocol by Goldreich-Micali-Wigderson (GMW) [GMW87] was introduced. The GMW protocol requires a large number of OTs and was believed to be less efficient for secure two-party computation than Yao’s protocol [HL10, CHK+12]. We improve the efficiency of the GMW protocol and show that it can outperform Yao’s garbled circuits protocol in settings with low bandwidth. Furthermore, we utilize the flexibility of OT and outline special-purpose constructions that can be used within the GMW protocol and which improve its efficiency even further. Parts of these results are published in: • T. Schneider, M. Zohner. GMW vs. Yao? Efficient Secure Two-Party Computation with Low Depth Circuits. In 17th International Conference on Financial Cryptography and Data Security (FC’13). • D. Demmler, T. Schneider, M. Zohner. ABY - A Framework for Efficient Mixed-Protocol Secure Two-Party Computation. In 22th Network and Distributed System Security Symposium (NDSS’15). • G. Dessouky, F. Koushanfar, A.-R. Sadeghi, T. Schneider, S. Zeitouni, M. Zohner. Pushing the Communication Barrier in Secure Computation using Lookup Tables. In 24th Network and Distributed System Security Symposium (NDSS’17).

Faster Private Set Intersection (PSI). PSI allows two parties to compute the intersection of their private sets without revealing any element that is not in the intersection. PSI is a well-studied problem in secure computation and many special-purpose protocols have been proposed. However, existing PSI protocols are several orders of magnitude slower than an insecure naive hashing solution that is used in practice. In addition, many protocols were compared in a biased fashion, which makes it difficult to identify the most promising solution for a particular scenario. We systematize the progress made on PSI protocols by reviewing, optimizing, and comparing existing PSI protocols. We then introduce a novel PSI protocol that is based on our efficiency improvements in OT extension protocols and which outperforms existing protocols by up to two orders of magnitude. Parts of these results are published in: • B. Pinkas, T. Schneider, M. Zohner. Faster Private Set Intersection Based on OT Extension. In 23th USENIX Security Symposium (USENIX Security’14). • B. Pinkas, T. Schneider, G. Segev, M. Zohner. Phasing: Private Set Intersection using Permutation-based Hashing. In 24th USENIX Security Symposium (USENIX Security’15). • B. Pinkas, T. Schneider, M. Zohner. Scalable Private Set Intersection Based on OT Extension. Journal paper. In submission. Online at http://iacr.eprint.org/2016/930.

Item Type: Ph.D. Thesis
Erschienen: 2017
Creators: Zohner, Michael
Type of entry: Primary publication
Title: Faster Oblivious Transfer Extension and Its Impact on Secure Computation
Language: English
Referees: Schneider, Dr. Thomas ; Pinkas, Prof. Dr. Benny ; Katzenbeisser, Prof. Dr. Stefan
Date: 2017
Place of Publication: Darmstadt
Refereed: 9 December 2016
URL / URN: http://tuprints.ulb.tu-darmstadt.de/6154
Abstract:

Secure two-party computation allows two parties to evaluate a function on their private inputs while keeping all information private except what can be inferred from the outputs. A major building block and the foundation for many efficient secure computation protocols is oblivious transfer (OT). In an OT protocol a sender inputs two messages (x_{0}, x_{1}) while a receiver with choice bit c wants to receive message x_{c}.The OT protocol execution guarantees that the sender learns no information about c and the receiver learns no information about x_{1−c}. This thesis focuses on the efficient generation of OTs and their use in secure computation. In particular, we show how to compute OTs more efficiently, improve generic secure computation protocols which can be used to securely evaluate any functionality, and develop highly efficient special-purpose protocols for private set intersection (PSI). We outline our contributions in more detail next.

More Efficient OT Extensions. The most efficient OT protocols are based on public-key cryptography and require a constant number of exponentiations per OT. However, for many practical applications where millions to billions of OTs need to be computed, these exponentiations become prohibitively slow. To enable these applications, OT extension protocols [Bea96, IKNP03] can be used, which extend a small number of public-key-based OTs to an arbitrarily large number using cheap symmetric-key cryptography only. We improve the computation and communication efficiency of OT extension protocols and show how to achieve security against malicious adversaries, which can arbitrarily deviate from the protocol, at low overhead. Our resulting protocols can compute several million of OTs per second and we show that, in contrast to previous belief, the local computation overhead for computing OTs is so low that the main bottleneck is the network bandwidth. Parts of these results are published in: • G. Asharov, Y. Lindell, T. Schneider, M. Zohner. More Efficient Oblivious Transfer and Extensions for Faster Secure Computation. In 20th ACM Conference on Computer and Communications Security (CCS’13). • G. Asharov, Y. Lindell, T. Schneider, M. Zohner. More Efficient Oblivious Transfer Extensions with Security for Malicious Adversaries. In 34th Advances in Cryptology – EUROCRYPT’15. • G. Asharov, Y. Lindell, T. Schneider, M. Zohner. More Efficient Oblivious Transfer Extensions. To appear in Journal of Cryptology. Online at http://eprint.iacr.org/2016/602.

Communication-Efficient Generic Secure Two-Party Computation. Generic secure two-party computation techniques allow to evaluate a function, represented as a circuit of linear (XOR) and non-linear (AND) gates. One of the most prominent generic secure two-party computation protocols is Yao’s garbled circuits [Yao86], for which many optimizations have been proposed. Shortly after Yao’s protocol, the generic secure protocol by Goldreich-Micali-Wigderson (GMW) [GMW87] was introduced. The GMW protocol requires a large number of OTs and was believed to be less efficient for secure two-party computation than Yao’s protocol [HL10, CHK+12]. We improve the efficiency of the GMW protocol and show that it can outperform Yao’s garbled circuits protocol in settings with low bandwidth. Furthermore, we utilize the flexibility of OT and outline special-purpose constructions that can be used within the GMW protocol and which improve its efficiency even further. Parts of these results are published in: • T. Schneider, M. Zohner. GMW vs. Yao? Efficient Secure Two-Party Computation with Low Depth Circuits. In 17th International Conference on Financial Cryptography and Data Security (FC’13). • D. Demmler, T. Schneider, M. Zohner. ABY - A Framework for Efficient Mixed-Protocol Secure Two-Party Computation. In 22th Network and Distributed System Security Symposium (NDSS’15). • G. Dessouky, F. Koushanfar, A.-R. Sadeghi, T. Schneider, S. Zeitouni, M. Zohner. Pushing the Communication Barrier in Secure Computation using Lookup Tables. In 24th Network and Distributed System Security Symposium (NDSS’17).

Faster Private Set Intersection (PSI). PSI allows two parties to compute the intersection of their private sets without revealing any element that is not in the intersection. PSI is a well-studied problem in secure computation and many special-purpose protocols have been proposed. However, existing PSI protocols are several orders of magnitude slower than an insecure naive hashing solution that is used in practice. In addition, many protocols were compared in a biased fashion, which makes it difficult to identify the most promising solution for a particular scenario. We systematize the progress made on PSI protocols by reviewing, optimizing, and comparing existing PSI protocols. We then introduce a novel PSI protocol that is based on our efficiency improvements in OT extension protocols and which outperforms existing protocols by up to two orders of magnitude. Parts of these results are published in: • B. Pinkas, T. Schneider, M. Zohner. Faster Private Set Intersection Based on OT Extension. In 23th USENIX Security Symposium (USENIX Security’14). • B. Pinkas, T. Schneider, G. Segev, M. Zohner. Phasing: Private Set Intersection using Permutation-based Hashing. In 24th USENIX Security Symposium (USENIX Security’15). • B. Pinkas, T. Schneider, M. Zohner. Scalable Private Set Intersection Based on OT Extension. Journal paper. In submission. Online at http://iacr.eprint.org/2016/930.

Alternative Abstract:
Alternative abstract Language

Sichere Zweiparteienberechnung erlaubt es zwei Parteien eine Funktion auf ihren privaten Eingabedaten zu evaluieren ohne dass Informationen über die Eingabedaten, die nicht von der Ausgabe ableitbar sind, preisgegeben werden. Ein wichtiger Baustein und die Grundlage für viele sichere Berechnungsprotokolle ist Oblivious Transfer (OT). In einem OT Protokoll interagieren ein Sender mit Nachrichten (x_{0}, x_{1}) und ein Empfänger mit Auswahlbit c, sodass der Empfänger die Nachricht x_{c} empfängt ohne dass der Sender Informationen über c oder der Empfänger Informationen über x_{1−c} lernt. Diese Dissertation befasst sich mit der effizienten Generierung von OTs und deren Einsatz im Gebiet der sicheren Zweiparteienberechnung. Wir zeigen wie OTs effizienter generiert werden können, verbessern generische sichere Berechnungsprotokolle, die dazu genutzt werden können um jede Funktion sicher zu berechnen, und entwickeln hoch effiziente sichere Berechnungsprotokolle für private Schnittmengenberechnung (PSI). Im Folgenden beschreiben wir unseren wissenschaftlichen Beitrag detaillierter.

Effizientere OT Extension Protokolle. Die meisten effizienten OT Protokolle basieren auf asymmetrischer Verschlüsselung und benötigen eine konstante Anzahl von Exponentiationen pro OT. Für praktische Anwendungen, in denen Millionen bis Milliarden von OTs benötigt werden, ist diese hohe Anzahl an Exponentiationen allerdings untragbar. Um solche Anwendungen trotzdem zu realisieren, wurden OT Extension Protokolle [Bea96, IKNP03] eingeführt, die eine kleine Anzahl von OTs aus Protokollen die auf asymmetrischer Verschlüsselung beruhen mittels effizienter symmetrischer Verschlüsselung auf eine beliebige Anzahl von OTs ausdehnen. Wir verbessern die Berechnungs- und Kommunikationseffizienz von OT Extension Protokollen und zeigen auf wie Sicherheit gegen stärkere, aktive Angreifer, welche beliebig von der Protokollausführung abweichen können, mittels geringem Mehraufwand erreicht werden kann. Unsere Protokolle ermöglichen die Generierung von mehreren Millionen OTs pro Sekunde, wobei die Netzwerkkommunikation den Flaschenhals darstellt anstatt, wie allgemein vermutet, die Berechnungskomplexität. Teile dieser Ergebnisse wurden publiziert in: • G. Asharov, Y. Lindell, T. Schneider, M. Zohner. More Efficient Oblivious Transfer and Extensions for Faster Secure Computation. In 20ter ACM Konferenz zu Computer and Communications Security (CCS’13). • G. Asharov, Y. Lindell, T. Schneider, M. Zohner. More Efficient Oblivious Transfer Extensions with Security for Malicious Adversaries. In 34ter Advances in Cryptology – EUROCRYPT’15. • G. Asharov, Y. Lindell, T. Schneider, M. Zohner. More Efficient Oblivious Transfer Extensions. Erscheint in Journal of Cryptology. Online auf http://eprint.iacr.org/2016/602.

Kommunikationseffiziente, Generische, Sichere Zweiparteienberechnung. Protokolle zur generischen sicheren Zweiparteienberechnung erlauben es eine Funktion zu evaluieren, die als Schaltkreis aus linearen (XOR) und nichtlinearen (UND) Gattern dargestellt ist. Eines der prominentesten Protokolle in diesem Umfeld ist Yao’s Garbled Circuits [Yao86], für welches viele Optimierungen vorgeschlagen wurden. Kurz nach Yao’s Protokoll wurde das generische, sichere Protokoll von Goldreich-Micali-Wigderson (GMW) [GMW87] vorgeschlagen, welches aber aufgrund seiner hohen Abhängigkeit von OT als weniger effizient für generisch, sichere Zweiparteienberechnung als Yao’s Protokoll angesehen wurde [HL10, CHK+12]. Wir verbessern die Effizienz des GMW Protokolls und zeigen, dass es besser in Szenarien mit niedriger Bandbreite abschneidet als Yao’s Protokoll. Zudem nutzen wir die Flexibilität von OT um Protokolle für spezielle Funktionen zu entwickeln, die mit dem GMW Protokoll kombinierbar sind und dessen Effizienz weiter steigern. Teile dieser Ergebnisse wurden publiziert in: • T. Schneider, M. Zohner. GMW vs. Yao? Efficient Secure Two-Party Computation with Low Depth Circuits. In 17ter Internationaler Konferenz zu Financial Cryptography and Data Security (FC’13). • D. Demmler, T. Schneider, M. Zohner. ABY - A Framework for Efficient Mixed-Protocol Secure Two-Party Computation. In 22ter Network and Distributed System Security Symposium (NDSS’15). • G. Dessouky, F. Koushanfar, A.-R. Sadeghi, T. Schneider, S. Zeitouni, M. Zohner. Pushing the Communication Barrier in Secure Computation using Lookup Tables. In 24ter Network and Distributed System Security Symposium (NDSS’17).

Schnellere Private Schnittmengenberechnung (PSI). Mittels PSI können zwei Parteien die Schnittmenge ihrer privaten Mengen berechnen ohne Elemente preiszugeben, die nicht in der Schnittmenge sind. Obwohl zahlreiche PSI Protokolle vorgeschlagen wurden, sind alle derzeit existierenden Protokolle mehrere Größenordnungen langsamer als eine unsichere Lösung, welche in der Praxis eingesetzt wird. Zudem wurden viele Protokolle unter ungleichen Bedingungen verglichen, was die Identifizierung des vielversprechendsten Protokolls für ein bestimmtes Szenario erschwert. Wir systematisieren existierende PSI Protokolle indem wir einen Überblick über existierende Protokolle geben und diese dann optimieren und vergleichen. Zudem entwickeln wir ein neues PSI Protokoll, das auf unseren Verbesserungen im Bereich der OT Extension Protokolle basiert und die Leistung bestehender PSI Protokolle um zwei Größenordnungen übertrifft. Teile dieser Ergebnisse wurden publiziert in: • B. Pinkas, T. Schneider, M. Zohner. Faster Private Set Intersection Based on OT Extension. In 23ter USENIX Security Symposium (USENIX Security’14). • B. Pinkas, T. Schneider, G. Segev, M. Zohner. Phasing: Private Set Intersection using Permutation-based Hashing. In 24ter USENIX Security Symposium (USENIX Security’15). • B. Pinkas, T. Schneider, M. Zohner. Scalable Private Set Intersection Based on OT Extension. Journal Einreichung. Im Bewertungsprozess. Online auf http://iacr.eprint.org/2016/930.

German
URN: urn:nbn:de:tuda-tuprints-61549
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science
20 Department of Computer Science > Cryptography and Privacy Engineering (ENCRYPTO)
20 Department of Computer Science > EC SPRIDE
20 Department of Computer Science > EC SPRIDE > Engineering Cryptographic Protocols (am 01.03.2018 in Cryptography and Privacy Engineering)
Date Deposited: 07 May 2017 19:55
Last Modified: 18 Jul 2018 20:14
PPN:
Referees: Schneider, Dr. Thomas ; Pinkas, Prof. Dr. Benny ; Katzenbeisser, Prof. Dr. Stefan
Refereed / Verteidigung / mdl. Prüfung: 9 December 2016
Export:
Suche nach Titel in: TUfind oder in Google
Send an inquiry Send an inquiry

Options (only for editors)
Show editorial Details Show editorial Details