In my last post many months ago, I offered some speculation about what sorts of
homomorphic encryption schemes are possible:
So we have these two “impossibility results” for vector spaces and fields. But
then on the simpler side of algebraic structures, we’ve already seen that there are
secure homomorphic encryption schemes for groups like RSA, but these are really
limited in the computations that they can express. I would guess there are also
secure homomorphic encryption schemes for even simpler structures like monoids
or even magmas.
Since then, I’ve circled back to this idea of homomorphic encryption schemes for
magmas a number of times, which didn’t really amount to much of anything. Until
now. (No, I didn’t solve a large open problem in cryptography).
Disclaimer: this post was mostly written in March 2026, and I heavily debated
whether to publish it. In the end, I decided “ehh, why not.” Enjoy, or don’t.
Magmas
Magmas are an incredibly simple algebraic structure. I’ve written about fields
and groups before, but magmas are much less widely discussed — probably in
large part because they’re “too simple” to have rich algebraic structure and
tidy classification theorems like groups and fields. Much like a group, a magma
is a set equipped with a single operation. The only property required of the
operation is closure, meaning that applying it to any two elements of the set
gives another element of the set. Groups have this property too, but the group
operation additionally needs to be associative, invertible, and have an identity
element. For magmas, not so! As a result, all groups are magmas, but not all
magmas are groups.
A lot of our discussion today is going to center around a particular magma with
two elements, \(\mathrm{NAND} = (\{0,1\}, \barwedge)\), which operates according
to the folllowing table, which you can think of like a “multiplication table.”
The value of \(x \barwedge y\) is in the row corresponding to \(x\) and column
corresponding to \(y\):
| \(\barwedge\) |
0 |
1 |
| 0 |
1 |
1 |
| 1 |
1 |
0 |
I’ll explicitly point out that \(\mathrm{NAND}\) is not associative:
\[(0 \barwedge 1) \barwedge 1 = 0 \\
0 \barwedge (1 \barwedge 1) = 1\]
There’s also no identity element, since \(0 \barwedge x = 1\) for all \(x\).
Since there’s no identity element, it isn’t strictly meaningful to speak of
inverses, but we do have that \((x \barwedge 1) \barwedge 1 = x\), so 1 is sort
of like its own inverse. However, there’s no such thing for zero. Interestingly,
it happens to be commutative: \(0 \barwedge 1 = 1 = 1 \barwedge 0\).
Functional Completeness of NAND
This \(\mathrm{NAND}\) structure has the very interesting property that any
function over the set \(\mathbb{B} = \{0, 1\}\) can be implemented by composing
\(\mathrm{NAND}\) with itself. In other words, any function
\(f : \mathbb{B}^n \rightarrow \mathbb{B}^m\) is equivalent to some term made up
only of its \(n\) input variables and the \(\mathrm{NAND}\) function. I remember
hearing this fact stated many times before I actually encountered a proof of it
(in a physics classes of all places!), so I’ll include the actual proof because
that’s just how I roll.
First, to simplify things a bit, any function with \(m\) results can be broken
down into \(m\) functions \(f_i : \mathbb{B}^n \rightarrow \mathbb{B}\), as
\(f(x_1, \ldots, x_n) = (f_1(x_1, \ldots, x_n), \ldots, f_m(x_1, \ldots, x_n))\).
Thus, functional completeness equivalently means we can express any function of
a single output.
Next, define some building blocks in terms of \(\mathrm{NAND}\):
\[\begin{aligned}
\overline{x} &\coloneqq x \barwedge x \\
x \wedge y &\coloneqq (x \barwedge y) \barwedge (x \barwedge y) \\
x \vee y &\coloneqq (x \barwedge x) \barwedge (y \barwedge y)
\end{aligned}\]
From these definitions, we can compute the tables for these new operations:
| \(x\) |
0 |
1 |
| \(\overline{x}\) |
1 |
0 |
| \(\wedge\) |
0 |
1 |
| 0 |
0 |
0 |
| 1 |
0 |
1 |
These operations are analogous to logical negation, conjunction, and disjunction,
respectively. This means that \(\overline{x}\) should be read as “not \(x\),”
\(x \wedge y\) as “\(x\) and \(y\),” and \(x \vee y\) as “\(x\) or \(y\).” The
names here suggest a connection with the logical connectives of classical logic.
Indeed, we can see that \(\overline{x}\) is 1 only if \(x\) is not 1,
\(x \wedge y\) is 1 only if \(x\) and \(y\) are both 1, and that \(x \vee y\) is
1 only if \(x\) is 1 or \(y\) is 1.
Next, we need to show that we can construct any function of binary variables
using these building blocks. We start with a concrete example, and will follow
with the general proof. Consider a function of four variables
\(f(x_1, x_2, x_3, x_4)\), which I chose at random, defined by the following
table. To fit it in a 2 dimensional table, the rows are indexed by \(x_1x_2\)
and the columns by \(x_3x_4\).
| \(f\) |
00 |
01 |
10 |
11 |
| 00 |
1 |
1 |
0 |
0 |
| 01 |
0 |
1 |
0 |
1 |
| 10 |
0 |
1 |
0 |
0 |
| 11 |
0 |
1 |
1 |
0 |
We can create functions that are 1 in exactly one spot and zero everywhere else
by “and”-ing all of our variables together. We can control which specific table
entry using negation. For example,
\(x_1 \wedge \overline{x}_2 \wedge \overline{x}_3 \wedge x_4\) produces this
table, because it’s 1 only if “\(x_1\) and not \(x_2\) and not \(x_3\) and
\(x_4\),” which is to say \(x_1x_2x_3x_4 = 1001\).
| |
00 |
01 |
10 |
11 |
| 00 |
0 |
0 |
0 |
0 |
| 01 |
0 |
0 |
0 |
0 |
| 10 |
0 |
1 |
0 |
0 |
| 11 |
0 |
0 |
0 |
0 |
We can then “or” together a bunch of these terms, which will allow us to fill in
multiple 1s in the table. This works because the overall expression will be 1 if
the first part is 1, or the second part is 1, and so on. In this way, we can
write down an expression for \(f\):
\[\begin{aligned}
f(x_1, x_2, x_3, x_4) &= (\overline{x}_1 \wedge \overline{x}_2 \wedge \overline{x}_3 \wedge \overline{x}_4) \\
& \vee (\overline{x}_1 \wedge \overline{x}_2 \wedge \overline{x}_3 \wedge x_4) \\
& \vee (\overline{x}_1 \wedge x_2 \wedge \overline{x}_3 \wedge x_4) \\
& \vee (\overline{x}_1 \wedge x_2 \wedge x_3 \wedge x_4) \\
& \vee (x_1 \wedge \overline{x}_2 \wedge \overline{x}_3 \wedge x_4) \\
& \vee (x_1 \wedge x_2 \wedge \overline{x}_3 \wedge x_4) \\
& \vee (x_1 \wedge x_2 \wedge x_3 \wedge \overline{x}_4)
\end{aligned}\]
Now to treat the general case. We need one extra piece of notation, which
allows us to denote whether or not to negate:
\[\lambda_0(x) \coloneqq \overline{x} \\
\lambda_1(x) \coloneqq x\]
In general, for any function \(f(x_1, \ldots, x_n)\) of binary variables,
we have that
\[f(x_1, \ldots, x_n) = \bigvee_{a_1\ldots a_n \in \{0,1\}^n} \bigg[f(a_1, \ldots, a_n) \wedge \bigg(\bigwedge_{i=1}^n \lambda_{a_i}(x_i) \bigg)\bigg]\]
To see that this equality holds, consider any point in the domain
\(x_1, \ldots, x_n\). In all the terms of the disjunction where
\(x_1, \ldots, x_n \ne a_1, \ldots a_n\), there is some \(x_i \ne a_i\). By
cases, we have that \(\lambda_{a_i}(x_i) = 0\), and since 0 is an absorbing
element for conjunction the full term is 0. Since 0 is the identity of
disjunction, this leaves only the term where \(x_1, \ldots, x_n = a_1, \ldots a_n\),
where now for all \(i\) we have \(\lambda_{a_i}(x_i) = 1\), and since 1 is the
identity of conjunction this term collapses to \(f(x_1, \ldots, x_n)\), which
completes the proof. Since the expression on the right uses only our basic
building blocks defined in terms of \(\mathrm{NAND}\) and constants (note that
\(f\) is only used with arguments that don’t depend on the inputs, so “falls
out” of the expression as in our example), it is defined entirely in terms of
\(\mathrm{NAND}\). Therefore, any binary function can be expressed in terms of
\(\mathrm{NAND}\).
I should point out that the construction in this proof is nowhere near optimal.
If the “cost” of a computation is measured in the number of times the
\(\mathrm{NAND}\) function needs to be evaluated, the description of \(f\) needs
something like 56 \(\mathrm{NAND}\)s with some sensible reuse of intermediates.
For example, I plugged \(f\) into an online solver and got this equivalent
but much smaller formula:
\[f(x_1, x_2, x_3, x_4) = (\overline{x}_1 \wedge \overline{x}_2 \wedge \overline{x}_3)
\vee (\overline{x}_1 \wedge x_2 \wedge x_4)
\vee (\overline{x}_3 \wedge x_4)
\vee (x_1 \wedge x_2 \wedge x_3 \wedge \overline{x}_4)\]
This formulation requires evaluating \(\mathrm{NAND}\) more like 29 times. I
wouldn’t be surprised if there were something much smaller than that, but finding
optimal circuits is a whole other can of worms. The key takeaway here is that
\(\mathrm{NAND}\) on its own is sufficient to compute arbitrary functions, and
so if we have a secure homomorphic encryption scheme for \(\mathrm{NAND}\), we
have fully homomorphic encryption.
Magmas with NAND homomorphisms
So the natural next step is to consider what sorts of structures have
\(\mathrm{NAND}\) homomorphisms. Unfortunately, the results here are not
especially encouraging. For example, the only magmas with 2 elements with
homomorphisms to \(\mathrm{NAND}\) are \(\mathrm{NAND}\) itself and its dual
\(\mathrm{NOR}\).
I did find something interesting with 4 elements though, which I originally
stumbled upon by imagining “published” values of 0 and 1, and then “secret”
values \(a\) and \(b\) whose values are kept as secret as possible. Essentially,
you can imagine that \(a\) and \(b\) are encryptions of 0 and 1, but not which
is which. We know what the results are for 0 and 1, since these are “in the
clear.” That fills in the top left corner. Then for \(a\) and \(b\), we know
that \(a \barwedge a\) is the opposite of \(a\), and similarly for \(b\); and
then we know \(a\) and \(b\) have opposite values, so \(a \barwedge b = 1\).
That fills in the bottom right corner. For our “cross terms” between \((0, 1)\)
and \((a, b)\), we have simple rules as well: \(0 \barwedge x = 1\), and
\(1 \barwedge x\) is the opposite of \(x\). That fills in the whole table.
| \(\cdot\) |
0 |
1 |
a |
b |
| 0 |
1 |
1 |
1 |
1 |
| 1 |
1 |
0 |
b |
a |
| a |
1 |
b |
b |
1 |
| b |
1 |
a |
1 |
a |
This works out very nicely, in that we end up with two distinct homomorphisms
between this structure and \(\mathrm{NAND}\): one which maps \(a\) to 0 and
\(b\) to 1, and another which maps \(a\) to 1 and \(b\) to 0 (while mapping 0
and 1 to 0 and 1). This can be verified by checking the homomorphism formula for
every entry in the table:
\[\phi(x \cdot y) = \phi(x) \barwedge \phi(y)\]
I didn’t realize it for a long time, there’s a very unfortunate reason that this
works out, and it’s not because the idea of using “published encryptions” to
hide other facts about the homomorphism was a breakthrough. It’s because of this
isomorphism:
\[\begin{cases}
0 \mapsto (0, 0) \\
1 \mapsto (1, 1) \\
a \mapsto (0, 1) \\
b \mapsto (1, 0)
\end{cases}\]
It turns out that this table is really just bitwise \(\mathrm{NAND}\) on 2-bit
values! The two homomorphisms I described a moment ago are actually hiding
inside of the isomorphism, too. The entries on the right side are the evaluations
of the homomorphisms at each point! This actually gives us a way to go in the
opposite direction: instead of picking a structure and identifying its
homomorphisms, we can pick its homomorphisms and learn about its structure.
So what does a magma with three \(\mathrm{NAND}\) homomorphisms look like?
Suppose we have a magma \((M,\cdot)\) with distinct homomorphisms
\(\phi_1\), \(\phi_2\), and \(\phi_3\). Now consider the structure
\(\mathrm{NAND}^3 = (\{0,1\}^3, \barwedge)\). It follows that the function
\(\phi(x) = (\phi_1(x), \phi_2(x), \phi_3(x))\) is a homomorphism:
\[\begin{aligned}
\phi(x \cdot y) &= (\phi_1(x \cdot y), \phi_2(x \cdot y), \phi_3(x \cdot y)) \\
&= (\phi_1(x) \barwedge \phi_1(y), \phi_2(x) \barwedge \phi_2(y), \phi_3(x) \barwedge \phi_3(y)) \\
&= (\phi_1(x), \phi_2(x), \phi_3(x)) \barwedge (\phi_1(y), \phi_2(y), \phi_3(y)) \\
&= \phi(x) \barwedge \phi(y)
\end{aligned}\]
The requirement that \(\phi_1\), \(\phi_2\), and \(\phi_3\) are distinct ends up
forcing \(\phi\) to be surjective. Since they are distinct, we know that there
is some point where each pair of functions differ, which we call \(x_{12}\),
\(x_{13}\), and \(x_{23}\) (where the subscripts denote the functions that must
differ at that point). Note that some of these points could be the same, it
doesn’t matter. Without loss of generality, we can take \(\phi_1(x_{12}) = 1\).
This leaves us a reasonably small set of possible values for \(\phi\) at these
points:
\[\begin{aligned}
\phi(x_{12}) &= (1, 0, 0) \mathrm{\; or \;} (1, 0, 1) \\
\phi(x_{13}) &= (1, 0, 0) \mathrm{\; or \;} (1, 1, 0) \mathrm{\; or \;} (0, 0, 1) \mathrm{\; or \;} (0, 1, 1) \\
\phi(x_{23}) &= (0, 1, 0) \mathrm{\; or \;} (1, 1, 0) \mathrm{\; or \;} (0, 0, 1) \mathrm{\; or \;} (1, 0, 1)
\end{aligned}\]
We could check each of these \(2 \cdot 4 \cdot 4 = 32\) cases by hand, but I’ll
just do one to illustrate. The others were verified by computer. Suppose
\(\phi(x_{12}) = (1, 0, 0)\), \(\phi(x_{13}) = (1, 0, 0)\), and \(\phi(x_{23}) = (0, 1, 0)\).
We can now use the fact that \(\phi\) is a homomorphism, and find points where
\(\phi\) evaluates to every point in \(\{0,1\}^3\). We can take a shortcut,
though, and save some work. First, another definition:
\[x+y \coloneqq (x \barwedge (x \barwedge y)) \barwedge ((x \barwedge y) \barwedge y)\]
This implements the \(\mathrm{XOR}\) operation in terms of \(\mathrm{NAND}\),
which is equivalent to addition mod 2. We can similarly construct modular
multiplication, but we’ve already done that: it’s just our \(\wedge\) operation.
Taking these operations elementwise, we have a vector space
\((\{0,1\}^3, +, \barwedge, 0, 1)\). Therefore, in order to show that \(\phi\)
is surjective, it suffices to show that the range of \(\phi\) includes a basis
of this vector space. Consider:
\[\begin{aligned}
\phi(x_{12}) &= (1, 0, 0) \\
\phi(x_{23}) &= (0, 1, 0) \\
\phi(x_{23} \cdot x_{23}) &= (1, 0, 1)
\end{aligned}\]
Checking the other 31 cases as well completes the proof that \(\phi\) is
surjective. Thus, any magma with 3 distinct \(\mathrm{NAND}\) homomorphisms must
have at least 8 elements. A similar computational search gives the similar
result that 4 distinct \(\mathrm{NAND}\) homomorphisms requires at least 16
elements, and leads me to conjecture that any magma with at least \(n\) distinct
\(\mathrm{NAND}\) homomorphisms has at least \(2^n\) elements, which means a
representation of such a structure is at least \(n\) bits which is not an
encouraging result for obtaining practical security. It would be nice to
formalize this better to get a concrete impossibility result, but since it
appears to be a dead end I’ll stop here.
In conclusion, if this conjecture holds in general, I think this means if there
are secure noiseless homomorphic encryption schemes for \(\mathrm{NAND}\), their
security doesn’t come from having a cryptographically large set of possible
decryption functions, but rather that it’s cryptographically hard to find such
homomorphisms while simultaneously still being easy to compute the
\(\mathrm{NAND}\) of ciphertexts.