Practical and Secure Outsourcing Algorithms for Solving Quadratic Congruences in Internet of Things

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 article, 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, achieve high efficiency for IoT devices. Meanwhile, we obscure the input and the output so that the outsourcing process does 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 the fact that our proposed algorithms are secure and efficient.