ON THE EXISTENCE OF STATISTICALLY HIDING BIT COMMITMENT SCHEMES AND FAIL-STOP SIGNATURES

We show that the existence of a statistically hiding bit commitment sc heme with noninteractive opening and public verifiability implies the existence of fail-stop signatures. Therefore such signatures can now b e based on any one-way permutation. We also show that genuinely practi cal fail-stop signatures follow from the existence of any collision-in tractable hash function. These are the weakest assumptions known to be sufficient for fail-stop signatures. Conversely, we show that any fai l-stop signature scheme with a property we call the almost unique secr et key property can be transformed into a statistically hiding bit com mitment scheme. All previously known fail-stop signature schemes have this property. We even obtain an equivalence, because we can modify th e construction of fail-stop signatures from bit commitments such that it has this property.