Patent ID: 8316417
Filing Date: 2012-11-20
Classification: G06F

Abstract:
1. Method for a dynamic management of an authenticated relational table forming part of a database; the method comprising: providing a primary memory; storing the authenticated relational table in a secondary memory with a storage capacity that is higher than the storage capacity of the primary memory and a data access time that is slower than the data access time of the primary memory; maintaining an authenticated skip list within the authenticated relational table in order to create an authentication superstructure; determining a signed hash or basis value which characterizes the entire authenticated relational table; authenticating the presence or otherwise of a set (S) of elements stored in an authenticated table (TA) comprising a hash tree (T) belonging to the skip list via a root path suitable for calculating a verification hash value comparable to the signed hash value which characterizes the entire authenticated relational table, wherein when verifying whether an element is present in a skip list, if the data item is present, a calculation is made that calculates a root path from an element found at a lowest level of the skip list that arrives at a root on the extreme left at a highest level of the skip list, the authenticated table (TA) for the set (S) further comprising a joint signature of a time marker and a value (f(r)) kept in a root (r) of the hash tree (T), wherein an element (x) belongs to the set (S) if it can be verified by control of a sequence of values stored in elements adjoining nodes of the path from the element (x) to the root (r), wherein the validation process recalculates the root label via hashing of labels in the sequence in an appropriate order; validating the result of the authentication step by checking that the verification hash value calculated by means of the root path is equal to the signed hash value that characterizes the entire authenticated relational table; maintaining, via the dynamic management, the authenticated relational table in the secondary memory, wherein the dynamic management permits frequent insertions and deletions in the authenticated relational table while maintaining a hierarchical order; defining a logarithmic subset of the records present in the authenticated relational table which contains the records necessary for reconstruction of the root path; loading, by means of appropriate queries to the authentication table permitting efficient selection only of the elements necessary for authentication, the logarithmic subset of the records necessary for reconstruction of the root path in the primary memory; and establishing an element to be authenticated and then reducing the number of queries to be made for loading the logarithmic subset using a “funnel” technique according to which, from the secondary memory to the primary memory all the following elements are loaded: elements located within the interval between two towers of the skip list which include the element to be authenticated; elements located on the lower level of the skip list with respect to the level of the element to be authenticated; and elements located on the maximum level of the skip list and having a value lower than the element to be authenticated.