This paper describes truncated and impossible differentials of Feistel block ciphers with round functions of 2-layer SPN (Substitution and Permutation Network) transformation modules such as the 128-bit block cipher Camellia, which was proposed by NTT and Mitsubishi Electric Corporation. Our work improves on the best known truncated and impossible differentials, and has found a nontrivial 9-round truncated differential that may lead to a possible attack against a reduced-round version of Camellia without input/output whitening, FL or FL^-1 (Camellia-NFL), in the chosen plain text scenario. Previously, only 6-round differentials were known that may suggest a possible attack of Camellia-NFL reduced to 8-rounds. We also show a nontrivial 7-round impossible differential, whereas only a 5-round impossible differential was previously known. We also consider the truncated differential of a reduced-round version of Camellia (Camellia-DS) whose round functions are composed of D-S (Diffusion and Substitution) transformation modules and without input/output whitening, FL or FL^-1 (Camellia-DS-NFL), and show a nontrivial 9-round truncated differential, which may lead to a possible attack in the chosen plain text scenario. This truncated differential is effective for general Feistel structures with round functions composed of S-D (Substitution and Diffusion) or D-S transformation.

This paper cryptanalyzes 128-bit block cipher Xenon, which was designed by Chang-Hyi Lee and has been recently proposed by Korea to ISO 18033-3, an ongoing activity in ISO/IEC JTC1/SC27/WG2 for standardizing block cipher algorithms. We study security of Xenon against linear cryptanalysis and show highly biased linear approximate paths that hold with probability 1/2 2^-11 in the full 16-round Xenon. As a result, we can easily derive four-bit subkey information of Xenon using 2²³ known plaintexts with approximate success rate 84%. We also demonstrate a distinguishing attack of Xenon in a chosen plaintext scenario, which successfully reduces the number of required plaintext/ciphertext pairs of the attack. All these results were confirmed by computer experiments.

We investigate the cryptanalysis of reduced-round RC6 without whitening. Up to now, key recovery algorithms against the reduced-round RC6 itself, the reduced-round RC6 without whitening, and even the simplified variants have been infeasible on a modern computer. In this paper, we propose an efficient and feasible key recovery algorithm against reduced-round RC6 without whitening. Our algorithm is very useful for analyzing the security of the round-function of RC6. Our attack applies to a rather large number of rounds. RC6 without whitening with r rounds can be broken with a success probability of 90% by using 2^{8.1r - 13.8} plaintexts. Therefore, our attack can break RC6 without whitening with 17 rounds by using 2^123.9 plaintexts with a probability of 90%.

The encryption algorithm Camellia is a 128 bit block cipher proposed by NTT and Mitsubishi, Japan. Since the algebraic degree of the outputs after 3 rounds is greater than 128, designers estimate that it is impossible to attack Camellia by higher order differential. In this paper, we show a new higher order differential attack which controls the value of differential using proper fixed value of plaintext. As the result, we found that 6-round F-function can be attacked using 8th order differentials. The attack requires 2¹⁷ chosen plaintexts and 2²² F-function operations. Our computer simulation took about 2 seconds for the attack. If we take 2-R elimination algorithm, 7-round F-function will be attacked using 8th order differentials. This attack requires 2¹⁹ chosen plaintexts and 2⁶⁴ F-function operations, which is less than exhaustive search for 128 bit key.

We extend the theorem by Hong et al. which gives the upper bounds of the maximum average differential and linear hull probabilities (MADP and MALHP) for SPN block cipher with optimal or quasi-optimal diffusion layers, to the case of nested SPN (NSPN) cipher. Applying the extended theorem to two NSPN ciphers, Hierocrypt-3 of 128-bit block and Hierocrypt-L1 of 64-bit block, we estimated that MADP and MALHP for 2-round Hierocrypt-3 are bounded by 2^-96, and that those for 2-round Hierocrypt-L1 are bounded by 2^-48. The extended theorem is also applied to AES, and found that MADP and MALHP are bounded by 2^-96 for its 4-round reduced model. The last result outperforms the best previous result 2^-92 for 10-round by Keliher et al.

In cryptography, we want a Boolean function which satisfies PC(l) of order k for many (l,k). Let PC_n(l,k) be a set of Boolean functions with n input bits satisfying PC(l) of order k. From a view point of construction, it is desirable that there exists (l₀,k₀) such that PC_n(l₀, k₀) PC_n(l_i,k_i) for many i 1. In this paper, we show a negative result for this problem. We prove that PC_n(l₁,k₁) PC_n(l₂,k₂) for a large class of l₁, k₁, l₂ and k₂.

