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.
5. The method of claim 4 , wherein: the set of search results can be injectively mapped to a result set over Z p *, the result set having q elements, t″ k , for k=1 to k=q; the method further comprises, at the search server: calculating coefficients of a polynomial expansion of P(s)=Π k=1 k=q (s+t″ k ), yielding q+1 result coefficients, b r ; and sending the q+1 result coefficients from the search server to the client device; and at the client device, verifying (d) includes: verifying that, for a randomly-selected value wεZ p *, Σ r=0 r=q b r w r =Π k=1 k=q (w+t″ k ); and for each search term, verifying that applying the non-degenerate bilinear pairing, e, to the subset witness for that search term and a product of, for all r=0 to r=q, an r-th generator power of the set of generator powers raised to the power of b r , is equivalent to applying the non-degenerate bilinear pairing, e, to g and the term witness for that search term, the r-th generator power corresponding to g^(s r ).