Isamu TERANISHI Takuro OYAMA Wakaha OGATA
We say that a signature scheme is strongly existentially unforgeable (SEU) if no adversary, given message/signature pairs adaptively, can generate a signature on a new message or a new signature on a previously signed message. We propose a general and efficient conversion in the standard model that transforms a secure signature scheme to SEU signature scheme. In order to construct that conversion, we use a chameleon commitment scheme. Here a chameleon commitment scheme is a variant of commitment scheme such that one can change the committed value after publishing the commitment if one knows the secret key. We define the chosen message security notion for the chameleon commitment scheme, and show that the signature scheme transformed by our proposed conversion satisfies the SEU property if the chameleon commitment scheme is chosen message secure. By modifying the proposed conversion, we also give a general and efficient conversion in the random oracle model, that transforms a secure signature scheme into a SEU signature scheme. This second conversion also uses a chameleon commitment scheme but only requires the key only attack security for it.
Chen-Chien HSU Tsung-Chi LU Heng-Chou CHEN
In this paper, an evolutionary approach is proposed to obtain a discrete-time state-space interval model for uncertain continuous-time systems having interval uncertainties. Based on a worst-case analysis, the problem to derive the discrete interval model is first formulated as multiple mono-objective optimization problems for matrix-value functions associated with the discrete system matrices, and subsequently optimized via a proposed genetic algorithm (GA) to obtain the lower and upper bounds of the entries in the system matrices. To show the effectiveness of the proposed approach, roots clustering of the characteristic equation of the obtained discrete interval model is illustrated for comparison with those obtained via existing methods.
We propose an adaptive SLM scheme based on peak observation for PAPR reduction of OFDM signals. The proposed scheme is composed of three steps: peak scaling, sequence selection, and SLM procedures. In the first step, the peak signal samples in the IFFT outputs of the original input sequence are scaled down. In the second step, the sub-carrier positions where the power difference between the original input sequence and the FFT output of the scaled signal is large, are identified. Then, the phase sequences having the maximum number of phase-reversed sequence words only for these positions are selected. Finally, the generic SLM procedure is performed by using only the selected phase sequences for the original input sequence. Simulation results show that the proposed scheme significantly reduce the complexity in terms of IFFT and PAPR calculation than the conventional SLM, while maintaining the PAPR reduction performance.
Kunihiko MIYAZAKI Goichiro HANAOKA Hideki IMAI
A digital signature does not allow any alteration of the document to which it is attached. Appropriate alteration of some signed documents, however, should be allowed because there are security requirements other than the integrity of the document. In the disclosure of official information, for example, sensitive information such as personal information or national secrets is masked when an official document is sanitized so that its nonsensitive information can be disclosed when it is requested by a citizen. If this disclosure is done digitally by using the current digital signature schemes, the citizen cannot verify the disclosed information because it has been altered to prevent the leakage of sensitive information. The confidentiality of official information is thus incompatible with the integrity of that information, and this is called the digital document sanitizing problem. Conventional solutions such as content extraction signatures and digitally signed document sanitizing schemes with disclosure condition control can either let the sanitizer assign disclosure conditions or hide the number of sanitized portions. The digitally signed document sanitizing scheme we propose here is based on the aggregate signature derived from bilinear maps and can do both. Moreover, the proposed scheme can sanitize a signed document invisibly, that is, no one can distinguish whether the signed document has been sanitized or not.
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.
Junichi NAKAYAMA Yasuhiko TAMURA
This paper deals with the scattering of a transverse magnetic (TM) plane wave from a perfectly conductive sinusoidal surface with finite extent. By use of the undersampling approximation and a rectangular pulse approximation, an asymptotic formula for the total scattering cross section at a low grazing limit of incident angle is obtained explicitly under conditions such that the surface is small in roughness and slope, and the corrugation width is sufficiently large. The formula shows that the total scattering cross section is proportional to the square root of the corrugation width but does not depend on the surface period and surface roughness. When the corrugation width is not large, however, the scattered wave can be obtained by a single scattering approximation, which gives the total scattering cross section proportional to the corrugation width and the Rayleigh slope parameter. From the asymptotic formula and the single scattering solution, a transition point is defined explicitly. By comparison with numerical results, it is concluded that the asymptotic formula is fairly accurate when the corrugation width is much larger than the transition point.
Junyi WANG Yuyuan CHANG Chuyu ZHENG Kiyomichi ARAKI ZhongZhao ZHANG
The low complexity tree-structure based user scheduling algorithm is extended into up-link MLD-based multi-user multiple-input multiple-output (MIMO) orthogonal frequency division multiplexing access (OFDMA) wireless systems. The system sum capacity is maximized by careful user selection on a defined tree structure. The calculation load is reduced by selecting the M most possible best branches and sampling in frequency dimension. The performances of the proposed scheduling algorithm are analyzed within three kinds of OFDMA systems and compared with conventional throughput-based algorithm. Both the theoretical analysis and simulation results show that the proposed algorithm obtains better performance with much low complexity.
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.
Kazuhiro HATTORI Junichi NAKAYAMA Yasuhiko TAMURA
This paper deals with the scattering of a TM plane wave from a periodic grating with single defect, of which position is known. The surface is perfectly conductive and made up with a periodic array of rectangular grooves and a defect where a groove is not formed. The scattered wave above grooves is written as a variation from the diffracted wave for the perfectly periodic case. Then, an integral equation for the scattering amplitude is obtained, which is solved numerically by use of truncation and the iteration method. The differential scattering cross section and the optical theorem are calculated in terms of the scattering amplitude and are illustrated in figures. It is found that incoherent Wood's anomaly appears at critical angles of scattering. The physical mechanisms of Wood's anomaly and incoherent Wood's anomaly are discussed in relation to the guided surface wave excited by the incident plane wave. It is concluded that incoherent Wood's anomaly is caused by the diffraction of the guided surface wave.
Jun KURIHARA Shinsaku KIYOMOTO Kazuhide FUKUSHIMA Toshiaki TANAKA
In Shamir's (k,n)-threshold secret sharing scheme [1], a heavy computational cost is required to make n shares and recover the secret from k shares. As a solution to this problem, several fast threshold schemes have been proposed. However, there is no fast ideal (k,n)-threshold scheme, where k ≥ 3 and n is arbitrary. This paper proposes a new fast (3,n)-threshold scheme by using just EXCLUSIVE-OR(XOR) operations to make shares and recover the secret, which is an ideal secret sharing scheme similar to Shamir's scheme. Furthermore, we evaluate the efficiency of the scheme, and show that it is more efficient than Shamir's in terms of computational cost. Moreover, we suggest a fast (k,n)-threshold scheme can be constructed in a similar way by increasing the sets of random numbers constructing pieces of shares.
In this letter, we consider the uplink packet scheduling for non-real-time data users in a DS-CDMA system. As an effort to jointly optimize throughput and fairness, we formulate a time-span minimization problem incorporating the time-multiplexing of different simultaneous transmission schemes. Based on simple rules, we propose efficient scheduling algorithms and compare them with the optimal solution obtained by linear programming.
A rate control algorithm for logo insertion which does not require full decoding and encoding in compressed video is proposed. A perceptual approach is adopted in order to reduce the distortion introduced by the rate control. The start position of rate control is randomly varied for each frame so that the perceptual distortion is evenly dispersed across the whole picture. The number of rate-controlled slices is changed instead of the quantization scale in order to maintain original bit rate. Simulations show that the original bit rate can be maintained by the rate control without noticeable distortion. The proposed rate control algorithm can be easily extended to other transcoding applications.
Xuedan ZHANG Jun HONG Lin ZHANG Xiuming SHAN Victor O. K. LI
This paper addresses the issue of transmission scheduling in wireless ad hoc networks. We propose a Time Division Multiple Access (TDMA) scheduling scheme based on edge coloring and probabilistic assignment, called CP-TDMA. We categorize the conflicts suffered by wireless links into two types: explicit conflicts and implicit conflicts, and utilize two different strategies to deal with them. Explicit conflicts are avoided completely by a simple distributed edge-coloring algorithm µ-M, and implicit conflicts are minimized by applying probabilistic time slot assignments to links. We evaluate CP-TDMA analytically and numerically, and find that CP-TDMA, which requires only local information exhibits a better performance than previous work.
Kazuhide FUKUSHIMA Shinsaku KIYOMOTO Toshiaki TANAKA Kouichi SAKURAI
Program analysis techniques have improved steadily over the past several decades, and software obfuscation schemes have come to be used in many commercial programs. A software obfuscation scheme transforms an original program or a binary file into an obfuscated program that is more complicated and difficult to analyze, while preserving its functionality. However, the security of obfuscation schemes has not been properly evaluated. In this paper, we analyze obfuscation schemes in order to clarify the advantages of our scheme, the XOR-encoding scheme. First, we more clearly define five types of attack models that we defined previously, and define quantitative resistance to these attacks. Then, we compare the security, functionality and efficiency of three obfuscation schemes with encoding variables: (1) Sato et al.'s scheme with linear transformation, (2) our previous scheme with affine transformation, and (3) the XOR-encoding scheme. We show that the XOR-encoding scheme is superior with regard to the following two points: (1) the XOR-encoding scheme is more secure against a data-dependency attack and a brute force attack than our previous scheme, and is as secure against an information-collecting attack and an inverse transformation attack as our previous scheme, (2) the XOR-encoding scheme does not restrict the calculable ranges of programs and the loss of efficiency is less than in our previous scheme.
Kazuki IWAMOTO Tadashi DOHI Naoto KAIO
Software rejuvenation is a preventive and proactive solution that is particularly useful for counteracting the phenomenon of software aging. In this article, we consider periodic software rejuvenation models based on the expected cost per unit time in the steady state under discrete-time operation circumstance. By applying the discrete renewal reward processes, we describe the stochastic behavior of a telecommunication billing application with a degradation mode, and determine the optimal periodic software rejuvenation schedule minimizing the expected cost. Similar to the earlier work by the same authors, we develop a statistically non-parametric algorithm to estimate the optimal software rejuvenation schedule, by applying the discrete total time on test concept. Numerical examples are presented to estimate the optimal software rejuvenation schedules from the simulation data. We discuss the asymptotic behavior of estimators developed in this paper.
Toshihiro OHIGASHI Yoshiaki SHIRAISHI Masakatu MORII
In a key scheduling algorithm (KSA) of stream ciphers, a secret key is expanded into a large initial state. An internal state reconstruction method is known as a general attack against stream ciphers; it recovers the initial state from a given pair of plaintext and ciphertext more efficiently than exhaustive key search. If the method succeeds, then it is desirable that the inverse of KSA is infeasible in order to avoid the leakage of the secret key information. This paper shows that it is easy to compute a secret key from an initial state of RC4. We propose a method to recover an -bit secret key from only the first bits of the initial state of RC4 using linear equations with the time complexity less than that of one execution of KSA. It can recover the secret keys of which number is 2103.6 when the size of the secret key is 128 bits. That is, the 128-bit secret key can be recovered with a high probability when the first 128 bits of the initial state are determined using the internal state reconstruction method.
Kanshiro KASHIKI Mitsuo NOHARA Satoshi IMATA Yukiko KISHIKI
In a Cognitive Radio system, it is essential to recognize and avoid sources of interference signals. This paper describes a study on a location sensing scheme for interference signals, which utilizes multi-beam phased array antenna for cognitive wireless networks. This paper also elucidates its estimation accuracy of the interference location for the radio communication link using an OFDM signal such as WiMAX. Furthermore, we use the frequency spectrum of the received OFDM interference signal, to create a method that can estimate the propagation status. This spectrum can be monitored by using a software defined radio receiver.
Mohammad Shah ALAM Shamim Ara SHAWKAT Gontaro KITAZUMI Mitsuji MATSUMOTO
IrBurst, recently proposed by IrDA, is a high speed information transmission protocol. In this paper, a mathematical model is developed which leads to derivation of the IrBurst throughput over the IrDA protocol stack. Based on this model, we compare the performance of IrBurst and existing OBEX protocol in order to investigate the suitability of IrBurst protocol for exchange of large data blocks over high-speed IrDA links. Furthermore, the model allows the evaluation of the impact of the link layer parameters, such as window size and frame length, and physical layer parameters, such as minimum turnaround time, on system throughput for high-speed IrDA links and in the presence of transmission errors. Consequently, an effective Automatic Repeat Request (ARQ) scheme is proposed at link layer to maximize the throughput efficiency for IrBurst protocol as well as for next generation high speed IrDA links. Simulation result indicates that employment of our proposed ARQ scheme results in significant improvement of IrBurst throughput efficiency at high bit error rates.
An injection-locked clock recovery circuit (CRC) with quadrature outputs based on multiplexed oscillator is presented. The CRC can operate at a half-rate speed to provide an adequate locking range with reasonable jitter and power consumption because both clock edges sample the data waveforms. Implemented by 0.18-µm CMOS technique, experimental results demonstrate that it can achieve the phase noise of the recovered clock about -121.55 dBc/Hz at 100-kHz offset and -129.58 dBc/Hz at 1-MMz offset with 25 MHz lock range, while operating at the input data rate of 1.55 Gb/s.
Yoshio YAMAGUCHI Yukari YAMAMOTO Hiroyoshi YAMADA Jian YANG Wolfgang-Martin BOERNER
Classification of terrain is one of the most important applications of Polarimetric Synthetic Aperture Radar (POLSAR) image analysis. This paper presents a simple method to classify terrain by the use of the correlation coefficients in the circular polarization basis together with the total power of the scattering matrix in the X-band. The reflection symmetry condition that the co-polarized and the cross-polarized correlations are close to zero for natural distributed scatterers is utilized to extract characteristic parameters of small forests or cluster of trees, and oriented urban building blocks with respect to the direction of the radar illumination. Both of these kinds of scatterers are difficult to identify in high resolution POLSAR images of complex urban areas. The indices employed here are the correlation coefficient, a modified coefficient normalized by the reflection symmetric conditional case, and the total power. It is shown that forest areas and oriented building blocks are easily detected and identified. The terrain classification yielded by these combinations is very accurate as confirmed by photographic ground truth images.