We look at the problem of designing Message Recognition Protocols (MRP) and note that all proposals available in the literature have relied on security proofs which hold in the random oracle model or are based on non-standard assumptions. Incorporating random coins, we propose a new MRP using a pseu- dorandom function F and prove its security based on new assumptions. Then, we show that these new assumptions are equivalent to the stan- dard notions of preimage resistance, second preimage resistance, and existential unforgeability given that F is a pseudorandom function.