dorsal/arxiv
View SchemaPossibility, Impossibility and Cheat-Sensitivity of Quantum Bit String Commitment
| Authors | Harry Buhrman, Matthias Christandl, Patrick Hayden, Hoi-Kwong Lo, Stephanie Wehner |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0504078 |
| URL | https://arxiv.org/abs/quant-ph/0504078 |
| DOI | 10.1103/PhysRevA.78.022316 |
| Journal | Phys. Rev. A 78, 022316 (2008) |
Abstract
Unconditionally secure non-relativistic bit commitment is known to be impossible in both the classical and the quantum worlds. But when committing to a string of n bits at once, how far can we stretch the quantum limits? In this paper, we introduce a framework for quantum schemes where Alice commits a string of n bits to Bob in such a way that she can only cheat on a bits and Bob can learn at most b bits of information before the reveal phase. Our results are two-fold: we show by an explicit construction that in the traditional approach, where the reveal and guess probabilities form the security criteria, no good schemes can exist: a+b is at least n. If, however, we use a more liberal criterion of security, the accessible information, we construct schemes where a=4log n+O(1) and b=4, which is impossible classically. We furthermore present a cheat-sensitive quantum bit string commitment protocol for which we give an explicit tradeoff between Bob's ability to gain information about the committed string, and the probability of him being detected cheating.
{
"annotation_id": "8d588856-568b-4c58-90b3-9b9ea903f38d",
"date_created": "2026-03-02T18:02:15.955000Z",
"date_modified": "2026-03-02T18:02:15.955000Z",
"file_hash": "8cd2fe4e529806ee520ee8c6127005621100cee5b03064e545200457410a1eef",
"private": false,
"record": {
"abstract": "Unconditionally secure non-relativistic bit commitment is known to be\nimpossible in both the classical and the quantum worlds. But when committing to\na string of n bits at once, how far can we stretch the quantum limits? In this\npaper, we introduce a framework for quantum schemes where Alice commits a\nstring of n bits to Bob in such a way that she can only cheat on a bits and Bob\ncan learn at most b bits of information before the reveal phase. Our results\nare two-fold: we show by an explicit construction that in the traditional\napproach, where the reveal and guess probabilities form the security criteria,\nno good schemes can exist: a+b is at least n. If, however, we use a more\nliberal criterion of security, the accessible information, we construct schemes\nwhere a=4log n+O(1) and b=4, which is impossible classically. We furthermore\npresent a cheat-sensitive quantum bit string commitment protocol for which we\ngive an explicit tradeoff between Bob\u0027s ability to gain information about the\ncommitted string, and the probability of him being detected cheating.",
"arxiv_id": "quant-ph/0504078",
"authors": [
"Harry Buhrman",
"Matthias Christandl",
"Patrick Hayden",
"Hoi-Kwong Lo",
"Stephanie Wehner"
],
"categories": [
"quant-ph"
],
"doi": "10.1103/PhysRevA.78.022316",
"journal_ref": "Phys. Rev. A 78, 022316 (2008)",
"title": "Possibility, Impossibility and Cheat-Sensitivity of Quantum Bit String Commitment",
"url": "https://arxiv.org/abs/quant-ph/0504078"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "431509e6-3bc7-4c65-93e4-a89770f7e3de",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}