Abstract In this paper, we study the security of the Key-Alternating Feistel (KAF) ciphers, a class of key alternating ciphers with the Feistel structure, where each round of the cipher is instantiated with n -bit public round permutation $$P_i$$ P i , namely the i -th round of the cipher maps $$\begin{aligned} (X_L, X_R) \mapsto (X_R, P_i(X_R \oplus K_i) \oplus K_i \oplus X_L). \end{aligned}$$ ( X L , X R ) ↦ ( X R , P i ( X R ⊕ K i ) ⊕ K i ⊕ X L ) . We have shown that our 5 round construction with independent round permutations and independent round keys achieves 2 n /3-bit security in the random permutation model, i.e., the setting where the adversary is allowed to make forward and inverse queries to the round permutations in a black box way.

In ICISC-05, and in the ePrint 2010/287, Patarin claimed a lower bound on the number of$2 q$tuples of$n$-bit strings$(P_{1}, \ldots, P_{2q}) \in ({\{0,1\}}^{n})^{2q}$satisfying$P_{2i - 1} \oplus P_{2i} = \lambda _{i}$for$1 \leq i \leq q$such that$P_{1}, P_{2}, \ldots $,$P_{2q}$are distinct and$\lambda _{i} \in {\{0,1\}} ^{n} \setminus \{0^{n}\}$. This result is known asMirror theoryand widely used in cryptography. It stands as a powerful tool to provide a high-security guarantee for many block cipher-(or even ideal permutation-) based designs. In particular, Mirror theory has a direct application in the security of XOR of block ciphers. Unfortunately, the proof of Mirror theory contains some unverifiable gaps and several mistakes. This paper provides a simple and verifiable proof of Mirror theory.

In cryptography, counters (classically encoded as bit strings of fixed size for all inputs) are employed to prevent collisions on the inputs of the underlying primitive which helps us to prove the security. In this paper we present a unified notion for counters, called counter function family, and identify some necessary and sufficient conditions on counters which give (possibly) simple proof of security for various counter-based cryptographic schemes. We observe that these conditions are trivially true for the classical counters. We also identify and study two variants of the classical counter which satisfy the security conditions. The first variant has message length dependent counter size, whereas the second variant uses universal coding to generate message length independent counter size. Furthermore, these variants provide better performance for shorter messages. For instance, when the message size is 219 bits, AES-LightMAC with 64-bit (classical) counter takes 1:51 cycles per byte (cpb), whereas it takes 0:81 cpb and 0:89 cpb for the first and second variant, respectively. We benchmark the software performance of these variants against the classical counter by implementing them in MACs and HAIFA hash function.

Multiple Bit Upsets (MBUs) have become increasingly more frequent with continued increase in memory density. The existing adjacent error correcting codes suffer from high probability of miscorrection for non-adjacent double errors. Miscorrection of a nonadjacent double error as an adjacent double error can reduce the reliability of the memory incorporating such codes. A constraint driven methodology is proposed here for deriving an error correcting code that can correct all single errors and correct the most likely double bit errors i.e., double adjacent errors in a memory while completely eliminating the miscorrection of the most likely nonadjacent double errors. The check bit overhead is minimal and comparable to SEC-DED and SEC-DAEC codes. The encoding and decoding schemes along with the associated hardware for the proposed code are also presented.

The paper presents a new channel allocation method for higher Embedded Deterministic Test (EDT) compression in SoC designs comprising isolated cores. It employs a test data reduction technique, which allows cores to interface with ATE through an optimized number of channels. This feature is subsequently used by a new test scheduling and test access mechanisms devised for both the input and output sides. Experimental results obtained for large industrial SoC designs illustrate feasibility of the proposed test application scheme and are reported herein.

