Obfuscation (Part II): Diamond IO

# Obfuscation (Part II): Diamond iO Source: [https://vitalik.eth.limo/general/2026/07/28/obfuscation_part_ii_diamond_io.html](https://vitalik.eth.limo/general/2026/07/28/obfuscation_part_ii_diamond_io.html) 2026 Jul 28[See all posts](https://vitalik.eth.limo/index.html) 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](https://eprint.iacr.org/2025/236),[presentation](https://simons.berkeley.edu/talks/sora-suegami-ethereum-foundation-machina-io-2025-06-24)\)\. 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](https://vitalik.eth.limo/general/2026/06/29/obfuscation1.html#attribute-based-encryption-abe)\. 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](https://eprint.iacr.org/2023/1716)and[AKY24](https://eprint.iacr.org/2024/1719)\. The third piece, the mechanism for constructing the ABE encodings of the inputs, originally came from[GGH15](https://eprint.iacr.org/2014/645); 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](https://vitalik.eth.limo/general/2026/06/29/obfuscation1.html#fully-homomorphic-encryption-fhe)\):  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](https://vitalik.eth.limo/general/2026/06/29/obfuscation1.html#attribute-based-encryption-abe), 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: 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 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 2. **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](https://eprint.iacr.org/2022/1204)\) - 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](https://eprint.iacr.org/2024/1742)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: - \\\(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](https://eprint.iacr.org/2023/906); 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](https://link.springer.com/chapter/10.1007/978-3-540-45146-4_6): 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](https://www.wisdom.weizmann.ac.il/~oded/PDF/prg10.pdf)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](https://eprint.iacr.org/2019/1085)against such constructions\. - Replace the GSW with some more efficient FHE \- either something BGV / CKKS flavor, or[packed GSW](https://security-kouza.github.io/paper/IEICE2016_hiromasa.pdf)\(see also:[my exploration here](https://github.com/vbuterin/crazy_gsw)\), 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\.