Revisiting the Sekine-Imai-Tani top-down algorithm to compute the BDD of all spanning trees and the Tutte polynomial of a given graph, we explicitly analyze the Fixed-Parameter Tractable (FPT) time complexity with respect to its (proper) pathwidth, pw (ppw), and obtain a bound of O*(Bellmin{pw}+1,ppw}), where Belln denotes the n-th Bell number, defined as the number of partitions of a set of n elements. We further investigate the case of complete graphs in terms of Bell numbers and related combinatorics, obtaining a time complexity bound of Belln-O(n/log n).

At PQCrypto 2016, Szepieniec et al. proposed a new type of trapdoor called Extension Field Cancellation (EFC) for constructing secure multivariate encryption cryptosystems. They also specifically suggested two schemes EFCp- and EFCpt2- that apply this trapdoor and some modifiers. Although both of them seem to avoid all attacks used for cryptanalysis on multivariate cryptography, their decryption efficiency has room for improvement. On the other hand, their security was analyzed mainly through an algebraic attack of computing the Gröbner basis of the public key, and there possibly exists more effective attacks. In this paper, we introduce a more efficient decryption approach for EFCp- and EFCpt2-, which manages to avoid all redundant computation involved in the original decryption algorithms without altering their public key. In addition, we estimate the secure parameters for EFCp- and EFCpt2- through a hybrid attack of algebraic attack and exhaustive search.

Along with the proliferation of IoT (Internet of Things) devices, cyberattacks towards them are on the rise. In this paper, aiming at efficient precaution and mitigation of emerging IoT cyberthreats, we present a multimodal study on applying machine learning methods to characterize malicious programs which target multiple IoT platforms. Experiments show that opcode sequences obtained from static analysis and API sequences obtained by dynamic analysis provide sufficient discriminant information such that IoT malware can be classified with near optimal accuracy. Automated and accelerated identification and mitigation of new IoT cyberthreats can be enabled based on the findings reported in this study.

In this paper, we focus on a large-scale ICN (Information-Centric Networking), and reveal the scaling property of ICN. Because of in-network content caching, ICN is a sort of cache networks and expected to be a promising architecture for replacing future Internet. To realize a global-scale (e.g., Internet-scale) ICN, it is crucial to understand the fundamental properties of such large-scale cache networks. However, the scaling property of ICN has not been well understood due to the lack of theoretical foundations and analysis methodologies. For answering research questions regarding the scaling property of ICN, we derive the cache hit probability at each router, the average content delivery delay of each entity, and the average content delivery delay of all entities over a content distribution tree comprised of a single repository (i.e., content provider), multiple routers, and multiple entities (i.e., content consumers). Through several numerical examples, we investigate the effect of the topology and the size of the content distribution tree and the cache size at routers on the average content delivery delay of all entities. Our findings include that the average content delivery delay of ICNs converges to a constant value if the cache size of routers are not small, which implies high scalability of ICNs, and that even when the network size would grow indefinitely, the average content delivery delay is upper-bounded by a constant value if routers in the network are provided with a fair amount of content caches.

We can enjoy various video contents such as movies in several ways. In this report, we show the effects of content differences on physiological parameters such as eye movements and CFF. This time we confirmed the difference in responses that after watching a movie. In addition, a consistent change that can infer that due to a movie was also indicated. Our results showed that content differences affect the parameters. This suggests the possibility that the influence of movie contents on the viewer can be evaluated by physiological parameters.

Software testing is an important problem to design a large software system and it is difficult to be solved due to its computational complexity. We try to use program nets to approach this problem. As the first step towards solving software testing problem, this paper provides a technique to generate subnets of a program net and applies this technique to software testing. Firstly, definitions and properties of program nets are introduced based on our previous works, and the explanation of software testing problem is given. Secondly, polynomial algorithms are proposed to generate subnets that can cover all the given program net. Finally, a case study is presented to show how to find subnets covering a given program net by using the proposed algorithms, as well as to show the input test data of the program net for software testing.

