GET IN TOUCH
We take pride in personally connecting with all interested partners, collaborators and potential clients. Please email us with a brief description of how you would like to be connected with Galois and we will do our best to respond within one business day.
New Tools for Characterizing Circuits with Unhideable Functionalities
Untrusted foundries may attempt to steal the circuit-design IP of the integrated circuits (ICs) they are contracted to fabricate. Sending these designs to the foundry in the clear makes it easy for the foundry to do their fabrication, but also to steal the IP. Two decades of hardware-security research has aimed to thwart this by developing mechanisms that cryptographically transform cleartext circuit designs into related “opaque” designs that hide the original circuit’s functionality, preferably without inducing significant new power-area-delay costs. These opaque designs can be fabricated into ICs that realize them, and then restored back to the original circuit’s functionality by an authorized party.
Researchers have used several suites of benchmark circuits to evaluate the security and efficacy of candidate design-hiding mechanisms. Yet by viewing these benchmark circuits through an unexpected lens, that of the boolean Fourier transform, we find that most of them are inherently not fit for security evaluations. No mechanism could have hidden these circuits because, in principle, they can be reverse-engineered without ever seeing an opaque version of them. Black-box access to a restored chip, which can be achieved once manufactured devices enter the supply chain, suffices for reverse engineering. This was an unexpected finding, but the real advance is the set of efficient Fourier-based techniques that we developed to uncover it. These are tools that the circuit designer can apply, before anything goes to the foundry, to gain insights about the hidability of their circuit. If our tools reveal particular structural characteristics, then design hiding is unlikely to provide any protection against reverse engineering, and the power-area-delay overhead they will impose is for nought. ▉
To Hide, or Not To Hide My Circuit Design?
Behind every integrated circuit (IC) is a massive global supply chain that, roughly speaking, begins with an IC design firm and ends with the fabrication of the design into physical chips, which are then integrated into printed circuit board assemblies (PCBAs) and higher levels of assembly. Because the cost of building and operating a fabrication plant runs into the billions, most design firms operate in a so-called “fabless” model, in which they entrust their designs—think of these as complete descriptions of the circuits (i.e, logic gates and interconnecting wires) that implement a given set of functionalities—to an external, and not necessarily trusted foundry. For nearly two decades, hardware security researchers have looked for ways to limit the financial and reputational harm that may be suffered by IP authors if their designs are reverse engineered. Any number of bad things may be enabled if the foundry can, in effect, steal the IP: from overproduction or counterfeiting of chips, to potentially making it easier to insert stealthy hardware trojans or backdoors into the chips that ultimately end up on the market (with the IP author’s name on them). We note that, even if the foundry is trusted, the fabless model may result in a loss of controlled custody for the circuit IP.
We’ve talked about one foundational problem—namely, that there weren’t really any foundations for most of that time period—in a prior blog post. Here, we want to address a different aspect of the community’s approach to research on design hiding (DH): are the benchmark circuits that have been used to evaluate the security and efficacy DH schemes actually useful for this purpose? It turns out that the answer is largely “no.”
This is the marquis result of our recent work, Bad Benchmarks and a Fourier-Analytic Framework for Characterizing the (Un)Hideability of Combinational-Logic Circuits, which will soon appear at Cryptographic Hardware and Embedded Systems (CHES’26). In it, we explore a basic question about the value of design-hiding schemes:
If an IP author is going to suffer the power-area-delay overhead that DH schemes induce, how can they tell whether the security “juice” is worth that “squeeze”?
To set the stage for answering this question, let’s recall the accepted threat model. The IP author must ship some circuit design to the foundry for fabrication into ICs that, ultimately, will be placed on the market. If what’s sent to the foundry was produced by transforming the original circuit design with a DH scheme, then what the foundry returns will need to be restored to the original functionality, before it can function as intended and enter the supply chain. In any case, the foundry (or a proxy) can purchase one of these chips, and then run it on inputs of the foundry’s choosing. So, the accepted threat model assumes that reverse-engineering attacks can leverage black-box access to the original circuit’s functionality, obtaining arbitrary input-output pairs.
Here’s the rub: if the original functionality can be efficiently learned by computing only on observed input-output pairs, then no DH scheme can hide that functionality. Why? Because the attack works even if the foundry forgets entirely the circuit-design that it received; it only needs the input-output pairs.
We call functions that can be efficiently learned from input-output pairs (only) simple functions.
There are potentially many reasons a function might be simple. Our work explores one motivated by classical learning-theoretic algorithms: properties of a function’s Boolean Fourier spectrum. We develop techniques for efficiently measuring those properties by bringing together learning theory, Fourier analysis of Boolean functions, and model counting.
The resulting framework gives us one way to characterize circuit hideability—and reveals some uncomfortable facts about the benchmarks the community has been using to evaluate it.
In what follows, we will focus on functions, or their circuit representations, that take n bits of input x1x2…xn and have a single bit of output. This may seem restrictive, but you can take a circuit with m bits of output y1y2…ym and, for each yi, find the subcircuit (or “slice”) that computes yi from the inputs. Intuitively, if you can learn each slice of a circuit, then you can put these together and learn a circuit that computes the target function. In short: if the slices are simple, then so is the circuit.
Looking for simplicity in the Fourier spectrum
Boolean Fourier analysis has a rich connection to computational learning theory: well-known learning algorithms already tell us that certain kinds of Fourier structure can be exploited to efficiently approximate a function from its input-output behavior.
The intuition is easiest to see in the setting where most people first encounter Fourier spectra, the analysis of time-domain signals. Looking directly at a signal’s waveform may not reveal much structure. But transform it into the frequency domain and we might discover that almost all of its energy is concentrated in just a few frequencies.
If so, the full frequency range may be enormous and yet mostly irrelevant. Keeping only those significant frequency components can give us an excellent approximation of the original signal. Said another way, something that looked complicated in one representation turns out to be surprisingly simple in another. Fourier analysis of Boolean functions gives us an analogous view of circuits.
Just as a time-domain signal can be represented as a weighted sum of single-frequency signals, a Boolean function can be represented as a weighted sum of so-called “parity functions” over subsets of its inputs. For example, the Boolean function AND(x1,x2) = ½ + ½(x1) + ½(x2) - ½(x1x2) when, as is common in this domain, we map logical True to -1 and logical False to 1. You can quickly verify that if both x1 and x2 are True, then AND(x1,x2) = ½ +½(-1) + ½(-1) - ½(1) = -1, or True; and for any other logical setting of x1 and x2, AND(x1,x2) = 1, or False. The parity functions are the constant function (not a function of x1 or x2), x1, x2, and x1x2; the weights (½,½,½,-½) are the Fourier coefficients, and collectively they form its Fourier spectrum. Sticking with our analogy, you might think of the constant term ½ as the “DC component,” the term ½ x1 as the contribution of “frequency” x1 to the output value, and so on.
With a bit of thought, you might see that if your Boolean function has n bits of input, there will be 2n coefficients in the spectrum, one for each possible subset of the input bits (including the empty subset and the full set). When n is small, like in the AND example, computing the full spectrum is easy. Each coefficient can be computed exactly by recovering the entire input-output table. Even moderately sized inputs, say n=20, admit exact recovery of the input-output table, and hence exact computation of the 220 (roughly, one million) spectral components. For larger functions/circuits, say when there are n > 40 input bits, brute force becomes infeasible. Even reasonable approximations of individual coefficients quickly become out of reach, and remember that there are 2n of them.
Fortunately, we may not need the entire spectrum.
Suppose only a relatively small number of Fourier coefficients carry significant weight, e.g., for a circuit with 40 input bits, maybe only 216 = 65k out of 240 (roughly a trillion) coefficients have magnitudes that are noticeably above zero. In this case, we’d say that the spectrum is sparse.
Spectral sparsity (of various natures) is a structural property that has been studied extensively in computational learning theory. Well-known algorithms—including Goldreich-Levin and Kushilevitz-Mansour and their descendants—exploit Fourier structure to learn good approximations of Boolean functions without exhaustively searching their 2n-sized domains. The quality of the approximation depends upon several parameters, e.g., the total number of input-output pairs used for each estimated coefficient, and the number of coefficients for which estimates are computed. Intuitively, the more input-output pairs used in the approximation of a coefficient, the higher the quality of the approximation; but for a fixed resource budget, you may need to carefully spread these pairs across the target coefficients.
In principle then, Fourier analysis gives us one well-understood path from structure to unhideability: sparse Fourier spectrum supports efficient learning, which implies simplicity, and that means no DH scheme will be effective with respect to existing notions of security.
Finding a few needles in an exponentially large haystack
This is all very promising, yet there is still a real-world algorithmic problem. How does one efficiently determine that there are relatively few important spectral components? Moreover, how does one identify which ones they are? Naively, you’d compute some sort of approximation of all 2n coefficients, and then throw out the ones that don’t matter. For interesting numbers of input bits (n) this is a non-starter.
The Goldreich-Levin algorithm provides a clever starting point. Imagine a search tree, with the root holding a “bucket” that contains the sum total “weight” of all coefficients in the spectrum. As we descend the tree, that spectrum is progressively divided into smaller, disjoint buckets of coefficients. At the leaves, buckets contain the weight of an individual parity function. This is conceptual; we don’t want to compute this entire search tree, since that’s no easier than computing each term individually. Instead, imagine that just below the root, we have split the root bucket into two sub-buckets that are disjoint with respect to their contents. If one bucket holds, say, 97% of the total weight, then we can safely skip computation of the subtree that would grow from the other bucket. That bucket cannot contain any significant terms.
Great, but there’s still the matter of deciding how to split the buckets at each level, and under what conditions you can discard a subtree.
How do we efficiently determine which branches are worth exploring?
Classical black-box techniques answer this by querying the function and statistically estimating quantities such as Fourier coefficients or the weight contained in portions of the spectrum. These techniques are quite practical in some cases—indeed, our experiments show that the black-box methods can be surprisingly competitive, under the right circumstances. But statistical estimation can also become expensive (or lose accuracy, if you fix the computational budget) as the quantities you want to estimate get smaller, and as the domain grows.
The key phrase here is “black-box methods,” i.e., ones that only use information gained by querying the circuit on selected inputs and observing the outputs. But let’s pop the stack and recall our application. An IP author wants to know if the overhead caused by applying a design-hiding scheme to their circuit is worth it. The IP author holds the original circuit, so they may be able to exploit this “white-box” information to speed up (or make more accurate) determinations of simplicity from spectral information. If they can efficiently determine that their circuit is simple, then they may choose to skip the DH scheme in favor of their original, optimized design. This technique allows designers to better manage their complex tradespace using objective measures.
This observation leads to the question of how to exploit the extra information to make a faster, more accurate version of the Goldreich-Levin algorithm for finding the significant Fourier components. And this is where model counters enter the story.
Turning Fourier analysis into counting
Consider just one of the input bits, say x1, and what is its influence on the output of the circuit. By this, I mean the following: set the rest of the bits x2x3…xn however you like, and hold them steady. Now look at the outputs when x1 is True and when x1 is False. If these are the same, then for this setting of x2x3…xn the value of x1 is irrelevant. If the value of x1 were irrelevant to the output for every setting of x2x3…xn then what’s the point of having x1 at all? It has no influence on the computation, (Foreshadowing a bit, if x1 has no influence on the output, it can’t have a significant Fourier coefficient, either,) but maybe the value of x1 is relevant to some settings of x2x3…xn. The notion of influence makes this concrete. In particular, the influence of xi measures how often flipping that input changes the output. Mathematically, if the circuit computes a Boolean function f, the influence of xi is Infi(f) = Pr[f(x1…xi…xn) ≠ f(x1…(¬xi)…xn)] where the probability is over uniform choice of the input x1…xn.
With only black-box access, we can estimate this probability by sampling many random n-bit inputs, and counting how often flipping xi changes the output value. But observe that with a circuit Cf for f in hand, we can make a new circuit Mf for which Mf(x1...xi…xn) is True if and only if f(x1... xi…xn) ≠ f(x1…(¬xi)...xn): namely, Mf(x1…xi…xn) = Cf(x1…xi…xn) ⊕ Cf(x1…(¬xi)…xn).
To stress the point, the IP author can make this Mf circuit because it has Cf in hand. So the IP author can determine the influence of any particular input bit by counting the number of inputs that cause Mf to evaluate to True.
If you have any experience with, say, SAT- or SMT-solvers, you’ll recognize immediately that you can feed Mf to a model counter to get the answer you need! Thus, the heavy lifting in computing the influence of an input bit can be offloaded to a model counter. The IP author just needs to hand it this Mf, which is essentially just two copies of their original Cf circuit.
Okay, so how does this help? It turns out that there is another, equivalent way to compute the influence of an input bit xi: effectively, it is the total spectral “weight” of all parity functions (i.e., all spectral terms) that contain xi. For example, if x1 is the target, then its influence is determined by the weight of x1, x1x2, x1x3, x1x2x5,... but not (say) x2x3x7 or x2x3x4x18 because these don’t contain x1. So this suggests a way to split the buckets in the Goldreich-Levin tree: if x1 has large influence as computed by the model counter, then split the root bucket into one bucket containing all terms with an x1 in them, and one bucket containing all terms without an x1 in them. There’s a good chance that the first bucket (whose weight is the influence of x1 scaled by a known constant) will contain significant spectral components. Using model counters, we can compute the influence of all input bits, order them from greatest influence to least, and split buckets based upon this ordering as we move down the Goldreich-Levin tree. There are other tricks, but this should give the gist. In the small example we use to illustrate the technique in the paper, influence information alone allows the accelerated algorithm to eliminate six of eight Fourier terms from consideration. That may sound modest until 2n stops being eight and starts being astronomical.
It turns out that the same basic idea of feeding circuits that the IP author can easily derive from their original Cf to a model counter has benefits beyond computing the influence. Using related circuit constructions, we can compute or approximate other quantities useful to the Fourier analysis. Our new techniques are empirically shown to achieve an 88x speedup, on average, over traditional ones, and to provide more accurate estimation.
So, what about those benchmark circuits?
This brings us back to the question we started with. We applied our framework to circuits from five benchmark families used in hardware research: MCNC, ISCAS’85, ISCAS’89, ITC’99, and EPFL. The results were striking.
Most of the circuits we examined from ISCAS’85 and MCNC—the two benchmark suites historically used most heavily to evaluate design-hiding schemes and attacks—satisfy our criteria for simplicity. Their Fourier structure indicates that their functionality can be efficiently learned. That makes them poor candidates for evaluating whether a design-hiding mechanism protects functionality.
Suppose a new DH mechanism prevents existing attacks from recovering the original circuit. If the underlying function can nevertheless be learned efficiently from its input-output behavior, what security property has the experiment actually demonstrated?
Conversely, if an attack succeeds against a protected benchmark, did it exploit a weakness in the DH mechanism—or was the underlying function simply easy to learn?
Without some understanding of the intrinsic simplicity of the benchmark, those results become difficult to interpret.
The benchmarks are the result. The framework is the opportunity.
The headline result of our paper is clear: many of the circuits that the design-hiding community has relied on for years appear to be fundamentally unhideable. But we think the more interesting contribution is the ability to ask the question systematically, and address it with efficient computations.
Fourier analysis gives us one mathematically grounded way to connect structural properties of a circuit's functionality to known learning algorithms. Circuit constructions and model counting let us exploit access to the original design to evaluate those properties. Techniques such as influence-based pruning of the traditional Goldreich-Levin tree help us avoid searching portions of an exponentially large Fourier spectrum that cannot matter very much.
On the flip side, passing our tests doesn't mean that a circuit is hideable. Another learning algorithm, exploiting entirely different structures (potential in other representations), might surface a different kind of simplicity.
That isn't a limitation, it suggests an opportunity for research. What other structural properties imply learnability? Can we give IP authors efficient ways to test for them? How should we build new suites of benchmark circuits, whose properties viz-a-vis hideability are understood rather than simply assumed?
I said this paper isn’t about attacks, and it isn’t. But… it is important to understand how much of the Fourier structure is maintained by this or that DH scheme. Why? If the opaque circuit, the output of the DH scheme that is delivered to the foundry, maintains much of the original circuit’s Fourier structure, then the foundry could use our techniques to recover the original circuit’s functionality. In short, is white-box access to the opaque circuit essentially as useful as white-box access to the original function, at least with respect to our simplicity test? Future work will find out.
When you pair all of this with the directions surfaced in our previous work, you begin to see the rich and unexplored research space more clearly. We will continue to unfold the map of challenges in future posts, and invite you to contact us at Galois if you want to know more.
.png)
