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

[David-Sarah Hopwood]

Zooko O'Whielacronx wrote:
[...]
> 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!)

Indeed, it isn't worth considering such schemes at all, since they are
strictly worse in both security assumptions and efficiency than hash-only
schemes, as discussed below.

> 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)

Actually the gold standard (or let's call it a 'platinum standard' if
the above is gold) would be not to depend on any trapdoor problem at all;
only on the preimage resistance of a hash function (which Tahoe must
depend on in any case). We have schemes that meet that standard, for
example Lamport-Diffie-Winternitz and constructions based on it.

(Lamport-Diffie-Winternitz, or LDW, is the scheme described in section
3.3.3 and Algorithm 5 of
<http://www.cosic.esat.kuleuven.be/publications/article-1048.pdf>.)

I have an idea for how to construct an efficient unlimited-time signature
scheme from LDW without any additional security assumptions. Except for
the larger signature size, it has comparable or better efficiency than
ECDSA according to some back-of-the-envelope calculations. That can wait
until after we have released Tahoe 1.7, though.

> 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

A 'platinum standard' scheme, if we were confident of implementing it
correctly, would obviate the need to use more than one scheme.

> and
> 4. not known to be vulnerable to quantum computers

Hash-only signature schemes are no more vulnerable to quantum computers
than the hashes they are based on. The best known algorithm for
generically finding preimages of a hash is Grover's algorithm, which
provides no more than a square-root improvement [*].
<http://arxiv.org/abs/quant-ph/9605034v1> proves that this is
tightly optimal for a generic quantum database search algorithm:

#  ... Finally we give a lower bound on the efficiency of any possible
#  quantum database searching algorithm and we show that Grover's
#  algorithm nearly comes within a factor 2 of being optimal in
#  terms of the number of probes required in the table.

[*] The complexity of the variant of Grover's algorithm described in
    the above paper is O(sqrt(N/t)) where t is the number of solutions.
    This compares to O(N/t) for conventional brute-force search. For a
    secure hash function with sufficiently long output, t is expected
    to be 1, i.e. the only solution is the one that the signer or key
    generator originally hashed.

It remains possible that either a quantum algorithm or a conventional
algorithm could take advantage of weaknesses in a particular hash
function, but we can use a hash combiner to reduce the risk of that.

> and finally but importantly:
>
> 4. easy to understand and to implement

I think that hash-only schemes can meet that requirement.

-- 
David-Sarah Hopwood  ⚥  http://davidsarah.livejournal.com

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 292 bytes
Desc: OpenPGP digital signature
Url : http://allmydata.org/pipermail/tahoe-dev/attachments/20100501/5578b687/attachment.pgp