Is there any research about cryptography on nondeterministic Turing machines?

I know it's a highly theoretical topic, but I was wondering if there was any research out there about what cryptography would be like assuming that we had access to nondeterministic Turing machines.

It seems to me like you couldn't have the kind of exponential hardness assumptions that we currently have, but the Time Heirarchy Theorem states that we can create functions that require $O(n^k)$ operations for any arbitrary k, which seems like it's almost as good.

-
I'm not an expert on complexity theory, but I'd expect a straight forward proof that an attack against an encryption scheme on a non deterministic turing machine can't take longer than the legitimate operation on a normal machine. – CodesInChaos Aug 15 '13 at 7:11
BTW quantum computers can only solve problems in BQP efficiently, which is much smaller than MA (the probabilistic equivalent of NP). (At least as far as we know, obviously we can't prove that ATM since we don't even know for sure if P!=NP) – CodesInChaos Aug 15 '13 at 7:15
@CodesInChaos > I'd expect a straight forward proof that an attack against an encryption scheme on a non deterministic turing machine can't take longer than the legitimate operation on a normal machine. If you have a known plaintext, this is certainly the case. One interesting aspect is that the encryption operation itself might be infeasible on a standard machine. – user8007 Aug 15 '13 at 14:04
@CodesInChaos I'm aware that a nondeterministic Turing machine is way more powerful than a quantum computer, but "post-post-quantum-cryptography" wasn't a tag. – user8007 Aug 15 '13 at 14:08
@D.W. Given that there are useful cryptosystems where one plaintext can be encoded as many differnt possible cyphertexts, it seems to me like the natural answer is that if more than one trace accepts, the output from a randomly selected trace is used. – user8007 Aug 20 '13 at 2:33

Summary. The short answer is: Cryptography would be insecure. Any encryption you can do with a non-deterministic algorithm, can be broken (in approximately the same running time) by another non-deterministic algorithm.

Non-determinism is extremely powerful. If you give everyone access to non-determinism, then secure encryption becomes impossible: the cryptanalysts win.

The Time Hierarchy Theorem isn't relevant here. Roughly speaking, it says that we can make encryption take as long as we want. However, that's not the relevant question. The relevant question is the ratio between the time it takes to break a cryptosystem, divided by the time it takes for legitimate participants to use this cryptosystem. If you give everyone access to non-determinism, this ratio becomes approximately 1. You can use the Time Hierarchy Theorem to make encryption take twice as long, and then cryptanalysis will take twice as long, but that doesn't really buy you anything: if an attacker can break the encryption as quickly as you can encrypt, you have no security.

This might be counter-intuitive, but hey, that's non-determinism for ya: it's not exactly an intuitive subject. I'll work out the technical details below for those interested, but I wanted to start with this summary of the bottom line.

Caveat: my answer is limited solely to encryption beyond the unicity distance (i.e., computational cryptography). The one-time pad remains information-theoretically secure, if you give everyone access to non-determinism: but that's not very helpful, as the one-time pad is not practical to use in most real-life situations. If we're not in the information-theoretic realm -- if the total amount of plaintext to be encrypted under a single key is much larger than the length of the key -- you are hosed; anything you do, will be breakable.

Intuition. Before diving into the technical details, let me give a crude analogy, for those who prefer to avoid the technical stuff. In some really loose way, giving Eve access to non-deterministic computation is like giving Eve the power to read minds.

Suppose we live in a world where everyone can read everyone else's mind. In a society of telepaths, is secure encryption possible? No, it's not possible. No matter what crazy stuff Alice does to encrypt her messages to Bob, it'll always be possible for Eve to read Bob's mind and extract the decryption key (or extract all bits necessary to decrypt). Consequently, in a world of telepaths, encryption as we are familiar with becomes impossible.

What does non-determinism have to do with reading minds? Well, suppose we think that every person's observable behavior is a known (or knowable) function of their internal brain state (or sequence of brain states). Imagine that we observe Zach for a long time. And, suppose we think that, for any set of observed behavior, there's only a single set of brain states that could have given rise to that behavior. Then a non-deterministic algorithm can infer Zach's brain states based upon Zach's observed behavior, merely by guessing Zach's brain state and checking whether it is consistent with Zach's observed behavior. In other words, in some really loose sense, a non-deterministic algorithm can read Zach's mind, based upon his observed behavior. Here Zach's brain state is sorta like the key and other hidden intermediate values/choice bits used by the encryption or decryption algorithm, and Zach's observed behavior is sorta like the set of messages and ciphertexts produced by the encryption scheme. "Reading Zach's mind" is kinda like recovering the key and hidden non-deterministic bits/intermediate values used during encryption or decryption. The restriction that there's only a single set of brain states that are consistent with Zach's observed behavior is roughly analogous to the criteria that we are working with computational cryptography, i.e., beyond the unicity distance.

