Efficient Algorithm for Secure Outsourcing of Modular Exponentiation with Single Server
Outsourcing computation allows an outsourcer with limited resource to delegate the computation load to a powerful server without the exposure of true inputs and outputs. It is well known that modular exponentiation is one of the most expensive operations in public key cryptosystems. Currently, most of outsourcing algorithms for modular exponentiation are based on two untrusted servers or have small checkability with single server. In this paper, we first propose an efficient outsourcing algorithm of modular exponentiation based on two untrusted servers, where the outsourcer can detect the error based on Euler theorem with a probability of 1 if one of the servers misbehaves. We then present an outsourcing algorithm of modular exponentiation with single server, and the outsourcer can also check the failure with a probability of 1. Therefore, the proposed algorithm with single server improves efficiency and checkability simultaneously compare with the previous ones. Finally, we provide the experimental evaluations to demonstrate that the proposed two algorithms are the most efficient ones in all of the outsourcing algorithms for an outsourcer.
Despite of many tremendous advantages, outsourcing computation also meets some security challenges. At the era of cloud computing, it is very difficult to find a cloud server which is absolutely trusted for an outsourcer. Firstly, the com-putation tasks always contain some sensitive information and the outsourcer does not want to disclose them to the servers . Therefore, the outsourcer should ensure the secrecy of in-puts and outputs before it delegates the computation task to the servers, which means sensitive information of the out-sourcer will not be exposed during the phase of outsourcing computation. The second problem the outsourcer should con-sider is how to detect the server’s failures with high probability since the servers are potentially malicious, for example, they may be controlled by an adversary and return invalid re-sults to the outsourcer. The outsourcer should verify the out-sourcing result returned by the server effectively and refuses it once the server misbehaves. The third challenge is that the test procedure should not include complicated operations be-cause the outsourcer will execute the procedure when it re-ceives the outsourcing result. The algorithm of outsourcing computation is meaningless if the test procedure is too com-plicated for the outsourcer with limited ability. Therefore, se-cure outsourcing computation should simultaneously ensure secrecy of sensitive information, verifiability of the outsourc-ing result, and efficiency of the testing phase.
• Firstly, the computation tasks always contain some sensitive information and the outsourcer does not want to disclose them to the servers
• The second problem the outsourcer should consider is how to detect the server’s failures with high probability since the servers are potentially malicious
• The third challenge is that the test procedure should not include complicated operations be-cause the outsourcer will execute the procedure when it receives the outsourcing result
In this work , we present two fully verifiable outsourcing algorithms of MExp based on Euler Theorem. Firstly, we propose an outsourcing algorithm in the one-malicious model of two untrusted servers, and the out-sourcer can detect the errors made by the dishonest server with a probability of 1. Compared with the previous algo-rithms, the proposed one is better in both checkability and ef-ficiency without interaction between the outsourcer and the servers. We also present secure outsourcing algorithm of MExp with full verifiability based on single server, which is the most important contribution of this paper. The second pro-posed algorithm improves efficiency and checkability simul-taneously compared with the previous ones with single server. At the end of this paper, we give the detailed theoretical and experimental analysis, which also show the advantage of the proposed two algorithms in checkability, communication and computation efficiency.
Thus this paper propose two non-interactive verifiable outsourc-ing algorithms for modular exponentiation. Firstly, we propose a new outsourcing algorithm of modular exponentiation based on two untrusted servers, where the outsourcer can detect the error based on Euler theorem with a probability of 1 if one of the serv-ers misbehaves. We then propose another outsourcing algorithm with single server, which improves the efficiency and the check-ability simultaneously compare with the previous ones. Finally, we conclude that the proposed algorithms are most efficient in all of the outsourcing algorithms for the outsourcer by theoretical analysis and experimental evaluation.