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 principle forms the basis of secure multi-party computation and is the same concept behind homomorphic encryption. Iit 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 theory developed 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 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 is 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.”
CIO Study: Outages Escalating with Massive Growth in Machine Identities
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 than other known encryption schemes, this is a disadvantage. However, performance is not an absolute value,” explains Rizomiliotis. When discussing 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
In addition to the two applications highlighted earlier in this article, numerous other uses exist. For instance, Microsoft has conducted thorough research on a technique known as Private Set Intersection (PSI).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 develop a PSI protocol that is not only fast but also has minimal communication overhead. This protocol is particularly effective when one set is significantly smaller than the other and maintains security against semi-honest adversaries. Microsoft has integrated this technology into their Edge browser through a feature named 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 Multi-Party Computation (MPC), multiple parties aim to collaboratively compute a function using their respective inputs, while ensuring the privacy of these inputs. The initial endeavor to implement MPC was by Yao in 1982. He introduced a protocol for two-party computation aimed at resolving what is known as the Millionaires’ problem: a scenario in which two or more millionaires wish to determine who is the wealthiest among them without disclosing their individual wealth to each other.
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 ingrained 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.
Elevate Your Data Security with Venafi's Zero Touch PKI:
Enable the full potential of your data security strategy with Venafi's Zero Touch PKI solution. Discover how homomorphic encryption and secure multi-party computation can revolutionize the way you protect sensitive information. With Venafi's advanced technology, you can ensure that your data remains encrypted and secure, even during processing and collaboration. Say goodbye to vulnerabilities, and hello to a new era of data protection!