# Re: [Cryptography] Opening Discussion: Speculation on "BULLRUN"

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

--John
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography