Is it possible to generate a secure permutation F over 32-bit integers even if F(0) ... F(n) is public knowledge? I'm currently interested in the problem of generating random-looking URLs from sequential database IDs, like how they do it in link shorteners. One way to do this is to encrypt the sequential database ids using a 32 bit block cypher and base62 encode the result so it can be written to the URL.

For example:

foo.com/1       foo.com/2        -- Original sequential IDs
foo.com/142365  foo.com/226340   -- Encrypt IDs using a permutation function
foo.com/b2D     foo.com/wse      -- Encode in base62 format - looks random + compact.


Now here is the catch: Whenever we encrypt the a new database ID and publish the URL, that plaintext-ciphertext pair become public knowledge. Is it possible to create an encryption system that makes it hard to guess what will be the next URL we will generate? That is, can we make it so the attacker can't guess the value of $F(1000000)$ even if he knows the values of $F(n)$ for $n \leq 999999$?

Some things that I think are important to note:


The cypher must have a 32 bit block size. Otherwise, the resulting URLs get too long.
The secret key is allowed to be any size.
Each number is only be encrypted once and all the messages I encrypt are 32 bits in length. (None of the stream-cypher stuff applies)




My actual use case – and most people's, to be honest – won't really need that kind of security. A bijective mapping from sequential IDs to URLs that looks scrambled at first glance is good enough. However, I am now curious if that unpredictability requirement is possible to achieve. In my searches, I found a lot of people saying that 32 bit blocks are too small due to the birthday problem but I am not sure that caveat applies here. On the other hand, none of the 32-bit block cyphers I found say anything about their resistance to known cyphertext attacks…
Yes, it is possible to implement the primitive asked, with a 32-bit block cipher that is secure (indistinguishable from a random permutation) no matter how many input-output pairs are known, keyed with a fixed secret randomly-chosen key. That's a standard building block in Format Preserving Encryption.

One such block cipher is: Louis Granboulan and Thomas Pornin, Perfect block ciphers with small blocks (in proceedings of FSE 2007).

Emil Stefanov and Elaine Shi's FastPRP: Fast Pseudo-Random Permutations for Small Domains (Cryptology ePrint Report 2012/254) claim a speed improvement, and review some earlier work.

Update: Ricky Demer kindly pointed another recent paper: Ben Morris and Phillip Rogaway, Sometimes-Recurse Shuffle, Almost-Random Permutations in Logarithmic Expected Time (Cryptology ePrint Report 2013/560).