TU Darmstadt

ULB

TUprints

Efficient Private Function Evaluation

Kiss, Ágnes (2021)
Efficient Private Function Evaluation.
Technische Universität Darmstadt
doi: 10.26083/tuprints-00017496
Ph.D. Thesis, Primary publication, Publisher's Version

Preview

Text
Dissertation_ÁgnesKiss_160221.pdf
Copyright Information: In Copyright.
Download (10MB) | Preview

Item Type:

Ph.D. Thesis

Type of entry:

Primary publication

Title:

Efficient Private Function Evaluation

Language:

English

Referees:

Schneider, Prof. Dr. Thomas ; Asokan, Prof. Dr N.

Date:

2021

Place of Publication:

Darmstadt

Collation:

XI, 208 Seiten

Date of oral examination:

25 September 2020

DOI:

10.26083/tuprints-00017496

Abstract:

Private function evaluation (PFE) allows two or more parties to jointly compute a private function of one of the parties on the private inputs of the other parties securely. PFE can provide a viable solution in a scenario where a server holding a function that is his intellectual property or trade secret would like to compute this function on a client’s sensitive input, in a privacy-preserving manner. In recent years, multiple approaches have been presented for PFE. These approaches are based on techniques that are used for secure function evaluation (SFE) as well, where parties jointly compute the result of a publicly known function on their private inputs while keeping their inputs private. These techniques include homomorphic encryption, garbling techniques and secret sharing.

In this thesis, we present results that improve the practicality of private function evaluation where nothing about the function is revealed except its (maximum) size. The contributions are split in two parts based on the underlying function representation as follows:

PFE of Boolean circuits. Boolean circuits can represent any Boolean function and are therefore generic. PFE can be realized with the secure evaluation of a so-called universal circuit (UC) that can be programmed with a set of program bits to compute any function up to a given size n. We are the first to implement asymptotically optimal UCs with size Ω(n log n) that have been proposed by Valiant (STOC’76). We improve their concrete size by providing optimizations and show that PFE with UCs is efficient for realistic circuit sizes with hundreds of thousands of gates. We identify that the bottleneck of our PFE implementations is memory consumption, and therefore, design an algorithm that utilizes only O(n) memory at each step of the protocol execution. PFE of Boolean circuits can also be realized using additively homomorphic encryption and standard SFE techniques. This linear-complexity approach was first introduced by Katz and Malka (ASIACRYPT’11). We have shown that their protocol is practical and that our optimized implementation achieves PFE with the best performance to date for circuits starting already at a few thousand gates.

This part of the thesis is based on the following four publications:

[KS16] Á. KISS, T. SCHNEIDER. “Valiant’s Universal Circuit is Practical”. In: 35. Advances in Cryptology – EUROCRYPT’16. Vol. 9665. LNCS. Full version: https://ia.cr/2016/093. Code: https://encrypto.de/code/UC. Springer, 2016, pp. 699–728. CORE Rank A*. Appendix A.

[GKS17] D. GÜNTHER, Á. KISS, T. SCHNEIDER. “More Efficient Universal Circuit Constructions”. In: 23. Advances in Cryptology – ASIACRYPT’17. Vol. 10625. LNCS. Full version: https://ia.cr/2017/798. Code: https://encrypto.de/code/UC. Springer, 2017, pp. 443–470. CORE Rank A. Appendix B.

[AGKS20] M. Y. ALHASSAN, D. GÜNTHER, Á. KISS, T. SCHNEIDER. “Efficient and Scalable Universal Circuits”. In: Journal of Cryptology (JoC) 33.3 (2020). Springer. Online version: https://ia.cr/2019/348. Code: https://encrypto.de/code/UC, pp. 1216–1271. CORE Rank A*. Appendix C.

[HKRS20] M. HOLZ, Á. KISS, D. RATHEE, T. SCHNEIDER. “Linear-Complexity Private Function Evaluation is Practical”. In: 25. European Symposium on Research in Computer Security (ESORICS’20). Vol. 12309. LNCS. Full version: https://ia.cr/2020/853. Code: https://encrypto.de/code/linearPFE. Springer, 2020, pp. 401–420. CORE Rank A. Appendix D.

PFE of decision trees. Decision trees are a machine learning model that allow for efficient classification based on a set of input features. Privacy-preserving decision tree evaluation has been considered in the literature, both using homomorphic encryption and garbling techniques. We systematically analyze existing protocols, identify the sub-protocols of private decision tree evaluation, and present novel combinations that result in better communication and computation tradeoff than previous methods.

This part of the thesis is based on the following systematization of knowledge (SoK) publication:

[KNL+19] Á. KISS, M. NADERPOUR, J. LIU, N. ASOKAN, T. SCHNEIDER. “SoK: Modular and Efficient Private Decision Tree Evaluation”. In: Proceedings on Privacy Enhancing Technologies (PoPETs) 2019.2 (2019). De Gruyter Open. Online version: https://ia.cr/2018/1099. Code: https://encrypto.de/code/PDTE, pp. 187–208. CORE Rank B. Appendix E.

