Inference of machine learning models with data privacy guarantees has been widely studied as privacy concerns are getting growing attention from the community. Among others, secure inference based on Fully Homomorphic Encryption (FHE) has proven its utility by providing stringent data privacy at sometimes affordable cost. Still, previous work was restricted to shallow and narrow neural networks and simple tasks due to the high computational cost incurred from FHE. In this paper, we propose a more efficient way of evaluating convolutions with FHE, where the cost remains constant regardless of the kernel size, resulting in 12–46× timing improvement on various kernel sizes. Combining our methods with FHE bootstrapping, we achieve at least 18.9% (and 48.1%) timing reduction in homomorphic evaluation of 20-layer CNN classifiers (and a part of it) on CIFAR10/100 (and ImageNet, respectively) datasets. Furthermore, in consideration of our methods being effective for evaluating CNNs with intensive convolutional operations and exploring such CNNs, we achieve at least 5× faster inference on CIFAR10/100 with FHE than the prior works having the same or less accuracy.