✦ LIBER ✦

Creating Strong, Total, Commutative, Associative One-Way Functions from Any One-Way Function in Complexity Theory

✍ Scribed by Lane A Hemaspaandra; Jörg Rothe

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 129 KB
Volume: 58
Category: Article
ISSN: 0022-0000
DOI: 10.1006/jcss.1998.1613

No coin nor oath required. For personal study only.

✦ Synopsis

Rabi and Sherman presented novel digital signature and unauthenticated secret-key agreement protocols, developed by themselves and by Rivest and Sherman. These protocols use strong, total, commutative (in the case of multiparty secret-key agreement), associative one-way functions as their key building blocks. Although Rabi and Sherman did prove that associative oneway functions exist if P{NP, they left as an open question whether any natural complexity-theoretic assumption is sufficient to ensure the existence of strong, total, commutative, associative one-way functions. In this paper, we prove that if P{NP then strong, total, commutative, associative one-way functions exist.

📜 SIMILAR VOLUMES

An observation on associative one-way fu

An observation on associative one-way functions in complexity theory

✍ Muhammad Rabi; Alan T. Sherman 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 606 KB

We introduce the notion of associative one-way functions and prove that they exist if and only if P # NP. As evidence of their utility, we present two novel protocols that apply strong forms of these functions to achieve secret-key agreement and digital signatures. @ 1997 Published by Elsevier Scien