%0 Journal Article %J Theory of Cryptography %D 2008 %T Universally composable multi-party computation with an unreliable common reference string %A Goyal,V. %A Katz, Jonathan %X Universally composable (UC) multi-party computation has been studied in two settings. When a majority of parties are honest, UC multi-party computation is possible without any assumptions. Without a majority of honest parties, UC multi-party computation is impossible in the plain model, but feasibility results have been obtained in various augmented models. The most popular such model posits a common reference string (CRS) available to parties executing the protocol.In either of the above settings, some assumption regarding the protocol execution is made: i.e., that many parties are honest in the first case, or that a legitimately-chosen string is available in the second. If this assumption is incorrect then all security is lost. A natural question is whether it is possible to design protocols secure if either one of these assumptions holds, i.e., a protocol which is secure if either at most s players are dishonest or if up to t > s players are dishonest but the CRS is chosen in the prescribed manner. We show that such protocols exist if and only if s + t < n. This work was done in part while the authors were visiting IPAM. %B Theory of Cryptography %P 142 - 154 %8 2008/// %G eng %R 10.1007/978-3-540-78524-8_9