Crystalline GaN films can be grown even on amorphous substrates with the use of graphene buffer layers by pulsed sputtering deposition (PSD). The graphene buffer layers allowed us to grow highly c-axis-oriented GaN films at low substrate temperatures. Full-color GaN-based LEDs can be fabricated on the GaN/graphene structures and they are operated successfully. This indicates that the present technique is promising for future large-area light-emitting displays on amorphous substrates.

In order to prevent the synonym substitution breaking the balance among frequencies of synonyms and improve the statistical undetectability, this paper proposed a novel linguistic steganography based on synonym run-length encoding. Firstly, taking the relative word frequency into account, the synonyms appeared in the text are digitized into binary values and expressed in the form of runs. Then, message are embedded into the parities of runs' lengths by self-adaptively making a positive or negative synonym transformation on boundary elements of two adjacent runs, while preserving the number of relative high and low frequency synonyms to reduce the embedding distortion. Experimental results have shown that the proposed synonym run-length encoding based linguistic steganographic algorithm makes fewer changes on the statistical characteristics of cover texts than other algorithms, and enhances the capability of anti-steganalysis.

This paper explores the feasibility of power analysis attacks against low-latency block ciphers implemented with unrolled architectures capable of encryption/decryption in a single clock cycle. Unrolled architectures have been expected to be somewhat resistant against side-channel attacks compared to typical loop architectures because of no memory (i.e. register) element storing intermediate results in a synchronous manner. In this paper, we present a systematic method for selecting Points-of-Interest for power analysis on unrolled architectures as well as calculating dynamic power consumption at a target function. Then, we apply the proposed method to PRINCE, which is known as one of the most efficient low-latency ciphers, and evaluate its validity with an experiment using a set of unrolled PRINCE processors implemented on an FPGA. Finally, a countermeasure against such analysis is discussed.

Card-based protocols enable us to easily perform cryptographic tasks such as secure multiparty computation using a deck of physical cards. Since the first card-based protocol appeared in 1989, many protocols have been designed. A protocol is usually described with a series of somewhat intuitive and verbal descriptions, such as “turn over this card,” “shuffle these two cards,” “apply a random cut to these five cards,” and so on. On the other hand, a formal computational model of card-based protocols via abstract machine was constructed in 2014. By virtue of the formalization, card-based protocols can be treated more rigorously; for example, it enables one to discuss the lower bounds on the number of cards required for secure computations. In this paper, an overview of the computational model with its applications to designing protocols and a survey of the recent progress in card-based protocols are presented.

One of major ideas to design a multivariate public key cryptosystem (MPKC) is to generate its quadratic forms by a polynomial map over an extension field. In fact, Matsumoto-Imai's scheme (1988), HFE (Patarin, 1996), MFE (Wang et al., 2006) and multi-HFE (Chen et al., 2008) are constructed in this way and Sflash (Akkar et al., 2003), Quartz (Patarin et al., 2001), Gui (Petzoldt et al, 2015) are variants of these schemes. An advantage of such extension field type MPKCs is to reduce the numbers of variables and equations to be solved in the decryption process. In the present paper, we study the security of MPKCs whose quadratic forms are derived from a “quadratic” map over an extension field and propose a new attack on such MPKCs. Our attack recovers partial information of the secret affine maps in polynomial time when the field is of odd characteristic. Once such partial information is recovered, the attacker can find the plain-text for a given cipher-text by solving a system of quadratic equations over the extension field whose numbers of variables and equations are same to those of the system of quadratic equations used in the decryption process.

In the field of computer science, the network reliability problem for evaluating the network failure probability has been extensively investigated. For a given undirected graph G, the network failure probability is the probability that edge failures (i.e., edge erasures) make G unconnected. Edge failures are assumed to occur independently with the same probability. The main contributions of the present paper are the upper and lower bounds on the expected network failure probability. We herein assume a simple random graph ensemble that is closely related to the Erds-Rényi random graph ensemble. These upper and lower bounds exhibit the typical behavior of the network failure probability. The proof is based on the fact that the cut-set space of G is a linear space over F2 spanned by the incident matrix of G. The present study shows a close relationship between the ensemble analysis of the expected network failure probability and the ensemble analysis of the error detection probability of LDGM codes with column weight 2.

