Yuto KAWAHARA Tetsutaro KOBAYASHI Gen TAKAHASHI Tsuyoshi TAKAGI
Pairing-based cryptosystems are generally constructed using many functions such as pairing computation, arithmetic in finite fields, and arithmetic on elliptic curves. MapToPoint, which is a hashing algorithm onto an elliptic curve point, is one of the functions for constructing pairing-based cryptosystems. There are two MapToPoint algorithms on supersingular elliptic curves in characteristic three, which is used by ηT pairing. The first is computed by using a square root computation in F3m, and the computational cost of this algorithm is O(log m) multiplications in F3m. The second is computed by using an (m-1)(m-1) matrix over F3. It can be computed by O(1) multiplications in F3m. However, this algorithm needs the off-line memory to store about m F3m-elements. In this paper, we propose an efficient MapToPoint algorithm on the supersingular elliptic curves in characteristic three by using 1/3-trace over F3m. We propose 1/3-trace over F3m, which can compute solution x of x3 -x = c by using no multiplication in F3m. The proposed algorithm is computed by O(1) multiplications in F3m, and it requires less than m F3-elements to be stored in the off-line memory to efficiently compute trace over F3m. Moreover, in our software implementation of F3509, the proposed MapToPoint algorithm is approximately 35% faster than the conventional MapToPoint algorithm using the square root computation on an AMD Opteron processor (2.2 GHz).
It is necessary to perform arithmetic in Fp12 to use an Ate pairing on a Barreto-Naehrig (BN) curve, where p is a prime given by p(z)=36z4+36z3+24z2+6z+1 for some integer z. In many implementations of Ate pairings, Fp12 has been regarded as a 6th degree extension of Fp2, and it has been constructed by Fp12=Fp2[v]/(v6-ξ) for an element ξ ∈ Fp2 such that v6-ξ is irreducible in Fp2[v]. Such a ξ depends on the value of p, and we may use a mathematical software package to find ξ. In this paper it is shown that when z ≡ 7,11 (mod 12), we can universally construct Fp12 as Fp12=Fp2[v]/(v6-u-1), where Fp2=Fp[u]/(u2+1).
Shigetoshi NAKATAKE Masahiro KAWAKITA Takao ITO Masahiro KOJIMA Michiko KOJIMA Kenji IZUMI Tadayuki HABASAKI
This paper presents a novel regularity evaluation of placement structure and techniques for handling conditional design rules along with dynamic diffusion sharing and well island generation, which are developed based on Sequence-Pair. The regular structures such as topological rows, arrays and repetitive structures are characterized by the way of forming sub-sequences of a sequence-pair. A placement objective is formulated balancing the regularity and the area efficiency. Furthermore, diffusion sharing and well island can be also identified looking into forming of a sequence-pair. In experiments, we applied our regularity-oriented placement mixed with the constraint-driven technique to real analog designs, and attained the results comparable to manual designs even when imposing symmetry constraints. Besides, the results also revealed the regularity serves to increase row-structures applicable to the diffusion sharing for area saving and wire-length reduction.
We investigate binary sequence pairs with two-level correlation in terms of their corresponding cyclic difference pairs (CDPs). We define multipliers of a cyclic difference pair and present an existence theorem for multipliers, which could be applied to check the existence/nonexistence of certain hypothetical cyclic difference pairs. Then, we focus on the ideal case where all the out-of-phase correlation coefficients are zero. It is known that such an ideal binary sequence pair exists for length υ = 4u for every u ≥ 1. Using the techniques developed here on the theory of multipliers of a CDP and some exhaustive search, we are able to determine that, for lengths υ ≤ 30, (1) there does not exist "any other" ideal/ binary sequence pair and (2) every example in this range is equivalent to the one of length υ = 4u above. We conjecture that if there is a binary sequence pair with an ideal two-level correlation then its in-phase correlation must be 4. This implies so called the circulant Hadamard matrix conjecture.
Binary sequence pairs as a class of mismatched filtering of binary sequences can be applied in radar, sonar, and spread spectrum communication system. Binary sequence pairs with two-level periodic autocorrelation function (BSPT) are considered as the extension of usual binary sequences with two-level periodic autocorrelation function. Each of BSPT consists of two binary sequences of which all out-phase periodic crosscorrelation functions, also called periodic autocorrelation functions of sequence pairs, are the same constant. BSPT have an equivalent relationship with difference set pairs (DSP), a new concept of combinatorial mathematics, which means that difference set pairs can be used to research BSPT as a kind of important tool. Based on the equivalent relationship between BSPT and DSP, several families of BSPT including perfect binary sequence pairs are constructed by recursively constructing DSP on the integer ring. The discrete Fourier transform spectrum property of BSPT reveals a necessary condition of BSPT. By interleaving perfect binary sequence pairs and Hadamard matrix, a new family of binary sequence pairs with zero correlation zone used in quasi-synchronous code multiple division address is constructed, which is close to the upper theoretical bound with sequence length increasing.
Lifeng HE Fang YANG Kewu PENG Jian SONG
In this paper, a novel pseudo-random noise complementary pair (PNCP) is proposed and adopted as the guard intervals in the time-domain synchronous OFDM (TDS-OFDM) system. The proposed PNCP has nearly ideal aperiodic auto-correlation property and inherits the differential property of the PN sequence. Simulations demonstrate the proposed TDS-OFDM system padded with PNCP could achieve better performance in both synchronization and channel estimation than the conventional TDS-OFDM system.
Toru NAKANISHI Yuta HIRA Nobuo FUNABIKI
To reduce the damage of key exposures, forward-secure group signature schemes have been first proposed by Song. In the forward-secure schemes, a secret key of a group member is updated by a one-way function every interval and the previous secret key is erased. Thus, even if a secret key is exposed, the signatures produced by the secret keys of previous intervals remain secure. Since the previous forward-secure group signature schemes are based on the strong RSA assumption, the signatures are longer than pairing-based group signatures. In addition, the complexity of the key update or signing/verification is O(T), where T is the total number of intervals. In this paper, a forward-secure group signature scheme from pairings is proposed. The complexity of our key update and signing/verification is O(log T).
Hisashi KASHIMA Satoshi OYAMA Yoshihiro YAMANISHI Koji TSUDA
Pairwise classification has many applications including network prediction, entity resolution, and collaborative filtering. The pairwise kernel has been proposed for those purposes by several research groups independently, and has been used successfully in several fields. In this paper, we propose an efficient alternative which we call a Cartesian kernel. While the existing pairwise kernel (which we refer to as the Kronecker kernel) can be interpreted as the weighted adjacency matrix of the Kronecker product graph of two graphs, the Cartesian kernel can be interpreted as that of the Cartesian graph, which is more sparse than the Kronecker product graph. We discuss the generalization bounds of the two pairwise kernels by using eigenvalue analysis of the kernel matrices. Also, we consider the N-wise extensions of the two pairwise kernels. Experimental results show the Cartesian kernel is much faster than the Kronecker kernel, and at the same time, competitive with the Kronecker kernel in predictive performance.
Giordano SPADACINI Sergio A. PIGNARI
This work presents a statistical model for the radiated susceptibility (RS) of an unshielded twisted-wire pair (TWP) running above ground, illuminated by a random electromagnetic field. The incident field is modeled as a superposition of elemental plane waves with random angular density, phase, and polarization. The statistical properties of both the differential-mode (DM) and the common-mode (CM) noise voltages induced across the terminal loads are derived and discussed.
Aya COMUTA Mitsuru KAWAZOE Tetsuya TAKAHASHI Isamu YOSHIZAWA
An explicit construction of pairing-friendly hyperelliptic curves with ordinary Jacobians was firstly given by D. Freeman for the genus two case. In this paper, we give an explicit construction of pairing-friendly hyperelliptic curves of genus two and four with ordinary Jacobians based on the closed formulae for the order of the Jacobian of special hyperelliptic curves. For the case of genus two, we prove the closed formula for curves of type y2=x5+c. By using the formula, we develop an analogue of the Cocks-Pinch method for curves of type y2=x5+c. For the case of genus four, we also develop an analogue of the Cocks-Pinch method for curves of type y2=x9+cx. In particular, we construct the first examples of pairing-friendly hyperelliptic curves of genus four with ordinary Jacobians.
This paper extends the Brezing-Weng method by parameterizing the discriminant D by a polynomial D(x). To date, the maximum of CM discriminant can be adequately addressed is about 14-digits. Thus the degree of the square free part of D(x) has to be sufficiently small. By making the square free part of D(x) a linear monomial, the degree of the square free part is small and by substituting x to some quadratic monomial, pairing-friendly curves with various discriminants can be constructed. In order that a square free part of D(x) is of the form ax, ax has to be a square element as a polynomial representation in a number field. Two methods are introduced to apply this construction. For k = 5, 8, 9, 15, 16, 20, 24 and 28, the proposed method gives smaller ρ value than those in previous studies.
Ha X. NGUYEN Ha H. NGUYEN Tho LE-NGOC
A stochastic quasi-gradient algorithm is applied to design linear dispersion (LD) codes for two-way wireless relay networks under Rayleigh fading channels. The codes are designed to minimize an upper bound of the average pairwise error probability. Simulation results show that the codes obtained by the optimization technique achieve a coding gain over codes that are randomly generated based on the isotropic distribution.
Mingchih CHEN Syouji NAKAMURA Toshio NAKAGAWA
This paper considers replacement and maintenance policies for an operating unit which works at random times for jobs. The unit undergoes minimal repairs at failures and is replaced at a planned time T or at a number N of working times, whichever occurs first. The expected cost rate is obtained, and an optimal policy which minimizes it is derived analytically. The imperfect preventive maintenance (PM) model, where the unit is improved by PM after the completion of each working time, is analyzed. Furthermore, when the work of a job incurs some damage to the unit, the replacement model with number N is proposed. The expected cost rate is obtained by using theory of cumulative processes. Two modified models, where the unit is replaced at number N or at the first completion of the working time over time T, and it is replaced at T or number N, whichever occurs last, are also proposed. Finally, when the unit is replaced at time T, number N or Kth failure, whichever occurs first, the expected cost rate is also obtained.
Maki YOSHIDA Shigeo MITSUNARI Toru FUJIWARA
This paper introduces a new computational problem on a two-dimensional vector space, called the vector decomposition problem (VDP), which is mainly defined for designing cryptosystems using pairings on elliptic curves. We first show a relation between the VDP and the computational Diffie-Hellman problem (CDH). Specifically, we present a sufficient condition for the VDP on a two-dimensional vector space to be at least as hard as the CDH on a one-dimensional subspace. We also present a sufficient condition for the VDP with a fixed basis to have a trapdoor. We then give an example of vector spaces which satisfy both sufficient conditions and on which the CDH is assumed to be hard in previous work. In this sense, the intractability of the VDP is a reasonable assumption as that of the CDH.
Toru NAKANISHI Hiroki FUJII Yuta HIRA Nobuo FUNABIKI
Lots of revocable group signature schemes have been proposed so far. In one type of revocable schemes, signing and/or verifying algorithms have O(N) or O(R) complexity, where N is the group size and R is the number of revoked members. On the other hand, in Camenisch-Lysyanskaya scheme and the followers, signing and verifying algorithms have O(1) complexity. However, before signing, the updates of the secret key are required. The complexity is O(R) in the worst case. In this paper, we propose a revocable scheme with signing and verifying of O(1) complexity, where any update of secret key is not required. The compensation is the long public key of O(N). In addition, we extend it to the scheme with O()-size public key, where signing and verifying have constant extra costs.
We propose a novel adaptive segment repair mechanism to improve traditional MPLS (Multi-Protocol Label Switching) failure recovery. The proposed mechanism protects one or more contiguous high failure probability links by dynamic setup of segment protection. Simulations demonstrate that the proposed mechanism reduces failure recovery time while also increasing network resource utilization.
Takehito SUZUKI Jiro HIROKAWA Makoto ANDO
This paper presents the analysis and design of a reflection-cancelling transverse slot-pair array antenna with baffles by using the Spectrum of Two-Dimensional Solutions (S2DS) method. For the transverse slot array, the slot spacings with more than one free-space wavelength cause the grating-lobes. The baffles suppress the grating-lobes effectively. A one-dimensional slot array is extracted from the 2D array with in-phase excitation by assuming periodicity in the transversal direction. The uniform excitation over the finite array is synthesized iteratively to demonstrate the fast and accurate results by S2DS. A unit design model with the baffles is introduced to determine the initial parameters of the slot-pairs, which greatly accelerate the iterations process. Experiments at 25.3 GHz demonstrate the suppression of the grating lobes to the level less than -20.0 dB and also the good uniformity of the aperture field distribution.
Keiichirou KUSAKARI Yasuo ISOGAI Masahiko SAKAI Frederic BLANQUI
Higher-order rewrite systems (HRSs) and simply-typed term rewriting systems (STRSs) are computational models of functional programs. We recently proposed an extremely powerful method, the static dependency pair method, which is based on the notion of strong computability, in order to prove termination in STRSs. In this paper, we extend the method to HRSs. Since HRSs include λ-abstraction but STRSs do not, we restructure the static dependency pair method to allow λ-abstraction, and show that the static dependency pair method also works well on HRSs without new restrictions.
Waiyawut SANAYHA Yuttapong RANGSANSERI
In this paper, we propose a novel image projection technique for face recognition applications based on Fisher Linear Discriminant Analysis (LDA). The projection is performed through a couple subspace analysis for overcoming the "small sample size" problem. Also, weighted pairwise discriminant hyperplanes are used in order to provide a more accurate discriminant decision than that produced by the conventional LDA. The proposed technique has been successfully tested on three face databases. Experimental results indicate that the proposed algorithm outperforms the conventional algorithms.
Yasuyuki NOGAMI Yumi SAKEMI Hidehiro KATO Masataka AKANE Yoshitaka MORIKAWA
It is said that the lower bound of the number of iterations of Miller's algorithm for pairing calculation is log 2r/(k), where () is the Euler's function, r is the group order, and k is the embedding degree. Ate pairing reduced the number of the loops of Miller's algorithm of Tate pairing from ⌊log 2r⌋ to ⌊ log 2(t-1)⌋, where t is the Frobenius trace. Recently, it is known to systematically prepare a pairing-friendly elliptic curve whose parameters are given by a polynomial of integer variable "χ." For such a curve, this paper gives integer variable χ-based Ate (Xate) pairing that achieves the lower bound. In the case of the well-known Barreto-Naehrig pairing-friendly curve, it reduces the number of loops to ⌊log 2χ⌋. Then, this paper optimizes Xate pairing for Barreto-Naehrig curve and shows its efficiency based on some simulation results.