Makoto SUGITA Mitsuru KAWAZOE Hideki IMAI
We clarify a relation between the XL algorithm and known Grobner basis algorithms. The XL algorithm was proposed to be a more efficient algorithm to solve a system of algebraic equations under a special condition, without calculating a whole Grobner basis. But in our result, it is shown that to solve a system of algebraic equations with a special condition under which the XL algorithm works is equivalent to calculate the reduced Grobner basis of the ideal associated with the system. Moreover we show that the XL algorithm is a Grobner basis algorithm which can be represented as a redundant variant of a known Grobner basis algorithm F4.
Khalid Mahmood AAMIR Mohammad Ali MAUD Arif ZAMAN Asim LOAN
Power Spectral Density (PSD) computed by taking the Fourier transform of auto-correlation functions (Wiener-Khintchine Theorem) gives better result, in case of noisy data, as compared to the Periodogram approach in case the signal is Gaussian. However, the computational complexity of Wiener-Khintchine approach is more than that of the Periodogram approach. For the computation of short time Fourier transform (STFT), this problem becomes even more prominent where computation of PSD is required after every shift in the window under analysis. This paper presents a recursive form of PSD to reduce the complexity. If the signal is not Gaussian, the PSD approach is insufficient and we estimate the higher order spectra of the signal. Estimation of higher order spectra is even more time consuming. In this paper, recursive versions for computation of bispectrum has been presented as well. The computational complexity of PSD and bispectrum for a window size of N, are O(N) and O(N2) respectively.
Isao NAKANISHI Hiroyuki SAKAMOTO Naoto NISHIGUCHI Yoshio ITOH Yutaka FUKUI
This paper presents a multi-matcher on-line signature verification system which fuses the verification scores in pen-position parameter and pen-movement angle one at total decision. Features of pen-position and pen-movement angle are extracted by the sub-band decomposition using the Discrete Wavelet Transform (DWT). In the pen-position, high frequency sub-band signals are considered as individual features to enhance the difference between a genuine signature and its forgery. On the other hand, low frequency sub-band signals are utilized as features for suppressing the intra-class variation in the pen-movement angle. Verification is achieved by the adaptive signal processing using the extracted features. Verification scores in the pen-position and the pen-movement angle are integrated by using a weighted sum rule to make total decision. Experimental results show that the fusion of pen-position and pen-movement angle can improve verification performance.
Machine learning and data mining algorithms are increasingly being used in the intrusion detection systems (IDS), but their performances are laggard to some extent especially applied in network based intrusion detection: the larger load of network traffic monitoring requires more efficient algorithm in practice. In this paper, we propose and design an anomaly intrusion detection (AID) system based on the vector quantization (VQ) which is widely used for data compression and high-dimension multimedia data index. The design procedure optimizes the performance of intrusion detection by jointly accounting for accurate usage profile modeling by the VQ codebook and fast similarity measures between feature vectors to reduce the computational cost. The former is just the key of getting high detection rate and the later is the footstone of guaranteeing efficiency and real-time style of intrusion detection. Experiment comparisons to other related researches show that the performance of intrusion detection is improved greatly.
Abdulrahman ALHARBY Hideki IMAI
Security protocols flaws represent a substantial portion of security exposures of data networks. In order to evaluate security protocols against any attack, formal methods are equipped with a number of techniques. Unfortunately, formal methods are applicable for static state only, and don't guarantee detecting all possible flaws. Therefore, formal methods should be complemented with dynamic protection. Anomaly detection systems are very suitable for security protocols environments as dynamic activities protectors. This paper presents an intrusion detection system that uses a number of different anomaly detection techniques to detect attacks against security protocols.
Ryotaro HAYASHI Keisuke TANAKA
In this paper, we present previously unproposed schemes for encryption with anonymity and ring signature by applying two techniques. That is, we construct a key-privacy encryption scheme by using N-ary representation, and a ring signature scheme by using the repetition of evaluation of functions. We analyze precisely the properties of these schemes and show their advantage and disadvantage.
In this paper, we analyse the Libert-Quisquater's q-DH signcryption scheme proposed in SCN'2004. Although the paper proved that their scheme is secure against adaptive chosen ciphertext attacks in the random oracle model, we disprove their claim and show that their scheme is not even secure against non-adaptive chosen ciphtertext attacks, which is the weaker security than the adaptive chosen ciphertext attacks. We further show that the semantically secure symmetric encryption scheme defined in their paper is not sufficient to guarantee their signcryption scheme to be secure against adaptive chosen ciphertext attacks.
Harunaga HIWATARI Keisuke TANAKA
At Eurocrypt '02, Cramer and Shoup [1] proposed a general paradigm to construct practical public-key encryption schemes secure against the adaptive chosen ciphertext attack as well as several concrete examples. One of these example is the scheme based on the quadratic residuosity (QR) problem. However this scheme is less efficient than the other examples. In this paper, we construct a new variant of the Cramer-Shoup encryption scheme which is related to the QR problem. Our variant is more efficient than the scheme based on the QR problem.
Hirofumi MATSUO Fujio KUROKAWA Katsuji IIDA
This paper presents an improved gate drive circuit for high power GTO thyristors. The energy-storage/transfer characteristics of an air-core reactor and the fast switching characteristics of FET are employed to make a high gate current of sharp pulse form. The power loss in the gate drive circuit is reduced by using the low resistance and the hysteresis comparator to detect and control the steady on-gate current. The proposed gate drive circuit is analyzed and its usefulness is confirmed by experiments.
Yasuyuki SAKAI Kouichi SAKURAI
We discuss side channel leakage from modular reduction for NIST recommended domain parameters. FIPS 186-2 has 5 recommended prime fields. These primes have a special form which is referred to as generalized Mersenne prime. These special form primes facilitate especially efficient implementation. A typical implementation of efficient modular reduction with such primes includes conditional reduction. A conditional reduction in modular reduction can constitute an information channel on the secret exponent. Several researchers have produced unified code for elliptic point addition and doubling in order to avoid a simple power analysis (SPA). However, Walter showed that SPA still be possible if Montgomery multiplication with conditional reduction is implemented within the unified code. In this paper we show SPA on the modular reduction with NIST recommended primes, combining with the unified code for elliptic point operations. As Walter stated, our results also indicate that even if the unified codes are implemented for elliptic point operations, underlying field operations should be implemented in constant time. The unified approach in itself can not be a countermeasure for side channel attacks.
This letter describes four-branch open-loop transmit diversity schemes that are based on group-coherent codes using space-time block codes (STBC-GCC), for orthogonal frequency-division multiplexing and code-division multiplexing (OFDM-CDM) systems. Open-loop STBC-GCC is designed for transmitting control data by two-dimensional spreading, which is achieved by applying two distinct Walsh-Hadamard (WH) codes within the same mother-code group to two different groups of transmit antennas. The simulation results demonstrated that open-loop STBC-GCC applied to two-dimensional spreading provides space diversity gains and frequency diversity gains. It can therefore be concluded that open-loop STBC-GCC is suitable for transmitting common control data or broadcast data via two-dimensional spreading OFDM-CDM.
Shih-Chieh SHIE Shinfeng D. LIN Chih-Ming FANG
An adaptive data hiding scheme capable of hiding considerable quantities of secret data while preserving acceptable visual quality for cover images is proposed. The major idea of this scheme is to hide secret data into the compressed codes of cover image during the encoding process of side-match vector quantization (SMVQ) such that the interceptors will not capture the secret information. Based on the experimental results, it is confirmed that the proposed scheme is better than earlier works. Moreover, the receiver can efficiently receive both the compressed cover image and the hidden secret data at the same time.
Recently, the direct conversion scheme has been actively investigated for the purpose of cost miniaturization and low power consumption of wireless receivers. IQ imbalance is one of the problems for the direct conversion receiver. In the case of OFCDM modulations, this IQ imbalance causes intercarrier interference (ICI) in the demodulated signals. In this paper, the decision directed scheme for IQ imbalance compensation is proposed. In the proposed scheme, the combination of received symbols which satisfies orthogonality conditions is used for compensation of IQ imbalance. Therefore, in addition to the pilot symbols, the received symbols can be used in order to improve the accuracy of the compensation matrix and BER can be reduced.
Zhangcai HUANG Atsushi KUROKAWA Jun PAN Yasuaki INOUE
In deep submicron designs, predicting gate slews and delays for interconnect loads is vitally important for Static Timing Analysis (STA). The effective capacitance Ceff concept is usually used to calculate the gate delay of interconnect loads. Many Ceff algorithms have been proposed to compute gate delay of interconnect loads. However, less work has been done to develop a Ceff algorithm which can accurately predict gate slew. In this paper, we propose a novel method for calculating the Ceff of interconnect load for gate slew. We firstly establish a new expression for Ceff in 0.8Vdd point. Then the Integration Approximation method is used to calculate the value of Ceff in 0.8Vdd point. In this method, the integration of a complicated nonlinear gate output is approximated with that of a piecewise linear waveform. Based on the value of Ceff in 0.8Vdd point, Ceff of interconnect load for gate slew is obtained. The simulation results demonstrate a significant improvement in accuracy.
Yuichi NAKAMURA Ko YOSHIKAWA Takeshi YOSHIMURA
This paper describes a novel engineering change order (ECO) design method for large-scale, high performance LSIs, based on a patchwork-like partitioning technique. In conventional design methods, even when only small changes are made to the design after the placement and routing process, a whole re-layout must be done, and this is very time consuming. Using the proposed method, we can partition the design into several parts after logic synthesis. When design changes occur in HDL, only the parts related to the changes need to be redesigned. The netlist for the changed design remains almost the same as the original, except for the small changed parts. For partitioning, we used multiple-fan-out-points as partition borders. An experimental evaluation of our method showed that when a small change was made in the RTL description, the revised circuit part had only about 87 gates on average. This greatly reduces the re-layout time required for implementing an ECO. In actual commercial designs in which several design changes are required, it takes only one day to redesign.
Hidenari NAKASHIMA Junpei INOUE Kenichi OKADA Kazuya MASU
Interconnect Length Distribution (ILD) represents the correlation between the number of interconnects and their length. The ILD can predict power consumption, clock frequency, chip size, etc. High core utilization and small circuit area have been reported to improve chip performance. We propose an ILD model to predict the correlation between core utilization and chip performance. The proposed model predicts the influences of interconnect length and interconnect density on circuit performances. As core utilization increases, small and simple circuits improve the performances. In large complex circuits, decreasing the wire coupling capacitance is more important than decreasing the total interconnect length for improvement of chip performance. The proposed ILD model expresses the actual ILD more accurately than conventional models.
Kentaro KAWAKAMI Miwako KANAMORI Yasuhiro MORITA Jun TAKEMURA Masayuki MIYAMA Masahiko YOSHIMOTO
To achieve both of a high peak performance and low average power characteristics, frequency-voltage cooperative control processor has been proposed. The processor schedules its operating frequency according to the required computation power. Its operating voltage or body bias voltage is adequately modulated simultaneously to effectively cut down either switching current or leakage current, and it results in reduction of total power dissipation of the processor. Since a frequency-voltage cooperative control processor has two or more operating frequencies, there are countless scheduling methods exist to realize a certain number of cycles by deadline time. This proposition is frequently appears in a hard real-time system. This paper proves two important theorems, which give the power-minimum frequency scheduling method for any types of frequency-voltage cooperative control processor, such as Vdd-control type, Vth-control type and Vdd-Vth-control type processors.
Jingyu HUA Xiaohu YOU Dongming WANG
In [1], an algorithm based on phase variations of received pilot symbols was proposed to estimate one of the most important channel parameters, maximum Doppler shift, fd. However, AWGN (Additive white gauss noise) will cause large estimation error in some cases. In order to analyze the influence of noise, we extended the phase probability density function (pdf) in [1] to the scenario with both fading and AWGN, then the estimation error is characterized in closed-form expression. By this error expression, we found that power control will affect the estimator of [1] and we proposed a modification method based on SNR estimation to obtain accurate Doppler shift estimation in moderate low SNRs (signal-to-noise ratio). Simulation results show high accuracy in wide range of velocities and SNRs.
Masanori HASHIMOTO Tomonori YAMAMOTO Hidetoshi ONODERA
This paper discusses clock skew due to manufacturing variability and environmental change. In clock tree design, transition time constraint is an important design parameter that controls clock skew and power dissipation. In this paper, we evaluate clock skew under several variability models, and demonstrate relationship among clock skew, transition time constraint and power dissipation. Experimental results show that constraint of small transition time reduces clock skew under manufacturing and supply voltage variabilities, whereas there is an optimum constraint value for temperature gradient. Our experiments in a 0.18 µm technology indicate that clock skew is minimized when clock buffer is sized such that the ratio of output and input capacitance is four.
This paper presents a standard cell-based frequency synthesizer with dynamic frequency counting (DFC) for multiplying input reference frequency by N times. The dynamic frequency counting loop uses variable time period to estimate and tune the frequency of digitally-controlled oscillator (DCO) which enhances frequency detection's resolution and loop stability. Two ripple counters serve as frequency estimator. Conventional phase-frequency detector (PFD) thus is replaced with a digital arithmetic comparator to yield a divider-free circuit structure. Additionally, a 15 bits DCO with the least significant bit (LSB) resolution 1.55 ps is designed by using the gate capacitance difference of 2-input NOR gate in fine-tuning stage. A modified incremental data weighted averaging (IDWA) circuit is also designed to achieve improved linearity of DCO by dynamic element matching (DEM) skill. Based on the proposed standard cell-based frequency synthesizer, a test chip is designed and verified on 0.35-µm complementary metal oxide silicon (CMOS) process, and has a frequency range of (18-214) MHz at 3.3 V with peak-to-peak (Pk-Pk) jitter of less than 70 ps at 192 MHz/3.3 V.