Statistically-Secure Bit Commitment and Coin Flipping Protocols Based on Quantum Hardware Assumptions

Statistically-Secure Bit Commitment and Coin Flipping Protocols Based on Quantum Hardware Assumptions Roo Dunnill∗ and Mina Doosti School of Informatics, University of Edinburgh, Quantum Software Lab

arXiv:2608.11187v1 [quant-ph] 11 Aug 2026

Bit commitment is impossible to achieve with unconditional security, even in quantum cryptography. We show that statistically secure bit commitment, satisfying both hiding and binding, can be constructed from hybrid locked physical unclonable functions (HLPUFs), a hardware primitive that combines classical hardware tokens and quantum communication. Our protocol uses these hardware assumptions in a novel and non-trivial way to achieve the first mistrustful two-party cryptographic protocol based on hybrid hardware modules. We prove statistical hiding and binding under natural assumptions on the HLPUF and using a carefully designed challenge generation algorithm as a subroutine of our bit-commitment protocol. The construction also yields the first hardware-based coin-flipping protocol. Our results suggest a new paradigm for secure two-party cryptography in quantum networks, combining rigorous security guarantees with a concrete route toward practical implementation.

I.

INTRODUCTION

Bit commitment is one of the fundamental primitives of modern cryptography, and a basic building block for a wide range of tasks, including coin flipping, zero-knowledge protocols, secure multiparty computation, and general two-party cryptographic constructions [1, 2]. Informally, bit commitment allows a sender Alice to commit to a bit in such a way that the value is hidden from the receiver Bob until Alice later chooses to reveal it, while at the same time preventing Alice from changing the bit after the commitment is made. In the quantum setting, bit commitment is particularly important for two reasons. First, it is a canonical test case for how much unconditional security quantum information can offer in mistrustful cryptography. Second, it sits at the centre of an extensive web of reductions: positive and negative results for bit commitment often propagate to many other two-party tasks. Early optimism that quantum mechanics might enable information-theoretically secure bit commitment was overturned by the Mayers–Lo–Chau impossibility theorem. In the plain non-relativistic two-party model, unconditionally secure quantum bit commitment is impossible: any protocol that is sufficiently concealing necessarily admits a coherent cheating strategy for Alice, based on purification and delayed measurement, that breaks binding [3, 4]. This impossibility result is one of the foundational no-go theorems of quantum cryptography. It sharply distinguishes key distribution, where unconditional security is achievable, from general two-party computation, where mistrustful tasks are much more constrained [5]. The no-go theorem also shows that, in order to achieve this functionality, a compromise needs to be made in the security level or setup assumptions. There are several major directions in which the impossibility theorem has been circumvented. One line of work considers weaker or asymmetric notions of security. For example, Aharonov et al. introduced quantum bit escrow, a weaker primitive that captures a form of cheat sensitivity rather than full binding and hiding [6]. Another important line develops computationally secure quantum commitments. A seminal result of Dumais et al. [7] gives a non-interactive quantum commitment scheme that is perfectly concealing and computationally binding under the assumption of quantum one-way permutations. Later works extended this picture and obtained statistically hiding or statistically binding quantum commitments from broader quantum one-way assumptions [8–10]. A different and highly influential route is to enrich the physical model. In relativistic cryptography, Minkowski causality can be used to enforce non-communication constraints between separated agents, and Kent [11] showed that unconditionally secure relativistic quantum bit commitment is possible in this setting. Another notable family of results is achieved by employing physical assumptions. An important work in this area is the bounded-quantum-storage model and the noisy-storage model, where limitations on an adversary’s quantum memory are assumed. Bit commitment and other two-party primitives become achievable with information-theoretic security in these models [12–15]. These works are especially relevant conceptually for us, as they illustrate the fundamental importance of hardware or physical assumptions in circumventing quantum cryptographic no-go’s and as new constructive routes for designing protocols.

∗ R.Dunnill@sms.ed.ac.uk

2 This paper follows that philosophy and studies bit commitment from a hardware assumption, while not just relying on existential results, but takes a constructive and implementation-aware protocol design mindset. In this work, we answer the following central question: How can we design constructive and implementable statistically-secure bit-commitment schemes that only rely on hardware assumptions? We answer the above question by introducing the first statistically secure quantum bit commitment protocol that achieves both hiding and binding under hybrid hardware assumptions. Our construction relies on a specific hardware module for which we explicitly state the required assumptions, and under these assumptions, the protocol achieves arbitrarily small hiding and binding without any additional adversarial restrictions on the mistrustful parties. Beyond its theoretical significance, our result provides a concrete design based on off-the-shelf hardware components and feasible quantum communication infrastructures, offering a practical route to implementing this fundamental cryptographic primitive in quantum networks. Our starting point is the emerging landscape of physically unclonable functions (PUFs) and their quantum variants. Classical PUFs are hardware objects whose challenge-response behaviour is difficult to clone or model, and they have been extensively studied as a resource in hardware security [16–20]. Quantum PUFs (QPUFs) were introduced in [21] as fully quantum variants of PUFs, and that work showed that, unlike in the classical setting, one can formulate provably secure quantum hardware assumptions. However, existing QPUF-based protocols face many practical limitations: in addition to requiring the transmission of high-dimensional quantum states over the channel, they require a quantum database to store the QPUF outputs prior to the initiation of the protocol. Hybrid quantumclassical variants, known as Hybrid Locked PUFs (HLPUFs), were proposed in [22] to combat these limitations by replacing the quantum database with a classical one. An HLPUF combines a classical PUF, which by itself is insufficient for provable security, with a quantum communication layer that upgrades the resulting hardware module to resist powerful quantum adversaries. In this way, hybrid PUFs aim to combine rigorous security guarantees with practical implementability. So far, however, quantum and hybrid PUFs have mostly been studied for functionalities such as authentication [21–25] and, more recently, key generation and secure storage [26]. In all of these settings, the honest parties use the hardware against an external network adversary. By contrast, quantum or hybrid hardware assumptions have not previously been explored for inherently mistrustful two-party tasks such as bit commitment or coin flipping. This makes the study of mistrustful multiparty protocols in this setting both interesting and technically challenging. A central conceptual insight of our work is that there is a fundamental reason for this difficulty: hardware assumptions fit naturally into settings with honest users and an external adversary, but they do not immediately extend to mistrustful two-party cryptography. Indeed, as we explain in the next section, a naive attempt to use a hardware module for bit commitment is bound to fail for a simple but crucial reason: if one of the parties is malicious, how can the protocol force that party to actually use the prescribed hardware token at all? Our protocol is designed specifically with this limitation in mind. It combines an enrolled and later locked hardware token with a BB84-style encoding of a challenge-dependent response substring, and it is carefully structured so that replacing the token with a lookalike device becomes statistically difficult. The key idea is to introduce a deliberate asymmetry between the verification part of the response and the committed stream of states. This asymmetry is essential both for ruling out the main cheating strategy and for evading the standard quantum no-go result. We also present a natural coin-flipping protocol built black-box from our bit-commitment scheme. To the best of our knowledge, this is also the first strong quantum coin-flipping protocol based on hybrid hardware assumptions. Combined, our results suggest a new paradigm for secure two-party cryptography in quantum networks, combining rigorous security guarantees with a concrete route toward practical implementation.

A.

Our technical contribution

To elaborate on our technical contribution, we first note that a naive hardware-based bit-commitment design is insufficient. If Alice is simply asked to prepare a commitment using a hardware token and later open it with a classical challenge-response pair, there is no reason a malicious Alice must actually use the prescribed token in the intended way. In particular, if the protocol only checks consistency of the opening data after the fact, then Alice may try to delay the effective choice of the bit until the opening phase, or replace the honest hardware by a look-alike strategy whose behaviour is driven only by the revealed opening data and not by the challenge-dependent rule that the real hardware is supposed to enforce. The main obstacle is therefore not merely to hide the committed value, but to force the opening transcript to be anchored to genuine hardware behaviour while still keeping the bit hidden before the reveal stage.

