⚛️ quantum physics

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

This paper presents the first statistically secure bit commitment and coin-flipping protocols based on hybrid locked physical unclonable functions (HLPUFs), overcoming the impossibility of unconditional security in quantum cryptography by combining classical hardware tokens with quantum communication to achieve a new paradigm for practical, mistrustful two-party cryptography.

Original authors: Roo Dunnill, Mina Doosti

Published 2026-08-12

📖 8 min read🧠 Deep dive

CC BY 4.0

Original authors: Roo Dunnill, Mina Doosti

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

=== SUMMARY ===
Imagine you are trying to build a digital vault that is so secure, not even a super-intelligent robot with infinite time could crack it. This is the dream of "unconditional security" in cryptography. For decades, scientists have been trying to build a specific kind of vault called "bit commitment." Think of it like a sealed envelope: you put a secret note inside, hand it to a friend, and promise that you can't swap the note later, while your friend can't peek inside until you say so. It sounds simple, but in the quantum world—the realm of atoms and light particles where things can be in two places at once—famous math theorems proved this is impossible to do perfectly without extra help. It's like trying to build a house of cards that never falls, even in a hurricane; the laws of physics say it can't be done if you only have air and paper.

However, scientists have found a clever workaround: instead of relying only on math, they can rely on the physical world itself. Imagine using a unique, uncopyable fingerprint made of hardware to lock the vault. This paper explores a new way to build that vault using a special mix of old-school computer chips and new-school quantum physics. The goal is to create a system where two people who don't trust each other can still play fair games, like flipping a coin or making a secret bet, without needing to trust a third party or rely on the enemy being too stupid to cheat.

The Impossible Game and the Hardware Hack

In the world of cryptography, "bit commitment" is the digital equivalent of a sealed envelope. You (Alice) want to commit to a choice (a 0 or a 1) and hand it to your friend (Bob). You need to promise two things: first, that Bob can't peek at your choice before you're ready to reveal it (this is called hiding); and second, that once you've sealed the envelope, you can't sneakily change your choice to the other number (this is called binding).

For a long time, scientists thought quantum mechanics could solve this perfectly. But then, a famous "no-go" theorem came along and said, "Nope, not possible." It turns out that in a purely quantum world, if you try to hide the bit perfectly, you leave a loophole that lets the cheater change their mind later. It's like a magic trick where the magician can't make the rabbit disappear without leaving a clue that they could pull a different rabbit out of the hat later.

To get around this, the authors of this paper decided to stop trying to solve the problem with just math and light. Instead, they brought in a physical object: a Hybrid Locked Physical Unclonable Function, or HLPUF for short.

Think of an HLPUF as a magical, uncopyable "black box" token.

Physical Unclonable: Just like no two snowflakes are alike, no two of these hardware tokens are exactly the same. Even the factory that made them can't copy the internal wiring. If you try to scan it and build a fake, the fake will behave differently.
Hybrid: It's a mix of a standard computer chip (which is easy to make) and a quantum layer (which is hard to fake).
Locked: This is the special sauce. The token has a "lock" mechanism. Once you use it in a certain way, it locks itself up. You can't open it again to see what's inside or change how it works.

The New Protocol: A Game of "Trust the Box"

The authors designed a protocol (a set of rules for a game) that uses this magical box to solve the impossible problem. Here is how the game works, step-by-step:

1. The Setup (The Enlistment)
Alice starts with the HLPUF token in an "unlocked" state. She asks the token a bunch of questions (challenges) and writes down the answers (responses) in a notebook. This is her database. Then, she flips a switch to lock the token. Now, the token is sealed. She hands this locked token to Bob.

2. The Commitment (The Sealed Envelope)
Alice wants to commit to a bit (0 or 1). She picks a question from her notebook, say "Question X."

She asks the token for the answer to "Question X."
She also uses a special algorithm to generate a "fake" question, "Question Y," which is very similar to X but slightly different.
She sends both Question X and Question Y to Bob.
Now, here is the magic trick: She takes the answer to Question X and turns it into a string of quantum particles (qubits).
- If she wants to commit to 0, she encodes the answer using the "style" (basis) of Question X.
- If she wants to commit to 1, she encodes the same answer using the "style" of Question Y.
She sends this string of quantum particles to Bob.

Why can't Bob peek?
Bob has the questions, but he doesn't know which "style" Alice used. Because the answers are random and the styles are mixed up, the quantum particles look exactly the same to him whether she chose 0 or 1. It's like sending a message in a bottle where the bottle looks identical whether the message inside says "Yes" or "No." He can't tell the difference until she opens it.

Why can't Alice cheat?
Alice has the locked token. To change her mind, she would need to change her commitment after the fact. But to prove she didn't change her mind, she has to reveal the full answer to the token.

