The security of an iterated block cipher heavily depends on its structure as well as each round function. Matsui showed that MISTY type structure is faster and more robust than Feistel structure in terms of its resistance against linear and differential cryptanalysis. On the other hand, Luby and Rackoff proved that the four round Feistel structure is super-pseudorandom if each round function f_i is a random function. This paper proves that the five round MISTY type structure is super-pseudorandom. We also characterize its round security.

We present the new 128-bit block cipher called Camellia. Camellia supports 128-bit block size and 128-, 192-, and 256-bit key lengths, i.e. the same interface specifications as the Advanced Encryption Standard (AES). Camellia was carefully designed to withstand all known cryptanalytic attacks and even to have a sufficiently large security leeway. It was also designed to suit both software and hardware implementations and to cover all possible encryption applications that range from low-cost smart cards to high-speed network systems. Compared to the AES finalists, Camellia offers at least comparable encryption speed in software and hardware. An optimized implementation of Camellia in assembly language can encrypt on a Pentium III (1.13 GHz) at the rate of 471 Mbits per second. In addition, a distinguishing feature is its small hardware design. A hardware implementation, which includes encryption, decryption, and the key schedule for 128-bit keys, occupies only 9.66 K gates using a 0.35 µm CMOS ASIC library. This is in the smallest class among all existing 128-bit block ciphers. It perfectly meets the current market requirements in wireless cards, for instance, where low power consumption is essential.

This paper studies security of Feistel ciphers with SPN round function against differential cryptanalysis, linear cryptanalysis, and truncated differential cryptanalysis from the "designer's standpoint." In estimating the security, we use the upper bounds of differential characteristic probability, linear characteristic probability and truncated differential probability, respectively. They are useful to design practically secure ciphers against these cryptanalyses. Firstly, we consider the minimum numbers of differential and linear active s-boxes. They provide the upper bounds of differential and linear characteristic probability, which show the security of ciphers constructed by s-boxes against differential and linear cryptanalysis. We clarify the (lower bounds of) minimum numbers of differential and linear active s-boxes in some consecutive rounds of the Feistel ciphers by using differential and linear branch numbers, P_d, P_l, respectively. Secondly, we discuss the following items on truncated differential probability from the designer's standpoint, and show how the following items affect the upper bound of truncated differential probability; (a) truncated differential probability of effective active-s-box, (b) XOR cancellation probability, and (c) effect of auxiliary functions. Finally, we revise Matsui's algorithm using the above discussion in order to evaluate the upper bound of truncated differential probability, since we consider the upper bound of truncated differential probability as well as that of differential and linear probability.

In this paper, we discuss the impossible differential cryptanalysis for the block cipher Zodiac. The main design principles of Zodiac include simplicity and efficiency. However, the diffusion layer in its round function is too simple to offer enough security. The impossible differential cryptanalysis exploits such weakness in Zodiac. Our attack using a 14-round impossible characteristic derives the 128-bit master key of the full 16-round Zodiac faster than the exhaustive search. The efficiency of the attack compared with exhaustive search increases as the key size increases.

Various attacks against RC5 have been analyzed intensively. A known plaintext attack has not been reported that it works on so higher round as a chosen plaintext attack, but it can work more efficiently and practically. In this paper, we investigate a known plaintext attack against RC5 by improving a correlation attack. As for a known plaintext attack against RC5, the best known result is a linear cryptanalysis. They have reported that RC5-32 with 10 rounds can be broken by 2⁶⁴ plaintexts under the heuristic assumption: RC5-32 with r rounds can be broken with a success probability of 90% by using 2^6r+4 plaintexts. However, their assumption seems to be highly optimistic. Our known plaintext correlation attack can break RC5-32 with 10 rounds (20 half-rounds) in a more strict sense with a success probability of 90% by using 2^63.67 plaintexts. Furthermore, our attack can break RC5-32 with 21 half-rounds in a success probability of 30% by using 2^63.07 plaintexts.

