8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Why is this question drawn in the negative? Do you have any source that claims that this cannot be done? If so, please point out the source. I'm not 100% either if "uncomputable function" is the right term, but that could just be me. $\endgroup$ – Maarten Bodewes Jun 1 at 11:20
  • 1
    $\begingroup$ You see "computable function" used a lot more, but uncomputable function (or undecidable problem, closely related) I think are more or less correct. And I have no source that says this can't be done; it just always seemed like an obvious thing to try, so I figured there must at least be a paper or two about it somewhere. And with the level of interest in $P=NP$ especially, I figure it's always safe to assume somebody else has beaten you to any idea that's any good. $\endgroup$ – Trev Jun 1 at 11:27
  • 1
    $\begingroup$ The "random rulesets" is problematic on a level beyond what this answer states. These rulesets must be public per the (2nd)) Kerckhoffs principle. Then it becomes possible for a PT algorithm to invert the proposed OWF bit per bit by trying sequential inputs until the output is as desired, then re-assemble the inputs found, breaking the OWF defining property. I'm not stating this can't be fixed, only that it must. $\endgroup$ – fgrieu Jun 1 at 16:52
  • 2
    $\begingroup$ Okay... the way I pictured it, the data I'm encrypting would act as the seed for generating the TMs and their behavior. Since I am allowed to keep my data secret, surely I am also allowed to keep the specifics of the running TMs out of view of adversary? He is welcome to see all the code before the fact, whereby it gets generated given some input, in general, but once I actually take my data and start hashing it and spinning up TMs, must those specific instances be inspectable by an adversary to comply with Kerckhoff? $\endgroup$ – Trev Jun 1 at 17:19
  • 2
    $\begingroup$ By adding the step limit, you convert your "uncomputable function" actually into a computable one (with partially different values). (This doesn't say anything against your idea, just the title.) $\endgroup$ – Paŭlo Ebermann Jun 1 at 22:08
22
$\begingroup$

The main fundamental issue with this approach, as with approaches that attempt to base cryptography on NP-completeness, is that the hardness you refer to is worst case hardness, and not average case hardness. In particular, the fact that the halting problem is hard merely means that for every algorithm there exists a TM $M$ for with the algorithm fails upon. It does not mean that it won't succeed on almost all input TMs. This is the same when looking at NP-hard problems. One-way functions need to be based on average case hardness, since they need to be hard to invert on a random input, and it needs to be the case that every algorithm will fail almost always.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Right, but in what way does this not meet that those criteria? I'll grant that any given random TM is very unlikely to do anything special, but taken in a modest group (say, that 1024), would it be possible to have an inverse function which had any significant chance of guessing exactly which TMs halted or not? It seems to me like that is the average case, which in turn is always very close to the worst case. $\endgroup$ – Trev Jun 1 at 11:21
  • $\begingroup$ I'd add that if they don't have access to any helpful specific information, then even if you don't bother normalizing your bits, and even if they can guess that they'll have about 700 $1$ bits to choose out of 1000, you're still looking at odds of $1$ in $10^{260}$ or thereabouts of guessing the data (which you would still have to run to verify)... surely a sufficiently bad average case? $\endgroup$ – Trev Jun 1 at 11:35
  • $\begingroup$ Sorry, one more comment, more to your point: the main idea behind using an uncomputable function is for this very reason. If you use something like an approximation of Chaitin's $\Omega$ constant, it actually guarantees that no algorithm can perform better than random, regardless of any other consideration... well, up to however well you can approach it yourself when encrypting your data. $\endgroup$ – Trev Jun 1 at 11:49
3
$\begingroup$

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 𝑡 steps, and then see which ones have halted by that point. [...] 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 [...]

I think I may be misunderstanding your idea here. Let me paraphrase:

The user inputs a string; let's say "password". We seed 8 Turing machines with the user's input: one with p, one with a, one with s, another one with s, and so on. Then we run each machine for 1000 steps. Let's say that machines p, s, and r halted in that time, and the rest didn't halt. So now you have an 8-bit string 10110010. And somehow you're claiming that this is hard to invert?

It seems trivial to invert. As an attacker, I can easily find a preimage that gives me 10110010. I just put random inputs through the 1000-step process until I find one that halts and one that doesn't; let's say, p halts and q doesn't. Then a valid preimage of 10110010 is pqppqqpq.

Remember, it doesn't matter if I can't invert your hash function. What matters is whether I can produce a collision. If you just want a function that's not invertible, you should use f(x) = 0 for all x — using that hash function, there's clearly no way I could ever figure out your password just from knowing that its hash value was 0! But "non-invertibility" is not the important thing, in a hash function. What's important is resistance to collision attacks.


Now, you did say that somehow we've got to take the user's 8-character password and expand it out to 1024 random Turing machines. You didn't describe how to do this non-trivial operation. The operation is technically known as key stretching. Sounds like you're relying on the key-stretching operation (which you did not specify) for literally all of the security properties of your algorithm. Which means that all this stuff about Turing machines and running for 1000 steps is completely superfluous.

| improve this answer | |
$\endgroup$
  • $\begingroup$ It looks like I may have been fundamentally mistaken about OWFs; I thought that to defeat them, it was necessary to be able to construct an inverse function that would give you, in your example, $f^{-1}(10110010)=\text{password}$. So if it's sufficient just to find a different input that produces the same output as your secret, then yeah, my specific example needs rethinking. That said, the core idea still feels sound: since we have functions that are guaranteed to be effectively random (or more accurately, more random the more computation you put in), that seems like it should be harnessable. $\endgroup$ – Trev Jun 2 at 22:31
  • $\begingroup$ "since we have functions that are guaranteed to be effectively random" — But we don't! This gets back to Yehuda's point: "worst-case incomputable" does not at all mean "average-case unpredictable." The thing about the Halting Problem is that it's literally impossible to get 100% correct; but it's actually pretty simple to get the first 99.9% correct. The hard part is that last 0.1%. :) $\endgroup$ – Quuxplusone Jun 3 at 0:58
  • $\begingroup$ I know, I know, but that's the point! We're not shooting for practicality here, only theoretical soundness. So we employ the halting problem by running enough different programs that we're guaranteed to hit that 0.1% a thousand times, and then only use the least significant 0.1% (or whatever) of our data, or whatever specific numbers we need to make sure our results can leverage that uncertainty. (see revision above) $\endgroup$ – Trev Jun 3 at 1:20
  • $\begingroup$ @Trev "I thought that to defeat them, it was necessary to be able to construct an inverse function" If that were the goal, then using a constant function would solve all of our problems. $\endgroup$ – Maeher Jun 3 at 8:32
  • $\begingroup$ "that we're guaranteed to hit that 0.1% a thousand times" — My "0.1%" was meant metaphorically. In reality (with slight handwaving) there is an infinite sequence of algorithms that efficiently and accurately solve the Halting Problem for 99%, 99.9%, 99.99%,... of programs. * It would probably help your intuition if you actually tried to solve the Halting Problem for a little while. Don't just trust that it's impossible; write a halting-detector program, and then find an input that breaks it, and then improve your program, and then find an input that still breaks it, and so on. $\endgroup$ – Quuxplusone Jun 3 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.