Classifying encrypted images
Very briefly, homomorphic encryption as used by the linked paper in the question works as follows (excuse ad-hoc notation). Define an encryption method $E(x,k)$ that takes some data $x$ and secret key $k$ that has the following properties:


There is a decryption method $D( E(x,k), k ) = x$ (optionally the two $k$ here can be different)
You can define operations that work on the encrypted data in a self-consistent manner, e.g. $\text{Add}_E(E(x,k),E(y,k)) = E(x+y,k)$ - note that the result is still encrypted, and you need to know $k$ in order to use method $D()$ and find out what $x+y$ is.
You may also need to support operations like $\text{Add}_E(E(x,k),y) = E(x+y,k)$ e.g. where one of the values is normal numeric variable - this might be useful for initialising a model - or using an existing trained model - but the catch is that when training you cannot keep these values unencrypted, once they use updated due to training results, they will also be encrypted.
Note that no operation can output a decrypted value without using the key, otherwise the whole scheme is insecure, it implies some backdoor to get decrypted data.
For ML use, you need an encryption scheme E that supports multiple basic operations, e.g. $\text{Add}_E$, $\text{Subtract}_E$, $\text{Multiply}_E$, $\text{GreaterThan}_E$ etc. You need some minimal set that is enough to build a model.


You can then build variant models that instead of performing arithmetic to sum/multiply etc numeric values, work with the abstract operations on encrypted data. The models would otherwise look just like their unencrypted counterparts - e.g. you could quickly build a linear regression using only a few types of operation.

Given that you are replacing simple fast floating point add, multiply operations that are built into the processor with a more complex custom operation, this significantly affects performance compared to the unencrypted model. How much so depends on the encryption scheme, and how it is implemented. The paper shows in section 5, timings on unencrypted vs encrypted data and the difference is several orders of magnitude slower when encrypted.

The paper was published in 2012, so it is possible that some improvements have been made here. However, on a deeper read of the subject I think that this is still at the stage of research proof-of-concept. I might be wrong, and there are nice workable implementations available that could be used in something as complex as a CNN, but I have not found anything.

You also linked numer.ai from comments. Initially that looked interesting because surely they would have solved efficiency problems. But in fact their main competitions are using data obfuscation techniques, not encryption - a homomorphic encryption paper is linked from their main site, but it does not seem to be what they are using. End users are writing very familiar-looking scripts that perform logistic regression etc using regular Python (no special operators imported)

I think you should take a second look at your wider problem and analyse your threat model. What precisely are you trying to protect against? If it is about keeping your own operations separate from client data, then you might be looking into company process and auditing solutions, rather than purely technical (you may still want to add technical solutions such as disk-level encryption to protect customer's data at rest in you data centre, in case someone gets into the centre physically and just grabs a disk containing all the cat images) 

For instance, look at Cloud Security Alliance which as well as having a certification scheme, has analysis showing how their recommendations map to other schemes such as UK's ISO27001. Note that this is typically significant capital investment including 1+ year project to implement, and usually undertaken by mid-sized or larger companies, when they want to work with government or large corporate's data. However, it is probably a more reliable and maybe still cheaper route than trying to research and build a technical solution involving models that process encrypted data at this time.