Frequency domain blind source separation has the great advantage that the complicated convolution in time domain becomes multiple efficient multiplications in frequency domain. However, the inherent ambiguity of permutation of ICA becomes an important problem that the separated signals at different frequencies may be permuted in order. Mapping the separated signal at each frequency to a target source remains to be a difficult problem. In this paper, we first discuss the inter-frequency correlation based method, and propose a new method using the continuity in power between adjacent frequency components of same source. The proposed method also implicitly utilizes the information of inter-frequency correlation, as such has better performance than the previous method.

The complete subtree (CS) method is widely accepted for the broadcast encryption. A new method for assigning keys in the CS method is proposed in this paper. The essential idea behind the proposed method is to use two trapdoor permutations. Using the trapdoor information, the key management center computes and assigns a key to each terminal so that the terminal can derive all information necessary in the CS method. A terminal has to keep just one key, while log2 N + 1 keys were needed in the original CS method where N is the number of all terminals. The permutations to be used need to satisfy a certain property which is similar to but slightly different from the claw-free property. The needed property, named strongly semi-claw-free property, is formalized in terms of probabilistic polynomial time algorithm, and its relation to the claw-free property is discussed. It is also shown that if the used permutations fulfill the strongly semi-claw-free property, then the proposed method is secure against attacks of malicious users.

The complete subtree (CS) method is one of the most well-known broadcast encryptions which do not enforce the receivers to keep "online." This paper is to reduce the size of secret information which must be stored in a terminal of the method. In the original CS method, the size of the secret information increases as the number of terminals increases. It is shown in this paper that, by making use of a one-way trapdoor permutation, we can make the size constant regardless of the number of terminals. The security of the proposed scheme is investigated, and detailed comparison with other similar schemes is presented. The proposed scheme is suitable for practical implementations of the CS method.

OMAC is a provably secure MAC scheme proposed by Iwata and Kurosawa. NIST currently intends to specify OMAC as the modes recommendation. In August 2003, Mitchell published a note "On the security of XCBC, TMAC and OMAC" to propose a new variant of OMAC. We call it OMAC1". In this paper, we prove that OMAC1" is less secure than the original OMAC. We show a security gap between them. As a result, we obtain a negative answer to Mitchell's open question--OMAC1" is not provably secure even if the underlying block cipher is a PRP. Further, we point out limitations of discussion in [16].

Tamper proofing is a crucial problem in the watermarking application. Aiming at the credibility of multimedia, we present a semi-fragile watermark based on the image permutation. Watermarking detection is performed without resorting to the host image and it is only controlled by secrete keys, thus the whole scheme does not have certain security gaps. The simulation experiments show that it can survive the JPEG compression and effectively specify the region of the image that has been modified maliciously.

This paper deals with broadcast encryption schemes, in which a sender can send information securely to a group of receivers excluding some receivers over a broadcast channel. In this paper we propose modifications of the Complete Subtree (CS), the Subset Difference (SD) and the Layered Subset Difference (LSD) methods based on the Master Key Tree (MKT). Our modifications eliminate log N keys or labels from receivers' storage, in exchange for an increase in the computational overhead, where N is the total number of receivers. We also propose modifications of the SD and LSD methods by applying the Trapdoor One-way Permutation Tree (TOPT) which is originally proposed in order to modify the CS method. Our modifications based on TOPT also eliminate log N labels, and the computational cost is much smaller than MKT based methods.

In this paper, we propose an efficient protocol for proving the correctness of shuffling and an efficient protocol for simultaneously proving the correctness of both shuffling and decryption. The former protocol is the most efficient in computational and communication complexity among 3-move honest verifier perfect zero-knowledge protocols for proving a shuffling of ElGamal cipher-texts. The latter protocol is the most efficient in computational, communication, and round complexity, as a whole, in proving the correctness of both shuffling and decryption of ElGamal cipher-texts. The proposed protocols will be a building block of an efficient, universally verifiable mix-net, whose application to voting systems is prominent.

