2
$\begingroup$

Is there a way to commit to a degree of a polynomial without committing to every single one of its coefficients?

The problem I am trying to solve is to prove that two polynomials are the same in a more efficient way than to prove that every coefficient of the two polynomials is the same.

My idea is that if you can prove that: 1) the sum of the coefficients of both polynomials are the same 2) the degree of both polynomials is the same

You can prove that the two polynomials are equal. Is this possible?

Improve this question
$\endgroup$
4
  • $\begingroup$ By 'not committing to ... its coefficients', you mean that you're not committing to a specific polynomial, but to any polynomial of that degree? The degree of a polynomial is just an integer; there are certainly ways to commit to an integer. What problem are you actually trying to solve? $\endgroup$
    – poncho
    Sep 12, 2019 at 12:55
  • $\begingroup$ I edited the question, explaining what i am trying to accomplish. $\endgroup$
    – Fiono
    Sep 12, 2019 at 13:01
  • 2
    $\begingroup$ To prove a polynomial has degree up to $d$, we have to show the number of roots is up to this number. To verify this claim, we need to interpolate. You know it is not efficient. Using Merkle Hash Tree to commit to the coefficients seems to be an efficient way but you don't want to use the coefficients! Meanwhile, I think the protocol that you have defined is not secure! Because we can show this proof is the same for all the polynomials such that the coefficients are permuting. e.g. $x^2+2x+1$ and $x^2+x+2$ !!! $\endgroup$
    – Mahdi
    Sep 12, 2019 at 14:29
  • 1
    $\begingroup$ @MahdiSedaghat: actually, showing that there are only $d$ roots would not imply that the polynomial is of degree $d$ $\endgroup$
    – poncho
    Sep 12, 2019 at 15:38

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.