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.

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.

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.

Minimizing intersite data transmissions is important for the join operation between two fragmented relations in distributed databases. In this paper, we examine communication costs of distributed joins when data redundancy and semantic information associated with fragments are not considered. We use a bit vector filtering technique to minimize unnecessary data transmissions in a computer network. The procedure of a distributed join algorithm is proposed and its communication cost is analyzed with filtering error in hashing. We performed computational experiments to show effect of the communication cost of the proposed algorithm in the number of sites and the semijoin selectivities. The experiments also include performance comparison between the proposed algorithm and another semijoin method which recently appeared in the literature. The results show that the communication cost of the proposed algorithm is smaller than that of the semijoin method the fragmented relations.

A new interpolation procedure is reported for fast Fourier transform (FFT) spectra of exponentially damped sinusoids multiplied by a family of sinα(X) windows. Using the rectangle (α0), the sine lobe (α1) and the Hanning (α2) windows we show interpolation formulas of the frequency, damping constant and amplitude determination. On the basis of these formulas, generalized interpolation formulas to which any integer value of α is applicable are derived. The formula of frequency determination is very simple and useful. An interpolated frequency is given from two ratios between just the largest three intensities on the spectral line shape in the discrete power spectrum. The interpolated frequency is used to determine the damping constant and amplitude. The characteristics of interpolation are examined for various integer values of α. Simulation results show that as a value of α increases, interpolation errors become remarkably reduced compared with those in Lorentzian interpolation corresponding to the case, α0. Thus a reasonably large value of α can be used in the generalized formulas for highly accurate interpolation.

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.

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.

Superdistribution is an approach to distributing software in which software is made available freely and without restriction but is protected from modifications and modes of usage not authorized by its vendor. By eliminating the need of software vendors to protect their products against piracy through copy protection and similar measures, superdistribution promotes unrestricted distribution of software. The superdistribution architecture we have developed provides three principal functions: administrative arrangements for collecting accounting information on software usage and fees for software usage; an accounting process that records and accumulates usage charges, payments, and the allocation of usage charges among different software vendors; and a defense mechanism, utilizing digitally protected modules, that protects the system against interference with its proper operation. Superdistribution software is distributed over public channels in encrypted form. In order to participate in superdistribution, a computer must be equipped with an S-box--a digitally protected module containing microprocessors, RAM, ROM, and a real-time clock. The S-box preserves secret information such as a deciphering key and manages the proprietary aspects of the superdistribution system. A Software Usage Monitor insures the integrity of the system and keeps track of accounting information. The S-box can be realized as a digitally protected module in the form of a three-dimensional integrated circuit.

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.

Optimal static load balancing of multi-class jobs in a distributed computer system model is considered. This model is an extension of the Tantawi and Towsley single job class model to a multiple job class model. Some properties of the optimal solution are shown. On the basis of these properties, a straight-forward and efficient algorithm optimal load balancing of multi-class jobs is derived. We compare the performance of our algorithm and two other well known algorithms for multi-class jobs, the flow deviation algorithm and the Dafermos algorithm. Our algorithm and the flow deviation algorithm both require a comparable amount of storage that is far less than that required by the Dafermos algorithm. In the results of numerical experiments our algorithm and the Dafermos algorithm required mutually comparable computation times for obtaining the optimal solution which were far less than that of the flow deviation algorithm.

This paper presents a queueing analysis method for the M/M/1 queue with service interruptions. The queueing model considered here is applicable to voice/data communication systems, communication swiching systems and so on. Assuming that both on- and off-periods of the server are generally distributed, the steady-state distribution of the number of customers in the system, including one unknown function, is derived by using the supplementary variable technique. The mean number of customers in the system is obtained by approximating one unknown parameter. The proposed approximate formula requires only the first two-moment input parameters, which is simple enough for numerical calculations. Some numerical examples are compared with the exact and simulated results and show good accuracy of the proposed formula for a practical situation.

This paper demonstrates and confirms that a large-network-oriented key sharing method called the key predistribution system (KPS) is really practical and useful for supporting end-to-end cryptographic communication, by presenting a prototype implementation of KPS using special IC cards and its application to facsimile systems. This prototype can build a secure channel over any ordinary facsimile network using the following types of equipments: (1) an IC card implementing a linear scheme for KPS and the DES algorithm, (2) an adaptor-type interface device between the IC card and a facsimile terminal with no cryptographic function, and (3) a device for each managing center of KPS.

S(ubstitution)-boxes are quite important components of modern symmetric cryptosystems. S-boxes bring nonlinearity to cryptosystems and strengthen their cryptographic security. An S-box satisfies the strict avalanche criterion (SAC), if and only if for any single input bit of the S-box, the inversion of it changes each output bit with probability one half. This paper presents some interesting properties of S-boxes and proposes an efficient and systematic means of generating arbitrary input size bijective S-boxes satisfying SAC.

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 deals with the firing activities of a data-flow program net, which is extended from conventional data-flow graph by allowing edge thresholds α and β to be any positive integer number, while a conventional data-flow graph has αβ1. For a switchless program net, a necessary and sufficient condition of structural termination is shown and an algorithm for verifying structural termination is provided. For a program net with switches that change their states only once during whole program execution, a sufficient condition for the uniqueness of maximum firing numbers is given.

An expression for the confidence intervals of the autoregressive (AR) power spectral estimate is derived by using Efron's approximate bootstrap method. The method has the second order correction for the nonlinearity of the estimate. We also propose an alternative confidence interval for extremely sharp peaks of the power spectrum at which the bootstrap approximation may break down. Simulations are carried out for two examples often used for the test of the confidence intervals.

Server-aided secret computation (SASC) protocols were proposed as methods to allow a not-so-powerful computer (a client) to compute a function efficiently with the aid of a powerful computer (a server) without revealing the client's secret to the server. A smart card system is considered to be the most promising application for SASC protocols. Matsumoto et al. proposed a class of protocols, called S2, which is suitable for RSA secret computation. It includes many variations, such as binary S2, non-binary S2, and KS schemes. Although it is expected that the non-binary S2 will be the most efficient scheme, performances for these protocols have not been fully analyzed, except for the KS scheme. This paper discusses how to determine appropriate parameters for non-binary S2. Performance was generally analyzed by using normalized variables. It is shown that a client can compute a signature 50 times faster, with a 105 times more powerful server's aid, than in the case without a server, provided that communication cost can be ignored. The SASC protocol performance is also discussed under the practical condition that a server is an 8-bit CPU and that the communication rate is 9.6 kbps. The client can sign a message in about 10 seconds, with the aid of a 32-bit CPU. This analysis coincides well with the experimental result. It is estimated that a client with a 16-bit CPU will accomplish a less that 2 second processing time with a 4.6 kbps server.

A reversible finite automaton (RFA) is a backward deterministic automaton, i.e., it can uniquely retrace its move sequence if the inverse sequence of its outputs is given. In this paper, we show a simple method to construct an RFA from Fredkin gates, which are reversible and bit-conserving logic gates, and unit wires (unit delays). The resulting circuit obtained by this method is garbage-less" in the sense that it has no inputs to which constants must be supplied nor outputs from which garbage signals are put out. We also show that a one-dimensional reversible partitioned cellular automaton, which are known to be computation universal, can be constructed from Fredkin gates and unit wires as a closed (thus garbage-less) infinite circuit.