Paper 2021/681 Original: eprint.iacr.org/2021/681 ↗
Learnability of Multiplexer PUF and $S_N$-PUF : A Fourier-based Approach
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.
- History
- 2021-05-25: last updated
- 2021-05-25: published
- Short URL
- https://ia.cr/2021/681
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}