The QC-MDPC McEliece scheme was considered one of the most promising public key encryption schemes for efficient post-quantum secure encryption. As a variant of the McEliece scheme, it is based on the syndrome decoding problem, which is a hard problem from Coding Theory. Its key sizes are competitive with the ones of the widely used RSA cryptosystem, and it came with an apparently strong security reduction. For three years, the scheme has not suffered major threats, until the end of 2016, at the Asiacrypt, when Guo, Johansson, and Stankovski presented a reaction attack on the QC-MDPC that exploits one aspect that was not considered in the security reduction: the probability of a decoding failure to occur is lower when the secret key and the error used for encryption share certain properties. Recording the decoding failures, the attacker obtains information about the secret key and then use the information gathered to reconstruct the key. Guo et al. presented an algorithm for key reconstruction for which we can point two weaknesses. The first one is that it cannot deal with partial information about the secret key, resulting in the attacker having to send a large number of decoding challenges. The second one is that it does not scale well for higher security levels. To improve the attack, we propose a key reconstruction algorithm that runs faster than Guo's et al. algorithm, even using around 20% less interactions with the secret key holder than used by their algorithm, considering parameters suggested for 80 bits of security. It also has a lower asymptotic complexity which makes it scale much better for higher security parameters. The algorithm can be parallelized straightforwardly, which is not the case for the one by Guo et al.

The energy efficiency of Internet of Things (IoT) could be improved by RF energy transfer technologies.Aiming at IoT applications with a mobility-constrained mobile sink, a double-sourced energy transfer (D-ET) scheme is proposed. Based on the hierarchical routing information of network nodes, the Simultaneous Wireless Information and Power Transfer (SWIPT) method helps to improve the global data gathering performance. A genetic algorithm and graph theory are combined to analyze the node energy consumption distribution. Then dedicated charger nodes are deployed on the basis of the genetic algorithm's output. Experiments are conducted using Network Simulator-3 (NS-3) to evaluate the performance of the D-ET scheme. The simulation results show D-ET outperforms other schemes in terms of network lifetime and data gathering performance.

In this study, we address a problem pertaining to the induced matching enumeration. An edge set M is an induced matching of a graph G=(V,E). The enumeration of matchings has been widely studied in literature; however, there few studies on induced matching. A straightforward algorithm takes O(Δ2) time for each solution that is coming from the time to generate a subproblem, where Δ is the maximum degree in an input graph. To generate a subproblem, an algorithm picks up an edge e and generates two graphs, the one is obtained by removing e from G, the other is obtained by removing e, adjacent edge to e, and edges adjacent to adjacent edge of e. Since this operation needs O(Δ2) time, a straightforward algorithm enumerates all induced matchings in O(Δ2) time per solution. We investigated local structures that enable us to generate subproblems within a short time and proved that the time complexity will be O(1) if the input graph is C4-free. A graph is C4-free if and only if none of its subgraphs have a cycle of length four.

Card-based cryptographic protocols provide secure multi-party computations using a deck of physical cards. The most important primitive of those protocols is the shuffling operation, and most of the existing protocols rely on uniform cyclic shuffles (such as the random cut and random bisection cut) in which each possible outcome is equally likely and all possible outcomes constitute a cyclic subgroup. However, a couple of protocols with non-uniform and/or non-cyclic shuffles were proposed by Koch, Walzer, and Härtel at Asiacrypt 2015. Compared to the previous protocols, their protocols require fewer cards to securely produce a hidden AND value, although to implement of such unconventional shuffles appearing in their protocols remains an open problem. This paper introduces “pile-shifting scramble,” which can be a secure implementation of those shuffles. To implement such unconventional shuffles, we utilize physical cases that can store piles of cards, such as boxes and envelopes. Therefore, humans are able to perform the shuffles using these everyday objects. Furthermore, we show that a certain class of non-uniform and/or non-cyclic shuffles having two possible outcomes can be implemented by the pile-shifting scramble. This also implies that we can improve upon the known COPY protocol using three card cases so that the number of cases required can be reduced to two.

