UC Santa Barbara

In this thesis, we investigate the cost of transforming “weaker” or “less-structured” variants of a cryptographic primitive into a “stronger” or “more structured” variant of the same primitive. We conduct the study via the lens of two fundamental security properties:

Pseudrandomness is critical to almost all of cryptography, and pseudorandom functions (PRFs) and pseudorandom permutations (PRPs) are powerful primitives enabling simple solutions for fundamental problems in secret-key cryptography. Their existence from general assumptions (e.g., one-way functions) is well-studied. But here we investigate new ways of building them with the goal of efficiency and achieving stronger security.

First, we consider building PRFs from non-adaptive PRFs (naPRFs), i.e., PRFs which are secure only against distinguishers issuing all of their queries at once. Known constructions either make $\omega(1)$ calls to an underlying naPRF or incur an undesirable super-polynomial loss in security. We provide the first evidence for this state of affairs by showing that a large class of one-call constructions cannot be proved to be a secure PRF under a black-box reduction to the (polynomial-time) naPRF security of the underlying function. Second, we revisit the question of transforming PRFs to PRPs which are used to reason about the security of block-ciphers when the underlying key is kept secret. However, in practice block-ciphers are also used in settings where the key is known to the adversary. To address this disparity, we introduce the first, plausible extensions of pseudorandomness to the known-key setting and provide secure constructions of PRPs which make two calls to an underlying appropriate PRF. This matches the complexity of PRF to PRP transformations in the secret-key setting.

Non-malleability captures security of cryptographic protocols against man-in-the-middle attacks and non-malleable commitments (NMC) are paragon examples of non-malleable protocols. Resolving the round complexity of NMC, a fundamental measure of cost, has remained a fascinating open question and barriers to achieving two-round (and non-interactive) solutions from polynomial-time assumptions were proved in 2013. We provide the first constructions of two-round and non-interactive NMC under sub-exponential time well-studied assumptions, crucially exploiting the synergy between different axes of hardness to circumvent the above impossibility. At heart, our result presents a round-preserving transformation (i.e., incurring no overhead in number of rounds) from NMC on $t$-bit identities to $\Omega(2^t)$-bits where the length of identities is a measure of a protocol's “non-malleability”. Previous such amplifications incurred additive blow-up in the round-complexity.