Patarin proposed a crytographic trapdoor called Hidden Field Equation (HFE), a trapdoor based on the Multivariate Quadratic (MQ) and the Isomorphism of Polynomials (IP) problems. The MQ problem was proved by Patarin et al.'s to be NP-complete. Although the basic HFE has been proved to be vulnerable to attacks, its variants obtained by some modifications have been proved to be stronger against attacks. The Quartz digital signature scheme based on the HFEv- trapdoor (a variant of HFE) with particular choices of parameters, has been shown to be stronger against algebraic attacks to recover the private key. Furthermore, it generates reasonably short signatures. However, Joux et al. proved (based on the Birthday Paradox Attack) that Quartz is malleable in the sense that, if an adversary gets a valid pair of message and signature, a valid signature to another related message is obtainable with 250 computations and 250 queries to the signing oracle. Currently, the recommended minimum security level is 2112. Our signature scheme is also based on Quartz but we achieve a 2112 security level against Joux et al.'s attack. It is also more efficient in signature verification and vector initializations. Furthermore, we implemented both the original and our improved Quartz signature and run empirical comparisons.

The key escrow problem and high computational cost are the two major problems that hinder the wider adoption of hierarchical identity-based signature (HIBS) scheme. HIBS schemes with either escrow-free (EF) or online/offline (OO) model have been proved secure in our previous work. However, there is no much EF or OO scheme that has been evaluated experimentally. In this letter, several EF/OO HIBS schemes are considered. We study the algorithmic complexity of the schemes both theoretically and experimentally. Scheme performance and practicability of EF and OO models are discussed.

Let G be a graph and K be a set of target vertices of G. Assume that all vertices of G, except the vertices in K, may fail with given probabilities. The K-terminal reliability of G is the probability that all vertices in K are mutually connected. This reliability problem is known to be #P-complete for general graphs. This work develops the first polynomial-time algorithm for computing the K-terminal reliability of circular-arc graphs.

The main contribution of this paper is a non-trivial expression, that is called dual expression, of the posterior values for non-adaptive group testing problems. The dual expression is useful for exact bitwise MAP estimation. We assume a simplest non-adaptive group testing scenario including N-objects with binary status and M-tests. If a group contains one or more positive object, the test result for the group is assumed to be one; otherwise, the test result becomes zero. Our inference problem is to evaluate the posterior probabilities of the objects from the observation of M-test results and the prior probabilities for objects. The derivation of the dual expression of posterior values can be naturally described based on a holographic transformation to the normal factor graph (NFG) representing the inference problem. In order to handle OR constraints in the NFG, we introduce a novel holographic transformation that converts an OR function to a function similar to an EQUAL function.

Non-volatile memories are paid attention to as a promising alternative to memory design. Data stored in them still may be destructed due to crosstalk and radiation. We can restore the data by using error-correcting codes which require extra bits to correct bit errors. Further, non-volatile memories consume ten to hundred times more energy than normal memories in bit-writing. When we configure them using error-correcting codes, it is quite necessary to reduce writing bits. In this paper, we propose a method to generate a bit-write-reducing code with error-correcting ability. We first pick up an error-correcting code which can correct t-bit errors. We cluster its codeswords and generate a cluster graph satisfying the S-bit flip conditions. We assign a data to be written to each cluster. In other words, we generate one-to-many mapping from each data to the codewords in the cluster. We prove that, if the cluster graph is a complete graph, every data in a memory cell can be re-written into another data by flipping at most S bits keeping error-correcting ability to t bits. We further propose an efficient method to cluster error-correcting codewords. Experimental results show that the bit-write-reducing and error-correcting codes generated by our proposed method efficiently reduce energy consumption. This paper proposes the world-first theoretically near-optimal bit-write-reducing code with error-correcting ability based on the efficient coding theories.

