Many knapsack cryptosystems have been proposed but almost all the schemes are vulnerable to lattice attack because of their low density. To prevent the lattice attack, Chor and Rivest proposed a low weight knapsack scheme, which made the density higher than critical density. In Asiacrypt2005, Nguyen and Stern introduced pseudo-density and proved that if the pseudo-density is low enough (even if the usual density is not low enough), the knapsack scheme can be broken by a single call to SVP/CVP oracle. However, the usual density and the pseudo-density are not sufficient to measure the resistance to the lattice attack individually. In this paper, we first introduce the new notion of density D, which naturally unifies the previous two density. Next, we derive conditions for our density so that a knapsack scheme is secure against lattice attack. We obtain a critical bound of density which depends only on the rate of the message length and its Hamming weight. Furthermore, we show that if D<0.8677, the knapsack scheme is solved by lattice attack. Next, we show that the critical bound goes to 1 if the Hamming weight decreases, which means that it is (almost) impossible to construct a low weight knapsack scheme which is supported by an argument of density.

This paper proposes a method for detecting ellipses from an image despite (1) multiple colors within the ellipses, (2) partially occluded ellipses' boundaries, (3) noisy, locally deformed boundaries of ellipses, (4) presence of multiple objects other than the ellipses in the image, and (5) combinations of (1) through (4). After boundary curves are obtained by edge detection, by utilizing the first-order difference curves of the edge orientation of each pixel in the boundary curves, a segment-reconnect method obtains boundary clusters. Then, a modified RANSAC detects ellipses by choosing five pixels randomly from the boundary clusters, where overlapped ellipses are merged. Experimental results using synthesized images and real images demonstrate the effectiveness of the proposed method together with comparison with the Randomized Hough Transform, a well-known conventional method.

This paper presents a novel approach for robot localization using landmark maps. With recent progress in SLAM researches, it has become crucial for a robot to obtain and use large-size maps that are incrementally built by other mapper robots. Our localization approach successfully works with such incremental and large-size maps. In literature, RANSAC map-matching has been a promising approach for large-size maps. We extend the RANSAC map-matching so as to deal with incremental maps. We combine the incremental RANSAC with an incremental LSH database and develop a hybrid of the position-based and the appearance-based approaches. A series of experiments using radish dataset show promising results.

For fast egomotion of a camera, computing feature correspondence and motion parameters by global search becomes highly time-consuming. Therefore, the complexity of the estimation needs to be reduced for real-time applications. In this paper, we propose a compound omnidirectional vision sensor and an algorithm for estimating its fast egomotion. The proposed sensor has both multi-baselines and a large field of view (FOV). Our method uses the multi-baseline stereo vision capability to classify feature points as near or far features. After the classification, we can estimate the camera rotation and translation separately by using random sample consensus (RANSAC) to reduce the computational complexity. The large FOV also improves the robustness since the translation and rotation are clearly distinguished. To date, there has been no work on combining multi-baseline stereo with large FOV characteristics for estimation, even though these characteristics are individually are important in improving egomotion estimation. Experiments showed that the proposed method is robust and produces reasonable accuracy in real time for fast motion of the sensor.

In this paper, we present a high-performance VC-1 main-profile decoder for high-definition (HD) video applications, which can decode HD 720p video streams with 30 fps at 80 MHz. We implemented the decoder with a one-poly eight-metal 0.13 µm CMOS process, which contains about 261,900 logic gates and on-chip memories of 13.9 KB SRAM and 13.1 KB ROM and occupies an area of about 5.1 mm2. In designing the VC-1 decoder, we used a template-based SoC design flow, with which we performed the design space exploration of the decoder by trying various configurations of communication channels. Moreover, we also describe architectures of the computation blocks optimized to satisfy the requirements of VC-1 HD applications.

