Obfuscation (Part II): Diamond iO
2026 Jul 28
See all posts
Obfuscation (Part II): Diamond iO
Special thanks to Sora Suegami and Janmajaya Mall for
feedback and review.
In the last part of this series, we went through the full tech tree
of the most mainstream and conservative line of cryptographic
obfuscation (iO) protocols. These protocols allow you to "encrypt"
programs in such a way that anyone can run the "encrypted" program on
plaintext inputs and get plaintext outputs, without being able to see
the internal logic of the program. This can be used for all kinds of use
cases, particularly situations where the program contains some secret
key internally, and obfuscating accomplishes the goal of giving someone
a package that lets them do some things with the secret key
in some circumstances, but not anything else.
The biggest downside of these protocols so far has been their
literally galactic runtime - if you actually try to figure out how long
it would take to run one of them, you would get an answer longer than
the lifetime of the universe. As a result, despite recent breakthroughs
in feasibility, obfuscation protocols have so far been theoretical
curiosities.
This post will describe in detail a different style of obfuscation:
diamond iO (paper, presentation).
This approach relies on much "braver" and more untested cryptographic
assumptions, but it achieves having merely "planetary", rather than
galactic runtime - still infeasible today, but perhaps only a few
further optimizations away from becoming a reality at least for a few
use cases.
Different
types of obfuscation
How does diamond iO work?
At a high level, diamond iO is built by modifying the BGG+14
attribute-based encryption (ABE) scheme, explained
in the previous post. I highly recommend re-reading that section
before continuing.
It's
also not this Abe. Bonus points if you know which Abe this one is -
harder than the four in the last post!
Like, the more traditional iO protocols, diamond iO runs the
computation in FHE inside of ABE, and then gives the evaluator a way to
decrypt the result only if it's actually the outcome of running the
computation correctly. But the way that diamond iO uses this
machinery is different. First, it uses a completely different mechanism
to do conditional FHE decryption. Second, it uses a completely different
mechanism to generate the encodings for the input.
These two modifications are connected to each other, and are the real
reason why diamond iO manages to be much more efficient - it's "just as
computationally intensive as" functional encryption, instead of being a
much more complicated tower on top of FE.
As a reminder, BGG+14 works by maintaining encodings of the form
\(s * (B
- G * m) + e\)
Where:
- \(s\) is a
secret
- \(B\) is a
public matrix, of which there is a different one for each "wire" in the
circuit
- \(m\) is the
bit on that wire during the computation
- \(e\) is an
"error"
(alternatively, you can add \(G * m\) instead of subtracting; both
give equally valid and efficient schemes)
Given two \(B\) matrices representing two "input
wires" to an operation - either addition, multiplication or negation -
you can generate a \(B\) matrix representing the output
wire. Given valid encodings for two inputs to an operation, you can get
an encoding for the output - \(1 - m\), \(m_a + m_b\)
or \(m_a * m_b\)
- that is based on the \(B\) matrix representing the output
wire. Importantly, this is not fully-homomorphic encryption: to
multiply, you need to know either \(m_a\) or \(m_b\) in
the clear.
In BGG+14, there is a step at the end, which allows decoding a
pre-selected output, only if the value in the computation on some
"output" wire equals 0. Here, we do not do that. Instead, what we will
do is just extract the data that we need from the encoding. But in both
cases, the decryption method depends on the encoding being based on a
specific matrix \(B_{final}\) representing the output
wire - this is how we enforce that decryption can happen if you did the
computation correctly, but not in any other context.
The core of diamond iO is:
- Generate BGG+14 \(B\)-matrices and encodings
representing the input \(x\), plus a few other things
- Run a computation, over these BGG+14 encodings, that converts \(x\) into an
FHE ciphertext \(FHE.enc(f(x, z))\), where \(f\) is
public and \(z\) is an
internal hidden input that the obfuscator is trying to hide
- Run another slightly modified BGG+14 step to FHE-decrypt the
output
- Finally, do a "trapdoor" step, borrowing similar machinery to BGG+14
decryption but using it in very different ways, to get the result - only
in the situation where the circuit that you ran is the "correct"
one
The complexity of diamond iO rests in three places:
- What you do to the encoding of the output at the end, that allows
this FHE decryption only in situations where the circuit that was
computed is exactly the same circuit representing \(f\), and
without fully leaking the key
- Some adjustments to \(f(x, z)\) to take into account the
fact that this whole scheme is only secure if the outputs of the FHE
decryption are fully uniformly distributed random-looking, and then
convert it from "obfuscate \(f(x, z)\) hiding \(z\)" to
"full iO that hides the program"
- How to let the evaluator construct the ABE encodings of the inputs,
without giving away the secrets.
The first two ideas came from prior work, particularly HLL23 and AKY24. The third piece, the
mechanism for constructing the ABE encodings of the inputs, originally
came from GGH15; the new
contribution in diamond iO is to use it not to evaluate the whole
program (which turned out insecure) but to generate BGG+ encodings for
the inputs.
We will tackle these three pieces in turn.
The decryption step
Assume for now that the evaluator somehow gets as input four
types of BGG+ encodings of:
- \(1\) (this
will be helpful later, for constructing these encodings)
- FHE encryptions of the fixed hidden input to \(f\), which
we denote \(z\) (we'll
denote the encrypted version \(E[z]\))
- The public input bits: \(s *
(B_{x_1} - x_1 * G) + e_{x_1} ... s * (B_{x_L} - x_L * G) +
e_{x_L}\), where \(x_1 ... x_L\) is the input to \(f\)
- An FHE decryption key (which must be low-norm, and the last value
must be -1), which we will call \(t\)
We'll label this ensemble \([1, E[z], x, t]\).
The evaluator first runs the BGG+ computation using the encodings of
\(E[z]\) and
\(x\).
Remember, the computation is not \(f(x, z)\) directly, rather, it's
\(FHE.eval(f, x, E[z])\). From the
BGG+ perspective, \(x\) and \(E[z]\) are both cleartext bits. From
the FHE perspective, \(z\) is a hidden input, of which only
the encrypted form is known to the evaluator.
At the end of doing the BGG+ computation, the evaluator has BGG+
encodings of bits of the FHE ciphertext representing \(f(x,
z)\).
BGG+ is not fully homomorphic encryption; in general, computing on
BGG+ encodings requires having the underlying cleartext. But we can
avoid this rule for additions, and for multiplications by
known values. This is because a BGG+ encoding of \(m_a * m_b\)
is computed via:
\(c_{out} = m_b * ​c_a ​+ c_b
* ​G^{-1}(B_a)\)
(If the encodings were adding \(G * m\) instead of subtracting, then
it would be \(G^{-1}(-B_a)\) instead)
We can allow \(m_a\) to be unknown (ie. given to us
via encodings only), as long as \(m_b\) is known.
This is an important fact for us. To see why, remember the structure
of GSW decryption (also described in the
previous post in this series):
Because the evaluator knows all the bits of the actual execution
trace, including the final FHE ciphertext (which we'll call \(Y\)), we
can give the evaluator the FHE decryption key, \(t\), only
as BGG+ encodings.
Let's see how the decryption works.
We want to compute \(t *
Y\). We have only BGG+ encodings of \(t\), and we
have both the BGG+ encodings and the raw bits of \(Y\). So in
principle we can do it.
But there's a problem: \(Y\) is given to us as a series of
bits. That is, we don't get a vector of the form \([2, 6,
11...]\). We get a vector of the form \([0, 1, 0, 0, 0, 1, 1, 0,
1, 1, 0, 1...]\), where each bucket of bits (in this
example, 4 bits) is a binary-encoding of a number, by convention
least-significant-bits first. So we have to somehow re-scale the bits,
so that in every cell where we BGG+ multiply some cell \(t_j *
Y_{\{i,j,b\}}\), where \(Y_{\{i,j,b\}}\) is the order \(2^b\) bit
of the cell \(Y_{\{i,j\}}\), the encoding that
comes out is scaled by \(2^b\).
For convenience, let's group together encodings of bits that are of
the same order and that will eventually be inside the same value in the
answer: that is, the whole column \(t_j *
Y_{\{i,j,b\}}\) for some specific \(i\) and
\(b\) across
all \(j\).
\(\sum_j
s * (B_{\{out,i,j,b\}} - t_j * Y_{\{i,j,b\}} * G) +
e_{\{out,i,j,b\}}\)
\(= s *
(B_{\{out,i,b\}} - (tY)_{\{i,b\}} * G) +
e_{\{out,i,b\}}\)
Now we get to the puzzle: how do we combine together bits of
different orders?
One naive thing we could do is just rescale and add:
\(\sum_{b=0}^{log(q)-1} (s * (B_{\{out,i,b\}} -
(tY)_{\{i,b\}} * G) + e_{\{out,i,b\}}) * 2^b\)
The problem with this is that it multiplies up the errors of the
high-order digits too much: the error of the highest-order term would
get multiplied by \(2^{log(q)-1} =
\frac{q}{2}\) so it would flood the whole range.
So here's what we do instead:
\(\sum_{b=0}^{log(q)-1} (s * (B_{\{out,i,b\}} -
(tY)_{\{i,b\}} * G) + e_{\{out,i,b\}}) *
G^{-1}(2^bG)\)
\(G^{-1}(2^bG)\) is doing all the work
here. Basically, this is a bucket-wise left shift
operator - it takes each \(log(q)\)-bit bucket \(tY\), and
shifts them all to the left.
Remember, BGG+ encodings are of the form \(s * (B - G * m) +
e\). And remember that \(G\) has this form:
This means that BGG+ encodings encode \(m\) simultaneously at every
scale. And what we're doing here is we're moving higher-scale
encodings of higher-order bits into the first column of each bucket. And
because we're just doing additions and shifts, not multiplications, we
avoid the error blowing up by more than the small amount that is
introduced by the additions.
To see why \(G^{-1}(2^bG)\) has this shift
effect, let's also look at \(G^{-1}\). On its own, \(G^{-1}\) is
the right-inverse of \(G\), the bit decomposition
operator (not a matrix).
Hence, plain \(G^{-1}(G)\) is just the identity
matrix:
But if we multiply \(G\) by \(2\) before sticking it into \(G^{-1}\),
each binary decomposition is shifted up by one place, and so we get the
desired shift:
This is just a notational trick that allows the "left-shift every
bucket" mechanism to be easily encoded into vector-and-matrix algebra.
See also that the \(G^{-1}(2^bG)\) matrix is also
clearly very low-norm (only ones and zeroes); this is another way to
know that this step does not unreasonably blow up error.
The final outcome of this step is that you get a BGG+ encoding of
\(tY\):
\(s *
(B_{\{final,i\}} - G * (tY)_i) + e_{\{final,i\}}\)
Note that these are no longer "normal" encodings, both because the
\((tY)_i\)'s
are full-range values modulo q, and because the evaluator does not know
the cleartext values. The evaluator cannot do any further BGG+
multiplication on them. But that's okay, because they do not have to;
the only step the evaluator has left is to remove the "wrapping with
\(s\)" so
that we can get to our final goal, extracting \((tY)_i +
e\).
To extract \((tY)_i
+ e\), we are going to diverge from BGG+ ABE fully. In
ABE, we know that, in those cases where decryption is supposed to be
possible, the answer \(C(tag)\) equals 0. \(G *
C(tag)\) disappears, and that's exactly why we can extract
the message. \(G *
C(tag)\) plays the role of a blinding factor.
Here, the use case is different: \((tY)_i\) is the entire thing that we
want to extract.
Let's rewrite our BGG+ encoding as:
\(s *
B_{\{final,i\}} - s * G * (tY)_i + e_{\{final,i\}}\)
Now, let's extract a single column from this expression - the
lowest-order column in the last bucket.
\(s * b_i - s * g * (tY)_i
+ e\)
The choice of lowest-order column diverges from "traditional GSW
decryption", where we extract the highest-order column, but remember:
because of our bucket-wise shifting trick, by this point the
lowest-order column contains information that was grabbed from the
highest-order columns representing the values that we care most about
(the message).
We constrain \(s\) so that its last value (which
we'll denote \(s_{last}\)) equals -1. Also, notice
that the column of \(G\) we chose, \(g\), is
just a bunch of zeroes followed by a 1. Hence, we get a nicely
simplified expression:
\(s * b_i - s_{last} *
(tY)_i + e_i\)
\(= s *
b_i + (tY)_i + e_i\)
Now, our task is to compute \(s * b_i\) so we can remove it.
Let us pull in one fact from a later section: the evaluator has
"access" to \(s\) in the form of an encoded sample
\(ct = (m
\otimes s) P_L + e_L\), where \(m\) is the full input to the
obfuscated computation and \(\otimes\) is the "tensor product".
That is, \(m
\otimes s\) is a vector of length \(len(m) *
len(s)\) that contains \(s\) multiplied by the first value in
\(m\), then
right after that \(s\) multiplied by the second value
in \(m\), and so
on. Conveniently, the first value in \(m\) is fixed to be 1.
Now, we use the trapdoor machinery, described in the ABE
section of the previous post, to make a low-norm preimage \(K_G\) that
satisfies:
\(P_L *
K_G = M\)
Here, \(M\) is a
matrix that contains all of the \(b_i\)'s - that is, the extracted
columns from each \(B_{\{final,i\}}\) matrix - and then
is padded with extra zeroes to make the dimensions match up.
This ensures that \(ct *
K_G\) evaluates to
\(((m \otimes s) * P_L +
e_L) * K_G\)
\(= (m \otimes s) * P_L *
K_G + e_L * K_G\)
\(= (m
\otimes s) * M + e_g\)
Now, notice that only the first \(len(s)\) rows of \(M\) are
nonzero, and the first \(len(s)\) values in \(m \otimes
s\) are just \(s\). So the above reduces to:
\(s * M +
e_g\)
Which is a concatenation of all of the \(s * b_i +
e_{\{i,g\}}\) that we need.
Now, we can subtract that, and get the \((tY)_i + e_i\) values we need, which
are our FHE decryption result. And then finally, the evaluator rounds,
to get the final value of \(f(x, z)\).
Here we can once again see where the security comes from: the \(K_G\)
"trapdoor" allows the evaluator to extract this only for those
specific \(b_i\), and
the \(b_i\) come
from \(B_{\{final,i\}}\), which are bound
to the exact shape of the circuit. If the evaluator computes \(s *
b'_i + e{\{i,g\}}\) for some different \(b'_i\),
then they would be left with a \(s * (b_i - b'_i)\) term blinding the
\((tY)_i +
e_i\), and would not be able to extract the answer.
Adjustments to f(x, z)
It turns out the security of the scheme we described above is only
provable under one condition: that the outputs \((tY)_i +
e_i\) are uniformly random - in fact,
jointly pseudorandom across all \(2^L\) inputs. "Jointly pseudorandom"
here basically means that if you were given unlimited access to the full
exponentially-sized table (though still only polynomial computation
time), you would not be able to distinguish it from random data.
This actually makes our work challenging. In a "normal" GSW
decryption, the last entry of \(t * Y\) equals \(\frac{q}{2} * m + e\). This would
give us two problems:
- Because the error is almost always much smaller than the message,
the output is very "spiky" around \(0\)
and \(\frac{q}{2}\). Even if the error
could somehow always cover the full range (difficult: worst-case and
average-case tend to differ massively), LWE error is correlated with the
message so it would still leak information
- The distribution of outputs \(m\)
is itself not uniform, because most "natural" functions
\(f\) are not
random.
We can tackle these in turn.
First, we modify the function that we evaluate in FHE. We make \(z\) contain
two secrets \((z_1, z_2)\): the secret input to
the function, and a random PRF key. Then, we do \(FHE.eval(f', x, E[z])\), where:
\(f'(x,
z) = \frac{q}{2} * f(x, z_1) - (\frac{q}{4} - e_{max}) + H_1(x,
z_2)\)
Here, \(H_1\) is a
hash function that returns values in \([0 ...
\frac{q}{2}-2e_{max})\), where \(e_{max}\)
is a bound on the largest possible error that our whole procedure could
introduce. Formally, \(H_1\) must be a PRF ("pseudorandom
function").
For correctness, it's okay to just think of it as a hash. However, in
practice, computing this hash is where almost all of the evaluation time
lies, and so making diamond iO practical will almost certainly involve
heavily optimizing \(H_1\) to target its specific needs,
and not using generic algorithms like SHA256.
In "normal" GSW, the \(\frac{q}{2}\) factor is implicit -
of course you multiply the message by \(\frac{q}{2}\) because otherwise it
might get smudged by the error. Here, we multiply the \(f(x, z_1)\)
part by \(\frac{q}{2}\) but not the \(H_1(x,
z_2)\) part, and we're okay with a few lower-order digits
of that getting mangled by the error - the \(H_1(x, z_2)\) is not data we care
about recovering, rather it's meant to be "maximum-range" pseudorandom
noise that is there to smudge out the FHE and ABE-related noise. The
goal of the \(\frac{q}{4} -
e_{max}\) offset is to "center" the output of \(H_1\) (ie.
make its range \([-(\frac{q}{4} - e_{max}), \frac{q}{4} -
e_{max}]\)), so that you can round to the nearest \(\frac{q}{2}\) and then divide to get
back \(f(x,
z)\).
Second, we modify the function again, by xoring a hash into
\(f\)
itself:
\(f'(x,
z) = \frac{q}{2} * xor(f(x, z_1), H_2(x)) - (\frac{q}{4} - e_{max}) +
H_1(x, z_2)\)
From \(H_2\), we
want a random oracle property. But \(H_2\) is not a bottleneck for
efficiency, so using generic algorithms like SHA256 is great here.
To get the final output in the clear, we xor \(H_2(x)\)
back out after we get the final \(f'(x, z)\) output from the diamond
iO.
The result of this trickery is that \((tY)_i\) is now fully
pseudorandom:
- Each highest-order bit is pseudorandom because it gets xor'd with a
bit of \(H_2(x)\), which we assume is
pseudorandom (in the formal sense described by the pseudorandom oracle
model)
- All lower-order bits are generated by \(H_1(x, z_2)\), which we again assume
is pseudorandom. The \(2e_{max}\)-wide empty space between
the ranges of possible outputs for the two possible message values is
exponentially small compared to \(q\), so we can safely ignore
it.
This technique is
sometimes called "PROM bootstrap", and it is a generic transformation
that converts "obfuscation for pseudorandom functionalities" into a more
general form of obfuscation that works for any \(f\).
Looking at a hash simultaneously as a random oracle and an implementable
circuit is also sometimes considered a "sketchy" cryptographic
assumption, though it is used widely today, eg. in recursive STARKs.
Finally, if we want to do "traditional" iO, which hides the function,
instead of fixing a public function \(f\) and hiding a private input \(z\), then
we do the trick we already did many times in the more conservative forms
of obfuscation: make \(f\) be a "universal circuit" \(VM\) whose
private input is a program \(P\), and that satisfies \(VM(x, P) =
P(x)\).
So far, we have just magically assumed that the evaluator gets BGG+
encodings \(s * (B_i - G * m_i) +
e_i\). But unfortunately things are not that simple. The
obfuscator could construct \(len(m) + L\) such encodings, for
\(m_i \in
\{0,1\}\), with the same \(s\) (they would only have to provide
both the \(0\) option
and the \(1\) option
for the \(x\) portion
of \(m\)). But
this is not secure: if you get two encodings with the same \(B_i\) and
the same \(s\) but
different \(m_i\) (if we're dealing with binary
bits, that means \(0\) and \(1\)), then you can just subtract
them and get \(s * G + (e_1 -
e_2)\), leaking \(s\) in the clear.
So we have to somehow give the evaluator a gadget that lets them
produce encodings for any \(m\), but with a different \(s\) for
each \(m\). Even
one bit of change in \(m\) should completely change the
\(s\). This
is where the core of diamond iO's machinery comes in.
The trick is as follows. First, remember the structure of \(m\): \([1, E[z], x,
t]\). The only thing that changes between different
evaluations is \(x\).
We will start off with a "base" message, \(m_0 = [1, E[z], 000...000,
t]\), and a "base" secret \(s_0\).
For the i'th bit, we will define matrices \(M_{\{i,0\}}\) and \(M_{\{i,1\}}\) which are the identity
matrix, but with the 1 in the slot corresponding to the i'th bit of
\(x\) either
deleted or moved to the first row. That is, \(M_{\{i,b_i\}}\) represents the idea
"keep \(m\) as is,
except change the i'th bit in \(x\) to \(b_i\)".
We also define low-norm matrices \(S_{\{i,0\}}\) and \(S_{\{i,1\}}\), whose goal is to
transform the secret.
Hence, any final vector \(m_L\) can be expressed as \(m_0 *
M_{\{1,b_1\}} * M_{\{2,b_2\}} * ... * M_{\{L,b_L\}}\). And
the corresponding \(s_0 *
S_{{1,b_1}} * S_{{2,b_2}} * ... * S_{{L,b_L}}\) gives us a
unique secret \(s_L\). Our goal will be to "fuse"
these transformations together, so that for each specific \(m_L\) you
generate, you get BGG+ encodings constructed with a unique corresponding
secret \(s_L\).
We will "fuse" these vectors and matrices by tensoring them together,
and then wrapping them in encodings so that they cannot be unpacked.
A mini example - we'll start with tensoring the vectors \(m\) and
\(s\):
The leftmost value in \(m\) is constrained to equal \(1\), and
the rightmost value in \(s\) is constrained to equal \(-1\).
And now this is what tensoring matrices looks like (all un-written
entries are zeroes):
See how \(M\) is in
the shape we described above, and \(S\) is constrained so that it
doesn't touch the last column, keeping the last value of \(s\) at
-1.
A key property of tensoring is that if \(m_1 = m_0 * M_{\{1,
b_1\}}\) and \(s_1 = s_0 * S_{\{1,
b_1\}}\), then \((m_1
\otimes s_1) = (m_0 \otimes s_0) * (M_{\{1, b_1\}} \otimes S_{\{1,
b_1\}})\). For convenience, we'll define \(Q_{\{i,b\}}\) as equaling \((M_{\{i, b\}} \otimes S_{\{i,
b\}})\)
So far, the evaluator's formula is: start with \(q_0 =
m_0 \otimes s_0\), multiply by each \(Q_{\{i,
b_i\}} =M_{\{i, b_i\}} \otimes S_{\{i, b_i\}}\) in
sequence, and then get \(q_L = m_L \otimes
s_L\) at the end.
We have already gotten somewhere: we now have a way to generate
some kind of encoding of each possible \(m_L\) that
the evaluator might need, such that it's bound to a unique \(s_L\). The
problem: so far, this encoding exposes \(m_L\) (including the \(t\) bits
which the evaluator is not meant to know) and \(s_L\)
completely in the clear.
The next step will be multiplying in matrices in the right places to
"blind" these encodings at each step.
The obfuscator will give the evaluator an encoding \(p_0
​=q_0​ * P_0 ​+ e_0\)
The obfuscator will then generate low-norm matrices \(K_{\{i,b\}}\), which satisfy \(P_{i-1}
* K_{\{i,b\}} = Q_{\{i,b\}} * P_i + E_{\{i,b\}}\). This
is allowed, again, because of the trapdoor mechanism.
The evaluator can then walk down the exponentially-sized tree of
possible encodings. Here's what this tree looks like graphically. Notice
that even though the tree is of size \(2^L\), the number of
actually-distinct "edge matrices" that generate this whole tree is only
\(2L+1\),
including the final \(K_f\) that we'll get to later).
And here's why this works mathematically:
\(p_1 =
p_0 * K_{\{1,b_1\}}\)
\(= q_0 *
P_0 * K_{\{1,b_1\}} + e_0 * K_{\{1,b_1\}}\)
\(= q_0 *
Q_{\{1,b_1\}} * P_1 + e_0 * K_{\{1,b_1\}} + q_0 *
E_{\{1,b_1\}}\)
\(= q_0 * Q_{\{1,b_1\}} *
P_1 + e_1\)
And then:
\(p_2 =
p_1 * K_{\{2,b_2\}}\)
\(= q_0 *
Q_{\{1,b_1\}} * P_1 * K_{\{2,b_2\}} + e_1 *
K_{\{2,b_2\}}\)
\(= q_0 *
Q_{\{1,b_1\}} * Q_{\{2,b_2\}} * P_2 + e_1 * K_{\{2,b_2\}} + q_0 *
Q_{\{1,b_1\}} * E_{\{2,b_2\}}\)
\(= q_0 *
Q_{\{1,b_1\}} * Q_{{2,b_2}} * P_2 + e_2\)
And so on all the way up until \(p_L =
q_0 * Q_{\{1,b_1\}} * ... * Q_{\{L,b_L\}} * P_L + e_L\),
where \(q_0 * Q_{{1,b_1}} * ... *
Q_{{L,b_L}} = q_L\).
Notice \(e_{i-1} *
K_{\{i,b_i\}}\) and \(q_{i-1} *
E_{{i,b_i}}\) both collapse into \(e_i\). This
means that \(K_{\{i,b\}}\), \(Q_{\{i,b\}}\) and \(q\) (and
hence \(m\), \(s\), \(M_{\{i,b\}}\), \(S_{\{i,b\}}\)) all have to be
low-norm (and they are).
Now, we have an actually-blinded encoding of \(q_L =
m_L \otimes s_L\). But it's not quite the right format. We
have:
\((m_L \otimes s_L) * P_L +
e_L\)
We need:
\(s_L * (B_i - G * m_L[i])
+ e_i\)
To cross this bridge, we add another trapdoor \(K_f\). It
needs to satisfy:
\(P_L *
K_f = u_1 \otimes B_{full} - I \otimes G\)
Here we just introduced a few pieces of new notation, so let's go
through them:
- \(u_1\) is a
vector that is 1 in the first position and 0 everywhere else. Depending
on context, it means "select the first (column / row / bucket /
entry)"
- \(B_{full}\)
is the concatenation of the \(B\) matrices for the encodings of
the whole input: \(B_i\) as in \(s *
(B_i - G * m_i) + e_i\)
- \(u_1
\otimes B_{full}\) means "vertically stack many copies of
\(B_{full}\)
where the first is multiplied by 1 and the rest multiplied by 0" - or in
even simpler terms, put a bunch of zeroes below \(B_{full}\)
- \(I
\otimes G\) looks like many copies of \(G\) along a
diagonal; it means "multiply by \(G\) bucket-wise"
Also notice that here (like the \(K_G\) case, unlike the
\(K_{\{i,b\}}\) case), there is no
error on the right side; that is fine, because the error in the final
ciphertexts will come from elsewhere, and the value on the right is a
public expression, so there is no security risk to not masking it.
Now, let's see what happens if we multiply \((m_L
\otimes s_L) * P_L + e_L\) by \(K_f\):
\(((m_L \otimes s_L) * P_L
+ e_L) * K_f\)
\(= (m_L
\otimes s_L) * P_L * K_f + e_L * K_f\)
\(= (m_L
\otimes s_L) * u_1 \otimes B_{full} - (m_L \otimes s_L) * (I \otimes G)
+ e_f\)
\(= s_L *
B_{full} - (m_L \otimes s_L) * (I \otimes G) + e_f\)
\(= s_L *
B_{full} - m_L \otimes (s_L * G) + e_f\)
The last two lines are the most nonobvious. What's going on is:
because \(m_L\) (like
all message vectors) starts with 1, the first bucket of \(m_L \otimes
s_L\) is just \(s_L\). And on the other hand, below
the first bucket of rows, \(u_1 \otimes
B_{full}\) just equals zero. Hence, \((m_L
\otimes s_L) * (u_1 \otimes B_{full})\) just reduces to
\(s_L *
B_{full}\). And then the \(I \otimes G\) plays its role as many
copies of \(G\) that
all get multiplied by many copies of \(s\), one for each message value in
\(m_L\).
(In the paper, they split up \(B_{full}\) into \(B_{att}\)
(excluding \(t\) in the
inputs) and \(B_t\), and run the above procedure
on those two pieces separately. This is mathematically equivalent to
what was described here. The conceptual reason to separate is that they
are different kinds of data - the raw values of \([1, E[z],
x]\) are given to the evaluator, but the raw values in
\(t\) are
not)
And the output is literally just the concatenation of all the \(s_L * (B_i - G * m_L[i])
+ e_{\{f,i\}}\) BGG+ encodings that we need.
Re-summarizing diamond iO
- The evaluator gets \(p_0\), which is an encoding of (i)
\(m\) with
the function-input parts set to zero and (ii) an initial key \(s_0\)
tensored together
- For each bit of the message, the evaluator can choose either \(K_{i,0}\)
or \(K_{i,1}\),
which play the role of simultaneously (i) writing either 0 or 1 in as
the i'th bit of the function-input part of \(m\), and (ii) mixing in a new factor
into the key
- At the end, we have \(p_L\) which encode the final \(m\) and
\(s\)
tensored together. We multiply by another trapdoor to push things into
the final form: BGG+ encodings of \([1, E[z], x, t]\)
- The evaluator then does the BGG+ computation to compute the
ciphertext of \(f'(x,
z) = \frac{q}{2} * xor(f(x, z_1), H_2(x)) - (\frac{q}{4} - e_{max}) +
H_1(x, z_2)\)
- Decrypting a GSW ciphertext is "just" vector-by-matrix multiplying
\(t * Y\) and
then rounding. Here, we have the bits of \(Y\), both as BGG+ encodings and as
cleartext, and we have just the BGG+ encodings (no cleartext) of \(t\).
- The evaluator does this as a BGG+ multiplication, but with a
bucket-wise left shift operation to appropriately scale entries of \(t*Y\) that
represent high-order bits
- This gives the evaluator an encoding \(s *
B_{\{final,i\}} - s * G * (tY)_i + e_{\{final,i\}}\)
- The evaluator extracts a single column - the lowest-order entry in
the bucket corresponding to the last entry of \(s\) (which
is fixed to -1). This lets us simplify to \(s * b_i + (tY)_i +
e_i\)
- Finally, the evaluator has a "trapdoor matrix" which allows
computing all \(s *
b_i\) at the same time - but only for those specific \(b_i\). This
lets them subtract \(s *
b_i\) out, and just have \((tY)_i + e_i\)
- The evaluator then rounds-and-divides this, and xors back \(H_2(x)\) in
the clear, to get the desired result \(f(x, z)\)
Security
The most "controversial" part of this protocol is the mechanism for
generating the BGG+ encodings for the input. This relies on two fairly
new cryptographic assumptions, called all-product LWE and
evasive LWE. Evasive LWE was introduced in Wee22; all-product LWE is
unique to diamond iO.
- Evasive LWE says that it's safe to publish
pre-images of a secret-bearing target. Roughly, if you have two matrices
\(A\) and
\(C\), and
samples \(sA +
e_1\) and \(sC + e_2\) (both errors independent)
that are indistinguishable from random, then publishing a low-norm
preimage \(B\)
satisfying \(A * B =
C\) won't make the \(sA + e_1\) samples distinguishable
from random. Note in particular that publishing \(B\) allows
an adversary to convert \(sA + e_1\) samples into \(sC +
e_1B\); the assumption says that this is safe. In our
case, the assumption implies that the \(K_{\{i,b\}}\) are safe to publish,
despite the fact that they are pre-images of a masked but secret-bearing
target: \(P_{i-1} * K_{\{i,b\}} =
C\) where \(C =
Q_{\{i,b\}} * P_i + E_{\{i,b\}} = (M_{\{i,b\}} \otimes S_{\{i,b\}}) *
P_i + E_{\{i,b\}}\), where the \(S_{\{i,b\}}\) are the building
blocks of the secret.
- All-product LWE says that the family of all \(s_x (B
- x \otimes G) + e_x\), across all \(2^L\)
values of x, with secrets constructed via the path-product
mechanism we described above, is jointly pseudorandom. That is, this
particular way of constructing many LWE samples with many secrets
is safe, as safe as if all \(2^L\) secrets were truly
independent. Note that this assumes that the initial errors entering the
product are pseudorandom; in the diamond iO use case, because we
published the \(K_{\{i,b\}}\) matrices, we can only
assume that if we also accept the evasive LWE assumption.
These LWE assumptions are at the same time plausible, avoiding many
pitfalls that we have come to understand from a decade of attempts to
create novel LWE assumptions that ended up broken by "zeroizing"
attacks, but also novel and risky. Evasive LWE is non-falsifiable in
Naor's sense: formally, it says "for every algorithm that can
distinguish X there exists an algorithm that can distinguish Y..." so it's
hard to tell if you even have a counterexample. There are already known
classes of situations in which evasive LWE is false; diamond iO
deliberately chooses a type of evasive LWE assumption that avoids
this.
More security analysis is needed to verify that these assumptions are
safe.
Efficiency
Constructing the BGG+ encodings is relatively "easy" (in part because
you can actually use a fan-out greater than 2, eg. a fan-out of 256
fills in 8 bits of \(x\) per multiplication). The hard
part is the BGG+ evaluation, which has "ABE * FHE" overhead, where the
FHE is itself GSW, which nobody uses in production because it's far less
efficient than more mainstream algorithms like BFV. GSW is needed
because it has "nice" algebraic properties, including no need for
relinearization or key-switching, and the ability to put plaintext into
any size bits of the ciphertext.
On top of this, there are other sources of inefficiency and
limitation:
- The whole mechanism also only tolerates low-depth circuits, because
the error blows up a lot with each round of BGG+ evaluation and
with each bit added to the input (we casually papered over this in the
explanations by implicitly invoking a "low-norm * low-norm = low-norm"
argument, but over many layers, it adds up).
- As with all forms of obfuscation so far, the need to "walk over"
\(2^L\)
possible inputs inside the proof means that the system requires
"subexponentially secure" parameters, which are much larger than
normal.
The main concrete bottleneck is actually computation of
\(H_1(x, z)\)
inside of the ABE * FHE. The main contributor to cost is depth (as depth
increases the dimensions needed to handle the error). If the computation
itself is deep, there are ways to "refresh" noise for BGG+ encodings,
but these methods themselves depend on having a feasible \(H_1\).
Hence, depth of \(H_1\) is the concrete bottleneck.
Diamond iO currently uses a "tree" of Goldreich
PRG executions to instantiate \(H_1\). This has multiplicative depth
3 per fan-out, and the number of fan-outs required is proportional to
the input length.
These reasons are why, in the chart showing different types of
obfuscation at the start of this post, diamond iO lands in the "very
aggressive" and "planetary" point of the chart.
If we want to improve concrete efficiency of diamond iO, a few
possible paths come to mind:
- Replace the tree of Goldreich PRG instantiations with something more
efficient
- Find some way to remove \(H_1\) completely. Perhaps this could
involve moving the noise generation into the input encoding step, though
there are known attacks
against such constructions.
- Replace the GSW with some more efficient FHE - either something BGV
/ CKKS flavor, or packed
GSW (see also: my
exploration here), and figure out how to make the conditional
decryption work there
- Find some way to at least partially "collapse" the ABE and FHE
layers together. Maybe this means modifying BGG+ to embrace the fact
that FHE operates "natively" over approximate computation
- Find a way to remove the "subexponentially secure" requirement on
the proof side
- Find some optimizations that much more explicitly engineer around
solely trying to obfuscate the "iO-complete program" (decrypt an FHE
ciphertext only if you receive a valid STARK proving that it was
constructed by FHE-evaluating the right circuit on valid inputs), which
you can then use to obfuscate anything else
A key advantage of diamond iO is its friendliness to analysis,
because of its simplicity. There are no towers of "protocols inside
protocols inside protocols" like in more conservative obfuscation
variants - the only nesting is the FHE inside of ABE. It can be
understood without reference to the entire tower of constructions
invented over the past 20 years by cryptographers: you don't need
sublinear randomized encodings, functional encryption, garbled circuits,
split FHE or even full ABE (we're using the core machinery of BGG+, but
the details are sufficiently different that the advantage to someone who
already knows how it works is much lower). For these reasons, I hope
that diamond iO can get much more attention and analysis on both
security and optimization, and we can get to an obfuscation protocol
that we can actually run.
Obfuscation (Part II): Diamond iO
2026 Jul 28 See all postsSpecial thanks to Sora Suegami and Janmajaya Mall for feedback and review.
In the last part of this series, we went through the full tech tree of the most mainstream and conservative line of cryptographic obfuscation (iO) protocols. These protocols allow you to "encrypt" programs in such a way that anyone can run the "encrypted" program on plaintext inputs and get plaintext outputs, without being able to see the internal logic of the program. This can be used for all kinds of use cases, particularly situations where the program contains some secret key internally, and obfuscating accomplishes the goal of giving someone a package that lets them do some things with the secret key in some circumstances, but not anything else.
The biggest downside of these protocols so far has been their literally galactic runtime - if you actually try to figure out how long it would take to run one of them, you would get an answer longer than the lifetime of the universe. As a result, despite recent breakthroughs in feasibility, obfuscation protocols have so far been theoretical curiosities.
This post will describe in detail a different style of obfuscation: diamond iO (paper, presentation). This approach relies on much "braver" and more untested cryptographic assumptions, but it achieves having merely "planetary", rather than galactic runtime - still infeasible today, but perhaps only a few further optimizations away from becoming a reality at least for a few use cases.
Different types of obfuscation
How does diamond iO work?
At a high level, diamond iO is built by modifying the BGG+14 attribute-based encryption (ABE) scheme, explained in the previous post. I highly recommend re-reading that section before continuing.
It's also not this Abe. Bonus points if you know which Abe this one is - harder than the four in the last post!
Like, the more traditional iO protocols, diamond iO runs the computation in FHE inside of ABE, and then gives the evaluator a way to decrypt the result only if it's actually the outcome of running the computation correctly. But the way that diamond iO uses this machinery is different. First, it uses a completely different mechanism to do conditional FHE decryption. Second, it uses a completely different mechanism to generate the encodings for the input.
These two modifications are connected to each other, and are the real reason why diamond iO manages to be much more efficient - it's "just as computationally intensive as" functional encryption, instead of being a much more complicated tower on top of FE.
As a reminder, BGG+14 works by maintaining encodings of the form
\(s * (B - G * m) + e\)
Where:
(alternatively, you can add \(G * m\) instead of subtracting; both give equally valid and efficient schemes)
Given two \(B\) matrices representing two "input wires" to an operation - either addition, multiplication or negation - you can generate a \(B\) matrix representing the output wire. Given valid encodings for two inputs to an operation, you can get an encoding for the output - \(1 - m\), \(m_a + m_b\) or \(m_a * m_b\) - that is based on the \(B\) matrix representing the output wire. Importantly, this is not fully-homomorphic encryption: to multiply, you need to know either \(m_a\) or \(m_b\) in the clear.
In BGG+14, there is a step at the end, which allows decoding a pre-selected output, only if the value in the computation on some "output" wire equals 0. Here, we do not do that. Instead, what we will do is just extract the data that we need from the encoding. But in both cases, the decryption method depends on the encoding being based on a specific matrix \(B_{final}\) representing the output wire - this is how we enforce that decryption can happen if you did the computation correctly, but not in any other context.
The core of diamond iO is:
The complexity of diamond iO rests in three places:
The first two ideas came from prior work, particularly HLL23 and AKY24. The third piece, the mechanism for constructing the ABE encodings of the inputs, originally came from GGH15; the new contribution in diamond iO is to use it not to evaluate the whole program (which turned out insecure) but to generate BGG+ encodings for the inputs.
We will tackle these three pieces in turn.
The decryption step
Assume for now that the evaluator somehow gets as input four types of BGG+ encodings of:
We'll label this ensemble \([1, E[z], x, t]\).
The evaluator first runs the BGG+ computation using the encodings of \(E[z]\) and \(x\). Remember, the computation is not \(f(x, z)\) directly, rather, it's \(FHE.eval(f, x, E[z])\). From the BGG+ perspective, \(x\) and \(E[z]\) are both cleartext bits. From the FHE perspective, \(z\) is a hidden input, of which only the encrypted form is known to the evaluator.
At the end of doing the BGG+ computation, the evaluator has BGG+ encodings of bits of the FHE ciphertext representing \(f(x, z)\).
BGG+ is not fully homomorphic encryption; in general, computing on BGG+ encodings requires having the underlying cleartext. But we can avoid this rule for additions, and for multiplications by known values. This is because a BGG+ encoding of \(m_a * m_b\) is computed via:
\(c_{out} = m_b * ​c_a ​+ c_b * ​G^{-1}(B_a)\)
(If the encodings were adding \(G * m\) instead of subtracting, then it would be \(G^{-1}(-B_a)\) instead)
We can allow \(m_a\) to be unknown (ie. given to us via encodings only), as long as \(m_b\) is known.
This is an important fact for us. To see why, remember the structure of GSW decryption (also described in the previous post in this series):
Because the evaluator knows all the bits of the actual execution trace, including the final FHE ciphertext (which we'll call \(Y\)), we can give the evaluator the FHE decryption key, \(t\), only as BGG+ encodings.
Let's see how the decryption works.
We want to compute \(t * Y\). We have only BGG+ encodings of \(t\), and we have both the BGG+ encodings and the raw bits of \(Y\). So in principle we can do it.
But there's a problem: \(Y\) is given to us as a series of bits. That is, we don't get a vector of the form \([2, 6, 11...]\). We get a vector of the form \([0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1...]\), where each bucket of bits (in this example, 4 bits) is a binary-encoding of a number, by convention least-significant-bits first. So we have to somehow re-scale the bits, so that in every cell where we BGG+ multiply some cell \(t_j * Y_{\{i,j,b\}}\), where \(Y_{\{i,j,b\}}\) is the order \(2^b\) bit of the cell \(Y_{\{i,j\}}\), the encoding that comes out is scaled by \(2^b\).
For convenience, let's group together encodings of bits that are of the same order and that will eventually be inside the same value in the answer: that is, the whole column \(t_j * Y_{\{i,j,b\}}\) for some specific \(i\) and \(b\) across all \(j\).
\(\sum_j s * (B_{\{out,i,j,b\}} - t_j * Y_{\{i,j,b\}} * G) + e_{\{out,i,j,b\}}\)
\(= s * (B_{\{out,i,b\}} - (tY)_{\{i,b\}} * G) + e_{\{out,i,b\}}\)
Now we get to the puzzle: how do we combine together bits of different orders?
One naive thing we could do is just rescale and add:
\(\sum_{b=0}^{log(q)-1} (s * (B_{\{out,i,b\}} - (tY)_{\{i,b\}} * G) + e_{\{out,i,b\}}) * 2^b\)
The problem with this is that it multiplies up the errors of the high-order digits too much: the error of the highest-order term would get multiplied by \(2^{log(q)-1} = \frac{q}{2}\) so it would flood the whole range.
So here's what we do instead:
\(\sum_{b=0}^{log(q)-1} (s * (B_{\{out,i,b\}} - (tY)_{\{i,b\}} * G) + e_{\{out,i,b\}}) * G^{-1}(2^bG)\)
\(G^{-1}(2^bG)\) is doing all the work here. Basically, this is a bucket-wise left shift operator - it takes each \(log(q)\)-bit bucket \(tY\), and shifts them all to the left.
Remember, BGG+ encodings are of the form \(s * (B - G * m) + e\). And remember that \(G\) has this form:
This means that BGG+ encodings encode \(m\) simultaneously at every scale. And what we're doing here is we're moving higher-scale encodings of higher-order bits into the first column of each bucket. And because we're just doing additions and shifts, not multiplications, we avoid the error blowing up by more than the small amount that is introduced by the additions.
To see why \(G^{-1}(2^bG)\) has this shift effect, let's also look at \(G^{-1}\). On its own, \(G^{-1}\) is the right-inverse of \(G\), the bit decomposition operator (not a matrix).
Hence, plain \(G^{-1}(G)\) is just the identity matrix:
But if we multiply \(G\) by \(2\) before sticking it into \(G^{-1}\), each binary decomposition is shifted up by one place, and so we get the desired shift:
This is just a notational trick that allows the "left-shift every bucket" mechanism to be easily encoded into vector-and-matrix algebra. See also that the \(G^{-1}(2^bG)\) matrix is also clearly very low-norm (only ones and zeroes); this is another way to know that this step does not unreasonably blow up error.
The final outcome of this step is that you get a BGG+ encoding of \(tY\):
\(s * (B_{\{final,i\}} - G * (tY)_i) + e_{\{final,i\}}\)
Note that these are no longer "normal" encodings, both because the \((tY)_i\)'s are full-range values modulo q, and because the evaluator does not know the cleartext values. The evaluator cannot do any further BGG+ multiplication on them. But that's okay, because they do not have to; the only step the evaluator has left is to remove the "wrapping with \(s\)" so that we can get to our final goal, extracting \((tY)_i + e\).
To extract \((tY)_i + e\), we are going to diverge from BGG+ ABE fully. In ABE, we know that, in those cases where decryption is supposed to be possible, the answer \(C(tag)\) equals 0. \(G * C(tag)\) disappears, and that's exactly why we can extract the message. \(G * C(tag)\) plays the role of a blinding factor. Here, the use case is different: \((tY)_i\) is the entire thing that we want to extract.
Let's rewrite our BGG+ encoding as:
\(s * B_{\{final,i\}} - s * G * (tY)_i + e_{\{final,i\}}\)
Now, let's extract a single column from this expression - the lowest-order column in the last bucket.
\(s * b_i - s * g * (tY)_i + e\)
The choice of lowest-order column diverges from "traditional GSW decryption", where we extract the highest-order column, but remember: because of our bucket-wise shifting trick, by this point the lowest-order column contains information that was grabbed from the highest-order columns representing the values that we care most about (the message).
We constrain \(s\) so that its last value (which we'll denote \(s_{last}\)) equals -1. Also, notice that the column of \(G\) we chose, \(g\), is just a bunch of zeroes followed by a 1. Hence, we get a nicely simplified expression:
\(s * b_i - s_{last} * (tY)_i + e_i\)
\(= s * b_i + (tY)_i + e_i\)
Now, our task is to compute \(s * b_i\) so we can remove it.
Let us pull in one fact from a later section: the evaluator has "access" to \(s\) in the form of an encoded sample \(ct = (m \otimes s) P_L + e_L\), where \(m\) is the full input to the obfuscated computation and \(\otimes\) is the "tensor product". That is, \(m \otimes s\) is a vector of length \(len(m) * len(s)\) that contains \(s\) multiplied by the first value in \(m\), then right after that \(s\) multiplied by the second value in \(m\), and so on. Conveniently, the first value in \(m\) is fixed to be 1.
Now, we use the trapdoor machinery, described in the ABE section of the previous post, to make a low-norm preimage \(K_G\) that satisfies:
\(P_L * K_G = M\)
Here, \(M\) is a matrix that contains all of the \(b_i\)'s - that is, the extracted columns from each \(B_{\{final,i\}}\) matrix - and then is padded with extra zeroes to make the dimensions match up.
This ensures that \(ct * K_G\) evaluates to
\(((m \otimes s) * P_L + e_L) * K_G\)
\(= (m \otimes s) * P_L * K_G + e_L * K_G\)
\(= (m \otimes s) * M + e_g\)
Now, notice that only the first \(len(s)\) rows of \(M\) are nonzero, and the first \(len(s)\) values in \(m \otimes s\) are just \(s\). So the above reduces to:
\(s * M + e_g\)
Which is a concatenation of all of the \(s * b_i + e_{\{i,g\}}\) that we need.
Now, we can subtract that, and get the \((tY)_i + e_i\) values we need, which are our FHE decryption result. And then finally, the evaluator rounds, to get the final value of \(f(x, z)\).
Here we can once again see where the security comes from: the \(K_G\) "trapdoor" allows the evaluator to extract this only for those specific \(b_i\), and the \(b_i\) come from \(B_{\{final,i\}}\), which are bound to the exact shape of the circuit. If the evaluator computes \(s * b'_i + e{\{i,g\}}\) for some different \(b'_i\), then they would be left with a \(s * (b_i - b'_i)\) term blinding the \((tY)_i + e_i\), and would not be able to extract the answer.
Adjustments to f(x, z)
It turns out the security of the scheme we described above is only provable under one condition: that the outputs \((tY)_i + e_i\) are uniformly random - in fact, jointly pseudorandom across all \(2^L\) inputs. "Jointly pseudorandom" here basically means that if you were given unlimited access to the full exponentially-sized table (though still only polynomial computation time), you would not be able to distinguish it from random data.
This actually makes our work challenging. In a "normal" GSW decryption, the last entry of \(t * Y\) equals \(\frac{q}{2} * m + e\). This would give us two problems:
We can tackle these in turn.
First, we modify the function that we evaluate in FHE. We make \(z\) contain two secrets \((z_1, z_2)\): the secret input to the function, and a random PRF key. Then, we do \(FHE.eval(f', x, E[z])\), where:
\(f'(x, z) = \frac{q}{2} * f(x, z_1) - (\frac{q}{4} - e_{max}) + H_1(x, z_2)\)
Here, \(H_1\) is a hash function that returns values in \([0 ... \frac{q}{2}-2e_{max})\), where \(e_{max}\) is a bound on the largest possible error that our whole procedure could introduce. Formally, \(H_1\) must be a PRF ("pseudorandom function").
For correctness, it's okay to just think of it as a hash. However, in practice, computing this hash is where almost all of the evaluation time lies, and so making diamond iO practical will almost certainly involve heavily optimizing \(H_1\) to target its specific needs, and not using generic algorithms like SHA256.
In "normal" GSW, the \(\frac{q}{2}\) factor is implicit - of course you multiply the message by \(\frac{q}{2}\) because otherwise it might get smudged by the error. Here, we multiply the \(f(x, z_1)\) part by \(\frac{q}{2}\) but not the \(H_1(x, z_2)\) part, and we're okay with a few lower-order digits of that getting mangled by the error - the \(H_1(x, z_2)\) is not data we care about recovering, rather it's meant to be "maximum-range" pseudorandom noise that is there to smudge out the FHE and ABE-related noise. The goal of the \(\frac{q}{4} - e_{max}\) offset is to "center" the output of \(H_1\) (ie. make its range \([-(\frac{q}{4} - e_{max}), \frac{q}{4} - e_{max}]\)), so that you can round to the nearest \(\frac{q}{2}\) and then divide to get back \(f(x, z)\).
Second, we modify the function again, by xoring a hash into \(f\) itself:
\(f'(x, z) = \frac{q}{2} * xor(f(x, z_1), H_2(x)) - (\frac{q}{4} - e_{max}) + H_1(x, z_2)\)
From \(H_2\), we want a random oracle property. But \(H_2\) is not a bottleneck for efficiency, so using generic algorithms like SHA256 is great here.
To get the final output in the clear, we xor \(H_2(x)\) back out after we get the final \(f'(x, z)\) output from the diamond iO.
The result of this trickery is that \((tY)_i\) is now fully pseudorandom:
This technique is sometimes called "PROM bootstrap", and it is a generic transformation that converts "obfuscation for pseudorandom functionalities" into a more general form of obfuscation that works for any \(f\). Looking at a hash simultaneously as a random oracle and an implementable circuit is also sometimes considered a "sketchy" cryptographic assumption, though it is used widely today, eg. in recursive STARKs.
Finally, if we want to do "traditional" iO, which hides the function, instead of fixing a public function \(f\) and hiding a private input \(z\), then we do the trick we already did many times in the more conservative forms of obfuscation: make \(f\) be a "universal circuit" \(VM\) whose private input is a program \(P\), and that satisfies \(VM(x, P) = P(x)\).
How does the evaluator learn the input encodings?
So far, we have just magically assumed that the evaluator gets BGG+ encodings \(s * (B_i - G * m_i) + e_i\). But unfortunately things are not that simple. The obfuscator could construct \(len(m) + L\) such encodings, for \(m_i \in \{0,1\}\), with the same \(s\) (they would only have to provide both the \(0\) option and the \(1\) option for the \(x\) portion of \(m\)). But this is not secure: if you get two encodings with the same \(B_i\) and the same \(s\) but different \(m_i\) (if we're dealing with binary bits, that means \(0\) and \(1\)), then you can just subtract them and get \(s * G + (e_1 - e_2)\), leaking \(s\) in the clear.
So we have to somehow give the evaluator a gadget that lets them produce encodings for any \(m\), but with a different \(s\) for each \(m\). Even one bit of change in \(m\) should completely change the \(s\). This is where the core of diamond iO's machinery comes in.
The trick is as follows. First, remember the structure of \(m\): \([1, E[z], x, t]\). The only thing that changes between different evaluations is \(x\).
We will start off with a "base" message, \(m_0 = [1, E[z], 000...000, t]\), and a "base" secret \(s_0\).
For the i'th bit, we will define matrices \(M_{\{i,0\}}\) and \(M_{\{i,1\}}\) which are the identity matrix, but with the 1 in the slot corresponding to the i'th bit of \(x\) either deleted or moved to the first row. That is, \(M_{\{i,b_i\}}\) represents the idea "keep \(m\) as is, except change the i'th bit in \(x\) to \(b_i\)".
We also define low-norm matrices \(S_{\{i,0\}}\) and \(S_{\{i,1\}}\), whose goal is to transform the secret.
Hence, any final vector \(m_L\) can be expressed as \(m_0 * M_{\{1,b_1\}} * M_{\{2,b_2\}} * ... * M_{\{L,b_L\}}\). And the corresponding \(s_0 * S_{{1,b_1}} * S_{{2,b_2}} * ... * S_{{L,b_L}}\) gives us a unique secret \(s_L\). Our goal will be to "fuse" these transformations together, so that for each specific \(m_L\) you generate, you get BGG+ encodings constructed with a unique corresponding secret \(s_L\).
We will "fuse" these vectors and matrices by tensoring them together, and then wrapping them in encodings so that they cannot be unpacked.
A mini example - we'll start with tensoring the vectors \(m\) and \(s\):
The leftmost value in \(m\) is constrained to equal \(1\), and the rightmost value in \(s\) is constrained to equal \(-1\).
And now this is what tensoring matrices looks like (all un-written entries are zeroes):
See how \(M\) is in the shape we described above, and \(S\) is constrained so that it doesn't touch the last column, keeping the last value of \(s\) at -1.
A key property of tensoring is that if \(m_1 = m_0 * M_{\{1, b_1\}}\) and \(s_1 = s_0 * S_{\{1, b_1\}}\), then \((m_1 \otimes s_1) = (m_0 \otimes s_0) * (M_{\{1, b_1\}} \otimes S_{\{1, b_1\}})\). For convenience, we'll define \(Q_{\{i,b\}}\) as equaling \((M_{\{i, b\}} \otimes S_{\{i, b\}})\)
So far, the evaluator's formula is: start with \(q_0 = m_0 \otimes s_0\), multiply by each \(Q_{\{i, b_i\}} =M_{\{i, b_i\}} \otimes S_{\{i, b_i\}}\) in sequence, and then get \(q_L = m_L \otimes s_L\) at the end.
We have already gotten somewhere: we now have a way to generate some kind of encoding of each possible \(m_L\) that the evaluator might need, such that it's bound to a unique \(s_L\). The problem: so far, this encoding exposes \(m_L\) (including the \(t\) bits which the evaluator is not meant to know) and \(s_L\) completely in the clear.
The next step will be multiplying in matrices in the right places to "blind" these encodings at each step.
The obfuscator will give the evaluator an encoding \(p_0 ​=q_0​ * P_0 ​+ e_0\)
The obfuscator will then generate low-norm matrices \(K_{\{i,b\}}\), which satisfy \(P_{i-1} * K_{\{i,b\}} = Q_{\{i,b\}} * P_i + E_{\{i,b\}}\). This is allowed, again, because of the trapdoor mechanism.
The evaluator can then walk down the exponentially-sized tree of possible encodings. Here's what this tree looks like graphically. Notice that even though the tree is of size \(2^L\), the number of actually-distinct "edge matrices" that generate this whole tree is only \(2L+1\), including the final \(K_f\) that we'll get to later).
And here's why this works mathematically:
\(p_1 = p_0 * K_{\{1,b_1\}}\)
\(= q_0 * P_0 * K_{\{1,b_1\}} + e_0 * K_{\{1,b_1\}}\)
\(= q_0 * Q_{\{1,b_1\}} * P_1 + e_0 * K_{\{1,b_1\}} + q_0 * E_{\{1,b_1\}}\)
\(= q_0 * Q_{\{1,b_1\}} * P_1 + e_1\)
And then:
\(p_2 = p_1 * K_{\{2,b_2\}}\)
\(= q_0 * Q_{\{1,b_1\}} * P_1 * K_{\{2,b_2\}} + e_1 * K_{\{2,b_2\}}\)
\(= q_0 * Q_{\{1,b_1\}} * Q_{\{2,b_2\}} * P_2 + e_1 * K_{\{2,b_2\}} + q_0 * Q_{\{1,b_1\}} * E_{\{2,b_2\}}\)
\(= q_0 * Q_{\{1,b_1\}} * Q_{{2,b_2}} * P_2 + e_2\)
And so on all the way up until \(p_L = q_0 * Q_{\{1,b_1\}} * ... * Q_{\{L,b_L\}} * P_L + e_L\), where \(q_0 * Q_{{1,b_1}} * ... * Q_{{L,b_L}} = q_L\).
Notice \(e_{i-1} * K_{\{i,b_i\}}\) and \(q_{i-1} * E_{{i,b_i}}\) both collapse into \(e_i\). This means that \(K_{\{i,b\}}\), \(Q_{\{i,b\}}\) and \(q\) (and hence \(m\), \(s\), \(M_{\{i,b\}}\), \(S_{\{i,b\}}\)) all have to be low-norm (and they are).
Now, we have an actually-blinded encoding of \(q_L = m_L \otimes s_L\). But it's not quite the right format. We have:
\((m_L \otimes s_L) * P_L + e_L\)
We need:
\(s_L * (B_i - G * m_L[i]) + e_i\)
To cross this bridge, we add another trapdoor \(K_f\). It needs to satisfy:
\(P_L * K_f = u_1 \otimes B_{full} - I \otimes G\)
Here we just introduced a few pieces of new notation, so let's go through them:
Also notice that here (like the \(K_G\) case, unlike the \(K_{\{i,b\}}\) case), there is no error on the right side; that is fine, because the error in the final ciphertexts will come from elsewhere, and the value on the right is a public expression, so there is no security risk to not masking it.
Now, let's see what happens if we multiply \((m_L \otimes s_L) * P_L + e_L\) by \(K_f\):
\(((m_L \otimes s_L) * P_L + e_L) * K_f\)
\(= (m_L \otimes s_L) * P_L * K_f + e_L * K_f\)
\(= (m_L \otimes s_L) * u_1 \otimes B_{full} - (m_L \otimes s_L) * (I \otimes G) + e_f\)
\(= s_L * B_{full} - (m_L \otimes s_L) * (I \otimes G) + e_f\)
\(= s_L * B_{full} - m_L \otimes (s_L * G) + e_f\)
The last two lines are the most nonobvious. What's going on is: because \(m_L\) (like all message vectors) starts with 1, the first bucket of \(m_L \otimes s_L\) is just \(s_L\). And on the other hand, below the first bucket of rows, \(u_1 \otimes B_{full}\) just equals zero. Hence, \((m_L \otimes s_L) * (u_1 \otimes B_{full})\) just reduces to \(s_L * B_{full}\). And then the \(I \otimes G\) plays its role as many copies of \(G\) that all get multiplied by many copies of \(s\), one for each message value in \(m_L\).
(In the paper, they split up \(B_{full}\) into \(B_{att}\) (excluding \(t\) in the inputs) and \(B_t\), and run the above procedure on those two pieces separately. This is mathematically equivalent to what was described here. The conceptual reason to separate is that they are different kinds of data - the raw values of \([1, E[z], x]\) are given to the evaluator, but the raw values in \(t\) are not)
And the output is literally just the concatenation of all the \(s_L * (B_i - G * m_L[i]) + e_{\{f,i\}}\) BGG+ encodings that we need.
Re-summarizing diamond iO
Security
The most "controversial" part of this protocol is the mechanism for generating the BGG+ encodings for the input. This relies on two fairly new cryptographic assumptions, called all-product LWE and evasive LWE. Evasive LWE was introduced in Wee22; all-product LWE is unique to diamond iO.
These LWE assumptions are at the same time plausible, avoiding many pitfalls that we have come to understand from a decade of attempts to create novel LWE assumptions that ended up broken by "zeroizing" attacks, but also novel and risky. Evasive LWE is non-falsifiable in Naor's sense: formally, it says "for every algorithm that can distinguish X there exists an algorithm that can distinguish Y..." so it's hard to tell if you even have a counterexample. There are already known classes of situations in which evasive LWE is false; diamond iO deliberately chooses a type of evasive LWE assumption that avoids this.
More security analysis is needed to verify that these assumptions are safe.
Efficiency
Constructing the BGG+ encodings is relatively "easy" (in part because you can actually use a fan-out greater than 2, eg. a fan-out of 256 fills in 8 bits of \(x\) per multiplication). The hard part is the BGG+ evaluation, which has "ABE * FHE" overhead, where the FHE is itself GSW, which nobody uses in production because it's far less efficient than more mainstream algorithms like BFV. GSW is needed because it has "nice" algebraic properties, including no need for relinearization or key-switching, and the ability to put plaintext into any size bits of the ciphertext.
On top of this, there are other sources of inefficiency and limitation:
The main concrete bottleneck is actually computation of \(H_1(x, z)\) inside of the ABE * FHE. The main contributor to cost is depth (as depth increases the dimensions needed to handle the error). If the computation itself is deep, there are ways to "refresh" noise for BGG+ encodings, but these methods themselves depend on having a feasible \(H_1\). Hence, depth of \(H_1\) is the concrete bottleneck. Diamond iO currently uses a "tree" of Goldreich PRG executions to instantiate \(H_1\). This has multiplicative depth 3 per fan-out, and the number of fan-outs required is proportional to the input length.
These reasons are why, in the chart showing different types of obfuscation at the start of this post, diamond iO lands in the "very aggressive" and "planetary" point of the chart.
If we want to improve concrete efficiency of diamond iO, a few possible paths come to mind:
A key advantage of diamond iO is its friendliness to analysis, because of its simplicity. There are no towers of "protocols inside protocols inside protocols" like in more conservative obfuscation variants - the only nesting is the FHE inside of ABE. It can be understood without reference to the entire tower of constructions invented over the past 20 years by cryptographers: you don't need sublinear randomized encodings, functional encryption, garbled circuits, split FHE or even full ABE (we're using the core machinery of BGG+, but the details are sufficiently different that the advantage to someone who already knows how it works is much lower). For these reasons, I hope that diamond iO can get much more attention and analysis on both security and optimization, and we can get to an obfuscation protocol that we can actually run.