We propose a security model, referred as g-eCK model, for group key exchange that captures essentially all non-trivial leakage of static and ephemeral secret keys of participants, i.e., group key exchange version of extended Canetti-Krawczyk (eCK) model. Moreover, we propose the first one-round tripartite key exchange (3KE) protocol secure in the g-eCK model under the gap Bilinear Diffie-Hellman (gap BDH) assumption and in the random oracle model.

It is known that the optimal sensor coverage of a mission space is performed by a Voronoi partition, which is called a Voronoi coverage problem. We consider the case that the mission space has several obstacles where mobile sensors cannot be deployed and search an optimal deployment to maximize the sensing performance. Inspired by the potential field method, we introduce a repulsive potential for obstacle avoidance and define the objective function by a combination of two functions: one for evaluation of the sensing performance and the other for obstacle avoidance. We introduce a space where a sensor can move, called its moving space. In general, a moving space may not coincide with the mission space. We assume that the respective moving spaces of each sensor may differ from each other. By introducing a barycentric coordinate over the moving space, we show that the Voronoi coverage problem to maximize the objective function is transformed into a potential game. In potential games, local maximizers of a potential function are stable equilibrium points of the corresponding replicator dynamics. We propose a distributed sensor coverage control method based on the replicator dynamics to search a local maximizer of the objective function and a path to it. Using simulations, we also compare the proposed method with the Lloyd and TangentBug algorithm proposed by Breitenmoser et al.

In this paper, we have reported the development of a snowblower support system which can safely navigate snowblowers, even during a whiteout, with the combination of a very accurate GPS system, so called RTK-GPS, and a unique and highly accurate map of roadsides and obstacles on roads. Particularly emphasized new techniques in this paper are ways to detect accurate geographical positions of roadsides and obstacles by utilizing and analyzing 3D laser scanned data, whose data has become available in recent days. The experiment has shown that the map created by the methods and RTK-GPS can sufficiently navigate snowblowers, whereby a secure and pleasant social environment can be archived in snow areas of Japan. In addition, proposed methods are expected to be useful for other systems such as a quick development of a highly accurate road map, a safely navigation of a wheeled chair, and so on.

This paper analyzes security of sequential multiple encryptions based on asymmetric key encryptions, and shows that a sequential construction of secure multiple encryptions exists. The sequential multiple encryption scheme can be proved to be indistinguishable against chosen ciphertext attacks for multiple encryptions (IND-ME-CCA), where the adversary can access to the decryption oracle of the multiple encryption, even when all the underlying encryptions of the multiple encryption are indistinguishable against chosen plaintext attacks (IND-CPA). We provide an extended security notion of sequential multiple encryptions, in which the adversary is allowed to access decryption oracles of the underlying encryptions in addition to the multiple encryption, and show that our constructed scheme satisfies the security notion when all the underlying encryptions are indistinguishable against chosen ciphertext attacks (IND-CCA).

This study formulates and solves the wire planning problem with electro-migration and interference using an effective integer linear programming (ILP)-based approach. For circuits without obstacles, the proposed approach obtains a wire planning with the minimum wiring area. An effective approach for estimating the length of feasible routing wire is proposed to handle circuits with obstacles. In addition, the space reservation technique, which allocates the ring of the free silicon space around obstacles, is presented to improve interference among routing wires and on-obstacle wires. For circuits with obstacles, the proposed method minimizes total wiring area and reduces interference. Experimental results show that the integer linear-programming-based approach effectively and efficiently minimizes wiring area of routing wires.

We analyze the security notion of information-theoretic secrecy against an adversary who can make adaptive queries to the decryption oracle, and show that it is equivalent to requiring that the encryption scheme can perfectly encrypt +1 different messages. This immediately yields a lower bound on the key length and an optimal construction, namely (+1)-wise independent permutations. This also gives an operational interpretation to the notion of decryption oracles in information-theoretic security.

Verifying the signing order is sometimes very important in multisignature schemes. A multisignature scheme in which the signing order can be verified is called structured multisignature scheme and many such schemes have been proposed so far. However, there are not many structured multisignature schemes utilizing an algebraic structure of underlying algebraic operation. Ohmori, Chida, Shizuya and Nishizeki have proposed a structured multisignature scheme by utilizing a non-commutative ring homomorphism. Since their scheme does not fully reflect the structure of signers and its rigorous security analysis is not provided, we construct an improved structured multisignature scheme overcoming these problems by utilizing the non-commutative ring homomorphism in a different way and discuss its rigorous security against various attacks, including signer structure forgery, rogue key attack and attack-0 under the discrete logarithm assumption. As far as we know, the scheme in [30], which does not use non-commutative ring homomorphism, guarantees the most rigorous security but the number of signers is restricted in order to prevent attack-0. In contrast, our scheme overcomes attack-0 by virtue of a ring homomorphism and no restriction is imposed on the number of signers.