In order to investigate reading processes of Japanese language learners, we have conducted an experiment to record eye movements during Japanese text reading using an eye-tracking system. We showed that Japanese native speakers use "forward and backward jumping eye movements" frequently [13] [14]. In this paper, we analyzed further the same eye tracking data. Our goal is to examine whether Japanese learners fix their eye movements at boundaries of linguistic units such as words, phrases or clauses when they start or end "backward jumping". We consider conventional linguistic boundaries as well as boundaries empirically defined based on the entropy of the N-gram model. Another goal is to examine the relation between the entropy of the N-gram model and the depth of syntactic structures of sentences. Our analysis shows that (1) Japanese learners often fix their eyes at linguistic boundaries, (2) the average of the entropy is the greatest at the fifth depth of syntactic structures.

In 2003, Kobayashi et al. proposed a new class of knapsack public-key cryptosystems over Gaussian integer ring. This scheme using two-sequences as the public key. In 2005, Sakamoto and Hayashi proposed an improved version of Kobayashi's scheme. In this paper, we propose the knapsack PKC using l-sequences as the public key and present the low-density attack on it. We have described Schemes R and G for l=2, in which the public keys are constructed over rational integer ring and over Gaussian integer ring, respectively. We discusses on the difference of the security against the low-density attack. We show that the security levels of Schemes R and G differ only slightly.

Ubiquitous computing and the upcoming broadcast-and-communication convergence require networks that provide very complex services. In particular, networks are needed that can service several users or terminals at various times or places with various application-layer functions that can be changed at a high response speed by adding high-speed processing at the network edge. I present a query-transaction acceleration appliance that uses a dynamic reconfigurable processor (DRP) and enables high-speed stateful packet-by-packet self-reconfiguration to achieve that requirement. This appliance processes at high speeds, has flexible application layer functions that are changeable with a high-speed response, and uses direct packet I/O bypassing memory, hierarchical interconnection of processors, and stateful packet-by-packet self-reconfiguration. In addition, the DRP enables the fabrication of a compact and electric-power-saving appliance. I made a prototype and implemented several transport/application layer functions, such as TCP connection control, auto-caching of server files, uploading cache data for server, and selection/insertion/deletion/update of data for a database. In an experimental evaluation in which four kinds of query-transactions were continually executed in order, I found that the appliance achieved four functions changeable at a high response speed (within 1 ms), and a processing speed (2,273 transactions/sec.) 18 times faster than a PC with a 2-GHz processor.

The support vector machines (SVMs) are one of the most effective classification techniques in several knowledge discovery and data mining applications. However, a SVM requires the user to set the form of its kernel function and parameters in the function, both of which directly affect to the performance of the classifier. This paper proposes a novel method, named a kernel-tree, the function of which is composed of multiple kernels in the form of a tree structure. The optimal kernel tree structure and its parameters is determined by genetic programming (GP). To perform a fine setting of kernel parameters, the gradient descent method is used. To evaluate the proposed method, benchmark datasets from UCI and dataset of text classification are applied. The result indicates that the method can find a better optimal solution than the grid search and the gradient search.

Although the line-of-sight (LoS) is expected to be useful as input methodology for computer systems, the application area of the conventional LoS detection system composed of video camera and image processor is restricted in the specialized area, such as academic research, due to its large size and high cost. There is a rapid eye motion, so called 'saccade' in our eye motion, which is expected to be useful for various applications. Because of the saccade's very high speed, it is impossible to track the saccade without using high speed camera. The authors have been proposing the high speed vision chip for LoS detection including saccade based on the pixel parallel processing architecture, however, its resolution is very low for the large size of its pixel. In this paper, we propose and discuss an architecture of the vision chip for LoS detection including saccade based on column-parallel processing manner for increasing the resolution with keeping high processing speed.

