As part of ISO standards on public-key encryption, Shoup introduced the framework of KEM (Key Encapsulation Mechanism), and DEM (Data Encapsulation Mechanism), for formalizing and realizing one-directional hybrid encryption; KEM is a formalization of asymmetric encryption specified for key distribution, which DEM is a formalization of symmetric encryption. This paper investigates a more general hybrid protocol, secure channel, that uses KEM and DEM, while KEM supports distribution of a session key and DEM, along with the session key, is used for multiple bi-directional encrypted transactions in a session. This paper shows that KEM, which is semantically secure against adaptively chosen ciphertext attacks (IND-CCA2), and DEM, which is semantically secure against adaptively chosen plaintext/ciphertext attacks (IND-P2-C2), along with secure signatures and ideal certification authority are sufficient to realize a universally composable (UC) secure channel. To obtain the main result, this paper also shows several equivalence results: UC KEM, IND-CCA2 KEM and NM-CCA2 (non-malleable against CCA2) KEM are equivalent, and UC DEM, IND-P2-C2 DEM and NM-P2-C2 DEM are equivalent.

This paper presents an efficient secure auction protocol for M+1st price auction. In our proposed protocol, a bidding price of a player is represented as a binary expression, while in the previous protocol it is represented as an integer. Thus, when the number of players is m and the bidding price is an integer up to p, compared to the complexity of the previous protocol which is a polynomial of m and p, the complexity of our protocol is a polynomial of m and log p. We apply the Boneh-Goh-Nissim encryption to the mix-and-match protocol to reduce the computation costs.

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.

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.

This paper discusses the generalized mutual exclusion problem defined by H. Kakugawa and M. Yamashita. A set of processes shares a set of resources of an identical type. Each resource must be accessed by at most one process at any time. Each process may have different accessible resources. If two processes have no common accessible resource, it is reasonable to ensure a condition in resource allocation, which is called allocation independence in this paper, i. e. , resource allocation to those processes must be performed without any interference. In this paper, we define a new structure, sharing structure coterie. By using a sharing structure coterie, the resource allocation algorithm proposed by H. Kakugawa and M. Yamashita ensures the above condition. We show a necessary and sufficient condition of the existence of a sharing structure coterie. The decision of the existence of a sharing structure coterie for an arbitrary distributed system is NP-complete. Furthermore, we show a resource allocation algorithm which guarantees the above requirement for distributed systems whose sharing structure coteries do not exist or are difficult to obtain.

The problem of constructing a reliable and efficient routing ρ in a communications network G is considered. The forwarding index ξ(G, ρ), which is defined as the maximum number of routes which pass through each node, is a criterion of network efficiency. The diameter of the surviving route graph D(R(G, ρ)/F), which is defined as the maximum number of surviving routes needed for communication between each pair of nodes if node and edge faults F occur, is a criterion of network reliability. Routings which minimize ξ(G, ρ) and D(R(G, ρ)/F) are needed. In this paper the following are shown: (1) A sufficient condition for k-connected digraphs (k2, 4) to have a routing ρ such that D(R(G, ρ)/F)6 for |F|k. (2) A method of constructing a digraph G and routing ρ2 such that ξ(G, ρ2)2logdn for any number of nodes n and maximum degree d. (3) A method of constructing a digraph G and routing such that ξ(G, ρ2)3logdn and D(R(G, )/F)3 for |F|d-1 if nd4 and d3.