Show simple item record

dc.contributor.advisorKanukurthi, Bhavana
dc.contributor.authorObbattu, Sai Lakshmi Bhavana
dc.date.accessioned2020-06-12T04:45:22Z
dc.date.available2020-06-12T04:45:22Z
dc.date.submitted2020
dc.identifier.urihttps://etd.iisc.ac.in/handle/2005/4454
dc.description.abstractNon-malleable codes(NMC) introduced by Dziembowski, Pietrzak and Wichs in ITCS 2010, provide powerful security guarantees where error-correcting codes can not provide any guarantee: a decoding of tampered codeword is either the same or completely independent of the underlying message. One of the most important families of tampering functions is the t-splitstate family, where, the adversary tampers each of the t blocks (called state) of a codeword, independently. In this thesis, we construct the first explicit constant-rate and constant-state non-malleable code. In particular, we construct an efficient non-malleable code in the t-splitstate model, for t = 4, that achieves a constant rate of 1 3+ζ , for any constant ζ > 0 and error 2 −Ω(`/logc+1`) , where ` is the length of the message and c > 0 is an arbitrary constant. We then focus on the fascinating problem of privacy amplification introduced by Bennett et.al in 1988. A privacy amplification(PA) protocol allows two parties, Alice and Bob, who a-priori share a weak secret w, to agree on a uniform secret key, in the presence of a computationally unbounded adversary Eve. Specifically, we show how to construct a constant round privacy amplification protocol from any augmented split-state non-malleable code. Existentially, this gives us another primitive (in addition to optimal non-malleable extractors) whose optimal construction would result in a privacy amplification protocol with optimal entropy loss and min-entropy requirement. Instantiating our code with the NMC due to Li (STOC 2017), gives us an 8-round privacy amplification protocol with entropy loss O(log(n) +κ log(κ)) and min-entropy requirement Ω(log(n) + κ log(κ)), where κ is the security parameter and n is the length of the shared weak secret. In fact, for our result, even the weaker primitive of Non-malleable Randomness Encoders suffice. We view this result as an exciting connection between two of the most fascinating and well-studied information theoretic primitives, non-malleable codes and privacy amplification.en_US
dc.language.isoen_USen_US
dc.rightsI grant Indian Institute of Science the right to archive and to make available my thesis or dissertation in whole or in part in all forms of media, now hereafter known. I retain all proprietary rights, such as patent rights. I also retain the right to use in future works (such as articles or books) all or part of this thesis or dissertationen_US
dc.subjecterror-correcting codesen_US
dc.subjecttampering functionsen_US
dc.subjectt-splitstate familyen_US
dc.subject.classificationResearch Subject Categories::TECHNOLOGY::Information technology::Computer science::Computer scienceen_US
dc.titleConstant-rate Non-malleable Codes and their Applicationsen_US
dc.typeThesisen_US
dc.degree.namePhDen_US
dc.degree.levelDoctoralen_US
dc.degree.grantorIndian Institute of Scienceen_US
dc.degree.disciplineEngineeringen_US


Files in this item

This item appears in the following Collection(s)

Show simple item record