Lattice Security Analysis Algorithms for the Quadratic Congruence Outsourcing Scheme in IoT

Designing secure outsourcing schemes enables resource-constrained Internet of Things (IoT) devices to perform highly complex computational tasks. Solving the quadratic congruence problem is one of the core components in the construction of cryptographic algorithms for IoT. Recently, Rangasamy designed an outsourcing scheme for solving quadratic congruence equations. Interestingly, we find that the scheme has the risk of secret information being cracked. We propose two lattice attack algorithms in this article. In the first attack algorithm, we prove that there is a possibility of leaking secret information in the public parameters of the outsourcing scheme. Specifically, by intercepting the parameters transmitted between the client and the server, and combining the ideas from Fermat’s Little Theorem and the Euclidean algorithm, the attacker can obtain multiples of the secret parameter p. Furthermore, after recover the value of p, our attack algorithm is capable of recovering all secret parameters in the quadratic congruence equation. In the second attack algorithm, we note that the authors recommend the randomly chosen value of k to be small in the original outsourcing scheme. However, in this article, we point out that the random value k should not be too small, otherwise, the outsourcing scheme would be wrecked. More precisely, we use the Coppersmith method to provide an approach that can recover all the secret information. Our attack algorithm will succeed once k satisfied <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$|k| \lt \sqrt {p}$ </tex-math></inline-formula>, so in order to ensure the security of the outsourcing scheme, we propose the recommended selection length of the random value k. Finally, we experimentally verified the two proposed attack algorithms.