Private Web Search with Constant Round Efficiency

Bolam Kang, Sung Cheol Goh, Myungsun Kim

2015

Abstract

Web searches are increasingly becoming essential activites because they are often the most effective and convenient way of finding information. However, a web search can be a threat to the privacy of users because their queries may reveal sensitive information. Private web search (PWS) solutions allow users to find information on the Internet while preserving their privacy. According to their underlying technology, existing PWS solutions can be divided into three types: Proxy-based solutions, Obfuscation-based solutions, and Cryptography-based solutions. Among them, cryptography-based PWS (CB-PWS) systems are particularly interesting because they provide strong privacy guarantees. In this paper, we present a constant-round CB-PWS protocol that preserves computational efficiency compared to known CB-PWS systems. To prove these arguments, we first analyze the efficiency of our protocol. According to our analysis, our protocol simply requires 3n modular exponentiations for n users. In particular, our protocol is a 5-round protocol that requires O(n) communication complexity. In addition, evaluating the security of our protocol shows that our construction is comparable to similar solutions in terms of user privacy.

Paper Citation

in Harvard Style

Kang B., Goh S. and Kim M. (2015). Private Web Search with Constant Round Efficiency . In Proceedings of the 1st International Conference on Information Systems Security and Privacy - Volume 1: ICISSP, ISBN 978-989-758-081-9, pages 205-212. DOI: 10.5220/0005225602050212

in Bibtex Style

@conference{icissp15,
author={Bolam Kang and Sung Cheol Goh and Myungsun Kim},
title={Private Web Search with Constant Round Efficiency},
booktitle={Proceedings of the 1st International Conference on Information Systems Security and Privacy - Volume 1: ICISSP,},
year={2015},
pages={205-212},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0005225602050212},
isbn={978-989-758-081-9},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 1st International Conference on Information Systems Security and Privacy - Volume 1: ICISSP,
TI - Private Web Search with Constant Round Efficiency
SN - 978-989-758-081-9
AU - Kang B.
AU - Goh S.
AU - Kim M.
PY - 2015
SP - 205
EP - 212
DO - 10.5220/0005225602050212