Rainbow is one of signature schemes based on the problem solving a set of multivariate quadratic equations. While its signature generation and verification are fast and the security is presently sufficient under suitable parameter selections, the key size is relatively large. Recently, Quaternion Rainbow — Rainbow over a quaternion ring — was proposed by Yasuda, Sakurai and Takagi (CT-RSA'12) to reduce the key size of Rainbow without impairing the security. However, a new vulnerability emerges from the structure of quaternion ring; in fact, Thomae (SCN'12) found that Quaternion Rainbow is less secure than the same-size original Rainbow. In the present paper, we further study the structure of Quaternion Rainbow and show that Quaternion Rainbow is one of sparse versions of the Rainbow. Its sparse structure causes a vulnerability of Quaternion Rainbow. Especially, we find that Quaternion Rainbow over even characteristic field, whose security level is estimated as about the original Rainbow of at most 3/4 by Thomae's analysis, is almost as secure as the original Rainbow of at most 1/4-size.

The mobile cloud computing (MCC) paradigm is aimed at integrating mobile devices with cloud computing. In the client-server architecture of MCC, mobile devices offload tasks to the cloud to utilize the computation and storage resources of data centers. However, due to the rapid increase in the traffic demand and complexity of mobile applications, service providers have to continuously upgrade their infrastructures at great expense. At the same time, modern mobile devices have greater resources (communication, computation, and sensing), and these resources are not always fully utilized by device users. Therefore, mobile devices, from time to time, encounter other devices that could provide resources to them. Because the amount of such resources has increased with the number of mobile devices, researchers have begun to consider making use of these resources, located at the “edge” of mobile networks, to increase the scalability of future information networks. This has led to a cooperation based architecture of MCC. This paper reports the concept and design of an resource sharing mechanism that utilize resources in mobile devices through opportunistic contacts between them. Theoretical models and formal definitions of problems are presented. The efficiency of the proposed mechanism is validated through formal proofs and extensive simulation.

The Hierarchical Memory Machine (HMM) is a theoretical parallel computing model that captures the essence of computing on CUDA-enabled GPUs. The approximate string matching (ASM) for two strings X and Y of length m and n is a task to find a substring of Y most similar to X. The main contribution of this paper is to show an optimal parallel algorithm for the approximate string matching on the HMM and implement it on GeForce GTX 580 GPU. Our algorithm runs in $O({nover w}+{mnover dw}+{nLover p}+{mnlover p})$ time units on the HMM with p threads, d streaming processors, memory band width w, global memory access latency L, and shared memory access latency l. We also show that the lower bound of the computing time is $Omega({nover w}+{mnover dw}+{nLover p}+{mnlover p})$ time units. Thus, our algorithm for the approximate string matching is time optimal. Further, we implemented our algorithm on GeForce GTX 580 GPU and evaluated the performance. The experimental results show that the ASM of two strings of 1024 and 4M (=222) characters can be done in 419.6ms, while the sequential algorithm can compute it in 27720ms. Thus, our implementation on the GPU attains a speedup factor of 66.1 over the single CPU implementation.

This paper presents an efficient method using Hadoop MapReduce for constructing a K-nearest neighbor graph (K-NNG) from a large-scale data set. K-NNG has been utilized as a data structure for data analysis techniques in various applications. If we are to apply the techniques to a large-scale data set, it is desirable that we develop an efficient K-NNG construction method. We focus on NN-Descent, which is a recently proposed method that efficiently constructs an approximate K-NNG. NN-Descent is implemented on a shared-memory system with OpenMP-based parallelization, and its extension for the Hadoop MapReduce framework is implied for a larger data set such that the shared-memory system is difficult to deal with. However, a simple extension for the Hadoop MapReduce framework is impractical since it requires extremely high system performance because of the high memory consumption and the low data transmission efficiency of MapReduce jobs. The proposed method relaxes the requirement by improving the MapReduce jobs, which employs an appropriate key-value pair format and an efficient sampling strategy. Experiments on large-scale data sets demonstrate that the proposed method both works efficiently and is scalable in terms of a data size, the number of machine nodes, and the graph structural parameter K.