This paper shows an extensive software performance analysis of dedicated hash functions, particularly concentrating on Pentium III, which is a current dominant processor. The targeted hash functions are MD5, RIPEMD-128 -160, SHA-1 -256 -512 and Whirlpool, which fully cover currently used and future promised hashing algorithms. We try to optimize hashing speed not only by carefully arranging pipeline scheduling but also by processing two or even three message blocks in parallel using MMX registers for 32-bit oriented hash functions. Moreover we thoroughly utilize 64-bit MMX instructions for maximizing performance of 64-bit oriented hash functions, SHA-512 and Whirlpool. To our best knowledge, this paper gives the first detailed measured performance analysis of SHA-256, SHA-512 and Whirlpool.

Batch verification is a useful tool in verifying a large number of cryptographic items all at one time. It is especially effective in verifying predicates based on modular exponentiation. In some cases, however the items can be incorrect although they pass batch verification together. Such leniency can be eliminated by checking the domain of each item in advance. With this in mind, we introduce the strict batch verification and investigate if the strict batch verification can remain more effective than separate verification. In this paper, we estimate the efficiency of such strict batch verification in several types of groups, a prime subgroup of Z_p with special/random prime p and prime subgroups defined on elliptic curves over F_p, F_2^m and F_p^m, with are often used in DL-based cryptographic primitives. Our analysis concludes that the efficiency differs greatly depending on the choice of the group and parameters determined by the verifying predicate. Furthermore, we even show that there are some cases where batch verification, regardless of strictness, loses its computational advantage.

In an order-specified multisignature scheme, one can verify not only a set of signers who have signed the message but also its signing order. Though we have seen several schemes with such properties proposed, none of them is given the security proof against active adversaries. The scheme can be easily modified to be an order-specified multisignature scheme, but still has the restriction that the possible signing orders are only ones of the type of serial signing. In this paper, we propose the first order-specified multisignature scheme, which is shown to be secure against adaptive chosen-message insider attacks in the random oracle model, and which allows the signing orders to form like any series-parallel graphs. The security is shown by using ID-reduction technique, which reduces the security of multisignature schemes to those of multi-round identification schemes. Furthermore, we discuss the efficiency of the proposed scheme and the upper bound of the possible number of participating signers.

This paper proposes a new algorithm to achieve about two-times speedup of modular exponentiation which is implemented by Montgomery multiplication based on Residue Number Systems (RNS). In RNS Montgomery multiplication, its performance is determined by two base transformations dominantly. For the purpose of realizing parallel processing of these base transformations, i. e. "duplicate processing," we present two procedures of RNS Montgomery multiplication, in which RNS bases a and b are interchanged, and perform them alternately in modular exponentiation iteration. In an investigation of implementation, 1.87-times speedup has been obtained for 1024-bit modular multiplication. The proposed RNS Montgomery multiplication algorithm has an advantage in achieving the performance corresponding to that the upper limit of the number of parallel processing units is doubled.

We develop efficient precomputation methods of multi-scalar multiplication on ECC. We should recall that multi-scalar multiplication is required in some elliptic curve cryptosystems including the signature verification of ECDSA signature scheme. One of the known fast computation methods of multi-scalar multiplication is a simultaneous method. A simultaneous method consists of two stages; precomputation stage and evaluation stage. Precomputation stage computes points of precomputation, which are used at evaluation stage. Evaluation stage computes multi-scalar multiplication using precomputed points. In the evaluation stage of simultaneous methods, we can compute the multi-scalar multiplied point quickly because the number of additions is small. However, if we take a large window width, we have to compute an enormous number of points in precomputation stage. Hence, we have to compute an abundance of inversions, which have large computational amount. As a result, precomputation stage requires much time, as well known. Our proposed method reduces from O(2^2w) inversions to O(w) inversions for a window width w, using Montgomery trick. In addition, our proposed method computes uP and vQ first, then compute uP+vQ, where P,Q are elliptic points. This procedure enables us to remove unused points of precomputation. Compared with the method without Montgomery trick, our proposed method is 3.6 times faster in the case of the precomputation stage for simultaneous sliding window NAF method with window width w=3 and 160-bit scalars under the assumption that I/M=30, S/M=0.8, where I,M,S respectively denote computational amounts of inversion, multiplication and squaring on a finite field.

We introduce efficient algorithms for the τ-adic sliding window method, which is a scalar multiplication algorithm on Koblitz curves over F_2^m. The τ-adic sliding window method is divided into two parts: the precomputation part and the main computation part. Until now, there has been no efficient way to deal with the precomputation part; the required points of the elliptic curves were calculated one by one. We propose two fast algorithms for the precomputation part. One of the proposed methods decreases the cost of the precomputation part by approximately 30%. Since more points are calculated, the total cost of scalar multiplication is decreased by approximately 7.5%.

