Delegating a Pairing Can Be Both Secure and Efficient
S. Canard, J. Devigne, and O. Sanders.
Abstract:

Bilinear pairings have been widely used in cryptographic protocols since they provide very interesting functionalities in regard of identity based cryptography, short signatures or cryptographic tools with complex properties. Unfortunately their implementation on limited devices remains complex and even if a lot of work has been done on the subject, the current results in terms of computational complexity may still be prohibitive. This is clearly not for today to find the implementation of a bilinear pairing in every smart card. One possibility to avoid this problem of efficiency is to delegate the pairing computation to a third party. The result should clearly be both secure and efficient. Regarding security, the resulting computation of a pairing $e(A,B)$ by the third party should be verifiable by the smart card. Moreover, if the points $A$ and/or $B$ are secret at the beginning of the protocol, they should also be secret after its execution. Regarding efficiency, besides some specific cases, existing protocols for delegating a pairing are costlier than a true embedded computation inside the smart card. This is due to the fact that they require several exponentiations to check the validity of the result. In this paper we first propose a formal security model for the delegation of pairings that fixes some weakness of the previous models. We also provide efficient ways to delegate the computation of a pairing $e(A,B)$, depending on the status of $A$ and $B$. Our protocols enable the limited device to verify the value received from the third party with mostly one exponentiation and can be improved to also ensure secrecy of $e(A,B)$.