Biblio

The separation of manufacturing and design processes in the integrated circuit industry to tackle the ever increasing circuit complexity and time to market issues has brought with it some major security challenges. Chief among them is IP piracy by untrusted parties. Hardware obfuscation which locks the functionality and modifies the structure of an IP core to protect it from malicious modifications or piracy has been proposed as a solution. In this paper, we develop an efficient hardware obfuscation method, called Mystic (Mystifying IP Cores), to protect IP cores from reverse engineering, IP overproduction, and IP piracy. The key idea behind Mystic is to add additional state transitions to the original/functional FSM (Finite State Machine) that are taken only when incorrect keys are applied to the circuit. Using the proposed Mystic obfuscation approach, the underlying functionality of the IP core is locked and normal FSM transitions are only available to authorized chip users. The synthesis results of ITC99 circuit benchmarks for ASIC 45nm technology reveal that the Mystic protection method imposes on average 5.14% area overhead, 5.21% delay overhead, and 8.06% power consumption overheads while it exponentially lowers the probability that an unauthorized user will gain access to or derive the chip functionality.

{We study secret sharing schemes for general (non-threshold) access structures. A general secret sharing scheme for n parties is associated to a monotone function F:\0,1\n$\rightarrowłbrace$0,1\}. In such a scheme, a dealer distributes shares of a secret s among n parties. Any subset of parties T {$\subseteq$} [n] should be able to put together their shares and reconstruct the secret s if F(T)=1, and should have no information about s if F(T)=0. One of the major long-standing questions in information-theoretic cryptography is to minimize the (total) size of the shares in a secret-sharing scheme for arbitrary monotone functions F. There is a large gap between lower and upper bounds for secret sharing. The best known scheme for general F has shares of size 2n-o(n), but the best lower bound is {$Ømega$}(n2/logn). Indeed, the exponential share size is a direct result of the fact that in all known secret-sharing schemes, the share size grows with the size of a circuit (or formula, or monotone span program) for F. Indeed, several researchers have suggested the existence of a representation size barrier which implies that the right answer is closer to the upper bound, namely, 2n-o(n). In this work, we overcome this barrier by constructing a secret sharing scheme for any access structure with shares of size 20.994n and a linear secret sharing scheme for any access structure with shares of size 20.999n. As a contribution of independent interest, we also construct a secret sharing scheme with shares of size 2Õ({$\surd$}n) for 2n n/2 monotone access structures, out of a total of 2n n/2{$\cdot$} (1+O(logn/n)) of them. Our construction builds on recent works that construct better protocols for the conditional disclosure of secrets (CDS) problem.

Let Addk,N denote the Boolean function which takes as input k strings of N bits each, representing k numbers a(1),…,a(k) in \0,1,…,2N−1\, and outputs 1 if and only if a(1) + ⋯ + a(k) ≥ 2N. Let MAJt,n denote a monotone unweighted threshold gate, i.e., the Boolean function which takes as input a single string x ∈ \0,1\n and outputs 1 if and only if x1 + ⋯ + xn ≥ t. The function Addk,N may be viewed as a monotone function that performs addition, and MAJt,n may be viewed as a monotone gate that performs counting. We refer to circuits that are composed of MAJ gates as monotone majority circuits. The main result of this paper is an exponential lower bound on the size of bounded-depth monotone majority circuits that compute Addk,N. More precisely, we show that for any constant d ≥ 2, any depth-d monotone majority circuit that computes Addd,N must have size 2Ω(N1/d). As Addk,N can be computed by a single monotone weighted threshold gate (that uses exponentially large weights), our lower bound implies that constant-depth monotone majority circuits require exponential size to simulate monotone weighted threshold gates. This answers a question posed by Goldmann and Karpinski (STOC’93) and recently restated by Håstad (2010, 2014). We also show that our lower bound is essentially best possible, by constructing a depth-d, size 2O(N1/d) monotone majority circuit for Addd,N. As a corollary of our lower bound, we significantly strengthen a classical theorem in circuit complexity due to Ajtai and Gurevich (JACM’87). They exhibited a monotone function that is in AC0 but requires super-polynomial size for any constant-depth monotone circuit composed of unbounded fan-in AND and OR gates. We describe a monotone function that is in depth-3 AC0 but requires exponential size monotone circuits of any constant depth, even if the circuits are composed of MAJ gates.

Due to the increase in design complexity and cost of VLSI chips, a number of design houses outsource manufacturing and import designs in a way to reduce the cost. This results in a decrease of the authenticity and security of the manufactured product. Since product development involves outside sources, circuit designers can not guarantee that their hardware has not been altered. It is often possible that attackers include additional hardware in order to gain privileges over the original circuit or cause damage to the product. These added circuits are called ``Hardware Trojans''. In this paper, we investigate introducing necessary modules needed for detection of hardware Trojans. We also introduce necessary programmable logic fabric that can be used in the implementation of the hardware assertion checkers. Our target is to utilize the provided programable fabric in a System on Chip (SoC) and optimize the hardware assertion to cover the detection of most hardware trojans in each core of the target SoC.