Title: How to Generate Pseudorandom Permutations Over Other Groups,
Abstract: Recent results by Alagic and Russell have given some evidence that the
Even-Mansour cipher may be secure against quantum adversaries with quantum
queries, if considered over other groups than $(\mathbb{Z}/2)^n$. This prompts
the question as to whether or not other classical schemes may be generalized to
arbitrary groups and whether classical results still apply to those generalized
schemes. In this thesis, we generalize the Even-Mansour cipher and the Feistel
cipher. We show that Even and Mansour's original notions of secrecy are
obtained on a one-key, group variant of the Even-Mansour cipher. We generalize
the result by Kilian and Rogaway, that the Even-Mansour cipher is pseudorandom,
to super pseudorandomness, also in the one-key, group case. Using a Slide
Attack we match the bound found above. After generalizing the Feistel cipher to
arbitrary groups we resolve an open problem of Patel, Ramzan, and Sundaram by
showing that the 3-round Feistel cipher over an arbitrary group is not super
pseudorandom. We generalize a result by Gentry and Ramzan showing that the
Even-Mansour cipher can be implemented using the Feistel cipher as the public
permutation. In this result, we also consider the one-key case over a group and
generalize their bound. Finally, we consider Zhandry's result on quantum
pseudorandom permutations, showing that his result may be generalized to hold
for arbitrary groups. In this regard, we consider whether certain card shuffles
may be generalized as well.