2026 Aug 21 See all posts
Special thanks to Nicholas Ho, Ran Canetti and Janmajaya Mall for feedback and review
In the last two parts of this series, we have gone through two of the major families of cryptographic obfuscation (iO) protocols: the mainstream and conservative line that tries to build it from somewhat-close-to-standard cryptographic assumptions, but at the cost of galactic overhead, and diamond iO, which adds more novel lattice-based assumptions, and reduces the overhead massively - but still not by enough to make it viable to run. In this post, we will go through the third major family being worked on today, called "local mixing".
The first thing to note about local mixing is that this is a totally different way of doing cryptography. There are no elliptic curves, no prime factorization and no lattices anywhere here. In fact, the closest thing that "regular" cryptography has to what is going on here is symmetric cryptography - encryption and hash function design.
In symmetric encryption and hash function design, there are no clean reductions to well-structured mathematical problems like "if you can crack this, that would imply you can quickly factor very large numbers". Instead, there is a fifty-year-long tradition of people attempting to create functions that are pseudorandom, mathematicians attacking them, and people figuring out design tricks that protect against those attacks, until the whole thing stabilized and we have secure hashes like SHA and BLAKE today. The goal of local-mixing is to take that tradition, and apply its ideas to circuits - achieving the properties that symmetric cryptographers have learned that their core building blocks need to achieve - while being functionality-preserving.
This is a wild and risky bet; it sits on a graveyard of failed attempts at white-box cryptography. The local mixing authors' hope is that if we push even more effort into this direction, and are smarter about it, including using AI to speed-run the three decades that hash functions took to stabilize and get to equal maturity in a few years, and at the same time we accept higher overhead, then we could make something that works.
How does local mixing work?
The goal of local mixing is to take a circuit \(C\) (made up of logic gates, eg. XOR, AND, NOT), and then apply a series of transformations to it, which preserve the functionality of \(C\), but progressively remove any ability to see its internal logic.
At a high level, the most important idea is exactly what you might guess from the name "local mixing": add a whole bunch of junk gates, shuffle everything around, and repeatedly replace small portions of the circuit with different sets of gates that have the same functionality.
But as you can see, that is only one step in the pipeline - the mixing step. The bulk of the cleverness is in the other steps in the pipeline - the steps that set up for circuit to be friendly to mixing, and that are optimized to remove some information leakage in the underlying circuit that is difficult for mixing to fully address.
Let us go through these steps one by one. We will start off with adding reversibility, because that step is necessary to set the stage for mixing, and then sandwiching. Then, we will talk about how mixing works. After that, we will talk about the limits of mixing as it stands today, and describe the major helper that was added to compensate: gadgetization.
Adding reversibility
As our example, we will use the same circuit that you may have already seen earlier in this series: the two-bit adder.
The first step is to convert the circuit \(C\) into a reversible circuit: a circuit that can be run backwards as well as forwards.
The main reason why this is done is that reversible circuits are far more friendly to mixing. A single reversible gate can be replaced with an arbitrarily large number of other reversible gates that all add up to having the same functionality as the original gate. Doing that with eg. AND and OR is much more difficult.
A key reason why is that irreversible computation collapses entropy: AND collapses 00, 01 and 10 into the same output, and likewise with OR and 01, 10 and 11. And so, long chains of irreversible gates will by default destroy huge amounts of information, proportional to the length of the circuit. A big-enough random reversible circuit is plausibly a secure cryptographic permutation, a big-enough random irreversible circuit degenerates into having only a few possible outputs.
There are ways to generate big irreversible circuits that don't have this property. For example, if the two-bit adder above returned both \(a+b\) and \(b\) itself, and avoided returning the x100 digit of \(a+b\) (so the addition becomes wraparound), then it would be a reversible circuit made out of irreversible gates: every output would have a single valid corresponding input. But such techniques basically end up reinventing reversible circuits, and so it's easier to just use reversible circuits as the base medium directly.
The choice to go with reversible circuits echoes time-worn wisdom from symmetric cryptography: even in irreversible applications like hash functions, the core underlying building block is a reversible permutation, and the irreversibility comes from a thin layer on top, precisely in order to make sure that for as long as possible, the full "state space" of the circuit is actually reachable.
In the case of our two-bit adder, making it reversible looks like this:
Notice a few things here:
- The new circuit is made out of many copies of an "r57" gate, which has three inputs and three outputs. The core logic is: flip wire C unless wire A equals 0 and wire B equals 1. The outputs on wire A and B stay the same. Each "standard" two-input-one-output gate can be implemented with two r57 gates.
- We now draw the circuit in a style that is easier to reason about mathematically. There is a well-defined "state" at each point in the execution - drawing a vertical line through the circuit, it's the values on each wire as they intersect that vertical line. Gates are arranged in sequence from left to right. Each gate has three coordinates that represents the positions of the three wires that it acts on.
- The circuit needs a whole bunch of extra "junk" inputs, of which one is expected to be 1 and the rest are expected to be 0. Two of these junk inputs (the topmost 0 and 1) assist the construction of "standard" gates through r57 gates. Others hold the result of intermediate computation. And the ones at the bottom are the space onto which the output is written.
You now have a two-bit adder that you can run forwards or backwards - sort of. If you try to just put 101 into the output position and zeroes in the other positions, and walk through the gates right to left, you won't wind up with 010 + 011 in the input positions, or 100 + 001, you'll wind up with total junk. The ability to actually run the original computation backwards depends on having not just the final output, but also the final values on each intermediate wire on the circuit.
The main thing that we have gained in this step is that we have an object that does the same thing as \(C\), but in a format that is naturally much more friendly to mixing.
Hardening
The next step is a hardening step. We take a reversible circuit \(C\) as a starting point - either the output of the previous reversibilization step, or some "natively reversible" circuit. The goal is to transform it in such a way that, without manipulating the gates, there is no way to use the circuit that does anything other than executing \(C\) on some input and getting the output.
There are two ways in which this condition gets violated:
- Reversibilization often (as above) creates helper wires (often called "ancillas"), that must be zero. If the ancillas are set to nonzero, it risks leaking internal behavior of \(C\) in arbitrary ways.
- The reversibilized version of \(C\) can, well, be run in reverse. We don't actually want this. We want to use reversible circuits as a medium, but we don't want \(C\) to be runnable in reverse.
The main technique to deal with this is called the hardened Toffoli technique, and works as follows.
We add two new sets of wires:
- One extra ancilla wire, called \(u_{\delta}\), as well as its helpers \(u_1 ... u_j\). The construction does not assume anything about \(u_{\delta}\)'s value - it can come in as 0 or 1, and it comes out with the same value that it came in. \(u_1 ... u_j\) can come in as any values, and leave unchanged.
- Output wires, new wires \(y_1 ... y_k\) that the output gets copied to. Again, the construction assumes nothing about these wires' contents: it simply xors \(C(inputs)\) into this position, so if they come in as \(y_1 ... y_k = X\) they come out as \(y_1 ... y_k = X \oplus C(inputs)\)
Here is what the gates look like:
- Run \(C\)
- If \(u_{\delta} = 0\), set \(y_1 ... y_k\ {\oplus}{=}\ C(inputs)\)
- Run \(C\) backwards, clearing all helper wires of \(C\)
- If all must-be-zero helper wires are zero (and all must-be-one helper wires are one), flip \(u_{\delta}\), otherwise keep it as is
- Repeat the above four steps again
Or, in diagram form:
We can walk through its behavior in both the normal case, and each of the "unusual" cases:
Normal case:
- \(u_{\delta}\) comes in as either 0 or 1.
- If all of the helper wires have their correct values, it gets flipped in the middle.
- Hence, in one of the two \(S'\) blocks, \(C(inputs)\) gets xor'd into the output wires, in the other, nothing happens.
- In each \(S'\) block, first \(C(inputs)\) gets computed, then (in one of the two runs) it gets xor'd into the output wires, then it gets "un-computed", which sets all wires except the output wires back to their original values, allowing the middle block to faithfully check them.
Some helper has an incorrect value:
- \(u_{\delta}\) does not get flipped in the middle, and so it's either 0 twice or 1 twice
- Hence, \(C(inputs)\) - or rather, the mangled execution of \(C(inputs)\) with some helper wire(s) flipped - either never gets xor'd into the output wires, or it gets xor'd in twice, in which case the copies cancel each other out
Run in reverse:
The full circuit run backwards just does the exact same thing as running it forwards!
- Each \(S'\) block is a perfect palindrome
- Each \(T\) block is not a palindrome in its gate arrangement, but it is designed to behave the same run forwards and backwards
- The fact that when you run in reverse the second \(T\) block is run before the \(S'\) doesn't matter, because that just flips \(u_{\delta}\), which we've established does not change the final outcome (it just flips which of the two \(S'\) blocks fires)
The authors' 2026 work includes a different approach, called sandwiching. You can think of sandwiching as a form of hardened Toffoli optimized for the use case where there is no reversibilization step, and it's directly obfuscating a random permutation (the most immediate use case is building public-key encryption).
Sandwiching has overhead \(\approx 2x\) instead of \(\approx 4x\) and does not require the extra \(u_{\delta}\) wire - it only does an \(S'\)-like step once. It does not need to defend against nonzero ancillas on the input, because it's intended to operate on random permutations that have no must-be-zero ancillas. It does defend against nonzero inputs on the output wires, but for that it uses a simpler trick: a set of random "slice" gates ensures that if those wires come in nonzero, the input gets completely mangled. The "compute \(C\) backwards" step is also replaced with an arbitrary random circuit \(D\).
Mixing
Mixing is conceptually very easy to understand: it's repeatedly making transformations to a small part of the circuit at a time. Each transformation preserves functionality while destroying (or rather, confusing and diffusing) some amount of visible information about structure. After many millions of rounds of transformation, each gate in the original circuit will have undergone mixing steps hundreds of times.
In the current code, mixing is done through a combination of several techniques, which we will describe in turn.
Generation mixing
Generation mixing works as follows:
- Make a giant table of all small circuits that have the same functionality (note: this will inevitably include "small circuits" that include pairs of sub-blocks that don't interact with each other at all)
- Repeatedly grab sets of gates from the circuit that are either contiguous, or don't have any gates in between that interfere with their functionality
- Check the table what "class" the set of gates you picked is in, and replace it with a random other small circuit from the same class
- Figure out the range of legal positions that the new sub-circuit is allowed to be in, before it moves so far that functionality breaks (eg. an input moves to before the output wire that last updated it). Move that gate to a random position in that range.
- Repeat
A large amount of the work in the local mixing repo is about optimizing this procedure: there's a canonicalization step which uses a few tricks to automatically identify small circuits that are the same even before the table, then conversion to a polynomial form, and then a "rainbow table" mechanism to store everything space-efficiently and make querying fast.
Here is a simplified diagram of how generation mixing works (the production version takes groups of ~7-10 gates, and the rainbow table is in the hundreds of gigabytes, though a much smaller "curated table" is also available):
Generation mixing is the most powerful step in the pipeline. It's able to change around the ways in which values inside a window are represented wholesale. This makes it the most effective step for introducing nonlinearities - getting to a point where any value \(x\) in the original circuit is represented only by a nonlinear function of the values in the obfuscated circuit. Generation mixing can also potentially "glue together" two pieces of the circuit that are far away in the original computation graph, replacing a sub-circuit that is a combination of those two pieces with one that interleaves them - and then further generations of mixing would make the interleaving hard to detect and reverse.
The pipeline does a huge number of rounds of generation mixing, with the goal of covering each gate in the circuit many times. It also does it in multiple phases: one which biases toward expanding the circuit, and the other which biases toward keeping the size the same, and at the end eventually shrinking it back down slightly.
Splitting
Splitting replaces r57 gates with a broader set of one and two-control gates. There is a bundle of techniques here.
(\(\oplus\) means xor, \(\lor\) means or, \(\land\) means and, \(\neg\) means not)
First, you can replace \(a\ {\oplus}{=}\ b \lor \neg c\) with either \(a\ {\oplus}{=}\ b;\ a\ {\oplus}{=}\ \neg b \land \neg c\) or \(a\ {\oplus}{=}\ \neg c;\ a\ {\oplus}{=}\ b \land c\).
Second, for any wire, you can do the following:
- Pick two positions A and B at which the wire gets modified
- At positions A and B, flip the wire - replace the gate modifying the wire with a gate that modifies that wire in the exact opposite set of circumstances
- In between A and B, negate that wire's role in any case where it's being read in a gate - if it was a positive control, make it a negative control, and vice versa
Splitting helps to destroy a particular type of visible information about the meaning of individual wires and gates: after enough rounds, it would not be practical to tell where some wire represents "x" and where it represents "not-x".
By broadening the set of gates being used, splitting also creates the conditions that are necessary to implement the next step, which allows us to shift around the order of gates with much fewer restrictions.
The crossing walk
Two gates that do not "collide" with each other, in the sense of one gate writing a value that the other reads, can be freely reordered. But two gates that do collide each other can also be reordered - as long as you add a new gate to compensate for the read and write switching places.
Here's how this works, split into three cases:
In principle, you can move a gate as far as you want, leaving behind "residues" for each gate that it crosses through.
Notice that this step takes gates with \(k\) controls (the above diagram shows \(k = 2\), but \(k \ge 3\) is also supported) and outputs gates with up to \(2k-1\) controls.
This is not a serious problem for the crossing walk itself. It just means that after many rounds of it, you might get gates with many controls. Additionally, at higher control counts, multiple "residue" gates may need to be created per crossing.
However, it is a problem if we decide to do crossing walks during generation mixing, rather than just after it as is the case now, because the current rainbow table only contains r57 gates. One could make a rainbow table that contains higher-control-count gates, but this risks exponentially increasing the rainbow table in size for the same level of coverage. The easiest solution would be to reduce each 3+ control gate back into a series of two-control gates.
fcompress
This step simplifies down a series of gates that modify a wire before it gets read.
This is primarily done not to do more hiding, but to shrink the program. The argument is that if we did not do this, the attacker could do it themselves anyway to have a smaller object to work with, so we might as well give the same efficiency gain to legitimate users.
Here are some of the simplifications:
And that's it for mixing!
One final thing worth mentioning here is gadgetization swaps. The gadgetization phase, which we will talk about later, includes a "role swapping" mechanism where two wires get their values and their roles swapped at some position in the circuit. The swaps that affect the output wires are undone at the end in a single step that extracts the right output wire to the right position. Even though it's done during the gadgetization phase, I still think of it as being a type of mixing. It allows wires to move "vertically", complementing the "horizontal" movement done by the crossing walk phase.
You can think of the different families of mixing as making "sudoku-like" transformations on the circuit that nicely complement each other:
Gadgetization: why do we need it?
To understand the need for this next phase, we should ask the question: what are some data leakages that inserting junk gates, shuffling and mixing are either bad at addressing, or fundamentally cannot address at all?
Here's one simple answer (it's not strictly correct, but for the moment, assume it is): each "wire" in \(C\), at each point in time, is still instantiated in the obfuscated circuit \(Obf(C)\) somewhere.
If an attacker has the original circuit \(C\) and the obfuscated circuit \(Obf(C)\), they can run the original circuit many times, see which wires in the obfuscated circuit are perfectly correlated with wires in the original circuit, and use that to determine the mapping from one to the other.
Of course, in real-world applications, the attacker does not have access to \(C\). But in many real-world applications, they almost do. Almost all of \(C\) is public, the only thing secret is some "embedded secret key" that \(Obf(C)\) is trying to hide. Even if the attacker has no access to \(C\) at all, they can do something like this:
- The attacker starts off knowing which input wires to \(Obf(C)\) correspond to which input wires to \(C\)
- Suppose you have an oracle that, given a gate in \(C\), finds which gate(s) and wire(s) in \(Obf(C)\) correspond to it (eg. this might be the correlation-based detector we described above)
- Enumerate all possible wires that we already know about, and all possible options for the next gate in the circuit. For each option, run the oracle. If it successfully finds the feature in \(Obf(C)\) that maps to that gate, then the gate must exist in \(C\)
- Keep going, using this attack to expose more gates further and further down \(C\), until you've exposed the whole thing
Adding junk gates does not affect this at all. Shuffling the gates does not affect this at all.
Mixing can affect this, in principle. For example, imagine you have a sub-circuit that does:
\(x\ {\oplus}{=}\ a \land b\)
You could replace that with:
\(x \ {\oplus}{=}\ y \oplus z \\ y\ {\oplus}{=}\ a \lor b \\ z\ {\oplus}{=}\ a \oplus b \\ x \ {\oplus}{=}\ y \oplus z \\ y\ {\oplus}{=}\ a \lor b \\ z\ {\oplus}{=}\ a \oplus b\)
The behavior is exactly the same: \(x\) gets flipped only if \(a\) and \(b\) are both 1. But in the replacement sub-circuit, the expression \(a \land b\) never gets instantiated.
What is going on is:
- \(a \land b\) gets replaced with \((a \lor b) \oplus (a \oplus b)\) (this is an algebraic identity)
- \(a \lor b\) and \(a \oplus b\) get applied separately, through \(y\) and \(z\) (wires that are borrowed and then put back in their place), so even these two components of \(a \land b\) are a few steps removed from each other.
In principle, this kind of transformation can be done by local mixing. Even more complex transformations can be done by local mixing. In principle, you could mix enough times that something like this just ends up happening to every wire many times over by random chance.
That was the authors' hope. But, so far, mixing has not proved to be good enough. There ended up being too many correlations between values in \(C\) and values in the obfuscation that remained. The authors visualize these correlations through heatmaps:
Gadgetization emerges as a way to more deterministically make sure that these kinds of correlations do not exist, even before any mixing starts. We take the problem "each wire in \(C\) must never be explicitly instantiated", and we explicitly solve for it.
Gadgetization: how does it work?
We replace each gate in the circuit with a "gadgetized gate". For example, here is the simplest possible gadgetization of an r57 gate:
In this design, we represent each wire \(w_i\) as two wires, \(s_i\) and \(r_i\), that satisfy \(w_i = s_i \oplus r_i\). The construction in the above diagram allows us to replicate the desired behavior over representations - flipping the representation of \(w_a\) only if either \(w_b = 1\) or \(w_c = 0\) - without ever explicitly instantiating \(w_a\), \(w_b\) or \(w_c\).
The construction here borrows ideas from multi-party computation, where the goal is identical: the participants start with a secret-sharing of the inputs and get to a secret-sharing of the outputs, without ever exposing any value in the computation (input, output or intermediate) to any single machine. The construction here is the simplest two-party case. Another source of inspiration is the secure hardware literature, eg. this work. In secure hardware design, a common model is the d-probing model: assume the adversary can read up to \(d\) wires, and mathematically guarantee that under this constraint they can learn nothing.
If we implement this kind of gadget, then we are guaranteed to get no single wire in the gadgetized output representing any specific wire of \(C\) - unless we get really unlucky and the mixing step undoes a gadgetization by sheer blind luck, which is currently very rare and mixing can be optimized to protect against further.
Now let's look at the full pipeline that makes gadgetization possible.
(Note: to simplify exposition, this description is mixing the secret-share gadget, which is from an older design, with a gadgetization pipeline that is as-of-today current)
The gadgetized gates that we discussed above go into the third phase, and they get interspersed with the swaps we mentioned earlier, which switch the role of two wires. The remaining phases are there to provide the scaffolding the makes the whole pipeline correct:
- The junk fill phase covers the newly added wires (\(z_1 ... z_5\) in the diagram) with junk, which is a high-degree function of the inputs. The high-degreeness is accomplished because the controls of each gate can come from either the \(x\) portion or the \(z\) portion, so the degree of each \(z\) wire keeps going up as it incorporates both \(x\)'s and other \(z\)'s
- The mask phase replaces \((value, junk)\) with \((value \oplus junk, junk)\). This brings the inputs into the correct form needed for the gadgetized gates. Once the mask phase is complete, there is no single wire in the gadgetized circuit that directly represents a wire in \(C\) - that responsibility is now shared between the two wires whose xor together equals the wire in \(C\).
- The gadgetized gates phase, as described above, contains a gadgetized gate for each of the actual gates from the reversibilized-and-hardened circuit, plus extra swaps thrown in
- The unmask phase brings \((value \oplus junk, junk)\) back to \((value, junk)\) so we can read off the outputs
- The route phase moves the outputs back to the positions that they are supposed to be at. You can think of it as "undoing all the swaps", though we only care about the wires representing outputs to \(C\).
- The refill phase adds more junk to all the junk wires. This is an extra precaution to make it harder for an adversary to see what the junk values are, making it harder to invert the masking.
Now, we have removed any direct one-to-one correspondences between wires in \(G\) (the gadgetized output) and wires in the original \(C\). We have even removed correlation: \(a \oplus b\) has zero correlation with \(a\) and with \(b\) - at least, as long as \(a\) and \(b\) are themselves independent with each other, which is approximately true with a high-quality junk-filling phase.
But there is still a major type of attack that remains.
Linear algebra attacks
We still have one type of relationship between the pre-gadgetized circuit \(C\) and the gadgetized circuit \(G\) that is discoverable: a linear (or more precisely, affine) relationship. Each wire \(w_i\) in \(C\), at some specific position in execution, corresponds to some \(g_j \oplus g_k\) in \(G\). And you can discover all such relationships, even if we expanded the gadgetization so there are eg. ten masks going into the xor, by using linear algebra attacks.
Here is how a linear algebra attack works. Consider \(c_{\{i,w\}}\), wire \(w\) in the state of \(C\) after executing the first \(i\) gates. Then take \(g_j\), the state of \(G\) after executing the first \(j\) gates. The goal will be to find linear relationships between \(c_{\{i,w\}}\) and \(g_j\) (mathematically, these are both vectors over \(F_2\)).
Do many executions of \(C\) and \(G\), so you have a vector of \(c_{\{i,w\}}\) values and a matrix of \(G\) states, \(G_j\). Append an extra column of all-ones to \(G_j\) to let us find dependencies that are offset-by-a-constant. Then, use Gaussian elimination (or, at very high dimension, slightly more efficient algorithms based on faster matmul eg. Strassen) to solve the system of linear equations:
\(G_j * v = c_{\{i,w\}}\)
Either this system has no solutions, or it has a solution. If it has a solution, then take even more executions of \(C\) and \(G\), and see for how many of these new executions it correctly predicts \(c_{\{w,i\}}\). If the number is very close to 0.5, then you've probably identified a spurious correlation, an accident. If the number is significantly above 0.5, then you've discovered at least a partially effective predictor of \(c_{\{w,i\}}\). For clear linear relationships like the two-value (or any multi-value) xor, it will return a correlation of 1.
This attack takes far longer than more naive attacks: Gaussian elimination is \(O(N^3)\), and Strassen-based approaches are \(O(N^{2.8})\) whereas finding perfect correlations between activations can be \(O(N*log(N))\) or even faster. But that's still not good enough.
And so the solution is to make the gadget represent \(w_i\) nonlinearly.
Nonlinear gadgetization
Instead of storing wires as \((s_i, r_i)\) satisfying \(w_i = s_i \oplus r_i\), we store them with a "carrier" wire \(c_i\) satisfying \(w_i = c_i \oplus B_{i1} \oplus B_{i2} \oplus ...\), where each "band product" \(B_{ij}\) is itself a product of some pseudorandomly generated "band values". Instead of the mask being linear, the mask is highly nonlinear.
When the value of a wire changes, it's always the carrier that changes: an xor to the carrier xors the underlying value. To apply a gate \(w_k\ {\oplus}{=}\ w_i \land w_j\), the goal is to apply a series of xors to the carrier of the output wire, which sum up to \(w_i \land w_j = c_i \land c_j \oplus c_i \land M_j \oplus M_i \land c_j \oplus M_i \land M_j\), where \(M_i\) and \(M_j\) are the two band products. However, we want to do this without ever instantiating this product or even any of its four cross-terms. The solution is a mechanism called Gray folding:
Gray folding is very flexible: it can be naturally extended to cover higher-degree monomials or expressions where different terms have a mixture of different degrees.
Here is one single gadget that uses this mechanism:
This gadget is now much more complex than the secret-sharing gadget we saw before. It accomplishes the goal of immunity to exact linear attacks on rows of G, which you can see by comparing heatmaps (this time, heatmaps that check for linear attacks, and not just value-to-value correlations):
Left: secretshare14 gadget (the secret share above plus some re-mixing), right: bandproduct92 (the 92-gate nonlinear-band-product gadget)
But as it turns out, even this approach is not perfect: it's still vulnerable to exact linear attacks on the whole trace of G.
The reason is fundamental: the series of xors applied to the carrier has to ultimately sum up to the actual output value of the gate, and no matter how much you try to put shuffles or other things into those xors, you can solve a system of linear equations to find the exact set of wires that sum up to the output value.
Here are the heatmaps against the trace of G:
Could you remove this vulnerability too? As it turns out, yes, but you have to do some extreme trickery: the value \(w_i\) has to be stored in multiple carriers in a nonlinear way. One winning equation is \(w_i = c_1(i) \land c_2(i) \oplus c_1(i) \land c_3(i) \oplus c_2(i) \land c_3(i) \oplus c_4(i) \oplus c_5(i)\).
The evaluation of a gate also has to be done in a way that avoids ever instantiating values any subset of which sum up to \(w_i\). Instead, we take the whole expression \(C_{\{c,out\}} = encode(gate(decode(C_a), decode(C_b), decode(C_{\{c,in\}})))\) (here each \(C\) stands in for five values), break it up into monomials, and then do Gray-coding-like tricks to apply each monomial to its target.
Here is one implementation, which I call nonlinear291. It uses 291 gates per gadget representing a single underlying gate.
It is fully immune to:
- Any exact linear attacks between \(C\) and the rows or trace of \(G\)
- Any correlations between \(C\) and individual values, or weight-2 expressions (xor, or, and, a-and-not-b) in the rows or trace of \(G\)
The simplest relationship between \(C\) and \(G\) that it does have is a 0.5 correlation between a wire value in \(C\) and an expression of three values in \(G\).
If you want to go full crazy, you can go even further, by stacking these constructions on top of each other. Here is a secretshare14 gadget, with each individual gate replaced by a full nonlinear291. I call this monster behemoth1415:
