InKoo KANG Kishore SINHA Heung-Kyu LEE
Combinatorial designs have been used to construct digital fingerprint codes. Here, a new constructive algorithm for an anticollusion fingerprint code based on group-divisible designs is presented. These codes are easy to construct and available for a large number of individuals, which is important from a business point of view. Group-divisible designs have not been used previously as a tool for fingerprint code construction.
Yusuke AYATO Akiko TAKATSU Kenji KATO Naoki MATSUDA
In situ observations were mainly performed by using slab optical waveguide (SOWG) spectroscopy synchronized with potential step measurements to investigate the time dependent spectral change of the adsorbed heptyl viologen cation radicals (HV+
This paper proposes a compact interpolation scheme dedicated to a 1-dimensional position sensitive detector (PSD) with an optical sensing pixel array. The pixels are divided into even- and odd-numbered groups and winner take all (WTA) circuits are provided to each of the groups. The simulated results show that the detecting step-width is reduced to the half of the original one after applying the interpolation scheme.
The concept of LR(k) validity is represented as an abstract interpretation of a refinement of the derivation semantics of a given grammar. Also the algorithm of LR(k) parsing is represented as an abstract interpretation of the refined semantics. Such representations of LR formalisms provide us with more intuitive and easier means by which to understand LR parsing.
Since the control input of a feedback linearizable system depends on the diffeomorphism, the transient behavior of the controlled system is different. In this paper, we propose a switching rule for selecting a diffeomorphism so that the transient behavior is improved and the switched system is stable. Specifically, we show the sufficient condition for the exponential stability and the exponential upper bound of the trajectory of the switched system.
In this paper, the interpolation line search (ILS) algorithm to find the desirable step length in a numerical optimization method is investigated to determine the optimal saturation limits with non-smooth nonlinearities. The simple steepest descent algorithm is used to illustrate that the ILS algorithm can provide adequate reductions in an objective function at minimal cost with fast convergence. The power system stabilizer (PSS) with output limits is used as an example for a nonlinear controller to be tuned. The efficient computation to implement the ILS algorithm in the steepest descent method is available by using the hybrid system model with the differential-algebraic-impulsive-switched (DAIS) structure. The simulation results are given to show the performance improved by the ILS algorithm.
Hans Georg SCHAATHUN Marcel FERNANDEZ
Collusion-secure codes are used for digital fingerprinting and for traitor tracing. In both cases, the goal is to prevent unauthorized copying of copyrighted material, by tracing at least one guilty user when illegal copies appear. The most well-known collusion-secure code is due to Boneh and Shaw (1995/98). In this paper we improve the decoding algorithm by using soft output from the inner decoder, and we show that this permits using significantly shorter codewords.
Takafumi KANAZAWA Toshimitsu USHIO
If some differences of perceptions arise between populations, then strategies which are regarded as the same strategy in a population may be perceived distinguishably in the other populations. To discuss such a situation, replicator dynamics for multi-population hypergames has been proposed. However, it is assumed that players' perceptions are given and fixed. In this paper, we consider that each population has various interpretation functions and choose one of them depending on payoffs, and we propose a hybrid system representation of replicator dynamics with changes of interpretation functions. Moreover, we apply our proposed model to a well-known example of a hypergame "Soccer Hooliganism" and show that behaviors converging to heteroclinic orbits can appear by the changes of the interpretation functions.
Urara SHINMYO Minoru KURIBAYASHI Masakatu MORII Hatsukazu TANAKA
For the construction of a large fingerprinting system, conventional protocols need many computations to provide each fingerprinted contents to each user. In order to reduce the computational cost, we introduce a new concept of distributed providers in the fingerprinting protocol. Before a sale, our practical fingerprinting protocol using a concept of secure oblivious transfer is performed between a contents supplier and each provider. Then each provider obtains fingerprinted contents such that each bit of fingerprinting information is embedded in each segment of the contents. When a user orders some contents to the supplier, each segment of the contents is distributed from each provider specified by the supplier. The selection of providers who distribute the segments of contents is executed based on the user's identity so that the sequence of embedded bits in the collected segments may indicate the user's identity.
This study presents an N-gram adaptation technique when additional text data for the adaptation do not exist. We use a language modeling approach to the information retrieval (IR) technique to collect the appropriate adaptation corpus from baseline text data. We propose to use a dynamic interpolation coefficient to merge the N-gram, where the interpolation coefficient is estimated from the word hypotheses obtained by segmenting the input speech. Experimental results show that the proposed adapted N-gram always has better performance than the background N-gram.
Large-throughput anomaly prevention mechanism in the upstream side of high-speed (over 10-Gbps) networks is required to prevent various anomalies such as distributed denial of service (DDoS) from causing various network problems. This mechanism requests the processors achieving not only high-speed response for analyzing many packets in a short time but also the flexibility to update the anomaly prevention algorithm. In this research, I assumed a dynamic reconfigurable processor (DRP) was most effective in achieving this anomaly prevention mechanism, for processors used in nodes with the mechanism, and I designed an anomaly prevention mechanism using DRPs. The mechanism can shorten anomaly prevention time in high-speed (10 Gbps) lines using an all-packet analysis. Through a simulation, I achieved the goal of the mechanism achieving a throughput of 83-M packets per second using three DRPs (432 execution elements used). Moreover, with the prototype, it was confirmed that the proposed mechanism prevented anomalies in a short time (constant 0.01 second), which was 3000 times faster than that of a legacy mechanism using a packet sampling method. I also proposed integrated prevention, which was able to reduce the number of execution elements comprising anomaly prevention algorithm against various kinds of anomalies. It was achieved with a simulation that the proposed integrated prevention against three kinds of anomalies (DDoS, worm, and peer to peer (P2P)) reduced the number of execution elements by 24% compared to legacy prevention. In addition, non-stop update was proposed to maintain throughput when updating an anomaly prevention algorithm without packet loss. It was confirmed with a simulation that there was enough time for non-stop update in 10 Gbps 4 lines.
Mamoru OHARA Ryo SUZUKI Masayuki ARAI Satoshi FUKUMOTO Kazuhiko IWASAKI
This paper discusses distributed checkpointing with logging for practical applications running with limited resources. We present a discrete time model evaluating the total expected overhead per event where the number of available checkpoints that each process can hold is finite. The rollback distance is also bound to some finite interval in many actual applications. Therefore, the recovery overhead for the checkpointing scheme is described by using a truncated geometric distribution as the rollback distance distribution. Although it is difficult to analytically derive the optimal checkpoint interval, which minimizes the total expected overhead, substituting other simple probabilistic distributions instead of the truncated geometric distribution enables us to do this explicitly. Numerical examples obtained through simulations are presented to show that we can achieve almost minimized total overhead by using the new models and analyses.
Nonlinear modeling of complex irregular systems constitutes the essential part of many control and decision-making systems and fuzzy logic is one of the most effective algorithms to build such a nonlinear model. In this paper, a new approach to fuzzy modeling is proposed. The model considered herein is the well-known Sugeno-type fuzzy system. The fuzzy modeling algorithm suggested in this paper is composed of two phases: coarse tuning and fine tuning. In the first phase (coarse tuning), a successive clustering algorithm with the fuzzy validity measure (SCFVM) is proposed to find the number of the fuzzy rules and an initial fuzzy model. In the second phase (fine tuning), a moving genetic algorithm with partial encoding (MGAPE) is developed and used for optimized tuning of membership functions of the fuzzy model. Two computer simulation examples are provided to evaluate the performance of the proposed modeling approach and compare it with other modeling approaches.
Shin-ichi NAKAYAMA Shigeru MASUYAMA
The minimum vertex ranking spanning tree problem is to find a spanning tree of G whose vertex ranking is minimum. This problem is NP-hard and no polynomial time algorithm for solving it is known for non-trivial classes of graphs other than the class of interval graphs. This paper proposes a polynomial time algorithm for solving the minimum vertex ranking spanning tree problem on outerplanar graphs.
It is known that any chordal graph can be uniquely decomposed into simplicial components. Based on this fact, it is shown that for a given chordal graph, its automorphism group can be computed in O((c!n)O(1)) time, where c denotes the maximum size of simplicial components and n denotes the number of nodes. It is also shown that isomorphism of those chordal graphs can be decided within the same time bound. From the viewpoint of polynomial-time computability, our result strictly strengthens the previous ones respecting the clique number.
Hideyo MAMIYA Atsuko MIYAJI Hiroaki MORIMOTO
In the execution on a smart card, side channel attacks such as the simple power analysis (SPA) and the differential power analysis (DPA) have become serious threat. Side channel attacks monitor the side channel information such as power consumption and even exploit the leakage information related to power consumption to reveal bits of a secret key d although d is hidden inside a smart card. Almost public key cryptosystems including RSA, DLP-based cryptosystems, and elliptic curve cryptosystems execute an exponentiation algorithm with a secret-key exponent, and they thus suffer from both SPA and DPA. In the case of elliptic curve cryptosystems, DPA is improved to the refined power analysis (RPA), which exploits a special point with a zero value and reveals a secret key. RPA is further generalized to zero-value register attack (ZRA). Both RPA and ZRA utilize a special feature of elliptic curves that happens to have a special point or a register used in addition and doubling formulae with a zero value and that the power consumption of 0 is distinguishable from that of a non-zero element. To make the matters worse, some previous efficient countermeasures to DPA are neither resistant to RPA nor ZRA. This paper focuses on elegant countermeasures of elliptic curve exponentiations against RPA, ZRA, DPA and SPA. Our novel countermeasure is easily generalized to be more efficient algorithm with a pre-computed table.
Mansoo PARK Hoi-Rin KIM Yong Man RO Munchurl KIM
The noise robustness of an audio fingerprinting system is one of the most important issues in music information retrieval by the content-based audio identification technique. In a real environment, sound recordings are commonly distorted by channel and background noise. Recently, Philips published a robust and efficient audio fingerprinting system for audio identification. To extract a robust and efficient audio fingerprint, Philips applied the first derivative (differential) to the frequency-time sequence of the perceptual filter-bank energies. In practice, however, the noise robustness of Philips' audio fingerprinting scheme is still insufficient. In this paper, we introduce an extension method of the audio fingerprinting scheme for the enhancement of noise robustness. As an alternative to frequency filtering, a type of band-pass filter, instead of a high-pass filter, is used to achieve robustness to background noise in a real situation. Our experimental results show that the proposed filter improves the noise robustness in audio identification.
Yunho LEE Seungjoo KIM Dongho WON
In 2005, Yong and Lee proposed a buyer-seller fingerprinting protocol using symmetric and commutative encryptions. They claimed that their protocol was practical and anonymous since they used symmetric and commutative encryptions. However, an attacker can get the content embedded with one or more honest buyers' fingerprints using man-in-the-middle attack. In this letter, we point out the weakness and propose methods for improving to their protocol.
Hideki ONO Satoshi TANIGUCHI Toshi-kazu SUZUKI
We have fabricated and investigated InGaAs Esaki tunnel diodes, grown on GaAs or InP substrates, of varied defect densities. The tunnel diodes exhibit the same I-V characteristics in spite of the variation of defect density. Under the simple thermal annealing and forward current stress tests, the change in the valley current was not observed, indicating that defects were not increased. On the other hand, the reduction in the peak current due to the carbon diffusion was observed under both tests. The diffusion was enhanced by the stress current owing to the energy dissipation associated with the nonradiative electron-hole recombination. From the reduction rates of the peak current, we obtained the thermal and current-enhanced carbon diffusion constants in InGaAs, which are independent of defect density. Although thermal diffusion of carbon in InGaAs is comparable with that in GaAs, the current-induced enhancement of diffusion in InGaAs is extremely weaker than that in GaAs. The difference between activation energy of thermal and current-enhanced diffusion is 0.8 eV, which is independent of stress current density and close to InGaAs bandgap energy. This indicates that the current-enhanced diffusion is dominated by the energy dissipation associated with nonradiative band-to-band recombination. This enhancement mechanism well explains that the current-induced enhancement is independent of defect density and extremely weak. We also have found that the current-enhanced diffusion constant is approximately proportional to the square of current density, suggesting that the recombination in the depletion layer dominates the current-enhanced diffusion.
Hiroaki TAKAI Takashi KANATANI Akira MATSUBAYASHI
The path coloring problem is to assign the minimum number of colors to a given set P of directed paths on a given symmetric digraph D so that no two paths sharing an arc have the same color. The problem has applications to efficient assignment of wavelengths to communications on WDM optical networks. In this paper, we show that the path coloring problem is NP-hard even if the underlying graph of D is restricted to a binary caterpillar. Moreover, we give a polynomial time algorithm which constructs, given a binary caterpillar G and a set P of directed paths on the symmetric digraph associated with G, a path coloring of P with at most colors, where L is the maximum number of paths sharing an edge. Furthermore, we show that no local greedy path coloring algorithm on caterpillars in general uses less than colors.