Quantum bit string commitment.
A bit string commitment protocol securely commits N classical bits so that the recipient can extract only M<N bits of information about the string. Classical reasoning suggests that bit string commitment implies bit commitment and hence, given the Mayers-Lo-Chau theorem, that nonrelativistic quantum bit string commitment is impossible. Not so: there exist nonrelativistic quantum bit string commitment protocols, with security parameters epsilon and M, that allow A to commit N=N(M,epsilon) bits to B so that A's probability of successfully cheating when revealing any bit and B's probability of extracting more than N'=N-M bits of information about the N bit string before revelation are both less than epsilon. With a restrictive definition of security against A, N can be taken to be O(exp(CN')) for a positive constant C. I briefly discuss possible applications.
Kent
Adrian
A
Hewlett-Packard Laboratories, Filton Road, Stoke Gifford, Bristol BS34 8QZ, United Kingdom and and Centre for Quantum Computation, DAMTP, Centre for Mathematical Sciences, University of Cambridge, Wilberforce Road, Cambridge CB3 0WA, United Kingdom.