Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Complexity Measures for Public-Key Cryptosystems

IP.com Disclosure Number: IPCOM000128015D
Original Publication Date: 1985-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 43 page(s) / 95K

Publishing Venue

Software Patent Institute

Related People

Joachim Grollmann: AUTHOR [+4]

Abstract

A general theory of public-key cryptography is developed that is based on the mathematical framework of complexity theory. Two related approaches are taken to the development of this theory, and these approaches correspond to different but equivalent, formulations of the problem of cracking a public-key cryprosystem (PKCS). The first approach is to model the cracking problem as a partial decision problem called a "promise problem." Every NP-hard promise problem is shown to be uniformly NP-hard, and a number of results and a conjecture about promise problems are shown to be equivalent to reparability assertions for sets in NP that are the natural analogues of well-known results in classical recursion theory. The conjecture, if it is true, implies nonexistence of PKCS having NP-hard cracking problems. The second approach represents the cracking problem of a PKCS as a partial computational problem directly. Using this approach, it is shown that one-way functions exist if and only if P y' UP and that one-way functions with greater cryptographic significance exist if and only if NP contains disjoint P-inseparable sets. The paper concludes with a discussion of almost-everywhere security measures for PKCS. ii

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 6% of the total text.

Page 1 of 43

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Complexity Measures for Public-Key Cryptosystems

by Joachim Grollmann and Alan L. Selman

November 1985

TR 85-31

Complexity Measure. for Public-Key Cryptosystems Joachim Grollmann Fachbereich Informatik I Universitat Dortmund

4000 Dortmund 50 West Germany Alan L. Selman Computer Science Department Iowa State University Ames, Iowa 50011 November 1985 This research was performed while the first; author visited the Computer Science Department, Iowa State University, Ames, Iowa 50011. Funding for this research was provided by the National Science Foundation under grants MCS81-20263 and DC'.R84-02033 and by the Fulbright Kommission of West Germany. Some of the result's of this paper were presented in preliminary form at the 25th IEEE Symposium on Foundations of Computer Science.

Key Words

public-key cryptography, promise problems, one-way function, UP, security, inseparable, NP- hard, uniformly NP-hard i

Abstract

A general theory of public-key cryptography is developed that is based on the mathematical framework of complexity theory. Two related approaches are taken to the development of this theory, and these approaches correspond to different but equivalent, formulations of the problem of cracking a public-key cryprosystem (PKCS). The first approach is to model the cracking problem as a partial decision problem called a "promise problem." Every NP-hard promise problem is shown to be uniformly NP-hard, and a number of results and a conjecture about promise problems are shown to be equivalent to reparability assertions for sets in NP that are the natural analogues of well-known results in classical recursion theory. The conjecture, if it is true, implies nonexistence of PKCS having NP-hard cracking problems. The second approach represents the cracking problem of a PKCS as a partial computational problem directly. Using this approach, it is shown that one-way functions exist if and only if P y' UP and that one-way functions with greater cryptographic significance exist if and only if NP contains disjoint P- inseparable sets. The paper concludes with a discussion of almost-everywhere security measures for PKCS. ii

1 Introduction

Since any public-key cryptosyst,em (PKCS) can be cracked nondeterministically in poly-nomial time, and since, minimally, a PKCS should not be crackable deterministically in polynomial time, a proof that a given system is secure would imply P -/- NP. Several concrete systems have been created in recent years, but none have been proved secure in this weak sense, even if P

Iowa State University Page 1 Dec 31, 1985

Page 2 of 43

Complexity Measures for Public-Key Cryptosystems

:/: NP is assumed as an hypothesis. The reasons for this vary but some general remarks can be made. The Merkle-Hellman schemes IMH781 are based on an NP-complete problem (Knapsack), but the problem of cracking these schemes are not necessarily polynomially equivalent to the original...