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

[yu xue]

I stumbled upon a special digital signature scheme which is based on
Mandelbrot and Julia Fractal Sets[1]. The author claimed that it has
advantage of shorter key size and better performace etc than RSA/DSA.
However, it seems that sender and receiver both need to generate pub/private
key... I am not sure whether this can be allowed.

In addition, I don't know whether the network coding-related digital
signature is benefit, such as [2,3]. It seems that this kind of signature is
still based on discrete log problem such as CDH assumptions....

Just a *half thought* consideration:), thanks..

Regards
  Yu Xue


Reference:
[1] A new digital scheme based on Mandelbrot and Julia Fractal Sets
http://www.scipub.org/fulltext/ajas/ajas411848-856.pdf
[2] Signing a Linear Subspace:Signature Schemes for Network Coding
http://crypto.stanford.edu/~dabo/abstracts/netcode.html
[3] http://eprint.iacr.org/2009/569
2010/4/29 Zooko O'Whielacronx <zookog at gmail.com>

> 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
> _______________________________________________
> tahoe-dev mailing list
> tahoe-dev at allmydata.org
> http://allmydata.org/cgi-bin/mailman/listinfo/tahoe-dev
>



-- 
    此致
敬礼!
                      薛宇

                  身前身后
                  是时间的深渊
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://allmydata.org/pipermail/tahoe-dev/attachments/20100430/cf77b7b2/attachment.htm