Automatic facial recognition is fast becoming a reliable method for identifying individuals. Due to its reliability and unobtrusive nature facial recognition has been widely deployed in law enforcement and civilian application. Recent implementations of facial recognition systems on public cloud computing infrastructures have raised strong concerns regarding an individual's privacy. In this paper, we propose and implement a novel approach for facial recognition in the encrypted domain. This allows for facial recognition to be performed without revealing the actual image unnecessarily as the features stay encrypted at all times. Our proposed system exploits the homomorphic properties of the Paillier cryptosystem and performs Euclidean distance calculations using encrypted data. We propose to represent the images using a radial Local Ternary Pattern approach where a higher than proposed radius is used to extract the image features. Our proposed system has been evaluated using two publicly available datasets and has also been compared against the previously used eigenface approach in the encrypted domain and the obtained results justify the feasibility of the proposed system.