Cryptography and Coding Theory are closely related in many respects. Recently, the problem of "decoding Reed Solomon codes" (also known as "polynomial reconstruction") was suggested as an intractability assumption to base the security of protocols on. This has initiated a line of cryptographic research exploiting the rich algebraic structure of the problem and its variants. In this paper we give a short overview of the recent works in this area as well as list directions and open problems in Polynomial Reconstruction Based Cryptography.

Braids have been studied by mathematicians for more than one century. Because they are so practical as to be used for cryptography, many cryptographers have been interested in them. For the last five years, there have been proposed some cryptographic applications and cryptanalyses in the area of braids. We survey the main examples of these results.

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 S_n 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 S_n 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 S_n of ε-approximate k-wise independent permutations such that || = ; (3) for any constant ε> 0 and any n = p^m - 1 with p prime, it is possible to construct a polynomial time samplable family S_n of ε-approximate pairwise independent permutations such that || = O(n(n - 1)/ε); (4) for any constant ε> 0 and any n = p^m with p prime, it is possible to construct a polynomial time samplable family S_n 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.

The main purpose of this paper is to show that we can exploit the difference (l₁-norm and l₂-norm) in the probability calculation between quantum and probabilistic computations to claim the difference in their space efficiencies. It is shown that there is a finite language L which contains sentences of length up to O(n^c+1) such that: (i) There is a one-way quantum finite automaton (qfa) of O(n^c+4) states which recognizes L. (ii) However, if we try to simulate this qfa by a probabilistic finite automaton (pfa) using the same algorithm, then it needs Ω(n^2c+4) states. It should be noted that we do not prove real lower bounds for pfa's but show that if pfa's and qfa's use exactly the same algorithm, then qfa's need much less states.

This paper investigates some fundamental properties of one-way alternating pushdown automata with sublinear space. We first show that one-way nondeterministic pushdown automata are incomparale with one-way alternating pushdown automata with only universal states, for spaces between log log n and log n, and also for spaces between log n and n/log n. We then show that there exists an infinite space hierarchy among one-way alternating pushdown automata with only universal states which have sublinear space.

This paper considers Quasi-Reduced ordered Multi-valued Decision Diagrams with k bits (QRMDD(k)s) to represent binary logic functions. Experimental results show relations between the values of k and the numbers of nodes, the memory sizes, the numbers of memory accesses, and area-time complexity for QRMDD(k). For many benchmark functions, the numbers of nodes and memory accesses for QRMDD(k)s are nearly equal to of the corresponding Quasi-Reduced ordered Binary Decision Diagrams (QRBDDs), and the memory sizes and the area-time complexities for QRMDD(k)s are minimum when k = 2 and k = 3-6, respectively.

A nearly equitable edge-coloring of a multigraph is a coloring such that edges incident to each vertex are colored equitably in number. This problem was solved in O(kn²) time, where n and k are the numbers of the edges and the colors, respectively. The running time was improved to be O(n²/k + n|V|) later. We present a more efficient algorithm for this problem that runs in O(n²/k) time.

The issues of comparing the similarity or dissimilarity (distance) between structures have been studied. Especially, several distances between trees and their efficient algorithms have been proposed. However, all of the tree distances are defined based on mapping between vertices only, and they are helpless to compare the tree structures whose vertices and edges hold information. In this paper, we will propose a mapping between rooted and unordered trees based on vertex translation and edge translation, and then define a distance based on proposed mapping, and develop an efficient algorithm for computing proposed distance. Proposed distance can be used to compare the similarity or distance between two natural language sentences.

The concepts of M-convexity and L-convexity, introduced by Murota (1996, 1998) for functions on the integer lattice, extract combinatorial structures in well-solved nonlinear combinatorial optimization problems. These concepts are extended to polyhedral convex functions and quadratic functions on the real space by Murota-Shioura (2000, 2001). In this paper, we consider a further extension to general convex functions. The main aim of this paper is to provide rigorous proofs for fundamental properties of general M-convex and L-convex functions.

This paper addresses the problem of arranging fewest possible probes to detect a hidden object in a specified region and presents a reasonable scheme for the purpose. Of special interest is the case where an object is a double-sided conic cylinder which represents the shape of the energy distribution of laser light used in the optical network. The performance of our scheme is evaluated by comparing the number of probes to that of an existing scheme, and our scheme shows a potential for reducing the number of probes. In other words, the time for detection is significantly reduced from a realistic point of view.

