Recently, Quantum Annealing (QA) has attracted attention as an efficient algorithm for combinatorial optimization problems. In QA, the input data size becomes large and its reduction is important for accelerating by the hardware emulation since the usable memory size and its bandwidth are limited. The paper proposes the compression method of input sparse matrices for QA emulator. The proposed method uses the sparseness of the coefficient matrix and the reappearance of the same values. An independent table is introduced and data are compressed by the search and registration method of two consecutive data in the value table. The proposed method is applied to Traveling Salesman Problem (TSP) with 32, 64 and 96 cities and Nurse Scheduling Problem (NSP). The proposed method could reduce the amount of data by 1/40 for 96 city TSP and could manage 96 city TSP on the hardware emulator. When applied to NSP, we confirmed the effectiveness of the proposed method by the compression ratio ranging from 1/4 to 1/11.8. The data reduction is also useful for the simulation/emulation performance when using the compressed data directly and 1.9 times faster speed can be found on 96 city TSP than the CSR-based method.

We have realized a design automation platform of hardware accelerator for pairing operation over multiple elliptic curve parameters. Pairing operation is one of the fundamental operations to realize functional encryption. However, known as a computational complexity-heavy algorithm. Also because there have been not yet identified standard parameters, we need to choose curve parameters based on the required security level and affordable hardware resources. To explore this design optimization for each curve parameter is essential. In this research, we have realized an automated design platform for pairing hardware for such purposes. Optimization results show almost equivalent to those prior-art designs by hand.

Approximate computing (AC) saves energy and improves performance by introducing approximation into computation in error-torrent applications. This work focuses on an AC strategy that accurately performs important computations and approximates others. In order to make AC circuits practical, we need to determine which computation is how important carefully, and thus need to appropriately approximate the redundant computation for maintaining the required computational quality. In this paper, we focus on the importance of computations at the flip-flop (FF) level and propose a novel importance evaluation methodology. The key idea of the proposed methodology is a two-step fault injection algorithm to extract the near-optimal set of redundant FFs in the circuit. In the first step, the proposed methodology performs the FI simulation for each FF and extracts the candidates of redundant FFs. Then, in the second step, the proposed methodology extracts the set of redundant FFs in a binary search manner. Thanks to the two-step strategy, the proposed algorithm reduces the complexity of architecture exploration from an exponential order to a linear order without understanding the functionality and behavior of the target application program. Experimental results show that the proposed methodology identifies the candidates of redundant FFs depending on the given constraints. In a case study of an image processing accelerator, the truncation for identified redundant FFs reduces the circuit area by 29.6% and saves power dissipation by 44.8% under the ASIC implementation while satisfying the PSNR constraint. Similarly, the dynamic power dissipation is saved by 47.2% under the FPGA implementation.

Stabilizer-based quantum secret sharing has two methods to reconstruct a quantum secret: The erasure correcting procedure and the unitary procedure. It is known that the unitary procedure has a smaller circuit width. On the other hand, it is unknown which method has smaller depth and fewer circuit gates. In this letter, it is shown that the unitary procedure has smaller depth and fewer circuit gates than the erasure correcting procedure which follows a standard framework performing measurements and unitary operators according to the measurements outcomes, when the circuits are designed for quantum secret sharing using the [[5, 1, 3]] binary stabilizer code. The evaluation can be reversed if one discovers a better circuit for the erasure correcting procedure which does not follow the standard framework.

Previously, we proposed a probabilistic data generation model represented by an unobservable tree and a sequential updating method to calculate a posterior distribution over a set of trees. The set is called a meta-tree. In this paper, we propose a more efficient batch updating method.

It is proven that many public-key cryptosystems would be broken by the quantum computer. The knapsack cryptosystem which is based on the subset sum problem has the potential to be a quantum-resistant cryptosystem. Murakami and Kasahara proposed a SOSI trapdoor sequence which is made by combining shifted-odd (SO) and super-increasing (SI) sequence in the modular knapsack cryptosystem. This paper firstly show that the key generation method could not achieve a secure density against the low-density attack. Second, we propose a high-density key generation method and confirmed that the proposed scheme is secure against the low-density attack.

Information-theoretic lower bounds of the Bayes risk have been investigated for a problem of parameter estimation in a Bayesian setting. Previous studies have proven the lower bound of the Bayes risk in a different manner and characterized the lower bound via different quantities such as mutual information, Sibson's α-mutual information, f-divergence, and Csiszár's f-informativity. In this paper, we introduce an inequality called a “meta-bound for lower bounds of the Bayes risk” and show that the previous results can be derived from this inequality.