3 Our first contribution is to show how to overcome exactly this obstacle using a deliberately asymmetric variant of an HLPUF. At a high level, the hardware response is split into two parts: a shorter verifier part and a longer payload part. The verifier part is used only to unlock and authenticate the hardware behaviour for a given challenge, while the payload part is what is encoded into the commitment state. The commitment itself is formed by taking the same payload and encoding it in one of two BB84 basis patterns determined by a complete challenge response pair and a carefully generated alternative challenge. The pair of candidate challenges is revealed already in the commit phase, but the hidden information is which of the two corresponding basis patterns was used to encode the commitment. This asymmetry is what makes the construction work: it allows the commitment state to conceal the bit, while ensuring that a successful opening must still be tied to a genuine challenge-response pair embedded in honest hardware. Our second contribution is a statistical hiding analysis for this construction. Informally, if the enrolled substrings are close to uniform, then the two honest commit states are correspondingly close, and in the ideal case, they are perfectly indistinguishable. In particular, the protocol achieves hiding because Bob receives a BB84-encoded commitment of a hardware response under two possible candidate challenges, which before opening, he does not know which basis pattern is the relevant one. At the informal level, the guarantee can be summarised as the trace distance between the commitment states dtr (ρ0 , ρ1 ) ≤ η, where η measures the deviation of the target distribution from uniform. In the ideal uniform case, this gives perfect hiding. At the proof level, the key idea is an intrinsic ensemble-symmetry argument: the pair-challenge generation procedure is designed so that, for all sent qubits, the four BB84 states appear in a statistically balanced way. Consequently, the two honest commitment ensembles are locally identical on these coordinates and hence globally identical, up to the residual leakage caused by the possibility that Bob can forge access to the locked hardware. Our third contribution is a binding proof that captures all possible attack strategies. The binding argument is based on finding the operator norm of the sum of all accepted openings. The core of the proof relies on the input-output spaces of the HLPUF, preventing the standard entanglement based bit commitment attacks to occur. This, combined with the commitment lying in the pre-disclosed basis preparations results in a bound of p0 + p 1 ≤ 1 + 2

−ℓmin 4

(1)

Where pb is the probability that a cheating Alice successfully opens bit b. Beyond the security statements themselves, we view the proof techniques as one of the main contributions of the paper. On the hiding side, the central idea is to impose a balanced combinatorial structure on the generated challenges, which makes the honest commitment ensembles intrinsically symmetric. On the binding side, the proof reduces arbitrary cheating strategies to an operator-norm bound for a small family of acceptance projectors. This reduction cleanly separates the intrinsic quantum-overlap limitation from the hardware-dependent parameters. Together, these two ingredients provide a constructive route to statistically secure bit commitment from hybrid hardware assumptions, and they also lead directly to a coin-flipping protocol via the standard commitment-based transformation. II.

PRELIMINARIES AND NOTATIONS

We start by introducing some of our main notations, as well as background on primitives and definitions that we use throughout the paper. For β ∈ {0, 1}, let |z⟩β denote the single-qubit BB84 encoding of z ∈ {0, 1} in basis β, where basis 0 is the computational basis (or Z basis) and basis 1 is the Hadamard basis (or X basis). For strings z, β ∈ {0, 1}ℓmin , we define |z⟩β :=

ℓO min

|zj ⟩βj .

(2)

j=1

If a ∈ {0, 1}2k , we write a = (θ, u) with θ, u ∈ {0, 1}k and define the k-qubit BB84 state where u denotes the value bit and θ denotes the basis bit. (ex: for a = (1, 0) would correspond to state |ψ a ⟩ := |u⟩θ = |+⟩). A.

Distance measures

We introduce the notation and definitions for the classical and quantum distances that we use. Let x and y be sets of x, y ∈ Fn2 . we denote their Hamming distance as follows: d(x, y) = |{i ∈ {1, ..., n}|xi ̸= yi }|

(3)

4 We also use the Hamming weight to measure the number of non-zero elements of a group. Let x be a set x ∈ Fn2 . Hamming weight is defined as: wt(x) = |{i ∈ {0, ..., n}|xi ̸= 0}|

(4)

For two quantum states ρ, σ ∈ (H2 )n , the trace distance is: dtr (ρ, σ) :=

1 ∥ρ − σ∥1 . 2

(5)

We also use the operator norm. For a linear operator A, its operator (infinity) norm is ∥A∥∞ := sup ∥Ax∥2 .

(6)

∥x∥2 =1

Equivalently, ∥A∥∞ = σmax (A),, where σmax (A) denotes the largest singular value of A. B.

Bit commitment

Bit commitment is a central two-party cryptographic primitive that enables one of the parties to commit a bit value and reveal it later to the other party. The two core security features are that the committing party cannot change their commitment after they have sent it to the party, and that the receiving party cannot open this commitment before the reveal step. This is known as the hiding (concealing) and binding property of a commitment scheme. Bit Commitment. A bit-commitment protocol between Alice and Bob has two phases. (i) In the commit phase, Alice with input b ∈ {0, 1} interacts with Bob and leaves Bob with a commitment transcript and possibly a quantum register. (ii) In the open phase, Alice sends opening information and Bob outputs either a bit b′ ∈ {0, 1} or reject. The protocol is correct if an honest execution with committed bit b is accepted with probability 1 and opens to b. In a dishonest scenario, the bit-commitment is expected to have two properties known as hiding (or concealing) and binding, defined as below: Definition 1 (ϵ-hiding Bit Commitment). A quantum bit commitment scheme is ϵ-hiding (concealing) if the receiving party satisfies: p0 + p1 − 1 ≤ ϵ(n)

(7)

Where pb is the probability the receiver can guess the commitment b correctly. Equivalently (more relevant for quantum commitment schemes), a bit-commitment protocol is ε-hiding if for every dishonest Bob the joint states after the commit phase corresponding to honest commitments of 0 and 1 is at most ε-distinguishable. Definition 2 (ϵ-binding Bit Commitment). A quantum bit commitment scheme is ϵ binding if the committing party satisfies: p0 + p1 − 1 ≤ ϵ(n)

(8)

Where pb is the probability the committer can reveal b. This notion of binding is often referred to as weak-binding, and it is the formulation often used for quantum bit commitment schemes [27]. C.

Coin flipping

Coin flipping is another fundamental two-party primitive, first introduced by Blum[28] and allows two mistrustful parties to agree on a shared random bit. The security of the protocol relies on neither of the parties being able to bias the protocol with probability higher than 21 + ϵ. Strong coin flipping is a variant of coin flipping where both outcomes are restricted by this bias.

5 Definition 3 (Strong coin flipping). A two-party protocol outputs a bit c ∈ {0, 1} or aborts. It is correct if, when both parties are honest, the output is uniformly distributed on {0, 1} and the protocol does not abort. It has bias at most ϵ if for every dishonest Alice and every dishonest Bob, Pr[c = c∗ ] ≤

1 +ϵ 2

(9)

for each target bit c∗ ∈ {0, 1}, except with abort probability explicitly accounted for by the protocol.

D.

Classical and Hybrid PUFs

Physical Unclonable Functions (PUFs) are hardware primitives that use the intrinsic randomness of physical devices as unique fingerprints, or physical keys, with the idea of providing unpredictability and unclonability against external adversaries and even the manufacturer of the device [29]. As a formal cryptographic primitive, some PUFs give a physical instantiation of a one-way function through hardware assumptions [16]. Classical PUFs (cPUFs) can be modelled as f : {0, 1}n → {0, 1}m . However, the description of the function itself is not accessible due to the hardware assumption and the behaviours of these devices are characterized via sets of Challenge-Response Pairs (CPRs) {(xi , ri )}qi through querying the device. A classical PUF can also be modelled as a probabilistic function f : R × X → Y where X is the input space, Y is the output space of f and R is the identifier. The creation of a classical PUF is formally expressed by invoking a manufacturing process f ← MP C (λ), where λ is the security parameter. An important property of a classical PUF in this model is the notion of randomness, which is the maximal probability of pfx (y) with an input xj ∈ X on PUF fi where i ∈ R. Definition 4 (p-Randomness (from [22])). We define the p-randomness of a classical PUF f : R × X → Y as p := max pfx (y). x∈X y∈Y

(10)

Apart from these, a device with an underlying function f needs to satisfy certain requirements to be qualified as a PUF. There exist different sets of such requirements in the literature [21–23, 30], however, for this work we adopt the minimal set of requirements also used in hybrid schemes such as in [22], which includes: δ1 -Robustness, δ2 -Collision Resistance, and δ3 -Uniqueness. We omit the formal definition of these requirements for the purpose of this work, as we are not explicitly using them here, and whenever referring to a classical PUF, we assume these requirements are satisfied.

