Quantum Physical Unclonable Functions: Possibilities And Impossibilities

Abstract

A Physical Unclonable Function (PUF) is a device with unique behaviour that is hard to clone hence providing a secure fingerprint. A variety of PUF structures and PUF-based applications have been explored theoretically as well as being implemented in practical settings. Recently, the inherent unclonability of quantum states has been exploited to derive the quantum analogue of PUF as well as new proposals for the implementation of PUF. We present the first comprehensive study of quantum Physical Unclonable Functions (qPUFs) with quantum cryptographic tools. We formally define qPUFs, encapsulating all requirements of classical PUFs as well as introducing a new testability feature inherent to the quantum setting only. We use a quantum game-based framework to define different levels of security for qPUFs: quantum exponential unforgeability, quantum existential unforgeability and quantum selective unforgeability. We introduce a new quantum attack technique based on the universal quantum emulator algorithm of Marvin and Lloyd to prove no qPUF can provide quantum existential unforgeability. On the other hand, we prove that a large family of qPUFs (called unitary PUFs) can provide quantum selective unforgeability which is the desired level of security for most PUF-based applications.

Popular summary

Physical Unclonable Functions (PUFs) are physical devices with unique behaviour, due to the imperfections and natural randomness during their manufacturing procedure, which makes them hard to clone. A large variety of PUF schemes have been mass-produced for a large domain of applications from anti-counterfeiting, identification, authentication and key generation to advanced protocols such as oblivious transfer, key exchange, key renovation and virtual proof of reality. Considering the importance of PUFs as a hardware security primitive in these real-world applications, it is crucial to investigate their security in the quantum regime as well. Recently, the inherent unclonability of quantum states has been exploited for defining quantum analogue to classical PUFs. We provide the first comprehensive study of the Quantum Physical Unclonable Functions (QPUFs) and develop a formal quantum security framework for our analysis. In doing so we define a new class of quantum attacks, called General Quantum Emulation Attack (QEA) that similar to the classical setting, where machine learning techniques have been developed to demonstrate the vulnerability of PUF, our QEA also exploits previously captured valid challenge-response pairs to emulate the action of an unknown quantum transformation on new input. We devise a concrete attack based on an existing quantum emulation algorithm and use it to show that a family of QPUFs do not provide previously claimed strong security. Our investigation, however, put forward the most general definitions of QPUFs that remains secure against the strongest possible quantum adversary, compatible with a practical setting where most of QPUF will be utilised.

► BibTeX data

