Efficient Construction of Quantum Physical Unclonable Functions with Unitary t-designs

Niraj Kumar, Rawad Mezher, Elham KashefiarXiv 2021 · DOI · arXiv

Abstract

Quantum physical unclonable functions (QPUFs) are emerging as critical hardware solutions for secure cryptographic functionalities, including key exchange, message authentication, and entity identification. Recent theoretical work establishes that provable security against quantum polynomial-time adversaries requires QPUFs to be unitaries sampled uniformly from the Haar measure. However, implementing such unitaries requires exponential resources, creating a significant feasibility gap. In this work, we propose an efficient construction using unitary $t$-designs, termed QPUF$_t$. We modify existing security definitions to accommodate efficient constructions and demonstrate that QPUF$_t$ maintains provable security guarantees against bounded quantum polynomial adversaries with $t$-query access. This represents the first application of unitary $t$-designs for arbitrary $t$. Furthermore, we investigate noise-resilience against unitary noise, concluding that while some resilience is achievable as system size increases, practical implementation will likely require error mitigation or correction.

1. Introduction

Physical Unclonable Functions (PUFs) serve as "digital fingerprints" for hardware, leveraging microscopic physical variations from the manufacturing process to generate unique, unclonable responses. In the quantum realm, QPUFs extend these capabilities, offering theoretically superior security for quantum communication and authentication tasks.

The primary challenge in QPUF design is the requirement for the device to behave like a unitary matrix sampled uniformly from the Haar measure—essentially a truly random rotation in a high-dimensional Hilbert space. While this provides maximum security, implementing a Haar-random unitary on $n$ qubits requires a circuit depth that scales exponentially with $n$, making it physically impossible for practical systems.

2. Proposed Construction: QPUF$_t$

To bridge the gap between theoretical security and physical realizability, we propose using unitary $t$-designs. A $t$-design is a distribution of unitaries that mimics the statistical properties (moments) of the Haar measure up to the $t$-th order. If an adversary is limited to $t$ queries, they cannot distinguish a $t$-design from a truly Haar-random unitary.

Schematic representation of a Quantum Physical Unclonable Function (QPUF) mapping an input state to an output state through a random quantum circuit.

Our construction utilizes a Random Quantum Circuit (RQC) model. We employ a 1D chain of qubits where nearest-neighbor gates are applied in a structured pattern. These gates are selected from an approximately universal set, allowing the circuit to explore the state space efficiently. Unlike Haar-random unitaries, these QPUF$_t$ devices can be implemented with a circuit depth that scales polynomially with the number of qubits and the security parameter $t$.

3. Redefining Security for Practicality

Because $t$-designs are efficiently constructible, we must update standard security definitions. We introduce the concept of "Practical Unknownness." This definition accounts for the fact that while a polynomial-time adversary could theoretically simulate a known efficient circuit, they cannot distinguish a specific, secret QPUF instance from a random one when given only limited black-box interaction. We prove that QPUF$_t$ retains "selective unforgeability," meaning an adversary cannot predict the response to a new challenge state even after observing multiple challenge-response pairs.

4. Numerical Validation and Results

We validated our construction through numerical simulations, measuring the "distinguishability" (via the diamond norm) between different QPUF instances. A high distinguishability is essential to ensure that two different devices do not produce the same response.

Simulations were conducted for systems of 4, 6, and 8 qubits with varying circuit depths. Even with shallow circuits (4 blocks of gates), the distinguishability was remarkably high:

  • 4 Qubits: Distinguishability $\ge 1.99$
  • 8 Qubits: Distinguishability $\ge 1.99999$

These results confirm that even relatively low-depth RQCs can effectively approximate the maximal distinguishability of Haar-random unitaries.

5. Noise Resilience and Limitations

We analyzed the impact of unitary noise—imperfections in the quantum gates themselves. Our analysis shows that while noise shifts the distribution, the device remains a $t$-design, though its closeness to the ideal Haar measure degrades.

One limitation of the current study is the focus on unitary noise rather than more complex decoherence (stochastic noise). As system sizes scale, the error rates per qubit must decrease to maintain security properties. Consequently, we conclude that integrating quantum error correction or mitigation will be necessary for large-scale, real-world QPUF deployment.

6. Conclusion

By replacing ideal Haar-random unitaries with unitary $t$-designs, we provide a path toward practical, provably secure quantum hardware. QPUF$_t$ offers a scalable solution for quantum authentication and cryptography, marking a significant milestone in the transition from theoretical quantum primitives to realizable security hardware.

Summary updated

Abstract

Quantum physical unclonable functions, or QPUFs, are rapidly emerging as theoretical hardware solutions to provide secure cryptographic functionalities such as key-exchange, message authentication, entity identification among others. Recent works have shown that in order to provide provable security of these solutions against any quantum polynomial time adversary, QPUFs are required to be a unitary sampled uniformly randomly from the Haar measure. This however is known to require an exponential amount of resources. In this work, we propose an efficient construction of these devices using unitary t-designs, called QPUF_t. Along the way, we modify the existing security definitions of QPUFs to include efficient constructions and showcase that QPUF_t still retains the provable security guarantees against a bounded quantum polynomial adversary with t-query access to the device. This also provides the first use case of unitary t-design construction for arbitrary t, as opposed to previous applications of t-designs where usually a few (relatively low) values of t are known to be useful for performing some task. We study the noise-resilience of QPUF_t against specific types of noise, unitary noise, and show that some resilience can be achieved particularly when the error rates affecting individual qubits become smaller as the system size increases. To make the noise-resilience more realistic and meaningful, we conclude that some notion of error mitigation or correction should be introduced.
BibTeX
@misc{kumar2021efficient,
  author = {Niraj Kumar and Rawad Mezher and Elham Kashefi},
  title = {{Efficient Construction of Quantum Physical Unclonable Functions with Unitary t-designs}},
  year = {2021},
  eprint = {2101.05692},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2101.05692},
}
Figure