Broadcast and synchronization techniques are used for cache coherence control in conventional larger scale snoop-based SMP systems. The penalty for synchronization is directly proportional to system size. Meanwhile, advances in LSI technology now enable placing a memory controller on a CPU die. The latency to access directly linked memory is drastically reduced by an on-die controller. Developing an enterprise server system with these CPUs allows us an opportunity to achieve higher performance. Though the penalty of synchronization is counted whenever a cache miss occurs, it is necessary to improve the coherence method to receive the full benefit of this effect. In this paper, we demonstrate a coherence directory organization that fits into DSM enterprise server systems. Originally, a directory-based method was adopted in high performance computing systems because of its huge scalability in comparison with snoop-based method. Though directory capacity miss and long directory access latency are the major problems of this method, the relaxed scalability requirement of enterprise servers is advantageous to us to solve these problems along with an advanced LSI technology. Our proposed directory solves both problems by implementing a full bit vector level map of the coherence directory on an LSI chip. Our experimental results validate that a system controlled by our proposed directory can surpass a snoop-based system in performance even without applying data localization optimization to an online transaction processing (OLTP) workload.

Rapid eye motion, or so called saccade, is a very quick eye motion which always occurs regardless of our intention. Although the line of sight (LOS) with saccade tracking is expected to be used for a new type of computer-human interface, it is impossible to track it using the conventional video camera, because of its speed which is often up to 600 degrees per second. Vision Chip is an intelligent image sensor which has the photo receptor and the image processing circuitry on a single chip, which can process the acquired image information by keeping its spatial parallelism. It has also the ability of implementing the very compact integrated vision system. In this paper, we describe the vision chip architecture which has the capability of detecting the line of sight from infrared eye image, with the processing speed supporting the saccade tracking. The vision chip described here has the pixel parallel processing architecture, with the node automata for each pixel as image processing. The acquired image is digitized to two flags indicating the Purkinje's image and the pupil by comparators at first. The digitized images are then shrunk, followed by several steps of expanding by node automata located at each pixel. The shrinking process is kept executed until all the pixels disappear, and the pixel disappearing at last indicates the center of the Purkinje's image and the pupil. This disappearing step is detected by the projection circuitry in pixel circuit for fast operation, and the coordinates of the center of the Purkinje's image and the pupil are generated by the simple encoders. We describe the whole architecture of this vision chip, as well as the pixel architecture. We also describe the evaluation of proposed algorithm with numerical simulation, as well as processing speed using FPGA, and improvement in resolution using column parallel architecture.

In this paper, we propose a hybrid fine-tuned multi-objective memetic algorithm hybridizing different solution fitness evaluation methods for global exploitation and exploration. To search across all regions in objective space, the algorithm uses a widely diversified set of weights at each generation, and employs a simulated annealing to optimize each utility function. For broader exploration, a grid-based technique is adopted to discover the missing nondominated regions on existing tradeoff surface, and a Pareto-based local perturbation is performed to reproduce incrementing solutions trying to fill up the discontinuous areas. Additional advanced feature is that the procedure is made dynamic and adaptive to the online optimization conditions based on a function of improvement ratio to obtain better stability and convergence of the algorithm. Effectiveness of our approach is shown by applying it to multi-objective 0/1 knapsack problem (MOKP).

In order to solve large Multidimensional Knapsack problems we examine a technique which decomposes a problem instance into two parts. The first part is solved using a traditional technique, such as Dynamic Programming, to reduce the number of variables in the problem by creating a single variable with many non-dominated states. In the second part the remaining variables are determined by an algorithm that repeatedly enumerates them with different constraint and objective requirements. The constraint and objective requirements are imposed by the various non-dominated states of the variable created in the first part of this technique. The main advantage of this approach is that when memory requirements prevent traditional techniques solving a problem instance, the enumeration provides a much less memory-intensive method, enabling a solution to be found. Two approaches are proposed for repeatedly enumerating a 0/1 Multidimensional Knapsack problem. It is demonstrated how these enumeration methods, in conjunction with the Modular Approach, were used to find the optimal solutions to a number of 500-variable, 5-constraint Multidimensional Knapsack problem instances proposed in the literature. The exact solutions to these instances were previously unknown.

