Advertisement
Published in:
2012 | OriginalPaper | Chapter
Secure and Efficient Outsourcing of Sequence Comparisons
Authors : Marina Blanton, Mikhail J. Atallah, Keith B. Frikken, Qutaibah Malluhi
Published in: Computer Security – ESORICS 2012
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We treat the problem of secure outsourcing of sequence comparisons by a client to remote servers, which given two strings
λ
and
μ
of respective lengths
n
and
m
, consists of finding a minimum-cost sequence of insertions, deletions, and substitutions (also called an
edit script
) that transform
λ
into
μ
. In our setting a client owns
λ
and
μ
and outsources the computation to two servers without revealing to them information about either the input strings or the output sequence. Our solution is non-interactive for the client (who only sends information about the inputs and receives the output) and the client’s work is linear in its input/output. The servers’ performance is
O
(
σmn
) computation (which is optimal) and communication, where
σ
is the alphabet size, and the solution is designed to work when the servers have only
O
(
σ
(
m
+
n
)) memory. By utilizing garbled circuit evaluation in a novel way, we completely avoid public-key cryptography, which makes our solution particularly efficient.