Patent ID: 8368517
Filing Date: 2013-02-05
Classification: H04L,H04Q

Abstract:
1. A method of authentication between a first device and at least one second device, comprising the steps of: a) sending a first random number from said first device to said second device; said second device comprising at least one key; b) generating a second random number at said second device; c) computing a plurality of cryptographic values at said second device using a cryptographic function; each of said plurality of cryptographic values computed using said first random number, said second random number, and at least a portion of one of said at least one key of said second device as inputs; d) sending said second random number and said plurality of cryptographic values from said second device to said first device; said first device having access to a key database comprising said at least one key of said at least one second device; and e) identifying the validity of said second device at said first device from said second random number and said plurality of cryptographic values received from said second device; wherein said at least one key in said second device comprises a path key and a leaf key, said path key split into a plurality of parts, said plurality of cryptographic values computed independent of the others; said plurality of cryptographic values further comprising: i) a plurality of path cryptographic values computed using said first random number, said second random number and one of said plurality of parts of said path key of said second device as inputs; and ii) a leaf cryptographic value computed using said first random number, said second random number and said leaf key of said second device as inputs; wherein said at least one key in said key database is stored using a sparse tree data structure arranged in multiple levels having a root node at a top level and a plurality of leaf nodes at the lowest level; said root node connected to said plurality of leaf nodes via non-leaf nodes at levels between said top level and said lowest level; said root node and said non-leaf nodes further storing a set of at least one index number; said leaf key associated with said leaf node and said path key corresponding to a path that traverses said sparse tree from said top node to said leaf node; and said identifying step further comprising the steps of: