In some applications, a short private exponent d is chosen to improve the decryption or signing process for RSA public key cryptosystem. However, in a typical RSA, if the private exponent d is selected first, the public exponent e should be of the same order of magnitude as φ(N). Sun et al. devised three RSA variants using unbalanced prime factors p and q to lower the computational cost. Unfortunately, Durfee & Nguyen broke the illustrated instances of the first and third variants by solving small roots to trivariate modular polynomial equations. They also indicated that the instances with unbalanced primes p and q are more insecure than the instances with balanced p and q. This investigation focuses on designing a new RSA variant with balanced p and q, and short exponents d and e, to improve the security of an RSA variant against the Durfee & Nguyen's attack, and the other existing attacks. Furthermore, the proposed variant (Scheme A) is also extended to another RSA variant (Scheme B) in which p and q are balanced, and a trade-off between the lengths of d and e is enable. In addition, we provide the security analysis and feasibility analysis of the proposed schemes.

In this paper, a multiplication algorithm in extension field Fpm is proposed. Different from the previous works, the proposed algorithm can be applied for an arbitrary pair of characteristic p and extension degree m only except for the case when 4p divides m(p-1) and m is an even number. As written in the title, when p>m, 4p does not divide m(p-1). The proposed algorithm is derived by modifying cyclic vector multiplication algorithm (CVMA). We adopt a special class of Gauss period normal bases. At first in this paper, it is formulated as an algorithm and the calculation cost of the modified algorithm is evaluated. Then, compared to those of the previous works, some experimental results are shown. Finally, it is shown that the proposed algorithm is sufficient practical when extension degree m is small.

A new method of multi-bit embedding based on a protocol of secure asymmetric digital watermarking detection is proposed. Secure watermark detection has been achieved by means of allowing watermark verifier to detect a message without any secret information exposed in extraction process. Our methodology is based on an asymmetric property of a watermark algorithm which hybridizes a statistical watermark algorithm and a public-key algorithm. In 2004, Furukawa proposed a secure watermark detection scheme using patchwork watermarking and Paillier encryption, but the feasibility had not tested in his work. We have examined it and have shown that it has a drawback in heavy overhead in processing time. We overcome the issue by replacing the cryptosystem with the modified El Gamal encryption and improve performance in processing time. We have developed software implementation for both methods and have measured effective performance. The obtained result shows that the performance of our method is better than Frukawa's method under most of practical conditions. In our method, multiple bits can be embedded by assigning distinct generators in each bit, while the embedding algorithm of Frukawa's method assumes a single-bit message. This strongly enhances capability of multi-bit information embedding, and also improves communication and computation cost.

Elliptic curve cryptosystems are expected to be a next standard of public-key cryptosystems. A security level of elliptic curve cryptosystems depends on a difficulty of a discrete logarithm problem on elliptic curves. The security level of a elliptic curve cryptosystem which has a public-key of 160-bit is equivalent to that of a RSA system which has a public-key of 1024-bit. We propose an elliptic curve cryptosystem LSI architecture embedding word-based Montgomery multipliers. A Montgomery multiplication is an efficient method for a finite field multiplication. We can design a scalable architecture for an elliptic curve cryptosystem by selecting structure of word-based Montgomery multipliers. Experimental results demonstrate effectiveness and efficiency of the proposed architecture. In the hardware evaluation using 0.18 µm CMOS library, the high-speed design using 126 Kgates with 208-bit multipliers achieved operation times of 3.6 ms for a 160-bit point multiplication.

We consider a network, where a special data called certificate is issued between two users, and all certificates issued by the users in the network can be represented by a directed graph. For any two users u and v, when u needs to send a message to v securely, v's public-key is needed. The user u can obtain v's public-key using the certificates stored in u and v. We need to disperse the certificates to the users such that when a user wants to send a message to the other user securely, there are enough certificates in them to get the reliable public-key. In this paper, when a certificate graph and a set of communication requests are given, we consider the problem to disperse the certificates among the nodes in the network, such that the communication requests are satisfied and the total number of certificates stored in the nodes is minimized. We formulate this problem as MINIMUM CERTIFICATE DISPERSAL (MCD for short). We show that MCD is NP-Complete, even if its input graph is restricted to a strongly connected graph. We also present a polynomial-time 2-approximation algorithm MinPivot for strongly connected graphs, when the communication requests satisfy some restrictions. We introduce some graph classes for which MinPivot can compute optimal dispersals, such as trees, rings, and some Cartesian products of graphs.

