Can any kind of public-key encryption hold up against a logically omniscient oracle?

Question

"Logical omniscience" can be defined for these purposes as a form of hypercomputation in which all Turing-computable functions can be computed in constant time. Practically speaking, this means that if you have all of the information that is logically necessary to solve a problem, you can effectively instantly know the answer to that problem.

Things like RSA are clearly out--they depend on certain theoretically-computable functions (like modular factorization) to be difficult to actually compute in practice, and fall apart under much weaker hypercomputation models. Other models, like elliptic-curve cryptography, are more robust than RSA, but still would fail against a logically omniscient oracle with infinite computing power.

Meanwhile, symmetric private key cryptography should still be mostly safe, because there is no algorithm to compute a single unique plaintext-key pair from a given ciphertext. An attacker could decide what they want the plaintext to be, and calculate what they key would've have to have been to get that, but that doesn't actually give you any information about what the original plaintext and key actually were. You can only build up statistical arguments if you have multiple messages that someone had the poor sense to encrypt with the same key, which is no different from how things work in the real world anyway.

So, are there any public-key encryption schemes that would be safe against a logically omniscient oracle? Where breaking them is not merely a matter of not having enough computational power, but for which a deterministic algorithm simply doesn't exist?

Background reason for the question: I have a world in which "demons" can be contacted to enact magic; one of their abilities, which is integral to the kind of magic they can perform, is hypercomputation, such that they can solve problems that are well beyond the technological abilities of the people summoning them (thus providing a justification for the risk of consorting with demons). However, making them too powerful may end up ruling out some magi-tech applications I want (like access to strong cryptography), so I'm trying to figure out what the maximum level of hypercomputation is that I can give to the demons without breaking the setting.

Answer 1

If this omniscient being is capable of infinite computing power, then public key encryption will fail.

all public key schemes are susceptible to a "brute-force key search attack"

Public-key cryptography: Weaknesses

Answer 2

A computer with such an oracle can solve NP-complete problems in polynomial time. Decryption is NP-complete, since you can verify a proposed solution in polynomial time. Therefore, with the oracle, you can break any normal encryption (not just public key) efficiently.

For better visualization, picture you bringing your laptop to Delphi. You ask the oracle what the key is. She deeply inhales the gasses and then rattles of a string of hex digits. You can plug that in and verify it easily, and get the output. Since you can verify whether the key is the right one or not (the chance that a cipher block can decipher into two reasonable plaintexts is almost zero), that allows the oracle to be a little bit infallible.

This will not work for a one-time pad, since a ciphertext can be decrypted into literally any plaintext you like, so you can't verify that it's the correct answer. You might as well just ask the oracle what the message says.

Answer 3

No.

Computers are algorithmic engines, pure and simple. They can't perform non-algorithmic operations. There are some input vectors (like hardware random number generators) that are capable of introducing randomness as an input, but not randomness as a process, and even that doesn't help with encryption.

Ultimately, encryption has to be deterministic, because if it isn't, then you can't decrypt. What encryption does is create a complicated set of steps to obfuscate a message in some form, usually based on a key of some type. The idea is that you give the key to the intended recipient, and they reverse the process you used to obfuscate the process. Without the key, the obvious attack vector is guessing the key, or in other words a brute-force attack. All modern encryption methods try to make that as hard as possible, but the only way to make it impossible is to make it so the intended recipient can't open the message either.

Put simply, if someone can read the message with the key, then someone with an infinite supply of computational power can read the message without the key. It's just a question of how badly they want the information. As such, encryption is about adjusting the effort/reward ratio to a point where for most people, it's just not worth the effort.

Answer 4

No; by definition, the public key can be generated from the private key and vice versa, with the security depending entirely on how hard it is to do the latter compared to the former. If all problems are equally hard, this can't be true.

It's always possible to encrypt an arbitrary message with the public key, and then use brute force to find a key that decrypts your message correctly. If there is a one-to-one correspondence between public and private keys, you're already done. But perhaps there is some algorithm where a public key corresponds to a very large number of private keys for any given message; in that case, you still don't know which is the "universal" private key. But you can just repeat the procedure with different plaintexts until there is only one candidate left, and again, your machine can by definition do this in no time.