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

Metadata
Available format(s)
PDF
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
2021-05-25: received
Short URL
https://ia.cr/2021/681
License
Creative Commons Attribution
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.