Single-Server Batch Delegation of Variable-Input Pairings with Unbounded Client Lifetime

Pairings are important building blocks in many public-key cryptosystems. Delegation of a pairing computation e(A, B) from a computationally weaker client to a computationally stronger server has been advocated to expand the applicability of pairing-based cryptosystems to computing with resource-constrained devices. In this paper we investigate the problem of delegating a batch of pairings. State of the art solutions are only efficient for pairings of the type \(e(A_i,B)\) ; that is, where only one of the input components varies across the batch inputs. In this paper we solve the problem of efficiently delegating a batch of pairings of the type \(e(A_i,B_i)\) ; that is, where both input components vary across the batch inputs. We show solutions for all of the input scenarios where the \(A_i,B_i\) are public or need to remain private, and are available in the offline phase or in the online phase of the delegation protocol. Both our protocols and those in the best previous work are among the very few in the delegation literature to enjoy unlimited client lifetime (i.e., after the offline phase, the number of delegation protocols executable by the resource-constrained client is an arbitrary polynomial), which is desirable in practical applications of resource-constrained client devices. The main technical components underlying our solutions consist of new probabilistic tests simultaneously verifying multiple pairing computations, with time-efficient online verification runtime and space-efficient offline storage.