Checking the equivalence of two Boolean functions under permutation of the variables is an important problem in the synthesis of multiplexer-based field-programmable gate arrays (FPGAs), and the problem is known as Boolean matching. This paper presents an efficient breadth-first search technique for computing a canonical form--namely P-representative--of Boolean functions under permutation of the variables. Two functions match if they have the same P-representative. On an ordinary workstation, on the average, the method requires several microseconds to check the Boolean matching of functions with up to eight variables against a library with tens of thousands of cells.

Automotive fuel pumps are driven by small DC motor. Commutation is carried out in gasoline, and arc voltage and duration are different from that in air. Our laboratory have analyzed commutation phenomenon in gasoline quantitatively and we have considered brush materials. To develop high power motor, we need to examine materials that are less arc abrasion and good sliding condition. In this research, we attend to characteristics of flat carbon commutator. As a result, it is possible to drive longer time, like established cylindrical copper commutator.

The notion of k-wise independent permutations has several applications. From the practical point of view, it often suffices to consider almost (i.e., ε-approximate) k-wise independent permutation families rather than k-wise independent permutation families, however, we know little about how to construct families of ε-approximate k-wise independent permutations of small size. For any n > 0, let Sn be the set of all permutations on {0,1,..., n - 1}. In this paper, we investigate the size of families of ε-approximate k-wise independent permutations and show that (1) for any constant ε 0, if a family Sn of permutations is ε-approximate k-wise independent, then || n(n - 1) (n - k + 1) if ε< 1; || {n(n - 1) (n - k + 1)}/(1 +ε) otherwise; (2) for any constant 0< ε 1, there exists a family Sn of ε-approximate k-wise independent permutations such that || = ; (3) for any constant ε> 0 and any n = pm - 1 with p prime, it is possible to construct a polynomial time samplable family Sn of ε-approximate pairwise independent permutations such that || = O(n(n - 1)/ε); (4) for any constant ε> 0 and any n = pm with p prime, it is possible to construct a polynomial time samplable family Sn of ε-approximate 3-wise independent permutations such that || = O(n(n - 1)(n - 2)/ε). Our results are derived by combinatorial arguments, i.e., probabilistic methods and linear algebra methods.

f 8 and f 9 are standardized by 3GPP to provide confidentiality and integrity, respectively. It was claimed that f 8 and f 9 are secure if the underlying block cipher is a PseudoRandom Permutation (PRP), where f 9 is a slightly modified version of f 9. In this paper, however, we disprove both claims by showing a counterexample. We first construct a PRP F with the following property: There is a non-zero constant Cst such that for any key K, FK()=(). We then show that f 8 and f 9 are completely insecure if F is used as the underlying block cipher. Therefore, PRP assumption does not necessarily imply the security of f 8 and f 9, and it is impossible to prove their security under PRP assumption. It should be stressed that these results do not imply the original f 8 and f 9 (with KASUMI as the underlying block cipher) are insecure, or broken. They simply undermine their provable security.

It is known that a super-pseudorandom permutation on 2n bits can be obtained from a random function f on n bits and two bi-symmetric and AXU hash functions h1 and h2 on n bits. It has a Feistel type structure which is usually denoted by φ(h1,f, f, h2). Bi-symmetric and AXU hash functions h1,h2 are much weaker primitives than a random function f and they can be computed much faster than random functions. This paper shows that we can further weaken the condition on h1.

Davidson's scheme utilizes the order of basic blocks to embed a digital signature in a computer program. To preserve the function of the original program, additional jump instructions are inserted. This involves some overhead in both size and performance. In our implementation, the increase in size was between 9% and 24%. The performance of benchmark programs was 86-102% of the original.

A tree 3-spanner T of a graph G is a spanning tree of G such that the distance between any two vertices in T is at most 3 times of their distance in G. Madanlal et al. have presented an O(n + m) time algorithm for finding a tree 3-spanner of a permutation graph. However, the complexity of their algorithm is not optimal, and their algorithm can not be easily parallelized. In this paper, we will propose an improved algorithm to solve the same problem in O(n) time. Moreover, our algorithm can be easily parallelized so that a tree 3-spanner of a permutation graph can be found in O(log n) time with processors on the EREW PRAM computational model.

