著者

Ryoichi TERAMURA Toshihiro OHIGASHI Hidenori KUWAKADO Masakatu MORII

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences (ISSN:09168508)

巻号頁・発行日

vol.E94-A, no.1, pp.10-18, 2011-01-01

---

Conventional class of weak keys on RC4 stream cipher is defined as a specific case that combinations of the first three bytes of secret key satisfy two relational equations. This paper expands and generalizes the classes of weak keys using generalized relational equations and special classes of the internal state (called predictive state). We derive the probability that generalized classes of weak keys leak the information of bytes of the secret key. Furthermore, we enumerate the generalized classes of weak keys and show that most of them leak more information of the secret key than Roos' one.

著者

Yuki ANDO Seiya SHIBATA Shinya HONDA Hiroyuki TOMIYAMA Hiroaki TAKADA

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences (ISSN:09168508)

巻号頁・発行日

vol.E93-A, no.12, pp.2509-2516, 2010-12-01

---

We present a hardware sharing method for design space exploration of multi-processor embedded systems. In our prior work, we had developed a system-level design tool named SystemBuilder which automatically synthesizes target implementation of a system from a functional description. In this work, we have extended SystemBuilder so that it can automatically synthesize an area-efficient implementation which shares a hardware module among different applications. With SystemBuilder, designers only need to enable an option in order to share a hardware module. The designers, therefore, can easily explore a design space including hardware sharing in short time. A case study shows the effectiveness of the hardware sharing on design space exploration.

著者

Tohru ISHIHARA

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences (ISSN:09168508)

巻号頁・発行日

vol.E93-A, no.12, pp.2533-2541, 2010-12-01

被引用文献数

5

---

This paper proposes an energy efficient processor which can be used as a design alternative for the dynamic voltage scaling (DVS) processors in embedded system design. The processor consists of multiple PE (processing element) cores and a selective set-associative cache memory. The PE-cores have the same instruction set architecture but differ in their clock speeds and energy consumptions. Only a single PE-core is activated at a time and the other PE-cores are deactivated using clock gating and signal gating techniques. The major advantage over the DVS processors is a small overhead for changing its performance. The gate-level simulation demonstrates that our processor can change its performance within 1.5 microsecond and dissipates about 10 nano-joule while conventional DVS processors need hundreds of microseconds and dissipate a few micro-joule for the performance transition. This makes it possible to apply our multi-performance processor to many real-time systems and to perform finer grained and more sophisticated dynamic voltage control.

著者

Makoto SUGIHARA

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences (ISSN:09168508)

巻号頁・発行日

vol.E93-A, no.12, pp.2560-2569, 2010-12-01

被引用文献数

2

---

Utilizing a heterogeneous multiprocessor system has become a popular design paradigm to build an embedded system at a cheap cost. A reliability issue, which is vulnerability to soft errors, has not been taken into account in the conventional IC (integrated circuit) design flow, while chip area, performance, and power consumption have been done. This paper presents a system design paradigm in which a heterogeneous multiprocessor system is synthesized and its chip area is minimized under real-time and reliability constraints. First we define an SEU vulnerability factor as a vulnerability measure for computer systems so that we evaluate task-wise reliability over various processor structures. Next we build a mixed integer linear programming (MILP) model for minimizing the chip area of a heterogeneous multiprocessor system under real-time and SEU vulnerability constraints. Finally, we show several experimental results on our synthesis approach. Experimental results show that our design paradigm has achieved automatic generation of cost-competitive and reliable heterogeneous multiprocessor systems.

著者

Hasitha Muthumala WAIDYASOORIYA Daisuke OKUMURA Masanori HARIYAMA Michitaka KAMEYAMA

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences (ISSN:09168508)

巻号頁・発行日

vol.E93-A, no.12, pp.2570-2580, 2010-12-01

---