Social networks often demonstrate hierarchical community structure with communities embedded in other ones. Most existing hierarchical community detection methods need one or more tunable parameters to control the resolution levels, and the obtained dendrograms, a tree describing the hierarchical community structure, are extremely complex to understand and analyze. In the paper, we propose a parameter-free hierarchical community detection method based on micro-community and minimum spanning tree. The proposed method first identifies micro-communities based on link strength between adjacent vertices, and then, it constructs minimum spanning tree by successively linking these micro-communities one by one. The hierarchical community structure of social networks can be intuitively revealed from the merging order of these micro-communities. Experimental results on synthetic and real-world networks show that our proposed method exhibits good accuracy and efficiency performance and outperforms other state-of-the-art methods. In addition, our proposed method does not require any pre-defined parameters, and the output dendrogram is simple and meaningful for understanding and analyzing the hierarchical community structure of social networks.

Various systems that share remote co-worker's awareness information have been proposed for realizing efficient collaborative work among distributed offices. In this study, we implemented an interruptibility sharing system in a university laboratory and assessed the observation behavior for the displayed information. Observation behavior for each target member was detected using an eye tracker to discuss the usage and effect of the system in a quantitative manner, along with the considerations of workers' job positions and relationships. The results suggested that participants observed interruptibility information approximately once an hour while at their desks. Observations were frequent during break-times rather than when the participants wanted to communicate with others. The most frequently observed targets were the participants themselves. The participants gazed the laboratory members not only in a close work relationship but also in a weak relationship. Results suggested that sharing of interruptibility information assists worker's self-reflection and contributes to the establishment of horizontal connection in an organization including members in weak work relationship.

It is not easy for a student to present a question or comment to the lecturer and other students in large classes. This paper introduces a new audience presentation system (APS), which creates slide presentations of students' mobile responses in the classroom. Experimental surveys demonstrate the utility of this APS for classroom interactivity.

The sparse unmixing of hyperspectral data has attracted much attention in recent years because it does not need to estimate the number of endmembers nor consider the lack of pure pixels in a given hyperspectral scene. However, the high mutual coherence of spectral libraries strongly affects the practicality of sparse unmixing. The collaborative sparse unmixing via variable splitting and augmented Lagrangian (CLSUnSAL) algorithm is a classic sparse unmixing algorithm that performs better than other sparse unmixing methods. In this paper, we propose a CLSUnSAL-based hyperspectral unmixing method based on dictionary pruning and reweighted sparse regression. First, the algorithm identifies a subset of the original library elements using a dictionary pruning strategy. Second, we present a weighted sparse regression algorithm based on CLSUnSAL to further enhance the sparsity of endmember spectra in a given library. Third, we apply the weighted sparse regression algorithm on the pruned spectral library. The effectiveness of the proposed algorithm is demonstrated on both simulated and real hyperspectral datasets. For simulated data cubes (DC1, DC2 and DC3), the number of the pruned spectral library elements is reduced by at least 94% and the runtime of the proposed algorithm is less than 10% of that of CLSUnSAL. For simulated DC4 and DC5, the runtime of the proposed algorithm is less than 15% of that of CLSUnSAL. For the real hyperspectral datasets, the pruned spectral library successfully reduces the original dictionary size by 76% and the runtime of the proposed algorithm is 11.21% of that of CLSUnSAL. These experimental results show that our proposed algorithm not only substantially improves the accuracy of unmixing solutions but is also much faster than some other state-of-the-art sparse unmixing algorithms.

This paper considers Peer-to-Peer (P2P) video streaming systems, in which a given video stream is divided into b stripes and those stripes are delivered to n peers through b spanning trees under the constraint such that each peer including the source can forward at most b stripes. The delivery of a stripe to n peers is said to be a k-hop delivery if all peers receive the stripe through a path of length at most k. Let Bk=∑i=0k-1bi. It is known that under the above constraint, k-hop delivery of b stripes to n peers is possible only if n≤Bk. This paper proves that (k+1)-hop delivery of b stripes to n peers is possible for any n≤Bk; namely, we can realize the delivery of stripes with a guaranteed latency while it is slightly larger than the minimum latency. In addition, we derive a necessary and sufficient condition on n to enable a k-hop delivery of b stripes for Bk-b+2≤n≤Bk-1; namely for n's close to Bk.

