Basing Cryptographic Protocols on Tamper-Evident Seals

In this paper we attempt to formally study two very intuitive physical models: sealed envelopes and locked boxes, often used as illustrations for 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 may be achievable in real life, where containers having this property are called “tamper-evident seals”. Another physical object with this property is the “scratch-off card”, often used in lottery tickets. We show that scratch-off cards can be used to implement bit-commitment and coin flipping, but not oblivious transfer. 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.