1.

Hybrid and Hybrid-locked PUFs

The main hardware module we use for our protocol is a specific type of Hybrid Locked PUF (HLPUF) introduced in [22]. An HLPUF is a hybrid device that combines a cPUF with quantum encoding and verification. Given the vulnerabilities of most existing cPUFs against modelling and machine learning attacks, HLPUFs are designed to boost the security of cPUFs against both general classical and also powerful quantum adversaries. The construction first takes a cPUF f : {0, 1}n → {0, 1}2m and encodes the outputted bitstring into BB84 states. The output is split into m pairs of bits where:  00 7→ |0⟩ , 01 7→ |1⟩ , ∀ 1 ≤ j ≤ m, f (x)2j−1 f (x)2j 7→ (11) 10 7→ |+⟩ , 11 7→ |−⟩ . This creates the mapping Ef : {0, 1}n → (H2 )m where x → ⊗m j=1 |ψ2j−1,2j ⟩ ⟨ψ2j−1,2j |, which is referred to as a HPUF. This encoding alone significantly improves security against powerful modelling attacks, but it does not protect against adaptive adversaries. To address this, an additional mechanism, called lock, is incorporated into the construction to provide security against adaptive quantum adversaries. Its output is partitioned as f (x) = f1 (x)∥f2 (x), where only f2 (x) is encoded into BB84 states by the HPUF. The lock component takes as input both the challenge and an m-qubit state, and outputs the state |ψf2 (x) ⟩ only if the supplied quantum state passes an internal verification procedure. In this verification step, the device measures the j-th qubit in the basis specified by the (2j − 1)-st bit of f1 (x), where 0 denotes the computational basis and 1 denotes the Hadamard basis. The device accepts only if, for every 1 ≤ j ≤ m, the measurement outcome equals the 2j-th bit of f1 (x). This locking mechanism prevents adaptive querying of the

6 cPUF and thereby provides unforgeability against such adversaries. This is particularly important in adversarial protocols, where the party holding the device may otherwise have adaptive access to it. These devices were originally introduced for authentication, with security based on a collection of hardware assumptions. The central assumption is that the device cannot be opened or tampered with and is therefore treated as a black box. This complements the locking mechanism: the HLPUF may initially operate in an unlocked mode, in which adaptive queries are possible, but once it is locked, it is assumed to be impossible to unlock it again at any later stage. III.

BIT-COMMITMENT PROTOCOL

At a high level, our protocol begins with the committer, Alice, holding the device in its unlocked mode and using it to create a classical database. She then locks the device and sends it to the verifier, Bob, who will later use it for verification. The main subtlety of the protocol is to exploit the properties of a specific HLPUF variant in a way that Alice is forced to use the hardware module to generate both the commitment state and the associated transcript needed to open the commitment later. At the same time, Bob cannot use the locked device to learn or open the committed value before the opening phase, due to the unforgeability properties of the HLPUF. Conceptually, hiding follows directly from the hardware assumption, whereas binding is more subtle and depends on the specific structure and properties of the protocol. In our protocol, Alice’s commitment to a bit b is a quantum state consisting of a sequence of BB84 states that encodes a partial response of the HLPUF under a challenge that serves as a key. For each commitment state, there are also two associated challenges, x0 and x1 . The challenge x0 supplies the response substring used in the commitment, while x1 is generated carefully by a dedicated algorithm and supplies the alternative basis pattern. Both are valid challenges of the HLPUF. These two challenges are announced publicly to Bob, but the crucial hidden information is which basis pattern was used for the encoding. In the opening phase, the full challenge-response relation is revealed, including the used challenge and the two halves of its response, f1 (x0 ) and f2 (x0 ). This information enables Bob to query the HLPUF in locked mode and verify that Alice did not cheat. To present our bit-commitment protocol, we first introduce two main ingredients. The first is the construction of the hardware module used in the protocol, together with the assumptions on which its security relies. The second is the algorithm used to generate alternative challenges. We begin with the hardware construction and its assumptions. A.

Asymmetric HLPUF construction and assumptions

Let us first specify the construction of the Hybrid Locked PUF that we need for our protocol, together with hardware assumptions. Our construction is similar to the one in [22], using an underlying classical PUF f : {0, 1}n → {0, 1}m , but with an asymmetric split in the response of the underlying classical PUF. As such, we refer to our variant here as an asymmetric HLPUF. Concretely, the classical response is split as f (x) = f1 (x) ∥ f2 (x),

f1 : X → {0, 1}s ,

f2 : X → {0, 1}t ,

s + t = m,

(12)

where s = 2k and t = 2l are even. For a string z ∈ {0, 1}2l , write z = (θ, u),

θ, u ∈ {0, 1}l ,

(13)

and define the associated l-qubit BB84 state |ψcz ⟩ := |u⟩θ .

(14)

In the unlocked mode (mode 0), the asymmetric HLPUF takes as input x and outputs the full classical response f (x) = f1 (x) ∥ f2 (x).

(15)

In the locked mode (mode 1), the asymmetric HLPUF takes as input a challenge x and a k-qubit state ρ, performs the verification measurement  f1 (x) |ψv ⟩⟨ψvf1 (x) | , I − |ψvf1 (x) ⟩⟨ψvf1 (x) | , (16) and, if the first outcome occurs, outputs the l-qubit state |ψcf2 (x) ⟩ . Otherwise it aborts and outputs ⊥.

(17)

7 Assumption 1 (Locked-mode black-box property and irreversibility ). In the locked mode (mode 1), it is impossible to obtain direct classical access to f2 (x) from the hardware token. In particular, the locked token can only be accessed f (x) through the interface above, which returns either the quantum state |ψc 2 ⟩ or ⊥. Also, once the token has been switched from mode 0 to mode 1, it cannot be unlocked again, and the functions f1 and f2 embedded in the token cannot be altered or queried except through the public locked-mode interface. Assumption 2 (cPUF bias). The underlying classical PUF is imperfect and can have a δr bias. Namely, for every output bit j ∈ [m] and every distribution on challenges, Pr[f (X)j = 1] −

1 ≤ δr . 2

(18)

Moreover, the output bits are independent and identically distributed. Assumption 3 (HLPUF unforgeability). The Asymmetric HLPUF is εforge -unforgeable where εforge (s, t) is a negligible function in s and t. Unforgeability is the main security property of PUFs and refers to the inability of an adversary to predict or produce valid outcomes for unseen instances. We rely on the general unforgeability of HLPUFs established in [22], and we assume that this property is satisfied by the construction we use here. Since the proof in our setting follows as a subset of the arguments already given in [22], we do not repeat it here.

B.

Challenge-pair generation algorithm

As mentioned before, our protocol uses a subroutine whose role is to generate an alternative challenge x1 from x0 such that they satisfy certain properties. For a given randomly selected challenge x0 , it flips the Jth bits of x0 to create x1 . The set J is designed in a way so that for a given random string r ∈ {0, 1}ℓmin , the corresponding f2 (x0 )J = r where ℓmin := αt with 0 < α ≤ 1. Finally it uses oracle access to the unlocked HLPUF to test to see if their response provides enough separation to be used for verification. It outputs the first candidate that passes all filters. Here we need to make a note about the notation first. Each challenge x ∈ {0, 1}n is written as x = (xbas , xaux ),

xbas ∈ {0, 1}t ,

xaux ∈ {0, 1}n−t .

(19)

where the t-bit string xbas determines the generation of an alternative challenge in the algorithm below. Whenever Algorithm 1 selects coordinates, we write J = (j1 , . . . , jℓmin ) for the ordered list of selected indices; subscripts such as f2 (x0 )J follow this order. When only membership or Hamming distance is relevant, we identify J with its underlying set. Since we mostly care about these basis value, we denote β(x) := xbas J

(20)