Heterogeneous multi-core processors are attracted by the media processing applications due to their capability of drawing strengths of different cores to improve the overall performance. However, the data transfer bottlenecks and limitations in the task allocation due to the accelerator-incompatible operations prevents us from gaining full potential of the heterogeneous multi-core processors. This paper presents a task allocation method based on algorithm transformation to increase the freedom of task allocation. We use approximation methods such as CORDIC algorithms to map the accelerator-incompatible operations to accelerator cores. According to the experimental results using HOG descriptor computation, the proposed task allocation method reduces the data transfer time by more than 82% and the total processing time by more than 79% compared to the conventional task allocation method.

著者

Shinyu NINOMIYA Masanori HASHIMOTO

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences (ISSN:09168508)

巻号頁・発行日

vol.E93-A, no.12, pp.2441-2446, 2010-12-01

---

Statistical timing analysis for manufacturing variability requires modeling of spatially-correlated variation. Common grid-based modeling for spatially-correlated variability involves a trade-off between accuracy and computational cost, especially for PCA (principal component analysis). This paper proposes to spatially interpolate variation coefficients for improving accuracy instead of fining spatial grids. Experimental results show that the spatial interpolation realizes a continuous expression of spatial correlation, and reduces the maximum error of timing estimates that originates from sparse spatial grids For attaining the same accuracy, the proposed interpolation reduced CPU time for PCA by 97.7% in a test case.

著者

KITAMOTO Takuya YAMAGUCHI Tetsu

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

IEICE transactions on fundamentals of electronics, communications and computer sciences (ISSN:09168508)

巻号頁・発行日

vol.91, no.8, pp.2101-2110, 2008-08-01

---

Let <i>M</i>(<i>y</i>) be a matrix whose entries are polynomial in <i>y</i>, λ(<i>y</i>) and υ(<i>y</i>) be a set of eigenvalue and eigenvector of <i>M</i>(<i>y</i>). Then, λ(<i>y</i>) and υ(<i>y</i>) are algebraic functions of <i>y</i>, and λ(<i>y</i>) and υ(<i>y</i>) have their power, series expansions<br>λ(<i>y</i>)=β₀+β₁<i>y</i>+…+β_<i>k</i><i>y</i>^<i>k</i>+…(β_<i>j</i>∈<b>C</b>), (1)<br>υ(<i>y</i>)=γ₀+γ₁<i>y</i>+…+γ_<i>k</i><i>y^k</i>+…(γ_<i>j</i>∈<b>C</b>^<i>n</i>), (2)<br>provided that <i>y</i>=0 is not a singular point of λ(<i>y</i>) or υ(<i>y</i>). Several algorithms are already proposed to compute the above power series expansions using Newton's method (the algorithm in [4]) or the Hensel construction (the algorithm in [5], [12]). The algorithms proposed so far compute high degree coefficients, β_<i>k</i> and γ_<i>k</i>, using lower degree coefficien β_<i>j</i> and γ_<i>j</i>(<i>j</i>=0,1,…,<i>k</i>-1). Thus with floating point arithmetic, the numerical errors in the coefficients can accumulate as index <i>k</i> increases. This can cause serious deterioration of the numerical accuracy of high degree coefficients β_<i>k</i> and γ_<i>k</i>, and we need to check the accuracy. In this paper, we assume that given matrix <i>M</i>(<i>y</i>) does not have multiple eigenvalues at <i>y</i>=0 (this implies that <i>y</i>=0 is not singular point of γ(<i>y</i>) or υ(<i>y</i>)), and presents an algorithm to estimate the accuracy of the computed power series β_<i>i</i>, γ_<i>j</i> in (1) and (2). The estimation process employs the idea in [9] which computes a coefficient of a power series with Cauchy's integral formula and numerical integrations. We present an efficient implementation of the algorithm that utilizes Newton's method. We also present a modification of Newton's method to speed up the procedure, introducing tuning parameter <i>p</i>. Numerical experiments of the paper indicates that we can enhance the performance of the algorithm by 12-16%, choosing the optimal tuning parameter <i>p</i>.

