Second homomorphic encryption standardization workshop delivers the goods

Published April 10, 2018

By Kristin Lauter , Principal Researcher and Partner Research Manager

Share this page

Group photo of the Second Homomorphic Encryption Standardization Workshop at the MIT Stata Center

What an exciting two days at the Second Homomorphic Encryption Standardization Workshop (opens in new tab) at Massachusetts Institute of Technology. More than 70 participants from 10 countries gathered together for two intense days of panels, discussions and planning and walked away with a significant milestone: the first draft standard for homomorphic encryption, Homomorphic Encryption Standard Section 1.0 and Homomorphic Encryption Standard Section 2.0 (opens in new tab). HES 1.0 standardizes the encryption schemes and HES 2.0 recommends parameter choices to achieve security. One participant characterized the gathering perfectly, “It’s hard to imagine how the workshop could have possibly gone better.”

For a decade now, researchers at Microsoft, IBM and in academia and government have been developing practical solutions for homomorphic encryption (HE). HE protects data by encrypting it but still allows for meaningful computation on the encrypted data. This enables private cloud storage and private Artificial Intelligence because data can be securely stored and crunched in an encrypted state without decrypting it.
Many people don’t realize how many different tasks and types of computation, data analytics and machine learning models have already been demonstrated to achieve practical performance on encrypted data using HE.

Standardization is crucial to advancing commercial deployment of new cryptographic schemes and primitives. For the public, industry and government to trust in a new cryptosystem, common practice requires an open forum for describing the schemes, security models and the best-known attacks. Security models capture the essence of the trust model and the capabilities an adversary may possess. Attacks are usually mathematical algorithms that solve the hard problem within a predictable running time. In order to be relevant for secure cryptosystem deployment, predictions of the running times need to be concrete and precise, including specifying the constants. Historically, new cryptosystems have been standardized through a combination of industry coalitions and consortia, academic professional societies and government agencies. Once standardization of a cryptographic technology is in place, an accreditation process can be built up where third-party vendors attest to the fidelity, robustness and quality of a software implementation with respect to the standard. This is how public trust is won.

Group photo of the First Homomorphic Encryption Standardization Workshop at Microsoft, July 2017

Things are progressing rapidly. The first Homomorphic Encryption Standardization Workshop (opens in new tab) was hosted less than a year ago by MSR Outreach at Microsoft and co-organized with Lily Chen, the leader of the Cryptography Group at National Institute of Standards and Technology. Several dozen invited expert participants collaborated to produce three white papers on security, API design and applications. These papers (opens in new tab) were made public two weeks after the workshop. The purpose of these white papers was to gather the collective knowledge of the research community on the state of the art of practical homomorphic encryption. Six teams from around the world demonstrated software libraries or tools for HE at the workshop, and all six teams used roughly the same underlying hardness assumption, encryption schemes and parameters. The time was ripe to describe these schemes and security parameters and levels in the security white paper (opens in new tab).

The hard problem underlying the security of HE is related to decades-old problems on lattices, variants of the so-called Shortest Vector Problem (SVP). A lattice can be thought of as a discrete linear subspace of continuous space. The hard problem is to find a secret vector, given a collection of many “noisy’’ inner products of the secret with random vectors; a small Gaussian noise is added to the inner product each time. If it is easy to remove or cancel out the noise from each sample, then the secret could be revealed through linear algebra calculations on the collection of inner products with the secret vector. Knowing a short basis for the lattice can help remove the noise from the samples and thus the relation with the SVP problem.

Over the past decade, concrete estimates for the running times of various lattice reduction algorithms to find short vectors have been developed through a combination of theory and experimentation. A tool for estimating the security of a lattice-based cryptosystem for a given set of parameters was developed by Martin Albrecht (RHUL) and is publicly available online. This Estimator (opens in new tab) was used to compute tables of recommended parameters for Homomorphic Encryption achieving 128-bit security levels and higher. We expect these parameters to provide the predicted level of security against classical and quantum attacks, unless new unforeseen attacks emerge. For that reason, homomorphic encryption is also referred to as a post-quantum encryption scheme because it is not vulnerable to polynomial-time quantum attacks.

Based on the discussion at the wrap-up session of the 2017 workshop, an open-community consortium was formed: HomomorphicEncryption.org (opens in new tab), with a web page, a mailing list and a working group that dedicated itself to transforming the white papers into a standard for HE. More than 200 researchers world-wide have joined the mailing list in the last six months!

A sampling of the more than 50 signatories to the Homomorphic Encryption Standard (HES)

The first step was to get broad agreement on the security of the underlying schemes and parameter choices, hence the top priority of this year’s workshop – that of approving the draft security standard, specifying the encryption schemes and security levels. This goal was accomplished on day one, with more than 50 co-signers, while day two was devoted to the second goal: standardizing the API design in the next iteration of the standard. The workshop also included a keynote, two panels on applications of HE in industry and government and in Health, and short technical talks. Day one concluded with a reception doubling as a poster and demo session with 12 demos, including SEAL (opens in new tab), the widely used HE library from Microsoft Research, and other libraries and projects such as PALISADE (opens in new tab), cuHE (opens in new tab), HeaAn (opens in new tab), and HELib (opens in new tab).

For the keynote, Turing Award winner Shafi Goldwasser reprised her recent congressional briefing on cryptography. The Applications in Industry and Government panel featured speakers from Samsung, Microsoft, Duality and the U.S. Navy. The Health Privacy panel included presentations from National Institutes of Health (NIH), the Medco project at EPFL, the iDASH project on Secure Genome Analysis, and Microsoft. Funded by NIH, iDASH has been running international competitions for the past five years to benchmark encryption technologies for privacy-preserving genome analysis. Tasks have included training machine learning models on encrypted genomic data, statistical analysis for Genome-Wide Association Studies (GWAS) and encrypted database search. Day 2 concluded with short technical talks and a wrap-up session to plan next steps.

Health Privacy Panel led by Heidi Sofia from National Institutes of Health (NIH)

Looks like the third HE workshop will be in October where participants hope to approve the draft standard for API design. See you there!

Organizers: Vinod Vaikuntanathan (MIT), Jung Hee Cheon (SNU), Kurt Rohloff (NJIT), and Kim Laine, Kristin Lauter and Roy Zimmermann (Microsoft Research).

Workshop Sponsors: Microsoft, MIT, Duality Technologies, and NJIT