In this paper, we present a new methodology, called a random oracle (RO) transformation, for designing IND-CCA secure PKE schemes in the standard model from schemes in the RO model. Unlike the RO methodology [3], [19], the security of the original scheme in the RO model does not necessarily have to be identical with that of the scheme resulting from the RO transformation. We then introduce a new notion, IND-INS-CCA security, and show how to obtain IND-CCA secure PKE schemes by instantiating ROs in IND-INS-CCA secure PKE schemes. Furthermore, we introduce another new notion, a strong pseudorandom function (PRF) family associated with a trapdoor one-way permutation generator (briefly, -SPRF family), which can be regarded as an enhanced PRF family, so that the resulting PKE scheme becomes quite practical.

Since the Merkle-Damgård hash function (denoted by MDFH) that uses a fixed input length random oracle as a compression function is not indifferentiable from a random oracle (denoted by RO) due to the extension attack, there is no guarantee for the security of cryptosystems, which are secure in the RO model, when RO is instantiated with MDHF. This fact motivates us to establish a criteria methodology for confirming cryptosystems security when RO is instantiated with MDHF. In this paper, we confirm cryptosystems security by using the following approach: 1.Find a weakened random oracle (denoted by WRO) which leaks values needed to realize the extension attack. 2.Prove that MDHF is indifferentiable from WRO. 3.Prove cryptosystems security in the WRO model. The indifferentiability framework of Maurer, Renner and Holenstein guarantees that we can securely use the cryptosystem when WRO is instantiated with MDHF. Thus we concentrate on such finding WRO. We propose Traceable Random Oracle (denoted by TRO) which leaks values enough to permit the extension attack. By using TRO, we can easily confirm the security of OAEP encryption scheme and variants of OAEP encryption scheme. However, there are several practical cryptosystems whose security cannot be confirmed by TRO (e.g. RSA-KEM). This is because TRO leaks values that are irrelevant to the extension attack. Therefore, we propose another WRO, Extension Attack Simulatable Random Oracle (denoted by ERO), which leaks just the value needed for the extension attack. Fortunately, ERO is necessary and sufficient to confirm the security of cryptosystems under MDHF. This means that the security of any cryptosystem under MDHF is equivalent to that under the ERO model. We prove that RSA-KEM is secure in the ERO model.

Ternary Content Addressable Memory (TCAM) is a special type of memory used in routers to achieve high-speed packet forwarding and classification. Packet forwarding is done by referring to the rules written in the routing table, whereas packet classification is performed by referring to the rules in the Access Control List (ACL). TCAM uses more transistors than Random Access Memory (RAM), resulting in high power consumption and high production cost. Therefore, it is necessary to reduce the entries written in the TCAM to reduce the transistor count. In this paper, we propose a new TCAM architecture by using Range Matching Devices (RMD) integrated within the TCAM's control logic with an optimized prefix expansion algorithm. The proposed method reduces the number of entries required to express ACL rules, especially when specifying port ranges. With less than 10 RMDs, the total number of lines required to write port ranges in the TCAM can be reduced to approximately 50%.

Policy in security devices such as firewalls and Network Intrusion Prevention Systems (NIPS) is usually implemented as a sequence of rules. This allows network packets to proceed or to be discarded based on rule's decision. Since attack methods are increasing rapidly, a huge number of security rules are generated and maintained in security devices. Under attack or during heavy traffic, the policy configured wrong creates security holes and prevents the system from deciding quickly whether to allow or deny a packet. Anomalies between the rules occur when there is overlap among the rules. In this paper, we propose a new method to detect anomalies among rules and generate new rules without configuration error in multiple security devices as well as in a single security device. The proposed method cuts the overlap regions among rules into minimum overlap regions and finds the abnormal domain regions of rules' predicates. Classifying rules by the network traffic flow, the proposed method not only reduces computation overhead but blocks unnecessary traffic among distributed devices.

This work focuses on a vulnerability of hash functions due to sloppy usages or implementations in the real world. If our cryptographic research community succeeded in the development of a perfectly secure random function as the random oracle, it might be broken in some sense by invalid uses. In this paper, we propose a new variant of the random oracle model in order to analyze the security of cryptographic protocols under the situation of an invalid use of hash functions. Our model allows adversaries to obtain contents of the hash list of input and output pairs arbitrarily. Also, we analyze the security of several prevailing protocols (FDH, OAEP, Cramer-Shoup cryptosystem, Kurosawa-Desmedt cryptosystem, NAXOS) in our model. As the result of analyses, we clarify that FDH and Cramer-Shoup cryptosystem are still secure but others are insecure in our model. This result shows the separation between our model and the standard model.

An anonymous identity based encryption (anonymous IBE) scheme requires that an adversary can not determine the identity of the recipient from a ciphertext encrypted by the corresponding public key. The anonymity was formalized in previous works [1],[13], and this can be considered under chosen plaintext attack and adaptive chosen ciphertext attack, yielding two notions of security, ID-II-CPA and ID-II-CCA, where II denotes "indistinguishability of identities." However, how to obtain an ID-II-CCA secure anonymous IBE in the random oracle model is still a challenging problem. We firstly propose a new notion of plaintext awareness in the two identities setting, called PATI. Secondly, we prove that the IBE scheme is ID-II-CCA secure if it is PATI secure. Finally, we propose the first generic conversion for anonymous IBE from ID-II-CPA to ID-II-CCA in the random oracle model.

