the additional pseudorandomness property

[goldbe]

I just added in aaa83e5 discussion of VRF security property that is used by some applications, but not for any of the applications that we (NSEC5) or the CONIKS folks are using.

This is a different type of pseudorandomness than that one we use. The pseudorandomness we use only holds if VRF keys are generated in correct way.

What this is, is pseudorandomness that must hold even if the VRF keys are generated adversarially, as long as the VRF input alpha is unpredictable.

Specifically, suppose the VRF keys are generated by an adversary. Then, a VRF hash output beta should look pseudorandom to the adversary as long as (1) its corresponding VRF hash alpha is chosen randomly and independently of the VRF key, (2) alpha is unknown to the adversary, (3) the corresponding proof pi is unknown to the adversary, and (4) the VRF public key chosen by the adversary is valid.

An additional TODO is to figure out what checks are needed to make sure the adversarially-chosen VRF public key is valid.

[goldbe]

@reyzin just talked to S. Gorbunov about this. What we had was not correct for algorand.
See commit 5aae74b

Here are some rough notes on how this might work.

Game one.
Suppose adv commits to key pk
Suppose alpha chosen randomly, made public
Adv computes VRF_proof_sk(alpha) = gamma
Should have that for most inputs alpha, you get a different gamma (ie gamma is unique)

Game 2:
Adversary commits to pk1 and pk2
Suppose that alpha chosen randomly, made public
Adv wins if VRF_proof_sk1(alpha) = gamma= VRF_sk2(alpha)

[Why algorand needs Game 2: to avoid the risk of all members of a malicious committee choosing a different pk that actually produces exactly the same VRF outputs. (collusion in the committee.)]

So now, if you want pseudorandomness in the output "even if the pk is chosen maliciously" (this needs to be formalized) then you change proof2hash so it becomes proof2hash(alpha, gamma, pk) . Currently we have proof2hash(gamma).

Notice that if (alpha, gamma, pk) is unique then by the randomness of the random oracle the output is well distributed.