In anonymous reputation systems, where after an interaction between anonymous users, one of the users evaluates the peer by giving a rating. Ratings for a user are accumulated, which becomes the reputation of the user. By using the reputation, we can know the reliability of an anonymous user. Previously, anonymous reputation systems have been proposed, using an anonymous e-cash scheme. However, in the e-cash-based systems, the bank grasps the accumulated reputations for all users, and the fluctuation of reputations. These are private information for users. Furthermore, the timing attack using the deposit times is possible, which makes the anonymity weak. In this paper, we propose an anonymous reputation system, where the reputations of users are secret for even the reputation manager such as the bank. Our approach is to adopt an anonymous credential certifying the accumulated reputation of a user. Initially a user registers with the reputation manager, and is issued an initial certificate. After each interaction with a rater, the user as the ratee obtains an updated certificate certifying the previous reputation summed up by the current rating. The update protocol is based on the zero-knowledge proofs, and thus the reputations are secret for the reputation manager. On the other hand, due to the certificate, the user cannot maliciously alter his reputation.

This paper proposes an efficient two-scan labeling algorithm for binary hexagonal images. Unlike conventional labeling algorithms, which process pixels one by one in the first scan, our algorithm processes pixels two by two. We show that using our algorithm, we can check a smaller number of pixels. Experimental results demonstrated that our method is more efficient than the algorithm extended straightly from the corresponding labeling algorithm for rectangle binary images.

The Hierarchical Memory Machine (HMM) is a theoretical parallel computing model that captures the essence of computation on CUDA-enabled GPUs. The offline permutation is a task to copy numbers stored in an array a of size n to an array b of the same size along a permutation P given in advance. A conventional algorithm can complete the offline permutation by executing b[p[i]] ← a[i] for all i in parallel, where an array p stores the permutation P. We first present that the conventional algorithm runs $D_w(P)+2{nover w}+3L-3$ time units using n threads on the HMM with width w and latency L, where Dw(P) is the distribution of P. We next show that important regular permutations including transpose, shuffle, and bit-reversal permutations run $2{nover w}+2{nover kw}+2L-2$ time units on the HMM with k DMMs. We have implemented permutation algorithms for these regular permutations on GeForce GTX 680 GPU. The experimental results show that these algorithms run much faster than the conventional algorithm. We also present an offline permutation algorithm for any permutation running in $16{nover w}+16{nover kw}+16L-16$ time units on the HMM with k DMMs. Quite surprisingly, our offline permutation algorithm on the GPU achieves better performance than the conventional algorithm in random permutation, although the running time has a large constant factor. We can say that the experimental results provide a good example of GPU computation showing that a complicated but ingenious implementation with a larger constant factor in computing time can outperform a much simpler conventional algorithm.

In the impulse noise removal from a color image, vector filters are suitable for suppressing false color generation. However, the vector filters do not select optimal vectors to restore noise corrupted pixels. To cope with this problem, a cost function-based vector filter is proposed in this letter.

One of the major applications of contrast-enhanced ultrasound (CEUS) is lesion classification. After contrast agents are administered, it is possible to identify a lesion type from its enhancement pattern. However, CEUS image reading is not easy because there are various types of enhancement patterns even for the same type of lesion, and clear classification criteria have not yet been defined. Some studies have used conventional time intensity curves (TICs), which show the vessel dynamics of a lesion. It is possible to predict lesion type from the TIC parameters, such as the coefficients obtained by curve fitting, peak intensity, flow rate and time to peak. However, these parameters are not always provide sufficient accuracy. In this paper, we prepare 1D Haar-like features which describe intensity changes in a TIC and adopt the Adaboost machine learning technique, which eases understanding of which features are useful. Hyperparameters of weak classifiers, e.g., the step size of a Haar-like filter length and threshold for output of the filter, are optimized by searching for those parameters that give the best accuracy. We evaluate the proposed method using 36 focal splenic lesions in canines 16 of which were benign and 20 malignant. The accuracies were 91.7% (33/36) when inspected by an experienced veterinarian, 75.0% (27/36) by linear discriminant analysis (LDA) using conventional three TIC parameters: time to peak, area under curve and peak intensity, and 91.7% (33/36) using our proposed method. McNemar testing shows the p-value to be less than 0.05 between the proposed method and LDA. This result shows the statistical significance of differences between the proposed method and the conventional TIC analysis method using LDA.

