In Asiacrypt '96, Bleichenbacher et al. showed the upper limit of the efficiency of one-time digital signature scheme using a directed graph of tree structure as its base. They also claimed that there exists more effective signature scheme on general directed graphs, and showed an example of a method to construct more effective signature schemes as a witness. Unfortunately, their example does not achieve the efficiency as they claimed. This paper shows the upper limit of the efficiency of the signature scheme on general directed graphs by showing no signature scheme is more effective than the optimal signature scheme on trees (or forests). Further, we introduce another signature scheme named pseudo k-time signature scheme. This signature scheme allows signers to sign k-time which is no less efficient than the one time signature scheme.

The addition chain (A-chain) and addition-subtraction chain (AS-chain) are efficient tools to calculate power Me (or multiplication eM), where integere is fixed andM is variable. Since the optimization problem to find the shortest A (or AS)-chain is NP-hard, many algorithms to get a sub-optimal A (or AS)-chain in polynomial time are proposed. In this paper, a window method for the AS-chain and an extended window method for the A-chain and AS-chain are proposed and their performances are theoretically evaluated by applying the theory of the optimal variable-to-fixed length code, i. e. , Tunstall code, in data compression. It is shown by theory and simulation that the proposed algorithms are more efficient than other algorithms in practical cases in addition to the asymptotic case.

In the linear cryptanalysis (LC), to decrease the number of plain/cipher text pairs required for successful attack against DES, it is necessary to improve the effectiveness of the linear approximate expression and to decrease the number of key bits in the expression to be exhaustively searched for. In the previous work, we proposed a linear sieve method to improve the effectiveness of the linear approximate expression. On the other hand, the number of key bits increased. To suppress the number of key bits, we propose Fixed Sieve Linear Cryptanalysis (FS-LC) with fixed sieve key of the linear sieve method. With FS-LC against 8-round DES, we showed the number of plain/cipher text pairs required for sucessful attack is less than that of LC. Furthmore, we extended FS-LC with Kaliski's techniques using the multiple linear approximate expressions to intoroduce Fixed Sieve multiple Linear Cryptanalysis (FS-mLC). With FS-mLC against 8-round DES, computer simulation revealed that it is possible to solve its encryption-key with 220 plain/cipher text pairs. The number of pairs is about a half of the Matsui's 1-round linear cryptanalysis cases.

This paper applies linear cryptanalysis to FEAL and describes the experimental results of attacking FEAL-8 by linear cryptanalysis. The following points are important in linear cryptanalysis to reduce the processing amount and memory size in the attack: 1) to find linear expressions with as high a deviation as possible, and 2) to reduce the number of effective key bits and effective text bits. We have succeeded in attacking FEAL-8 in about 1 hour on a low-end workstation (SPARCstation 10 Model 30). We have confirmed that the entire set of subkeys of FEAL-8 can be derived from 225 known plaintexts with a success rate of over 70%, and from 226 known plaintexts with a success rate of almost 100%.

This paper focuses on competitive learning algorithms for WTA (winner-take-all) networks which perform rotation invariant pattern classification. Although WTA networks may theoretically be possible to achieve rotation invariant pattern classification with infinite memory capacities, actual networks cannot memorize all input data. To effectively memorize input patterns or the vectors to be classified, we present two algorithms for learning vectors in classes (LVC1 and LVC2), where the cells in the network memorize not only weight vectors but also their firing numbers as statistical values of the vectors. The LVC1 algorithm uses simple and ordinary competitive learning functions, but it incorporates the firing number into a coefficient of the weight change equation. In addition to all the functions of the LVC1, the LVC2 algorithm has a function to utilize under-utilized weight vectors. From theoretical analysis, the LVC2 algorithm works to minimize the energy of all weight vectors to form an effective memory. From computer simulation with two-dimensional rotated patterns, the LVC2 is shown to be better than the LVC1 in learning and generalization abilities, and both are better than the conventional Kohonen self-organizing feature map (SOFM) and the learning vector quantization (LVQ1). Furthermore, the incorporation of the firing number into the weight change equation is shown to be efficient for both the LVC1 and the LVC2 to achieve higher learning and generalization abilities. The theoretical analysis given here is not only for rotation invariant pattern classification, but it is also applicable to other WTA networks for learning vector quantization.

