Suppose I want a strong 20-bit blockcipher. In other words, I want a function th

Question

Suppose I want a strong 20-bit blockcipher. In other words, I want a function that takes a key (suppose the key is 128 bits), and implements a permutation from 20 bits to 20 bits. The set of permutations should be close to a randomly-chosen subset of size 2128 of all 220! permutations on 20 bits.

I don't want you to build a new blockcipher from scratch. Instead, assume you have a "strong" blockcipher like AES (128-bit blocksize, 128-bit keysize) and use this to build your 20-bit cipher.

Of course, your construction should be practical (i.e., you should be able to run it in both directions with reasonable amounts of time and memory).

Explanation / Answer

There is a generic construction, by Granboulan and myself, which shows that it can be done "perfectly": if you have a seekable pseudo-random stream (which you can get with a conventional block cipher in CTR mode), then you can have a pseudo-random permutation over a domain of arbitrary size N, such that evaluating that permutation over a given input uses negligible memory, and O((log N)3) lookups in the seekable stream.

Unfortunately, this entails evaluating an hypergeometric distribution, which is cumbersome. The prototype we used followed that distribution exactly, hence the "perfect", but implied fiddling with floating point numbers with a high precision, and this was expensive. A basic PC would encrypt at most a dozen values per second with that (not thoroughly optimized) code.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.