### 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{\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.

Available format(s)
Category
Foundations
Publication info
Preprint. Minor revision.
Keywords
Physically Unclonable FuncitonsPAC LearningBoolean Functions
Contact author(s)
durba chatterjee94 @ gmail com
debdeep @ iitkgp ac in
aritrah @ cse iitkgp ac in
History
Short URL
https://ia.cr/2021/681

CC BY

BibTeX

@misc{cryptoeprint:2021/681,
author = {Durba Chatterjee and Debdeep Mukhopadhyay and Aritra Hazra},
title = {Learnability of Multiplexer PUF and $S_N$-PUF : A Fourier-based Approach},
howpublished = {Cryptology ePrint Archive, Paper 2021/681},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/681}},
url = {https://eprint.iacr.org/2021/681}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.