Why can't uncomputable functions be adapted to serve as theoretically perfect one-way functions? This has been bugging me for years, and I've never been able to track down an explanation of why it wouldn't work.
There are many possible variations on the same general theme; the one that seems most straightforward to me is to take the data you want to hide and use it to seed some large but manageable number of Turing Machines with random rulesets.
You let them run for up to $t$ steps, and then see which ones have halted by that point. Even done in massive parallel, it would fall clearly into $P$ territory. Say you ran $1024$ TMs; if you give each an index, and then toggle the corresponding bit depending on whether each one halts, you get a $1024$-bit number which is provably non-invertible, since any $P$ inverse function would require oracles or some other cheat. Ideally, the best an adversary could do is attack it in $O(2^n)$ time by brute force.
I mean, I do see some obstacles here. Taken exactly as written, this would probably be terrible, since the broader statistical behavior of a group of truly pseudorandom TMs is pretty regular inasmuch as they mostly halt quickly, following along a fairly well-behaved curve. Although even if they could anticipate that roughly $700$ bits would be $1$s, would that help that much?
Really, I know very little about cryptography, so I don't know if that would render this approach useless, or the fact that an adversary would have no way of knowing which machines would halt would mean it remained fairly robust. If the adversary is unable to access your initial data, and if that data is suitably hashed and used to set up the specific choice, design, and order of TMs, that seems to me like it could still work...
And if not, there are lots of more sophisticated ways to approach it, I'm sure. You could require the TMs to run a family of algorithms like Collatz or some highly chaotic processes to decrease the statistical predictability of the whole system. Instead of using halt-or-no-halt as your bit, you could grab a more arbitrary bit from mid-execution in each TM. Or, you could use an entirely different computational model, anything that supports undecidable problems: maybe $m$-tag systems or the Post correspondence problem would turn out to be more amenable to what we want.
Does the weak part of the chain lie in the hashing and other initial setup you would need to do to pseudorandomly configure a situation where you could use one of these undecidable problems? That was my only guess; and if so, couldn't you use a single instance of the problem as your initial hashing tool, and stage it out as you gather enough algorithmically random data to do so? Or is there a more fundamental problem here I'm overlooking or unaware of?
Lastly I'd just add that I also realize such an approach wouldn't be able to compete with the systems in general use; my interest is the theoretical angle of whether or not this could potentially serve as a provably perfect one-way function.
Revised idea
Based on the objections raised below, let me propose a more specific scheme along the same lines.
Let $f(x)$ be a function that takes a number $x$ and uses it to define a Turing Machine which is allowed to run for up to $t$ steps, at which point it stops and returns a $1$ or a $0$, based on whether the count of $1$s on the tape is odd or even. The specifics of how it converts $x$ to a rules table shouldn't matter for our purposes.
We use a hashing function that creates a Godel-encoded number from this input, repeated as much as desired. Call this function $g(d,n)$, where $d$ is our input (we'll use "password"), and $n$ is the number of steps to take.
- $g(d, 1)$ would give us $2^{16}$, with $2$ being the first prime and 'p' being the 16th letter of the alphabet (or use unicode, or whatever).
- $g(d,3)$ would give us $2^{16} \times 3^1 \times 5^{19}$, and so on.
- For $n>8$, it would wrap and start from 'p' again, but continue to increase the primes.
Suppose we ultimately want this to yield a 128-bit number. If we use a 64-state 2-symbol TM, and assume we start with a blank tape, said TM will support $2^{128}$ configurations. Let $p$ be the largest prime $< 2^{128}$.
So, we iterate $g(d,i)$ for $i$ up to whatever we want, and record $f(g(d,i) \bmod{p})$ for each value of $i$. Depending on how provably random we want to be, we can let $i$ go as high as we like. We take the average of all the results, and from that, only keep however many of the least significant bits that we need.
As far as I can figure, you should virtually never see the same TM twice. If you enforce a suitably large upper bound for $i$ to go to, would this whole thing taken together approach being a OWF? The $g$ function itself may or may not be vulnerable to some attack (maybe we choose our prime bases less predictably and base them on $d$), but so long as it does its job of suitably pseudo-randomizing the TM, the TM step should be theoretically unassailable to some calculable extent thanks to Rice's theorem and the like.
Even if arbitrary TMs have tapes with even numbers of $1$s more often than average (which is impossible), or more likely, our $g$ function inadvertently causes it to skew towards generating TMs with such a trait, that bias should become less prevalent as $i$ grows, and should disappear completely when you get to the step of taking only the least significant bits.
Again, I'm new to cryptography so may have made an obvious blunder here, and if so please explain. Also, I did throw together a proof of concept test of this in Mathematica, and while I can hardly say whether or not it works, the numbers I was getting back even for adjacent passwords passed the few randomness tests I ran the results through.