This paper presents a prediction model based on historical data to achieve optimal values of pipelining, concurrency and parallelism (PCP) in GridFTP data transfers in Cloud systems. Setting the correct values for these three parameters is crucial in achieving high throughput in end-to-end data movement. However, predicting and setting the optimal values for these parameters is a challenging task, especially in shared and non-predictive network conditions. Several factors can affect the optimal values for these parameters such as the background network traffic, available bandwidth, Round-Trip Time (RTT), TCP buffer size, and file size. Existing models either fail to provide accurate predictions or come with very high prediction overheads. The author shows that new model based on historical data can achieve high accuracy with low overhead.

Underlay cognitive radio (CR) permits unlicensed secondary users (SUs) to transmit their own data over the licensed spectrum unless the interference from the SUs on the licensed primary user (PU) exceeds an acceptable level. This paper proposes two generalized interference alignment (IA)-based distributed optimization designs for multiple secondary transceivers in the underlay CR case with channel uncertainty under assumption that the actual channel error norm is below a certain bound. One of the designs is an extension to an existing method and the other one is a new design. In these methods, the precoding and power allocation matrices for each SU are either independently or jointly optimized for imperfect channel knowledge to maximize the secondary rates and to hold the secondary interference on the primary receiver under an acceptable limit that is determined by the primary receiver. Numerical results prove the ability of the proposed methods to support significant secondary rates provided that the PU is protected from extra interference from SUs, even in presence of channel uncertainty.

As a prominent feature of Named Data Networking (NDN), in-network caching plays an important role in improving the performance of content delivery. However, if each NDN router indiscriminately caches every data packet passing by (i.e., Caching Everything Everywhere (CEE)), the result can be unnecessarily frequent cache replacement and cache redundancy in en-route routers and thus in-network caches are not utilized in an efficient way [1], [2]. Moreover, managing these in-network caches in a centralized way may lead to excessive resource consumption since the number of these caches is considerable. This work proposes a distributed and opportunistic on-path caching scheme. To be specific, each en-route router independently picks content items to cache in such a way that popular content is more likely to be cached by routers, especially routers near users, and cache redundancy is reduced. Extensive simulations including trace-driven ones in a PoP-level ISP topology suggest that the proposed scheme improves the average cache hit ratio of users' requests and reduces the average hop count as compared to CEE and the other on-path caching algorithms considered herein.

A method to synthesize facial caricatures with non-planar expression is proposed. Several methods have been already proposed to synthesize facial caricatures automatically, but they mainly synthesize plane facial caricatures which look somewhat monotonous. In order to generate expressive facial caricature, the image should be expressed in non-planar style, expressing the depth of the face by shading and highlighting. In this paper, a new method to express such non-planar effect in facial caricatures is proposed by blending the grayscale information of the real face image into the plane caricature. Some methods also have been proposed to generate non-planar facial caricature, but the proposed method can adjust the degree of non-planar expression by interactive evolutionary computing, so that the obtained expression is satisfied by the user based on his/her subjective criteria. Since the color of the face looks changed, when the grayscale information of the natural face image is mixed, the color information of the skin area are also set by interactive evolutionary computing. Experimental results show the high performance of the proposed method.

In this letter, we formally present the definition of KDM-CCA1 security in public key setting, which falls in between the existing KDM-CPA and KDM-CCA2 security. We also prove that if a public key encryption scheme is CCA1 secure and has the properties of secret-key multiplication (or addition) homomorphism, and conditioned plaintext-restorability, then it is KDM-CCA1 secure w.r.t. two ensembles of functions that had been used in [15],[17], respectively. For concrete scheme, we show that the (tailored) Damgård's Elgamal scheme achieves this KDM-CCA1 security based on different assumptions.

