1. A method of generating a certificate in a cryptographic data communication system, said method comprising: determining, for a first set of information sufficient to permit verification of a signature, additional information supplementary to that of said first set of information, said additional information facilitating the computation of at least one intermediate step involved in the performance of said verification; incorporating said additional information in a certificate associated with said signature to be verified by a recipient; and making said certificate available to said recipient to thereby provide said additional information to facilitate verification of said signature, wherein said additional information is to be used in at least one intermediate step involved in the performance of said verification.