Crypto-making vs Crypto-breaking

[Eric Cordian]

Ben Laurie wrote:

> Such a machine cannot exist. Proof:

> Let O be an oracle such that any encrypted message, E can be decrypted
> by O. That is, if E=Enc(M), then O(E)=M. Now, encrypt a message I as
> follows.

Let S be the set of all bitstrings.  Let, C, the set of all ciphers, be
the set of all finitely denumerable primitive recursive injections of S
into itself.  Let O, our oracle, associate with each M in C a map M', from
range(M) onto S, such that for x,y in S and y = M(x), x = M'(y).

> If bit 0 of I (I_0) is 1, then choose E_0 s.t. the MS bit of O(E_0)=0
> If bit 0 of I is 0, then choose E_0 s.t. the MS bit of O(E_0)=1

> Then for each subsequent bit, proceed as follows:

> If I_n is 1, then choose E_n s.t. O(E_n||E_{n-1}||...E_0) has an MS
> bit that is 0.
> If I_n is 0, then choose E_n s.t. O(E_n||E_{n-1}||...E_0) has an MS
> bit that is 1.

> Then the encrpytion of I is X=E_N||E_{N-1}...||E_0, and, by
> construction, O(X) != I.

Bzzzzzzzzzzzzzzzt.  While we may without loss of generalization view O as
acting on bitstrings, by encoding the ciphers and their inverses, neither
the domain nor range of O is going to be the set of all bitstrings.  
Ergo, we can not simply "choose" things based on the application of O to
bitstrings we arbitrarily construct.

Your proof can be fixed, of course, but I think you'll find that it boils
down to the usual diagonal argument that we can find a function on the
integers which is not primitive recursive, by ordering the countable set
of primitive recursive functions, and defining a new function that is for
an input of N, something other than the output of the Nth function for N.

As long as we restrict the ciphers to a countable set of "reasonable" 
computer programs which halt for all inputs and don't have neverending 
descriptions, the oracle exists, and your proof does not.

> Cheers,

Cheers,

-- 
Eric Michael Cordian 0+
O:.T:.O:. Mathematical Munitions Division
"Do What Thou Wilt Shall Be The Whole Of The Law"