Hybrid signature scheme

Abstract

A signature scheme is provided in which a message is divided in to a first portion which is hidden and is recovered during verification, and a second portion which is visible and is required as input to the verification algorithm. A first signature component is generated by encrypting the first portion alone. An intermediate component is formed by combining the first component and the visible portion and cryptographically hashing them. A second signature component is then formed using the intermediate component and the signature comprises the first and second components with the visible portion. A verification of the signature combines a first component derived only from the hidden portion of the message with the visible portion and produces a hash of the combination. The computed hash is used together with publicly available information to generate a bit string corresponding to the hidden portion. If the required redundancy is present the signature is accepted and the message reconstructed from the recovered bit string and the visible portion.

1. A method of digitally signing a plaintext message exchanged between a pair of correspondents in a data transmission system, one of said pair of correspondents being the signer and having a private key a, said public key being available to the other of said pair of correspondents, said method comprising the steps of:
 subdividing said plaintext message into a first plaintext bit string H and a second plaintext bit string V; 
 computing a first signature component c as a function of said first plaintext bit string H wherein the plaintext bit string H is hidden in said first signature component c; 
 computing an intermediate signature component c′ as a function of said first signature component c and said second plaintext bit string V; 
 computing a second signature component s as a function of said intermediate signature component c′ and said private key a; and 
 forming a signature (s,c,V) containing said first signature component c, said second signature component s, and said second plaintext bit string V as discrete signature components; 
 wherein by during verification, said second plaintext bit string V is available from said signature (s,c,V) as an input to a verification protocol. 
 
   
   
     2. A method according to  claim 1  wherein redundancy in said first plaintext bit string H is compared to a predetermined level prior to computing said first signature component c. 
   
   
     3. A method according to  claim 2  wherein said redundancy is adjusted to exceed a predetermined level. 
   
   
     4. A method according to  claim 3  wherein data is added to said first plaintext bit string H to adjust said redundancy. 
   
   
     5. A method according to  claim 4  wherein an indicator is included in said first plaintext bit string H to indicate additional data. 
   
   
     6. A method according to  claim 1  wherein said second signature component s is generated by hashing said first signature component c and said second plaintext bit string V. 
   
   
     7. A method according to  claim 1  wherein said first signature component c is computed by applying a unction to said first plaintext bit string H and said first plaintext bit string H may be recovered from said first signature component c by applying a complementary function to said first signature component c. 
   
   
     8. A method according to  claim 7  wherein said function is encryption with an encryption key, a decryption key is computable from information available in said signature, and said complementary unction is decryption with said decryption key. 
   
   
     9. A method according to  claim 8 , wherein said encryption key is a short-term derived from a random integer used in the provision of said second signature component. 
   
   
     10. 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. 
 
   
   
     11. A method according to  claim 10  wherein said combining of said first component and said second plaintext bit string V includes hashing said first component and said second plaintext bit string V. 
   
   
     12. A method according to  claim 10  wherein said predetermined characteristic is the redundancy of said recovered first plaintext bit string H. 
   
   
     13. A method according to  claim 12  wherein said signature includes a third component derived from a combination of said first component and said second plaintext bit string V and said first plaintext bit string H is recovered utilising said third component. 
   
   
     14. 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.