-
@ waxwing
2025-06-17 18:30:44
This paper from CRYPTO 2025 ( https://eprint.iacr.org/2024/1528 ) appears that it might be a major step forward in security analysis of Schnorr signatures. They argue that while you can't get a tight reduction from Schnorr to discrete log in the ROM, as has been proved by Seurin et al in 2012, you *can* get a tight reduction to what they call "CDL" ("circular discrete log") where the challenge is, instead of, given Y in the group, find y s.t. y*G = Y, you have to find (R, z) s.t. z*G = R + f(R)Y where f is some function. So what they're doing is matching more closely to Schnorr's actual structure. If CDL is as hard as DL, then this makes Schnorr's security reduction to DL actually tight (so that, for example, using 256 bit EC groups as we do in Bitcoin, *does* give 128 bit security directly from these proofs, which was not the case before).
But to counteract the argument of Seurin's earlier paper, the reason this CDL approach sidesteps it is because CDL is "representation dependent", specifically because the value f(R) depends on the representation of the group element R.
Reducing CDL to DL is something they analyze both in the GGM and a variant of the AGM. Don't understand the details.
Obviously this is way above my paygrade to assess, especially just from a skim read, but it *looks* like a pretty significant result than can put Schnorr-based signing algos on a firmer footing. They specifically analyze the case of Sparkle+ which is a recent improvement of the basic FROST threshold signing scheme, and they argue that this approach proves tight security reduction of Sparkle+ to (ec) discrete log. Very interesting.
#cryptography