6533b7d9fe1ef96bd126c186

RESEARCH PRODUCT

If P≠NP then some strongly noninvertible functions are invertible

Jörg RotheLane A. HemaspaandraKari Pasanen

subject

Discrete mathematicsGeneral Computer ScienceComputational complexity theorybusiness.industryP versus NP problemOne-way functionsCryptographyOne-way functionCryptographic protocolTheoretical Computer Sciencelaw.inventionComputational complexityInvertible matrixDigital signaturelawAssociativityCryptographyStrong noninvertibilitybusinessAssociative propertyMathematics

description

AbstractRabi, 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 (Rabi and Sherman attribute this protocol to Rivest and Sherman) and digital signatures (Rabi and Sherman)—that strongly noninvertible functions are 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 consequence: unless P=NP, some strongly noninvertible functions are invertible.

yearjournalcountryeditionlanguage
2006-10-01Theoretical Computer Science
10.1016/j.tcs.2006.05.022http://dx.doi.org/10.1016/j.tcs.2006.05.022