In cryptography, we want a Boolean function which satisfies PC(l) of order k for many (l,k). Let PCn(l,k) be a set of Boolean functions with n input bits satisfying PC(l) of order k. From a view point of construction, it is desirable that there exists (l0,k0) such that PCn(l0, k0) PCn(li,ki) for many i 1. In this paper, we show a negative result for this problem. We prove that PCn(l1,k1) PCn(l2,k2) for a large class of l1, k1, l2 and k2.

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.

Undeniable signature, and unpretendable signature schemes have been studied independently. In this paper, efficient schemes which serve as both at the same time are presented. The schemes find their typical application in anonymous auction where the winner cannot deny her bid; nobody can pretend to be the winner; and the anonymity of all losers is preserved. The security of the schemes is proved in the common reference string model under discrete logarithm type assumptions.

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.

To investigate cyber-criminals, Police sometimes asks Administrator of a computer system to disclose the whole transaction log. Administrator, however, wants to protect the privacy of innocent users. This paper presents a solution for the disclosure/privacy problem of transaction log. In this scheme, Police can search over the encrypted records of the transaction log by keywords. The administrator discloses only the records which include the keyword, but nothing more. Police can verify that the administrator faithfully disclosed all the records which include the keyword.

For a variant of RSA with modulus N=prq and ed ≡ 1 (mod(p-1)(q-1)), we show that d is to be recovered if d < N(2-)/(r+1). (Note that φ(N) (p-1)(q-1).) Boneh-Durfee's result for the standard RSA is obtained as a special case for r=1. Technically, we develop a method for finding a small root of a trivariate polynomial equation f(x, y,z)=x(y-1)(z-1)+1 ≡ 0 (mod e) under the condition that yrz=N. Our result cannot be obtained from the generic method of Jochemsz-May.

Recently a framework called Tag-KEM/DEM was introduced to construct efficient hybrid encryption schemes. Although it is known that generic encode-then-encrypt construction of chosen ciphertext secure public-key encryption also applies to secure Tag-KEM construction and some known encoding method like OAEP can be used for this purpose, it is worth pursuing more efficient encoding method dedicated for Tag-KEM construction. This paper proposes an encoding method that yields efficient Tag-KEM schemes when combined with set partial one-way permutations such as RSA and Rabin's encryption scheme. To our knowledge, this leads to the most practical hybrid encryption scheme of this type. We also present an efficient Tag-KEM which is CCA-secure under general factoring assumption rather than Blum factoring assumption.

It is known that perfectly secure (1-round, n-channel) message transmission (MT) schemes exist if and only if n ≥ 3t+1, where t is the number of channels that the adversary can corrupt. Then does there exist an almost secure MT scheme for n=2t+1 ? In this paper, we first sum up a number flaws of the previous almost secure MT scheme presented at Crypto 2004. We next show an equivalence between almost secure MT schemes and secret sharing schemes with cheaters. By using our equivalence, we derive a lower bound on the communication complexity of almost secure MT schemes. Finally, we present a near optimum scheme which meets our bound approximately. This is the first construction of provably secure almost secure (1-round, n-channel) MT schemes for n=2t+1.

KASUMI is a blockcipher that forms the heart of the 3GPP confidentiality and integrity algorithms. In this paper, we study the security of the five-round KASUMI type permutations, and derive a highly non-trivial security bound against adversaries with adaptive chosen plaintext and chosen ciphertext attacks. To derive our security bound, we heavily use the tools from graph theory. However the result does not show its super-pseudorandomness, this gives us a strong evidence that the design of KASUMI is sound.

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.

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 the model of no-dictionary searchable symmetric encryption (SSE) schemes, the client does not need to keep the list of keywords W. In this paper, we first show a generic method to transform any passively secure SSE scheme to a no-dictionary SSE scheme such that the client can verify search results even if w ∉ W. In particular, it takes only O(1) time for the server to prove that w ∉ W. We next present a no-dictionary SSE scheme such that the client can hide even the search pattern from the server.

In this paper, we design and analyze some new and practical (selectively) convertible undeniable signature (SCUS) schemes in both random oracle and standard model, which enjoy several merits over existing schemes in the literature. In particular, we design the first practical RSA-based SCUS schemes secure in the standard model. On the path, we also introduce two moduli RSA assumptions, including the strong twin RSA assumption, which is the RSA symmetry of the strong twin Diffie-Hellman assumption (Eurocrypt'08).

In this paper, we construct the first efficient leakage-resilient CCA2 (LR-CCA2)-secure attribute-based encryption (ABE) schemes. We also construct the first efficient LR-CCA2-secure identity-based encryption (IBE) scheme with optimal leakage rate. To obtain our results, we develop a new quasi-adaptive non-interactive zero-knowledge (QA-NIZK) argument for the ciphertext consistency of the LR-CPA-secure schemes. Our ABE schemes are obtained by boosting the LR-CPA-security of some existing schemes to the LR-CCA2-security by using our QA-NIZK arguments. The schemes are almost as efficient as the underlying LR-CPA-secure schemes.

In this paper, we propose TMAC. TMAC is a refinement of XCBC such that it requires only two keys while XCBC requires three keys. More precisely, TMAC requires only (k + n)-bit keys while XCBC requires (k + 2n)-bit keys, where k is the key length of the underlying block cipher E and n is its block length. We achieve this by using a universal hash function and the cost is almost negligible. Similar to XCBC, the domain is {0,1}* and it requires no extra invocation of E even if the size of the message is a multiple of n.

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.

OMAC is a provably secure MAC scheme proposed by Iwata and Kurosawa. NIST currently intends to specify OMAC as the modes recommendation. In August 2003, Mitchell published a note "On the security of XCBC, TMAC and OMAC" to propose a new variant of OMAC. We call it OMAC1". In this paper, we prove that OMAC1" is less secure than the original OMAC. We show a security gap between them. As a result, we obtain a negative answer to Mitchell's open question--OMAC1" is not provably secure even if the underlying block cipher is a PRP. Further, we point out limitations of discussion in [16].

The security of an iterated block cipher heavily depends on its structure as well as each round function. Matsui showed that MISTY type structure is faster and more robust than Feistel structure in terms of its resistance against linear and differential cryptanalysis. On the other hand, Luby and Rackoff proved that the four round Feistel structure is super-pseudorandom if each round function fi is a random function. This paper proves that the five round MISTY type structure is super-pseudorandom. We also characterize its round security.

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 this paper, we first show a multiple-use protocol under the Diffie-Hellman assumption such that the initialization phase is much more efficient than the previous one. We next present an efficient multiple-use protocol whose security is equivalent to breaking RSA. The securities of our protocols are all formally proved.