This paper describes a brief history of the development of crytologic research in Japan since 1984, when the first symposium on cryptography and information security was held. Six symposia and three workshops since 1984 played the leading roles in the history.

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.

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.

In this paper we propose a new secret key cryptosystem using a chaotic map. This system is based on the characteristics of chaos that the small variations of parameters make the results of recursive calculations on chaotic maps quite different. By appropriately setting the calculation times and selecting a parameter as a secret key, we can make a useful cryptosystem whose distribution of ciphertexts is uniform distribution U(0, 1) and the results of the computation for two slight different keys are relatively independent.

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.

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.

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.

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).

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 10⁵ 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 new compact modular-multiplication algorithm is proposed. The throughput of the algorithm is about twice as fast as conventional ones by spending the same amount of hardware. Thus, this algorithm allows a 512-bit modular multiplier to be made with about 50 Kgates by using a conventional LSI technology. The throughput of 512-bit modular exponentiation using it will be about 80 kbits/s at a 30 MHz clock.

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.

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.

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.

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.

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.

The purpose of this paper is to establish an access control system by using only fingerprint identification. In order to minimize the identification time, we propose a new fingerprint classification suitable for a personal computer, and the real machine by using the classification is introduced. Our classification is implemented by only cores which are one of the features on fingerprint pattern. Therefore, it classifies all fingerprints into one of 11 classes rapidly on a personal computer. In the machine, an input fingerprint is classified and compared with ones registered in the same class. If both the input fingerprint and the registered one match, the person is allowed entry to the restricted area. Simulation results show that 443 fingerprint patterns (45 persons) are classified completely and rapidly. And the machine is effective and useful as identifier for home and room security.

This paper presents a new digital signature scheme for computer-aided facsimile systems which directly embeds a signature onto document. We use multiple reference lines which have been scanned just before and modify each distance between changing pels both on the reference line specified by key and on the coding line with a single bit of the signature data. The sender embeds his signature secretly and transfers it, and the recipient makes a check of any forgery on the signature and the document. This scheme is compatible with the CCITT G3 and G4 facsimile standards. The total amount of data transmitted and the image quality are about the same to that of the original document, and thus an attacker may notice that no signature is embedded on the document.

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.

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.

The high-gain Four-Stacked Circular-Loop Array Antenna (FSLA) working as a single equilibrium feed antenna is presented and used as receiving antenna of the outdoor antenna gain measuring system in UHF TV band. The suppression effect of reflected waves and the error between available and directional gains are experimentally discussed.

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.

This letter describes quantification measurements of the discontact phenomena appearing in the sliding-contacts. The inherent properties of the discontact phenomena are shown by statistically measuring the occurrence time-rates of the discontacts and the discharges.

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.

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.

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.

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.

The performance of QPSK systems using decision-feedback (DF) filters in the presence of the pulsed continuous wave (CW) interference is analyzed. We derive the general analytic expressions for the optimum tap weights and the improvement factor of the signal-to-noise ratio (SNR) for both one-sided and two-sided transversal filters with and without DF taps. We find that in the presence of the pulsed CW interference, the leading taps of the two-sided filter plays an important role to suppress the pulsed CW interference, and therefore, the output SNR of the two-sided filter with DF is most improved. The transient behavior of the DF filters are also considered and it is found that the settling time of the two-sided filter with DF is almost the same as that one-sided filter with DF.

This paper is concerned with a theoretical study of electromagnetic wave scattering by infinite plane gratings located on both sides of a dielectric slab in case of oblique incidence and arbitrary polarization. In the analysis, we use the spectral domain method combined with the sampling theorem. Infinite sets of simultaneous equations are derived by the method of moments where spherical Bessel functions are used as weighting functions. Numerical results exhibit a good convergence. The use of a resonance phenomenon of a double grating makes it possible to greatly improve the cross polarization discrimination (X. P. D.) compared with the case of a single grating.

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 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.

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.