Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
International Journal of Information Security
Published in: International Journal of Information Security 5/2016

01-10-2016 | Regular Contribution

Efficient and verifiable algorithms for secure outsourcing of cryptographic computations

Authors: Mehmet Sabır Kiraz, Osmanbey Uzunkol

Published in: International Journal of Information Security | Issue 5/2016

Log in

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

search-config
loading …

Abstract

Reducing computational cost of cryptographic computations for resource-constrained devices is an active research area. One of the practical solutions is to securely outsource the computations to an external and more powerful cloud server. Modular exponentiations are the most expensive computation from the cryptographic point of view. Therefore, outsourcing modular exponentiations to a single, external and potentially untrusted cloud server while ensuring the security and privacy provides an efficient solution. In this paper, we propose new efficient outsourcing algorithms for modular exponentiations using only one untrusted cloud server. These algorithms cover public-base and private-exponent, private-base and public-exponent, private-base and private-exponent, more generally private-base and private-exponents simultaneous modular exponentiations. Our algorithms are the most efficient solutions utilizing only one single untrusted server with the best checkability probabilities. Furthermore, unlike existing schemes, which have fixed checkability probability, our algorithms provide adjustable predetermined checkability parameters. Finally, we apply our algorithms to outsource oblivious transfer protocols and blind signatures which are expensive primitives in modern cryptography.
previous article Private and oblivious set and multiset operations
next article Efficient wildcard search over encrypted data

Dont have a licence yet? Then find out more about our products and how to get one 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+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 "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
Footnotes
1
Note that disclosing both x and \(x^{-1} \mod \phi (n)\) for \(x \in \mathbb {Z}/n\mathbb {Z}\) allows an attacker to recover the factorization of the RSA modulus n.
 
