Bootstrapping Virtual Black-Box obfuscation via randomized encodings
No Thumbnail Available
Files
Aalto login required (access for Aalto Staff only).
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
Bachelor's thesis
Electronic archive copy is available locally at the Harald Herlin Learning Centre. The staff of Aalto University has access to the electronic bachelor's theses by logging into Aaltodoc with their personal Aalto user ID. Read more about the availability of the bachelor's theses.
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Author
Date
2024-06-07
Department
Major/Subject
Matematiikka ja systeemitieteet
Mcode
SCI3029
Degree programme
Teknistieteellinen kandidaattiohjelma
Language
en
Pages
20
Series
Abstract
Obfuscation 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.Obfuskoinnissa 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.Description
Supervisor
Brzuska, ChrisThesis advisor
Brzuska, ChrisKeywords
obfusaction, cryptography, virtual black-box, bootstrapping