Now keep in mind that this is an extremely loose analogy. Please don't take it very seriously, and please don't try to draw too many conclusions from it. I know it is full of holes and can be criticized in all sorts of ways. It is only intended for those who don't want to read the technical details and are willing to take it on faith that I know what I'm talking about, and want some gist of the idea without getting overwhelmed with the mathematics. If you start criticizing my analogy, I will have no sympathy whatsoever: I'm just going point you to the mathematics, below.

The technical details. OK, for those who want to see me spell out the justification for my claims in detail, let's dive into the mathematics.

Let's start with a definition of what it means for a non-deterministic algorithm $A$ to compute some value. We say that $A$ can yield output $y$ on input $x$ if, when you run $A$ on the input $x$, there exists some execution where $A$ accepts and outputs $y$.

Equivalently, you can think of $A$ as a deterministic algorithm $A_\text{det}$ with a side input $w$ to represent the choice bits used along the way (every place where $A$ makes a non-deterministic choice between two possibilities, it reads the next choice bit from $w$ and uses that to make the choice). Then, $A$ can yield output $y$ on input $x$ if there exists some $w$ such that $A_\text{det}(x;w)=(\text{accept},y)$. This formulation is easier to think about it, because it relates only to deterministic algorithms.

What about encryption and decryption? Suppose we have non-deterministic encryption and decryption algorithms $E,D$. Recall that for decryption to be correct, we need the decryption of an encrypted message to always return the original message. In other words, if $E(k,m)$ can yield output $c$, and if $D(k,c)$ can yield output $m'$, then we must have $m=m'$. One consequence is that if we fix a ciphertext $c$ and a key $k$, then there is a single unique message $m$ such that $D(k,c)$ can yield output $m$. In other words, if we fix $c,k$ where $c$ is an encryption of $m$, then for every $w$ such that $D_\text{det}(k,c;w)=(\text{accept},\text{something})$, we in fact have $D_\text{det}(k,c;w)=(\text{accept},m)$.

What does it mean to be beyond the unicity distance, i.e., that the total lengths of the messages are much longer than the key length? One consequence is that, if we have a set of known-plaintext/ciphertext pairs $(m_1,c_1),\dots,(m_n,c_n)$ where the sum of lengths of the $m_i$'s is much longer than the key $k$, then there is only a single key that is consistent with all of these pairs. In other words, there is only a single key $k$ such that $D(k,c_i)=m_i$ for all $i$. (OK, technically speaking, there might be multiple such keys, but they'll all be "equivalent", in the sense that if you have multiple keys $k,k'$ that are consistent, then they both decrypt most other messages the same way, so recovering either one counts as a "win" for Eve: either one will let Eve decrypt most of the other ciphertexts she sees. That's a bit of a technical minutae detail which isn't really important here, and which is not specific to anything about non-determinism: it arises in the deterministic setting too. We can safely ignore it, knowing that it can be fixed up if strictly needed.) Nothing about this changes in the presence of non-determinism.

These are all preliminaries and set-up. Now let's get to the proof of the claim I made in the summary. Suppose Eve has $n$ known plaintext/ciphertext pairs, $(m_1,c_1),\dots,(m_n,c_n)$. Here is an attack Eve can use:

1. Eve guesses the key $k$.

2. For $i=1,\dots,n$, Eve runs the decryption algorithm to compute $D(k,c_i)$ and checks whether $D(k,c_i)=m_i$. Note that if the decryption algorithm is non-deterministic, this involves Eve making additional guesses for each $i$ (whatever guesses the decryption algorithm calls for you to make).

3. If there is any $i$ for which $D(k,c_i)\ne m_i$, Eve rejects. Otherwise, Eve accepts and outputs $k$.

If you prefer to see the determinized version of this algorithm, it works like this. $\text{Eve}_\text{det}((m_1,c_1),\dots,(m_n,c_n);w)$ is the following:

1. Parse $w$ as the concatenation $(w_0,w_1,w_2,\dots,w_n)$, where the length of $w_0$ matches the length of the key $k$ and the length of each $w_i$ matches the number of choice bits made during decryption.

