Galbraith, Steven D.Russello, GiovanniZobernig, Lukas2020-10-272020-10-272020http://hdl.handle.net/2292/53400Program obfuscation is an active and heavily researched topic in theoretical and applied cryptography. General purpose program obfuscators would revolutionise the field and make designing new cryptosystems redundant. But as we shall see, there are various pitfalls surrounding general purpose program obfuscation. In this work we instead take a step back and consider special purpose program obfuscation for selected problems. We briefly explore the state of applied program obfuscation and see whether we can bring more theoretical techniques into the field; for this we study the example of evasive predicates. We construct an obfuscator for fuzzy Hamming distance matching which finds application in biometric authentication, fuzzy extractors, and secure sketches. The security of this obfuscator is based on a new computational assumption rooted in number theory, which we dubbed the modular subset product problem (MSP). We explain our approach to cryptanalysing this problem and give results and conjectures about its (post-quantum) hardness in various parameter ranges. The Hamming distance obfuscator leads us to another application for special purpose obfuscation: Conjunctions or pattern matching with wildcards. Our conjunction obfuscator is conveniently based on the MSP hardness. Finally, we give an obfuscator for a special class of deterministic finite automata (DFA). We consider what we call evasive DFAs which cannot be learned from oracle access. The obfuscator is based on techniques related to branching program obfuscation. It solves the problem of obfuscated substring matching where substrings can even be given by regular expressions.Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated.Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated.https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmhttp://creativecommons.org/licenses/by-nc-sa/3.0/nz/Thesis2020-10-06Copyright: The authorhttp://purl.org/eprint/accessRights/OpenAccessQ112954531