Novel Strong-PUF-based Authentication Protocols Leveraging Shamir’s Secret Sharing

Physical Unclonable Function (PUF) has emerged as an attractive hardware-primitive for lightweight authentication in the Internet of Things (IoT). However, strong-PUF-based authentication schemes are threatened by powerful machine learning attacks. Therefore, dedicated lightweight protocols are required to preserve the privacy of the embedded strong PUF. In this paper, we show that the “availability” and “reliability” features of Shamir’s secret sharing (SSS) can be applied to address the security issue. In protocol A, the mappings between challenges and responses are randomly shuffled to resist the machine learning attacks. Leveraging the “availability” feature of SSS, the verification process is unaffected by the randomized challenge-response pairs (CRPs) at the server end. Moreover, the “reliability” feature of SSS provides the error-tolerant characteristic in our protocol which is suitable for the noisy PUFs. Protocol A also presented a method to securely store the CRPs at the server-side. The improved protocol A optimizes protocol A by eliminating the response storage and matching process at the server end. In protocol B, we present a mutual authentication protocol where no response is exposed to the adversary. Protocol B can be classified as the lightweight protocol because it can avoid the use of cryptographic algorithms and error-correcting codes. We rigorously analyze and prove the security of our protocols with formal security proofs, informal security analysis, and several selected machine learning techniques, including Logistic Regression (LR), Deep Neural Network (DNN), Approximate attack, AutoGluon-Tabular, and a new brute-force machine learning attack. Furthermore, we present an efficient implementation of our protocols on FPGA. The experimental results shown the feasibility and practicability of our protocols under different parameters.