This letter proposes a concurrent fault detection scheme for a butterfly unit in an FFT processor. A fault in a butterfly unit is detected by recomuting. Input data to the butterfly unit is coded by a bit rotation and used for recomputing. The recomputed outputs are decoded and compared with the output for the first computation. The hardware overhead for the scheme is O(N) and the time overhead is O(log (N)) where N is the number of input data.

To provide the processor arrays with adequate fault-tolerant capabilities, a number of spare or redundant processors are prepared within the arrays. For such processor arrays, reconfiguration should be executed to bypass faulty processors. Concerning reconfiguration of processor arrays, Melhem presented a minimization problem (called the SPA problem). The SPA problem is to find an assignment of spare processors to faulty processors that minimizes the number of dangerous processors. Here, the dangerous processors are processors, for which there remains no longer any spare processor to be assigned when one more faults occur. In this paper, we present a more rigorous definition of the SPA problem, in which input parameters are n2 ordinary processors, 2n spare processors and m (mn2) faulty processors, and the output is an optimal assignment of spare processors to faulty processors, in the sense that the number of dangerous processors is minimum. Then, we develop an efficient algorithm based on the necessary and sufficient conditions, which allows highly efficient computation of spare processor assignment. The worstcase time complexity of the proposed algorithm is O(n2).

This paper considers a test set for a multibit shifter which can execute arbitrary bit length shifting/rotating operations. The multibit shifter consists of several stages of sub-shifters, each of which can shift/rotate its inputs by an arbitrary number of bits less than or equal to a predetermined constant. Outputs of one sub-shifter are shifted/rotated in the next sub-shifted. All of the sub-shifters have the same structure, and are constructed with multiplexers. Every sub-shirter is separately tested. All of the multiplexers in each sub-shifter are tested in parallel and exhaustively. A minimum test set for every sub-shifter can be obtained by the use of an algorithm which generates a Boolean 2pq matrix M such that any 2pp submatrix of M includes all bit patterns of length p, where p and q (pq) are the numbers of input lines in a multiplexer and those in a sub-shifter, respectively. A complete test set for the multibit shifter can be easily obtained as the union of minimum test sets for all sub-shifters.

A computing system, which plays an important role in our society, should be operated with high reliability and performance. A multisystem is one of the typical fault-tolerant computing systems, and is widely used in our society because of its high reliability and performance. In this paper we discuss a multisystem composed of two processors and buffer(s), and evaluate the system taking account of the reliability, performance and computational demands simultaneously. We propose two models for the system from the viewpoint of job assignment. Applying Markov renewal and queuing theories, we obtain the reliability/performance measures for each model. Using the numerical results of our models, we compare two models and show the impact of job assignment on the evaluation measures based on our numerical examples.

A rigorous analysis of magnetostatic forward volume wave resonators with circular metal edge is presented. The problem is cast into dual integral equations using Hankel transform. To solve the dual integral equations, along with an unknown function in the space domain, the kernel of the Hankel transform is also expanded in terms of the Jacobi polynomials. Thus the dual integral equations are systematically reduced to a set of algebraic equations. Theoretical results are compared with experimental ones to show an good agreement between them.

Robust test has been proposed to overcome the potential invalidation of the two-patten test due to hazards. However, it is difficult to generate robust test patterns and they may not exist for some stuck-open faults. In this paper, to overcome this difficulty, we propose a new testable design method with the robustness. Since a faulty gate is regarded as a tri-state element, the gate output node can be set to arbitrary logic value from the outside of a circuit. In the proposed method, on the basis of this idea, each output of the gate can be set to any logic value by an extra driver. Then, it is checked what value the output gives. Any stuck-open fault can be detected by one test pattern by this method which can be implemented relatively easily. To reduce the number of observalbe points, we also consider a method for selecting internal observable points without losing the property of the robustness. As a result, output nodes of reconvergent gates are used as internal observable points. Experimental results of the pattern generation for some benchmark circuits are given.

Hash functions are used to compress messages into digital signatures. A hash function has to be collision free; i.e., it must be computationally infeasible to construct different messages which output the same hash-value. This paper shows that five of the hash functions for digital signatures that are being discussed in ISO Standardization activities and/or recently proposed are not collision free. These hash functions are analyzed from the standpoints of their structure, the complementation property and the weak keys of the block ciphers used in them. As a result, it is clear that many pairs of messages can be created to generate the same hash-values. Therefore, the hash functions analyzed here are recommended to be revised or replaced by new ones that are collision free.

Spectral properties of an optically injection-locked semiconductor laser are analytically calculated and are experimentally verified the locking bandwidth is comparable to or smaller than the linewidth of a slave laser. In this case, the spectral lineshape becomes non-Lorentzian and its linewidth strongly depends on the locking bandwidth.

We present a family of cryptographic functions based on a conceptual model called majority M(n, m) circuit, and prove this family satisfies some properties which are required in cryptography: non-linearity, autoclave, flexible key length, computational efficiency, etc. A basic component of an M(n, m) circuit is a majority port with length n, or simply M(n) port, which is a Boolean device with n input bits and n output bits, characterized by a key that is a sequence of n symbols from the alphabet {0, 1, , }. This component is iterated m times to obtain an M(n, m) circuit, and to get a cascading effect, which is additional cryptographic property.

