We aim at constructing adaptive oblivious transfer protocols, enjoying fully simulatable security, from various well-known assumptions such as DDH, d-Linear, QR, and DCR. To this end, we present two generic constructions of adaptive OT, one of which utilizes verifiable shuffles together with threshold decryption schemes, while the other uses permutation networks together with what we call loosely-homomorphic key encapsulation schemes. The constructions follow a novel designing approach called “blind permutation”, which completely differs from existing ones. We then show that specific choices of the building blocks lead to concrete adaptive OT protocols with fully simulatable security in the standard model under the targeted assumptions. Our generic methods can be extended to build universally composable (UC) secure OT protocols, with a loss in efficiency.

In order to improve user's privacy in multi-authority Attribute-Based Encryption (ABE), we propose a solution which hides user's attributes by privacy homomorphism, such that not only the “external” adversary fails to access the private attribute of one user by eavesdropping on communications, but also the “internal” Attribute Authorities (AA), who are responsible for issuing attribute keys, are unable to build a full profile with all of the user's attributes by pooling their information on the user's ID. Meanwhile, the use of ID is essential to defend against collusion attack on ABE. Benefiting from privacy homomorphism, by which we distribute the part of the interpolation for the shares abstracted by the hidden attributes into each AA, the performance of the proposed scheme is higher than those of existing ABE schemes.

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.

We first consider a variant of the Schmidt-Samoa-Takagi encryption scheme without losing additively homomorphic properties. We show that this variant is secure in the sense of IND-CPA under the decisional composite residuosity assumption, and of OW-CPA under the assumption on the hardness of factoring n=p2q. Second, we introduce new algebraic properties "affine" and "pre-image restriction," which are closely related to homomorphicity. Intuitively, "affine" is a tuple of functions which have a special homomorphic property, and "pre-image restriction" is a function which can restrict the receiver to having information on the encrypted message. Then, we propose an encryption scheme with primitive power roots of unity in (Z/ns+1). We show that our scheme has, in addition to the additively homomorphic property, the above algebraic properties. In addition to the properties, we also show that the encryption scheme is secure in the sense of OW-CPA and IND-CPA under new number theoretic assumptions.

The Weil descent attack, suggested by Frey, has been implemented by Gaudry, Hess and Smart (the so-called GHS attack) on elliptic curves over finite fields of characteristic two and with composite extension degrees. Recently, Diem presented a general treatment of the GHS attack to hyperelliptic curves over finite fields of arbitrary odd characteristics. This paper shows that Diem's approach can be extended to curves of which the function fields are cyclic Galois extensions. In particular, we show the existence of GHS Weil restriction, triviality of the kernel of GHS conorm-norm homomorphism, and lower/upper bounds of genera of the resulting curves.

Given two terms and their rewriting rules, an unreachability problem proves the non-existence of a reduction sequence from one term to another. This paper formalizes a method for solving unreachability problems by abstraction; i. e. , reducing an original concrete unreachability problem to a simpler abstract unreachability problem to prove the unreachability of the original concrete problem if the abstract unreachability is proved. The class of rewriting systems discussed in this paper is called β rewriting systems. The class of β rewriting systems includes very important systems such as semi-Thue systems and Petri Nets. Abstract rewriting systems are also a subclass of β rewriting systems. A β rewriting system is defined on axiomatically formulated base structures, called β structures, which are used to formalize the concepts of "contexts" and "replacement," which are common to many rewritten objects. Each domain underlying semi-Thue systems, Petri Nets, and other rewriting systems are formalized by a β structure. A concept of homomorphisms from a β structure (a concrete domain) to a β structure (an abstract domain) is introduced. A homomorphism theorem (Theorem1)is established for β rewriting systems, which states that concrete reachability implies abstract reachability. An unreachability theorem (Corollary1) is also proved for β rewriting systems. It is the contraposition of the homomorphism theorem, i. e. , it says that abstract unreachability implies concrete unreachability. The unreachability theorem is used to solve two unreachability problems: a coffee bean puzzle and a checker board puzzle.

In this paper we discuss the relation between a one-way group homomorphism and a one-way ring homomorphism. Let U,V be finite abelian groups with #U=n. We show that if there exists a one-way group homomorphism f:UV, then there exists a one-way ring homomorphism F:ZnUZnImf. We also give examples of such ring homomorphisms which are one-way under a standard cryptographic assumption. This implies that there is an affirmative solution to an extended version of the open question raised by Feigenbaum and Merrit: Is there an encryption function f such that both f(x+y) and f(xy) can be efficiently computed from f(x) and f(y)? A multiple signature scheme is also given as an application of one-way ring homomorphisms.

A near-ring is an extended notion of a usual ring. Therefore a ring is a near-ring, but the converse does not necessarily hold. We investigate in this paper one-way functions associated with finite near-rings, and show that if there exists a one-way group homomorphism, there exists a one-way non-ring near-ring homomorphism (Theorem 1); if there exists a one-way ring homomorphism (Theorem 2). Further, we introduce a discrete logarithm problem over a finite near-ring, and show that the integer factoring is probabilistic polynomial-time Turing equivalent to a modified version of this problem (Theorem 3). Theorem 1 implies that under some standard cryptographic assumption, there is an affirmative but trivial solution to the extended version of the open question: Is there an encryption function f such that both f(x+y) and f(xy) are efficiently computed from given f(x) and f(y) ?