How to simultaneously exchange a secret bit by flipping a symmetrically-biased coin

Authors:
  • MLMichael Luby
    Michael Luby
  • SMSilvio Micali
    Silvio Micali
  • CRCharles Rackoff
    Charles Rackoff
Publisher website
Google Scholar
Abstract
We present a cryptographic protocol allowing two mutually distrusting parties, A and B, each having a secret bit, to "simultaneously" exchange the values of those bits. It is assumed that initially each party presents a correct encryption of his secret bit to the other party. We develop a new tool to implement our protocol: a slightly biased symmetric coin. The key property of this coin is that from each flip A receives a piece of probabilistic information about B's secret bit which is symmetric to the piece of information B receives about A's secret bit.