Bootstrapping Virtual Black-Box obfuscation via randomized encodings

dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.advisorBrzuska, Chris
dc.contributor.authorPaakkinen, Aleksanteri
dc.contributor.schoolPerustieteiden korkeakoulufi
dc.contributor.supervisorBrzuska, Chris
dc.date.accessioned2024-06-11T08:22:37Z
dc.date.available2024-06-11T08:22:37Z
dc.date.issued2024-06-07
dc.description.abstractObfuscation is the act of encrypting programs while preserving their functionality. It could be used in mobile payment applications that need to hide their secrets, guarding intellectual property like algorithms in software products or implementing digital rights management. Unfortunately direct constructions of provably secure obfuscators are hard. Thus current obfuscation research seeks to find which kind of other primitives suffice to construct obfuscators and which kind of security guarantees can be achieved for the obfuscated programs. Conversely existence of obfuscation also leads to alternative constructions of advanced cryptographic primitives like Fully Homomorphic Encryption (FHE), an encryption scheme which allows computation on encrypted data. Obfuscation methods can have different security guarantees. The one we use in this thesis is virtual black box (VBB) security where the obfuscated program reveals no information about the original program aside from its input and output behavior. The VBB security definition is very strong so a more relaxed security notion of indistinguishability obfuscation (iO) has been suggested. In iO two circuits of same size that compute the same function should be indistinguishable from each other after obfuscation. Many constructions of obfuscators tie together obfuscators for high and low complexity programs. With assistence of some additional assumptions (to be discussed shortly) the obfuscators for simple programs can be bootstrapped into obfuscators for more complex ones. This allows one to extend possibility and impossibility results from one complexity class to others and to understand properties of complexity classes by how they interact with obfuscation. In this thesis we review a result by Applebaum who, by using randomized encodings, bootstraps a VBB obfuscator for NC1 to a VBB obfuscator for all polynomial-sized circuits, provided that NC1 contains pseudorandom functions. This is a stronger result than earlier work where the bootstrapping is ultimately based on an assumption that decryption algorithm for FHE exists in NC1. Remarkably iO constructions too have followed a similar path as VBB constructions, where iO was first bootstrapped from the assumption of FHE existing in NC1. Later work shows that for iO the existence of FHE assumption can be relaxed to existence of Learning with Errors, or to existence of puncturable PRFs in NC1.en
dc.description.abstractObfuskoinnissa on tarkoituksena salata ohjelmia, kuitenkin samalla säilyttäen näiden ohjelmien toiminnallisuuden. Obfuskoinnin mahdollisia käyttökohteita on salausavaimia sisältävät mobiilimaksuohjelmat, immateriaalioikeuksien, kuten algoritmien, suojelu sovelluksissa tai digitaalisten käyttöoikeuksien hallinta. Valitettavasti todistettavasti turvallisten obfuskaattorien rakentaminen on hankalaa. Täten nykyaikainen tutkimus keskittyy selvittämään, mitkä yksinkertaisemmat algoritmit olisivat riittäviä obfuskaattorien rakentamiseksi, ja kuinka vahva salaus niillä voidaan obfuskaatiossa saavuttaa. Vastaavasti obfuskaattorien olemassaolo mahdollistaisi uusia tapoja rakentaa muita edistyneitä algoritmeja, kuten täysin homomorfinen salaus (engl. Fully-Holomorphic Encryption, FHE), joka mahdollistaa laskennan salatulla datalla ilman salauksen purkamista. Obfuskointimenetelmät tuottavat erivahvuisia takauksia turvallisuudesta. Tässä työssä käsiteltävä menetelmä takaa virtuaalisen mustan laatikon (engl. Virtual Black-Box, VBB) turvallisuuden, jossa obfuskoitu ohjelma ei paljasta mitään muuta tietoa alkuperäisistä ohjelmasta, kuin syötteitä vastaavat tulosteet. VBB-turvallisuus on erittäin vahva, ja se on vaikea saavuttaa, joten on esitetty helpompia turvallisuusmääritelmiä. Erottelemattomuusobfuskoinnissa (engl. Indistinguishability Obfuscation, iO) kaksi saman kokoista saman funktion laskevaa piiriä ovat obfuskoinnin jälkeen erottamattomia toisistaan. Obfuskaattoreita käsittelevät todistukset liittävät usein yhteen obfuskaattoreita korkean ja matalan monimutkaisuuden funktioille. Lisäoletusten avulla yksinkertaisien funktioiden obfuskaattorista voidaan rakentaa monimutkaisempiin funktioiryhmiin päteviä versioita. Olemassaoloon ja olemassaolemattomuuteen liittyvät tulokset auttavat täten luomaan yhteyksiä monimutkaisuusluokkien välille ja hahmottamaan obfuskoinnin riippuvuutta niistä. Tässä työssä käydään läpi Applebaumin tulos, jossa rakennetaan NC1-luokan funktioille toimivasta VBB-obfuskaattorista kaikille polynomiaalisesti kasvaville piireille toimiva VBB-obfuskaattori. Ainoana lisäoletuksena on, että NC1-luokka sisältää pseudosatunnaisen funktion. Tämä on vahvempi tulos verrattuna aiempiin rakennelmiin, joissa nojataan oletukseen, että NC1-luokka sisältää FHE-purkualgoritmin. On huomionarvoista, että myös iO-tyypin obfuskaattorit ovat käyneet läpi samanlaisen kehityskulun; alkuperäisiä FHE:hen perustuvia todistuksia on parannettu perustumalla ne heikompiin oletuksiin, kuten Learning with Errors tai Puncturable Pseudorandom Functions -konstruktioihin.fi
dc.format.extent20
dc.format.mimetypeapplication/pdfen
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/128643
dc.identifier.urnURN:NBN:fi:aalto-202406114233
dc.language.isoenen
dc.programmeTeknistieteellinen kandidaattiohjelmafi
dc.programme.majorMatematiikka ja systeemitieteetfi
dc.programme.mcodeSCI3029fi
dc.subject.keywordobfusactionen
dc.subject.keywordcryptographyen
dc.subject.keywordvirtual black-boxen
dc.subject.keywordbootstrappingen
dc.titleBootstrapping Virtual Black-Box obfuscation via randomized encodingsen
dc.typeG1 Kandidaatintyöfi
dc.type.dcmitypetexten
dc.type.ontasotBachelor's thesisen
dc.type.ontasotKandidaatintyöfi
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
Paakkinen_Aleksanteri_2024.pdf
Size:
461.91 KB
Format:
Adobe Portable Document Format
Download