Revisiting lightweight authentication protocols based on hard learning problems
Panagiotis Rizomiliotis, Stefanos Gritzalis · 2013
At the 2011 Eurocrypt, Kiltz et al., in their best paper price awarded paper, proposed an ultra-lightweight authentication protocol, called AUTH. This new protocol is supported by a delegated security proof, against passive and active attacks, based on the conjectured hardness of the Learning Parity with Noise (LPN) problem. However, AUTH has two shortcomings. The security proof does not include man-in-the-middle (MIM) attacks and the communication complexity is high. The weakness against MIM attacks was recently verified as a very efficient key recovery MIM attack was introduced with only linear complexity with respect to the length of the secret key. Regarding the communication overhead, Kiltz et al. proposed a modified version of AUTH where the communication complexity is reduced at the expense of higher storage complexity. This modified protocol was shown to be at least as secure as AUTH.