At Eurocrypt'98, Okamoto and Uchiyama presented a new trap-door (one-way) function based on factoring, while Fujisaki and Okamoto, at CRYPTO'99, showed a generic conversion from just one-way encryption to chosen-cipher secure encryption in the random oracle model. This paper shows that the result of combining both schemes is well harmonized (rather than an arbitrary combination) and, in the sense of exact security, boosts the level of security more than would be expected from [6]--The security of the scheme yielded by the combination is tightly reduced from factoring. This paper also gives a rigorous description of the new scheme, because this type of encryption may suffer serious damage if poorly implemented. The proposed scheme is at least as efficient as any other chosen-cipher secure asymmetric encryption scheme such as [2],[4],[13].

This paper presents a simple and generic conversion from a public-key encryption scheme that is indistinguishable against chosen-plaintext attacks into a public-key encryption scheme that is indistinguishable against adaptive chosen-ciphertext attacks in the random oracle model. The scheme obtained by the conversion is as efficient as the original encryption scheme and the security reduction is very tight in the exact security manner.

This paper proposes the first provably secure multi-signature schemes under the random oracle model. The security of our schemes can be proven in the sense of concrete security in Ref. [13]. The proposed schemes are efficient if the random oracle is replaced by practical hash functions. The essential techniques in our proof of security are the optimal reduction from breaking the corresponding identification to breaking signatures (ID Reduction Technique), and the hierarchical heavy row lemmas used in the concrete reduction from solving the primitive problem to breaking the identification scheme.

This paper describes two attacks against blind decryption (decode) based on the commutative random-self reducibility and RSA systems utilizing the transformability of digital signatures proposed in [2]. The transformable digital signature was introduced in [2],[8] for defeating an oracle attack, where the decrypter could be abused as an oracle to release useful information for an attacker acting as a requester of blind decryption. It was believed in [2],[8] that the correctness of a query to an oracle was ensured by the transformable signature derived from an original signature issued by the decrypter in advance, and a malicious query to an oracle could be detected before the blind decryption by the decrypter or would lead to release no useful information to an attacker. The first attack can decrypt all encrypted data with one access to an oracle. The second one generates a valid signature for an arbitrary message selected by an attacker abusing the validation check procedure.

In this paper, we investigate statistical and perfect Knowledge Complexity (KC) with respect ot oracle entropy and average case oracle measures. As main results. we show the following: (1) for any k(n) 1/poly (n), if a language L has perfect KC k(n) + n-ω(1) with respect to oracle entropy measure, then L has perfect KC k(n) with respect to oracle entropy measure (Theorem 3.1); (2) for any k(n) 1/poly(n), if a language L has perfect KC k(n) + n-ω(1) with respect to average case oracle measure, then L has perfect KC k(n) with respect to average case oracle measure (Theorem 3.2); (3) if a language L has statistical KC k(n) ο(1) with respect to oracle entropy measure, then for any ε > 0, L has statistical KC k(n) + 1 + ε with respect to average case oracle measure (Theorem 4.1); and (4) if a language L has perfect KC k(n) ο(1) with respect to oracle entropy measure, then for any ε > 0, L has perfect KC k(n) + 2 + ε with respect to average case oracle measure (Theorem 4.2).

In this paper, we investigate the knowledge complexity of interactive proof systems and show that (1) under the blackbox simulation, if a language L has a bounded move public coin interactive proof system with polynomially bounded knowledge complexity in the hint sense, then the language L itself has a one move interactive proof system; and (2) under the blackbox simulation, if a language L has a three move private coin interactive proof system with polynomially bounded knowledge complexity in the hint sense, then the language L itself has a one move interactive proof system. These results imply that as long as the blackbox simulation is concerned, any language L AM＼MA is not allowed to have a bounded move public coin (or three move private coin) interactive proof system with polynomially bounded knowledge complexity in the hint sense unless AM = AM. In addition, we present a definite distinction between knowledge complexity in the hint sense and in the strict oracle sense, i.e., any language in AM (resp. IP) has a two (resp. unbounded) move public coin interactive proof system with polynomially bounded knowledge complexity in the strict oracle sense.