search

fcelda / nsec5-draft

Working Copy of the NSEC5 Specification
15 stars 2 forks source link

the additional pseudorandomness property #28

Open goldbe opened 7 years ago

goldbe commented 7 years ago

I just added in aaa83e5b95dab2592aa8d9b63c43d2ef6961d637 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 commented 6 years ago

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

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.