Client-server trade-offs in secure computation

In the framework of secure computation based on threshold homomorphic cryptosystems, we consider scenarios in which a lightweight client device provides encrypted input to a secure computation to be performed on the server side. The computational power at the server side is assumed to be much higher than on the client side. We show how to trade-off work for the client against work for the server such that the total amount of work increases moderately. These client-server trade-offs are considered in detail for two applications: private biometrics and electronic voting.