In this paper we consider the VLSI layout (i.e., Manhattan layout) of graphs into grids with minimum width (i.e., the length of the shorter side of a grid) as well as with minimum area. The layouts into minimum area and minimum width are equivalent to those with the largest possible aspect ratio of a minimum area layout. Thus such a layout has a merit that, by "folding" the layout, a layout of all possible aspect ratio can be obtained with increase of area within a small constant factor. We show that an N-vertex tree with layout-width k (i.e., the minimum width of a grid into which the tree can be laid out is k) can be laid out into a grid of area O(N) and width O(k). For binary tree layouts, we give a detailed trade-off between area and width: an N-vertex binary tree with layout-width k can be laid out into area and width k + α, where α is an arbitrary integer with 0 α , and the area is existentially optimal for any k 1 and α 0. This implies that α = Ω(k) is essential for a layout of a graph into optimal area. The layouts proposed here can be constructed in polynomial time. We also show that the problem of laying out a given graph G into given area and width, or equivalently, into given length and width is NP-hard even if G is restricted to a binary tree.

A variety of real-time multicast applications such as video conferences, remote lectures, and video-on-demand have become in commonplace with the expansion of broadband Internet services. Due to nontrivial problems in the IP multicast technology, the peer-to-peer multicast technology (P2P-multicast) has emerged as a practical implementation, although its network resource utilization is less efficient. A multihome network has the potential of alleviating this inefficiency by providing flexibility in communication path selections for each host with multiple gateways to the Internet. This paper has first formulated the P2P-multicast routing problem in the multihome network, and has proved the NP-completeness of its decision problem. Then, a two-stage heuristic algorithm called P2PMM_router has been presented for this P2P Multicast Multihome-network routing problem. The first stage constructs an initial multicast routing tree from an optimum spanning tree by Prim algorithm, through satisfying the constraints. The second stage improves the tree by repeating partial modifications and constraint satisfactions. The extensive simulation results using random network instances support the effectiveness of our P2PMM_router.

Fractional calculus is the generalization of the operators of differential and integration to non-integer order, and a differential equation involving the fractional calculus operators such as d^1/2/dt^1/2 and d^-1/2/dt^-1/2 is called the fractional differential equation. They have many applications in science and engineering. But not only its analytical solutions exist only for a limited number of cases, but also, the numerical methods are difficult to solve. In this paper we propose a new numerical method based on the operational matrices of the orthogonal functions for solving the fractional calculus and fractional differential equations. Two classical fractional differential equation examples are included for demonstration. They show that the new approach is simper and more feasible than conventional methods. Advantages of the proposed method include (1) the computation is simple and computer oriented; (2) the scope of application is wide; and (3) the numerically unstable problem never occurs in our method.

To examine the computational complexity of cryptographic primitives such as the discrete logarithm problem, the factoring problem and the Diffie-Hellman problem, we define a new problem called square-root exponent, which is a problem to compute a value whose discrete logarithm is a square root of the discrete logarithm of a given value. We analyze reduction between the discrete logarithm problem modulo a prime and the factoring problem through the square-root exponent. We also examine reductions among the computational version and the decisional version of the square-root exponent and the Diffie-Hellman problem and show that the gap between the computational square-root exponent and the decisional square-root exponent partially overlaps with the gap between the computational Diffie-Hellman and the decisional Diffie-Hellman under some condition.

NMAC is a function for message authentication based on cryptographic hash functions such as SHA. It is shown to be a secure message authentication code if its compression function with fixed input length is a secure message authentication code and its iterated hash function with variable input length constructed with the compression function is weakly collision resistant. In this article, two results are shown on the strength of the weak collision resistance of the iterated hash function in NMAC. First, it is shown that the weak collision resistance of the iterated hash function in NMAC is not implied by the pseudorandomness of its compression function even if the MD-strengthening is assumed. Second, the weak collision resistance of the iterated hash function in NMAC implies the collision resistance of its compression function if the compression function is pseudorandom.

KASUMI is a block cipher which has been adopted as a standard of 3GPP. In this paper, we study the pseudorandomness of idealized KASUMI type permutations for adaptive adversaries. We show that
●the four-round version is pseudorandom and
●the six-round version is super-pseudorandom.

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, F_K()=(). 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.

