Ming-Deh A. Huang

Ming-Deh A. Huang

It has been shown recently that cryptographic trilinear maps are sufficient for achieving indistinguishability obfuscation. In this paper we develop algebraic blinding techniques for constructing such maps. An earlier approach involving Weil restriction can be regarded as a special case of blinding in our framework. However, the techniques developed in this paper are more general, more robust, and easier to analyze. The trilinear maps constructed in this paper are efficiently computable. The relationship between the published entities and the hidden entities under the blinding scheme is described by algebraic conditions. Finding points on an algebraic set defined by such conditions for the purpose of unblinding is difficult as these algebraic sets have dimension at least linear in $n$ and involves $Ω(n^2)$ variables, where $n$ is the security parameter. Finding points on such algebraic sets in general takes time exponential in $n^2\log n$ with the best known methods. Additionally these algebraic sets are characterized as being {\em triply confusing} and most likely {\em uniformly confusing} as well. These properties provide additional evidence that efficient algorithms to find points on such algebraic sets seems unlikely to exist. In addition to algebraic blinding, the security of the trilinear maps also depends on the computational complexity of a trapdoor discrete logarithm problem which is defined in terms of an associative non-commutative polynomial algebra acting on torsion points of a blinded product of elliptic curves.

Ming-Deh A. Huang

It has recently been shown that cryptographic trilinear maps are sufficient for achieving indistinguishability obfuscation. In this paper we develop a method for constructing such maps on the Weil descent (restriction) of abelian varieties over finite fields, including the Jacobian varieties of hyperelliptic curves and elliptic curves. The security of these candidate cryptographic trilinear maps raises several interesting questions, including the computational complexity of a trapdoor discrete logarithm problem.

Ming-Deh A. Huang

We continue to study the construction of cryptographic trilinear maps involving abelian varieties over finite fields. We introduce Weil descent as a tool to strengthen the security of a trilinear map. We form the trilinear map on the descent variety of an abelian variety of small dimension defined over a finite field of a large extension degree over a ground field. The descent bases, with respect to which the descents are performed, are trapdoor secrets for efficient construction of the trilinear map which pairs three trapdoor DDH-groups. The trilinear map also provides efficient public identity testing for the third group. We present a concrete construction involving the jacobian varieties of hyperelliptic curves.

Ming-Deh A. Huang

We construct cryptographic trilinear maps that involve simple, non-ordinary abelian varieties over finite fields. In addition to the discrete logarithm problems on the abelian varieties, the cryptographic strength of the trilinear maps is based on a discrete logarithm problem on the quotient of certain modules defined through the Néron-Severi groups. The discrete logarithm problem is reducible to constructing an explicit description of the algebra generated by two non-commuting endomorphisms, where the explicit description consists of a linear basis with the two endomorphisms expressed in the basis, and the multiplication table on the basis. It is also reducible to constructing an effective $\mathbb{Z}$-basis for the endomorphism ring of a simple non-ordinary abelian variety. Both problems appear to be challenging in general and require further investigation.