An entropy test for determining whether a MUX PUF is linear or nonlinear

Anoop Koyily, Chen Zhou, Chris H. Kim, Keshab K Parhi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)

Abstract

This paper proposes a novel entropy test to determine whether a MUX PUF is linear or not. Three MUX PUF configurations are considered, namely linear, feed-forward and modified feed-forward. In addition to these, we also consider feed-forward structures like overlap, cascade and separate configurations. The approach is focused on computing the conditional entropy of responses to a set of predefined challenges. The challenge set consists of randomly chosen challenges and their 1-bit neighbors. The entropy is computed across the responses of two 1-bit neighboring challenges. For non-linear MUX PUFs like feed-forward, the method determines the MUX stages which are controlled by internally generated challenge bits as opposed to external challenge bits. This is based on the observation that the conditional entropy for each of these stages is zero. Also, the number of zero conditional entropy values across the MUX stages provide an upper bound on the number of internal arbiters present in the PUF. With the proposed approach, we observe 100% sensitivity and 100% specificity for identifying non-linearity. Furthermore, we show that the proposed approach requires very less number of stable random challenges (about 50) for successfully determining whether a PUF is linear or not for real chips.

Original languageEnglish (US)
Title of host publicationIEEE International Symposium on Circuits and Systems
Subtitle of host publicationFrom Dreams to Innovation, ISCAS 2017 - Conference Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781467368520
DOIs
StatePublished - Sep 25 2017
Event50th IEEE International Symposium on Circuits and Systems, ISCAS 2017 - Baltimore, United States
Duration: May 28 2017May 31 2017

Publication series

NameProceedings - IEEE International Symposium on Circuits and Systems
ISSN (Print)0271-4310

Other

Other50th IEEE International Symposium on Circuits and Systems, ISCAS 2017
CountryUnited States
CityBaltimore
Period5/28/175/31/17

Fingerprint

Entropy

Keywords

  • MUX PUF
  • conditional entropy
  • non-linearity
  • physical unclonable function

Cite this

Koyily, A., Zhou, C., Kim, C. H., & Parhi, K. K. (2017). An entropy test for determining whether a MUX PUF is linear or nonlinear. In IEEE International Symposium on Circuits and Systems: From Dreams to Innovation, ISCAS 2017 - Conference Proceedings [8050670] (Proceedings - IEEE International Symposium on Circuits and Systems). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISCAS.2017.8050670

An entropy test for determining whether a MUX PUF is linear or nonlinear. / Koyily, Anoop; Zhou, Chen; Kim, Chris H.; Parhi, Keshab K.

IEEE International Symposium on Circuits and Systems: From Dreams to Innovation, ISCAS 2017 - Conference Proceedings. Institute of Electrical and Electronics Engineers Inc., 2017. 8050670 (Proceedings - IEEE International Symposium on Circuits and Systems).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Koyily, A, Zhou, C, Kim, CH & Parhi, KK 2017, An entropy test for determining whether a MUX PUF is linear or nonlinear. in IEEE International Symposium on Circuits and Systems: From Dreams to Innovation, ISCAS 2017 - Conference Proceedings., 8050670, Proceedings - IEEE International Symposium on Circuits and Systems, Institute of Electrical and Electronics Engineers Inc., 50th IEEE International Symposium on Circuits and Systems, ISCAS 2017, Baltimore, United States, 5/28/17. https://doi.org/10.1109/ISCAS.2017.8050670
Koyily A, Zhou C, Kim CH, Parhi KK. An entropy test for determining whether a MUX PUF is linear or nonlinear. In IEEE International Symposium on Circuits and Systems: From Dreams to Innovation, ISCAS 2017 - Conference Proceedings. Institute of Electrical and Electronics Engineers Inc. 2017. 8050670. (Proceedings - IEEE International Symposium on Circuits and Systems). https://doi.org/10.1109/ISCAS.2017.8050670
Koyily, Anoop ; Zhou, Chen ; Kim, Chris H. ; Parhi, Keshab K. / An entropy test for determining whether a MUX PUF is linear or nonlinear. IEEE International Symposium on Circuits and Systems: From Dreams to Innovation, ISCAS 2017 - Conference Proceedings. Institute of Electrical and Electronics Engineers Inc., 2017. (Proceedings - IEEE International Symposium on Circuits and Systems).
@inproceedings{3e48a383df904fbcaa0e344ef1387c87,
title = "An entropy test for determining whether a MUX PUF is linear or nonlinear",
abstract = "This paper proposes a novel entropy test to determine whether a MUX PUF is linear or not. Three MUX PUF configurations are considered, namely linear, feed-forward and modified feed-forward. In addition to these, we also consider feed-forward structures like overlap, cascade and separate configurations. The approach is focused on computing the conditional entropy of responses to a set of predefined challenges. The challenge set consists of randomly chosen challenges and their 1-bit neighbors. The entropy is computed across the responses of two 1-bit neighboring challenges. For non-linear MUX PUFs like feed-forward, the method determines the MUX stages which are controlled by internally generated challenge bits as opposed to external challenge bits. This is based on the observation that the conditional entropy for each of these stages is zero. Also, the number of zero conditional entropy values across the MUX stages provide an upper bound on the number of internal arbiters present in the PUF. With the proposed approach, we observe 100{\%} sensitivity and 100{\%} specificity for identifying non-linearity. Furthermore, we show that the proposed approach requires very less number of stable random challenges (about 50) for successfully determining whether a PUF is linear or not for real chips.",
keywords = "MUX PUF, conditional entropy, non-linearity, physical unclonable function",
author = "Anoop Koyily and Chen Zhou and Kim, {Chris H.} and Parhi, {Keshab K}",
year = "2017",
month = "9",
day = "25",
doi = "10.1109/ISCAS.2017.8050670",
language = "English (US)",
series = "Proceedings - IEEE International Symposium on Circuits and Systems",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
booktitle = "IEEE International Symposium on Circuits and Systems",

}

