This paper presents two new constant-round simulatable coin-flipping protocols, based explicitly on one or a few X-commitments of short seeds and a Q-commitment of a short hash, independently of the large target length. A pseudo-random generator and a collision-resistant hash function are used to combine the separate X and Q properties (associated with short bit-strings) into a unified X&Q property amplified to the target length, thus amortizing the cost of the base commitments. In this way, the new protocols are significantly more efficient than an obvious batching or extension of coin-flippings designed (in the same security setting) for short bit-strings and based on inefficient X&Q commitments.
The first protocol, simulatable with rewinding, deviates from the traditional coin-flipping template in order to improve simulatability in case of unknown adversarial probabilities of abort, without having to use a X&Q commitment scheme. The second protocol, one-pass simulatable, derives from a new construction of a universally composable X&Q commitment scheme for large bit-strings, achieving communication-rate asymptotically close to 1. Besides the base X and Q commitments, the new commitment scheme only requires corresponding collision-resistant hashing, pseudo-random generation and application of a threshold erasure code. Alternative constructions found in recent work with comparable communication complexity require explicit use of oblivious transfer and use different encodings of the committed value.Category / Keywords: cryptographic protocols / coin-flipping, commitments, simulatability, extractability, equivocability, rewinding, universal composability, efficient protocols Date: received 28 Jun 2015 Contact author: luis papers at gmail com Available format(s): PDF | BibTeX Citation Version: 20150630:192836 (All versions of this report) Short URL: ia.cr/2015/640 Discussion forum: Show discussion | Start new discussion