Canetti et al. [5] showed that there exist signature and encryption schemes that are secure in the random oracle (RO) model, but for which any implementation of the RO (by a single function or a function ensemble) results in insecure schemes. Their result greatly motivates the design of cryptographic schemes that are secure in the standard computational model. This paper gives some new results on the RO methodology. First, we give the necessary and sufficient condition for the existence of a signature scheme that is secure in the RO model but where, for any implementation of the RO, the resulting scheme is insecure. Next, we show that this condition induces a signature scheme that is insecure in the RO model, but that there is an implementation of the RO that makes the scheme secure.

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.

A concurrent model of computation and a language based on the model for bit-level operation are useful for developing asynchronous and concurrent programs compositionally, which frequently use bit-level operations. Some examples are programs for video games, hardware emulation (including virtual machines), and signal processing. However, few models and languages are optimized and oriented to bit-level concurrent computation. We previously developed a visual programming language called A-BITS for bit-level concurrent programming. The language is based on a dataflow-like model that computes using processes that provide serial bit-level operations and FIFO buffers connected to them. It can express bit-level computation naturally and develop compositionally. We then devised a concurrent computation model called APEC (Asynchronous Program Elements Connection) for bit-level concurrent computation. This model enables precise and formal expression of the process of computation, and a notion of primitive program elements for controlling and operating can be expressed synthetically. Specifically, the model is based on a notion of uniform primitive processes, called primitives, that have three terminals and four ordered rules at most, as well as on bidirectional communication using vehicles called carriers. A new notion is that a carrier moving between two terminals can briefly express some kinds of computation such as synchronization and bidirectional communication. The model's properties make it most applicable to bit-level computation compositionally, since the uniform computation elements are enough to develop components that have practical functionality. Through future application of the model, our research may enable further research on a base model of fine-grain parallel computer architecture, since the model is suitable for expressing massive concurrency by a network of primitives.

Chip-level substrate coupling analysis uses F-matrix computation with slice-and-stack execution to include highly concentrated substrate resistivity gradient. The technique that has been applied to evaluation of device-level isolation structures against substrate coupling is now developed into chip-level substrate noise analysis. A time-series divided parasitic capacitance (TSDPC) model is equivalent to a transition controllable noise source (TCNS) circuit that captures noise generation in a CMOS digital circuit. A reference structure incorporating TCNS circuits and an array of on-chip high precision substrate noise monitors provides a basis for the verification of chip-level analysis of substrate coupling in a given technology. Test chips fabricated in two different wafer processings of 0.30-µm and 0.18-µm CMOS technologies demonstrate the universal availability of the proposed analysis techniques. Substrate noise simulation achieves no more than 3 dB discrepancy in peak amplitude compared to measurements with 100-ps/100-µV resolution, enabling precise evaluation of the impacts of the distant placements of sensitive devices from sources of noise as well as application of guard ring/band structures.

In the Next-Generation Network (NGN), accommodating a wide variety of customer networks through virtual private network (VPN) technologies is one of the key issues. In particular, a core network provider has to provide bandwidth-assured and secured data transmission for individual private networks while performing optimal and flexible path selection. We present hierarchically distributed path computation elements (HDPCEs) that enable a virtual private network (VPN) provider to guarantee end-to-end required bandwidth and to maintain the secrecy of the link-state information of each customer from other customers. In previous studies, a VPN provider only considered link states in the provider network and did not consider customer domains connected by the provider network. HDPCEs, which are distributed to customer domains, communicate with an HDPCE for the provider network, and these HDPCEs enable the guarantee of necessary bandwidth for a data transmission from one customer domain to another via a provider network. We propose a new path-selection algorithm in each HDPCE and cooperation scheme to interwork HDPCEs, which are suitable for VPN requirements. In the evaluation, the superiority of HDPCE-based VPN path selection over legacy OSPF-TE-based VPN path selection is demonstrated in two typical VPN models: the dedicated model and shared model.

