This challenge concerns the Discrete Logarithm Problem (DLP) in a "medium" field.
For powers of very small primes and for large prime fields the function-field sieve and the number-field sieve are highly optimized; for intermediate fields algorithms with the same asymptotic behavior exist but the actual running times are slower. Are you able to solve the DLP in such a field anyway?
Read more...

Is it possible to provide a small example of this problem with known solution?
Something like it is in the challenge "Unbalanced Oil and Vinegar System", where there is a "baby example" with the correct key which helps to see how the system works.

This would make this challenge more accessible for people even they do not fully understand the theory involved in this cryptographic problem.

Viktor,
just to understand you right. Do you want us to offer an easy challenge in addition to the level-3 DSA-challenge?
For the UOV challenges there was the level-1-challenge "UOV Part 1" (http://www.mysterytwisterc3.org/en/cryp ... nges?id=62) and a level-2-challenge "UOV Part 2".
Or do you mean something else by "with known solution"?
Regards, be

No, I did not mean this, even though I do not resist if there will be level 1 or 2 challenge with the same problem.

What I meant was that in LEVEL 2 challenge "UOV Part 2" there was an additional zip file (http://www.mysterytwisterc3.org/images/ ... add-en.zip) which contained two files - one was the actual challenge and the second (toyExample_en.txt) was a "toy example" with few correct solutions and few wrong solutions. So we can test our algorithms first on toy example and try to use provided solutions to learn how the system works. So everybody could see an idea of the system without needing to understand the deep theory in it.

It is like I give you challenge to solve equation x^2 + 2 x - 3 = 0 and then told you x=-3 or x=1 are correct solutions and x=7 is wrong solution. Then you can verify it without knowing too much about quadratic equation and quadratic formula.
Then if I give you harder equation x^2-162 x+6497 = 0 you may be able to solve it even without using the quadratic formula (i.e. without needing too much theory).

I think this is the point, it is a problem that hasn't yet been solved fully. The DLP is not a system...it is not really cryptographical! It is merely a bit of number theory that makes things secure. The fact that DL's are hard to compute is the important thing.

This is going to be a hard challenge, probably unsolvable with current knowledge, hence the phrase "encouraging research" (in the slides) and hence why it is at level 3.

It is highly unlikely that someone who has no experience of discrete logarithms is going to find a solution...so there is really no need to dumb the problem down for anybody or to make it more accessible. It is pretty self explanatory to anyone with knowledge of finite fields.

Anybody capable of solving the problem is capable of generating their own toy examples to work on! It doesn't take much to generate numbers and generate powers in finite fields.

Some posts do not deserve a comment :-)
...and this is not a response to any of the above posts

I just want to encourage others, that toy examples can be really very useful in solving some challenges. It does not matter if it is a simple example of ECC, UOV, DSA or whatever.

This site was my first contact with UOV. I still have not got full knowledge of the theory behind it, but anyway, I was able to solve even the level II of it. And the toy example has helped me a lot in this.
And again this is my first contact with DSA.
It is always a good idea first to see a simple working example before trying to solve the challenge or to study DSA.

...but the challenge has nothing to do with DSA! The challenge is just to compute a discrete logarithm. There is no cryptographical system to break here, it is a (well documented) problem of pure maths.

That is simply what it is. So if you have no knowledge of what a discrete logarithm is then you have no hope in solving the challenge until you do know. Also, once you do know what one is you will not need to be given examples because it will be obvious how to make your own. It is just about finding the power of something in a finite field that gives another thing!

It is a level 3 challenge, so is going to be difficult (and the parameters of the problem make it a research standard challenge...we are not in a prime order field anymore but a field of prime power order). There is no way to simplify without making it is easy.

The discrete logarithm is the simplest thing that the user has to understand to be able to solve this challenge. By "simple to understand what it is" I do not mean that it is also easy to compute it. I guess nobody here would have problems to understand what the discrete logarithm is.

The problem is in understanding the system. And apparently there is a system, otherwise the challenge would be called solve the discrete logarithm and in PDF there would be one equation a^x=b mod N with given (a,b,N).

RSA is also a pure math. But it is also a system, precisely many different systems based on the same math problem. So if you understand that math problem does not mean that you can automatically understand every system, because every system can have its own specifications that you must be aware of.

ECC is again about pure math. But also a system, precisely many different systems...

Discrete logarithm is again about pure math. But can be used in many different ways, i.e. in many different systems.

UOV is again about pure math. But also a system... bla bla... same as above...

Most of the modern cryptographic systems are about pure math. And the same math problem can be used in many different ways, i.e. in many different systems.

Now I said enough. I will not be expressing myself to this topic anymore. Of course unless the author contribute with something, or a person that understands the system precisely.

Can you not see that most of the slides are just there as a discussion around the problem and related stuff? (since the problem is highly unsolved).

The challenge really IS just to compute a discrete logarithm...there is no high tech cryptosystem at work here. Knowledge of the notion of discrete logarithm is all you need to understand.

The challenge is given in exactly the form you just said:

Slide 6 - Here is a finite field
Slide 7 - Here is a base
Slide 8 - Here is a power of the base

Challenge - Find the power.

They called the challenge what it is because essentially solving this problem will lead on to breaking such a system, but that need not concern whoever is attempting the challenge. Also as for not just putting it on one slide and leaving at that...clearly they wanted their challenge to be presentable and nicely written, so added a few things on the background of the challenge and how things were created to stop the usual methods from working (so that people would not waste their time running such attacks).

No RSA is not pure maths, it is a cryptosystem that uses pure maths. All other examples you gave are the same. Discrete logarithms are a thing in pure maths that are used in cryptosystems. This is where your confusion stems from. There is not necessarily a cryptosystem behind every single problem in cryptography.

Well, I do not know what is your intention in all your posts here???

I just asked for a toy example, that is all. If there will be no such an example, that is OK.

If you think you do not need it, that is also OK. But why we should care that you think it would be useless for you? It is irrelevant for me.

And do not take it like I treat you as a person that understands the system precisely that I am replying. So please leave the decision on competent people if they decide to provide a toy example or not.