This paper presents a new sliding window algorithm that is well-suited to an elliptic curve defined over an extension field for which the Frobenius map can be computed quickly, e.g., optimal extension field. The algorithm reduces elliptic curve group operations by approximately 15% for scalar multiplications for a practically used curve in compared to Lim-Hwang's results presented at PKC2000, which was the fastest previously reported. The algorithm was implemented on computers. Scalar multiplication can be accomplished in 573 µs, 595 µs, and 254 µs on Pentium II (450 MHz), 21164A (500 MHz), and 21264 (500 MHz) computers, respectively.

This paper proposes a flexible tree-based key management framework for a terminal to connect with multiple content distribution systems (called as CDSs in this paper). In an existing tree-based key management scheme, a terminal keeps previously distributed node keys which are used for decrypting contents from a CDS. According to our proposal, the terminal can calculate its node keys of a selected CDS as the need arises, using the "public bulletin board" of the CDS. The public bulletin board is generated by a management center of the individual CDS, depending on a tree structure which it determines in its convenience. After the terminal calculates its node keys, it can get a content of the CDS using the calculated node keys.

This paper provides a M+1-st price auction scheme using homomorphic encryption and the mix and match technique; it offers secrecy of bidding price and public verifiability. Our scheme has low round communication complexity: 1 round from each bidder to auctioneer in bidding and log p rounds from auctioneer to trusted authority in opening when prices are selected from p prefixed choices.

Many services on ITS (Intelligent transport system) have been proposed, which include the ETC (electronic toll collection) system. In this paper, we first present some assumptions we can assume on ITS. Then we construct a light electronic ticket system which is suitable for payment on ITS. In our system, (1) only two moves are required to use a ticket, (2) the shop can check the validity of the ticket with only a few applying of hash functions. Further, we prove that forgery of a ticket by a user or a shop is detected with almost one probability.

This paper presents a new method to evaluate time stamping schemes from three viewpoints: integrity of a time stamp, cost of issuing and verifying a time stamp and availability of the schemes. The main advantage of the proposed evaluation method is to clarify whether or not a certain scheme is optimal under certain prioritized requirements. Therefore, the proposed method can help potential users of time stamping services select an appropriate one which meets their prioritized requirements. In this paper, we explain the basic idea of the evaluation method and show how to use it by applying it to seven existing schemes.

Access control involves a check to see if a user has an access right to a resource and then a decision is made as to whether his/her access to the resource is to be allowed or denied. Typical access control models are the Discretionary Access Control Model, the Mandatory Access Control Model, and the Role-Based Access Control Model. Today, the Role-Based Access Control Model has become popular and is recognized as an effective method. However, until now, the Role-Based Access Control Model was adequate only for bureaucracy organizations, in which some roles are standardized and organizational hierarchy is stable. Team-Based Access Control models that were designed for team-based organizations have been proposed, but they do not reflect some features of an adhocracy organization, which are organic, temporary, not standardized, changeable, and obscure in terms of hierarchical relationship, such as a Task Force Team in the company. This study shows the characteristics of an adhocracy organization that differ from the existing bureaucracy organization, and then shows why existing access control models have caused some problems. Finally, a revised Role-Based Access Control model is proposed to solve those problems and is analyzed according to main evaluation standards.

Software obfuscation is a promising approach to protect intellectual property rights and secret information of software in untrusted environments. Unfortunately previous software obfuscation techniques share a major drawback that they do not have a theoretical basis and thus it is unclear how effective they are. Therefore we propose new software obfuscation techniques in this paper. The techniques are based on the difficulty of interprocedural analysis of software programs. The essence of our obfuscation techniques is a new complexity problem to precisely determine the address a function pointer points to in the presence of arrays of function pointers. We show that the problem is NP-hard and the fact provides a theoretical basis for our obfuscation techniques. Furthermore, we have already implemented a prototype tool that obfuscates C programs according to our proposed techniques and in this paper we describe the implementation and discuss the experiments results.

Jan and Tseng, in 1999, proposed two efficient digital signature schemes with subliminal channels. However, we show that a malicious subliminal receiver can forge subliminal messages that will be accepted by other subliminal receivers in Jan and Tseng's two schemes. Moreover, we also present a modification of Jan and Tseng's schemes to repair the security flaw.

When people want to exchange digital money and digital data over the Internet like a market, privacy for the participant's behavior, security against malicious users and fairness for matching must be assured. We propose a new concept "Matching Oblivious Transfer," which can match valuable digital data with hiding the price suggested by participant and securely deliver the digital data to the matched participant. Then we propose a protocol for some general matching rules in which once a participant sends an order to the market, no interaction between each participant and the market is needed.

