Hiromitsu AWANO Tadayuki ICHIHASHI Makoto IKEDA
An ASIC crypto processor optimized for the 254-bit prime-field optimal-ate pairing over Barreto-Naehrig (BN) curve is proposed. The data path of the proposed crypto processor is designed to compute five Fp2 operations, a multiplication, three addition/subtractions, and an inversion, simultaneously. We further propose a design methodology to automate the instruction scheduling by using a combinatorial optimization solver, with which the total cycle count is reduced to 1/2 compared with ever reported. The proposed crypto processor is designed and fabricated by using a 65nm silicon-on-thin-box (SOTB) CMOS process. The chip measurement result shows that the fabricated chip successfully computes a pairing in 0.185ms when a typical operating voltage of 1.20V is applied, which corresponds to 2.8× speed up compared to the current state-of-the-art pairing implementation on ASIC platform.
Jung-Hyun KIM Min Kyu SONG Hong-Yeop SONG
In this paper, we investigate how to obtain binary locally repairable codes (LRCs) with good locality and availability from binary Simplex codes. We first propose a Combination code having the generator matrix with all the columns of positive weights less than or equal to a given value. Such a code can be also obtained by puncturing all the columns of weights larger than a given value from a binary Simplex Code. We call by block-puncturing such puncturing method. Furthermore, we suggest a heuristic puncturing method, called subblock-puncturing, that punctures a few more columns of the largest weight from the Combination code. We determine the minimum distance, locality, availability, joint information locality, joint information availability of Combination codes in closed-form. We also demonstrate the optimality of the proposed codes with certain choices of parameters in terms of some well-known bounds.
Locally repairable codes, which can repair erased symbols from other symbols, have attracted a good deal of attention in recent years because its local repair property is effective on distributed storage systems. (ru, δu)u∈[s]-locally repairable codes with multiple localities, which are an extension of ordinary locally repairable codes, can repair δu-1 erased symbols simultaneously from a set consisting of at most ru symbols. An upper bound on the minimum distance of these codes and a construction method of optimal codes, attaining this bound with equality, were given by Chen, Hao, and Xia. In this paper, we discuss the parameter restrictions of the existing construction, and we propose explicit constructions of optimal codes with multiple localities with relaxed restrictions based on the encoding polynomial introduced by Tamo and Barg. The proposed construction can design a code whose minimum distance is unrealizable by the existing construction.
A b-symbol read channel is a channel model in which b consecutive symbols are read at once. As special cases, it includes a symbol-pair read channel (b=2) and an ordinary channel (b=1). The sphere packing bound, the Gilbert-Varshamov (G-V) bound, and the asymptotic G-V bound for symbol-pair read channels are known for b=1 and 2. In this paper, we derive these three bounds for b-symbol read channels with b≥1. From analysis of the proposed G-V bound, it is confirmed that the achievable rate is higher for b-symbol read channels compared with those for ordinary channels based on the Hamming metric. Furthermore, it is shown that the optimal value of b that maximizes the asymptotic G-V bound is finitely determined depending on the fractional minimum distance.
Kotoko YAMADA Nuttapong ATTRAPADUNG Keita EMURA Goichiro HANAOKA Keisuke TANAKA
Attribute-based encryption (ABE), a cryptographic primitive, realizes fine-grained access control. Because of its attractive functionality, many systems based on ABE have been constructed to date. In such cryptographic systems, revocation functionality is indispensable to handle withdrawal of users, secret key exposure, and others. Although many ABE schemes with various functionalities have been proposed, only a few of these are revocable ABE (RABE). In this paper, we propose two generic constructions of RABE from ABE. Our first construction employs the pair encoding framework (Attrapadung, EUROCRYPT 2014), and combines identity-based revocation and ABE via the generic conjunctive conversion of Attrapadung and Yamada (CT-RSA 2015). Our second construction converts ABE to RABE directly when ABE supports Boolean formulae. Because our constructions preserve functionalities of the underlying ABE, we can instantiate various fully secure RABE schemes for the first time, e.g., supporting regular languages, with unbounded attribute size and policy structure, and with constant-size ciphertext and secret key.
Nii L. SOWAH Qingbo WU Fanman MENG Liangzhi TANG Yinan LIU Linfeng XU
In this paper, we improve upon the accuracy of existing tracklet generation methods by repairing tracklets based on their quality evaluation and detection propagation. Starting from object detections, we generate tracklets using three existing methods. Then we perform co-tracklet quality evaluation to score each tracklet and filtered out good tracklet based on their scores. A detection propagation method is designed to transfer the detections in the good tracklets to the bad ones so as to repair bad tracklets. The tracklet quality evaluation in our method is implemented by intra-tracklet detection consistency and inter-tracklet detection completeness. Two propagation methods; global propagation and local propagation are defined to achieve more accurate tracklet propagation. We demonstrate the effectiveness of the proposed method on the MOT 15 dataset
Warunya WUNNASRI Jaruwat PAILAI Yusuke HAYASHI Tsukasa HIRASHIMA
Collaborative learning is an active teaching and learning strategy, in which learners who give each other elaborated explanations can learn most. However, it is difficult for learners to explain their own understanding elaborately in collaborative learning. In this study, we propose a collaborative use of a Kit-Build concept map (KB map) called “Reciprocal KB map”. In a Reciprocal KB map for a pair discussion, at first, the two participants make their own concept maps expressing their comprehension. Then, they exchange the components of their maps and request each other to reconstruct their maps by using the components. The differences between the original map and the reconstructed map are diagnosed automatically as an advantage of the KB map. Reciprocal KB map is expected to encourage pair discussion to recognize the understanding of each other and to create an effective discussion. In an experiment reported in this paper, Reciprocal KB map was used for supporting a pair discussion and was compared with a pair discussion which was supported by a traditional concept map. Nineteen pairs of university students were requested to use the traditional concept map in their discussion, while 20 pairs of university students used Reciprocal KB map for discussing the same topic. The results of the experiment were analyzed using three metrics: a discussion score, a similarity score, and questionnaires. The discussion score, which investigates the value of talk in discussion, demonstrates that Reciprocal KB map can promote more effective discussion between the partners compared to the traditional concept map. The similarity score, which evaluates the similarity of the concept maps, demonstrates that Reciprocal KB map can encourage the pair of partners to understand each other better compared to the traditional concept map. Last, the questionnaires illustrate that Reciprocal KB map can support the pair of partners to collaborate in the discussion smoothly and that the participants accepted this method for sharing their understanding with each other. These results suggest that Reciprocal KB map is a promising approach for encouraging pairs of partners to understand each other and to promote the effective discussions.
Lianfei LUO Wenping MA Feifei ZHAO
Let Fpm be the field of pm elements where p is an odd prime. In this letter, binary sequence pairs of period N=pm-1 are presented, where sequences are generated from the polynomial x2-c for any c Fpm{0}. The cross-correlation values of sequence pairs are completely determined, our results show that those binary sequence pairs have optimal three-level correlation.
Donggu KIM Hoojin LEE Joonhyuk KANG
This paper derives highly accurate and effective closed-form formulas for the average upper bound on the pairwise error probability (PEP) of the multi-carrier index keying orthogonal frequency division multiplexing (MCIK-OFDM) system with low-complexity detection (i.e., greedy detection) in two-wave with diffuse power (TWDP) fading channels. To be specific, we utilize an exact moment generating function (MGF) of the signal-to-noise ratio (SNR) under TWDP fading to guarantee highly precise investigations of error probability performance; existing formulas for average PEP employ the approximate probability density function (PDF) of the SNR for TWDP fading, thereby inducing inherent approximation error. Moreover, some special cases of TWDP fading are also considered. To quantitatively reveal the achievable modulation gain and diversity order, we further derive asymptotic formulas for the upper bound on the average PEP. The obtained asymptotic expressions can be used to rapidly estimate the achievable error performance of MCIK-OFDM with the greedy detection over TWDP fading in high SNR regimes.
We have previously introduced the static dependency pair method that proves termination by analyzing the static recursive structure of various extensions of term rewriting systems for handling higher-order functions. The key is to succeed with the formalization of recursive structures based on the notion of strong computability, which is introduced for the termination of typed λ-calculi. To bring the static dependency pair method close to existing functional programs, we also extend the method to term rewriting models in which functional abstractions with patterns are permitted. Since the static dependency pair method is not sound in general, we formulate a class; namely, accessibility, in which the method works well. The static dependency pair method is a very natural reasoning; therefore, our extension differs only slightly from previous results. On the other hand, a soundness proof is dramatically difficult.
Hongbin LIN Xiuping PENG Chao FENG Qisheng TONG Kai LIU
The concept of Gaussian integer sequence pair is generalized from a single Gaussian integer sequence. In this letter, by adopting cyclic difference set pairs, a new construction method for perfect Gaussian integer sequence pairs is presented. Furthermore, the necessary and sufficient conditions for constructing perfect Gaussian integer sequence pairs are given. Through the research in this paper, a large number of perfect Gaussian integer sequence pairs can be obtained, which can greatly extend the existence of perfect sequence pairs.
Xiumin SHEN Yanguo JIA Xiaofei SONG Yubo LI
In this paper, a new generalized cyclotomy over Zpq is presented based on cyclotomy and Chinese remainder theorem, where p and q are different odd primes. Several new construction methods for binary sequence pairs of period pq with ideal two-level correlation are given by utilizing these generalized cyclotomic classes. All the binary sequence pairs from our constructions have both ideal out-of-phase correlation values -1 and optimum balance property.
Yulong SHANG Hojun KIM Hosung PARK Taejin JUNG
The conventional generalized spatial modulation (GSM) simultaneously activates multiple transmit antennas in order to improve the spectral efficiency of the original SM. In this letter, to lessen the hardware burden of the multiple RF chains, we provide a new scheme that is designed by combining the GSM scheme using only two active antennas with quaternary quasi-orthogonal sequences of a length of two. Compared with the other SM schemes, the proposed scheme has significant benefits in average error performances and/or their hardware complexities of the RF systems.
Zhi ZHENG Yuxuan YANG Wen-Qin WANG Guangjun LI Jiao YANG Yan GE
This paper proposes a novel method for two-dimensional (2-D) direction-of-arrival (DOA) estimation of multiple signals employing a sparse L-shaped array structured by a sparse linear array (SLA), a sparse uniform linear array (SULA) and an auxiliary sensor. In this method, the elevation angles are estimated by using the SLA and an efficient search approach, while the azimuth angle estimation is performed in two stages. In the first stage, the rough azimuth angle estimates are obtained by utilizing a noise-free cross-covariance matrix (CCM), the estimated elevation angles and data from three sensors including the auxiliary sensor. In the second stage, the fine azimuth angle estimates can be achieved by using the shift-invariance property of the SULA and the rough azimuth angle estimates. Without extra pair-matching process, the proposed method can achieve automatic pairing of the 2-D DOA estimates. Simulation results show that our approach outperforms the compared methods, especially in the cases of low SNR, snapshot deficiency and multiple sources.
A new method is proposed for the construction of pairing-friendly elliptic curves. For any fixed embedding degree, it can transform the problem to solving equation systems instead of exhaustive searching, thus it's more targeted and efficient. Via this method, we obtain various families including complete families, complete families with variable discriminant and sparse families. Specifically, we generate a complete family with important application prospects which has never been given before as far as we know.
Makoto TAKITA Masanori HIROTOMO Masakatu MORII
Symbol-pair read channels output overlapping pairs of symbols in storage applications. Pair distance and pair error are used in the channels. In this paper, we discuss error-trapping decoding for cyclic codes over symbol-pair read channels. By putting some restrictions on the correctable pair error patterns, we propose a novel error-trapping decoding algorithm over the channels and show a circuitry for implementing the decoding algorithm. In addition, we discuss how to modify the restrictions on the correctable pair error patterns.
Hojun KIM Yulong SHANG Taejin JUNG
In this paper, we propose a new spatial modulation (SM) scheme based on quaternary quasi-orthogonal sequences (Q-QOSs), referred to as Q-QOS-SM. First, the conventional SM and generalized-SM (GSM) schemes are reinterpreted as a new transmission scheme based on a spatial modulation matrix (SMM), whose column indices are used for the mapping of spatial-information bits unlike the conventional ones. Next, by adopting the SMM comprising the Q-QOSs, the proposed Q-QOS-SM that guarantees twice the number of spatial bits at a transmitter compared with the SM with a constraint of transmit antennas, is designed. From the computer-simulation results, the Q-QOS-SM is shown to achieve a greatly improved throughput compared with the conventional SM and GSM schemes, especially, for a large number of the receive antennas. This finding is mainly because the new scheme offers a much higher minimum Euclidean distance than the other schemes.
Yohei NAKAZAWA Hideo MAKINO Kentaro NISHIMORI Daisuke WAKATSUKI Makoto KOBAYASHI Hideki KOMAGATA
In this paper, we propose a precise indoor localization method using visible light communication (VLC) with dual-facing cameras on a smart device (mobile phone, smartphone, or tablet device). This approach can assist the visually impaired with navigation, or provide mobile-robot control. The proposed method is different from conventional techniques in that dual-facing cameras are used to expand the localization area. The smart device is used as the receiver, and light-emitting diodes on the ceiling are used as localization landmarks. These are identified by VLC using a rolling shutter effect of complementary metal-oxide semiconductor image sensors. The front-facing camera captures the direct incident light of the landmarks, while the rear-facing camera captures mirror images of landmarks reflected from the floor face. We formulated the relationship between the poses (position and attitude) of the two cameras and the arrangement of landmarks using tilt detection by the smart device accelerometer. The equations can be analytically solved with a constant processing time, unlike conventional numerical methods, such as least-squares. We conducted a simulation and confirmed that the localization area was 75.6% using the dual-facing cameras, which was 3.8 times larger than that using only the front-facing camera. As a result of the experiment using two landmarks and a tablet device, the localization error in the horizontal direction was less than 98 mm at 90% of the measurement points. Moreover, the error estimation index can be used for appropriate route selection for pedestrians.
Ruipan YANG Ruihu LI Luobin GUO Qiang FU
Locally repairable code (LRC) can recover any codeword symbol failure by accessing a small number of other symbols, which can increase the efficiency during the repair process. In a distributed storage system with locally repairable codes, any node failure can be rebuilt by accessing other fixed nodes. It is a promising prospect for the application of LRC. In this paper, some methods of constructing matrices which can generate codes with small locality will be proposed firstly. By analyzing the parameters, we construct the generator matrices of the best-known ternary linear codes of dimension 6, using methods such as shortening, puncturing and expansion. After analyzing the linear dependence of the column vectors in the generator matrices above, we find out the locality of the codes they generate. Many codes with small locality have been found.
Asymmetric bilinear maps using Type-3 pairings are known to be advantageous in several points (e.g., the speed and the size of a group element) to symmetric bilinear maps using Type-1 pairings. Kremer and Mazaré introduce a symbolic model to analyze protocols based on bilinear maps, and show that the symbolic model is computationally sound. However, their model only covers symmetric bilinear maps. In this paper, we propose a new symbolic model to capture asymmetric bilinear maps. Our model allows us to analyze security of various protocols based on asymmetric bilinear maps (e.g., Joux's tripartite key exchange, and Scott's client-server ID-based key exchange). Also, we show computational soundness of our symbolic model under the decisional bilinear Diffie-Hellman assumption.