Winternitz One-Time Signature (OTS) is an essential component in practical hash-based digital signature schemes that are regarded as quantum secure. This study aims to improve the efficiency of Winternitz OTS without impairing its provable security. The improvement is brought by a novel fingerprinting function that can be realized from an existing secure finger-printing function and an efficiently computable mapping. Besides the security proof of the strongly existential unforgeability, it is shown that the proposed scheme is the optimum in the sense that it minimizes the size of hash chains needed, and thus has the smallest computational costs for signature operations among all Winternitz-style OTS.

This study investigates the computational complexity of solving hash puzzles using quantum algorithms. A hash puzzle is formalized as a problem for finding a pre-image whose hash value falls within a specified target set. It is known that Grover quantum search algorithm and Boyer algorithm, which is a Bayesian utilization of Grover algorithm, can compute the preimage of a given hash value more efficiently than non-quantum algorithms. However, those quantum algorithms use implicit assumptions and approximations that are not compatible with a general hash puzzle. This study revises Boyer algorithm by excluding those assumptions and approximations, and clarifies the relation between the size of the target set of a hash puzzle and the complexity necessary for solving the puzzle. It is shown that, in the quantum framework, a hash puzzle with fewer targets can be easier to solve than a hash puzzle with more targets, which contradicts to the classical understanding where puzzles with fewer targets are more difficult to solve.

Time-based One-Time Password (TOTP) is commonly used in many digital services to meet the increasing demands of security in user authentication. The security of TOTP owes much to the management of TOTP seeds from which onetime passwords are computed, but there is a certain risk of the leakage of TOTP seeds in practice. This study aims to bring a mechanism that virtually realizes the expiration of TOTP seeds. Even if a seed is left unattended or exposed to somebody at a certain point in time, the seed expires as time passes. The mechanism is developed by using the logistic map, together with careful control of numeric values that is necessary to avoid issues caused by finite-precision calculations. The paper sketches the proposed scheme and introduces the results of numerical investigations for discussing choices of good parameters.

The maximum likelihood (ML) decoding is essential for error-correcting codes, but the ML decoding problem is NP-hard in general. This suggests that there is no single universal ML decoding algorithm that works efficiently for an arbitrary code. Therefore researchers developed many ML decoding algorithms with different characteristics so that they can be used complementary. This study is intended to propose an ML decoding algorithm that can be used for general non-binary linear codes. The algorithm proposed in this paper is a generalization of the adaptive and recursive ML decoding algorithm that was studied for binary codes. This paper shows that the structure and properties of linear codes that helped realizing the decoding algorithm for binary codes can be generalized to nonbinary cases, and reports the implementation results of the soft-decision ML decoding alogorithm for several non-binary linear codes.

The purpose of this study is to derive an upper-bound and a lower-bound of the entropy of a multinomial distribution. In spite of its practicality and versatility, there is no closed-form formula of the entropy of the multinomial distribution. Cichoń derived an asymptotic formula that approximates the entropy, but the approximation is not very useful because it can yield fatal error for non-asymptotic parameters, and there is no clear perspective of the approximation error. This paper proposes an upper-bound and a lower-bound formulas of the entropy of the multinomial distribution. The formulas are effective for arbitrary parameters, and contribute to the quantitative discussion of the entropy of the multinomial distribution.

The expected write deficiency of the index-less indexed flash codes (ILIFC) is studied, and a technique is developed to improve the write deficiency of ILIFC. ILIFC is a coding scheme for flash memory, and consists of two stages with different coding techniques. This study first clarify the average write deficiency of the first stage of ILIFC, and shows that omitting the second stage of ILIFC can be a practical option for realizing flash codes with good average performance. The study also investigates an improvement of the index-less coding which is used in the first stage of ILIFC. The improvement reduces the write deficiency of ILIFC, and relaxes the constraints on the rate of the code.

This paper investigates a mutual authentication scheme by making use of the visual secret sharing (VSS) scheme. The main concern of the investigated scheme is that it is easy for novice users to use the system. Novice users are seriously threatened by recently increasing phishing fraud. There are many technical countermeasures against phishing attacks, but those means are often too difficult for novice users to understand, set-up and utilize. In this paper, a scheme is investigated which does not require special hardware, software, plug-ins and so on. Thanks to the characteristics of the VSS scheme, users are able to obtain minimum but practical security by using their accustomed web browsers only. This paper discusses protocols which allow novice users protect themselves from phishing attacks. A prototype implementation of the proposed scheme is also introduced briefly.

The number of minimum weight codewords is an important parameter to measure the potential performance of a linear block code. This paper studies the number of minimum weight codewords of simple and full-length array (SFA) LDPC codes. The notion of a cyclic shift closure is introduced, and it is shown that the set of minimum weight codewords of the code is partitioned by cyclic shift closures of minimum weight codewords. Each cyclic shift closure is generated from a special codeword. With the help of computer experiment, general algebraic forms of the special codewords are determined. As the result, the numbers of minimum weight codewords of several classes of SFA-LDPC codes are clearly expressed by formulas.

Simple and full-length array LDPC codes (SFA-LDPC codes) is a class of LDPC codes which are algebraically constructed from a family of array codes. The minimum weight of SFA-LDPC codes has been investigated in literatures, but exact minimum weight of the code is not known except for some small parameters. In this paper it is shown that the class of SFA-LDPC codes which are denoted byCA(p, 4) in this paper contains a codeword whose minimum weight is 10 or less, ifpis a prime number greater than 7. Combined with the Yang's lower bound on the minimum weight ofCA(p,4), this implies that the minimum weight ofCA(p, 4) is exactly 10 for any prime p withp> 7.

A number of grammatical formalisms have been proposed to describe the syntax of natural languages, and the universal recognition problems for some of those classes of grammars have been studied. A universal recognition problem for a class Q of grammars is the one to decide, taking a grammar G ∈ G and a string ui as an input, whether G can generate w or not. In this paper, the computational complexities of the universal recognition problems for parallel multiple context‐free grammars, multiple context‐free grammars, and their subclasses are discussed.

A number of grammatical formalisms were introduced to define the syntax of natural languages. Among them are parallel multiple context-free grammars (pmcfg's) and lexical-functional grammars (lfg's). Pmcfg's and their subclass called multiple context-free grammars (mcfg's) are natural extensions of cfg's, and pmcfg's are known to be recognizable in polynomial time. Some subclasses of lfg's have been proposed, but they were shown to generate an NP-complete language. Finite state translation systems (fts') were introduced as a computational model of transformational grammars. In this paper, three subclasses of lfg's called nc-lfg's, dc-lfg's and fc-lfg's are introduced and the generative capacities of the above mentioned grammatical formalisms are investigated. First, we show that the generative capacity of fts' is equal to that of nc-lfg's. As relations among subclasses of those formalisms, it is shown that the generative capacities of deterministic fts', dc-lfg's, and pmcfg's are equal to each other, and the generative capacity of fc-lfg's is equal to that of mcfg's. It is also shown that at least one NP-complete language is generated by fts'. Consequently, deterministic fts', dc-lfg's and fc-lfg's can be recognized in polynomial time. However, fts' (and nc-lfg's) cannot, if P ≠ NP.