Communication-Efficient Private Protocols for Longest Common Subsequence

Matthew Franklin; Mark Gondree; Payman Mohassel

Paper 2009/019

Communication-Efficient Private Protocols for Longest Common Subsequence

Matthew Franklin, Mark Gondree, and Payman Mohassel

Abstract

We design communication efficient two-party and multi-party protocols for the longest common subsequence (LCS) and related problems. Our protocols achieve privacy with respect to passive adversaries, under reasonable cryptographic assumptions. We benefit from the somewhat surprising interplay of an efficient block-retrieval PIR (Gentry-Ramzan, ICALP 2005) with the classic “four Russians” algorithmic design. This result is the first improvement to the communication complexity for this application over generic results (such as Yao’s garbled circuit protocol) and, as such, is interesting as a contribution to the theory of communication efficiency for secure two-party and multiparty applications.

Note: revision to fix typos from copy-paste in title and abstract

Metadata

Available format(s): PDF
Category: Applications
Publication info: Published elsewhere. This is the full version of an article to appear in CT-RSA 2009.
Keywords: longest common subsequence secure multiparty computation
Contact author(s): pmohassel @ ucdavis edu
History: 2009-01-13: last of 2 revisions; 2009-01-13: received; See all versions
Short URL: https://ia.cr/2009/019
License: CC BY

BibTeX

@misc{cryptoeprint:2009/019,
      author = {Matthew Franklin and Mark Gondree and Payman Mohassel},
      title = {Communication-Efficient Private Protocols for Longest Common Subsequence},
      howpublished = {Cryptology {ePrint} Archive, Paper 2009/019},
      year = {2009},
      url = {https://eprint.iacr.org/2009/019}
}