Close this search box.

Brandao L.T.A.N.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

pp 297



This paper presents new cryptographic protocols for a stand-alone simulatable two-party parallel coin-flipping (into a well) and a universally composable commitment scheme, with near optimal asymptotic communication rate, in the static and computational malicious model. The approach, denoted expand-mask-hash, uses in both protocols a pseudo-random generator (PRG) and a collision-resistant hash function (CR-Hash) to combine separate extractable commitments and equivocable commitments (associated with short bit-strings) into a unified extractable-and-equivocable property amplified to a larger target length, amortizing the cost of base commitments. The new stand-alone coin-flipping protocol is based on a simple augmentation of the traditional coin-flipping template. To the knowledge of the author, it is the first proposal shown to simultaneously be two-side-simulatable and have an asymptotic (as the target length increases) communication rate converging to two bits per flipped coin and computation rate per party converging to that of PRG-generating and CR-hashing a bit-string with the target length. The new universally composable commitment scheme has efficiency comparable to very recent state-of-the-art constructions – namely asymptotic communication rate as close to 1 as desired, for each phase (commit and open) – while following a distinct design approach. Notably it does not require explicit use of oblivious transfer and it uses an erasure encoding instead of stronger error correction codes.