Re: [Cfrg] Requesting removal of CFRG co-chair

["Dan Harkins" <[e-mail]>]

  Trevor,

On Fri, December 27, 2013 7:56 am, Trevor Perrin wrote:
> I'm still not sure what you're asking.  Let's just look at a crude
> analysis of the "40-loops" countermeasure Kevin endorsed, comparing
> CFRG draft-00 vs draft-01/draft-02.
>
> Let's assume that modular square roots are calculated via modular
> exponentiation, and that Legendre symbol calculations take less time.
> Let's also ignore the variable time taken by a Legendre symbol
> calculation and other conditional logic, and just count the number of
> ops.
>
> In draft-00, the hunt-and-peck loop in 3.2.1 performs Legendre symbol
> calculations until it finds a square (probability ~1/2), at which
> point a square root is performed.  So:
>  - 1 modular exponentiation
>  - Variable number of Legendre symbol calculations
>    - geometric distribution with mean ~2, variance ~2
>
> In draft-01 and draft-02, the hunt-and-peck loop continues until it
> completes 40 loops, with a probability ~1/2 of performing a modular
> exponentiation on each iteration.  So:
>  - Variable number of modular exponentiations
>    - binomial distribution with mean ~20, variance ~10
>  - 40 Legendre symbol calculations
>
> The 40-loops algorithm was intended to reduce timing variance but
> instead increases it, and increases computation cost as well.  So I
> think "ineffective" is a fair description.  Do you agree?

  That is a good description of a problem. I now see how poor the
text is that describes the hunting-and-pecking loop. I wish you
would have put it in the form of a constructive comment, or at least
separated this signal from the general noise of your posts. But
nevertheless, I see that that section is poorly worded, I understand
your comment, and will address it in a subsequent version of the
draft.

  A sincere thank you for this comment!

  Dan.