In this paper, we present a new class of public-key cryptosystem (PKC) using algebraic coding on the basis of superimposition and randomness. The proposed PKC is featured by a generator matrix, in a characteristic form, where the generator matrix of an algebraic code is repeatedly used along with the generator matrix of a random code, as sub-matrices. This generator matrix, in the characteristic form, will be referred to as K-matrix. We show that the K-matrix yields the following advantages compared with the conventional schemes: (i) It realizes an abundant supply of PKCs, yielding more secure PKCs, (ii) It realizes a short public key.

Although the Digital Rights Management (DRM) systems have been rapidly developed to protect copyrights, they have not considered user privacy because they regard this as an unnecessary element in achieving their goals. However, the protection of user privacy becomes one of the most important issues in DRM systems as the number of people who suffer from accidents caused by the infringement of individual information dramatically increases. This paper suggests a license management protocol which is a more powerful protocol to protect individual information in DRM. To protect the exposure of information of user identification, the proposed protocol uses alias like a TID and a token instead of the identity of content users. Due to using alias, this protocol can guarantee the anonymity of content users. Also, it can prevent the leakage of individual information through encryption of usage information. In this way, it can protect the privacy of content users.

This paper proposes an extension field named TypeII AOPF. This extension field adopts TypeII optimal normal basis, cyclic vector multiplication algorithm, and Itoh-Tsujii inversion algorithm. The calculation costs for a multiplication and inversion in this field is clearly given with the extension degree. For example, the arithmetic operations in TypeII AOPF Fp5 is about 20% faster than those in OEF Fp5. Then, since CVMA is suitable for parallel processing, we show that TypeII AOPF is superior to AOPF as to parallel processing and then show that a multiplication in TypeII AOPF becomes about twice faster by parallelizing the CVMA computation in TypeII AOPF.

We propose a new type of revocation scheme for efficient public-key black-box traitor tracing. Our revocation scheme is flexible and efficient in the sense that (i) any number of subscribers can be revoked in each distribution under an assumption that the number of revoked subscribers who collude in one coalition is limited to a threshold and (ii) both each subscriber's storage and the transmission overhead are independent of n, while (i) the maximum number of revoked ones cannot be changed or (ii) they depend on n in previous schemes, where n is the total number of subscribers. The flexibility in revocation is significant since flexible revocation can be integrated with efficient black-box tracing and this integration can be achieved without a substantial increase in the transmission overhead over the previous schemes. In this paper, we present a concrete construction of an efficient public-key black-box traceable and revocable scheme by combining flexible revocation with a known black-box tracing algorithm which works under the same attack model as assumed in the previous schemes. Our scheme achieves that (i) the transmission overhead remains efficient, especially linear only in k in case of bulk revocation and (ii) the tracing algorithm runs in O(log n) time, while the previous ones cannot satisfy both of these properties, where k is the maximum number of traitors in a coalition.

Extensive studies have been made of the public key cryptosystems based on multivariate polynomials over F2. However most of the proposed public key cryptosystems based on multivariate polynomials, are proved not secure. In this paper, we propose several types of new constructions of public key cryptosystems based on randomly generated singular simultaneous equations. One of the features of the proposed cryptosystems is that the sets of random singular simultaneous equations significantly enlarges the size of the transformation.

Recently, Kasahara and Murakami proposed new product-sum type public-key cryptosystems with the Chinese remainder theorem, Methods B-II and B-IV. They also proposed a new technique of selectable encryption key, which is referred to as 'Home Page Method (HP Method).' In this paper, first, we describe Methods B-II and B-IV. Second, we propose an effective attack for Method B-II and discuss the security of Methods B-II and B-IV. Third, applying the HP Method to Methods B-II and B-IV, we propose new product-sum type PKC with selectable encryption key. Moreover, we discuss the security of the proposed cryptosystems.

