If P ≠ NP then Some Strongly Noninvertible Functions Are Invertible
Lane A. Hemaspaandra5 
, Kari Pasanen6 and Jörg Rothe7
| (5) |
Department of Computer Science, University of Rochester, Rochester, NY 14627, USA |
| (6) |
Nokia Networks and University of Jyväskylä, P.O. Box 12, FIN-40101 Jyväskylä, Finland |
| (7) |
Abteilung für Informatik, Heinrich-Heine-Universität Düsseldorf, 40225 Düsseldorf, Germany |
Abstract
Rabi, Rivest, and Sherman alter the standard notion of noninvertibility to a new notion they call strong noninvertibility,
and show—via explicit cryptographic protocols for secret-key agreement ([RS93,RS97] attribute this to Rivest and Sherman) and digital signatures [RS93,RS97]—that strongly noninvertible functions would be very useful components in protocol design. Their definition of strong noninvertibility
has a small twist (“respecting the argument given”) that is needed to ensure cryptographic usefulness. In this paper, we show
that this small twist has a large, unexpected consequence: Unless P = NP, some strongly noninvertible functions are invertible.
Keywords Computational and Structural Complexity
Supported in part by grants NSF-CCR-9322513 and NSF-INT-9815095/DAAD-315-PPP-gü-ab. Work done in part while visiting Julius-Maximilians-Universität
Würzburg.
Supported in part by grant NSF-INT-9815095/DAAD-315-PPP-gü-ab and a Heisenberg Fellowship of the Deutsche Forschungsgemeinschaft.
Work done in part while visiting the University of Rochester.
References secured to subscribers.