New Techniques for Private Function Evaluation

atmire.migration.oldid3883
dc.contributor.advisorMohassel, Payman
dc.contributor.authorSadeghian, SeyedSaeed
dc.contributor.committeememberSafavi-Naini, Reyhaneh Alsadat
dc.contributor.committeememberHøyer, Peter
dc.contributor.committeememberWoelfel, Philipp
dc.contributor.committeememberScheidler, Renate
dc.contributor.committeememberButler, Kevin
dc.date.accessioned2015-12-04T19:46:10Z
dc.date.available2015-12-04T19:46:10Z
dc.date.issued2015-12-04
dc.date.submitted2015en
dc.description.abstractIn this thesis, we study the problem of general-purpose private function evaluation (PFE) wherein a single party P1 holds a circuit C, while each Pi for 1<=i<=m holds a private input xi, and the goal is for a subset (or all) of the parties to learn C(x1,…,xm) but nothing else. We pursue the design of PFE with better concrete and/or asymptotic complexity for a variety of settings. We put forth a general framework for designing PFE as the first alternative general approach to universal circuits. In this framework, the task of hiding the circuit topology and securely evaluating its gates are addressed independently through two functionalities we call CTH (Circuit Topology Hiding) and PGE (Private Gate Evaluation). We instantiate our framework using the building blocks of several well-known general MPC constructions, obtaining more efficient PFE than prior work for two-party PFE, multi-party PFE and PFE for arithmetic circuits. Next, we propose the first general framework for designing actively secure PFE, not based on universal circuits. On the theoretical side, our framework yields the first actively secure PFE with linear complexity in the circuit size. On the practical side, we obtain the first actively secure PFE for arithmetic circuits with O(glogg) complexity where g is the circuit size, significantly improving over previous constructions with complexity O(g^5). Despite its inefficiency, we identify various advantages for PFE based on universal circuits. Valiant's construction (STOC 1976) yields universal circuits with the optimal asymptotic complexity, and has been employed in several recent works. But somewhat surprisingly, no implementations of the construction exist. We look back at this construction, and provide a more approachable description. This enables us to provide constant factor improvements and the first implementation. A more accurate comparison made possible through our implementation shows that the improved Valiant's UC performs better than the theoretical estimate, and in fact is almost always smaller than the UC construction of Kolesnikov and Schneider (FC 2008). We also observe, for the first time, that the same construction can be adapted to yield size-optimized universal arithmetic circuits (UAC).en_US
dc.identifier.citationSadeghian, S. (2015). New Techniques for Private Function Evaluation (Doctoral thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca. doi:10.11575/PRISM/27099en_US
dc.identifier.doihttp://dx.doi.org/10.11575/PRISM/27099
dc.identifier.urihttp://hdl.handle.net/11023/2657
dc.language.isoeng
dc.publisher.facultyGraduate Studies
dc.publisher.institutionUniversity of Calgaryen
dc.publisher.placeCalgaryen
dc.rightsUniversity of Calgary graduate students retain copyright ownership and moral rights for their thesis. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission.
dc.subjectComputer Science
dc.subject.classificationComputer Scienceen_US
dc.subject.classificationPrivacyen_US
dc.subject.classificationSecure Computationen_US
dc.subject.classificationPrivate Function Evaluationen_US
dc.titleNew Techniques for Private Function Evaluation
dc.typedoctoral thesis
thesis.degree.disciplineComputer Science
thesis.degree.grantorUniversity of Calgary
thesis.degree.nameDoctor of Philosophy (PhD)
ucalgary.item.requestcopytrue
Files