Crypto concepts promise partial progress via partial inversion

 cropped from source.

Shafi Goldwasser and Silvio Micali recently won the prestigious Turing Award. Our congratulations again to both of them. Shafi asked that we help announce the upcoming 8/22 deadline for the 5th Innovations in Theoretical Computer Science (ITCS) conference. We never do this kind of thing, so we will discuss something else.

Today I wish to talk about the Jacobian Conjecture, one of my favorite problems. Ken wanted to talk about it also, and he’s posting this during our travel to the kind of workshop we never announce, but he’s been enmeshed all week in the second story here.

The conjecture recently came up as an aside to the recent breakthrough work of Yitang Zhang on the Twin Prime Conjecture. Apparently his PhD work was on the Jacobian conjecture, and initially he thought he had solved the problem—see here for more details. While he did not succeed on that, he has—much later in life—pushed and almost proved the Twin Prime Conjecture. There is some lesson there for all of us.

The Conjecture

The Jacobian Conjecture in its purest form concerns polynomial mappings ${F = (f_1,\dots,f_n)}$ from ${\mathbb{C}^n}$ to ${\mathbb{C}^n}$. The Jacobian matrix ${J_F}$ has ${i}$-${j}$ entries defined by

$\displaystyle J_F(i,j) = \frac{\partial f_i}{\partial z_j}.$

Then ${jd_F = \det(J_F)}$ is a single polynomial over the same variables ${(z_1,\dots,z_n)}$. Since ${\mathbb{C}}$ is algebraically closed, the only way ${jd_F}$ can avoid having a zero is if it cancels out to be a nonzero constant. The Jacobian Conjecture is:

(JC) If ${jd_F}$ is a nonzero constant, then ${F}$ is an invertible mapping.

The intuition for this comes from the local inverse function theorem. If ${jd_F(\vec{z}) \neq 0}$, then the mapping ${F}$ is locally invertible at the point ${\vec{z}}$—that is, there is an open set containing ${\vec{z}}$ on which ${F}$ is invertible.

Thus if ${jd_F}$ never vanishes, ${F}$ is locally invertible everywhere. Offhand we would not expect this to imply the global 1-1 property, but perhaps the strong fact that ${jd_F}$ must in this case be constant makes this so? That is the question. It is open even for ${n = 2}$, and has attracted many false proofs, some from quite strong researchers.

With war clouds looming, Ott-Heinrich Keller posed this question in 1939, but it emerged only during the algebraic-geometry renaissance of the 1950′s and 1960′s. Shreeram Abyankhar raised it as an example of a problem that drew on its deeper aspects but required only elementary calculus to understand. He returned to it late in life, in papers published by the Journal of Algebra in 2008 that total over 300 pages. He passed away only recently, last November.

Arno van den Essen, whose work on JC we covered before, wrote his own thoughts into 292 fewer pages. Well he also wrote a book of 329 pages. JC has been proved when each ${f_i}$ has degree at most 2, while degree 3 is equivalent to the general case. This should remind us of complexity facts about ${\mathsf{2SAT}}$ and ${\mathsf{3SAT}}$, and makes us ask whether lurking behind all the words are issues that connect to complexity and crypto.

A Reduction

In computer theory we do reductions between problems all the time. In math this is also a normal mode of thinking. One of the neat theorems around the JC problem is that it is easy if all the polynomials are degree two, but has full generality if they are degree three, cubic. This is a standard transition from two to three that seems to repeat itself over and over, as with ${\mathsf{2SAT}}$ and ${\mathsf{3SAT}}$.

One can even do better than just reduce the degree to three; it is possible to have the polynomials take a special form. We give the definition for an arbitrary ring ${R}$.

Definition 1 Say a polynomial function ${F}$ from ${R^{n}}$ to ${R}$ is a D-polynomial provided ${F(x_{1},\dots,x_{n})=(y_{1},\dots,y_{n})}$ where each ${y_{i}}$ is of the form