It is well known that both shape and motion can be factorized directly from the measurement matrix constructed from feature points trajectories under orthographic camera model. In practical applications, the measurement matrix might be contaminated by noises and contains outliers. A direct SVD (Singular Value Decomposition) to the measurement matrix with outliers would yield erroneous result. This paper presents a novel algorithm for computing SVD with outliers. We decompose the SVD computation as a set of alternate linear regression subproblems. The linear regression subproblems are solved robustly by applying the RANSAC strategy. The proposed robust factorization method with outliers can improve the reconstruction result remarkably. Quantitative and qualitative experiments illustrate the good performance of the proposed method.

In the paper, we introduce TLM methodology focusing on IEEE 802.11 WLAN as a derivative system. Decomposing the entire system into several computation components, we analyzed the property of each transaction, resulting in the TLM. In the case of shared bus, the simulation results show the effect of communication architecture such as bus protocol and bus parameters on the system performance.

Fair scheduling algorithms have been proposed to tackle the problem of bursty and location-dependent errors in wireless packet networks. Most of those algorithms ensure the fairness property and guarantee the QoS of all sessions in a large-scale cellular network such as GSM or GPRS. In this paper, we propose the Weighted-Sacrificing Fair Queueing (WSFQ) scheduling algorithm for small-area and device-limited wireless networks. WSFQ slows down the growth of queue length in limited-buffer devices, still maintains the properties of fairness, and guarantees the throughputs of the system. Moreover, WSFQ can easily adapt itself to various kinds of traffic load. We also implement a packet-based scheduling algorithm, the Packetized Weighted Sacrificing Fair Queueing (PWSFQ), to approach the WSFQ. WSFQ and PWSFQ are evaluated by comparing with other algorithms by mathematical analysis and simulations.

To investigate cyber-criminals, Police sometimes asks Administrator of a computer system to disclose the whole transaction log. Administrator, however, wants to protect the privacy of innocent users. This paper presents a solution for the disclosure/privacy problem of transaction log. In this scheme, Police can search over the encrypted records of the transaction log by keywords. The administrator discloses only the records which include the keyword, but nothing more. Police can verify that the administrator faithfully disclosed all the records which include the keyword.

Spectral-amplitude coding (SAC) techniques in fiber-Bragg-grating (FBG)-based optical code-division multiple-access (OCDMA) systems were investigated in our previous work. This paper adopts the same network architecture to investigate the simultaneous reductions of multiple-access interference (MAI) and optical beat interference (OBI). The MAI is caused by overlapping wavelengths from undesired network coder/decoders (codecs) while the OBI is induced by interaction of simultaneous chips at adjacent gratings. It is proposed that MAI and OBI reductions may be obtained by use of: 1) a source spectrum that is divided into equal chip spacing; 2) coded FBGs characterized by approximately the same number of "0" and "1" code elements; and 3) spectrally balanced photo-detectors. With quasi-orthogonal Walsh-Hadamard coded FBGs, complementary spectral chips is employed as signal pairs to be recombined and detected in balanced photo-detectors, thus achieving simultaneous suppression of both MAIs and OBIs. Simulation results showed that the proposed OCDMA spectral-amplitude coding scheme achieves significant MAI and OBI reductions.

Broadcasting in wireless mobile computing environments is an effective technique to disseminate information to a massive number of clients equipped with powerful, battery operated devices. To conserve the usage of energy, which is scarce resource, the information to be broadcast must be organized so that the client can selectively tune in at the desired portion of the broadcast. In this letter, the power efficient behavior of a predeclaration-based transaction processing in mobile broadcast environments is examined. The analytical studies have been performed to observe the effectiveness of predeclaration-based transaction processing combined with selective tuning ability in mobile broadcast environments.