We present attacks on a generalized subset-sum pseudorandom generator, which was proposed by von zur Gathen and Shparlinski in 2004. Our attacks rely on a sub-quadratic algorithm for solving a vectorial variant of the 3SUM problem, which is of independent interest. The attacks presented have complexities well below the brute-force attack, making the generators vulnerable. We provide a thorough analysis of the attacks and their complexities and demonstrate their practicality through implementations and experiments.

Abstract Public-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 et al. (Su, Q., Zhang, R. and Xue, R. (2020) Secure outsourcing algorithms for composite modular exponentiation based on single untrusted cloud. Comput. J., 63, 1271.) and Rangasamy and Kuppusamy (Rangasamy, J. and Kuppusamy, L. (2018) Revisiting Single-Server Algorithms for Outsourcing Modular Exponentiation. In Chakraborty, D. and Iwata, T. (eds), Progress in Cryptology - INDOCRYPT 2018: 19th International Conference in Cryptology in India, New Delhi, India, December 912, Vol. 11356, Lecture Notes in Computer Science. Springer, Heidelberg, Germany, pp. 320. 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.