2. Set $k=w_0$ (this corresponds to "guessing" the key $k$).

3. For $i=1,\dots,n$, run $D_\text{det}(k,c_i;w_i)$ and checks whether $D_\text{det}(k,c_i;w_i)=(\text{accept},m_i)$.

4. If there is any $i$ for which $D_\text{det}(k,c_i;w_i)\ne (\text{accept},m_i)$, output $\text{reject}$. Otherwise, output $(\text{accept},k)$.

Notice that $\text{Eve}_\text{det}$ is a deterministic algorithm; it's the equivalent of the non-deterministic algorithm for Eve I gave above. Eve breaks the cipher if her algorithm accepts and outputs the correct key. In other words, Eve breaks the cipher if there exists some $w$ where $\text{Eve}_\text{det}((m_1,c_1),\dots,(m_n,c_n);w)$ accepts and for every $w$ where $\text{Eve}_\text{det}((m_1,c_1),\dots,(m_n,c_n);w)$ accepts, $\text{Eve}_\text{det}((m_1,c_1),\dots,(m_n,c_n);w)=(\text{accept},k)$.

So, does this attack work? Certainly $k$ is one possible output of the non-deterministic algorithm for Eve; that much is easy to see. Is it possible that Eve could accept and output some incorrect key $k'$ (where $k'\ne k$)? No, that's not possible, by my discussion about the unicity distance. Remember, there's only a single key $k$ that is consistent with all of the $(m_i,c_i)$ pairs. Also, remember that decryption is correct: given a fixed key and a fixed ciphertext, there's only a single message the decryption algorithm can output (it's not the case that there are multiple possible decryptions). So, if Eve happens to guess some other incorrect key $k'$, then there will be some known plaintext/ciphertext pair $(m_i,c_i)$ where $D(k',c_i)$ outputs $m'$ where $m'\ne m_i$. This means that Eve will reject on all execution traces where she guessed that the key was $k'$.

Consequently, we are guaranteed that Eve's algorithm will output the correct key $k$. And, $k$ is the only thing that her algorithm can output; she'll never output an incorrect key on any accepting execution. So, Eve breaks the encryption scheme. The only facts I used about the encryption scheme are that decryption is correct and that we're beyond the unicity distance, so this break is general.

Parting thoughts on the technical details. Phew. That's a mouthful. I expect that very few folks have followed to this point. Let me just give a little bit of intuition about this proof. I've basically just mimicked the standard proof that any polynomial-time encryption scheme can be broken using an $NP$ algorithm (i.e., non-determinism suffices to break any standard, deterministic encryption algorithm), but making small adjustments to account for the fact that now we want to allow the encryption/decryption scheme to be non-deterministic. It turns out that this doesn't change anything important.

Let me share with you one more analogy. The standard way of defining $NP$ is: a language $L$ is in $NP$ if there is a polynomial-time non-deterministic algorithm that recognizes $L$. Alternatively, we can define $NP$ without reference to non-determinism: roughly, $NP$ is the set of problems where solutions can be recognized in deterministic polynomial time. Slightly more precisely, a language $L$ is in $NP$ if there is a polynomial-time deterministic algorithm $V$ such that $x\in L$ if and only if there exists $w$ such that $V(x;w)=\text{true}$; we say that $w$ is a witness or proof to $x$ being in $L$, and the verifier $V$'s job is to check the validity of the proof.

What if we were to generalize the latter notion, to talk about the set of problems where solutions can be recognized in non-deterministic polynomial time? In other words, what if we defined a complexity class just like $NP$, except where now $V$ is allowed to be a non-deterministic algorithm (so you get to use non-determinism in checking the proof)? Here's the cute answer: what you get is no larger than $NP$; you get exactly $NP$.

The connection to cryptography is that verifying you've broken the cryptosystem correctly (verifying that you have the correct key) is analogous to the role of the verifier $V$ in the definition of $NP$. Even if you allow encryption and decryption to be polynomial-time non-deterministic algorithms (corresponding to allowing $V$ to be a polynomial-time non-deterministic algorithm), non-determinism still suffices to break everything (corresponding to the fact that $NP$ is still enough to recover all the corresponding languages). OK, I realize that maybe this didn't help at all.....

