Paper 2015/640

Very-efficient simulatable flipping of many coins into a well

Luís T. A. N. Brandão

Abstract

Secure two-party parallel coin-flipping is a cryptographic functionality that allows two mutually distrustful parties to agree on a common random bit-string of a certain target length. In coin-flipping into-a-well, one party learns the bit-string and then decides whether to abort or to allow the other party to learn it. It is well known that this functionality can be securely achieved in the ideal/real simulation paradigm, using commitment schemes that are simultaneously extractable (X) and equivocable (Q). 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.