This paper proposes a secure electronic sealed-bid auction protocol (SEAP) that provides an auction service on the Internet by combining three providers: an auction service provider, a key service provider, and a time service provider. The SEAP uses public key cryptography and the concept of a time-key certificate. The most important property of this protocol is that time-dependent security requirements can be strictly satisfied. The SEAP satisfies the following nine security requirements: (a) no one can deny having made a bid; (b) the protocol should be secure against malicious acts; (c) no bidder can act for another bidder; (d) no one can know who else is bidding until the time comes for the bids to be opened; (e) no one can discover the contents of any of the bids until the time comes for the bids to be opened; (f) the successful bid must have been submitted before the bidding deadline; (g) all bidders can verify that the auction policy has been correctly implemented; (h) the successful bidder can be identified without being required to make himself or herself known; and (i) the bidding contents cannot be altered. The protocol consists of three subprotocols: the Registration Subprotocol, the Bidding Subprotocol, and the Auction Subprotocol. The protocol parameters and algorithm are described in detail.
Kazuomi OISHI Masahiro MAMBO Eiji OKAMOTO
In this paper a public key certification scheme, which protects privacy of user of the public key certificate, is proposed. In the proposed scheme a certification authority issues anonymous public key certificates, with which a certificate user having his/her own secret key can make use of public key cryptography and a certificate verifier can confirm the authenticity of the cryptographic communication of the certificate user. The anonymity of their users is preserved against the verifier. In general, user's activities should not be linked each other from the viewpoint of privacy protection. The use of the same certificate results in the linkage of the cryptographic communications. So, ideally, a certificate should be used only once, and such a certificate is called a one-time certificate. In the proposed scheme one-time certificates are realized with low cost of communication and computation for the certificate user. Multiple certificates can be issued without interaction between CA and the user. The additional computation of the user to obtain a new anonymous public key certificate is one modular exponentiation. In addition, only one secret key is required for multiple certificates. Therefore, the proposed scheme is useful for applications which require anonymity, unlinkability, and efficiency.
Kazumasa NOMOTO Ryuichi UGAJIN Toshi-kazu SUZUKI Kenichi TAIRA Ichiro HASE
We propose a novel opto-electronic memory device using a single quantum dot (QD) and a logic device using coupled QDs (CQD) which performs (N)AND and (N)OR operations simultaneously. In both devices, occupation/unoccupation by a single electron in a QD is viewed as a bit 1/0 and data input/output (I/O) is performed by irradiation/absorption of photons. The (N)AND/(N)OR operations are performed by the relaxation of the electronic system to the Fock ground state which depends on the number of electrons in the CQD. When the device is constructed of semiconductor nanostructures, the main relaxation process is LA-phonon emission from an electron. Theoretical analysis of the device shows that (i) the error probability in the final state converges with the probability with which the system takes excited states at thermal equilibrium, i. e. , depends only on the dissipation energy and becomes smaller as the dissipation energy becomes larger, and (ii) the speed of operation depends on both the dissipation energy and dissipative interactions and becomes slower as the dissipation energy becomes larger if LA-phonon emission is taken into account. If the QDs are InAs cubes with sides of 10 nm and they are separated by the AlSb barrier with a width of 10 nm, the speed of operation and the error probability are estimated to be about 1 ns and about 0. 2 at 77 K, respectively. The basic idea of the device is applicable to two-dimensional (2D) pattern processing if the devices are arranged in a 2D array.
We describe an algorithm for efficiently compositing partial images generated during parallel volume rendering on a distributed memory parallel computer. In this object space partitioning algorithm, each PE is assigned to several subvolumes where each subvolume has a corresponding local frame buffer. After volume rendering is performed independently for each subvolume, the partial images stored in the local frame buffers are combined to generate a complete image. During this compositing process, the communication of partial image data between the PEs is kept minimal by assigning PEs to subvolumes in an interleaved manner. This assignment makes possible a reduction in communication in the axis direction in which there is the most communication. Experimental results indicate that a 9% to 35% reduction in the total rendering time can be attained with no additional data structures and no memory overhead.
This paper analyzes a finite buffer M/G/1 queue with two classes of customers who are served by a combination of head-of-the-line priority and push-out schemes. This combination gives each class of customers two different types of priorities with respect to both delay and loss. There are two models considered. The first one is that one class of customers has a higher priority over the other class with respect to both delay and loss; the second one is that one class has a higher priority with respect to loss and the other has high-priority with respect to delay. For both of these models, the joint probability distribution of the number of customers of both classes in the buffer is derived by a supplementary variable method. Using this probability distribution, we can easily calculate the loss probabilities of both classes, the mean waiting time for high-priority customers with respect to loss and the upper bound for mean waiting time for low-priority customers with respect to loss. Numerical examples demonstrate an effect of the combination of different types of priorities.
S-boxes (vector output Boolean functions) should satisfy cryptographic criteria even if some input bits (say, k bits) are kept constant. However, this kind of security has been studied only for scalar output Boolean functions. SAC (k) is a criterion for scalar output Boolean functions of this type. This paper studies a generalization of SAC (k) to vector output Boolean functions as the first step toward the security of block ciphers against attacks which keep some input bits constant. We first show a close relationship between such Boolean functions and linear error correcting codes. Then we show the existence, bounds and enumeration of vector Boolean functions which satisfy the generalized SAC (k). A design method and examples are also presented.
Tae-Joong KIM Ki-Jun KIM Seung-Hoon HWANG Keum-Chan WHANG
This paper presents a new CLSP/CC (Channel Load Sensing Protocol/Channel Clearance) in order to obtain better performances in spread slotted ALOHA networks. This protocol can decrease a wasteful utilization of channel by prohibiting continuous transmission of the packets destroyed in previous slot, with little added network complexities. For channel clearance technique, hub station broadcasts NAK to all mobile stations when the number of packets transmitted in a slot exceeds the channel capacity, and mobile stations cease own packet transmissions at NAK broadcast. The performances of the proposed CLSP/CC are obtained and compared with those of conventional CLSP by simulations. The performances include network throughput, average processing time and the number of mobile stations in backlogged state. As simulation results, the proposed CLSP/CC outperforms conventional CLSP, especially in highly offered load environment. Also as the proposed CLSP/CC obtain maximum throughputs at higher offered loads and the larger number of mobile stations in backlogged state than the conventional CLSP, it is found that our protocol can support more mobile stations and higher occurrence probabilities.
Jianliang XU Katsushi INOUE Yue WANG Akira ITO
This paper first investigates a relationship between inkdot-depth and inkdot-size of inkdot two-way alternating Turing machines and pushdown automata with sublogarithmic space, and shows that there exists a language accepted by a strongly loglog n space-bounded alternating pushdown automaton with inkdot-depth 1, but not accepted by any weakly o (log n) space-bounded and d (n) inkdot-size bounded alternating Turing machine, for any function d (n) such that limn [d (n)log n/n1/2] = 0. In this paper, we also show that there exists an infinite space hierarchy among two-way alternating pushdown automata with sublogarithmic space.
Hiroshi TAKAHASHI Shigeshi ABIKO Shintaro MIZUSHIMA Yuji OZAWA Kenichi TASHIRO Shigetoshi MURAMATSU Masahiro FUSUMADA Akemi TODOROKI Youichi TANAKA Masayasu ITOIGAWA Isao MORIOKA Hiroyuki MIZUNO Miki KOJIMA Giovanni NASO Emmanuel EGO Frank CHIRAT
A 100MIPS high speed and low power fixed point Digital Signal Processor (DSP) has been developed applying 0.45µm CMOS TLM technology. The DSP contains a 16-bit32K full CMOS static RAM with a hierarchical low power architecture. The device is a RAM based DSP with a total of 4.2 million transistors and a new low power design and process which enabled an approximate 50% reduction in power as compared to conventional DSPs at 40 MHz. In order to cover very wide application requirements, this DSP is capable of operating at 1.0 V for DSP core and 3.3 V for I/O. This was achieved by new level shifter circuitry to interface with cost effective 3 V external commodity products and confirmed 80% of power reduction at Core VDD=2.0 V, I/O VDD=3.3 V at 40MHz. This paper describes the new features of the high speed and low power DSP.
Eun-Chang CHOI Bhum-Cheol LEE Hee-Young JUNG Kwon-Chul PARK
In this paper, we analyze overload and stability in the charge-pump phase locked loop (PLL). We propose a new computational model that can be applied for the precise estimation of the physical limits of charge-pump, the leakage current of loop filter and waveform distortion of charge-pump PLL operating in high speed. We derive the exact mathematical expressions of the parameters describing the steady-state behavior of the PLL as well as the transient-state behavior. Performance comparisons with the conventional model are provided through numerical results. Algorithms for approximate analysis is also provided. The new model is particularity useful for analyzing the cases that the charge-pump PLL operates in high- speed or the loop filter has large leakage current.
Tohru KIKUTA Fumihito SASAMORI Fumio TAKAHATA
Considering that the application of the direct-sequence slotted spread ALOHA communications system to access/control channel is effective in communications systems with traffic channels operating at CDMA mode, the spread ALOHA communications system is discussed in terms of the system configuration and transmission efficiency. The transmission efficiency of the spread ALOHA communications system using a unified spread code is derived by means of two methods. One is based on the simulation of demodulation algorithm, and the other is based on the approximation by modeling. It becomes obvious from quantitative evaluation in terms of the probability of packet success and the throughput performance that the approximated results coincide with the simulated results, and that the modeling is very effective to estimate the transmission efficiency of the spread ALOHA communications system.
In supervisory control, discrete event dynamic systems (DEDSs) are modeled by finite-state automata, and their behaviors described by the associated formal languages; control is exercised by a supervisor, whose control action is to enable or disable the controllable events. In this paper we present a general stability concept for DEDSs, stability in the sense of Lyapunov with resiliency, by incorporating Lyapunov stability concepts with the concept of stability in the sense of error recovery. We also provide algorithms for verifying stability and obtaining a domain of attraction. Relations between the notion of stability and the notion of fault-tolerance are addressed.
Takao WATANABE Ryo FUJITA Kazumasa YANAGISAWA
The advantages of DRAM-logic integration were demonstrated through a comparison with a conventional separate-chip architecture. Although the available DRAM capacity is restricted by chip size, the integration provides a high throughput and low I/O-power dissipation due to a large number of on-chip I/O lines with small load capacitance. These features result in smaller chip counts as well as lower power dissipation for systems requiring high data throughput and having relatively small memory capacity. The chip count and I/O-power dissipation were formulated for multimedia systems. For the 3-D computer graphics system with a frame of 12801024 pixels requiring a 60-Mbit memory capacity and a 4.8-Gbyte/s throughput, DRAM-logic integration enabled a 1/12 smaller chip count and 1/10 smaller I/O-power dissipation. For the 200-MIPS hand-held portable computing system that had a 16-Mbit memory capacity and required a 416-Mbyte/s throughput, DRAM-logic integration enabled a 1/4 smaller chip count and 1/17 smaller I/O-power dissipation. In addition, innovative architectures that enhance the advantages of DRAM-logic integration were discussed. Pipeline access for a DRAM macro having a cascaded multi-bank structure, an on-chip cache DRAM, and parallel processing with a reduced supply voltage were introduced.
Komain PIBULYAROJANA Shigetomo KIMURA Yoshihiko EBIHARA
Many switching networks are currently designed to support ATM architectures. In this letter, we propose the performance improvement of a network called hybrid dilated banyan network with bypasses at the stage of 42 re-arrangeable output switch. Our letter also includes the performance analysis of the improved hybrid dilated banyan network.
Kisok KONG Manhee KIM Hyogun LEE Joonwon LEE
This paper presents a proportional-share CPU scheduler which can support multimedia applications in a general-purpose workstation environment. For this purpose, we have extended the stride scheduler which is designed originally for conventional tasks. New scheduling parameters are introduced to specify timing requirements of multimedia applications. Through the use of the rate regulator, the accuracy error of the scheduling is reduced to 0 (1). Separate task groups are proposed to represent both relative shares and absolute shares. The proposed scheduler is evaluated using a simulation study. The results show that the proposed scheduler achieves improved accuracy and adaptability as well as flexibility.
Jun-ya TAKAHASHI Hiromichi TAKAHASHI Norishige CHIBA
Producing realistic images and animations of flames is one of the most interesting subjects in the field of computer graphics. In a recent paper, we described a two-dimensional particle-based visual method of simulating flames. In the present paper, we first extend the simulation method, without losing any of its desirable features, in such a way that it functions in three-dimensional space. We then present an efficient method of producing an image of the scene, including flames acting as volume light sources, which normally requires a large amount of computing time in the usual simulation approaches. Finally, we demonstrate the capabilities of our visual simulation method by showing sample images generated by it, which are excerpted from an animation.
The EMC-adequate design of microelectronic systems includes all actions intended to eliminate electromagnetic interference in electronic systems. Challenges faced in the microelectronic area include a growing system complexity, high integration levels and higher operating speeds at all levels of integration (chip, MCM, printed circuit board and system). The growing complexity, denser design and higher speed all lead to a substantial increase in EMC problems and accordingly the design time. EMC is not commonly accepted as a vital topic in microelectronic design. Microelectronic designers often are of the opinion that EMC is limited to electrical and electronic systems and the mandatory product regulations instead of setting requirements also for the integrated circuit they are designing. In this contribution a concept for an EMC-adequate design of electronic systems will be introduced. This concept is based on a generalized development process to integrate EMC-constraints into the system design. A prototype of an environment to analyse signal integrity effects on PCB based on a workflow oriented integration approach will be presented. Based on this approach the generation of user specific design and analysis environments including various set of EMC-tools is possible.
Tsuyoshi KAWAGUCHI Takeharu BABA Ryo-ichi NAGATA
The main defficulty in recognizing 3-D objects from 2-D images is matching 2-D information to the 3-D object representation. The multiple-view approach makes this problem easy to solve by reducing the problem to 2-D to 2-D matching problem. This approach models each 3-D object by a collection of 2-D views from various viewing angles and recognizes an object in the image by finding a 2-D view that has the best match to the image. However, if the size of the model database becomes large, the approach requires long time for the recognition of objects. In this paper we present a 3-D object recognition algorithm based on multiple-view approach. To reduce the recognition time, the proposed algorithm uses the coarse-to-fine process previously proposed by the authors and a genetic algorithm-based search scheme for the selection of a best matched model in the database. And, we could verify from the results of the experiments that the algorithm proposed in this paper is useful to speed up the recognition process in multiple-view based object recognition systems.
Seunghwan LEE Masanori HARIYAMA Michitaka KAMEYAMA
Three-dimensional (3-D) instrumentation using an image sequence is a promising instrumentation method for intelligent systems in which accurate 3-D information is required. However, real-time instrumentation is difficult since much computation time and a large memory bandwidth are required. In this paper, a 3-D instrumentation VLSI processor with a concurrent memory-access scheme is proposed. To reduce the access time, frequently used data are stored in a cache register array and are concurrently transferred to processing elements using simple interconnections to the 8-nearest neighbor registers. Based on a row and column memory access pattern, we propose a diagonally interleaved frame memory by which pixel values of a row and column are stored across memory modules. Based on the concurrent memory-access scheme, a 40 GOPS vprocessor is designed and the delay time for the instrumentation is estimated to be 42 ms for a 256256 images.
Sung-Won LEE Dong-Ho CHO Yeong-Jin KIM Sun-Bae LIM
In this paper, we consider conventional signaling link fault tolerance and error correction mechanisms to provide reliable services of mobile multimedia telecommunication network based on ATM (Asynchronous Transfer Mode) technology. Also, we propose an efficient signaling protocol interworking architecture and a reliable distributed interworking network architecture between SS7 based FPLMTS and ATM networks. Besides, we evaluate the performance of proposed method through computer simulation. According to the results, proposed signaling architecture shows efficient and fast fault restoration characteristics than conventional MTP-3/3b based network. Functional signaling protocol stack and network architecture of proposed fast rerouting mechanism provide reliable and efficient restoration performance in view of interworking between SS7 based FPLMTS and ATM networks.