Please use this identifier to cite or link to this item:
http://arks.princeton.edu/ark:/88435/dsp01mk61rk68w
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Zhandry, Mark | - |
dc.contributor.advisor | Sarnak, Peter | - |
dc.contributor.author | Gjura, Boriana | - |
dc.date.accessioned | 2018-08-17T19:11:25Z | - |
dc.date.available | 2018-08-17T19:11:25Z | - |
dc.date.created | 2018-05 | - |
dc.date.issued | 2018-08-17 | - |
dc.identifier.uri | http://arks.princeton.edu/ark:/88435/dsp01mk61rk68w | - |
dc.description.abstract | In this thesis we analyze cryptanalytic attacks on the compute-and-compare program obfuscation scheme proposed by Wichs and Zirdelis [WZ17]. The work of Wichs and Zirdelis is the first to give a provable VBB obfuscation scheme for a large sub-class of evasive functions, compute-and-compare programs, under the Learning with Errors (LWE) assumption. If f : {0, 1} lin → {0, 1} lout, and y ∈ {0, 1} lout, then the compute-and-compare program CC[f, y](x) is 1 whenever f(x) = y, and 0 otherwise. The scheme starts by obfuscating a branching program P of length L that computes f, and reads the input x according to a specified input function. This is provably secure when y is computationally indistinguishable given f. In this paper, we consider the case when lout = 1, i.e. y is a single bit. We show that in this case, the scheme is not even iO-secure. Moreover, we show that we given enough examples of the form (x, f(x)) from a given distribution, with high probability we can learn f over that distribution. The key to proving these results is that the encoded version of the program allows us to evaluate the branching program P on inputs other than those specified by the input function. That is, this encoding scheme reveals too much information about the structure of the underlying program. | en_US |
dc.format.mimetype | application/pdf | - |
dc.language.iso | en | en_US |
dc.title | Obfuscating Compute-and-Compare Programs under the LWE assumption: Analysis of the Wichs & Zirdelis Scheme | en_US |
dc.type | Princeton University Senior Theses | - |
pu.date.classyear | 2018 | en_US |
pu.department | Mathematics | en_US |
pu.pdf.coverpage | SeniorThesisCoverPage | - |
pu.contributor.authorid | 961072805 | - |
Appears in Collections: | Mathematics, 1934-2020 |
Files in This Item:
File | Size | Format | |
---|---|---|---|
GJURA-BORIANA-THESIS.pdf | 421.41 kB | Adobe PDF | Request a copy |
Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.