Longest Common Subsequence as Private Search
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.
Description
This is the full version of an article [24] to appear in WPES’09.
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.Collections
Related items
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 ... -
Drone Technology: Implementation obstacles in Homeland Security and Private Sector applications [video]
Center for Homeland Defense and Security Naval Postgraduate School (2016-02);Technologies for unmanned aircraft, or drones, are exploding both in the private and public sectors. Each day, new applications for law enforcement, rescue and recovery, and other uses in Homeland Security are being developed ...