Secure and efficient outsourcing of sequence comparisons
Author | Blanton, Marina |
Author | Atallah, Mikhail J. |
Author | Frikken, Keith B. |
Author | Malluhi, Qutaibah |
Available date | 2024-07-17T07:14:52Z |
Publication Date | 2012 |
Publication Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
Resource | Scopus |
Identifier | http://dx.doi.org/10.1007/978-3-642-33167-1_29 |
ISSN | 3029743 |
Abstract | 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. |
Sponsor | Portions of this work were supported by NSF Grants CNS-0915436, CNS-0913875, CNS-0915843, and CCF-0939370; an NPRP grant from the Qatar National Research Fund; AFOSR Grant FA9550-09-1-0223; and sponsors of the CERIAS center. |
Language | en |
Publisher | Springer |
Subject | Alphabet size Garbled circuits Input string Output sequences Remote servers Sequence comparisons Public key cryptography Security of data Security systems Outsourcing |
Type | Conference Paper |
Pagination | 505-522 |
Volume Number | 7459 LNCS |
Files in this item
Files | Size | Format | View |
---|---|---|---|
There are no files associated with this item. |
This item appears in the following Collection(s)
-
Computer Science & Engineering [2284 items ]