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.