How Microsoft Edge Uses Fully Homomorphic Encryption to Secure Your Passwords

In January 2021, Microsoft introduced a powerful privacy-preserving feature in its Edge browser: a password manager powered by Fully Homomorphic Encryption (FHE). This marked a significant milestone—the first known consumer deployment of FHE technology. The goal? To let users check if their saved passwords have been involved in known data breaches, without ever exposing those passwords to Microsoft or anyone else.

This article unpacks how this system works, the role of homomorphic encryption, and the technical innovations that make it scalable and secure.

---

The Privacy Problem: Password Breach Detection Without Exposure

Typically, checking if a password is compromised requires sharing it—either in plaintext or hashed form—with a central service. This approach raises critical privacy concerns, especially if the password is reused across services (a common user behavior). Microsoft tackled this challenge by integrating FHE, which allows encrypted queries and encrypted responses.

---

How the Edge Password Manager Works

The FHE-based system can be summarized in the following key steps:

1. User Action: The user creates or saves a password in Microsoft Edge.
2. Password Encryption: The password is encrypted using FHE within the browser.
3. Encrypted Query: The encrypted password is sent to a Microsoft server to check against a database of breached credentials.
4. Homomorphic Evaluation: The server evaluates whether the encrypted password matches any in the database—without ever decrypting the password.
5. Encrypted Response: The result (Yes/No) is returned, still encrypted.
6. User Notification: Only the user’s browser decrypts the result and informs them if their password was compromised.

Neither Microsoft nor any third-party can access or infer the actual password or the result of the query.

---

Adversary Model

The security model considers two main adversaries:

• The Server: Microsoft or any cloud infrastructure that handles encrypted queries must not learn user passwords or usernames.
• Eavesdroppers: Network-based attackers capable of observing encrypted traffic must also be unable to infer passwords or query results.

This is achieved by encrypting both the query and the response, ensuring that even metadata leakage is minimized.

---

Technical Implementation

Three parties are involved in the full setup:

1. User/Browser (Edge)
2. Password Service (Microsoft)
3. Breach Database

Here’s a deeper look at how credentials are handled:

• A hash function, known only to Microsoft, transforms the password into a pseudorandom value.
• Using an oblivious pseudorandom function (OPRF) protocol, the password is hashed without revealing either the password or the hash function.
• The resulting hash is encrypted with FHE and sent to the server.
• The server runs a ComputeMatch algorithm that searches the database for a match — on encrypted data.
• The encrypted response is sent back to the browser for decryption.

This architecture ensures zero knowledge of both query and result for the server and any potential eavesdroppers.

---

Optimizations for Scalability

FHE operations are computationally intensive, but Microsoft made the system viable for real-world use by addressing two core challenges:

1. Database Size

The breach database is large, so to reduce computation, it is partitioned by the first two bytes of the hashed username. This significantly narrows the search space for each query.

2. Device & Network Compatibility

Since users operate on diverse devices (mobile, desktop, tablets), the implementation is:

• Lightweight in terms of network bandwidth
• Optimized for low CPU and battery usage
• Cross-platform compatible

These performance-conscious design choices enable Edge to run this FHE process seamlessly across environments.

---

Underlying Technology: Private Set Intersection with FHE

The cryptographic technique behind this solution is a variant of Private Set Intersection (PSI) using FHE. PSI allows two parties to determine the intersection of their data sets without revealing any other elements. In this case, the sets are:

• The user’s password (hashed and encrypted)
• The server’s breached password database

The innovation lies in applying PSI within the homomorphic encryption framework—securely, and without revealing any plaintext.

---

Why This Matters

This application represents a paradigm shift in how privacy can be preserved at scale:

• Users stay protected from password reuse attacks.
• Microsoft never sees users’ credentials.
• Attackers (internal or external) gain no insight from observing the system.

As Erin Hales noted in a recent expert interview, the Edge password manager is one of the first large-scale deployments of FHE in a consumer product, and a prime example of how this once-theoretical technology is becoming real.

---

What’s Next?

FHE is poised for broader adoption as its efficiency improves. Beyond password management, it is already being explored in:

• Healthcare analytics
• Secure financial computations
• Privacy-preserving machine learning