Re: [bitcoindev] Re: DahLIAS: Discrete Logarithm-Based Interactive Aggregate Signatures

[waxwing/ AdamISZ <ekaggata@gmail.com>]

[-- Attachment #1.1: Type: text/plain, Size: 8626 bytes --]

On the very important argument laid out in Appendix B:

(for readers, this part of the paper deals with this problem: if the scheme 
can allow a scenario where the output "effective nonce" of an honest signer 
is the same for two different contexts and thus have two difference 
signature hashes (in DahLIAS the sighash is H(L, R, X_i, m_i)), then with 
some deft mathematical footwork, we can extract a forgery on some other 
message by that signer, as long as we can do a bunch of parallel signing 
sessions; you can think of this as a sophisticated extension of the 
fundamental idea of "nonce reuse is insecure").

... I find myself stepping back through the arguments for this structure R1 
+ bR2 in MuSig2. In that case, it is vital that we end with a verification 
that looks like : sG =?= R + H(R,P,m)P, precisely, because we need MuSig2 
verification to be indistinguishable from single-key Schnorr verification.

In DahLIAS we have (obviously, reasonably) relaxed that restriction. The 
verification now allows for multiple pubkeys and messages to be inputs; 
that's the whole point, we're publically verifying authorization of a bunch 
of (pubkey, message) pairs, so it would be incoherent or at least 
unnecessary to *require* some kind of aggregate pubkey as input. (though as 
the paper discussed, you can *try* to build the IAS from an IMS, which 
would mean actually doing that, but as demonstrated, it doesn't really seem 
to work, anyway).

So when we look at the R component, which, distinct from the pubkeys, *must 
actually be published*, we do need to have an aggregated R value (to get a 
short signature), so at the end, we publish (R, s) and can do a 
verification with the implied pubkey message pairs ((P1, m1), (P2, m2),..) 
like: sG =?= R + sigma (sighash(Pn,mn) * Pn).

So here's my question: why does the signing context, represented by "b", in 
the aggregate R-value, need to be a fixed value across signing indices? 
Clearly if we have one b-value, H-non(ctx), where ctx is ((P1, m1), (P2, 
m2),..) [1], then it is easy to sum all the R1,i = R1 and then sum all the 
R2,i values = R2 and then R = R1 + bR2, exploiting the linearity. But why 
do we have to? If coefficient b were different per participant, i.e. b_i = 
H(ctx, m_i, P_i) then it makes that sum "harder" but still trivial for all 
participants to create/calculate. All participants can still agree on the 
correct aggregate "R" before making their second stage output s_i.

If I am right that that is possible, then the gain is clear (I claim!): the 
attacks previously described, involving "attacker uses same key with 
different message" fail. The first thing I'd note is that the basic 
thwarting of ROS/Wagner style attacks still exists, because the b_i values 
still include the whole context, meaning grinding your nonce doesn't allow 
you to control the victim's effective nonce. But because in this case, you 
cannot create scenarios like in Appendix B, i.e. in the notation there:
F(X1, m1(0), out1, ctx) = F(X1, m1(1), out1, ctx) is no longer true because 
b no longer only depends on global ctx, but also on m1 (b_1 = Hnon(ctx, m1, 
P1) is my proposal),

then the "Property 3" does not apply and so (maybe? I haven't thought it 
through properly) the duplication checks as currently described, would not 
be needed.

I feel like this alternate version is more intuitive: I see it as analogous 
to (though not the same) as Fiat-Shamir hashing, where the main idea is to 
fix the actual context of the proof; but the context of *my* partial 
signature for this aggregate, is not only ((P1, m1), (P2, m2),..) but also 
my particular entry in that list.

[1] Here I am ignoring that actual DahLIAS uses ctx including R2 values 
because I understand that that is part of the checking procedure that I am 
(somewhat vaguely) here trying to argue might be omitted.

Cheers,
AdamISZ/waxwing



On Thursday, May 1, 2025 at 12:14:30 AM UTC-3 waxwing/ AdamISZ wrote:

>
> > That partial signatures do not leak information about the secret key x_k 
> is 
> implied by the security theorem for DahLIAS: If information would leak, 
> the 
> adversary could use that to win the unforgeability game. However, the 
> adversary 
> doesn't win the game unless the adversary solves the DL problem or finds a 
> collision in hash function Hnon.
>
> OK, so that's maybe a theoretical confusion on my part, I'm thinking of 
> the HVZK property of the Schnorr ID scheme, which "kinda" carries over into 
> the FS transformed version with a simulator (maybe? kinda?). Anyway this is 
> a sidetrack and not relevant to the paper, so I'll stop on that.
>
> > This is a very interesting point, probably out of scope for the paper. A 
> single-party signer, given secret keys xi, ..., xn for public keys X1, 
> ..., Xn 
> can draw r at random, compute R := r*G and then set s := r + c1*x1 + ... + 
> cn*xn. So this would only require a single group multiplication.
>
> I feel bad for saying so, but I absolutely do believe it's in scope of the 
> paper :) If there is a concrete, meaningful optimisation that's both 
> possible and sensible (and as you say, there is such an ultra-simple 
> optimisation ... I guess that's entirely correct!), then it should be 
> included there and not elsewhere. Why? Because it's exactly the kind of 
> thing an engineer might want to do, but it's definitely not their place to 
> make a judgement as to whether it's safe or not, given that these protocols 
> are such a minefield. I'd say even if there is *no* such optimisation 
> possible it's worth saying so.
>
> I guess the counterargument is that it's suitable for a BIP not the paper? 
> But I'd disagree, this isn't purely a bitcoin thing.
>
> On the third paragraph, yeah, as per earlier email, I realised that that 
> just doesn't work.
>
> On Wednesday, April 30, 2025 at 9:03:34 AM UTC-6 Jonas Nick wrote:
>
>> Thanks for your comments. 
>>
>> > That side note reminds me of my first question: would it not be 
>> appropriate 
>> > to include a proof of the zero knowledgeness property of the scheme, 
>> and 
>> > not only the soundness? I can kind of accept the answer "it's trivial" 
>> > based on the structure of the partial sig components (s_k = r_k1 + 
>> br_k2 + 
>> > c_k x_k) being "identical" to baseline Schnorr? 
>>
>> That partial signatures do not leak information about the secret key x_k 
>> is 
>> implied by the security theorem for DahLIAS: If information would leak, 
>> the 
>> adversary could use that to win the unforgeability game. However, the 
>> adversary 
>> doesn't win the game unless the adversary solves the DL problem or finds 
>> a 
>> collision in hash function Hnon. 
>>
>> > The side note also raises this point: would it be a good idea to 
>> explicitly 
>> > write down ways in which the usage of the scheme/structure can, and 
>> cannot, 
>> > be optimised for the single-party case? 
>>
>> This is a very interesting point, probably out of scope for the paper. A 
>> single-party signer, given secret keys xi, ..., xn for public keys X1, 
>> ..., Xn 
>> can draw r at random, compute R := r*G and then set s := r + c1*x1 + ... 
>> + 
>> cn*xn. So this would only require a single group multiplication. 
>>
>> > On that last point about "proof of knowledge of R", I suddenly realised 
>> > it's not a viable suggestion: of course it defends against key 
>> subtraction 
>> > attacks, but does not defend at all against the ability to grind nonces 
>> > adversarially in a Wagner type attack 
>>
>> We believe Appendix B provides a helpful characterization of 
>> "Wagner-style" 
>> vulnerabilities. Roughly speaking, it shows that schemes where the 
>> adversary can 
>> ask the signer to produce a partial signature s = r + c*x or s' = r + 
>> c'*x such 
>> that c != c' then the scheme is vulnerable. In your "proof of knowledge 
>> of R 
>> idea", the adversary can choose to provide either R2 or R2' in a signing 
>> request, which would result in the same "effective nonce" r being used be 
>> the 
>> signer but different challenges c and c'. 
>>
>

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/3f23ebaa-02c7-45d1-bf57-9baf48c133a3n%40googlegroups.com.

[-- Attachment #1.2: Type: text/html, Size: 9680 bytes --]