Since the seminal work of Chen et al. to construct pseudorandom functions (PRFs) from the public random permutations, a series of designs of beyond-birthday-bound secure PRFs or message authentication codes(MACs) have been proposed, like pEDM , pPMAC _ Plus , PDM * MAC , and 1 K - PDM * MAC , etc. These constructions were classically proved to be secure at least up to O (2 2 n / 3) queries. In this paper, we consider to attack these constructions in the quantum setting. In particular, we show the key-recovery attack against pEDM and pPMAC _ Plus with O (n · 2 n / 2) quantum queries by using Grover-meets-Simon algorithm. Moreover, a forgery attack is given against the constructions PDM * MAC and nEHtM p with O(n) quantum complexity, and under the same query complexity, we can even recover the key of 1 K - PDM * MAC . [ABSTRACT FROM AUTHOR]