Algorithm for permissibility function for input pubkeys

Both the original paper and the code assume that the input elements of the set used as leaves of the curve tree are already permissible points.

Thus if your input values (curve points) are not permissible, converting them to permissible is "left as an exercise for the reader", so to say.

However the conversion of points created as the tree is traversed, into permissible, is handled in the code using this simple algorithm:

define f(pt):
while (pt is not permissible)
  pt = pt + H
return pt

where H is the generator for the randomness of the Pedersen commitment.

This function f is not viable as a hash of the initial public key for the leaf, however, since it isn't in any sense a cryptographic hash - it doesn't have second preimage resistance. Speaking less fancily, if the value of f(P) is P+3H, then clearly the value of f(P+H) is also P+3H. So we have second preimages.

Does this matter? I think the answer is similar to the concern in #2 , i.e. it is not a problem for the full protocol including Ped-DLEQ but it may or may not be a problem for other protocols using a Curve Tree.

If H is generated as NUMS, which it must be, then the user does not know the private key of P+H (staying in the hypothetical scenario where f() changes P to P+3H, so P+H is a second preimage, as are P+2H and P+3H), so if the algorithm here includes a proof of knowledge of the private key of P, which it does in the form of the Ped-DLEQ attached protocol, then this second preimage cannot be used to create an overall valid proof.

All the same it is worth considering whether an alternative function to the f() described above, might be better, if it avoid such preimages.

AdamISZ / aut-ct

Algorithm for permissibility function for input pubkeys #3