One-way permutations and self-witnessing languages

Show full item record

Title: One-way permutations and self-witnessing languages
Author: Homan, Christopher; Thakur, Mayur
Abstract: A desirable property of one-way functions is that they be total, one-to-one, and onto—in other words, that they be permutations. We prove that one-way permutations exist exactly if PaUP-coUP: This provides the first characterization of the existence of one-way permutations based on a complexity-class separation and shows that their existence is equivalent to a number of previously studied complexity theoretic hypotheses. We study permutations in the context of witness functions of nondeterministic Turing machines. A language is in PermUP if, relative to some unambiguous, nondeterministic, polynomial-time Turing machine accepting the language, the function mapping each string to its unique witness is a permutation of the members of the language. We show that, under standard complexity-theoretic assumptions, PermUP is a strict subset of UP. We study SelfNP, the set of all languages such that, relative to some nondeterministic, polynomial-time Turing machine that accepts the language, the set of all witnesses of strings in the language is identical to the language itself. We show that SATASelfNP; and, under standard complexity-theoretic assumptions, SelfNP /= NP:
Description: Journal of Computer and System Sciences article. Please see for the complete article.
Record URI:
Date: 2003

Files in this item

Files Size Format View
CHomanArticle03-28-2003.pdf 211.0Kb PDF View/Open

The following license files are associated with this item:

This item appears in the following Collection(s)

Show full item record

Search RIT DML

Advanced Search