Files in this item

FilesDescriptionFormat

application/pdf

application/pdfYU-DISSERTATION-2020.pdf (1MB)
(no description provided)PDF

Description

Title:Secure transformation of cryptographic protocols
Author(s):Yu, Ching-Hua
Director of Research:Prabhakaran, Manoj M
Doctoral Committee Chair(s):Erickson, Jeff G
Doctoral Committee Member(s):Miller, Andrew; Ishai, Yuval
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:Ph.D.
Genre:Dissertation
Subject(s):cryptography
secure multiparty computation
black-box transformation
bottleneck complexity
incremental FHE
SNARK
Abstract:Over decades of active research, MPC has grown into a rich and complex topic, with many incomparable flavors and numerous protocols and techniques. The diversity of models and questions forms a wide spectrum of possible tradeoffs between functionality, security, and efficiency, which partially explains the massive amount of research in the area. Meanwhile, several important results actually rely on “protocol transformations,” whereby protocols from one model of MPC are transformed to protocols from another model. Motivated by simplifying and unifying results in the area of MPC, our first goal is to formalize a general notion of black-box protocol transformations that captures previous transformations from the literature as special cases, and present several new transformations. In addition to the simplification of known feasibility results, we then push our study of protocol transformations by presenting several results regarding security augmentation and efficiency leveraging. On the other hand, we prove the impossibility of two simple types of black-box protocol transformations. Next, we initiate the study of bottleneck complexity as a new communication efficiency measure for secure multiparty computation (MPC). Roughly, the bottleneck complexity of an MPC protocol is defined as the maximum communication complexity required by any party within the protocol execution. While achieving O(n) bottleneck complexity (where n is the number of parties) is straightforward, we show that: (1) achieving sublinear bottleneck complexity is not always possible, even when no security is required. (2) On the other hand, several useful classes of functions do have o(n) bottleneck complexity, when no security is required. Then our main positive result regarding bottleneck complexity is a compiler that transforms any (possibly insecure) efficient protocol with a fixed communication-pattern for computing any functionality into a secure MPC protocol while preserving the bottleneck complexity of the underlying protocol (up to security parameter overhead). Given our compiler, an efficient protocol for any function f with sublinear bottleneck complexity can be transformed into an MPC protocol for f with the same bottleneck complexity. Along the way, we build cryptographic primitives – incremental fully-homomorphic encryption, succinct non-interactive arguments of knowledge with ID-based simulation-extractability property and verifiable protocol execution – that may be of independent interest.
Issue Date:2020-12-03
Type:Thesis
URI:http://hdl.handle.net/2142/109427
Rights Information:Copyright 2020 Ching-Hua Yu
Date Available in IDEALS:2021-03-05
Date Deposited:2020-12


This item appears in the following Collection(s)

Item Statistics