In this paper, an analysis of the basic process of a class of interactive-graph-cut-based image segmentation algorithms indicates that it is unnecessary to construct n-links for all adjacent pixel nodes of an image before calculating the maximum flow and the minimal cuts. There are many pixel nodes for which it is not necessary to construct n-links at all. Based on this, we propose a new algorithm for the dynamic construction of all necessary n-links that connect the pixel nodes explored by the maximum flow algorithm. These n-links are constructed dynamically and without redundancy during the process of calculating the maximum flow. The Berkeley segmentation dataset benchmark is used to prove that this method can reduce the average running time of segmentation algorithms on the premise of correct segmentation results. This improvement can also be applied to any segmentation algorithm based on graph cuts.

Web search queries are usually vague, ambiguous, or tend to have multiple intents. Users have different search intents while issuing the same query. Understanding the intents through mining subtopics underlying a query has gained much interest in recent years. Query suggestions provided by search engines hold some intents of the original query, however, suggested queries are often noisy and contain a group of alternative queries with similar meaning. Therefore, identifying the subtopics covering possible intents behind a query is a formidable task. Moreover, both the query and subtopics are short in length, it is challenging to estimate the similarity between a pair of short texts and rank them accordingly. In this paper, we propose a method for mining and ranking subtopics where we introduce multiple semantic and content-aware features, a bipartite graph-based ranking (BGR) method, and a similarity function for short texts. Given a query, we aggregate the suggested queries from search engines as candidate subtopics and estimate the relevance of them with the given query based on word embedding and content-aware features by modeling a bipartite graph. To estimate the similarity between two short texts, we propose a Jensen-Shannon divergence based similarity function through the probability distributions of the terms in the top retrieved documents from a search engine. A diversified ranked list of subtopics covering possible intents of a query is assembled by balancing the relevance and novelty. We experimented and evaluated our method on the NTCIR-10 INTENT-2 and NTCIR-12 IMINE-2 subtopic mining test collections. Our proposed method outperforms the baselines, known related methods, and the official participants of the INTENT-2 and IMINE-2 competitions.

Established in self-organized mode between mobile terminals (MT), mobile Ad Hoc networks are characterized by a fast change of network topology, limited power dissipation of network node, limited network bandwidth and poor security of the network. Therefore, this paper proposes an efficient one round certificateless authenticated group key agreement (OR-CLAGKA) protocol to satisfy the security demand of mobile Ad Hoc networks. Based on elliptic curve public key cryptography (ECC), OR-CLAGKA protocol utilizes the assumption of elliptic curve discrete logarithm problems (ECDLP) to guarantee its security. In contrast with those certificateless authenticated group key agreement (GKA) protocols, OR-CLAGKA protocol can reduce protocol data interaction between group users and it is based on efficient ECC public key infrastructure without calculating bilinear pairings, which involves negligible computational overhead. Thus, it is particularly suitable to deploy OR-CLAGKA protocol on MT devices because of its limited computation capacity and power consumption. Also, under the premise of keeping the forward and backward security, OR-CLAGKA protocol has achieved appropriate optimization to improve the performance of Ad Hoc networks in terms of frequent communication interrupt and reconnection. In addition, it has reduced executive overheads of key agreement protocol to make the protocol more suitable for mobile Ad Hoc network applications.

The Android pattern unlock is a popular graphical password scheme, where a user is presented a 3×3 grid and required to draw a pattern on the onscreen grid. Each pattern is a sequence of at least four contact points with some restrictions. Theoretically, the security level of unlock patterns is determined by the size of the pattern space. However, the number of possible patterns is only known for 3×3 and 4×4 grids, which was computed by brute-force enumeration. The only mathematical formula for the number of possible patterns is a permutation-based upper bound. In this article, we present an improved upper bound by counting the number of “visible” points that can be directly reached by a point.

