Dr. Kenji Koyama, one of the most respected and prominent Japanese researchers in modern cryptography, passed away on March 27, 2000. He left behind him many outstanding academic achievements in cryptography as well as other areas such as emotion transmission theory, learning and mathematical games. In this manuscript, with our deepest sympathy and greatest appreciation for his contribution to our society, we introduce his major works mainly in cryptography, although his papers in other areas are included in the bibliography list.

Every public-key encryption scheme has to incorporate a certain amount of randomness into its ciphertexts to provide semantic security against chosen ciphertext attacks (IND-CCA). The difference between the length of a ciphertext and the embedded message is called the ciphertext overhead. While a generic brute-force adversary running in 2t steps gives a theoretical lower bound of t bits on the ciphertext overhead for IND-CPA security, the best known IND-CCA secure schemes demand roughly 2t bits even in the random oracle model. Is the t-bit gap essential for achieving IND-CCA security? We close the gap by proposing an IND-CCA secure scheme whose ciphertext overhead matches the generic lower bound up to a small constant. Our scheme uses a variation of a four-round Feistel network in the random oracle model and hence belongs to the family of OAEP-based schemes. Maybe of independent interest is a new efficient method to encrypt long messages exceeding the length of the permutation while retaining the minimal overhead.

This paper proposes an inner-product encryption (IPE) scheme, which achieves selectively fully-attribute-hiding security in the standard model almost tightly reduced from the decisional linear (DLIN) assumption, and whose ciphertext is almost the shortest among the existing (weakly/fully) attribute-hiding IPE schemes, i.e., it consists of n+4 elements of G and 1 element of GT for a prime-order symmetric bilinear group (G, GT), where n is the dimension of attribute/predicate vectors. We also present a variant of the proposed IPE scheme that enjoys shorter public and secret keys with preserving the security. A hierarchical IPE (HIPE) scheme can be realized that has short ciphertexts and selectively fully-attribute-hiding security almost tightly reduced from the DLIN assumption.

This paper, for the first time, presents a provably secure signature scheme with message recovery based on the elliptic-curve discrete logarithm. The proposed scheme is proven to be secure in the strongest sense (i.e., existentially unforgeable against adaptively chosen message attacks) in the random oracle model under the discrete logarithm assumption. We give a concrete analysis of the security reduction. When practical hash functions are used in place of truly random functions, the proposed scheme is almost as efficient as the elliptic-curve version of the Schnorr signature scheme and existing schemes with message recovery such as the elliptic-curve version of the Nyberg-Rueppel and Miyaji schemes.

This paper proposes the first (practical) inner product encryption (IPE) scheme that is adaptively secure and fully attribute-hiding (attribute-hiding in the sense of the definition by Katz, Sahai and Waters), while the existing (practical) IPE schemes are either fully attribute-hiding but selectively secure or adaptively secure but weakly attribute-hiding. The proposed IPE scheme is proven to be adaptively secure and fully attribute-hiding under the decisional linear assumption in the standard model. The IPE scheme is comparably as efficient as the existing (practical) attribute-hiding IPE schemes. We also present a variant of the proposed IPE scheme with the same security that achieves shorter public and secret keys. A hierarchical IPE scheme can be constructed that is also adaptively secure and fully attribute-hiding under the same assumption. In this paper, we extend the dual system encryption technique by Waters into a more general manner, in which new forms of ciphertext and secret keys are employed and new types of information theoretical tricks are introduced along with several forms of computational reduction.

The concept of dual pairing vector spaces (DPVS) was introduced by Okamoto and Takashima in 2009, and it has been employed in various applications, functional encryption (FE) including attribute-based encryption (ABE) and inner-product encryption (IPE) as well as attribute-based signatures (ABS), generic conversion from composite-order group based schemes to prime-order group based ones and public-key watermarking. In this paper, we show the concept of DPVS, the major applications to FE and the key techniques employed in these applications. This paper presents them with placing more emphasis on plain and intuitive descriptions than formal preciseness.

This paper describes an attack that allows plural verifiers to check the validity of a signature simultaneously in Chaum's zero knowledge undeniable signature scheme, where if a malicious person takes part in the attack procedure as one verifier, the non-transitivity of a signature is suspect, and also proposes countermeasures to the attack.

Identity-based encryption (IBE) is one of the most important primitives in cryptography, and various security notions of IBE (e.g., IND-ID-CCA2, NM-ID-CCA2, IND-sID-CPA etc.) have been introduced. The relations among them have been clarified recently. This paper, for the first time, investigates the security of IBE in the universally composable (UC) framework. This paper first defines the UC-security of IBE, i.e., we define the ideal functionality of IBE, FIBE. We then show that UC-secure IBE is equivalent to conventionally-secure (IND-ID-CCA2-secure) IBE.

KEM (Key Encapsulation Mechanism) and DEM (Data Encapsulation Mechanism) were introduced by Shoup to formalize the asymmetric encryption specified for key distribution and the symmetric encryption specified for data exchange in ISO standards on public-key encryption. Shoup defined the "semantic security (IND) against adaptive chosen ciphertext attacks (CCA2)" as a desirable security notion of KEM and DEM, that is, IND-CCA2 KEM and IND-CCA2 DEM. This paper defines "non-malleability (NM)" for KEM, which is a stronger security notion than IND. We provide three definitions of NM for KEM, and show that these three definitions are equivalent. We then show that NM-CCA2 KEM is equivalent to IND-CCA2 KEM. That is, we show that NM is equivalent to IND for KEM under CCA2 attacks, although NM is stronger than IND in the definition (or under some attacks like CCA1). In addition, this paper defines the universally composable (UC) security of KEM and DEM, and shows that IND-CCA2 KEM (or NM-CCA2 KEM) is equivalent to UC KEM and that "IND against adaptive chosen plaintext/ciphertext attacks (IND-P2-C2)" DEM is equivalent to UC DEM.

