Quantum attacks on Sum of Even-Mansour pseudorandom functions

At CRYPTO 2019, constructions of a pseudorandom function from public random permutations were presented. We consider one of the constructions called Sum of Even-Mansour (SoEM), and present quantum attacks against the construction. Our attacks are based on two quantum algorithms, Simon's algorithm and Grover's algorithm, and derive the secret key. We also present quantum attacks against natural variants of SoEM.