Method for authentication item
First Claim
1. A computer-readable memory containing an authenticated search tree that is useful in a computer system for authenticating membership or non-membership of items in a set, the authenticated search tree comprising:
- a search tree having nodes and leaves and having associated therewith a search scheme, each node including dynamic search values which collectively define the search path from the root to a leaf, and the leaves including items of said set, each node being associated with a cryptographic hash function value that is produced by applying a cryptographic hash function to at least the cryptographic hash values of the children nodes;
at least the root node of said authenticated search tree having been authenticated by a digital signature.
1 Assignment
0 Petitions
Accused Products
Abstract
A memory containing an authenticated search tree that serves for authenticating membership or non membership of items in a set. The authenticated search tree including a search tree having nodes and leaves and being associated with a search scheme. The nodes including dynamic search values and the leaves including items of the set. The nodes are associated, each, with a cryptographic hash function value that is produced by applying a cryptographic hash function to the cryptographic hash values of the children nodes and to the dynamic search value of the node. The root node of the authenticated search tree is authenticated by a digital signature.
117 Citations
11 Claims
-
1. A computer-readable memory containing an authenticated search tree that is useful in a computer system for authenticating membership or non-membership of items in a set, the authenticated search tree comprising:
-
a search tree having nodes and leaves and having associated therewith a search scheme, each node including dynamic search values which collectively define the search path from the root to a leaf, and the leaves including items of said set, each node being associated with a cryptographic hash function value that is produced by applying a cryptographic hash function to at least the cryptographic hash values of the children nodes;
at least the root node of said authenticated search tree having been authenticated by a digital signature. - View Dependent Claims (2, 3, 4, 11)
-
-
5. A method for authenticating membership or non-membership in a set of an item, comprising:
-
(i) providing an authenticated search tree having nodes and leaves and having associated therewith a search scheme, each node including dynamic search values which collectively define the search path from the root to the leaf, and the leaves including items of the set, each node being associated with a cryptographic hash function value that is produced by applying a cryptographic hash function to (I) the cryptographic hash values of children nodes and, optionally, (II) the dynamic search value of the node, and wherein at least the root node of said authenticated search tree is authenticated by a digital signature; and
(ii) authenticating the membership or non-membership in the set of the item by computing one or more authentication paths as induced by the item and the root. - View Dependent Claims (7)
(a) the user providing to a directory a list of at least one item for authenticating membership or non-membership in a set of said at least one item;
(b) the directory computing and transmitting to a user the authentication path(s) as induced by said at least one item, the directory further transmitting said authenticated root; and
(c) the user verifying said items.
-
-
6. A method for updating at least one item of a set in an authenticated search tree, comprising:
-
(i) providing an authenticated search tree having nodes and leaves and having associated therewith a search scheme, each node including dynamic search values which collectively define the search path from the root to a leaf, and the leaves including items of the set, each node being associated with a cryptographic hash function value that is produced by applying a cryptographic hash function to (I) the cryptographic hash values of children nodes and, optionally, (II) the dynamic search value of the node, and wherein at least the root node of said authenticated search tree is authenticated by a digital signature;
(ii) updating said search tree so as to obtain updated nodes;
(iii) computing authentication path(s) as induced by said updated nodes; and
(iv) authenticating at least said root modified node by the digital signature. - View Dependent Claims (8, 9)
the CA executing;
(i) updating said search tree so as to obtain updated nodes;
(ii) computing an authentication path(s) as induced by said updated nodes; and
(iii) authenticating at least said root modified node by the digital signature; and
(iv) transmitting modified parameters to said directory;
the directory executing;
(a) applying said modification parameters, so as to obtain an authenticated directory root value; and
(b) verifying that the authenticated CA root value matches the authenticated directory root value.
-
-
9. A method according to claim 6, in a CA-user scheme including a plurality of users, comprising:
-
the CA executing;
(i) updating said search tree so as to obtain updated nodes;
(ii) computing an authentication path(s) as induced by said updated nodes, said authentication path(s) induced by said updated nodes comprising an induced sub-tree; and
(iii) authenticating at least said root modified node by the digital signature; and
(iv) publishing the induced sub-tree, the user executing;
(a) obtaining the published induced sub-tree;
(b) intersecting said induced sub-tree with user self-path ad obtaining the values of the nodes in said sub-tree necessary to authenticate the user self path;
(c) computing a user authenticated root value; and
(d) verifying that the authenticated CA root value matches the authenticated user value.
-
-
10. A method of authenticating non-membership in a set of an item having a specified value, comprising:
-
(i) providing an authenticated search tree having nodes and leaves having associated therewith a search scheme, each node including dynamic search values which collectively define the search path from the root to a leaf, and the leaves including items of the set, each node being associated with a cryptographic hash function value that is produced by applying a cryptographic hash function to (I) the cryptographic hash values of children nodes and, optionally, (II) the dynamic search value of the node, and wherein at least the root node of said authenticated search tree is authenticated by a digital signature; and
(ii) authenticating non-membership in the set by receiving authenticated path(s) authenticating the values of two adjacent leaves and determining that the value of said item is between the values of the two adjacent leaves.
-
Specification