Collision-resistant hash-shuffles on the reals
Abstract
Oneway real functions are effective maps on positive-measure sets of reals that preserve randomness and have no effective probabilistic inversions. We construct a oneway real function which is collision-resistant: the probability of effectively producing distinct reals with the same image is zero, and each real has uncountable inverse image.
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$) for all $n$. In this way we can talk about functions from $2^\omega$ to $2^\omega$ and the partial computable ones. Let $\mathsf{ML}$ be the collection of all Martin-Löf random reals.
Given functions $f,g$, $g$ is an \textbf{probabilistic inversion} of $f$ if
$$\mu({(y,r):f(g(y,r))=y})>0.$$
We define partial computable $f$ to be oneway if it is random-preserving ($f(\mathsf{ML})\subseteq\mathsf{ML}$) and it has no partial computable probabilistic inversion.
Given functions $f,g$, we also consider
$${r:g(r)=(x,z),x\neq z,f(x)=f(z)}$$
which are the random oracles on which $g$ can produce siblings of $f$.
We define partial computable $f$ to be collision-resistant if no partial computable $g$ can produce siblings of $f$ with positive probability.
Theorem. There exists a total computable $f$ which is
- a random-preserving oneway surjection
- collision-resistant and nowhere injective
and for each random $w\not\geq_T 0’$,
- $w$ does not compute any probabilistic inversion of f
- $w$ does not compute any pair of f-siblings.
Theorem. For each noncomputable c.e. set $A$ there is a total computable nowhere injective surjective function $f$ such that
- f is oneway and collision-resistant relative to almost all oracles
- f is not oneway and not collision-resistant relative to $A$.
Links and resources