In this paper, we formally define and analyze the security notions of authenticated encryption in unconditional security setting. For confidentiality, we define the notions, APS (almost perfect secrecy) and NM (non-malleability), in terms of an information-theoretic viewpoint along with our model where multiple senders and receivers exist. For authenticity, we define the notions, IntC (integrity of ciphertexts) and IntP (integrity of plaintexts), from a view point of information theory. And then we combine the above notions to define the security notions of unconditionally secure authenticated encryption. Then, we analyze relations among the security notions. In particular, it is shown that the strongest security notion is the combined notion of APS and IntC. Finally, we formally define and analyze the following generic composition methods in the unconditional security setting along with our model: Encrypt-and-Sign, Sign-then-Encrypt and Encrypt-then-Sign. Consequently, it is shown that: the Encrypt-and-Sign composition method is not always secure; the Sign-then-Encrypt composition method is not always secure; and the Encrypt-then-Sign composition method is always secure, if a given encryption meets APS and a given signature is secure.

Authentication codes (A-codes, for short) are considered as important building blocks for constructing unconditionally secure authentication schemes. Since in the conventional A-codes, two communicating parties, transmitter and receiver, utilized a common secret key, and such A-codes do not provide non-repudiation. With the aim of enhancing with non-repudiation property, Simmons introduced A²-codes. Later, Johansson formally defined an improved version of A²-codes called, the A³-codes. Unlike A²-codes, A³-codes do not require an arbiter to be fully trusted. In this paper, we clarify the security definition of A³-codes which may be misdefined. We show a concrete attack against an A³-code and conclude that concrete constructions of A³-codes implicitly assumes a trusted arbiter. We also show that there is no significant difference between A²-codes and A³-codes in a practical sense and further argue that it is impossible to construct an "ideal" A³-codes, that is, without any trusted arbiter. Finally, we introduce a novel model of asymmetric A-codes with an arbiter but do not have to be fully trusted, and also show a concrete construction of the asymmetric A-codes for the model. Since our proposed A-code does not require fully trusted arbiters, it is more secure than A²-codes or A³-codes.

We proposed a one-way trapdoor permutation f based multi-signature scheme which can keep tighter reduction rate. Assuming the underlying hash functions are ideal, our proposed scheme is not only provably secure, but are so in a tight. An ability to forge multi-signatures with a certain amount of computational resources implies the ability to invert a one-way trapdoor permutation f (on the same size modulus) with about the same computational effort. The proposed scheme provides the exact security against Adaptive-Chosen-Message-Attack and Adaptive-Insider-Attack by . can also attack in key generation phase, and act in collusion with corrupted signers.

In this paper, we propose a fast signature scheme which realizes short transmissions and minimal on-line computation. Our scheme requires a modular exponentiation as preprocessing (i.e., off-line computation). However, we need to acknowledge the existance of the following remarkable properties: neither multiplication nor modular reduction is used in the actual signature generation (i.e., on-line computation). Our scheme requires only two operations: hashing and addition. Although some fast signature schemes with small on-line computation have been proposed so far, those schemes require multiplication or modular reduction in the on-line phase. This leads to a large amount of work compared to that of addition. As far as we know, this is the first approach to obtain the fast signature without those two calculus methods.

In this paper, general definitions of collusion secure codes are shown. Previously defined codes such as frameproof code, secure frameproof code, identifiable parent property code, totally c-secure code, traceability code, and (c,g/s)-secure code are redefined under various marking assumptions which are suitable for most of the fingerprinting systems. Then, new relationships among the combined notions of codes and the marking assumptions are revealed. Some (non)existence results are also shown.

Illegal distribution of signed documents can be considered as one of serious problems of digital signatures. In this paper, to solve the problem, we propose three protocols concerning signature schemes. These schemes achieve not only traceability of an illegal user but also universal verifiability. The first scheme is a basic scheme which can trace an illegal receiver, and the generation and tracing of a signed document are simple and efficient. However, in this scheme, it is assumed that a signer is honest. The second scheme gives another tracing method which does not always assume that a signer is honest. Furthermore, in the method, an illegal user can be traced by an authority itself, hence, it is efficient in terms of communication costs. However, in this scheme it is assumed that there exists only a legal verification algorithm. Thus, in general, this scheme cannot trace a modified signed document which is accepted by a modified verification algorithm. The third one is a scheme which requires no trusted signer and allows a modified verification algorithm. It can trace an illegal receiver or even a signer in such a situation. All of our schemes are constructed by simple combinations of standard signature schemes, consequently, one can flexibly choose suitable building blocks for satisfying requirements for a system.

