You can construct arbitrarily-sized permutations with log(n) time random access using Sometimes-Recurse Shuffle: https://eprint.iacr.org/2013/560.pdf.