How to prove inconstructable cryptographic scheme?

Question

Hi,

I realize this question might not be that programming related, and that it by many will sound like a silly question due to the intuitive logical fault of this idéa.

My question is: is it provable impossible to construct a cryptographic scheme (implementable with a turing-complete programming language) where the encrypted data can be decrypted, without exposing a decryption key to the decrypting party?

Of course, I can see the intuitive logical fault to such a scheme, but as so often with formal logic and math, a formal proof have to be constructed before assuming such a statement. Is such a proof present, or can it easely be constructed?

Thank you for advice on this one!

Edit: Thank you all for valuable input to this discussion!

Answer 1

No; but I'm not sure you're asking what you want to be asking.

Obviously any person who is decrypting something (i.e. using a decryption key) must, obviously, have the key, otherwise they aren't decrypting it.

Are you asking about RSA, which has different keys for decrypting and encrypting? Or are you asking about a system where you may get a different (valid) result, based on the key you use?

Answer 2

Yes.

Proof: Encryption can be considered as a black box, so you get an input and an output and you have no idea how the black box transforms the input to get the output.

To reverse engineer the black box, you "simply" need to enumerate all possible Turing machines until one of them does produce the same result as the one you seek.

The same applies when you want to reverse the encryption.

Granted, this will take much more time than the universe will probably live, but it's not impossible that the algorithm will find a match before time runs out.

In practice, the question is how to efficiently find the key that will decode the output. This is a much smaller problem (since you already know the algorithm).

Answer 3

YES!!! This already exists and are called zero knowledge protocols and zero knowledge proofs.

See http://en.wikipedia.org/wiki/Zero-knowledge%5Fproof

However, you have to have a quite a good background in mathematics and crypto to understand the way it works and why it works.

One example of a zero knowledge protocol is Schnorr's ZK protocol

Answer 4

If by "decrypted" you just mean arrive at the clear text in some way, then it is certainly possible to create such a cryptographic scheme. In fact it already exists:

Take an asymmetric encryption scheme, eg: RSA where you have the public key but not the private key. Now we get a message that's been encrypted with the public key (and therefore needs the private key to decrypt it). We can get the original message by "brute force" (yes, this'll take an enormously long time given a reasonable key/block size) going through all possible candidates and encrypting them ourselves until we get the same encrypted text. Once we get the same encrypted text we know what the decrypted text would be without ever having discovered the private key.