Currently there is not any prospect of realizing quantum computers which can compute prime factorization, which RSA relies on, or discrete logarithms, which ElGamal relies on, of practical size. Additionally the rapid growth of Internet of Things (IoT) is requiring practical public key cryptosystems which do not use exponential operation. Therefore we constituted a cryptosystem relying on the difficulty of factoring the product of two large prime numbers, based on the Chinese Remainder Theorem, fully exploiting another strength of MPKC that exponential operation is not necessary. We evaluated its security by performing the Gröbner base attacks with workstations and consequently concluded that it requires computation complexity no less than entirely random quadratic polynomials. Additionally we showed that it is secure against rank attacks since the polynomials of central map are all full rank, assuming the environment of conventional computers.

We propose a practical blind channel identification algorithm based on the principal component analysis. The algorithm estimates (1) the channel order, (2) the noise variance, and then identifies (3) the channel impulse response, from the autocorrelation of the channel output signal without using the eigenvalue and singular-value decomposition. The special features of the proposed algorithm are (1) practical method to find the channel order and (2) reduction of computational complexity. Numerical examples show the effectiveness of the proposed algorithm.

We show that, if NP language L has an invulnerable generator and if L has an honest verifier standard statistical ZKIP, then L has a 5 move statistical ZKIP. Our class of languages involves random self reducible languages because they have standard perfect ZKIPs. We show another class of languages (class K) which have standard perfect ZKIPs. Blum numbers and a set of graphs with odd automorphism belong to this class. Therefore, languages in class K have 5 move statistical ZKIPs if they have invulnerable generators.

Following the last proposal of the nonlinear Piece in Hand method, which has 3-layer structure, 2-layer nonlinear Piece in Hand method is proposed. Both of them aim at enhancing the security of existing and future multivariate public key cryptosystems. The new nonlinear Piece in Hand is compared with the 3-layer method and PMI+, which was proposed by Ding, et al.

In 1978, Merkle and Hellman published two kinds of knapsack type public key cryptosystems, one of which was super-increasing type and the other was multiplicative type. However, the former was broken by Shamir in 1982 and latter was broken by Odlyzko in 1984. Recently, Chor and Rivest proposed a new multiplicative knapsack type cryptosystem based on arithmetic in GF (ph) which cannot be broken by the Odlyzko attack. This paper shows the new cryptosystem is broken if the public knapsack vector has three elements whose values are close to one another or if the primitive polynomial is known. We also present that not only the original secret-key also many other ones can decipher the cryptosystem.

Since the proposal of differential cryptanalysis and linear cryptanalysis in 1991 and 1993, respectively, the resistance to these cryptanalysis has been studied. In FSE2, Knudsen proposed a method of attacking block ciphers that used the higher order differential, and in FSE4, Jakobsen and Knudsen applied it to a cipher proposed by Nyberg and Knudsen. Their approach, however, requires large complexity of running time. In this paper, we improve this attack and show that our improved algorithm requires much fewer chosen texts and much less complexity than those of previous works.

A new signature scheme of MPKC is proposed. It is created by perturbing a traditional encryption scheme in two ways. The proposed perturbation polynomials successfully reinforce the Matsumoto-Imai cryptosystem This new signature scheme has a structure very difficult to cryptanalyze. Along with the security against algebraic attacks, its security against existing attacks is discussed. The experimental data imply that the scheme can create a both lightweight and secure signature system.

The linear Piece In Hand (PH, for short) matrix method with random variables was proposed in our former work. It is a general prescription which can be applicable to any type of multivariate public-key cryptosystems for the purpose of enhancing their security. Actually, we showed, in an experimental manner, that the linear PH matrix method with random variables can certainly enhance the security of HFE against the Grobner basis attack, where HFE is one of the major variants of multivariate public-key cryptosystems. In 1998 Patarin, Goubin, and Courtois introduced the plus method as a general prescription which aims to enhance the security of any given MPKC, just like the linear PH matrix method with random variables. In this paper we prove the equivalence between the plus method and the primitive linear PH matrix method, which is introduced by our previous work to explain the notion of the PH matrix method in general in an illustrative manner and not for a practical use to enhance the security of any given MPKC. Based on this equivalence, we show that the linear PH matrix method with random variables has the substantial advantage over the plus method with respect to the security enhancement. In the linear PH matrix method with random variables, the three matrices, including the PH matrix, play a central role in the secret-key and public-key. In this paper, we clarify how to generate these matrices and thus present two probabilistic polynomial-time algorithms to generate these matrices. In particular, the second one has a concise form, and is obtained as a byproduct of the proof of the equivalence between the plus method and the primitive linear PH matrix method.

