Special thanks to Sora Suegami and Janmajaya Mall forfeedback and review.

In the last part of this series, we went through the full tech treeof the most mainstream and conservative line of cryptographicobfuscation (iO) protocols. These protocols allow you to "encrypt"programs in such a way that anyone can run the "encrypted" program onplaintext inputs and get plaintext outputs, without being able to seethe internal logic of the program. This can be used for all kinds of usecases, particularly situations where the program contains some secretkey internally, and obfuscating accomplishes the goal of giving someonea package that lets them do some things with the secret keyin some circumstances, but not anything else.

The biggest downside of these protocols so far has been theirliterally galactic runtime - if you actually try to figure out how longit would take to run one of them, you would get an answer longer thanthe lifetime of the universe. As a result, despite recent breakthroughsin feasibility, obfuscation protocols have so far been theoreticalcuriosities.

This post will describe in detail a different style of obfuscation:diamond iO (paper, presentation).This approach relies on much "braver" and more untested cryptographicassumptions, but it achieves having merely "planetary", rather thangalactic runtime - still infeasible today, but perhaps only a fewfurther optimizations away from becoming a reality at least for a fewuse cases.

Differenttypes of obfuscation

How does diamond iO work?

At a high level, diamond iO is built by modifying the BGG+14attribute-based encryption (ABE) scheme, explainedin the previous post. I highly recommend re-reading that sectionbefore continuing.

It'salso 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 thecomputation in FHE inside of ABE, and then gives the evaluator a way todecrypt the result only if it's actually the outcome of running thecomputation correctly. But the way that diamond iO uses thismachinery is different. First, it uses a completely different mechanismto do conditional FHE decryption. Second, it uses a completely differentmechanism to generate the encodings for the input.

These two modifications are connected to each other, and are the realreason why diamond iO manages to be much more efficient - it's "just ascomputationally intensive as" functional encryption, instead of being amuch 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 asecret
• \(B\) is apublic matrix, of which there is a different one for each "wire" in thecircuit
• \(m\) is thebit on that wire during the computation
• \(e\) is an"error"

(alternatively, you can add \(G * m\) instead of subtracting; bothgive equally valid and efficient schemes)

Given two \(B\) matrices representing two "inputwires" to an operation - either addition, multiplication or negation -you can generate a \(B\) matrix representing the outputwire. Given valid encodings for two inputs to an operation, you can getan encoding for the output - \(1 - m\), \(m_a + m_b\)or \(m_a * m_b\)- that is based on the \(B\) matrix representing the outputwire. Importantly, this is not fully-homomorphic encryption: tomultiply, you need to know either \(m_a\) or \(m_b\) inthe clear.

In BGG+14, there is a step at the end, which allows decoding apre-selected output, only if the value in the computation on some"output" wire equals 0. Here, we do not do that. Instead, what we willdo is just extract the data that we need from the encoding. But in bothcases, the decryption method depends on the encoding being based on aspecific matrix \(B_{final}\) representing the outputwire - this is how we enforce that decryption can happen if you did thecomputation correctly, but not in any other context.

The core of diamond iO is:

• Generate BGG+14 \(B\)-matrices and encodingsrepresenting the input \(x\), plus a few other things
• Run a computation, over these BGG+14 encodings, that converts \(x\) into anFHE ciphertext \(FHE.enc(f(x, z))\), where \(f\) ispublic and \(z\) is aninternal hidden input that the obfuscator is trying to hide
• Run another slightly modified BGG+14 step to FHE-decrypt theoutput
• Finally, do a "trapdoor" step, borrowing similar machinery to BGG+14decryption but using it in very different ways, to get the result - onlyin 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 allowsthis FHE decryption only in situations where the circuit that wascomputed is exactly the same circuit representing \(f\), andwithout fully leaking the key
• Some adjustments to \(f(x, z)\) to take into account thefact that this whole scheme is only secure if the outputs of the FHEdecryption are fully uniformly distributed random-looking, and thenconvert 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, themechanism for constructing the ABE encodings of the inputs, originallycame from GGH15; the newcontribution in diamond iO is to use it not to evaluate the wholeprogram (which turned out insecure) but to generate BGG+ encodings forthe inputs.

