Tomohiro YOSHIHARA Dai KOBAYASHI Haruo YOKOTA
Many concurrency control protocols for B-trees use latch-coupling because its execution is efficient on a single machine. Some studies have indicated that latch-coupling may involve a performance bottleneck when using multicore processors in a shared-everything environment, but no studies have considered the possible performance bottleneck caused by sending messages between processing elements (PEs) in shared-nothing environments. We propose two new concurrency control protocols, “LCFB” and “LCFB-link”, which require no latch-coupling in optimistic processes. The LCFB-link also innovates B-link approach within each PE to reduce the cost of modifications in the PE, as a solution to the difficulty of consistency management for the side pointers in a parallel B-tree. The B-link algorithm is well known as a protocol without latch-coupling, but B-link has the difficulty of guaranteeing the consistency of the side pointers in a parallel B-tree. Experimental results in various environments indicated that the system throughput of the proposed protocols was always superior to those of the conventional protocols, particularly in large-scale configurations, and using LCFB-link was effective for higher update ratios. In addition, to mitigate access skew, data should migrate between PEs. We have demonstrated that our protocols always improve the system throughput and are effective as concurrency controls for data migration.
The security of current public-key cryptosystems relies on the hardness of factoring large integers or solving discrete logarithm problems. However, these mathematical problems can be solved in polynomial time using a quantum computer. This vulnerability has prompted research into post-quantum cryptography using alternative mathematical problems that are secure in the era of quantum computers. In this regard, the National Institute of Standards and Technology (NIST) began to standardize post-quantum cryptography in 2016. In this expository article, we give an overview of recent research on post-quantum cryptography. In particular, we describe the construction and security of multivariate polynomial cryptosystems and lattice-based cryptosystems, which are the main candidates of post-quantum cryptography.
Minoru KURIBAYASHI Nobuo FUNABIKI
The study of universal detector for fingerprinting code is strongly dependent on the design of scoring function. The optimal detector is known as MAP detector that calculates an optimal correlation score for a given single user's codeword. However, the knowledge about the number of colluders and their collusion strategy are inevitable. In this paper, we propose a new scoring function that equalizes the bias between symbols of codeword, which is called bias equalizer. We further investigate an efficient scoring function based on the bias equalizer under the relaxed marking assumption such that white Gaussian noise is added to a pirated codeword. The performance is compared with the MAP detector as well as some state-of-the-art scoring functions.
Tomoki HAYASHI Masafumi NISHIDA Norihide KITAOKA Tomoki TODA Kazuya TAKEDA
In this study, toward the development of smartphone-based monitoring system for life logging, we collect over 1,400 hours of data by recording including both the outdoor and indoor daily activities of 19 subjects, under practical conditions with a smartphone and a small camera. We then construct a huge human activity database which consists of an environmental sound signal, triaxial acceleration signals and manually annotated activity tags. Using our constructed database, we evaluate the activity recognition performance of deep neural networks (DNNs), which have achieved great performance in various fields, and apply DNN-based adaptation techniques to improve the performance with only a small amount of subject-specific training data. We experimentally demonstrate that; 1) the use of multi-modal signal, including environmental sound and triaxial acceleration signals with a DNN is effective for the improvement of activity recognition performance, 2) the DNN can discriminate specified activities from a mixture of ambiguous activities, and 3) DNN-based adaptation methods are effective even if only a small amount of subject-specific training data is available.
Deterministic ID-based signatures are digital signatures where secret keys are probabilistically generated by a key generation center while the signatures are generated deterministically. Although the deterministic ID-based signatures are useful for both systematic and cryptographic applications, to the best of our knowledge, there is no scheme with a tight reduction proof. Loosely speaking, since the security is downgraded through dependence on the number of queries by an adversary, a tighter reduction for the security of a scheme is desirable, and this reduction must be as close to the difficulty of its underlying hard problem as possible. In this work, we discuss mathematical features for a tight reduction of deterministic ID-based signatures, and show that the scheme by Selvi et al. (IWSEC 2011) is tightly secure by our new proof framework under a selective security model where a target identity is designated in advance. Our proof technique is versatile, and hence a reduction cost becomes tighter than the original proof even under an adaptive security model. We furthermore improve the scheme by Herranz (The Comp. Jour., 2006) to prove tight security in the same manner as described above. We furthermore construct an aggregate signature scheme with partial aggregation, which is a key application of deterministic ID-based signatures, from the improved scheme.
Tunstall code is known as an optimal variable-to-fixed length (VF) lossless source code under the criterion of average coding rate, which is defined as the codeword length divided by the average phrase length. In this paper we define the average coding rate of a VF code as the expectation of the pointwise coding rate defined by the codeword length divided by the phrase length. We call this type of average coding rate the average pointwise coding rate. In this paper, a new VF code is proposed. An incremental parsing tree construction algorithm like the one that builds Tunstall parsing tree is presented. It is proved that this code is optimal under the criterion of the average pointwise coding rate, and that the average pointwise coding rate of this code converges asymptotically to the entropy of the stationary memoryless source emitting the data to be encoded. Moreover, it is proved that the proposed code attains better worst-case coding rate than Tunstall code.
Thanyalak RATTANASAWAD Marut BURANARACH Kanda Runapongsa SAIKAEW Thepchai SUPNITHI
With the Semantic Web data standards defined, more applications demand inference engines in providing support for intelligent processing of the Semantic Web data. Rule-based inference engines or rule-based reasoners are used in many domains, such as in clinical support, and e-commerce recommender system development. This article reviews and compares key features of three freely-available rule-based reasoners: Jena inference engine, Euler YAP Engine, and BaseVISor. A performance evaluation study was conducted to assess the scalability and efficiency of these systems using data and rule sets adapted from the Berlin SPARQL Benchmark. We describe our methodology in assessing rule-based reasoners based on the benchmark. The study result shows the efficiency of the systems in performing reasoning tasks over different data sizes and rules involving various rule properties. The review and comparison results can provide a basis for users in choosing appropriate rule-based inference engines to match their application requirements.
A new method is proposed for the construction of pairing-friendly elliptic curves. For any fixed embedding degree, it can transform the problem to solving equation systems instead of exhaustive searching, thus it's more targeted and efficient. Via this method, we obtain various families including complete families, complete families with variable discriminant and sparse families. Specifically, we generate a complete family with important application prospects which has never been given before as far as we know.
Yuriko YOSHINO Masafumi HASHIMOTO Naoki WAKAMIYA
In this paper, we focus on two-layer wireless sensor networks (WSNs) that consist of sensor-concentrator and inter-concentrator networks. In order to collect as much data as possible from a wide area, improving of network capacity is essential because data collection applications often require to gather data within a limited period, i.e., acceptable collection delay. Therefore, we propose a two-stage scheduling method for inter-concentrator networks. The proposed method first strictly schedules time slots of links with heavy interference and congestion by exploiting the combination metric of interference and traffic demand. After that, it simply schedules time slots of the remaining sinks to mitigate complexity. Simulation-based evaluations show our proposal offers much larger capacity than conventional scheduling algorithms. In particular, our proposal improves up to 70% capacity compared with the conventional methods in situations where the proportion of one- and two-hop links is small.
Sheng HU Chuan XIAO Yoshiharu ISHIKAWA
Query autocompletion is an important and practical technique when users want to search for desirable information. As mobile devices become more and more popular, one of the main applications is location-aware service, such as Web mapping. In this paper, we propose a new solution to location-aware query autocompletion. We devise a trie-based index structure and integrate spatial information into trie nodes. Our method is able to answer both range and top-k queries. In addition, we discuss the extension of our method to support the error tolerant feature in case user's queries contain typographical errors. Experiments on real datasets show that the proposed method outperforms existing methods in terms of query processing performance.
Jingjing LIU Chao ZHANG Changyong PAN
In the advanced digital terrestrial/television multimedia broadcasting (DTMB-A) standard, a preamble based on distance detection (PBDD) is adopted for robust synchronization and signalling transmission. However, traditional signalling detection method will completely fail to work under severe frequency selective channels with ultra-long delay spread 0dB echoes. In this paper, a novel transmission parameter signalling detection method is proposed for the preamble in DTMB-A. Compared with the conventional signalling detection method, the proposed scheme works much better when the maximum channel delay is close to the length of the guard interval (GI). Both theoretical analyses and simulation results demonstrate that the proposed algorithm significantly improves the accuracy and robustness of detecting the transmitted signalling.
This study presents the design of a phase correlator for a digital frequency discriminator (DFD) that operates in the 2.0-6.0GHz frequency range. The accuracy of frequency discrimination as determined by the isolation of the correlator mixer was analyzed, and LO-RF isolation was found to have a significant effect on the frequency discrimination error by deriving various analytic equations related to the LO-RF isolation and phase performance. We propose a novel technique (phase sector compensation) to improve the accuracy of frequency discrimination. The phase sector compensation technique improved phase error by canceling the DC offset of the I and Q signals for only the frequency bands where the mixer's LO-RF isolation was below a specified limit. In the 2.0-6.0GHz range, the phase error of the designed phase correlator was decreased from 4.57° to 4.23° (RMS), and the frequency accuracy was improved from 1.02MHz to 0.95MHz (RMS). In the 4.8-6.0GHz range, the RMS phase error was improved from 5.59° to 4.12°, the frequency accuracy was improved from 1.24MHz to 0.92MHz, and the performance of the DFD correlator was improved by 26.3% in the frequency sector where LO-RF isolation was poor. Overall, the DFD correlator performance was improved by LO leakage compensation.
Xiaoqing YE Jiamao LI Han WANG Xiaolin ZHANG
Accurate stereo matching remains a challenging problem in case of weakly-textured areas, discontinuities and occlusions. In this letter, a novel stereo matching method, consisting of leveraging feature ensemble network to compute matching cost, error detection network to predict outliers and priority-based occlusion disambiguation for refinement, is presented. Experiments on the Middlebury benchmark demonstrate that the proposed method yields competitive results against the state-of-the-art algorithms.
Tsubasa MIYAUCHI Ayato ONO Hiroki YOSHIMURA Masashi NISHIYAMA Yoshio IWAI
We propose a method for embedding the awareness state and response state in an image-based avatar to smoothly and automatically start an interaction with a user. When both states are not embedded, the image-based avatar can become non-responsive or slow to respond. To consider the beginning of an interaction, we observed the behaviors between a user and receptionist in an information center. Our method replayed the behaviors of the receptionist at appropriate times in each state of the image-based avatar. Experimental results demonstrate that, at the beginning of the interaction, our method for embedding the awareness state and response state increased subjective scores more than not embedding the states.
Kento SUZUKI Nobukazu TAKAI Yoshiki SUGAWARA Masato KATO
Automatic design of analog circuits using a programmed algorithm is in great demand because optimal analog circuit design in a short time is required due to the limited development time. Although an automatic design using equation-based method can design simple circuits fast and accurately, it cannot solve complex circuits. On the other hand, an automatic design using optimization algorithm such as Ant Colony Optimization, Genetic Algorithm, and so on, can design complex circuits. However, because these algorithms are based on the stochastic optimization technique and determine the circuit parameters at random, a lot of circuits which do not operate in principle are generated and simulated to find the circuit which meets specifications. In this paper, to reduce the search space and the redundant simulations, automatic design using both equation-based method and a genetic algorithm is proposed. The proposed method optimizes the bias circuit blocks using the equation-based method and signal processing blocks using Genetic Algorithm. Simulation results indicate that the evaluation value which considers the trade-off of the circuit specification is larger than the conventional method and the proposed method can design 1.4 times more circuits which satisfy the minimum requirements than the conventional method.
Yukou KOBAYASHI Naoto YANAI Kazuki YONEYAMA Takashi NISHIDE Goichiro HANAOKA Kwangjo KIM Eiji OKAMOTO
By using Password-based Authenticated Key Exchange (PAKE), a server can authenticate a user who has only the same password shared with the server in advance and establish a session key with the user simultaneously. However, in the real applications, we may have a situation where a user needs to share a session key with server A, but the authentication needs to be done by a different server B that shares the password with the user. Further, to achieve higher security on the server side, it may be required to make PAKE tolerant of a server breach by having multiple authentication servers. To deal with such a situation, Abdalla et al. proposed a variant of PAKE called Gateway Threshold PAKE (GTPAKE) where a gateway corresponds to the aforementioned server A being an on-line service provider and also a potential adversary that may try to guess the passwords. However, the schemes of Abdalla et al. turned out to be vulnerable to Undetectable On-line Dictionary Attack (UDonDA). In this paper, we propose the first GTPAKE provably secure against UDonDA, and in the security analysis, we prove that our GTPAKE is secure even if an adversary breaks into parts of multiple authentication servers.
Atsushi NOZAKI Takanobu MIZUTA Isao YAGI
As financial products have grown in complexity and level of risk compounding in recent years, investors have come to find it difficult to assess investment risk. Furthermore, companies managing mutual funds are increasingly expected to perform risk control and thus prevent assumption of unforeseen risk by investors. A related revision to the investment fund legal system in Japan led to establishing what is known as “the rule for investment diversification” in December 2014, without a clear discussion of its expected effects on market price formation having taken place. In this paper, we therefore used an artificial market to investigate its effects on price formation in financial markets where investors follow the rule at the time of a market crash that is caused by the collapse of an asset fundamental price. As results, we found the possibility that when the fundamental price of one asset collapses and its market price also collapses, some asset market prices also fall, whereas other asset market prices rise for a market in which investors follow the rule for investment diversification.
Jun SHIOMI Tohru ISHIHARA Hidetoshi ONODERA
Scaling supply voltage (VDD) and threshold voltage (Vth) dynamically has a strong impact on energy efficiency of CMOS LSI circuits. Techniques for optimizing VDD and Vth simultaneously under dynamic workloads are thus widely investigated over the past 15 years. In this paper, we refer to the optimum pair of VDD and Vth, which minimizes the energy consumption of a circuit under a specific performance constraint, as a minimum energy point (MEP). Based on the simple transregional models of a CMOS circuit, this paper derives a simple necessary and sufficient condition for the MEP operation. The simple condition helps find the MEP of CMOS circuits. Measurement results using standard-cell based memories (SCMs) fabricated in a 65-nm process technology also validate the condition derived in this paper.
Yoshitomo ISOMAE Yosei SHIBATA Takahiro ISHINABE Hideo FUJIKAKE
We proposed the simulation method of reconstructed holographic images in considering phase distribution in the small pixels of liquid crystal spatial light modulator (LC-SLM) and clarified zero-order diffraction appeared on the reconstructed images when the phase distribution in a single pixel is non-uniform. These results are useful for design of fine LC-SLM for realizing wide-viewing-angle holographic displays.
Seiya KAWAMORITA Yosei SHIBATA Takahiro ISHINABE Hideo FUJIKAKE
We examined the novel aggregation control of the LC and monomer during formation of the polymer walls from a LC/monomer mixture in order to suppress the presence of the residual monomers and polymer networks in the pixel areas. The method is utilization of the differing wettabilities among LC and monomer molecules on a substrate surface. We patterned a substrate surface with a fluororesin and a polyimide film, and promoted phase separation of the LC and monomer by cooling process. This resulted in the LC and monomer aggregates primarily existing in the pixel areas and non-pixel areas, respectively. Moreover, the polymer-walls structure which was formed in this method partitioned into individual pixels in a lattice region and prevented the LC from flowing. This polymer-walls formation technique will be useful for developing high-quality flexible LCDs.