One of the themes that shows up repeatedly is what's called
"non-tightness of reduction". Recall that the idea behind
a reduction proof is to show that if you could break the
cipher (recover the key, plaintext, whatever you've modelled
it as) then you could use that ability to get leverage
on some believed-hard problem. So, for instance you might
want to prove that breaking your algorithm was "equivalent" to
letting you factor large products of prime.
There's generally some
additional effort required to solve the hard problem, so
you get a result where being able to break the cryptosystem
with effort *E* implies being able to solve the hard
problem with effort *cE*. If *c* is small, then the reduction
is called "tight". If *c* is large (and we're talking
real large, like big powers of two) then it's called
"non-tight".
K&N write:

Suppose that researchers have been able to obtain a highly non-tight reduction from a hard mathematical problem to breaking a protocol^{2}. There are various common ways to respond to this situation:

- Even a non-tight reduction is better than nothing at all. One should regard the cup as half-full rather than half-empty, derive some reassurance from what one has, and try not to think too much about what one wishes one had.
- Even though the reduction is not tight, it is reasonable to expect that in the future a tighter reduction will be found.
- Perhaps a tight reduction cannot be found for the protocol in question, but a small modification of the protocol can be made in such a way as to permit the construction of a tight reduction -- and we should regard this reduction as a type of assurance about the original protocol.
- A tight reduction perhaps can be obtained by relaxing the underlying hard problem (for example, replacing the computational Diffie Hellman problem by the decision DiffieHellman problem). [This is a very popular move -- EKR]
- Maybe the notion of security is too strict, and one should relax it a little so as to make possible a tight reduction.
- Perhaps the protocol is secure in practice, even though a tight reduction may simply not exist.
- Perhaps the protocol is in fact insecure, but an attack has not yet been discovered.
These seven points of view are not mutually exclusive. In fact, protocol developers usually adopt some combination of the first six interpretations -- but generally not the seventh.

K&N go on to show a number of depressing examples of this and other
problems. Probably the most depressing example they give of a proof that
doesn't show what you'd like is the Blum Blum Shub Pseudorandom Number Generator,
which is based on factoring. There are proofs that provide a lower
bound on the adversary's effort (and hence on the security of the
algorithm). Unfortunately, when you plug in
reasonable sounding parameters (1024 bits)
and the current best factoring algorithms
you discover that the formula for the lower bound tells us that
the attacker's lower bound is a stunning -2^{199} operations,
which isn't that useful. In order to get a reasonable security
guarantee, you need to use a 5000 bit modulus and extract only one
bit per crank of the generator, which is far too expensive for
practical use.

Other topics covered include the security of RSA (including OAEP), ECDSA, and a number of short signature schemes.

^{1.} I'm simplifying here, but it's
close enough for the purpose of explanation.

^{2.} This is cryptographer jargon. In networking,
protocol means "the bits that go on the wire" but in cryptography,
it means something more like "this is the set of cryptographic
messages that are sent between A and B". For most simple systems,
you can read "protocol" as "algorithm".

**UPDATE:** Fixed the title of the new paper. Thanks to Perry Metzger for pointing out the error.

Seems like these days it's pretty tough to get a crypto paper accepted at the good conferences unless you have a proof of security. It doesn't seem to matter much how good the proof is, or how strong the assumptions are you have to make, but it better be there.

The real question then is how to judge a scheme where the inventors can't come up with any kind of proof of security, vs one where there is a proof. Are we well advised to prefer the one with the proof, all else being equal? I think most cryptographers would say yes. If a proposal appears without such a proof, in a domain where proofs are commonly provided, then either the scheme is highly questionable, or the people involved are incompetent. The proof presents a certain barrier to entry that can weed out less well developed proposals.