The security of elliptic curve cryptography is closely related to the computational complexity of the elliptic curve discrete logarithm problem (ECDLP). Today, the best practical attacks against ECDLP are exponential-time generic discrete logarithm algorithms such as Pollard's rho method. A recent line of inquiry in index calculus for ECDLP started by Semaev, Gaudry, and Diem has shown that, under certain heuristic assumptions, such algorithms could lead to subexponential attacks to ECDLP. In this study, we investigate the computational complexity of ECDLP for elliptic curves in various forms — including Hessian, Montgomery, (twisted) Edwards, and Weierstrass representations — using index calculus. Using index calculus, we aim to determine whether there is any significant difference in the computational complexity of ECDLP for elliptic curves in various forms. We provide empirical evidence and insight showing an affirmative answer in this paper.

We present constant-time testing algorithms for generalized shogi (Japanese chess), chess, and xiangqi (Chinese chess). These problems are known or believed to be EXPTIME-complete. A testing algorithm (or a tester) for a property accepts an input if it has the property, and rejects it with high probability if it is far from having the property (e.g., at least 2/3) by reading only a constant part of the input. A property is said to be testable if a tester exists. Given any position on a ⌊√n⌋×⌊√n⌋ board with O(n) pieces, the generalized shogi, chess, and xiangqi problem are problems determining the property that “the player who moves first has a winning strategy.” We propose that this property is testable for shogi, chess, and xiangqi. The shogi tester and xiangqi tester have a one-sided-error, but surprisingly, the chess tester has no-error. Over the last decade, many problems have been revealed to be testable, but most of such problems belong to NP. This is the first result on the constant-time testability of EXPTIME-complete problems.

In this paper, we investigate computational complexity of pipe puzzles. A pipe puzzle is a kind of tiling puzzle; the input is a set of cards, and a part of a pipe is drawn on each card. For a given set of cards, we arrange them and connect the pipes. We have to connect all pipes without creating any local loop. While ordinary tiling puzzles, like jigsaw puzzles, ask to arrange the tiles with local consistency, pipe puzzles ask to join all pipes. We first show that the pipe puzzle is NP-complete in general even if the goal shape is quite restricted. We also investigate restricted cases and show some polynomial-time algorithms.

HIGHT is a 64-bit block lightweight cipher, which adopts the ARX-based generalized Feistel network, and it accepts a 128-bit key. It is a standard encryption algorithm in South Korea and also is internationally standardized by ISO/IEC 18033-3. Therefore, many third-party cryptanalyses have been proposed against HIGHT. Impossible differential and integral attacks are applied to reduced-round HIGHT, and especially, the impossible differential attack causes the 27-round attack, which is the current best attack under the single-key setting. In this paper, we propose some improved integral attacks against HIGHT. We first apply the division property to HIGHT and find new 19-round integral characteristics, which are improved by two rounds compared with the previous best ones. We append 9-round key recovery to these characteristics and it enables us to attack 28-round HIGHT. Its time complexity is 2127.02 where 263 chosen plaintexts and 2117 memory are required. Moreover, we can attack 29-round HIGHT if the full codebook is used, where its time and memory complexities are 2126.07 and 2118, respectively. It improves by two rounds compared with the previous best attack.

This paper analyzes the performance of various decoders in a two-user interference channel, and some improved decoders based on enhanced utilization of channel state information at the receiver side are presented. Further, new decoders, namely hierarchical constellation based decoders, are proposed. Simulations show that the improved decoders and the proposed decoders have much better performance than existing decoders. Moreover, the proposed decoders have lower decoding complexity than the traditional maximum likelihood decoder.

