Unfortunately, randomly permuting the input takes O(nlog(n)) steps (you need at least this much time just to read in sufficiently many random bits). Perhaps a clever parallel architecture could reduce the runtime?
This is not true if you can generate a random number in constant time which is probably the more practical of the constraints to satisfy when implementing this algorithm.