js bindings - aggregated public keys not working with multiple messages

[rickyk586]

is it possible to use aggregated public keys with aggregated signatures on multiple messages? This gives a false verification:

import loadBls from 'bls-signatures';

const BLS = await loadBls();

var seed = Uint8Array.from([
    0,  50, 6,  244, 24,  199, 1,  25,  52,  88,  192,
    19, 18, 12, 89,  6,   220, 18, 102, 58,  209, 82,
    12, 62, 89, 110, 182, 9,   44, 20,  254, 22
]);

// Generate some more private keys
seed[0] = 1;
var sk1 = BLS.AugSchemeMPL.key_gen(seed);
seed[0] = 2;
var sk2 = BLS.AugSchemeMPL.key_gen(seed);
seed[0] = 3;
var sk3 = BLS.AugSchemeMPL.key_gen(seed);
seed[0] = 4;
var sk4 = BLS.AugSchemeMPL.key_gen(seed);
var message = Uint8Array.from([1,2,3,4,5,6,7]);
var message2 = Uint8Array.from([1,2,3,4,5,6,8]);

// Generate first sig
var pk1 = sk1.get_g1();
var sig1 = BLS.AugSchemeMPL.sign(sk1, message);

// Generate second sig
var pk2 = sk2.get_g1();
var sig2 = BLS.AugSchemeMPL.sign(sk2, message);

// Generate third sig
var pk3 = sk3.get_g1();
var sig3 = BLS.AugSchemeMPL.sign(sk3, message2);

// Generate forth sig
var pk4 = sk4.get_g1();
var sig4 = BLS.AugSchemeMPL.sign(sk4, message2);

// Generate aggregated public keys
var aggPk1 = pk1.add(pk2);
var aggPk2 = pk3.add(pk4);

// Signatures can be non-interactively combined by anyone
var aggSig = BLS.AugSchemeMPL.aggregate([sig1, sig2, sig3, sig4]);

const ok = BLS.AugSchemeMPL.aggregate_verify([aggPk1, aggPk2], [message, message2], aggSig);
console.log(ok); // false

or is this the only way to do it:

const ok2 = BLS.AugSchemeMPL.aggregate_verify([pk1, pk2, pk3, pk4], [message, message, message2, message2], aggSig);
console.log(ok2); // true

[rickyk586]

I believe this answers my question that it cannot be done with aggregate public keys when there are multiple messages:

In the context of BLS12-381 and the BLS signature scheme, verifying an aggregated signature over different messages requires access to all the original public keys and messages involved in the aggregation. Here's why:

BLS Signature Aggregation Basics:

1. Same Message Aggregation:

   • When multiple signers sign the same message, their signatures can be aggregated by simply adding them together:
     [ s_{\text{agg}} = s_1 + s_2 + \dots + s_n ]
   • Their public keys can also be aggregated similarly:
     [ \text{pk}_{\text{agg}} = \text{pk}_1 + \text{pk}_2 + \dots + \text{pk}_n ]
   • Verification can then proceed using the aggregated signature and public key: [ e(s{\text{agg}}, G) = e(H(m), \text{pk}{\text{agg}}) ]

2. Different Messages Aggregation:

   • When aggregating signatures over different messages, the process is more complex due to the potential for rogue-key attacks.
   • The aggregated signature is still the sum of individual signatures: [ s_{\text{agg}} = s_1 + s_2 + \dots + s_n ]
   • However, verification requires pairing each hashed message with its corresponding public key: [ e(s{\text{agg}}, G) = \prod{i=1}^{n} e(H(m_i), \text{pk}_i) ]
   • This equation necessitates knowledge of each individual public key and message.

Implications for Your Scenario:

• Given:
  • Aggregated public keys: (\text{aggpk1} = \text{pk1} + \text{pk2}), (\text{aggpk2} = \text{pk3} + \text{pk4})
  • Messages: (m1) and (m2)
• Verification Challenge:
  • You cannot directly verify the aggregated signature over different messages using only the aggregated public keys (\text{aggpk1}) and (\text{aggpk2}).
  • The verification equation for different messages requires each original public key and its corresponding message.
• Conclusion:
  • You must have access to all the original public keys ((\text{pk1}, \text{pk2}, \text{pk3}, \text{pk4})) and their corresponding messages ((m1) for (\text{pk1}) and (\text{pk2}), (m2) for (\text{pk3}) and (\text{pk4})) to verify the aggregated signature.

Why Aggregated Public Keys Alone Are Insufficient:

• Loss of Individual Pairings:
  • Aggregating public keys over different messages causes a loss of the one-to-one relationship between each (H(m_i)) and (\text{pk}_i).
• Verification Equation Dependency:
  • The verification equation for aggregated signatures over different messages depends on each individual pairing (e(H(m_i), \text{pk}_i)).
• Security Considerations:
  • Bypassing individual public keys can introduce vulnerabilities, such as rogue-key attacks, compromising the security of the verification process.

Recommendation:

• Use all the original public keys and messages to perform the verification.
• Ensure that each public key is correctly associated with its corresponding message during verification.

References:

• Boneh, Dan, et al. "Short signatures from the Weil pairing." Journal of Cryptology 17.4 (2004): 297-319.
• BLS Signature Scheme Documentation and Standards.

Answer:

You need to use all the original public keys and messages to verify the aggregated signature—you cannot verify it using only their aggregated public keys.