On-line/Off-line Threshold Proxy Re-Signatures

To improve the performance of threshold proxy re-signatures, the notion of on-line/off-line threshold proxy re-signatures is introduced. The bulk of re-signature computation can be done in the off-line phase before the message arrives. The results of this pre-computation are saved and then utilized in the on-line phase once a message to be re-signed is known. Based on any threshold proxy re-signature scheme and a threshold version of chameleon hash function, we present a generic on-line/off-line threshold proxy re-signature scheme that can convert any existing secure threshold proxy re-signature scheme into an on-line/off-line one. The on-line phase of our scheme is efficient: computing a re-signature share requires one round of communication, two modular additions and one modular multiplication. Our scheme is provably secure under the discrete logarithm assumption without random oracles. Moreover, our scheme can achieve robustness in the presence of n/3 malicious proxies.