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.
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:


Eve guesses the key $k$.
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).
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:


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.
Set $k=w_0$  (this corresponds to "guessing" the key $k$).
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)$.
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.....