[charrisku]

I was mainly curious if any asymmetric algorithms exist which are not easily analyzed by algebraists, et al. According to the comment by tveita, this does not appear likely, and I am sorry to hear it. I don't discount what you say about mathematical algorithms being easier to analyze, so flaws are shallower. However, I have seen smart people do quite amazing things with mathematics in my life. People who spend years studying algebra or number theory learn so many patterns that the good ones can pull unbelievably clever arguments seemingly out of pure intuition. That is somewhat disconcerting to me because something like RSA or ECC is precisely the sort of problem those people can apply that intuition and pattern recognition towards. I obviously don't know of an asymmetric algorithm which is analogous, but something like AES is a nightmare to analyze algebraicly (it really does have that "jumble of shit" look to it when written out as an operator). That seems to me to offer some small resistance to the math genius with the spooky intuition. My main point was how dangerous a smart person can be with a problem that his/her brain is geared for, so I was curious if any algorithms existed which are not easy for a mathematician to attack.

[rockdoe]

This is understood. RSA depends on prime factoring. (EC)DH depends on discrete logarithms. These problems have been studied by the kind of people you mention, from all over the world, an in some cases massive speedups and breakthroughs have been made. But even after all those years, the problems are still "hard enough". That's what gives them confidence.

I'm not even sure what you would imagine the alternative would be. An algorithm that isn't amendable to mathematical analysis?

Even for symmetrical ciphers, which look far less like pure math, analysis proceeds very much along mathematical lines (differential/linear cryptanalysis), or in some cases, via algebra as well: https://en.wikipedia.org/wiki/XSL_attack

[charrisku]

I can't really say what I imagine the alternative to be (if I could, I'd write it up), but I do know that if it had an inherent complexity in it's mathematical structure, I would image it to be more resistant to attack by a good mathematician than otherwise. At present we cannot prove that any of these algorithms is actually NP complete and the best device in existence to prove the conventional wisdom wrong sits between two ears. I think any algorithm designed to make the human brain less effective at analyzing it necessarily adds security, although I wholeheartedly cede the point that it also makes the flaws in said algorithm harder to find, so there is obviously a trade-off inherent to this approach. I also agree that any analysis will ultimately take a mathematical flavor (it is an algorithm of course, math is essentially the only trick humans have come up with here), but that isn't to say we can't craft one which makes that analysis fiendishly difficult. Thanks for the XSL link, I'm not a cryptographer, so wasn't aware of that.

[aparent]

I think the issue is that the additional properties required for asymmetric key cryptography (as opposed to symmetric) are hard to gain without introducing some structure.

[empath75]

I'm surprised that you're a mathematician and seem unfamiliar with complexity classes.

[aparent]

What do mean by this? I don't think complexity classes give any provable security to asymmetric cryptography. It cannot be proven that the difficulty of breaking any of the currently used (or known?) asymmetric key cryptography is not in P (It can't even be proven to be NP-complete).

[charrisku]

This.

[wolfgke]

Asymmetric crypto clearly is in NPcomplete. What one can not prove yet is that some crypto system is in NPcomplete \ P (since this would imply P != NP).

[aparent]

> Asymmetric crypto clearly is in NPcomplete

To be in NP-complete a problem must both be in NP and every problem in NP must have a polynomial time reduction to it. This means that NP-complete is fully contained in NP and in fact smaller if P!=NP.

For example P is contained in NP and if P!=NP then no problems in P are in NP-complete.

[wolfgke]

Sorry, I was typing NPcomplete and meant NP. :-(