Quantum And Relativistic Protocols For Secure Multi-Party Computation
Open accessThe DOI matches its OpenAlex record; 5 of the 5 references it cites were found in a registry or an index.
Abstract
After a general introduction, the thesis is divided into four parts. In the first, we discuss the task of coin tossing, principally in order to highlight the effect different physical theories have on security in a straightforward manner, but, also, to introduce a new protocol for non-relativistic strong coin tossing. This protocol matches the security of the best protocol known to date while using a conceptually different approach to achieve the task. In the second part variable bias coin tossing is introduced. This is a variant of coin tossing in which one party secretly chooses one of two biased coins to toss. It is shown that this can be achieved with unconditional security for a specified range of biases, and with cheat-evident security for any bias. We also discuss two further protocols which are conjectured to be unconditionally secure for any bias. The third section looks at other two-party secure computations for which, prior to our work, protocols and no-go theorems were unknown. We introduce a general model for such computations, and show that, within this model, a wide range of functions are impossible to compute securely. We give explicit cheating attacks for such functions. In the final chapter we discuss the task of expanding a private random string, while dropping the usual assumption that the protocol's user trusts her devices. Instead we assume that all quantum devices are supplied by an arbitrarily malicious adversary. We give two protocols that we conjecture securely perform this task. The first allows a private random string to be expanded by a finite amount, while the second generates an arbitrarily large expansion of such a string.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?
Einstein, A., Podolsky, B., & Rosen, N. (1935) · Physical Review · doi:10.1103/physrev.47.777 · Cited by 16,654
Quantum generalizations of Bell's inequality
Cirel'son, B. S. (1980) · Letters in Mathematical Physics · doi:10.1007/bf00417500 · Cited by 1,788
Greenberger, D. M., Horne, M. A., & Zeilinger, A. (1989) · Bell’s Theorem, Quantum Theory and Conceptions of the Universe · doi:10.1007/978-94-017-0849-4_10 · Cited by 1,513
Universally Composable Privacy Amplification Against Quantum Adversaries
Renner, R., & König, R. (2005) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-30576-7_22 · Cited by 337 · cited 1×
“(See [21, 72, 73] for a further discussion, and an explicit example.”
BackgroundThe Universal Composable Security of Quantum Key Distribution
Ben-Or, M., Horodecki, M., Leung, D. W., Mayers, D., & Oppenheim, J. (2005) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-30576-7_21 · Cited by 227 · cited 1×
“(See [21, 72, 73] for a further discussion, and an explicit example.”
Background
Cited by
Loophole-free Bell inequality violation using electron spins separated by 1.3 kilometres
Hensen, B., Bernien, H., Dréau, A. E., Reiserer, A., Kalb, N., Blok, M. S., Ruitenberg, J., Vermeulen, R. F. L., Schouten, R. N., Abellán, C., et al. (2015) · Nature · doi:10.1038/nature15759 · Cited by 2,852
“In addition, a loophole-free Bell test is a critical component for device-independent quantum security protocols[20] and randomness certification[21,22].”
BackgroundMethodRandom numbers certified by Bell’s theorem
Pironio, S., Acín, A., Massar, S., de la Giroday, A. B., Matsukevich, D. N., Maunz, P., Olmschenk, S., Hayes, D., Luo, L., Manning, T. A., et al. (2010) · Nature · doi:10.1038/nature09008 · Cited by 1,420
“Hence what we describe here is a randomness expansion scheme 14 , where a small private random seedisexpandedintoa longer privaterandomstring.”
Quantum random number generators
Herrero-Collantes, M., & Garcia-Escartin, J. C. (2017) · Reviews of Modern Physics · doi:10.1103/revmodphys.89.015004 · Cited by 791
Quantum random number generation
Ma, X., Yuan, X., Cao, Z., Qi, B., & Zhang, Z. (2016) · npj Quantum Information · doi:10.1038/npjqi.2016.21 · Cited by 445
Free randomness can be amplified
Colbeck, R., & Renner, R. (2012) · Nature Physics · doi:10.1038/nphys2300 · Cited by 379
“It is worth contrasting randomness amplification, as considered here, with randomness expansion, introduced in [22] and further developed in [23, 24].”
BackgroundMethodSelf-citation
Metadata
- Authors
- Colbeck, R.
- Venue
- arXiv (Cornell University)
- Publisher
- arXiv
- Published
- 2009
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 0911.3814
- OpenAlex
- W1506311017
- Cited by
- 122
- References
- 5
- Type
- posted content
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Quantum And Relativistic Protocols For Secure Multi-Party Computation. https://app.cochat.ai/papers/10.48550/arxiv.0911.3814
- The paper
- Colbeck, R. (2009). Quantum And Relativistic Protocols For Secure Multi-Party Computation. arXiv (Cornell University). https://doi.org/10.48550/arxiv.0911.3814
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.