Abstract: To improve the performance of proxy re-signature schemes, the schemes of on-line/off-line proxy re-signature are proposed in this paper. The main idea is to split the re-signing procedure into two phases: the off-line and on-line phases. Most of the computations are performed in the off-line phase before seeing the message to be re-signed. The results of this precomputation are saved and then used in the on-line phase when the message must be re-signed. On-line/off-line proxy re-signature schemes are used in a particular scenario where the proxy must respond quickly once the message to be re-signed is presented. Based on the formal definition of on-line/off-line proxy re-signatures, an efficient construction of on-line/off-line proxy re-signature is presented. It can convert any proxy re-signature scheme into a highly efficient on-line/off-line one. Security is proved in the random oracle model. Compared wirh the existing proxy re-signature schemes, the new scheme is more efficient in the communication cost and the computational cost. It needs one modular subtraction computation and one modular multiplication computation in the on-line re-signing generation algorithm.