By the time quantum computers exist, the actual signing algorithms are not secure anymore. Then one can switch e.g. to so-called "Unbalanced Oil and Vinegar" systems. It is your challenge to break such a system, with realistic parameters, today already.
Read more...

Why should I bother to solve it when you do not bother to make a text file which contains equations in a format that is easy to read. There are "random" spaces and random "new line" symbols inside the polynomials…
what is easier to read and to insert into the computer
something like this
x1^2+x2x3+x4^2+7
or
x1^2…..+ x2
x3 +…..
x4^2……..+7
???? dots represents spaces which otherwise would be deleted when I post it
There is a big chance that people will copy it in their computer with mistakes and will solve completely different system of equation than is meant and will waste their time.
Perhaps every polynomial should be inserted between () like (x1^2+x2*x3+x4^2+7) and contain no other unnecessary symbols like spaces and new line symbols

… make a text file which contains equations in a format that is easy to read….
Perhaps every polynomial should be inserted between () like (x1^2+x2*x3+x4^2+7) and contain no other unnecessary symbols like spaces and new line symbols

Thanks for your feedback. I'll talk with the author.
My first impression is that the file containing the equations (uovMTlevel2_17_13.txt) is a typical unix text file. So it looks well structured if you use a unix editor like VI (contrary if you use a typical Windows editor like Notepad). As the equations are very long they are filled in lines where no single line is wider than 180 columns which is the reason for the newlines.
My experience with modern Computer Algebra Systems like SAGE is that they just ignore unnecessary blanks.
Could you please explain a bit more how you extracted the equations and what tools/operating system you used?

Is there supposed to be some weakness?

May I ask why this challenge is only in Level II?
I think it is the hardest problem of all on this site including in Level X, assuming that there is no weakness.
So my question again, is there supposed to be some kind of weakness?

It is a very hard problem but I am not sure it is as hard as some of the level 3 challenges.

At least there are available attacks against this system.

I agree with Viktor, probably I am missing something but unless one can spot some semplification (finding the ov form seems unfeasible) we are left with
39^16 possible variables assignment, try to compute each nanosecond the 13 equations and you will need about 0.86 the universe life :D
I think I am missing some semplification…
cheers

… we are left with 39^16 possible variables assignment, try to compute each nanosecond the 13 equations and you will need about 0.86 the universe life :D I think I am missing some semplification…

May I ask one of the three users who already found a solution (randall77, jomandi, Veselovský) to give a small hint?

This challenge needs either quite a powerful CPU or the most efficient algorithm for solving such system of equations available today to be able to find a solution in a reasonable time.
But on the other hand I found the faster the algorithm is the more memory it needs. (That does not have to be true, it is just my observation.)
My old computer needed almost a whole day to find a solution, but I used my own algorithm which probably was not very efficient.

As a hint I just say: Estimate what portion of all 39^17 (it is even more than 39^16 as Witten wrote) possibilities represent a solution. Then adapt your method in accordance with your estimation.

first of all, there are better ways than brute forcing. but if you want to brute force it, you should take the following into account.

each variable x1,…,x39 can take the values 0,…,16. so you have 17^39=9.710^47 (and not 39^17=1.110^27) possibilities to choose the variables.

when you fix for example x14,…,x39 with random values, then there exist 17^13 possibilities to choose x1,…,x13. you have 13 equations, and each function value f1,…,f13 can also have 17 possible values, so there are also 17^13 possibilities. that means, that you have 1 solution on average.

if there is such a solution, then a search will need approximately 17^13/2=5.0*10^15 tests to find it.

so you have 17^39=9.710^47 (and not 39^17=1.110^27) possibilities to choose the variables

Of course, it is 17^39.
It was a silly mistake in my previous post. What I meant was that there should be 17 in Witten post not 16 and I have not noticed his mistake in writing it in a wrong order.

yes yes of course!! mine was a (double) stupid writing mistake! thanks for the hints

Hello,
can anyone from the members that already solved this challenge verify that when i insert x as [1,12,11,3,4,16,15,6,7,9,5,10,14,2,7,11,9,3,6,0,4,1,16,5,15,12,2,7,3,7,6,13,3,14,4,11,16,8,10]
then the result is
[10,13,9,15,6,12,16,6,9,7,5,7,16] ?

In this way i will find out if some of my equations where implemented correctly to my program or if i have made some mistake/s.

Maybe this "someone" can also send me the correct answer - if i am mistaken - or another example that comes out of his program in order to verify my equations

I believe that such an example should have been given - as it was done in the toy example - in this way one could find out if he has done any mistakes.

Best regards,
George

…find out if some of my equations where implemented correctly to my program or if i have made some mistake/s.

I got the same problem when was solving it, I was not sure whether the equations were copied correctly into my computer. I had to correct the format of the equations manually then, which makes mistakes easily.
Seems like your 4-th and 6-th equations are wrong. I got result:
{10, 13, 9, 6, 6, 6, 16, 6, 9, 7, 5, 7, 16}

Here is a zipped attachment with a better format of the equations. It contains 13 equations separated by commas. Variables are named x1, x2,… instead of x_1,x_2…
There are no unnecessary symbols like space, newline symbol, tab symbol… and no things like Vec 1, Vec 2 in between, which makes it even worse.
Multiplication is represented by "*" and exponentiation by "^".