nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

CRT-Based Outsourcing Algorithms for Modular Exponentiations

verfasst von : Lakshmi Kuppusamy, Jothi Rangasamy

Erschienen in: Progress in Cryptology – INDOCRYPT 2016

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The problem of securely outsourcing cryptographic computations to the untrusted servers was formally addressed first by Hohenberger and Lysyanskaya in TCC 2005. They presented an algorithm which outsources computation of modular exponentiations securely to two non-interacting third-party servers but the checkability of third-party computations has probability 1 / 2. Chen et al. improved this algorithm for two non-colluding servers by increasing the checkability probability to 2/3. For real-world cryptographic applications it is desirable that the checkability probability is \(1-\epsilon \), where \(\epsilon \) becomes negligible for appropriate parameter choices. Towards a more practical use, we present an algorithm(s) for secure outsourcing of (simultaneous) modular exponentiation(s) which can be seen as another application of the Chinese remainder theorem (CRT). Interestingly the checkability probability of our algorithm is 1 in the presence of two non colluding servers. Our algorithm is superior in both efficiency and checkability compared to that of the previously known schemes of the same kind. Finally we discuss the potential practical applications for our outsourcing schemes, for example computing the final exponentiation in pairings.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel The Shortest Signatures Ever

Nächstes Kapitel Verifiable Computation for Randomized Algorithm

Nur mit Berechtigung zugänglich

We use the terms worker, program and oracle interchangeably to refer to the untrusted server.

Abadi, M., Feigenbaum, J., Kilian, J.: On hiding information from an oracle. In: Proceedings of the Second Annual Conference on Structure in Complexity Theory, pp. 195–203. IEEE Computer Society (1987)

Golle, P., Mironov, I.: Uncheatable distributed computations. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 425–440. Springer, Heidelberg (2001). doi:10.1007/3-540-45353-9_31 CrossRef

Girault, M., Lefranc, D.: Server-aided verification: theory and practice. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 605–623. Springer, Heidelberg (2005). doi:10.1007/11593447_33 CrossRef

Wu, W., Mu, Y., Susilo, W., Huang, X.: Server-aided verification signatures: definitions and new constructions. In: Baek, J., Bao, F., Chen, K., Lai, X. (eds.) ProvSec 2008. LNCS, vol. 5324, pp. 141–155. Springer, Heidelberg (2008). doi:10.1007/978-3-540-88733-1_10 CrossRef

Gennaro, R., Gentry, C., Parno, B.: Non-interactive verifiable computing: outsourcing computation to untrusted workers. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 465–482. Springer, Heidelberg (2010). doi:10.1007/978-3-642-14623-7_25 CrossRef

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

Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Mitzenmacher, M. (ed.) Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, pp. 169–178. ACM (2009)

Hohenberger, S., Lysyanskaya, A.: How to securely outsource cryptographic computations. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 264–282. Springer, Heidelberg (2005). doi:10.1007/978-3-540-30576-7_15 CrossRef

van Dijk, M., Clarke, D.E., Gassend, B., Suh, G.E., Devadas, S.: Speeding up exponentiation using an untrusted computational resource. Des. Codes Cryptogr. 39(2), 253–273 (2006)MathSciNetCrossRefMATH

10.

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.) ESORICS 2012. LNCS, vol. 7459, pp. 541–556. Springer, Heidelberg (2012). doi:10.1007/978-3-642-33167-1_31 CrossRef

11.

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: Kutyłowski, M., Vaidya, J. (eds.) ESORICS 2014. LNCS, vol. 8712, pp. 326–343. Springer, Heidelberg (2014). doi:10.1007/978-3-319-11203-9_19

12.

Kiraz, M.S., Uzunkol, O.: Efficient and verifiable algorithms for secure outsourcing of cryptographic computations. Cryptology ePrint Archive, Report 2014/748 (2014). http://eprint.iacr.org/

13.

Matsumoto, T., Kato, K., Imai, H.: Speeding up secret computations with insecure auxiliary devices. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 497–506. Springer, Heidelberg (1990). doi:10.1007/0-387-34799-2_35

14.

Nguyen, P.Q., Shparlinski, I.E.: On the insecurity of a server-aided RSA protocol. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 21–35. Springer, Heidelberg (2001). doi:10.1007/3-540-45682-1_2 CrossRef

15.

Chevalier, C., Laguillaumie, F., Vergnaud, D.: Privately outsourcing exponentiation to a single server: cryptanalysis and optimal constructions. IACR Cryptology ePrint Archive 2016/309 (2016)

