Authored by Riley Wong, Emergent Research, July 2025.
A PDF version of this report can be found here.
Abstract
Multi-party fully homomorphic encryption (MP-FHE) combines the strengths of multi-party computation (MPC) with fully homomorphic encryption (FHE), making it possible to collaboratively compute on encrypted data without revealing private inputs nor requiring a trusted third party. Benefits of MP-FHE include distributed trust, privacy, and quantum-resistance, and can be used currently for applications such as privacy-preserving machine learning, distributed data analytics, encrypted decision making, and more. MP-FHE is still considered a relatively new field in cryptography and would benefit from further optimizations given its computational intensity and coordination between parties, as well as further developments in library and developer support. New paradigms for what can be possible with MP-FHE in the broader world of programmable cryptography have yet to be fully explored.
Acknowledgements
Special thanks to Pia Park, Janabel Xia, Michele Orrù, Violet Vienhage, Aayush Gupta, and Yuki Yuminaga for their insightful comments, discussions, and feedback, and to Fenbushi Research for their grant support! ❤
Introduction
Fully homomorphic encryption (FHE) is a cryptographic scheme that makes it possible to compute on encrypted data. Multiparty computation (MPC) is a cryptographic protocol that allows multiple parties to jointly compute while keeping their data private, and often needs more than one round of communication. Multi-party fully homomorphic encryption (MP-FHE) combines these techniques for multiple parties to jointly compute encrypted data with minimal interaction.
A main benefit of MP-FHE over just FHE includes distributing decryption keys, which can be beneficial for security purposes as it reduces single points of failure and can decentralize trust. A main benefit of MP-FHE over just MPC means that the data existing in an encrypted state allows for fewer rounds of interaction and can be beneficial for scaling up for more parties. In short, MP-FHE benefits from the non-interactive and scalable features of FHE as well as the distributed security of MPC. MP-FHE offers strengths in providing distributed or decentralized architecture; trust and security benefits; and opportunities for collective governance mechanisms.
General practical use cases for MP-FHE may include scenarios that involve private data being distributed or computed among multiple parties, such as: private set intersections; privacy-preserving machine learning without revealing private data; privacy-preserving similarity calculations for private encodings; privacy-preserving data analysis for jointly computing aggregate statistics.
Examples of real world use cases for MP-FHE may include: privacy-preserving voting for citizen elections; training machine learning models while keeping individual health records private; privacy-preserving workplace abuse reporting; or private smart contracts and decentralized financial transactions.
In its current state, there exist a small handful of implementations, namely through the Lattigo and OpenFHE libraries. MP-FHE is still relatively nascent as a technology and undergoing active research; can be computationally expensive in its present state; and is considered quantum-safe when using lattice-based schemes. Novel use cases and applications for MP-FHE have yet to be fully explored.
Secure Multi-Party Computation (SMPC)
Secure multi-party computation (SMPC, or MPC) is a cryptographic technique that allows multiple parties to jointly compute a function over their private inputs. The parties can see the result of the computation without ever needing to reveal their data to one another.
Mathematically, we may frame MPC as a problem involving n parties P₁, P₂, … , Pₙ, where each party Pᵢ holds a private input xᵢ, with the goal for all parties to compute a function f (x₁, x₂, …, xₙ) = y.
The main flow of secret sharing-based multi-party computation generally goes as follows:
- Offline phase:
a. Preprocessing: Multiplication triplets, message authentication codes, and random values used for masking inputs can be generated ahead of time to be used later, independent of inputs.
2. Online phase:
a. Distributed input shares: Each party splits their input data into secret-shares and sends them to the other parties.
- In math terms: each input xᵢ is split into shares [xᵢ]₁, [xᵢ]₂, …, [xᵢ]ₙ. These shares are distributed to the other parties.
b. Distributed computation: Each party runs a partial computation based on the partial secret-shares they’ve received.
- In math terms: Given that each party Pᵢ holds [xᵢ]₁, [xᵢ]₂, …, [xᵢ]ₙ, each party can evaluate f for their set of received distributed shares: f ([xᵢ]ᵢ, [x₂]ᵢ, …, [xₙ]ᵢ) = [y]ᵢ.
- The result of this partial computation [y]ᵢ is shared with other parties.
c. Output reconstruction: The result of the computation is constructed by combining each partial computation’s result.
- In math terms: Reconstruct([y]₁, [y]₂, …, [y]ₙ) = y = f (x₁, x₂, …, xₙ).
No single party learns the private inputs of the computation, nor the intermediate values; only the result.
Currently, the main approaches to multi-party computation are:
- Secret sharing (e.g. Shamir’s secret sharing, SPDZ)
- Garbled circuits
- Multi-party Fully Homomorphic Encryption (See: Multi-Party Fully Homomorphic Encryption (MP-FHE))
Shamir’s Secret Sharing (SSS)
In secret-sharing based protocols, each party splits their private input into separate shares and distributes these shares to the other parties. Then, each party computes on these collected shares, without knowledge of the original inputs. At the end, parties combine the resulting computation to reconstruct the full output.
Mathematically, a secret share can be thought of as a point on a polynomial curve of degree n. With n+1 points on the curve, we can reconstruct the polynomial curve using polynomial interpolation, such as Lagrange; otherwise, it would be mathematically impossible to reconstruct.
Shamir’s secret sharing is a foundational tool used in MPC, though it is not by itself a full MPC protocol, and may need additional protocols for securely evaluating functions, handling malicious adversaries, or verifying results from tampering or collusion.
SPDZ (Smart, Pastro, Damgard, Zakarias)
Named after the paper authors, SPDZ (pronounced “speedz”) is one of the most common protocols for multi-party computation, using secret sharing as a foundation for securely computing functions over shared values, even when malicious adversaries are present (i.e. the protocol remains secure even if some parties try to cheat).
It operates in two distinct phases: offline, which is computationally heavy and input-independent; and online, which is fast and input-dependent.
The general flow of SPDZ goes as follows:
- Offline phase / preprocessing: This step happens independent of the computation inputs and occurs before any parties input their private data.
a. The system generates multiplication triples, sets of values (a, b, c) such that c = a*b. These triples will be used later to quickly compute secure multiplications. Each triple is secret-shared among the multiple parties.
b. Parties also generate random values for masking inputs as well as message authentication codes (MACs) to ensure integrity and detect cheating.
2. Online phase:
a. Distributed input shares: each party uses random values from the preprocessing phase to mask their inputs, then splits their private inputs into random shares and distributes them to all parties. No single party can reconstruct the original inputs.
b. Distributed computation: Each party evaluates their shares using addition and multiplication, using the multiplication triples for multiplication operations and the MACs to authenticate operations for integrity.
c. Output reconstruction: Parties reconstruct the computation result by combining output shares and verify MAC checks.
Garbled Circuits
Garbled circuits are a separate cryptographic protocol from secret sharing that also allows two or more parties to jointly compute a function on private inputs without revealing these inputs to one another.
In a 2-party garbled circuit, one party, the garbler, represents the computation as an encrypted boolean circuit.
A boolean circuit is a circuit made up of logic gates (AND, OR, NOT, etc.) that take bits (0 or 1) as input and outputs the corresponding bit for that gate, and can represent computations using these binary operations. The boolean circuit can furthermore be represented as a truth table of 0s and 1s.
To encrypt the boolean circuit, the garbler replaces the truth table values with labels, represented by randomly generated strings, and encrypts the output entries in the table using these generated labels. The garbler then permutes, or “garbles,” the rows of the encrypted table. This garbled truth table represents an encrypted boolean circuit, which the garbler sends to the second party, along with the labels that represent her inputs.
This second party, the evaluator, then takes the input labels from the garbler, as well as the input labels of their own inputs using oblivious transfer, and evaluates the encrypted circuit.
Thus, the inputs and intermediate values are not revealed to either party. This process can be extended to multiparty scenarios using secret sharing, where instead of a single garbler, each of the multiple parties garbles a portion of the circuit.
(See Appendix: Garbled Circuits for a slightly more detailed explanation.)
Oblivious Transfer
In garbled circuits, the evaluator needs to give the garbler their inputs into the circuit, without revealing what those values are. Oblivious transfer is a fundamental building block of garbled circuits and allows this process of delivering encrypted input bits to happen privately and securely.
In “1-out-of-2” oblivious transfer, the sender has two messages, and the receiver picks one of the two to learn without revealing their choice. The sender learns nothing about the receiver’s choice, and the receiver learns nothing about the other message. This process makes it possible to securely evaluate an encrypted boolean circuit without revealing private inputs.
Threshold Decryption
Threshold decryption is a technique where no single party can decrypt a message, but multiple parties can collaborate to decrypt it together. While MPC frameworks could require all parties for decryption, threshold decryption is significantly more common given its benefits around availability, fault tolerance, or usability. For example, if some parties go offline, get disconnected, crash, have high latency or downtime, or are malicious or adversarial, the MPC decryption can still succeed.
Table: Existing MPC Libraries
Some notable open-source libraries for MPC include:
Library Links: SCALE-MAMBA, EMP-toolkit, MP-SPDZ, MPyC, MOTION, FANNG-MPC
Existing Applications and Challenges
Secure MPC has already been adopted at places like Signal and Coinbase, namely in their key recovery protocols. SMPC was also used by the Internet Security Research Group (ISRG) in their COVID-19 exposure notification system for analyzing privacy-preserving aggregate statistics from mobile devices.
Currently, MPC protocols still require heavy computational and communication overhead, as they often require multiple rounds of interaction between parties, and/or assume parties are online and synchronous in order to communicate between rounds. MPC protocols would also benefit from improvements in scaling as the number of parties increases; further research into security guarantees against malicious parties and/or collusion; and further developments in usability and developer support and tooling.
Fully Homomorphic Encryption (FHE)
Fully homomorphic encryption is a cryptographic technique that allows for computations on encrypted data, without ever decrypting it. This means that data can stay encrypted throughout the entire process, from rest, transfer, and computation, resulting in an encrypted result that can only be decrypted by the original party.
This makes it possible to provide private computations as a service. For example, a machine learning model may be trained and give predictions on fully encrypted data, resulting in encrypted outputs; I can give my private data to this model and benefit from its predictions without my private data ever being revealed or decrypted by the model.
As an example use case, I may want to use a translation service such as Google Translate. With an FHE translation service, I can run the translation model on encrypted text, keeping my encrypted input text private from the translation service providers.
At the moment, FHE is still very computationally expensive, and would benefit from both mathematical as well as hardware optimizations.
How do homomorphic encryption (HE) and fully homomorphic encryption (FHE) differ? Given the way HE works, noise builds up in the computations such that, after enough operations, the noise eventually makes the output undecryptable, adding a hard computational limit. FHE involves a bootstrapping step that resets this noise in the process, making it possible to continue operations indefinitely.
Many FHE schemes rely on lattice-based constructions called Learning With Errors (LWE) and Ring Learning With Errors (RLWE), or a torus-based construction called Torus Learning With Errors (TLWE).
Learning with Errors (LWE)
The task of solving a system of linear equations is not necessarily difficult. However, by adding small random errors with a specific Gaussian distribution, solving a system of linear equations with the added errors becomes an NP-hard problem. Introduced by Oded Regev in 2005, this is referred to as the Learning with Errors problem.
What makes LWE a lattice-based construction? In 2-dimensions, a lattice can be thought of like a repeating grid. In higher dimensions, a lattice consists of linear combinations of vectors. Learning with errors can be thought of as points on a lattice-grid that are a little off-grid due to the added noise. This makes LWE analogous to the Closest Vector Problem (CVP).
Closest Vector Problem
Given a lattice L and a random point P, which lattice point is the closest? In high dimensions, finding the solution for this requires an exponentially large search space.
In LWE, you can think of the public key as a bunch of noisy points near the lattice points. You would need the secret key in order to find the nearest lattice point, and the distance between these points is the noise or error in LWE. Only someone who knows the original lattice grid, or the secret key, would be capable of removing the noise, or decrypt the message. Otherwise, it would be computationally infeasible, an NP-hard problem. This mathematical hardness is what makes LWE-based cryptography schemes assumed to be computationally secure and quantum-proof.
Bootstrapping and Noise Management
With LWE, the added random noise is what ensures security. However, this noise grows with each operation. After enough operations, the noise becomes too large to distinguish the decrypted message. Without a way to manage the noise, we hit a limit on the number of operations we can compute, leaving us with only somewhat or leveled homomorphic encryption.
What allows for homomorphic encryption to be fully homomorphic? Bootstrapping is a trick that allows us to “reset” the amount of noise in this process, making LWE-based encryption somewhat homomorphic, i.e. we can only run a limited number of operations, to fully homomorphic, i.e. we can continue to securely run unlimited operations.
The general idea of bootstrapping is that, by homomorphically decrypting the FHE ciphertext using an encryption of the original secret key, and re-encrypting it with a new secret key through a process called key switching, the noise is “reset” to a smaller value without ever revealing the underlying message. The specific technical details of bootstrapping depends on the FHE scheme used.
Ring Learning with Errors (RLWE)
Building off of LWE, ring-LWE operates similarly in that it’s also lattice-based, involves recovering a secret from a set of noisy equations, and is NP-hard and assumed to be quantum-resistant.
Instead of using vectors and matrices like in LWE, RLWE operates over a polynomial ring, a set of polynomials with defined addition and multiplication operations. The polynomial ring offers an algebraic structure such that computations are faster and more compact without sacrificing security or mathematical hardness, using polynomial multiplication and Fast Fourier Transforms (FFTs) instead of the matrix-vector operations of LWE.
While LWE has been foundational early in the field of FHE, RLWE is often what actually gets used in FHE implementations currently.
Torus Learning with Errors (TLWE)
Torus-LWE also builds off of the LWE problem, and is optimized specifically for boolean circuits, bit-level data (i.e. 0’s and 1’s), and logic gates, making it useful for applications such as encrypted decision trees, privacy-preserving rule-checking, bit-wise search or matching, or FHE for embedded systems, whereas RLWE would be more useful for applications such as privacy-preserving machine learning or privacy-preserving data analytics.
In Torus-LWE, the mathematical torus construction refers to the set of real numbers mod 1, and is therefore particularly applicable for bit-level data represented as 0’s and 1’s. While it includes fast, single-bit bootstrapping, making it especially efficient for bit-wise data operations, it can also be much less expressive compared to ring-based constructions.
Main FHE Schemes
Arithmetic
2011: BGV (Brakerski, Gentry, Vaikuntanathan)
Named after the paper authors, BGV relies on lattice-based Ring-LWE for performing encrypted addition and multiplication and is one of the first practical FHE schemes, acting as a foundation for many FHE systems used currently.
2014: BFV (Brakerski, Fan-Vercauteren)
Developed shortly after and named after the paper authors, BFV relies on lattice-based Ring-LWE to perform exact arithmetic for addition and multiplication on integers. BFV is seen as simpler and more usable over its BGV predecessor, with better noise management and more efficient multiplication.
BFV works for discrete values, such as counting, voting, or small integers. BFV works less well for real number calculations, and requires bootstrapping to reduce noise as computation depth grows.
2017: CKKS (Cheon, Kim, Kim, Song)
Named after the paper authors, CKKS works well for approximate arithmetic on real or complex numbers, such as for use cases like encrypted machine learning, signal processing, or statistics. CKKS also relies on Ring-LWE, including a step that encodes real or complex numbers, and trades off exactness for efficiency for real numbers. CKKS works less well for use cases where precision is a priority.
Boolean
2014: FHEW (Fast Homomorphic Encryption over the Weak Ring)
Introduced by Ducas & Micciancio, FHEW is optimized for binary data, is specialized for fast bootstrapping, and is meant to be useful for boolean circuits and bit-level operations. FHEW relies on Torus-LWE, with the W referring to the “weak ring” in the torus representation (as opposed to the polynomial rings in Ring-LWE schemes such as BGV and BFV).
The mathematical torus construction makes arithmetic more efficient and bootstrapping faster compared to those based on polynomial rings.
2016: TFHE (Torus FHE)
Paper authored by Chillotti, Gama, Georgieva, and Izabachène, TFHE builds off of FHEW, operates over the torus and implements logic gates using gate bootstrapping. Similar to FHEW, TFHE also works well for bit-level computations, such as for logic circuits, decision trees, and Boolean functions, operating on binary data with a fast bootstrapping mechanism that allows for unlimited computation depth. It works less well for large-scale arithmetic computations, such as matrix multiplications.
Named after the paper authors, fast fully homomorphic encryption schemes over the torus such as FHEW and TFHE are sometimes also referred to as CGGI (Chillotti‑Gama‑Georgieva‑Izabachène).
Table: Fully Homomorphic Encryption Schemes
Table: Existing FHE Libraries
The Awesome-HE Github repo compiles a large list of homomorphic encryption libraries as well. Some notable open-source libraries for FHE include:
Library Links: HElib, SEAL, PALISADE, Lattigo, TFHE-rs, OpenFHE
Note that, as of spring 2025, only Lattigo and OpenFHE provide robust multi-party support for FHE.
Existing Applications and Challenges
Production systems already using somewhat homomorphic encryption include Apple’s Live Caller ID Lookup, which uses HE to send an encrypted query to a server about whether a number is a spam caller or not, without the server ever seeing the specific phone number in the query; and Microsoft’s Password Monitor, which checks if a user’s password exists a list of breached passwords without the server ever seeing the specific password in the query.
Potential applications that FHE may be particularly fitting for currently include healthcare and genomics data, finance, government and census data, and privacy-preserving machine learning inference, to name a few.
While FHE libraries do exist that are ready for use, as of spring 2025, fully homomorphic encryption systems are still currently rare to see deployed in production. FHE is still extremely computationally heavy, often orders of magnitude slower than their plaintext operations counterparts. Existing bootstrapping methods for resetting noise are still computationally expensive as well. For many use cases, FHE is still not quite computationally feasible to easily or accessibly use compared to other privacy-preserving approaches.
For these reasons, trusted execution environments (TEEs), such as secure enclaves, are often a more practical alternative to FHE approaches for secure computation, as they are currently often faster, cheaper, and easier to deploy, as of spring 2025. Unlike FHE, TEEs require trusted third party vendors and can be vulnerable to hardware exploits, such as side-channel attacks.
Additional advances and further research in performance optimizations, hardware acceleration, developer tooling, and usability would make it more possible for FHE to be adopted more widely.
Multi-Party Fully Homomorphic Encryption (MP-FHE)
In multi-party fully homomorphic encryption (MP-FHE), multiple parties can jointly compute on encrypted data. No single party holds the decryption key, and no party reveals their private inputs. To reveal the computation output, enough parties must agree to cooperate to decrypt the result.
MP-FHE makes it possible to combine the power of FHE, computing on encrypted data, with the multi-party control over a secret key, making it possible to run collaborative, privacy-preserving computations non-interactively and without needing a trusted third party. Some benefits of MP-FHE include, notably, collective key ownership and privacy-preserving computation; removes the need for trusted setup; and, as with FHE, is assumed to be quantum-safe.
Potential tradeoffs of MP-FHE are that, currently, it requires high computational overhead, as FHE is already slow and resource intensive and now adds additional complexity for multi-party support; may require multiple rounds of communication between parties during distributed key generation and threshold decryption steps; is still relatively new and may lack mature, robust, and well-supported open-source libraries or developer tooling; and distributed bootstrapping techniques are still considered relatively complex and slow and requires additional research advances for optimization.
Putting It Together
At a high level, we combine the pieces of generating distributed secret key shares from MPC with computing on encrypted data from FHE.
A general high level flow of an MP-FHE computation may look like:
- Joint key generation: Multiple parties jointly generate a shared public key and distributed secret key shares. The secret key has been secret-shared using a protocol such as Shamir’s Secret Sharing or distributed key generation, and as a result, no single party knows the full decryption key.
- Encryption: Each party encrypts their private data using the shared public key. These encrypted inputs are fed into a computation using FHE.
- Homomorphic evaluation: Either a designated evaluator or all of the parties can run the computation on the encrypted inputs using FHE schemes such as BGV/BFV, CKKS, or TFHE, resulting in an encrypted output. This FHE step may also be outsourced to a third party that can run FHE computations, as all the inputs are encrypted.
- Collective decryption: Each party can partially decrypt the output using their secret key shares. Similar to Shamir’s secret sharing, i.e. using Lagrange interpolation, multiple parties must combine their partial decryption shares in order to construct the decrypted output. The final output is only fully decrypted when a minimum threshold of parties participate in this process.
Key Switching
Key switching is a fundamental technique used in FHE transforms a ciphertext encrypted under one secret key into an equivalent ciphertext under a different secret key, without ever decrypting the data.
While also used in FHE schemes, typically as a part returning the ciphertext to the original encryption key after bootstrapping, key switching may be worth noting for MP-FHE schemes.
In MP-FHE, where a secret key may be distributed among multiple parties, key switching is a collaborative process, where parties jointly generate a collective switching key that allows the ciphertext to be re-encrypted under a different shared decryption key. Additionally, if any party leaves or joins, key switching is needed to move existing ciphertexts from the old collective secret key over to a new collective secret key.
Table: Existing MP-FHE Libraries
Notable open-source libraries for MP-FHE include:
Library Links: Lattigo, OpenFHE
As of spring 2025, both Lattigo and OpenFHE are actively maintained.
Existing Applications and Challenges
As of spring 2025, existing MP-FHE systems are typically still considered experimental or research-grade.
Some potential use cases for MP-FHE include private set intersection (PSI) applications, privacy-preserving abuse reporting, or privacy-preserving content provenance databases. Other useful potential domains include: joint data analytics for healthcare, financial, government data, and other domains involving personally identifiable information (PII); aggregate genomic and biomedical data analysis; privacy-preserving abuse detection and content moderation; and privacy-preserving collective decision making, voting, and governance.
Similar to FHE, MP-FHE faces challenges around performance, and would benefit from optimizations in bootstrapping and key switching methods, advances in hardware acceleration, and scaling; and on the multi-party side, further research in security guarantees against malicious parties. Existing MP-FHE schemes combine properties of MPC and FHE, and novel frameworks that are inherently unique to MP-FHE are yet to be fully explored.
Bibliography
Al Badawi, A., & Polyakov, Y. (2023). Demystifying bootstrapping in fully homomorphic encryption. Cryptology ePrint Archive.
Apple and Google. (2021). Exposure Notification Privacy-preserving Analytics (ENPA) white paper.
Bartusek, J., Bergamaschi, T., Khoury, S., Mutreja, S., & Paradise, O. (2024, June). On the Communication Complexity of Secure Multi-Party Computation With Aborts. In Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing (pp. 480–491).
Bellare, M., Hoang, V. T., & Rogaway, P. (2012, October). Foundations of garbled circuits. In Proceedings of the 2012 ACM conference on Computer and communications security (pp. 784–796).
Brakerski, Z., Gentry, C., & Vaikuntanathan, V. (2014). (Leveled) fully homomorphic encryption without bootstrapping. ACM Transactions on Computation Theory (TOCT), 6(3), 1–36.
Chen, E., Lawrence, B., & Zhang, Y. X. (Eds.). (2025). Programmable Cryptography: Four Easy Pieces. 0xPARC.
Cheon, J. H., Kim, A., Kim, M., & Song, Y. (2017). Homomorphic encryption for arithmetic of approximate numbers. In Advances in cryptology–ASIACRYPT 2017: 23rd international conference on the theory and applications of cryptology and information security, Hong kong, China, December 3–7, 2017, proceedings, part i 23 (pp. 409–437). Springer International Publishing.
Corrigan-Gibbs, H., & Boneh, D. (2017). Prio: Private, robust, and scalable computation of aggregate statistics. In 14th USENIX symposium on networked systems design and implementation (NSDI 17) (pp. 259–282).
Damgård, I., Pastro, V., Smart, N., & Zakarias, S. (2012, August). Multiparty computation from somewhat homomorphic encryption. In Annual Cryptology Conference (pp. 643–662). Berlin, Heidelberg: Springer Berlin Heidelberg.
Ducas, L., & Micciancio, D. (2015, April). FHEW: bootstrapping homomorphic encryption in less than a second. In Annual international conference on the theory and applications of cryptographic techniques (pp. 617–640). Berlin, Heidelberg: Springer Berlin Heidelberg.
Fan, J., & Vercauteren, F. (2012). Somewhat practical fully homomorphic encryption. Cryptology ePrint Archive.
Gamiz, I., Regueiro, C., Lage, O., Jacob, E., & Astorga, J. (2025). Challenges and future research directions in secure multi-party computation for resource-constrained devices and large-scale computations. International Journal of Information Security, 24(1), 1–29.
Gentry, C. (2009, May). Fully homomorphic encryption using ideal lattices. In Proceedings of the forty-first annual ACM symposium on Theory of computing (pp. 169–178).
Gong, Y., Chang, X., Mišić, J., Mišić, V. B., Wang, J., & Zhu, H. (2024). Practical solutions in fully homomorphic encryption: a survey analyzing existing acceleration methods. Cybersecurity, 7(1), 5.
I. Chillotti, N. Gama, M. Georgieva and M. Izabachene, TFHE: fast fully homomorphic encryption over the torus, J. Cryptology, 33 (2020) no. 1 34–91.
Jadoul, R., van Leeuwen, B., & Zajonc, O. (2025). Multiparty FHE Redefined: A Framework for Unlimited Participants. Cryptology ePrint Archive.
Jin, S., Gu, Z., Li, G., Chen, D., Koç, C. K., Cheung, R. C., & Dai, W. (2024). Efficient Key-Switching for Word-Type FHE and GPU Acceleration. Cryptology ePrint Archive.
Joye, M. (2021). Guide to fully homomorphic encryption over the [discretized] torus. Cryptology ePrint Archive.
Kun, J. (2024, May 4). A High-Level Technical Overview of Fully Homomorphic Encryption.
Kun, J. (2024, October 29). Fully Homomorphic Encryption in Production Systems.
Li, M., Yang, Y., Chen, G., Yan, M., & Zhang, Y. (2024, July). SoK: Understanding Design Choices and Pitfalls of Trusted Execution Environments. In Proceedings of the 19th ACM Asia Conference on Computer and Communications Security (pp. 1600–1616).
Lyubashevsky, V., Peikert, C., & Regev, O. (2010). On ideal lattices and learning with errors over rings. In Advances in Cryptology–EUROCRYPT 2010: 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30–June 3, 2010. Proceedings 29 (pp. 1–23). Springer Berlin Heidelberg.
Mouchet, C., Bossuat, J. P., Troncoso-Pastoriza, J. R., & Hubaux, J. P. (2020). Lattigo: A Multiparty Homomorphic Encryption Library in Go. In Proceedings of the 8th Workshop on Encrypted Computing and Applied Homomorphic Cryptography (pp. 64–70).
Mouchet, C., Troncoso-Pastoriza, J., Bossuat, J. P., & Hubaux, J. P. (2021). Multiparty Homomorphic Encryption from Ring-Learning-with-Errors. Proceedings on Privacy Enhancing Technologies, 2021(4), 291–311.
Rabin, M. O. (2005). How to exchange secrets with oblivious transfer. Cryptology ePrint Archive.
Regev, O. (2009). On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM (JACM), 56(6), 1–40.
Shamir, A. (1979). How to share a secret. Communications of the ACM, 22(11), 612–613.
Chen, Z., Wang, J., Chen, L., & Song, X. (2014). A Regev‐Type Fully Homomorphic Encryption Scheme Using Modulus Switching. The Scientific World Journal, 2014(1), 983862.
Zhang, J., Cheng, X., Yang, L., Hu, J., Liu, X., & Chen, K. (2024). SoK: Fully homomorphic encryption accelerators. ACM Computing Surveys, 56(12), 1–32.
Further Reading
Multi-party computation
- A Gentle Introduction to the MPC-in-the-Head Transformation
- Theory and Practice of Multi-Party Computation Workshop (TPMPC)
Shamir’s secret sharing
Garbled circuits:
- Explaining Yao’s Garbled Circuits
- Understanding Yao’s Classical Garbled Circuits
- A Gentle Introduction to Yao’s Garbled Circuits
Threshold decryption
Oblivious transfer
Fully homomorphic encryption:
- A High-Level Technical Overview of Fully Homomorphic Encryption
- TFHE Deep Dive
- A Fully Homomorphic Encryption Scheme
- Bootstrapping for Dummies
- Guide to Fully Homomorphic Encryption over the [Discretized] Torus
- Challenges and open problems in Fully Homomorphic Encryption
- Fully Homomorphic Encryption in Production Systems
Learning with errors
- [Video] Learning with errors: Encrypting with unsolvable equations
- [Video] Lattice-based cryptography: The tricky math of dots
- The Learning with Errors Problem, Oded Regev
- Public-key Cryptography from Learning with Errors, 0xPARC
General
- 0xPARC Four Easy Pieces — Download easy.pdf
- Programmable Cryptography (Part 1), 0xPARC
Appendix
Garbled Circuits
Garbled circuits can be broken down into the following flow:
- Representing the function as a boolean circuit
a. The function that both parties want to jointly compute is converted into a boolean circuit made of logic gates. (Any computable function can be represented as a boolean circuit made of logic gates.)
b. Each gate has input and output wires, each carrying 1 bit.
2. Garbler assigning wire labels
a. For each wire in the circuit, the garbler creates two random cryptographic labels representing bit values, one representing 0 and the other representing 1. These labels look essential like random bit-strings.
3. Garbling the gates
a. For each gate in the circuit, the garbler encrypts the output wire for every input combination.
i. For example, an AND gate with inputs A and B would result in 4 encrypted output labels:
- Encₐ₀, ᵦ₀(C⁰)
- Encₐ₀, ᵦ₁(C⁰)
- Encₐ₁, ᵦ₀(C⁰)
- Encₐ₁, ᵦ₁(C¹)
ii. Based on the input values that the evaluator has, only one of these outputs will be decryptable by the evaluator.
4. Sending garbled circuit and garbled inputs to evaluator
a. The garbler sends the garbled circuit, made up of these encrypted gate tables, to the evaluator.
b. The garbler also sends their own input labels directly.
5. Using oblivious transfer for evaluator’s inputs
a. For each of the evaluator’s input bits, the garbler holds two input labels.
b. Using oblivious transfer, the evaluator receives the input label corresponding to their secret input bit without revealing their inputs.
6. Evaluating the encrypted circuit
a. The evaluator now has all the pieces for evaluating the garbled circuit: the garbler’s input labels, their own input labels (via oblivious transfer), and the garbled circuit, represented as an encrypted gate tables.
b. Starting with the input wires, the evaluator can evaluate each gate by finding the decryptable row in the gate table, eventually getting to the final gate, resulting in the decrypted output bits.
