Cryptology ePrint Archive: Report 2021/681

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

Durba Chatterjee and 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{\epsilon})$ and $O(N\sqrt{\epsilon})$ 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.

Category / Keywords: foundations / Physically Unclonable Funcitons, PAC Learning, Boolean Functions

Date: received 24 May 2021

Contact author: durba chatterjee94 at gmail com, debdeep at iitkgp ac in, aritrah at cse iitkgp ac in

Available format(s): PDF | BibTeX Citation

Version: 20210525:071305 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]