16.

Kiraz, M.S., Uzunkol, O.: Efficient and verifiable algorithms for secure outsourcing of cryptographic computations. Int. J. Inf. Secur. 15(5), 519–537 (2016). doi:10.1007/s10207-015-0308-7 CrossRef

17.

Boyko, V., Peinado, M., Venkatesan, R.: Speeding up discrete log and factoring based schemes via precomputations. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 221–235. Springer, Heidelberg (1998). doi:10.1007/BFb0054129

18.

Nguyen, P., Shparlinski, I., Stern, J.: Distribution of modular sums and the security of the server aided exponentiation. In: Proceedings of the Workshop on Cryptography and Computational Number Theory (CCNT 1999), Singapore, Birkhäuser, pp. 257–268 (2001)

19.

Hinek, M.: On the security of multi-prime RSA. http://cacr.uwaterloo.ca/techreports/2006/cacr2006-16.pdf

20.

Chevallier-Mames, B., Coron, J.-S., McCullagh, N., Naccache, D., Scott, M.: Secure delegation of elliptic-curve pairing. In: Gollmann, D., Lanet, J.-L., Iguchi-Cartigny, J. (eds.) CARDIS 2010. LNCS, vol. 6035, pp. 24–35. Springer, Heidelberg (2010). doi:10.1007/978-3-642-12510-2_3 CrossRef

21.

Guillevic, A.: Comparing the pairing efficiency over composite-order and prime-order elliptic curves. In: Jacobson, M., Locasto, M., Mohassel, P., Safavi-Naini, R. (eds.) ACNS. LNCS, vol. 7954, pp. 357–372. Springer, Heidelberg (2013)

22.

Scott, M.: Unbalancing pairing-based key exchange protocols. IACR Cryptology ePrint Archive 2013/688 (2013). http://eprint.iacr.org/2013/688

23.

Miller, V.S.: The weil pairing, and its efficient calculation. J. Cryptol. 17(4), 235–261 (2004)MathSciNetCrossRefMATH

24.

Scott, M., Benger, N., Charlemagne, M., Dominguez Perez, L.J., Kachisa, E.J.: On the final exponentiation for calculating pairings on ordinary elliptic curves. In: Shacham, H., Waters, B. (eds.) Pairing 2009. LNCS, vol. 5671, pp. 78–88. Springer, Heidelberg (2009). doi:10.1007/978-3-642-03298-1_6 CrossRef

25.

Kim, T., Kim, S., Cheon, J.H.: On the final exponentiation in tate pairing computations. IEEE Trans. Inf. Theory 59(6), 4033–4041 (2013)MathSciNetCrossRef

26.

Cramer, R., Shoup, V.: Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack. SIAM J. Comput. 33(1), 167–226 (2003)MathSciNetCrossRefMATH

27.

Schnorr, C.P.: Efficient identification and signatures for smart cards. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 239–252. Springer, Heidelberg (1990). doi:10.1007/0-387-34805-0_22 CrossRef

28.

Schnorr, C.P.: Efficient signature generation by smart cards. J. Cryptol. 4(3), 161–174 (1991)MathSciNetCrossRefMATH

29.

Ateniese, G., Medeiros, B.: Identity-based chameleon hash and applications. In: Juels, A. (ed.) FC 2004. LNCS, vol. 3110, pp. 164–180. Springer, Heidelberg (2004). doi:10.1007/978-3-540-27809-2_19 CrossRef

30.

Fischlin, M., Fischlin, R.: Efficient non-malleable commitment schemes. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 413–431. Springer, Heidelberg (2000). doi:10.1007/3-540-44598-6_26 CrossRef

31.

Ateniese, G., Burns, R.C., Curtmola, R., Herring, J., Kissner, L., Peterson, Z.N.J., Song, D.X.: Provable data possession at untrusted stores. In: Ning, P., di Vimercati, S.D.C., Syverson, P.F. (eds.) ACM CCS 2007, pp. 598–609. ACM (2007)

Titel: CRT-Based Outsourcing Algorithms for Modular Exponentiations
verfasst von: Lakshmi Kuppusamy
Jothi Rangasamy
Verlag: Springer International Publishing
Buch: Progress in Cryptology – INDOCRYPT 2016
Print ISBN: 978-3-319-49889-8

Electronic ISBN: 978-3-319-49890-4

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-319-49890-4_5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"