Jun.-Prof. Matthias Christandl, LMU

Assume that Alice wants to commit a bit to Bob and that they do not trusteach other. In order to do so, she writes the bit down on a piece of paperand puts it in a safe, she locks the safe and gives the safe -- but not the key -- to Bob. Clearly, Bob cannot open the safe since he doesn't have the key and Alice cannot change the bit, since she does not have the safe. The electronic analogue of this problem, called 'bit commitment', is a cornerstone of present-day cryptography. Unfortunately, it has been shown that perfect bit commitment is impossible in both the classical and quantum world. I will start my talk by reviewing the Mayers-Lo-Chau-no-go theorem for quantum bit commitment. I will then explain how this theorem can be extended to apply to commitments of multiple bits and, finally, I will present protocols that (under weaker security requirements) allow the commitment to multiple bits and have an additional quantum feature called 'cheat-sensitivity'. This is joint work with Harry Buhrman, Patrick Hayden, Hoi-Kwong Lo and Stephanie Wehner.