We study the following two kinds of one-way hash functions: universal one-way hash functions (UOHs) and collision intractable hash functions (CIHs). The main property of the former is that given an initial-string x, it is computationally difficult to find a different string y that collides with x. And the main property of the latter is that it is computationally difficult to find a pair xy of strings such that x collides with y. Our main results are as follows. First we prove that UOHs with respect to initial-strings chosen arbitrarily exist if and only if UOHs with respect to initial-strings chosen uniformly at random exist. Then, as an application of the result, we show that UOHs with respect to initial-strings chosen arbitrarily can be constructed under a weaker assumption, the existence of one-way quasi-injections. Finally, we investigate relationships among different versions of one-way hash functions. We prove that some versions of one-way hash functions are strictly included in others by explicitly constructing hash functions that are one-way in the sense of the former but not in the sense of the latter.

It was proven by Tompa and Woll that some specific random self-reducible problems have perfect zero-knowledge interactive proofs. In this paper, in order to determine a concrete set of random self-reducible problems, we consider a general problem of inverting a surjection from a finite group onto a finite set, and explore its random self-reducibility. The main result shows that there exist group-theoretic conditions for the random self-reducibility, and that any such random self-reducible problem has a perfect zero-knowledge interactive proof. By this result, some classes of random self-reducible problems are defined, and the inclusion relations among them are consequently clarified.

In this paper, we propose two-dimensional public key cryptosystems. We show the cryptosystems based on three schemes: the Rabin, the Williams and the RSA. It is proved that complete breaking of the proposed two-dimensional cryptosystems based on the Rabin scheme or the Williams scheme is computationally equivalent to factoring n used as the modulus. It is also proved that solving for relational information such as the ratio of plaintext pair for these systems is computationally equivalent to factoring n. It is shown that both two-dimensional cryptosystems based on the Williams scheme and the RSA scheme are uniquely decipherable.

An abstract enciphering machine model (AEM model); an encipherment evaluation model considering the recent trends in computer architecture is proposed. With the advances in computer communication, network security is an important issue. Although there exist several encipherment method, there is no abstract measure for comparing encipherment algorithms. The authors implemented several encipherment algorithms is C and assembler with several programming techniques. Observing the improvements in various programming techniques, especially with RISC processors, it has lead us to believe that the amount of algorithm-specific improvement techniques is small. It is noted that there exists an abstract machine model which can predict encipherment algorithm performance without implementation. The authors discuss the parameter value in the AEM model for encipherment evaluation comparing the real observation with the predicted values. Also, the upperbound speed of ideal fast encipherment algorithms is discussed with the AEM model.

Secret key encipherment is a basic technique for information security. The authors propose a new encipherment algorithm which is fast in software on 32-bit microprocessors. It is a 128-bit block encipherment algorithm and has fundamental security due to variable bit-rotations in the enciphering process. The algorithm is safe against trial-and-error key exhaustive attack and attacks utilizing the statistical properties of related plaintext and ciphertext pairs. The encryption speed is over 7 Mbps on a µP68030 microprocessor (25 MHz). This performance is about three or four times faster than that of FEAL-8. The algorithm will be effective for encryption in multimedia communication environments and as a hash function for message authentication, and digital signatures.

We proposed a membership authentication scheme in hierarchical multigroups where a user occupying a high position in a hierarchical structure can authenticate his membership of any lower position without revealing his identity or his higher position. In our scheme, a user can calculate each member information from only one piece of master secret information, a master secret key, and he convinces a verifier that he has the member information by using the extended Fiat-Shamir scheme. Two schemes are proposed to generate a master secret key. One is based on the blind signature and the other is based on Euclid's algorithm. Because each user stores only one piece of master secret key in order to prove various memberships, memory usage is very efficient in the proposed scheme. Moreover, Verifiers can check membership validity using public information independent from the number of users in an off-line environment. Therefore, our scheme is suitable for smart card applications.

A Multifiber mechanical switch with a plastic-molded ferrule and two guide-pins has been developed for transfer connection of 1.55µm zero-dispersion fibers. The switch has a low insertion loss of 0.35 dB and a switching time of 3 ms. In this letter, the structural design and performance are described.

This paper shows a general method how to construct a public key cryptosystem based on the γ-th residue problem. The necessary and sufficient conditions are presented which the parameters must satisfy for any γ (both for odd and even). The proposed cryptosystem has many applications, an efficient mental poker protocol, for example (Note that the number of cards is 52, which is even).

Based on the concept used in the generalization of concatenated codes, new coding and decoding schemes which have unequal symbol reliability are proposed. Error exponents for symbols in different positions of the codewords are derived over discrete memoryless channels and proved to have unequal values for any nonzero rates less than the channel capacity. Similar techniques presented in this paper are also applicable to product codes.