How to securely outsource the extended euclidean algorithm for large-scale polynomials over finite fields

Cloud computing gives resource-constrained clients great conveniences to outsource exorbitant computations to a public cloud. The extended Euclidean algorithm with large-scale polynomials over finite fields is fundamental and widespread in computer science and cryptography, yet it is computationally overloaded for quantities of lightweight devices emerged with the dawn of internet of things (IoT). In this respect, we design an efficient outsourcing algorithm that enables a lightweight client to achieve this heavy computation with the assistance of a remote cloud server. By comprehensively employing the variable substitution, random polynomial-based blind technique and unimodular matrix transformation, our algorithm achieves the goals of cheating resistance, privacy preservation, and high efficiency. Concretely, our algorithm is based on single untrusted program model which avoids the too strong security assumption between multiple servers, and it enables the client to detect the cloud's misbehaviors with (optimal) probability 1. Also, Thorough theoretical analysis indicates that the algorithm provides robust input/output privacy. Moreover, the algorithm only needs one round interaction between the client and the cloud. Strict theoretical analysis and extensive experimental evaluations demonstrate our algorithm's practical efficiency and effectiveness. Finally, an important application of our algorithm on securely outsourcing the expensive key generation step of NTRU cryptosystem is given. (C) 2019 Elsevier Inc. All rights reserved.