<?xml version="1.0" encoding="iso-8859-1" ?>
<rss version="2.0">
  <channel>
    <title>2010 Reports</title>
    <link>http://eprint.iacr.org/forum/list.php?10</link>
    <description><![CDATA[Discussion forum for Cryptology ePrint Archive reports posted in 2010.
Please put the report number in the subject.

]]></description>
    <language>EN</language>
    <pubDate>Tue, 07 Aug 2012 23:30:38 -0600</pubDate>
    <lastBuildDate>Tue, 07 Aug 2012 23:30:38 -0600</lastBuildDate>
    <category>2010 Reports</category>
    <generator>Phorum 5.1.22</generator>
    <ttl>600</ttl>
    <item>
      <title>Re: report 2010/288</title>
      <link>http://eprint.iacr.org/forum/read.php?10,665,753#msg-753</link>
      <author>laurelmjay</author>
      <description><![CDATA[good catch]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,665,753#msg-753</guid>
      <pubDate>Tue, 07 Aug 2012 23:30:38 -0600</pubDate>
    </item>
    <item>
      <title>report 2010/288</title>
      <link>http://eprint.iacr.org/forum/read.php?10,665,665#msg-665</link>
      <author>AG</author>
      <description><![CDATA[I read this paper and I found an error which is not very important but should be corrected:

page 9, in the Setup phase first one should generate an error vector e and then take v as A_0 * e and publish v as a part of the public key PK. Otherwise, if one just chooses v randomly and use it for encryption, nobody could do the associated decryption.

Thank you!]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,665,665#msg-665</guid>
      <pubDate>Mon, 25 Jun 2012 11:29:34 -0600</pubDate>
    </item>
    <item>
      <title>2010/625: Reason for revision 5</title>
      <link>http://eprint.iacr.org/forum/read.php?10,576,576#msg-576</link>
      <author>Ben.Smyth</author>
      <description><![CDATA[Version 20111110:012334 (posted 10-Nov-2011 01:23:34 UTC) contains a more detailed description of our results and includes complete proofs.]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,576,576#msg-576</guid>
      <pubDate>Wed, 09 Nov 2011 18:29:27 -0700</pubDate>
    </item>
    <item>
      <title>Re: Some views on 2010/652</title>
      <link>http://eprint.iacr.org/forum/read.php?10,521,522#msg-522</link>
      <author>wai2ha</author>
      <description><![CDATA[The mode is not a wide-pipe hash,it doesn't really
produce CV of 2 size big,besides this,for a wide-pipe hash,it must transform the CV of 2 size big back into one size big in the end.]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,521,522#msg-522</guid>
      <pubDate>Tue, 26 Jul 2011 21:16:48 -0600</pubDate>
    </item>
    <item>
      <title>Some views on 2010/652</title>
      <link>http://eprint.iacr.org/forum/read.php?10,521,521#msg-521</link>
      <author>wai2ha</author>
      <description><![CDATA[This paper tried to give a new mode to improve a codomain reducing problem for narrow-pipe hash functions.The paper is very badly written and full of typos.But I don't think those views on the  mode are right:
1.It fails to be secure against multicollision attacks.
    To see this, group calls to F by pairs calling the result G and consider messages of the restricted form (M_1, -M_1, M_2, -M_2, M_3, -M_3, ...)
   Then, all calls to G are of the form G(CV_i,0,M_i)=F(F(CV_{i-1},0,M_i),M_i,-M_i). As a consequence, G only receives  2 arguments as in a classical Merkle-Damgard and multicollision attacks do apply.

My reason is:
 a.    sum M_{i}=CV_{i-1}+sum M_{i-1}+M_{i},one can't simultaneously select a message and control an  exact value of CV_{i-1} to make the block sum M_{i-1}=0 

b. Even the case of sum M_{i-1}=0,it doesn't mean the mode is in a classical Merkle-Damgard.the sum M_{i-1}=0 is one of the 2^{m}(where,m=1024) results,any a result is additional addend for the normal step functions of compression function.

c. We can improve the step functions as(e.g.):for the steps of first round,the additional addend is m_{i,j} (where j=0,1,...,15),for steps of second round,the additional addend is cv_{i,j},in this way,no matter sum M_{i-1} is 0 or not, at least there will be effective additional addend for one round.  
So,multicollision attacks don't apply.

2.  However, using this method, the hash function is no longer narrow-piped. Therefore the result is not surprised. In general, the method is straightforward.
 
My reason is:
 The mode is not a wide-pipe hash,in reality,it has the attribute of narrow-pipe hash.A normal wide-pipe hash must make CV of 2 size big.e.g,if we make SHA512 tobe a wide-pipe hash,there must be 32 variables in stead of 16 variables,the added 16 variables must be uniformity and indistinguishability as the normal 16 variables strictly.So,it'a hard work.But in the new mode,it produce 16 variables just as a normal SHA512,it needn't the hard work of expanding 16 variables to 32 variables which of uniformity and indistinguishability,it only offers additional addend for the normal 16 step functions in each a round.
 The mode is straightforward,this is not the mistake of itself.]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,521,521#msg-521</guid>
      <pubDate>Tue, 26 Jul 2011 03:13:21 -0600</pubDate>
    </item>
    <item>
      <title>2010/625: Reason for revision 4</title>
      <link>http://eprint.iacr.org/forum/read.php?10,429,429#msg-429</link>
      <author>Ben.Smyth</author>
      <description><![CDATA[Version 20110321:170045 (posted 01-Jun-2011 12:17:16 UTC) adds further attacks against electronic voting schemes which do not assure ballot independence; in particular, we consider the protocols by Lee et al., Sako &amp; Kilian and Schoenmakers. In addition, we argue that no general relationships exist between independence and privacy properties.]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,429,429#msg-429</guid>
      <pubDate>Wed, 01 Jun 2011 06:21:03 -0600</pubDate>
    </item>
    <item>
      <title>Re: 2010/251 PUF exaggeration</title>
      <link>http://eprint.iacr.org/forum/read.php?10,247,388#msg-388</link>
      <author>boskom</author>
      <description><![CDATA[luzagodom Wrote:
-------------------------------------------------------
&gt; 2010/251 PUF exaggeration. Posted by: djb (IP
&gt; Logged). Date[url=http://gallstones-gallbladder.blogspot.com]:[/url] 05 May 2010 08:10. The authors of
&gt; 2010/251 are wildly exaggerating the impact of
&gt; their results


I must say that I desagree, but that is my opinion.]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,247,388#msg-388</guid>
      <pubDate>Tue, 17 May 2011 12:29:54 -0600</pubDate>
    </item>
    <item>
      <title>Re: 2010/485</title>
      <link>http://eprint.iacr.org/forum/read.php?10,296,372#msg-372</link>
      <author>Cihangir Tezcan</author>
      <description><![CDATA[This paper uses the ideas from Improbable Differential Cryptanalysis (see 2010/435) and present it as if they are something new. Even though I warned the author about this plagiarism, no proper citations are added. Please remove this so-called paper from eprint.]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,296,372#msg-372</guid>
      <pubDate>Wed, 30 Mar 2011 16:26:17 -0600</pubDate>
    </item>
    <item>
      <title>Re: One Question of  2010/384</title>
      <link>http://eprint.iacr.org/forum/read.php?10,329,371#msg-371</link>
      <author>wai2ha</author>
      <description><![CDATA[We can always only use one surjection round in the last iteration to recovere the domain $X$ by a sum block $ÓM_(L-1)$(assume the message was L- blocks),whenever the previous reductions were great or not.For the last iteration of a narrow-pipe hash function,the active domain $X$ is at least 2^2n ,then it's the case that the ideal random functions W map the
domain of (n+w)-bit strings $X = {0,1}^(n+w )$ to the domain $Y = {0,1}^n$ ,the probability of empty set is about $e^(-2^w)$,where $w&gt;2n-n=n$.
  So,a narrow pipe hash function can easily be amend by a sum block $ÓM_(L-1)$,and the same question in MAC can also be done.I'll  expound  on 2010/652 before toolong.]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,329,371#msg-371</guid>
      <pubDate>Sun, 27 Mar 2011 00:32:07 -0600</pubDate>
    </item>
    <item>
      <title>2010/625: Reason for revision 3</title>
      <link>http://eprint.iacr.org/forum/read.php?10,366,366#msg-366</link>
      <author>Ben.Smyth</author>
      <description><![CDATA[Version 20110321:170045 (posted 21-Mar-2011 17:00:45 UTC) proposes a fix and proves that the solution satisfies a formal definition of ballot secrecy using the applied pi calculus.]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,366,366#msg-366</guid>
      <pubDate>Mon, 21 Mar 2011 11:17:29 -0600</pubDate>
    </item>
    <item>
      <title>Re: One Question of  2010/384</title>
      <link>http://eprint.iacr.org/forum/read.php?10,329,352#msg-352</link>
      <author>wai2ha</author>
      <description><![CDATA[One of the key  questions is that processing the last block with additional bits in a normal iterative hash function,there's the entropy of CV_(L-1)  only n bits,namely a  n-bit domain X  maps to a n-bit codomain Y,the probability of  empty set is approximately
e^(-1).]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,329,352#msg-352</guid>
      <pubDate>Fri, 28 Jan 2011 07:08:14 -0700</pubDate>
    </item>
    <item>
      <title>Re: 2010/652</title>
      <link>http://eprint.iacr.org/forum/read.php?10,342,343#msg-343</link>
      <author>wai2ha</author>
      <description><![CDATA[It's interesting that 2010/430 and 2010/384 said there's a big trouble with narrow-pipe hash functions.]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,342,343#msg-343</guid>
      <pubDate>Tue, 28 Dec 2010 09:58:23 -0700</pubDate>
    </item>
    <item>
      <title>2010/652</title>
      <link>http://eprint.iacr.org/forum/read.php?10,342,342#msg-342</link>
      <author>wai2ha</author>
      <description><![CDATA[Applications of  surjection round try to thwart the conclusion( Of 2010/384 and 2010/430) on narrow-pipe hash functions.]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,342,342#msg-342</guid>
      <pubDate>Fri, 24 Dec 2010 11:00:58 -0700</pubDate>
    </item>
    <item>
      <title>Re: One Question of  2010/384</title>
      <link>http://eprint.iacr.org/forum/read.php?10,329,341#msg-341</link>
      <author>wai2ha</author>
      <description><![CDATA[A new text 2010/652 can thwart the conclusions on narrow-pipe hash functions.]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,329,341#msg-341</guid>
      <pubDate>Fri, 24 Dec 2010 10:49:39 -0700</pubDate>
    </item>
    <item>
      <title>About 2010/646.</title>
      <link>http://eprint.iacr.org/forum/read.php?10,339,339#msg-339</link>
      <author>fpautot</author>
      <description><![CDATA[Same comment as 2010/180: what's the point in violating Total Probability???
HO side-channel cryptanalysis belong to those uncommon parameters estimation problems where the number of (hyper)parameters increases (here linearly) with the sample size.
This is what makes &quot;HO-DPA&quot; particularly interesting, because orthodox methods such as profile maximum likelihood are known to fail (i.e. are inconsistent) in this case (as soon as the number of parameters grows too fast with sample size N (O(sqrt(N)) is already enough if I remember well, here we have O(N))).
Therefore it would be very interesting to compare orthodox estimators such as PMLE to Bayes MAP, as described in 2008/508: again, Extreme Values Theory versus Additive Theory of rvs...
Unfortunalety, it is apparently not yet clear to the authors that we must deal with and marginalize all those masks!
I am unable to understand why everybody in the field is reluctant to derive the subkeys MAP once and for all at least for gaussian attack and non-attack models??? 
F. Pautot]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,339,339#msg-339</guid>
      <pubDate>Wed, 22 Dec 2010 04:54:24 -0700</pubDate>
    </item>
    <item>
      <title>2010/625: Reason for revision 2</title>
      <link>http://eprint.iacr.org/forum/read.php?10,334,334#msg-334</link>
      <author>Ben.Smyth</author>
      <description><![CDATA[Version 20101217:132825 (posted 17-Dec-2010 13:28:25 UTC) adds a further variant of this attack on page 9 and makes a few minor revisions.]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,334,334#msg-334</guid>
      <pubDate>Fri, 17 Dec 2010 06:31:29 -0700</pubDate>
    </item>
    <item>
      <title>2010/625: Reason for revision</title>
      <link>http://eprint.iacr.org/forum/read.php?10,333,333#msg-333</link>
      <author>Ben.Smyth</author>
      <description><![CDATA[Version 20101208:231546 (posted 08-Dec-2010 23:15:46 UTC) of 2010/625 omitted 1.5 sentences of text due to an editing error. We are grateful to Charles Bouillaguet for notifying us of this mistake.]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,333,333#msg-333</guid>
      <pubDate>Mon, 13 Dec 2010 02:13:29 -0700</pubDate>
    </item>
    <item>
      <title>Re: 2010/575 ECDLP exaggeration</title>
      <link>http://eprint.iacr.org/forum/read.php?10,317,332#msg-332</link>
      <author>johnston</author>
      <description><![CDATA[Here we go again.

The problem here is not science.  It's rhetoric.  Here we have  someone who is entirely confined to a premise that certain  problems are difficult (e.g. DLP, CDH, DDH).  This person doesn't like my paper.

So, this guy comes to this forum and starts the slime machine.   When he feels the need to &quot;prove&quot; himself, he writes things like

&quot;Only about x^2/(log(x))^2 of those curves have prime or near prime order.&quot; --djb

This shows that he doesn't know what he is doing. He then waits a few days, realizes he's dead wrong, and comes back with a new distribution problem about elliptic curves defined in a factoring algorithm.  A little off topic, don't you think?

This is not a &quot;pure-mathematics&quot; versus &quot;computer science&quot;  debate.  A security expert needs to get the facts straight.  Making them up and then using them in a security analysis is a bit scary.  It begs for early retirement.

If anything good comes from this thread, it might be to attract attention to these distribution problems.  Some of the most interesting problems in all of mathematics begin here.]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,317,332#msg-332</guid>
      <pubDate>Fri, 03 Dec 2010 07:38:00 -0700</pubDate>
    </item>
    <item>
      <title>Re: 2010/575 ECDLP exaggeration</title>
      <link>http://eprint.iacr.org/forum/read.php?10,317,331#msg-331</link>
      <author>djb</author>
      <description><![CDATA[Here's an illustrative example. An application generates a uniform random integer a_6 modulo a large prime p. What's the chance that the curve y^2=x^3-3x+a_6 is a &quot;maximal&quot; elliptic curve over F_p, i.e., is an elliptic curve with p+1+floor(2 sqrt p) points?

One might naively think that, since the order of an elliptic curve is determined by its isogeny class, one should answer this question by counting isogeny classes. There are about 4 sqrt p isogeny classes of elliptic curves over F_p; exactly one of those classes consists of the &quot;maximal&quot; elliptic curves; so one might guess that the answer is about 1/(4 sqrt p), on the scale of p^(-1/2).

But this guess turns out to be horribly inaccurate. The correct answer is vastly smaller: typically on the scale of p^(-3/4), and sometimes on the scale of p^(-1), depending on p. The underlying source of this error is that y^2=x^3-3x+a_6 is very, very, very far from being uniformly distributed across isogeny classes.

The easiest way to see the correct scale is to apply Deuring's formula (using Kronecker class numbers) for the number of isomorphism classes of elliptic curves having a particular order. The curve y^2=x^3-3x+a_6 isn't uniformly distributed across isomorphism classes, but it's within a small constant factor of being uniformly distributed.

Students interested in learning more about these phenomena should see, e.g., the famous 1987 Annals paper &quot;Factoring integers with elliptic curves&quot; by Hendrik W. Lenstra, Jr. One might think that the success of a curve in ECM at finding a prime p is determined by the number of points on the curve over F_p (this is certainly much closer to being true for ECM than for Weil descent), and that one can therefore simply count isogeny classes. However, the curve in ECM is not even close to being uniformly distributed across isogeny classes, so counting isogeny classes is not answering the right question. That's why Lenstra is careful to count isomorphism classes. (Presumably Johnston will now claim that Lenstra is embarrassing himself.)

Pure mathematicians without algorithmic experience might think that counting isogeny classes is just as natural as counting isomorphism classes. Why do applied mathematicians always seem to pose isomorphism-class questions? Why don't applications such as ECM and ECC generate uniform random isogeny classes? The answer is that generating a uniform or near-uniform isomorphism class is algorithmically much more efficient than generating a uniform random isogeny class.

Anyway, I think this is getting a bit far from the original topic, namely the fact that all ECC standards for the past ten years have excluded the kinds of curves that 2010/575 is targeting. I'm not going to bother following up to whatever additional nonsense Johnston posts at this point. Anyone else who has questions about the inapplicability of 2010/575 is welcome to post those questions here.

---D. J. Bernstein
Research Professor, Computer Science, University of Illinois at Chicago]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,317,331#msg-331</guid>
      <pubDate>Thu, 02 Dec 2010 22:57:49 -0700</pubDate>
    </item>
    <item>
      <title>Re: One Question of  2010/384</title>
      <link>http://eprint.iacr.org/forum/read.php?10,329,330#msg-330</link>
      <author>kyqf</author>
      <description><![CDATA[The writer of 2010/384 gives a conclusion that a narrow-pipe hash function will lose the entropy and the codomain will Reduce.However,the ideal random compression function C  is designated by the writer as non-surjective function,if an ideal random compression functions C can always be a surjective function,are those inferences( on narrow-pipe hash functions ) still real?]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,329,330#msg-330</guid>
      <pubDate>Thu, 02 Dec 2010 07:06:19 -0700</pubDate>
    </item>
    <item>
      <title>One Question of  2010/384</title>
      <link>http://eprint.iacr.org/forum/read.php?10,329,329#msg-329</link>
      <author>kyqf</author>
      <description><![CDATA[If the Ideal random compression functions C is always chosen and kept as a surjective function  namely a onto mapping,what about the conclusion?]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,329,329#msg-329</guid>
      <pubDate>Wed, 01 Dec 2010 10:55:31 -0700</pubDate>
    </item>
    <item>
      <title>Re: 2010/575 ECDLP exaggeration</title>
      <link>http://eprint.iacr.org/forum/read.php?10,317,328#msg-328</link>
      <author>johnston</author>
      <description><![CDATA[We could have done this over email.

&quot;Only about x^2/(log(x))^2 of those curves have prime or near prime order.&quot; --djb

This is wrong, and everything concluded from it is also wrong.  The mistake here is the assumption that isomorphism classes of elliptic curves somehow carry over nicely to the distribution of their orders.  This is not true.  It is not uniform.  Many non-isomorphic elliptic curves have the same order, and the number of isomorphism classes of elliptic curves with the same order varies widely (see the references in my paper about this).  This problem isn't solved by a basic appeal to the prime number theorem. This is such a basic mistake I don't know what else I can write.  This has been studied for over 100 years.

&quot;I'm just saying that the isogeny-class question is asking about a quite different distribution from the distribution actually used in applications.&quot;  --djb

The order of an elliptic curve is its isogeny class.  To find &quot;prime&quot; or &quot;near-prime order&quot; groups, one is necessarily talking about an isogeny problem.  This is embarrassing.

&quot;One might naively think that the _existence_ of fast isogenies (...) implies that ECDL difficulty is an isogeny invariant.&quot; --djb

I'm going to explain this problem for every one.  Two RSA groups do not have to worry about (interesting) homomorphisms between them.  This also isn't a big issue for finite field multiplicative groups.  But for elliptic curves, this is a huge issue.  Two elliptic curves can have &quot;fast&quot; (i.e., efficient) morphisms between them that carry over much of the group structure for DLPs.  The literature on this only defeats the quoted argument.  These maps are extremely important, and it's the first thing one learns about when studying elliptic curves. 

This discussion needs to go to email, Dan.]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,317,328#msg-328</guid>
      <pubDate>Mon, 29 Nov 2010 10:31:21 -0700</pubDate>
    </item>
    <item>
      <title>Re: 2010/575 ECDLP exaggeration</title>
      <link>http://eprint.iacr.org/forum/read.php?10,317,327#msg-327</link>
      <author>djb</author>
      <description><![CDATA[As I said: Choosing a prime power q]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,317,327#msg-327</guid>
      <pubDate>Sun, 28 Nov 2010 22:12:21 -0700</pubDate>
    </item>
    <item>
      <title>Re: 2010/575 ECDLP exaggeration</title>
      <link>http://eprint.iacr.org/forum/read.php?10,317,326#msg-326</link>
      <author>johnston</author>
      <description><![CDATA[Dan, do you really think the issue here is about &quot;isomorphisms&quot; of elliptic curves?  A first year student knows this isn't the case.  Isomorphism needs to be isogeny.  Do you understand elliptic curve theory at all?  I don't want to hurt you with this, I just want the debate to be fair.  We could discuss this over email if you want.  I want to help you.  However, you can't take the wrong distribution and attack me with it on a public forum.  This just isn't the right thing to do.

This misconception has cost us hours. It's time to stop.  I have already emailed you, so you know how to contact me.  I can even stop by in Eindhoven and we can talk. We can then come back and post what we find.]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,317,326#msg-326</guid>
      <pubDate>Sun, 28 Nov 2010 06:15:25 -0700</pubDate>
    </item>
    <item>
      <title>Re: 2010/575 ECDLP exaggeration</title>
      <link>http://eprint.iacr.org/forum/read.php?10,317,325#msg-325</link>
      <author>djb</author>
      <description><![CDATA[No, there was never any regression in IEEE P1363 on this issue. In particular, the prime-or-power-of-2 requirement was never dropped from the IEEE P1363 curve-generation and curve-verification algorithms.

The alleged confusion in standards is nothing more than Johnston misrepresenting general elliptic-curve discussions as elliptic-curve-suitable-for-ECC discussions. Johnston persists in saying, e.g., that P1363 &quot;has ECC over extensions of prime fields&quot; in it, and trying to mislead the reader into believing that P1363 blindly allows all elliptic curves over extensions of prime fields; in fact, P1363 does _not_ allow most such extensions, and does _not_ allow most curves over such extensions.

Imagine someone misled by Johnston into believing that the ECC standards tolerate generating a uniform random (q,E) with q an arbitrary prime power between, say, 2^255 and 2^256, and E an arbitrary elliptic curve over F_q (up to isomorphism). This E will be quite likely to be broken by Pohlig-Hellman, and would have to be astonishingly unlucky to be broken by 2010/575 or any other Weil-descent attack. There are, asymptotically, about x^2/log x choices of E with q]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,317,325#msg-325</guid>
      <pubDate>Sat, 27 Nov 2010 08:57:44 -0700</pubDate>
    </item>
    <item>
      <title>Re: 2010/575 ECDLP exaggeration</title>
      <link>http://eprint.iacr.org/forum/read.php?10,317,324#msg-324</link>
      <author>johnston</author>
      <description><![CDATA[So, let's recap.  We've dropped the &quot;wild exaggerations&quot; complaint about the title.  We've accepted the fact that these curves occur in your work.  And we've dropped the complaint that my work might not be new (by the way, good work; I'm glad you read the paper you blindly cited).

Now we are back once again to the standards complaint.  I can make your life much easier.  If you want to prevent the elliptic curves in my attack from occurring, just make sure they are of odd order.  All of my curves have extra 2-torsion in them.  I need this in my double descent.  This would be simple enough.  In later work, we might get rid of this.  But you haven't really focused on my curves.  You have this need to diminish my work, and I don't really understand why.  And if we start cutting out curves from standards to &quot;prevent attacks,&quot; shouldn't we understand why?  All of ECC is based on assumptions about security, not proofs.

Why do you think Curve[insert number] is secure?  It's easy: you have assumed things.  It's a DLP assumption (and CDH, and DDH, and so on).  The one who makes the assumptions always has the burden of proof.  Papers like mine look at the mathematics behind these assumptions.  We find cases where these assumptions might not be ideal.  Why is this not &quot;main stream?&quot;  Does someone need to break every elliptic curve before an attack is &quot;main stream?&quot;  Let's hope it doesn't happen like that.  Remember, I am only offering a few new techniques.  I'm sure more will come.  Isn't it better this way?  This is all made perfectly clear in my introduction.

(And finally, about IEEE P1363, you cite the one in 1999, but a year later, there is a 4th draft that has ECC over extensions of prime fields in it.  You are not telling the truth when you act as if there is no confusion on this topic in the standards in the last ten years.  Let's not unleash the beast here.)]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,317,324#msg-324</guid>
      <pubDate>Sat, 27 Nov 2010 04:43:40 -0700</pubDate>
    </item>
    <item>
      <title>Re: 2010/575 ECDLP exaggeration</title>
      <link>http://eprint.iacr.org/forum/read.php?10,317,323#msg-323</link>
      <author>djb</author>
      <description><![CDATA[I've checked a 1999 draft of IEEE P1363. The &quot;algorithm for generating EC parameters&quot; (A.16.7) requires the field size q to be &quot;an odd prime p or 2^m.&quot; The &quot;algorithm for validating EC parameters&quot; has the same requirement.

I've also checked Certicom's SEC 1. It starts by imposing the same requirement, allowing only q=p or q=2^m. It then says that &quot;composite m was avoided to align this specification with other standards efforts and to address concerns expressed by some experts about the security of elliptic curves defined over F_{2^m} with m composite - see, for example, [32].&quot; The citation is to Galbraith-Smart, one of the first Weil-descent papers.

I've also checked FIPS PUB 186-3. Appendix D, &quot;Recommended elliptic curves for federal government use,&quot; specifies the NIST curves and states that they were &quot;generated using SHA-1 and the method given in the ANS X9.62 and IEEE Standard 1363-2000 standards.&quot; The only allowed field sizes are certain primes p and certain powers 2^p.

I've also checked Certicom's SEC 2, which specifies the NIST curves and various additional curves. The only allowed field sizes are certain primes p and certain powers 2^p.

I've also checked RFC 5480, &quot;Elliptic Curve Cryptography Subject Public Key Information.&quot; This specification requires the SEC curves, and prohibits use of a historical syntax that allowed arbitrary primes p and arbitrary powers 2^m. Even the historical syntax didn't allow powers of odd primes.

There are also specifications and deployments of Curve25519. The original Curve25519 paper selects a prime field for performance reasons, but also mentions (citing two Weil-descent papers) that prime fields have &quot;the virtue of minimizing the number of security concerns for elliptic curve cryptography,&quot; and in its Curve25519 security analysis briefly discusses the non-impact of Weil descent.

Over the years one can see evolution in the security requirements for ECC: for example, Curve25519 explicitly adds a twist-security requirement that most of the NIST/SEC curves don't meet. But adding a requirement of security against 2010/575 would be completely and utterly redundant. Out of of the curves allowed by the previous standards, there are _zero_ curves that can, even theoretically, be subject to the attack in 2010/575.

The paper is simply wrong when it claims that its example curve has &quot;no special features that would rule it out as undesirable from a cryptographic point of view.&quot; I've now cited five ECC standards that severely restrict the field size, ruling out this curve (and many more); in at least one of these standards the restriction is very clearly labelled as addressing potential security concerns.

Johnston continues (1) pointing to slides that discuss broad classes of elliptic curves and (2) misrepresenting those slides as absurd claims that all elliptic curves, including the rare curves targeted by 2010/575, are suitable for ECC. I really don't think that real-world ECC users have to worry that their curves are being selected by such confused people.

---D. J. Bernstein
Research Professor, Computer Science, University of Illinois at Chicago]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,317,323#msg-323</guid>
      <pubDate>Fri, 26 Nov 2010 22:00:03 -0700</pubDate>
    </item>
    <item>
      <title>Re: 2010/575 ECDLP exaggeration</title>
      <link>http://eprint.iacr.org/forum/read.php?10,317,322#msg-322</link>
      <author>johnston</author>
      <description><![CDATA[So, you drop the &quot;title&quot; debate.  We are making progress!  Let's try for some more.  Let's also work on formatting so that as you abandon certain issues and try to bring up new ones, I can keep a clear track of what still needs to be refuted.

1.  If you understood the research in this area, then you would know that (http://homes.esat.kuleuven.be/~jscholte/weilres.pdf) is dealt with by Satoh's Eurocrypt 2009 paper, which I discuss in my work.  To be specific, the author of the work you cite does not bring up discrete logarithms beyond the introduction.  It   isn't relevant here.  Going from elliptic curves to genus 2 curves is not enough.  One must do much more.  The author hints   in the introduction that DLP work might be possible in extensions of his work, but he never returns to this topic at all throughout the rest of his paper.  He never followed it up with other papers either.  It's a difficult topic, so we shouldn't blame him for this.  We also shouldn't see things that are not there.  He isn't doing what I'm doing at all.  And seriously, you should read what you cite before you wave it around.

2.  The weak curves I attack most definitely show up in your ECC work.  You define Edward's curves over any finite field in odd characteristic.  This contains the class of weak elliptic curves discussed in my paper.  The deep theory here goes like this: when one non-empty set is a subset of a second set, then the second set contains objects from the first set. Difficult?  If you want to talk about distributions, you might want to actually look at my text first.  My curves are not   &quot;rare,&quot; they grow at least in size q/2.  And this is a crude lower bound -- it's likely to be much more when the isogenies are factored in.

3. The IEEE P1363 proposals have even been updated recently.  Up until the 2006 drafts, there were still unrestricted   extension fields for elliptic curves in the documents.  Since you know all of the standards about absolutely every aspect of   ECC in the last ten years (minus the things I find), perhaps you can do the research and tell me what the current state of   IEEE P1363 is.  I don't have the password for the latest documents.  I guess I could get it, but it's more fun if you do it.  Then I can look for other standards for our next round.  But seriously, &quot;every&quot; standard?  Are you kidding?  Half of the theory community doesn't understand this topic, much less the engineers.  The irony here is that over at (http://www.ellipticsemi.com/pdf/presentations/EC_overGF_in_cryptography.pdf) your name comes up with a proposal for ECC over arbitrary finite fields in odd characteristic (page 8, and then on to page 15).  It's very clear the industry is confused on this point.  Keep at this one, though.  Soon we'll find a nice list of companies to help.]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,317,322#msg-322</guid>
      <pubDate>Fri, 26 Nov 2010 15:29:12 -0700</pubDate>
    </item>
    <item>
      <title>Re: 2010/575 ECDLP exaggeration</title>
      <link>http://eprint.iacr.org/forum/read.php?10,317,321#msg-321</link>
      <author>djb</author>
      <description><![CDATA[No, these curves don't show up in my ECC work. The talk that Johnston cited recommends precisely one elliptic curve for cryptography, namely Curve25519, and of course Curve25519 (like all of the NIST curves) is invulnerable to any attack of this type.

The idea that somebody is going to take a general definition of elliptic curves, misunderstand it as a definition of elliptic curves suitable for ECC, generate his own bad curve, implement his bad curve, manage to convince users to adopt that curve without anybody ever checking any discussions of ECC security from any standards or surveys in the last ten years, be so lucky as to avoid the typical curves vulnerable to other attacks, and be so astonishingly unlucky as to end up with one of the special curves vulnerable to Weil descent, is too absurd to warrant further discussion.

Johnston's repeated pointers to an IEEE P1363 draft are also missing any mention of how ancient that draft is. There were a few proposals in the 1990s of curves over fields such as F_{2^155} and F_{(2^61-1)^3}, but Frey's famous talk on Weil descent in 1998 (http://www.cacr.math.uwaterloo.ca/conferences/1998/ecc98/frey.ps), followed by a series of papers showing that Weil descent works for at least occasional curves, quickly killed interest in those proposals.

As for &quot;the entire area of research&quot;: Continued exploration of the exact boundaries of Weil descent is respectable work in computational number theory (if it's new; I'm privately told that Johnston should compare his paper to the 2003 paper http://homes.esat.kuleuven.be/~jscholte/weilres.pdf), and I've already outlined a way that it might help produce better cryptosystems someday, but it is not even marginally threatening to modern elliptic-curve cryptography.

---D. J. Bernstein
Research Professor, Computer Science, University of Illinois at Chicago]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,317,321#msg-321</guid>
      <pubDate>Fri, 26 Nov 2010 11:30:32 -0700</pubDate>
    </item>
    <item>
      <title>Re: 2010/575 ECDLP exaggeration</title>
      <link>http://eprint.iacr.org/forum/read.php?10,317,320#msg-320</link>
      <author>johnston</author>
      <description><![CDATA[As to the reference to your own work where these curves show up, I disagree with you that someone would be inspired to fix the problem with a magic internet search inspired by the words &quot;et al.&quot;  This is just not serious.  A simple google search finds all kinds of &quot;standards&quot; without any restriction on the base field, much like the one I cited last time.  I hope they are not in wide use, but they certainly indicate some confusion on this topic.

But now you have decided to attack my title.  You are certainly aware of &quot;Reducing elliptic curve logarithms to logarithms in a finite field&quot; by Menezes, Okamoto, and Vanstone (STOC 91).   This was about an extremely small class of elliptic curves, which does not at all diminish the importance of the result.  Would you call this a &quot;wild exaggeration&quot; as well?   The authors certainly did not mean this title applied to every elliptic curve.  If it did, there would be no need for most of ECC.  And this is just one example!  We could go on all day writing about titles that might be &quot;wild exaggerations&quot; if we apply your logic.

My work is not even about Weil descent.  It bypasses Weil descent and constructs another group.  This is made very clear in the paper.  Unfortunately, my paper is not really the issue here.  You simply attack the entire area of research.]]></description>
      <category>2010 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?10,317,320#msg-320</guid>
      <pubDate>Thu, 25 Nov 2010 05:27:40 -0700</pubDate>
    </item>
  </channel>
</rss>