著者

Mun-Kyu LEE Jeong Eun SONG Dooho CHOI Dong-Guk HAN

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences (ISSN:09168508)

巻号頁・発行日

vol.E93-A, no.1, pp.153-163, 2010-01-01

被引用文献数

25

---

The NTRU cryptosystem is a public key system based on lattice problems. While its theoretical security has been well studied, little effort has been made to analyze its security against implementation attacks including power analysis attacks. In this paper, we show that a typical software implementation of NTRU is vulnerable to the simple power analysis and the correlation power analysis including a second-order power attack. We also present novel countermeasures to prevent these attacks, and perform experiments to estimate the performance overheads of our countermeasures. According to our experimental results, the overheads in required memory and execution time are only 8.17% and 9.56%, respectively, over a Tmote Sky equipped with an MSP430 processor.

著者

Shingo HASEGAWA Hiroyuki HATANAKA Shuji ISOBE Eisuke KOIZUMI Hiroki SHIZUYA

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences (ISSN:09168508)

巻号頁・発行日

vol.E91-A, no.1, pp.330-337, 2008-01-01

---

This paper studies a method for transforming ordinary cryptographic primitives to new harder primitives. Such a method is expected to lead to general schemes that make present cryptosystems secure against the attack of quantum computers. We propose a general technique to construct a new function from an ordinary primitive function f with a help of another hard function g so that the resulting function is to be new hard primitives. We call this technique a lifting of f by g. We show that the lifted function is harder than original functions under some simple conditions.

著者

Ryoichi TERAMURA Yasuo ASAKURA Toshihiro OHIGASHI Hidenori KUWAKADO Masakatu MORII

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences (ISSN:09168508)

巻号頁・発行日

vol.E93-A, no.1, pp.164-171, 2010-01-01

---

Conventional efficient key recovery attacks against Wired Equivalent Privacy (WEP) require specific initialization vectors or specific packets. Since it takes much time to collect the packets sufficiently, any active attack should be performed. An Intrusion Detection System (IDS), however, will be able to prevent the attack. Since the attack logs are stored at the servers, it is possible to prevent such an attack. This paper proposes an algorithm for recovering a 104-bit WEP key from any IP packets in a realistic environment. This attack needs about 36,500 packets with a success probability 0.5, and the complexity of our attack is equivalent to about 220 computations of the RC4 key setups. Since our attack is passive, it is difficult for both WEP users and administrators to detect our attack.

著者

MINOWA Tadashi OGIWARA Haruo

出版者

一般社団法人電子情報通信学会

雑誌

IEICE transactions on fundamentals of electronics, communications and computer sciences (ISSN:09168508)

巻号頁・発行日

vol.81, no.10, pp.2047-2054, 1998-10-25

被引用文献数

25

---

Soft-in/soft-out Viterbi algorithm (SOVA) originally proposed for rate 1/n code is applied to rate m/(m+1) trellis-coded modulation (TCM). In TCM, 2^m branches merge into a node in a code trellis. After pruning the branches on path with less path-metric until two best paths remain, SOVA is applied to the pruned trellis. Based on the pruned trellis, an iterative decoding algorithm of turbo TCM is developed. Effects of path memory length and scaling of a value transferred between decoding stages are investigated through simulation. Turbo TCM over 8 PSK and 16 QAM channel with Gaussian noise realize a bit error rate (BER) of 10^<-5> within 1dB from the Shannon limit.

著者

KURIBAYASHI Minoru TANAKA Hatsukazu

出版者

一般社団法人電子情報通信学会

雑誌

IEICE transactions on fundamentals of electronics, communications and computer sciences (ISSN:09168508)

巻号頁・発行日

vol.85, no.3, 2002-03-01

被引用文献数

1

---

