Distributional Security for OWF, PRF and Garbling
Loading...
Journal Title
Journal ISSN
Volume Title
School of Science |
Doctoral thesis (article-based)
| Defence date: 2024-09-19
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.
Author
Date
2024
Major/Subject
Mcode
Degree programme
Language
en
Pages
40 + app. 136
Series
Aalto University publication series DOCTORAL THESES, 181/2024
Abstract
Cryptography studies secure communication, including but not limited to: how to send messages safely over an untrusted channel, how to store and send passwords safely and how to outsource computations on confidential data to an untrusted cloud computing service. Cryptography as a field defines the adversarial model and the aim mathematically, and seeks to find the simplest, most efficient and trustworthy assumptions and cryptographic tools, called primitives (e.g. encryption), that are needed to reach the goal. Often, the goal might require two or more parties to send several messages (that consist of outputs of some primitives, e.g. encryption of some data or hash of a password) between themselves, such interactive setting is called a cryptographic protocol. One of the most elementary and well-studied cryptographic primitives is a one-way function (OWF). The only security a OWF guarantees is that a polynomial time adversary cannot invert it, except with a negligible probability, when the input to the OWF comes from the uniform distribution. However, there is also a weaker variant of the OWF definition, namely, a OWF where the adversary only fails to invert on a small (say, constant or polynomial) fraction of the inputs. Even though a weak OWF is weaker than a OWF, there are several constructions to obtain a OWF from a weak OWF. The simplest such construction is through parallel repetition, due to Yao [40]. In this thesis, we first study which input distributions to such parallel repetition of a weak OWF can yield a OWF. We show a lower bound on the entropy that the input needs to have. We also study input distributions to pseudorandom functions (PRF). A PRF is a function whose outputs are indistinguishable from random to an adversary who can query the function multiple times with any inputs. A weak PRF on the other hand is secure only when the inputs come from a (public) uniform distribution. A weak PRF can be amplified to a PRF by passing the inputs first to a random oracle (RO). RO is a very idealized (and hence not always realistic [11, 10]) model for a hash function, where all parties, adversaries included, have blackbox access to a truly random function (the RO). In the construction of a PRF from a weak PRF, the RO effectively randomizes the adversary's inputs to the PRF and hence the adversary's choices will not help. We study how to achieve a similar 'input randomization' as the RO provides using a more standard assumption, namely, extremely lossy functions (ELF). We also study how to replace the RO with an ELF in a (slightly modified) popular public key encryption construction, the Fujisaki-Okamoto transform. Finally, we study input distributions to garbling schemes. A garbling scheme is a way to encode a circuit and an input to the circuit in such a way that the circuit can be evaluated to obtain the output, but nothing else, about the circuit or the input, is leaked. Specifically, we are interested in an 5 adaptive setting where the adversarial evaluator gets the garbled circuit first and only after that chooses the input-to-be-garbled. We study whether it is possible to achieve short input encoding and still satisfy a strong, so called simulation based, security notion. Two lower bounds [3, 24] show that is this setting, in general, the input encoding length needs to depend on the circuit's output length or (pseudo-)entropy. We study where exactly these negative results stem from and we propose a new distributional simulation based adaptive security definition that does not suffer from the lower bounds but that still captures a strong and meaningful security requirement. We also establish a bootstrapping result: if a garbling scheme satisfies our new security definition for low depth circuits, then there exists a garbling scheme that satisfies the new security definition for arbitrary polynomial sized circuits.Description
Supervising professor
Brzuska, Chris, Prof., Aalto University, Department of Mathematics and Systems Analysis, FinlandKeywords
theoretical cryptography, one-way function, pseudorandom function, garbling, teoreettinen kryptografia, yksisuuntainen funktio, näennäissatunnaisfunktio
Other note
Parts
-
[Publication 1]: Chris Brzuska, Geoffroy Couteau, Pihla Karanko, and Felix Rohrbach. On Derandomizing Yao’s Weak-to-Strong OWF Construction. Accepted for publication in TCC, pp 429–456, November 2021.
DOI: 10.1007/978-3-030-90453-1_15 View at publisher
-
[Publication 2]: Estuardo Alpirez Bock, Chris Brzuska, Pihla Karanko, Sabine Oechsner, and Kirthivaasan Puniamurthy. Adaptive Distributional Security for Garbling Schemes with O(|x|) Online Complexity. Accepted for publication in ASIACRYPT, pp 139–171, December 2023.
DOI: 10.1007/978-981-99-8721-4_5 View at publisher
- [Publication 3]: Chris Brzuska, Geoffroy Couteau, Christoph Egger, Pihla Karanko, and Pierre Meyer. New Random Oracle Instantiations from Extremely Lossy Functions. Submitted, July 2023
- [Publication 4]: Pihla Karanko. Different Flavours of HILL Pseudoentropy and Yao Incompressibility Entropy. Submitted, December 2023
