Let's suppose I design a block cipher such that, with a randomly generated key 
and 10,000 known plaintexts, I can recover that key.  For this to be useful in 
a world with relatively sophisticated cryptanalysts, I must have confidence 
that it is extremely hard to find my trapdoor, even when you can look closely 
at my cipher's design.   

At this point, what I have is a trapdoor one-way function.  You generate a 
random key K and then compute E(K,i) for i = 1 to 10000.  The output of the 
one-way function is the ciphertext.  The input is K.  If nobody can break the 
cipher, then this is a one-way funciton.  If only I, who designed it, can break 
it, then it's a trapdoor one-way function.  

At this point, I have a perfectly fine public key encryption system.  To send 
me a message, choose a random K, use it to encrypt 1 through 10000, and then 
send me the actual message encrypted after that in K.  If nobody but me can 
break the system, then this cipher works as my public key.  

The assumption that matters here is that you know enough cryptanalysis that it 
would be hard to hide a practical attack from you.  If you don't know about 
differential cryptanalysis, I can do the master key cryptosystem, but only 
until you learn about it, at which point you will break my cipher.   But if you 
can, say, hide the only good linear characteristics for some cipher in its 
S-boxes in a way that is genuinely intractible for anyone else to find, then 
you have a public key cryptosystem. You can publish the algorithm for hiding 
new linear characteristics in an S-box--this becomes the keypair generation 
algorithm.  The private key is the linear characteristic that lets you break 
the cipher with (say) 10000 known plaintexts, the public key is the cipher 

The cryptography mailing list

Reply via email to