Understanding Homomorphic Encryption and its Significance to the Elusiv Stack
Background
Asymmetric cryptography, also known as public-key cryptography, is a cryptographic approach that employs two interlinked keys for each user: a public key, which can be shared freely, and a private key, which must remain confidential. These keys are produced through cryptographic techniques grounded in mathematical challenges known as one-way functions. The effectiveness of asymmetric cryptography hinges on the private key’s confidentiality; sharing the public key doesn’t jeopardize the security. Anyone possessing the public key can generate a ciphertext by encrypting a message. Decrypting the ciphertext and extracting the original message requires the private key.
Although this can be useful, it possesses a lot of caveats. To process encrypted data, we need to decrypt it first. Leaving it exposed and potentially compromising its security. In conditions like cloud computing, this can result in data leaks since data needs to be processed by untrusted third parties.
Fully Homomorphic Encryption (FHE) emerges as a groundbreaking solution to this predicament. With FHE, computations can be performed directly on the encrypted data, eliminating the need for decryption during operations and thus maintaining the data’s confidentiality throughout the entire process. This evolution in encryption technology ensures not only the integrity of the data at rest but also during computation, paving the way for a more secure digital age.
Homomorphic encryption enables computations on encrypted data without requiring decryption. This produces an output identical to one generated from operations on the unencrypted data. Consequently, businesses can outsource data processing to third parties without entrusting them with the data’s security, provided these entities lack the decryption key. Furthermore, this encryption approach safeguards private data from hackers, even in instances of privilege escalation, ensuring the data remains secure.
Applications
The capability to process encrypted data can address numerous pressing challenges that businesses across various industries encounter.
In the healthcare domain, the utilization of homomorphic encryption is prominent in predictive analytics and machine learning. This is largely because entrusting third-party service providers with medical data poses significant privacy concerns. With homomorphic encryption, the need to process unencrypted data diminishes, mitigating associated privacy risks.
In the broader corporate world, businesses often collaborate with external stakeholders, ranging from suppliers and partners to various other contributors. These entities inevitably need access to a company’s sensitive data. Given that cybercriminals typically exploit the most vulnerable points in a system, sharing private data with third parties can potentially result in a devastating breach. However, with homomorphic encryption, the shared data remains encrypted. As a result, even in the event of a data breach, the company’s information remains uncompromised.
The data protection regulation landscape is very complex. The General Data Protection Regulation (GDPR) set new rules for EU countries stating that the data of EU citizens remains within the EU (or countries/companies with equivalent data security standards). This caused many problems for US companies with EU citizens. These requirements do not apply to encrypted data. Homomorphic encryption allows US companies to store and process data outside the EU and then only decrypt it on server locations that comply with GDPR EU regulations.
Homomorphic encryption offers a promising solution for enhancing election security. Take Microsoft’s ElectionGuard as an example. This tool employs homomorphic encryption to guarantee the integrity of voting outcomes. After casting their votes, voters receive unique tracking codes. These allow them to verify that their votes have been correctly accounted for while ensuring their choices remain confidential. Intriguingly, with homomorphic encryption, only the cumulative vote count can be decrypted, keeping individual voting choices concealed.
Homomorphic encryption also has applications in video security. For example, organizations can apply it to view encrypted streams of surveillance videos from public spaces. With this technology, all parts of the footage can be decrypted except for a boxed area around each individual’s face, for which the decryption key isn’t provided. This ensures that organizations can monitor activities without compromising personal identities.
It’s also possible to decrypt only the final tally through homomorphic encryption without seeing information about how individual voters cast their ballots.
Types of homomorphic encryption
Partially Homomorphic Encryption
Partially Homomorphic Encryption (PHE) refers to those encryption methodologies limited to a single type of mathematical gate, such as addition or multiplication. Such schemes permit unlimited repetitions of that specific operation. While this specificity constrains the range of potential applications, crafting partially homomorphic encryption algorithms is notably straightforward.
PHE was first Introduced in 1978 by Rivest, Shamir, and Adleman. RSA exemplifies multiplicatively homomorphic properties. This characteristic of RSA stems from its encryption principle centered on exponentiation: C = (m^x) mod n, where ‘m’ signifies the message and ‘x’ represents the secret key.
A quintessential instance of an additive partially homomorphic system is the Paillier cryptosystem (1999), rooted in public key cryptography. Another example is ElGamal cryptosystem (1985).
PHE comes with certain restrictions regarding gate operations. It permits either addition or multiplication but not a combination of both. This limitation can be problematic in scenarios where the simultaneous use of both gates is essential.
Somewhat Homomorphic Encryption
Somewhat homomorphic encryption (SHE) expands the scope by encompassing two types of gates in the circuit; however, it restricts the total number of permitted operations. A critical limitation of such encryption approaches is the ‘multiplicative depth’. Multiplicative depth measures the peak number of multiplicative operations that a somewhat homomorphic encryption is structured to handle. This is due to the accumulation of “noise” during computations on encrypted data.
Yet, despite these constraints, the practical utility of somewhat homomorphic encryption becomes evident in cases where the number of multiplications is low or known in advance.
Serving as a pivotal intermediary stage, somewhat homomorphic encryption algorithms play a significant role in the evolution towards achieving fully homomorphic encryption capabilities. The challenge intensifies when creating an algorithm versatile enough to accommodate both additive and multiplicative operations, especially when contrasted with algorithms singularly focused on boundless addition or multiplication of encrypted data.
Fully Homomorphic Encryption
Fully homomorphic encryption (FHE) stands as the pinnacle of homomorphic encryption. Characterized by its unparalleled flexibility, an FHE algorithm facilitates boundless additions or multiplications on ciphertexts, ensuring consistently accurate outcomes.
The journey towards realizing FHE bore fruit when Craig Gentry pioneered the first fully homomorphic encryption algorithm in 2009. This groundbreaking discovery catalyzed further research, leading to the emergence of enhanced algorithms that built upon Gentry’s foundational work.
How to choose the right scheme
Different FHE schemes exhibit unique characteristics tailored to specific computational and security requirements. Choosing an appropriate scheme hinges on the balance between desired computational efficiency and noise management. While some schemes focus on faster operations with rapid bootstrapping, others prioritize noise reduction for sustained computations. The choice should align with the specific demands of the application and the desired trade-offs between speed and noise resilience. We will go through different criteria for picking the right scheme in future articles.
Tools
SEAL
The Microsoft SEAL, crafted by Microsoft’s Cryptography and Privacy Research Group, is a user-friendly, open-source homomorphic encryption library under the MIT license. Developed using contemporary standard C++, it can be effortlessly compiled and executed across various platforms. For detailed insights into the Microsoft SEAL initiative, visit sealcrypto.org.
Features:
- Provides a high-level API to enable developers without deep cryptographic knowledge to utilize homomorphic encryption.
- It supports multiple encryption parameters, allowing for a balance between security and performance.
- Written in C++ but has .NET wrappers for integration with other platforms.
OpenFHE
OpenFHE is an open-source initiative offering efficient and adaptable implementations of top-tier post-quantum FHE algorithms.
Designed for both usability and speed, OpenFHE features user-friendly APIs, modularity, and compatibility across platforms while also integrating hardware accelerators. It adheres to the post-quantum security standards set by HomomorphicEncryption.org for homomorphic encryption. OpenFHE is available under the 2-clause BSD open-source license, facilitating its inclusion and redistribution in various products.
OpenFHE encompasses all primary FHE methods such as BGV, BFV, CKKS, DM (FHEW), and CGGI (TFHE) which we will go through in more detail in future articles. It supports multiple bootstrapping approaches, with ongoing development focused on enhancing bootstrapping efficiency.
Features:
- Offers a rich set of operations over encrypted data.
- Built with performance in mind, allowing for efficient computations.
- Written in C++.
TFHE-rs
TFHE-rs offers a comprehensive Rust-based implementation of TFHE, catering to Boolean and integer calculations on encrypted data. It features APIs for both Rust and C, along with a client-side WASM API. Ideal for developers and researchers, TFHE-rs grants extensive control over TFHE functionalities without the complexities of its underlying implementation. The objective is to present a robust, straightforward, high-efficiency library fully harnessing TFHE’s advanced capabilities.
Features:
- - Leverages the strong type system and memory safety features of the Rust programming language.
- Provides bindings and API for integration with other systems.
- Written in Rust.
Sunscreen
Sunscreen serves as a comprehensive framework for crafting applications that prioritize privacy through fully homomorphic encryption, with plans to integrate zero-knowledge proofs in the future. FHE stands out as a unique encryption method, enabling computations directly on the encrypted content. Recognizing the challenges in penning FHE programs, we’ve introduced a “compiler” to simplify the endeavor for developers.
Features:
- Addresses the challenges faced by previous FHE compilers, ensuring reduced performance overhead and enhanced user-friendliness.
- Streamlines the FHE program creation process by automatically managing intricate parameters and keys.
- Seamlessly conceals the complexities of polynomials, circuits, and parameter choices, allowing users to focus on their core tasks without getting bogged down in the details.
- Written in Rust.
Challenges
FHE possesses the potential to address an array of pressing business quandaries. Given its existence and capabilities, it seems poised to be ubiquitously adopted.
Yet, why is its widespread application still elusive? (no pun intended)
The crux of the challenge with contemporary FHE lies in its operational efficiency. While its design ensures full homomorphism — permitting boundless additions or multiplications on ciphertexts without compromising the integrity of the result — it concurrently imposes significant computational demands. Consequently, these algorithms often manifest sluggish performance and require substantial storage resources.
Another hurdle in the realm of homomorphic encryption is that the quest for both usability and interoperability is stymied by the absence of unified frameworks, tools, protocols, and benchmarks dedicated to homomorphic encryption. Additionally, venturing into homomorphic encryption can open Pandora’s box of legal, ethical, and societal challenges, encompassing topics like data proprietorship, informed consent, responsibility, and establishing trust.
A third intricacy associated with homomorphic encryption lies in maintaining its security and ensuring its accuracy. For instance, certain techniques that provide full homomorphism often necessitate strategies like bootstrapping for noise management, ensuring ciphertexts remain valid and uncorrupted. Additionally, challenges like increasing ciphertext sizes and the complexities introduced by underlying mathematical constructs, such as the Ring Learning With Errors (Ring-LWE) problem, further amplify the intricacies of ensuring optimal security and accuracy.
Elusiv use cases
Secure multi-party computation (MPC) is a subfield of cryptography that aims to perform collaborative computation on inputs while keeping those inputs private. Elusiv works on a particular implementation of MPC called SPDZ. SPDZ protocol consists of a preprocessing phase independent of the function to be computed and of the inputs and a much more efficient online phase where the actual computation occurs.
Elusiv utilizes FHE for the SPDZ Minimal Viable Product (MVP) implementation. Specifically, when the SPDZ protocol is applied, all parties first encrypt their input under the FHE scheme; then, they evaluate the desired function on the ciphertexts using the homomorphic properties, and finally, they perform a distributed decryption on the final ciphertexts to get the results. The advantage of the FHE-based approach is that interaction is only needed to supply inputs and get output.
A bright future for homomorphic encryption
Homomorphic encryption has shown promising advancements in recent years. Groundbreaking work by researchers and tech giants like IBM and Microsoft has significantly accelerated its processing speeds, with platforms like SEAL and HElib making considerable strides. While there’s room for improvement, ongoing research, and further standardization suggest a bright future for fully homomorphic encryption. In the blockchain space specifically, homomorphic encryption is imperative for solving the pervasive privacy challenges plaguing the technology. As technology evolves, there’s optimism that this encryption format could revolutionize Web3 data security in the coming years.
As such, Homomorphic Encryption is vital in our innovative Multiparty computation Execution Environments (MXEs). MXEs facilitate calculations on encrypted data without revealing the data’s content or the computation’s result. However, certain parts of the output may become decrypted under specific conditions, making this approach even more powerful than solely using computations on (fully) homomorphically encrypted data, which cannot self-decrypt the output. This advanced capability is achieved by integrating secure MPCs combined with FHE, threshold secret sharing, and distributed key generation (DKG) which we will release more details about in upcoming articles.
Stay tuned
Stay updated on Elusiv’s journey by following us on X and signing up for our newsletter. If you are looking to get involved or ask questions, join our community on Discord! We look forward to an exciting road ahead.