$\displaystyle x_{i} + (a_{i1}x_{1} + \cdots + a_{in}x_{n})^{3}.$

Further the matrix ${A}$ of ${a_{ij}}$ satisfies the condition that ${A^{2}=0}$.

A notation for such maps is ${x + A^{*3}}$. These maps are named for Ludwik Drużkowski, who proved this beautiful theorem:

Theorem 2 If for ${R}$ equal to the complex numbers, all ${D}$-polynomials are invertible, then the full JC is true.

A Crypto Attack On JC

Crypto has grown to study multivariate polynomial maps. There have been several systems based on such maps that have been put forward as potentially hard to break. Unfortunately, most—all?—of these to date have been broken. The appeal of such systems is that polynomial functions are possibly inherently fast, since they avoid raising to high exponents in the manner of RSA, for instance. However, the attacks to date have, not surprisingly, exploited the polynomial nature of the systems.

One theorem that is used as “evidence” of the potential hardness is actually an upper bound on the degree of the inverse of a polynomial function that is invertible. It is known that the degree of the inverse ${F^{-1}}$ is bounded by ${\mathsf{degree}(F)^{n-1}}$, and importantly, this bound is tight in certain situations. Despite many cases where it is not tight, this suggests that the inverse could in general be large and complex, and therefore there is hope in using polynomial maps for crypto. However, the difficulty again is that the heretofore suggested systems do not work.

My idea that I wish to discuss is the use of crypto-style arguments to perhaps shed light on the JC. I think that crypto tools may not prove the conjecture, but they could definitely help us understand the conjecture better. There are two themes:

1. Given an invertible ${F(x_{1},\dots,x_{n})}$ how hard is it to find a fast inversion algorithm? Note that the algorithm does not have to be: construct and apply the polynomial inverse. The inversion algorithm could use some other indirect method.

2. Given an invertible ${F(x_{1},\dots,x_{n})}$ is it possible to get some information about the input given the output? This is a classic crypto question. Even if we cannot fully invert fast, it would be great to show that some information is leaked.

Polynomial Maps Leak Information

The goal here is to make some simple observations about how polynomial maps can be shown to leak information. This is not enough to invert them, which would be a way to show that the JC is true. It is still an interesting insight that suggests to me that there may be even deeper results.

One small observation that I think deserves mention is the following:

Theorem 3 Suppose that ${F:\mathbb{Z}^{n} \rightarrow \mathbb{Z}}$ is a D-mapping. Then, for any integer vector ${x}$, given ${y=F(x)}$ we can correctly guess more than half of the values ${x_{i}}$ modulo ${7}$.

The proof of this is quite trivial. We guess ${y_{i} + \Delta_{i}}$ for ${x_{i}}$ where ${\Delta_{i}}$ is a random variable that uniformly selects a value from the set ${S = \{-1,0,+1\}}$. The reason this works is that the cube of any number modulo ${7}$ is in the set ${S}$. Thus we are exponentially likely to get more that one-half of the ${x_{i}}$‘s right. Actually we get each right with probability ${4/7}$.

Note that this can be extended to get more bits of information, since we can replace ${7}$ by any prime ${p}$ such that ${3}$ divides ${p-1}$. Of course the primes grow in a way that the fraction of the time we are correct goes, unfortunately, to zero. Perhaps there is some clever way to get more bits of information about ${x}$. I do not know what the maximum we can get is.

In Drużkowski’s form of JC, however, we focus on polynomials with an associated coefficient matrix of special type. Can we use its nilpotency to get even more bits? Indeed we can.

Theorem 4 Suppose that ${F:\mathbb{Z}^{n} \rightarrow \mathbb{Z}}$ is a D-mapping over the ring ${R}$. If ${R}$ satisfies the polynomial identity ${w^{3} = w}$ for all elements ${w}$, then ${F}$ is invertible.

