Cryptography from Sunspots: How to use an Imperfect Reference String

The Common Reference String (CRS) model enables otherwise-impossible cryptographic goals such as removing interaction from protocols and guaranteeing composable security.

However, the reference string in the CRS model must be guaranteed to be sampled from a precisely specified distribution; indeed, current security analyses typically fail when the distribution is changed even slightly. This fact rules out a large class of potential implementations of the CRS model such as measurements of physical phenomena (like sunspots), or alternatively using random sources that might be adversarially influenced.

Are there protocols that guarantee composable security even when the
reference string is taken from an ``imperfect'', or ``adversarially
controlled'' distribution?

The answer turns out to be surprisingly intricate.
We first show that impossibility results for composable secure computation in the plain model extend to this relaxed version of the CRS model, as long as the only guarantee on the reference  string is that it is taken from a distribution of some minimal min-entropy; here ``minimal'' is as high as full entropy minus any polynomially vanishing fraction.  Impossibility holds even when the reference string is taken from an  algorithmically samplable distribution, whose code is known to the adversary, as long as the sampling algorithm is allowed to run for sub-exponential time.  

Finally we show how to regain general feasibility of universally composable secure computation in this model, as long as the sampling algorithm is efficient, and known to the adversary. The construction and analysis make essential use of the technique of Barak's non black-box zero-knowledge protocol (FOCS 2001).