About

Ming-Deh A. Huang is a Professor of Computer Science at the University of Southern California, affiliated with the Thomas Lord Department of Computer Science. He holds a doctoral degree from Princeton University and a bachelor's degree in Electrical Engineering and Computer Science from National Taiwan University. His research focuses on computational complexity, algorithmic number theory, cryptography, quantum computing, and self-assembly. Throughout his career, he has received notable awards including the NSF Presidential Young Investigator Award in 1989 and the IBM Postdoctoral Fellowships in Mathematical Sciences in 1984. His work contributes to advancing understanding in theoretical computer science, particularly in areas related to complexity theory and cryptographic algorithms.

Research topics

• Computer Science
• Mathematics
• Pure mathematics
• Discrete mathematics
• Mathematical analysis
• Theoretical computer science
• Algorithm

Selected publications

• Last Fall Degree of Semilocal Polynomial Systems

  SIAM Journal on Applied Algebra and Geometry · 2026-01-28

  article1st authorCorresponding
  PublisherDOI

• On Semi-Local Decomposition

  SSRN Electronic Journal · 2024-01-01

  preprintOpen access1st authorCorresponding
  PublisherDOI

• Last fall degree of semi-local polynomial systems

  arXiv (Cornell University) · 2023-11-06

  preprintOpen access1st authorCorresponding

  We study the last fall degrees of {\em semi-local} polynomial systems, and the computational complexity of solving such systems for closed-point and rational-point solutions, where the systems are defined over a finite field. A semi-local polynomial system specifies an algebraic set which is the image of a global linear transformation of a direct product of local affine algebraic sets. As a special but interesting case, polynomial systems that arise from Weil restriction of algebraic sets in an affine space of low dimension are semi-local. Such systems have received considerable attention due to their application in cryptography. Our main results bound the last fall degree of a semi-local polynomial system in terms of the number of closed point solutions, and yield an efficient algorithm for finding all rational-point solutions when the prime characteristic of the finite field and the number of rational solutions are small. Our results on solving semi-local systems imply an improvement on a previously known polynomial-time attack on the HFE (Hidden Field Equations) cryptosystems. The attacks implied in our results extend to public key encryption functions which are based on semi-local systems where either the number of closed point solutions is small, or the characteristic of the field is small. It remains plausible to construct public key cryptosystems based on semi-local systems over a finite field of large prime characteristic with exponential number of closed point solutions. Such a method is presented in the paper, followed by further cryptanalysis involving the isomorphism of polynomials (IP) problem, as well as a concrete public key encryption scheme which is secure against all the attacks discussed in this paper.

  PublisherOA PDFDOI

• On product decomposition

  Information Processing Letters · 2022-11-30

  articleOpen access1st authorCorresponding
  PublisherOA PDFDOI

• On the last fall degree of Weil descent polynomial systems

  Finite Fields and Their Applications · 2021-03-18

  article1st authorCorresponding
  PublisherDOI

• On the last fall degree of Weil descent polynomial systems

  arXiv (Cornell University) · 2021-03-08

  preprintOpen access1st authorCorresponding

  Given a polynomial system $\mathcal{F}$ over a finite field $k$ which is not necessarily of dimension zero, we consider the Weil descent $\mathcal{F}'$ of $\mathcal{F}$ over a subfield $k'$. We prove a theorem which relates the last fall degrees of $\mathcal{F}_1$ and $\mathcal{F}'_1$, where the zero set of $\mathcal{F}_1$ corresponds bijectively to the set of $k$-rational points of $\mathcal{F}$, and the zero set of $\mathcal{F}'_1$ is the set of $k'$-rational points of the Weil descent $\mathcal{F}'$. As an application we derive upper bounds on the last fall degree of $\mathcal{F}'_1$ in the case where $\mathcal{F}$ is a set of linearized polynomials.

  PublisherOA PDFDOI

• Quasi-subfield Polynomials and the Elliptic Curve Discrete Logarithm Problem

  Journal of Mathematical Cryptology · 2020 · 4 citations

  1st authorCorresponding
  • Computer Science
  • Mathematics
  • Pure mathematics

  Abstract We initiate the study of a new class of polynomials which we call quasi-subfield polynomials. First, we show that this class of polynomials could lead to more efficient attacks for the elliptic curve discrete logarithm problem via the index calculus approach. Specifically, we use these polynomials to construct factor bases for the index calculus approach and we provide explicit complexity bounds. Next, we investigate the existence of quasi-subfield polynomials.

  PublisherOA PDFDOI

• Algebraic blinding and cryptographic trilinear maps

  arXiv (Cornell University) · 2020 · 1 citations

  1st authorCorresponding
  • Computer Science
  • Mathematics
  • Discrete mathematics

  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.

  PublisherOA PDF

• Weil descent and cryptographic trilinear maps

  arXiv (Cornell University) · 2019-08-19 · 2 citations

  preprintOpen access1st authorCorresponding

  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.

  PublisherOA PDFDOI

• Trilinear maps for cryptography

  arXiv (Cornell University) · 2018-03-27 · 1 citations

  preprintOpen access1st authorCorresponding

  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.

  PublisherOA PDFDOI

Recent grants

• Algebraic and Geometric Methods in Algorithmic Number Theory and Algorithmic Self-Assembly

  NSF · $345k · 2003–2007

• CT-ISG: The Foundational Security of Elliptic Curve Cryptography

  NSF · $300k · 2006–2010

Frequent coauthors

• Leonard M. Adleman

  47 shared

• Qi Cheng

  16 shared

• Gerhard Goos

  Utrecht University

  16 shared

• Jan Van Leeuwen

  Hong Kong Association of Registered Tour Co-ordinators

  16 shared

• Pablo Moisset de Espanés

  University of Chile

  12 shared

• Yiu-Chung Wong

  Cadence Design Systems (United States)

  9 shared

• Len Adleman

  8 shared

• Michiel Kosters

  University of California, Irvine

  7 shared

Education

• Ph.D., Computer Science

  University of California, Los Angeles

  1980

• M.S., Computer Science

  University of California, Los Angeles

  1976

• B.S., Electrical Engineering

  National Tsinghua University

  1974

Awards & honors

• 1989 NSF Presidential Young Investigator Award
• 1984 IBM IBM Postdoctoal Fellowships in Mathematical Science…