Re: Koblitz and Menezes: 'Another Look at "Provable Security"'

From: David Wagner (daw_at_taverner.cs.berkeley.edu)
Date: 11/05/04 

Date: Fri, 5 Nov 2004 07:48:22 +0000 (UTC)

Ernest Hammingweight wrote:
>I thought the above paper was great and wonderfully opinionated. It's
>written to be controversial. I was wondering whether better-informed
>people shared my opinion of it.

I have no significant complaints with most of the remarks about provable
security, how to interpret "proof of security" results, the limits
of provable security, and the like. The issues here are standard and
well-known to anyone working seriously in this area, but not necessarily
well-known to outsiders. It may well be useful to have them written down
in a form understandable to those who aren't specialists in this area.

Of course, keep in mind that these are the personal opinions of two
professional in the field, but not the consensus of the entire field.
Don't be surprised if others have differing opinions. Also, it is always
more fun to read about "the philosophy of X" when opinions are stated in
a slightly exaggerated, over-the-top, or contrarian fashion, so I tend
to think that opinion pieces like this should be read with that in mind.

>The authors seem to have a dislike of RSA-PSS and put forward a
>convincing (well, in my fickle view) handwaving argument that PSS is
>overkill. Do others agree?

Naah, I didn't buy their argument. PSS gets a stronger provable security
level by modifying the signature scheme to get a tighter reduction.
They point out that the other way you can get this same stronger provable
security level is by strengthening the complexity-theoretic hardness
assumptions: if you make a stronger assumption about RSA, then you can
prove stronger things about FDH (the simpler version of PSS).

Personally, I think weakening assumptions as much as possible is useful.
To repeat a lovely turn of phrase I read elsewhere, weaker assumptions
are less likely to disappoint. (Unfortunately, I can't remember where I
read this. Maybe someone else can point out the right citation so that
I can give proper credit.) The value of schemes like PSS is that they
let you get fully strong security (and tight reductions) with weaker
assumptions. Consequently, I believe such schemes have value.

>The paper also contains this delightful sentence 'Regrettably, many
>"provable security" papers seem to have been written to meet the goal
>of semantic security against comprehension by anyone outside the
>field.'. That seems rather harsh or is it accurate?

It is an exaggeration and totally false, of course. Does anyone think
that papers are written with the deliberate purpose of preventing
outsiders from being able to understand the paper? That's a ridiculous
assertion. I doubt that Koblitz and Menezes really mean this to be
taken literally; I assume it is a case of poetic license. I can say
that I am overjoyed when anyone reads one of my papers; if I knew how to
write my papers so that they would be more accessible and interesting
to a broader audience (without sacrificing efficiency of communication
to specialists), I'd do so.

Relevant Pages

  • Risks Digest 24.18
    ... Risks of using computers in airplanes ... New Security Paradigms Workshop: Call for Papers ... "Practical Internet Law for Business", ...
    (comp.risks)
  • [Full-disclosure] CFP: MobiPST 2012
    ... The Second International Workshop on Privacy, Security and Trust in Mobile ... Recently, mobile wireless devices, such as wireless sensors, smart tags, ... papers cannot have been previously published in or be under consideration ...
    (Full-Disclosure)
  • CFP CISIS 08
    ... Computational Intelligence in Security for Information Systems ... University of Burgos, Spain ... Accepted papers will be included in CISIS'08 Proceedings to be published ...
    (Bugtraq)
  • [fw-wiz] NSPW 2006 Call for Papers
    ... New Security Paradigms Workshop ... A paradigm shift is thus not an incremental contribution to an established ... We solicit and accept papers on any topic in information security subject ... The submission in PDF format, ...
    (Firewall-Wizards)
  • [fw-wiz] Call for Papers: NSPW Deadline Extended
    ... CALL FOR PAPERS: EXTENDED DEADLINE ... New Security Paradigms Workshop ... A paradigm shift is thus not an incremental contribution to an established ... The submission in PDF format, ...
    (Firewall-Wizards)