[146803] in cryptography@c2.net mail archive
Re: [Cryptography] Opening Discussion: Speculation on "BULLRUN"
daemon@ATHENA.MIT.EDU (John Kelsey)
Sun Sep 8 02:53:15 2013
X-Original-To: cryptography@metzdowd.com
In-Reply-To: <CB8B6D10-D19D-4100-A707-890827A5ABE1@lrw.com>
From: John Kelsey <crypto.jmk@gmail.com>
Date: Sat, 7 Sep 2013 23:45:22 -0400
To: Jerry Leichter <leichter@lrw.com>
Cc: "cryptography@metzdowd.com" <cryptography@metzdowd.com>,
Jon Callas <jon@callas.org>, "Perry E. Metzger" <perry@piermont.com>
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
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