In this letter we propose a new visual secret sharing scheme (VSSS) applicable to color images containing many colors such as photographs. In the proposed VSSS we can perceive a concealed secret image appearing on a reproduced image, which is obtained by stacking certain shares, according to the principle called the meanvalue-color mixing (MCM). First, we mathematically formulate the MCM and define a new parameter that determines the minimum quality of the reproduced secret image. Then, we explicitly construct the VSSS based on the MCM under general access structures. The construction is proved to be realistic by experiment under the (2,2)-threshold access structure.

This paper addresses a maximum likelihood method for source separation in the case of overdetermined mixtures corrupted by additive white Gaussian noise. We consider an approximate likelihood which is based on the Laplace approximation and develop a natural gradient adaptation algorithm to find a local maximum of the corresponding approximate likelihood. We present a detailed mathematical derivation of the algorithm using the Lie group invariance. Useful behavior of the algorithm is verified by numerical experiments.

A number of results on the estimation of direction of arrival have been obtained based on the assumption that the signal sources are point sources. Recently, it has been shown that signal source localization can be accomplished more adequately with distributed source models in some real surroundings. In this paper, we consider modeling of three-dimensional distributed signal sources, in which a source location is represented by the center angles and degrees of dispersion. We address estimation of the elevation and azimuth angles of distributed sources based on the proposed distributed source modeling in the three-dimensional space using two linear arrays. Some examples are included to more explicitly show the estimation procedures under the model: numerical results obtained by a MUSIC-based method with two uniform linear arrays are discussed.

The purpose of this paper is to derive a novel fractionally spaced Bayesian decision feedback equalizer (FS-BDFE). The oversampling technique changes single input single output (SISO) linear channel to single input multiple output (SIMO) linear channel. The Bayesian decision variable in the FS-BDFE is defined as the product of Bayesian decision variables in the Bayesian decision feedback equalizers (BDFE) corresponding to each channels of the SIMO. It can be shown that the FS-BDFE has less decision error probability than the conventional BDFE. The effectiveness of the proposed equalizer is also demonstrated by the computer simulation.

A digit-recurrence algorithm for computing reciprocal square-root which appears frequently in multimedia and graphics applications is proposed. The reciprocal square-root is computed by iteration of carry-propagation-free additions, shifts, and multiplications by one digit. Different specific versions of the algorithm are possible, depending on the radix, the redundancy factor of the digit set, and etc. Details of a radix-2 version and a radix-4 version and designs of a floating-point reciprocal square-root circuit based on them are shown.

This paper discusses two types of polyphase sequence sets, which will successfully provide CDMA systems without co-channel interference. One is a type of ZCZ sets, whose periodic auto-correlation functions take zero at continuous shifts on both side of the zero-shift, and periodic cross-ones also take zero at the continuous shifts and the zero-shift. The other is a new type of sets consisting of some subsets of polyphase sequences with zero cross-correlation zone, called ZCCZ sets, whose periodic cross-correlation functions among different subsets have take zero at continuous shifts on both side of the zero-shift including the zero-shift. The former can achieve a mathematical bound, and the latter can have large size.

Many types of adaptive algorithms based on the MMSE criterion for co-channel interference suppression in DS/CDMA systems have been studied in great detail. However, these algorithms have such a problem that the training speed is greatly dropped under the strong near-far problem. In this paper, we propose and analyze an adaptive filter based on the Maximum Signal to Interference and Noise Ratio (MSINR) criterion, called adaptive MSINR filter. This filter is basically equivalent to the adaptive filter based on the MMSE criterion. However, due to the structual difference, the convergence speed is greatly improved. Specifically, the de-spreading vector in this filter is so renewed as to maximize the Signal to Interference and Noise Ratio (SINR) by minimizing the de-spread interference and noise power under the condition that the de-spread desired signal power keeps constant. So the proposed filter uses the estimated interference and noise signal calculated by subtracting the estimated desired signal from the received signal. It is just the reason why the adaptive MSINR filter shows remarkable convergence speed. And to satisfy the constant signal power condition, the projection matrix onto the orthogonal complement of the desired signal space is used for the de-spreading vector. For the proposed filter, we analyze the convergence modes and also investigate the de-spread interfernce and noise power for calculating the theoretical SINR curve. Then, we conduct some computer simulations in order to show the difference between this filter and the conventional one in terms of the SINR convergence speed. As the result, we confirm that the adaptive filter based on the MSINR criterion achieves significant progress in terms of the SINR convergence speed.

This paper presents an effective approach for estimating of the load matching conditions for dielectric barrier discharge (DBD) load. By the simulation method proposed here, optimal working frequency and optimal applied voltage for driving of DBD load can be calculated. Estimation results for the DBD ultraviolet generation lamp as a load of series resonant inverter are presented here, together with their evaluations.