Paper 2022/1766

Systematically Quantifying Cryptanalytic Non-Linearities in Strong PUFs

Durba Chatterjee, Indian Institute of Technology Kharagpur
Kuheli Pratihar, Indian Institute of Technology Kharagpur
Aritra Hazra, Indian Institute of Technology Kharagpur
Ulrich Rührmair, Ludwig-Maximilians-Universität München, University of Connecticut
Debdeep Mukhopadhyay, Indian Institute of Technology Kharagpur

Physically Unclonable Functions~(PUFs) with large challenge space~(also called Strong PUFs) are promoted for usage in authentications and various other cryptographic and security applications. In order to qualify for these cryptographic applications, the Boolean functions realized by PUFs need to possess a high non-linearity~(NL). However, with a large challenge space~(usually $\geq 64$ bits), measuring NL by classical techniques like Walsh transformation is computationally infeasible. In this paper, we propose the usage of a heuristic-based measure called non-homomorphicity test which estimates the NL of Boolean functions with high accuracy in spite of not needing access to the entire challenge-response set. We also combine our analysis with a technique used in linear cryptanalysis, called Piling-up lemma, to measure the NL of popular PUF compositions. As a demonstration to justify the soundness of the metric, we perform extensive experimentation by first estimating the NL of constituent Arbiter/Bistable Ring PUFs using the non-homomorphicity test, and then applying them to quantify the same for their XOR compositions namely XOR Arbiter PUFs and XOR Bistable Ring PUF. Our findings show that the metric explains the impact of various parameter choices of these PUF compositions on the NL obtained and thus promises to be used as an important objective criterion for future efforts to evaluate PUF designs. While the framework is not representative of the machine learning robustness of PUFs, it can be a useful complementary tool to analyze the cryptanalytic strengths of PUF primitives.

Available format(s)
Attacks and cryptanalysis
Publication info
Strong PUFsNon-linearityCryptanalysisCryptanalytic AttacksNon-homomorphicity Tests
Contact author(s)
durba chatterjee94 @ gmail com
its kuheli96 @ gmail com
aritrah @ cse iitkgp ac in
ruehrmair @ ilo de
debdeep mukhopadhyay @ gmail com
2022-12-27: revised
2022-12-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Durba Chatterjee and Kuheli Pratihar and Aritra Hazra and Ulrich Rührmair and Debdeep Mukhopadhyay},
      title = {Systematically Quantifying Cryptanalytic Non-Linearities in Strong PUFs},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1766},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.