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
-
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},
url = {https://eprint.iacr.org/2021/681}
}
