cfrg/draft-irtf-cfrg-bls-signature

Question: is point at infinity signature valid for `Aggregate` inputs?

hwwhww opened this issue · 7 comments

hwwhww commented

Thanks to @kwantam for the previous response in #27! While we are creating more edge cases test vectors, we want to get confirmation from the standard writers if the point at infinity signature (0xc0....00) is valid for Aggregate inputs or not, especially for the proof of possession scheme.

In https://tools.ietf.org/html/draft-irtf-cfrg-bls-signature-04#section-2.8, Aggregate's signatures input is defined as

   Inputs:
   - signature_1, ..., signature_n, octet strings output by
     either CoreSign or Aggregate.

   Outputs:
   - signature, an octet string encoding a aggregated signature
     that combines all inputs; or INVALID.

   Precondition: n >= 1, otherwise return INVALID.
  1. It's kind of a deadlock to define a function's input as the same function's output. If we keep Aggregate in either CoreSign or Aggregate, I read it as any octet strings are VALID, so the point at infinity signature is also VALID.
  2. If we change either CoreSign or Aggregate to only CoreSign, it seems the point at infinity signature is INVALID since CoreSign disallows SK=0?

Thank you for your time again. :)

kirk-baird commented

You may run into an interesting case if you prevent Signatures from being infinity.

Take the example a user creates Key1 = a and Key2 = -a.

We can create two signatures for any message Sig1 and Sig2 and we'll have the case where Sig1 = -Sig2
(i.e. Sig1 + Sig2 = infinity).

So when we aggregate them we have Aggregate(Sig1, Sig2) = infinity.

Hence, if we disallowed infinity as a signature we could end up with two valid secret keys, two valid signatures but an invalid aggregate signature.

Now this could also be applied for any combination of Secret Keys which when summed are a multiple of the curve order. So it is possible (albeit negligible) that there may be a genuine case where users may have randomly chosen signatures which when summed are infinity.

  • 👍2
kwantam commented

@kirk-baird is correct. The point at infinity is a valid aggregate signature because it is the sum of two valid signatures. I believe this answers (2) above, but please let me know if I am wrong.

With respect to (1), @hwwhww, I am not sure what you mean by "deadlock," and I do not see any issue with the definition of Aggregate as written. It is not true that any octet-string is valid, because the output is given by point_to_signature(aggregate), and meanwhile aggregate is guaranteed by the definition of signature_to_point to be a valid point in the appropriate subgroup. So it would be correct to say that any valid encoding of a point in the signature subgroup is valid, which is equivalent to the definition given.

Does this help? Happy to chat more.

hwwhww commented

Thank you @kirk-baird and @kwantam for the great clarification!

By deadlock I meant, if I want to validate the valid input parameter format before I call Aggregate: to get the valid domain of the inputs signature_1, ..., signature_n of Aggregate, I need to know the domain of the valid outputs of Aggregate. But to know the possible domain of the valid outputs, I need to execute Aggregate to know the possible domain ahead.

The ambiguity to me is that we see the Aggregate inputs description: "signature_1, ..., signature_n, octet strings output by either CoreSign or Aggregate", we take it as a strict condition of the valid inputs domain. The spec also used "in the format output X" for other function descriptions. Does that mean we only have to check the input “format” (e.g., 96 bytes signature if it’s G2) + preconditions before we call the procedure? (signature_to_point and point_to_signature are checked in the procedure)

Thanks!

kwantam commented

By deadlock I meant, if I want to validate the valid input parameter format before I call Aggregate: to get the valid domain of the inputs signature_1, ..., signature_n of Aggregate, I need to know the domain of the valid outputs of Aggregate. But to know the possible domain of the valid outputs, I need to execute Aggregate to know the possible domain ahead.

Well, this is not true. It is possible to reason statically (i.e., without knowing specific values) about valid inputs to and outputs from this function. In particular, by construction Aggregate will only output a correct encoding (because of the call to point_to_signature) of the sum of points in the correct subgroup (because of the validity conditions enforced by signature_to_point).

Whether or not you have to check the lengths of inputs to procedures, etc., is implementation dependent. Some implementations can guarantee well formed inputs with typing rules plus, potentially, some small number of run-time checks. Other implementations, lacking type annotations, may require dynamic checks as part of the Aggregate implementation. The standard is silent on this because it is an implementation detail.

Does this clarify? I may be misunderstanding your questions, in which case I apologize. In any event, happy to chat more.

hwwhww commented

@kwantam

I can understand and admire that it's elegant to define a function with another well-defined function. (it's much less verbose!) but when implementing it, we are translating it into API documents so we want to ensure we didn't miss anything.

In particular, by construction Aggregate will only output a correct encoding (because of the call to point_to_signature) of the sum of points in the correct subgroup (because of the validity conditions enforced by signature_to_point).

Could you confirm that "the valid signature input of Aggregate function should be able to pass point_to_signature and signature_to_point"? If so, it's clear to me! 🙂

Whether or not you have to check the lengths of inputs to procedures, etc., is implementation dependent. Some implementations can guarantee well formed inputs with typing rules plus, potentially, some small number of run-time checks. Other implementations, lacking type annotations, may require dynamic checks as part of the Aggregate implementation. The standard is silent on this because it is an implementation detail.

Agreed!

Another example, the CoreVerify of the basic scheme (not PoP scheme) function input:

Inputs:
   - PK, a public key in the format output by SkToPk.

Does that mean the PK input of CoreVerify should be:

  1. Follow the "format" of SkToPk, that is, "a public key encoded as an octet string". Or
  2. (1) + since the point at infinity PK is not an output of SkToPk, the point at infinity PK is also disallowed for CoreVerify.

?

kwantam commented

Could you confirm that "the valid signature input of Aggregate function should be able to pass point_to_signature and signature_to_point"? If so, it's clear to me! slightly_smiling_face

I think this is the right idea, but I'm not 100% sure what you mean by "pass". So I'll try to restate back to you what I think you mean:

  • the output of Aggregate is a valid input to signature_to_point
  • the output of Aggregate is a valid output from point_to_signature
  • the output of Aggregate is the result of summing several elliptic curve points, each of which is a valid output from signature_to_point, and then passing the sum as the input to point_to_signature

Does this make sense? Does it look like I am missing an invariant that you were expecting?

The PK input to CoreVerify just needs to be in the format that SkToPk outputs. If PK is the point at infinity, CoreVerify will return INVALID because of the call to KeyValidate in step 4.

hwwhww commented

Does this make sense? Does it look like I am missing an invariant that you were expecting?

Correct, that's what I meant. :)

The PK input to CoreVerify just needs to be in the format that SkToPk outputs. If PK is the point at infinity, CoreVerify will return INVALID because of the call to KeyValidate in step 4.

Got it. 👍

Thank you @kwantam!
I'm closing this issue now. Feel free to reopen it if anyone still has questions.