TY - GEN

T1 - An entropy test for determining whether a MUX PUF is linear or nonlinear

AU - Koyily, Anoop

AU - Zhou, Chen

AU - Kim, Chris H.

AU - Parhi, Keshab K

PY - 2017/9/25

Y1 - 2017/9/25

N2 - This paper proposes a novel entropy test to determine whether a MUX PUF is linear or not. Three MUX PUF configurations are considered, namely linear, feed-forward and modified feed-forward. In addition to these, we also consider feed-forward structures like overlap, cascade and separate configurations. The approach is focused on computing the conditional entropy of responses to a set of predefined challenges. The challenge set consists of randomly chosen challenges and their 1-bit neighbors. The entropy is computed across the responses of two 1-bit neighboring challenges. For non-linear MUX PUFs like feed-forward, the method determines the MUX stages which are controlled by internally generated challenge bits as opposed to external challenge bits. This is based on the observation that the conditional entropy for each of these stages is zero. Also, the number of zero conditional entropy values across the MUX stages provide an upper bound on the number of internal arbiters present in the PUF. With the proposed approach, we observe 100% sensitivity and 100% specificity for identifying non-linearity. Furthermore, we show that the proposed approach requires very less number of stable random challenges (about 50) for successfully determining whether a PUF is linear or not for real chips.

AB - This paper proposes a novel entropy test to determine whether a MUX PUF is linear or not. Three MUX PUF configurations are considered, namely linear, feed-forward and modified feed-forward. In addition to these, we also consider feed-forward structures like overlap, cascade and separate configurations. The approach is focused on computing the conditional entropy of responses to a set of predefined challenges. The challenge set consists of randomly chosen challenges and their 1-bit neighbors. The entropy is computed across the responses of two 1-bit neighboring challenges. For non-linear MUX PUFs like feed-forward, the method determines the MUX stages which are controlled by internally generated challenge bits as opposed to external challenge bits. This is based on the observation that the conditional entropy for each of these stages is zero. Also, the number of zero conditional entropy values across the MUX stages provide an upper bound on the number of internal arbiters present in the PUF. With the proposed approach, we observe 100% sensitivity and 100% specificity for identifying non-linearity. Furthermore, we show that the proposed approach requires very less number of stable random challenges (about 50) for successfully determining whether a PUF is linear or not for real chips.

KW - MUX PUF

KW - conditional entropy

KW - non-linearity

KW - physical unclonable function

UR - http://www.scopus.com/inward/record.url?scp=85032661442&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85032661442&partnerID=8YFLogxK

U2 - 10.1109/ISCAS.2017.8050670

DO - 10.1109/ISCAS.2017.8050670

M3 - Conference contribution

AN - SCOPUS:85032661442

T3 - Proceedings - IEEE International Symposium on Circuits and Systems

BT - IEEE International Symposium on Circuits and Systems

PB - Institute of Electrical and Electronics Engineers Inc.

ER -