NK-Landscapes are stochastically generated fitness functions on bit strings, parameterized with N bits and K epistatic interactions between bits. The term epistasis describes nonlinearities in fitness functions due to changes in the values of interacting bits. Empirical studies have shown that the overall performance of random bit climbers on NK-Landscapes is superior to the performance of some simple and enhanced genetic algorithms (GAs). Analytical studies have also lead to suggest that NK-Landscapes may not be appropriate for testing the performance of GAs. In this work we study the effect of selection, drift, mutation, and recombination on NK-Landscapes for N = 96. We take a model of generational parallel varying mutation GA (GA-SRM) and switch on and off its major components to emphasize each of the four processes mentioned above. We observe that using an appropriate selection pressure and postponing drift make GAs quite robust on NK-Landscapes; different to previous studies, even simple GAs with these two features perform better than a random bit climber (RBC+) for a broad range of classes of problems (K 4). We also observe that the interaction of parallel varying mutation with crossover improves further the reliability of the GA, especially for 12 < K < 32. Contrary to intuition, we find that for small K a mutation only evolutionary algorithm (EA) is very effective and crossover may be omitted; but the relative importance of crossover interacting with varying mutation increases with K performing better than mutation alone (K > 12). This work indicates that NK-Landscapes are useful for testing each one of the major processes involved in a GA and for assessing the overall behavior of a GA on complex non-linear problems. This study also gives valuable guidance to practitioners applying GAs to real world problems of how to configure the GA to achieve better results as the non-linearity and complexity of the problem increases.

The banyan network is a popular and basic structure of the multi-stage ATM switches. This paper presents a novel approach to resolve the internal blocking of the banyan network by using a Non-Blocking Permutation Generator (NBPG). The NBPG performs two functions, i.e., the first is to extract the conflict cells from the incoming cells and the second is to re-assign new input port addresses to the conflict cells. As a result, NBPG generates non-blocking I/O permutations. To estimate the performance of the NBPG, we provide the results of several simulations.

In this work we study the performance of a distributed GA that incorporates in its core parallel cooperative-competitive genetic operators. A series of controlled experiments are conducted using various large and difficult 0/1 multiple knapsack problems to test the robustness of the distributed GA. Simulation results verify that the proposed distributed GA compared with a canonical distributed GA significantly gains in search speed and convergence reliability with less communication cost for migration.

An efficient construction of a permutation network has been proposed by Waksman. However, his construction is only for permutation networks with 2k 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.

A novel multilevel construction for permutation codes is presented. A permutation code of length n is a subset of all the vectors obtained from coordinate permutations on the vector (0,1,. . . ,n-1). We would like to construct a permutation code with cardinality as large as possible for a given code length n and a minimum distance. The proposed construction is available when n = 2m (m is a positive integer). We exploit m-constant weight binary codes as component codes and combine them in a multilevel way. Permutation codes with various parameters can be constructed by selecting appropriate combination of component codes. Furthermore, multi-stage decoding is available for decoding the permutation codes constructed by the proposed construction.

This paper presents an accelerated image halftoning technique using an improved genetic algorithm with tiny populations. The algorithm is based on a new cooperative model for genetic operators in GA. Two kinds of operators are used in parallel to produce offspring: (i) SRM (Self-Reproduction with Mutation) to introduce diversity by means of Adaptive Dynamic-Block (ADB) mutation inducing the appearance of beneficial mutations. (ii) CM (Crossover and Mutation) to promote the increase of beneficial mutations in the population. SRM applies qualitative mutation only to the bits inside a mutation block and controls the required exploration-exploitation balance through its adaptive mechanism. An extinctive selection mechanism subjects SRM's and CM's offspring to compete for survival. The simulation results show that our scheme impressively reduces computer memory and processing time required to obtain high quality halftone images. For example, compared to the conventional image halftoning technique with GA, the proposed algorithm using only a 2% population size required about 15% evaluations to generate high quality images. The results make our scheme appealing for practical implementations of the image halftoning technique using GA.