Improve SAC in PUFs: Metric, Analysis, Algorithm, and Application

Physical Unclonable Functions (PUFs) are crucial for lightweight authentication in the Internet of Things (IoT), but existing PUFs often have poor statistical properties and are vulnerable to machine learning attacks. Designs implementing the Strict Avalanche Criterion (SAC) lack sufficient theoretical foundation. This paper introduces quantitative metrics to evaluate the SAC performance of strong PUFs and conducts rigorous analysis on Arbiter PUFs (APUFs) and their classic variants, addressing imprecision in existing methods. Based on these metrics, we developed an algorithm to optimize the SAC performance of strong PUFs by adjusting the challenge sequences. This optimization improved the SAC performance of the 2-XOR APUF by 59% without additional resource consumption, making it comparable to the 4-XOR APUF; We also provided mathematical proof for the optimal solution. Furthermore, we propose the SAC Optimized Shuffled XOR Arbiter PUF (SOS XOR APUF), which improves SAC performance by 84% compared to the 3-XOR APUF with the same entropy source. It addresses the inherent defect of poor statistical properties when two adjacent bits in the challenge flip, achieving a theoretical response flip probability of 0.5. The SOS XOR APUF resists existing machine learning attacks---including Logistic Regression (LR), Covariance Matrix Adaptation Evolution Strategy (CMA-ES), Artificial Neural Network (ANN), and Deep Neural Network (DNN)---with prediction accuracy below 55%. Finally, we designed and verified an authentication protocol based on this PUF in the ProVerif environment, achieving mutual authentication between IoT devices and servers, preventing secret information from being stolen, and enhancing the security of the PUF structure.