Quantum And Relativistic Protocols For Secure Multi-Party Computation

By Roger Colbeck. 2009

488 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics

View Paper: https://www.semanticscholar.org/paper/14fdbdc3a57c072a8332826ab3291b6a8e664f3b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Atomic and Molecular Physics, and Optics

Citations in the corpus

Free randomness can be amplified (2011, methodology): “It is worth contrasting randomness amplification, as considered here, with randomness expansion, introduced in [22] and further developed in [23, 24].”
Loophole-free Bell inequality violation using electron spins separated by 1.3 kilometres (2015, methodology): “In addition, a loophole-free Bell test is a critical component for device-independent quantum security protocols[20] and randomness certification[21,22].”
Advances in quantum cryptography (2019, unknown): “[706] and the ideas there were developed in Ref.”
Quantum random number generators (2016, background): “…basic model behind device independent quantum information processing, which started in the context of quantum key distribution with (Mayers and Yao, 1998) and (Barrett et al., 2005) with multiple further developments (Aćın et al., 2007; Colbeck, 2007; Colbeck and Kent, 2011; Magniez et al., 2006).”
Private randomness expansion with untrusted devices (2010, methodology): “In earlier work on randomness expansion [15, 16] it was argued that there is no need to include X1 in the string undergoing privacy amplification, the argument being that since X1 is only used to do operations within Bob’s laboratory, it always remains secure against the outside and hence can be inc”
Fully device independent quantum key distribution (2012, result): “Building on an observation made in [Col06], Pironio et al. [PAM + 10] devised a protocol in which the generation of randomness could be certiﬁed solely by testing for a sufﬁciently large Bell inequality violation.”
Quantum random number generation (2015, background): “Since Colbeck 60,61 suggested that randomness can be expanded by untrusted devices, several protocols based on different assumptions have been proposed.”
A strong no-go theorem on the Wigner’s friend paradox (2019, unknown): “[37] Colbeck, R.”
Random numbers certified by Bell’s theorem (2009, unknown): “Hence what we describe here is a randomness expansion scheme 14 , where a small private random seedisexpandedintoa longer privaterandomstring.”