Ray Dillinger writes:
In the interest of making some news if you don't like the news you're getting, I present -- the Country Mile Cipher. Algorithm details available (for now) on
http://www.sonic.net/~bear/crypto/countrymile.html
This is a stream cipher based on the Blum-Blum-Shub pseuodo- random number generator -- and on work done more recently by Ronald Rivest, who "digitally sealed" a message that he expects to take 30 years of continuous computing to unscramble.
Your idea is to take BBS as a stream cipher, use a value based on a secret short key as a starting point, and then cycle it potentially a whole lot, millions or billions of cycles or more, before beginning to cipher the message with it. Using the idea of Rivest et all you can cycle BBS forward arbitrarily far in a limited amount of work, if you know the modulus factors. So you can encrypt with little work, while making the decryptor do an arbitrary amount of work even if he knows the key. You've combined the idea of time lock crypto with an encryption function. It's not clear these two ideas go all that well together, like the SNL product that was both a floor wax and a dessert topping. Usually you either want to encrypt, in which case you want to make it easy to decrypt for the guy who knows the key, or you want to time-lock, in which case you want to control how hard it will be to find the key. There don't seem to be that many cases where you want to allow decryption but only if you both know the key and are willing to put in a lot of time. Even if you did want to do that, you could just use Rivest's time lock to hide a key which then gets combined with your short key to produce the actual key to the message. Along these lines your own idea could be simplified; don't encipher the whole message using BBS, just encipher a block-cipher key and use 3DES or similar to encipher the message. You might also want to take a look at the paper by Dan Boneh and Moni Naor from Crypto 2000, http://crypto.stanford.edu/~dabo/abstracts/timedcommit.html. They have a similar idea but came up with an application for it in fair contract signing (where one party should not end up with the signature on a contract unless the other party does too). For their application they need to be able to encrypt a message such that it can only be decrypted with a specified large amount of work. However they must be able to reveal the encrypted message and prove that the decryption was accurate, using a small amount of work. This could be done in your scheme simply by revealing the modulus factors (the "long key") but they want to reuse the modulus so they use some fancy zero knowledge proofs.