Energy-efficiency is one of the main concerns in the wireless information dissemination system. This paper presents a wireless broadcast stream organization scheme which enables complex queries (e.g., aggregation queries) to be processed in an energy-efficient way. For efficient processing of complex queries, we propose an approach of broadcasting their pre-computed results with the data stream, wherein the way of replication of index and pre-computation results are investigated. Through analysis and experiments, we show that the new approach can achieve significant performance enhancement for complex queries with respect to the access time and tuning time.
Shingo HASEGAWA Shuji ISOBE Hiroki SHIZUYA
We define two functions fDL and fIF in NPMV, the class of all partial, multivalued functions computed nondeterministically in polynomial time. We prove that they are complete for NPMV, and show that (a) computing discrete logarithms modulo a prime reduces to fDL, and (b) computing integer factorization reduces to fIF. These are the first complete functions that have explicit reductions from significant cryptographic primitives.
Ryo NISHIMAKI Yoshifumi MANABE Tatsuaki OKAMOTO
Identity-based encryption (IBE) is one of the most important primitives in cryptography, and various security notions of IBE (e.g., IND-ID-CCA2, NM-ID-CCA2, IND-sID-CPA etc.) have been introduced. The relations among them have been clarified recently. This paper, for the first time, investigates the security of IBE in the universally composable (UC) framework. This paper first defines the UC-security of IBE, i.e., we define the ideal functionality of IBE, FIBE. We then show that UC-secure IBE is equivalent to conventionally-secure (IND-ID-CCA2-secure) IBE.
Human's ability to perceive elevation of a sound and distinguish whether a sound is coming from the front or rear strongly depends on the monaural spectral features of the pinnae. In order to realize an effective virtual auditory display by HRTF (head-related transfer function) customization, the pinna responses were isolated from the median HRIRs (head-related impulse responses) of 45 individual HRIRs in the CIPIC HRTF database and modeled as linear combinations of 4 or 5 basic temporal shapes (basis functions) per each elevation on the median plane by PCA (principal components analysis) in the time domain. By tuning the weight of each basis function computed for a specific height to replace the pinna response in the KEMAR HRIR at the same height with the resulting customized pinna response and listening to the filtered stimuli over headphones, 4 individuals with normal hearing sensitivity were able to create a set of HRIRs that outperformed the KEMAR HRIRs in producing vertical effects with reduced front/back ambiguity in the median plane. Since the monaural spectral features of the pinnae are almost independent of azimuthal variation of the source direction, similar vertical effects could also be generated at different azimuthal directions simply by varying the ITD (interaural time difference) according to the direction as well as the size of each individual's own head.
We focus on the relationship between the linearization method and linear complexity and show that the linearization method is another effective technique for calculating linear complexity. We analyze its effectiveness by comparing with the logic circuit method. We compare the relevant conditions and necessary computational cost with those of the Berlekamp-Massey algorithm and the Games-Chan algorithm. The significant property of a linearization method is that it needs no output sequence from a pseudo-random number generator (PRNG) because it calculates linear complexity using the algebraic expression of its algorithm. When a PRNG has n [bit] stages (registers or internal states), the necessary computational cost is smaller than O(2n). On the other hand, the Berlekamp-Massey algorithm needs O(N2) where N ( 2n) denotes period. Since existing methods calculate using the output sequence, an initial value of PRNG influences a resultant value of linear complexity. Therefore, a linear complexity is generally given as an estimate value. On the other hand, a linearization method calculates from an algorithm of PRNG, it can determine the lower bound of linear complexity.
Waka NAGAO Yoshifumi MANABE Tatsuaki OKAMOTO
KEM (Key Encapsulation Mechanism) and DEM (Data Encapsulation Mechanism) were introduced by Shoup to formalize the asymmetric encryption specified for key distribution and the symmetric encryption specified for data exchange in ISO standards on public-key encryption. Shoup defined the "semantic security (IND) against adaptive chosen ciphertext attacks (CCA2)" as a desirable security notion of KEM and DEM, that is, IND-CCA2 KEM and IND-CCA2 DEM. This paper defines "non-malleability (NM)" for KEM, which is a stronger security notion than IND. We provide three definitions of NM for KEM, and show that these three definitions are equivalent. We then show that NM-CCA2 KEM is equivalent to IND-CCA2 KEM. That is, we show that NM is equivalent to IND for KEM under CCA2 attacks, although NM is stronger than IND in the definition (or under some attacks like CCA1). In addition, this paper defines the universally composable (UC) security of KEM and DEM, and shows that IND-CCA2 KEM (or NM-CCA2 KEM) is equivalent to UC KEM and that "IND against adaptive chosen plaintext/ciphertext attacks (IND-P2-C2)" DEM is equivalent to UC DEM.
Fault-tolerance is an important design issue in building a reliable mobile computing system. This paper considers checkpointing recovery services for a mobile computing system based on the ad-hoc network environment. Since potential problems of this new environment are insufficient power and limited storage capacity, the proposed scheme tries to reduce disk access frequency for saving recovery information, and also the amount of information saved for recovery. A brief simulation study has been performed and the results show that the proposed scheme takes advantage of the existing checkpointing recovery schemes.
Takefumi MIYOSHI Nobuhiko SUGINO
For a coarse grain dynamic reconfigurable processing unit cooperating with a general purpose processor, a context selection method, which can reduce total execution cycles of a given program, is proposed. The method evaluates context candidates from a given program, in terms of reduction in cycles by exploiting parallel and pipeline execution of the reconfigurable processor. According to this evaluation measure, the method selects appropriate contexts for the dynamic reconfigurable processing unit. The proposed method is implemented on the framework of COINS project. For several example programs, the generated codes are evaluated by a software simulator in terms of execution cycles, and these results prove the effectiveness of the proposed method.
Sensor networks are often deployed in unattended environments, thus leaving these networks vulnerable to false data injection attacks in which an adversary injects forged reports into the network through compromised nodes, with the goal of deceiving the base station or depleting the resources of forwarding nodes. Several research solutions have been recently proposed to detect and drop such forged reports during the forwarding process. Each design can provide the equivalent resilience in terms of node compromising. However, their energy consumption characteristics differ from each other. Thus, employing only a single filtering scheme for a network is not a recommendable strategy in terms of energy saving. In this paper, we propose a fuzzy-based adaptive filtering scheme selection method for energy saving. A fuzzy rule-based system is exploited to choose one of three filtering schemes by considering the false traffic ratio, the security threshold value, distance, and the detection power of the filtering scheme. The adaptive selection of the filtering schemes can conserve energy, and guarantee sufficient resilience.
Hiroaki TANAKA Yoshinori TAKEUCHI Keishi SAKANUSHI Masaharu IMAI Hiroki TAGAWA Yutaka OTA Nobu MATSUMOTO
SIMD instructions are often implemented in modern multimedia oriented processors. Although SIMD instructions are useful for many digital signal processing applications, most compilers do not exploit SIMD instructions. The difficulty in the utilization of SIMD instructions stems from data parallelism in registers. In assembly code generation, the positions of data in registers must be noted. A technique of generating pack instructions which pack or reorder data in registers is essential for exploitation of SIMD instructions. This paper presents a code generation technique for SIMD instructions with pack instructions. SIMD instructions are generated by finding and grouping the same operations in programs. After the SIMD instruction generation, pack instructions are generated. In the pack instruction generation, Multi-valued Decision Diagram (MDD) is introduced to represent and to manipulate sets of packed data. Experimental results show that the proposed code generation technique can generate assembly code with SIMD and pack instructions performing repacking of 8 packed data in registers for a RISC processor with a dual-issue coprocessor which supports SIMD and pack instructions. The proposed method achieved speedup ratio up to about 8.5 by SIMD instructions and multiple-issue mechanism of the target processor.
Microwave measurement methods necessary to characterize copper-clad dielectric laminate substrates are reviewed to realize more precise design of planar circuits: that is, the balanced-type circular disk resonator method for the relative complex permittivity in the normal direction εrn and tan δn, the cavity resonator method and the cut-off waveguide method for one in the tangential direction εrt and tan δt, and the dielectric resonator method for the surface and interface conductivity of copper foil σs and σi. The measured results of the frequency and temperature dependences of these parameters are presented for a PTFE substrate and a copper-clad glass cloth PTFE laminate substrate.
Hiroyuki TODA Masaki NARA Masayuki MATSUMOTO Daniele ALZETTA
We experimentally demonstrated polarization-mode dispersion (PMD) compensation by distributing polarizers with only 1 degree of freedom (DOF) along the transmission line. The average power penalty was measured to be 0.4 dB by inserting four compensators, where average differential group delay was 47% of bit period.
Daisuke KOSAKA Makoto NAGATA Yoshitaka MURASAKA Atsushi IWATA
Chip-level substrate coupling analysis uses F-matrix computation with slice-and-stack execution to include highly concentrated substrate resistivity gradient. The technique that has been applied to evaluation of device-level isolation structures against substrate coupling is now developed into chip-level substrate noise analysis. A time-series divided parasitic capacitance (TSDPC) model is equivalent to a transition controllable noise source (TCNS) circuit that captures noise generation in a CMOS digital circuit. A reference structure incorporating TCNS circuits and an array of on-chip high precision substrate noise monitors provides a basis for the verification of chip-level analysis of substrate coupling in a given technology. Test chips fabricated in two different wafer processings of 0.30-µm and 0.18-µm CMOS technologies demonstrate the universal availability of the proposed analysis techniques. Substrate noise simulation achieves no more than 3 dB discrepancy in peak amplitude compared to measurements with 100-ps/100-µV resolution, enabling precise evaluation of the impacts of the distant placements of sensitive devices from sources of noise as well as application of guard ring/band structures.
Tsukasa YONEYAMA Hirokazu SAWADA Takashi SHIMIZU
Owing to simple structure, low cost and high performance, NRD-guide millimeter wave circuits have attracted much attention in recent years. In this paper, a variety of NRD-guide passive components are reviewed with emphasis on design techniques and performance estimation in the 60 GHz frequency band where the license-free advantage is available. The passive components to be discussed here include compact bends, wideband hybrid couplers, practical three-port junctions, versatile E-plane filters, and effective feeding structures for lens antennas. Some of them are employed to construct millimeter wave transceivers. Eye patterns observed at 1.5 Gbps confirm the potential ability of the fabricated NRD-guide transceivers for high bit-rate, wireless applications.
In this paper, we propose a converting technique based method to solve nonlinear multi-commodity network flow (NMNF) problems with a large number of capacity constraints and discuss the associated implementation. We have combined this method with a successive quadratic programming (SQP) method and a parallel dual-type (PDt) method possessing decomposition effects. We have tested our method in solving a kind of lattice-type network system examples of NMNF problems. The simulation results show that the proposed algorithm is efficient for solving NMNF problems and successfully handles a large number of coupling capacity constraints. Furthermore, the computational efficiency of the proposed algorithm is more significant while the numbers of capacity constraints are increased.
In this paper, we propose a multipath en-route filtering method to deal with the problems caused by black hole attacks and selective forwarding attacks. Our result shows that the method is more resilient to these problems up to a certain number of compromised nodes than the statistical en-route filtering scheme.
Munehiro MATSUURA Tsutomu SASAO
A multiple-output function can be represented by a binary decision diagram for characteristic function (BDD_for_CF). This paper presents a method to represent multiple-output incompletely specified functions using BDD_for_CFs. An algorithm to reduce the widths of BDD_for_CFs is presented. This method is useful for decomposition of incompletely specified multiple-output functions. Experimental results for radix converters, adders, a multiplier, and lists of English words show that this method is useful for the synthesis of LUT cascades. An implementation of English words list by LUT cascades and an auxiliary memory is also shown.
Deok-Kyu HWANG Seung-Hoon HWANG Keum-Chan WHANG
In this paper, we investigate a detection ordering scheme of OSIC (Ordered Successive Interference Cancellation) systems suitable for power controlled MIMO transmission. Most studies about power controlled systems have mainly focused on strategies for transmitter, while the ordering scheme optimized at open-loop system has not been modified. In a conventional ordering scheme, the ordering process is done according to the largeness and smallness relation of each sub-stream's SNR. Unlike the conventional scheme, we derive an optimized detection ordering scheme that uses proximity to the optimal SNR. Because of error propagation, our proximity based algorithm is not valid for open-loop MIMO system in many cases. An optimization problem analysis and simulation results show that the system using the proposed ordering scheme outperforms the system using the conventional ordering scheme. Furthermore, due to the nature of QR decomposition, the proposed scheme shows not only lower implementation complexity but also better BER performance compared with the conventional scheme based on pseudo-inverse.
Soon LEE Seung-Mook BAEK Jung-Wook PARK Young-Hyun MOON
This paper presents a study to estimate the composition of an electric load, i.e. to determine the amount of each load class by the direct measurements of the total electric current waveform from instrument reading. Kalman filter algorithm is applied to estimate the electric load composition on a consumer side of a distributed power system. The electric load supplied from the different voltage level by using a non-ideal delta-wye transformer is also studied with consideration of the practical environment for a distributed power system.
Wenjie JIANG Yusuke ASAI Takeshi ONIZAWA Satoru AIKAWA
In rich scattering environments, multiple antenna systems designed to accomplish spatial multiplexing have enormous potential of lifting the capacity of corresponding multiple input multiple output channels. In this paper, we present a new low complexity algorithm for decision feedback equalization detector in the SM scheme. The basic idea is to reduce the joint optimization problem to separate optimization problems to achieve better performance-complexity tradeoffs. Concretely, we separately optimize the detection order and the detector filters so that the complexity of the entire signal detection task is reduced. The new order search rule approximates the optimal Bell Labs layered space time (BLAST) approach from a geometrical perspective, and the detector filters are derived using a Cholesky based QR decomposition. The new algorithm is able to switch from zero forcing to minimum mean square error without additional operations and the computational effort is a small fraction of that in the optimal BLAST algorithm. Despite its low complexity, the error performance of new detector closely approximates that of the standard BLAST.