In this paper, we introduce a framework of distributed orthogonal approximate message passing for recovering sparse vector based on sensing by multiple nodes. The iterative recovery process consists of local computation at each node, and global computation performed either by a particular node or joint computation on the overall network by exchanging messages. We then propose a method to reduce the communication cost between the nodes while maintaining the recovery performance.

Distributed computing is one of the powerful solutions for computational tasks that need the massive size of dataset. Lagrange coded computing (LCC), proposed by Yu et al. [15], realizes private and secure distributed computing under the existence of stragglers, malicious workers, and colluding workers by using an encoding polynomial. Since the encoding polynomial depends on a dataset, it must be updated every arrival of new dataset. Therefore, it is necessary to employ efficient algorithm to construct the encoding polynomial. In this paper, we propose Newton coded computing (NCC) which is based on Newton interpolation to construct the encoding polynomial. Let K, L, and T be the number of data, the length of each data, and the number of colluding workers, respectively. Then, the computational complexity for construction of an encoding polynomial is improved from O(L(K+T)log 2(K+T)log log (K+T)) for LCC to O(L(K+T)log (K+T)) for the proposed method. Furthermore, by applying the proposed method, the computational complexity for updating the encoding polynomial is improved from O(L(K+T)log 2(K+T)log log (K+T)) for LCC to O(L) for the proposed method.

As one of privacy-enhancing authentications suitable for decentralized environments, ring signatures have intensively been researched. In ring signatures, each user can choose any ad-hoc set of users (specified by public keys) called a ring, and anonymously sign a message as one of the users. However, in applications of anonymous authentications, users may misbehave the service due to the anonymity, and thus a mechanism to exclude the anonymous misbehaving users is required. However, in the existing ring signature scheme, a trusted entity to open the identity of the user is needed, but it is not suitable for the decentralized environments. On the other hand, as another type of anonymous authentications, a decentralized blacklistable anonymous credential system is proposed, where anonymous misbehaving users can be detected and excluded by a blacklist. However, the DL-based instantiation needs O(N) proof size for the ring size N. In the research line of the DL-based ring signatures, an efficient scheme with O(log N) signature size, called DualRing, is proposed. In this paper, we propose a DL-based blacklistable ring signature scheme extended from DualRing, where in addition to the short O(log N) signature size for N, the blacklisting mechanism is realized to exclude misbehaving users. Since the blacklisting mechanism causes additional costs in our scheme, the signature size is O(log N+l), where l is the blacklist size.

A channel coding problem with cost constraint for general channels is considered. Verdú and Han derived ϵ-capacity for general channels. Following the same lines of its proof, we can also derive ϵ-capacity with cost constraint. In this paper, we derive a formula for ϵ-capacity with cost constraint allowing overrun. In order to prove this theorem, a new variation of Feinstein's lemma is applied to select codewords satisfying cost constraint and codewords not satisfying cost constraint.

The context tree model has the property that the occurrence probability of symbols is determined from a finite past sequence and is a broader class of sources that includes i.i.d. or Markov sources. This paper proposes a non-stationary source with context tree models that change from interval to interval. The Bayes code for this source requires weighting of the posterior probabilities of the context tree models and change points, so the computational complexity of it usually increases to exponential order. Therefore, the challenge is how to reduce the computational complexity. In this paper, we propose a special class of prior probability distribution of context tree models and change points and develop an efficient Bayes coding algorithm by combining two existing Bayes coding algorithms. The algorithm minimizes the Bayes risk function of the proposed source in this paper, and the computational complexity of the proposed algorithm is polynomial order. We investigate the behavior and performance of the proposed algorithm by conducting experiments.

The class of k-bit delay decodable codes, source codes allowing decoding delay of at most k bits for k≥0, can attain a shorter average codeword length than Huffman codes. This paper discusses the general properties of the class of k-bit delay decodable codes with a finite number of code tables and proves two theorems which enable us to limit the scope of codes to be considered when discussing optimal k-bit delay decodable codes.

The achievability part of the rate-distortion theorem is proved by showing existence of good codes. For i.i.d. sources, two methods showing existence are known; random coding and non-random coding. For general sources, however, no proof in which good codes are constructed with non-random coding is found. In this paper, with a non-random method of code construction, we prove the achievability part of the rate-distortion theorem for general sources. Moreover, we also prove a stochastic variation of the rate-distortion theorem with the same method.

