One-Way Functions in Worst-Case Cryptography: Algebraic and Security Properties
| dc.creator | Beygelzimer, A. | |
| dc.creator | Hemaspaandra, L. A. | |
| dc.creator | Homan, C. M. | |
| dc.creator | Rothe, J. | |
| dc.date | 1999-11-15 | |
| dc.date.accessioned | 2026-07-07T03:24:27Z | |
| dc.date.available | 2026-07-07T03:24:27Z | |
| dc.description | We survey recent developments in the study of (worst-case) one-way functions having strong algebraic and security properties. According to [RS93], this line of research was initiated in 1984 by Rivest and Sherman who designed two-party secret-key agreement protocols that use strongly noninvertible, total, associative one-way functions as their key building blocks. If commutativity is added as an ingredient, these protocols can be used by more than two parties, as noted by Rabi and Sherman [RS93] who also developed digital signature protocols that are based on such enhanced one-way functions. Until recently, it was an open question whether one-way functions having the algebraic and security properties that these protocols require could be created from any given one-way function. Recently, Hemaspaandra and Rothe [HR99] resolved this open issue in the affirmative, by showing that one-way functions exist if and only if strong, total, commutative, associative one-way functions exist. We discuss this result, and the work of Rabi, Rivest, and Sherman, and recent work of Homan [Hom99] that makes progress on related issues. | |
| dc.description | 17 pages | |
| dc.identifier | https://arxiv.org/abs/cs/9911007 | |
| dc.identifier | http://arxiv.org/abs/cs/9911007 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/33329 | |
| dc.subject | Computational Complexity | |
| dc.subject | Cryptography and Security | |
| dc.subject | F.1.3; E.3 | |
| dc.title | One-Way Functions in Worst-Case Cryptography: Algebraic and Security Properties | |
| dc.type | text |