In many cryptographic protocols, a common-key encryption is used to provide a secure data-transmission channel. More precisely, the general idea of protocols is to have an encryption provide data authenticity as well as data confidentiality. In fact, there are known to be quite a few ways to provide both forms of security, however none of them are optimized enough to be efficient. We present a new encryption mode that uses a random number generator (RNG). Assuming the security of the RNG, we can prove not only perfect secrecy, but also message authentication. The proven probability of a successful forgery is (n-1)/(2^b-1), where b is the number of bits in a block and n is the number of ciphertext blocks. The proposed scheme achieves very high practicality due to the potential advantages in efficiency. When we use a computationally secure RNG, such as instance a pseudorandom number generator PRNG, we have advantages in efficiency; in addition to the PRNG parallel computation, the scheme requires only a single-path process on the data stream so that even a limited hardware resource can operate an encryption of a very long data stream. We demonstrate the practicality of our scheme, by showing a realistic parameter set and the evaluations of its performance.

It is shown that the effective secret-key size of TOYOCRYPT-HS1 stream cipher is only 96 bits, although the secret key consists of 128 bits. This characteristic opens a door for developing an algorithm for cryptanalysis based on the time-memory-data trade-off with the overall complexity significantly smaller than the exhaustive search over the effective key space.

Almost all of the current public-key cryptosystems (PKCs) are based on number theory, such as the integer factoring problem and the discrete logarithm problem (which will be solved in polynomial-time after the emergence of quantum computers). While the McEliece PKC is based on another theory, i.e. coding theory, it is vulnerable against several practical attacks. In this paper, we summarize currently known attacks to the McEliece PKC, and then point out that, without any decryption oracles or any partial knowledge on the plaintext of the challenge ciphertext, no polynomial-time algorithm is known for inverting the McEliece PKC whose parameters are carefully chosen. Under the assumption that this inverting problem is hard, we propose a slightly modified version of McEliece PKC that can be proven, in the random oracle model, to be semantically secure against adaptive chosen-ciphertext attacks. Our conversion can achieve the reduction of the redundant data down to 1/3-1/4 compared with the generic conversions for practical parameters.

We present a scalar multiplication algorithm with recovery of the y-coordinate on a Montgomery-form elliptic curve over any non-binary field. The previous algorithms for scalar multiplication on a Montgomery form do not consider how to recover the y-coordinate. So although they can be applicable to certain restricted schemes (e.g. ECDH and ECDSA-S), some schemes (e.g. ECDSA-V and MQV) require scalar multiplication with recovery of the y-coordinate. We compare our proposed scalar multiplication algorithm with the traditional scalar multiplication algorithms (including Window-methods on the Weierstrass form), and discuss the Montgomery form versus the Weierstrass form in the performance of implementation with several techniques of elliptic curve cryptosystems (including ECES, ECDSA, and ECMQV). Our results clarify the advantage of the cryptographic usage of Montgomery-form elliptic curve in constrained environments such as mobile devices and smart cards.

Anonymous communication essentially involves two difficulties; 1) How does the sender send a message anonymously? 2) How does the receiver send a reply to the anonymous sender? In this paper, we propose an anonymous communication method named Rivulet that overcomes both of the difficulties by using group communication. Moreover, anonymous communication holds two dilemmas; 1) Strong anonymity or good performance? 2) Protect the privacy or promote the crime? Rivulet provides a solution for the former dilemma. The latter one is hard and important problem for all privacy protection schemes, therefore, we have to keep discussing this dilemma.

In this paper, we propose a new digital signature scheme based on a third order linear feedback shift register for signing documents. This signature scheme is different from most of the signature schemes that are based on discrete logarithm problem, elliptic curves discrete logarithm problem, RSA or quadratic residues. An efficient algorithm for computing kth term of a sequence is also presented. The advantage of this scheme is that the computation is efficient than Schnorr scheme. We also show that the security of the proposed signature scheme is equivalent to that of Schnorr signature scheme.

In this paper we discuss how one can delegate his power to authenticate or sign documents to others who, again, can delegate the power to someone else. A practical cryptographic solution would be to issue a certificate that consists of one's signature. The final verifier checks verifies the chain of these certificates. This paper provides an efficient and provably secure scheme that is suitable for such a delegation chain. We prove the security of our scheme against an adaptive chosen message attack in the random oracle model. Though our primary application would be agent systems where some agents work on behalf of a user, some other applications and variants will be discussed as well. One of the variants enjoys a threshold feature whereby one can delegate his power to a group so that they have less chance to abuse their power. Another application is an identity-based signature scheme that provides faster verification capability and less communication complexity compared to those provided by existing certificate-based public key infrastructure.

