2020.07.12 17:06:28 (1282330493355261952) from Daniel J. Bernstein, replying to "shlomtz(.eth) (@OmerShlomovits)" (1282315264508547074):
A little bit of compression is possible here too: the server broadcasting pairs (u,v) can arbitrarily scale the pairs, and can spend a little time searching for scales where v has some 0 bits that can be skipped. But there's a more interesting tradeoff in the other direction...
2020.07.12 17:12:24 (1282331983729668096) from Daniel J. Bernstein:
The server can send along u; v; u^2^56; v^2^56. Double traffic, but now computing u^r v^t with 112-bit r and 112-bit t costs only 56 squarings (1/4 of the original), maybe 3x speedup when mults (or curve adds/subs) are included. For many more options: https://cr.yp.to/papers.html#pippenger
2020.07.12 17:21:52 (1282334366446743552) from Daniel J. Bernstein:
At a lower level, the paper specifies P-224 (for BLE constraints) but tries to extrapolate from wolfSSL P-256 time (for keygen, which can be misleading). Since there are many (u,v) it should be better to work with affine coordinates and use Montgomery's batch-inversion trick.
2020.07.12 17:35:30 (1282337800268861440) from Daniel J. Bernstein:
There's surely also a speedup from using a better prime. https://cr.yp.to/talks.html#2001.10.29 suggested the curve y^2 = x^3+7530x^2+x mod 2^226-5, with keys squeezed into 224 bits (this takes negligible extra keygen time). Also wondering if 25519 could squeeze into extra BLE metadata bits.
2020.07.12 15:08:40 (1282300847607578625) from Daniel J. Bernstein:
The new CleverParrot exposure-notification protocol in https://eprint.iacr.org/2020/863 says your phone will spend 12 minutes per day checking, for your secret s, for many pairs u,v, whether u^s = v. Here's a nearly 2x speedup: check whether u^r v^t = 1 for half-size r,t with s = -r/t.
2020.07.12 16:05:57 (1282315264508547074) from "shlomtz(.eth) (@OmerShlomovits)":
reminds me of @EllipticKiwi observation in https://eprint.iacr.org/2020/196.pdf section 5, that enables to compress a group element in a class group, inspired by Bleichenbacher algorithm to compress Rabin signatures (cc: @claudiorlandi )