Files in this item
Files  Description  Format 

application/pdf Maji_Hemanta.pdf (1MB)  (no description provided) 
Description
Title:  On computational intractability assumptions in cryptography 
Author(s):  Maji, Hemanta K. 
Director of Research:  Prabhakaran, Manoj 
Doctoral Committee Chair(s):  Chekuri, Chandra S. 
Doctoral Committee Member(s):  Prabhakaran, Manoj; Borisov, Nikita; Kumar, P.R.; Ostrovsky, Rafail 
Department / Program:  Computer Science 
Discipline:  Computer Science 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Computational Intractability Assumptions
Reduction Universally Composable Security Relativistic Separation Implication and Equivalence of Assumptions 
Abstract:  In cryptographic protocols, honest parties would prefer that their security is assured even in presence of adversarial parties who have unbounded computational power. Information theoretic secure realization of cryptographic primitives provides such guarantees; but for most tasks such strong security guarantees cannot be provided for any reasonable notion of security. The standard technique used in cryptography is to assume the existence of some puzzle, whose hard instances are easy to generate but no efficient algorithm can solve them. Such assumptions, which define intractable problems for efficient algorithms, are called computational intractability assumptions. In this work, we motivate a study of computational intractability assumptions which is goal driven and lends support to the fundamental nature of some of the traditional assumptions beyond being historical accidents. Secure multiparty computation deals with the study of constructing secure protocols for general cryptographic tasks which conform to various notions of security. Inspired by complexity theory, we use the notion of reduction to further our understanding of computational intractability assumptions. Our framework explores the hardness of natural assumptions of the form: "Task F can be securely computed given an ideally secure facility for computing G". Formally, we characterize the minimal computational intractability assumption which is sufficient to securely realize a functionality using trusted copies of some other functionality. A functionality F reduces to G, similar to the complexitytheoretic notion of reduction, if F can be securely realized when parties can access trusted copies of G. Thus, if F does not reduce to G informationtheoretically, we are interested in characterizing the minimal assumption, which is sufficient, to securely realize the reduction of F to G. In our framework, we explore the relative strengths of these minimal computational assumptions. The fundamental problem, then, is to establish relations, like implication, equivalence and separation, among the assumptions which correspond to various reductions. In this work, we further our understanding of the minimal computational assumptions corresponding to such reductions by showing the following results: 1) We identify a spectrum for the set of assumptions that correspond to reduction between a pair of tasks under different security notions. These reductions are implied by the computational intractability assumption: "semihonest secure protocol for oblivious transfer exists" (shOT assumption). Additionally, the information theoretically impossible reductions considered in this thesis imply the assumption: "oneway functions exist" (OWF assumption). We conjecture that OWF assumption is necessary for these reductions. In fact, the reductions considered in this thesis are either information theoretically true, false, equivalent to OWF assumption or equivalent to shOT assumption [MPR10]. We expand our study to encompass reductions involving randomized functionalities and study the consequences of providing parties with a trusted source of common unbiased coins. For a strong notion of security they turn out to be useless and unless shOT assumption holds these randomness sources are not useful [MOPR11, MP11]. 2) We [MPS10] seek to lend additional support to the widely believed premise that "nontrivial cryptography entails the existence of oneway functions". We show that (constant round) weak cointossing protocols, imply OWF assumption. For the general problem, i.e. secure weak cointossing protocols with polynomial round complexity, we show a slightly weaker implication NP is not contained in BPP. 3) Finally, we indicate the possibility of a wide range of intractability assumptions in our spectrum, intermediate to OWF assumption and shOT assumption. We show that a class of natural assumptions corresponding to reductions that are relativistically separated from OWF assumption. Similar techniques have been used to show their separation from the assumption that "publickey encryption exists" (PKE assumption) [MMP11]; but these assumptions are not known to imply shOT assumption. We conjecture that, in fact, shOT assumption is relativistically separated from these assumptions. 
Issue Date:  20120206 
URI:  http://hdl.handle.net/2142/29716 
Rights Information:  Copyright 2011 by Hemanta Kumar Maji. All rights reserved. 
Date Available in IDEALS:  20120206 
Date Deposited:  201112 
This item appears in the following Collection(s)

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois 
Dissertations and Theses  Computer Science
Dissertations and Theses from the Dept. of Computer Science