An algorithm or an authentication system for a low-cost authenticating device such as a radio frequency identification (RFID) tag, or a sensor node are provided, by which authentication is processed efficiently without requiring complicated hardware. A claimant entity attempting to be authenticated and a verifying entity to authenticate the claimant entity, share a plurality of secret keys so that authentication is processed as the claimant entity responds to a challenge by the verifying entity. The verifying entity and the claimant entity perform authentication using Learning Parity with Noise (LPN) problem. The verifying entity and the claimant entity generate keys independently from one another, and exchange the generated keys. The claimant entity may generate an encrypted value for use in the authentication, using a basic Boolean Exclusive OR and a logical AND operations.