Most of the known public-key cryptosystems have an overall complexity which is dominated by the key-production algorithm, which requires the generation of prime numbers. This is most inconvenient in settings where the key-generation is not an one-off process, e.g., secure delegation of computation or EKE password-based key exchange protocols. To this end, we extend the Goldwasser-Micali (GM) cryptosystem to a provably secure system, denoted SIS, where the generation of primes is bypassed. Using number-theoretic and linear optimisation techniques, we align the security guarantees (i.e., resistance to factoring of moduli, etc.) of SIS to those of other well-known cryptosystems based on modular arithmetics. %Taking into consideration different possibilities to implement the fundamental operations, We explicitly compare and contrast the asymptotic complexity of well-known public-key cryptosystems based on modular arithmetics (e.g., GM and/or RSA) with that of SIS's. The latter shows that once we are ready to accept an increase in the size of the moduli, SIS's offers significant speed-ups to applications like the aforementioned secure delegation of computation or protocols where a fresh key needs to be generated with every new session. We also developed an efficient extension of SIS to handle more than one bit at a time, using linear codes, which will be omitted herein due to space constraints.