Browsing by Author "Paakkinen, Aleksanteri"

Now showing 1 - 1 of 1

Bootstrapping Virtual Black-Box obfuscation via randomized encodings
(2024-06-07) Paakkinen, Aleksanteri
Perustieteiden korkeakoulu | Bachelor's thesis
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.