Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 1 down vote favorite

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

share|improve this question
4  
If Bob is able to choose E, there is a risk that he choose it using a deterministic PRNG with some compact seed, allowing him to store only (F, seed) and from that reconstruct F, F', E. I conclude that the scheme can reach its goal only if Bob receives E, and there is no computationally efficient way to reconstruct E from D. – fgrieu Mar 25 '12 at 19:24
1  
What would be the use case of such a cipher? – Paŭlo Ebermann♦ Mar 25 '12 at 20:37
@fgrieu: Indeed, thanks for pointing that out! I've now removed the scenario altogether, but I'm still interested in the answer. – Arjen Kruithof Mar 25 '12 at 20:38

1 Answer

up vote 1 down vote

  1. Generate a random 2048-bit RSA key.

  2. Generate a random RC4 key.

  3. 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).

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

  5. D consists of the RSA public key and the RC4 key.

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

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

share|improve this answer
1  
That answers the question as stated now, but two of the requirements apparent in the (now gone) motivating application are not met: 1) E must be bigger than the plaintext (10 MB vs 1 MB), 2) E must not be easily compressible, including with knowledge of D. – fgrieu Mar 26 '12 at 7:24
E is bigger than the plaintext. E is 10MB regardless of the size of the plaintext. (The data is encrypted in 10MB blocks, padded up to that size if it's smaller.) So that requirement is met. I can't imagine a use case where the second requirement is sensible, but I bet it's not that difficult to meet. – David Schwartz Mar 26 '12 at 17:29
I wish I had written: 1) The ciphertext must be of size comparable to the plaintext 2) E (restricted to the portion thereof necessary to rebuild the ciphertext from the plaintext, and compressed) must be bigger than the ciphertext (10 MB vs 1 MB). Here is the motivating problem – fgrieu Mar 28 '12 at 19:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.