4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ This question is well beyond my expertise, but by golly do hypercomputational demons sound awesome. $\endgroup$ – Arkenstein XII Nov 29 '18 at 21:40
  • $\begingroup$ Secure public key cryptography is basically out if the adversary has effectively unlimited classical computing power. Realistically you would really need to be looking towards routine use of things like quantum key distribution involving keys at least the full length of the message to overcome this. It is of course still theoretically possible to attempt to guess the key by brute force but with one problem there exists a key that converts the cyphertext into every possible plaintext of the same length and quantum random sources make all equally likely. $\endgroup$ – MttJocy Nov 29 '18 at 23:17
  • 1
    $\begingroup$ Symmetric Key encryption is not safe either. It is only safe if used on messages smaller than the key, and never reusing the key. If you try to encrypt a longer message (like using AES to encrypt something larger than 128 bits), your oracle can generate the 2^128 possible messages and do staticical analysis on those. Any sort of structure in the data will quickly lead them to reject all except the correct key. Thus, the only data that is safe is a string of random digits... which doesn't really need encryption int he first place! $\endgroup$ – Cort Ammon Nov 30 '18 at 1:09
  • $\begingroup$ Ammusingly, that makes Grammarly a weaponizable program! $\endgroup$ – Cort Ammon Nov 30 '18 at 1:10
  • $\begingroup$ Appeal to ephemerals? $\endgroup$ – Giu Piete Nov 30 '18 at 7:17
9
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ While true that computers are deterministic, I can still take a very simple (not even Turing complete) computer, the Enigma Machine, and produce encrypted text that you can not decrypt even with all of the resources of modern computers... despite Enigma Machines being a thoroughly "broken" encryption scheme. I simply have to have a key that is as long as the plaintext, and never use it for any other purpose. If the cyphertext is "crf", then without the key, do you know if the plaintext is "foo" or "bar"? $\endgroup$ – Ghedipunk Nov 29 '18 at 22:01
  • 2
    $\begingroup$ That is -- This question isn't about encryption in general, but is looking for a specific family of encryption and asking if any member of that family has certain properties... I.e., "Can mammals lay eggs" usually gets met with "no." But "Can semi-aquatic, duck billed mammals lay eggs" gets met with a yes. $\endgroup$ – Ghedipunk Nov 29 '18 at 22:03
  • $\begingroup$ @Ghedipunk Semi-aquatic, duck billed 'mammals' are not really mammals; they're monotremes. (common mistake) So the answer is still no. The comment you make about non-Turing complete machines isn't about encryption, it's about ciphers, and having hidden, agreed meanings for specific phrases or even letters is a cipher, not an encryption. The Question IS about encryption generally, the title even asks specifically about public key encryption. Also, while I acknowledge your point in regards to foo and bar, messages of any size are easily cross-referencable for word sequences that make sense. $\endgroup$ – Tim B II Nov 29 '18 at 22:51
  • 1
    $\begingroup$ @Ghedipunk That would be called a One Time Pad I believe. The most secure form of encryption and also the one that relies on humans the most. The issue with a one time pad is the decryption stage. If I send a message encrypted by someone with a One Time Pad, I still need to send the One Time Pad which is just as vulnerable now. I can't encrypt a One Time Pad with another One Time Pad, since I need to send the new One Time Pad again. They simply shift the encryption problem to the Key which now needs to be securely transferred which is usually a bigger risk. $\endgroup$ – Shadowzee Nov 29 '18 at 22:58
  • $\begingroup$ I get the need for being pedantic and precise... but... using a cipher and having hidden, agreed meanings for specific units of information to hide it from eavesdropping is encryption in all definitions of the word. Just putting it in a hidden form, regardless if how you do it, is encryption. And yes, the One Time Pad is most definitely NOT an example of private key cryptography, but it IS an example of something that fits within this answer: An algorithm that uses deterministic values to produce encrypted messages. The first word of this answer is correct. The rest of it is [continued...] $\endgroup$ – Ghedipunk Nov 29 '18 at 23:11
0
$\begingroup$

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.

$\endgroup$

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.