Public defence in Mathematics, M.Sc. (Tech) Pihla Karanko

Title of the thesis: Distributional Security for OWF, PRF and Garbling

Doctoral student: Pihla Karanko
Opponent: Assistant Professor Pavel Hubáček, Czech Academy of Sciences, Czech Republic
Custos: Associate Professor Chris Brzuska, Aalto University School of Science, Department of Mathematics and Systems Analysis

Cryptography uses mathematical models to simulate real-world scenarios involving secrecy. Since we cannot know what an adversary might do (e.g. use supercomputers to break encryption), researchers try to model worst-case scenarios. Security is defined through "games" where a powerful unspecified adversarial algorithm attempts to break the system under controlled conditions. For example, in studying pseudorandom functions (PRFs), the adversary tries to distinguish between true PRF outputs and random bitstrings. If the adversary cannot guess correctly more than 50 % of the time, the PRF in question is considered secure.

Currently, no algorithm is proven to satisfy the rigorous security definitions for PRFs or other cryptographic tools. Instead, real-life systems rely on plausible candidates that have withstood extensive scrutiny. This reliance on unproven assumptions motivates efforts to reduce and better understand them. E.g. a PRF can be built from a one-way function (OWF), a tool with a simpler security definition. 

Main Results: 

- The thesis studies ways to get a OWF from a weaker (i.e. easier to break) OWF. We show that the existing methods are likely optimal in efficiency, highlighting the importance of the input distribution in such security amplification techniques. - We transform a weak PRF into a strong one using a special technique. This approach has practical applications in secure password handling, allowing more efficient authentication, where the user does not need to reveal the password to the server it is authenticating to. 

- We propose a modification to a popular public key encryption mechanism, Fujisaki-Okamoto (FO) Transform, used in post-quantum secure encryption schemes. Our modification provides a more robust security proof. 

- We propose a new security definition for garbling which is a method that allows outsourcing computations to untrusted servers without revealing the function or data. Our definition ensures strong security and efficient input encoding, overcoming current limitations when garbling cryptographic functions, useful for maintaining security when multiple servers encrypt a message jointly and one server becomes corrupted.

Key words: theoretical cryptography, one-way function, pseudorandom function

Thesis available for public display 10 days prior to the defence at: https://aaltodoc.aalto.fi/doc_public/eonly/riiputus/ 

Contact information:

Doctoral theses at the School of Science: https://aaltodoc.aalto.fi/handle/123456789/52 

Zoom Quick Guide: https://www.aalto.fi/en/services/zoom-quick-guide