Cryptology ePrint Archive: Report 2020/261

Foxtail+: A Learning with Errors-based Authentication Protocol for Resource-Constrained Devices

Matthieu Monteiro and Kumara Kahatapitiya and Hassan Jameel Asghar and Kanchana Thilakarathna and Thierry Rakotoarivelo and Dali Kaafar and Shujun Li and Ron Steinfeld and Josef Pieprzyk

Abstract: This paper presents Foxtail+, a new shared-key protocol to securely authenticate resource constrained devices, such as Internet of things (IoT) devices. Foxtail+ is based on a previously proposed protocol to authenticate unaided humans, called the Foxtail protocol, which we modify for authenticating resource constrained devices. It uses a computationally lightweight function, called the Foxtail function, which makes it ideal for IoT nodes with low memory, computational, and/or battery resources. We introduce a new family of functions based on the Foxtail function, analyze its security in terms of the number of samples required to obtain the secret, and demonstrate how it is connected with the learning with rounding (LWR) problem. We then build the Foxtail+ protocol from this function family, secure against active adversaries. Finally, we implement and experimentally evaluate the performance of Foxtail+ against a similar alternate protocol, i.e., the modified version of the Hopper and Blum protocol called HB+, and a block cipher based protocol instantiated with AES. The experiments are run on an IoT device connected to a LoRa network which is an IoT specific Low-Power Wide-Area Network (LPWAN). We show that Foxtail+ outperforms HB+ in terms of overall communication and energy cost, and its parallel implementation is comparable to the AES-based protocol in terms of time and energy consumption. To our knowledge, we provide the first implementation of any member of the HB+ family of protocols that directly compares its performance against an AES-based protocol in terms of time and power consumption. Our experiments shed new light on some of the limitations of identification protocols based on lightweight primitives, of which Foxtail+ is a member, over block cipher based protocols.

Category / Keywords: secret-key cryptography / Identification protocols, human identification protocols, HB+ protocol, learning with errors, AES

Date: received 25 Feb 2020

Contact author: hassan jameel at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20200225:204915 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]