Abstract
We investigate the problem of securely outsourcing modular exponentiations to a single, malicious computational resource. We revisit recently proposed schemes using single server and analyse them against two fundamental security properties, namely privacy of inputs and verifiability of outputs. Interestingly, we observe that the chosen schemes do not appear to meet both the security properties. In fact we present a simple polynomial-time attack on each algorithm, allowing the malicious server either to recover a secret input or to convincingly fool the client with wrong outputs. Then we provide a fix to the identified problem in the ExpSOS scheme. With our fix and without pre-processing, the improved scheme becomes the best to-date outsourcing scheme for single-server case. Finally we present the first precomputation-free single-server algorithm, \(\pi \)ExpSOS for simultaneous exponentiations, thereby solving an important problem formulated in [6].
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
Similar content being viewed by others
References
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 1987), pp 195–203. ACM (1987). https://doi.org/10.1145/28395.28417
Ateniese, G., et al.: Provable data possession at untrusted stores. In: Proceedings of the 14th ACM Conference on Computer and Communications Security, CCS 2007, pp. 598–609. ACM, New York (2007). https://doi.org/10.1145/1315245.1315318
Bowers, K.D., Juels, A., Oprea, A.: Proofs of retrievability: theory and implementation. In: Proceedings of the 2009 ACM Workshop on Cloud Computing Security, CCSW 2009, pp. 43–54. ACM, New York (2009). https://doi.org/10.1145/1655008.1655015
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). https://doi.org/10.1007/BFb0054129
Cai, J., Ren, Y., Huang, C.: Verifiable outsourcing computation of modular exponentiations with single server. Int. J. Network Secur. 19(3), 449–457 (2017). http://ijns.jalaxy.com.tw/download_paper.jsp?PaperID=IJNS-2015-12-05-1&PaperName=ijns-v19-n3/ijns-2017-v19-n3-p449-457.pdf
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). https://doi.org/10.1007/978-3-642-33167-1_31
Chevalier, C., Laguillaumie, F., Vergnaud, D.: Privately outsourcing exponentiation to a single server: cryptanalysis and optimal constructions. In: Askoxylakis, I., Ioannidis, S., Katsikas, S., Meadows, C. (eds.) ESORICS 2016. LNCS, vol. 9878, pp. 261–278. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-45744-4_13
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). https://doi.org/10.1007/978-3-642-14623-7_25
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). https://doi.org/10.1007/11593447_33
Golle, P., Mironov, I.: Uncheatable distributed computations. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 425–440. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45353-9_31
Green, M., Hohenberger, S., Waters, B.: Outsourcing the decryption of ABEciphertexts. In: USENIX Security Symposium 2011. USENIX Association (2011). https://www.usenix.org/publications/proceedings/?f[0]=im_group_audience%3A277
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). https://doi.org/10.1007/978-3-540-30576-7_15
Kim, S., Lewi, K., Mandal, A., Montgomery, H., Roy, A., Wu, D.J.: Function-Hiding Inner Product Encryption is Practical. Cryptology ePrint Archive, Report 2016/440 (2016), accepted at SCN 2018. https://eprint.iacr.org/2016/440
Kiraz, M.S., Uzunkol, O.: Efficient and verifiable algorithms for secure outsourcing of cryptographic computations. Int. J. Inf. Secur. 15(5), 519–537 (2016). https://doi.org/10.1007/s10207-015-0308-7
Kuppusamy, L., Rangasamy, J.: CRT-based outsourcing algorithms for modular exponentiations. In: Dunkelman, O., Sanadhya, S.K. (eds.) INDOCRYPT 2016. LNCS, vol. 10095, pp. 81–98. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-49890-4_5
Li, S., Huang, L., Fu, A., Yearwood, J.: CExp: secure and verifiable outsourcing of composite modular exponentiation with single untrusted server. Digit. Commun. Netw. 3(4), 236–241 (2017). https://doi.org/10.1016/j.dcan.2017.05.001
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, New York (1990). https://doi.org/10.1007/0-387-34799-2_35
McLoone, M., Robshaw, M.J.B.: Public key cryptography and RFID tags. In: Abe, M. (ed.) CT-RSA 2007. LNCS, vol. 4377, pp. 372–384. Springer, Heidelberg (2006). https://doi.org/10.1007/11967668_24
Miller, G.L.: Riemann’s hypothesis and tests for primality. In: Rounds, W.C., Martin, N., Carlyle, J.W., Harrison, M.A. (eds.) Proceedings of the ACM Symposium on Theory of Computing (STOC) 1975, pp. 234–239. ACM (1975). https://doi.org/10.1145/800116.803773
Nguyen, P.Q., Shparlinski, I.E., Stern, J.: Distribution of modular sums and the security of the server aided exponentiation. In: Proceedings of the Cryptography and Computational Number Theory Workshop, pp. 257–268. Birkhäuser (2001). https://doi.org/10.1007/978-3-0348-8295-8_24
Schnorr, C.P.: Efficient identification and signatures for smart cards. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 239–252. Springer, New York (1990). https://doi.org/10.1007/0-387-34805-0_22
Schnorr, C.P.: Efficient signature generation by smart cards. J. Cryptology 4(3), 161–174 (1991). https://doi.org/10.1007/BF00196725
Wang, Y., et al.: 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, Cham (2014). https://doi.org/10.1007/978-3-319-11203-9_19
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). https://doi.org/10.1007/978-3-540-88733-1_10
Zhou, K., Afifi, M.H., Ren, J.: ExpSOS: secure and verifiable outsourcing of exponentiation operations for mobile cloud computing. IEEE Trans. Inf. Forens. Secur. 12(11), 2518–2531 (2017). https://doi.org/10.1109/TIFS.2017.2710941
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Rangasamy, J., Kuppusamy, L. (2018). Revisiting Single-Server Algorithms for Outsourcing Modular Exponentiation. In: Chakraborty, D., Iwata, T. (eds) Progress in Cryptology – INDOCRYPT 2018. INDOCRYPT 2018. Lecture Notes in Computer Science(), vol 11356. Springer, Cham. https://doi.org/10.1007/978-3-030-05378-9_1
Download citation
DOI: https://doi.org/10.1007/978-3-030-05378-9_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-05377-2
Online ISBN: 978-3-030-05378-9
eBook Packages: Computer ScienceComputer Science (R0)