In the circumstances we want to deal with, transmission channel is limited and global motion can happen by camera movement, and also there exists a region-of-interest (ROI) which is more important than background. So very low bit rate coding algorithm is required and processing of global motion must be considered. Also ROI must be reconstructed with required quality after decoding because of its importance. But the existing methods such as H. 261, H. 263 are not suitable for such situations because they do not compensate global motion, which needs large amount of transmission bits in motion information and degrades image quality. And also they can not reconstruct ROI's with high quality because they do not consider the fact that ROI's are more important than background. So a new coding scheme is proposed that describes a method for encoding image sequences distinguishing bits between ROI and background. Simulations show that the suggested algorithm performs well especially in the circumstances where background changes and the area of ROI is small enough compared with that of background.

In this paper, a new nonlinear integrator with positive phase shifts is proposed. Results of the digital simulation show that the nonlinear integrator has a better performance than the conventional one in a control system.

Parallelism on heterogeneous machines brings cost effectiveness, but also raises a new set of complex and challenging problems. This paper addresses the problem of estimating the minimum time taken to execute a program on a fine-grained parallel machine composed of different types of processors. In an earlier publication, we took the first step in this direction by presenting a graph-construction method which partitions a given program into several homogeneous parts and incorporates timing constraints due to heterogeneous parallelism into each part. In this paper, to make the method easier to be applied in a scheduling framework and to demonstrate its practical utility, we present an efficient implementation method and compare the results of its use to the optimal schedule lengths obtained by enumerating all possible solutions. Experimental results for several different machine models indicate that this method can be effectively used to estimate a program's minimum execution time.

An oversampling theorem for regular sampling in wavelet subspaces is established. The sufficient-necessary condition for which it holds is found. Meanwhile the truncation error and aliasing error are estimated respectively when the theorem is applied to reconstruct discretely sampled signals. Finally an algorithm is formulated and an example is calculated to show the algorithm.

A simple method of compensating the DC drift of LiNbO3 Mach-Zehnder intensity modulators for very high speed optical transmission systems is proposed. This method adds low frequency perturbation to the modulator driving signal, and controls the bias voltage using the detected envelope of the modulator output signal. The control circuit is successfully demonstrated to work with less than a 0. 1-dB power penalty.

Fiat-Shamir's identification and signature scheme is efficient as well as provably secure, but it has a problem in that the transmitted information size and memory size cannot simultaneously be small. This paper proposes an identification and signature scheme which overcomes this problem. Our scheme is based on the difficulty of extracting theL-th roots modn (e. g.L=2 1020) when the factors ofnare unknown. We prove that the sequential version of our scheme is a zero knowledge interactive proof system and our parallel version reveals no transferable information if the factoring is difficult. The speed of our scheme's typical implementation is at least one order of magnitude faster than that of the RSA scheme and is relatively slow in comparison with that of the Fiat-Shamir scheme.

A multiple signature scheme proposed in [1] is proved to be insecure.

In this paper, we present an analytic model to study the reliability of some important disk array organizations that have been proposed by others in the literature. These organizations are based on the combination of two options for the data layout, regular RAID-5 and block designs, and three alternatives for sparing, hot sparing, distributed sparing and parity sparing. Uncorrectable bit errors have big effects on reliability but are ignored in traditional reliability analysis of disk arrays. We consider both disk failures and uncorrectable bit errors in the model. The reliability of disk arrays is measured in terms of MTTDL (Mean Time To Data Loss). A unified formula of MTTDL has been derived for these disk array organizations. The MTTDLs of these disk array organizations are also compared using the analytic model. By numerical experiments, we show that the data losses caused by uncorrectable bit errors may dominate the data losses of disk array systems though only the data losses caused by disk failures are traditionally considered. The consideration of uncorrectable bit errors provides a more realistic look at the reliability of the disk array systems.

A new broadband space diversity (B-SD) combining method, which is a key technique in the growth of digital microwave radio system, is proposed. In this B-SD combining method, two received signals, whose bandwidths are 280 MHz, are combined. To develop this combining method, an optimum control algorithm is developed that monitors power levels of all primary carriers and controls the endless phase shifter so that the higher level signal is decreased and the lower level signal is increased. This paper describes the proposed B-SD combining method which effectively operates over a wide bandwidth. Performance evaluations based on simulations and theoretical estimations are given. It is proven that this combining method offers the same performance obtained by the conventional narrowband SD combining method and can be applied to over 50% cases of the propagation paths observed in Japan. The suitability of the proposed combining method and the calculation methods adopted is demonstrated experimentally.

