FEI
ApplyAbout
At FEI, we wonder what math is capable of. And we do stuff to find out.
Math keeps surprising us. These surprises motivate us to learn more math, and improve how we think about and harness it. Fully homomorphic encryption is one recent example — how to make it work better, and how to think about its true potential. What happens in a world where insight generation no longer requires information sharing?
We're still finding out what else is possible with math — and what might be possible with a place like FEI.
Challenges for the 3blue1brown audience
A lot of pure math problems, often the kind that would arise in a contest math setting, are very relevant to the work we do. The first of these problems has a surprising connection to lattice-based cryptography and fully homomorphic encryption.
P1: Suppose I have a secret list of positive integers: (v_1, v_2, ..., v_n). You can't see my list, but you can ask me dot product questions. Give me any list of numbers (x_1, x_2, ..., x_n) of the same length, and I'll tell you x_1 \cdot v_1 + x_2 \cdot v_2 + ... + x_n \cdot v_n. Figure out my secret list using as few questions as possible.
Curious to see how this problem has surprising connections to lattice-based cryptography and fully homomorphic encryption? Learn more here.
These next problems, assembled by FEI’s Holden Mui, come in pairs. The first problem comes from the contest math world, while the second problem comes from our work.
P2: Suppose you have many black-box majority functions on three binary inputs. Is it possible to chain them to construct a majority function on 2025 binary inputs? You can duplicate inputs and outputs of the black-box function for free. (From TST 2018/4)
P3: The CKKS fully homomorphic encryption scheme gives a way to encrypt vectors in {C}^{32{,}768} such that anyone can add encrypted vectors elementwise, multiply encrypted vectors elementwise, or "rotate" ciphertexts \left(z_1, z_2, \ldots, z_{65536}\right) \mapsto\left(z_i, z_{i+1}, \ldots, z_{i-1}\right) by any "offset" i. Suppose that:
- encrypted addition takes 4 microseconds
- encrypted multiplication takes 5600 microseconds
- encrypted rotation takes 6100 microseconds
Find a fast arithmetic circuit that computes the Fourier transform on an encrypted vector, conditioned on the multiplicative depth of the circuit being at most three.
P4: Are there any nontrivial solutions to the system of equations
\begin{align*}
a+b+c+d &\equiv 0 \quad(\bmod p) \\
a^2+b^2+c^2+d^2 &\equiv 0 \quad(\bmod p) \\
a^3+b^3+c^3+d^3 &\equiv 0 \quad(\bmod p)
\end{align*}for p=2^{127} - 1?
P5: The programming language circom allows users to prove that they have an assignment to a set of variables satisfying a system of quadratic constraints
\begin{aligned}
(\text{lin. comb. of vars}) \times (\text{lin. comb. of vars}) &\equiv (\text{lin. comb. of vars}) \quad (\bmod p) \\
(\text{lin. comb. of vars}) \times (\text{lin. comb. of vars}) &\equiv (\text{lin. comb. of vars}) \quad (\bmod p) \\
&\vdots \\
(\text{lin. comb. of vars}) \times (\text{lin. comb. of vars}) &\equiv (\text{lin. comb. of vars}) \quad (\bmod p) \\
\end{aligned}without revealing the complete assignment of variables. Some of the variables are set to be public, Some of the variables are set to be public, and the rest are set to be private
(a) Give a system of quadratic constraints in private variables x, s_1, s_2, s_3, \ldots that has a satisfying solution if and only if x \in\left\{0,1, \ldots, 2^{64}-1\right\}.
(b) Give a system of quadratic constraints in private variables x, s_1, s_2, s_3, \ldots that has a satisfying solution if and only if r \ne 1.
(c) Give a system of quadratic constraints in one public variable n \in\left\{2,3, \ldots, 2^{64}-1\right\} and private variables s_1, s_2, s_3, \ldots such that finding a satisfying solution to the system of quadratic constraints is equivalent to finding a nontrivial factorization of n.
(d) Give a system of quadratic constraints in 64 public variables \ell_0, \ell_1, \ldots, \ell_{63} \in\left\{0,1, \ldots, 2^{64}-1\right\} and private variables s_1, s_2, s_3, \ldots such that finding a satisfying solution to the system of quadratic constraints is equivalent to finding a nontrivial factorization of \ell_0+2^{64} \ell_1+2^{128} \ell_2+ \cdots+2^{4032} \ell_{63}.
If you can solve any of these, we'd love to hear from you.
Submit a solutionSelect Examples of Our Work
Fully homomorphic encryption (FHE) lets programs run on encrypted data without ever decrypting the inputs or intermediate values. Using just polynomial arithmetic (with a dash of circuit engineering cleverness), we can solve surprisingly complex problems without knowing anything about the input. Combining this with a carefully designed software system optimized for parallel computing, we've built things from Fog of War chess to a Connect Four engine and more — all fast enough that you can barely tell anything different is happening under the hood.
Fog of War Chess
Fog of War chess is a chess variant in which each player sees only the squares their pieces can move to. Normally that takes a central server that knows both players' pieces and calculates what each side can see. Under FHE, clever board and piece encodings enable each side's vision to be computed entirely on encrypted data. No one sees the full board until the game ends, and in some implementations no server is needed at all, as the encrypted calculations can run in a player's browser.
Connect Four
In Connect Four, the first player can always force a win, but the winning strategies involve a lot of branching, which is hard under FHE because every operation must be data-oblivious. Instead, the engine precomputes a set of early-game moves and selects among them with an encrypted one-hot board state until the board reaches a steady state. From there it tracks that state and plays by a small set of rules instead of memorized moves.
Multiparty LUPI
In LUPI (Lowest Unique Positive Integer), everyone picks a number, and the lowest number nobody else picked wins. This demo runs it on multiparty FHE, so there is no trusted party at all. Before play, the keyholders run distributed key generation in their browsers, and the group key they end up with has no single owner — 5 of the 6 keyholders must combine their shares of the decryption key to reveal a result, and the server never holds any share of it. At one demo, 27 players on various devices all played over the same network.
The FHE Circuit Game
A large part of building any of the demos above is designing the circuit that performs the computation, then optimizing it. Stripped of everything around it, that work turned out to be fun enough to be a game.
Play the Circuit GameThe Math Behind FHE
These lecture notes explain how the CKKS scheme uses ring theory to construct fully homomorphic encryption. The security of CKKS relies on the ring learning with errors (RLWE) assumption: roughly, that adding a small amount of noise to an equation of ring elements makes it hard to solve. CKKS encrypts data by representing batches of complex numbers in terms of ring elements and adding a small amount of noise, making it possible to do approximate arithmetic on encrypted data in a single-instruction multiple-data format.
Message from Grant
As I walked through their offices, the first thing that caught my attention was how the problem up on one of their whiteboards was one that I was actively making a video about (IMO P6 2025). If this isn't a strong signal of alignment between the kinds of people who work there and the 3b1b audience, I don't know what is.
While it's hard to sum up FEI in a phrase, the answer I'd give is that it's a research lab focused on applied cryptography problems. The prototypical example in my mind based on our conversation, though it's not the only thing they work on, is that of fully homomorphic encryption (FHE). This is where you run computations on data without knowing anything about what that data represents. One example there would be multiple nations wanting to keep their satellites from colliding, but who, for various reasons, may not want to reveal where specifically their satellites are. I had always thought of FHE as being something which was theoretically pretty, but completely intractable in practice. Chatting with Albert Ni, though, I learned that's a bit of a misconception, and there are a lot of insights from both pure math and engineering to show how it's not as far out of reach as I thought.
I've always loved the math of cryptography, where you can often state problems that seem like they should be impossible, only to see that an elegant solution is just barely available with the right mathematical tools. It scratches exactly the same itch in my brain that good puzzles and brain teasers do. Moreover, the mathematical tools used in cryptography are beautiful! It's frankly just fun to see concepts usually reserved for the classrooms of a pure abstract algebra class in a university applied to tangible problems.