We will tackle these three pieces in turn.

The decryption step

Assume for now that the evaluator somehow gets as input fourtypes of BGG+ encodings of:

• \(1\) (thiswill be helpful later, for constructing these encodings)
• FHE encryptions of the fixed hidden input to \(f\), whichwe denote \(z\) (we'lldenote 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 valuemust 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 theBGG+ perspective, \(x\) and \(E[z]\) are both cleartext bits. Fromthe FHE perspective, \(z\) is a hidden input, of which onlythe 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 onBGG+ encodings requires having the underlying cleartext. But we canavoid this rule for additions, and for multiplications byknown 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, thenit would be \(G^{-1}(-B_a)\) instead)

We can allow \(m_a\) to be unknown (ie. given to usvia encodings only), as long as \(m_b\) is known.

This is an important fact for us. To see why, remember the structureof GSW decryption (also described in theprevious post in this series):

Because the evaluator knows all the bits of the actual executiontrace, including the final FHE ciphertext (which we'll call \(Y\)), wecan give the evaluator the FHE decryption key, \(t\), onlyas BGG+ encodings.

Let's see how the decryption works.

We want to compute \(t *Y\). We have only BGG+ encodings of \(t\), and wehave both the BGG+ encodings and the raw bits of \(Y\). So inprinciple we can do it.

But there's a problem: \(Y\) is given to us as a series ofbits. 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 thisexample, 4 bits) is a binary-encoding of a number, by conventionleast-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\) bitof the cell \(Y_{\{i,j\}}\), the encoding thatcomes out is scaled by \(2^b\).

For convenience, let's group together encodings of bits that are ofthe same order and that will eventually be inside the same value in theanswer: that is, the whole column \(t_j *Y_{\{i,j,b\}}\) for some specific \(i\) and\(b\) acrossall \(j\).

\(\sum_js * (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 ofdifferent 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 thehigh-order digits too much: the error of the highest-order term wouldget 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 workhere. Basically, this is a bucket-wise left shiftoperator - it takes each \(log(q)\)-bit bucket \(tY\), andshifts 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 everyscale. And what we're doing here is we're moving higher-scaleencodings of higher-order bits into the first column of each bucket. Andbecause we're just doing additions and shifts, not multiplications, weavoid the error blowing up by more than the small amount that isintroduced by the additions.

To see why \(G^{-1}(2^bG)\) has this shifteffect, let's also look at \(G^{-1}\). On its own, \(G^{-1}\) isthe right-inverse of \(G\), the bit decompositionoperator (not a matrix).

Hence, plain \(G^{-1}(G)\) is just the identitymatrix:

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 thedesired shift:

This is just a notational trick that allows the "left-shift everybucket" mechanism to be easily encoded into vector-and-matrix algebra.See also that the \(G^{-1}(2^bG)\) matrix is alsoclearly very low-norm (only ones and zeroes); this is another way toknow 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\)'sare full-range values modulo q, and because the evaluator does not knowthe 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\)" sothat 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. InABE, we know that, in those cases where decryption is supposed to bepossible, the answer \(C(tag)\) equals 0. \(G *C(tag)\) disappears, and that's exactly why we can extractthe message. \(G *C(tag)\) plays the role of a blinding factor.Here, the use case is different: \((tY)_i\) is the entire thing that wewant 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 - thelowest-order column in the last bucket.

\(s * b_i - s * g * (tY)_i+ e\)

The choice of lowest-order column diverges from "traditional GSWdecryption", where we extract the highest-order column, but remember:because of our bucket-wise shifting trick, by this point thelowest-order column contains information that was grabbed from thehighest-order columns representing the values that we care most about(the message).

We constrain \(s\) so that its last value (whichwe'll denote \(s_{last}\)) equals -1. Also, noticethat the column of \(G\) we chose, \(g\), isjust a bunch of zeroes followed by a 1. Hence, we get a nicelysimplified 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 theobfuscated 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\), thenright after that \(s\) multiplied by the second valuein \(m\), and soon. Conveniently, the first value in \(m\) is fixed to be 1.

Now, we use the trapdoor machinery, described in the ABEsection of the previous post, to make a low-norm preimage \(K_G\) thatsatisfies:

\(P_L *K_G = M\)

Here, \(M\) is amatrix that contains all of the \(b_i\)'s - that is, the extractedcolumns from each \(B_{\{final,i\}}\) matrix - and thenis 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\) arenonzero, and the first \(len(s)\) values in \(m \otimess\) 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, whichare 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 thosespecific \(b_i\), andthe \(b_i\) comefrom \(B_{\{final,i\}}\), which are boundto 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 onlyprovable 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 fullexponentially-sized table (though still only polynomial computationtime), you would not be able to distinguish it from random data.

This actually makes our work challenging. In a "normal" GSWdecryption, the last entry of \(t * Y\) equals \(\frac{q}{2} * m + e\). This wouldgive us two problems:

1. 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 errorcould somehow always cover the full range (difficult: worst-case andaverage-case tend to differ massively), LWE error is correlated with themessage so it would still leak information
2. The distribution of outputs \(m\)is itself not uniform, because most "natural" functions\(f\) are notrandom.

We can tackle these in turn.

First, we modify the function that we evaluate in FHE. We make \(z\) containtwo secrets \((z_1, z_2)\): the secret input tothe 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 ahash 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 couldintroduce. Formally, \(H_1\) must be a PRF ("pseudorandomfunction").

For correctness, it's okay to just think of it as a hash. However, inpractice, computing this hash is where almost all of the evaluation timelies, and so making diamond iO practical will almost certainly involveheavily 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 itmight 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 digitsof that getting mangled by the error - the \(H_1(x, z_2)\) is not data we careabout recovering, rather it's meant to be "maximum-range" pseudorandomnoise that is there to smudge out the FHE and ABE-related noise. Thegoal 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 getback \(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\), wewant a random oracle property. But \(H_2\) is not a bottleneck forefficiency, 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 diamondiO.

The result of this trickery is that \((tY)_i\) is now fullypseudorandom:

• Each highest-order bit is pseudorandom because it gets xor'd with abit of \(H_2(x)\), which we assume ispseudorandom (in the formal sense described by the pseudorandom oraclemodel)
• All lower-order bits are generated by \(H_1(x, z_2)\), which we again assumeis pseudorandom. The \(2e_{max}\)-wide empty space betweenthe ranges of possible outputs for the two possible message values isexponentially small compared to \(q\), so we can safely ignoreit.

This technique issometimes called "PROM bootstrap", and it is a generic transformationthat converts "obfuscation for pseudorandom functionalities" into a moregeneral form of obfuscation that works for any \(f\).Looking at a hash simultaneously as a random oracle and an implementablecircuit is also sometimes considered a "sketchy" cryptographicassumption, 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\), thenwe do the trick we already did many times in the more conservative formsof obfuscation: make \(f\) be a "universal circuit" \(VM\) whoseprivate input is a program \(P\), and that satisfies \(VM(x, P) =P(x)\).

How does theevaluator 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. Theobfuscator could construct \(len(m) + L\) such encodings, for\(m_i \in\{0,1\}\), with the same \(s\) (they would only have to provideboth the \(0\) optionand the \(1\) optionfor the \(x\) portionof \(m\)). Butthis is not secure: if you get two encodings with the same \(B_i\) andthe same \(s\) butdifferent \(m_i\) (if we're dealing with binarybits, that means \(0\) and \(1\)), then you can just subtractthem 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 themproduce encodings for any \(m\), but with a different \(s\) foreach \(m\). Evenone bit of change in \(m\) should completely change the\(s\). Thisis 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 differentevaluations 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 identitymatrix, but with the 1 in the slot corresponding to the i'th bit of\(x\) eitherdeleted 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 totransform 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\}}\). Andthe corresponding \(s_0 *S_{{1,b_1}} * S_{{2,b_2}} * ... * S_{{L,b_L}}\) gives us aunique secret \(s_L\). Our goal will be to "fuse"these transformations together, so that for each specific \(m_L\) yougenerate, you get BGG+ encodings constructed with a unique correspondingsecret \(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\), andthe rightmost value in \(s\) is constrained to equal \(-1\).

And now this is what tensoring matrices looks like (all un-writtenentries are zeroes):

See how \(M\) is inthe shape we described above, and \(S\) is constrained so that itdoesn'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\}}\) insequence, and then get \(q_L = m_L \otimess_L\) at the end.

We have already gotten somewhere: we now have a way to generatesome kind of encoding of each possible \(m_L\) thatthe evaluator might need, such that it's bound to a unique \(s_L\). Theproblem: so far, this encoding exposes \(m_L\) (including the \(t\) bitswhich 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\}}\). Thisis allowed, again, because of the trapdoor mechanism.

The evaluator can then walk down the exponentially-sized tree ofpossible encodings. Here's what this tree looks like graphically. Noticethat even though the tree is of size \(2^L\), the number ofactually-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\). Thismeans that \(K_{\{i,b\}}\), \(Q_{\{i,b\}}\) and \(q\) (andhence \(m\), \(s\), \(M_{\{i,b\}}\), \(S_{\{i,b\}}\)) all have to below-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. Wehave:

\((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\). Itneeds 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 gothrough them:

• \(u_1\) is avector that is 1 in the first position and 0 everywhere else. Dependingon context, it means "select the first (column / row / bucket /entry)"
• \(B_{full}\)is the concatenation of the \(B\) matrices for the encodings ofthe 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 ineven simpler terms, put a bunch of zeroes below \(B_{full}\)
• \(I\otimes G\) looks like many copies of \(G\) along adiagonal; it means "multiply by \(G\) bucket-wise"

Also notice that here (like the \(K_G\) case, unlike the\(K_{\{i,b\}}\) case), there is noerror on the right side; that is fine, because the error in the finalciphertexts will come from elsewhere, and the value on the right is apublic 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\) (likeall message vectors) starts with 1, the first bucket of \(m_L \otimess_L\) is just \(s_L\). And on the other hand, belowthe first bucket of rows, \(u_1 \otimesB_{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 manycopies of \(G\) thatall 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 theinputs) and \(B_t\), and run the above procedureon those two pieces separately. This is mathematically equivalent towhat was described here. The conceptual reason to separate is that theyare different kinds of data - the raw values of \([1, E[z],x]\) are given to the evaluator, but the raw values in\(t\) arenot)

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\) withthe 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 asthe i'th bit of the function-input part of \(m\), and (ii) mixing in a new factorinto 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 intothe final form: BGG+ encodings of \([1, E[z], x, t]\)
• The evaluator then does the BGG+ computation to compute theciphertext 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\) andthen rounding. Here, we have the bits of \(Y\), both as BGG+ encodings and ascleartext, and we have just the BGG+ encodings (no cleartext) of \(t\).
• The evaluator does this as a BGG+ multiplication, but with abucket-wise left shift operation to appropriately scale entries of \(t*Y\) thatrepresent 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 inthe bucket corresponding to the last entry of \(s\) (whichis fixed to -1). This lets us simplify to \(s * b_i + (tY)_i +e_i\)
• Finally, the evaluator has a "trapdoor matrix" which allowscomputing all \(s *b_i\) at the same time - but only for those specific \(b_i\). Thislets 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)\) inthe clear, to get the desired result \(f(x, z)\)