In this paper, we introduce new compression function design principles supporting variable output lengths (multiples of size n). They are based on a function or block cipher with an n-bit output size. In the case of the compression function with a(t+1)n-bit output size, in the random oracle and ideal cipher models, their maximum advantages from the perspective of collision resistance are . In the case of t=1, the advantage is near-optimal. In the case of t>1, the advantage is optimal.

Canetti et al. [5] showed that there exist signature and encryption schemes that are secure in the random oracle (RO) model, but for which any implementation of the RO (by a single function or a function ensemble) results in insecure schemes. Their result greatly motivates the design of cryptographic schemes that are secure in the standard computational model. This paper gives some new results on the RO methodology. First, we give the necessary and sufficient condition for the existence of a signature scheme that is secure in the RO model but where, for any implementation of the RO, the resulting scheme is insecure. Next, we show that this condition induces a signature scheme that is insecure in the RO model, but that there is an implementation of the RO that makes the scheme secure.

In this article, we discuss the security of double-block-length (DBL) hash functions against the free-start collision attack. We focus on the DBL hash functions composed of compression functions of the form F(x) = (f(x), f(p(x))), where f is a smaller compression function and p is a permutation. We first show, in the random oracle model, that a significantly good upper bound can be obtained on the success probability of the free-start collision attack with sufficient conditions on p and the set of initial values. We also show that a similar upper bound can be obtained in the ideal cipher model if f is composed of a block cipher.

We first model the formal security model of multisignature scheme following that of group signature scheme. Second, we prove that the following three probabilistic multisignature schemes based on a trapdoor permutation have tight security; PFDH (probabilistic full domain hash) based multisignature scheme (PFDH-MSS), PSS (probabilistic signature scheme) based multisignature scheme (PSS-MSS), and short signature PSS based multisignature scheme (S-PSS-MSS). Third, we give an optimal proof (general result) for multisignature schemes, which derives the lower bound for the length of random salt. We also estimate the upper bound for the length in each scheme and derive the optimal length of a random salt. Two of the schemes are promising in terms of security tightness and optimal signature length. In appendix, we describe a multisignature scheme using the claw-free permutation and discuss its security.

We focus our attention on the layout dependent Across Chip Linewidth Variability (ACLV) of gate-forming poly-silicon patterns as a measure for manufacturability, which is a major contributor of systematic gate-length variation. First, we study the ACLV of standard cell layouts by lithography simulation. Then, we introduce regularity in gate-forming poly-silicon patterns and how it improves the ACLV and also how it incurs area-overhead. According to the investigation, we propose two design guidelines for standard-cell layout that can reduce ACLV with reasonable area overhead. Those guidelines include on-grid fixed-pitch layout with dummy-poly insertion and stretched gate-poly extension. Design experiments assuming a 65 nm process technology indicate that a D-FF designed with the first guideline reduces ACLV by 35% with 14% area overhead and the second guideline reduces ACLV by 75% with 29% area overhead at the best focus condition. Under defocus conditions, both layouts exhibit stable characteristics whereas the variability of conventional layout grows rapidly as the level of defocus increases. Circuit-level lithography simulation over benchmark circuits also supports that the proposed guidelines considerably reduces the amount of gate length variation.

Chen et al. introduced a new notion of a concurrent signature scheme for a fair exchange of signatures with two parties. Chen et al. also proposed a concrete scheme and proved its security under the assumption of discrete logarithm problem. Recently, Hiwatari and Tanaka extended the concept of concurrent signature to many-to-one setting. Hiwatari and Tanaka also proposed a concrete scheme; however, it requires some strong assumption to achieve the fair exchange and it is not efficient. This paper gives another construction of concurrent signature for many-to-one setting with multisignature scheme. Hereafter, we call it (n,1) concurrent signature scheme. The proposed scheme is more efficient than the scheme of Hiwatari and Tanaka in computation complexity and signature size, and achieves the fair exchange without the assumption required for the scheme of Hiwatari and Tanaka. This paper also gives a construction for the fair exchange of signatures in many-to-many setting, called (n,m) concurrent signature scheme, in appendix.

Although a great deal of research has been done on electronic cash schemes with blind multisignatures to prevent an insider attack, there is no discussion of a formal security model in the literature. Firstly we discussed the security model of e-cash schemes based on the blind multisignature scheme against a (restricted) attack model and proposed a concrete scheme proven to be secure in the model [1]; however, this attack model disallows an attacker from corrupting an issuing bank and shops in the forgery game. In this paper, first, we reconsider the security model to remove the restriction of the attack model. Second, we propose a new untraceable e-cash scheme with a blind multisignature scheme and prove that the proposed scheme is secure against the (non-restricted) attacks under the DDH assumption in the random oracle model.