If P \neq NP then Some Strongly Noninvertible Functions are Invertible

Lane A. Hemaspaandra, Kari Pasanen, Jörg Rothe

Abstract

In the realm of computational complexity and cryptography, the relationship between different definitions of "one-wayness" is often more complex than intuition suggests. Rabi, Rivest, and Sherman previously introduced the concept of strong noninvertibility for two-argument (2-ary) functions, a property where a function remains hard to invert even when one of its inputs is revealed. This property is a cornerstone for protocols such as secret-key agreement and digital signatures. However, this paper demonstrates that the specific definition of strong noninvertibility contains a subtle "twist"—the requirement to respect the provided argument—that leads to an unexpected consequence: if $P \neq NP$, then there exist functions that are strongly noninvertible yet easily invertible in the standard sense.

The Problem: Defining One-Wayness for 2-ary Functions

In standard cryptography, a one-way function is defined as being easy to compute but computationally difficult to invert. When dealing with functions that take two inputs, $\sigma(a, b)$, the definition of noninvertibility must be refined.

Rabi, Rivest, and Sherman proposed that a function is strongly noninvertible if, given the output $z$ and one of the inputs (e.g., $a$), it is still hard to find the missing input ($b$). The prevailing intuition was that if a function is "strong" enough to resist an adversary who already possesses half the input, it must certainly be "strong" enough to resist an adversary who knows nothing. This paper sets out to formally test that intuition: Does strong noninvertibility imply standard noninvertibility?

Methodology

The authors employ the tools of structural complexity theory to investigate these definitions. Rather than empirical testing, the paper relies on formal mathematical proofs and reductions based on the standard complexity-theoretic assumption that $P \neq NP$.

  1. Construction: The authors define specific, "honest" (where pre-images are not excessively long), polynomial-time computable 2-ary functions.
  2. Reductions: They use mathematical reductions to prove that if these constructed functions could be inverted in a standard way, it would contradict the properties of the underlying one-way functions or the $P \neq NP$ assumption itself.

Key Insights: The "Backdoor" Strategy

The core of the paper's argument lies in the "twist" within the definition of strong noninvertibility. The definition requires an inverter to find a missing argument that respects the argument already provided. The authors realized that this constraint can be exploited to create a "backdoor."

They constructed functions $\sigma(a, b)$ that behave like one-way functions when an adversary is forced to work with a specific, provided $a$ or $b$. However, if the adversary is only given the output $z$ and is free to choose any pair $(a, b)$ such that $\sigma(a, b) = z$, the function becomes easy to invert. For example, the function might be designed such that setting one input to an empty string ($\epsilon$) allows for a trivial calculation of the other input, even though finding a specific $b$ for a given non-empty $a$ remains hard.

Key Results and Separations

The paper successfully separates several notions of noninvertibility, proving they do not automatically collapse into one another:

  • Theorem 3.2 (The Main Result): If $P \neq NP$, there exists a total, honest 2-ary function that is a strongly one-way function but not a one-way function. This confirms that a function can be hard to invert when one input is fixed, but easy to invert when the adversary has total freedom.
  • Theorem 3.4: Standard one-wayness does not imply strongness. A function can be one-way in the traditional sense but become easily invertible the moment either the first or second argument is revealed.
  • Theorem 3.6: The authors identify "half-strong" functions—those that are hard to invert given the first argument but easy to invert given the second.
  • Theorem 3.7: The paper introduces overstrongness (where finding any preimage is hard even when one input is provided) and proves it is a strictly more restrictive property than strong noninvertibility.

Implications for Cryptographic Design

While these results are framed within worst-case complexity (standard for $P$ vs. $NP$ theory), they offer a stern warning to protocol designers. The "twist" in the definition of strong noninvertibility is actually necessary for the cryptographic protocols it was designed for, such as secret-key agreement. However, designers cannot assume that a function possesses standard one-way properties simply because it has been proven to be strongly noninvertible.

The authors suggest that future research into "overstrongness" may provide a more robust framework for avoiding the "backdoor" paradoxes identified in this study, potentially leading to more secure protocol foundations.

Summary updated

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.
BibTeX
@inproceedings{hemaspaandra2001if,
  author = {Lane A. Hemaspaandra and Kari Pasanen and Jörg Rothe},
  title = {{If P \textbackslash\{\}neq NP then Some Strongly Noninvertible Functions are Invertible}},
  booktitle = {FCT},
  year = {2001},
  doi = {10.1007/3-540-44669-9\_17},
}

Loading related content...

Figure