Computational entropy from distributional hardness
Loading...
URL
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
2021-12-14
Department
Major/Subject
Matematiikka
Mcode
SCI3054
Degree programme
Master’s Programme in Mathematics and Operations Research
Language
en
Pages
67+2
Series
Abstract
A central problem in cryptography is the construction of basic \textit{primitives}, or low-level algorithms, from computational complexity-based assumptions. One way of viewing the hardness of a problem from the view of a computationally bounded adversary is via the notion of \textit{entropy}. Much like the toss of a normal coin is considered random due to limitations of human observers, the real entropy, or uncertainty, of a system can be much higher or lower than the entropy that is ``observable" by an efficient adversary. In this thesis we establish results obtaining this type of computational entropy from \textit{distributionally hard} primitives. This notion of distributional hardness captures that it is hard for an adversary to output a uniform pre-image of a randomly sampled image value. We use this computational entropy from distributional hardness to expand on existing results constructing pseudorandom generators from \textit{next-block pseudoentropy}, and statistically hiding commitment schemes from \textit{accessible entropy}. Although the existence of such constructions were implicit in existing literature, we establish much more efficient constructions with tighter bounds on the computational entropy than has previously been considered. Furthermore, the current known optimal construction of pseudorandom generators in terms of input (or \textit{seed}) length appears to hold with equivalent parameters for the much more general notion of distributional hardness, establishing that the much more general notion of distributional hardness may in itself yield conceptually interesting constructions. We improve on existing results using known known information theoretic inequalities. Most centrally we use an inequality due to Bretagnolle and Huber relating the statistical distance and relative entropy of distributions in a much tighter way in the context of highly disjoint distributions than the famous Pinsker bound.Ett centralt problem inom kryptografi är konstruktionen av kryptografiska \textit{primitiv}, eller enkla algorimtmer, från kompleksitetsteoretiska antaganden. Ett sätt att uppfatta svårhetsgraden av ett problem för en motståndare med begränsade beräkningsresurser är genom begreppet \textit{entropi}. Liksom deterministiska (och därmed förutsägbara) myntkast behandlas som slumpmässiga för mänskilga obervatörer, kan den äkta entropin, eller osäkerheten, av ett kryptosystem vara mycket lägre eller högre än vad en begränsad motståndare klarar av att observera. I detta diplomarbete härleder vi resultat som etalberar denna typs beräknelig entropi från \textit{distributionellt svåra} primitiv. Distributionell svårhet innebär att det är svårt för en motståndare att hitta jämndistribuerade urbilder för slumpmässiga bildelement. Detta inkluderar även funktioner som alltid har en enkel urbild. Via beräknelig entropi från distributionellt svåra problem bygger vi på existerande resultat inom litteraturen och påvisar konstruktioner av pseudoslumpgeneratorer från \textit{pseudoentropi}, och statistiskt gömmande lojalitetssystem från \textit{tillgänglig entropi}. Dessa konstruktioner är implicita i den existerande litteraturen, men våra resultat etablerar mycket stramare konstruktioner via mera optimala olikheter för beräknelig entropi från distributionell svårhet. Intressant nog, verkar den just nu mest optimala konstruktionen av pseudoslumpgeneratorer från envägsfunktioner hålla med ekvivalenta parametrar för den mycket mer generalla klassen av distributionellt hårda funktioner, alltså kan distributionellt svåra primitiv redan i sig möjligen ge interessanta konstruktioner. Vi bygger på existerande resultat via kända informationsteoretiska olikheter, mest centralt en olikhet av Bretagnolle och Huber som etablerar ett samband mellan statistisk distans of relativ entropi.Description
Supervisor
Brzuska, ChristopherThesis advisor
Brzuska, ChristopherKeywords
one-way functions, statistical distance, relative entropy, computational entropy, hash-functions