The proof is quite simple. Note that the inverse of the matrix ${I+A}$ where ${A^{2}=0}$ is the matrix ${I-A}$. This follows since,

$\displaystyle (I+A) \times (I-A) = I -A + A -A^{2} = I.$

Now let ${F(x)=x + A^{*3}(x)}$. In the ring ${R}$ this implies that ${F(x) = x + Ax = (I+A)x}$. Thus we can use the inverse matrix on ${F(x)}$ to recover the input ${x}$.

There are many rings that satisfy this polynomial identity. The ring ${\mathbb{Z}_{3}}$ is of course one, but there are an infinite number of such rings. This follows from both a direct product argument and a compactness argument from model theory. We can also work in quotient rings modulo this identity.

Suppose that we work instead over the integers. Then the polynomial identity ${w^3=w}$ is no longer true, of course, but we can still get some information.

Theorem 5 Suppose that ${F:\mathbb{Z}^{n} \rightarrow \mathbb{Z}}$ is a D-mapping over the integers. Then given ${F(x)}$, we can determine the elements of ${x}$ modulo ${3}$ in polynomial time.

Thus a D-map leaks quite a bit of information.

Polynomial Maps Over Two Variables

It is known that JC in two dimensions is true for all degrees up to 100. It seems also that 100 can be improved with more computer searching. This yields a result:

Theorem 6 Let ${H=(f(x,y),g(x,y))}$ be an integer polynomial map with Jacobian equal to ${q}$. Let ${H(x,y) = (u,v)}$. Then we can determine ${u}$ and ${v}$ modulo ${m}$ in polynomial time for

$\displaystyle m = \Pi_{p \in S} p,$

where ${S}$ is the set of primes less than ${100}$ and relatively prime to ${q}$.

The proof is simple. Take the ${u,v}$ mod each prime ${p}$. The point is that ${H}$ modulo ${p}$ maps to an invertible polynomial of degree at most ${100}$ for each prime in ${S}$. Then we invert and get ${u,v}$ modulo ${p}$.

We note that the product of all the primes less than 100 is quite large

$\displaystyle 2305567963945518424753102147331756070$

and so if ${q}$ is relatively prime to all of these, then we recover the inputs exactly for all inputs up to this number.

Open Problems

Can we prove that polynomial maps leak even more information? Does this shed any light on the actual JC? Or does it help understand the capabilities of polynomial maps in crypto?

4 Comments leave one →
1. August 5, 2013 12:42 pm

This looks very interesting to me, but it may be a month before I can get back to it.

Just off the top of my head, it may be of interest in our computational (polynomial, propositional) context to investigate the Boolean, characteristic 2, or logical analogues of this and other topics in differential geometry, especially the question of finding the right logical analogue of the tangent functor.

August 6, 2013 10:52 pm

Nice article.

I don’t understand the reasoning–I must be dense–that “we get each right with probability 4/7″. $\Delta_i$ is distributed as P=(3/7,1/7,3/7) over the set {-1,0,1}. If we draw $Z$ from the probability distribution $Q=(1/3,1/3,1/3)$ as suggested, and let Z be our guess, our probability of success for guessing each $\Delta_i$ correctly is $(1/3)*((3/7)+(1/7)+(1/7))=1/3,$ no?

If we always guess $Z=+1$ or $Z=-1$ our probability of success is (3/7). If we are allowed to make a single guess for each $\Delta_i$ we can’t do any better than this, whereby we guess (one of) the most likely outcome(s).

3. August 7, 2013 1:39 am

Nice post attacking the Jacobian conjecture from a refreshing angle. I am a bit confused by theorem 1, are you sure that A^2=0 ? I may be mistaken, but I cannot see this in the original paper of Drużkowski. Moreover if you take as matrix A={{0, 1, 0}, {-1, 0, 1}, {0, 1, 0}}, then A is a Drużkowski matrix, but A^2 is not null…. (as pointed in this (Gorni et al, Druikowski matrix search and D-nilpotent automorphisms, 1999))