eprint.iacr.org will be offline for approximately an hour
for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between
April 12 and April 14, and some authors have been notified that they need to resubmit their papers.
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},
note = {\url{https://eprint.iacr.org/2021/681}},
url = {https://eprint.iacr.org/2021/681}
}