In this paper, we evaluate a method of agile software development for carrier Cloud service platform development. It is generally said that agile software development is suitable for small-scale development, but we adopt it for the development which has more than 30 members. We attempted to enable automatic regression tests for each iteration when we adopted agile software development, so that we could start our Cloud service sufficiently fast. We compared and evaluated software reliability growth curves, regression test efforts and bug causes with waterfall development.

The dynamic time warping (DTW) algorithm is widely used to determine time series similarity search. As DTW has quadratic time complexity, the time taken for similarity search is the bottleneck for virtually all time series data mining algorithms. In this paper, we present a parallel approach for DTW on a heterogeneous platform with a graphics processing unit (GPU). In order to exploit fine-grained data-level parallelism, we propose a specific parallel decomposition in DTW. Furthermore, we introduce an optimization technique called diamond tiling to improve the utilization of threads. Results show that our approach substantially reduces computational time.

In recent years, ray space (or light field in other literatures) photography has become popular in the area of computer vision and image processing, and the capture of a ray space has become more significant to these practical applications. In order to handle the huge data problem in the acquisition stage, original data are compressively sampled in the first place and completely reconstructed later. In this paper, in order to achieve better reconstruction quality and faster reconstruction speed, we propose a statistically weighted model in the reconstruction of compressively sampled ray space. This model can explore the structure of ray space data in an orthogonal basis, and integrate this structure into the reconstruction of ray space. In the experiment, the proposed model can achieve much better reconstruction quality for both 2D image patch and 3D image cube cases. Especially in a relatively low sensing ratio, about 10%, the proposed method can still recover most of the low frequency components which are of more significance for representation of ray space data. Besides, the proposed method is almost as good as the state-of-art technique, dictionary learning based method, in terms of reconstruction quality, and the reconstruction speed of our method is much faster. Therefore, our proposed method achieves better trade-off between reconstruction quality and reconstruction time, and is more suitable in the practical applications.

As the development of Internet-of-Things is moving towards large scale industry, such as logistic and manifacturing, there is a need for end-users to get involved in the process of creating IoT easily. In this paper, we introduce PaperIO, a paper-based 3D I/O interface, in which a single piece of paper can be sensed and actuated at the same time in three dimensions using the technology of selective inductive power transmission. With this technology, paper material with multiple embedded receivers, can not only selectively receive inductive power to perform paper-computing behavior, but also work as input sensors to communicate with power transmitter wirelessly. This technology allows the creation of paper-based sensor and actuators, and forms an Interent of Embedded Paper-craft. This paper presents the detailed implementation of the system, results of the technical experiments, and a few sample applications of the presented paper-based 3D I/O interface, and finally discusses the future plan of this research.

This paper focuses on the S-parameter method that is a basic method for measuring the input impedance of balanced-fed antennas. The basic concept of the method is summarized using the two-port network, and it is shown that the method can be enhanced to the unbalanced antennas using a formulation based on incident and reflected waves. The compensation method that eliminates the influence of a measurement jig and the application of the S-parameter method for the measurement of a radiation pattern with reduced unbalanced currents are explained. Further, application of the method for measuring the reflection and coupling coefficients of multiple antennas is introduced. The measured results of the input impedance of a dipole antenna, radiation patterns of a helical antenna on a small housing, and S-parameters of multiple antennas on a small housing are examined, and the measured results obtained with the S-parameter method are verified.

Information-centric networking (ICN) is a promising architecture and has attracted much attention in the area of future Internet architectures. As one of the key technologies in ICN, in-network caching can enhance content retrieval at a global scale without requiring any special infrastructure. In this paper, we propose a workload-aware caching policy, LRU-GT, which allows cache nodes to protect newly cached contents for a period of time (guard time) during which contents are protected from being replaced. LRU-GT can utilize the temporal locality and distinguish contents of different popularity, which are both the characteristics of the workload. Cache replacement is modeled as a semi-Markov process under the Independent Reference Model (IRM) assumption and a theoretical analysis proves that popular contents have longer sojourn time in the cache compared with unpopular ones in LRU-GT and the value of guard time can affect the cache hit ratio. We also propose a dynamic guard time adjustment algorithm to optimize the performance. Simulation results show that LRU-GT can reduce the average hops to get contents and improve cache hit ratio.