Forum

Challenge "Post-Quantum Cryptography: Unbalanced Oil and Vinegar System — Part 1"

Challenge "Post-Quantum Cryptography: Unbalanced Oil and Vinegar System — Part 1"  

  By: admin on April 7, 2011, 9:34 a.m.

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 a simplified version of such a system today already.
Read more...

 Last edited by: admin on Oct. 31, 2021, 2:54 a.m., edited 1 time in total.

Re: Challenge  

  By: fretty on June 21, 2011, 6:25 p.m.

Is there meant to be a trick to this challenge or do I really have to find a solution by trial and error? I am trying to do it using pen and paper.

Re: Challenge  

  By: be on June 22, 2011, 8:21 p.m.

Is there meant to be a trick to this challenge or do I really have to find a solution by trial and error? I am trying to do it using pen and paper.

Yes, you need trial and error here. However, it's not too many tries.
The alternative is breaking UOV itself - but the best known algorithm for this needs /more/ trials as internal computations than you'd need for this challenge by "just trying".
You also can use a spreadsheet program like Excel or Calc, which many of you consider as paper&pencil equivalent today.

Re: Challenge  

  By: DarkFibre on July 12, 2011, 1:42 a.m.

I've solved for all the variables and entered the answer in three different formats but none of them were accepted. Is there a specific format the answer has to be in or am I just wrong?

Thanks.

Re: Challenge  

  By: be on July 12, 2011, 9:40 p.m.

I've solved for all the variables and entered the answer in three different formats but none of them were accepted. Is there a specific format the answer has to be in, or am I just wrong?

This challenge is defined over GF(5). You used the number set {-2, -1, 0, 1, 2}. Please use numbers from {0,1,2,3,4}.
More general: We only use in GF(p) numbers from 0…(p-1). Therefore your solutions have been rejected.
Please use the input and output set of the natural numbers.

Re: Challenge  

  By: DarkFibre on July 13, 2011, 5:34 p.m.

I've solved for all the variables and entered the answer in three different formats but none of them were accepted. Is there a specific format the answer has to be in, or am I just wrong?[/quote:x5o6oa15]
This challenge is defined over GF(5). You used the number set {-2, -1, 0, 1, 2}. Please use numbers from {0,1,2,3,4}.
More general: We only use in GF(p) numbers from 0…(p-1). Therefore your solutions have been rejected.
Please use the input and output set of the natural numbers.

brackets and it uses spaces. I swear the hardest part of most of these challenges is not finding the answer but guessing what format the answer should be entered in. I guessed 7 times (albeit with the wrong numbers…) and never guessed that format.

Re: Challenge  

  By: be on July 13, 2011, 9:48 p.m.

But how in the world were we supposed to guess to use {} brackets, commas, and no spaces?

I intended my answer to be a mathematical description of the set.
Our validation program here is more intelligent: If you have the right numbers in the right order it should be able to abstract from brackets or blanks or commas. Please try.

Maybe you can send me a direct email with suggestions how we can make the format of the solutions for other challenges more clear.

Re: Challenge  

  By: DarkFibre on July 14, 2011, 4 a.m.

But how in the world were we supposed to guess to use {} brackets, commas, and no spaces?

I intended my answer to be a mathematical description of the set.
Our validation program here is more intelligent: If you have the right numbers in the right order it should be able to abstract from brackets or blanks or commas. Please try.

Maybe you can send me a direct email with suggestions how we can make the format of the solutions for other challenges more clear.

I did not know that. Perhaps I am assuming too much based on my difficulty with getting the format from one or two others. My apologies.

But I apparently just do not understand the problem fully as I can't find any numbers (at least 0-99) that work now. I guess I need to brush up on my math…

Thanks for the reply and the challenges.

Re: Challenge  

  By: fretty on July 14, 2011, 4:20 p.m.

You do not even need to go past the number 4 for any of the variables, we are working mod 5.

e.g. in GF(5) we have that 2+4 = 1 because 2+4 = 6 in Z and 6 leaves remainder 1 on division by 5.

So really the 0,2,3 on the right hand sides of the equations are with respect to mod 5.

Say you were trying to solve the equation x^2 = 2. If you were looking for an integer solution then there will be none but working mod 7 (i.e. in GF(7)) we find that there are 2 solutions, x=3,4.

I think you might be looking for integer solutions to the equations rather than mod 5 solutions. As the above example shows, there may be no integer solutions yet there might exist mod 5 solutions (and infact here there are some).

Re: Challenge  

  By: DarkFibre on July 15, 2011, midnight

I guess I should have taken matrices and linear algebra in college… Using mod 5 reduced the run-time of my program from all day to almost instant. Thanks for the help! :)

Re: Challenge  

  By: Dano on July 31, 2011, 2:34 a.m.

hallo,

gibt es zu dem thema paar deutsche referenzen?
reines googeln war nicht sehr erfolgreich :(
um das lösen zu können muß ich erstmal wissen wie die verschlüsselung funktioniert^^

mfg Dano

Re: Challenge  

  By: fretty on July 31, 2011, 10:57 a.m.

This is a signature scheme (I think), rather than an encryption algorithm.

The basic question being asked here is:

"Can you find a solution [x[1], x[2], x[3], x[4], x[5]] mod 5 to the three equations?"

The quadratic terms make this a harder problem than if the equations were linear. In the users secret system the quadratic terms appear in a nicer fashion (I think).

Anyway, I solved this by hand and with a few nice choices of the variables you can eliminate things to make a nicer system to solve.

Re: Challenge  

  By: Witten on Dec. 5, 2011, 1:06 p.m.

Hi,
is it really needed an affine transformation to put the system in oil-vinegar decoupled form or one could just use an invertible matrix?
anyway i thought that for 3eqns within F5 a brute force algorithm was more then enough instead of trying to find the ov-form!
thanks for these nice challenges!
cheers

Re: Challenge  

  By: fretty on Dec. 6, 2011, 1:57 p.m.

I did it by hand in about 5 mins…just do a manual check.

Re: Challenge  

  By: Norbert on Sept. 21, 2016, 10:01 p.m.

Am I right in assuming that there is more than one solution? If yes, is any correct solution accepted? I have a couple of solutions, with 0 <= x[n] < 5, and I am pretty sure that they satisfy the equations mod 5, but the system refuses them. What might I be getting wrong?


Currently 10 guests and 0 members are online.
Powered by the CrypTool project
© 2009-2021 MysteryTwister team