Cryptology ePrint Archive: Report 2016/982

Securing Systems with Scarce Entropy: LWE-Based Lossless Computational Fuzzy Extractor for the IoT

Christopher Huth and Daniela Becker and Jorge Guajardo and Paul Duplys and Tim Güneysu

Abstract: With the advent of the Internet of Things, lightweight devices necessitate secure and cost-efficient key storage. Since traditional secure key storage is expensive, novel solutions have been developed based on the idea of deriving the key from noisy entropy sources. Such sources when combined with fuzzy extractors allow cryptographically strong key derivation. Information theoretic fuzzy extractors require large amounts of input entropy to account for entropy loss in the key extraction process. It has been shown by Fuller \textit{et al.}~(ASIACRYPT'13) that the entropy loss can be reduced if the requirement is relaxed to computational security based on the hardness of the Learning with Errors problem. Using this computational fuzzy extractor, we show how to construct a device-server authentication system providing outsider chosen perturbation security and pre-application robustness. We present the first implementation of a \emph{lossless} computational fuzzy extractor where the entropy of the source equals the entropy of the key on a constrained device. The implementation needs only 1.45KB of SRAM and 9.8KB of Flash memory on an 8-bit microcontroller. Furthermore, we also show how a device-server authentication system can be constructed and efficiently implemented in our system. We compare our implementation to existing work in terms of security, while achieving no entropy loss.

Category / Keywords: / Computational fuzzy extractor; Learning with errors; Authentication system; Implementation

Date: received 11 Oct 2016, last revised 17 Apr 2018

Contact author: christopher huth at de bosch com

Available format(s): PDF | BibTeX Citation

Note: We corrected our initial construction, as a work short after showed an successful attack.

Version: 20180417:081123 (All versions of this report)

Short URL: ia.cr/2016/982

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]