Which encodings have |encoding key| >> |decoding key|? I'm looking for an encoding scheme that requires a very large encoding key E (>10MB)  and suffices with a relatively small decoding key D (&lt;4kB). One should be able to prove some lower bound on |E| using only knowledge about the scheme, the encoded message and D.

It would be great if the proposed scheme has computationally efficient primitives.

EDIT: A use case for this can be to encourage voluntary disposal of E after encoding a smallish (~1MB) file.
EDIT 2: Ideally, it should not be possible to infer E from D.
Generate a random 2048-bit RSA key.
Generate a random RC4 key.
Seed an RC4 engine with the key generated in step 2. Throw away the first 128 bytes. Output 10MB of data from the RC4 engine (XOR with 0 or don't XOR at all).
E consists of the corresponding public key to the private key generated in step 1 and the first 10MB of data from the RC4 engine in step 3.
D consists of the RSA public key and the RC4 key.
Encryption proceeds by XORing the data to be encrypted (padded to a multiple of 10MB) with the 10MB RC4 output and then encrypting that with the RSA public key.
Decryption proceeds by regenerating the 10MB of RC4 data from the seed and reversing the encryption process.


There are numerous variations on this scheme. The idea is to make the 10MB pseudo-random (so the decryptors don't have to store it) and don't give anyone else the key needed to generate it, so they have to store the full 10MB. (You could also just pad the data up to 10MB and XOR the final output with the 10MB of data. Same idea.)