Non-malleable randomness extractors

University of Warsaw Repository

pl | en
 
 

Show simple item record

dc.contributor.advisor Pomykała, Jacek
dc.contributor.author Durnoga, Konrad
dc.date.accessioned 2014-05-30T10:58:08Z
dc.date.available 2014-05-30T10:58:08Z
dc.date.issued 2014-05-30
dc.identifier.uri https://depotuw.ceon.pl/handle/item/706
dc.description.abstract We 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.description.abstract Rozprawa 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.language.iso en
dc.rights 10daysAccess
dc.subject derandomization
dc.subject baby-steps giant-steps
dc.subject discrete logarithm
dc.subject non-malleable extractor
dc.subject randomness extractor
dc.subject derandomizacja
dc.subject algorytm małych-wielkich kroków
dc.subject logarytm dyskretny
dc.subject ekstraktor niekowalny
dc.subject ekstraktor losowości
dc.title Non-malleable randomness extractors
dc.title.alternative Niekowalne ekstraktory losowości
dc.type info:eu-repo/semantics/doctoralThesis
dc.description.eperson Konrad Durnoga
dc.contributor.department Wydział Matematyki, Informatyki i Mechaniki
dc.date.defence 2014-06-10

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search Repository


Advanced Search

Browse

My Account

Statistics