Compact encodings of the web graph are required in order to keep the graph on the main memory and to perform operations on the graph efficiently. In this paper, we propose a new compact encoding of the web graph. It is 10% more compact than Link2 used in the Connectivity Server of Altavista and 20% more compact than the encoding proposed by Guillaume et al. in 2002 and is comparable to it in terms of extraction time.

This paper investigates closure properties of one-pebble Turing machines with sublogarithmic space. It shows that for any function log log n L(n) = o(log n), neither of the classes of languages accepted by L(n) space-bounded deterministic and self-verifying nondeterministic one-pebble Turing machines is closed under concatenation, Kleene closure, and length-preserving homomorphism.

The efficient squaring algorithm is an important role in large integer arithmetic. All multiplication algorithms can be used for squaring large integers, but their performance can be greatly improved by using the standard squaring algorithm. The standard squaring algorithm is quite well-known, but unfortunately there is an improper carry handling bug in it. Recently, Guajardo and Paar proposed a modified squaring algorithm to fix the bug in the standard squaring algorithm. In this paper, we first point out that there is still an error-indexing bug in the Guajardo-Paar squaring algorithm. Then, we propose a new efficient squaring algorithm that not only avoids the bugs in both the standard squaring algorithm and the Guajardo-Paar squaring algorithm but also improves the performance in squaring computation. Our analyses and our simulations indicate that the proposed squaring algorithm is about 2.5 times faster in comparison with the standard multiplication algorithm in Pentium Series CPU. The performance of 1024-bit RSA cryptosystem can be saved 34.3% by using the proposed squaring algorithm to replace the standard multiplication.

We propose a method for reducing the size of a share in visual secret sharing schemes. The proposed method does not cause the leakage and the loss of the original image. The quality of the recovered image is almost same as that of previous schemes.

Combinatorial designs are normally used to construct visual cryptographic schemes. For such schemes two parameters are very important viz. pixel expansion and contrast. Optimizing both is a very hard problem. The schemes having optimal contrast tend to use a high pixel expansion. The focus of the paper is to construct schemes for which pixel expansion is modest and the contrast is close to optimality. Here the tool is latin squares that haven't been used earlier for this purpose.

This paper provides methods for construction of pairing-based cryptosystems based on non-supersingular elliptic curves.

In this paper, we examine the computational Diffie-Hellman problem and decisional Diffie-Hellman problem in 3-rd order linear feedback shift register and show that the shift register based Diffie-Hellman problems are equivalent to the Diffie-Hellman problems over prime subgroup of GF(p^3e) respectively. This result will be useful in constructing new cryptographic primitives based on the hardness of the shift register based Diffie-Hellman problems.

This paper presents recursive algorithms for the least mean-squared error linear filtering and fixed-interval smoothing estimators, from uncertain observations for the case of white and white plus coloured observation noises. The estimators are obtained by an innovation approach and do not use the state-space model, but only covariance information about the signal and the observation noises, as well as the probability that the signal exists in the observed values. Therefore the algorithms are applicable not only to signal processes that can be estimated by the conventional formulation using the state-space model but also to those for which a realization of the state-space model is not available. It is assumed that both the signal and the coloured noise autocovariance functions are expressed in a semi-degenerate kernel form. Since the semi-degenerate kernel is suitable for expressing autocovariance functions of non-stationary or stationary signal processes, the proposed estimators provide estimates of general signal processes.

This paper considers the least-squares linear estimation problem of signals from randomly delayed observations when the additive white noise is correlated with the signal. The delay values are treated as unknown variables, modelled by a binary white noise with values zero or one; these values indicate that the measurements arrive in time or they are delayed by one sampling time. A recursive one-stage prediction and filtering algorithm is obtained by an innovation approach and do not use the state-space model of the signal. It is assumed that both, the autocovariance functions of the signal and the crosscovariance function between the signal and the observation noise are expressed in a semi-degenerate kernel form; using this information and the delay probabilities, the estimators are recursively obtained.