The self-organization rule of planar neural networks has been proposed for learning of 2D distributions. However, it cannot be applied to 3D objects. In this paper, we propose a new model for global representation of the 3D objects. Based on this model, global topology reserving self-organization is achieved using parallel local competitive learning rule such as Kohonen's maps. The proposed model is able to represent the objects distributively and easily accommodate local features.

In this paper, we consider ZKIPs for promise problems. A promise problem is a pair of predicates (Q,R). A Turning machine T solves the promise problem (Q,R) if, for every x satisfying Q(x), machine T halts and it answers "yes" iff R(x). When ¬Q (x), we do not care what T does. First, we define "promised BPP" which is a promise problem version of BPP. Then, we prove that a promise problem (Q,R) has a 3-move interactive proof system which is black-box simulation zero knowledge if and only if (Q,R) ∈ promised BPP. Next, we show a "4-move" perfect ZKIPs (black-box simulation) for a promise problem of Quadratic Residuosity and that of Blum Numbers under no cryptographic assumption.

We propose a noise suppression algorithm with the Kalman filter theory. The algorithm aims to achieve robust noise suppression for the additive white and colored disturbance from the canonical state space models with (i) a state equation composed of the speech signal and (ii) an observation equation composed of the speech signal and additive noise. The remarkable features of the proposed algorithm are (1) applied to adaptive white and colored noises where the additive colored noise uses babble noise, (2) realization of high performance noise suppression without sacrificing high quality of the speech signal despite simple noise suppression using only the Kalman filter algorithm, while many conventional methods based on the Kalman filter theory usually perform the noise suppression using the parameter estimation algorithm of AR (auto-regressive) system and the Kalman filter algorithm. We show the effectiveness of the proposed method, which utilizes the Kalman filter theory for the proposed canonical state space model with the colored driving source, using numerical results and subjective evaluation results.

Genus 3 hyperelliptic curve cryptosystems are capable of fast-encryption on a 64-bit CPU, because a 56-bit field is enough for their definition fields. Recently, Kuroki et al. proposed an extension of the Harley algorithm, which had been known as the fastest addition algorithm of divisor classes on genus 2 hyperelliptic curves, on genus 3 hyperelliptic curves and Pelzl et al. improved the algorithm. This paper shows an improvement of the Harley algorithm on genus 3 hyperelliptic curves using Toom's multiplication. The proposed algorithm takes only I + 70M for an addition and I + 71M for a doubling instead of I + 76M and I + 74M respectively, which are the best possible of the previous works, where I and M denote the required time for an inversion and a multiplication over the definition field respectively. This paper also shows 2 variations of the proposed algorithm in order to adapt the algorithm to various platforms. Moreover this paper discusses finite field arithmetic suitable for genus 3 hyperelliptic curve cryptosystems and shows implementation results of the proposed algorithms on a 64-bit CPU. The implementation results show a 160-bit scalar multiplication can be done within 172 µs on a 64-bit CPU Alpha EV68 1.25 GHz.

The Weil descent attack, suggested by Frey, has been implemented by Gaudry, Hess and Smart (the so-called GHS attack) on elliptic curves over finite fields of characteristic two and with composite extension degrees. Recently, Diem presented a general treatment of the GHS attack to hyperelliptic curves over finite fields of arbitrary odd characteristics. This paper shows that Diem's approach can be extended to curves of which the function fields are cyclic Galois extensions. In particular, we show the existence of GHS Weil restriction, triviality of the kernel of GHS conorm-norm homomorphism, and lower/upper bounds of genera of the resulting curves.

