Praca doktorska
Miniatura
Pliki
auto.pdf219.08 KB
KDurnoga_thesis.pdf431.59 KB
KDurnoga_rec_DSimson.pdf100.23 KB
KDurnoga_rec_MKula.pdf72.37 KB
Licencja
ClosedAccessDostęp zamknięty
 

Non-malleable randomness extractors

Uproszczony widok
dc.abstract.enWe give an unconditional construction of a non-malleable extractor improving the solution from the recent paper "Privacy Amplification and Non-Malleable Extractors via Character Sums" by Dodis et al. (FOCS'11). There, the authors provide the first explicit example of a non-malleable extractor - a cryptographic primitive that significantly strengthens the notion of a classical randomness extractor. In order to make the extractor robust, so that it runs in polynomial time and outputs a linear number of bits, they rely on a certain conjecture on the least prime in a residue class. In this dissertation we present a modification of their construction that allows to remove that dependency and address an issue we identified in the original development. Namely, it required an additional assumption about feasibility of finding a primitive element in a finite field. As an auxiliary result, which can be of independent interest, we show an efficiently computable bijection between any order M subgroup of the multiplicative group of a finite field and a set of integers modulo M with the provision that M is a smooth number. Also, we provide a version of the baby-step giant-step method for solving multiple instances of the discrete logarithm problem in the multiplicative group of a prime field. It performs better than the generic algorithm when run on a machine without constant-time access to each memory cell, e.g., on a classical Turing machine.
dc.abstract.plRozprawa poświęcona jest analizie ekstraktorów losowości, czyli deterministycznych funkcji przekształcających niedoskonałe źródła losowości na takie, które są w statystycznym sensie bliskie rozkładom jednostajnym. Główny rezultat dysertacji stanowi bezwarunkowa i efektywna konstrukcja ekstraktora pewnego szczególnego typu, zwanego ekstraktorem niekowalnym. Jest to poprawienie wyniku z opublikowanej niedawno pracy "Privacy Amplification and Non-Malleable Extractors via Character Sums" autorstwa Dodisa i in. (FOCS'11). Podana tam konstrukcja stanowiła pierwszy jawny przykład ekstraktora niekowalnego, choć był to rezultat warunkowy, odwołujący się do pewnej hipotezy dotyczącej liczb pierwszych w postępach arytmetycznych. W rozprawie przedstawiona jest modyfikacja rozwiązania Dodisa i in., która pozwala na usunięcie tego dodatkowego założenia. Jednocześnie wskazana w dysertacji i występująca w oryginalnym rozumowaniu luka, związana z problemem wydajnego znajdowania generatora grupy multiplikatywnej w ciele skończonym, nie przenosi się na proponowaną w rozprawie konstrukcję.
dc.affiliationUniwersytet Warszawski
dc.affiliation.departmentWydział Matematyki, Informatyki i Mechaniki
dc.contributor.authorDurnoga, Konrad
dc.date.accessioned2014-05-30T10:58:08Z
dc.date.available2014-05-30T10:58:08Z
dc.date.defence2014-06-10
dc.date.issued2014-05-30
dc.date.submitted2013-06
dc.description.additionalLink archiwalny https://depotuw.ceon.pl/handle/item/706
dc.description.promoterPomykała, Jacek
dc.description.reviewerKula, Mieczysław
dc.description.reviewerSimson, Daniel
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/706
dc.languageen
dc.language.isoen
dc.language.otherpl
dc.rightsClosedAccess
dc.subject.enderandomization
dc.subject.enbaby-steps giant-steps
dc.subject.endiscrete logarithm
dc.subject.ennon-malleable extractor
dc.subject.enrandomness extractor
dc.subject.plderandomizacja
dc.subject.plalgorytm małych-wielkich kroków
dc.subject.pllogarytm dyskretny
dc.subject.plekstraktor niekowalny
dc.subject.plekstraktor losowości
dc.titleNon-malleable randomness extractors
dc.title.alternativeNiekowalne ekstraktory losowości
dc.typeDoctoralThesis
dspace.entity.typePublication