[Cryptography] What to put in a new cryptography course

[Jerry Leichter]

> The site contains lots of assertions that curves with particular
> properties are more secure than curves that don't have those
> properties....
> Having reread the whole site, I still have not discovered an
> explanation of exactly how the mechanics of geometry on modular
> coordinate systems are transformed in some cases into a specific
> algebraic formula whose solution would require mathematical
> operations believed to be Hard.  It seems to be treated as
> something that everyone except maybe a few specialists is
> simply expected to assume "because we say so."
It's *not quite* like that.

The *generic* discrete log problem (over the integers mod some N, or over an elliptic group) is considered hard because no one, after years of work, has found any attacks on it.

There's no *general* result that says these problems are hard.  What we have instead is some specific, very powerful attacks against particular instances of the problem.  We eliminate those particular instances from consideration and say "the rest look good".

*As a matter of theory and mathematics*, we're living in sin:  We assume the problems we pick are hard because our best minds have brought our best methods to bear on them and have not only made no progress, they've managed to prove that *using these techniques* no progress is possible.

Note that the same is true of RSA - and even of factoring, which *may* in fact be harder; we still, after all these years, don't know for sure.

Then again, the same is true for all of our other cryptographic primitives.  The best we can say about, say, AES is that it's secure against all known attack methods.

That's the state of our knowledge in cryptography today.  We use what we use as a matter of engineering, not science.

It's worth noting that one of the critiques of "provable security" is that when you dig deep into much of the work, you find that it starts off with assumed-hard problems that are rather specialized - a paper will seem to be assuming the difficulty of discrete logs, but it's *actually* assuming the difficulty of some decision problem related to discrete logs.  We may have no idea exactly how the difficulty of that specialized problem relates to the general discrete log problem, and it's unlikely all that much effort has been directed at the specialized problem.  See, for example, "The Brave New World of Bodacious Assumptions in Cryptography" http://www.ams.org/notices/201003/rtx100300357p.pdf

                                                        -- Jerry