Given a graph G=(V,E) where V and E are a vertex and an edge set, respectively, specified with a subset VNT of vertices called a non-terminal set, the spanning tree with non-terminal set VNT is a connected and acyclic spanning subgraph of G that contains all the vertices of V where each vertex in a non-terminal set is not a leaf. The complexity of finding a spanning tree with non-terminal set VNT on general graphs where each edge has the weight of one is known to be NP-hard. In this paper, we show that if G is an interval graph then finding a spanning tree with a non-terminal set VNT of G is linearly-solvable when each edge has the weight of one.

This paper studies a variant of the graph partitioning problem, called the evacuation planning problem, which asks us to partition a target area, represented by a graph, into several regions so that each region contains exactly one shelter. Each region must be convex to reduce intersections of evacuation routes, the distance between each point to a shelter must be bounded so that inhabitants can quickly evacuate from a disaster, and the number of inhabitants assigned to each shelter must not exceed the capacity of the shelter. This paper formulates the convexity of connected components as a spanning shortest path forest for general graphs, and proposes a novel algorithm to tackle this multi-objective optimization problem. The algorithm not only obtains a single partition but also enumerates all partitions simultaneously satisfying the above complex constraints, which is difficult to be treated by existing algorithms, using zero-suppressed binary decision diagrams (ZDDs) as a compressed expression. The efficiency of the proposed algorithm is confirmed by the experiments using real-world map data. The results of the experiments show that the proposed algorithm can obtain hundreds of millions of partitions satisfying all the constraints for input graphs with a hundred of edges in a few minutes.

A term is a connected acyclic graph (unrooted unordered tree) pattern with structured variables, which are ordered lists of one or more distinct vertices. A variable of a term has a variable label and can be replaced with an arbitrary tree by hyperedge replacement according to the variable label. The dimension of a term is the maximum number of vertices in the variables of it. A term is said to be linear if each variable label in it occurs exactly once. Let T be a tree and t a linear term. In this paper, we study the graph pattern matching problem (GPMP) for T and t, which decides whether or not T is obtained from t by replacing variables in t with some trees. First we show that GPMP for T and t is NP-complete if the dimension of t is greater than or equal to 4. Next we give a polynomial time algorithm for solving GPMP for a tree of bounded degree and a linear term of bounded dimension. Finally we show that GPMP for a tree of arbitrary degree and a linear term of dimension 2 is solvable in polynomial time.

In recent years, deep learning based approaches have substantially improved the performance of face recognition. Most existing deep learning techniques work well, but neglect effective utilization of face correlation information. The resulting performance loss is noteworthy for personal appearance variations caused by factors such as illumination, pose, occlusion, and misalignment. We believe that face correlation information should be introduced to solve this network performance problem originating from by intra-personal variations. Recently, graph deep learning approaches have emerged for representing structured graph data. A graph is a powerful tool for representing complex information of the face image. In this paper, we survey the recent research related to the graph structure of Convolutional Neural Networks and try to devise a definition of graph structure included in Compressed Sensing and Deep Learning. This paper devoted to the story explain of two properties of our graph - sparse and depth. Sparse can be advantageous since features are more likely to be linearly separable and they are more robust. The depth means that this is a multi-resolution multi-channel learning process. We think that sparse graph based deep neural network can more effectively make similar objects to attract each other, the relative, different objects mutually exclusive, similar to a better sparse multi-resolution clustering. Based on this concept, we propose a sparse graph representation based on the face correlation information that is embedded via the sparse reconstruction and deep learning within an irregular domain. The resulting classification is remarkably robust. The proposed method achieves high recognition rates of 99.61% (94.67%) on the benchmark LFW (YTF) facial evaluation database.

This letter describes a method that characterizes and improves the performance of a time-interleaved (TI) digital-to-analog converter (DAC) system by using multiport signal-flow graphs at microwave frequencies. A commercial signal generator with two TI DACs was characterized through s-parameter measurements and was compared to the conventional method. Moreover, prefilters were applied to correct the response, resulting in an error-vector magnitude improvement of greater than 8 dB for a 64-quadrature-amplitude-modulated signal of 4.8 Gbps. As a result, the bandwidth limitation and the complex post processing of the conventional method could be minimized.

