Many thanks for your answer. It's been shown in cs.cmu.edu/~leak/papers/set-tech-full.pdf that if $ degree (r)=degree(f_1)=degree(f_2)=degree(s)$, where $gcd(f_1,f_2)=1$ then $\ U= r \cdot f_1 + f_2 \cdot s$ has coefficients uniformly distributed in $R$. I just changed the degree of $r$ to 1.

Looking over that paper, they say that given $fr + gs$, where $f$ and $g$ are the polynomial representations of $S$ and $T$ respectively and $r$ and $s$ are random polynomials of degree $deg(f)$, the attacker learns no additional information about $S$ and $T$ than what can be deduced from $S\cap T$. Not sure how this directly translates to your problem.

Their Lemma 2 does specifically have that $degree(r)$ and $degree(s)$ $>$ $degree(f_1)$ (and $f_2$). Not sure if it can be extended to the case where $degree(r)=1$. Just checking, you do mean degree $1$ for $r$ and not $0$ (a random constant), right?

In our case $degree(r)=1$.

Since in that paper $ r,s \leftarrow R^d[x]$, where $R^d[x]$ is the set of polynomials of degree 0,...,d, I think it's clear we can have $degree(r) < degree(f)$ .

Looking at Lemma 2, $r,s$ have degree $\beta$ where $\beta\geq\alpha$ where $\alpha$ is the degree of $f$ and $g$.

Yes, but a paragraph up, the defined $r,s \leftarrow R^d[x]$, confusing.

Yeah, now, notice that when they choose the coefficients for r and s (really wish chat had mathjax), they choose the coefficients from R, not R*

So, potentially the coefficients could be 0 which is why the degree could be 0 to d.

But that doesn't really make sense and here's why. If that is the case, r,s could each be the constant polynomial 1. So (fr+gs) = f+g, but clearly the coefficients of f+g are not distributed uniformly and independently over R.

Right, imagin degree(r) is far more larger than degree(s) and the other polynomials. Here the result polynomial is not distributed in R^d[x] but is is distributed in a subfield.

There is definitely some confusion with lemma 2 and that earlier paragraph.

consider $f_2 \cdot s=f_3$ where $degree(s)=2d$ and $degree(f_2)=d$, then $degree(f_3)=3d$, If $degree( $f_1 \cdot r)=2d$. the result $U=f_1 \cdot r +f_2 \cdot s$ is distributed in $R^{2d}[x] not $R^{3d}[x]. So I think if we reduce the degree of r to 1 we would have the result $U$ distributed in $R^{d+1}[x]$, and that is why I thought it could be secure.

If f_3 has degree 3d, and f_1\cdot r has degree 2d, then f_3 + (f_1\cdot r) has degree 3d.

Yes but since f_1\cdot r has degree 2d cannot cover all terms in 3d, thus it is distributed in smaller field (what I can interpret from their paper and a few line below lemma 2)

When they specify in which field the result is distributed.

Okay, I see what you are saying.

I'm not sure what the answer is.

By the way, I do appreciate (as usual) for your help. Many thanks.

I gotta run. I'll check back in later.

You might try contacting the authors.

I'll try.