Abstrakt. Vi presenterar ett allmänt krypteringsprogram med följande egenskaper. Med tanke på ett förgreningsprogram P och en kryptering c av en ingång x, är det möjligt att effektivt beräkna en koncis chiffertext c från vilken P (x) effektivt kan avkodas med hjälp av den hemliga nyckeln. Storleken på c beror polynomiellt på storleken på x och längden på P, men beror inte ytterligare på storleken på P. Som intressanta specialfall, kan man effektivt utvärdera ändliga automata, beslut träd, och OBDDs på krypterade data, där storleken på den resulterande chiffertext c inte beror på storleken på det objekt som utvärderas. Dessa är de första allmänna representationsmodeller för vilka ett sådant genomförbarhetsresultat visas. Vår huvudsakliga konstruktion generaliserar tillvägagångssättet av Kushilevitz och Ostrovsky (FOCS 1997) för att bygga enserver Privat Information Retrieval protokoll. Vi visar också hur man stärker ovanstående så att c inte innehåller ytterligare information om P (annat än P (x) för vissa x) även om den offentliga nyckeln och chiffertext c är illvilligt bildas. Detta ger en två-meddelande säker protokoll för att utvärdera en längd bundna grenningsprogram P som innehas av en server på en ingång x hålls av en klient. Ett utmärkande drag för detta protokoll är att det döljer storleken på serverns indata P från klienten. Framför allt är kundens arbete oberoende av storleken på P.
Ett protokoll baserat på homomorfisk kryptering där servern utvärderar ett förgreningsprogram på klientens krypterade ingång föreslogs i REF.
Evaluating branching programs on encrypted data
{'venue': 'In TCC 2007', 'journal': None, 'mag_field_of_study': ['Computer Science']}