-
So the argument is more or less "a brute-force-attack becomes as cheap as a single try", right? – Paŭlo Ebermann Aug 21 '13 at 20:11
@PaŭloEbermann, thank you, yes, that's a good summary (with the caveat that you have to be able to verify whether your guess was correct or not). – D.W. Aug 22 '13 at 0:45

I don't know of any specific research in this area. However, I suspect that D.W.'s answer is not correct; it appears that if Alice and Bob have NTM's, they can communicate securely, even if Eve has one as well.

Here's a sketch of an encryption algorithm that appears to be secure against adversaries with NTM's, assuming:

• Alice and Bob both have NTMs

• Alice and Bob share a secret key $K$

• $H$ is a hard to invert (with a DTM turing machine) hash function that generates an $n$ bit output.

Now, when Alice wants to send a message to Bob, she:

• Selects a nonce $N$

• Generates a sequence of bits with this algorithm (with $i$ being the index of the bit):

• Determine if there is an $n$ bit value $M$ with $0 = H( K | N | i | M )$. Alice can do this because she has a NTM; the NTM guesses the value of $M$, and value validates the guess by computing $H( K | N | i | M )$ and comparing that result to 0 in polynomial time.

• If there is no such solution, bit $i$ is 0; if there is (at least) one solution, bit $i$ is 1.

• Given the sequence of bits, perform von Neumann debiasing; that is, consider the bits as consecutive pairs, with this mapping:

• The bit pair (0, 1) gets translated into 0
• The bit pair (1, 0) gets translated into 1
• The bit pairs (0, 0) and (1, 1) are discarded.

Once we have the debiased stream of bits, exclusive that into the plaintext to form the ciphertext. She sends the nonce and the ciphertext to Bob (and Eve).

To decrypt, Bob runs the same procedure (using his copy of $K$).

Now, Eve doesn't have $K$. We assume she knows the plaintext, and so is able to rederive the debiased stream. However, it's not at all clear how she would proceed after that (even with her NTM); her NTM can generate and validate a guess, as long as the process of validating that guess takes polynomial time. She can guess $K$, however it's not clear how she would generate the rest of the guess that would allow any meaningful validation; that guess would appear to need something that can prove (in polynomial time) that $0 = H( K | N | i | M )$ does not have a solution for certain values $i$, and it's not clear how a short guess would be able to demonstrate that.

-
@D.W.: actually, your proposed algorithm for Eve to find $K$ doesn't appear to work; her NTM can make a guess of $K$; however it then has to verify that guess (and verify it on a DTM; that's part of the definition of a NTM). That is, she can't use nondetermanism while doing the verification. Now, her NTM can make guesses in addition to the value of $K$; however it's not at all clear what additional guesses would help. – poncho Aug 20 '13 at 20:35
@D.W.: How does Eve verify a guess that a particular bit in the un-debiased string was a '0'? That is, for a specific value of $i$, there were no non-determanistic guesses that made the relation hold? – poncho Aug 20 '13 at 21:18
Oops, forget everything I wrote earlier! I just figured out what I missed. Your example is no good because Bob cannot decrypt. Try writing out a non-deterministic algorithm Bob can use to decrypt. To see this, just try writing a non-det. algorithm Bob can use to compute a single biased bit $i$. Make sure you remember the rules of non-deterministic algorithms: you have to specify the criteria under which Bob accepts or rejects. What is the condition under which Bob accepts and outputs that $i=0$ (that there is no solution $M$)? Try to write it down -- you'll see you are stuck. (cont.) – D.W. Aug 20 '13 at 22:05
(cont.) It is easy to find a condition under which Bob accepts and outputs that $i=1$, but no amount of non-determinism is enough for Bob to accept and output that $i=0$. (There's no single guess that lets Bob verify that there is no solution to your equation. If Bob guesses one value of $M$ and find it isn't a solution to the equation, he has no idea whether some other value of $M$ might be a solution.) Encryption has the same problem. So, your example is not valid: neither encryption nor decryption can be computed using a non-deterministic algorithm. – D.W. Aug 20 '13 at 22:06
@D.W.: I'm assuming that the NTM always returns an output, whether it is 'accept' (if there is at least one path to an 'accept' state), or 'reject' (if there is no such path). You appear to assume that if there is no such path, you don't get any usable output (not even a lack of output; that can be distinguished from an 'accept' output). If you grok polynomial hierarchies (complexity theory), I'm trying to create an encryption algorithm which is in $P^{NP}$ with the key, and $NP^{NP}$ without the key. – poncho Aug 20 '13 at 22:34