Score:3

Crypto

What exactly does "Extension of a polynomial" mean?

user93353

6/10/23, 11:23 AM

This from the manuscript of a book on Zero Knowledge Proofs - https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf

3.5 Low Degree and Multilinear Extensions Let $\mathbb F$ be any finite field, and let $f : \{0, 1\}^v \rightarrow \mathbb F$ be any function mapping the v-dimensional Boolean hypercube to $\mathbb F$. A $v$-variate polynomial $g$ over $\mathbb F$ is said to be an extension of $f$ if $g$ agrees with at all Boolean-valued inputs, i.e., $g(x) = f (x)$ for all $x \in \{0, 1\}^v$

I am unable to understand what this means.

I don't think they are talking about Extension fields here - i.e. then they would have $\mathbb F_p$ & $\mathbb F_{p^n}$
I think $\{0,1\}^v$ is a bit string of $v$ bits. Or am I misinterpreting it?
$f$ is a map - however I think it's also a polynomial. It's probably in the form of a polynomial of maximum degree $v$ & it takes it's coefficients from $\mathbb F_2$.
And $g$ is another polynomial. However, it's not clear to me which field $g$ takes it's coefficient from.
$g$ is a $v$ variate polynomial. So what exactly does $f(x) = g(x)$ for all $x \in \{0, 1\}^v$ mean. If $g$ is a multivariate polynomial, then g can't be evaluated just with $x$ as input - it needs $v$ different variables for evaluation i.e. $g(x_1, x_2 .... x_v)$. So how do we have $f(x) = g(x)$?

All in all, I don't understand what this "Extension of a polynomial" is? Can someone guide me towards understand what the quoted definition means.

120

0 + 0

zero-knowledge-proofs

information-theory

computational-complexity-theory

Score:3

Crypto

Daniel S

6/10/23, 11:53 AM

The distinction here is that $g$ maps from $\mathbb F^v\to \mathbb F$. The Boolean values 0 and 1 can be naturally identified with the additive and multiplicative identities in any field to make the coercion $\{0,1\}^v\to \mathbb F^v$ of $v$-long bit strings to $v$-tuples of elements of $\mathbb F$ meaningful and unambiguous.

An example might help here. Let $v=1$ and let $\mathbb F=\mathbb F_5$. Suppose that we have the function $f:\{0,1\}\to\mathbb F_5$ defined by $f(0)=2$ and $f(1)=4$. This function has an extension by the polynomial over $\mathbb F_5$ (i.e. a polynomial whose coefficients lie in $\mathbb F_5$) $g:=2x+2$. We see that $g(0)=2$ and that $g(1)=4$ which agrees with $f$ at the value required (note that the evaluation of $f$ can be thought of a s table look-up, whereas $g$ is calculated using $\mathbb F_5$ arithmetic). The extension property does not say anything about the behaviour of $g$ at other points and in fact there are several polynomials that are extensions of $f$. Another example is $g_2(x):=x^2+x+2$. More generally any polynomial of the form $2x+2+h(x)(x^2-x)$ will be an extension of $f$.

It doesn't make sense to think of $f$ as a polynomial over $\mathbb F_2$ as arithmetic over $\mathbb F_2$ cannot produce elements of $\mathbb F_5$.

ETA 20220211: For higher values of $v$, we separate the $v$-long bit string $x$ into $v$ variables to define $g$. For example with $v=2$ and $\mathbb F_5$ as before, we might have $f(00)=2$, $f(01)=2$ $f(10)=3$ and $f(11)=4$. We then want to find $g(x_1,x_2)\in \mathbb F_5[x_1,x_2]$ with $g(0,0)=2$, $g(0,1)=2$, $g(1,0)=3$ and $g(1,1)=4$. One example is $g(x_1,x_2)=x_1x_2+x_1+2$, but as before there are many other possibilities.

0 + 0

user93353

6/11/23, 9:18 AM

$g$ is a $v$ variate polynomial. So what exactly does $f(x) = g(x)$ for all $x \in \{0, 1\}^v$ mean. If $g$ is a multivariate polynomial, then g can't be evaluated just with $x$ as input - it needs $v$ different variables for evaluation i.e. $g(x_1, x_2 .... x_v)$. So how do we have $f(x) = g(x)$? I have edited the question to add this also - since in your example $v=1$, this question doesn't arise there