The Non-stop Service-Enhanceable Software (NOSES) platform was developed as part of our overall plan to establish a communications software platform that can be customized for use by various communications systems, such as STM, ATM and IN. The developed NOSES techniques are call-recovery restart, system file update, and on-line partial file modification, so called "Plug-in"; they were achieved by using dynamic program modification. A system-file update inevitably affects calls in service, despite efforts to save in-service calls by copying the call data from the old file to the new one. We therefore developed a different approach: Plug-in modification. This paper evaluates the applicability of the plug-in mechanism of the NOSES platform. Plug-in is a dynamic partial-file modification technique that does not affect calls in service in a communication switching system. In order to apply plug-in program modification widely, the static and dynamic properties of the modified software must be considered. Therefore, an applicability judgement matrix is introduced. The evaluated applicability of plug-in based on case studies and field data was about 60% for service feature additions and modifications. Thus, plug-in is effective for file maintenance of switching systems from the viewpoint of quick provisioning of new service features and bug fixes.

This letter gives a study of additionY=X+K mod 2w which is used in some cryptosystems as RC5. Our results enables us to express the differential and linear probability of addition as a function of addendK. To detect a good differential characteristics or linear approximation of a cryptosystem in which extended key is used as addend, we need to consider how the characteristics or approximations behave depending upon the value of the addend, which are clarified by our results.

This paper presents two types of two-dimensional (2-D) adaptive beamforming algorithm which have high rate of convergence. One is a linearly constrained minimum variance (LCMV) beamforming algorithm which minimizes the average output power of a beamformer, and the other is a generalized sidelobe canceler (GSC) algorithm which generalizes the notion of a linear constraint by using the multiple linear constraints. In both algorithms, we apply a 2-D lattice filter to an adaptive filtering since the 2-D lattice filter provides excellent properties compared to a transversal filter. In order to evaluate the validity of the algorithm, we perform computer simulations. The experimental results show that the algorithm can reject interference signals while maintaining the direction of desired signal, and can improve convergent performance.

In this paper, a threshold voltage (VT) cancellation circuit for neuron-MOS (νMOS) analog circuits is described. By connecting the output terminal of this circuit with one of the input terminals of the νMOS transistor, cancellation ofVT is realized. The circuit has advantages of ground-referenced output and is insensitive to the fluctuation of bias and supply voltages. Second-order effects, such as the channel length modulation effect, the mobility reduction effect and device mismatch of the proposed circuit are analyzed in detail. Low-power and high-swing νMOS cascode current mirror is presented as an application. Performance of the proposed circuits is confirmed by HSPICE simulation with MOSIS 2. 0 µ p-well double-poly and double-metal CMOS device parameters.

The basic operation characteristics of an asymmetric turnstile which transfers each electron one by one in one direction is described. A novel single electron counter circuit consisting of the asymmetric turnstiles, a load capacitor and an inverter which counts the number of high inputs is proposed. Monte Carlo circuit simulations reveal that the gate clock time of the counter circuit should be long enough to achieve allowable minimum error rate. The counter circuit implementing asymmetric single electron turnstiles is demonstrated to be applicable to a noise reduction system, a Winner-Take-All circuit and an artificial neuron circuit.

This paper proposes a secure electronic sealed-bid auction protocol (SEAP) that provides an auction service on the Internet by combining three providers: an auction service provider, a key service provider, and a time service provider. The SEAP uses public key cryptography and the concept of a time-key certificate. The most important property of this protocol is that time-dependent security requirements can be strictly satisfied. The SEAP satisfies the following nine security requirements: (a) no one can deny having made a bid; (b) the protocol should be secure against malicious acts; (c) no bidder can act for another bidder; (d) no one can know who else is bidding until the time comes for the bids to be opened; (e) no one can discover the contents of any of the bids until the time comes for the bids to be opened; (f) the successful bid must have been submitted before the bidding deadline; (g) all bidders can verify that the auction policy has been correctly implemented; (h) the successful bidder can be identified without being required to make himself or herself known; and (i) the bidding contents cannot be altered. The protocol consists of three subprotocols: the Registration Subprotocol, the Bidding Subprotocol, and the Auction Subprotocol. The protocol parameters and algorithm are described in detail.