DsaTest#testTiming bits bias

[Antonio Sanso]

hi *,

I'd have a question about  DsaTest#testTiming .

The test looks pretty interesting and I understand it well.

The underlying lattice's attack is well explained in [0].

I'd have a question though about a snippet in the comment.

   * <p><b>Sample output for the SUN provider:</b> <code>

   * count:50000 cutoff:4629300 relative average:0.9992225872624547 sigmas:0.3010906585642381

   * count:25000 cutoff:733961 relative average:0.976146066585879 sigmas:6.532668708070148

   * count:12500 cutoff:688305 relative average:0.9070352192339134 sigmas:18.00255238454385

   * count:6251 cutoff:673971 relative average:0.7747148791368986 sigmas:30.850903417893825

   * count:3125 cutoff:667045 relative average:0.5901994097874541 sigmas:39.67877152897901

   * count:1563 cutoff:662088 relative average:0.4060286694971057 sigmas:40.67294313795137

   * count:782 cutoff:657921 relative average:0.2577955312387898 sigmas:35.94906247333319

   * count:391 cutoff:653608 relative average:0.1453438859272699 sigmas:29.271192100879457

   * count:196 cutoff:649280 relative average:0.08035497211567771 sigmas:22.300206785132406

   * count:98 cutoff:645122 relative average:0.05063589092661368 sigmas:16.27820353139225

   * count:49 cutoff:641582 relative average:0.018255560447883384 sigmas:11.903018745467488

   * count:25 cutoff:638235 relative average:0.009082660721102722 sigmas:8.581595888660086

   * count:13 cutoff:633975 relative average:0.0067892346039088326 sigmas:6.20259924188633

   * </code>

   *

   * <p><b>What this shows:</b> The first line uses all 50'000 signatures. The average k of these

   * signatures is close to the expected value q/2. Being more selective gives us signatures with a

   * more biased k. For example, the 196 signatures with the fastest timing have about a 3-bit bias.

My question is, the is clear that the 196 signature have a bias. I was wondering where the number 3-bit comes from.

Is there any direct formula that correlates sigmas to the number of bit-bias?

Thanks a lot and regards

antonio 

[0] http://www.hpl.hp.com/techreports/1999/HPL-1999-90.pdf