Basing Cryptographic Protocols on Tamper-Evident Seals

or

Scratch-Off Crytpography

Tal Moran and Moni Naor

Abstract:

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 .

Related On-Line Papers:
Other Papers on Cryptography with Humans and Physical Devices

Back to: On-Line PublicationsRecent Papers

Back Home