There is a seemingly counterintuitive idea from theoretical computer science where two strangers combine their expertise without disclosing any personal information to each other. This is the concept behind homomorphic encryption and it is fueling what many are calling the next revolution in technology. Using the same logic, two governments may check whether they've been hacked by the same opponent without disclosing sensitive information, or two banks can check if they're being defrauded by the same person without violating federal regulations protecting sensitive customer information.
"Privacy-enhancing technology" is a catch-all word for the new cryptographic methods that allow you to share data while keeping it secure. They allow data owners to share information in novel and helpful ways. If we take the healthcare industry as an example, there are stringent regulations that prevent hospitals from exchanging patients' medical records. But if hospitals could pool their data into larger datasets, physicians would have access to more information and be able to make more informed treatment decisions. Indeed, beginning June 2022, a study in Switzerland using privacy enhancing technologies (PETs) has allowed medical researchers at four different teaching hospitals to undertake an analysis on their combined data of roughly 250,000 patients without any loss of privacy between institutions.
At the heart of privacy enhancing technologies, we find homomorphic encryption and secure multi-party computation.
Interest and necessity drive further developments in homomorphic encryption
“When looking at the current state of homomorphic encryption (HE), it is important to understand where we were just over a decade ago,” says Panagiotis Rizomiliotis, Assistant Professor at Harokopio University in Athens, Greece. It was just 2009 that Craig Gentry demonstrated how HE could be implemented based on the theorydeveloped by Dertouzos, Rivest and Adleman in 1978.
The performance of homomorphic encryption is becoming 10 times faster every two years. This is due to the increased interest and investment in this technology, and it also helps many organizations meet stringent regulatory compliance requirements around personal and sensitive data protection. Hence, many technology institutions, like DARPA, and technology companies like Microsoft and Intel are investing heavily because they realize the benefits HE has for the academia, law enforcement, and society as a whole.
Survivors of sexual assault can use a database maintained by the organization Callisto to record their information and that of their attacker, including the latter's name, address, and contact information (such as social media handles and phone numbers). The information is encrypted to safeguard it from tampering. If two victims name the same culprit, however, the system recognizes a match and notifies the respective attorney through email. The name of one of the surviving individuals are given to each of the attorneys (but not the name of the perpetrator). The attorneys then get in touch with the survivors to inform them of the match and offer their services as case coordinators if the survivors decide to take legal action. In a nutshell, Callisto provides a new level of anonymity to sexual assault victims by letting them check to see if their abuser is a repeat offender without having to reveal their own identities to the authorities.
“Survivors can find it healing to know they are not the only one. They don’t feel it is their fault,” says Tracy DeTomasi, Callisto CEO. And there is strength in numbers. “Maybe one person doesn’t have a case, but two people do.”
Barriers in HE development and implementation
“Despite the progress made in accelerating HE, performance is still an obvious barrier compared to other encryption algorithms,” notes Professor Rizomiliotis. “Even if HE is made to be two times slower that other known encryption schemes, this is a disadvantage. However, performance is not an absolute value,” explains Rizomiliotis. When discussing about performance, it is essential to consider it in the framework of the use case.
“However, a barrier that is often underestimated is the high storage overhead associated with HE,” notes Professor Rizomiliotis. Storing HE ciphertexts of state-of-the-art HE schemes and implementations, such as in Microsoft SEAL library incurs a blowup in storage size compared to storing the data in cleartext or encrypted by standard schemes such as AES. “Although storage costs are quickly declining, the problem is how to transfer this data from one point to another,” explains Rizomiliotis.
Homomorphic encryption applications
Besides the two use cases mentioned earlier in this article, there are many more applications. For example, Microsoft has done extensive research on what is known as Private Set Intersection (PSI). “PSI is a secure multi-party computation cryptographic technique that allows two parties holding sets to compare encrypted versions of these sets to compute the intersection. Neither party reveals anything to the counterparty except for the elements in the intersection,” explains Professor Rizomiliotis.
Microsoft uses fully homomorphic encryption to construct a fast PSI protocol with a small communication overhead that works particularly well when one of the two sets is much smaller than the other and is secure against semi-honest adversaries. The tech company has already implemented PSI in their Edge browser, in a feature called Password Monitor.
“The feature notifies users if any of their saved passwords have been found in a third-party breach. All this is done while ensuring Microsoft doesn’t learn the user’s passwords. The underlying technology ensures privacy and security of the user’s passwords, which means that neither Microsoft nor any other party can learn the user’s passwords while they are being monitored,” reads a Microsoft Research blog.
“In addition, the growing interest and demand for more private and secure approaches to Artificial Intelligence (AI) is driving growth in Homomorphic Encryption,” notes Rizomiliotis. Regulators are regulating AI in new ways, and HE may allow companies to better comply with those regulations. Very large markets, especially healthcare and public safety, are highly sensitive to AI’s implications for privacy and security, and they are beginning to investigate HE to address these concerns.
Meet the twin of HE—secure multi-party computation
“HE cannot deliver its promises if it is not examined together with secure multi-party computation (MPC),” explains Professor Rizomiliotis.
In MPC, two or more parties would like to jointly compute a function on their inputs, while keeping these inputs private. The first attempt to realize MPC is the one by Yao in 1982, who proposed a two-party computation protocol to solve its famous Millionaires’ problem: two or more millionaires would like to learn who among them is the richest, without revealing to the others the money they own.
And if HE and MPC appear to be formidable on their own, one can only imagine what will occur if they join forces. A few practical instances already exist in the literature, while numerous theoretical concerns remain unsolved. Concerning the practical ones, there are already constructs that combine MPC with (additive) homomorphic encryption: in these circumstances, homomorphic encryption is used as a subroutine to generate correlated randomness, which is important in the so-called online phase. In schemes supporting multi-key capabilities, HE can also become "multi-party"; e-voting schemes are a practical implementation of this technology.
In a world where privacy is engrained in every facet of our digital lives, having the ability to use big data and AI securely will drive the developments in technology and encryption. I would like to take this opportunity to thank Panagiotis Rizomiliotis for the discussion and insights on HE and MPC.
Related posts
