How are secure hashing and encryption algorithms proven? Given that:


  You should always use proven secure hashing and encryption algorithms,
  rather than attempting to write your own.


What's the process for criteria for an algorithm being proven?

Is it necessarily a peer review process? Does an algorithm need to withstand exploit attempts for N amount of time by M many experts?

Or, is there a mathematical proving process that security experts can apply on their own to evaluate an algorithm?

From the consumer perspective, how can early algorithm adopters vet new potential algorithms? Or put another way: When should security-concerned folks start considering new algorithm X?
My personal opinion: "proven secure" is more of an advertising slogan than anything else. The one-time pad and certain multiparty protocols can be shown to have some kind of information-theoretic security; these are exceptions to the rule. "Don't roll your own crypto" is still sensible advice however.

For the rest of this discussion, I'll try and stick to facts.

In public-key cryptography, there are three kinds of number-theoretical primitives in common use (RSA groups, prime-order groups based on finite fields F_p, prime-order groups based on elliptic curves) for which the security properties and arguments are based on a combination of experience and heuristics. For example, RSA has been around for 35-odd years now without anyone finding a way to break it when used properly; a lot of effort has gone into factoring integers but the best number-field sieving algorithms available today are still nowhere close to factoring 4096-bit RSA moduli. Similar considerations apply to taking discrete logarithms in finite fields.

What "provable security" does is construct a layer of cryptographic components on top of these primitives and prove that a certain formal definition of breaking the components is at least as hard as breaking a certain formal notion of security on one of the primitives. For example, one can prove that if you obtain my ElGamal public key and you give me any two messages of the same length, and I give you an ElGamal encryption of one of them back, then you cannot do any better than guess at random which of your two messages I encrypted --- unless you can also solve one of cryptography's basic hard problems over the group I'm using to do my ElGamal encryption, which has been studied since around the 1980s. (This is formally called the IND-CPA to DDH reduction for ElGamal and is a staple of public-key cryptography 101 courses.)

Does this mean that ElGamal is secure for a particular application? It depends, and it says nothing about "out of band" attacks such as malware on your computer, biased randomness generators etc. 

I see the role of security proofs primarily as a layer of security within the cryptographic research community. Proposals for new primitives are rare, and need a jot of justification to be accepted. However, let's say you have a particular application where you want, for example, an encryption scheme for messages where you want anyone to be able to tell just from looking at a ciphertext if the plaintext is all zeroes or not, but nothing else. A cryptographer might be able to design such a scheme for you based on existing primitives or schemes, and then prove that breaking the new scheme with the additional feature is in some way at least as hard as breaking one of the existing and well understood schemes. For example, one could adapt ElGamal and prove that if you can tell an encryption of 01 from an encryption of 10 or 11, then you can also break ElGamal directly.

Within this specific context --- proving a scheme to satisfy some formal notion under the assumption that the primitives already satisfy some formal notion --- the word "proof" in cryptography means the same as it does in mathematics. Cryptographic proofs typically do not address the following points:


Does the primitive in question really satisfy the property? 
Is the formal notion of security sufficient for a particular real-world application?
Is the proof correct? The amount of proof-reading done before a paper gets into CRYPTO is much less than for most mathematical journals; mistakes do happen.


To give another example: block cipher modes of operation. The security proof for (say) Galois-Counter Mode (GCM) is that if you had a perfect block cipher B then B-GCM (with random initialisation vectors and a few other things) would give you  authenticated encryption. In contrast, ECB mode has no such security proof (and fairly obviously does NOT provide much security even with a perfect block cipher). AES is not a perfect block cipher, but a pretty good one judging by experience. But we can still say that AES-GCM is a much better choice than AES-ECB.

The original quote, in my opinion, would read better as:

"Cryptographers should not (usually) design new schemes for the sake of adding features without proving them to be at least as secure as existing ones. Everyone else should stick to standardised algorithms."