Literature
1.
Van Dijk, M., Juels, A.: On the impossibility of cryptography alone for privacy-preserving cloud computing. In: Proceedings of the 5th USENIX Conference on Hot Topics in Security (HotSec’10), pp. 1–8. USENIX Association (2010)
2.
Chen, X., Li, J., Ma, J., Tang, Q., Lou, W.: New algorithms for secure outsourcing of modular exponentiations. In: Foresti, S., Yung, M., Martinelli, F. (eds.) Computer Security ESORICS 2012, volume 7459 of Lecture Notes in Computer Science, pp. 541–556. Springer, Berlin (2012)
3.
Hohenberger, S., Lysyanskaya, A.: How to securely outsource cryptographic computations. In: Kilian, J. (ed.) Theory of Cryptography, volume 3378 of Lecture Notes in Computer Science, pp. 264–282. Springer, Berlin (2005)
4.
Kuppusamy, P.G.L., Rangasamy, J.: On secure outsourcing of cryptographic computations to cloud. In: ACM Symposium on Information Computer and Communications Security (ASIACCS). ACM (2014)
5.
Wang, Y., Wu, Q., Wong, D.S., Qin, B., Chow, S.S.M., Liu, Z., Tan, X.: Securely outsourcing exponentiations with single untrusted program for cloud storage. In: Kutyowski, M., Vaidya, J. (eds.) Computer Security—ESORICS 2014, volume 8712 of Lecture Notes in Computer Science, pp. 326–343. Springer, Berlin (2014)
6.
Li, J., Wong, D., Li, J., Huang, X., Xiang, Y.: Secure outsourced attribute-based signatures. IEEE Trans. Parallel Distrib. Syst. 99 (preprints) (2014)
7.
Nie, H., Chen, X., Li, J., Liu, J., Lou, W.: Efficient and verifiable algorithm for secure outsourcing of large-scale linear programming. In: 2014 IEEE 28th International Conference on Advanced Information Networking and Applications (AINA), pp. 591–596 (2014)
8.
Beaver, D., Feigenbaum, J.: Hiding instances in multioracle queries. In: STACS 90, volume 415 of Lecture Notes in Computer Science, pp. 37–48. Springer, Berlin (1990)
9.
Beaver, D., Feigenbaum, J., Kilian, J., Rogaway, P.: Locally random reductions: improvements and applications. J. Cryptol. 10(1), 17–36 (1997)MathSciNetCrossRefMATH
10.
Abadi, M., Feigenbaum, J., Kilian, J.: On hiding information from an oracle. In: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing (STOC ’87), pp. 195–203. ACM (1987)
11.
Boyko, V., Peinado, M., Venkatesan, R.: Speeding up discrete log and factoring based schemes via precomputations. In: Advances in Cryptology EUROCRYPT’98, volume 1403 of Lecture Notes in Computer Science, pp. 221–235. Springer, Berlin (1998)
12.
de Rooij, P.: On schnorrs preprocessing for digital signature schemes. J. Cryptol. 10(1), 1–16 (1997)CrossRefMATH
13.
Matsumoto, T., Kato, K., Imai, H.: Speeding up secret computations with insecure auxiliary devices. In: Advances in Cryptology CRYPTO 88, volume 403 of Lecture Notes in Computer Science, pp. 497–506. Springer, New York (1990)
14.
Nguyen, P.Q., Shparlinski, I.E., Stern, J.: Distribution of modular sums and the security of the server aided exponentiation. In: Cryptography and Computational Number Theory, volume 20 of Progress in Computer Science and Applied Logic, pp. 331–342. Birkhauser, Basel (2001)
15.
Schnorr, C.P.: Efficient identification and signatures for smart cards. In: Quisquater, J.-J., Vandewalle, J. (eds.) Advances in Cryptology EUROCRYPT 89, volume 434 of Lecture Notes in Computer Science, pp. 688–689. Springer, Berlin (1990)
16.
17.
Van Dijk, M., Clarke, D., Gassend, B., Edward Suh, G., Devadas, S.: Speeding up exponentiation using an untrusted computational resource. Des. Codes Cryptogr. 39, 253–273 (2006)MathSciNetCrossRefMATH
18.
19.
Cramer, R., Damgard, I., Schoenmakers, B.: Proofs of partial knowledge and simplified design of witness hiding protocols. In: Advances in Cryptology (CRYPTO 94), volume 839 of Lecture Notes in Computer Science, pp. 174–187. Springer, Berlin (1994)
20.
El Gamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. In: Proceedings of CRYPTO 84 on Advances in Cryptology, pp. 10–18. Springer, New York (1985)
21.
Ma, X., Li, J., Zhang, F.: Outsourcing computation of modular exponentiations in cloud computing. Clust. Comput. 16(4), 787–796 (2013)CrossRef
22.
Liu, J., Yang, B., Du, Z.: Outsourcing of verifiable composite modular exponentiations. In: INCoS, pp. 546–551 (2013)
23.
Yao, A.C.: Protocols for secure computations. In: Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (SFCS ’82), pp. 160–164. IEEE Computer Society (1982)
24.
Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Advances in Cryptology EUROCRYPT 99, volume 1592 of Lecture Notes in Computer Science, pp. 223–238. Springer, Berlin (1999)
25.
Boneh, D., Goh, E.-J., Nissim, K.: Evaluating 2-dnf formulas on ciphertexts. In: Theory of Cryptography, volume 3378 of Lecture Notes in Computer Science, pp. 325–341. Springer, Berlin (2005)
26.
Gentry, C.: A Fully Homomorphic Encryption Scheme. PhD thesis, Stanford, CA, USA (2009)
27.
Kilian, J.: Founding crytpography on oblivious transfer. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing (STOC ’88), pp. 20–31. ACM, New York, NY, USA (1988)
28.
Goldreich, O.: Foundations of Cryptography: Basic Applications, vol. 2. Cambridge University Press, New York (2004)CrossRefMATH
29.
30.
Di Crescenzo, G., Malkin, T., Ostrovsky, R.: Single database private information retrieval implies oblivious transfer. In: Advances in Cryptology EUROCRYPT 2000, volume 1807 of Lecture Notes in Computer Science, pp. 122–138. Springer, Berlin (2000)
31.
Juels, A., Szydlo, M.: A two-server, sealed-bid auction protocol. In: Blaze, M. (ed.) Financial Cryptography, volume 2357 of Lecture Notes in Computer Science, pp. 72–86. Springer, Berlin (2003)
32.
Lipmaa, H.: Verifiable homomorphic oblivious transfer and private equality test. In: Advances in Cryptology—ASIACRYPT 2003, volume 2894 of Lecture Notes in Computer Science, pp. 416–433. Springer, Berlin (2003)
33.
Bringer, J., Chabanne, H., Patey, A.: Shade: Secure hamming distance computation from oblivious transfer. In: Financial Cryptography and Data Security, volume 7862 of Lecture Notes in Computer Science, pp. 164–176. Springer, Berlin (2013)
34.
Chaum, D.: Blind signatures for untraceable payments. In: Chaum, D., Rivest, R.L., Sherman, A.T. (eds.) Advances in Cryptology, Proceedings of CRYPTO ’82, pp. 199–203. Springer, Berlin (1983)
35.
Brands, S.A.: Rethinking Public Key Infrastructures and Digital Certificates: Building in Privacy. MIT Press, Cambridge (2000)
36.
Cohen, H., Frey, G., Avanzi, R., Doche, C., Lange, T., Nguyen, K., Vercauteren, F.: Handbook of Elliptic and Hyperelliptic Curve Cryptography, 1st edn. Chapman & Hall, Boca Raton (2006)MATH
37.
Barbulescu, R., Gaudry, P., Joux, A., Thomé, E.: A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic. CoRR, abs/1306.4244 (2013)
38.
39.
40.
41.
Coster, M.J., Joux, A., 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
42.
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
43.
Aumann, Y., Lindell, Y.: Security against covert adversaries: efficient protocols for realistic adversaries. J. Cryptol. 23(2), 281–343 (2010)MathSciNetCrossRefMATH
44.
Di Crescenzo, G., Ostrovsky, R.: On concurrent zero-knowledge with pre-processing. In: Advances in Cryptology (CRYPTO 99), volume 1666 of Lecture Notes in Computer Science, pp. 485–502. Springer, Berlin (1999)
45.
Pedersen, T.: Non-interactive and information-theoretic secure verifiable secret sharing. In: Advances in Cryptology (CRYPTO 91), volume 576 of Lecture Notes in Computer Science, pp. 129–140. Springer, Berlin (1992)
46.
Cramer, R., Gennaro, R., Schoenmakers, B: A secure and optimally efficient multi-authority election scheme. In: Proceedings of the 16th Annual International Conference on Theory and Application of Cryptographic Techniques (EUROCRYPT’97), pp. 103–118. Springer, Berlin (1997)
47.
Gennaro, R.: Multi-trapdoor commitments and their applications to proofs of knowledge secure under concurrent man-in-the-middle attacks. In: Advances in Cryptology (CRYPTO 2004), volume 3152 of Lecture Notes in Computer Science, pp. 220–236. Springer, Berlin (2004)
48.
Seysen, M.: Using an rsa accelerator for modular inversion. In: Proceedings of the Cryptographic Hardware and Embedded Systems (CHES 2005), 7th International Workshop, Edinburgh, UK, August 29–September 1, 2005, volume 3659 of Lecture Notes in Computer Science, pp. 226–236. Springer, Berlin (2005)
Metadata
Title
Efficient and verifiable algorithms for secure outsourcing of cryptographic computations
Authors
Mehmet Sabır Kiraz
Osmanbey Uzunkol
Publication date
01-10-2016
Publisher
Springer Berlin Heidelberg
Published in
International Journal of Information Security / Issue 5/2016
Print ISSN: 1615-5262
Electronic ISSN: 1615-5270
DOI
https://doi.org/10.1007/s10207-015-0308-7

Other articles of this Issue 5/2016

International Journal of Information Security 5/2016 Go to the issue

Regular Contribution

Private and oblivious set and multiset operations

Regular Contribution

If it looks like a spammer and behaves like a spammer, it must be a spammer: analysis and detection of microblogging spam accounts

Regular Contribution

Time-specific encryption from forward-secure encryption: generic and direct constructions

Regular Contribution

Efficient wildcard search over encrypted data

Regular Contribution

New facets of mobile botnet: architecture and evaluation

Premium Partner

    Image Credits