Security

The most "controversial" part of this protocol is the mechanism forgenerating the BGG+ encodings for the input. This relies on two fairlynew cryptographic assumptions, called all-product LWE andevasive LWE. Evasive LWE was introduced in Wee22; all-product LWE isunique to diamond iO.

• Evasive LWE says that it's safe to publishpre-images of a secret-bearing target. Roughly, if you have two matrices\(A\) and\(C\), andsamples \(sA +e_1\) and \(sC + e_2\) (both errors independent)that are indistinguishable from random, then publishing a low-normpreimage \(B\)satisfying \(A * B =C\) won't make the \(sA + e_1\) samples distinguishablefrom random. Note in particular that publishing \(B\) allowsan adversary to convert \(sA + e_1\) samples into \(sC +e_1B\); the assumption says that this is safe. In ourcase, 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-bearingtarget: \(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 buildingblocks 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-productmechanism we described above, is jointly pseudorandom. That is, thisparticular way of constructing many LWE samples with many secretsis safe, as safe as if all \(2^L\) secrets were trulyindependent. Note that this assumes that the initial errors entering theproduct are pseudorandom; in the diamond iO use case, because wepublished the \(K_{\{i,b\}}\) matrices, we can onlyassume that if we also accept the evasive LWE assumption.

These LWE assumptions are at the same time plausible, avoiding manypitfalls that we have come to understand from a decade of attempts tocreate novel LWE assumptions that ended up broken by "zeroizing"attacks, but also novel and risky. Evasive LWE is non-falsifiable inNaor's sense: formally, it says "for every algorithm that candistinguish X there exists an algorithm that can distinguish Y..." so it'shard to tell if you even have a counterexample. There are already knownclasses of situations in which evasive LWE is false; diamond iOdeliberately chooses a type of evasive LWE assumption that avoidsthis.

More security analysis is needed to verify that these assumptions aresafe.

Efficiency

Constructing the BGG+ encodings is relatively "easy" (in part becauseyou can actually use a fan-out greater than 2, eg. a fan-out of 256fills in 8 bits of \(x\) per multiplication). The hardpart is the BGG+ evaluation, which has "ABE * FHE" overhead, where theFHE is itself GSW, which nobody uses in production because it's far lessefficient than more mainstream algorithms like BFV. GSW is neededbecause it has "nice" algebraic properties, including no need forrelinearization or key-switching, and the ability to put plaintext intoany size bits of the ciphertext.

On top of this, there are other sources of inefficiency andlimitation:

• The whole mechanism also only tolerates low-depth circuits, becausethe error blows up a lot with each round of BGG+ evaluation andwith each bit added to the input (we casually papered over this in theexplanations 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 thannormal.

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 depthincreases the dimensions needed to handle the error). If the computationitself 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 GoldreichPRG executions to instantiate \(H_1\). This has multiplicative depth3 per fan-out, and the number of fan-outs required is proportional tothe input length.

These reasons are why, in the chart showing different types ofobfuscation at the start of this post, diamond iO lands in the "veryaggressive" and "planetary" point of the chart.

If we want to improve concrete efficiency of diamond iO, a fewpossible paths come to mind:

• Replace the tree of Goldreich PRG instantiations with something moreefficient
• Find some way to remove \(H_1\) completely. Perhaps this couldinvolve moving the noise generation into the input encoding step, thoughthere are known attacksagainst such constructions.
• Replace the GSW with some more efficient FHE - either something BGV/ CKKS flavor, or packedGSW (see also: myexploration here), and figure out how to make the conditionaldecryption work there
• Find some way to at least partially "collapse" the ABE and FHElayers together. Maybe this means modifying BGG+ to embrace the factthat FHE operates "natively" over approximate computation
• Find a way to remove the "subexponentially secure" requirement onthe proof side
• Find some optimizations that much more explicitly engineer aroundsolely trying to obfuscate the "iO-complete program" (decrypt an FHEciphertext only if you receive a valid STARK proving that it wasconstructed by FHE-evaluating the right circuit on valid inputs), whichyou 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 insideprotocols inside protocols" like in more conservative obfuscationvariants - the only nesting is the FHE inside of ABE. It can beunderstood without reference to the entire tower of constructionsinvented over the past 20 years by cryptographers: you don't needsublinear randomized encodings, functional encryption, garbled circuits,split FHE or even full ABE (we're using the core machinery of BGG+, butthe details are sufficiently different that the advantage to someone whoalready knows how it works is much lower). For these reasons, I hopethat diamond iO can get much more attention and analysis on bothsecurity and optimization, and we can get to an obfuscation protocolthat we can actually run.

免责声明：本文章仅代表作者个人观点，不代表本平台的立场和观点。本文章仅供信息分享，不构成对任何人的任何投资建议。用户与作者之间的任何争议，与本平台无关。如网页中刊载的文章或图片涉及侵权，请提供相关的权利证明和身份证明发送邮件到support@aicoin.com，本平台相关工作人员将会进行核查。