We construct a reasonably efficient threshold and proactive pseudo-random permutation (PRP). Our protocol needs only
(1) communication rounds. It tolerates up to (
– 1)/2 of
dishonest servers in the semi-honest environment. Many protocols that use PRPs (
., a CBC block cipher mode) can now be translated into the distributed setting. Our main technique for constructing invertible threshold PRPs is a distributed Luby-Rackoff construction where both the secret keys
the input are shared among the servers. We also present protocols for obliviously computing pseudo-random functions by Naor-Reingold  and Dodis-Yampolskiy  with shared input and keys.