Abstract
Security protocols using public-key cryptography often requires large number of costly modular exponentiations (MEs). With the proliferation of resource-constrained (mobile) devices and advancements in cloud computing, delegation of such expensive computations to powerful server providers has gained lots of attention. In this paper, we address the problem of verifiably secure delegation of MEs using two servers, where at most one of which is assumed to be malicious (the OMTUP-model). We first show verifiability issues of two recent schemes: We show that a scheme from IndoCrypt 2016 does not offer full verifiability, and that a scheme for n simultaneous MEs from AsiaCCS 2016 is verifiable only with a probability 0.5909 instead of the author’s claim with a probability 0.9955 for \(n=10\). Then, we propose the first non-interactive fully verifiable secure delegation scheme by hiding the modulus via Chinese Remainder Theorem (CRT). Our scheme improves also the computational efficiency of the previous schemes considerably. Hence, we provide a lightweight delegation enabling weak clients to securely and verifiably delegate MEs without any expensive local computation (neither online nor offline). The proposed scheme is highly useful for devices having (a) only ultra-lightweight memory, and (b) limited computational power (e.g. sensor nodes, RFID tags).
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
Notes
- 1.
In this paper, we introduce a special delegation scheme by working with a subgroup \(\mathbb {G}\) of the group \(\mathbb {Z}_p^*\) of prime order q.
- 2.
We assume here that the prime numbers p and q are chosen suitably that the factorization of \(n=pq\) is intractable.
- 3.
We here only consider the group operations like group multiplications, modular reduction, inversions and exponentiations as atomic operations, and neglect any lower-order operations such as congruence testing, equality testing, and modular additions.
- 4.
More precisely, hiding p enables the delegator to achieve the full verifiability in a single round unlike the fully verifiable scheme in [11] which requires an additional round of communication. The reason is that it is possible for \(\mathcal {C}\) to send the randomized base and the exponent by a system of simultaneous congruences, and recover/verify the actual outputs by performing modular reductions (once modulo p for recovery, and once modulo r for verification) in a single round. Note that for a given p each client \(\mathcal {C}\) is required to use the same prime number r since otherwise p can be found by taking gcd’s of different moduli.
References
Asghar, N.: A survey on blind digital signatures. Technical report (2011)
Cavallo, B., Di Crescenzo, G., Kahrobaei, D., Shpilrain, V.: Efficient and secure delegation of group exponentiation to a single server. In: Mangard, S., Schaumont, P. (eds.) RFIDSec 2015. LNCS, vol. 9440, pp. 156–173. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-24837-0_10
Chaum, D.: Blind signatures for untraceable payments. In: Chaum, D., Rivest, R.L., Sherman, A.T. (eds.) Advances in Cryptology, pp. 199–203. Springer, Boston, MA (1983). https://doi.org/10.1007/978-1-4757-0602-4_18
Chaum, D., Pedersen, T.P.: Wallet databases with observers. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 89–105. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-48071-4_7
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
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
Kiraz, M.S., Uzunkol, O.: Efficient and verifiable algorithms for secure outsourcing of cryptographic computations. Int. J. Inf. Sec. 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
Nyberg, K., Rueppel, R.A.: Message recovery for signature schemes based on the discrete logarithm problem. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 182–193. Springer, Heidelberg (1995). https://doi.org/10.1007/BFb0053434
Ren, Y., Ding, N., Zhang, X., Lu, H., Gu, D.: Verifiable outsourcing algorithms for modular exponentiations with improved checkability. In: AsiaCCS 2016, pp. 293–303. ACM, New York (2016). https://doi.org/10.1145/2897845.2897881
Uzunkol, O., Rangasamy, J., Kuppusamy, L.: Hide The Modulus: a secure non-interactive fully verifiable delegation scheme for modular exponentiations via CRT (full version). IACR Cryptology ePrint Archive, Report 2018 (2018). https://eprint.iacr.org/2018/644
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, Cham (2014). https://doi.org/10.1007/978-3-319-11203-9_19
Zhou, K., Afifi, M.H., Ren, J.: ExpSOS: secure and verifiable outsourcing of exponentiation operations for mobile cloud computing. IEEE Trans. Inf. Forensics Sec. 12(11), 2518–2531 (2017). https://doi.org/10.1109/TIFS.2017.2710941
Acknowledgement
We thank the anonymous reviewers for their helpful comments on the previous version of the paper which led to improvements in the presentation of the paper.
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
Uzunkol, O., Rangasamy, J., Kuppusamy, L. (2018). Hide the Modulus: A Secure Non-Interactive Fully Verifiable Delegation Scheme for Modular Exponentiations via CRT. In: Chen, L., Manulis, M., Schneider, S. (eds) Information Security. ISC 2018. Lecture Notes in Computer Science(), vol 11060. Springer, Cham. https://doi.org/10.1007/978-3-319-99136-8_14
Download citation
DOI: https://doi.org/10.1007/978-3-319-99136-8_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-99135-1
Online ISBN: 978-3-319-99136-8
eBook Packages: Computer ScienceComputer Science (R0)