Return to Microsoft Research Lab – Redmond

Cryptography and Privacy Research

These are project we are not actively working on, but that we continue to maintain and support.

Homomorphic Encryption

(Fully) Homomorphic Encryption (HE or FHE) refers to a class of encryption methods that allow computing on encrypted data without decryption. It keeps data private from the party who performs computation, i.e., enables privacy-preserving (outsourced) computation. As all modern encryption schemes, homomorphic encryption is randomized: encrypting a particular value multiple times results always in different encryptions. The encryption can be reversed only with the secret key. “Homomorphic” refers to a mathematical concept, indicating that some operations on ciphertexts reflect to some operations on the underlying plaintexts. For example, the user can encrypt two numbers, compute a sum-like operation on the ciphertexts, and decrypt the result to obtain the sum of the plaintext numbers.
Computing on encrypted data, followed by decryption, yields the same result as computing on unencrypted data.

There have been many instantiations of homomorphic encryption, varying in types of supported computations, run-time performance, and application development effort. The most popular ones are Brakerski-Fan-Vercauteren (BFV), Brakerski-Gentry-Vaikuntanathan (BGV), and Cheon-Kim-Kim-Song (CKKS). BFV and BGV precisely preserve operations and are suitable for database retrieval or string matching, while CKKS approximately preserves operations and is preferred when processing floating-point data. All of these schemes base their security on a mathematical hard problem known as Learning with Errors (LWE), which is also the security foundation of many post-quantum cryptographic schemes currently being considered for recommendation by NIST.

Microsoft SEAL

Microsoft SEAL is a production-quality homomorphic encryption library that the Cryptography and Privacy Research Group has been building since 2015. It is actively maintained, supports multiple platforms, and currently implements the BFV, BGV, and CKKS schemes.

Homomorphic encryption can be conceptually difficult to learn and writing applications using the CKKS scheme API in Microsoft SEAL can be very challenging. To address this, we have created EVA, a language a compiler, for the CKKS scheme.


In 2017 we launched together with partners from industry, academia, and government, a community standardization effort that is today known as The community standard sets recommendations for secure parameters that are now used by multiple implementations and contributed to the upcoming ISO/IEC standard on fully homomorphic encryption (ISO/IEC 18033-8).

Private Set Intersection

Private Set Intersection (PSI) often refers to a group of multiple related functionalities. In its simplest form, PSI allows two distrusting parties to find the intersection of their private sets of “items” (strings, multi-precision integers, documents) without revealing any other information to each other. Variants of PSI target scenarios with roughly equally sized sets (symmetric PSI), very unequally sized sets (asymmetric PSI), retrieval of data corresponding to items in the intersection (labeled PSI), or post-processing on the intersection, e.g., returning the sum of values in the intersection (PSI with post-processing).

PSI can be realized by orchestrating multiple cryptographic primitives to achieve different variants with performance/communication trade-offs. For example, homomorphic encryption can provide communication-efficient solutions in the asymmetric case where one set is very small while the other is very large, even up to billions of elements, whereas such a solution would be completely impractical when both sets have size in the millions.


APSI is a library we built for asymmetric (labeled) PSI. It allows a client to look up the presence of a relatively few (tens of thousands) of items from a much larger database held by a server, and for those items that are found, optionally retrieve data the server has associated to them. The entire operation reveals nothing to the server, except that a query was performed, and the client learns nothing beyond what the functionality indicates. Edge Password Monitor uses APSI to provide an efficient and secure way to detect whether Edge users’ credentials are found in Microsoft’s database of breached credentials. APSI is implemented using Microsoft SEAL.