4. The method of claim 1 , wherein the method further comprises, by the client device: (a) sending the conjunctive term web search request to the search server; (b) receiving the set of search results, the term witness associated with each search term, the Merkle proof for each search term, the subset witness for each search term, and the set of completeness witnesses from the search server in response to the received conjunctive term web search request; (c) verifying, for each search term, that its associated term witness and Merkle proof are consistent with the published tree signature; (d) verifying, with reference to the published set of security parameters and the published set of generator powers, for each search term, with reference to the term witness associated with that search term and the subset witness for that search term, that the set of search results is a subset of the term set for that term; (e) verifying, with reference to the published set of security parameters, the subset witness for all of the search terms, and the completeness witness for all of the search terms, that an intersection of the complementary term sets for all of the search terms is null; and (f) in response to verifying (c), (d), and (e), validating that the set of search results is complete and correct.
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: a prime integer order, p; a generator element, g; a first cyclic multiplicative group, G, of order, p, G being generated by g; a second cyclic multiplicative group, G′, of order, p; and a non-degenerate bilinear pairing, e, e mapping G×G→G′; generating the term witnesses includes, using a secret key, s, sεZ p *, for each searchable term, calculating the associated term witness by raising g to the power of a product of multiplicands, each multiplicand being an injective function of s and an identifier of a hyperlinked web page corresponding to that searchable term, for each hyperlinked web page corresponding to that searchable term; 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 i , for i=1 through i=n; 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 Π i=1 i=n (s+t i ); the method further comprises, by the web crawler: for all integers, x, from 1 to a maximum size, m, of the term set for any searchable term, computing a set of generator powers, {g^(s x )}, the set of generator powers having m elements; and publishing the set of generator powers for access by client devices; and the method further comprises, by the search server: receiving a conjunctive term web search request from a client device, the conjunctive term web search request including a plurality of search terms; in response to receiving the request, generating a set of search results by performing a set intersection operation between the term sets for each search term of the conjunctive term web search request; for each search term: generating a Merkle proof for the term witness associated with that search term, the Merkle proof including sibling node values along a path within the Merkle hash tree from a leaf corresponding to that term witness to the root node; and generating a subset witness for that search term with reference to a complementary term set associated with that search term, the complementary term set associated with that search term having p elements, t′ j , for j=1 through j=p, such that that complementary term set is the relative complement of the set of search results in the term set defined by that search term, the subset witness equal to g raised to the power of ∏ j = 1 j = p ⁢ ⁢ ( s + t j ′ ) , the subset witness being calculated by expanding a mathematical representation of ∏ j = 1 j = p ⁢ ⁢ ( s + t j ′ ) , into a set of polynomial terms of powers of s, calculating a value of g raised to the power of each polynomial term of the set of polynomial terms of powers of s with reference to the set of generator powers, and multiplying the calculated values together; generating, using an extended Euclidian algorithm, a set of completeness witnesses, each completeness witness of the set of completeness witnesses having a greatest common divisor of 1 with the subset witnesses for all of the search terms; and sending the set of search results, the term witness associated with each search term, the Merkle proof for each search term, the subset witness for each search term, and the set of completeness witnesses to the client device in response to the received conjunctive term web search request.