In this paper, we extend our framework of speculative computation in multi-agent systems by introducing default constraints. In research on multi-agent systems, handling incomplete information due to communication failure or due to other agents' delay in communication is a very important issue. For a solution to this problem, we previously proposed speculative computation based on abduction in the context of master-slave multi-agent systems and gave a procedure in abductive logic programming. In our previous proposal, a master agent prepares a default value for a yes/no question in advance, and it performs speculative computation using the default without waiting for a reply to the question. This computation is effective unless the contradictory reply to the default is returned. In this paper, we formalize speculative constraint processing, and propose a correct operational model for such computation so that we can handle not only yes/no questions, but also more general types of questions.

In this paper, we propose one low-computation cycle and power-efficient recursive discrete Fourier transform (DFT)/inverse DFT (IDFT) architecture adopting a hybrid of input strength reduction, the Chebyshev polynomial, and register-splitting schemes. Comparing with the existing recursive DFT/IDFT architectures, the proposed recursive architecture achieves a reduction in computation-cycle by half. Appling this novel low-computation cycle architecture, we could double the throughput rate and the channel density without increasing the operating frequency for the dual tone multi-frequency (DTMF) detector in the high channel density voice over packet (VoP) application. From the chip implementation results, the proposed architecture is capable of processing over 128 channels and each channel consumes 9.77 µW under 1.2 V@20 MHz in TSMC 0.13 1P8M CMOS process. The proposed VLSI implementation shows the power-efficient advantage by the low-computation cycle architecture.

In this paper, we propose a low complexity realization method for compensating for nonlinear distortion. Generally, nonlinear distortion is compensated for by a linearization system using a Volterra kernel. However, this method has a problem of requiring a huge computational complexity for the convolution needed between an input signal and the 2nd-order Volterra kernel. The Simplified Volterra Filter (SVF), which removes the lines along the main diagonal of the 2nd-order Volterra kernel, has been previously proposed as a way to reduce the computational complexity while maintaining the compensation performance for the nonlinear distortion. However, this method cannot greatly reduce the computational complexity. Hence, we propose a subband linearization system which consists of a subband parallel cascade realization method for the 2nd-order Volterra kernel and subband linear inverse filter. Experimental results show that this proposed linearization system can produce the same compensation ability as the conventional method while reducing the computational complexity.

The key weakness of Low-Density Parity Check codes is the complexity of the encoding scheme. The generator matrices can be made by Gaussian elimination of parity check matrices for normal block codes. Richardson succeeded in making parity bits from parity check matrices by the low density computation. In this letter, we focus on the execution of numerical experiments which show that even if the matrix D, which is the part of the Richardson's LDPC matrix, is restricted, proposed LDPC codes is lower complexity than Richardson's LDPC codes. The constraint of D results in reducing complexity from O(n + g2) to O(n) due to the omission of computing inverse matrices of φ and T in Richardson's encoding scheme. All the sub-matrices in parity check matrix are composed of Circulant Permutation Matrices based on Galois Fields.

This paper considers optical transport and packet networks and discusses the constraints and solutions in computation of traffic engineering paths. We categorize the constraints into prunable or non-prunable classes. The former involves a simple metric which can be applied for filtering to determine the path. The latter requires a methodic consideration of more complicated network element attributes. An example of this type of constraints is path loss in which the metric can be evaluated only on a path basis, as opposed to simply applying the metric to the link. Another form of non-prunable constraint requires adaptation and common vector operation. Examples are the switching type adaptation and wavelength continuity, respectively. We provide possible solutions to cases with different classes of constraints and address the problem of path computation in support of traffic engineering in multi-layer networks where a set of constrains are concurrently present. The solutions include the application of channel graph and common vector to support switching type adaptation and label continuity, respectively.

