Tsutomu INAMOTO Yoshinobu HIGAMI
In this paper, we aim to develop technologies for the circuit fault diagnosis and propose a formulation of a measure of a test pattern for the circuit fault diagnosis. Given a faulty circuit, the fault diagnosis is to deduce locations of faults that had occurred in the circuit. The fault diagnosis is executed in software before the failure analysis by which engineers inspect physical defects, and helps to improve the manufacturing process which yielded faulty circuits. The heart of the fault diagnosis is to distinguish between candidate faults by using test patterns, which are applied to the circuit-under-diagnosis (CUD), and thus test patterns that can distinguish as many faults as possible need to be generated. This fact motivates us to consider the test pattern measure based on the number of fault-pairs that become distinguished by a test pattern. To the best of the authors' knowledge, that measure requires the computational time of complexity order O(NF2), where NF denotes the number of candidate faults. Since NF is generally large for real industrial circuits, the computational time of the measure is long even when a high-performance computer is used. The formulation proposed in this paper makes it possible to calculate the measure in the computational complexity of O(NF log NF), and thus that measure is useful for the test pattern selection in the fault diagnosis. In computational experiments, the effectiveness of the formulation is demonstrated as samples of computational times of the measure calculated by the traditional and the proposed formulae and thorough comparisons between several greedy heuristics which are based on the measure.
Yoshiki KAYANO Yoshio KAMI Fengchao XIAO
For actual multi-channel differential signaling system, the ideal balance or symmetrical topology cannot be established, and hence, an imbalance component is excited. However a theoretical analysis method of evaluating the voltage and current distribution on the differential-paired lines, which allows to anticipate EM radiation at the design stage and to study possible means for suppressing imbalance components, has not been implemented. To provide the basic considerations for electromagnetic (EM) radiation from practical asymmetrical differential-paired lines structure with equi-length routing used in high-speed board design, this paper newly proposes an analytical method for evaluating the voltage and current at any point on differential-paired lines by expressing the differential paired-lines with an equivalent source circuit and an equivalent load circuit. The proposed method can predict S-parameters, distributions of voltage and current and EM radiation with sufficient accuracy. In addition, the proposed method provides enough flexibility for different geometric parameters and can be used to develop physical insights and design guidelines. This study has successfully established a basic method to effectively predict signal integrity and EM interference issues on a differential-paired lines.
Shimpei SATO Kano AKAGI Atsushi TAKAHASHI
Routing problems derived from silicon-interposer and etc. are often formulated as a set-pair routing problem where the combination of pin-pairs to be connected is flexible. In this routing problem, a length matching routing pattern is often required due to the requirement of the signal propagation delays be the same. We propose a fast length matching routing method for the set-pair routing problem. The existing algorithm generates a good length matching routing pattern in practical time. However, due to the limited searching range, there are length matching routing patterns that cannot find due to the limited searching range of the algorithm. Also, it needs heavy iterative steps to improve a solution, and the computation time is practical but not fast. In the set-pair routing, although pin-pairs to be connected is flexible, it is expected that combinations of pin-pairs which realize length matching are restricted. In our method, such a combination of pin-pairs is selected in advance, then routing is performed to realize the connection of the selected pin-pairs. Heavy iterative steps are not used for both the selection and the routing, then a routing pattern is generated in a short time. In the experiments, we confirm that the quality of routing patterns generated by our method is almost equivalent to the existing algorithm. Furthermore, our method finds length matching routing patterns that the existing algorithm cannot find. The computation time is about 360 times faster than the existing algorithm.
Takanori ISOBE Kyoji SHIBUTANI
In this paper, we explore the security of single-key Even-Mansour ciphers against key-recovery attacks. First, we introduce a simple key-recovery attack using key relations on an n-bit r-round single-key Even-Mansour cipher (r-SEM). This attack is feasible with queries of DTr=O(2rn) and $2^{rac{2r}{r + 1}n}$ memory accesses, which is $2^{rac{1}{r + 1}n}$ times smaller than the previous generic attacks on r-SEM, where D and T are the number of queries to the encryption function EK and the internal permutation P, respectively. Next, we further reduce the time complexity of the key recovery attack on 2-SEM by a start-in-the-middle approach. This is the first attack that is more efficient than an exhaustive key search while keeping the query bound of DT2=O(22n). Finally, we leverage the start-in-the-middle approach to directly improve the previous attacks on 2-SEM by Dinur et al., which exploit t-way collisions of the underlying function. Our improved attacks do not keep the bound of DT2=O(22n), but are the most time-efficient attacks among the existing ones. For n=64, 128 and 256, our attack is feasible with the time complexity of about $2^{n} cdot rac{1}{2 n}$ in the chosen-plaintext model, while Dinur et al.'s attack requires $2^{n} cdot rac{{ m log}(n)}{ n} $ in the known-plaintext model.
Tashpolat NIZAMIDIN Li ZHAO Ruiyu LIANG Yue XIE Askar HAMDULLA
As one of the popular topics in the field of human-computer interaction, the Speech Emotion Recognition (SER) aims to classify the emotional tendency from the speakers' utterances. Using the existing deep learning methods, and with a large amount of training data, we can achieve a highly accurate performance result. Unfortunately, it's time consuming and difficult job to build such a huge emotional speech database that can be applicable universally. However, the Siamese Neural Network (SNN), which we discuss in this paper, can yield extremely precise results with just a limited amount of training data through pairwise training which mitigates the impacts of sample deficiency and provides enough iterations. To obtain enough SER training, this study proposes a novel method which uses Siamese Attention-based Long Short-Term Memory Networks. In this framework, we designed two Attention-based Long Short-Term Memory Networks which shares the same weights, and we input frame level acoustic emotional features to the Siamese network rather than utterance level emotional features. The proposed solution has been evaluated on EMODB, ABC and UYGSEDB corpora, and showed significant improvement on SER results, compared to conventional deep learning methods.
Locally repairable codes (LRCs) with locality r and availability t are a class of codes which can recover data from erasures by accessing other t disjoint repair groups, that every group contain at most r other code symbols. This letter will investigate constructions of LRCs derived from cyclic codes and generalized quadrangle. On the one hand, two classes of cyclic LRC with given locality m-1 and availability em are proposed via trace function. Our LRCs have the same locality, availability, minimum distance and code rate, but have short length and low dimension. On the other hand, an LRC with $(2,(p+1)lfloorrac{s}{2} floor)$ is presented based on sets of points in PG(k, q) which form generalized quadrangles with order (s, p). For k=3, 4, 5, LRCs with r=2 and different t are determined.
Gengxin NING Shenjie JIANG Xuejin ZHAO Cui YANG
This paper presents a two-dimensional (2D) DOA algorithm for double L-shaped arrays. The algorithm is applied to the underwater environment for eliminating the performance error caused by the sound speed uncertainty factor. By introducing the third dimensional array, the algorithm eliminates the sound velocity variable in the depression angle expression, so that the DOA estimation no longer considering the true value of unknown sound velocity. In order to determine the parameters of a three-dimensional array, a parameter matching method with the double L-shaped array is also proposed. Simulations show that the proposed algorithm outperforms the conventional 2D-DOA estimation algorithm in unknown sound velocity environment.
Fanxin ZENG Xiping HE Guixin XUAN Zhenyu ZHANG Yanni PENG Li YAN
In an OFDM communication system using quadrature amplitude modulation (QAM) signals, peak envelope powers (PEPs) of the transmitted signals can be well controlled by using QAM Golay complementary sequence pairs (CSPs). In this letter, by making use of a new construction, a family of new 16-QAM Golay CSPs of length N=2m (integer m≥2) with binary inputs is presented, and all the resultant pairs have the PEP upper bound 2N. However, in the existing such pairs from other references their PEP upper bounds can arrive at 3.6N when the worst case happens. In this sense, novel pairs are good candidates for OFDM applications.
Satoshi MIZUTANI Xufeng ZHAO Toshio NAKAGAWA
When a unit repeats some works over again and undergoes minimal repairs at failures, it is more practical to replace it preventively at the end of working cycles or at its failure times. In this case, it would be an interesting problem to know which is better to replace the unit at a number of working cycles or at random failures from the point of cost. For this purpose, we give models of the expected cost rates for the following replacement policies: (1) The unit is replaced at a working cycle N and at a failure number K, respectively; (2) Replacement first and last policies with working cycle N and failure number K, respectively; (3) Replacement overtime policies with working cycle N and failure number K, respectively. Optimizations and comparisons of the policies for N and K are made analytically and numerically.
Junichi TOMIDA Masayuki ABE Tatsuaki OKAMOTO
Inner product functional encryption (IPFE) is a subclass of functional encryption (FE), whose function class is limited to inner product. We construct an efficient private-key IPFE scheme with full-hiding security, where confidentiality is assured for not only encrypted data but also functions associated with secret keys. Recently, Datta et al. presented such a scheme in PKC 2016 and this is the only scheme that achieves full-hiding security. Our scheme has an advantage over their scheme for the two aspects. More efficient: keys and ciphertexts of our scheme are almost half the size of those of their scheme. Weaker assumption: our scheme is secure under the k-linear (k-Lin) assumption, while their scheme is secure under a stronger assumption, namely, the symmetric external Diffie-Hellman (SXDH) assumption. It is well-known that the k-Lin assumption is equivalent to the SXDH assumption when k=1 and becomes weak as k increases.
Yuu AIKOU Shahidatul SADIAH Toru NAKANISHI
In conventional ID-based user authentications, privacy issues may occur, since users' behavior histories are collected in Service Providers (SPs). Although anonymous authentications such as group signatures have been proposed, these schemes rely on a Trusted Third Party (TTP) capable of tracing misbehaving users. Thus, the privacy is not high, because the TTP of tracing authority can always trace users. Therefore, the anonymous credential system using a blacklist without the TTP of tracing authority has been proposed, where blacklisted anonymous users can be blocked. Recently, an RSA-based blacklistable anonymous credential system with efficiency improvement has been proposed. However, this system still has an efficiency problem: The data size in the authentication is O(K'), where K' is the maximum number of sessions in which the user can conduct. Furthermore, the O(K')-size data causes the user the computational cost of O(K') exponentiations. In this paper, a blacklistable anonymous credential system using a pairing-based accumulator is proposed. In the proposed system, the data size in the authentication is constant for parameters. Although the user's computational cost depends on parameters, the dependent cost is O(δBL·K) multiplications, instead of exponentiations, where δBL is the number of sessions added to the blacklist after the last authentication of the user, and K is the number of past sessions of the user. The demerit of the proposed system is O(n)-size public key, where n corresponds to the total number of all sessions of all users in the system. But, the user only has to download the public key once.
In ID-based user authentications, a privacy problem can occur, since the service provider (SP) can accumulate the user's access history from the user ID. As a solution to that problem, group signatures have been researched. One of important issues in the group signatures is the user revocation. Previously, an efficient revocable scheme with signing/verification of constant complexity was proposed by Libert et al. In this scheme, users are managed by a binary tree, and a list of data for revoked users, called a revocation list (RL), is used for revocation. However, the scheme suffers from the large RL. Recently, an extended scheme has been proposed by Sadiah and Nakanishi, where the RL size is reduced by compressing RL. On the other hand, there is a problem that some overhead occurs in the authentication as a price for reducing the size of RL. In this paper, we propose an extended scheme where the authentication is speeded up by reducing the number of Groth-Sahai (GS) proofs. Furthermore, we implemented it on a PC to show the effectiveness. The verification time is about 30% shorter than that of the previous scheme by Sadiah and Nakanishi.
Min ZHANG Bo XU Xiaoyun LI Dong FU Jian LIU Baojian WU Kun QIU
The capacity of optical transport networks has been increasing steadily and the networks are becoming more dynamic, complex, and transparent. Though it is common to use worst case assumptions for estimating the quality of transmission (QoT) in the physical layer, over provisioning results in high margin requirements. Accurate estimation on the QoT for to-be-established lightpaths is crucial for reducing provisioning margins. Machine learning (ML) is regarded as one of the most powerful methodological approaches to perform network data analysis and enable automated network self-configuration. In this paper, an artificial neural network (ANN) framework, a branch of ML, to estimate the optical signal-to-noise ratio (OSNR) of to-be-established lightpaths is proposed. It takes account of both nonlinear interference between spectrum neighboring channels and optical monitoring uncertainties. The link information vector of the lightpath is used as input and the OSNR of the lightpath is the target for output of the ANN. The nonlinear interference impact of the number of neighboring channels on the estimation accuracy is considered. Extensive simulation results show that the proposed OSNR estimation scheme can work with any RWA algorithm. High estimation accuracy of over 98% with estimation errors of less than 0.5dB can be achieved given enough training data. ANN model with R=4 neighboring channels should be used to achieve more accurate OSNR estimates. Based on the results, it is expected that the proposed ANN-based OSNR estimation for new lightpath provisioning can be a promising tool for margin reduction and low-cost operation of future optical transport networks.
The Gabidulin-based locally repairable code (LRC) construction by Silberstein et al. is an important example of distance optimal (r,δ)-LRCs. Its distance optimality has been further shown to cover the case of multiple (r,δ)-locality, where the (r,δ)-locality constraints are different among different symbols. However, the optimality only holds under the ordered (r,δ) condition, where the parameters of the multiple (r,δ)-locality satisfy a specific ordering condition. In this letter, we show that Gabidulin-based LRCs are still distance optimal even without the ordered (r,δ) condition.
Masayuki ABE Fumitaka HOSHINO Miyako OHKUBO
We propose a simple framework for evaluating the performance of pairing-based cryptographic schemes for various types of curves and parameter settings. The framework, which we call ‘Opcount’, enables the selection of an appropriate curve and parameters by estimating the performance of a cryptographic scheme from a pseudo-code describing the cryptographic scheme and an implementation-information database that records the performance of basic operations in curves targeted for evaluation. We apply Opcount to evaluate and compare the computational efficiency of several structure-preserving signature schemes that involve tens of pairing products in their signature verification. In addition to showing the usefulness of Opcount, our experiments also reveal the overlooked importance of taking account of the properties of underlying curves when optimizing computations and demonstrate the impact of tight security reductions.
Tao WANG Mingfang WANG Yating WU Yanzan SUN
This paper proposes an energy efficiency (EE) maximized resource allocation (RA) algorithm in orthogonal frequency division multiple access (OFDMA) downlink networks with multiple relays, where a novel opportunistic subcarrier pair based decode-and-forward (DF) protocol with beamforming is used. Specifically, every data transmission is carried out in two consecutive time slots. During every transmission, multiple parallel paths, including relayed paths and direct paths, are established by the proposed RA algorithm. As for the protocol, each subcarrier in the 1st slot can be paired with any subcarrier in 2nd slot to best utilize subcarrier resources. Furthermore, for each relayed path, multiple (not just single or all) relays can be chosen to apply beamforming at the subcarrier in the 2nd slot. Each direct path is constructed by an unpaired subcarrier in either the 1st or 2nd slot. In order to guarantee an acceptable spectrum efficiency, we also introduce a minimum rate constraint. The EE-maximized problem is a highly nonlinear optimization problem, which contains both continuous, discrete variables and has a fractional structure. To solve the problem, the best relay set and resource allocation for a relayed path are derived first, then we design an iterative algorithm to find the optimal RA for the network. Finally, numerical experiments are taken to demonstrate the effectiveness of the proposed algorithm, and show the impact of minimum rate requirement, user number and circuit power on the network EE.
Minhwan CHOI Hoojin LEE Haewoon NAM
This letter presents a comprehensive analytical framework for average pairwise error probability (PEP) of decode-and-forward cooperative network based on various distributed space-time block codes (DSTBCs) with antenna switching (DDF-AS) technique over quasi-static Rayleigh fading channels. Utilizing the analytical framework, exact and asymptotic PEP expressions can be effectively formulated, which are based on the Lauricella multiplicative hypergeometric function, when various DSTBCs are adopted for the DDF-AS system. The derived asymptotic PEP formulas and some numerical results enable us to verify that the DDF-AS scheme outperforms the conventional cooperative schemes in terms of error rate performance. Furthermore, the asymptotic PEP formulas can also provide explicit and useful insights into the full diversity transmission achieved by the DDF-AS system.
We introduce a notion of watermarking for cryptographic functions and propose a concrete scheme for watermarking cryptographic functions. Informally speaking, a digital watermarking scheme for cryptographic functions embeds information, called a mark, into functions such as one-way functions and decryption functions of public-key encryption. There are two basic requirements for watermarking schemes. A mark-embedded function must be functionally equivalent to the original function. It must be difficult for adversaries to remove the embedded mark without damaging the original functionality. In spite of its importance and usefulness, there have only been a few theoretical works on watermarking for functions (or programs). Furthermore, we do not have rigorous definitions of watermarking for cryptographic functions and concrete constructions. To solve the problem above, we introduce a notion of watermarking for cryptographic functions and define its security. Furthermore, we present a lossy trapdoor function (LTF) based on the decisional bilinear Diffie-Hellman problem problem and a watermarking scheme for the LTF. Our watermarking scheme is secure under the symmetric external Diffie-Hellman assumption in the standard model. We use techniques of dual system encryption and dual pairing vector spaces (DPVS) to construct our watermarking scheme. This is a new application of DPVS.
Masayuki ABE Fumitaka HOSHINO Miyako OHKUBO
Bilinear-type conversion is to translate a cryptographic scheme designed over symmetric bilinear groups into one that works over asymmetric bilinear groups with small overhead regarding the size of objects concerned in the target scheme. In this paper, we address scalability for converting complex cryptographic schemes. Our contribution is threefold. Investigating complexity of bilinear-type conversion. We show that there exists no polynomial-time algorithm for worst-case inputs under standard complexity assumption. It means that bilinear-type conversion in general is an inherently difficult problem. Presenting a new scalable conversion method. Nevertheless, we show that large-scale conversion is indeed possible in practice when the target schemes are built from smaller building blocks with some structure. We present a novel conversion method, called IPConv, that uses 0-1 Integer Programming instantiated with a widely available IP solver. It instantly converts schemes containing more than a thousand of variables and hundreds of pairings. Application to computer-aided design. Our conversion method is also useful in modular design of middle to large scale cryptographic applications; first construct over simpler symmetric bilinear groups and run over efficient asymmetric groups. Thus one can avoid complication of manually allocating variables over asymmetric bilinear groups. We demonstrate its usefulness by somewhat counter-intuitive examples where converted DLIN-based Groth-Sahai proofs are more compact than manually built SXDH-based proofs. Though the early purpose of bilinear-type conversion is to save existing schemes from attacks against symmetric bilinear groups, our new scalable conversion method will find more applications beyond the original goal. Indeed, the above computer-aided design can be seen as a step toward automated modular design of cryptographic schemes.
Takanori ISOBE Kyoji SHIBUTANI
We propose new key recovery attacks on the two-round single-key n-bit Even-Mansour ciphers (2SEM) that are secure up to 22n/3 queries against distinguishing attacks proved by Chen et al. Our attacks are based on the meet-in-the-middle technique which can significantly reduce the data complexity. In particular, we introduce novel matching techniques which enable us to compute one of the two permutations without knowing a part of the key information. Moreover, we present two improvements of the proposed attack: one significantly reduces the data complexity and the other reduces the time complexity. Compared with the previously known attacks, our attack first breaks the birthday barrier on the data complexity although it requires chosen plaintexts. When the block size is 64 bits, our attack reduces the required data from 245 known plaintexts to 226 chosen plaintexts with keeping the time complexity required by the previous attacks. Furthermore, by increasing the time complexity up to 262, the required data is further reduced to 28, and DT=270, where DT is the product of data and time complexities. We show that our data-optimized attack requires DT=2n+6 in general cases. Since the proved lower bound on DT for the single-key one-round n-bit Even-Mansour ciphers is 2n, our results imply that adding one round to one-round constructions does not sufficiently improve the security against key recovery attacks. Finally, we propose a time-optimized attacks on 2SEM in which, we aim to minimize the number of the invocations of internal permutations.