mRSA Signatures.

A user generates a signature on a message m as follows:

• 1. The user U_i first sends a hash of the message m to the appropriate SEM.
  • - SEM checks that U_i is not revoked and, if so, computes a partial signature $PS_{sem}=m^{d_i^{sem}} (\bmod n_i)$ and replies with it to the user. This PS_sem is the token enabling signature generation.
  • - concurrently, U_i computes $PS_u=m^{d_i^u} \;(\bmod n_i)$
• 2. U_i receives PS_sem and computes $m'=(PS_{sem}*PS_u)^{e_i} \;(\bmod n_i)$. If m'=m, the signature is set to: $(PS_{sem}*PS_u)=m^{d_i} \pmod{n_i}$.

Note that in Step 2 the user U_i validates the response from the SEM. Signature verification is identical to that in standard RSA.