This paper focuses on the watermarking system using a controlled quantization process. We first present a model of the watermark embedding and extracting processes and carry out their analyses. Then we examine the robustness of the watermarking system against common image processing and clarify the reason why detection errors occur in the watermark extracting process. Based on the result, we improve the watermark extracting process and design robust watermarking systems. The improvement is accomplished using a deconvolution filter and neural network techniques. Numerical experiments using the DCT-based watermarking system show good performance as expected by us.

Time stamping is a technique used to prove the existence of certain digital data prior to a specific point in time. With the recent expansion of electronic commerce, it has been widely recognized as an important technique for ensuring the integrity of digital data for a long time period. Recently, various time stamping schemes have been proposed. However, a framework for evaluating their security and cost has not yet been established. Therefore, it has been difficult for users and system designers to select appropriate time stamping schemes. This paper presents a new framework for evaluating the security and cost of time stamping schemes. Our framework classifies time stamping schemes into 108 categories and clarifies their characteristics with regard to security and cost. By applying our framework to a certain scheme, we can easily evaluate its security and cost without discussing details of its specification. In this paper, we explain the basic idea of our framework and show how to use it by applying it to four existing schemes: Digital Notary/SecureSeal, PKITS, TIMESEC and Cuculus.

We have introduced the first electronic cash scheme with unconditional security. That is, even malicious users with unlimited computational ability cannot forge a coin and cannot change user's identity secretly embedded in each coin. While, the spender's anonymity is preserved by our new blind signature scheme based on unconditionally secure signature proposed in [7]. But the anonymity is preserved only computationally under the assumption that Decisional Diffie-Hellman Problem is intractable.

Quantum cryptography has two advantages in comparison with conventional cryptography: one is that its security is guaranteed by a fundamental physical law, and the other is that it can detect eavesdropping. In this paper, we focus on an experimental realization of quantum cryptography as a total security system. To realize this, we adopt an interferometric optical system using Faraday mirror and improve its optical system. We also utilize semiconductor laser at a short wavelength (830 nm). As a result, we have successfully implemented quantum cryptosystem including error correction and privacy amplification. We confirmed that key distribution was performed at a rate of 1.1 kbps with a 1.7% QBER (quantum bit error rate) over a distance of 200 m (optical fiber). We also show our experimental results over a distance of 1 km (optical fiber) at a rate of 0.76 kbps.

In this paper, we treat visual secret sharing scheme (VSSS) for color images. We first evaluate the brightness of the decrypted color image under certain conditions on the mixture of colors. We obtain a general formula for the construction of VSSS using mixture of colors. We second propose an iterative algorithm for constructing VSSS in a practical situation. If we use the iterative construction, we have only to solve partial differential equations with small n even if n is actually large, where n denotes the number of participants. This iterative construction has never discussed in the both cases under the original images are black-white images and color images. Finally, we propose the way to embed a color image on each share for the case that the original image is color.

This paper addresses the problem of designing an unconditionally secure conference system that fulfills the requirements of both traceability and dynamic sender. In a so-called conference system, a common key is shared among all authorized users, and messages are encrypted using the shared key. It is known that a straightforward implementation of such a system may present a number of security weaknesses. Our particular concern lies in the possibility that unauthorized users may be able to acquire the shared key by illegal means, say from one or more authorized but dishonest users (called traitors). An unauthorized user who has successfully obtained the shared key can now decrypt scrambled messages without leaving any evidence on who the traitors were. To solve this problem, in this paper we propose a conference system that admits dynamic sender traceability. The new solution can detect traitors, even if the sender of a message is dynamically determined after a shared key is distributed to authorized users. We also prove that this scheme is unconditionally secure.

Since the impact of the recent rapid penetration of Information Technologies into the society is so tremendous, it is said that IT revolution is coming. Recognizing the above new waves, the Japanese Government is now promoting e-Government programs, and most enterprises are going to depend on the Internet to do their various activities. However, computer criminals, and other threats to security are increasing and becoming serious. Therefore, 'security' is the key for the Internet to be infrastructure of the future society in a true sense. There are many products for security controls, which are not necessarily compatible or interoperable. Interoperability is the basic requirement for infrastructures. In April, 2000, JNSA was organized by about a hundred IT companies. On the other hand, in October, 2000, LINCS was set up in Kogakuin University. The two organizations set up a Consortium to make experimental studies on IPSec interoperability. This is the first report of the activities and intermediate (the first) results obtained.

