On computational intractability assumptions in cryptography

Maji, Hemanta K.

Permalink

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

Description

Title

On computational intractability assumptions in cryptography

Author(s)

Maji, Hemanta K.

Issue Date

2012-02-06T20:12:37Z

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

Prabhakaran, Manoj

Doctoral Committee Chair(s)

Chekuri, Chandra S.

Committee Member(s)

• Prabhakaran, Manoj
• Borisov, Nikita
• Kumar, P.R.
• Ostrovsky, Rafail

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)

• 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 multi-party 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 complexity-theoretic 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 information-theoretically, 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: ""semi-honest secure protocol for oblivious transfer exists"" (sh-OT assumption). Additionally, the information theoretically impossible reductions considered in this thesis imply the assumption: ""one-way 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 sh-OT 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 sh-OT assumption holds these randomness sources are not useful [MOPR11, MP11]. 2) We [MPS10] seek to lend additional support to the widely believed premise that ""non-trivial cryptography entails the existence of one-way functions"". We show that (constant round) weak coin-tossing protocols, imply OWF assumption. For the general problem, i.e. secure weak coin-tossing 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 sh-OT 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 ""public-key encryption exists"" (PKE assumption) [MMP11]; but these assumptions are not known to imply sh-OT assumption. We conjecture that, in fact, sh-OT assumption is relativistically separated from these assumptions."

Graduation Semester

2011-12

Permalink

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

Copyright and License Information

Copyright 2011 by Hemanta Kumar Maji. All rights reserved.

Owning Collections