In 1997, Lo showed that if one party is malicious, unconditionally secure two-party quantum computation is impossible. Under computational assumptions, such as a one-way permutation secure against quantum adversaries, secure quantum bit-commitment does become possible. Complete fairness, where both parties get the output or neither does, remained open.

This paper shows for the first time that some functions admit secure two-party quantum computation with complete fairness and no trusted third party. That stands in sharp contrast with the impossibility result of Ben-Or et al. (FOCS 2006).