Cloud computing is a technological paradigm that enables the consumer to enjoy the benefits of computing services and applications without necessarily worrying about the investment and maintenance costs. This paper focuses on the applicability of a new fully homomorphic encryption scheme (FHE) in solving data security in cloud computing. Different types of existing homomorphic encryption schemes; including both partial and fully homomorphic encryption schemes are reviewed. The study was aimed at constructing a fully homomorphic encryption scheme that lessens the computational strain on the computing assets as compared to Gentry’s contribution on partial homomorphic encryption schemes where he constructed homomorphic encryption based on ideal lattices using both additive and multiplicative Homomorphisms. In this study both addition and composition operations implementing a fully homomorphic encryption scheme that secures data within cloud computing is used. The work is founded on mathematical theory that is translated into an algorithm implementable in JAVA. The work was tested by a single computing hardware to ascertain its suitability. The newly developed FHE scheme posted better results that confirmed its suitability for data security in cloud computing.