Hybrid signature scheme

A method of verifying a plaintext message from a signature of a purported signer in a data transmission system, said plaintext message being subdivided into a first plaintext bit string H and a second plaintext bit string V, said signature formed as a set of discrete components, said signature containing a first component computed as a unction of said first plaintext bit string H whereby said bit string H is encrypted therein, and said second plaintext bit string V as a second component, said purported signer having a private key used in the computation of said signature and a corresponding public key available for use in verification, said method comprising the steps of:

• generating a value by combining said first component with said second plaintext bit string V;
• recovering said first plaintext bit string H from said value using publicly available information of the purported signer including said public key;
• examining said recovered first plaintext bit string H for a predetermined characteristic;
• and
• verifying said message if said predetermined characteristic is present.

A method for authenticating a communication between a first correspondent and a second correspondent in a data transmission system, said first correspondent having a private key a and a public key derived from the private key a, said public key being available to said second correspondent, said method comprising:

• said first correspondent subdividing a plaintext message into a first plaintext bit string H and a second plaintext bit string V;
• said first correspondent computing a first signature component c as a function of said first plaintext bits string H wherein the plaintext bit string is hidden in said first signature component c;
• said first correspondent computing an intermediate signature component c′ as a function of said first signature component c and said second plaintext bit string V;
• said first correspondent computing a second signature component s as a function of said intermediate signature component c′ and said private key a;
• said first correspondent forming a signature (s,c,V) containing said first signature component c, said second component s, and said second plaintext bit string V as discrete signature components;
• said first correspondent making available to said second correspondent, at least said first signature component c and said plaintext bit string V;
• said second correspondent generating a value by combining said first signature component c with said second plaintext bit string V;
• said second correspondent recovering said first plaintext bit string H from said value using publicly available information of said first correspondent including said public key;
• said second correspondent examining said recovered first plaintext bit string H for a predetermined characteristic;
• and
• said second correspondent verifying said message if said predetermined characteristic is present.