It is widely believed to take exponential time to find a solution of a system of random multivariate polynomials because of the NP-completeness of such a task. On the other hand, in most of multivariate public key cryptosystems proposed so far, the computational complexity of cryptanalysis is polynomial time due to the trapdoor structure. In this paper, we introduce a new concept, piece in hand (soldiers in hand) matrix, which brings the computational complexity of cryptanalysis of multivariate public key cryptosystems close to exponential time by adding random polynomial terms to original cryptosystems. This is a general concept which can be applicable to any type of multivariate public key cryptosystems for the purpose of enhancing their security. As an implementation of the concept, we propose the linear PH matrix method with random variables. In 2003 Faugere and Joux broke the first HFE challenge (80 bits), where HFE is one of the major variants of multivariate public key cryptosystem, by computing a Grobner basis of the public key of the cryptosystem. We show, in an experimental manner, that the linear PH matrix method with random variables can enhance the security of HFE even against the Grobner basis attack. In what follows, we consider the strength of the linear PH matrix method against other possible attacks.

Broadcasting with secrecy of messages is important in a situation such as pay television. In pay television only a broadcasting station broadcasts a message. On the other hand, broadcast communication is also important. Broadcast communication means any user in a whole group can broadcast a message to any subset of the group. In this paper the efficiency of secure broadcast communication is discussed in terms of the length of messages sent and the encryption speed. We prove that the length of the broadcast messages is not kept less than O(n), where n is the number of receivers, when a broadcast system has a form of a single system which is defined as the generalized form of an individual key method and a master key method. In contrast, the proposed secure broadcast communication method, a multi-dimension method, keeps the length of messages sent O(mmn), where m is the number of the dimension used in the multi-dimension method. At the same time the encryption speed was reduced from O(n(log(n+C2)+C3)) of the master key method to O(mn(logmn+C1)) of the multi-dimension method.

This note presents a new global optimization method and derives a learning schema based on the method for multilayer artificial neural networks. The schema consists of (1) pasting" the admissible region in Rn to a n-D torus Tn and smoothly connecting the potential function at the boundary; (2) global searching along the flow of a nonvanishing vector field on the compact smooth manifold Tn. This flow is featured by the ability of automatically passing through distinct local minima one after another along the negative/positive gradient field. It has also a unit norm everywhere on the Tn, so the searching speed will not slow down in the neighborhood of critical points.

Mobile communication networks need public key cryptosystems that offer both low computation cost and user authentication. Tatebayashi et al. showed a key distribution protocol for such networks at Crypto'89 based on low exponent RSA. This paper shows that their protocol is not secure. We also present two types of secure and efficient key distribution protocols.

This paper shows a collision free hash function which is based on the r-th residue cryptosystem (not based on the claw free pairs). In the proposed method, finding a collision pair is as hard as factorization.

In this paper it is pointed out that although an elegant differential-like approach is developed, Coppersmith' attacking method on NIKS-TAS cannot succeed to forge a shared key of legitimate entities especially when p-1 contains highly composite divisors, as well as decomposibility-hard divisors. This is mainly due to a severe reduction of modulo size. Computer simulation results confirm this assertion. The ambiguity in the solutions to the collusion equations in the first phase can be analyzed by the elementary divisor theory. Moreover, two basis vectors, qi,ri in the second phase, are found to be inadequate to represent the space spanned by xi-yi and ui-vi(i=1,...,N), because qi,ri exist frequently over the space with small modulo size. Then, the erroneous values of αi,βi,...,εi(i=1,...,N) are derived from the inadequate basis vectors, qi,ri. Also, when the degeneracy in modulo size happens, the solutions to αi,βi,...,εi(i=1,...,N) cannot be solved even by means of the exhaustive search over the small prime divisors of p-1.

In this paper we present a new, two-centered electronic voting scheme that is capable of preserving privacy, universal verifiability, and robustness. An interesting property of our scheme is the use of double encryption with additive homomorphic encryption functions. In the two-centered scheme, the first center decrypts the ballots, checks the eligibility of the voters, and multiplies each eligible vote, which is still encrypted in the cryptosystem of the second center. After the deadline is reached, the second center obtains the final tally by decrypting the accumulated votes. As such, both centers cannot know the content of any individual vote, as each vote is hidden in the accumulated result, therefore the privacy of the voters is preserved. Our protocols, together with some existing protocols, allow everyone to verify that all valid votes are correctly counted. We apply the r-th residue cryptosystem as the homomorphic encryption function. Although decryption in the r-th residue cryptosystem requires an exhaustive search for all possible values, based on experiments we show that it is possible to achieve desirable performance for large-scale elections.