Both placing responsibility of message sending on every IoT object and obfuscating the object's location from other objects are essential to realize a secure and privacy-preserved communication service. Two or more short-lived link identifiers (or pseudonyms) authorized by a trustable authority are often used in related studies, instead of a persistent or long-term use link identifier (i.e. vendor assigned MAC address). However, related studies have limitations in terms of frequently changing pseudonyms to enhance location privacy because the cryptographic algorithms used in them fixedly couple object's identifiers with its security keys. To overcome those limitations, we present a new pseudonym and key management scheme that enables dynamic coupling of pseudonym and key pairs without incurring any adverse impacts. Furthermore, we propose two lightweight pseudonym allocation protocols to effectively reduce the volume of message carrying the allocation parameters. Through qualitative analyses, we verify that the proposed scheme is more scalable than related approaches as it can efficiently allocate enough number of pseudonym/key pairs by reducing the control message overhead by more than 90%.

In historical learning, to grasp the causal relationship between historical events and to understand factors that bring about important events are significant for fostering the historical thinking. However, some students are not able to find historical events that have causal relationships. The view of observing the historical events is different among individuals, so it is not appropriate to define the historical events that have causal relationships and impose students to remember them. The students need to understand the definition of the causal relationships and find the historical events that satisfy the definition according to their viewpoints. The objective of this paper is to develop a support system for understanding the meaning of a causal relationship and creating causal relation graphs that represent the causal relationships between historical events. When historical events have a causal relationship, a state change caused by one event becomes the cause of the other event. To consider these state changes is critically important to connect historical events. This paper proposes steps for considering causal relationships between historical events by arranging the state changes of historical people along with them. It also develops the system that supports students to create the causal relation graph according to the state changes. In our system, firstly, the interface for arranging state changes of historical people according to the historical events is given. Then, the interface for drawing the causal relation graph of historical events is provided in which state changes are automatically indicated on the created links in the causal relation graph. By observing the indicated state changes on the links, students are able to check by themselves whether their causal relation graphs correctly represent the causal relationships between historical events.

This paper presents an adaptive least-significant-bit (LSB) steganography for spatial color images on smartphones. For each red, green, and blue color component, the combinations of All-4bit, One-4bit+Two-2bit, and Two-3bit+One-2bit LSB replacements are proposed for content-adaptivity and natural histograms. The high capacity of 8.4bpp with the average peak signal noise ratio (PSNR) 43.7db and fast processing times on smartphones are also demonstrated

A vertex subset F ⊆ V(G) is called a cyclic vertex-cut set of a connected graph G if G-F is disconnected such that at least two components in G-F contain cycles. The cyclic vertex connectivity is the cardinality of a minimum cyclic vertex-cut set. In this paper, we show that the cyclic vertex connectivity of the trivalent Cayley graphs TGn is equal to eight for n ≥ 4.

Utilizing software architecture patterns is important for reducing maintenance costs. However, maintaining code according to the constraints defined by the architecture patterns is time-consuming work. As described herein, we propose a technique to detect code fragments that are incompliant to the architecture as fine-grained architectural violations. For this technique, the dependence graph among code fragments extracted from the source code and the inference rules according to the architecture are the inputs. A set of candidate components to which a code fragment can be affiliated is attached to each node of the graph and is updated step-by-step. The inference rules express the components' responsibilities and dependency constraints. They remove candidate components of each node that do not satisfy the constraints from the current estimated state of the surrounding code fragment. If the inferred role of a code fragment does not include the component that the code fragment currently belongs to, then it is detected as a violation. We have implemented our technique for the Model-View-Controller for Web Application architecture pattern. By applying the technique to web applications implemented using Play Framework, we obtained accurate detection results. We also investigated how much does each inference rule contribute to the detection of violations.

