On the Complexity of UC Commitments
Résumé
Motivated by applications to secure multiparty computation, we study the complexity of realizing universally composable (UC) commitments. Several recent works obtain practical UC commitment protocols in the common reference string (CRS) model under the DDH assumption. These protocols have two main disadvantages. First, even when applied to long messages, they can only achieve a small constant rate (namely, the communication complexity is larger than the length of the message by a large constant factor). Second, they require computationally expensive public-key operations for each block of each message being committed.
Our main positive result is a UC commitment protocol that simultaneously avoids both of these limitations. It achieves an optimal rate of 1 (strictly speaking, 1 − o(1)) by making only few calls to an ideal oblivious transfer (OT) oracle and additionally making a black-box use of a (computationally inexpensive) PRG. By plugging in known efficient protocols for UC-secure OT, we get rate-1, computationally efficient UC commitment protocols under a variety of setup assumptions (including the CRS model) and under a variety of standard cryptographic assumptions (including DDH). We are not aware of any previous UC commitment protocols that achieve an optimal asymptotic rate.
A corollary of our technique is a rate-1 construction for UC commitment length extension, that is, a UC commitment protocol for a long message using a single ideal commitment for a short message. The extension protocol additionally requires the use of a semi-honest (stand-alone) OT protocol. This raises a natural question: can we achieve UC commitment length extension while using only inexpensive PRG operations as is the case for stand-alone commitments and UC OT? We answer this question in the negative, showing that the existence of a semi-honest OT protocol is necessary (and sufficient) for UC commitment length extension. This shows, quite surprisingly, that UC commitments are qualitatively different from both stand-alone commitments and UC OT.