Comments: 20 pages, 7 figures. This version contains detailed proofs of authentication and fault tolerance. It also contains protocols for quantum inputs and outputs and appendices not available in the published version
Journal-ref: Proceedings of the 50th Annual IEEE Symposium on Foundations of
Computer Science (FOCS 2009), pp. 517-526