<div>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.</div>
<div> </div>
<div>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....</div>
<div> </div>
<div>Just a *half thought* consideration:), thanks..</div>
<div> </div>
<div>Regards</div>
<div> Yu Xue</div>
<div> </div>
<div><br>Reference:</div>
<div>[1] A new digital scheme based on Mandelbrot and Julia Fractal Sets</div>
<div><a href="http://www.scipub.org/fulltext/ajas/ajas411848-856.pdf">http://www.scipub.org/fulltext/ajas/ajas411848-856.pdf</a></div>
<div>[2] Signing a Linear Subspace:Signature Schemes for Network Coding</div>
<div><a href="http://crypto.stanford.edu/~dabo/abstracts/netcode.html">http://crypto.stanford.edu/~dabo/abstracts/netcode.html</a></div>
<div>[3] <a href="http://eprint.iacr.org/2009/569">http://eprint.iacr.org/2009/569</a><br></div>
<div class="gmail_quote">2010/4/29 Zooko O'Whielacronx <span dir="ltr"><<a href="mailto:zookog@gmail.com">zookog@gmail.com</a>></span><br>
<blockquote style="BORDER-LEFT: #ccc 1px solid; MARGIN: 0px 0px 0px 0.8ex; PADDING-LEFT: 1ex" class="gmail_quote">On Thu, Apr 22, 2010 at 12:40 PM, Jonathan Katz <<a href="mailto:jkatz@cs.umd.edu">jkatz@cs.umd.edu</a>> wrote:<br>
> On Thu, 22 Apr 2010, Zooko O'Whielacronx wrote:<br>><br>>> Unless I misunderstand, if you read someone's plaintext without having<br>>> the private key then you have proven that P=NP!<br>…<br>> The paper you cite reduces security to a hard-on-average problem, whereas<br>
> all that P \neq NP guarantees is hardness in the worst case.<br><br>I see. I did misunderstand. So although cracking the Lyubashevsky,<br>Palacio, Segev encryption scheme [1] doesn't mean that you've proven<br>
P=NP, because NP is about worst-case rather than average-case, it<br>*does* mean that you've solved the subset sum problem for a random<br>instance. If you can do that for all keys that people use in real life<br>then you can solve the subset sum problem for almost all random<br>
instances, which seems like it would still be a breakthrough in<br>complexity theory. If you can do it for only a few keys then this<br>means that the Lyubashevsky, Palacio, Segev scheme is susceptible to<br>"weak keys".<br>
<br>Is that right?<br><br>Anyway, although this is not one, there do exist proposals for public<br>key crypto schemes where breaking the scheme implies solving a worst<br>case instance of a supposedly hard problem, right?<br>
<br>Here is a recent paper which surveys several of them (all<br>lattice-based) and estimates secure key sizes: [2].<br><br>None of the signature schemes mentioned therein appear to have the<br>sort of efficiency that we are used to. For example the "ecdonaldp"<br>
(ECDSA) signature schemes measured on<br><a href="http://bench.cr.yp.to/results-sign.html" target="_blank">http://bench.cr.yp.to/results-sign.html</a> have key sizes on the order of<br>tens of bytes, where the most efficient digital signature algorithm<br>
described in [2] has key sizes on the order of thousands of bytes.<br>(And that one is a one-time signature scheme!)<br><br>Okay, so I'm still searching for a signature algorithm which has the<br>following properties (or as many of them as I can get):<br>
<br>1. efficient (signing time, verification time, key generation time,<br>key size, signature size)<br><br>2. some kind of strong argument that it really is secure (the gold<br>standard would be reduction to a worst-case instance of an NP-complete<br>
problem)<br><br>or, if we can't have (2) then at least we want (3) and (4):<br><br>3. rather different from ECDSA, so that a breakthrough is unlikely to<br>invalidate both ECDSA and this other scheme at once<br>and<br>
4. not known to be vulnerable to quantum computers<br><br>and finally but importantly:<br><br>4. easy to understand and to implement<br><br>Suggestions welcome!<br><br>Regards,<br><br>Zooko Wilcox-O'Hearn<br><br>[1] <a href="http://eprint.iacr.org/2009/576" target="_blank">http://eprint.iacr.org/2009/576</a><br>
[2] <a href="http://eprint.iacr.org/2010/137" target="_blank">http://eprint.iacr.org/2010/137</a><br>_______________________________________________<br>tahoe-dev mailing list<br><a href="mailto:tahoe-dev@allmydata.org">tahoe-dev@allmydata.org</a><br>
<a href="http://allmydata.org/cgi-bin/mailman/listinfo/tahoe-dev" target="_blank">http://allmydata.org/cgi-bin/mailman/listinfo/tahoe-dev</a><br></blockquote></div><br><br clear="all"><br>-- <br> 此致<br>敬礼!<br> 薛宇<br>
<br> 身前身后<br> 是时间的深渊<br>