Almost all of the current public-key cryptosystems (PKCs) are based on number theory, such as the integer factoring problem and the discrete logarithm problem (which will be solved in polynomial-time after the emergence of quantum computers). While the McEliece PKC is based on another theory, i.e. coding theory, it is vulnerable against several practical attacks. In this paper, we summarize currently known attacks to the McEliece PKC, and then point out that, without any decryption oracles or any partial knowledge on the plaintext of the challenge ciphertext, no polynomial-time algorithm is known for inverting the McEliece PKC whose parameters are carefully chosen. Under the assumption that this inverting problem is hard, we propose a slightly modified version of McEliece PKC that can be proven, in the random oracle model, to be semantically secure against adaptive chosen-ciphertext attacks. Our conversion can achieve the reduction of the redundant data down to 1/3-1/4 compared with the generic conversions for practical parameters.

Recently, Kasahara and Murakami proposed new product-sum public-key cryptosystems using the Chinese remainder theorem as the trapdoor. We proposed 'Yaezakura' as the high-density product-sum PKC applying the method using the reduced bases. In this paper, we propose another high-density scheme with the Chinese remainder theorem trapdoor using the message extension. We also show that the proposed scheme is invulnerable to the low-density attack. In the proposed scheme, the sender can freely select the positions of the dummy messages.

Certificate Revocation is a critical issue for a practical, public-key infrastructure. A new efficient revocation protocol using a one-way hash tree structure (instead of the classical list structure, which is known as a standard for revocation), was proposed and examined to reduce communication and computation costs. In this paper, we analysis a k-ary hash tree for certificate revocation and prove that k = 2 minimizes communication cost.

This paper proposes a public-key cryptography by applying RSA and Petri nets. We introduce RSA and a Petri net based private-key cryptography and then taking the advantages of these two cryptography, we propose a new public-key cryptography, PNPKC. To compare with RSA on security as well as computation order, we do simulation experiments. As the results, the security of PNPKC is as strong as RSA cryptography, and the encryption and decryption of PNPKC are in average 239 times as fast as RSA cryptography from our experiments. Besides, to see if our current PNPKC program can be practically used, we do comparative experiment with PGP, which shows PNPKC takes computation time in average as much as 36 times of PGP cryptography. That means our PNPKC program still needs to be technically improved.

We introduce a refined definition of semantic security. The new definition is valid against not only chosen-plaintext attacks but also chosen-ciphertext attacks whereas the original one is defined against only chosen-plaintext attacks. We show that semantic security formalized by the new definition is equivalent to indistinguishability, due to Goldwasser and Micali for each of chosen-plaintext attacks, non-adaptive chosen-ciphertext attack, and adaptive chosen-ciphertext attack.

Modern cryptology was born in the late seventies and developed in the eighties. A decade since 1991 is the period of continuation of the development and new expansion of cryptology. In this paper we survey the development of cryptologic researches in this decade with emphasis on the results in Japan. We also present some future important works and propose the foundation of a public institution for evaluation of information security techniques.

This paper newly formalizes some notions of security for probabilistic public-key encryption schemes. The framework for these notions was originally presented in the work by Bellare et al., in which they consider non-malleability and indistinguishability under chosen-plaintext attack, non-adaptive chosen-ciphertext attack and adaptive chosen-ciphertext attack. This paper extends the results of Bellare et al. by introducing two goals, equivalence undecidability and non-verifiability under the above three attack models. Such goals are sometimes required in electronic voting and bids systems. It is shown that equivalence undecidability, non-verifiability and indistinguishability are all equivalent under the three attack models.

We review public-key cryptosystems from lattice problems, which are inspired by Ajtai's remarkable result, and consider their security from the point of view of both theory and practice. We also survey recent results on the power of the lattice reduction algorithm in cryptanalysis.

We discuss the security of the improved knapsack cryptosystem that Kobayashi and Kimura have proposed. Two attacking methods for their cryptosystem are proposed; one is the method for obtaining secret keys from public keys by using the continued fraction, and the other is for decrypting the ciphertext without knowing secret keys. We show that their cryptosystem is not secure against these attacks.