Vi studerar problemet med databehandling på stora dataset som lagras på en opålitlig server. Vi följer metoden med amorterad kontrollerbar beräkning som infördes av Gennaro, Gentry och Parno i CRYPTO 2010. Vi presenterar det första praktiska verifierbara beräkningssystemet för höggradiga polynomfunktioner. Sådana funktioner kan till exempel användas för att göra förutsägelser baserade på polynom som är monterade på ett stort antal provpunkter i ett experiment. Förutom de många icke-kryptografiska applikationerna av att delegera höggradiga polynom, använder vi vårt verifierbara beräkningssystem för att få nya lösningar för kontrollerbar sökordssökning, och bevis på att det går att få tillbaka. Våra konstruktioner är baserade på DDH antagande och dess varianter, och uppnå adaptiv säkerhet, som lämnades som ett öppet problem av Gennaro et al (om än för allmänna funktioner). Vårt andra resultat är en primitiv som vi kallar en kontrollerbar databas (VDB). Här, en svag klient outsourcar en stor tabell till en opålitlig server, och gör hämtning och uppdatera frågor. För varje fråga ger servern ett svar och ett bevis på att svaret beräknades korrekt. Målet är att minimera de resurser som kunden behöver. Detta görs särskilt utmanande om antalet uppdateringsförfrågningar är obegränsat. Vi presenterar ett VDB-system baserat på hårdheten i undergruppsmedlemsproblemet i sammansatta tvåradiga grupper. Detta är den första sådana konstruktion som bygger på en "konstant storlek" antagande, och inte kräver dyr generering av primer per operation.
Under 2011 föreslog Ref ett problem som databehandling på stora datauppsättningar som lagras på opålitlig server.
Verifiable delegation of computation over large datasets
{'venue': 'In Proceedings of the 31st annual conference on Advances in cryptology, CRYPTO’11', 'journal': None, 'mag_field_of_study': ['Computer Science']}