Generally, a signal embedded in the low frequency domain is not affected seriously by attacks, but blocking effects which can be perceived easily may be occurred among adjoining blocks. In order to prevent the blocking effects, a watermark is embedded using the addition property among two-dimensional DCT basic matrices. For the addition property, a watermark is able to extracted not from the embedded block directly, but from the sub-block located in the central region of the block. Considering the distortions caused by the geometric transformations, we recover the synchronization loss before the extraction process. The robustness can also be improved by error-correction.

著者

LEHTOMAKI Janne SULIMAN Isameldin UMEBAYASHI Kenta SUZUKI Yasuo

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

IEICE transactions on fundamentals of electronics, communications and computer sciences (ISSN:09168508)

巻号頁・発行日

vol.92, no.5, pp.1356-1362, 2009-05-01

被引用文献数

5

---

In direct communication, terminals that are close to each other can communicate directly without traffic going through centralized controller such as a base station (BS). This brings several advantages. We study direct communication with localized distribution, so that users tend to gather around some areas (clusters/hot-spots) within the cell such as buildings. Previous analysis about clustering has focused on one dimensional scenarios. Here we present theoretical analysis of direct communication with two dimensional clustering. Additional analysis is presented for direct communication with correlated clusters. With correlated clusters some pairs of source and destination clusters are more probable than other pairs. According to our best knowledge, this is the first time that theoretical analysis is presented about clustering and correlated clusters in two dimensional scenarios. Simulations confirm the validity of the analysis. In addition to the exact results, we also suggest using the point-based approximation to rapidly and easily obtain results. The numerical results show that the gains from direct communication, in terms of blocking probability and carried traffic, depend on the offered traffic. Additionally, correlation in cluster selection is shown to significantly improve performance. Point-based approximation is shown to be very useful when the number of clusters is large.

著者

CHOI Wan KIM Jin Young

出版者

一般社団法人電子情報通信学会

雑誌

IEICE transactions on fundamentals of electronics, communications and computer sciences (ISSN:09168508)

巻号頁・発行日

vol.84, no.6, pp.1406-1412, 2001-06-01

被引用文献数

4

---

In future mobile communication systems, forward link may be a limiting one because emerging data services are likely to require higher data rates in the forward link than in the reverse link. In this paper, we derive joint Erlang capacity of a DS/CDMA forward link in terms of both outage probability and blocking probability for each type of traffic in a mixed traffic environment. Resource sharing algorithm and generalized Erlang model are employed to derive joint Erlang capacity of the DS/CDMA system with various types of traffics. The joint Erlang capacity reflecting both outage probability and blocking probability of each type of traffic is obtained by an approach based on virtual circuit switching perspective. We take into account effect of closed loop power control in the analysis. From numerical results, it is confirmed that blocking probability as a QoS(quality of service)parameter has a significant impact on the forward link capacity. The results of this paper can be applied to design of the DS/CDMA systems supporting wireless multimedia traffics.

著者

TAKITA Kenji MUQUIT Mohammad Abdul AOKI Takafumi HIGUCHI Tatsuo

出版者

一般社団法人電子情報通信学会

雑誌

IEICE transactions on fundamentals of electronics, communications and computer sciences (ISSN:09168508)

巻号頁・発行日

vol.87, no.8, pp.1913-1923, 2004-08-01

被引用文献数

80

---

This paper presents a technique for high-accuracy correspondence search between two images using Phase-Only Correlation (POC) and its performance evaluation in a 3D measurement application. The proposed technique employs (i) a coarse-to-fine strategy using image pyramids for correspondence search and (ii) a sub-pixel window alignment technique for finding a pair of corresponding points with sub-pixel displacement accuracy. Experimental evaluation shows that the proposed method makes possible to estimate the displacement between corresponding points with approximately 0.05-pixel accuracy when using 11 × 11-pixel matching windows. This paper also describes an application of the proposed technique to passive 3D measurement system.

著者

