Abstract: It is important to provide strong security guarantees for low cost devices such as Radio Frequency Identification (RFID) tags，since they are more vulnerable to all kinds of attacks．In this vein，this paper presents a two-round symmetric authentication protocol LPNAP which is able to resist man-in-the-middle (MIM) attacks．LPNAP is constructed on the learning parity with noise (LPN) problem．Hence，it has small computation cost and low communication overhead．Moreover，it has been proven to be as secure as the subspace LPN problem．To reduce the storage requirement，an optimized variant of LPNAP is introduced through Toeplitz-LPN．