Privacy-preserving composite modular exponentiation outsourcing with optimal checkability in single untrusted cloud server

Outsourcing computing allows users with resource-constrained devices to outsource their complex computation workloads to cloud servers, which is more economical for cloud customers. However, since users lose direct control of the computation task, possible threats need to be addressed, such as data privacy and the correctness of results. Modular exponentiation is one of the most basic and time-consuming operations but widely applied in the field of cryptography. In this paper, we propose two new and efficient algorithms for secure outsourcing of single and multiple composite modular exponentiations. Unlike the algorithms based on two untrusted servers, we outsource modular exponentiation operation to only a single server, eliminating the possible collusion attack with two servers. Moreover, we put forward a new mathematical division method, which hides the base and exponent of the outsourced data, without exposing sensitive information to the cloud server. In addition, compared with other state-of-the-art algorithms, our scheme shows a remarkable improvement in checkability, enabling the user to detect any misbehavior with the optimal probability close to 1. Finally, we use our proposed algorithms as a subroutine to realize Shamir's Identity-Based Signature Scheme and Identity-Based Multi-Signatures Scheme.