Bird of Prey 2: non-malleable Schnorr + PQ signatures

Thanks for flagging that.

Seems like a pretty important paper.

The way I’m getting the gist here is: ‘default’ stuff out there, in industry, and NIST and whatnot, is doing hybrid by concat. And this makes sense when you care about EUF and not SUF. But some things require SUF and Bitcoin is one of them.

So “nesting” exists, but it’s hard to get it to have the properties you want: if you just sign one scheme with the other, you don’t get SUF from the fact that the outer scheme is SUF. (To concretize: we’re imagining: outer scheme is bip340 and inner scheme is something PQ).

In the paper they try to argue (probably right, I have no idea) that this problem can’t really be avoided if you just treat the two sig schemes as black-box.

So the trick (in BOP-2 which is one of three different constructions here) is to not treat Schnorr as black-box. They treat it as an ID scheme (which it is) and make the challenge in such a way that the SUF property is inherited, even if the PQ scheme doesn’t have it.

Do I have that roughly right?

About batch-verify, a couple of questions:

How crucial is batch verification, today, in Bitcoin?

For your point that it might just be not possible in the PQ regime: what about isogenies, I wonder. I guess hash-based is a non-starter, and lattices .. well there’s some linearity there right? But from what I’m reading, no dice. And isogenies even if sound might not be performant enough for this stuff. Shrug, no idea :slight_smile:

About including R or not: I think if I’m reading this right, we’re publishing \sigma_{sch} and \sigma_{pq} so since the latter is the dominant element, does it matter?

1 Like