Abstrakt. Storskaliga problem inom fysik och life science revolutioneras av Internet computing teknik, som rutnät computing, som möjliggör den massiva kooperativa delning av beräkningskraft, bandbredd, lagring och data. En svag beräkningsenhet, när den väl är ansluten till ett sådant rutnät, begränsas inte längre av dess långsamma hastighet, små mängder lokal lagring och begränsad bandbredd: Den kan utnyttja det överflöd av dessa resurser som finns tillgängliga någon annanstans på nätet. Ett hinder för användningen av "beräkningsutkontraktering" är att uppgifterna i fråga ofta är känsliga, t.ex. av nationell betydelse för säkerheten, eller äganderättsligt skyddade och innehåller affärshemligheter, eller ska hållas privata för rättsliga krav som HIPAA-lagstiftningen, Gramm-Leach-Bliley eller liknande lagar. Detta motiverar utformningen av tekniker för beräkning av outsourcing på ett integritetsbevarande sätt, dvs. utan att avslöja för de fjärragenter vars beräkningskraft används, antingen ens data eller resultatet av beräkningen av data. Detta papper undersöker sådan säker outsourcing för allmänt tillämpliga sekvensjämförelseproblem, och ger ett effektivt protokoll för en kund att säkert outsourca sekvensjämförelser till två fjärragenter, så att agenterna lär sig ingenting om kundens två privata sekvenser eller resultatet av jämförelsen. De lokala beräkningar som görs av kunden är linjära i storleken på sekvenserna, och den beräkningskostnader och mängden kommunikation som görs av externa agenter är nära tids komplexiteten hos den mest kända algoritmen för att lösa problemet på en enda maskin (dvs., kvadratisk, vilket är en enorm beräkningsbörda för de typer av massiva data på vilka sådana jämförelser görs). Det problem med sekvensjämförelse som beaktas uppstår i ett stort antal tillämpningar, inklusive taligenkänning, maskinseende och molekylära sekvensjämförelser. Dessutom, i huvudsak samma protokoll kan lösa en större klass av problem vars standard dynamiska programmeringslösningar liknar i struktur till den upprepning som subtenderar sekvensjämförelse algoritmen.
Atallah och Li REF undersökte problemet med att beräkna redigeringsavståndet mellan två sekvenser och presenterade ett effektivt protokoll för att säkert outsourca sekvensjämförelser till två servrar.
SECURE OUTSOURCING OF SEQUENCE COMPARISONS
{'venue': 'Privacy Enhancing Technologies', 'journal': None, 'mag_field_of_study': ['Computer Science']}