Show simple item record

AuthorBlanton, Marina
AuthorAtallah, Mikhail J.
AuthorFrikken, Keith B.
AuthorMalluhi, Qutaibah
Available date2024-07-17T07:14:52Z
Publication Date2012
Publication NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ResourceScopus
Identifierhttp://dx.doi.org/10.1007/978-3-642-33167-1_29
ISSN3029743
URIhttp://hdl.handle.net/10576/56780
AbstractWe 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.
SponsorPortions 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.
Languageen
PublisherSpringer
SubjectAlphabet size
Garbled circuits
Input string
Output sequences
Remote servers
Sequence comparisons
Public key cryptography
Security of data
Security systems
Outsourcing
TitleSecure and efficient outsourcing of sequence comparisons
TypeConference Paper
Pagination505-522
Volume Number7459 LNCS
dc.accessType Abstract Only


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record