Proxy Re-Signatures: New Definitions, Algorithms, and Applications.

In 1998, Blaze, Bleumer, and Strauss (BBS) proposed proxy re-signatures, in which a semitrusted 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 Die-Hellman (CDH) assumption; here the proxy can translate from Alice to Bob and vice-versa. Our second scheme relies on the CDH and 2Discrete 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 ecient and secure in the random oracle model.