Non ci sono prove che FHE non possa essere implementata in modo efficiente. È solo che, proprio ora, non sappiamo come farlo. Con algoritmi attualmente noti (l'algoritmo di Gentry, con alcune ottimizzazioni conosciute), sarebbe estremamente lento, il che significa poco pratico (e abbastanza lontano nel regno "poco pratico", in realtà). La FHE dovrebbe diventare migliaia di volte più veloce di quello che si può fare oggi, al fine di ottenere un qualche tipo di praticità generica.
Naturalmente, ci sono alcune applicazioni specifiche che possono già fare uso, in modo molto pratico, della crittografia omomorfica. In genere, i sistemi di voto, come Helios Voting - non hanno bisogno della crittografia omomorfica completamente e possono funzionare con un ElGamal semplice, efficiente, parzialmente omomorfico.