NAKANO Takumi KOMATSUDAIRA Yoshiki SHIOMI Akichika IMAI Masaharu

出版者

一般社団法人電子情報通信学会

雑誌

IEICE transactions on fundamentals of electronics, communications and computer sciences (ISSN:09168508)

巻号頁・発行日

vol.82, no.11, pp.2375-2382, 1999-11-25

被引用文献数

3

---

In a real-time system, it is required to reduce the response time to an interrupt signal, as well as the execution time of a Real-Time Operating System (RTOS). In order to satisfy this requirement, we have proposed a method of implementing some of the functionalities of an RTOS using hardware. Based on this idea, we have implemented a VLSI chip, called STRON (silicon TRON: The Realtime Operating system Nucleus), to enhance the performance of an RTOS, where the STRON chip works as a peripheral unit of any MPU. In this paper we describe the hardware architecture of the STRON chip and the performance evaluation results of the RTOS using the STRON chip. The following results were obtained. (1) The STRON chip is implemented in only about 10,000 gates when the number of each object (task, event flag, semaphore, and interrupt) is 7. (2) The task scheduler can execute within 8 clocks in a fixed period using the hardware algorithm when the number of tasks is 7. (3) Most of the basic μITRON system calls using the STRON chip can be executed in a fixed period of a few microseconds. (4) The execution time of a system call, measured by a multitask application program model, can be reduced to about one-fifth that in the case of the conventional software RTOS. (5) The total performance, including context switching, is about 2.2 times faster than that of the software RTOS. We conclude that the execution time of the part of the system call implemented by the STRON chip can almost be ignored, but the part of the interface software and context switching related to the architecture of a MPU strongly influence the total performance of an RTOS.

著者

IKEDA Yoshikazu TOKINAGA Shozo

出版者

一般社団法人電子情報通信学会

雑誌

IEICE transactions on fundamentals of electronics, communications and computer sciences (ISSN:09168508)

巻号頁・発行日

vol.83, no.8, pp.1599-1607, 2000-08-25

被引用文献数

42

---

This paper deals with the identification of system equation of the chaotic dynamics by using smaller number of data based upon the genetic programming (GP). The problem to estimate the system equation from the chaotic data is important to analyze the structure of dynamics in the fields such as the business and economics. Especially, for the prediction of chaotic dynamics, if the number of data is restricted, we can not use conventional numerical method such as the linear-reconstruction of affractors and the prediction by using the neural networks. In this paper we utilize an efficient method to identify the system equation by using the GP. In the GP, the performance (fitness) of each individual is defined as the inversion of the root mean square error of the spectrum obtained by the original and predicted time series to suppress the effect of the initial value of variables. Conventional GA (Genetic Algorithm) is combined to optimize the constants in equations and to select the primitives in the GP representation. By selecting a pair of individuals having higher fitness, the crossover operation is applied to generate new individuals. The crossover operation used here means the replacement of a part of tree in individual A by a part of tree in individual B. To avoid the meaningless genetic operation, the validity of prefix representation of the subtree to be embedded to the other tree is probed by using the stack count. These newly generated individuals replace old individuals with lower fitness. The mutation operation is also used to avoid the convergence to the local minimum. In the simulation study, the identification method is applied at first to the well known chaotic dynamics such as the Logistic map and the Henon map. Then, the method is applied to the identification of the chaotic data of various time series by using one dimensional and higher dimensional system. The result shows better prediction than conventional ones in cases where the number of data is small.

著者

Shunichi HAYASHI Mitsuru TADA

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences (ISSN:09168508)

巻号頁・発行日

vol.E91-A, no.5, pp.1253-1264, 2008-05-01

---

In [13], we proposed new decision problems related to lattices, and proved their NP-completeness. In this paper, we present a new public-key identification scheme and a digital signature scheme based on one of the problems in [13]. We also prove the security of our schemes under certain assumptions, and analyze the efficiency of ours.