Akito MONDEN Antoine MONSIFROT Clark THOMBORSON
Many computer systems are designed to make it easy for end-users to install and update software. An undesirable side effect, from the perspective of many software producers, is that hostile end-users may analyze or tamper with the software being installed or updated. This paper proposes a way to avoid the side effect without affecting the ease of installation and updating. We construct a computer system M with the following properties: 1) the end-user may install a program P in any conveniently accessible area of M; 2) the program P contains encoded instructions whose semantics are obscure and difficult to understand; and 3) an internal interpreter W, embedded in a non-accessible area of M, interprets the obfuscated instructions without revealing their semantics. Our W is a finite state machine (FSM) which gives context-dependent semantics and operand syntax to the encoded instructions in P; thus, attempts to statically analyze the relation between instructions and their semantics will not succeed. We present a systematic method for constructing a P whose instruction stream is always interpreted correctly regardless of its input, even though changes in input will (in general) affect the execution sequence of instructions in P. Our framework is easily applied to conventional computer systems by adding a FSM unit to a virtual machine or a reconfigurable processor.
We show that a problem of deciding whether a formula for a multivariate polynomial of n variables over a finite field of characteristic 2 has degree n when reduced modulo a certain Boolean ideal belongs to P. When the formula is allowed to have succinct representations as sums of monomials, the problem becomes P-complete.
Chisato KONOMA Masahiro MAMBO Hiroki SHIZUYA
To the authors' knowledge, there are not many cryptosystems proven to be as difficult as or more difficult than the discrete logarithm problem. Concerning problems related to the discrete logarithm problem, there are problems called the double discrete logarithm problem and the e-th root of the discrete logarithm problem. These two problems are likely to be difficult and they have been utilized in cryptographic protocols such as verifiable secret sharing scheme and group signature scheme. However, their exact complexity has not been clarified, yet. Related to the e-th root of the discrete logarithm problem, we can consider a square root of the discrete logarithm problem. Again, the exact complexity of this problem has not been clarified, yet. The security of cryptosystems using these underlying problems deeply depends on the difficulty of these underlying problems. Hence it is important to clarify their difficulty. In this paper we prove reductions among these fundamental problems and show that under certain conditions, these problems are as difficult as or more difficult than the discrete logarithm problem modulo a prime.
This letter proposes an efficient and simple stopping criterion for turbo decoding, which is derived by observing the behavior of log-likelihood ratio (LLR) values. Based on the behavior, the proposed criterion counts the number of absolute LLR values less than a threshold and the number of hard decision 1's in order to complete the iterative decoding procedure. Simulation results show that the proposed approach achieves a reduced number of iterations while maintaining similar BER/FER performance to the previous criteria.
Akira MURAYA Tadashi MATSUMOTO Seiichiro MORO Haruo HASEGAWA
For fixed initial and destination states (i.e., markings), M0 and Md, there exist generally infinite firing count vectors in a Petri net. In this letter, it is shown that all fundamental particular solutions as well as all minimal T-invariants w.r.t. firing count vectors are needed to express an arbitrary firing count vector for the fixed M0 and Md. An algorithm for finding a special firing count vector which is expressed by using the only one specified fundamental particular solution is also given.
This paper presents a computer-aided design procedure of simulated annealing algorithm to optimize dual-wideband microstrip line filters with symmetrical at least 500 MHz bandwidths respectively. This method demonstrates the superiority of designing microstrip line dual-band filters. The value of characteristic impedances and electrical lengths of transmission lines synthesizing 2.4 GHz and 5.2 GHz dualband filters with a single input and a single output are adjusted to the annealing process by the optimization algorithm. The fabricated dual-wideband spectral transmittance and reflectance curves of these filters applying this method all effectively achieved desired high performances and resulted in a lower cost dual-band filters and open the way to commercial mass production. The method is applicable not only in 2.4 GHz and 5.2 GHz, but can be applied to any other multi-frequency bands.
Yuki KATO Hiroyuki SEKI Tadao KASAMI
Several grammars have been proposed for representing RNA secondary structure including pseudoknots such as simple linear tree adjoining grammar (sl-tag), extended sl-tag (esl-tag) and RNA pseudoknot grammar (rpg). The main purpose of this paper is to compare the generative power of these grammars by identifying them as subclasses of multiple context-free grammars (mcfg). Specifically, it is shown that the class of languages generated by esl-tag (ESL-TAL) properly includes the class of languages generated by sl-tag (SL-TAL) and the class of languages generated by cfg. Also, we show that the class of languages generated by rpg coincides with the class of languages generated by mcfg with dimension one or two and rank one or two. Furthermore, it is shown that SL-TAL is a full trio and ESL-TAL is a substitution closed full AFL.
Shinji WATANABE Yasuhiro MINAMI Atsushi NAKAMURA Naonori UEDA
A Shared-State Hidden Markov Model (SS-HMM) has been widely used as an acoustic model in speech recognition. In this paper, we propose a method for constructing SS-HMMs within a practical Bayesian framework. Our method derives the Bayesian model selection criterion for the SS-HMM based on the variational Bayesian approach. The appropriate phonetic decision tree structure of the SS-HMM is found by using the Bayesian criterion. Unlike the conventional asymptotic criteria, this criterion is applicable even in the case of an insufficient amount of training data. The experimental results on isolated word recognition demonstrate that the proposed method does not require the tuning parameter that must be tuned according to the amount of training data, and is useful for selecting the appropriate SS-HMM structure for practical use.
Satoshi INOUE Katsushi INOUE Akira ITO Yue WANG
For each positive integer r 1, a nondeterministic machine M is r path-bounded if for any input word x, there are r computation paths of M on x. This paper investigates the accepting powers of path-bounded one-way (simple) multihead nondeterministic finite automata. It is shown that for each k 2 and r 1, there is a language accepted by an (r + 1) path-bounded one-way nondeterministic k head finite automaton, but not accepted by any r path-bounded one-way nondeterministic k head finite automaton whether or not simple.
In this letter, a method to construct good binary and quaternary error correcting codes, called complex Hadamard codes, based on a complex Hadamard matrix is presented. The related properties of the codes are analyzed. In addition, through the operation in Z4 domain, a new simplex soft-decision decoding algorithm for the complex Hadamard codes is also proposed.
Katsunari YOSHIOKA Junji SHIKATA Tsutomu MATSUMOTO
Fingerprinting is a technique to add identifying marks to each copy of digital contents in order to enhance traceability to a distribution system. Collusion attacks, in which the attackers collect two or more fingerprinted copies and try to generate an untraceable copy, are considered to be a threat for the fingerprinting system. With the aim of enhancing collusion security to the fingerprinting system, several collusion secure codes, such as c-frameproof code, c-secure frameproof code and c-identifiable parent property code, have been proposed. Here, c indicates the maximum number of colluding users. However, a practical construction of the above codes is still an issue because of the tight restrictions originated from their combinatorial properties. In this paper, we introduce an evaluation of frameproof, secure frameproof, and identifiable parent property by the probability that a code has the required property. Then, we focus on random codes. For frameproof and secure frameproof properties, we estimate the average probability that random codes have the required property where the probability is taken over the random construction of codes and random construction of coalitions. For the estimation, we assume the uniform distribution of symbols of random codes and the symbols that the coalitions hold. Therefore, we clarify the adequacy of the assumptions by comparison with numerical results. The estimates and numerical results resemble, which implies the adequacy of the assumption at least in the range of the experiment.
Naobumi MICHISHITA Hiroyuki ARAI Yasuko KIMURA
This paper describes the choke-loaded patch array antenna for use in the IMT-2000 repeater systems. The choke structure of the 4-element array is designed by means of an electromagnetic analysis. A high front-to-back (FB) ratio is required for suppressing mutual coupling in order to stop the oscillation caused by the interference waves between a transmitting and receiving antenna. The suppression of the FB ratio by a choke is limited in the case of the 16-element array because its side lobe level is large. In this paper, we examine the effect of suppressing the mutual coupling using a binomial array.
Chung-Ming WANG Peng-Cheng WANG
We present a novel scheme for digital steganography of point-sampled geometry in the spatial domain. Our algorithm is inspired by the concepts proposed by Cayre and Macq for 3D polygonal models. It employs a principal component analysis (PCA), resulting in a blind approach. We validate our scheme with various model complexities in terms of capacity, complexity, visibility, and security. This scheme is robust against translation, rotation, and scaling operations. It is fast and can achieve high data capacity with insignificant visual distortion in the stego models.
Futoshi KUROKI Kouichi YAMAOKA Motofumi YAMAGUCHI Tsukasa YONEYAMA
It is known that a high permittivity NRD guide suffers from irregular transmission phenomena. In this study, we clarified that this problem is caused by a mode coupling phenomenon between the operating and parasitic modes due to a small remaining asymmetrically air gap between the metal plates and high permittivity dielectric materials.
This paper deals with broadcast encryption schemes, in which a sender can send information securely to a group of receivers excluding some receivers over a broadcast channel. In this paper we propose modifications of the Complete Subtree (CS), the Subset Difference (SD) and the Layered Subset Difference (LSD) methods based on the Master Key Tree (MKT). Our modifications eliminate log N keys or labels from receivers' storage, in exchange for an increase in the computational overhead, where N is the total number of receivers. We also propose modifications of the SD and LSD methods by applying the Trapdoor One-way Permutation Tree (TOPT) which is originally proposed in order to modify the CS method. Our modifications based on TOPT also eliminate log N labels, and the computational cost is much smaller than MKT based methods.
Yasuhiro OHTAKI Masaru KAMADA Kaoru KUROSAWA
To investigate cyber-criminals, Police sometimes asks Administrator of a computer system to disclose the whole transaction log. Administrator, however, wants to protect the privacy of innocent users. This paper presents a solution for the disclosure/privacy problem of transaction log. In this scheme, Police can search over the encrypted records of the transaction log by keywords. The administrator discloses only the records which include the keyword, but nothing more. Police can verify that the administrator faithfully disclosed all the records which include the keyword.
In this paper, we propose an efficient protocol for proving the correctness of shuffling and an efficient protocol for simultaneously proving the correctness of both shuffling and decryption. The former protocol is the most efficient in computational and communication complexity among 3-move honest verifier perfect zero-knowledge protocols for proving a shuffling of ElGamal cipher-texts. The latter protocol is the most efficient in computational, communication, and round complexity, as a whole, in proving the correctness of both shuffling and decryption of ElGamal cipher-texts. The proposed protocols will be a building block of an efficient, universally verifiable mix-net, whose application to voting systems is prominent.
Extensive studies have been made of the public key cryptosystems based on multivariate polynomials over F2. However most of the proposed public key cryptosystems based on multivariate polynomials, are proved not secure. In this paper, we propose several types of new constructions of public key cryptosystems based on randomly generated singular simultaneous equations. One of the features of the proposed cryptosystems is that the sets of random singular simultaneous equations significantly enlarges the size of the transformation.
Ruey-Shun CHEN Duen-Kai CHEN Szu-Yin LIN
The traffic congestion problem in urban areas is worsening since traditional traffic signal control systems cannot provide] efficient traffic regulation. Therefore, dynamic traffic signal control in Intelligent Transportation System (ITS) recently has received increasing attention. This study devised a multi-agent architecture, the Adaptive and Cooperative Traffic light Agent Model (ACTAM), for a decentralized traffic signal control system. The proposed architecture comprises a data storage and communication layer, a traffic regulation factor processing layer, and a decision-making layer. This study focused on utilizing the cooperation of multi-agents and the prediction mechanism of our architecture, the Forecast Module, to forecast future traffic volume in each individual intersection. The Forecast Module is designed to forecast traffic volume in an intersection via multi-agent cooperation by exchanging traffic volume information for adjacent intersections, since vehicles passing through nearby intersections were believed to significantly influence the traffic volume of specific intersections. The proposed architecture can achieve dynamic traffic signal control. Thus, total delay time of the traffic network under ACTAM can be reduced by 37% compared to the conventional fixed sequence traffic signal control strategy. Consequently, traffic congestion in urban areas can be alleviated by adopting ACTAM.
Satoshi SUYAMA Hiroshi SUZUKI Kazuhiko FUKAWA
When the multipath delay difference exceeds the guard interval (GI), the performance of MIMO-OFDM transmission suffers severely from both the inter-symbol interference (ISI) from the adjacent OFDM symbols and the inter-carrier interference (ICI) within the same symbol. This paper therefore proposes a MIMO-OFDM receiver employing the low-complexity turbo equalization. The proposed receiver initially separates the data streams and suppresses ICI by linear processing. In the iterative processing, it cancels the other data streams as well as ISI and ICI. The MIMO-OFDM turbo equalizer consists of an ISI canceller, an ICI canceller, an optimal detection filter, and a MAP detector. The proposed receiver can improve the transmission performance by exploiting the log-likelihood ratio that the decoding process produces for canceling both ISI and ICI and separating of the spatially multiplexed streams. Computer simulations, which apply the wireless LAN to MIMO, demonstrate that the proposed receiver can provide excellent performance in the severe multipath channels where the delay difference is greater than GI.