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.
Category / Keywords: applications / private search, genomic computation, longest common subsequence Publication Info: Full version of a paper to appear at WPES 2009 Date: received 15 Aug 2009 Contact author: pmohasse at cpsc ucalgary ca Available format(s): PDF | BibTeX Citation Version: 20090817:121844 (All versions of this report) Short URL: ia.cr/2009/401