We propose two types of public-key cryptographic schemes based on elliptic curves modulo n, where n is the product of secret large primes p and q. The RSA-type scheme has an encryption function with an odd multiplier. The Rabin-type scheme has an encryption function with a multiplier of 2. The security of the proposed schemes is based on the difficulty of factoring n. Other security characteristics are also discussed. We show some applications to a master key scheme and blind signature scheme.

This paper presents efficient secure auction protocols for first price auction and second price auction. Previous auction protocols are based on a generally secure multi-party protocol called mix-and-match protocol based on plaintext equality tests. However, the time complexity of the plaintext equality tests is large, although the mix-and-match protocol can securely calculate any logical circuits. The proposed protocols reduce the number of times the plaintext equality tests is used by replacing them with the Boneh-Goh-Nissim encryption, which enables calculation of 2-DNF of encrypted data.

In this paper, we present a framework to construct message recovery signature schemes from Sigma-protocols. The key technique of our construction is the redundancy function that adds some redundancy to the message only legitimately signed and recovered message can have. We provide a characterization of the redundancy functions that make the resulting message recovery signature scheme proven secure. Our framework includes known schemes when the building blocks are given concrete implementations, i.e., random oracles and ideal ciphers, hence presents insightful explanation to their structure.

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.

In this paper, we propose a new type of authentication system, one-time zero-knowledge authentication system. Informally speaking, in this authentication system, double usage of the same authentication is prevented. Based on these one-time zero-knowledge authentication systems, we propose a new untraceable electronic cash scheme satisfying both untraceability and unreusablity. This scheme overcomes the problems of the previous scheme proposed by Chaum, Fiat and Naor through its greater efficiency and provable security under reasonable cryptographic assumptions. We also propose a scheme, transferable untraceable electronic cash scheme, satisfying transferability as well as the above two criteria. Moreover, we also propose a new type of electronic cash, untraceable electronic coupon ticket, in which the value of one piece of the electronic cash can be subdivided into many pieces.

This paper presents the first attribute-based signature (ABS) scheme in which the correspondence between signers and signatures is captured in an arithmetic model of computation. Specifically, we design a fully secure, i.e., adaptively unforgeable and perfectly signer-private ABS scheme for signing policies realizable by arithmetic branching programs (ABP), which are a quite expressive model of arithmetic computations. On a more positive note, the proposed scheme places no bound on the size and input length of the supported signing policy ABP's, and at the same time, supports the use of an input attribute for an arbitrary number of times inside a signing policy ABP, i.e., the so called unbounded multi-use of attributes. The size of our public parameters is constant with respect to the sizes of the signing attribute vectors and signing policies available in the system. The construction is built in (asymmetric) bilinear groups of prime order, and its unforgeability is derived in the standard model under (asymmetric version of) the well-studied decisional linear (DLIN) assumption coupled with the existence of standard collision resistant hash functions. Due to the use of the arithmetic model as opposed to the boolean one, our ABS scheme not only excels significantly over the existing state-of-the-art constructions in terms of concrete efficiency, but also achieves improved applicability in various practical scenarios. Our principal technical contributions are (a) extending the techniques of Okamoto and Takashima [PKC 2011, PKC 2013], which were originally developed in the context of boolean span programs, to the arithmetic setting; and (b) innovating new ideas to allow unbounded multi-use of attributes inside ABP's, which themselves are of unbounded size and input length.

In this paper we discuss how one can delegate his power to authenticate or sign documents to others who, again, can delegate the power to someone else. A practical cryptographic solution would be to issue a certificate that consists of one's signature. The final verifier checks verifies the chain of these certificates. This paper provides an efficient and provably secure scheme that is suitable for such a delegation chain. We prove the security of our scheme against an adaptive chosen message attack in the random oracle model. Though our primary application would be agent systems where some agents work on behalf of a user, some other applications and variants will be discussed as well. One of the variants enjoys a threshold feature whereby one can delegate his power to a group so that they have less chance to abuse their power. Another application is an identity-based signature scheme that provides faster verification capability and less communication complexity compared to those provided by existing certificate-based public key infrastructure.

Although threshold key-recovery systems for the discrete log based cryptosystems such as the ElGamal scheme have been proposed by Feldman and Pedersen , no (practical) threshold key-recovery system for the factoring based cryptosystems such as the RSA scheme has been proposed. This paper proposes the first (practical) threshold key-recovery systems for the factoring based cryptosystems including the RSA and Rabin schemes. Almost all of the proposed systems are unconditionally secure, since the systems utilize unconditionally secure bit-commitment protocols and unconditionally secure VSS.

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].

Inner product functional encryption (IPFE) is a subclass of functional encryption (FE), whose function class is limited to inner product. We construct an efficient private-key IPFE scheme with full-hiding security, where confidentiality is assured for not only encrypted data but also functions associated with secret keys. Recently, Datta et al. presented such a scheme in PKC 2016 and this is the only scheme that achieves full-hiding security. Our scheme has an advantage over their scheme for the two aspects. More efficient: keys and ciphertexts of our scheme are almost half the size of those of their scheme. Weaker assumption: our scheme is secure under the k-linear (k-Lin) assumption, while their scheme is secure under a stronger assumption, namely, the symmetric external Diffie-Hellman (SXDH) assumption. It is well-known that the k-Lin assumption is equivalent to the SXDH assumption when k=1 and becomes weak as k increases.