Security Analysis And Improvement Of Modular Index Outsourcing Scheme

Cloud computing has the ability to process huge amounts of data and perform parallel computation,which provides customers with convenient and abundant storage and computing resources on demand based on the pay-for-use manner.Therefore,resource-constrained users can perform complex computing tasks with the help of cloud computing platform.However,the cloud server is not trusted and the outsourced data is sensitive,which makes the outsourced computing model face many security issues and challenges.In this background,how to build a secure and verifiable outsourcing scheme has become a research hotspot in the field of cloud computing security.As a basic operation in public key cryptography,modular exponent often involves complex large integer operation,which causes heavy computing burden to various resource-limited Internet of Things devices.Therefore,the design of secure cloudassisted modular exponential outsourcing computing scheme has attracted extensive attention from researchers.This paper analyzes the security of the modular exponentiation outsourcing algorithm proposed by Ding et al.,Zhou et al.,and points out the security weakness in their schemes.Meanwhile,several flaw in Ren et al's modular exponentiation outsourcing algorithm are modified:(1)We evaluate the security of the modular exponential outsourcing scheme based on the single server model proposed by Ding et al,point out the security problems in their schemes,and give countermeasures and suggestions.Firstly,the private key recovery problem in these schemes is transformed into the problem of finding the short vector in lattice.Furthermore,based on lattice basis reduction techniques,we present a polynomial-time small key recovery attack in ciphertext-only mode,which indicates that the recommended parameters of their original protocols can not guarantee the privacy of the exponents.Meanwhile,based on the different size of input in the actual problem,we alter the strategy of parameter selection strategy in the original schemes to avoid these attacks.Finally,we analyze the efficiency of the altered schemes with security parameters.Our theoretical analysis and experimental results shows that in practice scenarios,the outsourcing scheme for single modular exponential Exp is ineffective,the efficiency of the simultaneous modular exponential outsourcing scheme SExp is reduced,and the efficiency of the multiple modular exponential outsourcing scheme MExp increases with the increase of the number of exponentiations.(2)We performed the weak-key analysis on Zhou et al.'s single-server-model outsourcing scheme Exp SOS for modular exponentiation,and the parameter selection scale in the original scheme is quantitatively analyzed based on lattice reduction algorithm.Based on the lattice-based Coppersmith's method,the problem of recovering key parameters in the scheme can be transformed into the problem of solving small integer solutions of polynomials module unknown divisors,and the security vulnerabilities of Exp SOS scheme are analyzed and evaluated comprehensively.In the actual application scenario,the applicable size of base for the outsourcing scheme and the security conditions for the key parameters in the scheme are estimated,and specific suggestions are put forward for the security deployment of the scheme in the actual application.Finally,with the recommended parameters of DSS,we simulate the Exp SOS scheme and some practical attack examples of weak key in Exp SOS scheme are given,which confirm the effectiveness of our theoretical attack and the necessity of the scheme remedy.(3)We point out the design defects in the Ren et al.'s two algorithms for outsourcing modular exponentiations are actually incorrect due to the misuse of the Euler theorem in the verification step,which makes their verification process incorrect in general.Moreover,we suggest a remedial measure for the two-server algorithm.