Enhancing Privacy in Cryptographic Protocols

For the past three decades, a wide variety of cryptographic protocols have been proposed to solve secure communication problems even in the presence of adversaries. The range of this work varies from developing basic security primitives providing confidentiality and authenticity to solving more complex, application-specific problems. However, when these protocols are deployed in practice, a significant challenge is to ensure not just security but also privacy throughout these protocols' lifetime. As computer-based devices are more widely used and the Internet is more globally accessible, new types of applications and new types of privacy threats are being introduced. In addition, user privacy (or equivalently, key privacy) is more likely to be jeopardized in large-scale distributed applications because the absence of a central authority complicates control over these applications. In this dissertation, we consider three relevant cryptographic protocols facing user privacy threats when deployed in practice. First, we consider matchmaking protocols among strangers to enhance their privacy by introducing the "durability" and "perfect forward privacy" properties. Second, we illustrate the fragility of formal definitions with respect to password privacy in the context of password-based authenticated key exchange (PAKE). In particular, we show that PAKE protocols provably meeting the existing formal definitions do not achieve the expected level of password privacy when deployed in the real world. We propose a new definition for PAKE that is tightly connected to what is actually desired in practice and suggest guidelines for realizing this definition. Finally, we answer to a specific privacy question, namely whether privacy properties of symmetric-key encryption schemes obtained by non-tight reduction proofs are retained in the real world. In particular, we use the privacy notion of "multi-key hiding" property and show its non-tight relation with the IND$-CPA property of symmetric-key schemes. We use the experimental result by Gligor et al. to show how a real attack breaks the "multi-key hiding" property of IND$-CPA symmetric-key encryption schemes with high probability in practice. Finally, we identify schemes that satisfy the "multi-key hiding" and enhance key privacy in the real world.