2020.07.14 09:39:37 (1282942814767083520) from Daniel J. Bernstein, replying to "Madars Virza 🛡 (@MadarsV)" (1282443601570562055):
There are many choices of "half-gcd" algorithms, including many 2-dim lattice-basis-reduction algorithms, but some care is required: almost all of the algorithms in the literature will leak secrets through timing. There are several solutions; easiest: compute s from random r, t.
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.13 00:35:55 (1282443601570562055) from "Madars Virza 🛡 (@MadarsV)":
Nice! And presumably one would use a lattice reduction algorithm like https://eprint.iacr.org/2020/454 to find such r, t pairs?