Passwords have become the most ubiquitous form of client-server authentication on the Internet nowadays. Password-over-TLS, the almost universal password authentication protocol in practice, suffers from two major drawbacks: (i) it requires a secure channel; and (ii)

the server sees the client's password in the clear.

This dissertation focuses on another approach of password authentication, which eliminates the two shortcomings above. We study cryptographic protocols in the password-only setting, that is, the only information shared between the client and the server is the short and low-entropy password. We present highly efficient realizations of two kinds of such protocols: (1) Password-Protected Secret Sharing (PPSS), in which the client stores a long secret (e.g., its private key) in a group of servers, and recovers the secret via interacting with a subset of servers using a password; and (2) asymmetric Password-Authenticated Key Exchange (aPAKE), in which the client (which enters a password) and the server (which stores a password file) establish the same secret key. All these protocols are resilient to man-in-the-middle attacks (i.e., no authenticated channel is required) as well as server compromise: the only forms of attacks are the unavoidable ones, namely online password guessing attacks and offline dictionary attacks in case of server compromise.

We present thorough description of our protocols, the proofs of their security, and analyses of their computational costs. All security proofs are in the Universally Composable (UC) framework, which addresses subtle vulnerabilities of passwords (non-uniform distribution over the dictionary, reuse of the same password over different accounts, etc.) in a natural and easy-to-argue way, and thus is preferred over the traditional game-based security model.

Password-Protected Secret-Sharing (PPSS) schemes (parameterized by t and n) are a type of cryptographic protocols executed by a user and n servers, where the user shares a secret key (which in turn protects some secret information) among the servers and can reconstruct the key by interacting with t + 1 servers later. Any efficient adversary who breaks into t servers learns no information about the user's key. In this work, we take an existing PPSS scheme and improve it in terms of computational costs. We analyze the security of the new scheme in detail.

The PPSS scheme uses a functionality called Oblivious PRF (OPRF) as a crucial block. In addition, OPRF itself might be of interest in other areas. We formalize this OPRF functionality in the Universal-Composability (UC) framework, and realize it efficiently. This forms an improvement of a previous realization. We reduce the computational costs significantly, without changing the basic functions of OPRF.

Password authentication is common in the digital world, yet current methods rely completely on Public Key Infrastructure (PKI) and server trust to establish security. A promising solution to this problem is Password Authenticated Key Exchange (PAKE), a cryptographic primitive in which two parties who share a password establish a cryptographic key. This dissertation is a collection of three articles which all center on creating and analyzing PAKE variants in the strong Universally Composable model that solve real-world problems efficiently enough to be adopted in practice. The articles are entitled “Password Authenticated Public Key Encryption,” [27] “Strong Asymmetric PAKE based on Trapdoor CKEM,” [28] and “Universally Composable Relaxed Password Authenticated Key Exchange” [2].

An Oblivious RAM (ORAM) protocol allows a client to access memory outsourced at the server without leaking the access pattern. A related notion is Multi-Party Computation ORAM (MPC-ORAM), which is a protocol that can implement the RAM functionality for secure computation of any RAM programs on large data, e.g., MPC processing of database queries on a secret-shared database. MPC-ORAM can be constructed from any (client-server) ORAM by implementing the ORAM client algorithm with MPC protocols. However, efficient ORAM does not necessarily translate to efficient MPC-ORAM. Most previous work constructed efficient MPC-ORAM in the two-party secure computation (2PC) setting, but since secure computation of many functions is more efficient in the three-party honest-majority setting than in the two-party setting, it is natural to ask if the cost of an MPC-ORAM scheme can be reduced if one is willing to use three servers instead of two and assumes an honest majority. In this study, we show four constructions of MPC-ORAM in the three-party setting (3PC-ORAM) with honest majority, using customized 3PC protocols for performance optimization, which can make the resulting 3PC-ORAM schemes to be orders of magnitude more efficient than the current best 2PC-ORAM schemes. These improvements help to achieve practical and efficient performance results, and make MPC-ORAM more suitable for real world applications.

In the last few years the subject of password authenticated key exchange (PAKE) protocols, particularly in the client-server setting (called {\em asymmetric} PAKE, or aPAKE for short), has seen renewed interest due to the weaknesses of password protocols and the ongoing standardization effort at the Internet Engineering Task Force. In particular, due to vulnerabilities in PKI systems and TLS deployment, the standard PKI-based encrypted password authentication(or ``password-over-TLS") often leads to disclosure of passwords and increased exploitation of phishing techniques. Even when the password is decrypted at the correct server, its presence in plaintext form after decryption, constitutes a security vulnerability as evidenced by repeated incidents where plaintext passwords were accidentally stored in large quantities and for long periods of time even by security-conscious companies. Both problems of relying on PKI and server seeing password in clear are properly solved by PAKE protocols in the password-only setting.

While many PAKE protocols have been proposed, an interesting question is that whether there is an efficiency limit (for computation or communication) for PAKE protocols, and how to achieve that. Attempting to push such limit, this dissertation proposes a new paradigm for building efficient (a)PAKE protocols. First we present a minimal-cost aPAKE compiler called KHAPE, which offers the best performance in terms of exponentiations with less than the cost of an exponentiation on top of an un-authenticated Diffie-Hellman key exchange. In the followup work we propose OKAPE, which further improve the round complexity of KHAPE to only two rounds of messages by leveraging a unilaterally authenticated key exchange. Since both KHAPE and OKAPE relies on Ideal Cipher (IC) Model, and existng construction for Ideal Cipher on groups all have drawbacks, we present a weakened version called Randomized Ideal Cipher (RIC) by giving up randomness of part of the ciphertext but still can be used as a drop-in replacement for IC applications. We proved that the modified 2-Feistel realizes this notion, which further improves the computation efficiency for our aPAKE compilers. Furthermore, by replacing IC with RIC in EKE protocol we get a PAKE compiler from any CPA-secure and anonymous KEM, which also opens the door for efficient lattice-based PAKE. Finally, we develop a PAKE-to-aPAKE compiler from KEM, which by embedding the previous KEM-based PAKE we can achieve an aPAKE compiler from KEM.

Private Set Intersection (PSI) is a cryptographic primitive that allows two network connected parties with hidden inputs to jointly compute the intersection of these inputs while keeping their specific inputs secret. PSI can be used as a building block for a variety of applications, most notably querying a remote relational database without revealing the query or the database. Many constructions of PSI exist, each building off of a subset of an assortment of cryptographic primitives such as: oblivious transfer, hash functions, garbled circuits, public key encryption and signature schemes, and basic number theoretic hardness assumptions. In this dissertation, we study variations of PSI and their practicality to modern day applications. Specifically, we study new security constraints for PSI that arise from applications such as genomics, consumer applications, and inter-agency information sharing. These constraints lead to several novel secure computation protocols. Through actualized prototypes of these schemes we conclude that, specialized PSI protocols are fast enough for use today, even on resource constrained hardware.