TY - JOUR
T1 - Efficient verification of webcontent searching through authenticated web crawlers
AU - Goodrich, Michael T.
AU - Nguyen, Duy
AU - Ohrimenko, Olga
AU - Papamanthou, Charalampos
AU - Tamassia, Roberto
AU - Triandopoulos, Nikos
AU - Lopes, Cristina Videira
PY - 2012/6
Y1 - 2012/6
N2 - We consider the problem of verifying the correctness and completeness of the result of a keyword search. We introduce the concept of an authenticated web crawler and present its design and prototype implementation. An authenticated web crawler is a trusted program that computes a specially-crafted signature over the web contents it visits. This signa-ture enables (i) the verication of common Internet queries on web pages, such as conjunctive keyword searches|this guarantees that the output of a conjunctive keyword search is correct and complete; (ii) the verication of the content returned by such Internet queries|this guarantees that web data is authentic and has not been maliciously altered since the computation of the signature by the crawler. In our solu-tion, the search engine returns a cryptographic proof of the query result. Both the proof size and the verication time are proportional only to the sizes of the query description and the query result, but do not depend on the number or sizes of the web pages over which the search is performed. As we experimentally demonstrate, the prototype implementa-tion of our system provides a low communication overhead between the search engine and the user, and fast verication of the returned results by the user.
AB - We consider the problem of verifying the correctness and completeness of the result of a keyword search. We introduce the concept of an authenticated web crawler and present its design and prototype implementation. An authenticated web crawler is a trusted program that computes a specially-crafted signature over the web contents it visits. This signa-ture enables (i) the verication of common Internet queries on web pages, such as conjunctive keyword searches|this guarantees that the output of a conjunctive keyword search is correct and complete; (ii) the verication of the content returned by such Internet queries|this guarantees that web data is authentic and has not been maliciously altered since the computation of the signature by the crawler. In our solu-tion, the search engine returns a cryptographic proof of the query result. Both the proof size and the verication time are proportional only to the sizes of the query description and the query result, but do not depend on the number or sizes of the web pages over which the search is performed. As we experimentally demonstrate, the prototype implementa-tion of our system provides a low communication overhead between the search engine and the user, and fast verication of the returned results by the user.
UR - http://www.scopus.com/inward/record.url?scp=84873161865&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84873161865&partnerID=8YFLogxK
U2 - 10.14778/2336664.2336666
DO - 10.14778/2336664.2336666
M3 - Article
AN - SCOPUS:84873161865
VL - 5
SP - 920
EP - 931
JO - Proceedings of the VLDB Endowment
JF - Proceedings of the VLDB Endowment
IS - 10
ER -