How Should We Solve Search Problems Privately? Export

@incollection{citeulike:2240521, abstract = {Secure multiparty computation allows a group of distrusting parties to jointly compute a (possibly randomized) function of their inputs. However, it is often the case that the parties executing a computation try to solve a search problem, where one input may have a multitude of correct answers – such as when the parties compute a shortest path in a graph or find a solution to a set of linear equations. Picking one output arbitrarily from the solution set has significant implications on the privacy of the algorithm. Beimel et al. [STOC 2006] gave a minimal definition for private computation of search problems with focus on proving impossibility result. In this work we aim for stronger definitions of privacy for search problems that provide reasonable privacy. We give two alternative definitions and discuss their privacy guarantees. We also supply algorithmic machinery for designing such protocols for a broad selection of search problems.}, author = {Beimel, Amos and Malkin, Tal and Nissim, Kobbi and Weinreb, Enav}, citeulike-article-id = {2240521}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/978-3-540-74143-5_3}, doi = {10.1007/978-3-540-74143-5_3}, journal = {Advances in Cryptology - CRYPTO 2007}, keywords = {private, search}, pages = {31--49}, posted-at = {2008-01-16 19:03:01}, priority = {2}, title = {How Should We Solve Search Problems Privately?}, url = {http://dx.doi.org/10.1007/978-3-540-74143-5_3}, year = {2007} }

TY - CHAP ID - citeulike:2240521 L3 - citeulike-article-id:2240521 N2 - Secure multiparty computation allows a group of distrusting parties to jointly compute a (possibly randomized) function of their inputs. However, it is often the case that the parties executing a computation try to solve a search problem, where one input may have a multitude of correct answers – such as when the parties compute a shortest path in a graph or find a solution to a set of linear equations. Picking one output arbitrarily from the solution set has significant implications on the privacy of the algorithm. Beimel et al. [STOC 2006] gave a minimal definition for private computation of search problems with focus on proving impossibility result. In this work we aim for stronger definitions of privacy for search problems that provide reasonable privacy. We give two alternative definitions and discuss their privacy guarantees. We also supply algorithmic machinery for designing such protocols for a broad selection of search problems. JF - Advances in Cryptology - CRYPTO 2007 EP - 49 TI - How Should We Solve Search Problems Privately? SP - 31 KW - private KW - search AU - Beimel, Amos AU - Malkin, Tal AU - Nissim, Kobbi AU - Weinreb, Enav PY - 2007/// UR - http://dx.doi.org/10.1007/978-3-540-74143-5_3 ER -