Publicly verifiable secret sharing for cloud-based key management

Running the key-management service of cryptographic systems in the cloud is an attractive cost saving proposition. Supporting key-recovery is an essential component of every key-management service. We observe that to verifiably support key-recovery in a public cloud, it is essential to use publicly verifiable secret-sharing (PVSS) schemes. In addition, a holistic approach to security must be taken by requiring that running the key-management service in the (untrusted) cloud does not violate the security of the cryptographic system at hand. This paper takes such a holistic approach for the case of public-key encryption which is one of the most basic cryptographic tasks. The approach boils down to formalizing the security of public-key encryption in the presence of PVSS. We present such a formalization and observe that the PVSS scheme of Stadler [29] can be shown to satisfy our definition, albeit in the Random Oracle Model. We construct a new scheme based on pairings which is much more efficient than Stadler's scheme. Our scheme is noninteractive and can support any monotone access structure. In addition, it is proven secure in the standard model under the Bilinear Diffie-Hellman (BDH) assumption. Interestingly, our PVSS scheme is actually the first non-interactive scheme proven secure in the standard model; all previous non-interactive PVSS schemes assume the existence of a Random Oracle. Our scheme is simple and efficient; an implementation of our scheme demonstrates that our scheme compares well with the current fastest known PVSS schemes.