Data privacy is a growing concern as more cloud-based solutions for extracting insights from images are available. Fully Homomorphic Encryption (FHE) is one of the state-of-the-art techniques to enable privacy preserving machine learning. However, encrypted deep neural network-based inference methods face the fundamental challenge of optimizing computational depth and complexity to achieve an acceptable trade-off between accuracy and practical feasibility. Existing works only report high level implementations without providing rigorous analysis of the intricacies involved in the FHE implementation of generic primitive operators of a convolutional neural network (CNN). In this paper, we use the CKKS encryption scheme available in the open-source HElib library to run encrypted inference experiments on the MNIST dataset. The experiments indicate that efficient ciphertext packing schemes, model optimization and multi-threading strategies play a critical role in determining the throughput and latency of the inference process. We also show that operational parameters of the chosen FHE scheme such as the degree of the cyclotomic polynomial, depth limitations of the underlying leveled HE scheme, and the computational precision parameters result in significant trade-offs between accuracy, security level and computational time of the machine learning model. The key contribution of the paper is the analysis and recommendation of optimization techniques for efficient encrypted CNN inference. © 2021 IEEE.