CWI Cryptology Group

Abstract: Non-local boxes are hypothetical ``machines'' that give rise to superstrong non-local correlations, leading to a stronger violation of Bell/CHSH inequalities than is possible within the framework of quantum mechanics. We show how non-local boxes can be used to perform any two-party secure computation. We first construct a protocol for bit commitment and then show how to achieve oblivious transfer using non-local boxes. Both have been shown to be impossible using quantum mechanics alone.
This is joint work with Harry Buhrman, Matthias Christandl, Stephanie Wehner and Andreas Winter

Abstract: In this talk we present a theoretic model for quantum secret sharing schemes in terms of quantum information theoretical notions. Based on this model several properties of quantum secret sharing schemes are rigorously derived. We apply the model to quantum MSP (monotone span program) constructions that have been proposed and prove rigorously their security. Finally, we explain the relation between quantum secret sharing schemes and quantum error correcting codes.

Abstract: Private information retrieval concerns the following problem. A user wants to retrieve the i-th bit from an n-bit database that is replicated over k servers, but he wants to do that privately: none of the servers should learn any information about i. We are interested in the amount of communication needed for this, comparing classical and quantum PIR schemes. For 1 server this amount is linear in n, classically as well as quantumly (Nayak). For 2 servers, the best known classical PIR scheme uses n^1/3 communication. We exhibit a quantum 2-server PIR scheme that uses n^3/10 qubits of communication. Our main tool is a certain reduction from 2 classical servers to 1 quantum server. We get similar quantum improvements for more than 2 servers. We also prove a new lower bound for classical 2-server PIR schemes in which the servers send only short answers.
This talk is based on joint work with Iordanis Kerenidis (STOC 03) and Stephanie Wehner (ICALP 05)

Abstract: We initiate the study of two-party cryptographic primitives with unconditional security, assuming that the adversary's quantum memory is of bounded size. We show that oblivious transfer and bit commitment can be implemented in this model using protocols where honest parties need no quantum memory, whereas an adversarial player needs quantum memory of size at least n/2 in order to break the protocol, where n is the number of qubits transmitted. This is in sharp contrast to the classical bounded-memory model, where we can only tolerate adversaries with memory of size quadratic in honest players' memory size. Our protocols are efficient, non-interactive and can be implemented using today's technology.
This is joint work with Ivan Damgaard, Louis Salvail and Christian Schaffner (FOCS05).

Abstract: We discuss applications of entropic uncertainty relations for the design of quantum private-key ciphers for classical messages. We discuss how to use entropic uncertainty relations for mutually unbiased observables in order to construct quantum ciphers with better resilience against known plaintext attacks than their classical counterparts. Finally, we show how to transform such ciphers into ones that allow for key-recycling while preserving perfect security in sharp contrast with what can be achieved through classical means.

Abstract: Quantum bit commitment is impossible, but how far can we stretch the quantum limits when the task is to commit a string of n bits rather than a single bit?
"Not very far" is the answer that we obtain from a no-go argument, where we invoke the Holevo information as the security criterion. In particular, our result implies the optimality of the trivial scheme, in which Alice sends a subset of b bits to Bob (commit phase) and later reveals the remaining n-b bits.
Things change dramatically, however, if we are willing to revise our standard of security and use the accessible information instead of the Holevo information. Based on the phenomenon of "locking" classical information into quantum states, we are able to design protocols which impose strong limitations on the ability of both parties to cheat.
This is joint work with Matthias Christandl, Patrick Hayden, Hoi-Kwong Lo and Stephanie Wehner.