This paper proposes three new information measures for individual sequences and clarifies their properties. Our new information measures are called as the non-overlapping max-entropy, the overlapping smooth max-entropy, and the non-overlapping smooth max-entropy, respectively. These measures are related to the fixed-length coding of individual sequences. We investigate these measures, and show the following three properties: (1) The non-overlapping max-entropy coincides with the topological entropy. (2) The overlapping smooth max-entropy and the non-overlapping smooth max-entropy coincide with the Ziv-entropy. (3) When an individual sequence is drawn from an ergodic source, the overlapping smooth max-entropy and the non-overlapping smooth max-entropy coincide with the entropy rate of the source. Further, we apply these information measures to the fixed-length coding of individual sequences, and propose some new universal coding schemes which are asymptotically optimum.

In this study, we consider the data compression with side information available at both the encoder and the decoder. The information source is assigned to a variable-length code that does not have to satisfy the prefix-free constraints. We define several classes of codes whose codeword lengths and error probabilities satisfy worse-case criteria in terms of side-information. As a main result, we investigate the exact first-order asymptotics with second-order bounds scaled as Θ(√n) as blocklength n increases under the regime of nonvanishing error probabilities. To get this result, we also derive its one-shot bounds by employing the cutoff operation.

The present study proposes a scheme in which variable-length orthogonal codes generated by combining inverse discrete Fourier transform matrices over a finite field multiplex user data into a multiplexed sequence and its sequence forms one or a plural number of codewords for Reed-Solomon coding. The proposed scheme realizes data multiplexing, error correction coding, and multi-rate transmitting at the same time. This study also shows a design example and its performance analysis of the proposed scheme.

Information-theoretic security and computational security are fundamental paradigms of security in the theory of cryptography. The two paradigms interact with each other but have shown different progress, which motivates us to explore the intersection between them. In this paper, we focus on Multi-Party Computation (MPC) because the security of MPC is formulated by simulation-based security, which originates from computational security, even if it requires information-theoretic security. We provide several equivalent formalizations of the security of MPC under a semi-honest model from the viewpoints of information theory and statistics. The interpretations of these variants are so natural that they support the other aspects of simulation-based security. Specifically, the variants based on conditional mutual information and sufficient statistics are interesting because security proofs for those variants can be given by information measures and factorization theorem, respectively. To exemplify this, we show several security proofs of BGW (Ben-Or, Goldwasser, Wigderson) protocols, which are basically proved by constructing a simulator.

Adversarial examples (AEs), which cause misclassification by adding subtle perturbations to input images, have been proposed as an attack method on image-classification systems using deep neural networks (DNNs). Physical AEs created by attaching stickers to traffic signs have been reported, which are a threat to traffic-sign-recognition DNNs used in advanced driver assistance systems. We previously proposed an attack method for generating a noise area on images by superimposing an electrical signal on the mobile industry processor interface and showed that it can generate a single adversarial mark that triggers a backdoor attack on the input image. Therefore, we propose a misclassification attack method n DNNs by creating AEs that include small perturbations to multiple places on the image by the fault injection. The perturbation position for AEs is pre-calculated in advance against the target traffic-sign image, which will be captured on future driving. With 5.2% to 5.5% of a specific image on the simulation, the perturbation that induces misclassification to the target label was calculated. As the experimental results, we confirmed that the traffic-sign-recognition DNN on a Raspberry Pi was successfully misclassified when the target traffic sign was captured with. In addition, we created robust AEs that cause misclassification of images with varying positions and size by adding a common perturbation. We propose a method to reduce the amount of robust AEs perturbation. Our results demonstrated successful misclassification of the captured image with a high attack success rate even if the position and size of the captured image are slightly changed.

In the field of machine learning security, as one of the attack surfaces especially for edge devices, the application of side-channel analysis such as correlation power/electromagnetic analysis (CPA/CEMA) is expanding. Aiming to evaluate the leakage resistance of neural network (NN) model parameters, i.e. weights and biases, we conducted a feasibility study of CPA/CEMA on floating-point (FP) operations, which are the basic operations of NNs. This paper proposes approaches to recover weights and biases using CPA/CEMA on multiplication and addition operations, respectively. It is essential to take into account the characteristics of the IEEE 754 representation in order to realize the recovery with high precision and efficiency. We show that CPA/CEMA on FP operations requires different approaches than traditional CPA/CEMA on cryptographic implementations such as the AES.