6533b859fe1ef96bd12b7f6e

RESEARCH PRODUCT

If P ≠ NP then Some Strongly Noninvertible Functions Are Invertible

Lane A. HemaspaandraKari PasanenJörg Rothe

subject

Discrete mathematicsComputational complexity theorybusiness.industryP versus NP problemCryptographyCryptographic protocollaw.inventionInvertible matrixDigital signaturelawTwistbusinessTime complexityMathematics

description

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.

yearjournalcountryeditionlanguage
2001-01-01
https://doi.org/10.1007/3-540-44669-9_17