On the Existence of Statistically Hiding Bit Commitment Schemes and Fail-Stop Signatures

We show that the existence of a statistically hiding bit commitment scheme with non-interactive opening and public verification implies the existence of fail-stop signatures. Therefore such signatures can now be based on any one-way permutation — the weakest assumption known to be sufficient for fail-stop signatures. We also show that genuinely practical fail-stop signatures follow from the existence of any collision-intractable hash function. A similar idea is used to improve a commitment scheme of Naor and Yung, so that one can commit to several bits with amortized O(1) bits of communication per bit committed to.Conversely, we show that any fail-stop signature scheme with a property we call the almost unique secret key property can be transformed into a statistically hiding bit commitment scheme. All previously known fail-stop signature schemes have this property. We even obtain an equivalence since we can modify the construction of fail-stop signatures from bit commitments such that it has this property.