In (k,n) threshold scheme, Tompa and Woll considered a problem of cheaters who try to make another participant reconstruct an invalid secret. Later, some models of such cheating were formalized and lower bounds of the size of share were shown in the situation of fixing the maximum successful cheating probability to ε. Some efficient schemes in which size of share is equal to the lower bound were also proposed. Let |S| be the field size of the secret. Under the assumption that cheaters do not know the distributed secret, these sizes of share of previous schemes which can work for ε > 1/|S| are somewhat larger than the bound. In this paper, we show the bound for this case is really tight by constructing a new scheme. When distributing uniform secret, the bit length of share in the proposed scheme is only 1 bit longer than the known bound. Further, we show a tighter bound of the size of share in case of ε < 1/|S|.
It is well known that the problem to solve a set of randomly chosen multivariate quadratic equations over a finite field is NP-hard. However, when the number of variables is much larger than the number of equations, it is not necessarily difficult to solve equations. In fact, when n ≥ m(m+1) (n,m are the numbers of variables and equations respectively) and the field is of even characteristic, there is an algorithm to find one of solutions of equations in polynomial time (see [Kipnis et al., Eurocrypt '99] and also [Courtois et al., PKC '02]). In the present paper, we propose two new algorithms to find one of solutions of quadratic equations; one is for the case of n ≥ (about) m2-2m 3/2+2m and the other is for the case of n ≥ m(m+1)/2+1. The first one finds one of solutions of equations over any finite field in polynomial time, and the second does with O(2m) or O(3m) operations. As an application, we also propose an attack to UOV with the parameters given in 2003.
Naoki KANAYAMA Tadanori TERUYA Eiji OKAMOTO
In the present paper, we propose elliptic curve scalar multiplication methods on pairing-friendly elliptic curves. The proposed method is efficient on elliptic curves on which Atei pairing or optimal pairing is efficiently computed.
In ubiquitous sensor networks, extra energy savings can be achieved by selecting the filtering solution to counter the attack. This adaptive selection process employs a fuzzy rule-based system for selecting the best solution, as there is uncertainty in the reasoning processes as well as imprecision in the data. In order to maximize the performance of the fuzzy system the membership functions should be optimized. However, the efforts required to perform this optimization manually can be impractical for commonly used applications. This paper presents a GA-based membership function optimizer for fuzzy adaptive filtering (GAOFF) in ubiquitous sensor networks, in which the efficiency of the membership functions is measured based on simulation results and optimized by GA. The proposed optimization consists of three units; the first performs a simulation using a set of membership functions, the second evaluates the performance of the membership functions based on the simulation results, and the third constructs a population representing the membership functions by GA. The proposed method can optimize the membership functions automatically while utilizing minimal human expertise.
Oren ELIEZER Robert Bogdan STASZEWSKI
Digital RF solutions have been shown to be advantageous in various design aspects, such as accurate modeling, design reuse, and scaling when migrating to the next CMOS process node. Consequently, the majority of new low-cost and feature cell phones are now based on this approach. However, another equally important aspect of this approach to wireless transceiver SoC design, which is instrumental in allowing fast and low-cost productization, is in creating the inherent capability to assess performance and allow for low-cost built-in calibration and compensation, as well as characterization and final-testing. These internal capabilities can often rely solely on the SoCs existing processing resources, representing a zero cost adder, requiring only the development of the appropriate algorithms. This paper presents various examples of built-in measurements that have been demonstrated in wireless transceivers offered by Texas Instruments in recent years, based on the digital-RF processor (DRPTM) technology, and highlights the importance of the various types presented; built-in self-calibration and compensation, built-in self-characterization, and built-in self-testing (BiST). The accompanying statistical approach to the design and productization of such products is also discussed, and fundamental terms related with these, such as 'soft specifications', are defined.
Mohammad Reza ZOGHI Mohammad Hossein KAHAEI
This paper addresses the problem of sensor selection in wireless sensor networks (WSN) subject to a distortion constraint. To do so, first, a cost function is derived based on the spatial correlation obtained using the best estimation of the event source. Then, a new adaptive algorithm is proposed in which the number of active sensors is adaptively determined and the best topology of the active set is selected based on the add-one-sensor-node-at-a-time method. Simulations results show that the active sensors selected using the proposed cost function have less event distortion. Also, it is shown that the proposed sensor selection algorithm is near optimum and it has better performance than other algorithms with regard to the computational burden and distortion.
A perfect sequence is a sequence having an impulsive autocorrelation function. Perfect sequences have several applications, such as CDMA, ultrasonic imaging, and position control. A parameterization of a perfect sequence is presented in the present paper. We treat a set of perfect sequences as a zero set of quadratic equations and prove a decomposition law of perfect sequences. The decomposition law reduces the problem of the parameterization of perfect sequences to the problem of the parameterization of quasi-perfect sequences and the parameterization of perfect sequences of short length. The parameterization of perfect sequences for simple cases and quasi-perfect sequences should be helpful in obtaining a parameterization of perfect sequences of arbitrary length. According to our theorem, perfect sequences can be represented by a sum of trigonometric functions.
Yoshinori SUZUKI Kiyoshi KOBAYASHI
This paper presents a novel electrical polarization forming antenna for mobile satellite communication systems using linear polarization. To electrically form the desired polarization, it is necessary to excite the two orthogonal polarization antenna planes with appropriate weights. The proposed antenna uses digitally-based polarization and calibration functions to characterize the two RF paths. The calibration techniques used are critical to accurately forming the desired polarization. Proposed calibration techniques are very simple; the feedback signal consists of just amplitude levels. The proposals are validated by polarization forming measurements conducted on a fabricated antenna.
Orthogonal frequency division multiplexing has emerged as a promising air interface scheme for wireless broadband communications. For OFDM systems, frame synchronization has received much attention in the literature, though simple correlators are still widely used in real systems. In this letter, we present the analytical expression of the optimal frame synchronizer for OFDM systems. Frame synchronization is posed as a maximum a posteriori probability estimation. We show that the resulting frame synchronizer consists of a correlation term and a correction term. The correction term accounts for the random data surrounding a synchronization word. Numerical results show the performance gain of the proposed frame synchronizer over a correlation scheme.
Railway operators adjust timetables, and accordingly reschedule rolling stock circulation and crew duties, when the train operations are disrupted by accidents or adverse weather conditions. This paper discusses the problem of rescheduling driver assignment to freight trains after timetable adjustment has been completed. We construct a network from the disrupted situation, and model the problem as an integer programming problem with set-covering constraints combined with set-partitioning constraints. The integer program is solved by column generation in which we reduce the column generation subproblem to a shortest path problem and such paths by utilizing data parallelism. Numerical experiments using a real timetable, driver scheduling plan and major disruption data in the highest-frequency freight train operation area in Japan reveal that our method provides a quality driver rescheduling solution within 25 seconds.
Jianxiong HUANG Taiyi ZHANG Runping YUAN Jing ZHANG
This letter investigates the performance of amplify-and-forward relaying systems using maximum ratio transmission at the source. A closed-form expression for the outage probability and a closed-form lower bound for the average bit error probability of the system are derived. Also, the approximate expressions for the outage probability and average bit error probability in the high signal-to-noise ratio regime are given, based on which the optimal power allocation strategies to minimize the outage probability and average bit error probability are developed. Furthermore, numerical results illustrate that optimizing the allocation of power can improve the system performance, especially in the high signal-to-noise ratio regime.
This paper presents a new and robust framework for real-coded genetic algorithm, called real-code conditional genetic algorithm (rc-CGA). The most important characteristic of the proposed rc-CGA is the implicit self-adaptive feature of the crossover and mutation mechanism. Besides, a new crossover operator with laplace distribution following a few promising descent directions (FPDD-LX) is proposed for the rc-CGA. The proposed genetic algorithm (rc-CGA+FPDD-LX) is tested using 31 benchmark functions and compared with four existing algorithms. The simulation results show excellent performance of the proposed rc-CGA+FPDD-LX for continuous function optimization.
In this paper, we deal with the algebraic immunity of the symmetric Boolean functions. The algebraic immunity is a property which measures the resistance against the algebraic attacks on symmetric ciphers. It is well known that the algebraic immunity of the symmetric Boolean functions is completely determined by a narrow class of annihilators with low degree which is denoted by G(n,). We study and determine the weight support of part of these functions. Basing on this, we obtain some relations between the algebraic immunity of a symmetric Boolean function and its simplified value vector. For applications, we put forward an upper bound on the number of the symmetric Boolean functions with algebraic immunity at least d and prove that the algebraic immunity of the symmetric palindromic functions is not high.
Nozomu KATAYAMA Takeshi FUJIMURA Hiroyoshi MIWA Noriaki KAMIYAMA Haruhisa HASEGAWA Hideaki YOSHINO
When a link or node fails in a network, the affected flows are automatically rerouted. This increases the hop counts of the flows, which can drastically degrade network performance. Keeping the hop lengths as stable as possible, i.e., minimizing the difference in hop length between the original flow and the rerouted flow is important for network reliability. Therefore, network service providers need a method for designing networks that stabilizes the flow hop length and maintains connectivity during a link or node failure with limited investment cost. First, we formulate the network design problem used for determining the set of links to be added that satisfies the required constraints on flow hop length stability, connectivity, and node degree. Next, we prove that this problem is NP-complete and present two approximation algorithms for the optimization problem so as to minimize the number of links added. Evaluation of the performance of these algorithms by using 39 backbone networks of commercial ISPs and networks generated by two well-known models showed that the proposed algorithms provide effective solutions in sufficiently short computation time.
Secure access is one of the key concerns of wireless sensor networks (WSNs). In WSNs, because there are many dynamically mutable attributes, continuous access decisions and dynamic attribute updates should be important properties of access control. In addition, WSNs need low-complexity authentication protocols because of the constrained resources. However, the authentication protocols of most current security access schemes have relatively high complexity. More importantly, the access control models of existing schemes cannot provide attribute mutability and continuous decisions dynamically. To address above issues, we propose a dynamic secure access mechanism for WSNs. Firstly, we design a lightweight secure authentication protocol and dynamic access control based on security token and usage control (UCON), respectively. Then, the agent technology is adopted to implement the proposed secure access scheme. Secondly, we analyze the probability of the dynamic attribute update and decisions. Thirdly, we implement an instance of UCON. The implementation results indicate the feasibility of using UCON in WSNs. Finally, by evaluating and comparing with current schemes, the authentication protocol in our scheme presents several advantages including the low expenses in calculation, storage and communication. To our best knowledge, this paper is the first to realize next generation dynamic access control with attribute mutability and continuous decisions in WSNs.
Bin SONG Hao QIN Xuelu PENG Yanhui QIN
An adaptive selective retransmission algorithm for video communications based on packet importance value is proposed. The algorithm can adaptively select the retransmission threshold in realtime and efficiently manage the retransmission process in heavy loaded networks while guaranteeing acceptable video quality at the receiver.
This letter is devoted to derivation of a transformation law which converts a class of nonlinear affine control systems with n-states and 2-iputs into simpler systems with chained structure. First, we give a problem formulation that we consider throughout this letter. We next introduce a transformation law and gives its mathematical certification. Then, we apply the transformation method to an example and consider control design based on chained structure for the example in order to confirm the effectiveness of our approach.
In optical packet switches, the overhead of reconfiguring a switch fabric is not negligible with respect to the packet transmission time and can adversely affect switch performance. The overhead increases the average waiting time of packets and worsens throughput performance. Therefore, scheduling packets requires additional considerations on the reconfiguration frequency. This work intends to analytically find the optimal reconfiguration frequency that minimizes the average waiting time of packets. It proposes an analytical model to facilitate our analysis on reconfiguration optimization for input-buffered optical packet switches with the reconfiguration overhead. The analytical model is based on a Markovian analysis and is used to study the effects of various network parameters on the average waiting time of packets. Of particular interest is the derivation of closed-form equations that quantify the effects of the reconfiguration frequency on the average waiting time of packets. Quantitative examples are given to show that properly balancing the reconfiguration frequency can significantly reduce the average waiting time of packets. In the case of heavy traffic, the basic round-robin scheduling scheme with the optimal reconfiguration frequency can achieve as much as 30% reduction in the average waiting time of packets, when compared with the basic round-robin scheduling scheme with a fixed reconfiguration frequency.
Kei MATSUMOTO Tetsuya HIROSE Yuji OSAKI Nobutaka KUROKI Masahiro NUMA
We propose a subthreshold Static Random Access Memory (SRAM) circuit architecture with improved write ability. Even though the circuits can achieve ultra-low power dissipation in subthreshold digital circuits, the performance is significantly degraded with threshold voltage variations due to the fabrication process and temperature. Because the write operation of SRAM is prone to failure due to the unbalance of threshold voltages between the nMOSFET and pMOSFET, stable operation cannot be ensured. To achieve robust write operation of SRAM, we developed a compensation technique by using an adaptive voltage scaling technique that uses an on-chip threshold voltage monitoring circuit. The monitoring circuit detects the threshold voltage of a MOSFET with the on-chip circuit configuration. By using the monitoring voltage as a supply voltage for SRAM cells, write operation can be compensated without degrading cell stability. Monte Carlo simulations demonstrated that the proposed SRAM architecture exhibits a smaller write operation failure rate and write time variation than a conventional 6T SRAM.
Existing time synchronization schemes in sensor networks were all developed to be energy-efficient, precise, and robust, but none of them were developed with security in mind. We have developed a secure, accurate and energy-efficient time synchronization protocol (SAEP). SAEP achieves accurate time synchronization service with significantly reducing the number of message exchanges. Also, it safeguards against Byzantine failure, in which nodes drop, modify, or delay time information in an attempt to disrupt the time synchronization service in multi-hop networks. SAEP takes a distributed approach where each sensor independently makes decisions based only on the information collected from multiple adjacent nodes, thus achieving a high level of resistance to various attacks while minimizing the energy cost. We investigate the misbehavior of a maliciously compromised node and analyze how SAEP can combat these attacks. In our experiment SAEP outperforms the existing time synchronization protocol in accuracy, energy consumption and it is even resilient to multiple capture attacks.