Low ambiguity in strong, total, associative, one-way functions

Show full item record

Title: Low ambiguity in strong, total, associative, one-way functions
Author: Homan, Christopher
Abstract: Rabi and Sherman [RS97] present a cryptographic paradigm based on associative, one-way functions that are strong (i.e., hard to invert even if one of their arguments is given) and total. Hemaspaandra and Rothe [HR99] proved that such powerful one-way functions exist exactly if (standard) one-way functions exist, thus showing that the associative one-way function approach is as plausible as previous approaches. In the present paper, we study the degree of ambiguity of one-way functions. Rabi and Sherman showed that no associative one-way function (over a universe having at least two elements) can be unambiguous (i.e., one-to-one). Nonetheless, we prove that if standard, unambiguous, one-way functions exist, then there exist strong, total, associative, one-way functions that are O(n)-to-one. This puts a reasonable upper bound on the ambiguity. Our other main results are: 1. P 6= FewP if and only if there exists an (nO(1))-to-one, strong, total AOWF. 2. No O(1)-to-one total, associative functions exist in [see article for equations]. 3. For every nondecreasing, unbounded, total, recursive function g : N → N, there is a g(n)-to-one, total, commutative, associative, recursive function in [see article for equations]
Record URI: http://hdl.handle.net/1850/9086
Date: 2008

Files in this item

Files Size Format View
CHomanTechReport02-07-2008.pdf 208.3Kb 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

Browse