Patent ID: 8452969

Claim:
A method for authenticating a message that is transmitted wirelessly, said method comprising: providing a matrix that includes rows of private key values and columns of private key values; performing a key pair generation process that provides a key pair including a private key and a public key for each row in the matrix, said private key being the set of private key values for that row, wherein performing the key pair generation process includes applying a plurality of hash functions to the private key values where a succeeding hash function provides a hash of a previous hash function, wherein a concatenated value of the final hash values is the public key; performing a signature generation process, using a microprocessor, that includes generating a message digest by applying a hash function on the message to be signed and separating the message digest into two parts including signing bits and selection bits where the selection bits select which row in the matrix will be used to sign the message and the signing bits are signed by a signing algorithm using the private key values from the selected row, and where performing the signature generation process uses the algorithm: Input: hash function H: {0,1}*→{0,1} L , block parameter n,n 1 ,k and j, message M, signature key S Output: One time signature σ M on M 1: Compute H(M) from M 2: Break H(M) in ‘n’, k-bit words and ‘n’j bit words 3: ‘n’ n 1 k-bits words are used for signing. They are denoted as b 1 1 ,b 2 1 , . . . ,b n 1 1 ,b 1 2 ,b 2 2 , . . . ,b n 1 2 , . . . ,b 1 n ,b 2 n , . . . ,b n 1 n 4:‘n’j bit words represent n indices in {1:2 j } are used for selection, They are denoted as m 1 , m 2 , . . . , m n 5: Compute b 0 i =Σ l-1 n 1 b l i for each i ε{1:n } 6: For each m i sign (b 0 i ,b 1 i , . . . ,b n 1 i )use Winternitz signature to generate σ m i 7: The signature of M is σ M =[σ m i ∥σ m i ∥. . . ∥σ m n ] 8: return σ M ; and performing a signature authentication process that includes using the key pair to authenticate the message.