Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aranha, D.F., López, J., Hankerson, D.: High-Speed Parallel Software Implementation of the η T Pairing. In: Pieprzyk, J. (ed.) CT-RSA 2010. LNCS, vol. 5985, pp. 89–105. Springer, Heidelberg (2010)
Beimel, A.: Secure Schemes for Secret Sharing and Key Distribution. PhD thesis, Israel Institute of Technology, Technion, Haifa, Israel (June 1996)
Bellare, M., Goldwasser, S.: Verifiable partial key escrow. In: ACM Conference on Computer and Communications Security, pp. 78–91 (1997)
Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols. In: ACM Conference on Computer and Communications Security, pp. 62–73 (1993)
Blakley Jr., G.R.: Safeguarding cryptographic keys. In: AFIPS 1979, National Computer Conference, vol. 48, pp. 313–317 (1979)
Boneh, D., Boyen, X.: Efficient Selective-ID Secure Identity-Based Encryption Without Random Oracles. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 223–238. Springer, Heidelberg (2004)
Boneh, D., Franklin, M.: Identity-Based Encryption from the Weil Pairing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213–229. Springer, Heidelberg (2001)
Boneh, D., Franklin, M.K.: Identity-based encryption from the Weil pairing. SIAM J. Comput. 32(3), 586–615 (2003); Ealier version in [7]
Chor, B., Goldwasser, S., Micali, S., Awerbuch, B.: Verifiable secret sharing and achieving simultaneity in the presence of faults (extended abstract). In: 26th Annual Symposium on Foundations of Computer Science (FOCS), pp. 383–395. IEEE (1985)
Creeger, M.: Cloud computing: An overview. Queue 7, 2:3–2:4 (2009)
Feldman, P.: A practical scheme for non-interactive verifiable secret sharing. In: 28th Annual Symposium on Foundations of Computer Science (FOCS), pp. 427–437. IEEE (1987)
El Gamal, T.: A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 10–18. Springer, Heidelberg (1985)
Goldwasser, S., Micali, S.: Probabilistic encryption. J. Comput. Syst. Sci. 28(2), 270–299 (1984)
Goyal, V., Pandey, O., Sahai, A., Waters, B.: Attribute-based encryption for fine-grained access control of encrypted data. In: Juels, A., Wright, R.N., De Capitani di Vimercati, S. (eds.) ACM Conference on Computer and Communications Security, pp. 89–98. ACM (2006)
Joux, A.: A one round protocol for tripartite Diffie-Hellman. In: Bosma, W. (ed.) ANTS 2000. LNCS, vol. 1838, pp. 385–394. Springer, Heidelberg (2000)
Joux, A.: A one round protocol for tripartite Diffie-Hellman. J. Cryptology 17(4), 263–276 (2004); Earlier version in [15]
Klien, M.: Six Benefits of Cloud Computing (2010), http://resource.onlinetech.com/the-six-benefits-of-cloud-computing/
Martin, L.: Federated Key Management for Secure Cloud Computing. Presentation by Voltage Security, Inc. (May 2010), http://storageconference.org/2010/Presentations/KMS/17.Martin.pdf
Micali, S.: Fair Public-Key Cryptosystems. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 113–138. Springer, Heidelberg (1993)
Micali, S., Shamir, A.: Partial key-escrow (1996) (manuscript)
Escrowed encryption standard (EES). FIPS PUB 185, National Institute of Standards and Technology (February 1994)
National Institute of Standards and Technology. NIST Special Publication 800-57: Recommendation for Key Management — Part 1: General (revised) (2007)
Pedersen, T.P.: Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 129–140. Springer, Heidelberg (1992)
Sahai, A., Waters, B.: Fuzzy Identity-Based Encryption. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 457–473. Springer, Heidelberg (2005)
Schoenmakers, B.: A Simple Publicly Verifiable Secret Sharing Scheme and Its Application to Electronic Voting. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 148–164. Springer, Heidelberg (1999)
Scott, M.: MIRACL—A Multiprecision Integer and Rational Arithmetic C/C++ Library. Shamus Software Ltd, Dublin, Ireland (2010), http://www.shamus.ie/
Shamir, A.: How to share a secret. Commun. ACM 22(11), 612–613 (1979)
Shoup, V.: Encryption algorithms—part 2: Asymmetric ciphers. Final Committee Draft 18033-2, ISO/IEC (December 2004), http://www.shoup.net/iso/std6.pdf
Stadler, M.: Publicly Verifiable Secret Sharing. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 190–199. Springer, Heidelberg (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
D’Souza, R., Jao, D., Mironov, I., Pandey, O. (2011). Publicly Verifiable Secret Sharing for Cloud-Based Key Management. In: Bernstein, D.J., Chatterjee, S. (eds) Progress in Cryptology – INDOCRYPT 2011. INDOCRYPT 2011. Lecture Notes in Computer Science, vol 7107. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-25578-6_21
Download citation
DOI: https://doi.org/10.1007/978-3-642-25578-6_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-25577-9
Online ISBN: 978-3-642-25578-6
eBook Packages: Computer ScienceComputer Science (R0)