We describe a scheme of secret communication over the Internet utilizing the potentiality of the TCP/IP protocol suite in a non-standard way. Except for the sender and the receiver of the secret communication it does not need any entities installed with special software. Moreover it does not require them to share any key beforehand. Such features of the scheme stem from the use of IP datagrams with spoofed source addresses and their related error messages for the Internet Control Message Protocol (ICMP) induced by artificial faults. Countermeasures against IP spoofing are deployed in various places since it is often used together with attacks such as distributed denial of service (DDoS) and SPAM mailing. Thus we examine the environment where the scheme works as an intention and also clarify the conditions to obsolete the scheme. Furthermore we estimate the amount of secretly communicated data by the scheme and storage requirements for the receivers and those for the observers who monitor the traffic to detect the very existence of such a secret communication. We also discuss various issues including the sender anonymity achieved by the scheme.

The function of a message authentication code (MAC) is to verify the validity of a whole message. The disadvantage of usual MACs is that a receiver can not check its validity until the receipt of a message is finished. Hence, usual MACs are not suitable for verifying a large amount of data such as video and audio (called stream). In this letter, we propose a MAC such that the validity of a stream can be consecutively verified without waiting for the end of the reception. In addition, we show its implementations: one is based on practical hash functions, and the other is based on universal hash functions.

An efficient construction of a permutation network has been proposed by Waksman. However, his construction is only for permutation networks with 2^k inputs. This paper provides a construction of permutation networks with arbitrary number of inputs that is an extension of Waksman's construction. By applying our construction to Abe's Mix-net, we can improve the efficiency of the Mix-net.

This paper considers FIR filter design using linear predictive coding technique, for which the coefficients belong to a small set of integers, so that the coefficients have small wordlengths. Previously, integer programming was used to find the coefficients of such filters. However, the design method using integer programming suffers from high computational cost as the filter length increases. The computation can quickly become prohibition. In this paper, we propose two designs of predictive encoded FIR filters based on a modified Karmarkar's linear programming algorithm, which is known to be more suitable for solving large problems. First, we formulate the problem as a weighted minimax error problem and arrange it in a form that the modified Karmarkar algorithm can be applied. The design algorithm has the same (low) complexity as that of the weighted least-square method, but it can solve problems with some constraints, whereas the weighted least-square method cannot. However, the algorithm has a difficulty due to an ill condition caused by matrix inversion when the predictive filter order is high. To avoid this difficulty, we formulate the design as a weighted least absolute error problem. By using this second proposed algorithm, a filter with shorter coefficient wordlength can be found using a higher-order predictor filter at the expense of more computational cost. To further reduce the coefficient wordlength, the filter impulse response is separated into two sections having different ranges of coefficient values. Each section uses a different scaling factor to scale the coefficient values. With small coefficient wordlength, the filter can be realized without hardware multipliers using a low-radix signed-digit number representation. Each coefficient is distributed in space as 2-3 ternary {0,1} or quinary {0,1, 2} coefficients. Ternary coefficients require only add/subtract operation, while quinary coefficients require one-bit shift and add/subtract operations. The shift can be hardwired without any additional hardware.

In this paper, a new image synthesis model based on a set of wavelet bases is proposed. In the proposed model, images are approximated by the sum of synthesis functions that are translated to image edge positions. By applying the proposed model to sketch-based image coding, no iterative image recovery procedure is required for image decoding. In the design of the synthesis functions, we define the synthesis functions as a linear combination of wavelet bases. The coefficients for wavelet bases are obtained from an iterative procedure. The vector quantization is applied to the vectors of the coefficients to limit the number of the synthesis functions. We apply the proposed synthesis model to the sketch-based image coding. Image coding experiments by eight synthesis functions and a comparison with the orthogonal transform methods are also given.