kodlu

6/12/23, 2:13 PM

regarding your question above, $f$ is a *function* which can be given as a table lookup. $\{0,1\}^v$ is a *subset* of $\mathbb{F}^v$ and that's where the function is specified. Then the extension is chosen to match $f$ on this subset. while a bit informal I don't see where the problem is in this excellent answer.

user93353

6/14/23, 6:57 AM

Thank you for the further explanation. It's still not 100% clear to me - is there any book which covers this "Extension Polynomial" & it's significance? If I google for extension & polynomial, I keep hitting polynomials over extension fields rather than this topic?

user93353

6/14/23, 6:59 AM

I have understood the f(x) = g(x) part now, but the significance of this whole extension is still not clear to me.

user93353

6/14/23, 7:15 AM

$g(x_1,x_2)\in \mathbb F_4[x_1,x_2]$ - why is it $F_4$ here & not $F_5$?

user93353

6/14/23, 7:18 AM

polynomial of the form $2x+2+h(x)(x^2-x)$ - what is $h(x)$ here?

Daniel S

6/14/23, 7:28 AM

$\mathbb F_4$ was a typo which I have now corrected; my apologies. The term $h(x)$ represents any polynomial over $\mathbb F_5$. I don’t know of any books that cover this topic.

Score:1

Crypto

Mark

6/14/23, 8:22 AM

Perhaps a better-known name for this technique is arithmetization. The broad idea behind it is to encode boolean logic into low-degree polynomials, which (for certain technical reasons) have various useful analytical techniques available (probably most obviously the Schwartz-Zippel lemma). This is in particular useful for proving soundness of interactive proofs, and was key to Shamir's proof of $\mathsf{IP} = \mathsf{PSPACE}$.

$f$ is a map - however I think it's also a polynomial. It's probably in the form of a polynomial of maximum degree $v$ & it takes it's coefficients from $\mathbb{F}_2$.

Even if you can think of $f$ as a polynomial, it is better not to. We have some initial "standard" computational object we want to analyze, which typically means

a boolean formula, or
a boolean circuit, or
a truth table.

You can view these all as polynomials over $\mathbb{F}_2$ (and arguably that is precisely what boolean circuits are), but sometimes you'll have a formula instead or whatever.

The idea behind finding an extension polynomial (or, as I said before, appealing to "arithmetization") is to encode this (standard) object as a polynomial $g(x) \in \mathbb{F}[x_1,\dots,x_v]$ that "agrees with" $f(x)$ in the sense that

$$\forall (x_1,\dots,x_v)\in\{0,1\}^v : f(x_1,\dots,x_v) = g(x_1,\dots,x_v).$$

This can easily be done for certain operations, for example $g_{AND}(x,y) = xy$ is the extension of AND, $g_{NOT}(x) = 1-x$ is the extension of NOT. For other operations it is a little less straightforward, for example $$g_{XOR}(x,y) = x+y-2xy = 1 - (xy - (1-x)(1-y)).$$ is the arithmetization of XOR (I think), and is perhaps not obvious beforehand.

In the comments you've asked why we care. Perhaps the best motivation is Schwartz-Zippel Lemma, but its s technical lemma who's utility may not be useful immediately. The "elevator pitch" for arithmetization is

it was key to proving $\mathsf{IP} = \mathsf{PSPACE}$ (via Shamir's "sumcheck" protocol), one of the first big results in interactive proof systems, and
the proof of this result was very special (non-relativizing, and not a natural proof). Arguably "arithmetization" is one of ~3 or 4 fundamental proof techniques we know in complexity theory. Until 2009, it was really the main "big" techniques which still had a shot at showing that $\mathsf{P} \neq \mathsf{NP}$ --- it no longer has a shot though.

Anyway, for an explicit book reference, I know it is at least contained in Arora & Barak's Computational Complexity : A Modern Approach. Using ctrl+f to search "arithmetization" immediately brings you to chapter 8.5.2, which discusses the approach. In general, searching on this term will likely be much more fruitful than "extension polynomial", which may have more inadvertent name collisions.

0 + 0

user93353

6/15/23, 12:40 AM