Where |J| = ℓmin and we use this notation instead of x inside the algorithm. The remaining n − ℓmin bits play no direct role in the encoding and serve only as auxiliary challenge degrees of freedom in the alternative challenge generation procedure. In particular, for any pair of challenges (x0 , x1 ), the number of coordinates on which the two basis strings differ is d(β(x0 ), β(x1 )) which is exactly the Hamming distance between ℓmin bits of the two challenges. To minimise the probability of breaking the binding while obtaining the bound stated above, we choose the length α α of the verification string as s := ℓmin 4 . The security parameter ℓmin should be chosen between 2 ≤ p ≤ 1 − 2 where p := 12 + δr . The reasoning for these choices are given in Theorem 10 and Lemma 3. This algorithm also ensures that the distribution of encoded bits of f2 (x0 ) are chosen randomly while the basis they are encoded in are also uniformly randomly sampled; allowing for the indistinguishability condition to be met. While Bob receives both challenges in the commit phase, this indistinguishability condition results in him gaining no information on the bit committed. The formal description of the Algorithm is given below.

8 Algorithm 1 Balanced alternative-challenge generation Require: a challenge x0 , oracle access to the asymmetric HLPUF in unlocked mode, and a target parameter ℓmin Ensure: either a challenge x1 together with the selected ordering J or fail $ 1: Choose a random string r ← {0, 1}ℓmin 2: Query the unlocked HLPUF on x0 and obtain f (x0 ) = f1 (x0 ) ∥ f2 (x0 ),

f2 (x0 ) = u ∈ {0, 1}t .

3: if wt(f2 (x0 )) ≥ wt(r) ∧ t − wt(f2 (x0 )) ≥ ℓmin − wt(r) then 4: else 5: return fail 6: end if 7: repeat 8: Initialise J ← () 9: for i ∈ [|r|] do 10: 11: 12: 13: 14: 15:

$

Sample j ← {k ∈ [t] : f2 (x0 )k = ri } \ J J ← (J, j) end for x1 ← x0 (x1 )j ← (x0 )j ⊕ 1, ∀ j ∈ J Query the unlocked HLPUF on x1 and obtain f1 (x1 ). 2

≤ 2−s/2 17: return x1 and retain the selected ordering J

16: until ⟨ψ f1 (x0 ) |ψ f1 (x1 ) ⟩

Algorithm 1, which we also denote as Alg(x0 ) for brevity (referring to its returned challenge x1 , with J retained as auxiliary information), has certain properties that we use in the proofs, and we list them here to clarify their importance. Proposition 1 (Properties of Algorithm 1). Suppose Algorithm 1 returns another challenge x1 for the original challenge x0 . Let J = (j1 , . . . , jℓmin ) be the ordered list retained by the algorithm; its underlying set is exactly { j ∈ [t] : (x0 )j ⊕ (x1 )j = 1 }.

(21)

Then the algorithm has the following properties: (i) Challenge permutability: both challenges have the same probability of producing the other when entered into the algorithm Pr[Alg(x0 ) = x1 ] = Pr[Alg(x1 ) = x0 ]

(22)

(ii) Challenge Hamming weight probability: given an inputted randomly chosen challenge, both challenges have the same probability of Hamming weights ∀ i Pr[(x0 )i = 1] = Pr[(x1 )i = 1] =

1 2

(23)

(iii) Large basis-distance: The Hamming-distance of the basis bits of both challenges is equal to a certain threshold lmin d(β(x0 ), β(x1 )) = ℓmin ,

(24)

|J| = d(β(x0 ), β(x1 )) = ℓmin ,

(25)

Equivalently,

(iv) Perfect value and basis balancing: On the differing coordinates, the basis and value bits are balanced such that they produce evenly distributed BB84 states. With the ordered list J = (j1 , . . . , jℓmin ) selected by the algorithm, uJ = f2 (x0 )J = r, and hence the selected value string is uniformly distributed: Pr[uJ = v] = 2−ℓmin

∀ v ∈ {0, 1}ℓmin .

(26)

9 In particular, ∀ j ∈ J Pr[uj = 1] =

1 2

(27)

and Pr[(x0 )j = 1] =

1 2

(28)

(v) Verifier separation: the encoded state of the f1 (.) for the two challenges have small overlap. ⟨ψ f1 (x0 ) |ψ f1 (x1 ) ⟩

2

≤ 2−s/2 .

(29)

All of these properties are straightforwardly satisfied by the specific steps of the algorithm. However, for the algorithm to be useful in our protocol, an additional important requirement is that it can efficiently find an alternative candidate for a given selected challenge. In other words, the algorithm must be efficient both in its query complexity to the HLPUF and in its combinatorial complexity. In the following three theorems, we show that this is indeed the case. The proofs are deferred to the Appendix A. Lemma 1 (Symmetry of Challenge Generation). Let x0 ∈ {0, 1}n be a challenge selected uniformly at random. Let x1 be a challenge created by Algorithm 1 from x0 , by flipping a set of indices in J ⊆ [t]. Given the unforgeability conditions of the HLPUF, then: Pr [Alg(x0 ) = x1 ] = Pr [Alg(x1 ) = x0 ]

(30)

Proof. Let J = {j1 ...ji } ⊆ [t] be the set of indices selected in 1. The algorithm produces x1 from x0 by flipping all indices within set J. ∀ j ∈ J,

(x1 )j ← (x0 )j ⊕ 1

(31)

By the assumptions of the construction of the HLPUF, the output distribution of f2 (x) is identical for all x ∈ {0, 1}n . As such, for any two challenges x, x′ , the distributions of f2 (x), f2 (x′ ) are identical. Consequently, the distribution of all possible sets J generated from a response is identical for all uniformly sampled challenges. Since the indices are selected at random from the positions of f2 (x), the probability of selecting a set J is identical for all challenges. As such, the probability to obtain a specific set J ∗ := {j ∈ [t] : (x0 )j ̸= (x1 )j } is the same for both challenges x0 , x1 . Furthermore, XOR is self-inverse. As such, applying J ∗ to x0 generates x1 and applying J ∗ to x1 generates x0 . Thus the probability that x0 generates x1 is the same as the probability that x1 generates x0 Pr[Alg(x0 ) = x1 ] = Pr[J = J ∗ |x0 ] = Pr[J = J ∗ |x1 ] = Pr[Alg(x1 ) = x0 ]

(32)

Theorem 1 (High-Probability Combinatorial Feasibility Test in Algorithm 1). Let ℓmin be the number of qubits in ρb , let t be the length of the string f2 (x0 ) and let δr be the bias of the HLPUF. The probability that the combinatorial feasibility test in Algorithm 1 is satisfied for one sampled string r is: Pr[success] =

ℓX min  y=0

1 2

ℓmin 

ℓmin y

 t−(ℓX k  t−k min −y)    t 1 1 + δr − δr k 2 2

(33)

k=y

$

Theorem 2 (High-probability combinatorial feasibility of Algorithm 1). Let x0 ← − {0, 1}n , and suppose that the bits t of f2 (x0 ) ∈ {0, 1} are independently and identically distributed with a bias at most δr . where p := Pr[f2 (x0 )j = 1]. $

Let r ← − {0, 1}ℓmin be sampled independently, where ℓmin = αt,

0 < α < 1,

(34)

and assume that ℓmin is an integer. If α α <p<1− , 2 2

(35)

10 then the combinatorial feasibility condition in Step 3 of Algorithm 1, namely wt(f2 (x0 )) ≥ wt(r)

and

t − wt(f2 (x0 )) ≥ ℓmin − wt(r),

(36)

is satisfied with probability Pr[feasible] = 1 − e−Ω(t) .

(37)

Theorem 3 (Query complexity of Algorithm 1). Conditioned on the combinatorial feasibility test being satisfied, for every fixed δr < 1/2 the expected number of unlocked-HLPUF queries made by Algorithm 1 satisfies E[Q] = 2 + e−Ω(s) .

(38)

