Secure transformation of cryptographic protocols

Yu, Ching-Hua

Permalink

https://hdl.handle.net/2142/109427 Copy

Description

Title

Secure transformation of cryptographic protocols

Author(s)

Yu, Ching-Hua

Issue Date

2020-12-03

Director of Research (if dissertation) or Advisor (if thesis)

Prabhakaran, Manoj M

Doctoral Committee Chair(s)

Erickson, Jeff G

Committee Member(s)

• Miller, Andrew
• Ishai, Yuval

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(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.

Graduation Semester

2020-12

Type of Resource

Thesis

Permalink

http://hdl.handle.net/2142/109427

Copyright and License Information

Copyright 2020 Ching-Hua Yu

Owning Collections