In this work, a novel Multiple Valued Exclusive-Or Sum Of Products (MVESOP) minimization formulation is analyzed and an algorithm is presented that detects minimum MVESOP expressions when the weight of the function is less than eight. A heuristic MVESOP algorithm based on a novel cube transformation operation is then presented. Experimental results on MCNC benchmarks and randomly generated functions indicate that the algorithm matches or outperforms the quality of the state of the art in ESOP minimizers.

In the CNN problem, a "scene" appears on the two-dimensional plane, at different positions sequentially, and a "camera crew" has to shoot the scene whenever it appears. If a scene appears at some position, the camera crew does not have to move to the position exactly, but has only to move to a point that lies in the same horizontal or vertical line with the scene. Namely it is enough to move either to the same row or to the same column. The goal is to minimize the total moving distance of the camera crew. This problem has been quite popular in the last decade but it is still open whether or not there is a competitive algorithm, i.e., an algorithm with competitive ratio bounded by a constant. In this paper we study this problem under a natural restriction that the server can move only along the X-axis and the Y-axis. It is shown that there exists a competitive algorithm for this restricted version, namely there is an online algorithm for this "axis-bound CNN" with competitive ratio 9.0.

H-coloring problem is a coloring problem with restrictions such that some pairs of colors cannot be used for adjacent vertices, where H is a graph representing the restrictions of colors. We deal with the case that H is the complement graph of a cycle of odd order 2p + 1. This paper presents the following results: (1) chordal graphs and internally maximal planar graphs are -colorable if and only if they are p-colorable (p 2), (2) -coloring problem on planar graphs is NP-complete, and (3) there exists a class that includes infinitely many -colorable but non-3-colorable planar graphs.

A 2-dimensional cylindrical k-within-consecutive-(r, s)-out-of-(m, n):F system consists of m n components arranged on a cylindrical grid. Each of m circles has n components, and this system fails if and only if there exists a grid of size r s within which at least k components are failed. This system may be used into reliability models of "Feelers for measuring temperature on reaction chamber," "TFT Liquid Crystal Display system with 360 degree wide area" and others. In this paper, first, we propose an efficient algorithm for the reliability of a 2-dimensional cylindrical k-within-consecutive-(r, s)-out-of-(m, n):F system. The feature of this algorithm is calculating their system reliabilities with shorter computing time and smaller memory size than Akiba and Yamamoto. Next, we show some numerical examples so that our proposed algorithm is more effective than Akiba and Yamamoto for systems with large n.

In this paper, a simple blind algorithm for a beamforming antenna is proposed. This algorithm exploits the property of cyclostationary signals whose cyclic autocorrelation function depends on delay as well as frequency. The cost function is the mean square error between the delay product of the beamformer output and a complex exponential. Exploiting the delay greatly reduces the possibility of capturing undesired signals. Through analysis of the minima of the non-quadratic cost function, conditions to extract a single signal are derived. Application of this algorithm to code-division multiple-access systems is considered, and it is shown through simulation that the desired signal can be extracted by appropriately choosing the delay as well as the frequency.

In this paper, we present a predictive control method, based on Fuzzy Neural Network (FNN), for the control of chaotic systems without precise mathematical models. In our design method, the parameters of both predictor and controller are tuned by a simple gradient descent scheme, and the weight parameters of the FNN are determined adaptively throughout system operations. In order to design the predictive controller effectively, we describe the computing procedure for each of the two important parameters. In addition, we introduce a projection matrix for determining the control input, which decreases the control performance function very rapidly. Finally, we depict various computer simulations on two representative chaotic systems (the Duffing and Hénon systems) so as to demonstrate the effectiveness of the new chaos control method.

An efficient architecture for a FPGA symmetry FIR filter is proposed that employs 2-bit parallel-distributed arithmetic (2-bit PDA). The partial product is pre-calculated and saved into the distributed ROM. This eliminates the large amount of logic needed to compute multiplication results. The proposed architecture consumes less area and offers higher speed operation because the multiplier is omitted.

We propose Max-Plus Linear (MPL) systems with selective parameters that can describe a certain class of Timed Petri nets (TPN). In this class, selector and joint places are incorporated with Single-Input and Single-Output Timed Event Graph (SISO TEG) subnets. We confirm that the proposed controller effectively works taking into account practical constraints through a numerical example.