Solving quadratic congruences is a widely applied operation in cryptographic protocols to ensure the data secrecy in the Internet of Things (IoT). Yet it requires unaffordable computation resource for resource-constrained IoT devices when bulk of this type of operations need to be performed. How to efficiently and effectively solve quadratic congruences on IoT devices becomes a challenging issue. To address this problem, in this paper, we propose two practical and secure outsourcing algorithms for solving quadratic congruences. Our proposed algorithms enable the IoT devices to outsource the heavy computation of solving quadratic congruences to a single cloud server, and therefore achieves high efficiency for IoT devices. Meanwhile, we obscure the input and the output so that the outsourcing process will not leak the privacy of the computation, and the IoT devices in our algorithms can detect any misbehavior of the cloud server with a probability of 1. In addition, we take the Rabin encryption algorithm as an example to show how our proposed algorithms can be applied to IoT applications. The theoretical analysis and experimental results support that our proposed algorithms are secure and efficient.

Rivest-Shamir-Adleman (RSA) is one widely deployed public key algorithm. Yet, its decryption facet is very time-consuming for resource-constrained Internet-of-Thing (IoT) devices, as it is based on the modular exponentiation of a large number. Although several variants of RSA have been designed to accelerate decryption, the outcomes have been far from satisfactory. Therefore, it is of imminent importance to investigate how to securely outsource RSA decryption to computational powerful parties as an alternative solution. In this paper, we introduce the first efficient and secure outsourcing scheme for RSA decryption in IoT. Though RSA decryption is achieved via modular exponentiation, existing secure outsourcing schemes for modular exponentiation either assume the modulus to be prime and are not applicable to RSA, or incur massive computation costs and are heavy-laden in practice. To address these issues, we have designed our scheme based on the Chinese Remainder Theorem (CRT). In our scheme, the private key (including the exponent and the modulus) and the plaintext are concealed concurrently, and the proposed scheme is highly efficient for both client and cloud. In addition, our scheme enables the client to detect any misbehavior of the cloud server with a probability of 99.17 %. To validate the effectiveness of our proposed scheme, we provide rigorous proofs of security and verifiability, as well as efficiency analysis. The effectiveness and efficiency of our scheme are further confirmed based on experimental results.

With the recent growth and commercialization of cloud computing, outsourcing computation has become one of the most important cloud services, which allows the resource-constrained clients to efficiently perform large-scale computation in a pay-per-use manner. Meanwhile, outsourcing large scale computing problems and computationally intensive applications to the cloud has become prevalent in science and engineering computing community. As important fundamental operations, large-scale matrix multiplication computation (MMC), matrix inversion computation (MIC) and matrix determinant computation (MDC) have been frequently used. In this paper, we present three new algorithms to enable secure, verifiable, and efficient outsourcing of MMC, MIC and MDC operations to a cloud that may be potentially malicious. The main idea behind our algorithms is a novel matrix encryption/decryption method utilizing consecutive and sparse unimodular matrix transformations. Compared with previous works, this versatile technique can be applied to many matrix operations, while achieving a good balance between security and efficiency. First, the proposed algorithms provide robust confidentiality by concealing the local information of the entries in the input matrices. Besides, they also protect the statistic information of the original matrix. Moreover, these algorithms are highly efficient. Our theoretical analysis indicates that the proposed algorithms reduce the time overhead on the client side from O(n2.3728639) to O(n2). Finally, the extensive experimental evaluations demonstrate the practical efficiency and effectiveness of our algorithms.