Cryptanalysis of Modular Exponentiation Outsourcing Protocols

International audiencePublic-key cryptographic primitives are time-consuming for resource-constrained devices. A classical problem is to securely offload group exponentiations from a (comparatively) weak device-the client-to an untrusted more powerful device-the server. A delegation protocol must usually meet two security objectives: privacy-the exponent or the base should not be revealed to a passive adversary-and verifiability-a malicious server should not be able to make the client accept an invalid value as the result of the delegated computation. Most proposed protocols relies on a secret splitting of the exponent and the base and a considerable amount of literature has been devoted to their analysis. Recently, Su, Zhang and Xue [The Computer Journal, 2020] and Rangasamy and Kuppusamy [Indocrypt 2018] proposed outsourcing protocols for modular exponentiations. They claim that their protocols achieve security (privacy and verifiability). We show that these claims are flawed and that their schemes are broken beyond repair. They remain insecure even if one increases significantly the proposed parameters (and consequently the protocols computational and communication complexities). Our attacks rely on standard lattice-based cryptanalytic techniques, namely the Coppersmith methods to find small integer zeroes of modular multivariate polynomials and simultaneous Diophantine approximation methods for the so-called approximate greatest common divisor problem