Finding DC operating-points of nonlinear circuits is an important and difficult task. The Newton-Raphson method employed in the SPICE-like simulators often fails to converge to a solution. To overcome this convergence problem, homotopy methods have been studied from various viewpoints. The fixed-point homotopy method is one of the excellent methods. However, from the viewpoint of implementation, it is important to study it further so that the method can be easily and widely used by many circuit designers. This paper presents a practical method to implement the fixed-point homotopy method. A special circuit called the solution-tracing circuit for the fixed-point homotopy method is proposed. By using this circuit, the solution curves of homotopy equations can be traced by performing the SPICE transient analysis. Therefore, no modification to the existing programs is necessary. Moreover, it is proved that the proposed method is globally convergent. Numerical examples show that the proposed technique is effective and can be easily implemented. By the proposed technique, many SPICE users can easily implement the fixed-point homotopy method.

We present an efficient heuristic algorithm to reduce glitch power dissipation in CMOS digital circuits. In this paper, gate sizing is classified into three types and the buffer insertion is classified into two types. The proposed algorithm combines three types of gate sizing and two types of buffer insertion into a single optimization process to maximize the glitch reduction. The efficiency of our algorithm has been verified on LGSynth91 benchmark circuits with a 0.5 µm standard cell library. Experimental results show an average of 69.98% glitch reduction and 28.69% power reduction that are much better than those of gate sizing and buffer insertion performed independently.

A novel scheduling method for asynchronous multirate/multi-task processing by programmable digital signal processors (DSPs) has been developed. This mixed scheduling method combines static and dynamic scheduling, and avoids runtime overheads due to interrupts in context switching to realizes asynchronous multirate systems. The processing delay introduced when using static scheduling with static buffering is avoided by introducing deadline scheduling in the static schedule design. In the developed software design system, a block-diagram description language is extended to describe asynchronous multi-task processing. The scheduling method enables asynchronous multirate processing, such as arbitrary-sampling-ratio rate conversion, asynchronous interface, and multimedia applications, to be efficiently realized by programmable DSPs.

In this paper, four coupled chaotic circuits generating four-phase quasi-synchronization of chaos are proposed. By tuning the coupling parameter, chaotic wandering over the phase states characterized by the four-phase synchronization occurs. In order to analyze chaotic wandering, dependent variables corresponding to phases of solutions in subcircuits are introduced. Combining the variables with hysteresis decision of the phase states enables statistical analysis of chaotic wandering.

In this paper, a design method of neural-net based PID controllers is proposed for multivariable nonlinear systems with mutual interactions. The proposed method adopt both a static pre-compensator and some multi-layered neural networks. The former is used for roughly decoupling the controlled object, and the latter is used in order to improve decoupling and to linearize the approximately decoupled controlled object. Also the design scheme based on the relationship between PID law and the generalized minimum variance control (GMVC) law is adopted. The effectivenes of the proposed control scheme is evaluated on a simulation example.

This letter proposes a new approach for feature extraction using steerable filters. This approach is based on the concept of orientation-energy histogram which yields the local direction of dominant orientation. The testing is carried out using a training set of 1000 and a set of 300 unknown 40 40 hand-written digits. As a result of the simulations, 92% correct recognition is provided.

Several methods have been developed for solving blind deconvolution problem. Recursive inverse filtering method is proposed recently and shown to have good convergence properties. This method requires accurate estimate of the region of support. In this paper, we propose to modify the original method by incorporating split, merge and grouping algorithm to find the region of support automatically.

We describe a construction of a class of Optical Orthogonal Codes with maximum correlation 1. The construction can be used for constant weight code vectors. The cardinality of the constructed code is larger than known lower bounds.

Besides single byte errors which are caused by single chip failures, semiconductor memories used in some applications, such as satellite memory systems, are highly vulnerable to random double bit errors. It is therefore necessary to design Double bit Error Correcting--Single b-bit byte Error Correcting (DEC-S_bEC) codes which correct both random double bit errors and single b-bit byte errors. This correspondence proposes a class of generic DEC-S_bEC codes that are applicable to computer memory systems using recent high density DRAM chips with wide I/O data, such as, 8, 16 or 32 bits per chip. The proposed DEC-S₈EC codes are suitable for memory systems using DRAM chips with 8-bit I/O data, and require 24 check bits for practical information lengths such as 64 and 128 bits.