Low Ambiguity in Strong, Total, Associative, One-Way Functions
<|reference_start|>Low Ambiguity in Strong, Total, Associative, One-Way Functions: Rabi and Sherman 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 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. Rabiand 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 $\mathcal{O}(n)$-to-one. This puts a reasonable upper bound on the ambiguity.<|reference_end|>
@article{homan2000low,
    title={Low Ambiguity in Strong, Total, Associative, One-Way Functions},
    author={Christopher M. Homan},
    journal={arXiv preprint arXiv:cs/0010005},
    year={2000},
    archivePrefix={arXiv},
    eprint={cs/0010005},
    primaryClass={cs.CC}
}