[tahoe-dev] What's the state of the art in digital signatures? Re: What's the state of the art in factorization?

[Zooko O'Whielacronx]

On Thu, Apr 22, 2010 at 12:40 PM, Jonathan Katz <jkatz at cs.umd.edu> wrote:
> On Thu, 22 Apr 2010, Zooko O'Whielacronx wrote:
>
>> Unless I misunderstand, if you read someone's plaintext without having
>> the private key then you have proven that P=NP!
…
> The paper you cite reduces security to a hard-on-average problem, whereas
> all that P \neq NP guarantees is hardness in the worst case.

I see. I did misunderstand. So although cracking the Lyubashevsky,
Palacio, Segev encryption scheme [1] doesn't mean that you've proven
P=NP, because NP is about worst-case rather than average-case, it
*does* mean that you've solved the subset sum problem for a random
instance. If you can do that for all keys that people use in real life
then you can solve the subset sum problem for almost all random
instances, which seems like it would still be a breakthrough in
complexity theory. If you can do it for only a few keys then this
means that the Lyubashevsky, Palacio, Segev scheme is susceptible to
"weak keys".

Is that right?

Anyway, although this is not one, there do exist proposals for public
key crypto schemes where breaking the scheme implies solving a worst
case instance of a supposedly hard problem, right?

Here is a recent paper which surveys several of them (all
lattice-based) and estimates secure key sizes: [2].

None of the signature schemes mentioned therein appear to have the
sort of efficiency that we are used to. For example the "ecdonaldp"
(ECDSA) signature schemes measured on
http://bench.cr.yp.to/results-sign.html have key sizes on the order of
tens of bytes, where the most efficient digital signature algorithm
described in [2] has key sizes on the order of thousands of bytes.
(And that one is a one-time signature scheme!)

Okay, so I'm still searching for a signature algorithm which has the
following properties (or as many of them as I can get):

1. efficient (signing time, verification time, key generation time,
key size, signature size)

2. some kind of strong argument that it really is secure (the gold
standard would be reduction to a worst-case instance of an NP-complete
problem)

or, if we can't have (2) then at least we want (3) and (4):

3. rather different from ECDSA, so that a breakthrough is unlikely to
invalidate both ECDSA and this other scheme at once
and
4. not known to be vulnerable to quantum computers

and finally but importantly:

4. easy to understand and to implement

Suggestions welcome!

Regards,

Zooko Wilcox-O'Hearn

[1] http://eprint.iacr.org/2009/576
[2] http://eprint.iacr.org/2010/137