@article{Arapinis2021quantumphysical, doi = {10.22331/q-2021-06-15-475}, url = {https://doi.org/10.22331/q-2021-06-15-475}, title = {Quantum {P}hysical {U}nclonable {F}unctions: {P}ossibilities and {I}mpossibilities}, author = {Arapinis, Myrto and Delavar, Mahshid and Doosti, Mina and Kashefi, Elham}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {5}, pages = {475}, month = jun, year = {2021}<br /> }

► References

[1] Andris Ambainis and Joseph Emerson. Quantum t-designs: t-wise independence in the quantum world. In Proceedings of Twenty-Second Annual IEEE Conference on Computational Complexity (CCC’07), pages 129–140. IEEE, 2007. DOI: 10.1109/CCC.2007.26.
https://doi.org/10.1109/CCC.2007.26

[2] Mohammad Hassan Ameri, Mahshid Delavar, and Javad Mohajeri. Provably secure and efficient PUF-based broadcast authentication schemes for smart grid applications. International Journal of Communication Systems, 32(8):e3935, 2019. DOI: 10.1002/dac.3935.
https://doi.org/10.1002/dac.3935

[3] Frederik Armknecht, Daisuke Moriyama, Ahmad-Reza Sadeghi, and Moti Yung. Towards a unified security model for physically unclonable functions. In Proceedings of Cryptographers’ Track at the RSA Conference, pages 271–287. Springer, 2016. DOI: 10.1007/978-3-319-29485-8–16.
https://doi.org/10.1007/978-3-319-29485-8_16

[4] Saikrishna Badrinarayanan, Dakshita Khurana, Rafail Ostrovsky, and Ivan Visconti. Unconditional uc-secure computation with (stronger-malicious) PUFs. In Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 382–411. Springer, 2017. DOI: 10.1007/978-3-319-56620-7–14.
https://doi.org/10.1007/978-3-319-56620-7_14

[5] Dan Boneh and Mark Zhandry. Secure signatures and chosen ciphertext security in a quantum computing world. In Proceedings of Annual International Cryptology Conference, pages 361–379. Springer, 2013. DOI: 10.1007/978-3-642-40084-1–21.
https://doi.org/10.1007/978-3-642-40084-1_21

[6] Dagmar Bruss, Artur Ekert, and Chiara Macchiavello. Optimal universal quantum cloning and state estimation. Physical Review Letters, 81(12):2598, 1998. DOI: 10.1103/PhysRevLett.81.2598.
https://doi.org/10.1103/PhysRevLett.81.2598

[7] Christina Brzuska, Marc Fischlin, Heike Schröder, and Stefan Katzenbeisser. Physically uncloneable functions in the universal composition framework. In Proceedings of Annual International Cryptology Conference, pages 51–70. Springer, 2011. DOI: 10.1007/978-3-642-22792-9–4.
https://doi.org/10.1007/978-3-642-22792-9_4

[8] Harry Buhrman, Richard Cleve, John Watrous, and Ronald De Wolf. Quantum fingerprinting. Physical Review Letters, 87(16):167902, 2001. DOI: 10.1103/PhysRevLett.87.167902.
https://doi.org/10.1103/PhysRevLett.87.167902

[9] Ran Canetti and Marc Fischlin. Universally composable commitments. In Proceedings of Annual International Cryptology Conference, pages 19–40. Springer, 2001. DOI: 10.1007/3-540-44647-8–2.
https://doi.org/10.1007/3-540-44647-8_2

[10] Ulysse Chabaud, Eleni Diamanti, Damian Markham, Elham Kashefi, and Antoine Joux. Optimal quantum-programmable projective measurement with linear optics. Physical Review A, 98(6):062318, 2018. DOI: 10.1103/PhysRevA.98.062318.
https://doi.org/10.1103/PhysRevA.98.062318

[11] Chip-Hong Chang, Yue Zheng, and Le Zhang. A retrospective and a look forward: Fifteen years of physical unclonable function advancement. IEEE Circuits and Systems Magazine, 17(3):32–62, 2017. DOI: 10.1109/MCAS.2017.2713305.
https://doi.org/10.1109/MCAS.2017.2713305

[12] Giulio Chiribella, Giacomo Mauro D’Ariano, and Paolo Perinotti. Optimal cloning of unitary transformation. Physical review letters, 101(18):180504, 2008. DOI: 10.1103/PhysRevLett.101.180504.
https://doi.org/10.1103/PhysRevLett.101.180504

[13] Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine. Exact and approximate unitary 2-designs and their application to fidelity estimation. Physical Review A, 80(1):012304, 2009. DOI: 10.1103/PhysRevA.80.012304.
https://doi.org/10.1103/PhysRevA.80.012304

[14] GM D’Ariano and P Lo Presti. Quantum tomography for measuring experimentally the matrix elements of an arbitrary quantum operation. Physical Review Letters, 86(19):4195, 2001. DOI: 10.1103/PhysRevLett.86.4195.
https://doi.org/10.1103/PhysRevLett.86.4195

[15] Mahshid Delavar, Sattar Mirzakuchaki, Mohammad Hassan Ameri, and Javad Mohajeri. PUF-based solutions for secure communications in advanced metering infrastructure (ami). International Journal of Communication Systems, 30(9):e3195, 2017. DOI: 10.1002/dac.3195.
https://doi.org/10.1002/dac.3195

[16] Mahshid Delavar, Sattar Mirzakuchaki, and Javad Mohajeri. A ring oscillator-based PUF with enhanced challenge-response pairs. Canadian Journal of Electrical and Computer Engineering, 39(2):174–180, 2016. DOI: 10.1109/CJECE.2016.2521877.
https://doi.org/10.1109/CJECE.2016.2521877

[17] Mina Doosti, Farzad Kianvash, and Vahid Karimipour. Universal superposition of orthogonal states. Physical Review A, 96(5):052318, 2017. DOI: 10.1103/PhysRevA.96.052318.
https://doi.org/10.1103/PhysRevA.96.052318

[18] Lukas Fladung, Georgios M Nikolopoulos, Gernot Alber, and Marc Fischlin. Intercept-resend emulation attacks against a continuous-variable quantum authentication protocol with physical unclonable keys. Cryptography, 3(4):25, 2019. DOI: 10.3390/cryptography3040025.
https://doi.org/10.3390/cryptography3040025

[19] Fatemeh Ganji, Shahin Tajik, Fabian Fäßler, and Jean-Pierre Seifert. Strong machine learning attack against PUFs with no mathematical model. In International Conference on Cryptographic Hardware and Embedded Systems, pages 391–411. Springer, 2016. DOI: 10.1007/978-3-662-53140-2–19.
https://doi.org/10.1007/978-3-662-53140-2_19

[20] Blaise Gassend, Dwaine Clarke, Marten Van Dijk, and Srinivas Devadas. Silicon physical random functions. In Proceedings of the 9th ACM conference on Computer and communications security, pages 148–160. ACM, 2002. DOI: 10.1145/586110.586132.
https://doi.org/10.1145/586110.586132

[21] Giulio Gianfelici, Hermann Kampermann, and Dagmar Bruß. Theoretical framework for physical unclonable functions, including quantum readout. Physical Review A, 101(4):042337, 2020. DOI: 10.1103/PhysRevA.101.042337.
https://doi.org/10.1103/PhysRevA.101.042337

[22] Sebastianus A Goorden, Marcel Horstmann, Allard P Mosk, Boris Škorić, and Pepijn WH Pinkse. Quantum-secure authentication of a physical unclonable key. Optica, 1(6):421–424, 2014. DOI: 10.1364/OPTICA.1.000421.
https://doi.org/10.1364/OPTICA.1.000421

[23] Daniel Greenbaum and Zachary Dutton. Modeling coherent errors in quantum error correction. Quantum Science and Technology, 3(1):015007, 2017. DOI: 10.1088/2058-9565/aa9a06.
https://doi.org/10.1109/CCC.2007.26

[24] Jorge Guajardo, Sandeep S Kumar, Geert-Jan Schrijen, and Pim Tuyls. Fpga intrinsic PUFs and their use for ip protection. In Proceedings of International workshop on cryptographic hardware and embedded systems, pages 63–80. Springer, 2007. DOI: 10.1007/978-3-540-74735-2–5.
https://doi.org/10.1007/978-3-540-74735-2_5

[25] B. Halak. Physically Unclonable Functions: From Basic Design Principles to Advanced Hardware Security Applications. Springer International Publishing, 2019. DOI: 10.1007/978-3-319-76804-5.
https://doi.org/10.1007/978-3-319-76804-5

[26] Charles Herder, Meng-Day Yu, Farinaz Koushanfar, and Srinivas Devadas. Physical unclonable functions and applications: A tutorial. Proceedings of the IEEE, 102(8):1126–1141, 2014. DOI: 10.1109/JPROC.2014.2320516.
https://doi.org/10.1109/JPROC.2014.2320516

[27] Jonathan Katz. Universally composable multi-party computation using tamper-proof hardware. In Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 115–128. Springer, 2007. DOI: 10.1007/978-3-540-72540-4–7.
https://doi.org/10.1007/978-3-540-72540-4_7

[28] Mahmoud Khalafalla and Catherine Gebotys. PUFs deep attacks: Enhanced modeling attacks using deep learning techniques to break the security of double arbiter PUFs. In 2019 Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 204–209. IEEE, 2019. DOI: 10.23919/DATE.2019.8714862.
https://doi.org/10.23919/DATE.2019.8714862

[29] Niraj Kumar, Rawad Mezher, and Elham Kashefi. Efficient construction of quantum physical unclonable functions with unitary t-designs, 2021. arXiv:2101.05692.
arXiv:2101.05692

[30] Weiqiang Liu, Lei Zhang, Zhengran Zhang, Chongyan Gu, Chenghua Wang, Maire O’neill, and Fabrizio Lombardi. Xor-based low-cost reconfigurable pufs for iot security. ACM Transactions on Embedded Computing Systems (TECS), 18(3):1–21, 2019. DOI: 10.1145/32746665.
https://doi.org/10.1145/32746665

[31] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component analysis. Nature Physics, 10(9):631, 2014. DOI: 10.1038/nphys3029.
https://doi.org/10.1038/nphys3029

[32] Roel Maes. Physically Unclonable Functions: Constructions, Properties and Applications. Springer-Verlag Berlin Heidelberg, 2016. DOI: 10.1007/978-3-642-41395-7–3.
https://doi.org/10.1007/978-3-642-41395-7_3

[33] Cédric Marchand, Lilian Bossuet, Ugo Mureddu, Nathalie Bochard, Abdelkarim Cherkaoui, and Viktor Fischer. Implementation and characterization of a physical unclonable function for iot: a case study with the tero-PUF. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 37(1):97–109, 2017. DOI: 10.1109/TCAD.2017.2702607.
https://doi.org/10.1109/TCAD.2017.2702607

[34] Iman Marvian and Seth Lloyd. Universal quantum emulator. arXiv preprint arXiv:1606.02734, 2016. arXiv:1606.02734.
arXiv:1606.02734

[35] Charis Mesaritakis, Marialena Akriotou, Alexandros Kapsalis, Evangelos Grivas, Charidimos Chaintoutis, Thomas Nikas, and Dimitris Syvridis. Physical unclonable function based on a multi-mode optical waveguide. Scientific reports, 8(1):9653, 2018. DOI: 10.1038/s41598-018-28008-6.
https://doi.org/10.1038/s41598-018-28008-6

[36] Debdeep Mukhopadhyay. PUFs as promising tools for security in internet of things. IEEE Design & Test, 33(3):103–115, 2016. DOI: 10.1109/MDAT.2016.2544845.
https://doi.org/10.1109/MDAT.2016.2544845

[37] Michael A Nielsen and Isaac L Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 10th edition, 2010. DOI: 10.1017/CBO9780511976667.
https://doi.org/10.1017/CBO9780511976667

[38] Georgios M Nikolopoulos. Continuous-variable quantum authentication of physical unclonable keys: Security against an emulation attack. Physical Review A, 97(1):012324, 2018. DOI: 10.1103/PhysRevA.97.012324.
https://doi.org/10.1103/PhysRevA.97.012324

[39] Georgios M Nikolopoulos and Eleni Diamanti. Continuous-variable quantum authentication of physical unclonable keys. Scientific reports, 7:46047, 2017. DOI: 10.1038/srep46047.
https://doi.org/10.1038/srep46047

[40] Michał Oszmaniec, Andrzej Grudka, Michał Horodecki, and Antoni Wójcik. Creating a superposition of unknown quantum states. Physical Review Letters, 116(11), 2016. DOI: 10.1103/PhysRevLett.116.110403.
https://doi.org/10.1103/PhysRevLett.116.110403

[41] Ravikanth Pappu, Ben Recht, Jason Taylor, and Neil Gershenfeld. Physical one-way functions. Science, 297(5589):2026–2030, 2002. DOI: 10.1126/science.1074376.
https://doi.org/10.1126/science.1074376

[42] Ulrich Rührmair and Daniel E Holcomb. PUFs at a glance. In Proceedings of the conference on Design, Automation & Test in Europe, page 347. European Design and Automation Association, 2014. DOI: 10.7873/DATE.2014.360.
https://doi.org/10.7873/DATE.2014.360

[43] Ulrich Rührmair, Frank Sehnke, Jan Sölter, Gideon Dror, Srinivas Devadas, and Jürgen Schmidhuber. Modeling attacks on physical unclonable functions. In Proceedings of the 17th ACM conference on Computer and communications security, pages 237–249, 2010. DOI: 10.1145/1866307.1866335.
https://doi.org/10.1145/1866307.1866335

[44] Ulrich Ruhrmair and Jan Solter. PUF modeling attacks: An introduction and overview. In 2014 Design, Automation & Test in Europe Conference & Exhibition (DATE), 2014. DOI: 10.7873/DATE2014.361.
https://doi.org/10.7873/DATE2014.361

[45] Boris Škorić. Quantum readout of physical unclonable functions. In Proceedings of International Conference on Cryptology in Africa, pages 369–386. Springer, 2010. DOI: 10.1007/978-3-642-12678-9–22.
https://doi.org/10.1007/978-3-642-12678-9_22

[46] BORIS ŠKORIĆ . Quantum readout of physical unclonable functions. International Journal of Quantum Information, 10(01):1250001, 2012. DOI: 10.1142/S0219749912500013.
https://doi.org/10.1142/S0219749912500013

[47] Boris Škorić, Allard P Mosk, and Pepijn WH Pinkse. Security of quantum-readout PUFs against quadrature-based challenge-estimation attacks. International journal of quantum information, 11(04):1350041, 2013. DOI: 10.1142/S021974991350041X.
https://doi.org/10.1142/S021974991350041X

[48] Boris Škorić, Pepijn WH Pinkse, and Allard P Mosk. Authenticated communication from quantum readout of PUFs. Quantum Information Processing, 16(8):200, 2017. DOI: 10.1007/s11128-017-1649-0.
https://doi.org/10.1007/s11128-017-1649-0

[49] G Edward Suh and Srinivas Devadas. Physical unclonable functions for device authentication and secret key generation. In Proceedings of 44th ACM/IEEE Design Automation Conference, pages 9–14. IEEE, 2007. 2007 44th ACM/IEEE Design Automation Conference.
https://ieeexplore.ieee.org/document/4261134

[50] Lars Tebelmann, Michael Pehl, and Vincent Immler. Side-channel analysis of the tero PUF. In International Workshop on Constructive Side-Channel Analysis and Secure Design, pages 43–60. Springer, 2019. DOI: 10.1007/978-3-030-16350-1–4.
https://doi.org/10.1007/978-3-030-16350-1_4

[51] Ravitej Uppu, Tom AW Wolterink, Sebastianus A Goorden, Bin Chen, Boris Škorić, Allard P Mosk, and Pepijn WH Pinkse. Asymmetric cryptography with physical unclonable keys. Quantum Science and Technology, 4(4):045011, 2019. DOI: 10.1088/2058-9565/ab479f.
https://doi.org/10.1088/2058-9565/ab479f

[52] William K Wootters and Wojciech H Zurek. A single quantum cannot be cloned. Nature, 299(5886):802, 1982. DOI: 10.1038/299802a0.
https://doi.org/10.1038/299802a0

[53] Yao Yao, Ming Gao, Mo Li, and Jian Zhang. Quantum cloning attacks against PUF-based quantum authentication systems. Quantum Information Processing, 15(8):3311–3325, 2016. DOI: 10.1007/s11128-016-1316-x.
https://doi.org/10.1007/s11128-016-1316-x

[54] Robert Young, Utz Roedig, and Jonathan Roberts. Quantum physical unclonable function, 2019. Patent: US10148435B2.
https://patents.google.com/patent/US10148435B2/en

[55] Karol Życzkowski and Hans-Jürgen Sommers. Average fidelity between random quantum states. Physical Review A, 71(3):032313, 2005. DOI: 10.1103/PhysRevA.71.032313.
https://doi.org/10.1103/PhysRevA.71.032313

Cited by

[1] Giulio Gianfelici, Hermann Kampermann, and Dagmar Bruß, “Theoretical framework for physical unclonable functions, including quantum readout”, Physical Review A 101 4, 042337 (2020).

[2] Mina Doosti, Niraj Kumar, Mahshid Delavar, and Elham Kashefi, “Client-Server Identification Protocols with Quantum PUF”, arXiv:2006.04522.

[3] Niraj Kumar, Rawad Mezher, and Elham Kashefi, “Efficient Construction of Quantum Physical Unclonable Functions with Unitary t-designs”, arXiv:2101.05692.

[4] Koustubh Phalak, Abdullah Ash-Saki, Mahabubul Alam, Rasit Onur Topaloglu, and Swaroop Ghosh, “Quantum PUF for Security and Trust in Quantum Computing”, arXiv:2104.06244.

[5] Juan Carlos Garcia-Escartin, “Physical Unclonable Functions with Boson Sampling”, arXiv:1911.08417.

[6] Sreeja Chowdhury, Ana Covic, Rabin Yu Acharya, Spencer Dupee, Fatemeh Ganji, and Domenic Forte, “Physical Security in the Post-quantum Era: A Survey on Side-channel Analysis, Random Number Generators, and Physically Unclonable Functions”, arXiv:2005.04344.

[7] Mina Doosti, Mahshid Delavar, Elham Kashefi, and Myrto Arapinis, “A Unified Framework For Quantum Unforgeability”, arXiv:2103.13994.

The above citations are from SAO/NASA ADS (last updated successfully 2021-06-15 14:07:27). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2021-06-15 14:07:25: Could not fetch cited-by data for 10.22331/q-2021-06-10-475 from Crossref. This is normal if the DOI was registered recently.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.

Generative Data Intelligence

Quantum Physical Unclonable Functions: Possibilities and Impossibilities

Abstract

Popular summary

► BibTeX data

► References

Cited by

Telegram announces plans to tokenize stickers, emojis as NFTs on TON blockchain

Runes could solve Bitcoin’s long-term security: IntoTheBlock

Latest Intelligence

Dominick Puni 2024 NFL Draft Profile

Cam Hart 2024 NFL Draft Profile

Leaving Behind Bitcoin Sectarianism

Justin Sun Reveals The Perfect Recipe For A Crypto Market Boom – CryptoInfoNet

“A Bright Spring Day” By Grant Yun: Exploring Digital Art On Solana | NFT And Web3 Culture News – CryptoInfoNet

Top-5 jurisdictions for obtaining Forex license

Chat with us