Modeling user activities on the Web is a key problem for various Web services, such as news article recommendation and ad click prediction. In our work-in-progress paper[1], we introduced an approach that summarizes each sequence of user Web page visits using Paragraph Vector[3], considering users and URLs as paragraphs and words, respectively. The learned user representations are used among the user-related prediction tasks in common. In this paper, on the basis of analysis of our Web page visit data, we propose Backward PV-DM, which is a modified version of Paragraph Vector. We show experimental results on two ad-related data sets based on logs from Web services of Yahoo! JAPAN. Our proposed method achieved better results than those of existing vector models.

Non-volatile memories are a promising alternative to memory design but data stored in them still may be destructed due to crosstalk and radiation. The data stored in them can be restored by using error-correcting codes but they require extra bits to correct bit errors. One of the largest problems in non-volatile memories is that they consume ten to hundred times more energy than normal memories in bit-writing. It is quite necessary to reduce writing bits. Recently, a REC code (bit-write-reducing and error-correcting code) is proposed for non-volatile memories which can reduce writing bits and has a capability of error correction. The REC code is generated from a linear systematic error-correcting code but it must include the codeword of all 1's, i.e., 11…1. The codeword bit length must be longer in order to satisfy this condition. In this letter, we propose a method to generate a relaxed REC code which is generated from a relaxed error-correcting code, which does not necessarily include the codeword of all 1's and thus its codeword bit length can be shorter. We prove that the maximum flipping bits of the relaxed REC code is still limited theoretically. Experimental results show that the relaxed REC code efficiently reduce the number of writing bits.

A frequently occurring subcircuit consists of a loop of a resistor (R), a field-effect transistor (FET), and a capacitor (C). The FET acts as a switch, controlled at its gate terminal by a clock voltage. This subcircuit may be acting as a sample-and-hold (S/H), as a passive mixer (P-M), or as a bandpass filter or bandpass impedance. In this work, we will present a useful analysis that leads to a simple signal flow graph (SFG), which captures the FET-R-C circuit's action completely across a wide range of design parameters. The SFG dissects the circuit into three filtering functions and ideal sampling. This greatly simplifies analysis of frequency response, noise, input impedance, and conversion gain, and leads to guidelines for optimum design. This paper focuses on the analysis of a single-path FET-R-C circuit's signal transfer characteristics including the reconstruction of the complete waveform from the discrete-time sampled voltage.

The microfabrication technique based on SR (Synchrotron Radiation) direct etching process has recently been applied to construct PTFE microstructures. This paper attempts to fabricate an integrated PTFE-filled waveguide Butler matrix for short millimeter-wave by SR direct etching. First, a cruciform 3-dB directional coupler and an intersection circuit (0-dB coupler) are designed at 180 GHz. Then, a 4×4 Butler matrix with horn antennas is designed and fabricated. Finally, the measured radiation patterns of the Butler matrix are shown.

In this paper, we propose the first identity-based dynamic multi-cast key distribution (ID-DMKD) protocol which is secure against maximum exposure of secret information (e.g., secret keys and session-specific randomness). In DMKD protocols, users share a common session key without revealing any information of the session key to the semi-honest server, and can join/leave to/from the group at any time even after establishing the session key. Most of the known DMKD protocols are insecure if some secret information is exposed. Recently, an exposure resilient DMKD protocol was introduced, however, each user must manage his/her certificate by using the public-key infrastructure. We solve this problem by constructing the DMKD protocol authenticated by user's ID (i.e., without certificate). We introduce a formal security definition for ID-DMKD by extending the previous definition for DMKD. We must carefully consider exposure of the server's static secret key in the ID-DMKD setting because exposure of the server's static secret key causes exposure of all users' static secret keys. We prove that our protocol is secure in our security model in the standard model. Another advantage of our protocol is scalability: communication and computation costs of each user are independent from the number of users. Furthermore, we show how to extend our protocol to achieve non-interactive join by using certificateless encryption. Such an extension is useful in applications that the group members frequently change like group chat services.

Direct-binary search method has been used for converting complex holograms into binary format. However, this algorithm is optimized to reconstruct monochromatic digital holograms and is accurate only in a narrow-depth range. In this paper, we proposed an advanced direct-binary search method to increase the depth of field of 3D scenes reconstructed in RGB by binary holograms.