This paper presents a new concept in cryptography called the sibling intractable function family (SIFF) which has the property that given a set of initial strings colliding with one another, it is computationally infeasible to find another string that would collide with the initial strings. The various concepts behind SIFF are presented together with a construction of SIFF from any one-way function. Applications of SIFF to many practical problems are also discussed. These include the hierarchical access control problem which is a long-standing open problem induced by a paper of Akl and Taylor about ten years ago, the shared mail box problem, access control in distributed systems and the multiple message authentication problem.

In this paper, we investigate the discrepancy between a serial version and a parallel version of zero-knowledge protocols, and clarify the information "leaked" in the parallel version, which is not zero-knowledge unlike the case of the serial version. We consider two sides: one negative and the other positive in the parallel version of zero-knowledge protocols, especially of the Fiat-Shamir scheme.

Given an integer N, it is easy to determine whether or not N is prime, because a set of primes is in LPP. Then given a composite number N, is it easy to determine whether or not N is of a specified form? In this paper, we consider a subset of odd composite numbers +1MOD4 (resp. +3MOD4), which is a subset of odd composite numbers consisting of prime factors congruent to 1 (resp. 3) modulo 4, and show that (1) there exists a four move (blackbox simulation) perfect ZKIP for the complement of +1MOD4 without any unproven assumption; (2) there exists a five move (blackbox simulation) perfect ZKIP for +1MOD4 without any unproven assumption; (3) there exists a four move (blackbox simulation) perfect ZKIP for +3MOD4 without any unproven assumption; and (4) there exists a five move (blackbox simulation) statistical ZKIP for the complement of +3MOD4 without any unproven assumption. To the best of our knowledge, these are the first results for a language L that seems to be not random self-reducible but has a constant move blackbox simulation perfect or statistical ZKIP for L and without any unproven assumption.

In this paper, we investigate the round complexity of zero-knowledge interactive proof systems of possession of knowledge, and mainly show that if a relation R has a three move blackbox simulation zero-knowledge interactive proof system of possession of knowledge, then there exists a probabilistic polynomial time algorithm that on input x{0,1}^*, outputs y such that (x,y)R with overwhelming probability if xdom R, and outputs "" with probability 1 if x dom R. The result above can not be generalized to zero-knowledge interactive proof systems of possession of knowledge with more than four moves, because it is known that there exists a "four" move blackbox simulation perfect zero-knowledge interactive proof system of possession of knowledge for a nontrivial relation R.

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.

We define the communication complexity of a perfect zero-knowledge interactive proof (ZKIP) as the expected number of bits communicated to achieve the given error probabilities (of both the completeness and the soundness). While the round complexity of ZKIPs has been studied greatly, no progress has been made for the communication complexity of those. This paper shows a perfect ZKIP whose communication complexity is 11/12 of that of the standard perfect ZKIP for a specific class of Quadratic Residuosity.

In 1990, Menezes, Okamoto and Vanstone proposed a method that reduces EDLP to DLP, which gave an impact on the security of cryptosystems based on EDLP. But this reducing is valid only when Weil pairing can be defined over the m-torsion group which includes the base point of EDLP. If an elliptic curve is ordinary, there exists EDLP to which we cannot apply the reducing. In this paper, we investigate the condition for which this reducing is invalid.

The basic operation in elliptic cryptosystems is the computation of a multiple d・P of a point P on the elliptic curve modulo n. We propose a fast and systematic method of reducing the number of operations over elliptic curves. The proposed method is based on pre-computation to generate an adequate addition-subtraction chain for multiplier the d. By increasing the average length of zero runs in a signed binary representation of d, we can speed up the window method. Formulating the time complexity of the proposed method makes clear that the proposed method is faster than other methods. For example, for d with length 512 bits, the proposed method requires 602.6 multiplications on average. Finally, we point out that each addition/subtraction over the elliptic curve using homogeneous coordinates can be done in 3 multiplications if parallel processing is allowed.

We propose a new randomized version of DES in which a key-dependent swapping is used to strengthen DES and DES-like cryptosystems against differential cryptanalysis. This new scheme, called RDES, decreases the probability of success in differential attack by decreasing the characteristic probability. The characteristic is the effect of particular differences in plaintext pairs on the differences in the resultant ciphertext pairs. The characteristic probability for the n-round RDES is 2^-n+1 times that for the n-round DES. As for the differential cryptanalysis based on characteristics, the 16-round RDES is as strong as the about 20-round DES. Encryption/decryption speed of n-round RDES is almost the same as that of the n-round DES.