This paper introduces a novel Test Access Mechanism (TAM) for chips with multiple isolated identical cores through which all the cores can be tested in parallel and at the same time accurate failure diagnosis can be achieved while requiring similar test resources (tester memory and tester channels) as for a single core. The proposed pipelined architecture relies on forming nonlinear equations on a very limited number of output pins that compress the outputs from the identical cores and solve them off-chip to reproduce the failure information of each core. A very nice feature of the proposed scheme is that the number of observation pins required to achieve a desirable level of diagnostic resolution does not scale with the number of identical cores and can practically be kept constant.

Conventional error correcting code (ECC) schemes used in memories and caches cannot correct double bit errors caused by a single event upset (SEU). As memory density increases, multiple bit upsets in nearby cells become more frequent. A methodology is proposed here for deriving an error correcting code through heuristic search that can detect and correct the most likely double bit errors in a memory while minimizing the miscorrection probability of the unlikely double bit errors. A key feature of the proposed ECC is that it uses the same number of check bits as the conventional single error correcting/double error detecting (SEC-DED) codes commonly used, and has nearly identical syndrome generator/encoder area and timing overhead. Hence, there is very little additional cost to using the proposed ECC. The proposed ECC can be used instead of or in addition to bit interleaving to provide greater flexibility for optimizing a memory layout and/or provide better protection from multiple bit upsets. It is also useful for small memories, e.g., content addressable memory or register files, where interleaving is not possible

In-place flipping of rectangular blocks/cells can potentially reduce the wirelength of a floorplan/placement solution without changing the chip area, In a recent work [Hao 05], the flipping optimization is solved through a binary decision diagram (BDD) based approach. However, the BDD-based approach is not scalable for large SOC designs with many blocks due to memory and runtime blow-up. This paper presents a new approach using the partitioned ordered partial decision diagrams (POPDD) for wirelength minimization. POPDD is based on a novel compact partial functional representation between flip configurations and corresponding wirelengths. By controlling the number of nodes allowed per POPDD and the iterations, easy trade-off between runtime/memory and accuracy/optimality can be achieved. Experimental results clearly demonstrate the efficiency of the proposed approach.

Existing techniques that incorporate decompressor constraints in the ATPG search/backtrace (e.g., Illinois scan) are based on combinational expansion in which each scan slice must be encoded using only the free-variables arriving from the tester in the current clock cycle. Sequential expansion is more powerful as it allows free-variables across multiple clock cycles to be used, however conventional approaches for sequential expansion that are based on linear finite state machines (LFSRs) and ring generators are not amenable to including the constraints in the ATPG backtrace because the constraints are too complex. This paper investigates the use of limited dependence sequential expansion to combine the benefits of sequential decompression with the benefits of incorporating the decompressor constraints in the ATPG backtrace. Analytical and experimental results are presented showing the benefits of the proposed approach

This paper presents an improved method to accurately estimate signal probabilities using ordered partial decision diagrams (OPDDs) [Kodavarti 93] for partial representation of the functions at the circuit lines. OPDDs which are limited to a certain maximum number of nodes are built iteratively with different variable orderings to efficiently explore different regions of the function. Signal probability bounds (upper and lower) are computed from the OPDDs. From each OPDD, information is extracted to tighten the signal probability bound and guide the variable ordering for the next OPDD. By restricting the size of each OPDD to a small number of nodes, they can be constructed and processed quickly to obtain a fast and accurate estimate of signal probabilities. Experimental results demonstrate the effectiveness of the approach compared with existing methods

A new method for synthesizing nonintrusive concurrent error detection (CED) circuitry is presented. The idea is to use single-bit parity to detect all errors affecting an odd number of bits and then synthesize a circuit to detect the even errors. A novel statistical sampling and expanding methodology is proposed for constructing the even error detection circuitry. A major feature of the proposed methodology is that it allows very efficient tradeoffs between error coverage and overhead. While CED schemes that use a fixed checker based on a particular error detecting code are not amenable to simplification without a major impact on coverage, the proposed scheme can easily facilitate significant reductions in overhead with only a small loss in coverage. Experimental results show that the proposed scheme can provide very high levels of soft error protection at a fraction of the cost of duplication