Implementing the fast-responding multi-layer service network (MLSN) functionality will allow the IP/MPLS service network logical topology and Optical Virtual Network topology to be reconfigured dynamically according to the traffic pattern on the network. Direct links can be created or removed in the logical IP/MPLS service network topology, when either extra capacity in MLSN core is needed or existing capacity in core is no longer required. Reconfiguring the logical and virtual network topologies constitute a new manner by which Traffic Engineering (TE) can solve or avoid network congestion problems and service degradations. As both IP and optical network layers are involved, this is called Multi-layer Traffic Engineering. We proposed border model based MLSN architecture in [5]. In this paper, we define the realization of Multi-Layer TE functions using Path Computation Element (PCE) for Border model based MLSN. It defines nodal requirements for multi-layer TE. Requirements of communication protocol between PCC (Path Computation Client) and PCE is introduced. It presents Virtual Network Topology (VNT) scenarios and steps involved along with examples for PCE-based VNT reconfiguration triggered by network failure, where VNT is a set of different layer's network resource accumulation.

We survey traffic matrix models, whose elements represent the traffic demand between source-destination pair nodes. Modeling the traffic matrix is useful for multilayer Traffic Engineering (TE) in IP optical networks. Multilayer TE techniques make the network so designed flexible and reliable. This is because it allows reconfiguration of the virtual network topology (VNT), which consists of a set of several lower-layer (optical) paths and is provided to the higher layer, in response to fluctuations (diurnal) in traffic demand. It is, therefore, important to synthetically generate traffic matrices as close to the real ones as possible to maximize the performance of multilayer TE. We compare several models and clarify their applicability to VNT design and control. We find that it is difficult in practice to make an accurate traffic matrix with conventional schemes because of the high cost for data measurement and the complicated calculations involved. To overcome these problems, we newly introduce a simplified traffic matrix model that is practical; it well mirrors real networks. Next, this paper presents our developed server, the IP Optical TE server. It performs multilayer TE in IP optical networks. We evaluate the effectiveness of multilayer TE using our developed IP Optical server and the simplified traffic matrix. We confirm that multilayer TE offers significant CAPEX savings. Similarly, we demonstrate basic traffic control in IP optical networks, and confirm the dynamic control of the network and the feasibility of the IP Optical TE server.

This paper proposes a new computational optimization method modified from the dynamic encoding algorithm for searches (DEAS). Despite the successful optimization performance of DEAS for both benchmark functions and parameter identification, the problem of exponential computation time becomes serious as problem dimension increases. The proposed optimization method named univariate DEAS (uDEAS) is especially implemented to reduce the computation time using a univariate local search scheme. To verify the algorithmic feasibility for global optimization, several test functions are optimized as benchmark. Despite the simpler structure and shorter code length, function optimization performance show that uDEAS is capable of fast and reliable global search for even high dimensional problems.

It is well known that a basic version (i.e., maximizing the number of base-pairs) of the RNA secondary structure prediction problem can be solved in O(n3) time by using simple dynamic programming procedures. For this problem, an O(n3(log log n)1/2/(log n)1/2) time exact algorithm and an O(n2.776+(1/ε)O(1)) time approximation algorithm which has guaranteed approximation ratio 1-ε for any positive constant ε are also known. Moreover, when two RNA sequences are given, there is an O(n6) time exact algorithm which can optimize structure and alignments. In this paper, we show an O(n5) time approximation algorithm for optimizing structure and alignments of two RNA sequences with assuming that the optimal number of base-pairs is more than O(n0.75). We also show that the problem to optimize structure and alignments for given N sequences is NP-hard and introduce a constant-factor approximation algorithm.

