The encryption and the decryption of the product-sum type public key cryptosystems can be performed extremely fast. However, when the density is low, the cryptosystem should be broken by the low-density attack. In this paper, we propose a new class of the product-sum type public key cryptosystems based on the reduced bases, which is invulnerable to the low-density attack.