Cryptography from Sunspots: How to Use an Imperfect Reference String

The common reference string (CRS) model equips all protocol participants with a common string that is sampled from a pre-specified distribution, say the uniform distribution. This model enables otherwise-impossible cryptographic goals such as removing interaction from protocols and guaranteeing composable security. However, knowing the precise distribution of the reference string seems crucial for all known protocols in this model, in the sense that current security analyses fail when the actual distribution of the reference string is allowed to differ from the specified one even by a small amount. This fact rules out many potential implementations of the CRS model, such as measurements of physical phenomena (like sunspots), or alternatively using random sources that might be adversarially influenced. We study the possibility of obtaining universally composable (UC) security in a relaxed variant of the CRS model, where the reference string it taken from an adversarially specified distribution that's unknown to the protocol. On the positive side, we demonstrate that UC general secure computation is obtainable even when the reference string is taken from an arbitrary, adversarially chosen distribution, as long as (a) this distribution has some minimal min-entropy, (b) it has not too long a description, (c) it is efficiently samplable, and (d) the sampling algorithm is known to the adversary (and simulator). On the negative side, we show that if any one of these four conditions is removed then genera! UC secure computation becomes essentially impossible.

Authors

• Ran Canetti
• Rafael Pass
• Abhi Shelat

Keywords

• Cryptography
• Security
• Cryptographic protocols
• Computational modeling
• Access protocols
• Public key
• Computer science
• Radio access networks
• Failure analysis
• Distributed computing
• Sunspot
• Reference String
• Multi-party Computation
• Corruption
• Hybrid Model
• Short Description
• Description Of Algorithm
• Forward Error Correction
• Noisy Measurements
• Random Choice
• Random Input
• Security Framework
• Security Parameter
• Idea Of The Proof
• Results In More Detail
• Random String
• Protocol Execution
• Signature Scheme
• Plausible Deniability
• Zero-knowledge Proof
• UC Security
• Setup Models
• Common Reference String
• Non black-box constructions
• Entropy