Paper 2009/401

Longest Common Subsequence as Private Search

Mark Gondree and Payman Mohassel

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.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. Full version of a paper to appear at WPES 2009
Keywords
private searchgenomic computationlongest common subsequence
Contact author(s)
pmohasse @ cpsc ucalgary ca
History
2009-08-17: received
Short URL
https://ia.cr/2009/401
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/401,
      author = {Mark Gondree and Payman Mohassel},
      title = {Longest Common Subsequence as Private Search},
      howpublished = {Cryptology {ePrint} Archive, Paper 2009/401},
      year = {2009},
      url = {https://eprint.iacr.org/2009/401}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.