Message recovery for signature schemes based on the discrete logarithm problem (Q1910422)

Digital signature schemes based on the discrete logarithm problem, like NIST's DSA, compared with the well known RSA signature scheme do not offer message recovery functionality, i.e. in their straightforward use the message cannot be conveyed within the signature and recovered at the verifier's site. The paper presents a general technique to modify all previously presented signature schemes based on the discrete logarithm problem to allow message recovery functionality. Also it is shown that some of the new signature schemes can be naturally combined with ElGamal encryption scheme thus together giving the same functionality as RSA does. However, there is a subtle difference as the signature and recovery transformations of the new systems do not commute, so they cannot be directly used as encryption algorithms in the same way as RSA. On the other hand such systems offer a clear separation of confidentiality and authentication functions.