We propose a new method to construct a public-key encryption scheme, where one can homomorphically transform a ciphertext encrypted under a key \(\textbf{x}\) into a ciphertext under \((P, P(\textbf{x}))\) , for any polynomial-time RAM program \(P: \textbf{x} \mapsto \textbf{y}\) with runtime T and memory L. Combined with other lattice techniques, this allows us to construct: All of our schemes rely on the hardness of the decomposed learning with errors (LWE) problem, along with other standard computational assumptions on lattices. The decomposed LWE problem can be interpreted as postulating the circular-security of a natural lattice-based public-key encryption scheme. To gain confidence in the assumption, we show that it is implied by the hardness of the succinct LWE problem of Wee (CRYPTO’24).