{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/109427"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/109427","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Secure transformation of cryptographic protocols","abstract":"This Dissertation was approved for publication on 2020-12-03 at 10:35.","abstract_html":"This Dissertation was approved for publication on 2020-12-03 at 10:35.","abstract_has_math":false,"creators":["Yu, Ching-Hua"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Prabhakaran, Manoj M","Erickson, Jeff G","Miller, Andrew","Ishai, Yuval"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2021,"date_issued":"2021-03-05T21:38:19Z","date_published":"2021-03-05T21:38:19Z","updated_at":"2026-07-22T22:24:50Z","subjects":["cryptography","secure multiparty computation","black-box transformation","bottleneck complexity","incremental FHE","SNARK"],"languages":["en"],"rights":["Copyright 2020 Ching-Hua Yu"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/109427","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Prabhakaran, Manoj M","Erickson, Jeff G","Miller, Andrew","Ishai, Yuval"]},{"key":"dc:creator","label":"Author","values":["Yu, Ching-Hua"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2021-03-05T21:38:19Z","2020-12-03","2020-12"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["cryptography","secure multiparty computation","black-box transformation","bottleneck complexity","incremental FHE","SNARK"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2020 Ching-Hua Yu"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/109427"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["This Dissertation was approved for publication on 2020-12-03 at 10:35.","DSpace SAF Submission Ingestion Package generated from Vireo submission #16036 on 2021-03-04 at 15:35:58","Made available in DSpace on 2021-03-05T21:38:19Z (GMT). No. of bitstreams: 2 YU-DISSERTATION-2020.pdf: 1087725 bytes, checksum: db3b460b80a9f8e020c6270764d89980 (MD5) LICENSE.txt: 4209 bytes, checksum: 51c365d90cafaf84e2c9ccd9a2ffce2a (MD5) Previous issue date: 2020-12-03","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.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2021-03-04 without embargo terms","The student, Ching-Hua Yu, accepted the attached license on 2020-12-02 at 13:36.","The student, Ching-Hua Yu, submitted this Dissertation for approval on 2020-12-02 at 16:57."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Secure transformation of cryptographic protocols"]}]}],"canonical_facts":{"dc:contributor":["Prabhakaran, Manoj M","Erickson, Jeff G","Miller, Andrew","Ishai, Yuval"],"dc:creator":["Yu, Ching-Hua"],"dc:date":["2021-03-05T21:38:19Z","2020-12-03","2020-12"],"dc:description":["This Dissertation was approved for publication on 2020-12-03 at 10:35.","DSpace SAF Submission Ingestion Package generated from Vireo submission #16036 on 2021-03-04 at 15:35:58","Made available in DSpace on 2021-03-05T21:38:19Z (GMT). No. of bitstreams: 2 YU-DISSERTATION-2020.pdf: 1087725 bytes, checksum: db3b460b80a9f8e020c6270764d89980 (MD5) LICENSE.txt: 4209 bytes, checksum: 51c365d90cafaf84e2c9ccd9a2ffce2a (MD5) Previous issue date: 2020-12-03","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.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2021-03-04 without embargo terms","The student, Ching-Hua Yu, accepted the attached license on 2020-12-02 at 13:36.","The student, Ching-Hua Yu, submitted this Dissertation for approval on 2020-12-02 at 16:57."],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/109427"],"dc:language":["en"],"dc:rights":["Copyright 2020 Ching-Hua Yu"],"dc:subject":["cryptography","secure multiparty computation","black-box transformation","bottleneck complexity","incremental FHE","SNARK"],"dc:title":["Secure transformation of cryptographic protocols"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:50Z"}