Links

̶
Adam I. Gerard
ISU
NIU
CS MS TBD

One-Way Functions

Thoughts on this important and elusive concept in Computer Science.

Apparently, the [mathematical] proof of a One-Way Function is an open problem in mathematics and computer science!

Below, I'll discuss a few related-concepts and see if we can tease out some interesting intersections.

Trap Doors

An operation that contains some secret or unknown aspect to calculate the output from the input.

  1. A password.
  2. A purely random variable.
  3. A salt or hash.

To calculate the input from the output is either impossible or extremely expensive without having the secret.

Chained Trap Doors

Chaining trap-doors can also increase the security of some operation and reduces the likelihood of breach.

Temporal Trap Doors

A trap-door with a time-dependent variable such that any attempt to solve the cipher at a current time T would be impossible (since the solution would be solved in T+1 time rendering the T time solution incomplete).

Certain two-factor security implementations satisfy these requirements (provided that any chosen authentication device is secure) - the presence of device-specific security vulnerabilities like SIM Swapping defeats these constraints.

A trap-door with a time-dependent variable such that any attempt to solve the cipher at a future time T would be mitigated against (either impossible or very challenging).

Brute force scenarios fall into this category too.

Shared Secrets

Where, like 2FA, multiple authentication pieces must be present to unlock the secured resource.

Schemes like Shamir's Shared Secret require multiple people to be supply some necessary authentication component known only to them.

Randomly Defined Functions?

What about randomly defined functions? E.g. -

  1. Relies on a secret (in manner similar to a standard trap door).
  2. Definition of a function itself is subject to permutation.
  3. Second function modifies the background assumptions of the first.

Examples:

  1. The initial function would remain invariant while the background structure undergoes transformation (by way of the second). Consider a propositional password where p ⊢ ¬¬p plays a critical role in encryption and decryption. Then, the background logic shifts to intuitionism.
  2. In another case, the function definition might be altered so that, at some future point in time, the function (as it exists with respect to the operation at hand) has a completely different profile. In this case, a mathematical function equivalent to the first would still exist but would not be identified with the current one.

Entanglement

Quantum trap doors disturb an entangled quantum state effectively signaling that the protected information has been accessed.

Anti-symmetric Functions

Functions that are logically non-symmetric (which requires rethinking some fundamental presuppositions about functions).

One physical implementation: functions whose cryptographic key changes on every keystroke. This is, however, not quite what I have in mind. Something stronger.

Posthuman Languages

Formally: If function f is expressed in a language L and undergoes transformation into f+ in a language L+ such that f+ cannot be recovered in L, then the mapping from f to f+ is a one-way function.

Inner Semantics

[I assert that]Inner Semantics also produces one-way functions:

  1. Sentence S to the assignment A of its meaning, proposition P.
  2. The assignment A of meaning, P, to a sentence, S, is one-way (by definition).

The inverse of A recovers the association of P to S but the assignment operation itself cannot be meaningfully inverted (exhibiting a zero probability chance of inversion).

Note: the meaning and the sentence can be derived from each other.

Note: Better formalization (and the possibility of good proof thereby) is still required to follow-up on this intuition.

Contents