Getting full uniqueness

[reyzin]

If we want to get rid of "trusted" in the "trusted uniqueness" for EC VRF, we can add some optional steps for the verifier, so that uniqueness can be assured even when key generation is not trusted.

There are three cases:

• Curve is well-established ahead of time, g is trusted, PK g^k is not trusted. This case is easiest: verify that PK is on curve, not point at infinity, and that PK^q is point at infinity.
• Curve is well-established ahead of time, g is not trusted, PK g^k is not trusted. Same as above, except for both g and g^k.
• Curve could have been picked adversarially. This is the hardest one to handle, because adversary could, in principle, first compute ECVRF_hash_points on some six "points" that aren't even on a well-defined curve and them try to find a curve that lets him violate uniqueness on these points. There is no known attack, but the proof doesn't go through, because the proof requires a well-defined notion of log that is fixed at the time ECVRF_hash_points is called (so that only one c can work). If we add a description of the curve to the hash input in ECVRF_hash_points, this problem goes away, but we have to be careful about what we mean by "description," to make sure the adversary really is committed to the curve. Here's an attack if we are not careful: the adversary decides a curve's name before the curve is even selected (e.g., SecureCurve256), uses it as a curve "description" during hashing, then finds an adversarial curve that allows him to cheat, then standardizes SecureCurve256 as the name for that adversarial curve by adding it to some future standard, and then finally cheats.

[fcelda]

We can probably turn this into question for the IETF community. Can we add it into slides as an open question @goldbe?

[goldbe]

We could! But honestly I think we can and should include it in the draft. It's not hard to include now for the EC-VRF that Leo and I have thought it through. Really the only thing holding us back is that I have not had the time to sit and write this yet. Let me sit and write it down first.

NOTE: we don't yet know how to do this with the RSA vrf!

[goldbe]

Addressed this in 1c7f40154032df14f66f8ce1dba0b5c217201ccc

[goldbe]

Note: the text that Leo wrote when opening this issue is outdated as it does not take into account the way we addressed cofactors in the current version of the draft. The definative way of dealing with untrusted keys in available in the latest version of the paper, which says to raise PK^cofactor and check its not 1, instead of raising PK^q and checking it is a point at infinity.

[goldbe]

I just corrected the draft to reflect this, see commit 4b85fb57407215d65e2a2c3cdb5f8b2045a30735