Paper 2015/378

PAC Learning of Arbiter PUFs

Fatemeh Ganji, Shahin Tajik, and Jean-Pierre Seifert

Abstract

The general concept of Physically Unclonable Functions (PUFs) has been nowadays widely ac cepted and adopted to meet the requirements of secure identification and key generation/storage for cryptographic ciphers. However, shattered by different attacks, e.g., modeling attacks, it has been proved that the promised security features of arbiter PUFs, including unclonability and unpredictability, are not supported unconditionally. However, so far the success of existing modeling attacks relies on pure trial and error estimates. This means that neither the probability of obtaining a useful model (confidence), nor the sufficient number of CRPs, nor the probability of correct prediction (accuracy) is guaranteed. To address these issues, this work presents a Probably Approximately Correct (PAC) learning algorithm. Based on a crucial discretization process, we are able to define a Deterministic Finite Automaton (of polynomial size), which exactly accepts the regular language corresponding to the challenges mapped by the given PUF to one responses.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Minor revision. Journal of Cryptographic Engineering
DOI
10.1007/s13389-016-0119-4
Keywords
Arbiter PUFDeterministic Finite AutomataMachine LearningPAC LearningRegular Language
Contact author(s)
stajik @ sec t-labs tu-berlin de
History
2016-02-13: revised
2015-04-28: received
See all versions
Short URL
https://ia.cr/2015/378
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/378,
      author = {Fatemeh Ganji and Shahin Tajik and Jean-Pierre Seifert},
      title = {PAC Learning of Arbiter PUFs},
      howpublished = {Cryptology ePrint Archive, Paper 2015/378},
      year = {2015},
      doi = {10.1007/s13389-016-0119-4},
      note = {\url{https://eprint.iacr.org/2015/378}},
      url = {https://eprint.iacr.org/2015/378}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.