Top

Cluster Computing

Published in:

01-12-2013

Outsourcing computation of modular exponentiations in cloud computing

Authors: Xu Ma, Jin Li, Fangguo Zhang

Published in: Cluster Computing | Issue 4/2013

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Cloud computing is an emerging computing paradigm in which IT resources and capacities are provided as services over the Internet. Promising as it is, this paradigm also brings forth new challenges for security when users want to securely outsource the computation of cryptographic operations to the untrusted cloud servers. As we know, modular exponentiation is one of the basic operations among most of current cryptosystems. In this paper, we present the generic secure outsourcing schemes enabling users to securely outsource the computations of exponentiations to the untrusted cloud servers. With our techniques, a batch of exponentiations (e.g. t exponentiations) can be efficiently computed by the user with only O(n+t) multiplications, where n is the number of bits of the exponent. Compared with the state-of-the-art algorithm, the proposed schemes are superior in both efficiency and verifiability. Furthermore, there are not any complicated pre-computations on the user side. Finally, the schemes are proved to be secure under the Subset Sum Problem.

previous article Hierarchical semantic information modeling and ontology for bird ecology

next article Efficient leakage-resilient public key encryption from DDH assumption

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Applebaum, B., Ishai, Y., Kushilevitz, E.: From secrecy to soundness: efficient verification via secure computation. In: ICALP 2010, pp. 152–163 (2010)

Armbrust, M., Fox, A., Griffith, R., Joseph, A., Katz, R., Konwinski, A., Lee, G., Patterson, D., Rabkin, A., Stoica, I., Zaharia, M.: Above the cloud: a Berkeley view of cloud computing. Berkeley University (2009)

Assuncao, M.D., Costanzo, A., Buyya, R.: A cost-benefit analysis of using cloud computing to extend the capacity of clusters. Clust. Comput. 13(3), 335–347 (2010) CrossRef

Atallah, M.J., Frikken, K.B.: Securely outsourcing linear algebra computations. In: AISACCS 2010, pp. 48–59 (2010)

Babai, L.: Trading group theory for randomness. In: Proceeding of ACM Symposium on Theory of Computing (STOC), pp. 421–429 (1985)

Barbosa, M., Farshim, P.: Delegatable homomorphic encryption with applicatoins to secure outsourcing of computation. In: CT-RSA 2012. LNCS, vol. 7178, pp. 296–312. Springer, Heidelberg (2012)

Benabbas, S., Gennaro, R., Vahlis, Y.: Verifiable delegation of computation over large datasets. In: CRYPTO 2011. LNCS, vol. 6841, pp. 111–131. Springer, Heidelberg (2011) CrossRef

Benjamin, D., Atallah, M.J.: Private and cheating-free outsourcing of algebraic computations. In: PST 2008, pp. 240–245 (2008)

Boyko, V., Peinado, M.: Speeding up discrete log and factoring based schemes via precomputation. In: EUROCRRYPTO 1998. LNCS, vol. 1403, pp. 221–232. Springer, Heidelberg (1998)

10.

Chapman, C., Emmerich, W., Marquez, F.G., Clayman, S., Galis, A.: Software architecture definition for on-demand cloud provisioning. Clust. Comput. 15(2), 79–100 (2012) CrossRef

11.

Chaum, D., Pedersen, T.P.: Wallet database with observers. In: CRYPTO 1992. LNCS, vol. 740, pp. 89–105. Springer, Heidelberg (1993)

12.

Chen, X., Li, J., Ma, J., Tang, Q., Lou, W.: New algorithms for secure outsourcing of modular exponentiations. In: ESORICS 2012. LNCS, vol. 7459, pp. 541–556. Springer, Heidelberg (2012) CrossRef

13.

Chung, K.M., Kalai, Y., Vadhan, S.P.: Improved delegation of computation using fully homomorphic encryption. In: CRYPTO 2010. LNCS, vol. 6223, pp. 483–501. Springer, Heidelberg (2010) CrossRef

14.

