Patent ID: 9152716
Filing Date: 2015-10-06
Classification: G06F

Abstract:
1. A method comprising, by a crawler application running on a computing device connected to a network, the method comprising: crawling through a distributed collection of data sets available on the network, at least one data set of the distributed collection being published by an entity distinct and under separate control from the crawler, to generate a search structure indexing a plurality of searchable data items found within the distributed collection of data sets, the search structure establishing a correspondence between each searchable data item and particular data sets that contain that searchable data item; generating an authenticated search structure, the authenticated search structure including the search structure and a set of item witnesses using an authentication primitive associated with a set of security parameters, each item witness associated with a particular searchable data item and serving to cryptographically verify which data sets of the distributed collection of data sets correspond to that searchable data item as indicated by the search structure; building a digest of the distributed collection of data sets using the authenticated search structure; signing the digest to produce a digest signature; sending the authenticated search structure and the digest to a search server; and publishing the digest signature and the set of security parameters for access by client devices to allow client devices to authenticate results of searches for particular searchable data items performed by the search server over the distributed collection of data sets; wherein: the crawler application is a web crawler; the data sets are hyperlinked web pages; the searchable data items are searchable terms that appear within the distributed collection of hyperlinked web pages; the item witnesses are term witnesses, each term witness serving to cryptographically verify that a particular sub-collection of the distributed collection of hyperlinked web pages all contain a searchable term associated with that term witness; building the digest of the distributed collection of data sets includes building a Merkle hash tree over the set of term witnesses, the Merkle hash tree having a root node; signing the digest to produce the digest signature includes signing the root node of the Merkle hash tree; the set of security parameters includes: generating the term witnesses includes, using a secret key, s, sεZ the particular hyperlinked web pages that contain each searchable term define a term set for that searchable term, that term set having n elements, t calculating the associated term witness for each searchable term by raising g to the power of the product of multiplicands includes raising g to the power of Π the method further comprises, by the web crawler: