Shamir's secret sharing scheme is an effective way to distribute secret to a group of shareholders. The security of the unprotected sharing scheme, however, can be easily broken by cheaters or attackers who maliciously feed incorrect shares during the secret recovery stage or inject faults into hardware computing the secret. In this paper, we propose cheater detection and identification schemes based on robust and algebraic manipulation detection (AMD) codes and m-disjunct matrices (superimposed codes). We present the constructions of codes for cheater detection and identification and describe how the cheater identification problem can be related to the classic group testing algorithms based on m-disjunct matrices. Simulation and synthesis results show that the proposed architecture can improve the security level significantly even under strong cheating attack models with reasonable area and timing overheads.

Most cache designs support single or double bit-level error detection and correction in cache lines. However, a single error may distort a whole byte or even more, resulting in much higher decoding complexity than that of bit-level distortions. Thereby this paper proposes a new group testing based error correcting code (GTB code) for byte-level error locating and correcting which provides much stronger protection for memories. This new class of non-binary GTB codes is generated from binary superimposed codes. Since it is encoded and decoded by binary matrices, no complicated Galois Field computations in GF(Q) such as multiplications and inversions are involved. Comparing with popular non-binary error correcting codes (ECC) such as Hamming, Reed-Solomon and interleaved codes, the GTB codes achieves up to 42% reduction of the decoding complexity (hardware cost × latency) for single-byte error correction, and up to 98% reduction for double-byte error correction. Moreover, given the length of codewords (e.g. 512 bits for cache lines), as the size of each Q-ary digit (byte) increases, the saving increases.

The security of communication or computational systems protected by traditional error detecting codes rely on the assumption that the information bits of the message (output of the device-under-attack) are not known to attackers or the error patterns are not controllable by external forces. For applications where the assumption is not valid, e.g., secure cryptographic devices, secret sharing, etc, the security of systems protected by traditional error detecting codes can be easily compromised by an attacker. In this paper, we present constructions for strongly secure codes based on the nonlinear encoding functions. For$(\mbi {k},\mbi {m},\mbi {r})$strongly secure codes, a message contains three parts:$\mbi {k}$-bit information data$\mbi {y}$,$\mbi {m}$-bit random data$\mbi {x}$, and$\mbi {r}$-bit redundancy$\mbi {f}(\mbi {y},\mbi {x})$. For any error$\mbi {e}$and information$\mbi {y}$, the fraction of$\mbi {x}$that masks the error$\mbi {e}$is less than 1. In this paper, we describe lower and upper bounds on the proposed codes and show that the presented constructions can generate optimal or close to optimal codes. An efficient encoding and decoding method for the codes minimizing the number of multipliers using the multivariate Horner scheme is presented.

The reliability and security of memories are crucial considerations in the modern digital system design. Traditional codes usually concentrate on detecting and correcting errors of certain types, e.g. errors with small multiplicities or byte errors, and cannot detect or correct unanticipated errors. In this paper we present a reliable and secure memory architecture based on robust Algebraic Manipulation Correction codes. These codes can provide a guaranteed error detection probability and can correct any error regardless of its multiplicity as long as the error stays for several consecutive clock cycles. The construction and the error correction procedure for the code will be described. The probability that an error can be successfully detected and/or corrected and the hardware overhead of the memory architecture based on these codes will be estimated.

Public-key cryptographic devices are vulnerable to fault-injection attacks. As countermeasures, a number of secure architectures based on linear and nonlinear error detecting codes were proposed. Linear codes provide protection only against primitive adversaries with limited attack capabilities. On the other hand nonlinear codes provide protection against strong adversaries, but at the price of high area overhead (200%-400%). In this paper we propose a novel error detection technique based on the random selection of linear arithmetic codes and explore the use of this technique for the protection of the multiplier, which is a basic block in many public-key cryptographic devices. The error detection technique does not imply any limitations on the types of errors at the output of the device, e.g., the multiplicity of the error does not have to be small. Under mild assumptions the proposed construction achieves near nonlinear code error detection performance at a lower cost (at most 50% area overhead for the protection of multipliers) due to the fact that no nonlinear operations are needed for the encoder and decoder.

Multi-level cell (MLC) nand flash memories are popular storage media because of their power efficiency and large storage density. Conventional reliable MLC nand flash memories based on BCH codes or Reed-Solomon (RS) codes have a large number of undetectable and miscorrected errors. Moreover, standard decoders for BCH and RS codes cannot be easily modified to correct errors beyond their error correcting capabilityt=[(d-1/2)], wheredis the Hamming distance of the code. In this paper, we propose two general constructions of nonlinear multi-error correcting codes based on concatenations or generalized from Vasil'ev codes. The proposed constructions can generate nonlinear bit-error correcting or digit-error correcting codes with very few or even no errors undetected or miscorrected for all codewords. Moreover, codes generated by the generalized Vasil'ev construction can correct some errors with multiplicities larger thantwithout any extra overhead in area, latency, and power consumption compared to schemes where only errors with multiplicity up totare corrected. The design of reliable MLC nand flash architectures can be based on the proposed nonlinear multi-error correcting codes. The reliability, area overhead and the penalty in latency and power consumption of the architectures based on the proposed codes are compared to architectures based on BCH codes and RS codes. The results show that using the proposed nonlinear error correcting codes for the protection of MLC nand flash memories can reduce the number of errors undetected or miscorrected for all codewords to be almost 0 at the cost of less than 20% increase in power and area compared to architectures based on BCH codes and RS codes.

Carbon nanotubes (CNTs) are considered as a possible successor to the CMOS technology. The adoption of these nanodevices for designing large VLSI systems, however, is limited by the unreliable manufacturing process. In this paper, we investigate the possibility of using CNTFETs to build SRAM arrays. We analyze the error mechanisms and show how stuck-at faults and pattern sensitive faults are caused by metallic tubes in different transistors of a 6-T SRAM cell. The results indicate the need of stronger error detecting codes than the widely used single-error-correcting, double-error-detecting codes in CMOS SRAMs.

Cryptographic devices are vulnerable to fault injection attacks. All previous countermeasures against fault injection attacks based on error detecting codes assume that the attacker cannot simultaneously control the fault-free outputs of a device-under-attack and error patterns. For advanced attackers who are able to control both of the above two aspects, traditional protections can be easily compromised. In this paper, we propose optimal algebraic manipulation detection (AMD) codes based on the nonlinear encoding functions and the random number generators. The proposed codes can provide a guaranteed high error detecting probability even if the attacker can fully control the fault-free outputs of a device-under-attack as well as the error patterns. As a case study, we present the protection architectures based on AMD codes for multipliers in Galois fields used for the elliptic curve cryptography. The results show that the proposed architecture can provide a very low error masking probability at the cost of a reasonable area overhead. The protected multiplier has no latency penalty when the predictor is pipelined.

Multi-level cell (MLC) NAND flash memories are very popular storage media because of their power efficiency and big storage density. This paper proposes to use nonlinear t-error-correcting codes to replace linear BCH codes for error detection and correction in MLC NAND flash memories. Compared to linear BCH codes with the same bit-error correcting capability t, the proposed codes have less errors miscorrected by all codewords and nearly no undetectable errors. For example, the proposed (8281, 8201, 11) 5-error-correcting code has no errors of multiplicity six miscorrected by all codewords while the widely used (8262, 8192, 11) linear shortened BCH code has 11 over 6 × A11errors in this class, where A11≈ 1014is the number of codewords of Hamming weight eleven in the shortened BCH code. Moreover, in spite of the fact that the Hamming distance of the proposed code is 2t+1, it can also correct some errors of multiplicity t+1 and t+2 requiring no extra hardware overhead and latency penalty. In this paper, the constructions and the error correction algorithm for the nonlinear t-error-correcting codes are presented. The architecture of the encoder and the decoder for the codes are shown. The error correcting capabilities, the hardware overhead, the latency and the power consumption for the encoder and the decoder will be analyzed and compared to that of the linear BCH codes to demonstrate the advantages of the proposed codes for error detection and correction in MLC NAND flash memories.

The security of the cryptographic device may be compromised if the FSM of the system is not properly protected. FSM protection architectures based on linear codes cannot provide a guaranteed level of protection under the assumption of a strong attack model. In this paper, we propose secure FSM architectures based on the idea of randomly selecting one code from a set of codes for each encoding and decoding operation. Assuming that the attacker is able to inject specific error patterns, randomly selecting one code from L codes as described in the paper can reduce the chance for the attacker to conduct a successful attack by a factor of L. The proposed techniques can achieve much higher security level than architectures based on linear codes with reasonable hardware overhead for cryptography applications (120% - 130% for the protection of the FSM for the Montgomery ladder algorithm). The security level of the proposed architectures can be increased by increasing L and the number of information bits k of the codes.

Linear single-error-correcting, double-error-detecting (SEC-DED) codes used in the design of reliable memories cannot detect and can miscorrect errors with large Hamming weights. We propose protection for memory devices based on extended Vasil'ev codes. These nonlinear SECDED codes have a minimum distance of four, fewer undetectable errors and fewer errors that are miscorrected than linear codes with the same dimension and redundancy. The extended Vasil'ev codes can provide for higher reliability in the presence of repeating errors or high rate of multibitupsets. As far as we know, our paper is the only one discussing application of efficient nonlinear codes for design of reliable memories. The proposed approach can be applied to RAM, ROM, FLASH and disk memories with relatively low hardware overhead.

Transaction-level modeling is an essential component of system-level design. This paper advocates using rendezvous, a construct common to concurrent programming languages, as a theoretical foundation for transactions. Compared to regular function calls, rendezvous are atomic and support multipartiness and parallel composition. However, scheduling multiparty rendezvous is a challenging task due to its NP-hard complexity. This paper describes a heuristic algorithm that significantly reduces the scheduling complexity in practice. It first constructs a relationship graph among rendezvous. It then simplifies the graph and translates it into a decision tree, which assists the scheduler in partitioning and pruning the search space. Our experimental results show that the algorithm is able to improve the efficiency of the scheduler significantly.

We propose an efficient technique for the detection of errors in cryptographic circuits introduced by strong adversaries. Previously a number of linear and non-linear error detection schemes were proposed. Linear codes provide protection only against primitive adversaries which no longer represents practice. On the other hand non-linear codes provide protection against strong adversaries, but at the price of high overhead. Here we propose a novel error detection technique, based on the random selection of linear codes. Under mild assumptions the proposed construction achieves near non-linear code error detection performance at much lower cost due to the fact that no non-linear operations are needed for the encoder and decoder.

Cryptographic hardware is vulnerable to power analysis attacks. To resist these attacks,special balanced dual-rail gates have been developed which have equal power consumption for all valid data values and transitions. A limitation of existing designs is that they require balanced routing of the dual-rail interconnect between gates. Natural process variation and suboptimal routing tools make it practically impossible to perfectly match the capacitances of the dual- rail pair making the balanced routing constraint difficult to satisfy. We present a general method and designs which achieve power balance in dual-rail circuits without requiring matching of gate output load capacitances or random masking.The method and design are based on a directional discharge protocol which ensures that both rails are always fully discharged and charged in each cycle.

The adaptive and active nature of fault based side-channel attacks along with the large arsenal of fault injection methods complicates the design of effective countermeasures. To overcome the unpredictability of fault attackers protection methods based on robust codes were proposed which can provide uniform error detection against all errors eliminating possible weaknesses in the protection. In this paper we evaluate and compare the error detection properties and hardware overheads of architectures based on robust, partially robust, and minimum distance robust codes for both public and private key cryptosystems.

Existing methods for gate level power attack countermeasures depend on exact capacitance matching of the dual-rail data outputs of each gate. Process variability and a lack of design tools make this requirement very difficult to satisfy in practice. We present a novel asynchronous dual-rail gate design which is power balanced, does not require capacitance matching of the data outputs, and is tolerant to process variability on the routed interconnect between gates.