Coster, M.J., LaMacchia, B.A., Odlyzko, A.M., Schnorr, C.P., Stern, J.: Improved low-density subset sum algorithms. Comput. Complex. 2(2), 111–128 (1992) MathSciNetCrossRefMATH

15.

Gennaro, R., Gentry, C., Parno, B.: Non-interactive verifiable computing: outsourcing computation to untrusted workers. In: CRYPTO 2010. LNCS, vol. 6223, pp. 465–482. Springer, Heidelberg (2010) CrossRef

16.

Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Proceeding of ACM Symposium on Theory of Computing (STOC), pp. 169–178 (2009)

17.

Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186–208 (1989) MathSciNetCrossRefMATH

18.

Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: Delegating computation: interactive proofs for muggles. In: Proceeding of ACM Symposium on Theory of Computing (STOC), pp. 113–122 (2008)

19.

Golle, P., Mironov, I.: Uncheatable distributed computation. In: CT-RSA 2001. LNCS, vol. 2020, pp. 425–550. Springer, Heidelberg (2001)

20.

Green, M., Hohenberger, S., Waters, B.: Outsourcing the decryption of ABE ciphertexts. In: Proceeding of the USENIX Security Symposium (2011)

21.

Hohenbergera, S., Lysyanskaya, A.: How to securely outsource cryptographic computations. In: TCC 2005. LNCS, vol. 3378, pp. 264–282. Springer, Heidelberg (2005)

22.

Horowitz, E., Sahni, S.: Computing partitions with applications to the knapsack problem. J. ACM 21(2), 277–292 (1974) MathSciNetCrossRefMATH

23.

Jakobsson, M., Wetzel, S.: Secure server-aided signature generation. In: PKC 2001. LNCS, vol. 1992, pp. 383–401. Springer, Heidelberg (2001)

24.

Kilian, J.: A note on efficient zero-knowledge proofs and arguments. In: Proceeding of ACM Symposium on Theory of Computing (STOC), pp. 723–732 (1992)

25.

Kilian, J.: Improved efficient arguments. In: CRYPTO 1995. LNCS, vol. 963, pp. 311–324. Springer, Heidelberg (1995)

26.

Matsumoto, T., Kato, K., Iami, H.: Speeding up secret computations with insecure auxiliary devices. In: CRYPTO 1990. LNCS, vol. 403, pp. 497–506. Springer, Heidelberg (1990)

27.

Micali, S.: CS proofs (extended abstract). In: Proceeding of the 35th IEEE Symposium on Foundations of Computer Science, pp. 436–453 (1994) CrossRef

28.

Papamanthou, C., Shi, E., Tamassia, R.: Publicly verifiable delegation of computation. http://eprint.iacr.org/2011/587

29.

Parno, B., Raykova, M., Vaikuntanathan, V.: How to delegate and verify in public: verifiable computation from attribute-based encryption. In: TCC 2012. LNCS, vol. 7194, pp. 422–439 (2012)

30.

Sahai, A., Seyalioglu, H., Waters, B.: Dynamic credentials and ciphertext delegation for attribute-based encryption. In: CRYPTO 2012. LNCS, vol. 7417, pp. 199–217. Springer, Heidelberg (2012) CrossRef

31.

Schnorr, C.P., Euchner, M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Program. 66(1–3), 181–199 (1994) MathSciNetCrossRefMATH

Title: Outsourcing computation of modular exponentiations in cloud computing
Authors: Xu Ma
Jin Li
Fangguo Zhang
Publication date: 01-12-2013
Publisher: Springer US
Published in: Cluster Computing / Issue 4/2013
Print ISSN: 1386-7857
Electronic ISSN: 1573-7543
DOI: https://doi.org/10.1007/s10586-013-0252-0

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 4/2013

VRAA: virtualized resource auction and allocation based on incentive and penalty

Efficient push-based packet scheduling for Peer-to-Peer live streaming

A MapReduce task scheduling algorithm for deadline constraints

A fuzzy-based reliability system for knowledge sharing between robots in P2P JXTA-overlay platform

A systematic method to design strong designated verifier signature without random oracles

Proxy based seamless connection management method in mobile cloud computing

Premium Partner