In this work, a high efficiency coding unit (CU) size decision algorithm is proposed for high efficiency video coding (HEVC) inter coding. The CU splitting or non-splitting is modeled as a binary classification problem based on probability graphical model (PGM). This method incorporates two sub-methods: CU size termination decision and CU size skip decision. This method focuses on the trade-off between encoding efficiency and encoding complexity, and it has a good performance. Particularly in the high resolution application, simulation results demonstrate that the proposed algorithm can reduce encoding time by 53.62%-57.54%, while the increased BD-rate are only 1.27%-1.65%, compared to the HEVC software model.

In this paper, an insect classification method using scanning electron microphotographs is presented. Images taken by a scanning electron microscope (SEM) have a unique problem for classification in that visual features differ from each other by magnifications. Therefore, direct use of conventional methods results in inaccurate classification results. In order to successfully classify these images, the proposed method generates an optimal training dataset for constructing a classifier for each magnification. Then our method classifies images using the classifiers constructed by the optimal training dataset. In addition, several images are generally taken by an SEM with different magnifications from the same insect. Therefore, more accurate classification can be expected by integrating the results from the same insect based on Dempster-Shafer evidence theory. In this way, accurate insect classification can be realized by our method. At the end of this paper, we show experimental results to confirm the effectiveness of the proposed method.

The online interval coloring problem has been extensively studied for many years. Kierstead and Trotter (Congressus Numerantium 33, 1981) proved that their algorithm is an optimal online algorithm for this problem. The number of colors used by the algorithm is at most 3ω(G)-2, where ω(G) is the size of the maximum clique in a given graph G. Also, they presented an instance for which the number of colors used by any online algorithm is at least 3ω(G)-2. This instance includes intervals with various lengths, which cannot be applied to the case when the lengths of the given intervals are restricted to one, i.e., the online unit interval coloring problem. In this case, the current best upper and lower bounds on the number of colors used by an online algorithm are 2ω(G)-1 and 3ω(G)/2 respectively by Epstein and Levy (ICALP2005). In this letter, we conduct a complete performance analysis of the Kierstead-Trotter algorithm for online unit interval coloring, and prove it is NOT optimal. Specifically, we provide an upper bound of 3ω(G)-3 on the number of colors used by their algorithm. Moreover, the bound is the best possible.

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. In the case where each edge has the weight of a nonnegative integer, the problem of finding a minimum spanning tree with a non-terminal set VNT of G was known to be NP-hard. However, the complexity of finding a spanning tree on general graphs where each edge has the weight of one was unknown. In this paper, we consider this problem and first show that it is NP-hard even if each edge has the weight of one on general graphs. We also show that if G is a cograph then finding a spanning tree with a non-terminal set VNT of G is linearly solvable when each edge has the weight of one.

Light field data, which is composed of multi-view images, have various 3D applications. However, the cost of acquiring many images from slightly different viewpoints sometimes makes the use of light fields impractical. Here, compressive sensing is a new way to obtain the entire light field data from only a few camera shots instead of taking all the images individually. In paticular, the coded aperture/mask technique enables us to capture light field data in a compressive way through a single camera. A pixel value recorded by such a camera is a sum of the light rays that pass though different positions on the coded aperture/mask. The target light field can be reconstructed from the recorded pixel values by using prior information on the light field signal. As prior information, the current state of the art uses a dictionary (light field atoms) learned from training datasets. Meanwhile, it was reported that general bases such as those of the discrete cosine transform (DCT) are not suitable for efficiently representing prior information. In this study, however, we demonstrate that a 4D-DCT basis works surprisingly well when it is combined with a weighting scheme that considers the amplitude differences between DCT coefficients. Simulations using 18 light field datasets show the superiority of the weighted 4D-DCT basis to the learned dictionary. Furthermore, we analyzed a disparity-dependent property of the reconstructed data that is unique to light fields.