Longest Common Subsequence as Private Search
Loading...
Authors
Gondree, Mark
Mohassel, Payman
Subjects
Advisors
Date of Issue
2009
Date
Publisher
Language
Abstract
At STOC 2006 and CRYPTO 2007, Beimel et al. introduced a set of privacy requirements for
algorithms that solve search problems. In this paper, we consider the longest common subsequence
(LCS) problem as a private search problem, where the task is to find a string of (or embedding
corresponding to) an LCS. We show that deterministic selection strategies do not meet the privacy
guarantees considered for private search problems and, in fact, may “leak” an amount of information
proportional to the entire input.
We then put forth and investigate several privacy structures for the LCS problem and design
new and efficient output sampling and equivalence protecting algorithms that provably meet the
corresponding privacy notions. Along the way, we also provide output sampling and equivalence
protecting algorithms for finite regular languages, which may be of independent interest.
Type
Article
Description
This is the full version of an article [24] to appear in WPES’09.
Series/Report No
Department
Computer Science (CS)
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.