Proxy re-signatures: New definitions, algorithms, and applications

In 1998, Blaze, Bleumer, and Strauss (BBS) proposed proxy re-signatures, in which a semi-trusted proxy acts as a translator between Alice and Bob. To translate, the proxy converts a signature from Alice into a signature from Bob on the same message. The proxy, however, does not learn any signing key and cannot sign arbitrary messages on behalf of either Alice or Bob. Since the BBS proposal, the proxy re-signature primitive has been largely ignored, but we show that it is a very useful tool for sharing web certificates, forming weak group signatures, and authenticating a network path. We begin our results by formalizing the definition of security for a proxy re-signature. We next substantiate the need for improved schemes by pointing out certain weaknesses of the original BBS proxy re-signature scheme which make it unfit for most practical applications. We then present two secure proxy re-signature schemes based on bilinear maps. Our first scheme relies on the Computational Diffie-Hellman (CDH) assumption; here the proxy can translate from Alice to Bob and vice-versa. Our second scheme relies on the CDH and 2-Discrete Logarithm (2-DL) assumptions and achieves a stronger security guarantee - the proxy is only able to translate in one direction. Constructing such a scheme has been an open problem since proposed by BBS in 1998. Furthermore in this second scheme, even if the delegator and the proxy collude, they cannot sign on behalf of the delegatee. Both schemes are efficient and secure in the random oracle model.