We analyze the security of iterated 2m-bit hash functions with rate 1 whose round functions use a block cipher with an m-bit input (output) and a 2m-bit key. We first show a preimage attack with O(2m) complexity on Yi and Lam's hash function of this type. This means that their claim is wrong and it is less secure than MDC-2. Next, it is shown that a very wide class of such functions is also less secure than MDC-2. More precisely, we prove that there exist a preimage attack and a 2nd preimage attack with O(2m) complexity and a collision attack with O(23m/4) complexity, respectively. Finally, we suggest a class of hash functions with a 2m-bit hashed value which seem to be as secure as MDC-2.

In recent years, with the rapid growth of the Internet as well as the increasing demand for broadband services, live pay-television broadcasting via the Internet has become a promising business. To get this implemented, it is necessary to protect distributed contents from illegal copying and redistributing after they are accessed. Fingerprinting system is a useful tool for it. This paper shows that the anti-collusion code has advantages over other existing fingerprinting codes in terms of efficiency and effectivity for live pay-television broadcasting. Next, this paper presents how to achieve efficient and effective anti-collusion codes based on unital and affine plane, which are two known examples of balanced incomplete block design (BIBD). Meanwhile, performance evaluations of anti-collusion codes generated from unital and affine plane are conducted. Their practical explicit constructions are given last.

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.

Recently, Yagisawa proposed a public key cryptosystem which is very similar to the modified Lu-Lee cryptosystem. The differences are the set of messages and the decryption. On the other hand, Brickell and Odlyzko showed that the modified Lu-Lee cryptosystem is completely broken in polynomial time. This paper shows that Yagisawa cryptosystem is completely broken in the same way.

In this paper, we show an entropy-based approach to the privacy of multi-party protocols. First, we formulate the amount of leaked information by using mutual information for a two-party case. This is a better measure for some situations than the combinatorial measure known so far. Next, we apply multi-terminal information theoty to more than two parties and give the first formulation of the leaked information for more than two parties.

S-boxes (vector output Boolean functions) should satisfy cryptographic criteria even if some input bits (say, k bits) are kept constant. However, this kind of security has been studied only for scalar output Boolean functions. SAC (k) is a criterion for scalar output Boolean functions of this type. This paper studies a generalization of SAC (k) to vector output Boolean functions as the first step toward the security of block ciphers against attacks which keep some input bits constant. We first show a close relationship between such Boolean functions and linear error correcting codes. Then we show the existence, bounds and enumeration of vector Boolean functions which satisfy the generalized SAC (k). A design method and examples are also presented.

In this paper we study n-input m-output Boolean functions (abbr. (n,m)-functions) with high nonlinearity. First, we present a basic construction method for a balanced (n,m)-function based on a primitive element in GF(2m). With an iterative procedure, we improve some lower bounds of the maximum nonlinearity of balanced (n,m)-functions. The resulting bounds are larger than the maximum nonlinearity achieved by any previous construction method for (n,m)-functions. Finally, our basic method is developed to construct an (n,m)-bent function and discuss its maximum algebraic degree.