This thesis presents results that contribute to making private function evaluation (PFE) efficient and practical for deployment in use cases such as privacy-preserving classification for medical diagnostics and privacy-preserving insurance rate calculation.

Alternative Abstract:

Alternative Abstract

Language

Private Funktionsevaluierung (PFE) ermöglicht es zwei oder mehr Parteien gemeinsam eine private Funktion, die eine der Parteien kennt, auf den privaten Eingaben der anderen Parteien zu berechnen. Mit PFE lassen sich Szenarien ermöglichen, in denen eine private Funktion eines Servers, die ein geistiges Eigentum oder ein Geschäftsgeheimnis beinhalten kann, auf den sensitiven Daten eines Clients berechnet wird. In den letzten Jahren wurden mehrere PFE Ansätze vorgestellt. Diese basieren auf bekannte Techniken aus der sicheren Funktionsevaluierung (SFE), bei der die Parteien gemeinsam eine öffentlich bekannte Funktion auf ihren privaten Eingaben berechnen, ohne dass eine der Parteien die Eingaben einer anderen Partei lernt. Zu diesen Techniken zählen homomorphe Verschlüsselung, Garbling-Techniken und Secret Sharing.

Diese Dissertation zeigt praktisch anwendbare Lösungen für private Funktionsevaluierung, bei denen ausschließlich die (maximale) Größe der Funktion offenbart wird. Die Beiträge sind in zwei Abschnitte aufgeteilt, die sich aus der Art ergeben, wie die Funktion repräsentiert wird:

PFE von Booleschen Schaltkreisen. Boolesche Schaltkreise sind eine generische Option, Funktionen zu repräsentieren, da sie jede Boolesche Funktion darstellen können. PFE kann durch sichere Funktionsevaluierung eines universellen Schaltkreises (UC) ermöglicht werden, der mittels Programmierbits zur Berechnung einer beliebigen Funktion von maximaler Größe n programmiert werden kann. Wir sind die Ersten, die einen asymptotisch optimalen UC der Größe Ω(n log n) implementiert haben, der auf Valiant’s Konstruktion (STOC’76) basiert. Wir optimieren die konkrete Größe von UCs und zeigen damit, dass PFE mittels UCs effizient für realistische Schaltkreis-Größen mit mehreren Millionen Gates umsetzbar ist. Wir identifizieren, dass der Flaschenhals unserer PFE Implementierungen der Speicherverbauch ist, weswegen wir einen Algorithmus entworfen haben, der nur O(n) Speicher in jedem Protokollschritt benötigt. PFE von Booleschen Schaltkreisen kann alternativ auch mit additiver homomorpher Verschlüsselung und Standard SFE Techniken realisiert werden. Katz und Malka (ASIACRYPT’11) sind die Ersten, die diesen Ansatz mit linearer Komplexität vorgestellt haben. Wir haben gezeigt, dass dieser Ansatz praktikabel ist und dass unsere optimierte Implementierung die bis zum heutigen Tag performanteste PFE Lösung für Schaltkreise bereits ab einer Größe von einigen tausend Gattern ist.

Dieser Abschnitt der Dissertation basiert auf folgenden vier Veröffentlichungen:

PFE von Entscheidungsbäumen. Entscheidungsbäume sind ein Modell des maschinellen Lernens, die eine effiziente Klassifizierung anhand von einer Menge von Eingabe-Eigenschaften ermöglichen. Die privatsphäre-freundliche Evaluierung von Entscheidungsbäumen wurde in der Literatur mit homomorpher Verschlüsselung und Garbling-Techniken betrachtet. Wir analysieren systematisch existierende Protokolle, identifizieren die Unterprotokolle zur privaten Auswertung von Entscheidungsbäumen, und präsentieren neuartige Kombinationen, die einen besseren Abgleich von Kommunikation und Laufzeit aufweisen als bisher bekannte Methoden.

Dieser Abschnitt der Dissertation basiert auf folgender Systematization of Knowledge (SoK) Publikation:

Diese Dissertation präsentiert Ergebnisse, die private Funktionsevaluierung (PFE) effizient umsetzbar und praktikabel machen und für praktische Anwendungsfälle wie privatsphärefreundlicher medizinischer Diagnostik und privaten Berechnungen von Versicherungstarifen eingesetzt werden können.

German

Status:

Publisher's Version

URN:

urn:nbn:de:tuda-tuprints-174969

Classification DDC:

000 Generalities, computers, information > 004 Computer science

Divisions:

20 Department of Computer Science > Cryptography and Privacy Engineering (ENCRYPTO)

Date Deposited:

25 Mar 2021 12:39

Last Modified: