Title: How to Generate Pseudorandom Permutations Over Other Groups: Even-Mansour and Feistel Revisited,
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 paper, 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. Finally, 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 last result, we also consider the one-key case over
a group and generalize their bound.