Re: 2 forwarded messages...DNSEXT discussion of Day and Kaminsky

On Wed, Feb 18, 2009 at 7:17 AM, David Nicol <[email protected]> wrote:
> I'll second this -- what's a good reference for what is a security
> reduction proof?
> http://en.wikipedia.org/wiki/Provable_security seems like a nice
> introduction, my takeaway from reading the article was that "provable
> security" is concerned with making "given A, therefore B" kinds of
> statements in a formal way, and that the literature of that field
> calls their proven lemmas "reductions".

The name refers to reducing the problem scope.  If you can prove that
A is secure as long as B is secure, and B is simpler to analyze than
A, then you've "reduced" the work to analyze A.  E.g., forging a
Rabin-Williams signature is reducible to factoring (i.e., if you can
forge a Rabin-Williams signature for a given public key, then you can
factor that public key with a high probability of success), and
factoring is a well known problem that has received significant
scrutiny, so it lends confidence to the security of Rabin-Williams
signatures.