We define the polynomials $r,f_1,f_2,s\in R[x]$. Where $r$ is a random degree 1 polynomial and $s$ is a random polynomial such that: $\deg(s)=\deg(f_1)=\deg(f_2)$. Let $R$ be $\mathbb {Z}_q$ where $q$ is a large prime number

My question: how to To prove "Given $r\cdot f_1+f_2 \cdot (s+1)$ one who knows only $f_2$ cannot learn anything about $f_1$."?


  • $\begingroup$ Who is $R$? a generic ring or the field of reals?? $\endgroup$ – MattAllegro Nov 19 '14 at 18:06
  • $\begingroup$ So this person, does he know the full polynomial $rf_1+f_2(s+1)$ and $f_2$ itself and nothing more? $\endgroup$ – Arthur Nov 19 '14 at 18:07
  • 1
    $\begingroup$ Let $R$ be $\mathbb {Z}_q$ where $q$ is a large prime number. $\endgroup$ – user13676 Nov 19 '14 at 18:07
  • $\begingroup$ @Arthur Yes. That's right. $\endgroup$ – user13676 Nov 19 '14 at 18:09
  • $\begingroup$ I do know that if $r$ is a random polynomial of the same as the degree of the other polynomials (e.g. $f_1$) then he cannot find out. But I do not know whether the same is true for degree one $r$. cs.cmu.edu/~leak/papers/set-tech-full.pdf $\endgroup$ – user13676 Nov 19 '14 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.