If she tries to lie, she has to guess the answer to the token's question without actually having the token.
But the token is unclonable. She can't make a fake one.
And the token is locked. She can't ask it new questions to figure out the answer.
The only way to win is to have the real answer from the real token. If she tries to fake it, the math says she will fail almost every time.

The Results: A New Kind of Security

The paper proves that this system works with statistical security. This means that while a super-smart cheater might be able to change their commitment, the odds are so astronomically low that it's practically impossible. It's not "mathematically impossible" (which the paper says can't be done), but it's "so unlikely you'll never see it happen."

The authors showed two main things:

Perfect Hiding: Bob cannot guess the bit before the reveal. The quantum states are so similar that even with a perfect quantum computer, he can't tell them apart.
Strong Binding: Alice cannot change her bit after sending the quantum particles. The only way to open the envelope successfully is to have the genuine, unforgeable answer from the hardware token.

They also used this bit-commitment game to build a Coin Flipping protocol. Imagine Alice and Bob want to decide who goes first in a game by flipping a coin, but they are in different cities and don't trust each other. Using this new hardware-based method, they can flip a coin that neither can rig. If Alice tries to force the coin to land on Heads, she has to break the hardware token, which is statistically impossible.

Why This Matters

This paper suggests a new way forward for the future of the internet. Instead of hoping that hackers are too dumb to break our codes, or that they don't have enough computer memory, we can build systems that rely on the physical laws of the hardware itself.

The authors admit that this isn't a magic wand that solves everything instantly. They note that building these tokens requires specific hardware assumptions (like the token being truly unclonable and the lock being unbreakable). But they argue that this is a realistic path. We already have the chips; we just need to add the quantum layer and the locking mechanism.

In short, the paper says: "We can't make a perfect vault out of pure math, but if we build a vault out of a special, uncopyable physical key, we can make one that is secure enough for the real world." It's a shift from "trust the math" to "trust the physics," offering a concrete route to secure communication in a world where everyone is suspicious of everyone else.

=== DRAFT ===
Here is a detailed technical summary of the paper "Statistically-Secure Bit Commitment and Coin Flipping Protocols Based on Quantum Hardware Assumptions" by Roo Dunnill and Mina Doosti.

Problem Statement

Bit commitment is a fundamental cryptographic primitive essential for tasks like coin flipping, zero-knowledge proofs, and secure multiparty computation. However, the Mayers–Lo–Chau impossibility theorem establishes that unconditionally secure quantum bit commitment is impossible in a standard non-relativistic two-party model. Any protocol that is sufficiently concealing (hiding) inevitably admits a coherent strategy for the committer (Alice) based on purification and delayed measurement, thereby breaking the binding property.

Existing approaches to circumvent this no-go theorem typically rely on:

Weaker security notions (e.g., cheat sensitivity).
Computational assumptions (e.g., quantum one-way permutations).
Relativistic constraints (e.g., non-communication between separated agents).
Storage limitations on the adversary (e.g., bounded-quantum-storage or noisy-storage models).

The authors identify a gap: Physical hardware assumptions have been successfully used for authentication and key generation against external adversaries, but they have not been effectively adapted for mistrustful two-party cryptography (where both parties may be malicious). A straightforward attempt to use a hardware token for bit commitment fails because a malicious party could simply replace the prescribed hardware with a look-alike device or delay their choice of the committed bit until the opening phase. The core challenge is to design a protocol that forces the committer to use the genuine hardware behavior while keeping the committed bit hidden from the receiver.

Methodology

The authors propose a constructive protocol based on Hybrid Locked Physical Unclonable Functions (HLPUFs). An HLPUF is a hardware primitive combining a classical PUF (cPUF) with a quantum communication layer.

1. The Hardware Primitive (Asymmetric HLPUF):
The protocol utilizes an asymmetric variant of the HLPUF introduced in prior work [22]. The classical response $f(x)$ of the underlying cPUF is split into two parts:

$f_1(x)$ (Verifier): A shorter string used for verification.
$f_2(x)$ (Payload): A longer string encoded into quantum states.

The device operates in two modes:

Unlocked Mode (Setup): Alice queries the device to build a database of challenge-response pairs.
Locked Mode (Execution): The device is "locked." It accepts a challenge $x$ and a quantum state $|\psi\rangle$ . It verifies if $|\psi\rangle$ matches the expected state derived from $f_1(x)$ . If valid, it outputs the quantum state corresponding to $f_2(x)$ ; otherwise, it aborts. Crucially, once locked, the device cannot be unlocked or queried classically for $f_2(x)$ .

2. The Protocol Design:
The protocol introduces a deliberate asymmetry to prevent dishonest behavior:

Challenge Pair Generation: For a chosen challenge $x_0$ , the protocol uses a specific algorithm (Algorithm 1) to generate an alternative challenge $x_1$ . These challenges are constructed such that they differ in a specific set of indices $J$ (size $\ell_{min}$ ), ensuring that the basis bits of the BB84 encoding differ significantly while the value bits remain balanced.
Commitment: Alice commits to a bit $b \in \{0, 1\}$ $b \in {0, 1}$ by preparing a quantum state $\rho_b$ $ρ_{b}$ . This state encodes the payload substring $f_2(x_0)_J$ $f_{2} (x_{0})_{J}$ (the response bits at indices $J$ $J$ ).
- If $b=0$ , the state is encoded in the basis defined by $x_0$ ( $\beta(x_0)$ ).
- If $b=1$ , the state is encoded in the basis defined by $x_1$ ( $\beta(x_1)$ ).
- Alice sends the pair $(x_0, x_1)$ and the ordering $J$ to Bob, along with the quantum state $\rho_b$ .
Opening: Alice reveals $b$ , the challenge $x_0$ , and the full classical responses $f_1(x_0)$ and $f_2(x_0)$ .
Verification: Bob uses the locked HLPUF to verify the authenticity of the response. He prepares a verifier state based on $f_1(x_0)$ and queries the device. If the device accepts, Bob measures the stored quantum state in the basis corresponding to the revealed bit $b$ and checks consistency with $f_2(x_0)_J$ .

3. Security Mechanisms:

Hiding: Relies on the unforgeability of the HLPUF. Without the ability to forge a valid verifier state, Bob cannot extract information about $f_2(x_0)$ before the reveal. The protocol ensures that the two possible commitment states (for $b=0$ and $b=1$ ) are statistically indistinguishable because the payload bits are uniformly distributed and the basis patterns are balanced.
Binding: Relies on the locking mechanism and the operator norm bound. A dishonest Alice cannot prepare an entangled state that allows her to open to both 0 and 1 with high probability because the verification step requires a specific classical response $f_1(x_0)$ that is hard to forge. The binding proof reduces any dishonest strategy to an operator-norm bound on the sum of acceptance projectors, showing that the probability of successfully opening both bits is bounded by a negligible function.

Key Contributions

First Statistically Secure Quantum Bit Commitment: The paper presents the first bit commitment protocol that achieves both statistical hiding and binding under hybrid hardware assumptions (specifically HLPUFs) without relying on computational hardness or relativistic constraints.
Novel Hardware Usage: The authors demonstrate how to use hardware tokens in a mistrustful setting. They overcome the "look-alike" problem by structuring the protocol so that the commitment state is statistically tied to the genuine hardware's challenge-response behavior, making it impossible for a malicious party to substitute the token without detection.
Asymmetric HLPUF Construction: The introduction of an asymmetric split in the PUF response (Verifier vs. Payload) and a specific challenge-pair generation algorithm (Algorithm 1) that ensures balanced BB84 state distributions.
First Hardware-Based Coin Flipping: By applying the standard transformation to their bit commitment scheme, the authors construct the first strong quantum coin-flipping protocol based on hybrid hardware assumptions.
Proof Techniques: The paper develops new proof techniques, including an "intrinsic ensemble-symmetry" argument for hiding and an operator-norm reduction for binding, which separate intrinsic quantum limitations from hardware parameters.

Results

Correctness: The protocol is correct; honest parties always succeed with probability 1.
Hiding: The protocol is $\epsilon_{hide}$ -hiding, where $\epsilon_{hide} \le \epsilon_{forge}$ (the unforgeability parameter of the HLPUF). If the HLPUF is exponentially unforgeable, the hiding is perfect (statistically indistinguishable).
Binding: The protocol is $\epsilon_{bind}$ -binding. The probability that a dishonest Alice can successfully open both bits is bounded by:
$p_0 + p_1 \le 1 + 2^{-\frac{\ell_{min} - 2s}{4}}$
where $s$ is the length of the verifier string and $\ell_{min}$ is the length of the payload substring. This bound is negligible for appropriate parameter choices.
Coin Flipping Bias: The resulting coin-flipping protocol has a bias of at most $\delta_{CF} \le \frac{1}{2} \max\{\epsilon_{hide}, \epsilon_{bind}\}$ .

Significance and Claims

The authors claim that their work establishes a new paradigm for secure two-party cryptography in quantum networks. By combining rigorous security guarantees with concrete, off-the-shelf hardware components (PUFs) and feasible quantum communication, they offer a practical route to implementing fundamental cryptographic primitives that are otherwise impossible in the plain quantum setting.

The paper emphasizes that this approach does not require assumptions about an adversary's quantum memory (unlike bounded-storage models), allowing for indefinite security. Instead, security relies on the physical unclonability and tamper-resistance of the hardware token. The authors position this as a constructive alternative to existential results, providing a specific design that bridges the gap between theoretical quantum cryptography and practical implementation.

The authors remain modest regarding future work, noting that the tamper-proof implementation of the device is an open engineering question and that a fully composable security analysis is left for future study. They also suggest that the protocol could be adapted to scenarios without quantum memory (by allowing early measurement), though this would weaken security parameters.