Paper 2021/681

Learnability of Multiplexer PUF and $S_N$-PUF : A Fourier-based Approach

Durba Chatterjee, Debdeep Mukhopadhyay, and Aritra Hazra

Abstract

In this work, we prove that Multiplexer PUF~(MPUF) and $S_N$-PUF are learnable in the PAC model. First, we show that both the designs can be represented as a function of Linear Threshold Functions. We show that the noise sensitivity of $(n,k)$-MPUF and $S_N$-PUF can be bounded by $O(2^k\sqrt{ϵ})$ and $O(N\sqrt{ϵ})$ respectively. Finally, we show that as a result of bounded noise sensitivity, both the designs can be accurately approximated using low degree algorithm. Also, the number of labelled examples~(challenge-response pairs) required by the algorithm is polynomial in the input length and PAC model parameters.