This paper presents an efficient multi-precision modular-multiplication algorithm which minimizes the calculation RAM space required when implementing public-key schemes with software on general-purpose computers including smart cards and personal computers. Many modular-multiplication algorithms cannot be efficiently realized on small systems due to their high RAM consumption. The Montgomery algorithm, which can rapidly perform modular multiplication, has received a lot of attention. Unfortunately, the Montgomery algorithm is difficult to implement, especially in smart cards which have extremely limited RAM space. Furthermore, when the modulus of modular multiplication is frequently changed, or when the number of permissible repeated modular multiplications is small, pre- and post-processing operations such as conversion from/to the Montgomery space become wasteful. The proposed algorithm avoids these problems because it requires only half the RAM space and no pre- and post-processing operations. The algorithm is a radical extension to the approximation methods that use the most significant bits and our newly proposed lookahead determination method. This paper gives a proof of the completeness of this method, describes implementation results using a smart card, introduces a theory supported by the results, and considers the optimal technique to enhance the speed of this method.

We propose two types of key management systems that use complementary exponential calculation, in which users in the system divide into groups, and the different modulus numbers are assigned to each group and edges between groups. Key generation information over the modulus numbers is issued to a user by a trusted center. The user who receives the information can generate shared encryption keys between users in the system without using key exchange protocol. In our proposed system, the number of primes is one of the parameters for generating key generation information. The number decreases in inverse proportion to the square of the number of groups compared to the original method. Our proposed technique enabled us to extend the number of users in the system to more than one million, which is not possible with the original method.

This paper presents two methods for securely realizing caller-authenticated and callee-specified calls over telecommunication networks with terminals that accept IC cards having KPS-based cryptographic functions. In the proposed protocols, users can verify that the partner is the proper owner of a certain ID or a certain pen name. Users' privacy is protected even if they do the caller-authenticated and callee-specified calls and do not pay their telephone charge in advance.

It is difficult to decide whether or not a given cryptographic protocol is secure even though the cryptographic algorithm used for the protocol is assumed to be secure. We have proposed an algorithm to decide the security of cryptographic protocols under several conditions. In this paper, we review our algorithm and report a system to verify the security. The system has be implemented on a computer. By using this system, we have verified the security of several protocols efficiently.

The performance of an enciphered B⁺-tree can be improved by the selective encryption of the components of the nodes in the tree. This paper suggests an approach to the selective encryption of nodes in a B⁺-tree and a method to substitute the plaintext search keys in order to increase the security of the tree. The method is based on structures in combinatorial block designs, and it allows for faster traversal of the tree, hence improving the overall speed of query responses. It also represents a trade-off between security and performance in that the substitution method affords less security compared to encryption. However, assuming the use of a secure cryptosystem with parameters which are kept secret, the encrypted state of the data pointers and data blocks still prevents an intruder from accessing the stored data. The method based on block designs has the advantage of requiring only a small amount of information being kept secret. This presents a considerable savings in terms of space used to hold security-related information.

The security problems of object-oriented database system are investigated and security level assignment constraints and an access control mechanism based on the multilevel access control security policy are proposed. The proposed mechanism uses the Trusted Computing Base. A unique feature of the mechanism is that security levels are assigned not only to data items (objects), but also to methods and methods are not shown to the users whose security level is lower than that of the methods. And we distinguish between the security level of a variable in a class and that in an instance and distinguish between the level of an object when it is taken by itself and it is taken as a variable or an element of another complex object. All of this realizes the policy of multilevel access control.

A high resolution iterative algorithm for estimating the direction-of-arrival of multiple wide band sources is proposed in this paper. For equally spaced array structure, two Unitary Transform based approaches are proposed in frequency domain for signal subspace processing in both coherent multipath and incoherent environment. Given a priori knowledge of the initial estimates of DOA, with proper spatial prefiltering to separate multiple groups of closely spaced sources, our proposed algorithm is shown to have high resolution capability even in coherent multipath environment without reducing the angular resolution, compared with the use of subarray. Compared with the conventional algorithm, the performance by the proposed algorithm is shown by the simulations to be improved under low Signal to Noise Ratio (SNR) while the performance is not degraded under high SNR. Moreover the computation burden involved in the eigencomputation is largely reduced by introducing the Pesudo-Hermitian matrix approximation.

In this paper a recursive form of Welch-Berlekamp (W-B) algorithm is provided which is a novel and fast decoding algorithm.