Computable one-way functions on the reals
Abstract
A major open problem in computational complexity is the existence of a one-way function, namely a function from strings to strings which is computationally easy to compute but hard to invert. Levin (2023) formulated the notion of one-way functions from reals (infinite bit-sequences) to reals in terms of computability, and asked whether partial computable one-way functions exist. We give a strong positive answer using the hardness of the halting problem and exhibiting a total computable one-way function.
Content Overview
We regard a Turing functional $f$ as a (possibly partial) map (function) from $2^\omega$ to $2^\omega$, that is, $f(x)$ is the real $y$ such that $y(n)=f^x(n)$ (the output of $f$ with oracle $x$ and input $n$).
Given functions $f,g$, we say that $g$ inverts $f$ on $y$ if $f(g(y))=y$, that is, $g$ outputs one of the preimage of $y$. We say that $g$ is an inversion of $f$ if $g$ inverts $f$ on any $y\in{\rm ran}f$.
A function $f$ is random-preserving if it maps randoms to randoms.
Theorem. There is a random-preserving total surjective Turing functional $f$ such that any inversion of $f$ computes $\emptyset’$.
We may also give $g$ the access to a random oracle $r$. By letting $$L_{f,g}={(y,r):f(g(y,r))=y},$$ Levin defined a Turing functional $f$ to be one-way if $\mu(L_{f,g})=0$ for all Turing functionals $g$, and asked if there is a random-preserving one-way function. We give a positive answer.
Theorem. There is a random-preserving total surjective Turing functional $f$ such that any function $g$ with $\mu(L_{f,g})>0$ computes $\emptyset’$.
We then characterize the extent that a one-way (or, in other sense, hard to invert) functional fails to be oneway.
Theorem. If a Turing functional $f$ is total one-way, then $f^{-1}(y)$ is uncountable for almost every $y\in 2^\omega$.
A function is two-to-one if $|f^{-1}(y)|\leq 2$ for all $y\in 2^\omega$.
Theorem. There is a random-preserving total surjective two-to-one Turing functional $f$, such that any incomplete $g$ fails to invert $f$ with positive probablity.
Links and resources
Relevant contents
