Cryptographic assumptions and security goals are fundamentally distributional. As a result, statistical techniques are ubiquitous in cryptographic constructions and proofs. In this thesis, we build upon existing techniques and seek to improve both theoretical and practical constructions in three fundamental primitives in cryptography: blockciphers, hash functions, and encryption schemes. First, we present a tighter hybrid argument via collision probability that is more general than previously known, allowing applications to blockciphers. We then use our result to improve the bound of the Swap-or-Not cipher. We also develop a new blockcipher composition theorem that is both class and security amplifying. Second, we prove a variant of Leftover Hash Lemma for joint leakage, inspired by the Universal Computational Extractor (UCE) assumption. We then apply this technique to construct various standard-model UCE- secure hash functions. Third, we survey existing “lossy primitives” in cryptography, in particular Lossy Trapdoor Functions (LTDF) and Lossy Encryptions (LE); we pro- pose a generalized primitive called Lossy Deterministic Encryption (LDE). We show that LDE is equivalent to LTDFs. This is in contrast with the block-box separation of trapdoor functions and public-key encryption schemes in the computational case. One common theme in our methods is the focus on statistical techniques. Another theme is that the results obtained are in contrast with their computational counterparts—the corresponding computational results are implausible or are know to be false.

Memory-hard functions (MHFs) is a class of hash functions whose fast evaluation requires the heavy use of memory, and an evaluation that spends less memory has to incur a much larger time penalty. Memory-hardness is particularly useful in the setting of password hashing and cryptocurrencies, as memory cost is platform-independent and efficient special-purpose hardware for brute-forcing attacks becomes much harder to be built. Since its first proposal by Colin Percival in 2009, many memory-hard hash heuristics were proposed, and the notion/design of MHFs has received a considerable amount of theoretical scrutiny as well. However, a large gap still exists when theory meets practice. On the one hand, most of the practical schemes are only heuristics without formal analysis, and attacks do exist for some of them; on the other hand, theoretical analyses are usually based on unrealistic assumptions: they consider MHFs as modes of operation of some underlying hash function H, modeled as a random oracle. Unfortunately, in practice, this is never the case as H is usually a heuristic design built from simpler primitives.

This dissertation makes progress in addressing both of the problems. Our main contributions are threefold. First, we prove that a widely-used MHF candidate, called scrypt, is provably and optimally memory-hard, thus shedding light on the confidence of its wide application. Second, we model simple cryptographic tools (e.g. AES) as the underlying ideal primitives and present a generic and provably-secure MHF construction from hard-to-pebble graphs. The resulting scheme significantly decreases the efficiency gap between legitimate users and ASICs-equipped attackers. Finally, given the practice demands for H to have large outputs (to increase memory hardness without changing the description size of MHFs), we go back to the framework of constructing MHFs from H (with large output). Different from previous work, we take finer-granularity of the hash function H into account and provide the first provably secure design of H from simpler primitives (e.g. fixed-key AES).

As organizations and companies are increasingly offloading data and computation to the cloud to reduce infrastructure administration,

data volume keeps growing and new services and algorithms are needed to meet increasing demands for both storage capacity and privacy.

The first part of my thesis will address cloud data backup.

Organizations and companies often backup and archive high volumes of binary and text datasets for fault tolerance,

internal investigation, and electronic discovery. Source-side deduplication has an advantage to avoid or minimize duplicated data transmitted over the network,

however it demands more computing resource to perform extensive fingerprint comparison which would otherwise be available for primary services at the source.

For data stored in the cloud, users need efficient, scalable services for searching these files.

In the first part of this thesis, I will cover the key components of existing solutions for large-scale backup storage in the cloud.

I will go into detail on how deduplication is important to large scale backup systems, and review some ongoing work.

I will also detail my contributions in this area towards low-profile source-side deduplication.

The second part of my thesis addresses an open problem for efficient private document search on data hosted on the cloud.

As sensitive information is increasingly centralized into the cloud, for the protection of data privacy, such data is often encrypted,

which makes effective data indexing and search a very challenging task. To overcome the challenges of querying encrypted datasets,

searchable encryption schemes allow users to securely search over encrypted data through keywords.

No existing solutions for efficient ranking which involves complex arithmetic computation in feature composition and scoring currently exist,

and without relevant ranking of search results queries over very large datasets which may return many results can be impractical.

In the second part of my thesis I will review existing work on private search and introduce our ongoing and published work for this open problem,

focusing on how to make private search practical and scalable for large datasets.

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.