Protocol 1 (HLPUF bit commitment.). Public parameters: security parameters s = 2k and t; challenge space X ; minimum basis-distance parameter ℓmin ; The protocol uses an Asymmetric HLPUF as defined in Section III A with bias parameter δr . Setup phase: 1. Alice queries the HLPUF in mode 0 on enough challenges to obtain a database of challenge-response pairs DB = {(x, f1 (x), f2 (x)) : x ∈ U}. For each enrolled challenge x ∈ U , she also runs Algorithm 1 to produce an associated challenge x1 and retains the corresponding ordered list J. 2. Alice locks the HLPUF, switches it to mode 1, and sends it to Bob. Commit phase: The commitment is a bit b ∈ {0, 1}. 3. Alice samples a challenge x0 ∈ U, together with its associated challenge x1 and ordered list J. 4. Alice sends Bob the pair (x0 , x1 ) together with the ordering J. 5. Alice prepares the ℓmin -qubit state ( ρb :=

|f2 (x0 )J ⟩⟨f2 (x0 )J |β(x0 )

if b = 0,

|f2 (x0 )J ⟩⟨f2 (x0 )J |β(x1 )

if b = 1.

Where f2 (x0 )J corresponds to the indices of f2 (x0 ) that are in J := {j ∈ [t] : (x0 )j ̸= (x1 )j } and |J| = ℓmin . 6. Alice sends the register containing ρb to Bob. 7. Bob checks that ∀j ∈ J, (x0 )j ⊕ (x1 )j = 1, otherwise he rejects Open phase: 7. Alice sends the triple (b, a, z), where a = f1 (x0 ),

z = f2 (x0 ).

Verification phase: 8. Bob prepares the verifier state |ψva ⟩ from the revealed classical string a. 9. Bob queries the HLPUF on (x0 , |ψva ⟩). If the token outputs ⊥, he rejects. Otherwise he receives a l-qubit state σ. 10. Bob measures σ with the two-outcome test {|ψcz ⟩⟨ψcz | , I − |ψcz ⟩⟨ψcz |}. If this test rejects, he rejects the opening. 11. Bob measures the stored commitment register in basis ( β(x0 ) if b = 0, γb := β(x1 ) if b = 1. obtaining a string z ′ ∈ {0, 1}ℓmin . If z ′ ̸= zJ , he rejects. Otherwise, he accepts bit b.

11 C.

Formal protocol description

Our hardware-based bit-commitment protocol works as follows: In the setup phase, Alice uses the HLPUF in its unlocked mode to build a database of valid challenge-response pairs and, for each challenge, computes a corresponding challenge. She then locks the device and sends it to Bob. To commit to a bit b, Alice chooses a challenge x0 together with its counterpart x1 , sends Bob the ordered pair (x0 , x1 ) together with the retained ordering J, and prepares a BB84 sequence of states using the response f2 (x0 ), encoded either in the basis of the challenge x0 or in the basis of the alternative challenge x1 depending on the committed bit. Later, to open the commitment, Alice reveals which challenge was used to prepare the state and provides the corresponding classical response information. Bob then uses the locked HLPUF to verify that the revealed response is genuine, and checks that the previously received quantum state is consistent with the claimed bit. In this way, the protocol forces Alice to commit using valid HLPUF data, while preventing Bob from learning the bit before the opening phase. The formal description of the protocol is given in Protocol 1 IV.

SECURITY PROOF

We now formally prove correctness, hiding and binding for Protocol 1. Theorem 4 (Correctness). If both parties are honest and the announced pair (x0 , x1 ) was produced by Algorithm 1, then Protocol 1 opens correctly to the committed bit, and Bob accepts with probability 1. Proof. Let Alice commit to bit b ∈ {0, 1}, and let z = f2 (x0 ) ∈ {0, 1}t ,

a = f1 (x0 ) ∈ {0, 1}s .

(39)

Let zJ be the elements of z in the group J := {j ∈ [t] : (x0 )j ̸= (x1 )j } and |J| = ℓmin . By the protocol, Alice sends the commitment register in the state ( |zJ ⟩⟨zJ |β(x0 ) if b = 0, ρb = (40) |zJ ⟩⟨zJ |β(x1 ) if b = 1. In the opening phase, Alice reveals the challenge x0 , together with b, a = f1 (x0 ), and z = f2 (x0 ). In Step 9, Bob queries the locked HLPUF on (x0 , |ψva ⟩). Since a = f1 (x0 ), the verifier state is exactly the correct state for the original challenge, and the token outputs the l-qubit BB84 state |ψcz ⟩. Hence Bob’s test in Step 10 accepts with probability 1. In Step 11, Bob measures the stored commitment register in basis ( β(x0 ) if b = 0, γb = (41) β(x1 ) if b = 1. This is exactly the basis in which Alice prepared the state ρb . Therefore the measurement outcome is precisely zJ , and Bob accepts. Thus the protocol opens to the correct bit and is accepted with probability 1. To prove hiding, we first prove a Lemma to show that, without any side information from the HLPUF, commitment states ρ0 and ρ1 are perfectly indistinguishable, and further the conditional states for the ordered pairs are also indistinguishable. Lemma 2 (Perfect intrinsic ensemble hiding). Fix a public ordered pair (x0 , x1 ) and its associated ordering J produced by Algorithm 1. Given Property (iv) in Proposition 1, the two honest commit ensemble states corresponding to b = 0 and b = 1 are perfectly indistinguishable: dtr (ρ0 , ρ1 ) = 0.

(42)

Proof. Let x0 denote the original challenge, and let x1 denote the alternative element of the pair. These are sent labelled during the commitment stage, with Bob having full knowledge of their entire classical description. Given the properties of unforgeability of the HLPUF, he cannot know beyond a negligible probability what the corresponding f2 (x0 ) or f2 (x1 ) are. This consequently results in him gaining no information from using these challenges to either measure the states early, or to try to unlock the HLPUF before the reveal stage. This forces him to attempt to distinguish the two possible quantum ensembles with no knowledge of the underlying encoded string.

12 Let U := f2 (x0 )J ∈ {0, 1}ℓmin denote the random payload string. The states relevant to Bob are the ensemble density operators X ρ0 = Pr[U = u] |u⟩⟨u|β(x0 ) (43) u∈{0,1}ℓmin

and X

ρ1 =

Pr[U = u] |u⟩⟨u|β(x1 ) .

(44)

u∈{0,1}ℓmin

By Property (iv) of Proposition 1, U is uniformly distributed over {0, 1}ℓmin . Therefore ρ0 =

1 2ℓmin

X

|u⟩⟨u|β(x0 ) =

I 2ℓmin

|u⟩⟨u|β(x1 ) =

2ℓmin

u∈{0,1}ℓmin

(45)

and similarly ρ1 =

1 2ℓmin

X u∈{0,1}ℓmin

I

.

(46)

Hence ρ0 = ρ1 , and therefore dtr (ρ0 , ρ1 ) = 0.

(47)

Now we show that the hiding parameter is essentially bounded by the unforgeability of HLPUF, and hence we show an exponentially small hiding parameter. Theorem 5 (Hiding). Let εforge be the unforgeability parameter of HLPUF according to Assumption 3. Then Protocol 1 is εhide -hiding with εhide ≤ εforge .

(48)

In particular, if the HLPUF is exponentially unforgeable in s, then εhide = negl(s). Proof. Fix an arbitrary cheating Bob. Let F be the event that Bob successfully produces a verifier state accepted by the locked HLPUF on at least one of the two announced candidate challenges before the opening phase. By definition, Pr[F ] ≤ εforge .

(49)

Since εforge isthe maximum probability, over all cheating strategies for Bob carried out before the opening phase, that Bob successfully produces a verifier state accepted by the locked HLPUF. Let ρ0 and ρ1 denote Bob’s full commit-phase states for honest commitments to 0 and 1, respectively. Decompose them according to the event F : ρb = (1 − Pr[F ]) ρ¬F + Pr[F ] ρF b b ,

b ∈ {0, 1}.

(50)

Conditioned on ¬F , Bob has no successful verifier forgery, so by Lemma 2, ρ¬F = ρ¬F 0 1 .

(51)

¬F F F dtr (ρ0 , ρ1 ) ≤ (1 − Pr[F ]) dtr (ρ¬F 0 , ρ1 ) + Pr[F ] dtr (ρ0 , ρ1 ).

(52)

Therefore, using joint convexity of trace distance,

The first term vanishes and the second is at most Pr[F ], since trace distance is always at most 1. Hence dtr (ρ0 , ρ1 ) ≤ Pr[F ] ≤ εforge . This is exactly the claimed bound and by Assumption 3, the right hand side quantity is negligible.

(53)

13 Lemma 3 (Bounding Operator Norm of Opening Measurements). Fix the public pair (x0 , x1 ) and its corresponding ordered list J, with underlying set J = {j ∈ [t] : (x0 )j ̸= (x1 )j } and |J| = ℓmin , and set x = x0 . Let Rx ⊆ {0, 1}s × {0, 1}t

(54)

denote the set of verifier/output pairs (a, z) such that, if Bob queries the locked HLPUF on (x, |ψva ⟩) and then measures the returned state with the test {|ψcz ⟩⟨ψcz | , I − |ψcz ⟩⟨ψcz |},

(55)

S := {zJ : ∃ a ∈ {0, 1}s such that (a, z) ∈ Rx }.

(56)

the verification accepts. For this fixed J, let

Here the operator argument below treats Rx as an acceptance relation containing at most one accepted output string z for each verifier string a. The finite-copy test above is interpreted probabilistically. Let H := H ⊗ℓmin , and let, X P := |y⟩⟨y|β(x0 ) (57a) y∈S

Q :=

X

|y⟩⟨y|β(x1 ) = HP H =

y∈S

X

H |y⟩⟨y|β(x0 ) H

(57b)

y∈S

the operator norm of ||P + Q||∞ is bounded by, ||P + Q||∞ ≤ 1 + 2

2s−ℓmin 2

(58)

Proof. The operator norm can be bounded by ||P + Q||∞ = 1 + ||P Q||∞ ≤ 1 + ||P Q||F = 1 +

q

Tr[(P Q)† (P Q)]

(59)

Where || · ||F denotes the Frobenius norm. Given that both P and Q are projectors and the cyclic property of the trace Tr[(P Q)† (P Q)] = Tr[QP P Q] = Tr[QP Q] = Tr[HP HP HP H] = Tr[P HP HP ] = Tr[P HP H]

(60)

As trace is the sum of basis vectors Tr[A] =

X

⟨u| A |u⟩

(61)

u

Expressing P as a sum of states and expanding out the trace X X Tr[ |y⟩⟨y| H |z⟩⟨z| H] = y,z∈S

X

X

⟨u|y⟩ ⟨y| H |z⟩⟨z| H |u⟩ =

u∈{0,1}ℓmin y,z∈S

δu,y 2−ℓmin (−1)y·z (−1)u·z =

y,z∈S

X

2−ℓmin (−1)2y·z = 2−ℓmin |S|2

(62)

y,z∈S

Note that |S| ≤ 2s under the acceptance-relation above, since there are 2s input strings a and at most one associated output string for each a. Taking the square root leads to r 2s−ℓmin |S|2 ||P + Q||∞ = 1 + ||P Q||∞ ≤ 1 + =1+2 2 (63) ℓ min 2

Theorem 6 (Binding). Protocol 1 is εbind -binding with εbind ≤ 2

2s−ℓmin 2

(64)

which results in p0 + p 1 ≤ 1 + 2

2s−ℓmin 2

(65)

14 Proof. Fix an arbitrary cheating strategy for Alice. This strategy may be fully general: Alice may send Bob one half of an arbitrary entangled state in the commit phase, keep a private ancilla, measure that ancilla adaptively during the opening phase, and choose her classical opening data based on the measurement outcome. We now show that even in this most general setting, the total cheating probability is bounded by the claimed expression. By quantum state purification, any mixed state can be represented as a pure bipartite state, in a larger Hilbert space. Alice can leverage this knowledge to keep an entangled register A, in which after concluding on her commitment, Alice can measure this state in a given way to influence Bob’s register B. Let ρB denote Bob’s reduced commitment state immediately before the opening phase. For an attempted opening of bit b, Alice’s measurement on her private system induces a collection of subnormalised conditional states {τb,y }y∈S on Bob’s register, satisfying X τb,y ⪰ 0, τb,y = ρB . (66) y∈S

Let Π0,y := |y⟩⟨y|β(x0 ) and Π1,y := |y⟩⟨y|β(x1 ) . Conditioned on opening data corresponding to y, Bob accepts the commitment register only through the projector Πb,y . Hence X pb ≤ Tr[Πb,y τb,y ]. (67) y∈S

Since Π0,y ≤ P and Π1,y ≤ Q for every y ∈ S, it follows that p0 ≤ Tr[P ρB ],

p1 ≤ Tr[QρB ].

(68)

Therefore p0 + p1 ≤ Tr[(P + Q)ρB ] ≤ ∥P + Q∥∞ .

(69)

Applying Lemma 3 gives p0 + p1 ≤ ||P + Q||∞ ≤ 1 + 2

V.

2s−ℓmin 2

.

(70)

COIN FLIPPING FROM BIT COMMITMENT

We now build a coin-flipping protocol from Protocol 1 as a black box. Protocol CF (coin flipping from BC Protocol 1). 1. Alice samples a uniform random bit a ← {0, 1} and commits to a using Protocol BC⋆ . 2. Bob samples a uniform random bit b ← {0, 1} and sends b to Alice. 3. Alice opens the commitment. 4. If Bob rejects the opening, the protocol aborts. Otherwise both parties output c = a ⊕ b. Theorem 7 (Correctness of coin flipping). If both parties are honest, Protocol CF⋆ outputs a uniform bit and does not abort. Proof. By Theorem 4, the underlying commitment opens correctly with certainty. Conditional on acceptance, the protocol does not abort. Since a and b are independent uniform bits, a ⊕ b is uniform on {0, 1}. Theorem 8 (Fairness of coin flipping). Assume Protocol 1 is εhide -hiding and εbind -binding. Then Protocol CF has bias at most 1 δCF ≤ max{εhide , εbind }. (71) 2 In particular, under Theorems 5 and 6, n o ℓmin 1 δCF ≤ max εforge , 2− 4 . (72) 2

15 Proof. We consider dishonest Bob and dishonest Alice separately. Dishonest Bob. Bob receives the commitment transcript and the commitment register before sending his bit b. By Theorem 5, his distinguishing advantage between commitments of 0 and 1 is at most εhide , hence his bias is at most εhide /2. Dishonest Alice. Alice commits before learning Bob’s bit b. To force a target outcome c∗ after receiving b, she must successfully open the commitment to the bit a = c∗ ⊕ b.

(73)

1 1 1 p0 + p1 ≤ (1 + εbind ), 2 2 2

(74)

Since honest Bob chooses b uniformly at random,

so her bias is at most εbind /2. Taking the larger of the two cheating biases gives the claim.

VI.

DISCUSSION AND FUTURE WORK

We have presented a hardware-based route to statistically secure bit commitment and coin flipping in a nonrelativistic setting. Our construction uses Hybrid-Locked PUFs to benefit from both the availability of classical PUFs and the security advantages of quantum protocols. We then use this hardware token in a setting beyond its usual application, which is typically one where the parties are honest and security is only required against a network adversary. We design the protocol so that the commitment is tightly tied to the specific challenge-response behaviour of the hardware module, and we exploit the properties of the HLPUF to achieve statistical hiding and binding. The main challenge in designing such quantum protocols is to evade the impossibility of quantum bit commitment while at the same time forcing the commitment state to reflect genuine hardware behaviour. Our protocol addresses this by using the unforgeability property to obtain hiding, and the lock mechanism to enable a verification procedure that yields binding. We believe that both the protocol and the proof techniques developed here open new pathways toward secure two-party communication and computation in quantum networks using intrinsically weak, off-the-shelf PUFs whose security is amplified through protocol design. An appealing aspect of the protocol is that it allows for a variant in which early measurement is possible. Bob may measure each qubit in a random basis when received, recording each outcome. Then in the commit stage, he only keeps the information for which the bits of β(xb ) match the bases he measured in. Although this weakens the security parameter, this allows for a statistically secure protocol in which no quantum memory is required. Naturally, a full analysis on this protocol would be for future work. In contrast to the bounded or noisy quantum storage models, our construction does not require the assumptions regarding an adversary’s storage capabilities. This allows for the protocol to be indefinitely secure, rather than scaling either the number of qubits sent or time taken to run the protocol. The trade off involves the replacement of an adversary’s memory with that of the hardness of forging the HLPUF. It remains an open question as to how the tamper proof-ness of the device would be implemented and scaled. There are several natural next steps. One direction is to design simpler variants of the protocol with a less complex fake-challenge generation procedure. On the proof side, it would be desirable to obtain a fully composable security treatment, since the present analysis is carried out in the stand-alone setting. It would also be interesting to understand how far the same design principles extend to stronger tasks such as string commitment, oblivious transfer, and other mistrustful multiparty functionalities. Finally, experimental implementation of these protocols would be an especially intriguing direction for future work.

Acknowledgments

The authors would like to thanks Dominik Leichtle and Alexandru Cojocaru for helpful discussions at different stages of this work. RD acknowledges the support of the PhD Studentship from the Quantum Computing and Simulation QCS hub, grant number EP/T001062/1. MD acknowledges the support of the UK Engineering and Physical Sciences Research Council, the Integrated Quantum Networks Hub, grant reference EP/Z533208/1, and the

16 Quantum Advantage Pathfinder (QAP), with grant reference EP/X026167/1.

[1] J. Katz and Y. Lindell, Introduction to Modern Cryptography (CRC Press, 2015). [2] O. Goldreich, Foundations of Cryptography Vol 1: Basic Tools (Cambridge University Press, 2003). [3] D. Mayers, Unconditionally secure quantum bit commitment is impossible, Physical Review Letters 78, 3414 (1997). [4] H.-K. Lo and H. F. Chau, Is quantum bit commitment really possible?, Physical Review Letters 78, 3410 (1997). [5] T. Vidick and S. Wehner, Introduction to Quantum Cryptography (Cambridge University Press, 2024). [6] D. Aharonov, A. Ta-Shma, U. Vazirani, and A. Yao, Quantum bit escrow (2000), arXiv:quant-ph/0004017 [quant-ph]. [7] P. Dumais, D. Mayers, and L. Salvail, Perfectly concealing quantum bit commitment from any quantum one-way permutation, in Advances in Cryptology — EUROCRYPT 2000 , Lecture Notes in Computer Science, Vol. 1807, edited by B. Preneel (Springer, 2000) pp. 300–315. [8] T. Koshiba, Statistically-hiding quantum bit commitment from approximable preimage-size quantum one-way function, in Theory of Quantum Computation, Communication, and Cryptography, Lecture Notes in Computer Science, Vol. 5906, edited by H. Mori, H. Imai, and M. Owari (Springer, 2009) pp. 16–28. [9] T. Koshiba and T. Odaira, Non-interactive statistically-hiding quantum bit commitment from any quantum one-way function (2011), arXiv:1102.3441 [quant-ph]. [10] D. Unruh, Computationally binding quantum commitments, in Advances in Cryptology — EUROCRYPT 2016, Part II , Lecture Notes in Computer Science, Vol. 9666, edited by M. Fischlin and J.-S. Coron (Springer, 2016) pp. 497–527. [11] A. Kent, Unconditionally secure bit commitment by transmitting measurement outcomes, Physical Review Letters 109, 130501 (2012). [12] I. B. Damgård, S. Fehr, L. Salvail, and C. Schaffner, Cryptography in the bounded-quantum-storage model, in 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05) (IEEE Computer Society, 2005) pp. 449–458. [13] I. B. Damgård, S. Fehr, L. Salvail, and C. Schaffner, Cryptography in the bounded-quantum-storage model, SIAM Journal on Computing 37, 1865 (2008). [14] S. Wehner, C. Schaffner, and B. M. Terhal, Cryptography from noisy storage, Physical Review Letters 100, 220502 (2008). [15] N. H. Y. Ng, S. K. Joshi, C. C. Ming, C. Kurtsiefer, and S. Wehner, Experimental implementation of bit commitment in the noisy-storage model, Nature Communications 3, 1326 (2012). [16] R. Pappu, B. Recht, J. Taylor, and N. Gershenfeld, Physical one-way functions, Science 297, 2026 (2002), https://www.science.org/doi/pdf/10.1126/science.1074376. [17] J. Guajardo, S. S. Kumar, G.-J. Schrijen, and P. Tuyls, Fpga intrinsic pufs and their use for ip protection, in Cryptographic Hardware and Embedded Systems - CHES 2007, edited by P. Paillier and I. Verbauwhede (Springer Berlin Heidelberg, Berlin, Heidelberg, 2007) pp. 63–80. [18] U. Ruhrmair, H. Bisch, and S. Katzenbeisser, Strong pufs: Models, constructions and security proofs, in Towards Hardware Intrinsic Security (2010) pp. 79–96. [19] R. Maes and I. Verbauwhede, Physically uncloneable functions: A study on the state of the art and future research directions, in Towards Hardware Intrinsic Security (2010) pp. 3–38. [20] U. Ruhrmair, Disorder based security hardware: An overview, in Secure System Design and Trustable Computing (2016) pp. 3–37. [21] M. Arapinis, M. Delavar, M. Doosti, and E. Kashefi, Quantum physical unclonable functions: Possibilities and impossibilities, Quantum 5, 475 (2021). [22] K. Chakraborty, M. Doosti, Y. Ma, C. Wadhwa, M. Arapinis, and E. Kashefi, Quantum Lock: A Provable Quantum Communication Advantage, Quantum 7, 1014 (2023). [23] M. Doosti, M. Delavar, E. Kashefi, and M. Arapinis, A unified framework for quantum unforgeability (2021), arXiv:2103.13994 [quant-ph]. [24] S. Goswami, M. Doosti, and E. Kashefi, Hybrid authentication protocols for advanced quantum networks (2025), arXiv:2504.11552 [quant-ph]. [25] N. Laurent-Puig, M. Doosti, A. Innocenzi, and E. Diamanti, Unconditional authentication in quantum key distribution via hybrid entangled physical unclonable functions, arXiv preprint arXiv:2605.04650 (2026). [26] K. Nilesh, C. Deppe, and H. Boche, Quantum puf based secret key generation and secure storage with side information, in 2025 IEEE International Symposium on Information Theory (ISIT) (2025). [27] D. Mayers, Unconditionally secure quantum bit commitment is impossible, Physical Review Letters 78, 3414–3417 (1997). [28] M. Blum, Coin flipping by telephone a protocol for solving impossible problems, SIGACT News 15, 23–27 (1983). [29] V. Galetsky, S. Ghosh, C. Deppe, and R. Ferrara, Comparison of quantum puf models, in 2022 IEEE Globecom Workshops (GC Wkshps) (IEEE, 2022) pp. 820–825. [30] F. Armknecht, D. Moriyama, A.-R. Sadeghi, and M. Yung, Towards a unified security model for physically unclonable functions, in Topics in Cryptology-CT-RSA 2016: The Cryptographers’ Track at the RSA Conference 2016, San Francisco, CA, USA, February 29-March 4, 2016, Proceedings (Springer, 2016) pp. 271–287.

17 Appendix A: Complexity Analysis of Algorithm 1

Here we provide a more detailed formulation of the Theorems 1, 2 and 3, and their proofs. Theorem 9 (Success Probability of Step 3 in Algorithm 1). Let t be the length of f2 (x) and ℓmin ≤ t be the number of qubits in the register ρb . Let δr be the bias of the HLPUF. The probability that the algorithm succeeds in one run is: Pr[success] =

ℓX min  y=0

1 2

ℓmin 

ℓmin y

 t−(ℓX k  t−k min −y)    t 1 1 + δr − δr k 2 2

(A1)

k=y

Proof. The algorithm succeeds whenever f2 (x0 ) contains at least as many 0s as r and at least as many 1s as r. This occurs when the properties wt(f2 (x)) ≥ wt(r) ∧ t − wt(f2 (x)) ≥ lmin − wt(r) are satisfied. The distribution of the string f2 (x0 ) can be modelled by the binomial distribution X := wt(f2 (x0 )) ∼ Bin(t, p) , p =

1 + δr 2

(A2)

with expectation µx := E[X] = tp

(A3)

while the distribution of the string r can be modelled by the binomial distribution 1 Y := wt(r) ∼ Bin(ℓmin , ) 2

(A4)

ℓmin αt = 2 2

(A5)

with expectation µy := E[Y ] =

Conditioning on the event that Y = y, success occurs if y ≤ X ≤ t − (ℓmin − y), therefore t−(ℓmin −y) 

X

Pr[success|Y = y] =

k=y

 t k t−k (p) (1 − p) k

(A6)

By the law of total probability Pr[success] =

ℓX min

Pr[success|Y = y] Pr[Y = y]

(A7)

y=0

Therefore: Pr[success] = Pr[wt(f2 (x)) ≥ wt(r) ∧ t − wt(f2 (x)) ≥ lmin − wt(r)] =  t−(ℓX k  t−k ℓX min −y)    min  ℓmin  ℓmin t 1 1 1 + δr − δr 2 y k 2 2 y=0

(A8)

k=y

$

Theorem 10 (High-probability combinatorial feasibility of Algorithm 1). Let x0 ← − {0, 1}n , and suppose that the bits $

of f2 (x0 ) ∈ {0, 1}t are independently and identically distributed with a bias at most δr . Let r ← − {0, 1}ℓmin be sampled independently, where ℓmin = αt,

0 < α < 1,

(A9)

and assume that ℓmin is an integer. If α α <p<1− , 2 2

(A10)

18 then the combinatorial feasibility condition in Step 3 of Algorithm 1, namely wt(f2 (x0 )) ≥ wt(r)

and

t − wt(f2 (x0 )) ≥ ℓmin − wt(r),

(A11)

is satisfied with probability Pr[feasible] = 1 − e−Ω(t) .

(A12)

Equivalently, except with probability e−Ω(t) , Algorithm 1 can select ℓmin distinct indices j1 , . . . , jℓmin ∈ [t] such that f2 (x0 )ji = ri

for every i ∈ [ℓmin ].

(A13)

The constant implicit in the Ω(t) notation may depend on α and p, but not on t. Proof. Let X := wt(f2 (x0 )) ∼ Bin(t, p),

(A14)

µx := E[X] = tp,

(A15)

with expectation

and let 

1 Y := wt(r) ∼ Bin ℓmin , 2

 ,

(A16)

with expectation µy := E[Y ] =

αt ℓmin = . 2 2

(A17)

Since x0 and r are sampled independently, the random variables X and Y are independent. The combinatorial feasibility condition in Step 3 is satisfied precisely when X≥Y

and

t − X ≥ ℓmin − Y,

(A18)

or equivalently, Y ≤ X ≤ t − ℓmin + Y.

(A19)

α α <p<1− , 2 2

(A20)

Since

we may choose a constant εy ∈ (0, 1) sufficiently small such that α α (1 + εy ) < p < 1 − (1 + εy ). 2 2

(A21)

Define ymax := (1 + εy )µy ,

ymin := (1 − εy )µy .

(A22)

Applying multiplicative Chernoff bounds to Y gives ε2y µy Pr[Y ≥ (1 + εy )µy ] ≤ exp − 2 + εy

! (A23)

and ε2y µy Pr[Y ≤ (1 − εy )µy ] ≤ exp − 2

! .

(A24)

19 Since µy = αt/2, it follows that the event EY := {ymin ≤ Y ≤ ymax }

(A25)

Pr[EY ] = 1 − e−Ω(t) .

(A26)

ymax ≤ X ≤ t − ℓmin + ymin ,

(A27)

Y ≤ ymax ≤ X

(A28)

X ≤ t − ℓmin + ymin ≤ t − ℓmin + Y.

(A29)

EX := {ymax ≤ X ≤ t − ℓmin + ymin } .

(A30)

Pr[EX ] ≥ 1 − Pr[X < ymax ] − Pr[X > t − ℓmin + ymin ].

(A31)

occurs with probability

Conditioned on EY , it is sufficient that

because then

and

Define the event

By the union bound,

By the choice of εy , ymax =

αt (1 + εy ) < tp = µx . 2

(A32)

Therefore, the lower-tail Chernoff bound gives    Pr[X < ymax ] ≤ exp −

1 − yµmax x 2

Substituting µx = tp and ymax = αt(1 + εy )/2, we obtain "

2

 µx  .

t p − α2 (1 + εy ) Pr[X < ymax ] ≤ exp − 2p

(A33)

2 # .

(A34)

  α t − ℓmin + ymin = t 1 − (1 + εy ) > tp = µx . 2

(A35)

Similarly,

Using the upper-tail Chernoff bound  2  δ µx Pr[X > (1 + δ)µx ] ≤ exp − , 2+δ

(A36)

with δ=

t − ℓmin + ymin − 1, µx

(A37)

gives "

2

(t − ℓmin + ymin − µx ) Pr[X > t − ℓmin + ymin ] ≤ exp − µx + t − ℓmin + ymin

# .

(A38)

20 Substituting the corresponding values yields
2 # t 1 − p − α2 (1 + εy ) . Pr[X > t − ℓmin + ymin ] ≤ exp − 1 + p − α2 (1 + εy )

(A39)

2 # t p − α2 (1 + εy ) Pr[EX ] ≥ 1 − exp − 2p "
2 # t 1 − p − α2 (1 + εy ) − exp − . 1 + p − α2 (1 + εy )

(A40)

"

Consequently, "

Both exponents are linear in t with strictly positive coefficients. Hence, Pr[EX ] = 1 − e−Ω(t) .

(A41)

Y ≤ X ≤ t − ℓmin + Y.

(A42)

Finally, the event EX ∩ EY implies

Since EX depends only on X, while EY depends only on Y , independence gives Pr[Y ≤ X ≤ t − ℓmin + Y ] ≥ Pr[EX ∩ EY ] = Pr[EX ] Pr[EY ]    = 1 − e−Ω(t) 1 − e−Ω(t)

(A43)

= 1 − e−Ω(t) . This proves the claimed high-probability combinatorial feasibility. Theorem 11 (HLPUF query complexity of Algorithm 1). Assume the setting of Theorem 9. Let Q denote the total number of unlocked-HLPUF queries made by Algorithm 1 on input x0 , counting the initial query to obtain f (x0 ). Conditioned on the combinatorial feasibility test being satisfied, then E[Q] ≤ 1 +

1 psep

,

(A44)

where  psep ≥ 1 −

1−

E[Q] ≤ 1 +



1 − δr 2

2 !s/2 .

(A45)

Equivalently, 1 1− 1−

2 s/2 1 2 − δr

.

(A46)

In particular, for every fixed δr < 12 , E[Q] = 2 + e−Ω(s) .

(A47)

Proof. Algorithm 1 always makes one unlocked-HLPUF query on the original challenge x0 in order to obtain f (x0 ) = f1 (x0 ) ∥ f2 (x0 ).

(A48)

After that, the balancing filter uses only classical computation on x0 , f2 (x0 ), and the public map β, so it requires no additional HLPUF queries. Every additional unlocked-HLPUF query is used only to test whether a candidate challenge x satisfies the verifier-separation condition.

21 Write s = 2k, so the verifier state has k = 2s BB84 qubits. Fix one verifier qubit of the original challenge, determined by two bits of f1 (x0 ). For a tested candidate challenge x, the corresponding verifier qubit is orthogonal to the original one whenever the basis bit matches and the value bit is opposite. By the independent bitwise bias assumption, the probability of this orthogonal event is at least  q⊥ ≥

1 − δr 2

2 .

(A49)

If this orthogonal event occurs on at least one verifier qubit, then the total verifier overlap is zero, and in particular ⟨ψvf1 (x0 ) |ψvf1 (x) ⟩

2

≤ 2−s/2 .

(A50)

Therefore a sufficient condition for a candidate challenge to pass the verifier-separation test is that at least one of the k = 2s verifier qubits be orthogonal. Since the qubits are independent, 

k

psep ≥ 1 − (1 − q⊥ ) ≥ 1 −

1−

1 − δr 2

2 !s/2 .

(A51)

Under the sampling assumption, each tested candidate succeeds independently with probability at least psep . Thus the number N of additional candidate tests before the first successful one is stochastically dominated by a geometric random variable with success probability psep , and E[N ] ≤

1

.

(A52)

E[Q] ≤ 1 +

1 . psep

(A53)



2

psep

Since Q = 1 + N , we obtain

Finally, for every fixed δr < 1/2, the quantity 1−

1 − δr 2

(A54)

is a constant strictly smaller than 1. Hence  1 − psep ≤

1−

1 − δr 2

2 !s/2

= e−Ω(s) ,

(A55)

which implies E[Q] = 1 +

1 = 2 + e−Ω(s) . 1 − e−Ω(s)

(A56)

Related documents

• Experimental Side Channel Analysis of Protocol Stages in Quantum Identity Authentication#405583
• Operational Roles of QRNG-Derived Quantum Entropy in Bitcoin Proof-of-Work Architectures#972043
• Impossibility of perfect cheating for single-qubit position verification#617762
• Impossibility of perfect cheating for single-qubit position verification#617262
• Security framework for practical quantum key distribution with imperfect devices#1109837