We formally study two very intuitive physical models: sealed envelopes and locked boxes, often used as illustrations of common cryptographic operations. We relax the security properties usually required from locked boxes (such as in bit-commitment protocols) and require only that a broken lock or torn envelope be identifiable to the original sender. Unlike the completely impregnable locked box, this functionality maybe achievable in `real life'; containers that claim to have this property are called tamper-evident seals, and are widely used. Another common instance is the scratch-off card, often used in lottery tickets.
We consider the possibility of implementing standard cryptographic operations using tamper-evident seals as primitives, focusing on oblivious transfer, bit-commitment and coin-flipping. We discuss three variations of tamper-evident seals, where the differences arise from two properties: whether or not sealed containers can be told apart and whether or not an honest player can break the seal. For these models we show implementations of oblivious transfer, bit-commitment and coin flipping protocols. We also show a separation between the three models: only the strongest one can support implementations of oblivious transfer and the weakest cannot implement bit-commitment. Of particular interest, we give a strongly-fair coin flipping protocol with bias bounded by O(1/r) (where r is the number of rounds), beating the best known bias in the standard model even with cryptographic assumptions.
Postscript , gzipped Postscript , PDF .
Back to: On-Line Publications, Recent Papers