feedback from Dan

[kwantam]

A couple points of feedback from Dan:

1. Should include suites for more pairing-friendly curves, since BLS signatures are one of the common use cases. We've also heard this from Michael Scott. Probably makes sense to define suites for all of the curves in the pairing-friendly curves document.

2. "Nonuniform encoding" vs "random-oracle encoding" is the wrong terminology. The reason is, the "nonuniform encoding" is also a random oracle---it's just one that has a nonuniform output distribution. This is important because the current text does not communicate the security properties of the encoding in a way that is useful to people specifying future documents. We've also heard this feedback from Leo Reyzin; we made some tweaks to the text in response, but probably not enough.

For the first one, the action is pretty simple: just write down suites for the extra curves!

For the second one, the edits will be more extensive but the main change would be to the names we use in Section 3 (most of the edits will be propagating this terminology elsewhere).

Dan proposed "nonuniform encoding" and "uniform encoding" for NU and RO, respectively. Then we can add text in Section 3 and maybe Section 10 discussing the specific properties we get from each.

Thoughts?

[armfazh]

Agree, note that adding suites in the pf-draft will exemplify how to create a suite following the recommendations given in the h2c draft.

For the second, is there a way to make a conection with the term hashing? Both encodings are deterministic hash functions, one of them is indiferentiable from a random oracle. Does the terms proposed are closely related to standard definitions, e.g. https://eprint.iacr.org/2003/161 ?

[kwantam]

Agree, note that adding suites in the pf-draft will exemplify how to create a suite following the recommendations given in the h2c draft.

Ah, sorry that my initial statement was ambiguous. I think it would be good to define suites for those curves in h2c, since the pairing-friendly curves draft is nearing completion.

For the second, is there a way to make a conection with the term hashing? Both encodings are deterministic hash functions, one of them is indiferentiable from a random oracle.

The issue is, the term "hashing" is not really a well-defined technical term. For example, both of them are resistant to collisions and preimages, but they have other properties, too, e.g., it's infeasible to find inputs s.t. the output points satisfy any algebraic relation. And indeed both are indifferentiable from random oracles (as long as hash_to_field works correctly), it's just that one of the oracles has a nonuniform output distribution (but this is still a perfectly valid random oracle!).

I will take a look at the paper you referenced and post another reply soon.

[kwantam]

Ah, right, I'm familiar with MRH03. So I think what's going on is as stated above---both are indifferentiable.

---

Sketching the simulator for encode_to_curve (this is nearly the same as the simulator from BCIMRT10): suppose that we have an ideal algorithm H that on input msg in {0,1}^* selects a point in the image of map_to_curve with an output distribution matching the one induced by map_to_curve when inputs range uniformly over F. The simulator's job is, roughly, to "explain" how this point came from h, the hash_to_field random oracle.

On a fresh query msg in {0,1}^*, the simulator queries H(msg) and gets a point P that is in the image of map_to_curve. It then computes the preimages of P under map_to_curve---these are elements u of F such that map_to_curve(u) == P---picks one at random, and simulates h(msg) by replying with that value. Since H(msg) chooses P from the distribution induced by map_to_curve, this value of h(msg) is satistically close to uniform as required.

The only question remaining is, can the simulator invert map_to_curve efficiently? The answer is yes in all cases: Elligator 2 is easy to invert, and Tibouchi shows in Elligator Squared that both SvdW and SWU can be inverted efficiently.

(Note that I'm implicitly using composition of indifferentiability above: we know that hash_to_field is indifferentiable, so this means the simulated value h(msg) can itself be simulated in terms of the underlying random oracle, e.g., the SHA-2 compression function.)

[chris-wood]

Dan proposed "nonuniform encoding" and "uniform encoding" for NU and RO, respectively. Then we can add text in Section 3 and maybe Section 10 discussing the specific properties we get from each.

I like this change, even though it is a bit more invasive. The notion of a uniform distribution is probably easier to understand than Random Oracle, which might make choosing the right encoding less error-prone.

[armfazh]

After going through the papers, I think the key point on the distinction betwen encode_to_curve and hash_to_curve is that one of them is constructed using an admissible encoding (under Def 4 of BCIMRT10). Def 4 augments the previous definition by requiring the Regular property. This property ensures that the output distributions are unifom. So, being more technical, we can say that hash_to_curve is constructed with an admissible encoding function. However, just saying that the encoding is uniform, it seems to have the same meaning. So I am in favor to replace the names.

Also the important fact is not whether encode_to_curve and hash_to_curve are random-oracles (yes, both are), but instead we must communicate in the draft that the distinction is on whether or not they can be used to replace an ideal primitive of a hash function in the random oracle model.

Finally, the indifferentiability property seems to follow easily, as it does not take into account the probability distribution of outputs. So this argument is orthogonal, and we might not require an explicit proof of indifferentiability in the document.

I left some suggestions in the PR too.