An Efficient Small Modulus Test and Its Applications to Delegated Computation Without Preprocessing

Delegation of operations used in cryptographic schemes from a computationally weaker client to a computationally stronger server has been advocated to expand the applicability of cryptosystems to computing with resource-constrained devices. Classical results for the verification of integer and polynomial products are based on a test due to Pippenger, Yao and Kaminski which verifies these operations modulo a small prime. In this paper we describe and prove an efficient small integer modulus test and show its application to single-server delegated computation of operations of interest in cryptosystems. In particular, we show single-server delegated computation protocols, without any preprocessing, for the following operations: Our protocols satisfy result correctness, input privacy (unless the input is public), result security and client efficiency. Previous work satisfied only a subset of these properties, or required preprocessing, or satisfied lower client efficiency.