2
$\begingroup$

I've been thinking about verifiable random functions recently due to my interest in sortition (random selection of political officials). I wrote up this little paragraph below, and I'm wondering: Does this paragraph seem accurate? I'm not very confident in my thought process haha as I'm quite a newbie to cryptology and hadn't even heard of a VRF before yesterday.

If you do find problems in what follows, please let me know! I really want to understand at least the very basics of this correctly.


Of course, one time-honored method of random selection is to simply put some names in a big tub and mix them around. However, with recent advances in cryptology more sophisticated mechanisms could be used. In particular, verifiable random functions could be used to choose citizens. In general, the owner of a verifiable random function f employs a secret key and a chosen input x to compute f(x), which is essentially a random value. When x and f(x) are published, the owner also releases a proof that, combined with a previously disseminated public key, allows anyone to confirm that the published value f(x) was indeed correctly computed. However, the public never learns of the secret key and thus cannot evaluate the function for any input other than x. This is in part because verifiable random functions are a kind of “one-way function”: It is easy for the public to check the correctness of an output, but impossible for them to figure out how the function actually operates in general -- thereby preserving the secrecy and integrity of the procedure.

$\endgroup$
1
$\begingroup$

Sure VRFs can be used for sortition. One can say that a party is selected if the output of his VRF satisifies some property.

The VRF outputs two things - a random output and a proof that the output is computed correctly. It is not always the case that if the output of a VRF is f(x) the corresponding proof is x. For example, the VRF could simply output a pseudo random function $PRF_{sk}(x)$ along with a zero knowledge proof that the PRF was computed correctly.

"but impossible for them to figure out how the function actually operates in general" : This would not be accurate, everyone knows how the VRF operates, else how would one verify that the output is actually correct. In cryptography the working of a protocol is never hidden (Kerckhoff's principle)

You can find more information on VRFs here. This is a working IETF draft to standardize the construction of VRFs. They have some interesting constructions there.

Welcome to the community!

$\endgroup$
1
  • 2
    $\begingroup$ Moreover Algorand (eprint.iacr.org/2017/454) uses sortition to select a committee. This committee achieve consensus over the next block on the block chain. The authors have a nice article on VRFs. You should find that helpful too - medium.com/algorand/… $\endgroup$ – zkvroon Nov 12 '18 at 15:17
0
$\begingroup$

This only works if the person (or coordinating group) selecting the seed for the VRF doesn't have control over the indexing of the candidates or the choice of x.

If the person selecting the seed has control of the candidate indexing and knows x then they can make sure their prefered candidate is indexed at f(x) and is chosen. And if they have control over x and know the candidate indexing then they can choose an x such that f(x) is the index of their prefered candidate.

In the realm of sortition this becomes more of an issue because if you have a trusted coin and trusted flipper you can just have them flip the coin. The only reason you'd need to start using crypto methods is if you don't trust the central RNG. So to use VRF you have to trust that the choice of x and the indexing is out of the hands of whatever conspiracy has sabotaged (or would be able to sabotage) the central RNG.

I've been thinking about this a lot recently and have (mostly) come to the conclusion that it'll need to use more of the tools from multi-party coin flipping if you want to get verifiable RNG in a highly adversarial environment. I don't think VRF will cut it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.