Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Shunta TERUI,Katsuhisa YAMANAKA,Takashi HIRAYAMA,Takashi HORIYAMA,Kazuhiro KURITA,Takeaki UNO, Vol.E106-A, No.9, pp.1082-1091 We are given a set S of n points in the Euclidean plane. We assume that S is in general position. A simple polygon P is an empty polygon of S if each vertex of P is a point in S and every point in S is either outside P or a vertex of P. In this paper, we consider the problem of enumerating all the empty polygons of a given point set. To design an efficient enumeration algorithm, we use a reverse search by Avis and Fukuda with child lists. We propose an algorithm that enumerates all the empty polygons of S in O(n2 ε(S) )-time, where ε(S) is the set of empty polygons of S. Moreover, by applying the same idea to the problem of enumerating surrounding polygons of a given point set S, we propose an enumeration algorithm that enumerates them in O(n2)-delay, while the known algorithm enumerates in O(n2 log n)-delay, where a surroundingpolygon of S is a polygon such that each vertex of the polygon is a point in S and every point in S is either inside the polygon or a vertex of the polygon. Publication Date: 2023/09/01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Kazuyuki MIURA, Vol.E106-A, No.9, pp.1092-1099 In a convex grid drawing of a plane graph, all edges are drawn as straight-line segments without any edge-intersection, all vertices are put on grid points and all facial cycles are drawn as convex polygons. A plane graph G has a convex drawing if and only if G is internally triconnected, and an internally triconnected plane graph G has a convex grid drawing on an (n-1) × (n-1) grid if either G is triconnected or the triconnected component decomposition tree T(G) of G has two or three leaves, where n is the number of vertices in G. An internally triconnected plane graph G has a convex grid drawing on a 2n × 2n grid if T(G) has exactly four leaves. Furthermore, an internally triconnected plane graph G has a convex grid drawing on a 20n × 16n grid if T(G) has exactly five leaves. In this paper, we show that an internally triconnected plane graph G has a convex grid drawing on a 10n × 5n grid if T(G) has exactly five leaves. We also present a linear-time algorithm to find such a drawing. Publication Date: 2023/09/01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Hiroshi FUJIWARA,Masaya KAWAGUCHI,Daiki TAKIZAWA,Hiroaki YAMAMOTO, Vol.E106-A, No.9, pp.1100-1110 The bin packing problem is a problem of finding an assignment of a sequence of items to a minimum number of bins, each of capacity one. An online algorithm for the bin packing problem is an algorithm that irrevocably assigns each item one by one from the head of the sequence. Gutin, Jensen, and Yeo (2006) considered a version in which all items are only of two different sizes and the online algorithm knows the two possible sizes in advance, and gave an optimal online algorithm for the case when the larger size exceeds 1/2. In this paper we provide an optimal online algorithm for some of the cases when the larger size is at most 1/2, on the basis of a framework that facilitates the design and analysis of algorithms. Publication Date: 2023/09/01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Takashi FUCHINO,Takashi HARADA,Ken TANAKA,Kenji MIKAWA, Vol.E106-A, No.9, pp.1111-1118 Packet classification is used to determine the behavior of incoming packets in network devices according to defined rules. As it is achieved using a linear search on a classification rule list, a large number of rules will lead to longer communication latency. To solve this, the problem of finding the order of rules minimizing the latency has been studied. Misherghi et al. and Harada et al. have proposed a problem that relaxes to policy-based constraints. In this paper, we show that the Relaxed Optimal Rule Ordering (RORO) for the allowlist is NP-hard, and by reducing from this we show that RORO for the general rule list is NP-hard. We also propose a heuristic algorithm based on the greedy method for an allowlist. Furthermore, we demonstrate the effectiveness of our method using ClassBench, which is a benchmark for packet classification algorithms. Publication Date: 2023/09/01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Yuji HASHIMOTO,Koji NUIDA, Vol.E106-A, No.9, pp.1119-1130 There are two types of elliptic curves, ordinary elliptic curves and supersingular elliptic curves. In 2012, Sutherland proposed an efficient and almost deterministic algorithm for determining whether a given curve is ordinary or supersingular. Sutherland's algorithm is based on sequences of isogenies started from the input curve, and computation of each isogeny requires square root computations, which is the dominant cost of the algorithm. In this paper, we reduce this dominant cost of Sutherland's algorithm to approximately a half of the original. In contrast to Sutherland's algorithm using j-invariants and modular polynomials, our proposed algorithm is based on Legendre form of elliptic curves, which simplifies the expression of each isogeny. Moreover, by carefully selecting the type of isogenies to be computed, we succeeded in gathering square root computations at two consecutive steps of Sutherland's algorithm into just a single fourth root computation (with experimentally almost the same cost as a single square root computation). The results of our experiments using Magma are supporting our argument; for cases of characteristic p of 768-bit to 1024-bit lengths, our proposed algorithm for characteristic p≡1 (mod 4) runs in about 61.5% of the time and for characteristic p≡3 (mod 4) also runs in about 54.9% of the time compared to Sutherland's algorithm. Publication Date: 2023/09/01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Yuji HASHIMOTO,Koji NUIDA, Vol.E106-A, No.9, pp.1131-1140 The CGL hash function is a provably secure hash function using walks on isogeny graphs of supersingular elliptic curves. A dominant cost of its computation comes from iterative computations of power roots over quadratic extension fields. In this paper, we reduce the necessary number of power root computations by almost half, by applying and also extending an existing method of efficient isogeny sequence computation on Legendre curves (Hashimoto and Nuida, CASC 2021). We also point out some relationship between 2-isogenies for Legendre curves and those for Edwards curves, which is of independent interests, and develop a method of efficient computation for 2e-th roots in quadratic extension fields. Publication Date: 2023/09/01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Ren ISHIBASHI,Kazuki YONEYAMA, Vol.E106-A, No.9, pp.1141-1163 Authenticated Key Exchange (AKE) is a cryptographic protocol to share a common session key among multiple parties. Usually, PKI-based AKE schemes are designed to guarantee secrecy of the session key and mutual authentication. However, in practice, there are many cases where mutual authentication is undesirable such as in anonymous networks like Tor and Riffle, or difficult to achieve due to the certificate management at the user level such as the Internet. Goldberg et al. formulated a model of anonymous one-sided AKE which guarantees the anonymity of the client by allowing only the client to authenticate the server, and proposed a concrete scheme. However, existing anonymous one-sided AKE schemes are only known to be secure in the random oracle model. In this paper, we propose generic constructions of anonymous one-sided AKE in the random oracle model and in the standard model, respectively. Our constructions allow us to construct the first post-quantum anonymous one-sided AKE scheme from isogenies in the standard model. Publication Date: 2023/09/01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Hiroki YAMAMURO,Keisuke HARA,Masayuki TEZUKA,Yusuke YOSHIDA,Keisuke TANAKA, Vol.E106-A, No.9, pp.1164-1176 Message franking is introduced by Facebook in end-to-end encrypted messaging services. It allows to produce verifiable reports of malicious messages by including cryptographic proofs, called reporting tags, generated by Facebook. Recently, Grubbs et al. (CRYPTO'17) proceeded with the formal study of message franking and introduced committing authenticated encryption with associated data (CAEAD) as a core primitive for obtaining message franking. In this work, we aim to enhance the security of message franking and introduce forward security and updates of reporting tags for message franking. Forward security guarantees the security associated with the past keys even if the current keys are exposed and updates of reporting tags allow for reporting malicious messages after keys are updated. To this end, we firstly propose the notion of key-evolving message franking with updatable reporting tags including additional key and reporting tag update algorithms. Then, we formalize five security requirements: confidentiality, ciphertext integrity, unforgeability, receiver binding, and sender binding. Finally, we show a construction of forward secure message franking with updatable reporting tags based on CAEAD, forward secure pseudorandom generator, and updatable message authentication code. Publication Date: 2023/09/01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Kyosuke YAMASHITA,Ryu ISHII,Yusuke SAKAI,Tadanori TERUYA,Takahiro MATSUDA,Goichiro HANAOKA,Kanta MATSUURA,Tsutomu MATSUMOTO, Vol.E106-A, No.9, pp.1177-1188 A fault-tolerant aggregate signature (FT-AS) scheme is a variant of an aggregate signature scheme with the additional functionality to trace signers that create invalid signatures in case an aggregate signature is invalid. Several FT-AS schemes have been proposed so far, and some of them trace such rogue signers in multi-rounds, i.e., the setting where the signers repeatedly send their individual signatures. However, it has been overlooked that there exists a potential attack on the efficiency of bandwidth consumption in a multi-round FT-AS scheme. Since one of the merits of aggregate signature schemes is the efficiency of bandwidth consumption, such an attack might be critical for multi-round FT-AS schemes. In this paper, we propose a new multi-round FT-AS scheme that is tolerant of such an attack. We implement our scheme and experimentally show that it is more efficient than the existing multi-round FT-AS scheme if rogue signers randomly create invalid signatures with low probability, which for example captures spontaneous failures of devices in IoT systems. Publication Date: 2023/09/01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Kazuyuki AMANO, Vol.E106-A, No.9, pp.1189-1190 We show that every polynomial threshold function that sign-represents the ODD-MAXBITn function has total absolute weight 2Ω(n1/3). The bound is tight up to a logarithmic factor in the exponent. Publication Date: 2023/09/01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Miyuji HIROTA,Yoshifumi SAKAI, Vol.E106-A, No.9, pp.1191-1194 For any m strings of total length n, we propose an O(mn log n)-time, O(n)-space algorithm that finds a maximal common subsequence of all the strings, in the sense that inserting any character in it no longer yields a common subsequence of them. Such a common subsequence could be treated as indicating a nontrivial common structure we could find in the strings since it is NP-hard to find any longest common subsequence of the strings. Publication Date: 2023/09/01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Kenya UOMORI, Vol.E106-A, No.9, pp.1195-1195 Publication Date: 2023/09/01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Toshihiko YAMASAKI, Vol.E106-A, No.9, pp.1196-1201 Our research group has been working on attractiveness prediction, reasoning, and even enhancement for multimedia content, which we call “attractiveness computing.” Attractiveness includes impressiveness, instagrammability, memorability, clickability, and so on. Analyzing such attractiveness was usually done by experienced professionals but we have experimentally revealed that artificial intelligence (AI) based on big multimedia data can imitate or reproduce professionals' skills in some cases. In this paper, we introduce some of the representative works and possible real-life applications of our attractiveness computing for image media. Publication Date: 2023/09/01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Rebeka SULTANA,Gosuke OHASHI, Vol.E106-A, No.9, pp.1202-1210 High-performance deep learning-based object detection models can reduce traffic accidents using dashcam images during nighttime driving. Deep learning requires a large-scale dataset to obtain a high-performance model. However, existing object detection datasets are mostly daytime scenes and a few nighttime scenes. Increasing the nighttime dataset is laborious and time-consuming. In such a case, it is possible to convert daytime images to nighttime images by image-to-image translation model to augment the nighttime dataset with less effort so that the translated dataset can utilize the annotations of the daytime dataset. Therefore, in this study, a GAN-based image-to-image translation model is proposed by incorporating self-attention with cycle consistency and content/style separation for nighttime data augmentation that shows high fidelity to annotations of the daytime dataset. Experimental results highlight the effectiveness of the proposed model compared with other models in terms of translated images and FID scores. Moreover, the high fidelity of translated images to the annotations is verified by a small object detection model according to detection results and mAP. Ablation studies confirm the effectiveness of self-attention in the proposed model. As a contribution to GAN-based data augmentation, the source code of the proposed image translation model is publicly available at https://github.com/subecky/Image-Translation-With-Self-Attention Publication Date: 2023/09/01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Sang Hoon KIM,Jong Hwan KO, Vol.E106-A, No.9, pp.1211-1215 The existing target-dependent scalable image compression network can control the target of the compressed images between the human visual system and the deep learning based classification task. However, in its RNN based structure controls the bit-rate through the number of iterations, where each iteration generates a fixed size of the bit stream. Therefore, a large number of iterations are required at the high BPP, and fine-grained image quality control is not supported at the low BPP. In this paper, we propose a novel RNN-based image compression model that can schedule the channel size per iteration, to reduce the number of iterations at the high BPP and fine-grained bit-rate control at the low BPP. To further enhance the efficiency, multiple network models for various channel sizes are combined into a single model using the slimmable network architecture. The experimental results show that the proposed method achieves comparable performance to the existing method with finer BPP adjustment, increases parameters by only 0.15% and reduces the average amount of computation by 40.4%. Publication Date: 2023/09/01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Tomoya FUJII,Rie JINKI,Yuukou HORITA, Vol.E106-A, No.9, pp.1216-1219 The social infrastructure, including roads and bridges built during period of rapid economic growth in Japan, is now aging, and there is a need to strategically maintain and renew the social infrastructure that is aging. On the other hand, road maintenance in rural areas is facing serious problems such as reduced budgets for maintenance and a shortage of engineers due to the declining birthrate and aging population. Therefore, it is difficult to visually inspect all roads in rural areas by maintenance engineers, and a system to automatically detect road damage is required. This paper reports practical improvements to the road damage model using YOLOv5, an object detection model capable of real-time operation, focusing on road image features. Publication Date: 2023/09/01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Takashi YAMAZOE,Jinyu TANG,Gin INOUE,Kenji SUGIYAMA, Vol.E106-A, No.9, pp.1220-1223 HDR video is possible to display the maximum 1200% luminance, however, it is limited in SDR display. In this study, we expand high luminance area considering with perceptual performance to improve a presentation performance of HDR video in the SDR display. As results of objective experiments, it is recognized that the proposed method can improve the presentation performance maximally 0.8dB in WPSNR. Publication Date: 2023/09/01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Masanori TSUJIKAWA,Yoshinobu KAJIKAWA, Vol.E106-A, No.9, pp.1224-1233 In this paper, we propose a low-complexity and accurate noise suppression based on an a priori SNR (Speech to Noise Ratio) model for greater robustness w.r.t. short-term noise-fluctuation. The a priori SNR, the ratio of speech spectra and noise spectra in the spectral domain, represents the difference between speech features and noise features in the feature domain, including the mel-cepstral domain and the logarithmic power spectral domain. This is because logarithmic operations are used for domain conversions. Therefore, an a priori SNR model can easily be expressed in terms of the difference between the speech model and the noise model, which are modeled by the Gaussian mixture models, and it can be generated with low computational cost. By using a priori SNRs accurately estimated on the basis of an a priori SNR model, it is possible to calculate accurate coefficients of noise suppression filters taking into account the variance of noise, without serious increase in computational cost over that of a conventional model-based Wiener filter (MBW). We have conducted in-car speech recognition evaluation using the CENSREC-2 database, and a comparison of the proposed method with a conventional MBW showed that the recognition error rate for all noise environments was reduced by 9%, and that, notably, that for audio-noise environments was reduced by 11%. We show that the proposed method can be processed with low levels of computational and memory resources through implementation on a digital signal processor. Publication Date: 2023/09/01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Tatsuya KAI,Koshi MAEHARA, Vol.E106-A, No.9, pp.1234-1240 This paper develops a design method and theoretical analysis for piecewise nonlinear oscillators that have desired circular limit cycles. Especially, the mathematical proof on existence, uniqueness, and stability of the limit cycle is shown for the piecewise nonlinear oscillator. In addition, the relationship between parameters in the oscillator and rotational directions and periods of the limit cycle trajectories is investigated. Then, some numerical simulations show that the piecewise nonlinear oscillator has a unique and stable limit cycle and the properties on rotational directions and periods hold. Publication Date: 2023/09/01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Xianliang GE,Shinji KIMURA, Vol.E106-A, No.9, pp.1241-1250 Majority operation has been paid attention as a basic element of beyond-Moore devices on which logic functions are constructed from Majority elements and inverters. Several optimization methods are developed to reduce the number of elements on Majority-Inverter Graphs (MIGs) but more area and power reduction are required. The paper proposes a new exact synthesis method for MIG based on a new topological constraint using node levels. Possible graph structures are clustered by the levels of input nodes, and all possible structures can be enumerated efficiently in the exact synthesis compared with previous methods. Experimental results show that our method decreases the runtime up to 25.33% compared with the fence-based method, and up to 6.95% with the partial-DAG-based method. Furthermore, our implementation can achieve better performance in size optimization for benchmark suites. Publication Date: 2023/09/01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Veeramani KARTHIKA,Suresh JAGANATHAN, Vol.E106-A, No.9, pp.1251-1262 Considering the growth of the IoT network, there is a demand for a decentralized solution. Incorporating the blockchain technology will eliminate the challenges faced in centralized solutions, such as i) high infrastructure, ii) maintenance cost, iii) lack of transparency, iv) privacy, and v) data tampering. Blockchain-based IoT network allows businesses to access and share the IoT data within their organization without a central authority. Data in the blockchain are stored as blocks, which should be validated and added to the chain, for this consensus mechanism plays a significant role. However, existing methods are not designed for IoT applications and lack features like i) decentralization, ii) scalability, iii) throughput, iv) faster convergence, and v) network overhead. Moreover, current blockchain frameworks failed to support resource-constrained IoT applications. In this paper, we proposed a new consensus method (WoG) and a lightweight blockchain framework (iLEDGER), mainly for resource-constrained IoT applications in a permissioned environment. The proposed work is tested in an application that tracks the assets using IoT devices (Raspberry Pi 4 and RFID). Furthermore, the proposed consensus method is analyzed against benign failures, and performance parameters such as CPU usage, memory usage, throughput, transaction execution time, and block generation time are compared with state-of-the-art methods. Publication Date: 2023/09/01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Makoto OSAWA,Norisato SUGA, Vol.E106-A, No.9, pp.1263-1267 The radio map of wireless communications should be surveyed in advance when installing base stations to efficiently utilize radio waves. Generally, this is calculated using radio wave propagation simulation. Because the simulation is time-consuming, a tensor-rank minimization-based interpolation method has been proposed as fast method. However, this method interpolates the radio map using an iterative algorithm. The number of iterations required for further acceleration should be reduced; therefore, we propose a tensor interpolation using rank minimization that considers the characteristics of radio wave propagation. Furthermore, we proved that the proposed method could interpolate with fewer iterations than the existing method. Publication Date: 2023/09/01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Jiao DU,Ziyu CHEN,Le DONG,Tianyin WANG,Shanqi PANG, Vol.E106-A, No.9, pp.1268-1271 In this paper, the notion of 2-tuples distribution matrices of the rotation symmetric orbits is proposed, by using the properties of the 2-tuples distribution matrix, a new characterization of 2-resilient rotation symmetric Boolean functions is demonstrated. Based on the new characterization of 2-resilient rotation symmetric Boolean functions, constructions of 2-resilient rotation symmetric Boolean functions (RSBFs) are further studied, and new 2-resilient rotation symmetric Boolean functions with prime variables are constructed. Publication Date: 2023/09/01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Xiaoyu CHEN,Yihan ZHANG,Lianfeng SUN,Yubo LI, Vol.E106-A, No.9, pp.1272-1276 This letter is devoted to constructing new Type-II Z-complementary pairs (ZCPs). A ZCP of length N with ZCZ width Z is referred to in short by the designation (N, Z)-ZCP. Inspired by existing works of ZCPs, systematic constructions of (2N+3, N+2)-ZCPs and (4N+4, 7/2N+4)-ZCPs are proposed by appropriately inserting elements into concatenated GCPs. The odd-length binary Z-complementary pairs (OB-ZCPs) are Z-optimal. Furthermore, the proposed construction can generate even-length binary Z-complementary pairs (EB-ZCPs) with ZCZ ratio (i.e. ZCZ width over the sequence length) of 7/8. It turns out that the PMEPR of resultant EB-ZCPs are upper bounded by 4. Publication Date: 2023/09/01
Subscription journal
[4 journals]
