A quantum lower bound for distinguishing random functions from random permutations

Henry Yuen

The problem of distinguishing between a random function and a random permutation on a domain of size $N$ is important in theoretical cryptography, where the security of many primit…