In this paper, we propose a useful algorithm that can be applied to reduce the response time of speech recognizers based on HMM's. In our algorithm, to reduce the response time, promising HMM states are selected by single Gaussians. In speech recognition, HMM state likelihoods are evaluated by the corresponding single Gaussians first, and then likelihoods by original full Gaussians are computed and replaced only for the HMM states having relatively large likelihoods. By doing so, we can reduce the pattern-matching time for speech recognition significantly without any noticeable loss of the recognition rate. In addition, we cluster the single Gaussians into groups by measuring the distance between Gaussians. Therefore, we can reduce the extra memory much more. In our 10,000 word Korean POI (point-of-interest) recognition task, our proposed algorithm shows 35.57% reduction of the response time in comparison with that of the baseline system at the cost of 10% degradation of the WER.

We study quantum entanglement by Schmidt decomposition for some typical quantum algorithms. In the Shor's exponentially fast algorithm the quantum entanglement holds almost maximal, which is a major factor that a classical computer is not adequate to simulate quantum efficient algorithms.

We propose constant-round protocols for interval tests, equality tests, and comparisons where shared secret inputs are not given bitwise. In [9]. Damgård et al. presented a novel protocol called the bit-decomposition, which can convert a polynomial sharing of an element in prime field Zp into sharings of bits. Though, by using the bit-decomposition protocol, those protocols can be constructed with constant round complexities theoretically, it involves expensive computation, leading to relatively high round and communication complexities. In this paper, we construct more efficient protocols for those protocols without relying on the bit-decomposition protocol. In the interval test protocol, checking whether a shared secret exists in the known interval is reduced to checking whether a bitwise-shared random secret exists in the appropriate interval. In the comparison protocol, comparing two shared secrets is reduced to comparing the two secrets viaindirectly where p is an odd prime for an underlying linear secret sharing scheme. In the equality test protocol, checking whether two shared secrets are equal is reduced to checking whether the difference of the two secrets is zero and furthermore checking whether the difference is a zero is reduced to checking quadratice residuosity of a random secret in a probabilistic way.

An edge-weighted directed graph is referred to as a network in this paper, and an edge operation is an operation that increases or decreases an edge weight. Decreasing an edge weight from the infinite to a finite value or increasing any edge weight from a finite one to the infinite corresponds to addition or deletion of this edge, respectively. The dynamic shortest path problem (DSPP for short) is defined by "Given any network with a specified vertex (denoted as s), and any sequence of edge operations, construct a shortest path tree of each network obtained by executing those edge operations one by one in the order of the sequence." As an application, fast routing for an interior network using link state protocols, such as OSPF and IS-IS, requires solving DSPP efficiently. In this paper, among as many existing algorithms as possible, including those which execute several edge operations simultaneously, fundamental and/or important algorithms are implemented and their capability is evaluated based on the results of computational experiments.

Fractional Motion Estimation (FME) is an advanced feature adopted in H.264/AVC video compression standard with quarter-pixel accuracy. Although FME could gain considerably higher encoding efficiency, sub-pixel interpolation and sum of absolute transformed difference (SATD) computation, as main parts of FME, increase the computation complexity a lot. To reduce the complexity of FME, this paper proposes a full computation reusable VLSI oriented algorithm. Through exploiting the similarity among motion vectors (MVs) of partitions in the same macroblock (MB), temporary computation results can be fully reused. Furthermore, a simple and effective searching method is adopted to make the proposed method more suitable for VLSI implementation. Experiment results show that up to 80% add operations and 85% internal reference frame memory access operations are saved without any degradation in the coding quality.

This paper proposes a butterfly structure for Viterbi decoders, which works for convolutional codes of all rates k/n. The proposed butterfly structure can exploit the inherent symmetry of trellis branches, so that only some branch metrics need to be computed, while the others can be derived from the computed branches. Consequently, the computational complexity of the Viterbi decoder can be significantly reduced without any error performance loss. The applicability of the butterfly structure is validated by the best codes of rates 1/2, 2/3, and 3/4. Most of the best codes can apply the butterfly structure to reduce their branch metric computation complexity by a factor of 2 or 4. This study also reports a number of new codes with high branch symmetry under the symmetry consideration. Their branch metric computation can be reduced by a factor of 4, 8 or 16 with the similar performance to the best codes.