[charrisku]

As a mathematician (though not a cryptographer), I have a great deal of difficulty trusting cryptographic protocols which have a mathematical basis. Whether they are based on factoring, elliptic curves, or any other mathematical concept, they always "smelled" sketchy to me for the very simple reason that they are easy to formulate in terms of mathematical ideas, hence naturally lend themselves to the thought process of an algebraist or a number theorist. In short, these problems look like precisely the sort of questions a mathematical genius would find tractable. Without any solid proof that they are actually computationally hard to break, it seems like they are inherently dangerous to rely upon because they look like fair game to the next Ramanujan.

I'll also go out on a limb here and also say that I think the technology community has a bias towards thinking something like "math == hard" is true, so gives added weight towards using these same protocols. I know many people here have deep knowledge of both cryptography and software development, so I'd be very interested to hear other people's thoughts on these issues. Can anyone speak about options to math-based public key algorithms, or ways to inject some skepticism into the tech community about these algorithms, so perhaps alternatives can start being implemented? A public key algorithm which doesn't lend itself easily to algebraic analysis would feel much safer to me.

[rockdoe]

Pretty much all of crypto is based on and analyzed by math (at the very least computing and complexity theory), so I'm not clear at all what you're saying here.

People prefer algorithms with a clear mathematical basis because they're easier to analyze, so the flaws surface easier and it's clearer what breakthroughs would break them.

Cryptographers have been looking for algorithms that are NP-hard for example, because having a "breakthrough" in them having to require P=NP is a large hurdle. But it's not the end of the story, because it turns out that a problem being NP-hard doesn't mean it isn't easy to crack (worst case vs actual case).

Your comment reads a bit as saying "we shouldn't use maths to compute things". But maths is what computers do...

[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).

[tveita]

In practice, relying on a clearly defined mathematical problem that is thought to be hard to solve has worked out a lot better than the common alternative of throwing a bunch of random shit together and hoping the result is too complex for anyone to understand.

For asymmetric cryptography there is no alternative not based on math. Even snake oil cryptography mostly deals in symmetric crypto like "unbreakable" ciphers and hashes, because you can't make a working asymmetric encryption scheme by mashing together whatever operations your schizophrenia tells you to.

[syntheticnature]

The Discordians promulgated a code that might be a bit more mathematically resistant. It involves this series of steps:

  CONVERSION:
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

  STEP 1. Write out the message (HAIL ERIS) and put all the vowels at the end (HLRSAIEI)

  STEP 2. Reverse order (IEIASRLH)

  STEP 3. Convert to numbers (9-5-9-1-19-18-12-8)

  STEP 4. Put into numerical order (1-5-8-9-9-12-18-19)

  STEP 5. Convert back to letters (AEHIILRS)

They assert 100% unbreakability, which isn't true, but on a sufficiently long message one's anagram checker might give out, and then there is the task of ordering the words so generated...

Mind you, decryption by the intended recipient is equally complex.

[philh]

Not 100% unbreakable in general, but I think it does pretty well in the real world. There are plenty of messages that Eve simply can't decrypt with complete confidence. For example, she can't tell ATTACK WILL AT DAWN from ATTACK DAWN AT WILL. She'd have to resort to priors to guess which of those was intended.

[aparent]

It is so good that even Alice can't decrypt those with confidence! :)

[wanderfowl]

It's the newest, hottest thing in Crypto: Perfect Backwards Secrecy!

[wolfgke]

This algorithm can be simplified - step 2 can be skipped.

[watersb]

While technically correct, "simplified" is not part of the Discordian vocabulary.

[MatthaeusHarris]

The whole algorithm boils down to "Write your message into an array, then sort the array."

[JadeNB]

On what should they be based, if not a sound foundation that lends itself to rigorously proveable statements (I carefully say only proveable, not proven) and the well developed intuition of a community of experts? To say that, because mathematicians understand and can think about something, they will be able to solve it, seems to be denying the existence of long- (and still-) unsolved elementary problems.

[rpglover64]

Are you happier with the state of symmetric crypto, which, despite relying on conjectures (like the existence of pseudo-random functions) tends not to rely on _algebraic_ ones?

Personally, I don't have particular worries about the hardness assumptions of asymmetric crypto, and I think of them a bit like I think of bitcoin (hear me out). Yes, it is certain that eventually someone will solve the discrete log problem for any given algebraic structure (either by rendering all crypto that relies on it broken, or (less likely) proving it fundamentally secure), but for now, we know that this is hard (since it has been open for a while), and we're also incentivizing people to make mathematical discoveries.

I'd also claim that the "crypto community" (at least the academic side of it) and the "technology community" are not the same, and (at least to me) often feel opposed. Cryptologists write papers filled to the brim with dense and precise mathematical assumptions and reductions; technologists skim the papers, ignore the assumptions, and implement half-assed, unaudited versions of the systems in question and claim them secure (pardon my cynicism).

As to what the community thinks about mathematical public key crypto, they hail it as the greatest innovation since sliced bread and the herald of modern cryptography. Prior to modernity, cryptography was very ad-hoc and depended on what the author's intuitions; modernity introduced precise definitions of what it meant for a system to be secure and raised the bar. It also relies heavily on the concept of a hardness reduction, i.e. a proof that breaking a cryptogrpahic primitive is at least as hard as solving a yet-unsolved math problem.

Specifically about algebraic problems, I have a (low confidence) intuition that they are unavoidable in public-key crypto precisely because of the need for an algebraic structure relating the public and private keys. With this in mind, I'd rather have algorithms which rely on known hard to solve problems (demonstrated hard by having years of mathematical effort poured into them with minimal result) to those which rely on problems no one has ever bothered to look at.

A final question: you are unhappy with public key crypto that relies on algebra; would you be happier if it relied on some other branch of mathematics? Analysis? Topology (okay, so that's still algebra)? Complexity theory (a secure cryptosystem that relied only on P!=NP would be a holy grail for several reasons, but I don't know of any attempts to find one)? Would you feel safe using a cryptosystem that was secure if and only if the Riemann Hypothesis were true? If the RH were false? The Collatz Conjecture?