Longest Common Subsequence as Private Search
MetadataShow full item record
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.
This is the full version of an article  to appear in WPES’09.
Showing items related by title, author, creator and subject.
Analysis of the United States Computer Emergency Readiness Team's (U.S. CERT) Einstein III intrusion detection system, and its impact on privacy Oree, William L. (Monterey, California. Naval Postgraduate School, 2013-03);To secure information technology and telecommunications systems, the U.S Department of Homeland Security created the United States Computer Emergency Readiness Team (U.S. CERT) to provide 24-hour early warning and detection ...
Fabricating synthetic data in support of training for domestic terrorist activity data mining research Lavelle, Stephen J. (Monterey, California. Naval Postgraduate School, 2010-09);Data mining is a mature technology, widespread in both government and industry. The proliferation of data storage in public and private sectors has provided more information than can be expediently processed. Data mining ...
Ringing the bell; sounding the alarm a proposal for the simultaneous advancement of security and privacy Novak, Kneilan K. (Monterey California. Naval Postgraduate School, 2006-03);The need for domestic intelligence and information sharing to detect indications and warnings of terrorist acts and prevent them has raised privacy and civil liberties concerns. The relationship between national security ...