A key-order preserving structured overlay network is a class of structured overlay network that preserves, in its structure, the order of keys to support efficient range queries. This paper presents a novel key-order preserving structured overlay network “Suzaku”. Similar to the conventional Chord#, Suzaku uses a periodically updated finger table as a routing table, but extends its uni-directional finger table to bi-directional, which achieves ⌈log2 n⌉-1 maximum lookup hops in the converged state. Suzaku introduces active and passive bi-directional finger table update algorithms for node insertion and deletion. This method maintains good lookup performance (lookup hops increase nearly logarithmically against n) even in churn situations. As well as its good performance, the algorithms of Suzaku are simple and easy to implement. This paper describes the principles of Suzaku, followed by simulation evaluations, in which it showed better performance than the conventional networks, Chord# and Skip Graph.

A Multipath TCP (MPTCP) connection uses multiple subflows (i.e., TCP flows), each of which traverses over a wireless link, enabling throughput and resilience enhancements in mobile wireless networks. However, to achieve the benefits, the subflows are necessarily initialized (i.e., must complete TCP handshakes) and sequentially attached to the MPTCP connection. In the standard (MPTCPST), MPTCP initialization raises several problems. First, the TCP handshake of opening subflow is generally associated with a predetermined network. That leads to degraded MPTCP performance when the network does not have the lowest latency among available ones. Second, the first subflow's initialization needs to be successful before the next subflow can commence its attempt to achieve initialization. Therefore, the resilience of multiple paths fails when the first initialization fails. This paper proposes a novel method for MPTCP initialization, namely MPTCPSD (i.e., MPTCP with SYN duplication), which can solve the problems. MPTCPSD duplicates the first SYN and attempts to establish TCP handshakes for all subflows simultaneously, hence inherently improves the loss-resiliency. The subflow that achieves initialization first, is selected as the first subflow, consequently solving the first problem. We have implemented and extensively evaluated MPTCPSD in comparison to MPTCPST. In an emulated network, the evaluation results show that MPTCPSD has better performance that MPTCPST with the scenarios of medium and short flows. Moreover, MPTCPSD outperforms MPTCPST in the case that the opening subflow fails. Moreover, a real network evaluation proves that MPTCPSD efficiently selects the lowest delay network among three ones for the first subflow regardless of the preconfigured default network. Additionally, we propose and implement a security feature for MPTCPSD, that prevents the malicious subflow from being established by a third party.

With the advantages of higher blocking voltage, higher operation temperature, fast-switching characteristics, and lower switching losses, the silicon carbide (SiC) MOSFET has attracted more attentions and become an available replacement of traditional silicon (Si) power semiconductor in applications. Despite of all the merits above, electromagnetic interference (EMI) issues will be induced consequently by the ultra-fast switching transitions of the SiC MOSFET. To quickly and precisely assess the switching behaviors of the SiC MOSFET for EMI investigation, an analytical model is proposed. This model has comprehensively considered most of the key factors, including parasitic inductances, non-linearity of the junction capacitors, negative feedback effect of Ls and Cgd shared by the power and the gate stage loops, non-linearity of the trans-conductance, and skin effect during voltage and current ringing stages, which will considerably affect the switching performance of the SiC MOSFET. Additionally, a finite-state machine (FSM) is especially utilized so as to analytically and intuitively describe the switching behaviors of the SiC MOSFET via Stateflow. Based on double pulse test (DPT), the effectiveness and correctness of the proposed model are validated through the comparison between the calculated and the measured waveforms during switching transitions. Besides, the model can appropriately depict the spectrum of the drain-source voltage of the MOSFET and is suitable for EMI investigation in applying of SiC devices.

Traceability links between software artifacts can assist in several software development tasks. There are some automatic traceability recovery methods that help with managing the massive number of software artifacts and their relationships, but they do not work well for software artifacts whose descriptions are different in terms of language or abstraction level. To overcome these weakness, we propose the Connecting Links Method (CLM), which recovers transitive traceability links between two artifacts by intermediating a third artifact. In order to apply CLM for general use without limitation in terms of software artifact type, we have designed a standardized method to calculate the relation score of transitive traceability links using the scores of direct traceability links between three artifacts. Furthermore, we propose an improvement of CLM by considering software version. We evaluated CLM by applying it to three software products and found that it is more effective for software artifacts whose language type or vocabulary are different compared to previous methods using textual similarity.